1f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/* 2f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 3f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 4f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 5f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * you may not use this file except in compliance with the License. 6f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * You may obtain a copy of the License at 7f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 8f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 9f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 10f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 11f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 12f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * See the License for the specific language governing permissions and 14f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * limitations under the License. 15f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 16f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 17f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpackage com.android.dx.rop.code; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 19f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Hex; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * All of the parts that make up a method at the rop layer. 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class RopMethod { 2699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} basic block list of the method */ 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final BasicBlockList blocks; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 2999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code >= 0;} label for the block which starts the method */ 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int firstLabel; 31f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 3399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code null-ok;} array of predecessors for each block, indexed by block 34de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * label 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntList[] predecessors; 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 3999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code null-ok;} the predecessors for the implicit "exit" block, that is 40de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * the labels for the blocks that return, if calculated 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private IntList exitPredecessors; 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. 46de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param blocks {@code non-null;} basic block list of the method 4899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param firstLabel {@code >= 0;} the label of the first block to execute 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RopMethod(BasicBlockList blocks, int firstLabel) { 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (blocks == null) { 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new NullPointerException("blocks == null"); 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (firstLabel < 0) { 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("firstLabel < 0"); 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.blocks = blocks; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.firstLabel = firstLabel; 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.predecessors = null; 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.exitPredecessors = null; 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the basic block list for this method. 68de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 6999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the list 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlockList getBlocks() { 72f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return blocks; 73f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 74f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the label for the first block in the method that this list 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * represents. 78de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 7999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the first-block label 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getFirstLabel() { 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return firstLabel; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the predecessors associated with the given block. This throws 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * an exception if there is no block with the given label. 88de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 8999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} the label of the block in question 9099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the predecessors of that block 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList labelToPredecessors(int label) { 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (exitPredecessors == null) { 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calcPredecessors(); 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList result = predecessors[label]; 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result == null) { 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new RuntimeException("no such block: " + Hex.u2(label)); 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the exit predecessors for this instance. 108de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 10999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the exit predecessors 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public IntList getExitPredecessors() { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (exitPredecessors == null) { 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project calcPredecessors(); 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return exitPredecessors; 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns an instance that is identical to this one, except that 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the registers in each instruction are offset by the given 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * amount. 124de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param delta the amount to offset register numbers by 12699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RopMethod withRegisterOffset(int delta) { 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RopMethod result = new RopMethod(blocks.withRegisterOffset(delta), 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project firstLabel); 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (exitPredecessors != null) { 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The predecessors have been calculated. It's safe to 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inject these into the new instance, since the 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * transformation being applied doesn't affect the 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * predecessors. 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.exitPredecessors = exitPredecessors; 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.predecessors = predecessors; 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Calculates the predecessor sets for each block as well as for the 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * exit. 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void calcPredecessors() { 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int maxLabel = blocks.getMaxLabel(); 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList[] predecessors = new IntList[maxLabel]; 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList exitPredecessors = new IntList(10); 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = blocks.size(); 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * For each block, find its successors, and add the block's label to 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the successor's predecessors. 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = blocks.get(i); 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label = one.getLabel(); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = one.getSuccessors(); 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int ssz = successors.size(); 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (ssz == 0) { 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This block exits. 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitPredecessors.add(label); 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < ssz; j++) { 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succLabel = successors.get(j); 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList succPreds = predecessors[succLabel]; 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (succPreds == null) { 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succPreds = new IntList(10); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project predecessors[succLabel] = succPreds; 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project succPreds.add(label); 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Sort and immutablize all the predecessor lists. 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < maxLabel; i++) { 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList preds = predecessors[i]; 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (preds != null) { 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project preds.sort(); 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project preds.setImmutable(); 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 190f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitPredecessors.sort(); 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project exitPredecessors.setImmutable(); 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The start label might not ever have had any predecessors 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * added to it (probably doesn't, because of how Java gets 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * translated into rop form). So, check for this and rectify 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the situation if required. 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (predecessors[firstLabel] == null) { 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project predecessors[firstLabel] = IntList.EMPTY; 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.predecessors = predecessors; 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.exitPredecessors = exitPredecessors; 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 207