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