1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.ssa.back; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.BasicBlock; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.BasicBlockList; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.CstInsn; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.Insn; 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.InsnList; 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RegOps; 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.RopMethod; 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.rop.code.SwitchInsn; 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport java.util.BitSet; 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Searches for basic blocks that all have the same successor and insns 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * but different predecessors. These blocks are then combined into a single 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * block and the now-unused blocks are deleted. These identical blocks 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * frequently are created when catch blocks are edge-split. 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic class IdenticalBlockCombiner { 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final RopMethod ropMethod; 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BasicBlockList blocks; 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BasicBlockList newBlocks; 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs instance. Call {@code process()} to run. 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param rm {@code non-null;} instance to process 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IdenticalBlockCombiner(RopMethod rm) { 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson ropMethod = rm; 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson blocks = ropMethod.getBlocks(); 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlocks = blocks.getMutableCopy(); 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Runs algorithm. TODO: This is n^2, and could be made linear-ish with 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * a hash. In particular, hash the contents of each block and only 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * compare blocks with the same hash. 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} new method that has been processed 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public RopMethod process() { 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szBlocks = blocks.size(); 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // indexed by label 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BitSet toDelete = new BitSet(blocks.getMaxLabel()); 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // For each non-deleted block... 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int bindex = 0; bindex < szBlocks; bindex++) { 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock b = blocks.get(bindex); 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (toDelete.get(b.getLabel())) { 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // doomed block 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList preds = ropMethod.labelToPredecessors(b.getLabel()); 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // ...look at all of it's predecessors that have only one succ... 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szPreds = preds.size(); 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szPreds; i++) { 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int iLabel = preds.get(i); 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock iBlock = blocks.labelToBlock(iLabel); 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (toDelete.get(iLabel) 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || iBlock.getSuccessors().size() > 1 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson || iBlock.getFirstInsn().getOpcode().getOpcode() == 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RegOps.MOVE_RESULT) { 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson continue; 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList toCombine = new IntList(); 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // ...and see if they can be combined with any other preds... 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = i + 1; j < szPreds; j++) { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int jLabel = preds.get(j); 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock jBlock = blocks.labelToBlock(jLabel); 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (jBlock.getSuccessors().size() == 1 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson && compareInsns(iBlock, jBlock)) { 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toCombine.add(jLabel); 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson toDelete.set(jLabel); 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson combineBlocks(iLabel, toCombine); 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = szBlocks - 1; i >= 0; i--) { 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (toDelete.get(newBlocks.get(i).getLabel())) { 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlocks.set(i, null); 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlocks.shrinkToFit(); 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlocks.setImmutable(); 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return new RopMethod(newBlocks, ropMethod.getFirstLabel()); 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Helper method to compare the contents of two blocks. 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param a {@code non-null;} a block to compare 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param b {@code non-null;} another block to compare 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code true} iff the two blocks' instructions are the same 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private static boolean compareInsns(BasicBlock a, BasicBlock b) { 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return a.getInsns().contentEquals(b.getInsns()); 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Combines blocks proven identical into one alpha block, re-writing 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * all of the successor links that point to the beta blocks to point 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * to the alpha block instead. 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param alphaLabel block that will replace all the beta block 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param betaLabels label list of blocks to combine 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void combineBlocks(int alphaLabel, IntList betaLabels) { 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szBetas = betaLabels.size(); 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < szBetas; i++) { 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int betaLabel = betaLabels.get(i); 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock bb = blocks.labelToBlock(betaLabel); 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList preds = ropMethod.labelToPredecessors(bb.getLabel()); 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int szPreds = preds.size(); 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = 0; j < szPreds; j++) { 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock predBlock = newBlocks.labelToBlock(preds.get(j)); 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson replaceSucc(predBlock, betaLabel, alphaLabel); 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Replaces one of a block's successors with a different label. Constructs 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * an updated BasicBlock instance and places it in {@code newBlocks}. 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param block block to replace 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param oldLabel label of successor to replace 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param newLabel label of new successor 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void replaceSucc(BasicBlock block, int oldLabel, int newLabel) { 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList newSuccessors = block.getSuccessors().mutableCopy(); 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int newPrimarySuccessor; 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSuccessors.set(newSuccessors.indexOf(oldLabel), newLabel); 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPrimarySuccessor = block.getPrimarySuccessor(); 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (newPrimarySuccessor == oldLabel) { 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newPrimarySuccessor = newLabel; 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newSuccessors.setImmutable(); 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock newBB = new BasicBlock(block.getLabel(), 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson block.getInsns(), newSuccessors, newPrimarySuccessor); 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson newBlocks.set(newBlocks.indexOfLabel(block.getLabel()), newBB); 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 183