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