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

SCCP

public class SCCP extends Object
A small variant of Wegman and Zadeck's Sparse Conditional Constant Propagation algorithm.

Fields Summary
private static final int
TOP
Lattice values
private static final int
CONSTANT
private static final int
VARYING
private SsaMethod
ssaMeth
method we're processing
private int
regCount
ssaMeth.getRegCount()
private int[]
latticeValues
Lattice values for each SSA register
private com.android.dx.rop.cst.Constant[]
latticeConstants
For those registers that are constant, this is the constant value
private ArrayList
cfgWorklist
Worklist of basic blocks to be processed
private BitSet
executableBlocks
Bitset containing bits for each block that has been found executable
private ArrayList
ssaWorklist
Worklist for SSA edges. This is a list of registers to process
private ArrayList
varyingWorklist
Worklist for SSA edges that represent varying values. It makes the algorithm much faster if you move all values to VARYING as fast as possible.
Constructors Summary
private SCCP(SsaMethod ssaMeth)


       
        this.ssaMeth = ssaMeth;
        this.regCount = ssaMeth.getRegCount();
        this.latticeValues = new int[this.regCount];
        this.latticeConstants = new Constant[this.regCount];
        this.cfgWorklist = new ArrayList<SsaBasicBlock>();
        this.executableBlocks = new BitSet(ssaMeth.getBlocks().size());
        this.ssaWorklist = new ArrayList<SsaInsn>();
        this.varyingWorklist = new ArrayList<SsaInsn>();
        for (int i = 0; i < this.regCount; i++) {
            latticeValues[i] = TOP;
            latticeConstants[i] = null;
        }
Methods Summary
private voidaddBlockToWorklist(SsaBasicBlock ssaBlock)
Add a new SSA basic block to the CFG worklist

param
ssaBlock Block to add

        if (!executableBlocks.get(ssaBlock.getIndex())) {
            cfgWorklist.add(ssaBlock);
            executableBlocks.set(ssaBlock.getIndex());
        }
private voidaddUsersToWorklist(int reg, int latticeValue)
Adds an SSA register's uses to the SSA worklist.

param
reg SSA register
param
latticeValue new lattice value for @param reg.

        if (latticeValue == VARYING) {
            for (SsaInsn insn: ssaMeth.getUseListForRegister(reg)) {
                varyingWorklist.add(insn);
            }
        } else {
            for (SsaInsn insn: ssaMeth.getUseListForRegister(reg)) {
                ssaWorklist.add(insn);
            }
        }
private static java.lang.StringlatticeValName(int latticeVal)

        switch (latticeVal) {
            case TOP: return "TOP";
            case CONSTANT: return "CONSTANT";
            case VARYING: return "VARYING";
            default: return "UNKNOWN";
        }
public static voidprocess(SsaMethod ssaMethod)
Performs sparse conditional constant propagation on a method.

param
ssaMethod Method to process

        new SCCP(ssaMethod).run();
private voidreplaceConstants()
Replaces TypeBearers in source register specs with constant type bearers if possible. These are then referenced in later optimization steps.

        for (int reg = 0; reg < regCount; reg++) {            
            if (latticeValues[reg] != CONSTANT) {
                continue;
            }
            if (!(latticeConstants[reg] instanceof TypedConstant)) {
                // We can't do much with these
                continue;
            }

            SsaInsn defn = ssaMeth.getDefinitionForRegister(reg);
            TypeBearer typeBearer = defn.getResult().getTypeBearer();

            if (typeBearer.isConstant()) {
                /*
                 * The definition was a constant already.
                 * The uses should be as well.
                 */
                continue;
            }

            /*
             * Update the sources RegisterSpec's of all non-move uses.
             * These will be used in later steps.
             */
            for(SsaInsn insn: ssaMeth.getUseListForRegister(reg)) {
                if (insn.isPhiOrMove()) {
                    continue;
                }

                NormalSsaInsn nInsn = (NormalSsaInsn) insn;
                RegisterSpecList sources = insn.getSources();

                int index = sources.indexOfRegister(reg);

                RegisterSpec spec = sources.get(index);
                RegisterSpec newSpec
                        = spec.withType((TypedConstant)latticeConstants[reg]);


                nInsn.changeOneSource(index, newSpec);
            }
        }
private voidrun()

        SsaBasicBlock firstBlock = ssaMeth.getEntryBlock();
        addBlockToWorklist(firstBlock);

        /* Empty all the worklists by propagating our values */
        while (!cfgWorklist.isEmpty()
                || !ssaWorklist.isEmpty()
                || !varyingWorklist.isEmpty()) {
            while (!cfgWorklist.isEmpty()) {
                int listSize = cfgWorklist.size() - 1;
                SsaBasicBlock block = cfgWorklist.remove(listSize);
                simulateBlock(block);
            }
            while (!varyingWorklist.isEmpty()) {
                int listSize = varyingWorklist.size() - 1;
                SsaInsn insn = varyingWorklist.remove(listSize);

                if (!executableBlocks.get(insn.getBlock().getIndex())) {
                    continue;
                }

                if (insn instanceof PhiInsn) {
                    simulatePhi((PhiInsn)insn);
                } else {
                    simulateStmt(insn);
                }
            }
            while (!ssaWorklist.isEmpty()) {
                int listSize = ssaWorklist.size() - 1;
                SsaInsn insn = ssaWorklist.remove(listSize);

                if (!executableBlocks.get(insn.getBlock().getIndex())) {
                    continue;
                }

                if (insn instanceof PhiInsn) {
                    simulatePhi((PhiInsn)insn);
                } else {
                    simulateStmt(insn);
                }
            }
        }

        replaceConstants();
private booleansetLatticeValueTo(int reg, int value, com.android.dx.rop.cst.Constant cst)
Sets a lattice value for a register to value.

param
reg SSA register
param
value Lattice value
param
cst Constant value (may be null)
return
true if the lattice value changed.

        if (value != CONSTANT) {
            if (latticeValues[reg] != value) {
                latticeValues[reg] = value;
                return true;
            }
            return false;
        } else {
            if (latticeValues[reg] != value
                    || !latticeConstants[reg].equals(cst)) {
                latticeValues[reg] = value;
                latticeConstants[reg] = cst;
                return true;
            }
            return false;
        }
private booleansetLatticeValueTo(int reg, int value)

        return setLatticeValueTo(reg, value, null);
private com.android.dx.rop.code.InsnsimplifyJump(com.android.dx.rop.code.Insn insn)
Simplifies a jump statement.

param
insn jump to simplify
return
an instruction representing the simplified jump.

        return insn;
private voidsimulateBlock(SsaBasicBlock block)
Simulate a block and note the results in the lattice.

param
block Block to visit

        for (SsaInsn insn: block.getInsns()) {
            if (insn instanceof PhiInsn) {
                simulatePhi((PhiInsn) insn);
            } else {
                simulateStmt(insn);
            }
        }
private com.android.dx.rop.cst.ConstantsimulateMath(SsaInsn insn)
Simulates math insns, if possible.

param
insn non-null insn to simulate
return
constant result or null if not simulatable.

        Insn ropInsn = insn.getOriginalRopInsn();
        int opcode = insn.getOpcode().getOpcode();
        RegisterSpecList sources = insn.getSources();
        int regA = sources.get(0).getReg();
        Constant cA;
        Constant cB;

        if (latticeValues[regA] != CONSTANT) {
            cA = null;
        } else {
            cA = latticeConstants[regA];
        }

        if (sources.size() == 1) {
            CstInsn cstInsn = (CstInsn) ropInsn;
            cB = cstInsn.getConstant();
        } else { /* sources.size() == 2 */
            int regB = sources.get(1).getReg();
            if (latticeValues[regB] != CONSTANT) {
                cB = null;
            } else {
                cB = latticeConstants[regB];
            }
        }

        if (cA == null || cB == null) {
            //TODO handle a constant of 0 with MUL or AND
            return null;
        }

        switch (insn.getResult().getBasicType()) {
            case Type.BT_INT:
                int vR;
                boolean skip=false;

                int vA = ((CstInteger) cA).getValue();
                int vB = ((CstInteger) cB).getValue();

                switch (opcode) {
                    case RegOps.ADD:
                        vR = vA + vB;
                        break;
                    case RegOps.SUB:
                        vR = vA - vB;
                        break;
                    case RegOps.MUL:
                        vR = vA * vB;
                        break;
                    case RegOps.DIV:
                        if (vB == 0) {
                            skip = true;
                            vR = 0; // just to hide a warning
                        } else {
                            vR = vA / vB;
                        }
                        break;
                    case RegOps.AND:
                        vR = vA & vB;
                        break;
                    case RegOps.OR:
                        vR = vA | vB;
                        break;
                    case RegOps.XOR:
                        vR = vA ^ vB;
                        break;
                    case RegOps.SHL:
                        vR = vA << vB;
                        break;
                    case RegOps.SHR:
                        vR = vA >> vB;
                        break;
                    case RegOps.USHR:
                        vR = vA >>> vB;
                        break;
                    case RegOps.REM:
                        vR = vA % vB;
                        break;
                    default:
                        throw new RuntimeException("Unexpected op");
                }

                return skip ? null : CstInteger.make(vR);

            default:
                // not yet supported
                return null;
        }
private voidsimulatePhi(PhiInsn insn)
Simulates a PHI node and set the lattice for the result to the approriate value. Meet values: TOP x anything = anything VARYING x anything = VARYING CONSTANT x CONSTANT = CONSTANT if equal constants, VARYING otherwise

param
insn PHI to simulate.

        int phiResultReg = insn.getResult().getReg();

        if (latticeValues[phiResultReg] == VARYING) {
            return;
        }

        RegisterSpecList sources = insn.getSources();
        int phiResultValue = TOP;
        Constant phiConstant = null;
        int sourceSize = sources.size();
        for (int i = 0; i < sourceSize; i++) {
            int predBlockIndex = insn.predBlockIndexForSourcesIndex(i);
            int sourceReg = sources.get(i).getReg();
            int sourceRegValue = latticeValues[sourceReg];

            if (!executableBlocks.get(predBlockIndex)
                    || sourceRegValue == TOP) {
                continue;
            }

            if (sourceRegValue == CONSTANT) {
                if (phiConstant == null) {
                    phiConstant = latticeConstants[sourceReg];
                    phiResultValue = CONSTANT;
                 } else if (!latticeConstants[sourceReg].equals(phiConstant)){
                    phiResultValue = VARYING;
                    break;
                }

            } else if (sourceRegValue == VARYING) {
                phiResultValue = VARYING;
                break;
            }
        }
        if (setLatticeValueTo(phiResultReg, phiResultValue, phiConstant)) {
            addUsersToWorklist(phiResultReg, phiResultValue);
        }
private voidsimulateStmt(SsaInsn insn)
Simulates a statement and set the result lattice value.

param
insn instruction to simulate

        Insn ropInsn = insn.getOriginalRopInsn();
        if (ropInsn.getOpcode().getBranchingness() != Rop.BRANCH_NONE
                || ropInsn.getOpcode().isCallLike()) {
            ropInsn = simplifyJump (ropInsn);
            /* TODO: If jump becomes constant, only take true edge. */
            SsaBasicBlock block = insn.getBlock();
            int successorSize = block.getSuccessorList().size();
            for (int i = 0; i < successorSize; i++) {
                int successor = block.getSuccessorList().get(i);
                addBlockToWorklist(ssaMeth.getBlocks().get(successor));
            }
        }

        if (insn.getResult() == null) {
            return;
        }

        /* TODO: Simplify statements when possible using the constants. */
        int resultReg = insn.getResult().getReg();
        int resultValue = VARYING;
        Constant resultConstant = null;
        int opcode = insn.getOpcode().getOpcode();
        switch (opcode) {
            case RegOps.CONST: {
                CstInsn cstInsn = (CstInsn)ropInsn;
                resultValue = CONSTANT;
                resultConstant = cstInsn.getConstant();
                break;
            }
            case RegOps.MOVE: {
                if (insn.getSources().size() == 1) {
                    int sourceReg = insn.getSources().get(0).getReg();
                    resultValue = latticeValues[sourceReg];
                    resultConstant = latticeConstants[sourceReg];
                }
                break;
            }

            case RegOps.ADD:
            case RegOps.SUB:
            case RegOps.MUL:
            case RegOps.DIV:
            case RegOps.AND:
            case RegOps.OR:
            case RegOps.XOR:
            case RegOps.SHL:
            case RegOps.SHR:
            case RegOps.USHR:
            case RegOps.REM:

                resultConstant = simulateMath(insn);

                if (resultConstant == null) {
                    resultValue = VARYING;
                } else {
                    resultValue = CONSTANT;
                }
            break;
            /* TODO: Handle non-int arithmetic.
               TODO: Eliminate check casts that we can prove the type of. */
            default: {}
        }
        if (setLatticeValueTo(resultReg, resultValue, resultConstant)) {
            addUsersToWorklist(resultReg, resultValue);
        }