1 /* 2 * Copyright 2013, Google Inc. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * * Redistributions in binary form must reproduce the above 12 * copyright notice, this list of conditions and the following disclaimer 13 * in the documentation and/or other materials provided with the 14 * distribution. 15 * * Neither the name of Google Inc. nor the names of its 16 * contributors may be used to endorse or promote products derived from 17 * this software without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 package org.jf.dexlib2.analysis; 33 34 import com.google.common.base.Objects; 35 import com.google.common.collect.Maps; 36 import org.jf.dexlib2.iface.instruction.*; 37 import org.jf.dexlib2.iface.reference.MethodReference; 38 import org.jf.dexlib2.iface.reference.Reference; 39 import org.jf.util.ExceptionWithContext; 40 41 import javax.annotation.Nonnull; 42 import javax.annotation.Nullable; 43 import java.util.*; 44 45 public class AnalyzedInstruction implements Comparable<AnalyzedInstruction> { 46 /** 47 * The actual instruction 48 */ 49 protected Instruction instruction; 50 51 /** 52 * The index of the instruction, where the first instruction in the method is at index 0, and so on 53 */ 54 protected final int instructionIndex; 55 56 /** 57 * Instructions that can pass on execution to this one during normal execution 58 */ 59 protected final TreeSet<AnalyzedInstruction> predecessors = new TreeSet<AnalyzedInstruction>(); 60 61 /** 62 * Instructions that can execution could pass on to next during normal execution 63 */ 64 protected final LinkedList<AnalyzedInstruction> successors = new LinkedList<AnalyzedInstruction>(); 65 66 /** 67 * This contains the register types *before* the instruction has executed 68 */ 69 protected final RegisterType[] preRegisterMap; 70 71 /** 72 * This contains the register types *after* the instruction has executed 73 */ 74 protected final RegisterType[] postRegisterMap; 75 76 /** 77 * This contains optional register type overrides for register types from predecessors 78 */ 79 @Nullable 80 protected Map<PredecessorOverrideKey, RegisterType> predecessorRegisterOverrides = null; 81 82 /** 83 * When deodexing, we might need to deodex this instruction multiple times, when we merge in new register 84 * information. When this happens, we need to restore the original (odexed) instruction, so we can deodex it again 85 */ 86 protected final Instruction originalInstruction; 87 88 public AnalyzedInstruction(Instruction instruction, int instructionIndex, int registerCount) { 89 this.instruction = instruction; 90 this.originalInstruction = instruction; 91 this.instructionIndex = instructionIndex; 92 this.postRegisterMap = new RegisterType[registerCount]; 93 this.preRegisterMap = new RegisterType[registerCount]; 94 RegisterType unknown = RegisterType.getRegisterType(RegisterType.UNKNOWN, null); 95 for (int i=0; i<registerCount; i++) { 96 preRegisterMap[i] = unknown; 97 postRegisterMap[i] = unknown; 98 } 99 } 100 101 public int getInstructionIndex() { 102 return instructionIndex; 103 } 104 105 public int getPredecessorCount() { 106 return predecessors.size(); 107 } 108 109 public SortedSet<AnalyzedInstruction> getPredecessors() { 110 return Collections.unmodifiableSortedSet(predecessors); 111 } 112 113 public RegisterType getPredecessorRegisterType(@Nonnull AnalyzedInstruction predecessor, int registerNumber) { 114 if (predecessorRegisterOverrides != null) { 115 RegisterType override = predecessorRegisterOverrides.get( 116 new PredecessorOverrideKey(predecessor, registerNumber)); 117 if (override != null) { 118 return override; 119 } 120 } 121 return predecessor.postRegisterMap[registerNumber]; 122 } 123 124 protected boolean addPredecessor(AnalyzedInstruction predecessor) { 125 return predecessors.add(predecessor); 126 } 127 128 protected void addSuccessor(AnalyzedInstruction successor) { 129 successors.add(successor); 130 } 131 132 protected void setDeodexedInstruction(Instruction instruction) { 133 assert originalInstruction.getOpcode().odexOnly(); 134 this.instruction = instruction; 135 } 136 137 protected void restoreOdexedInstruction() { 138 assert originalInstruction.getOpcode().odexOnly(); 139 instruction = originalInstruction; 140 } 141 142 public int getSuccessorCount() { 143 return successors.size(); 144 } 145 146 public List<AnalyzedInstruction> getSuccesors() { 147 return Collections.unmodifiableList(successors); 148 } 149 150 public Instruction getInstruction() { 151 return instruction; 152 } 153 154 public Instruction getOriginalInstruction() { 155 return originalInstruction; 156 } 157 158 /** 159 * Is this instruction a "beginning instruction". A beginning instruction is defined to be an instruction 160 * that can be the first successfully executed instruction in the method. The first instruction is always a 161 * beginning instruction. If the first instruction can throw an exception, and is covered by a try block, then 162 * the first instruction of any exception handler for that try block is also a beginning instruction. And likewise, 163 * if any of those instructions can throw an exception and are covered by try blocks, the first instruction of the 164 * corresponding exception handler is a beginning instruction, etc. 165 * 166 * To determine this, we simply check if the first predecessor is the fake "StartOfMethod" instruction, which has 167 * an instruction index of -1. 168 * @return a boolean value indicating whether this instruction is a beginning instruction 169 */ 170 public boolean isBeginningInstruction() { 171 //if this instruction has no predecessors, it is either the fake "StartOfMethod" instruction or it is an 172 //unreachable instruction. 173 if (predecessors.size() == 0) { 174 return false; 175 } 176 177 if (predecessors.first().instructionIndex == -1) { 178 return true; 179 } 180 return false; 181 } 182 183 /* 184 * Merges the given register type into the specified pre-instruction register, and also sets the post-instruction 185 * register type accordingly if it isn't a destination register for this instruction 186 * @param registerNumber Which register to set 187 * @param registerType The register type 188 * @returns true If the post-instruction register type was changed. This might be false if either the specified 189 * register is a destination register for this instruction, or if the pre-instruction register type didn't change 190 * after merging in the given register type 191 */ 192 protected boolean mergeRegister(int registerNumber, RegisterType registerType, BitSet verifiedInstructions, 193 boolean override) { 194 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 195 assert registerType != null; 196 197 RegisterType oldRegisterType = preRegisterMap[registerNumber]; 198 199 RegisterType mergedRegisterType; 200 if (override) { 201 mergedRegisterType = getMergedPreRegisterTypeFromPredecessors(registerNumber); 202 } else { 203 mergedRegisterType = oldRegisterType.merge(registerType); 204 } 205 206 if (mergedRegisterType.equals(oldRegisterType)) { 207 return false; 208 } 209 210 preRegisterMap[registerNumber] = mergedRegisterType; 211 verifiedInstructions.clear(instructionIndex); 212 213 if (!setsRegister(registerNumber)) { 214 postRegisterMap[registerNumber] = mergedRegisterType; 215 return true; 216 } 217 218 return false; 219 } 220 221 /** 222 * Iterates over the predecessors of this instruction, and merges all the post-instruction register types for the 223 * given register. Any dead, unreachable, or odexed predecessor is ignored. This takes into account any overridden 224 * predecessor register types 225 * 226 * @param registerNumber the register number 227 * @return The register type resulting from merging the post-instruction register types from all predecessors 228 */ 229 protected RegisterType getMergedPreRegisterTypeFromPredecessors(int registerNumber) { 230 RegisterType mergedRegisterType = null; 231 for (AnalyzedInstruction predecessor: predecessors) { 232 RegisterType predecessorRegisterType = getPredecessorRegisterType(predecessor, registerNumber); 233 if (predecessorRegisterType != null) { 234 if (mergedRegisterType == null) { 235 mergedRegisterType = predecessorRegisterType; 236 } else { 237 mergedRegisterType = predecessorRegisterType.merge(mergedRegisterType); 238 } 239 } 240 } 241 return mergedRegisterType; 242 } 243 /** 244 * Sets the "post-instruction" register type as indicated. 245 * @param registerNumber Which register to set 246 * @param registerType The "post-instruction" register type 247 * @return true if the given register type is different than the existing post-instruction register type 248 */ 249 protected boolean setPostRegisterType(int registerNumber, RegisterType registerType) { 250 assert registerNumber >= 0 && registerNumber < postRegisterMap.length; 251 assert registerType != null; 252 253 RegisterType oldRegisterType = postRegisterMap[registerNumber]; 254 if (oldRegisterType.equals(registerType)) { 255 return false; 256 } 257 258 postRegisterMap[registerNumber] = registerType; 259 return true; 260 } 261 262 /** 263 * Adds an override for a register type from a predecessor. 264 * 265 * This is used to set the register type for only one branch from a conditional jump. 266 * 267 * @param predecessor Which predecessor is being overriden 268 * @param registerNumber The register number of the register being overriden 269 * @param registerType The overridden register type 270 * @param verifiedInstructions 271 * 272 * @return true if the post-instruction register type for this instruction changed as a result of this override 273 */ 274 protected boolean overridePredecessorRegisterType(@Nonnull AnalyzedInstruction predecessor, int registerNumber, 275 @Nonnull RegisterType registerType, BitSet verifiedInstructions) { 276 if (predecessorRegisterOverrides == null) { 277 predecessorRegisterOverrides = Maps.newHashMap(); 278 } 279 predecessorRegisterOverrides.put(new PredecessorOverrideKey(predecessor, registerNumber), registerType); 280 281 RegisterType mergedType = getMergedPreRegisterTypeFromPredecessors(registerNumber); 282 283 if (preRegisterMap[registerNumber].equals(mergedType)) { 284 return false; 285 } 286 287 preRegisterMap[registerNumber] = mergedType; 288 verifiedInstructions.clear(instructionIndex); 289 290 if (!setsRegister(registerNumber)) { 291 if (!postRegisterMap[registerNumber].equals(mergedType)) { 292 postRegisterMap[registerNumber] = mergedType; 293 return true; 294 } 295 } 296 297 return false; 298 } 299 300 protected boolean isInvokeInit() { 301 if (instruction == null || !instruction.getOpcode().canInitializeReference()) { 302 return false; 303 } 304 305 ReferenceInstruction instruction = (ReferenceInstruction)this.instruction; 306 307 Reference reference = instruction.getReference(); 308 if (reference instanceof MethodReference) { 309 return ((MethodReference)reference).getName().equals("<init>"); 310 } 311 312 return false; 313 } 314 315 public boolean setsRegister() { 316 return instruction.getOpcode().setsRegister(); 317 } 318 319 public boolean setsWideRegister() { 320 return instruction.getOpcode().setsWideRegister(); 321 } 322 323 public boolean setsRegister(int registerNumber) { 324 //When constructing a new object, the register type will be an uninitialized reference after the new-instance 325 //instruction, but becomes an initialized reference once the <init> method is called. So even though invoke 326 //instructions don't normally change any registers, calling an <init> method will change the type of its 327 //object register. If the uninitialized reference has been copied to other registers, they will be initialized 328 //as well, so we need to check for that too 329 if (isInvokeInit()) { 330 int destinationRegister; 331 if (instruction instanceof FiveRegisterInstruction) { 332 destinationRegister = ((FiveRegisterInstruction)instruction).getRegisterC(); 333 } else { 334 assert instruction instanceof RegisterRangeInstruction; 335 RegisterRangeInstruction rangeInstruction = (RegisterRangeInstruction)instruction; 336 assert rangeInstruction.getRegisterCount() > 0; 337 destinationRegister = rangeInstruction.getStartRegister(); 338 } 339 340 if (registerNumber == destinationRegister) { 341 return true; 342 } 343 RegisterType preInstructionDestRegisterType = getPreInstructionRegisterType(registerNumber); 344 if (preInstructionDestRegisterType.category != RegisterType.UNINIT_REF && 345 preInstructionDestRegisterType.category != RegisterType.UNINIT_THIS) { 346 347 return false; 348 } 349 //check if the uninit ref has been copied to another register 350 if (getPreInstructionRegisterType(registerNumber).equals(preInstructionDestRegisterType)) { 351 return true; 352 } 353 return false; 354 } 355 356 if (!setsRegister()) { 357 return false; 358 } 359 int destinationRegister = getDestinationRegister(); 360 361 if (registerNumber == destinationRegister) { 362 return true; 363 } 364 if (setsWideRegister() && registerNumber == (destinationRegister + 1)) { 365 return true; 366 } 367 return false; 368 } 369 370 public int getDestinationRegister() { 371 if (!this.instruction.getOpcode().setsRegister()) { 372 throw new ExceptionWithContext("Cannot call getDestinationRegister() for an instruction that doesn't " + 373 "store a value"); 374 } 375 return ((OneRegisterInstruction)instruction).getRegisterA(); 376 } 377 378 public int getRegisterCount() { 379 return postRegisterMap.length; 380 } 381 382 @Nonnull 383 public RegisterType getPostInstructionRegisterType(int registerNumber) { 384 return postRegisterMap[registerNumber]; 385 } 386 387 @Nonnull 388 public RegisterType getPreInstructionRegisterType(int registerNumber) { 389 return preRegisterMap[registerNumber]; 390 } 391 392 public int compareTo(AnalyzedInstruction analyzedInstruction) { 393 if (instructionIndex < analyzedInstruction.instructionIndex) { 394 return -1; 395 } else if (instructionIndex == analyzedInstruction.instructionIndex) { 396 return 0; 397 } else { 398 return 1; 399 } 400 } 401 402 private static class PredecessorOverrideKey { 403 public final AnalyzedInstruction analyzedInstruction; 404 public final int registerNumber; 405 406 public PredecessorOverrideKey(AnalyzedInstruction analyzedInstruction, int registerNumber) { 407 this.analyzedInstruction = analyzedInstruction; 408 this.registerNumber = registerNumber; 409 } 410 411 @Override public boolean equals(Object o) { 412 if (this == o) return true; 413 if (o == null || getClass() != o.getClass()) return false; 414 PredecessorOverrideKey that = (PredecessorOverrideKey)o; 415 return com.google.common.base.Objects.equal(registerNumber, that.registerNumber) && 416 Objects.equal(analyzedInstruction, that.analyzedInstruction); 417 } 418 419 @Override public int hashCode() { 420 return Objects.hashCode(analyzedInstruction, registerNumber); 421 } 422 } 423 } 424 425