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 || !instruction.opcode.canInitializeReference()) { 240 return false; 241 } 242 243 //TODO: check access flags instead of name? 244 245 InstructionWithReference instruction = (InstructionWithReference)this.instruction; 246 Item item = instruction.getReferencedItem(); 247 assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM; 248 MethodIdItem method = (MethodIdItem)item; 249 250 if (!method.getMethodName().getStringValue().equals("<init>")) { 251 return false; 252 } 253 254 return true; 255 } 256 257 public boolean setsRegister() { 258 return instruction.opcode.setsRegister(); 259 } 260 261 public boolean setsWideRegister() { 262 return instruction.opcode.setsWideRegister(); 263 } 264 265 public boolean setsRegister(int registerNumber) { 266 //When constructing a new object, the register type will be an uninitialized reference after the new-instance 267 //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke 268 //instructions don't normally change any registers, calling an <init> method will change the type of its 269 //object register. If the uninitialized reference has been copied to other registers, they will be initialized 270 //as well, so we need to check for that too 271 if (isInvokeInit()) { 272 int destinationRegister; 273 if (instruction instanceof FiveRegisterInstruction) { 274 destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterD(); 275 } else { 276 assert instruction instanceof RegisterRangeInstruction; 277 RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction; 278 assert rangeInstruction.getRegCount() > 0; 279 destinationRegister = rangeInstruction.getStartRegister(); 280 } 281 282 if (registerNumber == destinationRegister) { 283 return true; 284 } 285 RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber); 286 if (preInstructionDestRegisterType.category != RegisterType.Category.UninitRef && 287 preInstructionDestRegisterType.category != RegisterType.Category.UninitThis) { 288 289 return false; 290 } 291 //check if the uninit ref has been copied to another register 292 if (getPreInstructionRegisterType(registerNumber) == preInstructionDestRegisterType) { 293 return true; 294 } 295 return false; 296 } 297 298 if (!setsRegister()) { 299 return false; 300 } 301 int destinationRegister = getDestinationRegister(); 302 303 if (registerNumber == destinationRegister) { 304 return true; 305 } 306 if (setsWideRegister() && registerNumber == (destinationRegister + 1)) { 307 return true; 308 } 309 return false; 310 } 311 312 public int getDestinationRegister() { 313 if (!this.instruction.opcode.setsRegister()) { 314 throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " + 315 "store a value"); 316 } 317 return ((SingleRegisterInstruction)instruction).getRegisterA(); 318 } 319 320 public int getRegisterCount() { 321 return postRegisterMap.length; 322 } 323 324 public RegisterType getPostInstructionRegisterType(int registerNumber) { 325 return postRegisterMap[registerNumber]; 326 } 327 328 public RegisterType getPreInstructionRegisterType(int registerNumber) { 329 return preRegisterMap[registerNumber]; 330 } 331 332 public int compareTo(AnalyzedInstruction analyzedInstruction) { 333 //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? 334 if (instructionIndex < analyzedInstruction.instructionIndex) { 335 return -1; 336 } else if (instructionIndex == analyzedInstruction.instructionIndex) { 337 return 0; 338 } else { 339 return 1; 340 } 341 } 342 } 343 344