MethodAnalyzer.java revision b0c62b9781751e4d04d2ddb4458940d545cc8bb2 
1/*
2 * [The "BSD licence"]
3 * Copyright (c) 2010 Ben Gruver (JesusFreke)
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in the
13 *    documentation and/or other materials provided with the distribution.
14 * 3. The name of the author may not be used to endorse or promote products
15 *    derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29package org.jf.dexlib.Code.Analysis;
30
31import org.jf.dexlib.*;
32import org.jf.dexlib.Code.*;
33import org.jf.dexlib.Code.Format.*;
34import org.jf.dexlib.Util.AccessFlags;
35import org.jf.dexlib.Util.ExceptionWithContext;
36import org.jf.dexlib.Util.SparseArray;
37
38import java.util.BitSet;
39import java.util.EnumSet;
40import java.util.List;
41
42/**
43 * The MethodAnalyzer performs several functions. It "analyzes" the instructions and infers the register types
44 * for each register, it can deodex odexed instructions, and it can verify the bytecode. The analysis and verification
45 * are done in two separate passes, because the analysis has to process instructions multiple times in some cases, and
46 * there's no need to perform the verification multiple times, so we wait until the method is fully analyzed and then
47 * verify it.
48 *
49 * Before calling the analyze() method, you must have initialized the ClassPath by calling
50 * ClassPath.InitializeClassPath
51 */
52public class MethodAnalyzer {
53    private final ClassDataItem.EncodedMethod encodedMethod;
54
55    private final DeodexUtil deodexUtil;
56
57    private SparseArray<AnalyzedInstruction> instructions;
58
59    private static final int NOT_ANALYZED = 0;
60    private static final int ANALYZED = 1;
61    private static final int VERIFIED = 2;
62    private int analyzerState = NOT_ANALYZED;
63
64    private BitSet analyzedInstructions;
65
66    private ValidationException validationException = null;
67
68    //This is a dummy instruction that occurs immediately before the first real instruction. We can initialize the
69    //register types for this instruction to the parameter types, in order to have them propagate to all of its
70    //successors, e.g. the first real instruction, the first instructions in any exception handlers covering the first
71    //instruction, etc.
72    private AnalyzedInstruction startOfMethod;
73
74    public MethodAnalyzer(ClassDataItem.EncodedMethod encodedMethod, boolean deodex) {
75        if (encodedMethod == null) {
76            throw new IllegalArgumentException("encodedMethod cannot be null");
77        }
78        if (encodedMethod.codeItem == null || encodedMethod.codeItem.getInstructions().length == 0) {
79            throw new IllegalArgumentException("The method has no code");
80        }
81        this.encodedMethod = encodedMethod;
82
83        if (deodex) {
84            this.deodexUtil = new DeodexUtil(encodedMethod.method.getDexFile());
85        } else {
86            this.deodexUtil = null;
87        }
88
89        //override AnalyzedInstruction and provide custom implementations of some of the methods, so that we don't
90        //have to handle the case this special case of instruction being null, in the main class
91        startOfMethod = new AnalyzedInstruction(null, -1, encodedMethod.codeItem.getRegisterCount()) {
92            public boolean setsRegister() {
93                return false;
94            }
95
96            @Override
97            public boolean setsWideRegister() {
98                return false;
99            }
100
101            @Override
102            public boolean setsRegister(int registerNumber) {
103                return false;
104            }
105
106            @Override
107            public int getDestinationRegister() {
108                assert false;
109                return -1;
110            };
111        };
112
113        buildInstructionList();
114
115        analyzedInstructions = new BitSet(instructions.size());
116    }
117
118    public boolean isAnalyzed() {
119        return analyzerState >= ANALYZED;
120    }
121
122    public boolean isVerified() {
123        return analyzerState == VERIFIED;
124    }
125
126    public void analyze() {
127        assert encodedMethod != null;
128        assert encodedMethod.codeItem != null;
129
130        if (analyzerState >= ANALYZED) {
131            //the instructions have already been analyzed, so there is nothing to do
132            return;
133        }
134
135        CodeItem codeItem = encodedMethod.codeItem;
136        MethodIdItem methodIdItem = encodedMethod.method;
137
138        int totalRegisters = codeItem.getRegisterCount();
139        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
140
141        int nonParameterRegisters = totalRegisters - parameterRegisters;
142
143        for (AnalyzedInstruction instruction: instructions.getValues()) {
144            instruction.dead = true;
145        }
146
147        //if this isn't a static method, determine which register is the "this" register and set the type to the
148        //current class
149        if ((encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0) {
150            nonParameterRegisters--;
151            int thisRegister = totalRegisters - parameterRegisters - 1;
152
153            //if this is a constructor, then set the "this" register to an uninitialized reference of the current class
154            if ((encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0) {
155                setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
156                        RegisterType.getRegisterType(RegisterType.Category.UninitThis,
157                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
158            } else {
159                setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
160                        RegisterType.getRegisterType(RegisterType.Category.Reference,
161                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
162            }
163        }
164
165        TypeListItem parameters = methodIdItem.getPrototype().getParameters();
166        if (parameters != null) {
167            RegisterType[] parameterTypes = getParameterTypes(parameters, parameterRegisters);
168            for (int i=0; i<parameterTypes.length; i++) {
169                RegisterType registerType = parameterTypes[i];
170                int registerNum = (totalRegisters - parameterRegisters) + i;
171                setPostRegisterTypeAndPropagateChanges(startOfMethod, registerNum, registerType);
172            }
173        }
174
175        RegisterType uninit = RegisterType.getRegisterType(RegisterType.Category.Uninit, null);
176        for (int i=0; i<nonParameterRegisters; i++) {
177            setPostRegisterTypeAndPropagateChanges(startOfMethod, i, uninit);
178        }
179
180        BitSet instructionsToAnalyze = new BitSet(instructions.size());
181
182        //make sure all of the "first instructions" are marked for processing
183        for (AnalyzedInstruction successor: startOfMethod.successors) {
184            instructionsToAnalyze.set(successor.instructionIndex);
185        }
186
187        BitSet undeodexedInstructions = new BitSet(instructions.size());
188
189        do {
190            boolean didSomething = false;
191
192            while (!instructionsToAnalyze.isEmpty()) {
193                for(int i=instructionsToAnalyze.nextSetBit(0); i>=0; i=instructionsToAnalyze.nextSetBit(i+1)) {
194                    instructionsToAnalyze.clear(i);
195                    if (analyzedInstructions.get(i)) {
196                        continue;
197                    }
198                    AnalyzedInstruction instructionToAnalyze = instructions.valueAt(i);
199                    instructionToAnalyze.dead = false;
200                    try {
201                        if (instructionToAnalyze.originalInstruction.opcode.odexOnly()) {
202                            //if we had deodexed an odex instruction in a previous pass, we might have more specific
203                            //register information now, so let's restore the original odexed instruction and
204                            //re-deodex it
205                            instructionToAnalyze.restoreOdexedInstruction();
206                        }
207
208                        if (!analyzeInstruction(instructionToAnalyze)) {
209                            undeodexedInstructions.set(i);
210                            continue;
211                        } else {
212                            didSomething = true;
213                            undeodexedInstructions.clear(i);
214                        }
215                    } catch (ValidationException ex) {
216                        this.validationException = ex;
217                        int codeAddress = getInstructionAddress(instructionToAnalyze);
218                        ex.setCodeAddress(codeAddress);
219                        ex.addContext(String.format("opcode: %s", instructionToAnalyze.instruction.opcode.name));
220                        ex.addContext(String.format("CodeAddress: %d", codeAddress));
221                        ex.addContext(String.format("Method: %s", encodedMethod.method.getMethodString()));
222                        break;
223                    }
224
225                    analyzedInstructions.set(instructionToAnalyze.getInstructionIndex());
226
227                    for (AnalyzedInstruction successor: instructionToAnalyze.successors) {
228                        instructionsToAnalyze.set(successor.getInstructionIndex());
229                    }
230                }
231                if (validationException != null) {
232                    break;
233                }
234            }
235
236            if (!didSomething) {
237                break;
238            }
239
240            if (!undeodexedInstructions.isEmpty()) {
241                for (int i=undeodexedInstructions.nextSetBit(0); i>=0; i=undeodexedInstructions.nextSetBit(i+1)) {
242                    instructionsToAnalyze.set(i);
243                }
244            }
245        } while (true);
246
247        for (int i=0; i<instructions.size(); i++) {
248            AnalyzedInstruction instruction = instructions.valueAt(i);
249
250            int objectRegisterNumber;
251            switch (instruction.getInstruction().getFormat()) {
252                case Format22cs:
253                    objectRegisterNumber = ((Instruction22cs)instruction.instruction).getRegisterB();
254                    break;
255                case Format35mi:
256                case Format35ms:
257                    objectRegisterNumber = ((FiveRegisterInstruction)instruction.instruction).getRegisterD();
258                    break;
259                case Format3rmi:
260                case Format3rms:
261                    objectRegisterNumber = ((RegisterRangeInstruction)instruction.instruction).getStartRegister();
262                    break;
263                default:
264                    continue;
265            }
266
267            instruction.setDeodexedInstruction(new UnresolvedOdexInstruction(instruction.instruction,
268                    objectRegisterNumber));
269        }
270
271        analyzerState = ANALYZED;
272    }
273
274    public void verify() {
275        if (analyzerState < ANALYZED) {
276            throw new ExceptionWithContext("You must call analyze() before calling verify().");
277        }
278
279        if (analyzerState == VERIFIED) {
280            //we've already verified the bytecode. nothing to do
281            return;
282        }
283
284        BitSet instructionsToVerify = new BitSet(instructions.size());
285        BitSet verifiedInstructions = new BitSet(instructions.size());
286
287        //make sure all of the "first instructions" are marked for processing
288        for (AnalyzedInstruction successor: startOfMethod.successors) {
289            instructionsToVerify.set(successor.instructionIndex);
290        }
291
292        while (!instructionsToVerify.isEmpty()) {
293            for (int i=instructionsToVerify.nextSetBit(0); i>=0; i=instructionsToVerify.nextSetBit(i+1)) {
294                instructionsToVerify.clear(i);
295                if (verifiedInstructions.get(i)) {
296                    continue;
297                }
298                AnalyzedInstruction instructionToVerify = instructions.valueAt(i);
299                try {
300                    verifyInstruction(instructionToVerify);
301                } catch (ValidationException ex) {
302                    this.validationException = ex;
303                    int codeAddress = getInstructionAddress(instructionToVerify);
304                    ex.setCodeAddress(codeAddress);
305                    ex.addContext(String.format("opcode: %s", instructionToVerify.instruction.opcode.name));
306                    ex.addContext(String.format("CodeAddress: %d", codeAddress));
307                    ex.addContext(String.format("Method: %s", encodedMethod.method.getMethodString()));
308                    break;
309                }
310
311                verifiedInstructions.set(instructionToVerify.getInstructionIndex());
312
313                for (AnalyzedInstruction successor: instructionToVerify.successors) {
314                    instructionsToVerify.set(successor.getInstructionIndex());
315                }
316            }
317            if (validationException != null) {
318                break;
319            }
320        }
321
322        analyzerState = VERIFIED;
323    }
324
325    private int getThisRegister() {
326        assert (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0;
327
328        CodeItem codeItem = encodedMethod.codeItem;
329        assert codeItem != null;
330
331        MethodIdItem methodIdItem = encodedMethod.method;
332        assert methodIdItem != null;
333
334        int totalRegisters = codeItem.getRegisterCount();
335        if (totalRegisters == 0) {
336            throw new ValidationException("A non-static method must have at least 1 register");
337        }
338
339        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
340
341        return totalRegisters - parameterRegisters - 1;
342    }
343
344    private boolean isInstanceConstructor() {
345        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0 &&
346               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
347    }
348
349    private boolean isStaticConstructor() {
350        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) != 0 &&
351               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
352    }
353
354    public AnalyzedInstruction getStartOfMethod() {
355        return startOfMethod;
356    }
357
358    /**
359     * @return a read-only list containing the instructions for tihs method.
360     */
361    public List<AnalyzedInstruction> getInstructions() {
362        return instructions.getValues();
363    }
364
365    public ClassDataItem.EncodedMethod getMethod() {
366        return this.encodedMethod;
367    }
368
369    public ValidationException getValidationException() {
370        return validationException;
371    }
372
373    private static RegisterType[] getParameterTypes(TypeListItem typeListItem, int parameterRegisterCount) {
374        assert typeListItem != null;
375        assert parameterRegisterCount == typeListItem.getRegisterCount();
376
377        RegisterType[] registerTypes = new RegisterType[parameterRegisterCount];
378
379        int registerNum = 0;
380        for (TypeIdItem type: typeListItem.getTypes()) {
381            if (type.getRegisterCount() == 2) {
382                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, true);
383                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, false);
384            } else {
385                registerTypes[registerNum++] = RegisterType.getRegisterTypeForTypeIdItem(type);
386            }
387        }
388
389        return registerTypes;
390    }
391
392    public int getInstructionAddress(AnalyzedInstruction instruction) {
393        return instructions.keyAt(instruction.instructionIndex);
394    }
395
396    private void setDestinationRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction,
397                                                               RegisterType registerType) {
398        setPostRegisterTypeAndPropagateChanges(analyzedInstruction, analyzedInstruction.getDestinationRegister(),
399                registerType);
400    }
401
402    private void setPostRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction, int registerNumber,
403                                                RegisterType registerType) {
404
405        BitSet changedInstructions = new BitSet(instructions.size());
406
407        if (!analyzedInstruction.setPostRegisterType(registerNumber, registerType)) {
408            return;
409        }
410
411        propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions);
412
413        //Using a for loop inside the while loop optimizes for the common case of the successors of an instruction
414        //occurring after the instruction. Any successors that occur prior to the instruction will be picked up on
415        //the next iteration of the while loop.
416        //This could also be done recursively, but in large methods it would likely cause very deep recursion,
417        //which requires the user to specify a larger stack size. This isn't really a problem, but it is slightly
418        //annoying.
419        while (!changedInstructions.isEmpty()) {
420            for (int instructionIndex=changedInstructions.nextSetBit(0);
421                     instructionIndex>=0;
422                     instructionIndex=changedInstructions.nextSetBit(instructionIndex+1)) {
423
424                changedInstructions.clear(instructionIndex);
425
426                propagateRegisterToSuccessors(instructions.valueAt(instructionIndex), registerNumber,
427                        changedInstructions);
428            }
429        }
430
431        if (registerType.category == RegisterType.Category.LongLo) {
432            checkWidePair(registerNumber, analyzedInstruction);
433            setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
434                    RegisterType.getRegisterType(RegisterType.Category.LongHi, null));
435        } else if (registerType.category == RegisterType.Category.DoubleLo) {
436            checkWidePair(registerNumber, analyzedInstruction);
437            setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
438                    RegisterType.getRegisterType(RegisterType.Category.DoubleHi, null));
439        }
440    }
441
442    private void propagateRegisterToSuccessors(AnalyzedInstruction instruction, int registerNumber,
443                                               BitSet changedInstructions) {
444        RegisterType postRegisterType = instruction.getPostInstructionRegisterType(registerNumber);
445        for (AnalyzedInstruction successor: instruction.successors) {
446            if (successor.mergeRegister(registerNumber, postRegisterType, analyzedInstructions)) {
447                changedInstructions.set(successor.instructionIndex);
448            }
449        }
450    }
451
452    private void buildInstructionList() {
453        assert encodedMethod != null;
454        assert encodedMethod.codeItem != null;
455        int registerCount = encodedMethod.codeItem.getRegisterCount();
456
457        Instruction[] insns = encodedMethod.codeItem.getInstructions();
458
459        instructions = new SparseArray<AnalyzedInstruction>(insns.length);
460
461        //first, create all the instructions and populate the instructionAddresses array
462        int currentCodeAddress = 0;
463        for (int i=0; i<insns.length; i++) {
464            instructions.append(currentCodeAddress, new AnalyzedInstruction(insns[i], i, registerCount));
465            assert instructions.indexOfKey(currentCodeAddress) == i;
466            currentCodeAddress += insns[i].getSize(currentCodeAddress);
467        }
468
469        //next, populate the exceptionHandlers array. The array item for each instruction that can throw an exception
470        //and is covered by a try block should be set to a list of the first instructions of each exception handler
471        //for the try block covering the instruction
472        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
473        int triesIndex = 0;
474        CodeItem.TryItem currentTry = null;
475        AnalyzedInstruction[] currentExceptionHandlers = null;
476        AnalyzedInstruction[][] exceptionHandlers = new AnalyzedInstruction[insns.length][];
477
478        if (tries != null) {
479            for (int i=0; i<instructions.size(); i++) {
480                AnalyzedInstruction instruction = instructions.valueAt(i);
481                Opcode instructionOpcode = instruction.instruction.opcode;
482                currentCodeAddress = getInstructionAddress(instruction);
483
484                //check if we have gone past the end of the current try
485                if (currentTry != null) {
486                    if (currentTry.getStartCodeAddress() + currentTry.getTryLength() <= currentCodeAddress) {
487                        currentTry = null;
488                        triesIndex++;
489                    }
490                }
491
492                //check if the next try is applicable yet
493                if (currentTry == null && triesIndex < tries.length) {
494                    CodeItem.TryItem tryItem = tries[triesIndex];
495                    if (tryItem.getStartCodeAddress() <= currentCodeAddress) {
496                        assert(tryItem.getStartCodeAddress() + tryItem.getTryLength() > currentCodeAddress);
497
498                        currentTry = tryItem;
499
500                        currentExceptionHandlers = buildExceptionHandlerArray(tryItem);
501                    }
502                }
503
504                //if we're inside a try block, and the instruction can throw an exception, then add the exception handlers
505                //for the current instruction
506                if (currentTry != null && instructionOpcode.canThrow()) {
507                    exceptionHandlers[i] = currentExceptionHandlers;
508                }
509            }
510        }
511
512        //finally, populate the successors and predecessors for each instruction. We start at the fake "StartOfMethod"
513        //instruction and follow the execution path. Any unreachable code won't have any predecessors or successors,
514        //and no reachable code will have an unreachable predessor or successor
515        assert instructions.size() > 0;
516        BitSet instructionsToProcess = new BitSet(insns.length);
517
518        addPredecessorSuccessor(startOfMethod, instructions.valueAt(0), exceptionHandlers, instructionsToProcess);
519        while (!instructionsToProcess.isEmpty()) {
520            int currentInstructionIndex = instructionsToProcess.nextSetBit(0);
521            instructionsToProcess.clear(currentInstructionIndex);
522
523            AnalyzedInstruction instruction = instructions.valueAt(currentInstructionIndex);
524            Opcode instructionOpcode = instruction.instruction.opcode;
525            int instructionCodeAddress = getInstructionAddress(instruction);
526
527            if (instruction.instruction.opcode.canContinue()) {
528                if (instruction.instruction.opcode != Opcode.NOP ||
529                    !instruction.instruction.getFormat().variableSizeFormat) {
530
531                    if (currentInstructionIndex == instructions.size() - 1) {
532                        throw new ValidationException("Execution can continue past the last instruction");
533                    }
534
535                    AnalyzedInstruction nextInstruction = instructions.valueAt(currentInstructionIndex+1);
536                    addPredecessorSuccessor(instruction, nextInstruction, exceptionHandlers, instructionsToProcess);
537                }
538            }
539
540            if (instruction.instruction instanceof OffsetInstruction) {
541                OffsetInstruction offsetInstruction = (OffsetInstruction)instruction.instruction;
542
543                if (instructionOpcode == Opcode.PACKED_SWITCH || instructionOpcode == Opcode.SPARSE_SWITCH) {
544                    MultiOffsetInstruction switchDataInstruction =
545                            (MultiOffsetInstruction)instructions.get(instructionCodeAddress +
546                                    offsetInstruction.getTargetAddressOffset()).instruction;
547                    for (int targetAddressOffset: switchDataInstruction.getTargets()) {
548                        AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
549                                targetAddressOffset);
550
551                        addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers,
552                                instructionsToProcess);
553                    }
554                } else {
555                    int targetAddressOffset = offsetInstruction.getTargetAddressOffset();
556                    AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
557                            targetAddressOffset);
558                    addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers, instructionsToProcess);
559                }
560            }
561        }
562    }
563
564    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
565                                                AnalyzedInstruction[][] exceptionHandlers,
566                                                BitSet instructionsToProcess) {
567        addPredecessorSuccessor(predecessor, successor, exceptionHandlers, instructionsToProcess, false);
568    }
569
570    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
571                                                AnalyzedInstruction[][] exceptionHandlers,
572                                                BitSet instructionsToProcess, boolean allowMoveException) {
573
574        if (!allowMoveException && successor.instruction.opcode == Opcode.MOVE_EXCEPTION) {
575            throw new ValidationException("Execution can pass from the " + predecessor.instruction.opcode.name +
576                    " instruction at code address 0x" + Integer.toHexString(getInstructionAddress(predecessor)) +
577                    " to the move-exception instruction at address 0x" +
578                    Integer.toHexString(getInstructionAddress(successor)));
579        }
580
581        if (!successor.addPredecessor(predecessor)) {
582            return;
583        }
584
585        predecessor.addSuccessor(successor);
586        instructionsToProcess.set(successor.getInstructionIndex());
587
588
589        //if the successor can throw an instruction, then we need to add the exception handlers as additional
590        //successors to the predecessor (and then apply this same logic recursively if needed)
591        //Technically, we should handle the monitor-exit instruction as a special case. The exception is actually
592        //thrown *after* the instruction executes, instead of "before" the instruction executes, lke for any other
593        //instruction. But since it doesn't modify any registers, we can treat it like any other instruction.
594        AnalyzedInstruction[] exceptionHandlersForSuccessor = exceptionHandlers[successor.instructionIndex];
595        if (exceptionHandlersForSuccessor != null) {
596            //the item for this instruction in exceptionHandlersForSuccessor should only be set if this instruction
597            //can throw an exception
598            assert successor.instruction.opcode.canThrow();
599
600            for (AnalyzedInstruction exceptionHandler: exceptionHandlersForSuccessor) {
601                addPredecessorSuccessor(predecessor, exceptionHandler, exceptionHandlers, instructionsToProcess, true);
602            }
603        }
604    }
605
606    private AnalyzedInstruction[] buildExceptionHandlerArray(CodeItem.TryItem tryItem) {
607        int exceptionHandlerCount = tryItem.encodedCatchHandler.handlers.length;
608        int catchAllHandler = tryItem.encodedCatchHandler.getCatchAllHandlerAddress();
609        if (catchAllHandler != -1) {
610            exceptionHandlerCount++;
611        }
612
613        AnalyzedInstruction[] exceptionHandlers = new AnalyzedInstruction[exceptionHandlerCount];
614        for (int i=0; i<tryItem.encodedCatchHandler.handlers.length; i++) {
615            exceptionHandlers[i] = instructions.get(tryItem.encodedCatchHandler.handlers[i].getHandlerAddress());
616        }
617
618        if (catchAllHandler != -1) {
619            exceptionHandlers[exceptionHandlers.length - 1] = instructions.get(catchAllHandler);
620        }
621
622        return exceptionHandlers;
623    }
624
625    /**
626     * @return false if analyzedInstruction is an odex instruction that couldn't be deodexed, due to its
627     * object register being null
628     */
629    private boolean analyzeInstruction(AnalyzedInstruction analyzedInstruction) {
630        Instruction instruction = analyzedInstruction.instruction;
631
632        switch (instruction.opcode) {
633            case NOP:
634                return true;
635            case MOVE:
636            case MOVE_FROM16:
637            case MOVE_16:
638            case MOVE_WIDE:
639            case MOVE_WIDE_FROM16:
640            case MOVE_WIDE_16:
641            case MOVE_OBJECT:
642            case MOVE_OBJECT_FROM16:
643            case MOVE_OBJECT_16:
644                analyzeMove(analyzedInstruction);
645                return true;
646            case MOVE_RESULT:
647            case MOVE_RESULT_WIDE:
648            case MOVE_RESULT_OBJECT:
649                analyzeMoveResult(analyzedInstruction);
650                return true;
651            case MOVE_EXCEPTION:
652                analyzeMoveException(analyzedInstruction);
653                return true;
654            case RETURN_VOID:
655            case RETURN:
656            case RETURN_WIDE:
657            case RETURN_OBJECT:
658                return true;
659            case CONST_4:
660            case CONST_16:
661            case CONST:
662                analyzeConst(analyzedInstruction);
663                return true;
664            case CONST_HIGH16:
665                analyzeConstHigh16(analyzedInstruction);
666                return true;
667            case CONST_WIDE_16:
668            case CONST_WIDE_32:
669            case CONST_WIDE:
670            case CONST_WIDE_HIGH16:
671                analyzeWideConst(analyzedInstruction);
672                return true;
673            case CONST_STRING:
674            case CONST_STRING_JUMBO:
675                analyzeConstString(analyzedInstruction);
676                return true;
677            case CONST_CLASS:
678                analyzeConstClass(analyzedInstruction);
679                return true;
680            case MONITOR_ENTER:
681            case MONITOR_EXIT:
682                return true;
683            case CHECK_CAST:
684                analyzeCheckCast(analyzedInstruction);
685                return true;
686            case INSTANCE_OF:
687                analyzeInstanceOf(analyzedInstruction);
688                return true;
689            case ARRAY_LENGTH:
690                analyzeArrayLength(analyzedInstruction);
691                return true;
692            case NEW_INSTANCE:
693                analyzeNewInstance(analyzedInstruction);
694                return true;
695            case NEW_ARRAY:
696                analyzeNewArray(analyzedInstruction);
697                return true;
698            case FILLED_NEW_ARRAY:
699            case FILLED_NEW_ARRAY_RANGE:
700                return true;
701            case FILL_ARRAY_DATA:
702                analyzeArrayDataOrSwitch(analyzedInstruction);
703            case THROW:
704            case GOTO:
705            case GOTO_16:
706            case GOTO_32:
707                return true;
708            case PACKED_SWITCH:
709            case SPARSE_SWITCH:
710                analyzeArrayDataOrSwitch(analyzedInstruction);
711                return true;
712            case CMPL_FLOAT:
713            case CMPG_FLOAT:
714            case CMPL_DOUBLE:
715            case CMPG_DOUBLE:
716            case CMP_LONG:
717                analyzeFloatWideCmp(analyzedInstruction);
718                return true;
719            case IF_EQ:
720            case IF_NE:
721            case IF_LT:
722            case IF_GE:
723            case IF_GT:
724            case IF_LE:
725            case IF_EQZ:
726            case IF_NEZ:
727            case IF_LTZ:
728            case IF_GEZ:
729            case IF_GTZ:
730            case IF_LEZ:
731                return true;
732            case AGET:
733                analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Integer);
734                return true;
735            case AGET_BOOLEAN:
736                analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Boolean);
737                return true;
738            case AGET_BYTE:
739                analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Byte);
740                return true;
741            case AGET_CHAR:
742                analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Char);
743                return true;
744            case AGET_SHORT:
745                analyze32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Short);
746                return true;
747            case AGET_WIDE:
748                analyzeAgetWide(analyzedInstruction);
749                return true;
750            case AGET_OBJECT:
751                analyzeAgetObject(analyzedInstruction);
752                return true;
753            case APUT:
754            case APUT_BOOLEAN:
755            case APUT_BYTE:
756            case APUT_CHAR:
757            case APUT_SHORT:
758            case APUT_WIDE:
759            case APUT_OBJECT:
760                return true;
761            case IGET:
762                analyze32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Integer);
763                return true;
764            case IGET_BOOLEAN:
765                analyze32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Boolean);
766                return true;
767            case IGET_BYTE:
768                analyze32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Byte);
769                return true;
770            case IGET_CHAR:
771                analyze32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Char);
772                return true;
773            case IGET_SHORT:
774                analyze32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Short);
775                return true;
776            case IGET_WIDE:
777            case IGET_OBJECT:
778                analyzeIgetWideObject(analyzedInstruction);
779                return true;
780            case IPUT:
781            case IPUT_BOOLEAN:
782            case IPUT_BYTE:
783            case IPUT_CHAR:
784            case IPUT_SHORT:
785            case IPUT_WIDE:
786            case IPUT_OBJECT:
787                return true;
788            case SGET:
789                analyze32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Integer);
790                return true;
791            case SGET_BOOLEAN:
792                analyze32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Boolean);
793                return true;
794            case SGET_BYTE:
795                analyze32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Byte);
796                return true;
797            case SGET_CHAR:
798                analyze32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Char);
799                return true;
800            case SGET_SHORT:
801                analyze32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Short);
802                return true;
803            case SGET_WIDE:
804            case SGET_OBJECT:
805                analyzeSgetWideObject(analyzedInstruction);
806                return true;
807            case SPUT:
808            case SPUT_BOOLEAN:
809            case SPUT_BYTE:
810            case SPUT_CHAR:
811            case SPUT_SHORT:
812            case SPUT_WIDE:
813            case SPUT_OBJECT:
814                return true;
815            case INVOKE_VIRTUAL:
816            case INVOKE_SUPER:
817                return true;
818            case INVOKE_DIRECT:
819                analyzeInvokeDirect(analyzedInstruction);
820                return true;
821            case INVOKE_STATIC:
822            case INVOKE_INTERFACE:
823            case INVOKE_VIRTUAL_RANGE:
824            case INVOKE_SUPER_RANGE:
825                return true;
826            case INVOKE_DIRECT_RANGE:
827                analyzeInvokeDirectRange(analyzedInstruction);
828                return true;
829            case INVOKE_STATIC_RANGE:
830            case INVOKE_INTERFACE_RANGE:
831                return true;
832            case NEG_INT:
833            case NOT_INT:
834                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Integer);
835                return true;
836            case NEG_LONG:
837            case NOT_LONG:
838                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.LongLo);
839                return true;
840            case NEG_FLOAT:
841                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Float);
842                return true;
843            case NEG_DOUBLE:
844                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.DoubleLo);
845                return true;
846            case INT_TO_LONG:
847                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.LongLo);
848                return true;
849            case INT_TO_FLOAT:
850                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Float);
851                return true;
852            case INT_TO_DOUBLE:
853                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.DoubleLo);
854                return true;
855            case LONG_TO_INT:
856            case DOUBLE_TO_INT:
857                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Integer);
858                return true;
859            case LONG_TO_FLOAT:
860            case DOUBLE_TO_FLOAT:
861                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Float);
862                return true;
863            case LONG_TO_DOUBLE:
864                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.DoubleLo);
865                return true;
866            case FLOAT_TO_INT:
867                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Integer);
868                return true;
869            case FLOAT_TO_LONG:
870                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.LongLo);
871                return true;
872            case FLOAT_TO_DOUBLE:
873                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.DoubleLo);
874                return true;
875            case DOUBLE_TO_LONG:
876                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.LongLo);
877                return true;
878            case INT_TO_BYTE:
879                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Byte);
880                return true;
881            case INT_TO_CHAR:
882                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Char);
883                return true;
884            case INT_TO_SHORT:
885                analyzeUnaryOp(analyzedInstruction, RegisterType.Category.Short);
886                return true;
887            case ADD_INT:
888            case SUB_INT:
889            case MUL_INT:
890            case DIV_INT:
891            case REM_INT:
892            case SHL_INT:
893            case SHR_INT:
894            case USHR_INT:
895                analyzeBinaryOp(analyzedInstruction, RegisterType.Category.Integer, false);
896                return true;
897            case AND_INT:
898            case OR_INT:
899            case XOR_INT:
900                analyzeBinaryOp(analyzedInstruction, RegisterType.Category.Integer, true);
901                return true;
902            case ADD_LONG:
903            case SUB_LONG:
904            case MUL_LONG:
905            case DIV_LONG:
906            case REM_LONG:
907            case AND_LONG:
908            case OR_LONG:
909            case XOR_LONG:
910            case SHL_LONG:
911            case SHR_LONG:
912            case USHR_LONG:
913                analyzeBinaryOp(analyzedInstruction, RegisterType.Category.LongLo, false);
914                return true;
915            case ADD_FLOAT:
916            case SUB_FLOAT:
917            case MUL_FLOAT:
918            case DIV_FLOAT:
919            case REM_FLOAT:
920                analyzeBinaryOp(analyzedInstruction, RegisterType.Category.Float, false);
921                return true;
922            case ADD_DOUBLE:
923            case SUB_DOUBLE:
924            case MUL_DOUBLE:
925            case DIV_DOUBLE:
926            case REM_DOUBLE:
927                analyzeBinaryOp(analyzedInstruction, RegisterType.Category.DoubleLo, false);
928                return true;
929            case ADD_INT_2ADDR:
930            case SUB_INT_2ADDR:
931            case MUL_INT_2ADDR:
932            case DIV_INT_2ADDR:
933            case REM_INT_2ADDR:
934            case SHL_INT_2ADDR:
935            case SHR_INT_2ADDR:
936            case USHR_INT_2ADDR:
937                analyzeBinary2AddrOp(analyzedInstruction, RegisterType.Category.Integer, false);
938                return true;
939            case AND_INT_2ADDR:
940            case OR_INT_2ADDR:
941            case XOR_INT_2ADDR:
942                analyzeBinary2AddrOp(analyzedInstruction, RegisterType.Category.Integer, true);
943                return true;
944            case ADD_LONG_2ADDR:
945            case SUB_LONG_2ADDR:
946            case MUL_LONG_2ADDR:
947            case DIV_LONG_2ADDR:
948            case REM_LONG_2ADDR:
949            case AND_LONG_2ADDR:
950            case OR_LONG_2ADDR:
951            case XOR_LONG_2ADDR:
952            case SHL_LONG_2ADDR:
953            case SHR_LONG_2ADDR:
954            case USHR_LONG_2ADDR:
955                analyzeBinary2AddrOp(analyzedInstruction, RegisterType.Category.LongLo, false);
956                return true;
957            case ADD_FLOAT_2ADDR:
958            case SUB_FLOAT_2ADDR:
959            case MUL_FLOAT_2ADDR:
960            case DIV_FLOAT_2ADDR:
961            case REM_FLOAT_2ADDR:
962                analyzeBinary2AddrOp(analyzedInstruction, RegisterType.Category.Float, false);
963                return true;
964            case ADD_DOUBLE_2ADDR:
965            case SUB_DOUBLE_2ADDR:
966            case MUL_DOUBLE_2ADDR:
967            case DIV_DOUBLE_2ADDR:
968            case REM_DOUBLE_2ADDR:
969                analyzeBinary2AddrOp(analyzedInstruction, RegisterType.Category.DoubleLo, false);
970                return true;
971            case ADD_INT_LIT16:
972            case RSUB_INT:
973            case MUL_INT_LIT16:
974            case DIV_INT_LIT16:
975            case REM_INT_LIT16:
976                analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.Category.Integer, false);
977                return true;
978            case AND_INT_LIT16:
979            case OR_INT_LIT16:
980            case XOR_INT_LIT16:
981                analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.Category.Integer, true);
982                return true;
983            case ADD_INT_LIT8:
984            case RSUB_INT_LIT8:
985            case MUL_INT_LIT8:
986            case DIV_INT_LIT8:
987            case REM_INT_LIT8:
988            case SHL_INT_LIT8:
989                analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.Category.Integer, false);
990                return true;
991            case AND_INT_LIT8:
992            case OR_INT_LIT8:
993            case XOR_INT_LIT8:
994                analyzeLiteralBinaryOp(analyzedInstruction, RegisterType.Category.Integer, true);
995                return true;
996            case SHR_INT_LIT8:
997                analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, true),
998                        false);
999                return true;
1000            case USHR_INT_LIT8:
1001                analyzeLiteralBinaryOp(analyzedInstruction, getDestTypeForLiteralShiftRight(analyzedInstruction, false),
1002                        false);
1003                return true;
1004
1005            /*odexed instructions*/
1006            case IGET_VOLATILE:
1007            case IPUT_VOLATILE:
1008            case SGET_VOLATILE:
1009            case SPUT_VOLATILE:
1010            case IGET_OBJECT_VOLATILE:
1011            case IGET_WIDE_VOLATILE:
1012            case IPUT_WIDE_VOLATILE:
1013            case SGET_WIDE_VOLATILE:
1014            case SPUT_WIDE_VOLATILE:
1015                analyzePutGetVolatile(analyzedInstruction);
1016                return true;
1017            case THROW_VERIFICATION_ERROR:
1018                return true;
1019            case EXECUTE_INLINE:
1020                analyzeExecuteInline(analyzedInstruction);
1021                return true;
1022            case EXECUTE_INLINE_RANGE:
1023                analyzeExecuteInlineRange(analyzedInstruction);
1024                return true;
1025            case INVOKE_DIRECT_EMPTY:
1026                analyzeInvokeDirectEmpty(analyzedInstruction);
1027                return true;
1028            case IGET_QUICK:
1029            case IGET_WIDE_QUICK:
1030            case IGET_OBJECT_QUICK:
1031            case IPUT_QUICK:
1032            case IPUT_WIDE_QUICK:
1033            case IPUT_OBJECT_QUICK:
1034                return analyzeIputIgetQuick(analyzedInstruction);
1035            case INVOKE_VIRTUAL_QUICK:
1036                return analyzeInvokeVirtualQuick(analyzedInstruction, false, false);
1037            case INVOKE_SUPER_QUICK:
1038                return analyzeInvokeVirtualQuick(analyzedInstruction, true, false);
1039            case INVOKE_VIRTUAL_QUICK_RANGE:
1040                return analyzeInvokeVirtualQuick(analyzedInstruction, false, true);
1041            case INVOKE_SUPER_QUICK_RANGE:
1042                return analyzeInvokeVirtualQuick(analyzedInstruction, true, true);
1043            case IPUT_OBJECT_VOLATILE:
1044            case SGET_OBJECT_VOLATILE:
1045            case SPUT_OBJECT_VOLATILE:
1046                analyzePutGetVolatile(analyzedInstruction);
1047                return true;
1048            default:
1049                assert false;
1050                return true;
1051        }
1052    }
1053
1054
1055        private void verifyInstruction(AnalyzedInstruction analyzedInstruction) {
1056        Instruction instruction = analyzedInstruction.instruction;
1057
1058        switch (instruction.opcode) {
1059            case NOP:
1060                return;
1061            case MOVE:
1062            case MOVE_FROM16:
1063            case MOVE_16:
1064                verifyMove(analyzedInstruction, Primitive32BitCategories);
1065                return;
1066            case MOVE_WIDE:
1067            case MOVE_WIDE_FROM16:
1068            case MOVE_WIDE_16:
1069                verifyMove(analyzedInstruction, WideLowCategories);
1070                return;
1071            case MOVE_OBJECT:
1072            case MOVE_OBJECT_FROM16:
1073            case MOVE_OBJECT_16:
1074                verifyMove(analyzedInstruction, ReferenceOrUninitCategories);
1075                return;
1076            case MOVE_RESULT:
1077                verifyMoveResult(analyzedInstruction, Primitive32BitCategories);
1078                return;
1079            case MOVE_RESULT_WIDE:
1080                verifyMoveResult(analyzedInstruction, WideLowCategories);
1081                return;
1082            case MOVE_RESULT_OBJECT:
1083                verifyMoveResult(analyzedInstruction, ReferenceCategories);
1084                return;
1085            case MOVE_EXCEPTION:
1086                verifyMoveException(analyzedInstruction);
1087                return;
1088            case RETURN_VOID:
1089                verifyReturnVoid(analyzedInstruction);
1090                return;
1091            case RETURN:
1092                verifyReturn(analyzedInstruction, Primitive32BitCategories);
1093                return;
1094            case RETURN_WIDE:
1095                verifyReturn(analyzedInstruction, WideLowCategories);
1096                return;
1097            case RETURN_OBJECT:
1098                verifyReturn(analyzedInstruction, ReferenceCategories);
1099                return;
1100            case CONST_4:
1101            case CONST_16:
1102            case CONST:
1103            case CONST_HIGH16:
1104            case CONST_WIDE_16:
1105            case CONST_WIDE_32:
1106            case CONST_WIDE:
1107            case CONST_WIDE_HIGH16:
1108            case CONST_STRING:
1109            case CONST_STRING_JUMBO:
1110                return;
1111            case CONST_CLASS:
1112                verifyConstClass(analyzedInstruction);
1113                return;
1114            case MONITOR_ENTER:
1115            case MONITOR_EXIT:
1116                verifyMonitor(analyzedInstruction);
1117                return;
1118            case CHECK_CAST:
1119                verifyCheckCast(analyzedInstruction);
1120                return;
1121            case INSTANCE_OF:
1122                verifyInstanceOf(analyzedInstruction);
1123                return;
1124            case ARRAY_LENGTH:
1125                verifyArrayLength(analyzedInstruction);
1126                return;
1127            case NEW_INSTANCE:
1128                verifyNewInstance(analyzedInstruction);
1129                return;
1130            case NEW_ARRAY:
1131                verifyNewArray(analyzedInstruction);
1132                return;
1133            case FILLED_NEW_ARRAY:
1134                verifyFilledNewArray(analyzedInstruction);
1135                return;
1136            case FILLED_NEW_ARRAY_RANGE:
1137                verifyFilledNewArrayRange(analyzedInstruction);
1138                return;
1139            case FILL_ARRAY_DATA:
1140                verifyFillArrayData(analyzedInstruction);
1141                return;
1142            case THROW:
1143                verifyThrow(analyzedInstruction);
1144                return;
1145            case GOTO:
1146            case GOTO_16:
1147            case GOTO_32:
1148                return;
1149            case PACKED_SWITCH:
1150                verifySwitch(analyzedInstruction, Format.PackedSwitchData);
1151                return;
1152            case SPARSE_SWITCH:
1153                verifySwitch(analyzedInstruction, Format.SparseSwitchData);
1154                return;
1155            case CMPL_FLOAT:
1156            case CMPG_FLOAT:
1157                verifyFloatWideCmp(analyzedInstruction, Primitive32BitCategories);
1158                return;
1159            case CMPL_DOUBLE:
1160            case CMPG_DOUBLE:
1161            case CMP_LONG:
1162                verifyFloatWideCmp(analyzedInstruction, WideLowCategories);
1163                return;
1164            case IF_EQ:
1165            case IF_NE:
1166                verifyIfEqNe(analyzedInstruction);
1167                return;
1168            case IF_LT:
1169            case IF_GE:
1170            case IF_GT:
1171            case IF_LE:
1172                verifyIf(analyzedInstruction);
1173                return;
1174            case IF_EQZ:
1175            case IF_NEZ:
1176                verifyIfEqzNez(analyzedInstruction);
1177                return;
1178            case IF_LTZ:
1179            case IF_GEZ:
1180            case IF_GTZ:
1181            case IF_LEZ:
1182                verifyIfz(analyzedInstruction);
1183                return;
1184            case AGET:
1185                verify32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Integer);
1186                return;
1187            case AGET_BOOLEAN:
1188                verify32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Boolean);
1189                return;
1190            case AGET_BYTE:
1191                verify32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Byte);
1192                return;
1193            case AGET_CHAR:
1194                verify32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Char);
1195                return;
1196            case AGET_SHORT:
1197                verify32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Short);
1198                return;
1199            case AGET_WIDE:
1200                verifyAgetWide(analyzedInstruction);
1201                return;
1202            case AGET_OBJECT:
1203                verifyAgetObject(analyzedInstruction);
1204                return;
1205            case APUT:
1206                verify32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Integer);
1207                return;
1208            case APUT_BOOLEAN:
1209                verify32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Boolean);
1210                return;
1211            case APUT_BYTE:
1212                verify32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Byte);
1213                return;
1214            case APUT_CHAR:
1215                verify32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Char);
1216                return;
1217            case APUT_SHORT:
1218                verify32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Short);
1219                return;
1220            case APUT_WIDE:
1221                verifyAputWide(analyzedInstruction);
1222                return;
1223            case APUT_OBJECT:
1224                verifyAputObject(analyzedInstruction);
1225                return;
1226            case IGET:
1227                verify32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Integer);
1228                return;
1229            case IGET_BOOLEAN:
1230                verify32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Boolean);
1231                return;
1232            case IGET_BYTE:
1233                verify32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Byte);
1234                return;
1235            case IGET_CHAR:
1236                verify32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Char);
1237                return;
1238            case IGET_SHORT:
1239                verify32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Short);
1240                return;
1241            case IGET_WIDE:
1242                verifyIgetWide(analyzedInstruction);
1243                return;
1244            case IGET_OBJECT:
1245                verifyIgetObject(analyzedInstruction);
1246                return;
1247            case IPUT:
1248                verify32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Integer);
1249                return;
1250            case IPUT_BOOLEAN:
1251                verify32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Boolean);
1252                return;
1253            case IPUT_BYTE:
1254                verify32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Byte);
1255                return;
1256            case IPUT_CHAR:
1257                verify32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Char);
1258                return;
1259            case IPUT_SHORT:
1260                verify32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Short);
1261                return;
1262            case IPUT_WIDE:
1263                verifyIputWide(analyzedInstruction);
1264                return;
1265            case IPUT_OBJECT:
1266                verifyIputObject(analyzedInstruction);
1267                return;
1268            case SGET:
1269                verify32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Integer);
1270                return;
1271            case SGET_BOOLEAN:
1272                verify32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Boolean);
1273                return;
1274            case SGET_BYTE:
1275                verify32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Byte);
1276                return;
1277            case SGET_CHAR:
1278                verify32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Char);
1279                return;
1280            case SGET_SHORT:
1281                verify32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Short);
1282                return;
1283            case SGET_WIDE:
1284                verifySgetWide(analyzedInstruction);
1285                return;
1286            case SGET_OBJECT:
1287                verifySgetObject(analyzedInstruction);
1288                return;
1289            case SPUT:
1290                verify32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Integer);
1291                return;
1292            case SPUT_BOOLEAN:
1293                verify32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Boolean);
1294                return;
1295            case SPUT_BYTE:
1296                verify32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Byte);
1297                return;
1298            case SPUT_CHAR:
1299                verify32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Char);
1300                return;
1301            case SPUT_SHORT:
1302                verify32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Short);
1303                return;
1304            case SPUT_WIDE:
1305                verifySputWide(analyzedInstruction);
1306                return;
1307            case SPUT_OBJECT:
1308                verifySputObject(analyzedInstruction);
1309                return;
1310            case INVOKE_VIRTUAL:
1311                verifyInvoke(analyzedInstruction, INVOKE_VIRTUAL);
1312                return;
1313            case INVOKE_SUPER:
1314                verifyInvoke(analyzedInstruction, INVOKE_SUPER);
1315                return;
1316            case INVOKE_DIRECT:
1317                verifyInvoke(analyzedInstruction, INVOKE_DIRECT);
1318                return;
1319            case INVOKE_STATIC:
1320                verifyInvoke(analyzedInstruction, INVOKE_STATIC);
1321                return;
1322            case INVOKE_INTERFACE:
1323                verifyInvoke(analyzedInstruction, INVOKE_INTERFACE);
1324                return;
1325            case INVOKE_VIRTUAL_RANGE:
1326                verifyInvokeRange(analyzedInstruction, INVOKE_VIRTUAL);
1327                return;
1328            case INVOKE_SUPER_RANGE:
1329                verifyInvokeRange(analyzedInstruction, INVOKE_SUPER);
1330                return;
1331            case INVOKE_DIRECT_RANGE:
1332                verifyInvokeRange(analyzedInstruction, INVOKE_DIRECT);
1333                return;
1334            case INVOKE_STATIC_RANGE:
1335                verifyInvokeRange(analyzedInstruction, INVOKE_STATIC);
1336                return;
1337            case INVOKE_INTERFACE_RANGE:
1338                verifyInvokeRange(analyzedInstruction, INVOKE_INTERFACE);
1339                return;
1340            case NEG_INT:
1341            case NOT_INT:
1342                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1343                return;
1344            case NEG_LONG:
1345            case NOT_LONG:
1346                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1347                return;
1348            case NEG_FLOAT:
1349                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1350                return;
1351            case NEG_DOUBLE:
1352                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1353                return;
1354            case INT_TO_LONG:
1355                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1356                return;
1357            case INT_TO_FLOAT:
1358                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1359                return;
1360            case INT_TO_DOUBLE:
1361                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1362                return;
1363            case LONG_TO_INT:
1364            case DOUBLE_TO_INT:
1365                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1366                return;
1367            case LONG_TO_FLOAT:
1368            case DOUBLE_TO_FLOAT:
1369                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1370                return;
1371            case LONG_TO_DOUBLE:
1372                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1373                return;
1374            case FLOAT_TO_INT:
1375                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1376                return;
1377            case FLOAT_TO_LONG:
1378                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1379                return;
1380            case FLOAT_TO_DOUBLE:
1381                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1382                return;
1383            case DOUBLE_TO_LONG:
1384                verifyUnaryOp(analyzedInstruction, WideLowCategories);
1385                return;
1386            case INT_TO_BYTE:
1387                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1388                return;
1389            case INT_TO_CHAR:
1390                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1391                return;
1392            case INT_TO_SHORT:
1393                verifyUnaryOp(analyzedInstruction, Primitive32BitCategories);
1394                return;
1395            case ADD_INT:
1396            case SUB_INT:
1397            case MUL_INT:
1398            case DIV_INT:
1399            case REM_INT:
1400            case SHL_INT:
1401            case SHR_INT:
1402            case USHR_INT:
1403            case AND_INT:
1404            case OR_INT:
1405            case XOR_INT:
1406                verifyBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories);
1407                return;
1408            case ADD_LONG:
1409            case SUB_LONG:
1410            case MUL_LONG:
1411            case DIV_LONG:
1412            case REM_LONG:
1413            case AND_LONG:
1414            case OR_LONG:
1415            case XOR_LONG:
1416                verifyBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories);
1417                return;
1418            case SHL_LONG:
1419            case SHR_LONG:
1420            case USHR_LONG:
1421                verifyBinaryOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories);
1422                return;
1423            case ADD_FLOAT:
1424            case SUB_FLOAT:
1425            case MUL_FLOAT:
1426            case DIV_FLOAT:
1427            case REM_FLOAT:
1428                verifyBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories);
1429                return;
1430            case ADD_DOUBLE:
1431            case SUB_DOUBLE:
1432            case MUL_DOUBLE:
1433            case DIV_DOUBLE:
1434            case REM_DOUBLE:
1435                verifyBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories);
1436                return;
1437            case ADD_INT_2ADDR:
1438            case SUB_INT_2ADDR:
1439            case MUL_INT_2ADDR:
1440            case DIV_INT_2ADDR:
1441            case REM_INT_2ADDR:
1442            case SHL_INT_2ADDR:
1443            case SHR_INT_2ADDR:
1444            case USHR_INT_2ADDR:
1445            case AND_INT_2ADDR:
1446            case OR_INT_2ADDR:
1447            case XOR_INT_2ADDR:
1448                verifyBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories);
1449                return;
1450            case ADD_LONG_2ADDR:
1451            case SUB_LONG_2ADDR:
1452            case MUL_LONG_2ADDR:
1453            case DIV_LONG_2ADDR:
1454            case REM_LONG_2ADDR:
1455            case AND_LONG_2ADDR:
1456            case OR_LONG_2ADDR:
1457            case XOR_LONG_2ADDR:
1458                verifyBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories);
1459                return;
1460            case SHL_LONG_2ADDR:
1461            case SHR_LONG_2ADDR:
1462            case USHR_LONG_2ADDR:
1463                verifyBinary2AddrOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories);
1464                return;
1465            case ADD_FLOAT_2ADDR:
1466            case SUB_FLOAT_2ADDR:
1467            case MUL_FLOAT_2ADDR:
1468            case DIV_FLOAT_2ADDR:
1469            case REM_FLOAT_2ADDR:
1470                verifyBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories);
1471                return;
1472            case ADD_DOUBLE_2ADDR:
1473            case SUB_DOUBLE_2ADDR:
1474            case MUL_DOUBLE_2ADDR:
1475            case DIV_DOUBLE_2ADDR:
1476            case REM_DOUBLE_2ADDR:
1477                verifyBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories);
1478                return;
1479            case ADD_INT_LIT16:
1480            case RSUB_INT:
1481            case MUL_INT_LIT16:
1482            case DIV_INT_LIT16:
1483            case REM_INT_LIT16:
1484                verifyLiteralBinaryOp(analyzedInstruction);
1485                return;
1486            case AND_INT_LIT16:
1487            case OR_INT_LIT16:
1488            case XOR_INT_LIT16:
1489                verifyLiteralBinaryOp(analyzedInstruction);
1490                return;
1491            case ADD_INT_LIT8:
1492            case RSUB_INT_LIT8:
1493            case MUL_INT_LIT8:
1494            case DIV_INT_LIT8:
1495            case REM_INT_LIT8:
1496            case SHL_INT_LIT8:
1497                verifyLiteralBinaryOp(analyzedInstruction);
1498                return;
1499            case AND_INT_LIT8:
1500            case OR_INT_LIT8:
1501            case XOR_INT_LIT8:
1502                verifyLiteralBinaryOp(analyzedInstruction);
1503                return;
1504            case SHR_INT_LIT8:
1505                verifyLiteralBinaryOp(analyzedInstruction);
1506                return;
1507            case USHR_INT_LIT8:
1508                verifyLiteralBinaryOp(analyzedInstruction);
1509                return;
1510            case IGET_VOLATILE:
1511            case IPUT_VOLATILE:
1512            case SGET_VOLATILE:
1513            case SPUT_VOLATILE:
1514            case IGET_OBJECT_VOLATILE:
1515            case IGET_WIDE_VOLATILE:
1516            case IPUT_WIDE_VOLATILE:
1517            case SGET_WIDE_VOLATILE:
1518            case SPUT_WIDE_VOLATILE:
1519            case THROW_VERIFICATION_ERROR:
1520            case EXECUTE_INLINE:
1521            case EXECUTE_INLINE_RANGE:
1522            case INVOKE_DIRECT_EMPTY:
1523            case IGET_QUICK:
1524            case IGET_WIDE_QUICK:
1525            case IGET_OBJECT_QUICK:
1526            case IPUT_QUICK:
1527            case IPUT_WIDE_QUICK:
1528            case IPUT_OBJECT_QUICK:
1529            case INVOKE_VIRTUAL_QUICK:
1530            case INVOKE_SUPER_QUICK:
1531            case INVOKE_VIRTUAL_QUICK_RANGE:
1532            case INVOKE_SUPER_QUICK_RANGE:
1533            case IPUT_OBJECT_VOLATILE:
1534            case SGET_OBJECT_VOLATILE:
1535            case SPUT_OBJECT_VOLATILE:
1536                //TODO: throw validation exception?
1537            default:
1538                assert false;
1539                return;
1540        }
1541    }
1542
1543    private static final EnumSet<RegisterType.Category> Primitive32BitCategories = EnumSet.of(
1544            RegisterType.Category.Null,
1545            RegisterType.Category.One,
1546            RegisterType.Category.Boolean,
1547            RegisterType.Category.Byte,
1548            RegisterType.Category.PosByte,
1549            RegisterType.Category.Short,
1550            RegisterType.Category.PosShort,
1551            RegisterType.Category.Char,
1552            RegisterType.Category.Integer,
1553            RegisterType.Category.Float);
1554
1555    private static final EnumSet<RegisterType.Category> WideLowCategories = EnumSet.of(
1556            RegisterType.Category.LongLo,
1557            RegisterType.Category.DoubleLo);
1558
1559    private static final EnumSet<RegisterType.Category> WideHighCategories = EnumSet.of(
1560            RegisterType.Category.LongHi,
1561            RegisterType.Category.DoubleHi);
1562
1563    private static final EnumSet<RegisterType.Category> ReferenceCategories = EnumSet.of(
1564            RegisterType.Category.Null,
1565            RegisterType.Category.Reference);
1566
1567    private static final EnumSet<RegisterType.Category> ReferenceOrUninitThisCategories = EnumSet.of(
1568            RegisterType.Category.Null,
1569            RegisterType.Category.UninitThis,
1570            RegisterType.Category.Reference);
1571
1572    private static final EnumSet<RegisterType.Category> ReferenceOrUninitCategories = EnumSet.of(
1573            RegisterType.Category.Null,
1574            RegisterType.Category.UninitRef,
1575            RegisterType.Category.UninitThis,
1576            RegisterType.Category.Reference);
1577
1578    private static final EnumSet<RegisterType.Category> ReferenceAndPrimitive32BitCategories = EnumSet.of(
1579            RegisterType.Category.Null,
1580            RegisterType.Category.One,
1581            RegisterType.Category.Boolean,
1582            RegisterType.Category.Byte,
1583            RegisterType.Category.PosByte,
1584            RegisterType.Category.Short,
1585            RegisterType.Category.PosShort,
1586            RegisterType.Category.Char,
1587            RegisterType.Category.Integer,
1588            RegisterType.Category.Float,
1589            RegisterType.Category.Reference);
1590
1591    private static final EnumSet<RegisterType.Category> BooleanCategories = EnumSet.of(
1592            RegisterType.Category.Null,
1593            RegisterType.Category.One,
1594            RegisterType.Category.Boolean);
1595
1596    private void analyzeMove(AnalyzedInstruction analyzedInstruction) {
1597        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1598
1599        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1600        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
1601    }
1602
1603    private void verifyMove(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1604        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1605
1606        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validCategories);
1607    }
1608
1609    private void analyzeMoveResult(AnalyzedInstruction analyzedInstruction) {
1610        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
1611        if (!previousInstruction.instruction.opcode.setsResult()) {
1612            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
1613                    "invoke-*/fill-new-array instruction");
1614        }
1615
1616        RegisterType resultRegisterType;
1617        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.instruction;
1618        Item item = invokeInstruction.getReferencedItem();
1619
1620        if (item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM) {
1621            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
1622                    ((MethodIdItem)item).getPrototype().getReturnType());
1623        } else {
1624            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1625            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1626        }
1627
1628        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, resultRegisterType);
1629    }
1630
1631    private void verifyMoveResult(AnalyzedInstruction analyzedInstruction,
1632                                     EnumSet<RegisterType.Category> allowedCategories) {
1633        if (analyzedInstruction.instructionIndex == 0) {
1634            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " cannot be the first " +
1635                    "instruction in a method. It must occur after an invoke-*/fill-new-array instruction");
1636        }
1637
1638        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
1639
1640        if (!previousInstruction.instruction.opcode.setsResult()) {
1641            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
1642                    "invoke-*/fill-new-array instruction");
1643        }
1644
1645        //TODO: does dalvik allow a move-result after an invoke with a void return type?
1646        RegisterType resultRegisterType;
1647
1648        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.getInstruction();
1649        Item item = invokeInstruction.getReferencedItem();
1650
1651        if (item instanceof MethodIdItem) {
1652            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
1653                    ((MethodIdItem)item).getPrototype().getReturnType());
1654        } else {
1655            assert item instanceof TypeIdItem;
1656            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1657        }
1658
1659        if (!allowedCategories.contains(resultRegisterType.category)) {
1660            throw new ValidationException(String.format("Wrong move-result* instruction for return value %s",
1661                    resultRegisterType.toString()));
1662        }
1663    }
1664
1665    private void analyzeMoveException(AnalyzedInstruction analyzedInstruction) {
1666        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
1667        int instructionAddress = getInstructionAddress(analyzedInstruction);
1668
1669        if (tries == null) {
1670            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1671        }
1672
1673        RegisterType exceptionType = null;
1674
1675        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
1676            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
1677                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
1678                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
1679                break;
1680            }
1681            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
1682                if (handler.getHandlerAddress() == instructionAddress) {
1683                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
1684                            .merge(exceptionType);
1685                }
1686            }
1687        }
1688
1689        if (exceptionType == null) {
1690            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1691        }
1692
1693        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
1694    }
1695
1696    private void verifyMoveException(AnalyzedInstruction analyzedInstruction) {
1697        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
1698        int instructionAddress = getInstructionAddress(analyzedInstruction);
1699
1700        if (tries == null) {
1701            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1702        }
1703
1704        RegisterType exceptionType = null;
1705
1706        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
1707            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
1708                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
1709                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
1710                break;
1711            }
1712            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
1713                if (handler.getHandlerAddress() == instructionAddress) {
1714                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
1715                            .merge(exceptionType);
1716                }
1717            }
1718        }
1719
1720        if (exceptionType == null) {
1721            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1722        }
1723
1724        //TODO: check if the type is a throwable. Should we throw a ValidationException or print a warning? (does dalvik validate that it's a throwable? It doesn't in CodeVerify.c, but it might check in DexSwapVerify.c)
1725        if (exceptionType.category != RegisterType.Category.Reference) {
1726            throw new ValidationException(String.format("Exception type %s is not a reference type",
1727                    exceptionType.toString()));
1728        }
1729    }
1730
1731    private void verifyReturnVoid(AnalyzedInstruction analyzedInstruction) {
1732        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1733        if (returnType.getTypeDescriptor().charAt(0) != 'V') {
1734            //TODO: could add which return-* variation should be used instead
1735            throw new ValidationException("Cannot use return-void with a non-void return type (" +
1736                returnType.getTypeDescriptor() + ")");
1737        }
1738    }
1739
1740    private void verifyReturn(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1741        /*if (this.isInstanceConstructor()) {
1742            checkConstructorReturn(analyzedInstruction);
1743        }*/
1744
1745        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1746        int returnRegister = instruction.getRegisterA();
1747        RegisterType returnRegisterType = getAndCheckSourceRegister(analyzedInstruction, returnRegister,
1748                validCategories);
1749
1750        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1751        if (returnType.getTypeDescriptor().charAt(0) == 'V') {
1752            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
1753        }
1754
1755        RegisterType methodReturnRegisterType = RegisterType.getRegisterTypeForTypeIdItem(returnType);
1756
1757        if (!validCategories.contains(methodReturnRegisterType.category)) {
1758            //TODO: could add which return-* variation should be used instead
1759            throw new ValidationException(String.format("Cannot use %s with return type %s",
1760                    analyzedInstruction.instruction.opcode.name, returnType.getTypeDescriptor()));
1761        }
1762
1763        if (validCategories == ReferenceCategories) {
1764            if (methodReturnRegisterType.type.isInterface()) {
1765                if (returnRegisterType.category != RegisterType.Category.Null &&
1766                    !returnRegisterType.type.implementsInterface(methodReturnRegisterType.type)) {
1767                    //TODO: how to handle warnings?
1768                }
1769            } else {
1770                if (returnRegisterType.category == RegisterType.Category.Reference &&
1771                    !returnRegisterType.type.extendsClass(methodReturnRegisterType.type)) {
1772
1773                    throw new ValidationException(String.format("The return value in register v%d (%s) is not " +
1774                            "compatible with the method's return type %s", returnRegister,
1775                            returnRegisterType.type.getClassType(), methodReturnRegisterType.type.getClassType()));
1776                }
1777            }
1778        }
1779    }
1780
1781    private void analyzeConst(AnalyzedInstruction analyzedInstruction) {
1782        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
1783
1784        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(instruction.getLiteral());
1785
1786        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1787        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1788        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
1789    }
1790
1791    private void analyzeConstHigh16(AnalyzedInstruction analyzedInstruction) {
1792        //the literal value stored in the instruction is a 16-bit value. When shifted left by 16, it will always be an
1793        //integer
1794        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1795                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
1796    }
1797
1798    private void analyzeWideConst(AnalyzedInstruction analyzedInstruction) {
1799        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1800                RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1801    }
1802
1803    private void analyzeConstString(AnalyzedInstruction analyzedInstruction) {
1804        ClassPath.ClassDef stringClassDef = ClassPath.getClassDef("Ljava/lang/String;");
1805        RegisterType stringType = RegisterType.getRegisterType(RegisterType.Category.Reference, stringClassDef);
1806        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
1807    }
1808
1809    private void analyzeConstClass(AnalyzedInstruction analyzedInstruction) {
1810        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
1811        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
1812
1813        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, classType);
1814    }
1815
1816
1817    private void verifyConstClass(AnalyzedInstruction analyzedInstruction) {
1818        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
1819        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
1820
1821        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1822        Item item = instruction.getReferencedItem();
1823        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1824
1825        //TODO: need to check class access
1826        //make sure the referenced class is resolvable
1827        ClassPath.getClassDef((TypeIdItem)item);
1828    }
1829
1830    private void verifyMonitor(AnalyzedInstruction analyzedInstruction) {
1831        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1832        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), ReferenceCategories);
1833    }
1834
1835    private void analyzeCheckCast(AnalyzedInstruction analyzedInstruction) {
1836        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1837
1838        Item item = instruction.getReferencedItem();
1839        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1840
1841        RegisterType castRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1842        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, castRegisterType);
1843    }
1844
1845    private void verifyCheckCast(AnalyzedInstruction analyzedInstruction) {
1846        {
1847            //ensure the "source" register is a reference type
1848            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1849
1850            RegisterType registerType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
1851                    ReferenceCategories);
1852        }
1853
1854        {
1855            //resolve and verify the class that we're casting to
1856            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1857
1858            Item item = instruction.getReferencedItem();
1859            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1860
1861            //TODO: need to check class access
1862            RegisterType castRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1863            if (castRegisterType.category != RegisterType.Category.Reference) {
1864                //TODO: verify that dalvik allows a non-reference type..
1865                //TODO: print a warning, but don't re-throw the exception. dalvik allows a non-reference type during validation (but throws an exception at runtime)
1866            }
1867        }
1868    }
1869
1870    private void analyzeInstanceOf(AnalyzedInstruction analyzedInstruction) {
1871        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1872                RegisterType.getRegisterType(RegisterType.Category.Boolean, null));
1873    }
1874
1875    private void verifyInstanceOf(AnalyzedInstruction analyzedInstruction) {
1876        {
1877            //ensure the register that is being checks is a reference type
1878            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1879
1880            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), ReferenceCategories);
1881        }
1882
1883        {
1884            //resolve and verify the class that we're checking against
1885            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1886
1887            Item item = instruction.getReferencedItem();
1888            assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1889            RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1890            if (registerType.category != RegisterType.Category.Reference) {
1891                throw new ValidationException(String.format("Cannot use instance-of with a non-reference type %s",
1892                        registerType.toString()));
1893            }
1894
1895            //TODO: is it valid to use an array type?
1896            //TODO: could probably do an even more sophisticated check, where we check the possible register types against the specified type. In some cases, we could determine that it always fails, and print a warning to that effect.
1897        }
1898    }
1899
1900    private void analyzeArrayLength(AnalyzedInstruction analyzedInstruction) {
1901        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1902                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
1903    }
1904
1905    private void verifyArrayLength(AnalyzedInstruction analyzedInstruction) {
1906        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1907
1908        int arrayRegisterNumber = instruction.getRegisterB();
1909        RegisterType arrayRegisterType = getAndCheckSourceRegister(analyzedInstruction, arrayRegisterNumber,
1910                ReferenceCategories);
1911
1912        if (arrayRegisterType.type != null) {
1913            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1914                throw new ValidationException(String.format("Cannot use array-length with non-array type %s",
1915                        arrayRegisterType.type.getClassType()));
1916            }
1917            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1918        }
1919    }
1920
1921    private void analyzeNewInstance(AnalyzedInstruction analyzedInstruction) {
1922        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1923
1924        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1925        RegisterType destRegisterType = analyzedInstruction.getPostInstructionRegisterType(register);
1926        if (destRegisterType.category != RegisterType.Category.Unknown) {
1927            assert destRegisterType.category == RegisterType.Category.UninitRef;
1928
1929            //the post-instruction destination register will only be set if we have already analyzed this instruction
1930            //at least once. If this is the case, then the uninit reference has already been propagated to all
1931            //successors and nothing else needs to be done.
1932            return;
1933        }
1934
1935        Item item = instruction.getReferencedItem();
1936        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1937
1938        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1939
1940        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1941                RegisterType.getUnitializedReference(classType.type));
1942    }
1943
1944    private void verifyNewInstance(AnalyzedInstruction analyzedInstruction) {
1945        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1946
1947        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1948        RegisterType destRegisterType = analyzedInstruction.postRegisterMap[register];
1949        if (destRegisterType.category != RegisterType.Category.Unknown) {
1950            assert destRegisterType.category == RegisterType.Category.UninitRef;
1951
1952            //the "post-instruction" destination register will only be set if we've gone over
1953            //this instruction at least once before. If this is the case, then we need to check
1954            //all the other registers, and make sure that none of them contain the same
1955            //uninitialized reference that is in the destination register.
1956
1957            for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
1958                if (i==register) {
1959                    continue;
1960                }
1961
1962                if (analyzedInstruction.getPreInstructionRegisterType(i) == destRegisterType) {
1963                    throw new ValidationException(String.format("Register v%d contains an uninitialized reference " +
1964                            "that was created by this new-instance instruction.", i));
1965                }
1966            }
1967
1968            return;
1969        }
1970
1971        Item item = instruction.getReferencedItem();
1972        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1973
1974        //TODO: need to check class access
1975        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1976        if (classType.category != RegisterType.Category.Reference) {
1977            throw new ValidationException(String.format("Cannot use new-instance with a non-reference type %s",
1978                    classType.toString()));
1979        }
1980
1981        if (((TypeIdItem)item).getTypeDescriptor().charAt(0) == '[') {
1982            throw new ValidationException("Cannot use array type \"" + ((TypeIdItem)item).getTypeDescriptor() +
1983                    "\" with new-instance. Use new-array instead.");
1984        }
1985    }
1986
1987    private void analyzeNewArray(AnalyzedInstruction analyzedInstruction) {
1988        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1989
1990        Item item = instruction.getReferencedItem();
1991        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1992
1993        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1994        assert arrayType.type instanceof ClassPath.ArrayClassDef;
1995
1996        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1997    }
1998
1999    private void verifyNewArray(AnalyzedInstruction analyzedInstruction) {
2000        {
2001            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2002            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
2003        }
2004
2005        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2006
2007        Item item = instruction.getReferencedItem();
2008        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
2009
2010        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
2011        assert arrayType.type instanceof ClassPath.ArrayClassDef;
2012
2013        if (arrayType.category != RegisterType.Category.Reference) {
2014            throw new ValidationException(String.format("Cannot use new-array with a non-reference type %s",
2015                    arrayType.toString()));
2016        }
2017        if (arrayType.type.getClassType().charAt(0) != '[') {
2018            throw new ValidationException("Cannot use non-array type \"" + arrayType.type.getClassType() +
2019                    "\" with new-array. Use new-instance instead.");
2020        }
2021    }
2022
2023    private void verifyFilledNewArrayCommon(AnalyzedInstruction analyzedInstruction,
2024                                               RegisterIterator registerIterator) {
2025        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2026
2027        RegisterType arrayType;
2028        RegisterType arrayImmediateElementType;
2029
2030        Item item = instruction.getReferencedItem();
2031        assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
2032
2033        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
2034
2035        if (classDef.getClassType().charAt(0) != '[') {
2036            throw new ValidationException("Cannot use non-array type \"" + classDef.getClassType() +
2037                "\" with new-array. Use new-instance instead.");
2038        }
2039
2040        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)classDef;
2041        arrayType = RegisterType.getRegisterType(RegisterType.Category.Reference, classDef);
2042        arrayImmediateElementType = RegisterType.getRegisterTypeForType(
2043                arrayClassDef.getImmediateElementClass().getClassType());
2044        String baseElementType = arrayClassDef.getBaseElementClass().getClassType();
2045        if (baseElementType.charAt(0) == 'J' || baseElementType.charAt(0) == 'D') {
2046            throw new ValidationException("Cannot use filled-new-array to create an array of wide values " +
2047                    "(long or double)");
2048        }
2049
2050        do {
2051            int register = registerIterator.getRegister();
2052            RegisterType elementType = analyzedInstruction.getPreInstructionRegisterType(register);
2053            assert elementType != null;
2054
2055            if (!elementType.canBeAssignedTo(arrayImmediateElementType)) {
2056                throw new ValidationException("Register v" + Integer.toString(register) + " is of type " +
2057                        elementType.toString() + " and is incompatible with the array type " +
2058                        arrayType.type.getClassType());
2059            }
2060        } while (registerIterator.moveNext());
2061    }
2062
2063    private void verifyFilledNewArray(AnalyzedInstruction analyzedInstruction) {
2064        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
2065        verifyFilledNewArrayCommon(analyzedInstruction, new Format35cRegisterIterator(instruction));
2066    }
2067
2068    private void verifyFilledNewArrayRange(AnalyzedInstruction analyzedInstruction) {
2069        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
2070
2071        //instruction.getStartRegister() and instruction.getRegCount() both return an int value, but are actually
2072        //unsigned 16 bit values, so we don't have to worry about overflowing an int when adding them together
2073        if (instruction.getStartRegister() + instruction.getRegCount() >= 1<<16) {
2074            throw new ValidationException(String.format("Invalid register range {v%d .. v%d}. The ending register " +
2075                    "is larger than the largest allowed register of v65535.",
2076                    instruction.getStartRegister(),
2077                    instruction.getStartRegister() + instruction.getRegCount() - 1));
2078        }
2079
2080        verifyFilledNewArrayCommon(analyzedInstruction, new Format3rcRegisterIterator(instruction));
2081    }
2082
2083    private void verifyFillArrayData(AnalyzedInstruction analyzedInstruction) {
2084        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2085
2086        int register = instruction.getRegisterA();
2087        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
2088        assert registerType != null;
2089
2090        if (registerType.category == RegisterType.Category.Null) {
2091            return;
2092        }
2093
2094        if (registerType.category != RegisterType.Category.Reference) {
2095            throw new ValidationException(String.format("Cannot use fill-array-data with non-array register v%d of " +
2096                    "type %s", register, registerType.toString()));
2097        }
2098
2099        assert registerType.type instanceof ClassPath.ArrayClassDef;
2100        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)registerType.type;
2101
2102        if (arrayClassDef.getArrayDimensions() != 1) {
2103            throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can only " +
2104                    "be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
2105        }
2106
2107        int elementWidth;
2108        switch (arrayClassDef.getBaseElementClass().getClassType().charAt(0)) {
2109            case 'Z':
2110            case 'B':
2111                elementWidth = 1;
2112                break;
2113            case 'C':
2114            case 'S':
2115                elementWidth = 2;
2116                break;
2117            case 'I':
2118            case 'F':
2119                elementWidth = 4;
2120                break;
2121            case 'J':
2122            case 'D':
2123                elementWidth = 8;
2124                break;
2125            default:
2126                throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can " +
2127                        "only be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
2128        }
2129
2130
2131        int arrayDataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
2132        int arrayDataCodeAddress = getInstructionAddress(analyzedInstruction) + arrayDataAddressOffset;
2133        AnalyzedInstruction arrayDataInstruction = this.instructions.get(arrayDataCodeAddress);
2134        if (arrayDataInstruction == null || arrayDataInstruction.instruction.getFormat() != Format.ArrayData) {
2135            throw new ValidationException(String.format("Could not find an array data structure at code address 0x%x",
2136                    arrayDataCodeAddress));
2137        }
2138
2139        ArrayDataPseudoInstruction arrayDataPseudoInstruction =
2140                (ArrayDataPseudoInstruction)arrayDataInstruction.instruction;
2141
2142        if (elementWidth != arrayDataPseudoInstruction.getElementWidth()) {
2143            throw new ValidationException(String.format("The array data at code address 0x%x does not have the " +
2144                    "correct element width for array type %s. Expecting element width %d, got element width %d.",
2145                    arrayDataCodeAddress, arrayClassDef.getClassType(), elementWidth,
2146                    arrayDataPseudoInstruction.getElementWidth()));
2147        }
2148    }
2149
2150    private void verifyThrow(AnalyzedInstruction analyzedInstruction) {
2151        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
2152
2153        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
2154        assert registerType != null;
2155
2156        if (registerType.category == RegisterType.Category.Null) {
2157            return;
2158        }
2159
2160        if (registerType.category != RegisterType.Category.Reference) {
2161            throw new ValidationException(String.format("Cannot use throw with non-reference type %s in register v%d",
2162                    registerType.toString(), register));
2163        }
2164
2165        assert registerType.type != null;
2166
2167        if (!registerType.type.extendsClass(ClassPath.getClassDef("Ljava/lang/Throwable;"))) {
2168            throw new ValidationException(String.format("Cannot use throw with non-throwable type %s in register v%d",
2169                    registerType.type.getClassType(), register));
2170        }
2171    }
2172
2173    private void analyzeArrayDataOrSwitch(AnalyzedInstruction analyzedInstruction) {
2174        int dataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
2175
2176        int dataCodeAddress = this.getInstructionAddress(analyzedInstruction) + dataAddressOffset;
2177        AnalyzedInstruction dataAnalyzedInstruction = instructions.get(dataCodeAddress);
2178
2179        if (dataAnalyzedInstruction != null) {
2180            dataAnalyzedInstruction.dead = false;
2181
2182            //if there is a preceding nop, it's deadness should be the same
2183            AnalyzedInstruction priorInstruction =
2184                    instructions.valueAt(dataAnalyzedInstruction.getInstructionIndex()-1);
2185            if (priorInstruction.getInstruction().opcode == Opcode.NOP &&
2186                    !priorInstruction.getInstruction().getFormat().variableSizeFormat) {
2187
2188                priorInstruction.dead = false;
2189            }
2190        }
2191    }
2192
2193    private void verifySwitch(AnalyzedInstruction analyzedInstruction, Format expectedSwitchDataFormat) {
2194        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
2195        int switchCodeAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
2196
2197        getAndCheckSourceRegister(analyzedInstruction, register, Primitive32BitCategories);
2198
2199        int switchDataCodeAddress = this.getInstructionAddress(analyzedInstruction) + switchCodeAddressOffset;
2200        AnalyzedInstruction switchDataAnalyzedInstruction = instructions.get(switchDataCodeAddress);
2201
2202        if (switchDataAnalyzedInstruction == null ||
2203            switchDataAnalyzedInstruction.instruction.getFormat() != expectedSwitchDataFormat) {
2204            throw new ValidationException(String.format("There is no %s structure at code address 0x%x",
2205                    expectedSwitchDataFormat.name(), switchDataCodeAddress));
2206        }
2207    }
2208
2209    private void analyzeFloatWideCmp(AnalyzedInstruction analyzedInstruction) {
2210        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2211                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
2212    }
2213
2214    private void verifyFloatWideCmp(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
2215        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2216
2217        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validCategories);
2218        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), validCategories);
2219    }
2220
2221    private void verifyIfEqNe(AnalyzedInstruction analyzedInstruction) {
2222        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2223
2224        RegisterType registerType1 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2225        assert registerType1 != null;
2226
2227        RegisterType registerType2 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2228        assert registerType2 != null;
2229
2230        if (!(
2231                (ReferenceCategories.contains(registerType1.category) &&
2232                ReferenceCategories.contains(registerType2.category))
2233                    ||
2234                (Primitive32BitCategories.contains(registerType1.category) &&
2235                Primitive32BitCategories.contains(registerType2.category))
2236              )) {
2237
2238            throw new ValidationException(String.format("%s cannot be used on registers of dissimilar types %s and " +
2239                    "%s. They must both be a reference type or a primitive 32 bit type.",
2240                    analyzedInstruction.instruction.opcode.name, registerType1.toString(), registerType2.toString()));
2241        }
2242    }
2243
2244    private void verifyIf(AnalyzedInstruction analyzedInstruction) {
2245        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2246
2247        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
2248        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
2249    }
2250
2251    private void verifyIfEqzNez(AnalyzedInstruction analyzedInstruction) {
2252        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2253
2254        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2255                ReferenceAndPrimitive32BitCategories);
2256    }
2257
2258    private void verifyIfz(AnalyzedInstruction analyzedInstruction) {
2259        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2260
2261        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
2262    }
2263
2264    private void analyze32BitPrimitiveAget(AnalyzedInstruction analyzedInstruction,
2265                                             RegisterType.Category instructionCategory) {
2266        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2267                RegisterType.getRegisterType(instructionCategory, null));
2268    }
2269
2270    private void verify32BitPrimitiveAget(AnalyzedInstruction analyzedInstruction,
2271                                             RegisterType.Category instructionCategory) {
2272        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2273
2274        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2275
2276        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2277        assert arrayRegisterType != null;
2278
2279        if (arrayRegisterType.category != RegisterType.Category.Null) {
2280            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2281                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
2282                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
2283            }
2284
2285            assert arrayRegisterType.type != null;
2286            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2287                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
2288                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
2289            }
2290
2291            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2292            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2293
2294            if (arrayClassDef.getArrayDimensions() != 1) {
2295                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
2296                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
2297            }
2298
2299            RegisterType arrayBaseType =
2300                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
2301            if (!checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
2302                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
2303                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2304                        arrayRegisterType.type.getClassType()));
2305            }
2306        }
2307    }
2308
2309    private void analyzeAgetWide(AnalyzedInstruction analyzedInstruction) {
2310        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2311
2312        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2313        assert arrayRegisterType != null;
2314
2315        if (arrayRegisterType.category != RegisterType.Category.Null) {
2316            assert arrayRegisterType.type != null;
2317            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2318                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
2319                        arrayRegisterType.type.getClassType()));
2320            }
2321
2322            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2323            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2324
2325            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
2326            if (arrayBaseType == 'J') {
2327                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2328                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
2329            } else if (arrayBaseType == 'D') {
2330                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2331                        RegisterType.getRegisterType(RegisterType.Category.DoubleLo, null));
2332            } else {
2333                throw new ValidationException(String.format("Cannot use aget-wide with array type %s. Incorrect " +
2334                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2335            }
2336        } else {
2337            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2338                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
2339        }
2340    }
2341
2342    private void verifyAgetWide(AnalyzedInstruction analyzedInstruction) {
2343        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2344
2345        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2346
2347        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2348        assert arrayRegisterType != null;
2349
2350        if (arrayRegisterType.category != RegisterType.Category.Null) {
2351            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2352                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
2353                        arrayRegisterType.category.toString()));
2354            }
2355
2356            assert arrayRegisterType.type != null;
2357            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2358                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
2359                        arrayRegisterType.type.getClassType()));
2360            }
2361
2362            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2363            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2364
2365            if (arrayClassDef.getArrayDimensions() != 1) {
2366                throw new ValidationException(String.format("Cannot use aget-wide with multi-dimensional array type %s",
2367                        arrayRegisterType.type.getClassType()));
2368            }
2369
2370            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
2371            if (arrayBaseType != 'J' && arrayBaseType != 'D') {
2372                throw new ValidationException(String.format("Cannot use aget-wide with array type %s. Incorrect " +
2373                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2374            }
2375        }
2376    }
2377
2378    private void analyzeAgetObject(AnalyzedInstruction analyzedInstruction) {
2379        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2380
2381        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2382        assert arrayRegisterType != null;
2383
2384        if (arrayRegisterType.category != RegisterType.Category.Null) {
2385            assert arrayRegisterType.type != null;
2386            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2387                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2388                        arrayRegisterType.type.getClassType()));
2389            }
2390
2391            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2392            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2393
2394            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
2395            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
2396            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
2397                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
2398                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2399            }
2400
2401            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2402                    RegisterType.getRegisterType(RegisterType.Category.Reference, elementClassDef));
2403        } else {
2404            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2405                    RegisterType.getRegisterType(RegisterType.Category.Null, null));
2406        }
2407    }
2408
2409    private void verifyAgetObject(AnalyzedInstruction analyzedInstruction) {
2410        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2411
2412        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2413
2414        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2415        assert arrayRegisterType != null;
2416
2417        if (arrayRegisterType.category != RegisterType.Category.Null) {
2418            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2419                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2420                        arrayRegisterType.category.toString()));
2421            }
2422
2423            assert arrayRegisterType.type != null;
2424            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2425                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2426                        arrayRegisterType.type.getClassType()));
2427            }
2428
2429            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2430            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2431
2432            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
2433            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
2434            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
2435                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
2436                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2437            }
2438        }
2439    }
2440
2441    private void verify32BitPrimitiveAput(AnalyzedInstruction analyzedInstruction,
2442                                             RegisterType.Category instructionCategory) {
2443        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2444
2445        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2446
2447        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2448        assert sourceRegisterType != null;
2449        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2450        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2451            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2452                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2453        }
2454
2455
2456        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2457        assert arrayRegisterType != null;
2458
2459        if (arrayRegisterType.category != RegisterType.Category.Null) {
2460            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2461                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
2462                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
2463            }
2464
2465            assert arrayRegisterType.type != null;
2466            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2467                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
2468                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
2469            }
2470
2471            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2472            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2473
2474            if (arrayClassDef.getArrayDimensions() != 1) {
2475                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
2476                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
2477            }
2478
2479            RegisterType arrayBaseType =
2480                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
2481            if (!checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
2482                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
2483                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2484                        arrayRegisterType.type.getClassType()));
2485            }
2486        }
2487    }
2488
2489    private void verifyAputWide(AnalyzedInstruction analyzedInstruction) {
2490        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2491
2492        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2493        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2494
2495        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2496        assert arrayRegisterType != null;
2497
2498        if (arrayRegisterType.category != RegisterType.Category.Null) {
2499            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2500                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
2501                        arrayRegisterType.category.toString()));
2502            }
2503
2504            assert arrayRegisterType.type != null;
2505            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2506                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
2507                        arrayRegisterType.type.getClassType()));
2508            }
2509
2510            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2511            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2512
2513            if (arrayClassDef.getArrayDimensions() != 1) {
2514                throw new ValidationException(String.format("Cannot use aput-wide with multi-dimensional array type %s",
2515                        arrayRegisterType.type.getClassType()));
2516            }
2517
2518            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
2519            if (arrayBaseType != 'J' && arrayBaseType != 'D') {
2520                throw new ValidationException(String.format("Cannot use aput-wide with array type %s. Incorrect " +
2521                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2522            }
2523        }
2524    }
2525
2526    private void verifyAputObject(AnalyzedInstruction analyzedInstruction) {
2527        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2528
2529        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2530
2531        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2532        assert sourceRegisterType != null;
2533
2534        //TODO: ensure sourceRegisterType is a Reference type?
2535
2536        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2537        assert arrayRegisterType != null;
2538
2539        if (arrayRegisterType.category != RegisterType.Category.Null) {
2540            //don't check the source type against the array type, just make sure it is an array of reference types
2541
2542            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2543                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2544                        arrayRegisterType.category.toString()));
2545            }
2546
2547            assert arrayRegisterType.type != null;
2548            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2549                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2550                        arrayRegisterType.type.getClassType()));
2551            }
2552
2553            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2554            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2555
2556            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
2557            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
2558            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
2559                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
2560                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2561            }
2562        }
2563    }
2564
2565    private void analyze32BitPrimitiveIget(AnalyzedInstruction analyzedInstruction,
2566                                             RegisterType.Category instructionCategory) {
2567        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2568                RegisterType.getRegisterType(instructionCategory, null));
2569    }
2570
2571    private void verify32BitPrimitiveIget(AnalyzedInstruction analyzedInstruction,
2572                                             RegisterType.Category instructionCategory) {
2573        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2574
2575        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2576                ReferenceOrUninitThisCategories);
2577
2578        //TODO: check access
2579        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2580        assert referencedItem instanceof FieldIdItem;
2581        FieldIdItem field = (FieldIdItem)referencedItem;
2582
2583        if (objectRegisterType.category != RegisterType.Category.Null &&
2584            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2585            throw new ValidationException(String.format("Cannot access field %s through type %s",
2586                    field.getFieldString(), objectRegisterType.type.getClassType()));
2587        }
2588
2589        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2590
2591        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2592                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2593                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2594                        field.getFieldString()));
2595        }
2596    }
2597
2598    private void analyzeIgetWideObject(AnalyzedInstruction analyzedInstruction) {
2599        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2600
2601        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2602        assert referencedItem instanceof FieldIdItem;
2603        FieldIdItem field = (FieldIdItem)referencedItem;
2604
2605        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2606        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2607    }
2608
2609    private void verifyIgetWide(AnalyzedInstruction analyzedInstruction) {
2610        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2611
2612        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2613                ReferenceOrUninitThisCategories);
2614
2615        //TODO: check access
2616        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2617        assert referencedItem instanceof FieldIdItem;
2618        FieldIdItem field = (FieldIdItem)referencedItem;
2619
2620        if (objectRegisterType.category != RegisterType.Category.Null &&
2621            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2622            throw new ValidationException(String.format("Cannot access field %s through type %s",
2623                    field.getFieldString(), objectRegisterType.type.getClassType()));
2624        }
2625
2626        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2627
2628        if (!WideLowCategories.contains(fieldType.category)) {
2629            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2630                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2631                    field.getFieldString()));
2632        }
2633    }
2634
2635    private void verifyIgetObject(AnalyzedInstruction analyzedInstruction) {
2636        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2637
2638        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2639                ReferenceOrUninitThisCategories);
2640
2641        //TODO: check access
2642        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2643        assert referencedItem instanceof FieldIdItem;
2644        FieldIdItem field = (FieldIdItem)referencedItem;
2645
2646        if (objectRegisterType.category != RegisterType.Category.Null &&
2647            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2648            throw new ValidationException(String.format("Cannot access field %s through type %s",
2649                    field.getFieldString(), objectRegisterType.type.getClassType()));
2650        }
2651
2652        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2653
2654        if (fieldType.category != RegisterType.Category.Reference) {
2655            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2656                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2657                        field.getFieldString()));
2658        }
2659    }
2660
2661    private void verify32BitPrimitiveIput(AnalyzedInstruction analyzedInstruction,
2662                                             RegisterType.Category instructionCategory) {
2663        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2664
2665        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2666                ReferenceOrUninitThisCategories);
2667
2668        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2669        assert sourceRegisterType != null;
2670
2671        //per CodeVerify.c in dalvik:
2672        //java generates synthetic functions that write byte values into boolean fields
2673        if (sourceRegisterType.category == RegisterType.Category.Byte &&
2674            instructionCategory == RegisterType.Category.Boolean) {
2675
2676            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
2677        }
2678
2679        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2680        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2681            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2682                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2683        }
2684
2685
2686        //TODO: check access
2687        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2688        assert referencedItem instanceof FieldIdItem;
2689        FieldIdItem field = (FieldIdItem)referencedItem;
2690
2691        if (objectRegisterType.category != RegisterType.Category.Null &&
2692            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2693            throw new ValidationException(String.format("Cannot access field %s through type %s",
2694                    field.getFieldString(), objectRegisterType.type.getClassType()));
2695        }
2696
2697        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2698
2699        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2700                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2701                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2702                        field.getFieldString()));
2703        }
2704    }
2705
2706    private void verifyIputWide(AnalyzedInstruction analyzedInstruction) {
2707        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2708
2709        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2710                ReferenceOrUninitThisCategories);
2711
2712        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2713
2714        //TODO: check access
2715        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2716        assert referencedItem instanceof FieldIdItem;
2717        FieldIdItem field = (FieldIdItem)referencedItem;
2718
2719        if (objectRegisterType.category != RegisterType.Category.Null &&
2720                !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2721            throw new ValidationException(String.format("Cannot access field %s through type %s",
2722                    field.getFieldString(), objectRegisterType.type.getClassType()));
2723        }
2724
2725        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2726
2727        if (!WideLowCategories.contains(fieldType.category)) {
2728            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2729                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2730                    field.getFieldString()));
2731        }
2732    }
2733
2734    private void verifyIputObject(AnalyzedInstruction analyzedInstruction) {
2735        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2736
2737        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2738                ReferenceOrUninitThisCategories);
2739
2740        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2741                ReferenceCategories);
2742
2743        //TODO: check access
2744        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2745        assert referencedItem instanceof FieldIdItem;
2746        FieldIdItem field = (FieldIdItem)referencedItem;
2747
2748        if (objectRegisterType.category != RegisterType.Category.Null &&
2749            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2750            throw new ValidationException(String.format("Cannot access field %s through type %s",
2751                    field.getFieldString(), objectRegisterType.type.getClassType()));
2752        }
2753
2754        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2755
2756        if (fieldType.category != RegisterType.Category.Reference) {
2757            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2758                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2759                        field.getFieldString()));
2760        }
2761
2762        if (sourceRegisterType.category != RegisterType.Category.Null &&
2763            !fieldType.type.isInterface() &&
2764            !sourceRegisterType.type.extendsClass(fieldType.type)) {
2765
2766            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
2767                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
2768        }
2769    }
2770
2771    private void analyze32BitPrimitiveSget(AnalyzedInstruction analyzedInstruction,
2772                                             RegisterType.Category instructionCategory) {
2773        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2774                RegisterType.getRegisterType(instructionCategory, null));
2775    }
2776
2777    private void verify32BitPrimitiveSget(AnalyzedInstruction analyzedInstruction,
2778                                             RegisterType.Category instructionCategory) {
2779        //TODO: check access
2780        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2781        assert referencedItem instanceof FieldIdItem;
2782        FieldIdItem field = (FieldIdItem)referencedItem;
2783
2784        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2785
2786        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2787                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2788                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2789                        field.getFieldString()));
2790        }
2791    }
2792
2793    private void analyzeSgetWideObject(AnalyzedInstruction analyzedInstruction) {
2794        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2795        assert referencedItem instanceof FieldIdItem;
2796        FieldIdItem field = (FieldIdItem)referencedItem;
2797
2798        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2799        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2800    }
2801
2802    private void verifySgetWide(AnalyzedInstruction analyzedInstruction) {
2803        //TODO: check access
2804        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2805        assert referencedItem instanceof FieldIdItem;
2806        FieldIdItem field = (FieldIdItem)referencedItem;
2807
2808        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2809
2810
2811        if (fieldType.category != RegisterType.Category.LongLo &&
2812            fieldType.category != RegisterType.Category.DoubleLo) {
2813
2814            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2815                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2816                    field.getFieldString()));
2817        }
2818    }
2819
2820    private void verifySgetObject(AnalyzedInstruction analyzedInstruction) {
2821        //TODO: check access
2822        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2823        assert referencedItem instanceof FieldIdItem;
2824        FieldIdItem field = (FieldIdItem)referencedItem;
2825
2826        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2827
2828        if (fieldType.category != RegisterType.Category.Reference) {
2829                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2830                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2831                        field.getFieldString()));
2832        }
2833    }
2834
2835    private void verify32BitPrimitiveSput(AnalyzedInstruction analyzedInstruction,
2836                                             RegisterType.Category instructionCategory) {
2837        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2838
2839        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2840        assert sourceRegisterType != null;
2841
2842        //per CodeVerify.c in dalvik:
2843        //java generates synthetic functions that write byte values into boolean fields
2844        if (sourceRegisterType.category == RegisterType.Category.Byte &&
2845            instructionCategory == RegisterType.Category.Boolean) {
2846
2847            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
2848        }
2849
2850        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2851        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2852            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2853                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2854        }
2855
2856        //TODO: check access
2857        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2858        assert referencedItem instanceof FieldIdItem;
2859        FieldIdItem field = (FieldIdItem)referencedItem;
2860
2861        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2862
2863        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2864                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2865                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2866                        field.getFieldString()));
2867        }
2868    }
2869
2870    private void verifySputWide(AnalyzedInstruction analyzedInstruction) {
2871        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2872
2873
2874        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2875
2876        //TODO: check access
2877        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2878        assert referencedItem instanceof FieldIdItem;
2879        FieldIdItem field = (FieldIdItem)referencedItem;
2880
2881        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2882
2883        if (!WideLowCategories.contains(fieldType.category)) {
2884                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2885                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2886                        field.getFieldString()));
2887        }
2888    }
2889
2890    private void verifySputObject(AnalyzedInstruction analyzedInstruction) {
2891        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2892
2893        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2894                ReferenceCategories);
2895
2896        //TODO: check access
2897        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2898        assert referencedItem instanceof FieldIdItem;
2899        FieldIdItem field = (FieldIdItem)referencedItem;
2900
2901        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2902
2903        if (fieldType.category != RegisterType.Category.Reference) {
2904            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2905                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2906                        field.getFieldString()));
2907        }
2908
2909        if (sourceRegisterType.category != RegisterType.Category.Null &&
2910            !fieldType.type.isInterface() &&
2911            !sourceRegisterType.type.extendsClass(fieldType.type)) {
2912
2913            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
2914                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
2915        }
2916    }
2917
2918    private void analyzeInvokeDirect(AnalyzedInstruction analyzedInstruction) {
2919        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
2920        analyzeInvokeDirectCommon(analyzedInstruction, new Format35cRegisterIterator(instruction));
2921    }
2922
2923    private void verifyInvoke(AnalyzedInstruction analyzedInstruction, int invokeType) {
2924        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
2925        verifyInvokeCommon(analyzedInstruction, false, invokeType, new Format35cRegisterIterator(instruction));
2926    }
2927
2928    private void analyzeInvokeDirectRange(AnalyzedInstruction analyzedInstruction) {
2929        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
2930        analyzeInvokeDirectCommon(analyzedInstruction, new Format3rcRegisterIterator(instruction));
2931    }
2932
2933    private void verifyInvokeRange(AnalyzedInstruction analyzedInstruction, int invokeType) {
2934        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
2935        verifyInvokeCommon(analyzedInstruction, true, invokeType, new Format3rcRegisterIterator(instruction));
2936    }
2937
2938    private static final int INVOKE_VIRTUAL = 0x01;
2939    private static final int INVOKE_SUPER = 0x02;
2940    private static final int INVOKE_DIRECT = 0x04;
2941    private static final int INVOKE_INTERFACE = 0x08;
2942    private static final int INVOKE_STATIC = 0x10;
2943
2944    private void analyzeInvokeDirectCommon(AnalyzedInstruction analyzedInstruction, RegisterIterator registers) {
2945        //the only time that an invoke instruction changes a register type is when using invoke-direct on a
2946        //constructor (<init>) method, which changes the uninitialized reference (and any register that the same
2947        //uninit reference has been copied to) to an initialized reference
2948
2949        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2950
2951        Item item = instruction.getReferencedItem();
2952        assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM;
2953        MethodIdItem methodIdItem = (MethodIdItem)item;
2954
2955        if (!methodIdItem.getMethodName().getStringValue().equals("<init>")) {
2956            return;
2957        }
2958
2959        RegisterType objectRegisterType;
2960        //the object register is always the first register
2961        int objectRegister = registers.getRegister();
2962
2963        objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister);
2964        assert objectRegisterType != null;
2965
2966        if (objectRegisterType.category != RegisterType.Category.UninitRef &&
2967                objectRegisterType.category != RegisterType.Category.UninitThis) {
2968            return;
2969        }
2970
2971        setPostRegisterTypeAndPropagateChanges(analyzedInstruction, objectRegister,
2972                RegisterType.getRegisterType(RegisterType.Category.Reference, objectRegisterType.type));
2973
2974        for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
2975            RegisterType postInstructionRegisterType = analyzedInstruction.postRegisterMap[i];
2976            if (postInstructionRegisterType.category == RegisterType.Category.Unknown) {
2977                RegisterType preInstructionRegisterType =
2978                        analyzedInstruction.getPreInstructionRegisterType(i);
2979
2980                if (preInstructionRegisterType.category == RegisterType.Category.UninitRef ||
2981                    preInstructionRegisterType.category == RegisterType.Category.UninitThis) {
2982
2983                    RegisterType registerType;
2984                    if (preInstructionRegisterType == objectRegisterType) {
2985                        registerType = analyzedInstruction.postRegisterMap[objectRegister];
2986                    } else {
2987                        registerType = preInstructionRegisterType;
2988                    }
2989
2990                    setPostRegisterTypeAndPropagateChanges(analyzedInstruction, i, registerType);
2991                }
2992            }
2993        }
2994    }
2995
2996    private void verifyInvokeCommon(AnalyzedInstruction analyzedInstruction, boolean isRange, int invokeType,
2997                                       RegisterIterator registers) {
2998        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2999
3000        //TODO: check access
3001
3002        Item item = instruction.getReferencedItem();
3003        assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM;
3004        MethodIdItem methodIdItem = (MethodIdItem)item;
3005
3006        TypeIdItem methodClass = methodIdItem.getContainingClass();
3007        boolean isInit = false;
3008
3009        if (methodIdItem.getMethodName().getStringValue().charAt(0) == '<') {
3010            if ((invokeType & INVOKE_DIRECT) != 0) {
3011                isInit = true;
3012            } else {
3013                throw new ValidationException(String.format("Cannot call constructor %s with %s",
3014                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name));
3015            }
3016        }
3017
3018        ClassPath.ClassDef methodClassDef = ClassPath.getClassDef(methodClass);
3019        if ((invokeType & INVOKE_INTERFACE) != 0) {
3020            if (!methodClassDef.isInterface()) {
3021                throw new ValidationException(String.format("Cannot call method %s with %s. %s is not an interface " +
3022                        "class.", methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
3023                        methodClassDef.getClassType()));
3024            }
3025        } else {
3026            if (methodClassDef.isInterface()) {
3027                throw new ValidationException(String.format("Cannot call method %s with %s. %s is an interface class." +
3028                        " Use invoke-interface or invoke-interface/range instead.", methodIdItem.getMethodString(),
3029                        analyzedInstruction.instruction.opcode.name, methodClassDef.getClassType()));
3030            }
3031        }
3032
3033        if ((invokeType & INVOKE_SUPER) != 0) {
3034            ClassPath.ClassDef currentMethodClassDef = ClassPath.getClassDef(encodedMethod.method.getContainingClass());
3035            if (currentMethodClassDef.getSuperclass() == null) {
3036                throw new ValidationException(String.format("Cannot call method %s with %s. %s has no superclass",
3037                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
3038                        methodClassDef.getSuperclass().getClassType()));
3039            }
3040
3041            if (!currentMethodClassDef.getSuperclass().extendsClass(methodClassDef)) {
3042                throw new ValidationException(String.format("Cannot call method %s with %s. %s is not an ancestor " +
3043                        "of the current class %s", methodIdItem.getMethodString(),
3044                        analyzedInstruction.instruction.opcode.name, methodClass.getTypeDescriptor(),
3045                        encodedMethod.method.getContainingClass().getTypeDescriptor()));
3046            }
3047
3048            if (!currentMethodClassDef.getSuperclass().hasVirtualMethod(methodIdItem.getVirtualMethodString())) {
3049                throw new ValidationException(String.format("Cannot call method %s with %s. The superclass %s has" +
3050                        "no such method", methodIdItem.getMethodString(),
3051                        analyzedInstruction.instruction.opcode.name, methodClassDef.getSuperclass().getClassType()));
3052            }
3053        }
3054
3055        assert isRange || registers.getCount() <= 5;
3056
3057        TypeListItem typeListItem = methodIdItem.getPrototype().getParameters();
3058        int methodParameterRegisterCount;
3059        if (typeListItem == null) {
3060            methodParameterRegisterCount = 0;
3061        } else {
3062            methodParameterRegisterCount = typeListItem.getRegisterCount();
3063        }
3064
3065        if ((invokeType & INVOKE_STATIC) == 0) {
3066            methodParameterRegisterCount++;
3067        }
3068
3069        if (methodParameterRegisterCount != registers.getCount()) {
3070            throw new ValidationException(String.format("The number of registers does not match the number of " +
3071                    "parameters for method %s. Expecting %d registers, got %d.", methodIdItem.getMethodString(),
3072                    methodParameterRegisterCount + 1, registers.getCount()));
3073        }
3074
3075        RegisterType objectRegisterType = null;
3076        int objectRegister = 0;
3077        if ((invokeType & INVOKE_STATIC) == 0) {
3078            objectRegister = registers.getRegister();
3079            registers.moveNext();
3080
3081            objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister);
3082            assert objectRegisterType != null;
3083            if (objectRegisterType.category == RegisterType.Category.UninitRef ||
3084                    objectRegisterType.category == RegisterType.Category.UninitThis) {
3085
3086                if (!isInit) {
3087                    throw new ValidationException(String.format("Cannot invoke non-<init> method %s on uninitialized " +
3088                            "reference type %s", methodIdItem.getMethodString(),
3089                            objectRegisterType.type.getClassType()));
3090                }
3091            } else if (objectRegisterType.category == RegisterType.Category.Reference) {
3092                if (isInit) {
3093                    throw new ValidationException(String.format("Cannot invoke %s on initialized reference type %s",
3094                            methodIdItem.getMethodString(), objectRegisterType.type.getClassType()));
3095                }
3096            } else if (objectRegisterType.category == RegisterType.Category.Null) {
3097                if (isInit) {
3098                    throw new ValidationException(String.format("Cannot invoke %s on a null reference",
3099                            methodIdItem.getMethodString()));
3100                }
3101            }
3102            else {
3103                throw new ValidationException(String.format("Cannot invoke %s on non-reference type %s",
3104                        methodIdItem.getMethodString(), objectRegisterType.toString()));
3105            }
3106
3107            if (isInit) {
3108                if (objectRegisterType.type.getSuperclass() == methodClassDef) {
3109                    if (!encodedMethod.method.getMethodName().getStringValue().equals("<init>")) {
3110                        throw new ValidationException(String.format("Cannot call %s on type %s. The object type must " +
3111                                "match the method type exactly", methodIdItem.getMethodString(),
3112                                objectRegisterType.type.getClassType()));
3113                    }
3114                }
3115            }
3116
3117            if ((invokeType & INVOKE_INTERFACE) == 0 && objectRegisterType.category != RegisterType.Category.Null &&
3118                    !objectRegisterType.type.extendsClass(methodClassDef)) {
3119
3120               throw new ValidationException(String.format("Cannot call method %s on an object of type %s, which " +
3121                       "does not extend %s.", methodIdItem.getMethodString(), objectRegisterType.type.getClassType(),
3122                        methodClassDef.getClassType()));
3123            }
3124        }
3125
3126        if (typeListItem != null) {
3127            List<TypeIdItem> parameterTypes = typeListItem.getTypes();
3128            int parameterTypeIndex = 0;
3129            while (!registers.pastEnd()) {
3130                assert parameterTypeIndex < parameterTypes.size();
3131                RegisterType parameterType =
3132                        RegisterType.getRegisterTypeForTypeIdItem(parameterTypes.get(parameterTypeIndex));
3133
3134                int register = registers.getRegister();
3135
3136                RegisterType parameterRegisterType;
3137                if (WideLowCategories.contains(parameterType.category)) {
3138                    parameterRegisterType = getAndCheckSourceRegister(analyzedInstruction, register, WideLowCategories);
3139
3140                    if (!registers.moveNext()) {
3141                        throw new ValidationException(String.format("No 2nd register specified for wide register pair v%d",
3142                                parameterTypeIndex+1));
3143                    }
3144                    int nextRegister = registers.getRegister();
3145
3146                    if (nextRegister != register + 1) {
3147                        throw new ValidationException(String.format("Invalid wide register pair (v%d, v%d). Registers " +
3148                                "must be consecutive.", register, nextRegister));
3149                    }
3150                } else {
3151                    parameterRegisterType = analyzedInstruction.getPreInstructionRegisterType(register);
3152                }
3153
3154                assert parameterRegisterType != null;
3155
3156                if (!parameterRegisterType.canBeAssignedTo(parameterType)) {
3157                    throw new ValidationException(
3158                            String.format("Invalid register type %s for parameter %d %s.",
3159                                    parameterRegisterType.toString(), parameterTypeIndex+1,
3160                                    parameterType.toString()));
3161                }
3162
3163                parameterTypeIndex++;
3164                registers.moveNext();
3165            }
3166        }
3167    }
3168
3169    private void analyzeUnaryOp(AnalyzedInstruction analyzedInstruction, RegisterType.Category destRegisterCategory) {
3170        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
3171                RegisterType.getRegisterType(destRegisterCategory, null));
3172    }
3173
3174    private void verifyUnaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSourceCategories) {
3175        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3176
3177        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validSourceCategories);
3178    }
3179
3180    private void analyzeBinaryOp(AnalyzedInstruction analyzedInstruction, RegisterType.Category destRegisterCategory,
3181                                boolean checkForBoolean) {
3182        if (checkForBoolean) {
3183            ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
3184
3185            RegisterType source1RegisterType =
3186                    analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
3187            RegisterType source2RegisterType =
3188                    analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterC());
3189
3190            if (BooleanCategories.contains(source1RegisterType.category) &&
3191                BooleanCategories.contains(source2RegisterType.category)) {
3192
3193                destRegisterCategory = RegisterType.Category.Boolean;
3194            }
3195        }
3196
3197        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
3198                RegisterType.getRegisterType(destRegisterCategory, null));
3199    }
3200
3201    private void verifyBinaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
3202                                EnumSet validSource2Categories) {
3203        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
3204
3205        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validSource1Categories);
3206        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), validSource2Categories);
3207    }
3208
3209    private void analyzeBinary2AddrOp(AnalyzedInstruction analyzedInstruction,
3210                                      RegisterType.Category destRegisterCategory, boolean checkForBoolean) {
3211        if (checkForBoolean) {
3212            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3213
3214            RegisterType source1RegisterType =
3215                    analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
3216            RegisterType source2RegisterType =
3217                    analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
3218
3219            if (BooleanCategories.contains(source1RegisterType.category) &&
3220                BooleanCategories.contains(source2RegisterType.category)) {
3221
3222                destRegisterCategory = RegisterType.Category.Boolean;
3223            }
3224        }
3225
3226        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
3227                RegisterType.getRegisterType(destRegisterCategory, null));
3228    }
3229
3230    private void verifyBinary2AddrOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
3231                                EnumSet validSource2Categories) {
3232        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3233
3234        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), validSource1Categories);
3235        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validSource2Categories);
3236    }
3237
3238    private void analyzeLiteralBinaryOp(AnalyzedInstruction analyzedInstruction,
3239                                        RegisterType.Category destRegisterCategory, boolean checkForBoolean) {
3240        if (checkForBoolean) {
3241            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3242
3243            RegisterType sourceRegisterType =
3244                    analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
3245
3246            if (BooleanCategories.contains(sourceRegisterType.category)) {
3247                long literal = ((LiteralInstruction)analyzedInstruction.instruction).getLiteral();
3248                if (literal == 0 || literal == 1) {
3249                    destRegisterCategory = RegisterType.Category.Boolean;
3250                }
3251            }
3252        }
3253
3254        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
3255                RegisterType.getRegisterType(destRegisterCategory, null));
3256    }
3257
3258    private void verifyLiteralBinaryOp(AnalyzedInstruction analyzedInstruction) {
3259        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3260
3261        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
3262    }
3263
3264    private RegisterType.Category getDestTypeForLiteralShiftRight(AnalyzedInstruction analyzedInstruction,
3265                                                                  boolean signedShift) {
3266        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3267
3268        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
3269                Primitive32BitCategories);
3270        long literalShift = ((LiteralInstruction)analyzedInstruction.instruction).getLiteral();
3271
3272        if (literalShift == 0) {
3273            return sourceRegisterType.category;
3274        }
3275
3276        RegisterType.Category destRegisterCategory;
3277        if (!signedShift) {
3278            destRegisterCategory = RegisterType.Category.Integer;
3279        } else {
3280            destRegisterCategory = sourceRegisterType.category;
3281        }
3282
3283        if (literalShift >= 32) {
3284            //TODO: add warning
3285            return destRegisterCategory;
3286        }
3287
3288        switch (sourceRegisterType.category) {
3289            case Integer:
3290            case Float:
3291                if (!signedShift) {
3292                    if (literalShift > 24) {
3293                        return RegisterType.Category.PosByte;
3294                    }
3295                    if (literalShift >= 16) {
3296                        return RegisterType.Category.Char;
3297                    }
3298                } else {
3299                    if (literalShift >= 24) {
3300                        return RegisterType.Category.Byte;
3301                    }
3302                    if (literalShift >= 16) {
3303                        return RegisterType.Category.Short;
3304                    }
3305                }
3306                break;
3307            case Short:
3308                if (signedShift && literalShift >= 8) {
3309                    return RegisterType.Category.Byte;
3310                }
3311                break;
3312            case PosShort:
3313                if (literalShift >= 8) {
3314                    return RegisterType.Category.PosByte;
3315                }
3316                break;
3317            case Char:
3318                if (literalShift > 8) {
3319                    return RegisterType.Category.PosByte;
3320                }
3321                break;
3322            case Byte:
3323                break;
3324            case PosByte:
3325                return RegisterType.Category.PosByte;
3326            case Null:
3327            case One:
3328            case Boolean:
3329                return RegisterType.Category.Null;
3330            default:
3331                assert false;
3332        }
3333
3334        return destRegisterCategory;
3335    }
3336
3337
3338    private void analyzeExecuteInline(AnalyzedInstruction analyzedInstruction) {
3339        if (deodexUtil == null) {
3340            throw new ValidationException("Cannot analyze an odexed instruction unless we are deodexing");
3341        }
3342
3343        Instruction35mi instruction = (Instruction35mi)analyzedInstruction.instruction;
3344
3345        DeodexUtil.InlineMethod inlineMethod = deodexUtil.lookupInlineMethod(analyzedInstruction);
3346        MethodIdItem inlineMethodIdItem = inlineMethod.getMethodIdItem();
3347        if (inlineMethodIdItem == null) {
3348            throw new ValidationException(String.format("Cannot load inline method with index %d",
3349                    instruction.getInlineIndex()));
3350        }
3351
3352        Opcode deodexedOpcode = null;
3353        switch (inlineMethod.methodType) {
3354            case DeodexUtil.Direct:
3355                deodexedOpcode = Opcode.INVOKE_DIRECT;
3356                break;
3357            case DeodexUtil.Static:
3358                deodexedOpcode = Opcode.INVOKE_STATIC;
3359                break;
3360            case DeodexUtil.Virtual:
3361                deodexedOpcode = Opcode.INVOKE_VIRTUAL;
3362                break;
3363            default:
3364                assert false;
3365        }
3366
3367        Instruction35c deodexedInstruction = new Instruction35c(deodexedOpcode, instruction.getRegCount(),
3368                instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
3369                instruction.getRegisterG(), instruction.getRegisterA(), inlineMethodIdItem);
3370
3371        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3372
3373        analyzeInstruction(analyzedInstruction);
3374    }
3375
3376    private void analyzeExecuteInlineRange(AnalyzedInstruction analyzedInstruction) {
3377        if (deodexUtil == null) {
3378            throw new ValidationException("Cannot analyze an odexed instruction unless we are deodexing");
3379        }
3380
3381        Instruction3rmi instruction = (Instruction3rmi)analyzedInstruction.instruction;
3382
3383        DeodexUtil.InlineMethod inlineMethod = deodexUtil.lookupInlineMethod(analyzedInstruction);
3384        MethodIdItem inlineMethodIdItem = inlineMethod.getMethodIdItem();
3385        if (inlineMethodIdItem == null) {
3386            throw new ValidationException(String.format("Cannot load inline method with index %d",
3387                    instruction.getInlineIndex()));
3388        }
3389
3390        Opcode deodexedOpcode = null;
3391        switch (inlineMethod.methodType) {
3392            case DeodexUtil.Direct:
3393                deodexedOpcode = Opcode.INVOKE_DIRECT_RANGE;
3394                break;
3395            case DeodexUtil.Static:
3396                deodexedOpcode = Opcode.INVOKE_STATIC_RANGE;
3397                break;
3398            case DeodexUtil.Virtual:
3399                deodexedOpcode = Opcode.INVOKE_VIRTUAL_RANGE;
3400                break;
3401            default:
3402                assert false;
3403        }
3404
3405        Instruction3rc deodexedInstruction = new Instruction3rc(deodexedOpcode, instruction.getRegCount(),
3406                instruction.getStartRegister(), inlineMethodIdItem);
3407
3408        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3409
3410        analyzeInstruction(analyzedInstruction);
3411    }
3412
3413    private void analyzeInvokeDirectEmpty(AnalyzedInstruction analyzedInstruction) {
3414        Instruction35s instruction = (Instruction35s)analyzedInstruction.instruction;
3415
3416        Instruction35c deodexedInstruction = new Instruction35c(Opcode.INVOKE_DIRECT, instruction.getRegCount(),
3417                instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
3418                instruction.getRegisterG(), instruction.getRegisterA(), instruction.getReferencedItem());
3419
3420        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3421
3422        analyzeInstruction(analyzedInstruction);
3423    }
3424
3425    private boolean analyzeIputIgetQuick(AnalyzedInstruction analyzedInstruction) {
3426        Instruction22cs instruction = (Instruction22cs)analyzedInstruction.instruction;
3427
3428        int fieldOffset = instruction.getFieldOffset();
3429        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
3430                ReferenceOrUninitCategories);
3431
3432        if (objectRegisterType.category == RegisterType.Category.Null) {
3433            return false;
3434        }
3435
3436        FieldIdItem fieldIdItem = deodexUtil.lookupField(objectRegisterType.type, fieldOffset);
3437        if (fieldIdItem == null) {
3438            throw new ValidationException(String.format("Could not resolve the field in class %s at offset %d",
3439                    objectRegisterType.type.getClassType(), fieldOffset));
3440        }
3441
3442        String fieldType = fieldIdItem.getFieldType().getTypeDescriptor();
3443
3444        Opcode opcode = OdexedFieldInstructionMapper.getAndCheckDeodexedOpcodeForOdexedOpcode(fieldType, instruction.opcode);
3445
3446        Instruction22c deodexedInstruction = new Instruction22c(opcode, (byte)instruction.getRegisterA(),
3447                (byte)instruction.getRegisterB(), fieldIdItem);
3448        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3449
3450        analyzeInstruction(analyzedInstruction);
3451
3452        return true;
3453    }
3454
3455    private boolean analyzeInvokeVirtualQuick(AnalyzedInstruction analyzedInstruction, boolean isSuper,
3456                                              boolean isRange) {
3457        int methodIndex;
3458        int objectRegister;
3459
3460
3461        if (isRange) {
3462            Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
3463            methodIndex = instruction.getVtableIndex();
3464            objectRegister = instruction.getStartRegister();
3465        } else {
3466            Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
3467            methodIndex = instruction.getVtableIndex();
3468            objectRegister = instruction.getRegisterD();
3469        }
3470
3471        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, objectRegister,
3472                ReferenceOrUninitCategories);
3473
3474        if (objectRegisterType.category == RegisterType.Category.Null) {
3475            return false;
3476        }
3477
3478        MethodIdItem methodIdItem = null;
3479        if (isSuper) {
3480            ClassPath.ClassDef classDef = ClassPath.getClassDef(this.encodedMethod.method.getContainingClass(), false);
3481            assert classDef != null;
3482
3483            if (classDef.getSuperclass() != null) {
3484                methodIdItem = deodexUtil.lookupVirtualMethod(classDef.getSuperclass(), methodIndex);
3485            }
3486
3487            if (methodIdItem == null) {
3488                //it's possible that the pre-odexed instruction had used the method from the current class instead
3489                //of from the superclass (although the superclass method is still what would actually be called).
3490                //And so the MethodIdItem for the superclass method may not be in the dex file. Let's try to get the
3491                //MethodIdItem for the method in the current class instead
3492                methodIdItem = deodexUtil.lookupVirtualMethod(classDef, methodIndex);
3493            }
3494        } else{
3495            methodIdItem = deodexUtil.lookupVirtualMethod(objectRegisterType.type, methodIndex);
3496        }
3497
3498        if (methodIdItem == null) {
3499            throw new ValidationException(String.format("Could not resolve the method in class %s at index %d",
3500                    objectRegisterType.type.getClassType(), methodIndex));
3501        }
3502
3503
3504        Instruction deodexedInstruction;
3505        if (isRange) {
3506            Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
3507            Opcode opcode;
3508            if (isSuper) {
3509                opcode = Opcode.INVOKE_SUPER_RANGE;
3510            } else {
3511                opcode = Opcode.INVOKE_VIRTUAL_RANGE;
3512            }
3513
3514            deodexedInstruction = new Instruction3rc(opcode, instruction.getRegCount(),
3515                    instruction.getStartRegister(), methodIdItem);
3516        } else {
3517            Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
3518            Opcode opcode;
3519            if (isSuper) {
3520                opcode = Opcode.INVOKE_SUPER;
3521            } else {
3522                opcode = Opcode.INVOKE_VIRTUAL;
3523            }
3524
3525            deodexedInstruction = new Instruction35c(opcode, instruction.getRegCount(),
3526                    instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
3527                    instruction.getRegisterG(), instruction.getRegisterA(), methodIdItem);
3528        }
3529
3530        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3531        analyzeInstruction(analyzedInstruction);
3532
3533        return true;
3534    }
3535
3536    private boolean analyzePutGetVolatile(AnalyzedInstruction analyzedInstruction) {
3537        FieldIdItem fieldIdItem =
3538                (FieldIdItem)(((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem());
3539
3540        String fieldType = fieldIdItem.getFieldType().getTypeDescriptor();
3541
3542        Opcode opcode = OdexedFieldInstructionMapper.getAndCheckDeodexedOpcodeForOdexedOpcode(fieldType,
3543                analyzedInstruction.instruction.opcode);
3544
3545        Instruction deodexedInstruction;
3546
3547        if (analyzedInstruction.instruction.opcode.isOdexedStaticVolatile()) {
3548            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
3549
3550            deodexedInstruction = new Instruction21c(opcode, (byte)instruction.getRegisterA(),
3551                fieldIdItem);
3552        } else {
3553            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
3554
3555            deodexedInstruction = new Instruction22c(opcode, (byte)instruction.getRegisterA(),
3556                (byte)instruction.getRegisterB(), fieldIdItem);
3557        }
3558
3559        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
3560        analyzeInstruction(analyzedInstruction);
3561
3562        return true;
3563    }
3564
3565    private static boolean checkArrayFieldAssignment(RegisterType.Category arrayFieldCategory,
3566                                                  RegisterType.Category instructionCategory) {
3567        if (arrayFieldCategory == instructionCategory) {
3568            return true;
3569        }
3570
3571        if ((arrayFieldCategory == RegisterType.Category.Integer &&
3572             instructionCategory == RegisterType.Category.Float) ||
3573            (arrayFieldCategory == RegisterType.Category.Float &&
3574             instructionCategory == RegisterType.Category.Integer)) {
3575            return true;
3576        }
3577        return false;
3578    }
3579
3580    private static RegisterType getAndCheckSourceRegister(AnalyzedInstruction analyzedInstruction, int registerNumber,
3581                                            EnumSet validCategories) {
3582        assert registerNumber >= 0 && registerNumber < analyzedInstruction.postRegisterMap.length;
3583
3584        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(registerNumber);
3585        assert registerType != null;
3586
3587        checkRegister(registerType, registerNumber, validCategories);
3588
3589        if (validCategories == WideLowCategories) {
3590            checkRegister(registerType, registerNumber, WideLowCategories);
3591            checkWidePair(registerNumber, analyzedInstruction);
3592
3593            RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(registerNumber + 1);
3594            assert secondRegisterType != null;
3595            checkRegister(secondRegisterType, registerNumber+1, WideHighCategories);
3596        }
3597
3598        return registerType;
3599    }
3600
3601    private static void checkRegister(RegisterType registerType, int registerNumber, EnumSet validCategories) {
3602        if (!validCategories.contains(registerType.category)) {
3603            throw new ValidationException(String.format("Invalid register type %s for register v%d.",
3604                    registerType.toString(), registerNumber));
3605        }
3606    }
3607
3608    private static void checkWidePair(int registerNumber, AnalyzedInstruction analyzedInstruction) {
3609        if (registerNumber + 1 >= analyzedInstruction.postRegisterMap.length) {
3610            throw new ValidationException(String.format("v%d cannot be used as the first register in a wide register" +
3611                    "pair because it is the last register.", registerNumber));
3612        }
3613    }
3614
3615    private static interface RegisterIterator {
3616        int getRegister();
3617        boolean moveNext();
3618        int getCount();
3619        boolean pastEnd();
3620    }
3621
3622    private static class Format35cRegisterIterator implements RegisterIterator {
3623        private final int registerCount;
3624        private final int[] registers;
3625        private int currentRegister = 0;
3626
3627        public Format35cRegisterIterator(FiveRegisterInstruction instruction) {
3628            registerCount = instruction.getRegCount();
3629            registers = new int[]{instruction.getRegisterD(), instruction.getRegisterE(),
3630                                  instruction.getRegisterF(), instruction.getRegisterG(),
3631                                  instruction.getRegisterA()};
3632        }
3633
3634        public int getRegister() {
3635            return registers[currentRegister];
3636        }
3637
3638        public boolean moveNext() {
3639            currentRegister++;
3640            return !pastEnd();
3641        }
3642
3643        public int getCount() {
3644            return registerCount;
3645        }
3646
3647        public boolean pastEnd() {
3648            return currentRegister >= registerCount;
3649        }
3650    }
3651
3652    private static class Format3rcRegisterIterator implements RegisterIterator {
3653        private final int startRegister;
3654        private final int registerCount;
3655        private int currentRegister = 0;
3656
3657        public Format3rcRegisterIterator(RegisterRangeInstruction instruction) {
3658            startRegister = instruction.getStartRegister();
3659            registerCount = instruction.getRegCount();
3660        }
3661
3662        public int getRegister() {
3663            return startRegister + currentRegister;
3664        }
3665
3666        public boolean moveNext() {
3667            currentRegister++;
3668            return !pastEnd();
3669        }
3670
3671        public int getCount() {
3672            return registerCount;
3673        }
3674
3675        public boolean pastEnd() {
3676            return currentRegister >= registerCount;
3677        }
3678    }
3679}
3680