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