FileDocCategorySizeDatePackage
IdenticalBlockCombiner.javaAPI DocAndroid 5.1 API6233Thu Mar 12 22:18:30 GMT 2015com.android.dx.ssa.back

IdenticalBlockCombiner

public class IdenticalBlockCombiner extends Object
Searches for basic blocks that all have the same successor and insns but different predecessors. These blocks are then combined into a single block and the now-unused blocks are deleted. These identical blocks frequently are created when catch blocks are edge-split.

Fields Summary
private final com.android.dx.rop.code.RopMethod
ropMethod
private final com.android.dx.rop.code.BasicBlockList
blocks
private final com.android.dx.rop.code.BasicBlockList
newBlocks
Constructors Summary
public IdenticalBlockCombiner(com.android.dx.rop.code.RopMethod rm)
Constructs instance. Call {@code process()} to run.

param
rm {@code non-null;} instance to process

        ropMethod = rm;
        blocks = ropMethod.getBlocks();
        newBlocks = blocks.getMutableCopy();
Methods Summary
private voidcombineBlocks(int alphaLabel, com.android.dx.util.IntList betaLabels)
Combines blocks proven identical into one alpha block, re-writing all of the successor links that point to the beta blocks to point to the alpha block instead.

param
alphaLabel block that will replace all the beta block
param
betaLabels label list of blocks to combine

        int szBetas = betaLabels.size();

        for (int i = 0; i < szBetas; i++) {
            int betaLabel = betaLabels.get(i);
            BasicBlock bb = blocks.labelToBlock(betaLabel);
            IntList preds = ropMethod.labelToPredecessors(bb.getLabel());
            int szPreds = preds.size();

            for (int j = 0; j < szPreds; j++) {
                BasicBlock predBlock = newBlocks.labelToBlock(preds.get(j));
                replaceSucc(predBlock, betaLabel, alphaLabel);
            }
        }
private static booleancompareInsns(com.android.dx.rop.code.BasicBlock a, com.android.dx.rop.code.BasicBlock b)
Helper method to compare the contents of two blocks.

param
a {@code non-null;} a block to compare
param
b {@code non-null;} another block to compare
return
{@code true} iff the two blocks' instructions are the same

        return a.getInsns().contentEquals(b.getInsns());
public com.android.dx.rop.code.RopMethodprocess()
Runs algorithm. TODO: This is n^2, and could be made linear-ish with a hash. In particular, hash the contents of each block and only compare blocks with the same hash.

return
{@code non-null;} new method that has been processed

        int szBlocks = blocks.size();
        // indexed by label
        BitSet toDelete = new BitSet(blocks.getMaxLabel());

        // For each non-deleted block...
        for (int bindex = 0; bindex < szBlocks; bindex++) {
            BasicBlock b = blocks.get(bindex);

            if (toDelete.get(b.getLabel())) {
                // doomed block
                continue;
            }

            IntList preds = ropMethod.labelToPredecessors(b.getLabel());

            // ...look at all of it's predecessors that have only one succ...
            int szPreds = preds.size();
            for (int i = 0; i < szPreds; i++) {
                int iLabel = preds.get(i);

                BasicBlock iBlock = blocks.labelToBlock(iLabel);

                if (toDelete.get(iLabel)
                        || iBlock.getSuccessors().size() > 1
                        || iBlock.getFirstInsn().getOpcode().getOpcode() ==
                            RegOps.MOVE_RESULT) {
                    continue;
                }

                IntList toCombine = new IntList();

                // ...and see if they can be combined with any other preds...
                for (int j = i + 1; j < szPreds; j++) {
                    int jLabel = preds.get(j);
                    BasicBlock jBlock = blocks.labelToBlock(jLabel);

                    if (jBlock.getSuccessors().size() == 1
                            && compareInsns(iBlock, jBlock)) {

                        toCombine.add(jLabel);
                        toDelete.set(jLabel);
                    }
                }

                combineBlocks(iLabel, toCombine);
            }
        }

        for (int i = szBlocks - 1; i >= 0; i--) {
            if (toDelete.get(newBlocks.get(i).getLabel())) {
                newBlocks.set(i, null);
            }
        }

        newBlocks.shrinkToFit();
        newBlocks.setImmutable();

        return new RopMethod(newBlocks, ropMethod.getFirstLabel());
private voidreplaceSucc(com.android.dx.rop.code.BasicBlock block, int oldLabel, int newLabel)
Replaces one of a block's successors with a different label. Constructs an updated BasicBlock instance and places it in {@code newBlocks}.

param
block block to replace
param
oldLabel label of successor to replace
param
newLabel label of new successor

        IntList newSuccessors = block.getSuccessors().mutableCopy();
        int newPrimarySuccessor;

        newSuccessors.set(newSuccessors.indexOf(oldLabel), newLabel);
        newPrimarySuccessor = block.getPrimarySuccessor();

        if (newPrimarySuccessor == oldLabel) {
            newPrimarySuccessor = newLabel;
        }

        newSuccessors.setImmutable();

        BasicBlock newBB = new BasicBlock(block.getLabel(),
                block.getInsns(), newSuccessors, newPrimarySuccessor);

        newBlocks.set(newBlocks.indexOfLabel(block.getLabel()), newBB);