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; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.CstInsn; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.Insn; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.InsnList; 24b0d01b0178081c98b8cdb2fba2d84f275a0c595ejeffhaoimport com.android.dx.rop.code.RegOps; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RopMethod; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.SwitchInsn; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.BitSet; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Searches for basic blocks that all have the same successor and insns 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * but different predecessors. These blocks are then combined into a single 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * block and the now-unused blocks are deleted. These identical blocks 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * frequently are created when catch blocks are edge-split. 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic class IdenticalBlockCombiner { 3899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final RopMethod ropMethod; 3999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final BasicBlockList blocks; 4099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private final BasicBlockList newBlocks; 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs instance. Call {@code process()} to run. 44de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 4599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param rm {@code non-null;} instance to process 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IdenticalBlockCombiner(RopMethod rm) { 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ropMethod = rm; 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project blocks = ropMethod.getBlocks(); 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks = blocks.getMutableCopy(); 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 5499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Runs algorithm. TODO: This is n^2, and could be made linear-ish with 5599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * a hash. In particular, hash the contents of each block and only 5699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * compare blocks with the same hash. 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 5899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} new method that has been processed 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RopMethod process() { 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szBlocks = blocks.size(); 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // indexed by label 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BitSet toDelete = new BitSet(blocks.getMaxLabel()); 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // For each non-deleted block... 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int bindex = 0; bindex < szBlocks; bindex++) { 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock b = blocks.get(bindex); 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (toDelete.get(b.getLabel())) { 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // doomed block 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList preds = ropMethod.labelToPredecessors(b.getLabel()); 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ...look at all of it's predecessors that have only one succ... 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szPreds = preds.size(); 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szPreds; i++) { 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int iLabel = preds.get(i); 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock iBlock = blocks.labelToBlock(iLabel); 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 8399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project if (toDelete.get(iLabel) 8402f3081cc41387cf2d221a663493cd7458e0f796jeffhao || iBlock.getSuccessors().size() > 1 8502f3081cc41387cf2d221a663493cd7458e0f796jeffhao || iBlock.getFirstInsn().getOpcode().getOpcode() == 8602f3081cc41387cf2d221a663493cd7458e0f796jeffhao RegOps.MOVE_RESULT) { 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList toCombine = new IntList(); 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // ...and see if they can be combined with any other preds... 9399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int j = i + 1; j < szPreds; j++) { 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int jLabel = preds.get(j); 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock jBlock = blocks.labelToBlock(jLabel); 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (jBlock.getSuccessors().size() == 1 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && compareInsns(iBlock, jBlock)) { 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toCombine.add(jLabel); 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project toDelete.set(jLabel); 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project combineBlocks(iLabel, toCombine); 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 10999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project for (int i = szBlocks - 1; i >= 0; i--) { 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (toDelete.get(newBlocks.get(i).getLabel())) { 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.set(i, null); 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.shrinkToFit(); 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.setImmutable(); 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new RopMethod(newBlocks, ropMethod.getFirstLabel()); 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 12199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** 12299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Helper method to compare the contents of two blocks. 123de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 12499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param a {@code non-null;} a block to compare 12599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param b {@code non-null;} another block to compare 12699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the two blocks' instructions are the same 12799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project */ 12899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project private static boolean compareInsns(BasicBlock a, BasicBlock b) { 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return a.getInsns().contentEquals(b.getInsns()); 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Combines blocks proven identical into one alpha block, re-writing 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * all of the successor links that point to the beta blocks to point 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the alpha block instead. 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param alphaLabel block that will replace all the beta block 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param betaLabels label list of blocks to combine 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void combineBlocks(int alphaLabel, IntList betaLabels) { 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szBetas = betaLabels.size(); 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < szBetas; i++) { 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int betaLabel = betaLabels.get(i); 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock bb = blocks.labelToBlock(betaLabel); 14699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project IntList preds = ropMethod.labelToPredecessors(bb.getLabel()); 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int szPreds = preds.size(); 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < szPreds; j++) { 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock predBlock = newBlocks.labelToBlock(preds.get(j)); 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project replaceSucc(predBlock, betaLabel, alphaLabel); 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Replaces one of a block's successors with a different label. Constructs 15899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * an updated BasicBlock instance and places it in {@code newBlocks}. 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param block block to replace 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param oldLabel label of successor to replace 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param newLabel label of new successor 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void replaceSucc(BasicBlock block, int oldLabel, int newLabel) { 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList newSuccessors = block.getSuccessors().mutableCopy(); 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newPrimarySuccessor; 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSuccessors.set(newSuccessors.indexOf(oldLabel), newLabel); 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPrimarySuccessor = block.getPrimarySuccessor(); 17099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (newPrimarySuccessor == oldLabel) { 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newPrimarySuccessor = newLabel; 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newSuccessors.setImmutable(); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock newBB = new BasicBlock(block.getLabel(), 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project block.getInsns(), newSuccessors, newPrimarySuccessor); 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newBlocks.set(newBlocks.indexOfLabel(block.getLabel()), newBB); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 183