dx/src/com/android/jack/dx/ssa/DeadCodeRemover.java - toolchain/jack - Git at Google

 /*
  * Copyright (C) 2007 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.android.jack.dx.ssa;

 import com.android.jack.dx.rop.code.RegisterSpec;
 import com.android.jack.dx.rop.code.RegisterSpecList;

 import java.util.ArrayList;
 import java.util.BitSet;
 import java.util.HashSet;

 /**
  * A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form".
  *
  * TODO(dx team) this algorithm is more efficient if run in reverse from exit
  * block to entry block.
  */
 public class DeadCodeRemover {
   /** method we're processing */
   private final SsaMethod ssaMeth;

   /** ssaMeth.getRegCount() */
   private final int regCount;

   /**
    * indexed by register: whether reg should be examined
    * (does it correspond to a no-side-effect insn?)
    */
   private final BitSet worklist;

   /** use list indexed by register; modified during operation */
   private final ArrayList<SsaInsn>[] useList;

   /**
    * Process a method with the dead-code remver
    *
    * @param ssaMethod method to process
    */
   public static void process(SsaMethod ssaMethod) {
     DeadCodeRemover dc = new DeadCodeRemover(ssaMethod);
     dc.run();
   }

   /**
    * Constructs an instance.
    *
    * @param ssaMethod method to process
    */
   private DeadCodeRemover(SsaMethod ssaMethod) {
     this.ssaMeth = ssaMethod;

     regCount = ssaMethod.getRegCount();
     worklist = new BitSet(regCount);
     useList = ssaMeth.getUseListCopy();
   }

   /**
    * Runs the dead code remover.
    */
   private void run() {
     pruneDeadInstructions();

     HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

     ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist));

     int regV;

     while (0 <= (regV = worklist.nextSetBit(0))) {
       worklist.clear(regV);

       if (useList[regV].size() == 0 || isCircularNoSideEffect(regV, null)) {

         SsaInsn insnS = ssaMeth.getDefinitionForRegister(regV);

         // This insn has already been deleted.
         if (deletedInsns.contains(insnS)) {
           continue;
         }

         RegisterSpecList sources = insnS.getSources();

         int sz = sources.size();
         for (int i = 0; i < sz; i++) {
           // Delete this insn from all usage lists.
           RegisterSpec source = sources.get(i);
           useList[source.getReg()].remove(insnS);

           if (!hasSideEffect(ssaMeth.getDefinitionForRegister(source.getReg()))) {
             /*
              * Only registers whose definition has no side effect
              * should be added back to the worklist.
              */
             worklist.set(source.getReg());
           }
         }

         // Schedule this insn for later deletion.
         deletedInsns.add(insnS);
       }
     }

     ssaMeth.deleteInsns(deletedInsns);
   }

   /**
    * Removes all instructions from every unreachable block.
    */
   private void pruneDeadInstructions() {
     HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

     ssaMeth.computeReachability();

     for (SsaBasicBlock block : ssaMeth.getBlocks()) {
       if (block.isReachable()) {
         continue;
       }

       // Prune instructions from unreachable blocks
       for (int i = 0; i < block.getInsns().size(); i++) {
         SsaInsn insn = block.getInsns().get(i);
         RegisterSpecList sources = insn.getSources();
         int sourcesSize = sources.size();

         // Delete this instruction completely if it has sources
         if (sourcesSize != 0) {
           deletedInsns.add(insn);
         }

         // Delete this instruction from all usage lists.
         for (int j = 0; j < sourcesSize; j++) {
           RegisterSpec source = sources.get(j);
           useList[source.getReg()].remove(insn);
         }

         // Remove this instruction result from the sources of any phis
         RegisterSpec result = insn.getResult();
         if (result == null) {
           continue;
         }
         for (SsaInsn use : useList[result.getReg()]) {
           if (use instanceof PhiInsn) {
             PhiInsn phiUse = (PhiInsn) use;
             phiUse.removePhiRegister(result);
           }
         }
       }
     }

     ssaMeth.deleteInsns(deletedInsns);
   }

   /**
    * Returns true if the only uses of this register form a circle of
    * operations with no side effects.
    *
    * @param regV register to examine
    * @param set a set of registers that we've already determined
    * are only used as sources in operations with no side effect or null
    * if this is the first recursion
    * @return true if usage is circular without side effect
    */
   private boolean isCircularNoSideEffect(int regV, BitSet set) {
     if ((set != null) && set.get(regV)) {
       return true;
     }

     for (SsaInsn use : useList[regV]) {
       if (hasSideEffect(use)) {
         return false;
       }
     }

     if (set == null) {
       set = new BitSet(regCount);
     }

     // This register is only used in operations that have no side effect.
     set.set(regV);

     for (SsaInsn use : useList[regV]) {
       RegisterSpec result = use.getResult();

       if (result == null || !isCircularNoSideEffect(result.getReg(), set)) {
         return false;
       }
     }

     return true;
   }

   /**
    * Returns true if this insn has a side-effect. Returns true
    * if the insn is null for reasons stated in the code block.
    *
    * @param insn {@code null-ok;} instruction in question
    * @return true if it has a side-effect
    */
   private static boolean hasSideEffect(SsaInsn insn) {
     if (insn == null) {
       /* While false would seem to make more sense here, true
        * prevents us from adding this back to a worklist unnecessarally.
        */
       return true;
     }

     return insn.hasSideEffect();
   }

   /**
    * A callback class used to build up the initial worklist of
    * registers defined by an instruction with no side effect.
    */
   private static class NoSideEffectVisitor implements SsaInsn.Visitor {
     BitSet noSideEffectRegs;

     /**
      * Passes in data structures that will be filled out after
      * ssaMeth.forEachInsn() is called with this instance.
      *
      * @param noSideEffectRegs to-build bitset of regs that are
      * results of regs with no side effects
      */
     public NoSideEffectVisitor(BitSet noSideEffectRegs) {
       this.noSideEffectRegs = noSideEffectRegs;
     }

     /** {@inheritDoc} */
     @Override
     public void visitMoveInsn(NormalSsaInsn insn) {
       // If we're tracking local vars, some moves have side effects.
       if (!hasSideEffect(insn)) {
         noSideEffectRegs.set(insn.getResult().getReg());
       }
     }

     /** {@inheritDoc} */
     @Override
     public void visitPhiInsn(PhiInsn phi) {
       // If we're tracking local vars, then some phis have side effects.
       if (!hasSideEffect(phi)) {
         noSideEffectRegs.set(phi.getResult().getReg());
       }
     }

     /** {@inheritDoc} */
     @Override
     public void visitNonMoveInsn(NormalSsaInsn insn) {
       RegisterSpec result = insn.getResult();
       if (!hasSideEffect(insn) && result != null) {
         noSideEffectRegs.set(result.getReg());
       }
     }
   }
 }
	/*
	* Copyright (C) 2007 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.android.jack.dx.ssa;

	import com.android.jack.dx.rop.code.RegisterSpec;
	import com.android.jack.dx.rop.code.RegisterSpecList;

	import java.util.ArrayList;
	import java.util.BitSet;
	import java.util.HashSet;

	/**
	* A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form".
	*
	* TODO(dx team) this algorithm is more efficient if run in reverse from exit
	* block to entry block.
	*/
	public class DeadCodeRemover {
	/** method we're processing */
	private final SsaMethod ssaMeth;

	/** ssaMeth.getRegCount() */
	private final int regCount;

	/**
	* indexed by register: whether reg should be examined
	* (does it correspond to a no-side-effect insn?)
	*/
	private final BitSet worklist;

	/** use list indexed by register; modified during operation */
	private final ArrayList<SsaInsn>[] useList;

	/**
	* Process a method with the dead-code remver
	*
	* @param ssaMethod method to process
	*/
	public static void process(SsaMethod ssaMethod) {
	DeadCodeRemover dc = new DeadCodeRemover(ssaMethod);
	dc.run();
	}

	/**
	* Constructs an instance.
	*
	* @param ssaMethod method to process
	*/
	private DeadCodeRemover(SsaMethod ssaMethod) {
	this.ssaMeth = ssaMethod;

	regCount = ssaMethod.getRegCount();
	worklist = new BitSet(regCount);
	useList = ssaMeth.getUseListCopy();
	}

	/**
	* Runs the dead code remover.
	*/
	private void run() {
	pruneDeadInstructions();

	HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

	ssaMeth.forEachInsn(new NoSideEffectVisitor(worklist));

	int regV;

	while (0 <= (regV = worklist.nextSetBit(0))) {
	worklist.clear(regV);

	if (useList[regV].size() == 0 \|\| isCircularNoSideEffect(regV, null)) {

	SsaInsn insnS = ssaMeth.getDefinitionForRegister(regV);

	// This insn has already been deleted.
	if (deletedInsns.contains(insnS)) {
	continue;
	}

	RegisterSpecList sources = insnS.getSources();

	int sz = sources.size();
	for (int i = 0; i < sz; i++) {
	// Delete this insn from all usage lists.
	RegisterSpec source = sources.get(i);
	useList[source.getReg()].remove(insnS);

	if (!hasSideEffect(ssaMeth.getDefinitionForRegister(source.getReg()))) {
	/*
	* Only registers whose definition has no side effect
	* should be added back to the worklist.
	*/
	worklist.set(source.getReg());
	}
	}

	// Schedule this insn for later deletion.
	deletedInsns.add(insnS);
	}
	}

	ssaMeth.deleteInsns(deletedInsns);
	}

	/**
	* Removes all instructions from every unreachable block.
	*/
	private void pruneDeadInstructions() {
	HashSet<SsaInsn> deletedInsns = new HashSet<SsaInsn>();

	ssaMeth.computeReachability();

	for (SsaBasicBlock block : ssaMeth.getBlocks()) {
	if (block.isReachable()) {
	continue;
	}

	// Prune instructions from unreachable blocks
	for (int i = 0; i < block.getInsns().size(); i++) {
	SsaInsn insn = block.getInsns().get(i);
	RegisterSpecList sources = insn.getSources();
	int sourcesSize = sources.size();

	// Delete this instruction completely if it has sources
	if (sourcesSize != 0) {
	deletedInsns.add(insn);
	}

	// Delete this instruction from all usage lists.
	for (int j = 0; j < sourcesSize; j++) {
	RegisterSpec source = sources.get(j);
	useList[source.getReg()].remove(insn);
	}

	// Remove this instruction result from the sources of any phis
	RegisterSpec result = insn.getResult();
	if (result == null) {
	continue;
	}
	for (SsaInsn use : useList[result.getReg()]) {
	if (use instanceof PhiInsn) {
	PhiInsn phiUse = (PhiInsn) use;
	phiUse.removePhiRegister(result);
	}
	}
	}
	}

	ssaMeth.deleteInsns(deletedInsns);
	}

	/**
	* Returns true if the only uses of this register form a circle of
	* operations with no side effects.
	*
	* @param regV register to examine
	* @param set a set of registers that we've already determined
	* are only used as sources in operations with no side effect or null
	* if this is the first recursion
	* @return true if usage is circular without side effect
	*/
	private boolean isCircularNoSideEffect(int regV, BitSet set) {
	if ((set != null) && set.get(regV)) {
	return true;
	}

	for (SsaInsn use : useList[regV]) {
	if (hasSideEffect(use)) {
	return false;
	}
	}

	if (set == null) {
	set = new BitSet(regCount);
	}

	// This register is only used in operations that have no side effect.
	set.set(regV);

	for (SsaInsn use : useList[regV]) {
	RegisterSpec result = use.getResult();

	if (result == null \|\| !isCircularNoSideEffect(result.getReg(), set)) {
	return false;
	}
	}

	return true;
	}

	/**
	* Returns true if this insn has a side-effect. Returns true
	* if the insn is null for reasons stated in the code block.
	*
	* @param insn {@code null-ok;} instruction in question
	* @return true if it has a side-effect
	*/
	private static boolean hasSideEffect(SsaInsn insn) {
	if (insn == null) {
	/* While false would seem to make more sense here, true
	* prevents us from adding this back to a worklist unnecessarally.
	*/
	return true;
	}

	return insn.hasSideEffect();
	}

	/**
	* A callback class used to build up the initial worklist of
	* registers defined by an instruction with no side effect.
	*/
	private static class NoSideEffectVisitor implements SsaInsn.Visitor {
	BitSet noSideEffectRegs;

	/**
	* Passes in data structures that will be filled out after
	* ssaMeth.forEachInsn() is called with this instance.
	*
	* @param noSideEffectRegs to-build bitset of regs that are
	* results of regs with no side effects
	*/
	public NoSideEffectVisitor(BitSet noSideEffectRegs) {
	this.noSideEffectRegs = noSideEffectRegs;
	}

	/** {@inheritDoc} */
	@Override
	public void visitMoveInsn(NormalSsaInsn insn) {
	// If we're tracking local vars, some moves have side effects.
	if (!hasSideEffect(insn)) {
	noSideEffectRegs.set(insn.getResult().getReg());
	}
	}

	/** {@inheritDoc} */
	@Override
	public void visitPhiInsn(PhiInsn phi) {
	// If we're tracking local vars, then some phis have side effects.
	if (!hasSideEffect(phi)) {
	noSideEffectRegs.set(phi.getResult().getReg());
	}
	}

	/** {@inheritDoc} */
	@Override
	public void visitNonMoveInsn(NormalSsaInsn insn) {
	RegisterSpec result = insn.getResult();
	if (!hasSideEffect(insn) && result != null) {
	noSideEffectRegs.set(result.getReg());
	}
	}
	}
	}