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.rop.type.StdTypeList; 20f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.TypeList; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.Hex; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.IntList; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.util.LabeledList; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * List of {@link BasicBlock} instances. 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class BasicBlockList extends LabeledList { 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 3099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code >= -1;} the count of registers required by this method or 31de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * {@code -1} if not yet calculated 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int regCount; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 3699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs an instance. All indices initially contain {@code null}, 3799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * and the first-block label is initially {@code -1}. 38de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param size the size of the list 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlockList(int size) { 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(size); 43f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 44f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = -1; 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Constructs a mutable copy for {@code getMutableCopy()}. 49de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param old block to copy 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 52893ea594be06711902de7a484c0eecb910356f42Dan Bornstein private BasicBlockList(BasicBlockList old) { 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super(old); 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = old.regCount; 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the element at the given index. It is an error to call 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * this with the index for an element which was never set; if you 6199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * do that, this will throw {@code NullPointerException}. 62de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 6399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which index 6499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} element at that index 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlock get(int n) { 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (BasicBlock) get0(n); 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 71f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Sets the basic block at the given index. 72de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 7399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param n {@code >= 0, < size();} which index 7499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param bb {@code null-ok;} the element to set at {@code n} 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void set(int n, BasicBlock bb) { 77f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project super.set(n, bb); 78de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Reset regCount, since it will need to be recalculated. 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = -1; 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns how many registers this method requires. This is simply 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the maximum of register-number-plus-category referred to by this 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instance's instructions (indirectly through {@link BasicBlock} 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instances). 88de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 8999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the register count 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getRegCount() { 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (regCount == -1) { 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegCountVisitor visitor = new RegCountVisitor(); 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project forEachInsn(visitor); 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = visitor.getRegCount(); 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return regCount; 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the total instruction count for this instance. This is the 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * sum of the instruction counts of each block. 104de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 10599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the total instruction count 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getInstructionCount() { 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size(); 109f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int result = 0; 110f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = (BasicBlock) getOrNull0(i); 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result += one.getInsns().size(); 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the total instruction count for this instance, ignoring 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * mark-local instructions which are not actually emitted. 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 12599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the total instruction count 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getEffectiveInstructionCount() { 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size(); 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int result = 0; 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = (BasicBlock) getOrNull0(i); 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = one.getInsns(); 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int insnsSz = insns.size(); 136f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 137f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int j = 0; j < insnsSz; j++) { 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Insn insn = insns.get(j); 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn.getOpcode().getOpcode() != RegOps.MARK_LOCAL) { 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result++; 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 149f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the first block in the list with the given label, if any. 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 15399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param label {@code >= 0;} the label to look for 15499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the so-labelled block 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws IllegalArgumentException thrown if the label isn't found 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlock labelToBlock(int label) { 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int idx = indexOfLabel(label); 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (idx < 0) { 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("no such label: " 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project + Hex.u2(label)); 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 165f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return get(idx); 166f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Visits each instruction of each block in the list, in order. 170de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 17199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param visitor {@code non-null;} visitor to use 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void forEachInsn(Insn.Visitor visitor) { 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size(); 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = get(i); 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project InsnList insns = one.getInsns(); 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.forEach(visitor); 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns an instance that is identical to this one, except that 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the registers in each instruction are offset by the given 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * amount. Mutability of the result is inherited from the 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * original. 188de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param delta the amount to offset register numbers by 19099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlockList withRegisterOffset(int delta) { 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = size(); 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlockList result = new BasicBlockList(sz); 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project BasicBlock one = (BasicBlock) get0(i); 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (one != null) { 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.set(i, one.withRegisterOffset(delta)); 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (isImmutable()) { 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.setImmutable(); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns a mutable copy of this list. 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 21399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} an appropriately-constructed instance 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlockList getMutableCopy() { 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return new BasicBlockList(this); 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 219f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the preferred successor for the given block. If the block 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * only has one successor, then that is the preferred successor. 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Otherwise, if the block has a primay successor, then that is 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the preferred successor. If the block has no successors, then 22499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * this returns {@code null}. 225de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 22699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block {@code non-null;} the block in question 22799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code null-ok;} the preferred successor, if any 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 229f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public BasicBlock preferredSuccessorOf(BasicBlock block) { 230f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primarySuccessor = block.getPrimarySuccessor(); 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList successors = block.getSuccessors(); 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int succSize = successors.size(); 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project switch (succSize) { 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project case 0: { 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return null; 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project case 1: { 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return labelToBlock(successors.get(0)); 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 241f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (primarySuccessor != -1) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return labelToBlock(primarySuccessor); 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return labelToBlock(successors.get(0)); 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Compares the catches of two blocks for equality. This includes 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * both the catch types and target labels. 253de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 25499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block1 {@code non-null;} one block to compare 25599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param block2 {@code non-null;} the other block to compare 25699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} if the two blocks' non-primary successors 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are identical 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 259893ea594be06711902de7a484c0eecb910356f42Dan Bornstein public boolean catchesEqual(BasicBlock block1, BasicBlock block2) { 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeList catches1 = block1.getExceptionHandlerTypes(); 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TypeList catches2 = block2.getExceptionHandlerTypes(); 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!StdTypeList.equalContents(catches1, catches2)) { 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 265f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 266f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 267f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList succ1 = block1.getSuccessors(); 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project IntList succ2 = block2.getSuccessors(); 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = succ1.size(); // Both are guaranteed to be the same size. 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primary1 = block1.getPrimarySuccessor(); 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int primary2 = block2.getPrimarySuccessor(); 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (((primary1 == -1) || (primary2 == -1)) 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (primary1 != primary2)) { 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * For the current purpose, both blocks in question must 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * either both have a primary or both not have a primary to 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * be considered equal, and it turns out here that that's not 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the case. 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 284de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label1 = succ1.get(i); 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int label2 = succ2.get(i); 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label1 == primary1) { 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * It should be the case that block2's primary is at the 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * same index. If not, we consider the blocks unequal for 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the current purpose. 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label2 != primary2) { 296f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (label1 != label2) { 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 310f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Instruction visitor class for counting registers used. 311f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static class RegCountVisitor 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project implements Insn.Visitor { 31499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code >= 0;} register count in-progress */ 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int regCount; 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public RegCountVisitor() { 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = 0; 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Gets the register count. 326de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 32799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the count 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public int getRegCount() { 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return regCount; 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPlainInsn(PlainInsn insn) { 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitPlainCstInsn(PlainCstInsn insn) { 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitSwitchInsn(SwitchInsn insn) { 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitThrowingCstInsn(ThrowingCstInsn insn) { 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitThrowingInsn(ThrowingInsn insn) { 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 358f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** {@inheritDoc} */ 359f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void visitFillArrayDataInsn(FillArrayDataInsn insn) { 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project visit(insn); 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 36499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * Helper for all the {@code visit*} methods. 365de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 36699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} instruction being visited 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void visit(Insn insn) { 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec result = insn.getResult(); 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 371f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (result != null) { 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processReg(result); 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList sources = insn.getSources(); 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int sz = sources.size(); 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < sz; i++) { 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project processReg(sources.get(i)); 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processes the given register spec. 385de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 38699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code non-null;} the register spec 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void processReg(RegisterSpec spec) { 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reg = spec.getNextReg(); 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 391f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reg > regCount) { 392f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project regCount = reg; 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 395de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro } 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 397