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.dex.code; 18f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 193dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornsteinimport com.android.dx.dex.DexOptions; 207ba91291bb6ce64691398a8751656207e8e3e98dDan Bornsteinimport com.android.dx.io.Opcodes; 21f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.LocalItem; 22f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpec; 23f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecList; 24f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.RegisterSpecSet; 25f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.code.SourcePosition; 26f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.Constant; 27f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstMemberRef; 28f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstType; 29333201833d506a3accdeac6ceb7caba8d4b95797Jesse Wilsonimport com.android.dx.rop.cst.CstString; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Type; 31eba7057935e122d8a9234154ea97e3fa32452a4fJesse Wilson 32fc785c7597c477af84b273c8f191f33339f7735eJesse Wilsonimport com.android.dx.util.DexException; 33f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 34dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhaoimport java.util.BitSet; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashSet; 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processor for instruction lists, which takes a "first cut" of 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction selection as a basis and produces a "final cut" in the 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * form of a {@link DalvInsnList} instance. 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 42f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class OutputFinisher { 433dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein /** {@code non-null;} options for dex output */ 443dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein private final DexOptions dexOptions; 453dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein 46f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code >= 0;} register count for the method, not including any extra 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "reserved" registers needed to translate "difficult" instructions 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int unreservedRegCount; 51f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 5299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} the list of instructions, per se */ 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<DalvInsn> insns; 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** whether any instruction has position info */ 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasAnyPositionInfo; 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** whether any instruction has local variable info */ 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasAnyLocalInfo; 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 61f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code >= 0;} the count of reserved registers (low-numbered 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers used when expanding instructions that can't be 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * represented simply); becomes valid after a call to {@link 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #massageInstructions} 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int reservedCount; 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 70f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. It initially contains no instructions. 71de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 723dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein * @param dexOptions {@code non-null;} options for dex output 7399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param regCount {@code >= 0;} register count for the method 74380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param initialCapacity {@code >= 0;} initial capacity of the 75380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * instructions list 76f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 773dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount) { 783dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein this.dexOptions = dexOptions; 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.unreservedRegCount = regCount; 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.insns = new ArrayList<DalvInsn>(initialCapacity); 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.reservedCount = -1; 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.hasAnyPositionInfo = false; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.hasAnyLocalInfo = false; 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns whether any of the instructions added to this instance 88f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * come with position info. 89de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether any of the instructions added to this instance 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * come with position info 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean hasAnyPositionInfo() { 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return hasAnyPositionInfo; 95f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 96de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 98f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns whether this instance has any local variable information. 99de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether this instance has any local variable information 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean hasAnyLocalInfo() { 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return hasAnyLocalInfo; 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #add} which scrutinizes a single 108f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction for local variable information. 109de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 11099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} instruction to scrutinize 11199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the instruction refers to any 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * named locals 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean hasLocalInfo(DalvInsn insn) { 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof LocalSnapshot) { 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = specs.size(); 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(specs.get(i))) { 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalStart) { 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec = ((LocalStart) insn).getLocal(); 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(spec)) { 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #hasAnyLocalInfo} which scrutinizes a single 135f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * register spec. 136de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 13799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code non-null;} spec to scrutinize 13899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the spec refers to any 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * named locals 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean hasLocalInfo(RegisterSpec spec) { 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (spec != null) 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (spec.getLocalItem().getName() != null); 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the set of all constants referred to by instructions added 148f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to this instance. 149de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 15099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the set of constants 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public HashSet<Constant> getAllConstants() { 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashSet<Constant> result = new HashSet<Constant>(20); 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (DalvInsn insn : insns) { 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, insn); 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #getAllConstants} which adds all the info for 164f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a single instruction. 165de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 16699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param result {@code non-null;} result set to add to 16799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} instruction to scrutinize 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void addConstants(HashSet<Constant> result, 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn) { 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof CstInsn) { 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Constant cst = ((CstInsn) insn).getConstant(); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(cst); 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalSnapshot) { 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = specs.size(); 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, specs.get(i)); 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalStart) { 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec = ((LocalStart) insn).getLocal(); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, spec); 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 187f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #getAllConstants} which adds all the info for 18899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * a single {@code RegisterSpec}. 189f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 19099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param result {@code non-null;} result set to add to 19199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code null-ok;} register spec to add 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void addConstants(HashSet<Constant> result, 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec) { 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec == null) { 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 197f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 198de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = spec.getLocalItem(); 200333201833d506a3accdeac6ceb7caba8d4b95797Jesse Wilson CstString name = local.getName(); 201333201833d506a3accdeac6ceb7caba8d4b95797Jesse Wilson CstString signature = local.getSignature(); 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type type = spec.getType(); 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (type != Type.KNOWN_NULL) { 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(CstType.intern(type)); 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (name != null) { 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(name); 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (signature != null) { 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(signature); 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 218f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds an instruction to the output. 219de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 220de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * @param insn {@code non-null;} the instruction to add 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void add(DalvInsn insn) { 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(insn); 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateInfo(insn); 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 228f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inserts an instruction in the output at the given offset. 229de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 23099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param at {@code >= 0;} what index to insert at 23199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction to insert 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void insert(int at, DalvInsn insn) { 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(at, insn); 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateInfo(insn); 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #add} and {@link #insert}, 240f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * which updates the position and local info flags. 241de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 24299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} an instruction that was just introduced 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void updateInfo(DalvInsn insn) { 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! hasAnyPositionInfo) { 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = insn.getPosition(); 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pos.getLine() >= 0) { 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasAnyPositionInfo = true; 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! hasAnyLocalInfo) { 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(insn)) { 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasAnyLocalInfo = true; 255f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 256f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 257f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 258f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 259f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Reverses a branch which is buried a given number of instructions 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * backward in the output. It is illegal to call this unless the 262f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indicated instruction really is a reversible branch. 263de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 264f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param which how many instructions back to find the branch; 26599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code 0} is the most recently added instruction, 26699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code 1} is the instruction before that, etc. 267380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param newTarget {@code non-null;} the new target for the 268380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * reversed branch 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void reverseBranch(int which, CodeAddress newTarget) { 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int index = size - which - 1; 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn targetInsn; 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project targetInsn = (TargetInsn) insns.get(index); 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (IndexOutOfBoundsException ex) { 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("too few instructions"); 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ClassCastException ex) { 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("non-reversible instruction"); 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * No need to call this.set(), since the format and other info 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are the same. 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(index, targetInsn.withNewTargetAndReversed(newTarget)); 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Assigns indices in all instructions that need them, using the 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * given callback to perform lookups. This should be called before 295f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * calling {@link #finishProcessingAndGetList}. 296de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 29799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param callback {@code non-null;} callback object 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void assignIndices(DalvCode.AssignIndicesCallback callback) { 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (DalvInsn insn : insns) { 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof CstInsn) { 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignIndices((CstInsn) insn, callback); 303f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 304f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 305f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 306f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 307f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #assignIndices} which does assignment for one 309f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction. 310de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 31199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction 31299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param callback {@code non-null;} the callback 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void assignIndices(CstInsn insn, 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvCode.AssignIndicesCallback callback) { 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Constant cst = insn.getConstant(); 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int index = callback.getIndex(cst); 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (index >= 0) { 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setIndex(index); 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (cst instanceof CstMemberRef) { 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstMemberRef member = (CstMemberRef) cst; 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstType definer = member.getDefiningClass(); 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project index = callback.getIndex(definer); 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (index >= 0) { 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setClassIndex(index); 329f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 330f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 331f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 332f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 333f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Does final processing on this instance and gets the output as 335f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a {@link DalvInsnList}. Final processing consists of: 336de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ul> 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>optionally renumbering registers (to make room as needed for 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * expanded instructions)</li> 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>picking a final opcode for each instruction</li> 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>rewriting instructions, because of register number, 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constant pool index, or branch target size issues</li> 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>assigning final addresses</li> 344f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ul> 345de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p><b>Note:</b> This method may only be called once per instance 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of this class.</p> 348f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 34999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the output list 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if this method has 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * already been called 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public DalvInsnList finishProcessingAndGetList() { 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedCount >= 0) { 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException("already processed"); 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 357f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 358380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop[] opcodes = makeOpcodesArray(); 359380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein reserveRegisters(opcodes); 360380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein massageInstructions(opcodes); 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignAddressesAndFixBranches(); 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return DalvInsnList.makeImmutable(insns, 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedCount + unreservedRegCount); 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 368f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which extracts 369380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * the opcode out of each instruction into a separate array, to be 370f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * further manipulated as things progress. 371de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 372380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @return {@code non-null;} the array of opcodes 373f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 374380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private Dop[] makeOpcodesArray() { 375f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 376380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop[] result = new Dop[size]; 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 378f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 379380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein result[i] = insns.get(i).getOpcode(); 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which figures 387f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * out how many reserved registers are required and then reserving 388380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * them. It also updates the given {@code opcodes} array so 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as to avoid extra work when constructing the massaged 390f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction list. 391de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 392380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 393380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 394f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 395380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private void reserveRegisters(Dop[] opcodes) { 396f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount; 397de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Call calculateReservedCount() and then perform register 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * reservation, repeatedly until no new reservations happen. 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 402f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 403380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein int newReservedCount = calculateReservedCount(opcodes); 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldReservedCount >= newReservedCount) { 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reservedDifference = newReservedCount - oldReservedCount; 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * CodeAddress instance identity is used to link 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TargetInsns to their targets, so it is 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inappropriate to make replacements, and they don't 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have registers in any case. Hence, the instanceof 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * test below. 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(insn instanceof CodeAddress)) { 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * No need to call this.set() since the format and 423f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * other info are the same. 424de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro */ 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn.withRegisterOffset(reservedDifference)); 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project oldReservedCount = newReservedCount; 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedCount = oldReservedCount; 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #reserveRegisters}, which does one 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * pass over the instructions, calculating the number of 438f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers that need to be reserved. It also updates the 439380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * {@code opcodes} list to help avoid extra work in future 440f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * register reservation passes. 441de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 442380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 443380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 44499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the count of reserved registers 445f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 446380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private int calculateReservedCount(Dop[] opcodes) { 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Potential new value of reservedCount, which gets updated in the 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * following loop. It starts out with the existing reservedCount 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and gets increased if it turns out that additional registers 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * need to be reserved. 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newReservedCount = reservedCount; 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 458f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 459380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = opcodes[i]; 460380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop newOpcode = findOpcodeForInsn(insn, originalOpcode); 461f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 462380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (newOpcode == null) { 463f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 464dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * The instruction will need to be expanded, so find the 465dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * expanded opcode and reserve registers for it. 466f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 467dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao Dop expandedOp = findExpandedOpcodeForInsn(insn); 468dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao BitSet compatRegs = expandedOp.getFormat().compatibleRegs(insn); 469dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao int reserve = insn.getMinimumRegisterRequirement(compatRegs); 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reserve > newReservedCount) { 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newReservedCount = reserve; 472f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 473dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao } else if (originalOpcode == newOpcode) { 474dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao continue; 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 476f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 477380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein opcodes[i] = newOpcode; 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newReservedCount; 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 483f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 484380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * Attempts to fit the given instruction into a specific opcode, 485380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * returning the opcode whose format that the instruction fits 486380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * into or {@code null} to indicate that the instruction will need 487380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * to be expanded. This fitting process starts with the given 488380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode as a first "best guess" and then pessimizes from there 489380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * if necessary. 490f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 49199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction in question 492380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param guess {@code null-ok;} the current guess as to the best 493380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode; {@code null} means that no simple opcode fits 494380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @return {@code null-ok;} a possibly-different opcode; either a 495380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * {@code non-null} good fit or {@code null} to indicate that no 496380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * simple opcode fits 497f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 498380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private Dop findOpcodeForInsn(DalvInsn insn, Dop guess) { 499380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein /* 500380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * Note: The initial guess might be null, meaning that an 501380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * earlier call to this method already determined that there 502380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * was no possible simple opcode fit. 503380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein */ 504f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 505380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein while (guess != null) { 506380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (guess.getFormat().isCompatible(insn)) { 507266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao /* 508266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao * Don't break out for const_string to generate jumbo version 509266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao * when option is enabled. 510266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao */ 511266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao if (!dexOptions.forceJumbo || 512266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao guess.getOpcode() != Opcodes.CONST_STRING) { 513266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao break; 514266f45ff7da18022faf5f77df76c69f8cdad313fjeffhao } 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 516380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein 5173dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein guess = Dops.getNextOrNull(guess, dexOptions); 518f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 519f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 520380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein return guess; 521f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 522de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 523f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 524dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * Finds the proper opcode for the given instruction, ignoring 525dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * register constraints. 526dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * 527dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * @param insn {@code non-null;} the instruction in question 528dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * @return {@code non-null;} the opcode that fits 529dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao */ 530dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao private Dop findExpandedOpcodeForInsn(DalvInsn insn) { 531ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson Dop result = findOpcodeForInsn(insn.getLowRegVersion(), insn.getOpcode()); 532ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson if (result == null) { 533fc785c7597c477af84b273c8f191f33339f7735eJesse Wilson throw new DexException("No expanded opcode for " + insn); 534ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson } 535ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson return result; 536dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao } 537dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao 538dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao /** 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which goes 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * through each instruction in the output, making sure its opcode 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can accomodate its arguments. In cases where the opcode is 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unable to do so, this replaces the instruction with a larger 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction with identical semantics that <i>will</i> work. 544de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method may also reserve a number of low-numbered 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers, renumbering the instructions' original registers, in 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * order to have register space available in which to move 548f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * very-high registers when expanding instructions into 549f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * multi-instruction sequences. This expansion is done when no 550f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * simple instruction format can be found for a given instruction that 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is able to accomodate that instruction's registers.</p> 552de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method ignores issues of branch target size, since 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * final addresses aren't known at the point that this method is 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * called.</p> 556de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 557380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 558380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 559f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 560380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private void massageInstructions(Dop[] opcodes) { 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedCount == 0) { 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The easy common case: No registers were reserved, so we 564380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * merely need to replace any instructions whose format 565380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * (and hence whose opcode) changed during the reservation 566380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * pass, but all instructions will stay at their original 567380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * indices, and the instruction list doesn't grow. 568f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 569f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 573380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = insn.getOpcode(); 574380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop currentOpcode = opcodes[i]; 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 576380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (originalOpcode != currentOpcode) { 577380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns.set(i, insn.withOpcode(currentOpcode)); 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The difficult uncommon case: Some instructions have to be 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * expanded to deal with high registers. 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 585380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns = performExpansion(opcodes); 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 587f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 588f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 589f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 590f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #massageInstructions}, which constructs a 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * replacement list, where each {link DalvInsn} instance that 592f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * couldn't be represented simply (due to register representation 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * problems) is expanded into a series of instances that together 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * perform the proper function. 595de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 596380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 597380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 59899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the replacement list 599f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 600380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private ArrayList<DalvInsn> performExpansion(Dop[] opcodes) { 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<DalvInsn> result = new ArrayList<DalvInsn>(size * 2); 603f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60440c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver ArrayList<CodeAddress> closelyBoundAddresses = new ArrayList<CodeAddress>(); 60540c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 608380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = insn.getOpcode(); 609380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop currentOpcode = opcodes[i]; 610f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn prefix; 611f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn suffix; 612f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 613380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (currentOpcode != null) { 614f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // No expansion is necessary. 615f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project prefix = null; 616f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project suffix = null; 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expansion is required. 619dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao currentOpcode = findExpandedOpcodeForInsn(insn); 620dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao BitSet compatRegs = 621dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao currentOpcode.getFormat().compatibleRegs(insn); 622dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao prefix = insn.expandedPrefix(compatRegs); 623dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao suffix = insn.expandedSuffix(compatRegs); 624dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao 625dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao // Expand necessary registers to fit the new format 626dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao insn = insn.expandedVersion(compatRegs); 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 62940c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver if (insn instanceof CodeAddress) { 63040c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver // If we have a closely bound address, don't add it yet, 63140c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver // because we need to add it after the prefix for the 63240c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver // instruction it is bound to. 63340c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver if (((CodeAddress) insn).getBindsClosely()) { 63440c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver closelyBoundAddresses.add((CodeAddress)insn); 63540c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver continue; 63640c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver } 63740c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver } 63840c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (prefix != null) { 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(prefix); 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 642de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 64340c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver // Add any pending closely bound addresses 64440c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver if (!(insn instanceof ZeroSizeInsn) && closelyBoundAddresses.size() > 0) { 64540c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver for (CodeAddress codeAddress: closelyBoundAddresses) { 64640c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver result.add(codeAddress); 64740c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver } 64840c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver closelyBoundAddresses.clear(); 64940c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver } 65040c69d949e67fe2cc2cccf4dd16b2f9fdabea396Ben Gruver 651380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (currentOpcode != originalOpcode) { 652380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insn = insn.withOpcode(currentOpcode); 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(insn); 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (suffix != null) { 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(suffix); 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 660de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which assigns 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * addresses to each instruction, possibly rewriting branches to 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * fix ones that wouldn't otherwise be able to reach their 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * targets. 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 670f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void assignAddressesAndFixBranches() { 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 672f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignAddresses(); 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!fixBranches()) { 674f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #assignAddressesAndFixBranches}, which 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * assigns an address to each instruction, in order. 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void assignAddresses() { 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int address = 0; 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 688f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setAddress(address); 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project address += insn.codeSize(); 691f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 695f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #assignAddressesAndFixBranches}, which checks 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the branch target size requirement of each branch instruction 697f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to make sure it fits. For instructions that don't fit, this 69899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * rewrites them to use a {@code goto} of some sort. In the 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * case of a conditional branch that doesn't fit, the sense of the 70099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * test is reversed in order to branch around a {@code goto} 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the original target. 702de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether any branches had to be fixed 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean fixBranches() { 706f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean anyFixed = false; 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(insn instanceof TargetInsn)) { 712f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This loop only needs to inspect TargetInsns. 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 716380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop opcode = insn.getOpcode(); 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn target = (TargetInsn) insn; 718f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 719380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (opcode.getFormat().branchFits(target)) { 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 7237ba91291bb6ce64691398a8751656207e8e3e98dDan Bornstein if (opcode.getFamily() == Opcodes.GOTO) { 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // It is a goto; widen it if possible. 725380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein opcode = findOpcodeForInsn(insn, opcode); 726380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (opcode == null) { 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The branch is already maximally large. This should 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * only be possible if a method somehow manages to have 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * more than 2^31 code units. 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException("method too long"); 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 734380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns.set(i, insn.withOpcode(opcode)); 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * It is a conditional: Reverse its sense, and arrange for 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it to branch around an absolute goto to the original 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * branch target. 740de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Note: An invariant of the list being processed is 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that every TargetInsn is followed by a CodeAddress. 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Hence, it is always safe to get the next element 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * after a TargetInsn and cast it to CodeAddress, as 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is happening a few lines down. 746de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Also note: Size gets incremented by one here, as we 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have -- in the net -- added one additional element 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the list, so we increment i to match. The added 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and changed elements will be inspected by a repeat 751f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * call to this method after this invocation returns. 752f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 753f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CodeAddress newTarget; 754f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 755f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newTarget = (CodeAddress) insns.get(i + 1); 756f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (IndexOutOfBoundsException ex) { 757f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The TargetInsn / CodeAddress invariant was violated. 758f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalStateException( 759f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "unpaired TargetInsn (dangling)"); 760f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ClassCastException ex) { 761f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The TargetInsn / CodeAddress invariant was violated. 762f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalStateException("unpaired TargetInsn"); 763f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 764f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn gotoInsn = 765f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new TargetInsn(Dops.GOTO, target.getPosition(), 766f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, target.getTarget()); 767f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, gotoInsn); 768f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(i, target.withNewTargetAndReversed(newTarget)); 769f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size++; 770f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 771f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 772f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 773f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project anyFixed = true; 774f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 775f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 776f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return anyFixed; 777f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 778f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 779