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