• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.Function;
35 import com.google.common.collect.ImmutableList;
36 import com.google.common.collect.Lists;
37 import org.jf.dexlib2.AccessFlags;
38 import org.jf.dexlib2.Opcode;
39 import org.jf.dexlib2.iface.*;
40 import org.jf.dexlib2.iface.instruction.*;
41 import org.jf.dexlib2.iface.instruction.formats.*;
42 import org.jf.dexlib2.iface.reference.FieldReference;
43 import org.jf.dexlib2.iface.reference.MethodReference;
44 import org.jf.dexlib2.iface.reference.Reference;
45 import org.jf.dexlib2.iface.reference.TypeReference;
46 import org.jf.dexlib2.immutable.instruction.*;
47 import org.jf.dexlib2.immutable.reference.ImmutableFieldReference;
48 import org.jf.dexlib2.immutable.reference.ImmutableMethodReference;
49 import org.jf.dexlib2.util.MethodUtil;
50 import org.jf.dexlib2.util.ReferenceUtil;
51 import org.jf.dexlib2.util.TypeUtils;
52 import org.jf.dexlib2.writer.util.TryListBuilder;
53 import org.jf.util.BitSetUtils;
54 import org.jf.util.ExceptionWithContext;
55 import org.jf.util.SparseArray;
56 
57 import javax.annotation.Nonnull;
58 import javax.annotation.Nullable;
59 import java.util.BitSet;
60 import java.util.List;
61 
62 /**
63  * The MethodAnalyzer performs several functions. It "analyzes" the instructions and infers the register types
64  * for each register, it can deodex odexed instructions, and it can verify the bytecode. The analysis and verification
65  * are done in two separate passes, because the analysis has to process instructions multiple times in some cases, and
66  * there's no need to perform the verification multiple times, so we wait until the method is fully analyzed and then
67  * verify it.
68  *
69  * Before calling the analyze() method, you must have initialized the ClassPath by calling
70  * ClassPath.InitializeClassPath
71  */
72 public class MethodAnalyzer {
73     @Nonnull private final Method method;
74     @Nonnull private final MethodImplementation methodImpl;
75 
76     private final boolean normalizeVirtualMethods;
77 
78     private final int paramRegisterCount;
79 
80     @Nonnull private final ClassPath classPath;
81     @Nullable private final InlineMethodResolver inlineResolver;
82 
83     // This contains all the AnalyzedInstruction instances, keyed by the code unit address of the instruction
84     @Nonnull private final SparseArray<AnalyzedInstruction> analyzedInstructions =
85             new SparseArray<AnalyzedInstruction>(0);
86 
87     // Which instructions have been analyzed, keyed by instruction index
88     @Nonnull private final BitSet analyzedState;
89 
90     @Nullable private AnalysisException analysisException = null;
91 
92     //This is a dummy instruction that occurs immediately before the first real instruction. We can initialize the
93     //register types for this instruction to the parameter types, in order to have them propagate to all of its
94     //successors, e.g. the first real instruction, the first instructions in any exception handlers covering the first
95     //instruction, etc.
96     private final AnalyzedInstruction startOfMethod;
97 
MethodAnalyzer(@onnull ClassPath classPath, @Nonnull Method method, @Nullable InlineMethodResolver inlineResolver, boolean normalizeVirtualMethods)98     public MethodAnalyzer(@Nonnull ClassPath classPath, @Nonnull Method method,
99                           @Nullable InlineMethodResolver inlineResolver, boolean normalizeVirtualMethods) {
100         this.classPath = classPath;
101         this.inlineResolver = inlineResolver;
102         this.normalizeVirtualMethods = normalizeVirtualMethods;
103 
104         this.method = method;
105 
106         MethodImplementation methodImpl = method.getImplementation();
107         if (methodImpl == null) {
108             throw new IllegalArgumentException("The method has no implementation");
109         }
110 
111         this.methodImpl = methodImpl;
112 
113         //override AnalyzedInstruction and provide custom implementations of some of the methods, so that we don't
114         //have to handle the case this special case of instruction being null, in the main class
115         startOfMethod = new AnalyzedInstruction(this, null, -1, methodImpl.getRegisterCount()) {
116             public boolean setsRegister() {
117                 return false;
118             }
119 
120             @Override
121             public boolean setsWideRegister() {
122                 return false;
123             }
124 
125             @Override
126             public boolean setsRegister(int registerNumber) {
127                 return false;
128             }
129 
130             @Override
131             public int getDestinationRegister() {
132                 assert false;
133                 return -1;
134             }
135         };
136 
137         buildInstructionList();
138 
139         analyzedState = new BitSet(analyzedInstructions.size());
140         paramRegisterCount = MethodUtil.getParameterRegisterCount(method);
141         analyze();
142     }
143 
getClassPath()144     public ClassPath getClassPath() {
145         return classPath;
146     }
147 
analyze()148     private void analyze() {
149         Method method = this.method;
150         MethodImplementation methodImpl = this.methodImpl;
151 
152         int totalRegisters = methodImpl.getRegisterCount();
153         int parameterRegisters = paramRegisterCount;
154 
155         int nonParameterRegisters = totalRegisters - parameterRegisters;
156 
157         //if this isn't a static method, determine which register is the "this" register and set the type to the
158         //current class
159         if (!MethodUtil.isStatic(method)) {
160             int thisRegister = totalRegisters - parameterRegisters;
161 
162             //if this is a constructor, then set the "this" register to an uninitialized reference of the current class
163             if (MethodUtil.isConstructor(method)) {
164                 setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
165                         RegisterType.getRegisterType(RegisterType.UNINIT_THIS,
166                                 classPath.getClass(method.getDefiningClass())));
167             } else {
168                 setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
169                         RegisterType.getRegisterType(RegisterType.REFERENCE,
170                                 classPath.getClass(method.getDefiningClass())));
171             }
172 
173             propagateParameterTypes(totalRegisters-parameterRegisters+1);
174         } else {
175             propagateParameterTypes(totalRegisters-parameterRegisters);
176         }
177 
178         RegisterType uninit = RegisterType.getRegisterType(RegisterType.UNINIT, null);
179         for (int i=0; i<nonParameterRegisters; i++) {
180             setPostRegisterTypeAndPropagateChanges(startOfMethod, i, uninit);
181         }
182 
183         BitSet instructionsToAnalyze = new BitSet(analyzedInstructions.size());
184 
185         //make sure all of the "first instructions" are marked for processing
186         for (AnalyzedInstruction successor: startOfMethod.successors) {
187             instructionsToAnalyze.set(successor.instructionIndex);
188         }
189 
190         BitSet undeodexedInstructions = new BitSet(analyzedInstructions.size());
191 
192         do {
193             boolean didSomething = false;
194 
195             while (!instructionsToAnalyze.isEmpty()) {
196                 for(int i=instructionsToAnalyze.nextSetBit(0); i>=0; i=instructionsToAnalyze.nextSetBit(i+1)) {
197                     instructionsToAnalyze.clear(i);
198                     if (analyzedState.get(i)) {
199                         continue;
200                     }
201                     AnalyzedInstruction instructionToAnalyze = analyzedInstructions.valueAt(i);
202                     try {
203                         if (instructionToAnalyze.originalInstruction.getOpcode().odexOnly()) {
204                             //if we had deodexed an odex instruction in a previous pass, we might have more specific
205                             //register information now, so let's restore the original odexed instruction and
206                             //re-deodex it
207                             instructionToAnalyze.restoreOdexedInstruction();
208                         }
209 
210                         if (!analyzeInstruction(instructionToAnalyze)) {
211                             undeodexedInstructions.set(i);
212                             continue;
213                         } else {
214                             didSomething = true;
215                             undeodexedInstructions.clear(i);
216                         }
217                     } catch (AnalysisException ex) {
218                         this.analysisException = ex;
219                         int codeAddress = getInstructionAddress(instructionToAnalyze);
220                         ex.codeAddress = codeAddress;
221                         ex.addContext(String.format("opcode: %s", instructionToAnalyze.instruction.getOpcode().name));
222                         ex.addContext(String.format("code address: %d", codeAddress));
223                         ex.addContext(String.format("method: %s", ReferenceUtil.getReferenceString(method)));
224                         break;
225                     }
226 
227                     analyzedState.set(instructionToAnalyze.getInstructionIndex());
228 
229                     for (AnalyzedInstruction successor: instructionToAnalyze.successors) {
230                         instructionsToAnalyze.set(successor.getInstructionIndex());
231                     }
232                 }
233                 if (analysisException != null) {
234                     break;
235                 }
236             }
237 
238             if (!didSomething) {
239                 break;
240             }
241 
242             if (!undeodexedInstructions.isEmpty()) {
243                 for (int i=undeodexedInstructions.nextSetBit(0); i>=0; i=undeodexedInstructions.nextSetBit(i+1)) {
244                     instructionsToAnalyze.set(i);
245                 }
246             }
247         } while (true);
248 
249         //Now, go through and fix up any unresolvable odex instructions. These are usually odex instructions
250         //that operate on a null register, and thus always throw an NPE. They can also be any sort of odex instruction
251         //that occurs after an unresolvable odex instruction. We deodex if possible, or replace with an
252         //UnresolvableOdexInstruction
253         for (int i=0; i< analyzedInstructions.size(); i++) {
254             AnalyzedInstruction analyzedInstruction = analyzedInstructions.valueAt(i);
255 
256             Instruction instruction = analyzedInstruction.getInstruction();
257 
258             if (instruction.getOpcode().odexOnly()) {
259                 int objectRegisterNumber;
260                 switch (instruction.getOpcode().format) {
261                     case Format10x:
262                         analyzeOdexReturnVoid(analyzedInstruction, false);
263                         continue;
264                     case Format21c:
265                     case Format22c:
266                         analyzePutGetVolatile(analyzedInstruction, false);
267                         continue;
268                     case Format35c:
269                         analyzeInvokeDirectEmpty(analyzedInstruction, false);
270                         continue;
271                     case Format3rc:
272                         analyzeInvokeObjectInitRange(analyzedInstruction, false);
273                         continue;
274                     case Format22cs:
275                         objectRegisterNumber = ((Instruction22cs)instruction).getRegisterB();
276                         break;
277                     case Format35mi:
278                     case Format35ms:
279                         objectRegisterNumber = ((FiveRegisterInstruction)instruction).getRegisterC();
280                         break;
281                     case Format3rmi:
282                     case Format3rms:
283                         objectRegisterNumber = ((RegisterRangeInstruction)instruction).getStartRegister();
284                         break;
285                     default:
286                         continue;
287                 }
288 
289                 analyzedInstruction.setDeodexedInstruction(
290                         new UnresolvedOdexInstruction(instruction, objectRegisterNumber));
291             }
292         }
293     }
294 
propagateParameterTypes(int parameterStartRegister)295     private void propagateParameterTypes(int parameterStartRegister) {
296         int i=0;
297         for (MethodParameter parameter: method.getParameters()) {
298             if (TypeUtils.isWideType(parameter)) {
299                 setPostRegisterTypeAndPropagateChanges(startOfMethod, parameterStartRegister + i++,
300                         RegisterType.getWideRegisterType(parameter, true));
301                 setPostRegisterTypeAndPropagateChanges(startOfMethod, parameterStartRegister + i++,
302                         RegisterType.getWideRegisterType(parameter, false));
303             } else {
304                 setPostRegisterTypeAndPropagateChanges(startOfMethod, parameterStartRegister + i++,
305                         RegisterType.getRegisterType(classPath, parameter));
306             }
307         }
308     }
309 
getAnalyzedInstructions()310     public List<AnalyzedInstruction> getAnalyzedInstructions() {
311         return analyzedInstructions.getValues();
312     }
313 
getInstructions()314     public List<Instruction> getInstructions() {
315         return Lists.transform(analyzedInstructions.getValues(), new Function<AnalyzedInstruction, Instruction>() {
316             @Nullable @Override public Instruction apply(@Nullable AnalyzedInstruction input) {
317                 if (input == null) {
318                     return null;
319                 }
320                 return input.instruction;
321             }
322         });
323     }
324 
325     @Nullable
326     public AnalysisException getAnalysisException() {
327         return analysisException;
328     }
329 
330     public int getParamRegisterCount() {
331         return paramRegisterCount;
332     }
333 
334     public int getInstructionAddress(@Nonnull AnalyzedInstruction instruction) {
335         return analyzedInstructions.keyAt(instruction.instructionIndex);
336     }
337 
338     private void setDestinationRegisterTypeAndPropagateChanges(@Nonnull AnalyzedInstruction analyzedInstruction,
339                                                                @Nonnull RegisterType registerType) {
340         setPostRegisterTypeAndPropagateChanges(analyzedInstruction, analyzedInstruction.getDestinationRegister(),
341                 registerType);
342     }
343 
344     private void propagateChanges(@Nonnull BitSet changedInstructions, int registerNumber, boolean override) {
345         //Using a for loop inside the while loop optimizes for the common case of the successors of an instruction
346         //occurring after the instruction. Any successors that occur prior to the instruction will be picked up on
347         //the next iteration of the while loop.
348         //This could also be done recursively, but in large methods it would likely cause very deep recursion.
349         while (!changedInstructions.isEmpty()) {
350             for (int instructionIndex=changedInstructions.nextSetBit(0);
351                  instructionIndex>=0;
352                  instructionIndex=changedInstructions.nextSetBit(instructionIndex+1)) {
353 
354                 changedInstructions.clear(instructionIndex);
355 
356                 propagateRegisterToSuccessors(analyzedInstructions.valueAt(instructionIndex), registerNumber,
357                         changedInstructions, override);
358             }
359         }
360     }
361 
362     private void overridePredecessorRegisterTypeAndPropagateChanges(
363             @Nonnull AnalyzedInstruction analyzedInstruction, @Nonnull AnalyzedInstruction predecessor,
364             int registerNumber, @Nonnull RegisterType registerType) {
365         BitSet changedInstructions = new BitSet(analyzedInstructions.size());
366 
367         if (!analyzedInstruction.overridePredecessorRegisterType(
368                 predecessor, registerNumber, registerType, analyzedState)) {
369             return;
370         }
371         changedInstructions.set(analyzedInstruction.instructionIndex);
372 
373         propagateChanges(changedInstructions, registerNumber, true);
374 
375         if (registerType.category == RegisterType.LONG_LO) {
376             checkWidePair(registerNumber, analyzedInstruction);
377             overridePredecessorRegisterTypeAndPropagateChanges(analyzedInstruction, predecessor, registerNumber + 1,
378                     RegisterType.LONG_HI_TYPE);
379         } else if (registerType.category == RegisterType.DOUBLE_LO) {
380             checkWidePair(registerNumber, analyzedInstruction);
381             overridePredecessorRegisterTypeAndPropagateChanges(analyzedInstruction, predecessor, registerNumber + 1,
382                     RegisterType.DOUBLE_HI_TYPE);
383         }
384     }
385 
386     private void setPostRegisterTypeAndPropagateChanges(@Nonnull AnalyzedInstruction analyzedInstruction,
387                                                         int registerNumber, @Nonnull RegisterType registerType) {
388 
389         BitSet changedInstructions = new BitSet(analyzedInstructions.size());
390 
391         if (!analyzedInstruction.setPostRegisterType(registerNumber, registerType)) {
392             return;
393         }
394 
395         propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions, false);
396 
397         propagateChanges(changedInstructions, registerNumber, false);
398 
399         if (registerType.category == RegisterType.LONG_LO) {
400             checkWidePair(registerNumber, analyzedInstruction);
401             setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.LONG_HI_TYPE);
402         } else if (registerType.category == RegisterType.DOUBLE_LO) {
403             checkWidePair(registerNumber, analyzedInstruction);
404             setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1, RegisterType.DOUBLE_HI_TYPE);
405         }
406     }
407 
408     private void propagateRegisterToSuccessors(@Nonnull AnalyzedInstruction instruction, int registerNumber,
409                                                @Nonnull BitSet changedInstructions, boolean override) {
410         RegisterType postRegisterType = instruction.getPostInstructionRegisterType(registerNumber);
411         for (AnalyzedInstruction successor: instruction.successors) {
412             if (successor.mergeRegister(registerNumber, postRegisterType, analyzedState, override)) {
413                 changedInstructions.set(successor.instructionIndex);
414             }
415         }
416     }
417 
418     private void buildInstructionList() {
419         int registerCount = methodImpl.getRegisterCount();
420 
421         ImmutableList<Instruction> instructions = ImmutableList.copyOf(methodImpl.getInstructions());
422 
423         analyzedInstructions.ensureCapacity(instructions.size());
424 
425         //first, create all the instructions and populate the instructionAddresses array
426         int currentCodeAddress = 0;
427         for (int i=0; i<instructions.size(); i++) {
428             Instruction instruction = instructions.get(i);
429             analyzedInstructions.append(currentCodeAddress,
430                     new AnalyzedInstruction(this, instruction, i, registerCount));
431             assert analyzedInstructions.indexOfKey(currentCodeAddress) == i;
432             currentCodeAddress += instruction.getCodeUnits();
433         }
434 
435         //next, populate the exceptionHandlers array. The array item for each instruction that can throw an exception
436         //and is covered by a try block should be set to a list of the first instructions of each exception handler
437         //for the try block covering the instruction
438         List<? extends TryBlock<? extends ExceptionHandler>> tries = methodImpl.getTryBlocks();
439         tries = TryListBuilder.massageTryBlocks(tries);
440         int triesIndex = 0;
441         TryBlock currentTry = null;
442         AnalyzedInstruction[] currentExceptionHandlers = null;
443         AnalyzedInstruction[][] exceptionHandlers = new AnalyzedInstruction[instructions.size()][];
444 
445         if (tries != null) {
446             for (int i=0; i< analyzedInstructions.size(); i++) {
447                 AnalyzedInstruction instruction = analyzedInstructions.valueAt(i);
448                 Opcode instructionOpcode = instruction.instruction.getOpcode();
449                 currentCodeAddress = getInstructionAddress(instruction);
450 
451                 //check if we have gone past the end of the current try
452                 if (currentTry != null) {
453                     if (currentTry.getStartCodeAddress() + currentTry.getCodeUnitCount()  <= currentCodeAddress) {
454                         currentTry = null;
455                         triesIndex++;
456                     }
457                 }
458 
459                 //check if the next try is applicable yet
460                 if (currentTry == null && triesIndex < tries.size()) {
461                     TryBlock<? extends ExceptionHandler> tryBlock = tries.get(triesIndex);
462                     if (tryBlock.getStartCodeAddress() <= currentCodeAddress) {
463                         assert(tryBlock.getStartCodeAddress() + tryBlock.getCodeUnitCount() > currentCodeAddress);
464 
465                         currentTry = tryBlock;
466 
467                         currentExceptionHandlers = buildExceptionHandlerArray(tryBlock);
468                     }
469                 }
470 
471                 //if we're inside a try block, and the instruction can throw an exception, then add the exception handlers
472                 //for the current instruction
473                 if (currentTry != null && instructionOpcode.canThrow()) {
474                     exceptionHandlers[i] = currentExceptionHandlers;
475                 }
476             }
477         }
478 
479         //finally, populate the successors and predecessors for each instruction. We start at the fake "StartOfMethod"
480         //instruction and follow the execution path. Any unreachable code won't have any predecessors or successors,
481         //and no reachable code will have an unreachable predessor or successor
482         assert analyzedInstructions.size() > 0;
483         BitSet instructionsToProcess = new BitSet(instructions.size());
484 
485         addPredecessorSuccessor(startOfMethod, analyzedInstructions.valueAt(0), exceptionHandlers, instructionsToProcess);
486         while (!instructionsToProcess.isEmpty()) {
487             int currentInstructionIndex = instructionsToProcess.nextSetBit(0);
488             instructionsToProcess.clear(currentInstructionIndex);
489 
490             AnalyzedInstruction instruction = analyzedInstructions.valueAt(currentInstructionIndex);
491             Opcode instructionOpcode = instruction.instruction.getOpcode();
492             int instructionCodeAddress = getInstructionAddress(instruction);
493 
494             if (instruction.instruction.getOpcode().canContinue()) {
495                 if (currentInstructionIndex == analyzedInstructions.size() - 1) {
496                     throw new AnalysisException("Execution can continue past the last instruction");
497                 }
498 
499                 AnalyzedInstruction nextInstruction = analyzedInstructions.valueAt(currentInstructionIndex+1);
500                 addPredecessorSuccessor(instruction, nextInstruction, exceptionHandlers, instructionsToProcess);
501             }
502 
503             if (instruction.instruction instanceof OffsetInstruction) {
504                 OffsetInstruction offsetInstruction = (OffsetInstruction)instruction.instruction;
505 
506                 if (instructionOpcode == Opcode.PACKED_SWITCH || instructionOpcode == Opcode.SPARSE_SWITCH) {
507                     AnalyzedInstruction analyzedSwitchPayload = analyzedInstructions.get(
508                             instructionCodeAddress + offsetInstruction.getCodeOffset());
509                     if (analyzedSwitchPayload == null) {
510                         throw new AnalysisException("Invalid switch payload offset");
511                     }
512                     SwitchPayload switchPayload = (SwitchPayload)analyzedSwitchPayload.instruction;
513 
514                     for (SwitchElement switchElement: switchPayload.getSwitchElements()) {
515                         AnalyzedInstruction targetInstruction = analyzedInstructions.get(instructionCodeAddress +
516                                 switchElement.getOffset());
517                         if (targetInstruction == null) {
518                             throw new AnalysisException("Invalid switch target offset");
519                         }
520 
521                         addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers,
522                                 instructionsToProcess);
523                     }
524                 } else if (instructionOpcode != Opcode.FILL_ARRAY_DATA) {
525                     int targetAddressOffset = offsetInstruction.getCodeOffset();
526                     AnalyzedInstruction targetInstruction = analyzedInstructions.get(instructionCodeAddress +
527                             targetAddressOffset);
528                     addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers, instructionsToProcess);
529                 }
530             }
531         }
532     }
533 
534     private void addPredecessorSuccessor(@Nonnull AnalyzedInstruction predecessor,
535                                          @Nonnull AnalyzedInstruction successor,
536                                          @Nonnull AnalyzedInstruction[][] exceptionHandlers,
537                                          @Nonnull BitSet instructionsToProcess) {
538         addPredecessorSuccessor(predecessor, successor, exceptionHandlers, instructionsToProcess, false);
539     }
540 
541     private void addPredecessorSuccessor(@Nonnull AnalyzedInstruction predecessor,
542                                          @Nonnull AnalyzedInstruction successor,
543                                          @Nonnull AnalyzedInstruction[][] exceptionHandlers,
544                                          @Nonnull BitSet instructionsToProcess, boolean allowMoveException) {
545 
546         if (!allowMoveException && successor.instruction.getOpcode() == Opcode.MOVE_EXCEPTION) {
547             throw new AnalysisException("Execution can pass from the " + predecessor.instruction.getOpcode().name +
548                     " instruction at code address 0x" + Integer.toHexString(getInstructionAddress(predecessor)) +
549                     " to the move-exception instruction at address 0x" +
550                     Integer.toHexString(getInstructionAddress(successor)));
551         }
552 
553         if (!successor.addPredecessor(predecessor)) {
554             return;
555         }
556 
557         predecessor.addSuccessor(successor);
558         instructionsToProcess.set(successor.getInstructionIndex());
559 
560 
561         //if the successor can throw an instruction, then we need to add the exception handlers as additional
562         //successors to the predecessor (and then apply this same logic recursively if needed)
563         //Technically, we should handle the monitor-exit instruction as a special case. The exception is actually
564         //thrown *after* the instruction executes, instead of "before" the instruction executes, lke for any other
565         //instruction. But since it doesn't modify any registers, we can treat it like any other instruction.
566         AnalyzedInstruction[] exceptionHandlersForSuccessor = exceptionHandlers[successor.instructionIndex];
567         if (exceptionHandlersForSuccessor != null) {
568             //the item for this instruction in exceptionHandlersForSuccessor should only be set if this instruction
569             //can throw an exception
570             assert successor.instruction.getOpcode().canThrow();
571 
572             for (AnalyzedInstruction exceptionHandler: exceptionHandlersForSuccessor) {
573                 addPredecessorSuccessor(predecessor, exceptionHandler, exceptionHandlers, instructionsToProcess, true);
574             }
575         }
576     }
577 
578     @Nonnull
579     private AnalyzedInstruction[] buildExceptionHandlerArray(@Nonnull TryBlock<? extends ExceptionHandler> tryBlock) {
580         List<? extends ExceptionHandler> exceptionHandlers = tryBlock.getExceptionHandlers();
581 
582         AnalyzedInstruction[] handlerInstructions = new AnalyzedInstruction[exceptionHandlers.size()];
583         for (int i=0; i<exceptionHandlers.size(); i++) {
584             handlerInstructions[i] = analyzedInstructions.get(exceptionHandlers.get(i).getHandlerCodeAddress());
585         }
586 
587         return handlerInstructions;
588     }
589 
590     /**
591      * @return false if analyzedInstruction is an odex instruction that couldn't be deodexed, due to its
592      * object register being null
593      */
594     private boolean analyzeInstruction(@Nonnull AnalyzedInstruction analyzedInstruction) {
595         Instruction instruction = analyzedInstruction.instruction;
596 
597         switch (instruction.getOpcode()) {
598             case NOP:
599                 return true;
600             case MOVE:
601             case MOVE_FROM16:
602             case MOVE_16:
603             case MOVE_WIDE:
604             case MOVE_WIDE_FROM16:
605             case MOVE_WIDE_16:
606             case MOVE_OBJECT:
607             case MOVE_OBJECT_FROM16:
608             case MOVE_OBJECT_16:
609                 analyzeMove(analyzedInstruction);
610                 return true;
611             case MOVE_RESULT:
612             case MOVE_RESULT_WIDE:
613             case MOVE_RESULT_OBJECT:
614                 analyzeMoveResult(analyzedInstruction);
615                 return true;
616             case MOVE_EXCEPTION:
617                 analyzeMoveException(analyzedInstruction);
618                 return true;
619             case RETURN_VOID:
620             case RETURN:
621             case RETURN_WIDE:
622             case RETURN_OBJECT:
623                 return true;
624             case RETURN_VOID_BARRIER:
625             case RETURN_VOID_NO_BARRIER:
626                 analyzeOdexReturnVoid(analyzedInstruction);
627                 return true;
628             case CONST_4:
629             case CONST_16:
630             case CONST:
631             case CONST_HIGH16:
632                 analyzeConst(analyzedInstruction);
633                 return true;
634             case CONST_WIDE_16:
635             case CONST_WIDE_32:
636             case CONST_WIDE:
637             case CONST_WIDE_HIGH16:
638                 analyzeWideConst(analyzedInstruction);
639                 return true;
640             case CONST_STRING:
641             case CONST_STRING_JUMBO:
642                 analyzeConstString(analyzedInstruction);
643                 return true;
644             case CONST_CLASS:
645                 analyzeConstClass(analyzedInstruction);
646                 return true;
647             case MONITOR_ENTER:
648             case MONITOR_EXIT:
649                 return true;
650             case CHECK_CAST:
651                 analyzeCheckCast(analyzedInstruction);
652                 return true;
653             case INSTANCE_OF:
654                 analyzeInstanceOf(analyzedInstruction);
655                 return true;
656             case ARRAY_LENGTH:
657                 analyzeArrayLength(analyzedInstruction);
658                 return true;
659             case NEW_INSTANCE:
660                 analyzeNewInstance(analyzedInstruction);
661                 return true;
662             case NEW_ARRAY:
663                 analyzeNewArray(analyzedInstruction);
664                 return true;
665             case FILLED_NEW_ARRAY:
666             case FILLED_NEW_ARRAY_RANGE:
667                 return true;
668             case FILL_ARRAY_DATA:
669                 return true;
670             case THROW:
671             case GOTO:
672             case GOTO_16:
673             case GOTO_32:
674                 return true;
675             case PACKED_SWITCH:
676             case SPARSE_SWITCH:
677                 return true;
678             case CMPL_FLOAT:
679             case CMPG_FLOAT:
680             case CMPL_DOUBLE:
681             case CMPG_DOUBLE:
682             case CMP_LONG:
683                 analyzeFloatWideCmp(analyzedInstruction);
684                 return true;
685             case IF_EQ:
686             case IF_NE:
687             case IF_LT:
688             case IF_GE:
689             case IF_GT:
690             case IF_LE:
691             case IF_LTZ:
692             case IF_GEZ:
693             case IF_GTZ:
694             case IF_LEZ:
695                 return true;
696             case IF_EQZ:
697             case IF_NEZ:
698                 analyzeIfEqzNez(analyzedInstruction);
699                 return true;
700             case AGET:
701                 analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.INTEGER_TYPE);
702                 return true;
703             case AGET_BOOLEAN:
704                 analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.BOOLEAN_TYPE);
705                 return true;
706             case AGET_BYTE:
707                 analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.BYTE_TYPE);
708                 return true;
709             case AGET_CHAR:
710                 analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.CHAR_TYPE);
711                 return true;
712             case AGET_SHORT:
713                 analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.SHORT_TYPE);
714                 return true;
715             case AGET_WIDE:
716                 analyzeAgetWide(analyzedInstruction);
717                 return true;
718             case AGET_OBJECT:
719                 analyzeAgetObject(analyzedInstruction);
720                 return true;
721             case APUT:
722             case APUT_BOOLEAN:
723             case APUT_BYTE:
724             case APUT_CHAR:
725             case APUT_SHORT:
726             case APUT_WIDE:
727             case APUT_OBJECT:
728                 return true;
729             case IGET:
730                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.INTEGER_TYPE);
731                 return true;
732             case IGET_BOOLEAN:
733                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BOOLEAN_TYPE);
734                 return true;
735             case IGET_BYTE:
736                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BYTE_TYPE);
737                 return true;
738             case IGET_CHAR:
739                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.CHAR_TYPE);
740                 return true;
741             case IGET_SHORT:
742                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.SHORT_TYPE);
743                 return true;
744             case IGET_WIDE:
745             case IGET_OBJECT:
746                 analyzeIgetSgetWideObject(analyzedInstruction);
747                 return true;
748             case IPUT:
749             case IPUT_BOOLEAN:
750             case IPUT_BYTE:
751             case IPUT_CHAR:
752             case IPUT_SHORT:
753             case IPUT_WIDE:
754             case IPUT_OBJECT:
755                 return true;
756             case SGET:
757                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.INTEGER_TYPE);
758                 return true;
759             case SGET_BOOLEAN:
760                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BOOLEAN_TYPE);
761                 return true;
762             case SGET_BYTE:
763                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.BYTE_TYPE);
764                 return true;
765             case SGET_CHAR:
766                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.CHAR_TYPE);
767                 return true;
768             case SGET_SHORT:
769                 analyze32BitPrimitiveIgetSget(analyzedInstruction, RegisterType.SHORT_TYPE);
770                 return true;
771             case SGET_WIDE:
772             case SGET_OBJECT:
773                 analyzeIgetSgetWideObject(analyzedInstruction);
774                 return true;
775             case SPUT:
776             case SPUT_BOOLEAN:
777             case SPUT_BYTE:
778             case SPUT_CHAR:
779             case SPUT_SHORT:
780             case SPUT_WIDE:
781             case SPUT_OBJECT:
782                 return true;
783             case INVOKE_VIRTUAL:
784                 analyzeInvokeVirtual(analyzedInstruction, false);
785                 return true;
786             case INVOKE_SUPER:
787                 analyzeInvokeVirtual(analyzedInstruction, false);
788                 return true;
789             case INVOKE_DIRECT:
790                 analyzeInvokeDirect(analyzedInstruction);
791                 return true;
792             case INVOKE_STATIC:
793                 return true;
794             case INVOKE_INTERFACE:
795                 // TODO: normalize interfaces
796                 return true;
797             case INVOKE_VIRTUAL_RANGE:
798                 analyzeInvokeVirtual(analyzedInstruction, true);
799                 return true;
800             case INVOKE_SUPER_RANGE:
801                 analyzeInvokeVirtual(analyzedInstruction, true);
802                 return true;
803             case INVOKE_DIRECT_RANGE:
804                 analyzeInvokeDirectRange(analyzedInstruction);
805                 return true;
806             case INVOKE_STATIC_RANGE:
807                 return true;
808             case INVOKE_INTERFACE_RANGE:
809                 // TODO: normalize interfaces
810                 return true;
811             case NEG_INT:
812             case NOT_INT:
813                 analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE);
814                 return true;
815             case NEG_LONG:
816             case NOT_LONG:
817                 analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE);
818                 return true;
819             case NEG_FLOAT:
820                 analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE);
821                 return true;
822             case NEG_DOUBLE:
823                 analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE);
824                 return true;
825             case INT_TO_LONG:
826                 analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE);
827                 return true;
828             case INT_TO_FLOAT:
829                 analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE);
830                 return true;
831             case INT_TO_DOUBLE:
832                 analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE);
833                 return true;
834             case LONG_TO_INT:
835             case DOUBLE_TO_INT:
836                 analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE);
837                 return true;
838             case LONG_TO_FLOAT:
839             case DOUBLE_TO_FLOAT:
840                 analyzeUnaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE);
841                 return true;
842             case LONG_TO_DOUBLE:
843                 analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE);
844                 return true;
845             case FLOAT_TO_INT:
846                 analyzeUnaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE);
847                 return true;
848             case FLOAT_TO_LONG:
849                 analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE);
850                 return true;
851             case FLOAT_TO_DOUBLE:
852                 analyzeUnaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE);
853                 return true;
854             case DOUBLE_TO_LONG:
855                 analyzeUnaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE);
856                 return true;
857             case INT_TO_BYTE:
858                 analyzeUnaryOp(analyzedInstruction, RegisterType.BYTE_TYPE);
859                 return true;
860             case INT_TO_CHAR:
861                 analyzeUnaryOp(analyzedInstruction, RegisterType.CHAR_TYPE);
862                 return true;
863             case INT_TO_SHORT:
864                 analyzeUnaryOp(analyzedInstruction, RegisterType.SHORT_TYPE);
865                 return true;
866             case ADD_INT:
867             case SUB_INT:
868             case MUL_INT:
869             case DIV_INT:
870             case REM_INT:
871             case SHL_INT:
872             case SHR_INT:
873             case USHR_INT:
874                 analyzeBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false);
875                 return true;
876             case AND_INT:
877             case OR_INT:
878             case XOR_INT:
879                 analyzeBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true);
880                 return true;
881             case ADD_LONG:
882             case SUB_LONG:
883             case MUL_LONG:
884             case DIV_LONG:
885             case REM_LONG:
886             case AND_LONG:
887             case OR_LONG:
888             case XOR_LONG:
889             case SHL_LONG:
890             case SHR_LONG:
891             case USHR_LONG:
892                 analyzeBinaryOp(analyzedInstruction, RegisterType.LONG_LO_TYPE, false);
893                 return true;
894             case ADD_FLOAT:
895             case SUB_FLOAT:
896             case MUL_FLOAT:
897             case DIV_FLOAT:
898             case REM_FLOAT:
899                 analyzeBinaryOp(analyzedInstruction, RegisterType.FLOAT_TYPE, false);
900                 return true;
901             case ADD_DOUBLE:
902             case SUB_DOUBLE:
903             case MUL_DOUBLE:
904             case DIV_DOUBLE:
905             case REM_DOUBLE:
906                 analyzeBinaryOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE, false);
907                 return true;
908             case ADD_INT_2ADDR:
909             case SUB_INT_2ADDR:
910             case MUL_INT_2ADDR:
911             case DIV_INT_2ADDR:
912             case REM_INT_2ADDR:
913             case SHL_INT_2ADDR:
914             case SHR_INT_2ADDR:
915             case USHR_INT_2ADDR:
916                 analyzeBinary2AddrOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false);
917                 return true;
918             case AND_INT_2ADDR:
919             case OR_INT_2ADDR:
920             case XOR_INT_2ADDR:
921                 analyzeBinary2AddrOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true);
922                 return true;
923             case ADD_LONG_2ADDR:
924             case SUB_LONG_2ADDR:
925             case MUL_LONG_2ADDR:
926             case DIV_LONG_2ADDR:
927             case REM_LONG_2ADDR:
928             case AND_LONG_2ADDR:
929             case OR_LONG_2ADDR:
930             case XOR_LONG_2ADDR:
931             case SHL_LONG_2ADDR:
932             case SHR_LONG_2ADDR:
933             case USHR_LONG_2ADDR:
934                 analyzeBinary2AddrOp(analyzedInstruction, RegisterType.LONG_LO_TYPE, false);
935                 return true;
936             case ADD_FLOAT_2ADDR:
937             case SUB_FLOAT_2ADDR:
938             case MUL_FLOAT_2ADDR:
939             case DIV_FLOAT_2ADDR:
940             case REM_FLOAT_2ADDR:
941                 analyzeBinary2AddrOp(analyzedInstruction, RegisterType.FLOAT_TYPE, false);
942                 return true;
943             case ADD_DOUBLE_2ADDR:
944             case SUB_DOUBLE_2ADDR:
945             case MUL_DOUBLE_2ADDR:
946             case DIV_DOUBLE_2ADDR:
947             case REM_DOUBLE_2ADDR:
948                 analyzeBinary2AddrOp(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE, false);
949                 return true;
950             case ADD_INT_LIT16:
951             case RSUB_INT:
952             case MUL_INT_LIT16:
953             case DIV_INT_LIT16:
954             case REM_INT_LIT16:
955                 analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false);
956                 return true;
957             case AND_INT_LIT16:
958             case OR_INT_LIT16:
959             case XOR_INT_LIT16:
960                 analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true);
961                 return true;
962             case ADD_INT_LIT8:
963             case RSUB_INT_LIT8:
964             case MUL_INT_LIT8:
965             case DIV_INT_LIT8:
966             case REM_INT_LIT8:
967             case SHL_INT_LIT8:
968                 analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, false);
969                 return true;
970             case AND_INT_LIT8:
971             case OR_INT_LIT8:
972             case XOR_INT_LIT8:
973                 analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.INTEGER_TYPE, true);
974                 return true;
975             case SHR_INT_LIT8:
976                 analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, true),
977                         false);
978                 return true;
979             case USHR_INT_LIT8:
980                 analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, false),
981                         false);
982                 return true;
983 
984             /*odexed instructions*/
985             case IGET_VOLATILE:
986             case IPUT_VOLATILE:
987             case SGET_VOLATILE:
988             case SPUT_VOLATILE:
989             case IGET_OBJECT_VOLATILE:
990             case IGET_WIDE_VOLATILE:
991             case IPUT_WIDE_VOLATILE:
992             case SGET_WIDE_VOLATILE:
993             case SPUT_WIDE_VOLATILE:
994                 analyzePutGetVolatile(analyzedInstruction);
995                 return true;
996             case THROW_VERIFICATION_ERROR:
997                 return true;
998             case EXECUTE_INLINE:
999                 analyzeExecuteInline(analyzedInstruction);
1000                 return true;
1001             case EXECUTE_INLINE_RANGE:
1002                 analyzeExecuteInlineRange(analyzedInstruction);
1003                 return true;
1004             case INVOKE_DIRECT_EMPTY:
1005                 analyzeInvokeDirectEmpty(analyzedInstruction);
1006                 return true;
1007             case INVOKE_OBJECT_INIT_RANGE:
1008                 analyzeInvokeObjectInitRange(analyzedInstruction);
1009                 return true;
1010             case IGET_QUICK:
1011             case IGET_WIDE_QUICK:
1012             case IGET_OBJECT_QUICK:
1013             case IPUT_QUICK:
1014             case IPUT_WIDE_QUICK:
1015             case IPUT_OBJECT_QUICK:
1016             case IPUT_BOOLEAN_QUICK:
1017             case IPUT_BYTE_QUICK:
1018             case IPUT_CHAR_QUICK:
1019             case IPUT_SHORT_QUICK:
1020             case IGET_BOOLEAN_QUICK:
1021             case IGET_BYTE_QUICK:
1022             case IGET_CHAR_QUICK:
1023             case IGET_SHORT_QUICK:
1024                 return analyzeIputIgetQuick(analyzedInstruction);
1025             case INVOKE_VIRTUAL_QUICK:
1026                 return analyzeInvokeVirtualQuick(analyzedInstruction, false, false);
1027             case INVOKE_SUPER_QUICK:
1028                 return analyzeInvokeVirtualQuick(analyzedInstruction, true, false);
1029             case INVOKE_VIRTUAL_QUICK_RANGE:
1030                 return analyzeInvokeVirtualQuick(analyzedInstruction, false, true);
1031             case INVOKE_SUPER_QUICK_RANGE:
1032                 return analyzeInvokeVirtualQuick(analyzedInstruction, true, true);
1033             case IPUT_OBJECT_VOLATILE:
1034             case SGET_OBJECT_VOLATILE:
1035             case SPUT_OBJECT_VOLATILE:
1036                 analyzePutGetVolatile(analyzedInstruction);
1037                 return true;
1038             default:
1039                 assert false;
1040                 return true;
1041         }
1042     }
1043 
1044     private static final BitSet Primitive32BitCategories = BitSetUtils.bitSetOfIndexes(
1045             RegisterType.NULL,
1046             RegisterType.ONE,
1047             RegisterType.BOOLEAN,
1048             RegisterType.BYTE,
1049             RegisterType.POS_BYTE,
1050             RegisterType.SHORT,
1051             RegisterType.POS_SHORT,
1052             RegisterType.CHAR,
1053             RegisterType.INTEGER,
1054             RegisterType.FLOAT);
1055 
1056     private static final BitSet WideLowCategories = BitSetUtils.bitSetOfIndexes(
1057             RegisterType.LONG_LO,
1058             RegisterType.DOUBLE_LO);
1059 
1060     private static final BitSet WideHighCategories = BitSetUtils.bitSetOfIndexes(
1061             RegisterType.LONG_HI,
1062             RegisterType.DOUBLE_HI);
1063 
1064     private static final BitSet ReferenceOrUninitCategories = BitSetUtils.bitSetOfIndexes(
1065             RegisterType.NULL,
1066             RegisterType.UNINIT_REF,
1067             RegisterType.UNINIT_THIS,
1068             RegisterType.REFERENCE);
1069 
1070     private static final BitSet BooleanCategories = BitSetUtils.bitSetOfIndexes(
1071             RegisterType.NULL,
1072             RegisterType.ONE,
1073             RegisterType.BOOLEAN);
1074 
1075     private void analyzeMove(@Nonnull AnalyzedInstruction analyzedInstruction) {
1076         TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1077 
1078         RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1079         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
1080     }
1081 
1082     private void analyzeMoveResult(@Nonnull AnalyzedInstruction analyzedInstruction) {
1083         AnalyzedInstruction previousInstruction = null;
1084         if (analyzedInstruction.instructionIndex > 0) {
1085             previousInstruction = analyzedInstructions.valueAt(analyzedInstruction.instructionIndex-1);
1086         }
1087         if (previousInstruction == null || !previousInstruction.instruction.getOpcode().setsResult()) {
1088             throw new AnalysisException(analyzedInstruction.instruction.getOpcode().name + " must occur after an " +
1089                     "invoke-*/fill-new-array instruction");
1090         }
1091 
1092         RegisterType resultRegisterType;
1093         ReferenceInstruction invokeInstruction = (ReferenceInstruction)previousInstruction.instruction;
1094         Reference reference = invokeInstruction.getReference();
1095 
1096         if (reference instanceof MethodReference) {
1097             resultRegisterType = RegisterType.getRegisterType(classPath, ((MethodReference)reference).getReturnType());
1098         } else {
1099             resultRegisterType = RegisterType.getRegisterType(classPath, (TypeReference)reference);
1100         }
1101 
1102         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, resultRegisterType);
1103     }
1104 
1105     private void analyzeMoveException(@Nonnull AnalyzedInstruction analyzedInstruction) {
1106         int instructionAddress = getInstructionAddress(analyzedInstruction);
1107 
1108         RegisterType exceptionType = RegisterType.UNKNOWN_TYPE;
1109 
1110         for (TryBlock<? extends ExceptionHandler> tryBlock: methodImpl.getTryBlocks()) {
1111             for (ExceptionHandler handler: tryBlock.getExceptionHandlers()) {
1112 
1113                 if (handler.getHandlerCodeAddress() == instructionAddress) {
1114                     String type = handler.getExceptionType();
1115                     if (type == null) {
1116                         exceptionType = RegisterType.getRegisterType(RegisterType.REFERENCE,
1117                                 classPath.getClass("Ljava/lang/Throwable;"));
1118                     } else {
1119                         exceptionType = RegisterType.getRegisterType(RegisterType.REFERENCE, classPath.getClass(type))
1120                                 .merge(exceptionType);
1121                     }
1122                 }
1123             }
1124         }
1125 
1126         if (exceptionType.category == RegisterType.UNKNOWN) {
1127             throw new AnalysisException("move-exception must be the first instruction in an exception handler block");
1128         }
1129 
1130         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
1131     }
1132 
1133     private void analyzeOdexReturnVoid(AnalyzedInstruction analyzedInstruction) {
1134         analyzeOdexReturnVoid(analyzedInstruction, true);
1135     }
1136 
1137     private void analyzeOdexReturnVoid(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) {
1138         Instruction10x deodexedInstruction = new ImmutableInstruction10x(Opcode.RETURN_VOID);
1139 
1140         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1141 
1142         if (analyzeResult) {
1143             analyzeInstruction(analyzedInstruction);
1144         }
1145     }
1146 
1147     private void analyzeConst(@Nonnull AnalyzedInstruction analyzedInstruction) {
1148         NarrowLiteralInstruction instruction = (NarrowLiteralInstruction)analyzedInstruction.instruction;
1149 
1150         //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1151         //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1152         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1153                 RegisterType.getRegisterTypeForLiteral(instruction.getNarrowLiteral()));
1154     }
1155 
1156     private void analyzeWideConst(@Nonnull AnalyzedInstruction analyzedInstruction) {
1157         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE);
1158     }
1159 
1160     private void analyzeConstString(@Nonnull AnalyzedInstruction analyzedInstruction) {
1161         TypeProto stringClass = classPath.getClass("Ljava/lang/String;");
1162         RegisterType stringType = RegisterType.getRegisterType(RegisterType.REFERENCE, stringClass);
1163         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
1164     }
1165 
1166     private void analyzeConstClass(@Nonnull AnalyzedInstruction analyzedInstruction) {
1167         TypeProto classClass = classPath.getClass("Ljava/lang/Class;");
1168         RegisterType classType = RegisterType.getRegisterType(RegisterType.REFERENCE, classClass);
1169         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, classType);
1170     }
1171 
1172     private void analyzeCheckCast(@Nonnull AnalyzedInstruction analyzedInstruction) {
1173         ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction;
1174         TypeReference reference = (TypeReference)instruction.getReference();
1175         RegisterType castRegisterType = RegisterType.getRegisterType(classPath, reference);
1176         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, castRegisterType);
1177     }
1178 
1179     static boolean canNarrowAfterInstanceOf(AnalyzedInstruction analyzedInstanceOfInstruction,
1180                                             AnalyzedInstruction analyzedIfInstruction, ClassPath classPath) {
1181         Instruction ifInstruction = analyzedIfInstruction.instruction;
1182         assert analyzedIfInstruction.instruction != null;
1183         if (((Instruction21t)ifInstruction).getRegisterA() == analyzedInstanceOfInstruction.getDestinationRegister()) {
1184             Reference reference = ((Instruction22c)analyzedInstanceOfInstruction.getInstruction()).getReference();
1185             RegisterType registerType = RegisterType.getRegisterType(classPath, (TypeReference)reference);
1186 
1187             if (registerType.type != null && !registerType.type.isInterface()) {
1188                 int objectRegister = ((TwoRegisterInstruction)analyzedInstanceOfInstruction.getInstruction())
1189                         .getRegisterB();
1190 
1191                 RegisterType originalType = analyzedIfInstruction.getPreInstructionRegisterType(objectRegister);
1192 
1193                 if (originalType.type != null) {
1194                     // Only override if we're going from an interface to a class, or are going to a narrower class
1195                     if (originalType.type.isInterface()) {
1196                         return true;
1197                     } else {
1198                         TypeProto commonSuperclass = registerType.type.getCommonSuperclass(originalType.type);
1199                         // only if it's a narrowing conversion
1200                         if (commonSuperclass.getType().equals(originalType.type.getType())) {
1201                             return true;
1202                         }
1203                     }
1204                 }
1205             }
1206         }
1207         return false;
1208     }
1209 
1210     /**
1211      * Art uses a peephole optimization for an if-eqz or if-nez that occur immediately after an instance-of. It will
1212      * narrow the type if possible, and then NOP out any corresponding check-cast instruction later on
1213      *
1214      * TODO: Is this still safe to do even for dalvik odexes? I think it should be..
1215      */
1216     private void analyzeIfEqzNez(@Nonnull AnalyzedInstruction analyzedInstruction) {
1217         int instructionIndex = analyzedInstruction.getInstructionIndex();
1218         if (instructionIndex > 0) {
1219             AnalyzedInstruction prevAnalyzedInstruction = analyzedInstructions.valueAt(instructionIndex - 1);
1220             if (prevAnalyzedInstruction.instruction != null &&
1221                     prevAnalyzedInstruction.instruction.getOpcode() == Opcode.INSTANCE_OF) {
1222                 if (canNarrowAfterInstanceOf(prevAnalyzedInstruction, analyzedInstruction, classPath)) {
1223                     // Propagate the original type to the failing branch, and the new type to the successful branch
1224                     int narrowingRegister = ((Instruction22c)prevAnalyzedInstruction.instruction).getRegisterB();
1225                     RegisterType originalType = analyzedInstruction.getPreInstructionRegisterType(narrowingRegister);
1226                     RegisterType newType = RegisterType.getRegisterType(classPath,
1227                             (TypeReference)((Instruction22c)prevAnalyzedInstruction.instruction).getReference());
1228 
1229                     AnalyzedInstruction fallthroughInstruction = analyzedInstructions.valueAt(
1230                             analyzedInstruction.getInstructionIndex() + 1);
1231 
1232                     int nextAddress = getInstructionAddress(analyzedInstruction) +
1233                             ((Instruction21t)analyzedInstruction.instruction).getCodeOffset();
1234                     AnalyzedInstruction branchInstruction = analyzedInstructions.get(nextAddress);
1235 
1236                     if (analyzedInstruction.instruction.getOpcode() == Opcode.IF_EQZ) {
1237                         overridePredecessorRegisterTypeAndPropagateChanges(fallthroughInstruction, analyzedInstruction,
1238                                 narrowingRegister, newType);
1239                         overridePredecessorRegisterTypeAndPropagateChanges(branchInstruction, analyzedInstruction,
1240                                 narrowingRegister, originalType);
1241                     } else {
1242                         overridePredecessorRegisterTypeAndPropagateChanges(fallthroughInstruction, analyzedInstruction,
1243                                 narrowingRegister, originalType);
1244                         overridePredecessorRegisterTypeAndPropagateChanges(branchInstruction, analyzedInstruction,
1245                                 narrowingRegister, newType);
1246                     }
1247                 }
1248             }
1249         }
1250     }
1251 
1252     private void analyzeInstanceOf(@Nonnull AnalyzedInstruction analyzedInstruction) {
1253         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.BOOLEAN_TYPE);
1254     }
1255 
1256     private void analyzeArrayLength(@Nonnull AnalyzedInstruction analyzedInstruction) {
1257         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.INTEGER_TYPE);
1258     }
1259 
1260     private void analyzeNewInstance(@Nonnull AnalyzedInstruction analyzedInstruction) {
1261         ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction;
1262 
1263         int register = ((OneRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1264         RegisterType destRegisterType = analyzedInstruction.getPostInstructionRegisterType(register);
1265         if (destRegisterType.category != RegisterType.UNKNOWN) {
1266             //the post-instruction destination register will only be set if we have already analyzed this instruction
1267             //at least once. If this is the case, then the uninit reference has already been propagated to all
1268             //successors and nothing else needs to be done.
1269             assert destRegisterType.category == RegisterType.UNINIT_REF;
1270             return;
1271         }
1272 
1273         TypeReference typeReference = (TypeReference)instruction.getReference();
1274 
1275         RegisterType classType = RegisterType.getRegisterType(classPath, typeReference);
1276 
1277         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1278                 RegisterType.getRegisterType(RegisterType.UNINIT_REF, classType.type));
1279     }
1280 
1281     private void analyzeNewArray(@Nonnull AnalyzedInstruction analyzedInstruction) {
1282         ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction;
1283 
1284         TypeReference type = (TypeReference)instruction.getReference();
1285         if (type.getType().charAt(0) != '[') {
1286             throw new AnalysisException("new-array used with non-array type");
1287         }
1288 
1289         RegisterType arrayType = RegisterType.getRegisterType(classPath, type);
1290 
1291         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1292     }
1293 
1294     private void analyzeFloatWideCmp(@Nonnull AnalyzedInstruction analyzedInstruction) {
1295         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.BYTE_TYPE);
1296     }
1297 
1298     private void analyze32BitPrimitiveAget(@Nonnull AnalyzedInstruction analyzedInstruction,
1299                                            @Nonnull RegisterType registerType) {
1300         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, registerType);
1301     }
1302 
1303     private void analyzeAgetWide(@Nonnull AnalyzedInstruction analyzedInstruction) {
1304         ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1305 
1306         RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1307         if (arrayRegisterType.category != RegisterType.NULL) {
1308             if (arrayRegisterType.category != RegisterType.REFERENCE ||
1309                     !(arrayRegisterType.type instanceof ArrayProto)) {
1310                 throw new AnalysisException("aget-wide used with non-array register: %s", arrayRegisterType.toString());
1311             }
1312             ArrayProto arrayProto = (ArrayProto)arrayRegisterType.type;
1313 
1314             if (arrayProto.dimensions != 1) {
1315                 throw new AnalysisException("aget-wide used with multi-dimensional array: %s",
1316                         arrayRegisterType.toString());
1317             }
1318 
1319             char arrayBaseType = arrayProto.getElementType().charAt(0);
1320             if (arrayBaseType == 'J') {
1321                 setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE);
1322             } else if (arrayBaseType == 'D') {
1323                 setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.DOUBLE_LO_TYPE);
1324             } else {
1325                 throw new AnalysisException("aget-wide used with narrow array: %s", arrayRegisterType);
1326             }
1327         } else {
1328             // If the array register is null, we can assume that the destination register was meant to be a wide type.
1329             // This is the same behavior as dalvik's verifier
1330             setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.LONG_LO_TYPE);
1331         }
1332     }
1333 
1334     private void analyzeAgetObject(@Nonnull AnalyzedInstruction analyzedInstruction) {
1335         ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1336 
1337         RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1338         if (arrayRegisterType.category != RegisterType.NULL) {
1339             if (arrayRegisterType.category != RegisterType.REFERENCE ||
1340                     !(arrayRegisterType.type instanceof ArrayProto)) {
1341                 throw new AnalysisException("aget-object used with non-array register: %s",
1342                         arrayRegisterType.toString());
1343             }
1344 
1345             ArrayProto arrayProto = (ArrayProto)arrayRegisterType.type;
1346 
1347             String elementType = arrayProto.getImmediateElementType();
1348 
1349             setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1350                     RegisterType.getRegisterType(RegisterType.REFERENCE, classPath.getClass(elementType)));
1351         } else {
1352             // If the array register is null, we can assume that the destination register was meant to be a reference
1353             // type, so we set the destination to NULL. This is the same behavior as dalvik's verifier
1354             setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, RegisterType.NULL_TYPE);
1355         }
1356     }
1357 
1358     private void analyze32BitPrimitiveIgetSget(@Nonnull AnalyzedInstruction analyzedInstruction,
1359                                                @Nonnull RegisterType registerType) {
1360         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, registerType);
1361     }
1362 
1363     private void analyzeIgetSgetWideObject(@Nonnull AnalyzedInstruction analyzedInstruction) {
1364         ReferenceInstruction referenceInstruction = (ReferenceInstruction)analyzedInstruction.instruction;
1365 
1366         FieldReference fieldReference = (FieldReference)referenceInstruction.getReference();
1367 
1368         RegisterType fieldType = RegisterType.getRegisterType(classPath, fieldReference.getType());
1369         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
1370     }
1371 
1372     private void analyzeInvokeDirect(@Nonnull AnalyzedInstruction analyzedInstruction) {
1373         FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
1374         analyzeInvokeDirectCommon(analyzedInstruction, instruction.getRegisterC());
1375     }
1376 
1377     private void analyzeInvokeDirectRange(@Nonnull AnalyzedInstruction analyzedInstruction) {
1378         RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
1379         analyzeInvokeDirectCommon(analyzedInstruction, instruction.getStartRegister());
1380     }
1381 
1382     private void analyzeInvokeDirectCommon(@Nonnull AnalyzedInstruction analyzedInstruction, int objectRegister) {
1383         //the only time that an invoke instruction changes a register type is when using invoke-direct on a
1384         //constructor (<init>) method, which changes the uninitialized reference (and any register that the same
1385         //uninit reference has been copied to) to an initialized reference
1386 
1387         ReferenceInstruction instruction = (ReferenceInstruction)analyzedInstruction.instruction;
1388 
1389         MethodReference methodReference = (MethodReference)instruction.getReference();
1390 
1391         if (!methodReference.getName().equals("<init>")) {
1392             return;
1393         }
1394 
1395         RegisterType objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister);
1396 
1397         if (objectRegisterType.category != RegisterType.UNINIT_REF &&
1398                 objectRegisterType.category != RegisterType.UNINIT_THIS) {
1399             return;
1400         }
1401 
1402         setPostRegisterTypeAndPropagateChanges(analyzedInstruction, objectRegister,
1403                 RegisterType.getRegisterType(RegisterType.REFERENCE, objectRegisterType.type));
1404 
1405         for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
1406             RegisterType postInstructionRegisterType = analyzedInstruction.postRegisterMap[i];
1407             if (postInstructionRegisterType.category == RegisterType.UNKNOWN) {
1408                 RegisterType preInstructionRegisterType =
1409                         analyzedInstruction.getPreInstructionRegisterType(i);
1410 
1411                 if (preInstructionRegisterType.category == RegisterType.UNINIT_REF ||
1412                         preInstructionRegisterType.category == RegisterType.UNINIT_THIS) {
1413                     RegisterType registerType;
1414                     if (preInstructionRegisterType.equals(objectRegisterType)) {
1415                         registerType = analyzedInstruction.postRegisterMap[objectRegister];
1416                     } else {
1417                         registerType = preInstructionRegisterType;
1418                     }
1419 
1420                     setPostRegisterTypeAndPropagateChanges(analyzedInstruction, i, registerType);
1421                 }
1422             }
1423         }
1424     }
1425 
1426     private void analyzeUnaryOp(@Nonnull AnalyzedInstruction analyzedInstruction,
1427                                 @Nonnull RegisterType destRegisterType) {
1428         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType);
1429     }
1430 
1431     private void analyzeBinaryOp(@Nonnull AnalyzedInstruction analyzedInstruction,
1432                                  @Nonnull RegisterType destRegisterType, boolean checkForBoolean) {
1433         if (checkForBoolean) {
1434             ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1435 
1436             RegisterType source1RegisterType =
1437                     analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1438             RegisterType source2RegisterType =
1439                     analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
1440 
1441             if (BooleanCategories.get(source1RegisterType.category) &&
1442                     BooleanCategories.get(source2RegisterType.category)) {
1443                 destRegisterType = RegisterType.BOOLEAN_TYPE;
1444             }
1445         }
1446 
1447         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType);
1448     }
1449 
1450     private void analyzeBinary2AddrOp(@Nonnull AnalyzedInstruction analyzedInstruction,
1451                                       @Nonnull RegisterType destRegisterType, boolean checkForBoolean) {
1452         if (checkForBoolean) {
1453             TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1454 
1455             RegisterType source1RegisterType =
1456                     analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1457             RegisterType source2RegisterType =
1458                     analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1459 
1460             if (BooleanCategories.get(source1RegisterType.category) &&
1461                     BooleanCategories.get(source2RegisterType.category)) {
1462                 destRegisterType = RegisterType.BOOLEAN_TYPE;
1463             }
1464         }
1465 
1466         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType);
1467     }
1468 
1469     private void analyzeLiteralBinaryOp(@Nonnull AnalyzedInstruction analyzedInstruction,
1470                                         @Nonnull RegisterType destRegisterType, boolean checkForBoolean) {
1471         if (checkForBoolean) {
1472             TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1473 
1474             RegisterType sourceRegisterType =
1475                     analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1476 
1477             if (BooleanCategories.get(sourceRegisterType.category)) {
1478                 int literal = ((NarrowLiteralInstruction)analyzedInstruction.instruction).getNarrowLiteral();
1479                 if (literal == 0 || literal == 1) {
1480                     destRegisterType = RegisterType.BOOLEAN_TYPE;
1481                 }
1482             }
1483         }
1484 
1485         setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, destRegisterType);
1486     }
1487 
1488     private RegisterType getDestTypeForLiteralShiftRight(@Nonnull AnalyzedInstruction analyzedInstruction, boolean signedShift) {
1489         TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1490 
1491         RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1492                 Primitive32BitCategories);
1493         long literalShift = ((NarrowLiteralInstruction)analyzedInstruction.instruction).getNarrowLiteral();
1494 
1495         if (literalShift == 0) {
1496             return sourceRegisterType;
1497         }
1498 
1499         RegisterType destRegisterType;
1500         if (!signedShift) {
1501             destRegisterType = RegisterType.INTEGER_TYPE;
1502         } else {
1503             destRegisterType = sourceRegisterType;
1504         }
1505 
1506         literalShift = literalShift & 0x1f;
1507 
1508         switch (sourceRegisterType.category) {
1509             case RegisterType.INTEGER:
1510             case RegisterType.FLOAT:
1511                 if (!signedShift) {
1512                     if (literalShift > 24) {
1513                         return RegisterType.POS_BYTE_TYPE;
1514                     }
1515                     if (literalShift >= 16) {
1516                         return RegisterType.CHAR_TYPE;
1517                     }
1518                 } else {
1519                     if (literalShift >= 24) {
1520                         return RegisterType.BYTE_TYPE;
1521                     }
1522                     if (literalShift >= 16) {
1523                         return RegisterType.SHORT_TYPE;
1524                     }
1525                 }
1526                 break;
1527             case RegisterType.SHORT:
1528                 if (signedShift && literalShift >= 8) {
1529                     return RegisterType.BYTE_TYPE;
1530                 }
1531                 break;
1532             case RegisterType.POS_SHORT:
1533                 if (literalShift >= 8) {
1534                     return RegisterType.POS_BYTE_TYPE;
1535                 }
1536                 break;
1537             case RegisterType.CHAR:
1538                 if (literalShift > 8) {
1539                     return RegisterType.POS_BYTE_TYPE;
1540                 }
1541                 break;
1542             case RegisterType.BYTE:
1543                 break;
1544             case RegisterType.POS_BYTE:
1545                 return RegisterType.POS_BYTE_TYPE;
1546             case RegisterType.NULL:
1547             case RegisterType.ONE:
1548             case RegisterType.BOOLEAN:
1549                 return RegisterType.NULL_TYPE;
1550             default:
1551                 assert false;
1552         }
1553 
1554         return destRegisterType;
1555     }
1556 
1557 
1558     private void analyzeExecuteInline(@Nonnull AnalyzedInstruction analyzedInstruction) {
1559         if (inlineResolver == null) {
1560             throw new AnalysisException("Cannot analyze an odexed instruction unless we are deodexing");
1561         }
1562 
1563         Instruction35mi instruction = (Instruction35mi)analyzedInstruction.instruction;
1564         Method resolvedMethod = inlineResolver.resolveExecuteInline(analyzedInstruction);
1565 
1566         Opcode deodexedOpcode;
1567         int acccessFlags = resolvedMethod.getAccessFlags();
1568         if (AccessFlags.STATIC.isSet(acccessFlags)) {
1569             deodexedOpcode = Opcode.INVOKE_STATIC;
1570         } else if (AccessFlags.PRIVATE.isSet(acccessFlags)) {
1571             deodexedOpcode = Opcode.INVOKE_DIRECT;
1572         } else {
1573             deodexedOpcode = Opcode.INVOKE_VIRTUAL;
1574         }
1575 
1576         Instruction35c deodexedInstruction = new ImmutableInstruction35c(deodexedOpcode, instruction.getRegisterCount(),
1577                 instruction.getRegisterC(), instruction.getRegisterD(), instruction.getRegisterE(),
1578                 instruction.getRegisterF(), instruction.getRegisterG(), resolvedMethod);
1579 
1580         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1581         analyzeInstruction(analyzedInstruction);
1582     }
1583 
1584     private void analyzeExecuteInlineRange(@Nonnull AnalyzedInstruction analyzedInstruction) {
1585         if (inlineResolver == null) {
1586             throw new AnalysisException("Cannot analyze an odexed instruction unless we are deodexing");
1587         }
1588 
1589         Instruction3rmi instruction = (Instruction3rmi)analyzedInstruction.instruction;
1590         Method resolvedMethod = inlineResolver.resolveExecuteInline(analyzedInstruction);
1591 
1592         Opcode deodexedOpcode;
1593         int acccessFlags = resolvedMethod.getAccessFlags();
1594         if (AccessFlags.STATIC.isSet(acccessFlags)) {
1595             deodexedOpcode = Opcode.INVOKE_STATIC_RANGE;
1596         } else if (AccessFlags.PRIVATE.isSet(acccessFlags)) {
1597             deodexedOpcode = Opcode.INVOKE_DIRECT_RANGE;
1598         } else {
1599             deodexedOpcode = Opcode.INVOKE_VIRTUAL_RANGE;
1600         }
1601 
1602         Instruction3rc deodexedInstruction = new ImmutableInstruction3rc(deodexedOpcode, instruction.getStartRegister(),
1603                 instruction.getRegisterCount(), resolvedMethod);
1604 
1605         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1606         analyzeInstruction(analyzedInstruction);
1607     }
1608 
1609     private void analyzeInvokeDirectEmpty(@Nonnull AnalyzedInstruction analyzedInstruction) {
1610         analyzeInvokeDirectEmpty(analyzedInstruction, true);
1611     }
1612 
1613     private void analyzeInvokeDirectEmpty(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) {
1614         Instruction35c instruction = (Instruction35c)analyzedInstruction.instruction;
1615 
1616         Instruction35c deodexedInstruction = new ImmutableInstruction35c(Opcode.INVOKE_DIRECT,
1617                 instruction.getRegisterCount(), instruction.getRegisterC(), instruction.getRegisterD(),
1618                 instruction.getRegisterE(), instruction.getRegisterF(), instruction.getRegisterG(),
1619                 instruction.getReference());
1620 
1621         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1622 
1623         if (analyzeResult) {
1624             analyzeInstruction(analyzedInstruction);
1625         }
1626     }
1627 
1628     private void analyzeInvokeObjectInitRange(@Nonnull AnalyzedInstruction analyzedInstruction) {
1629         analyzeInvokeObjectInitRange(analyzedInstruction, true);
1630     }
1631 
1632     private void analyzeInvokeObjectInitRange(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) {
1633         Instruction3rc instruction = (Instruction3rc)analyzedInstruction.instruction;
1634 
1635         Instruction deodexedInstruction;
1636 
1637         int startRegister = instruction.getStartRegister();
1638         // hack: we should be using instruction.getRegisterCount, but some tweaked versions of dalvik appear
1639         // to generate invoke-object-init/range instructions with an invalid register count. We know it should
1640         // always be 1, so just use that.
1641         int registerCount = 1;
1642         if (startRegister < 16) {
1643             deodexedInstruction = new ImmutableInstruction35c(Opcode.INVOKE_DIRECT,
1644                     registerCount, startRegister, 0, 0, 0, 0, instruction.getReference());
1645         } else {
1646             deodexedInstruction = new ImmutableInstruction3rc(Opcode.INVOKE_DIRECT_RANGE,
1647                     startRegister, registerCount, instruction.getReference());
1648         }
1649 
1650         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1651 
1652         if (analyzeResult) {
1653             analyzeInstruction(analyzedInstruction);
1654         }
1655     }
1656 
1657     private boolean analyzeIputIgetQuick(@Nonnull AnalyzedInstruction analyzedInstruction) {
1658         Instruction22cs instruction = (Instruction22cs)analyzedInstruction.instruction;
1659 
1660         int fieldOffset = instruction.getFieldOffset();
1661         RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1662                 ReferenceOrUninitCategories);
1663 
1664         if (objectRegisterType.category == RegisterType.NULL) {
1665             return false;
1666         }
1667 
1668         TypeProto objectRegisterTypeProto = objectRegisterType.type;
1669         assert objectRegisterTypeProto != null;
1670 
1671         TypeProto classTypeProto = classPath.getClass(objectRegisterTypeProto.getType());
1672         FieldReference resolvedField = classTypeProto.getFieldByOffset(fieldOffset);
1673 
1674         if (resolvedField == null) {
1675             throw new AnalysisException("Could not resolve the field in class %s at offset %d",
1676                     objectRegisterType.type.getType(), fieldOffset);
1677         }
1678 
1679         ClassDef thisClass = classPath.getClassDef(method.getDefiningClass());
1680 
1681         if (!TypeUtils.canAccessClass(thisClass.getType(), classPath.getClassDef(resolvedField.getDefiningClass()))) {
1682 
1683             // the class is not accessible. So we start looking at objectRegisterTypeProto (which may be different
1684             // than resolvedField.getDefiningClass()), and walk up the class hierarchy.
1685             ClassDef fieldClass = classPath.getClassDef(objectRegisterTypeProto.getType());
1686             while (!TypeUtils.canAccessClass(thisClass.getType(), fieldClass)) {
1687                 String superclass = fieldClass.getSuperclass();
1688                 if (superclass == null) {
1689                     throw new ExceptionWithContext("Couldn't find accessible class while resolving field %s",
1690                             ReferenceUtil.getShortFieldDescriptor(resolvedField));
1691                 }
1692 
1693                 fieldClass = classPath.getClassDef(superclass);
1694             }
1695 
1696             // fieldClass is now the first accessible class found. Now. we need to make sure that the field is
1697             // actually valid for this class
1698             resolvedField = classPath.getClass(fieldClass.getType()).getFieldByOffset(fieldOffset);
1699             if (resolvedField == null) {
1700                 throw new ExceptionWithContext("Couldn't find accessible class while resolving field %s",
1701                         ReferenceUtil.getShortFieldDescriptor(resolvedField));
1702             }
1703             resolvedField = new ImmutableFieldReference(fieldClass.getType(), resolvedField.getName(),
1704                     resolvedField.getType());
1705         }
1706 
1707         String fieldType = resolvedField.getType();
1708 
1709         Opcode opcode = classPath.getFieldInstructionMapper().getAndCheckDeodexedOpcode(
1710                 fieldType, instruction.getOpcode());
1711 
1712         Instruction22c deodexedInstruction = new ImmutableInstruction22c(opcode, (byte)instruction.getRegisterA(),
1713                 (byte)instruction.getRegisterB(), resolvedField);
1714         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1715 
1716         analyzeInstruction(analyzedInstruction);
1717 
1718         return true;
1719     }
1720 
1721     private boolean analyzeInvokeVirtual(@Nonnull AnalyzedInstruction analyzedInstruction, boolean isRange) {
1722         MethodReference targetMethod;
1723 
1724         if (!normalizeVirtualMethods) {
1725             return true;
1726         }
1727 
1728         if (isRange) {
1729             Instruction3rc instruction = (Instruction3rc)analyzedInstruction.instruction;
1730             targetMethod = (MethodReference)instruction.getReference();
1731         } else {
1732             Instruction35c instruction = (Instruction35c)analyzedInstruction.instruction;
1733             targetMethod = (MethodReference)instruction.getReference();
1734         }
1735 
1736         TypeProto typeProto = classPath.getClass(targetMethod.getDefiningClass());
1737         int methodIndex;
1738         try {
1739             methodIndex = typeProto.findMethodIndexInVtable(targetMethod);
1740         } catch (UnresolvedClassException ex) {
1741             return true;
1742         }
1743 
1744         if (methodIndex < 0) {
1745             return true;
1746         }
1747 
1748         Method replacementMethod = typeProto.getMethodByVtableIndex(methodIndex);
1749         assert replacementMethod != null;
1750         while (true) {
1751             String superType = typeProto.getSuperclass();
1752             if (superType == null) {
1753                 break;
1754             }
1755             typeProto = classPath.getClass(superType);
1756             Method resolvedMethod = typeProto.getMethodByVtableIndex(methodIndex);
1757             if (resolvedMethod == null) {
1758                 break;
1759             }
1760 
1761             if (!resolvedMethod.equals(replacementMethod)) {
1762                 if (!AnalyzedMethodUtil.canAccess(typeProto, replacementMethod, true, true, true)) {
1763                     continue;
1764                 }
1765 
1766                 replacementMethod = resolvedMethod;
1767             }
1768         }
1769 
1770         if (replacementMethod.equals(method)) {
1771             return true;
1772         }
1773 
1774         Instruction deodexedInstruction;
1775         if (isRange) {
1776             Instruction3rc instruction = (Instruction3rc)analyzedInstruction.instruction;
1777             deodexedInstruction = new ImmutableInstruction3rc(instruction.getOpcode(), instruction.getStartRegister(),
1778                     instruction.getRegisterCount(), replacementMethod);
1779         } else {
1780             Instruction35c instruction = (Instruction35c)analyzedInstruction.instruction;
1781             deodexedInstruction = new ImmutableInstruction35c(instruction.getOpcode(), instruction.getRegisterCount(),
1782                     instruction.getRegisterC(), instruction.getRegisterD(), instruction.getRegisterE(),
1783                     instruction.getRegisterF(), instruction.getRegisterG(), replacementMethod);
1784         }
1785 
1786         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1787         return true;
1788     }
1789 
1790     private boolean analyzeInvokeVirtualQuick(@Nonnull AnalyzedInstruction analyzedInstruction, boolean isSuper,
1791                                               boolean isRange) {
1792         int methodIndex;
1793         int objectRegister;
1794 
1795         if (isRange) {
1796             Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
1797             methodIndex = instruction.getVtableIndex();
1798             objectRegister = instruction.getStartRegister();
1799         } else {
1800             Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
1801             methodIndex = instruction.getVtableIndex();
1802             objectRegister = instruction.getRegisterC();
1803         }
1804 
1805         RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, objectRegister,
1806                 ReferenceOrUninitCategories);
1807         TypeProto objectRegisterTypeProto = objectRegisterType.type;
1808 
1809         if (objectRegisterType.category == RegisterType.NULL) {
1810             return false;
1811         }
1812 
1813         assert objectRegisterTypeProto != null;
1814 
1815         MethodReference resolvedMethod;
1816         if (isSuper) {
1817             // invoke-super is only used for the same class that we're currently in
1818             TypeProto typeProto = classPath.getClass(method.getDefiningClass());
1819             TypeProto superType;
1820 
1821             String superclassType = typeProto.getSuperclass();
1822             if (superclassType != null) {
1823                 superType = classPath.getClass(superclassType);
1824             } else {
1825                 // This is either java.lang.Object, or an UnknownClassProto
1826                 superType = typeProto;
1827             }
1828 
1829             resolvedMethod = superType.getMethodByVtableIndex(methodIndex);
1830         } else {
1831             resolvedMethod = objectRegisterTypeProto.getMethodByVtableIndex(methodIndex);
1832         }
1833 
1834         if (resolvedMethod == null) {
1835             throw new AnalysisException("Could not resolve the method in class %s at index %d",
1836                     objectRegisterType.type.getType(), methodIndex);
1837         }
1838 
1839         // no need to check class access for invoke-super. A class can obviously access its superclass.
1840         ClassDef thisClass = classPath.getClassDef(method.getDefiningClass());
1841 
1842         if (!isSuper && !TypeUtils.canAccessClass(
1843                 thisClass.getType(), classPath.getClassDef(resolvedMethod.getDefiningClass()))) {
1844 
1845             // the class is not accessible. So we start looking at objectRegisterTypeProto (which may be different
1846             // than resolvedMethod.getDefiningClass()), and walk up the class hierarchy.
1847             ClassDef methodClass = classPath.getClassDef(objectRegisterTypeProto.getType());
1848             while (!TypeUtils.canAccessClass(thisClass.getType(), methodClass)) {
1849                 String superclass = methodClass.getSuperclass();
1850                 if (superclass == null) {
1851                     throw new ExceptionWithContext("Couldn't find accessible class while resolving method %s",
1852                             ReferenceUtil.getMethodDescriptor(resolvedMethod, true));
1853                 }
1854 
1855                 methodClass = classPath.getClassDef(superclass);
1856             }
1857 
1858             // methodClass is now the first accessible class found. Now. we need to make sure that the method is
1859             // actually valid for this class
1860             MethodReference newResolvedMethod =
1861                     classPath.getClass(methodClass.getType()).getMethodByVtableIndex(methodIndex);
1862             if (newResolvedMethod == null) {
1863                 // TODO: fix NPE here
1864                 throw new ExceptionWithContext("Couldn't find accessible class while resolving method %s",
1865                         ReferenceUtil.getMethodDescriptor(resolvedMethod, true));
1866             }
1867             resolvedMethod = newResolvedMethod;
1868             resolvedMethod = new ImmutableMethodReference(methodClass.getType(), resolvedMethod.getName(),
1869                     resolvedMethod.getParameterTypes(), resolvedMethod.getReturnType());
1870         }
1871 
1872         Instruction deodexedInstruction;
1873         if (isRange) {
1874             Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
1875             Opcode opcode;
1876             if (isSuper) {
1877                 opcode = Opcode.INVOKE_SUPER_RANGE;
1878             } else {
1879                 opcode = Opcode.INVOKE_VIRTUAL_RANGE;
1880             }
1881 
1882             deodexedInstruction = new ImmutableInstruction3rc(opcode, instruction.getStartRegister(),
1883                     instruction.getRegisterCount(), resolvedMethod);
1884         } else {
1885             Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
1886             Opcode opcode;
1887             if (isSuper) {
1888                 opcode = Opcode.INVOKE_SUPER;
1889             } else {
1890                 opcode = Opcode.INVOKE_VIRTUAL;
1891             }
1892 
1893             deodexedInstruction = new ImmutableInstruction35c(opcode, instruction.getRegisterCount(),
1894                     instruction.getRegisterC(), instruction.getRegisterD(), instruction.getRegisterE(),
1895                     instruction.getRegisterF(), instruction.getRegisterG(), resolvedMethod);
1896         }
1897 
1898         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1899         analyzeInstruction(analyzedInstruction);
1900 
1901         return true;
1902     }
1903 
1904     private boolean analyzePutGetVolatile(@Nonnull AnalyzedInstruction analyzedInstruction) {
1905         return analyzePutGetVolatile(analyzedInstruction, true);
1906     }
1907 
1908     private boolean analyzePutGetVolatile(@Nonnull AnalyzedInstruction analyzedInstruction, boolean analyzeResult) {
1909         FieldReference field = (FieldReference)((ReferenceInstruction)analyzedInstruction.instruction).getReference();
1910         String fieldType = field.getType();
1911 
1912         Opcode originalOpcode = analyzedInstruction.instruction.getOpcode();
1913 
1914         Opcode opcode = classPath.getFieldInstructionMapper().getAndCheckDeodexedOpcode(
1915                 fieldType, originalOpcode);
1916 
1917         Instruction deodexedInstruction;
1918 
1919         if (originalOpcode.isStaticFieldAccessor()) {
1920             OneRegisterInstruction instruction = (OneRegisterInstruction)analyzedInstruction.instruction;
1921             deodexedInstruction = new ImmutableInstruction21c(opcode, instruction.getRegisterA(), field);
1922         } else {
1923             TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1924 
1925             deodexedInstruction = new ImmutableInstruction22c(opcode, instruction.getRegisterA(),
1926                     instruction.getRegisterB(), field);
1927         }
1928 
1929         analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
1930 
1931         if (analyzeResult) {
1932             analyzeInstruction(analyzedInstruction);
1933         }
1934         return true;
1935     }
1936 
1937     @Nonnull
1938     private static RegisterType getAndCheckSourceRegister(@Nonnull AnalyzedInstruction analyzedInstruction,
1939                                                           int registerNumber, BitSet validCategories) {
1940         assert registerNumber >= 0 && registerNumber < analyzedInstruction.postRegisterMap.length;
1941 
1942         RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(registerNumber);
1943 
1944         checkRegister(registerType, registerNumber, validCategories);
1945 
1946         if (validCategories == WideLowCategories) {
1947             checkRegister(registerType, registerNumber, WideLowCategories);
1948             checkWidePair(registerNumber, analyzedInstruction);
1949 
1950             RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(registerNumber + 1);
1951             checkRegister(secondRegisterType, registerNumber+1, WideHighCategories);
1952         }
1953 
1954         return registerType;
1955     }
1956 
1957     private static void checkRegister(RegisterType registerType, int registerNumber, BitSet validCategories) {
1958         if (!validCategories.get(registerType.category)) {
1959             throw new AnalysisException(String.format("Invalid register type %s for register v%d.",
1960                     registerType.toString(), registerNumber));
1961         }
1962     }
1963 
1964     private static void checkWidePair(int registerNumber, AnalyzedInstruction analyzedInstruction) {
1965         if (registerNumber + 1 >= analyzedInstruction.postRegisterMap.length) {
1966             throw new AnalysisException(String.format("v%d cannot be used as the first register in a wide register" +
1967                     "pair because it is the last register.", registerNumber));
1968         }
1969     }
1970 }