FileDocCategorySizeDatePackage
IdenticalBlockCombiner.javaAPI DocAndroid 1.5 API5806Wed May 06 22:41:02 BST 2009com.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 com.android.dx.rop.code.RopMethod
ropMethod
private com.android.dx.rop.code.BasicBlockList
blocks
private com.android.dx.rop.code.BasicBlockList
newBlocks
Constructors Summary
public IdenticalBlockCombiner(com.android.dx.rop.code.RopMethod rm)
Constructs instance. Call process() to run.

param
rm 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;

            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 booleancompareInsns(com.android.dx.rop.code.BasicBlock a, com.android.dx.rop.code.BasicBlock b)

        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.

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