FileDocCategorySizeDatePackage
DeadCodeRemover.javaAPI DocAndroid 5.1 API8521Thu Mar 12 22:18:30 GMT 2015com.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 final SsaMethod
ssaMeth
method we're processing
private final int
regCount
ssaMeth.getRegCount()
private final BitSet
worklist
indexed by register: whether reg should be examined (does it correspond to a no-side-effect insn?)
private final ArrayList[]
useList
use list indexed by register; modified during operation
Constructors Summary
private DeadCodeRemover(SsaMethod ssaMethod)
Constructs an instance.

param
ssaMethod method to process

        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 {@code 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 = new DeadCodeRemover(ssaMethod);
        dc.run();
private voidpruneDeadInstructions()
Removes all instructions from every unreachable block.

        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);
private voidrun()
Runs the dead code remover.

        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);