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

ConstCollector

public class ConstCollector extends Object
Collects constants that are used more than once at the top of the method block. This increases register usage by about 5% but decreases insn size by about 3%.

Fields Summary
private static final int
MAX_COLLECTED_CONSTANTS
Maximum constants to collect per method. Puts cap on reg use
private static boolean
COLLECT_STRINGS
Also collect string consts, although they can throw exceptions. This is off now because it just doesn't seem to gain a whole lot. TODO if you turn this on, you must change SsaInsn.hasSideEffect() to return false for const-string insns whose exceptions are not caught in the current method.
private static boolean
COLLECT_ONE_LOCAL
If true, allow one local var to be involved with a collected const. Turned off because it mostly just inserts more moves.
private final SsaMethod
ssaMeth
method we're processing
Constructors Summary
private ConstCollector(SsaMethod ssaMethod)

        this.ssaMeth = ssaMethod;
Methods Summary
private voidfixLocalAssignment(RegisterSpec origReg, RegisterSpec newReg)
Inserts mark-locals if necessary when changing a register. If the definition of origReg is associated with a local variable, then insert a mark-local for newReg just below it. We expect the definition of origReg to ultimately be removed by the dead code eliminator

param
origReg non-null; original register
param
newReg non-null; new register that will replace origReg

        for (SsaInsn use: ssaMeth.getUseListForRegister(origReg.getReg())) {
            RegisterSpec localAssignment = use.getLocalAssignment();
            if (localAssignment == null) {
                continue;
            }

            if (use.getResult() == null) {
                // this is a mark-local. it will be updated when all uses
                // are updated
                continue;
            }

            LocalItem local = localAssignment.getLocalItem();

            /*
             * un-associate original use
             */
            use.setResultLocal(null);

            /*
             * now add a mark-local to the new reg immediately after
             */                       
            newReg = newReg.withLocalItem(local);

            SsaInsn newInsn
                    = SsaInsn.makeFromRop(
                        new PlainInsn(Rops.opMarkLocal(newReg),
                        SourcePosition.NO_INFO, null,
                                RegisterSpecList.make(newReg)),
                    use.getBlock());

            ArrayList<SsaInsn> insns = use.getBlock().getInsns();

            insns.add(insns.indexOf(use) + 1, newInsn);
        }
private java.util.ArrayListgetConstsSortedByCountUse()
Gets all of the collectable constant values used in this method, sorted by most used first. Skips non-collectable consts, such as non-string object constants

return
non-null; list of constants in most-to-least used order

        int regSz = ssaMeth.getRegCount();

        final HashMap<TypedConstant, Integer> countUses
                = new HashMap<TypedConstant, Integer>();

        // Each collected constant can be used by just one local
        // (used only if COLLECT_ONE_LOCAL is true)
        final HashSet<TypedConstant> usedByLocal
                = new HashSet<TypedConstant>();

        // Count how many times each const value is used
        for (int i = 0; i < regSz; i++) {
            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

            if (insn == null) continue;

            RegisterSpec result = insn.getResult();

            TypeBearer typeBearer = insn.getResult().getTypeBearer();

            if (!typeBearer.isConstant()) continue;

            TypedConstant cst = (TypedConstant) typeBearer;

            if (insn.canThrow()) {
                /*
                 * Don't move anything other than strings -- the risk
                 * of changing where an exception is thrown is too high.                
                 */
                if (!(cst instanceof CstString) || !COLLECT_STRINGS) {
                    continue;
                }
                /*
                 * We can't move any throwable const whose throw will be caught,
                 * so don't count them.                 
                 */
                if (insn.getBlock().getSuccessors().cardinality() > 1) {
                    continue;
                }
            }

            // TODO might be nice to try and figure out which local wins most
            // when collected
            if (ssaMeth.isRegALocal(result)) {
                if (!COLLECT_ONE_LOCAL) {
                    continue;
                } else {
                    if (usedByLocal.contains(cst)) {
                        // Count one local usage only
                        continue;
                    } else {
                        usedByLocal.add(cst);
                    }
                }
            }

            Integer has = countUses.get(cst);
            if (has == null) {
                countUses.put(cst, 1);
            } else {
                countUses.put(cst, has + 1);
            }
        }

        // Collect constants that have been reused
        Iterator<TypedConstant> it = countUses.keySet().iterator();
        ArrayList<TypedConstant> constantList = new ArrayList<TypedConstant>();
        while (it.hasNext()) {
            TypedConstant cst = it.next();

            if (countUses.get(cst) > 1) {
                constantList.add(cst);
            }
        }

        // Sort by use, with most used at the beginning of the list
        Collections.sort(constantList, new Comparator<Constant>() {
            public int compare(Constant a, Constant b) {
                int ret;
                ret = countUses.get(b) - countUses.get(a);

                if (ret == 0) {
                    /*
                     * Provide sorting determinisim for constants with same
                     * usage count.
                     */
                    ret = a.compareTo(b);
                }

                return ret;
            }
            public boolean equals (Object obj) {
                return obj == this;
            }
        });
        return constantList;
public static voidprocess(SsaMethod ssaMethod)
Process a method.

param
ssaMethod non-null; method to process


                  
         
        ConstCollector dc;

        dc = new ConstCollector(ssaMethod);
            
        dc.run();
private voidrun()
Applies the optimization.

        int regSz = ssaMeth.getRegCount();

        ArrayList<TypedConstant> constantList
                = getConstsSortedByCountUse();
    
        int toCollect = Math.min(constantList.size(), MAX_COLLECTED_CONSTANTS);

        SsaBasicBlock start = ssaMeth.getEntryBlock();

        // Constant to new register containing the constant
        HashMap<TypedConstant, RegisterSpec> newRegs
                = new HashMap<TypedConstant, RegisterSpec> (toCollect);

        for (int i = 0; i < toCollect; i++) {
            TypedConstant cst = constantList.get(i);
            RegisterSpec result
                    = RegisterSpec.make(ssaMeth.makeNewSsaReg(), cst);

            Rop constRop = Rops.opConst(cst);

            if (constRop.getBranchingness() == Rop.BRANCH_NONE) {
                start.addInsnToHead(
                        new PlainCstInsn(Rops.opConst(cst),
                                SourcePosition.NO_INFO, result,
                                RegisterSpecList.EMPTY, cst));
            } else {
                // We need two new basic blocks along with the new insn
                SsaBasicBlock entryBlock = ssaMeth.getEntryBlock();
                SsaBasicBlock successorBlock
                        = entryBlock.getPrimarySuccessor();

                /*
                 * Insert a block containing the const insn
                 */
                SsaBasicBlock constBlock
                        = entryBlock.insertNewSuccessor(successorBlock);

                constBlock.replaceLastInsn(
                        new ThrowingCstInsn(constRop, SourcePosition.NO_INFO,
                                RegisterSpecList.EMPTY,
                                StdTypeList.EMPTY, cst));

                /*
                 * Insert a block containing the move-result-pseudo insn
                 */

                SsaBasicBlock resultBlock
                        = constBlock.insertNewSuccessor(successorBlock);

                resultBlock.addInsnToHead(
                        new PlainInsn(
                                Rops.opMoveResultPseudo(result.getTypeBearer()),
                                SourcePosition.NO_INFO,
                                result, RegisterSpecList.EMPTY));
            }

            newRegs.put(cst, result);
        }

        updateConstUses(newRegs, regSz);
private voidupdateConstUses(java.util.HashMap newRegs, int origRegCount)
Updates all uses of various consts to use the values in the newly assigned registers.

param
newRegs non-null; mapping between constant and new reg
param
origRegCount >=0; original SSA reg count, not including newly added constant regs


        // Set of constants associated with a local variable
        // Used only if COLLECT_ONE_LOCAL is true
        final HashSet<TypedConstant> usedByLocal
                = new HashSet<TypedConstant>();

        final ArrayList<SsaInsn>[] useList = ssaMeth.getUseListCopy();

        for (int i = 0; i < origRegCount; i++) {
            SsaInsn insn = ssaMeth.getDefinitionForRegister(i);

            if (insn == null) {
                continue;
            }

            final RegisterSpec origReg = insn.getResult();
            TypeBearer typeBearer = insn.getResult().getTypeBearer();

            if (!typeBearer.isConstant()) continue;

            TypedConstant cst = (TypedConstant) typeBearer;
            final RegisterSpec newReg = newRegs.get(cst);

            if (newReg == null) {
                continue;
            }

            if (ssaMeth.isRegALocal(origReg)) {
                if (!COLLECT_ONE_LOCAL) {
                    continue;                    
                } else {
                    // TODO if the same local gets the same cst multiple times,
                    // it would be nice to reuse the register
                    if (usedByLocal.contains(cst)) {
                        continue;
                    } else {
                        usedByLocal.add(cst);
                        fixLocalAssignment(origReg, newRegs.get(cst));
                    }
                }
            }

            // Maps an original const register to the new collected register
            RegisterMapper mapper = new RegisterMapper() {
                @Override
                public int getNewRegisterCount() {
                    return ssaMeth.getRegCount();
                }

                @Override
                public RegisterSpec map(RegisterSpec registerSpec) {
                    if (registerSpec.getReg() == origReg.getReg()) {
                        return newReg.withLocalItem(registerSpec.getLocalItem());
                    }

                    return registerSpec;
                }
            };

            for (SsaInsn use: useList[origReg.getReg()]) {
                if (use.canThrow()
                        && use.getBlock().getSuccessors().cardinality() > 1) {
                    continue;
                }
                use.mapSourceRegisters(mapper);
            }
        }