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