1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.ssa.back; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.BasicBlock; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.BasicBlockList; 21b0d01b0178081c98b8cdb2fba2d84f275a0c595ejeffhaoimport com.android.dx.rop.code.RegOps; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RopMethod; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Searches for basic blocks that all have the same successor and insns 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * but different predecessors. These blocks are then combined into a single 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block and the now-unused blocks are deleted. These identical blocks 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frequently are created when catch blocks are edge-split. 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class IdenticalBlockCombiner { 3399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final RopMethod ropMethod; 3499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final BasicBlockList blocks; 3599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final BasicBlockList newBlocks; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 3899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs instance. Call {@code process()} to run. 39de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 4099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param rm {@code non-null;} instance to process 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IdenticalBlockCombiner(RopMethod rm) { 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropMethod = rm; 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks = ropMethod.getBlocks(); 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks = blocks.getMutableCopy(); 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Runs algorithm. TODO: This is n^2, and could be made linear-ish with 5099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * a hash. In particular, hash the contents of each block and only 5199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * compare blocks with the same hash. 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 5399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} new method that has been processed 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RopMethod process() { 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szBlocks = blocks.size(); 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // indexed by label 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet toDelete = new BitSet(blocks.getMaxLabel()); 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // For each non-deleted block... 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int bindex = 0; bindex < szBlocks; bindex++) { 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock b = blocks.get(bindex); 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (toDelete.get(b.getLabel())) { 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // doomed block 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList preds = ropMethod.labelToPredecessors(b.getLabel()); 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ...look at all of it's predecessors that have only one succ... 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szPreds = preds.size(); 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szPreds; i++) { 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int iLabel = preds.get(i); 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock iBlock = blocks.labelToBlock(iLabel); 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (toDelete.get(iLabel) 7902f3081cc41387cf2d221a663493cd7458e0f796jeffhao || iBlock.getSuccessors().size() > 1 8002f3081cc41387cf2d221a663493cd7458e0f796jeffhao || iBlock.getFirstInsn().getOpcode().getOpcode() == 8102f3081cc41387cf2d221a663493cd7458e0f796jeffhao RegOps.MOVE_RESULT) { 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList toCombine = new IntList(); 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ...and see if they can be combined with any other preds... 8899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int j = i + 1; j < szPreds; j++) { 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int jLabel = preds.get(j); 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock jBlock = blocks.labelToBlock(jLabel); 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (jBlock.getSuccessors().size() == 1 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && compareInsns(iBlock, jBlock)) { 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toCombine.add(jLabel); 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toDelete.set(jLabel); 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project combineBlocks(iLabel, toCombine); 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 10499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int i = szBlocks - 1; i >= 0; i--) { 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (toDelete.get(newBlocks.get(i).getLabel())) { 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.set(i, null); 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.shrinkToFit(); 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.setImmutable(); 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new RopMethod(newBlocks, ropMethod.getFirstLabel()); 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 11699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 11799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Helper method to compare the contents of two blocks. 118de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 11999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param a {@code non-null;} a block to compare 12099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param b {@code non-null;} another block to compare 12199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the two blocks' instructions are the same 12299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 12399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private static boolean compareInsns(BasicBlock a, BasicBlock b) { 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return a.getInsns().contentEquals(b.getInsns()); 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Combines blocks proven identical into one alpha block, re-writing 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * all of the successor links that point to the beta blocks to point 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the alpha block instead. 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param alphaLabel block that will replace all the beta block 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param betaLabels label list of blocks to combine 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void combineBlocks(int alphaLabel, IntList betaLabels) { 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szBetas = betaLabels.size(); 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szBetas; i++) { 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int betaLabel = betaLabels.get(i); 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = blocks.labelToBlock(betaLabel); 14199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project IntList preds = ropMethod.labelToPredecessors(bb.getLabel()); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szPreds = preds.size(); 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szPreds; j++) { 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock predBlock = newBlocks.labelToBlock(preds.get(j)); 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project replaceSucc(predBlock, betaLabel, alphaLabel); 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replaces one of a block's successors with a different label. Constructs 15399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * an updated BasicBlock instance and places it in {@code newBlocks}. 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param block block to replace 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldLabel label of successor to replace 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newLabel label of new successor 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void replaceSucc(BasicBlock block, int oldLabel, int newLabel) { 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSuccessors = block.getSuccessors().mutableCopy(); 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newPrimarySuccessor; 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSuccessors.set(newSuccessors.indexOf(oldLabel), newLabel); 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPrimarySuccessor = block.getPrimarySuccessor(); 16599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newPrimarySuccessor == oldLabel) { 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPrimarySuccessor = newLabel; 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSuccessors.setImmutable(); 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock newBB = new BasicBlock(block.getLabel(), 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project block.getInsns(), newSuccessors, newPrimarySuccessor); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.set(newBlocks.indexOfLabel(block.getLabel()), newBB); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 178