FileDocCategorySizeDatePackage
DeadCodeRemover.javaAPI DocAndroid 1.5 API7021Wed May 06 22:41:02 BST 2009com.android.dx.ssa

DeadCodeRemover

public class DeadCodeRemover extends Object
A variation on Appel Algorithm 19.12 "Dead code elimination in SSA form". TODO this algorithm is more efficient if run in reverse from exit block to entry block.

Fields Summary
private SsaMethod
ssaMeth
method we're processing
private int
regCount
ssaMeth.getRegCount()
private BitSet
worklist
indexed by register: whether reg should be examined (does it correspond to a no-side-effect insn?)
private ArrayList[]
useList
use list indexed by register; modified during operation
Constructors Summary
private DeadCodeRemover(SsaMethod ssaMethod)

        this.ssaMeth = ssaMethod;

        regCount = ssaMethod.getRegCount();

        worklist = new BitSet(regCount);

        useList = ssaMeth.getUseListCopy();
Methods Summary
private static booleanhasSideEffect(SsaInsn insn)
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 null-ok; instruction in question
return
true if it has a side-effect

        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();
private booleanisCircularNoSideEffect(int regV, java.util.BitSet set)
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

        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;
public static voidprocess(SsaMethod ssaMethod)
Process a method with the dead-code remver

param
ssaMethod method to process

        DeadCodeRemover dc;

        dc = new DeadCodeRemover(ssaMethod);
            
        dc.run();
private voidrun()
Run the dead code remover


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

        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 who's 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);