OutputFinisher.java revision eba7057935e122d8a9234154ea97e3fa32452a4f
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; 29f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.cst.CstUtf8; 30f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport com.android.dx.rop.type.Type; 31eba7057935e122d8a9234154ea97e3fa32452a4fJesse Wilson 32f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.ArrayList; 33dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhaoimport java.util.BitSet; 34f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectimport java.util.HashSet; 35f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 36f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project/** 37f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Processor for instruction lists, which takes a "first cut" of 38f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction selection as a basis and produces a "final cut" in the 39f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * form of a {@link DalvInsnList} instance. 40f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 41f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Projectpublic final class OutputFinisher { 423dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein /** {@code non-null;} options for dex output */ 433dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein private final DexOptions dexOptions; 443dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein 45f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 4699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code >= 0;} register count for the method, not including any extra 47f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * "reserved" registers needed to translate "difficult" instructions 48f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 49f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private final int unreservedRegCount; 50f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 5199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project /** {@code non-null;} the list of instructions, per se */ 52f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private ArrayList<DalvInsn> insns; 53f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 54f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** whether any instruction has position info */ 55f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasAnyPositionInfo; 56f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 57f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** whether any instruction has local variable info */ 58f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean hasAnyLocalInfo; 59f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 60f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 6199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code >= 0;} the count of reserved registers (low-numbered 62f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers used when expanding instructions that can't be 63f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * represented simply); becomes valid after a call to {@link 64f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * #massageInstructions} 65f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 66f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private int reservedCount; 67f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 68f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 69f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Constructs an instance. It initially contains no instructions. 70de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 713dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein * @param dexOptions {@code non-null;} options for dex output 7299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param regCount {@code >= 0;} register count for the method 73380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param initialCapacity {@code >= 0;} initial capacity of the 74380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * instructions list 75f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 763dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein public OutputFinisher(DexOptions dexOptions, int initialCapacity, int regCount) { 773dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein this.dexOptions = dexOptions; 78f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.unreservedRegCount = regCount; 79f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.insns = new ArrayList<DalvInsn>(initialCapacity); 80f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.reservedCount = -1; 81f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.hasAnyPositionInfo = false; 82f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project this.hasAnyLocalInfo = false; 83f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 84f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 85f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 86f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns whether any of the instructions added to this instance 87f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * come with position info. 88de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 89f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether any of the instructions added to this instance 90f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * come with position info 91f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 92f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean hasAnyPositionInfo() { 93f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return hasAnyPositionInfo; 94f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 95de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 96f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 97f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns whether this instance has any local variable information. 98de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 99f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether this instance has any local variable information 100f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 101f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public boolean hasAnyLocalInfo() { 102f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return hasAnyLocalInfo; 103f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 104f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 105f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 106f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #add} which scrutinizes a single 107f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction for local variable information. 108de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 10999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} instruction to scrutinize 11099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the instruction refers to any 111f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * named locals 112f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 113f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean hasLocalInfo(DalvInsn insn) { 114f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof LocalSnapshot) { 115f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 116f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = specs.size(); 117f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 118f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(specs.get(i))) { 119f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 120f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 121f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 122f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalStart) { 123f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec = ((LocalStart) insn).getLocal(); 124f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(spec)) { 125f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return true; 126f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 127f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 128f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 129f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return false; 130f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 131f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 132f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 133f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #hasAnyLocalInfo} which scrutinizes a single 134f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * register spec. 135de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 13699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code non-null;} spec to scrutinize 13799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code true} iff the spec refers to any 138f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * named locals 139f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 140f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static boolean hasLocalInfo(RegisterSpec spec) { 141f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return (spec != null) 142f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project && (spec.getLocalItem().getName() != null); 143f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 144f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 145f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 146f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Returns the set of all constants referred to by instructions added 147f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to this instance. 148de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 14999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the set of constants 150f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 151f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public HashSet<Constant> getAllConstants() { 152f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project HashSet<Constant> result = new HashSet<Constant>(20); 153f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 154f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (DalvInsn insn : insns) { 155f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, insn); 156f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 157f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 158f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 159f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 160f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 161f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 162f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #getAllConstants} which adds all the info for 163f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a single instruction. 164de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 16599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param result {@code non-null;} result set to add to 16699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} instruction to scrutinize 167f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 168f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void addConstants(HashSet<Constant> result, 169f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn) { 170f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof CstInsn) { 171f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Constant cst = ((CstInsn) insn).getConstant(); 172f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(cst); 173f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalSnapshot) { 174f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecSet specs = ((LocalSnapshot) insn).getLocals(); 175f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = specs.size(); 176f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 177f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, specs.get(i)); 178f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 179f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else if (insn instanceof LocalStart) { 180f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec = ((LocalStart) insn).getLocal(); 181f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project addConstants(result, spec); 182f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 183f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 184f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 185f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 186f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #getAllConstants} which adds all the info for 18799409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * a single {@code RegisterSpec}. 188f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 18999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param result {@code non-null;} result set to add to 19099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param spec {@code null-ok;} register spec to add 191f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 192f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void addConstants(HashSet<Constant> result, 193f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpec spec) { 194f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (spec == null) { 195f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return; 196f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 197de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 198f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project LocalItem local = spec.getLocalItem(); 199f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstUtf8 name = local.getName(); 200f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstUtf8 signature = local.getSignature(); 201f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Type type = spec.getType(); 202f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 203f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (type != Type.KNOWN_NULL) { 204f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(CstType.intern(type)); 205f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 206f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 207f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (name != null) { 208f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(name); 209f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 210f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 211f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (signature != null) { 212f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(signature); 213f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 214f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 215f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 216f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 217f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Adds an instruction to the output. 218de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 219de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * @param insn {@code non-null;} the instruction to add 220f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 221f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void add(DalvInsn insn) { 222f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(insn); 223f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateInfo(insn); 224f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 225f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 226f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 227f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Inserts an instruction in the output at the given offset. 228de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 22999409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param at {@code >= 0;} what index to insert at 23099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction to insert 231f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 232f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void insert(int at, DalvInsn insn) { 233f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(at, insn); 234f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project updateInfo(insn); 235f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 236f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 237f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 238f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #add} and {@link #insert}, 239f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * which updates the position and local info flags. 240de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 24199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} an instruction that was just introduced 242f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 243f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void updateInfo(DalvInsn insn) { 244f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! hasAnyPositionInfo) { 245f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project SourcePosition pos = insn.getPosition(); 246f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (pos.getLine() >= 0) { 247f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasAnyPositionInfo = true; 248f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 249f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 250f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 251f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (! hasAnyLocalInfo) { 252f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (hasLocalInfo(insn)) { 253f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project hasAnyLocalInfo = true; 254f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 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 * Reverses a branch which is buried a given number of instructions 260f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * backward in the output. It is illegal to call this unless the 261f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * indicated instruction really is a reversible branch. 262de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 263f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @param which how many instructions back to find the branch; 26499409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code 0} is the most recently added instruction, 26599409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * {@code 1} is the instruction before that, etc. 266380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param newTarget {@code non-null;} the new target for the 267380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * reversed branch 268f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 269f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void reverseBranch(int which, CodeAddress newTarget) { 270f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 271f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int index = size - which - 1; 272f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn targetInsn; 273f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 274f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 275f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project targetInsn = (TargetInsn) insns.get(index); 276f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (IndexOutOfBoundsException ex) { 277f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 278f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("too few instructions"); 279f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ClassCastException ex) { 280f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Translate the exception. 281f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalArgumentException("non-reversible instruction"); 282f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 283f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 284f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 285f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * No need to call this.set(), since the format and other info 286f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * are the same. 287f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 288f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(index, targetInsn.withNewTargetAndReversed(newTarget)); 289f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 290f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 291f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 292f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Assigns indices in all instructions that need them, using the 293f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * given callback to perform lookups. This should be called before 294f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * calling {@link #finishProcessingAndGetList}. 295de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 29699409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param callback {@code non-null;} callback object 297f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 298f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public void assignIndices(DalvCode.AssignIndicesCallback callback) { 299f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (DalvInsn insn : insns) { 300f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (insn instanceof CstInsn) { 301f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignIndices((CstInsn) insn, callback); 302f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 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 * Helper for {@link #assignIndices} which does assignment for one 308f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction. 309de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 31099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction 31199409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param callback {@code non-null;} the callback 312f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 313f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private static void assignIndices(CstInsn insn, 314f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvCode.AssignIndicesCallback callback) { 315f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project Constant cst = insn.getConstant(); 316f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int index = callback.getIndex(cst); 317f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 318f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (index >= 0) { 319f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setIndex(index); 320f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 321f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 322f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (cst instanceof CstMemberRef) { 323f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstMemberRef member = (CstMemberRef) cst; 324f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CstType definer = member.getDefiningClass(); 325f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project index = callback.getIndex(definer); 326f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (index >= 0) { 327f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setClassIndex(index); 328f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 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 * Does final processing on this instance and gets the output as 334f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * a {@link DalvInsnList}. Final processing consists of: 335de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 336f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <ul> 337f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>optionally renumbering registers (to make room as needed for 338f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * expanded instructions)</li> 339f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>picking a final opcode for each instruction</li> 340f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>rewriting instructions, because of register number, 341f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * constant pool index, or branch target size issues</li> 342f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <li>assigning final addresses</li> 343f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * </ul> 344de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 345f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p><b>Note:</b> This method may only be called once per instance 346f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * of this class.</p> 347f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 34899409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the output list 349f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @throws UnsupportedOperationException if this method has 350f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * already been called 351f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 352f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project public DalvInsnList finishProcessingAndGetList() { 353f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedCount >= 0) { 354f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException("already processed"); 355f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 356f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 357380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop[] opcodes = makeOpcodesArray(); 358380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein reserveRegisters(opcodes); 359380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein massageInstructions(opcodes); 360f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignAddressesAndFixBranches(); 361f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 362f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return DalvInsnList.makeImmutable(insns, 363f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedCount + unreservedRegCount); 364f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 365f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 366f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 367f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which extracts 368380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * the opcode out of each instruction into a separate array, to be 369f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * further manipulated as things progress. 370de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 371380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @return {@code non-null;} the array of opcodes 372f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 373380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private Dop[] makeOpcodesArray() { 374f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 375380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop[] result = new Dop[size]; 376f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 377f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 378380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein result[i] = insns.get(i).getOpcode(); 379f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 380f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 381f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 382f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 383f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 384f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 385f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which figures 386f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * out how many reserved registers are required and then reserving 387380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * them. It also updates the given {@code opcodes} array so 388f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * as to avoid extra work when constructing the massaged 389f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction list. 390de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 391380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 392380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 393f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 394380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private void reserveRegisters(Dop[] opcodes) { 395f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int oldReservedCount = (reservedCount < 0) ? 0 : reservedCount; 396de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 397f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 398f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Call calculateReservedCount() and then perform register 399f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * reservation, repeatedly until no new reservations happen. 400f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 401f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 402380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein int newReservedCount = calculateReservedCount(opcodes); 403f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (oldReservedCount >= newReservedCount) { 404f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 405f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 406f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 407f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int reservedDifference = newReservedCount - oldReservedCount; 408f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 409f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 410f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 411f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 412f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * CodeAddress instance identity is used to link 413f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * TargetInsns to their targets, so it is 414f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * inappropriate to make replacements, and they don't 415f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have registers in any case. Hence, the instanceof 416f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * test below. 417f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 418f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 419f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(insn instanceof CodeAddress)) { 420f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 421f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * No need to call this.set() since the format and 422f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * other info are the same. 423de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro */ 424f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, insn.withRegisterOffset(reservedDifference)); 425f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 426f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 427f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 428f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project oldReservedCount = newReservedCount; 429f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 430f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 431f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project reservedCount = oldReservedCount; 432f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 433f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 434f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 435f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #reserveRegisters}, which does one 436f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * pass over the instructions, calculating the number of 437f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers that need to be reserved. It also updates the 438380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * {@code opcodes} list to help avoid extra work in future 439f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * register reservation passes. 440de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 441380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 442380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 44399409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code >= 0;} the count of reserved registers 444f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 445380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private int calculateReservedCount(Dop[] opcodes) { 446f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 447f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 448f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 449f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Potential new value of reservedCount, which gets updated in the 450f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * following loop. It starts out with the existing reservedCount 451f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and gets increased if it turns out that additional registers 452f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * need to be reserved. 453f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 454f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int newReservedCount = reservedCount; 455f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 456f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 457f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 458380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = opcodes[i]; 459380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop newOpcode = findOpcodeForInsn(insn, originalOpcode); 460f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 461380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (newOpcode == null) { 462f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 463dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * The instruction will need to be expanded, so find the 464dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * expanded opcode and reserve registers for it. 465f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 466dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao Dop expandedOp = findExpandedOpcodeForInsn(insn); 467dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao BitSet compatRegs = expandedOp.getFormat().compatibleRegs(insn); 468dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao int reserve = insn.getMinimumRegisterRequirement(compatRegs); 469f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reserve > newReservedCount) { 470f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newReservedCount = reserve; 471f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 472dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao } else if (originalOpcode == newOpcode) { 473dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao continue; 474f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 475f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 476380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein opcodes[i] = newOpcode; 477f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 478f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 479f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return newReservedCount; 480f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 481f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 482f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 483380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * Attempts to fit the given instruction into a specific opcode, 484380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * returning the opcode whose format that the instruction fits 485380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * into or {@code null} to indicate that the instruction will need 486380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * to be expanded. This fitting process starts with the given 487380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode as a first "best guess" and then pessimizes from there 488380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * if necessary. 489f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * 49099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @param insn {@code non-null;} the instruction in question 491380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param guess {@code null-ok;} the current guess as to the best 492380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode; {@code null} means that no simple opcode fits 493380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @return {@code null-ok;} a possibly-different opcode; either a 494380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * {@code non-null} good fit or {@code null} to indicate that no 495380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * simple opcode fits 496f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 497380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private Dop findOpcodeForInsn(DalvInsn insn, Dop guess) { 498380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein /* 499380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * Note: The initial guess might be null, meaning that an 500380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * earlier call to this method already determined that there 501380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * was no possible simple opcode fit. 502380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein */ 503f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 504380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein while (guess != null) { 505380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (guess.getFormat().isCompatible(insn)) { 506f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 507f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 508380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein 5093dfda9ad1964510e4a7948a240b30cd710e86341Dan Bornstein guess = Dops.getNextOrNull(guess, dexOptions); 510f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 511f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 512380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein return guess; 513f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 514de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 515f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 516dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * Finds the proper opcode for the given instruction, ignoring 517dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * register constraints. 518dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * 519dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * @param insn {@code non-null;} the instruction in question 520dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao * @return {@code non-null;} the opcode that fits 521dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao */ 522dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao private Dop findExpandedOpcodeForInsn(DalvInsn insn) { 523ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson Dop result = findOpcodeForInsn(insn.getLowRegVersion(), insn.getOpcode()); 524ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson if (result == null) { 525ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson throw new AssertionError(); 526ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson } 527ed0fe6c2f310f8c2cc28c35c2b473d8de36db8a4Jesse Wilson return result; 528dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao } 529dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao 530dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao /** 531f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which goes 532f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * through each instruction in the output, making sure its opcode 533f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * can accomodate its arguments. In cases where the opcode is 534f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * unable to do so, this replaces the instruction with a larger 535f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * instruction with identical semantics that <i>will</i> work. 536de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 537f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method may also reserve a number of low-numbered 538f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * registers, renumbering the instructions' original registers, in 539f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * order to have register space available in which to move 540f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * very-high registers when expanding instructions into 541f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * multi-instruction sequences. This expansion is done when no 542f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * simple instruction format can be found for a given instruction that 543f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is able to accomodate that instruction's registers.</p> 544de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 545f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * <p>This method ignores issues of branch target size, since 546f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * final addresses aren't known at the point that this method is 547f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * called.</p> 548de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 549380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 550380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 551f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 552380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private void massageInstructions(Dop[] opcodes) { 553f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (reservedCount == 0) { 554f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 555f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The easy common case: No registers were reserved, so we 556380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * merely need to replace any instructions whose format 557380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * (and hence whose opcode) changed during the reservation 558380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * pass, but all instructions will stay at their original 559380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * indices, and the instruction list doesn't grow. 560f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 561f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 562f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 563f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 564f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 565380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = insn.getOpcode(); 566380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop currentOpcode = opcodes[i]; 567f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 568380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (originalOpcode != currentOpcode) { 569380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns.set(i, insn.withOpcode(currentOpcode)); 570f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 571f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 572f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 573f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 574f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The difficult uncommon case: Some instructions have to be 575f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * expanded to deal with high registers. 576f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 577380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns = performExpansion(opcodes); 578f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 579f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 580f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 581f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 582f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #massageInstructions}, which constructs a 583f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * replacement list, where each {link DalvInsn} instance that 584f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * couldn't be represented simply (due to register representation 585f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * problems) is expanded into a series of instances that together 586f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * perform the proper function. 587de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 588380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * @param opcodes {@code non-null;} array of per-instruction 589380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein * opcode selections 59099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * @return {@code non-null;} the replacement list 591f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 592380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein private ArrayList<DalvInsn> performExpansion(Dop[] opcodes) { 593f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 594f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project ArrayList<DalvInsn> result = new ArrayList<DalvInsn>(size * 2); 595f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 596f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 597f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 598380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop originalOpcode = insn.getOpcode(); 599380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop currentOpcode = opcodes[i]; 600f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn prefix; 601f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn suffix; 602f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 603380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (currentOpcode != null) { 604f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // No expansion is necessary. 605f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project prefix = null; 606f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project suffix = null; 607f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 608f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // Expansion is required. 609dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao currentOpcode = findExpandedOpcodeForInsn(insn); 610dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao BitSet compatRegs = 611dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao currentOpcode.getFormat().compatibleRegs(insn); 612dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao prefix = insn.expandedPrefix(compatRegs); 613dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao suffix = insn.expandedSuffix(compatRegs); 614dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao 615dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao // Expand necessary registers to fit the new format 616dd79e4e11fa20d6677b70ce6618a8653a1f3520djeffhao insn = insn.expandedVersion(compatRegs); 617f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 618f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 619f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (prefix != null) { 620f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(prefix); 621f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 622de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 623380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (currentOpcode != originalOpcode) { 624380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insn = insn.withOpcode(currentOpcode); 625f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 626f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(insn); 627f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 628f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (suffix != null) { 629f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project result.add(suffix); 630f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 631f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 632de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro 633f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return result; 634f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 635f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 636f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 637f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #finishProcessingAndGetList}, which assigns 638f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * addresses to each instruction, possibly rewriting branches to 639f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * fix ones that wouldn't otherwise be able to reach their 640f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * targets. 641f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 642f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void assignAddressesAndFixBranches() { 643f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (;;) { 644f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project assignAddresses(); 645f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!fixBranches()) { 646f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project break; 647f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 648f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 649f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 650f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 651f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 652f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #assignAddressesAndFixBranches}, which 653f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * assigns an address to each instruction, in order. 654f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 655f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private void assignAddresses() { 656f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int address = 0; 657f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 658f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 659f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 660f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 661f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insn.setAddress(address); 662f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project address += insn.codeSize(); 663f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 664f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 665f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 666f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /** 667f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Helper for {@link #assignAddressesAndFixBranches}, which checks 668f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * the branch target size requirement of each branch instruction 669f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to make sure it fits. For instructions that don't fit, this 67099409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * rewrites them to use a {@code goto} of some sort. In the 671f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * case of a conditional branch that doesn't fit, the sense of the 67299409883d9c4c0ffb49b070ce307bb33a9dfe9f1The Android Open Source Project * test is reversed in order to branch around a {@code goto} 673f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the original target. 674de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 675f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * @return whether any branches had to be fixed 676f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 677f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project private boolean fixBranches() { 678f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project int size = insns.size(); 679f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project boolean anyFixed = false; 680f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 681f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project for (int i = 0; i < size; i++) { 682f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project DalvInsn insn = insns.get(i); 683f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project if (!(insn instanceof TargetInsn)) { 684f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // This loop only needs to inspect TargetInsns. 685f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 686f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 687f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 688380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein Dop opcode = insn.getOpcode(); 689f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn target = (TargetInsn) insn; 690f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 691380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (opcode.getFormat().branchFits(target)) { 692f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project continue; 693f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 694f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 6957ba91291bb6ce64691398a8751656207e8e3e98dDan Bornstein if (opcode.getFamily() == Opcodes.GOTO) { 696f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // It is a goto; widen it if possible. 697380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein opcode = findOpcodeForInsn(insn, opcode); 698380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein if (opcode == null) { 699f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 700f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * The branch is already maximally large. This should 701f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * only be possible if a method somehow manages to have 702f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * more than 2^31 code units. 703f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 704f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new UnsupportedOperationException("method too long"); 705f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 706380dc65454b24ee89274ed26b1188386ece7ccdcDan Bornstein insns.set(i, insn.withOpcode(opcode)); 707f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } else { 708f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project /* 709f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * It is a conditional: Reverse its sense, and arrange for 710f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * it to branch around an absolute goto to the original 711f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * branch target. 712de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 713f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Note: An invariant of the list being processed is 714f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * that every TargetInsn is followed by a CodeAddress. 715f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Hence, it is always safe to get the next element 716f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * after a TargetInsn and cast it to CodeAddress, as 717f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * is happening a few lines down. 718de75089fb7216d19e9c22cce4dc62a49513477d3Carl Shapiro * 719f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * Also note: Size gets incremented by one here, as we 720f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * have -- in the net -- added one additional element 721f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * to the list, so we increment i to match. The added 722f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * and changed elements will be inspected by a repeat 723f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project * call to this method after this invocation returns. 724f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project */ 725f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project CodeAddress newTarget; 726f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project try { 727f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project newTarget = (CodeAddress) insns.get(i + 1); 728f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (IndexOutOfBoundsException ex) { 729f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The TargetInsn / CodeAddress invariant was violated. 730f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalStateException( 731f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project "unpaired TargetInsn (dangling)"); 732f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } catch (ClassCastException ex) { 733f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project // The TargetInsn / CodeAddress invariant was violated. 734f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project throw new IllegalStateException("unpaired TargetInsn"); 735f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 736f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project TargetInsn gotoInsn = 737f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project new TargetInsn(Dops.GOTO, target.getPosition(), 738f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project RegisterSpecList.EMPTY, target.getTarget()); 739f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.set(i, gotoInsn); 740f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project insns.add(i, target.withNewTargetAndReversed(newTarget)); 741f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project size++; 742f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project i++; 743f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 744f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 745f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project anyFixed = true; 746f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 747f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project 748f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project return anyFixed; 749f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project } 750f6c387128427e121477c1b32ad35cdcaa5101ba3The Android Open Source Project} 751