1917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/* 2917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Copyright (C) 2007 The Android Open Source Project 3917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 4917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Licensed under the Apache License, Version 2.0 (the "License"); 5917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * you may not use this file except in compliance with the License. 6917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * You may obtain a copy of the License at 7917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 8917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * http://www.apache.org/licenses/LICENSE-2.0 9917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 10917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Unless required by applicable law or agreed to in writing, software 11917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * distributed under the License is distributed on an "AS IS" BASIS, 12917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * See the License for the specific language governing permissions and 14917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * limitations under the License. 15917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 16917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 17917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpackage com.android.dexgen.rop.code; 18917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 19917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport com.android.dexgen.util.Bits; 20917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport com.android.dexgen.util.Hex; 21917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulimport com.android.dexgen.util.IntList; 22917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 23917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul/** 24917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * All of the parts that make up a method at the rop layer. 25917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 26917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgulpublic final class RopMethod { 27917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code non-null;} basic block list of the method */ 28917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final BasicBlockList blocks; 29917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 30917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** {@code >= 0;} label for the block which starts the method */ 31917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private final int firstLabel; 32917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 33917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 34917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * {@code null-ok;} array of predecessors for each block, indexed by block 35917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * label 36917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 37917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private IntList[] predecessors; 38917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 39917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 40917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * {@code null-ok;} the predecessors for the implicit "exit" block, that is 41917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the labels for the blocks that return, if calculated 42917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 43917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private IntList exitPredecessors; 44917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 45917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 46917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Constructs an instance. 47917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 48917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param blocks {@code non-null;} basic block list of the method 49917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param firstLabel {@code >= 0;} the label of the first block to execute 50917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 51917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public RopMethod(BasicBlockList blocks, int firstLabel) { 52917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (blocks == null) { 53917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new NullPointerException("blocks == null"); 54917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 55917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 56917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (firstLabel < 0) { 57917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new IllegalArgumentException("firstLabel < 0"); 58917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 59917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 60917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.blocks = blocks; 61917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.firstLabel = firstLabel; 62917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 63917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.predecessors = null; 64917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.exitPredecessors = null; 65917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 66917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 67917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 68917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the basic block list for this method. 69917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 70917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} the list 71917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 72917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public BasicBlockList getBlocks() { 73917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return blocks; 74917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 75917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 76917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 77917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the label for the first block in the method that this list 78917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * represents. 79917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 80917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code >= 0;} the first-block label 81917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 82917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public int getFirstLabel() { 83917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return firstLabel; 84917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 85917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 86917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 87917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the predecessors associated with the given block. This throws 88917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * an exception if there is no block with the given label. 89917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 90917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param label {@code >= 0;} the label of the block in question 91917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} the predecessors of that block 92917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 93917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntList labelToPredecessors(int label) { 94917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (exitPredecessors == null) { 95917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul calcPredecessors(); 96917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 97917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 98917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList result = predecessors[label]; 99917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 100917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (result == null) { 101917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul throw new RuntimeException("no such block: " + Hex.u2(label)); 102917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 103917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 104917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 105917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 106917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 107917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 108917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Gets the exit predecessors for this instance. 109917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 110917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} the exit predecessors 111917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 112917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public IntList getExitPredecessors() { 113917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (exitPredecessors == null) { 114917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul calcPredecessors(); 115917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 116917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 117917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return exitPredecessors; 118917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 119917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 120917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 121917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 122917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Returns an instance that is identical to this one, except that 123917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the registers in each instruction are offset by the given 124917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * amount. 125917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * 126917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @param delta the amount to offset register numbers by 127917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * @return {@code non-null;} an appropriately-constructed instance 128917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 129917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul public RopMethod withRegisterOffset(int delta) { 130917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul RopMethod result = new RopMethod(blocks.withRegisterOffset(delta), 131917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul firstLabel); 132917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 133917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (exitPredecessors != null) { 134917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 135917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * The predecessors have been calculated. It's safe to 136917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * inject these into the new instance, since the 137917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * transformation being applied doesn't affect the 138917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * predecessors. 139917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 140917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.exitPredecessors = exitPredecessors; 141917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul result.predecessors = predecessors; 142917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 143917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 144917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul return result; 145917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 146917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 147917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /** 148917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * Calculates the predecessor sets for each block as well as for the 149917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * exit. 150917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 151917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul private void calcPredecessors() { 152917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int maxLabel = blocks.getMaxLabel(); 153917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList[] predecessors = new IntList[maxLabel]; 154917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList exitPredecessors = new IntList(10); 155917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int sz = blocks.size(); 156917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 157917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 158917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * For each block, find its successors, and add the block's label to 159917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the successor's predecessors. 160917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 161917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < sz; i++) { 162917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul BasicBlock one = blocks.get(i); 163917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int label = one.getLabel(); 164917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList successors = one.getSuccessors(); 165917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int ssz = successors.size(); 166917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (ssz == 0) { 167917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // This block exits. 168917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul exitPredecessors.add(label); 169917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } else { 170917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int j = 0; j < ssz; j++) { 171917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul int succLabel = successors.get(j); 172917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList succPreds = predecessors[succLabel]; 173917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (succPreds == null) { 174917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul succPreds = new IntList(10); 175917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul predecessors[succLabel] = succPreds; 176917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 177917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul succPreds.add(label); 178917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 179917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 180917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 181917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 182917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul // Sort and immutablize all the predecessor lists. 183917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul for (int i = 0; i < maxLabel; i++) { 184917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul IntList preds = predecessors[i]; 185917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (preds != null) { 186917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul preds.sort(); 187917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul preds.setImmutable(); 188917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 189917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 190917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 191917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul exitPredecessors.sort(); 192917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul exitPredecessors.setImmutable(); 193917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 194917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul /* 195917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * The start label might not ever have had any predecessors 196917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * added to it (probably doesn't, because of how Java gets 197917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * translated into rop form). So, check for this and rectify 198917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul * the situation if required. 199917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul */ 200917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul if (predecessors[firstLabel] == null) { 201917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul predecessors[firstLabel] = IntList.EMPTY; 202917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 203917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul 204917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.predecessors = predecessors; 205917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul this.exitPredecessors = exitPredecessors; 206917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul } 207917cb222329ee8c035c3ffaf947e4265761b9367Piotr Gurgul} 208