1 /* 2 * [The "BSD licence"] 3 * Copyright (c) 2010 Ben Gruver (JesusFreke) 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 package org.jf.dexlib.Code.Analysis; 30 31 import org.jf.dexlib.Code.*; 32 import org.jf.dexlib.Item; 33 import org.jf.dexlib.ItemType; 34 import org.jf.dexlib.MethodIdItem; 35 import org.jf.dexlib.Util.ExceptionWithContext; 36 37 import java.util.*; 38 39 public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { 40 /** 41 * The actual instruction 42 */ 43 protected Instruction instruction; 44 45 /** 46 * The index of the instruction, where the first instruction in the method is at index 0, and so on 47 */ 48 protected final int instructionIndex; 49 50 /** 51 * Instructions that can pass on execution to this one during normal execution 52 */ 53 protected final TreeSet<AnalyzedInstruction> predecessors = new TreeSet<AnalyzedInstruction>(); 54 55 /** 56 * Instructions that can execution could pass on to next during normal execution 57 */ 58 protected final LinkedList<AnalyzedInstruction> successors = new LinkedList<AnalyzedInstruction>(); 59 60 /** 61 * This contains the register types *before* the instruction has executed 62 */ 63 protected final RegisterType[] preRegisterMap; 64 65 /** 66 * This contains the register types *after* the instruction has executed 67 */ 68 protected final RegisterType[] postRegisterMap; 69 70 /** 71 * When deodexing, we might need to deodex this instruction multiple times, when we merge in new register 72 * information. When this happens, we need to restore the original (odexed) instruction, so we can deodex it again 73 */ 74 protected final Instruction originalInstruction; 75 76 /** 77 * An analyzed instruction's "deadness" is set during analysis (i.e. MethodAnalyzer.analyzer()). A dead instruction 78 * is one that the analyzer never reaches. This occurs either with natural "dead code" - code that simply has no 79 * code path that can ever reach it, or code that follows an odexed instruction that can't be deodexed. 80 */ 81 protected boolean dead = false; 82 83 public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) { 84 this.instruction = instruction; 85 this.originalInstruction = instruction; 86 this.instructionIndex = instructionIndex; 87 this.postRegisterMap = new RegisterType[registerCount]; 88 this.preRegisterMap = new RegisterType[registerCount]; 89 RegisterType unknown = RegisterType.getRegisterType(RegisterType.Category.Unknown, null); 90 for (int i=0; i<registerCount; i++) { 91 preRegisterMap[i] = unknown; 92 postRegisterMap[i] = unknown; 93 } 94 } 95 96 public int getInstructionIndex() { 97 return instructionIndex; 98 } 99 100 public int getPredecessorCount() { 101 return predecessors.size(); 102 } 103 104 public SortedSet<AnalyzedInstruction> getPredecessors() { 105 return Collections.unmodifiableSortedSet(predecessors); 106 } 107 108 protected boolean addPredecessor(AnalyzedInstruction predecessor) { 109 return predecessors.add(predecessor); 110 } 111 112 protected void addSuccessor(AnalyzedInstruction successor) { 113 successors.add(successor); 114 } 115 116 protected void setDeodexedInstruction(Instruction instruction) { 117 assert originalInstruction.opcode.odexOnly(); 118 this.instruction = instruction; 119 } 120 121 protected void restoreOdexedInstruction() { 122 assert originalInstruction.opcode.odexOnly(); 123 instruction = originalInstruction; 124 } 125 126 public int getSuccessorCount() { 127 return successors.size(); 128 } 129 130 public List<AnalyzedInstruction> getSuccesors() { 131 return Collections.unmodifiableList(successors); 132 } 133 134 public Instruction getInstruction() { 135 return instruction; 136 } 137 138 public Instruction getOriginalInstruction() { 139 return originalInstruction; 140 } 141 142 public boolean isDead() { 143 return dead; 144 } 145 146 /** 147 * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction 148 * that can be the first successfully executed instruction in the method. The first instruction is always a 149 * beginning instruction. If the first instruction can throw an exception, and is covered by a try block, then 150 * the first instruction of any exception handler for that try block is also a beginning instruction. And likewise, 151 * if any of those instructions can throw an exception and are covered by try blocks, the first instruction of the 152 * corresponding exception handler is a beginning instruction, etc. 153 * 154 * To determine this, we simply check if the first predecessor is the fake "StartOfMethod" instruction, which has 155 * an instruction index of -1. 156 * @return a boolean value indicating whether this instruction is a beginning instruction 157 */ 158 public boolean isBeginningInstruction() { 159 //if this instruction has no predecessors, it is either the fake "StartOfMethod" instruction or it is an 160 //unreachable instruction. 161 if (predecessors.size() == 0) { 162 return false; 163 } 164 165 if (predecessors.first().instructionIndex == -1) { 166 return true; 167 } 168 return false; 169 } 170 171 /* 172 * Merges the given register type into the specified pre-instruction register, and also sets the post-instruction 173 * register type accordingly if it isn't a destination register for this instruction 174 * @param registerNumber Which register to set 175 * @param registerType The register type 176 * @returns true If the post-instruction register type was changed. This might be false if either the specified 177 * register is a destination register for this instruction, or if the pre-instruction register type didn't change 178 * after merging in the given register type 179 */ 180 protected boolean mergeRegister(int registerNumber, RegisterType registerType, BitSet verifiedInstructions) { 181 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 182 assert registerType != null; 183 184 RegisterType oldRegisterType = preRegisterMap[registerNumber]; 185 RegisterType mergedRegisterType = oldRegisterType.merge(registerType); 186 187 if (mergedRegisterType == oldRegisterType) { 188 return false; 189 } 190 191 preRegisterMap[registerNumber] = mergedRegisterType; 192 verifiedInstructions.clear(instructionIndex); 193 194 if (!setsRegister(registerNumber)) { 195 postRegisterMap[registerNumber] = mergedRegisterType; 196 return true; 197 } 198 199 return false; 200 } 201 202 /** 203 * Iterates over the predecessors of this instruction, and merges all the post-instruction register types for the 204 * given register. Any dead, unreachable, or odexed predecessor is ignored 205 * @param registerNumber the register number 206 * @return The register type resulting from merging the post-instruction register types from all predecessors 207 */ 208 protected RegisterType mergePreRegisterTypeFromPredecessors(int registerNumber) { 209 RegisterType mergedRegisterType = null; 210 for (AnalyzedInstruction predecessor: predecessors) { 211 RegisterType predecessorRegisterType = predecessor.postRegisterMap[registerNumber]; 212 assert predecessorRegisterType != null; 213 mergedRegisterType = predecessorRegisterType.merge(mergedRegisterType); 214 } 215 return mergedRegisterType; 216 } 217 218 /* 219 * Sets the "post-instruction" register type as indicated. 220 * @param registerNumber Which register to set 221 * @param registerType The "post-instruction" register type 222 * @returns true if the given register type is different than the existing post-instruction register type 223 */ 224 protected boolean setPostRegisterType(int registerNumber, RegisterType registerType) { 225 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 226 assert registerType != null; 227 228 RegisterType oldRegisterType = postRegisterMap[registerNumber]; 229 if (oldRegisterType == registerType) { 230 return false; 231 } 232 233 postRegisterMap[registerNumber] = registerType; 234 return true; 235 } 236 237 238 protected boolean isInvokeInit() { 239 if (instruction == null || 240 (instruction.opcode != Opcode.INVOKE_DIRECT && instruction.opcode != Opcode.INVOKE_DIRECT_RANGE && 241 instruction.opcode != Opcode.INVOKE_DIRECT_EMPTY)) { 242 return false; 243 } 244 245 //TODO: check access flags instead of name? 246 247 InstructionWithReference instruction = (InstructionWithReference)this.instruction; 248 Item item = instruction.getReferencedItem(); 249 assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM; 250 MethodIdItem method = (MethodIdItem)item; 251 252 if (!method.getMethodName().getStringValue().equals("<init>")) { 253 return false; 254 } 255 256 return true; 257 } 258 259 public boolean setsRegister() { 260 return instruction.opcode.setsRegister(); 261 } 262 263 public boolean setsWideRegister() { 264 return instruction.opcode.setsWideRegister(); 265 } 266 267 public boolean setsRegister(int registerNumber) { 268 //When constructing a new object, the register type will be an uninitialized reference after the new-instance 269 //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke 270 //instructions don't normally change any registers, calling an <init> method will change the type of its 271 //object register. If the uninitialized reference has been copied to other registers, they will be initialized 272 //as well, so we need to check for that too 273 if (isInvokeInit()) { 274 int destinationRegister; 275 if (instruction instanceof FiveRegisterInstruction) { 276 destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterD(); 277 } else { 278 assert instruction instanceof RegisterRangeInstruction; 279 RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction; 280 assert rangeInstruction.getRegCount() > 0; 281 destinationRegister = rangeInstruction.getStartRegister(); 282 } 283 284 if (registerNumber == destinationRegister) { 285 return true; 286 } 287 RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber); 288 if (preInstructionDestRegisterType.category != RegisterType.Category.UninitRef && 289 preInstructionDestRegisterType.category != RegisterType.Category.UninitThis) { 290 291 return false; 292 } 293 //check if the uninit ref has been copied to another register 294 if (getPreInstructionRegisterType(registerNumber) == preInstructionDestRegisterType) { 295 return true; 296 } 297 return false; 298 } 299 300 if (!setsRegister()) { 301 return false; 302 } 303 int destinationRegister = getDestinationRegister(); 304 305 if (registerNumber == destinationRegister) { 306 return true; 307 } 308 if (setsWideRegister() && registerNumber == (destinationRegister + 1)) { 309 return true; 310 } 311 return false; 312 } 313 314 public int getDestinationRegister() { 315 if (!this.instruction.opcode.setsRegister()) { 316 throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " + 317 "store a value"); 318 } 319 return ((SingleRegisterInstruction)instruction).getRegisterA(); 320 } 321 322 public int getRegisterCount() { 323 return postRegisterMap.length; 324 } 325 326 public RegisterType getPostInstructionRegisterType(int registerNumber) { 327 return postRegisterMap[registerNumber]; 328 } 329 330 public RegisterType getPreInstructionRegisterType(int registerNumber) { 331 return preRegisterMap[registerNumber]; 332 } 333 334 public int compareTo(AnalyzedInstruction analyzedInstruction) { 335 //TODO: out of curiosity, check the disassembly of this to see if it retrieves the value of analyzedInstruction.instructionIndex for every access. It should, because the field is final. What about if we set the field to non-final? 336 if (instructionIndex < analyzedInstruction.instructionIndex) { 337 return -1; 338 } else if (instructionIndex == analyzedInstruction.instructionIndex) { 339 return 0; 340 } else { 341 return 1; 342 } 343 } 344 } 345 346