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