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.rop.code; 18 19 import com.android.dx.util.Bits; 20 import com.android.dx.util.Hex; 21 import com.android.dx.util.IntList; 22 23 /** 24 * All of the parts that make up a method at the rop layer. 25 */ 26 public final class RopMethod { 27 /** {@code non-null;} basic block list of the method */ 28 private final BasicBlockList blocks; 29 30 /** {@code >= 0;} label for the block which starts the method */ 31 private final int firstLabel; 32 33 /** 34 * {@code null-ok;} array of predecessors for each block, indexed by block 35 * label 36 */ 37 private IntList[] predecessors; 38 39 /** 40 * {@code null-ok;} the predecessors for the implicit "exit" block, that is 41 * the labels for the blocks that return, if calculated 42 */ 43 private IntList exitPredecessors; 44 45 /** 46 * Constructs an instance. 47 * 48 * @param blocks {@code non-null;} basic block list of the method 49 * @param firstLabel {@code >= 0;} the label of the first block to execute 50 */ 51 public RopMethod(BasicBlockList blocks, int firstLabel) { 52 if (blocks == null) { 53 throw new NullPointerException("blocks == null"); 54 } 55 56 if (firstLabel < 0) { 57 throw new IllegalArgumentException("firstLabel < 0"); 58 } 59 60 this.blocks = blocks; 61 this.firstLabel = firstLabel; 62 63 this.predecessors = null; 64 this.exitPredecessors = null; 65 } 66 67 /** 68 * Gets the basic block list for this method. 69 * 70 * @return {@code non-null;} the list 71 */ 72 public BasicBlockList getBlocks() { 73 return blocks; 74 } 75 76 /** 77 * Gets the label for the first block in the method that this list 78 * represents. 79 * 80 * @return {@code >= 0;} the first-block label 81 */ 82 public int getFirstLabel() { 83 return firstLabel; 84 } 85 86 /** 87 * Gets the predecessors associated with the given block. This throws 88 * an exception if there is no block with the given label. 89 * 90 * @param label {@code >= 0;} the label of the block in question 91 * @return {@code non-null;} the predecessors of that block 92 */ 93 public IntList labelToPredecessors(int label) { 94 if (exitPredecessors == null) { 95 calcPredecessors(); 96 } 97 98 IntList result = predecessors[label]; 99 100 if (result == null) { 101 throw new RuntimeException("no such block: " + Hex.u2(label)); 102 } 103 104 return result; 105 } 106 107 /** 108 * Gets the exit predecessors for this instance. 109 * 110 * @return {@code non-null;} the exit predecessors 111 */ 112 public IntList getExitPredecessors() { 113 if (exitPredecessors == null) { 114 calcPredecessors(); 115 } 116 117 return exitPredecessors; 118 } 119 120 121 /** 122 * Returns an instance that is identical to this one, except that 123 * the registers in each instruction are offset by the given 124 * amount. 125 * 126 * @param delta the amount to offset register numbers by 127 * @return {@code non-null;} an appropriately-constructed instance 128 */ 129 public RopMethod withRegisterOffset(int delta) { 130 RopMethod result = new RopMethod(blocks.withRegisterOffset(delta), 131 firstLabel); 132 133 if (exitPredecessors != null) { 134 /* 135 * The predecessors have been calculated. It's safe to 136 * inject these into the new instance, since the 137 * transformation being applied doesn't affect the 138 * predecessors. 139 */ 140 result.exitPredecessors = exitPredecessors; 141 result.predecessors = predecessors; 142 } 143 144 return result; 145 } 146 147 /** 148 * Calculates the predecessor sets for each block as well as for the 149 * exit. 150 */ 151 private void calcPredecessors() { 152 int maxLabel = blocks.getMaxLabel(); 153 IntList[] predecessors = new IntList[maxLabel]; 154 IntList exitPredecessors = new IntList(10); 155 int sz = blocks.size(); 156 157 /* 158 * For each block, find its successors, and add the block's label to 159 * the successor's predecessors. 160 */ 161 for (int i = 0; i < sz; i++) { 162 BasicBlock one = blocks.get(i); 163 int label = one.getLabel(); 164 IntList successors = one.getSuccessors(); 165 int ssz = successors.size(); 166 if (ssz == 0) { 167 // This block exits. 168 exitPredecessors.add(label); 169 } else { 170 for (int j = 0; j < ssz; j++) { 171 int succLabel = successors.get(j); 172 IntList succPreds = predecessors[succLabel]; 173 if (succPreds == null) { 174 succPreds = new IntList(10); 175 predecessors[succLabel] = succPreds; 176 } 177 succPreds.add(label); 178 } 179 } 180 } 181 182 // Sort and immutablize all the predecessor lists. 183 for (int i = 0; i < maxLabel; i++) { 184 IntList preds = predecessors[i]; 185 if (preds != null) { 186 preds.sort(); 187 preds.setImmutable(); 188 } 189 } 190 191 exitPredecessors.sort(); 192 exitPredecessors.setImmutable(); 193 194 /* 195 * The start label might not ever have had any predecessors 196 * added to it (probably doesn't, because of how Java gets 197 * translated into rop form). So, check for this and rectify 198 * the situation if required. 199 */ 200 if (predecessors[firstLabel] == null) { 201 predecessors[firstLabel] = IntList.EMPTY; 202 } 203 204 this.predecessors = predecessors; 205 this.exitPredecessors = exitPredecessors; 206 } 207 } 208
