AnalyzedInstruction.java revision ef24b31c9872b24f60c88bdae9b2d8c93eb36fee
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 29package org.jf.dexlib.Code.Analysis; 30 31import org.jf.dexlib.Code.*; 32import org.jf.dexlib.Item; 33import org.jf.dexlib.ItemType; 34import org.jf.dexlib.MethodIdItem; 35import org.jf.dexlib.Util.ExceptionWithContext; 36 37import java.util.*; 38 39public 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 /** 78 * A dead instruction is one that is unreachable because it follows an odexed instruction that can't be deodexed 79 * because it's object register is always null. In the non-odexed code that the odex was generated from, we would 80 * have technically considered this code reachable and could verify it, even though the instruction that ended up 81 * being odexed was always null, because we would assume both "paths" out of the instruction are valid - the one 82 * where execution proceeds normally to the next instruction, and the one where an exception occurs and execution 83 * either goes to a catch block, or out of the method. 84 * 85 * However, in the odexed case, we can't verify the code following an undeodexable instruction because we lack 86 * the register information from the undeodexable instruction - because we don't know the actual method or field 87 * that is being accessed. 88 * 89 * The undeodexable instruction is guaranteed to throw an NPE, so the following code is effectivetly unreachable. 90 * Once we detect an undeodexeable instruction, the following code is marked as dead up until a non-dead execution 91 * path merges in. Additionally, we remove the predecessors/successors of any dead instruction. For example, if 92 * there is a dead goto instruction, then we would remove the target instruction as a successor, and we would 93 * also remove the dead goto instruction as a predecessor to the target. 94 */ 95 protected boolean dead = false; 96 97 public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) { 98 this.instruction = instruction; 99 this.originalInstruction = instruction; 100 this.instructionIndex = instructionIndex; 101 this.postRegisterMap = new RegisterType[registerCount]; 102 this.preRegisterMap = new RegisterType[registerCount]; 103 RegisterType unknown = RegisterType.getRegisterType(RegisterType.Category.Unknown, null); 104 for (int i=0; i<registerCount; i++) { 105 preRegisterMap[i] = unknown; 106 postRegisterMap[i] = unknown; 107 } 108 } 109 110 public int getInstructionIndex() { 111 return instructionIndex; 112 } 113 114 public int getPredecessorCount() { 115 return predecessors.size(); 116 } 117 118 public SortedSet<AnalyzedInstruction> getPredecessors() { 119 return Collections.unmodifiableSortedSet(predecessors); 120 } 121 122 protected boolean addPredecessor(AnalyzedInstruction predecessor) { 123 return predecessors.add(predecessor); 124 } 125 126 protected void addSuccessor(AnalyzedInstruction successor) { 127 successors.add(successor); 128 } 129 130 protected void setDeodexedInstruction(Instruction instruction) { 131 assert originalInstruction.opcode.odexOnly(); 132 this.instruction = instruction; 133 } 134 135 protected void restoreOdexedInstruction() { 136 assert originalInstruction.opcode.odexOnly(); 137 instruction = originalInstruction; 138 } 139 140 public int getSuccessorCount() { 141 return successors.size(); 142 } 143 144 public List<AnalyzedInstruction> getSuccesors() { 145 return Collections.unmodifiableList(successors); 146 } 147 148 public Instruction getInstruction() { 149 return instruction; 150 } 151 152 public Instruction getOriginalInstruction() { 153 return originalInstruction; 154 } 155 156 public boolean isDead() { 157 return dead; 158 } 159 160 /** 161 * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction 162 * that can be the first successfully executed instruction in the method. The first instruction is always a 163 * beginning instruction. If the first instruction can throw an exception, and is covered by a try block, then 164 * the first instruction of any exception handler for that try block is also a beginning instruction. And likewise, 165 * if any of those instructions can throw an exception and are covered by try blocks, the first instruction of the 166 * corresponding exception handler is a beginning instruction, etc. 167 * 168 * To determine this, we simply check if the first predecessor is the fake "StartOfMethod" instruction, which has 169 * an instruction index of -1. 170 * @return a boolean value indicating whether this instruction is a beginning instruction 171 */ 172 public boolean isBeginningInstruction() { 173 //if this instruction has no predecessors, it is either the fake "StartOfMethod" instruction or it is an 174 //unreachable instruction. 175 if (predecessors.size() == 0) { 176 return false; 177 } 178 179 if (predecessors.first().instructionIndex == -1) { 180 return true; 181 } 182 return false; 183 } 184 185 /* 186 * Merges the given register type into the specified pre-instruction register, and also sets the post-instruction 187 * register type accordingly if it isn't a destination register for this instruction 188 * @param registerNumber Which register to set 189 * @param registerType The register type 190 * @returns true If the post-instruction register type was changed. This might be false if either the specified 191 * register is a destination register for this instruction, or if the pre-instruction register type didn't change 192 * after merging in the given register type 193 */ 194 protected boolean mergeRegister(int registerNumber, RegisterType registerType, BitSet verifiedInstructions) { 195 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 196 assert registerType != null; 197 198 RegisterType oldRegisterType = preRegisterMap[registerNumber]; 199 RegisterType mergedRegisterType = oldRegisterType.merge(registerType); 200 201 if (mergedRegisterType == oldRegisterType) { 202 return false; 203 } 204 205 preRegisterMap[registerNumber] = mergedRegisterType; 206 verifiedInstructions.clear(instructionIndex); 207 208 if (!setsRegister(registerNumber)) { 209 postRegisterMap[registerNumber] = mergedRegisterType; 210 return true; 211 } 212 213 return false; 214 } 215 216 /** 217 * Iterates over the predecessors of this instruction, and merges all the post-instruction register types for the 218 * given register. Any dead, unreachable, or odexed predecessor is ignored 219 * @param registerNumber the register number 220 * @return The register type resulting from merging the post-instruction register types from all predecessors 221 */ 222 protected RegisterType mergePreRegisterTypeFromPredecessors(int registerNumber) { 223 RegisterType mergedRegisterType = null; 224 for (AnalyzedInstruction predecessor: predecessors) { 225 RegisterType predecessorRegisterType = predecessor.postRegisterMap[registerNumber]; 226 assert predecessorRegisterType != null; 227 mergedRegisterType = predecessorRegisterType.merge(mergedRegisterType); 228 } 229 return mergedRegisterType; 230 } 231 232 /* 233 * Sets the "post-instruction" register type as indicated. 234 * @param registerNumber Which register to set 235 * @param registerType The "post-instruction" register type 236 * @returns true if the given register type is different than the existing post-instruction register type 237 */ 238 protected boolean setPostRegisterType(int registerNumber, RegisterType registerType) { 239 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 240 assert registerType != null; 241 242 RegisterType oldRegisterType = postRegisterMap[registerNumber]; 243 if (oldRegisterType == registerType) { 244 return false; 245 } 246 247 postRegisterMap[registerNumber] = registerType; 248 return true; 249 } 250 251 252 protected boolean isInvokeInit() { 253 if (instruction == null || 254 (instruction.opcode != Opcode.INVOKE_DIRECT && instruction.opcode != Opcode.INVOKE_DIRECT_RANGE && 255 instruction.opcode != Opcode.INVOKE_DIRECT_EMPTY)) { 256 return false; 257 } 258 259 //TODO: check access flags instead of name? 260 261 InstructionWithReference instruction = (InstructionWithReference)this.instruction; 262 Item item = instruction.getReferencedItem(); 263 assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM; 264 MethodIdItem method = (MethodIdItem)item; 265 266 if (!method.getMethodName().getStringValue().equals("<init>")) { 267 return false; 268 } 269 270 return true; 271 } 272 273 public boolean setsRegister() { 274 return instruction.opcode.setsRegister(); 275 } 276 277 public boolean setsWideRegister() { 278 return instruction.opcode.setsWideRegister(); 279 } 280 281 public boolean setsRegister(int registerNumber) { 282 //When constructing a new object, the register type will be an uninitialized reference after the new-instance 283 //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke 284 //instructions don't normally change any registers, calling an <init> method will change the type of its 285 //object register. If the uninitialized reference has been copied to other registers, they will be initialized 286 //as well, so we need to check for that too 287 if (isInvokeInit()) { 288 int destinationRegister; 289 if (instruction instanceof FiveRegisterInstruction) { 290 destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterD(); 291 } else { 292 assert instruction instanceof RegisterRangeInstruction; 293 RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction; 294 assert rangeInstruction.getRegCount() > 0; 295 destinationRegister = rangeInstruction.getStartRegister(); 296 } 297 298 if (registerNumber == destinationRegister) { 299 return true; 300 } 301 RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber); 302 if (preInstructionDestRegisterType.category != RegisterType.Category.UninitRef && 303 preInstructionDestRegisterType.category != RegisterType.Category.UninitThis) { 304 305 return false; 306 } 307 //check if the uninit ref has been copied to another register 308 if (getPreInstructionRegisterType(registerNumber) == preInstructionDestRegisterType) { 309 return true; 310 } 311 return false; 312 } 313 314 if (!setsRegister()) { 315 return false; 316 } 317 int destinationRegister = getDestinationRegister(); 318 319 if (registerNumber == destinationRegister) { 320 return true; 321 } 322 if (setsWideRegister() && registerNumber == (destinationRegister + 1)) { 323 return true; 324 } 325 return false; 326 } 327 328 public int getDestinationRegister() { 329 if (!this.instruction.opcode.setsRegister()) { 330 throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " + 331 "store a value"); 332 } 333 return ((SingleRegisterInstruction)instruction).getRegisterA(); 334 } 335 336 public int getRegisterCount() { 337 return postRegisterMap.length; 338 } 339 340 public RegisterType getPostInstructionRegisterType(int registerNumber) { 341 return postRegisterMap[registerNumber]; 342 } 343 344 public RegisterType getPreInstructionRegisterType(int registerNumber) { 345 return preRegisterMap[registerNumber]; 346 } 347 348 public int compareTo(AnalyzedInstruction analyzedInstruction) { 349 //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? 350 if (instructionIndex < analyzedInstruction.instructionIndex) { 351 return -1; 352 } else if (instructionIndex == analyzedInstruction.instructionIndex) { 353 return 0; 354 } else { 355 return 1; 356 } 357 } 358} 359 360