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