Home | History | Annotate | Download | only in Analysis 
      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