1579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/* 2579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Copyright (C) 2007 The Android Open Source Project 3579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 4579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * you may not use this file except in compliance with the License. 6579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * You may obtain a copy of the License at 7579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 8579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 10579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * See the License for the specific language governing permissions and 14579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * limitations under the License. 15579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 16579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 17579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpackage com.android.dx.rop.code; 18579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 19579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Bits; 20579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.Hex; 21579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonimport com.android.dx.util.IntList; 22579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 23579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson/** 24579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * All of the parts that make up a method at the rop layer. 25579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 26579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilsonpublic final class RopMethod { 27579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code non-null;} basic block list of the method */ 28579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final BasicBlockList blocks; 29579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 30579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** {@code >= 0;} label for the block which starts the method */ 31579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private final int firstLabel; 32579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 33579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 34579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code null-ok;} array of predecessors for each block, indexed by block 35579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * label 36579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 37579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private IntList[] predecessors; 38579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 39579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 40579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * {@code null-ok;} the predecessors for the implicit "exit" block, that is 41579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the labels for the blocks that return, if calculated 42579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 43579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private IntList exitPredecessors; 44579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 45579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 46579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Constructs an instance. 47579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 48579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param blocks {@code non-null;} basic block list of the method 49579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param firstLabel {@code >= 0;} the label of the first block to execute 50579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 51579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public RopMethod(BasicBlockList blocks, int firstLabel) { 52579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (blocks == null) { 53579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new NullPointerException("blocks == null"); 54579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 55579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 56579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (firstLabel < 0) { 57579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new IllegalArgumentException("firstLabel < 0"); 58579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 59579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 60579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.blocks = blocks; 61579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.firstLabel = firstLabel; 62579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 63579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.predecessors = null; 64579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.exitPredecessors = null; 65579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 66579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 67579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 68579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the basic block list for this method. 69579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 70579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the list 71579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 72579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public BasicBlockList getBlocks() { 73579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return blocks; 74579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 75579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 76579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 77579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the label for the first block in the method that this list 78579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * represents. 79579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 80579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code >= 0;} the first-block label 81579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 82579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public int getFirstLabel() { 83579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return firstLabel; 84579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 85579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 86579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 87579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the predecessors associated with the given block. This throws 88579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * an exception if there is no block with the given label. 89579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 90579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param label {@code >= 0;} the label of the block in question 91579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the predecessors of that block 92579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 93579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList labelToPredecessors(int label) { 94579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (exitPredecessors == null) { 95579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson calcPredecessors(); 96579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 97579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 98579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList result = predecessors[label]; 99579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 100579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (result == null) { 101579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson throw new RuntimeException("no such block: " + Hex.u2(label)); 102579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 103579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 104579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 105579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 106579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 107579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 108579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Gets the exit predecessors for this instance. 109579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 110579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} the exit predecessors 111579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 112579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public IntList getExitPredecessors() { 113579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (exitPredecessors == null) { 114579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson calcPredecessors(); 115579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 116579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 117579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return exitPredecessors; 118579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 119579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 120579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 121579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 122579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Returns an instance that is identical to this one, except that 123579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the registers in each instruction are offset by the given 124579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * amount. 125579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * 126579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @param delta the amount to offset register numbers by 127579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * @return {@code non-null;} an appropriately-constructed instance 128579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 129579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson public RopMethod withRegisterOffset(int delta) { 130579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson RopMethod result = new RopMethod(blocks.withRegisterOffset(delta), 131579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson firstLabel); 132579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 133579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (exitPredecessors != null) { 134579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 135579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The predecessors have been calculated. It's safe to 136579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * inject these into the new instance, since the 137579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * transformation being applied doesn't affect the 138579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * predecessors. 139579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 140579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.exitPredecessors = exitPredecessors; 141579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson result.predecessors = predecessors; 142579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 143579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 144579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson return result; 145579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 146579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 147579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /** 148579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * Calculates the predecessor sets for each block as well as for the 149579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * exit. 150579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 151579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson private void calcPredecessors() { 152579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int maxLabel = blocks.getMaxLabel(); 153579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList[] predecessors = new IntList[maxLabel]; 154579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList exitPredecessors = new IntList(10); 155579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int sz = blocks.size(); 156579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 157579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 158579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * For each block, find its successors, and add the block's label to 159579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the successor's predecessors. 160579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 161579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < sz; i++) { 162579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson BasicBlock one = blocks.get(i); 163579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int label = one.getLabel(); 164579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList successors = one.getSuccessors(); 165579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int ssz = successors.size(); 166579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (ssz == 0) { 167579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // This block exits. 168579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson exitPredecessors.add(label); 169579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } else { 170579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int j = 0; j < ssz; j++) { 171579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson int succLabel = successors.get(j); 172579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList succPreds = predecessors[succLabel]; 173579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (succPreds == null) { 174579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson succPreds = new IntList(10); 175579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predecessors[succLabel] = succPreds; 176579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 177579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson succPreds.add(label); 178579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 179579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 180579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 181579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 182579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson // Sort and immutablize all the predecessor lists. 183579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson for (int i = 0; i < maxLabel; i++) { 184579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson IntList preds = predecessors[i]; 185579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (preds != null) { 186579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson preds.sort(); 187579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson preds.setImmutable(); 188579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 189579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 190579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 191579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson exitPredecessors.sort(); 192579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson exitPredecessors.setImmutable(); 193579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 194579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson /* 195579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * The start label might not ever have had any predecessors 196579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * added to it (probably doesn't, because of how Java gets 197579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * translated into rop form). So, check for this and rectify 198579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson * the situation if required. 199579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson */ 200579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson if (predecessors[firstLabel] == null) { 201579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson predecessors[firstLabel] = IntList.EMPTY; 202579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 203579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson 204579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.predecessors = predecessors; 205579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson this.exitPredecessors = exitPredecessors; 206579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson } 207579d7739c53a2707ad711a2d2cae46d7d782f06Jesse Wilson} 208