MethodAnalyzer.java revision 00fc68adf2e39aeb9fed35293f2576bbe729ec4b 
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.*;
35
36
37import java.util.*;
38
39public class MethodAnalyzer {
40    private final ClassDataItem.EncodedMethod encodedMethod;
41
42    private final DeodexUtil deodexUtil;
43
44    private SparseArray<AnalyzedInstruction> instructions;
45
46    private boolean analyzed = false;
47
48    private BitSet verifiedInstructions;
49
50    private ValidationException validationException = null;
51
52    //This is a dummy instruction that occurs immediately before the first real instruction. We can initialize the
53    //register types for this instruction to the parameter types, in order to have them propagate to all of its
54    //successors, e.g. the first real instruction, the first instructions in any exception handlers covering the first
55    //instruction, etc.
56    private AnalyzedInstruction startOfMethod;
57
58    public MethodAnalyzer(ClassDataItem.EncodedMethod encodedMethod, boolean deodex) {
59        if (encodedMethod == null) {
60            throw new IllegalArgumentException("encodedMethod cannot be null");
61        }
62        if (encodedMethod.codeItem == null || encodedMethod.codeItem.getInstructions().length == 0) {
63            throw new IllegalArgumentException("The method has no code");
64        }
65        this.encodedMethod = encodedMethod;
66
67        if (deodex) {
68            this.deodexUtil = new DeodexUtil(encodedMethod.method.getDexFile());
69        } else {
70            this.deodexUtil = null;
71        }
72
73        //override AnalyzedInstruction and provide custom implementations of some of the methods, so that we don't
74        //have to handle the case this special case of instruction being null, in the main class
75        startOfMethod = new AnalyzedInstruction(null, -1, encodedMethod.codeItem.getRegisterCount()) {
76            public boolean setsRegister() {
77                return false;
78            }
79
80            @Override
81            public boolean setsWideRegister() {
82                return false;
83            }
84
85            @Override
86            public boolean setsRegister(int registerNumber) {
87                return false;
88            }
89
90            @Override
91            public int getDestinationRegister() {
92                assert false;
93                return -1;
94            };
95        };
96
97        buildInstructionList();
98
99        verifiedInstructions = new BitSet(instructions.size());
100    }
101
102    public AnalyzedInstruction[] analyze() {
103        assert encodedMethod != null;
104        assert encodedMethod.codeItem != null;
105
106        if (analyzed) {
107            return makeInstructionArray();
108        }
109
110        CodeItem codeItem = encodedMethod.codeItem;
111        MethodIdItem methodIdItem = encodedMethod.method;
112
113        int totalRegisters = codeItem.getRegisterCount();
114        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
115
116        int nonParameterRegisters = totalRegisters - parameterRegisters;
117
118        //if this isn't a static method, determine which register is the "this" register and set the type to the
119        //current class
120        if ((encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0) {
121            nonParameterRegisters--;
122            int thisRegister = totalRegisters - parameterRegisters - 1;
123
124            //if this is a constructor, then set the "this" register to an uninitialized reference of the current class
125            if ((encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0) {
126                //TODO: it would probably make more sense to validate this somewhere else, and just put an assert here. Also, need to do a similar check for static constructor
127                if (!encodedMethod.method.getMethodName().getStringValue().equals("<init>")) {
128                    throw new ValidationException("The constructor flag can only be used with an <init> method.");
129                }
130
131                setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
132                        RegisterType.getRegisterType(RegisterType.Category.UninitThis,
133                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
134            } else {
135                if (encodedMethod.method.getMethodName().getStringValue().equals("<init>")) {
136                    throw new ValidationException("An <init> method must have the \"constructor\" access flag");
137                }
138
139                setPostRegisterTypeAndPropagateChanges(startOfMethod, thisRegister,
140                        RegisterType.getRegisterType(RegisterType.Category.Reference,
141                            ClassPath.getClassDef(methodIdItem.getContainingClass())));
142            }
143        }
144
145        TypeListItem parameters = methodIdItem.getPrototype().getParameters();
146        if (parameters != null) {
147            RegisterType[] parameterTypes = getParameterTypes(parameters, parameterRegisters);
148            for (int i=0; i<parameterTypes.length; i++) {
149                RegisterType registerType = parameterTypes[i];
150                int registerNum = (totalRegisters - parameterRegisters) + i;
151                setPostRegisterTypeAndPropagateChanges(startOfMethod, registerNum, registerType);
152            }
153        }
154
155        RegisterType uninit = RegisterType.getRegisterType(RegisterType.Category.Uninit, null);
156        for (int i=0; i<nonParameterRegisters; i++) {
157            setPostRegisterTypeAndPropagateChanges(startOfMethod, i, uninit);
158        }
159
160        BitSet instructionsToAnalyze = new BitSet(verifiedInstructions.size());
161
162        //make sure all of the "first instructions" are marked for processing
163        for (AnalyzedInstruction successor: startOfMethod.successors) {
164            instructionsToAnalyze.set(successor.instructionIndex);
165        }
166
167        BitSet odexedInstructions = new BitSet(verifiedInstructions.size());
168
169        do {
170            boolean didSomething = false;
171
172            while (!instructionsToAnalyze.isEmpty()) {
173                for(int i=instructionsToAnalyze.nextSetBit(0); i>=0; i=instructionsToAnalyze.nextSetBit(i+1)) {
174                    instructionsToAnalyze.clear(i);
175                    if (verifiedInstructions.get(i)) {
176                        continue;
177                    }
178                    AnalyzedInstruction instructionToVerify = instructions.valueAt(i);
179                    try {
180                        if (instructionToVerify.originalInstruction.opcode.odexOnly()) {
181                            instructionToVerify.restoreOdexedInstruction();
182                        }
183
184                        if (!analyzeInstruction(instructionToVerify)) {
185                            odexedInstructions.set(i);
186                            continue;
187                        } else {
188                            didSomething = true;
189                            odexedInstructions.clear(i);
190                        }
191                    } catch (ValidationException ex) {
192                        this.validationException = ex;
193                        int codeAddress = getInstructionAddress(instructionToVerify);
194                        ex.setCodeAddress(codeAddress);
195                        ex.addContext(String.format("opcode: %s", instructionToVerify.instruction.opcode.name));
196                        ex.addContext(String.format("CodeAddress: %d", codeAddress));
197                        ex.addContext(String.format("Method: %s", encodedMethod.method.getMethodString()));
198                        break;
199                    }
200
201                    verifiedInstructions.set(instructionToVerify.getInstructionIndex());
202
203                    for (AnalyzedInstruction successor: instructionToVerify.successors) {
204                        instructionsToAnalyze.set(successor.getInstructionIndex());
205                    }
206                }
207                if (validationException != null) {
208                    break;
209                }
210            }
211
212            if (!didSomething) {
213                break;
214            }
215
216            if (!odexedInstructions.isEmpty()) {
217                for (int i=odexedInstructions.nextSetBit(0); i>=0; i=odexedInstructions.nextSetBit(i+1)) {
218                    instructionsToAnalyze.set(i);
219                }
220            }
221        } while (true);
222
223        for (int i=0; i<instructions.size(); i++) {
224            AnalyzedInstruction instruction = instructions.valueAt(i);
225
226            if (!odexedInstructions.get(i)) {
227
228                //TODO: We probably need to re-verify everything after changing unknown-uninit. Better yet, maybe we should split the register propagation logic and the verification logic, and only do the verification after all the register info is known
229
230                //We don't want to change unknown register types to uninit for unreachable instructions, as the register
231                //types for the unreachable instruction shouldn't be taken into account when merging registers for any
232                //reachable predecessor (for example, the predecessor of an unreachable goto instruction)
233                //So we keep the unreachable register types as unknown, because anything else + unknown = anything else
234                if (verifiedInstructions.get(i)) {
235                    for (int j=0; j<instruction.postRegisterMap.length; j++) {
236                        if (instruction.postRegisterMap[j].category == RegisterType.Category.Unknown) {
237                            instruction.postRegisterMap[j] = uninit;
238                        }
239                    }
240                }
241            } else {
242                Instruction odexedInstruction = instruction.instruction;
243                int objectRegisterNumber;
244
245                if (odexedInstruction.getFormat() == Format.Format22cs) {
246                    objectRegisterNumber = ((Instruction22cs)odexedInstruction).getRegisterB();
247                } else if (odexedInstruction.getFormat() == Format.Format35ms) {
248                    objectRegisterNumber = ((Instruction35ms)odexedInstruction).getRegisterD();
249                } else if (odexedInstruction.getFormat() == Format.Format3rms) {
250                    objectRegisterNumber = ((Instruction3rms)odexedInstruction).getStartRegister();
251                } else {
252                    assert false;
253                    throw new ExceptionWithContext(String.format("Unexpected format %s for odexed instruction",
254                            odexedInstruction.getFormat().name()));
255                }
256
257                instruction.setDeodexedInstruction(new UnresolvedNullReference(odexedInstruction,
258                        objectRegisterNumber));
259
260                setAndPropagateDeadness(instruction);
261            }
262        }
263
264        analyzed = true;
265        return makeInstructionArray();
266    }
267
268    private int getThisRegister() {
269        assert (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0;
270
271        CodeItem codeItem = encodedMethod.codeItem;
272        assert codeItem != null;
273
274        MethodIdItem methodIdItem = encodedMethod.method;
275        assert methodIdItem != null;
276
277        int totalRegisters = codeItem.getRegisterCount();
278        if (totalRegisters == 0) {
279            throw new ValidationException("A non-static method must have at least 1 register");
280        }
281
282        int parameterRegisters = methodIdItem.getPrototype().getParameterRegisterCount();
283
284        return totalRegisters - parameterRegisters - 1;
285    }
286
287    private boolean isInstanceConstructor() {
288        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) == 0 &&
289               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
290    }
291
292    private boolean isStaticConstructor() {
293        return (encodedMethod.accessFlags & AccessFlags.STATIC.getValue()) != 0 &&
294               (encodedMethod.accessFlags & AccessFlags.CONSTRUCTOR.getValue()) != 0;
295    }
296
297    public AnalyzedInstruction getStartOfMethod() {
298        return startOfMethod;
299    }
300
301    public AnalyzedInstruction[] makeInstructionArray() {
302        AnalyzedInstruction[] instructionArray = new AnalyzedInstruction[instructions.size()];
303        for (int i=0; i<instructions.size(); i++) {
304            instructionArray[i] = instructions.valueAt(i);
305        }
306        return instructionArray;
307    }
308
309    public ValidationException getValidationException() {
310        return validationException;
311    }
312
313    private static RegisterType[] getParameterTypes(TypeListItem typeListItem, int parameterRegisterCount) {
314        assert typeListItem != null;
315        assert parameterRegisterCount == typeListItem.getRegisterCount();
316
317        RegisterType[] registerTypes = new RegisterType[parameterRegisterCount];
318
319        int registerNum = 0;
320        for (TypeIdItem type: typeListItem.getTypes()) {
321            if (type.getRegisterCount() == 2) {
322                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, true);
323                registerTypes[registerNum++] = RegisterType.getWideRegisterTypeForTypeIdItem(type, false);
324            } else {
325                registerTypes[registerNum++] = RegisterType.getRegisterTypeForTypeIdItem(type);
326            }
327        }
328
329        return registerTypes;
330    }
331
332    public int getInstructionAddress(AnalyzedInstruction instruction) {
333        return instructions.keyAt(instruction.instructionIndex);
334    }
335
336    private void setDestinationRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction,
337                                                               RegisterType registerType) {
338        setPostRegisterTypeAndPropagateChanges(analyzedInstruction, analyzedInstruction.getDestinationRegister(),
339                registerType);
340    }
341
342
343    private void setAndPropagateDeadness(AnalyzedInstruction analyzedInstruction) {
344        BitSet instructionsToProcess = new BitSet(instructions.size());
345
346        //temporarily set the undeodexeble instruction as dead, so that the "set dead if all predecessors are dead"
347        //operation works
348        analyzedInstruction.dead = true;
349
350        for (AnalyzedInstruction successor: analyzedInstruction.successors) {
351            instructionsToProcess.set(successor.instructionIndex);
352        }
353
354        instructionsToProcess.set(analyzedInstruction.instructionIndex);
355
356        while (!instructionsToProcess.isEmpty()) {
357            for (int i=instructionsToProcess.nextSetBit(0); i>=0; i=instructionsToProcess.nextSetBit(i+1)) {
358                AnalyzedInstruction currentInstruction = instructions.valueAt(i);
359                instructionsToProcess.clear(i);
360
361                if (currentInstruction.dead) {
362                    continue;
363                }
364
365                boolean isDead = true;
366
367                for (AnalyzedInstruction predecessor: currentInstruction.predecessors) {
368                    if (!predecessor.dead) {
369                        isDead = false;
370                        break;
371                    }
372                }
373
374                if (isDead) {
375                    currentInstruction.dead = true;
376
377                    for (AnalyzedInstruction successor: currentInstruction.successors) {
378                        instructionsToProcess.set(successor.instructionIndex);
379                    }
380                }
381            }
382        }
383
384        analyzedInstruction.dead = false;
385    }
386
387    private void setPostRegisterTypeAndPropagateChanges(AnalyzedInstruction analyzedInstruction, int registerNumber,
388                                                RegisterType registerType) {
389
390        BitSet changedInstructions = new BitSet(instructions.size());
391
392        if (!analyzedInstruction.setPostRegisterType(registerNumber, registerType)) {
393            return;
394        }
395
396        propagateRegisterToSuccessors(analyzedInstruction, registerNumber, changedInstructions);
397
398        //Using a for loop inside the while loop optimizes for the common case of the successors of an instruction
399        //occurring after the instruction. Any successors that occur prior to the instruction will be picked up on
400        //the next iteration of the while loop.
401        //This could also be done recursively, but in large methods it would likely cause very deep recursion,
402        //which requires the user to specify a larger stack size. This isn't really a problem, but it is slightly
403        //annoying.
404        while (!changedInstructions.isEmpty()) {
405            for (int instructionIndex=changedInstructions.nextSetBit(0);
406                     instructionIndex>=0;
407                     instructionIndex=changedInstructions.nextSetBit(instructionIndex+1)) {
408
409                changedInstructions.clear(instructionIndex);
410
411                propagateRegisterToSuccessors(instructions.valueAt(instructionIndex), registerNumber,
412                        changedInstructions);
413            }
414        }
415
416        if (registerType.category == RegisterType.Category.LongLo) {
417            checkWidePair(registerNumber, analyzedInstruction);
418            setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
419                    RegisterType.getRegisterType(RegisterType.Category.LongHi, null));
420        } else if (registerType.category == RegisterType.Category.DoubleLo) {
421            checkWidePair(registerNumber, analyzedInstruction);
422            setPostRegisterTypeAndPropagateChanges(analyzedInstruction, registerNumber+1,
423                    RegisterType.getRegisterType(RegisterType.Category.DoubleHi, null));
424        }
425    }
426
427    private void propagateRegisterToSuccessors(AnalyzedInstruction instruction, int registerNumber,
428                                               BitSet changedInstructions) {
429        RegisterType postRegisterType = instruction.getPostInstructionRegisterType(registerNumber);
430        for (AnalyzedInstruction successor: instruction.successors) {
431            if (successor.mergeRegister(registerNumber, postRegisterType, verifiedInstructions)) {
432                changedInstructions.set(successor.instructionIndex);
433            }
434        }
435    }
436
437    private void buildInstructionList() {
438        assert encodedMethod != null;
439        assert encodedMethod.codeItem != null;
440        int registerCount = encodedMethod.codeItem.getRegisterCount();
441
442        Instruction[] insns = encodedMethod.codeItem.getInstructions();
443
444        instructions = new SparseArray<AnalyzedInstruction>(insns.length);
445
446        //first, create all the instructions and populate the instructionAddresses array
447        int currentCodeAddress = 0;
448        for (int i=0; i<insns.length; i++) {
449            instructions.append(currentCodeAddress, new AnalyzedInstruction(insns[i], i, registerCount));
450            assert instructions.indexOfKey(currentCodeAddress) == i;
451            currentCodeAddress += insns[i].getSize(currentCodeAddress);
452        }
453
454        //next, populate the exceptionHandlers array. The array item for each instruction that can throw an exception
455        //and is covered by a try block should be set to a list of the first instructions of each exception handler
456        //for the try block covering the instruction
457        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
458        int triesIndex = 0;
459        CodeItem.TryItem currentTry = null;
460        AnalyzedInstruction[] currentExceptionHandlers = null;
461        AnalyzedInstruction[][] exceptionHandlers = new AnalyzedInstruction[insns.length][];
462
463        if (tries != null) {
464            for (int i=0; i<instructions.size(); i++) {
465                AnalyzedInstruction instruction = instructions.valueAt(i);
466                Opcode instructionOpcode = instruction.instruction.opcode;
467                currentCodeAddress = getInstructionAddress(instruction);
468
469                //check if we have gone past the end of the current try
470                if (currentTry != null) {
471                    if (currentTry.getStartCodeAddress() + currentTry.getTryLength() <= currentCodeAddress) {
472                        currentTry = null;
473                        triesIndex++;
474                    }
475                }
476
477                //check if the next try is applicable yet
478                if (currentTry == null && triesIndex < tries.length) {
479                    CodeItem.TryItem tryItem = tries[triesIndex];
480                    if (tryItem.getStartCodeAddress() <= currentCodeAddress) {
481                        assert(tryItem.getStartCodeAddress() + tryItem.getTryLength() > currentCodeAddress);
482
483                        currentTry = tryItem;
484
485                        currentExceptionHandlers = buildExceptionHandlerArray(tryItem);
486                    }
487                }
488
489                //if we're inside a try block, and the instruction can throw an exception, then add the exception handlers
490                //for the current instruction
491                if (currentTry != null && instructionOpcode.canThrow()) {
492                    exceptionHandlers[i] = currentExceptionHandlers;
493                }
494            }
495        }
496
497        //finally, populate the successors and predecessors for each instruction. We start at the fake "StartOfMethod"
498        //instruction and follow the execution path. Any unreachable code won't have any predecessors or successors,
499        //and no reachable code will have an unreachable predessor or successor
500        assert instructions.size() > 0;
501        BitSet instructionsToProcess = new BitSet(insns.length);
502
503        addPredecessorSuccessor(startOfMethod, instructions.valueAt(0), exceptionHandlers, instructionsToProcess);
504        while (!instructionsToProcess.isEmpty()) {
505            int currentInstructionIndex = instructionsToProcess.nextSetBit(0);
506            instructionsToProcess.clear(currentInstructionIndex);
507
508            AnalyzedInstruction instruction = instructions.valueAt(currentInstructionIndex);
509            Opcode instructionOpcode = instruction.instruction.opcode;
510            int instructionCodeAddress = getInstructionAddress(instruction);
511
512            if (instruction.instruction.opcode.canContinue()) {
513                if (instruction.instruction.opcode != Opcode.NOP ||
514                    !instruction.instruction.getFormat().variableSizeFormat) {
515
516                    if (currentInstructionIndex == instructions.size() - 1) {
517                        throw new ValidationException("Execution can continue past the last instruction");
518                    }
519
520                    AnalyzedInstruction nextInstruction = instructions.valueAt(currentInstructionIndex+1);
521                    addPredecessorSuccessor(instruction, nextInstruction, exceptionHandlers, instructionsToProcess);
522                }
523            }
524
525            if (instruction.instruction instanceof OffsetInstruction) {
526                OffsetInstruction offsetInstruction = (OffsetInstruction)instruction.instruction;
527
528                if (instructionOpcode == Opcode.PACKED_SWITCH || instructionOpcode == Opcode.SPARSE_SWITCH) {
529                    MultiOffsetInstruction switchDataInstruction =
530                            (MultiOffsetInstruction)instructions.get(instructionCodeAddress +
531                                    offsetInstruction.getTargetAddressOffset()).instruction;
532                    for (int targetAddressOffset: switchDataInstruction.getTargets()) {
533                        AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
534                                targetAddressOffset);
535
536                        addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers,
537                                instructionsToProcess);
538                    }
539                } else {
540                    int targetAddressOffset = offsetInstruction.getTargetAddressOffset();
541                    AnalyzedInstruction targetInstruction = instructions.get(instructionCodeAddress +
542                            targetAddressOffset);
543                    addPredecessorSuccessor(instruction, targetInstruction, exceptionHandlers, instructionsToProcess);
544                }
545            }
546        }
547    }
548
549    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
550                                                AnalyzedInstruction[][] exceptionHandlers,
551                                                BitSet instructionsToProcess) {
552        addPredecessorSuccessor(predecessor, successor, exceptionHandlers, instructionsToProcess, false);
553    }
554
555    private void addPredecessorSuccessor(AnalyzedInstruction predecessor, AnalyzedInstruction successor,
556                                                AnalyzedInstruction[][] exceptionHandlers,
557                                                BitSet instructionsToProcess, boolean allowMoveException) {
558
559        if (!allowMoveException && successor.instruction.opcode == Opcode.MOVE_EXCEPTION) {
560            throw new ValidationException("Execution can pass from the " + predecessor.instruction.opcode.name +
561                    " instruction at code address 0x" + Integer.toHexString(getInstructionAddress(predecessor)) +
562                    " to the move-exception instruction at address 0x" +
563                    Integer.toHexString(getInstructionAddress(successor)));
564        }
565
566        if (!successor.addPredecessor(predecessor)) {
567            return;
568        }
569
570        predecessor.addSuccessor(successor);
571        instructionsToProcess.set(successor.getInstructionIndex());
572
573
574        //if the successor can throw an instruction, then we need to add the exception handlers as additional
575        //successors to the predecessor (and then apply this same logic recursively if needed)
576        //Technically, we should handle the monitor-exit instruction as a special case. The exception is actually
577        //thrown *after* the instruction executes, instead of "before" the instruction executes, lke for any other
578        //instruction. But since it doesn't modify any registers, we can treat it like any other instruction.
579        AnalyzedInstruction[] exceptionHandlersForSuccessor = exceptionHandlers[successor.instructionIndex];
580        if (exceptionHandlersForSuccessor != null) {
581            //the item for this instruction in exceptionHandlersForSuccessor should only be set if this instruction
582            //can throw an exception
583            assert successor.instruction.opcode.canThrow();
584
585            for (AnalyzedInstruction exceptionHandler: exceptionHandlersForSuccessor) {
586                addPredecessorSuccessor(predecessor, exceptionHandler, exceptionHandlers, instructionsToProcess, true);
587            }
588        }
589    }
590
591    private AnalyzedInstruction[] buildExceptionHandlerArray(CodeItem.TryItem tryItem) {
592        int exceptionHandlerCount = tryItem.encodedCatchHandler.handlers.length;
593        int catchAllHandler = tryItem.encodedCatchHandler.getCatchAllHandlerAddress();
594        if (catchAllHandler != -1) {
595            exceptionHandlerCount++;
596        }
597
598        AnalyzedInstruction[] exceptionHandlers = new AnalyzedInstruction[exceptionHandlerCount];
599        for (int i=0; i<tryItem.encodedCatchHandler.handlers.length; i++) {
600            exceptionHandlers[i] = instructions.get(tryItem.encodedCatchHandler.handlers[i].getHandlerAddress());
601        }
602
603        if (catchAllHandler != -1) {
604            exceptionHandlers[exceptionHandlers.length - 1] = instructions.get(catchAllHandler);
605        }
606
607        return exceptionHandlers;
608    }
609
610    private boolean analyzeInstruction(AnalyzedInstruction analyzedInstruction) {
611        Instruction instruction = analyzedInstruction.instruction;
612
613        switch (instruction.opcode) {
614            case NOP:
615                return true;
616            case MOVE:
617            case MOVE_FROM16:
618            case MOVE_16:
619                handleMove(analyzedInstruction, Primitive32BitCategories);
620                return true;
621            case MOVE_WIDE:
622            case MOVE_WIDE_FROM16:
623            case MOVE_WIDE_16:
624                handleMove(analyzedInstruction, WideLowCategories);
625                return true;
626            case MOVE_OBJECT:
627            case MOVE_OBJECT_FROM16:
628            case MOVE_OBJECT_16:
629                handleMove(analyzedInstruction, ReferenceOrUninitCategories);
630                return true;
631            case MOVE_RESULT:
632                handleMoveResult(analyzedInstruction, Primitive32BitCategories);
633                return true;
634            case MOVE_RESULT_WIDE:
635                handleMoveResult(analyzedInstruction, WideLowCategories);
636                return true;
637            case MOVE_RESULT_OBJECT:
638                handleMoveResult(analyzedInstruction, ReferenceCategories);
639                return true;
640            case MOVE_EXCEPTION:
641                handleMoveException(analyzedInstruction);
642                return true;
643            case RETURN_VOID:
644                handleReturnVoid(analyzedInstruction);
645                return true;
646            case RETURN:
647                handleReturn(analyzedInstruction, Primitive32BitCategories);
648                return true;
649            case RETURN_WIDE:
650                handleReturn(analyzedInstruction, WideLowCategories);
651                return true;
652            case RETURN_OBJECT:
653                handleReturn(analyzedInstruction, ReferenceCategories);
654                return true;
655            case CONST_4:
656            case CONST_16:
657            case CONST:
658                handleConst(analyzedInstruction);
659                return true;
660            case CONST_HIGH16:
661                handleConstHigh16(analyzedInstruction);
662                return true;
663            case CONST_WIDE_16:
664            case CONST_WIDE_32:
665            case CONST_WIDE:
666            case CONST_WIDE_HIGH16:
667                handleWideConst(analyzedInstruction);
668                return true;
669            case CONST_STRING:
670            case CONST_STRING_JUMBO:
671                handleConstString(analyzedInstruction);
672                return true;
673            case CONST_CLASS:
674                handleConstClass(analyzedInstruction);
675                return true;
676            case MONITOR_ENTER:
677            case MONITOR_EXIT:
678                handleMonitor(analyzedInstruction);
679                return true;
680            case CHECK_CAST:
681                handleCheckCast(analyzedInstruction);
682                return true;
683            case INSTANCE_OF:
684                handleInstanceOf(analyzedInstruction);
685                return true;
686            case ARRAY_LENGTH:
687                handleArrayLength(analyzedInstruction);
688                return true;
689            case NEW_INSTANCE:
690                handleNewInstance(analyzedInstruction);
691                return true;
692            case NEW_ARRAY:
693                handleNewArray(analyzedInstruction);
694                return true;
695            case FILLED_NEW_ARRAY:
696                handleFilledNewArray(analyzedInstruction);
697                return true;
698            case FILLED_NEW_ARRAY_RANGE:
699                handleFilledNewArrayRange(analyzedInstruction);
700                return true;
701            case FILL_ARRAY_DATA:
702                handleFillArrayData(analyzedInstruction);
703                return true;
704            case THROW:
705                handleThrow(analyzedInstruction);
706                return true;
707            case GOTO:
708            case GOTO_16:
709            case GOTO_32:
710                //nothing to do
711                return true;
712            case PACKED_SWITCH:
713                handleSwitch(analyzedInstruction, Format.PackedSwitchData);
714                return true;
715            case SPARSE_SWITCH:
716                handleSwitch(analyzedInstruction, Format.SparseSwitchData);
717                return true;
718            case CMPL_FLOAT:
719            case CMPG_FLOAT:
720                handleFloatWideCmp(analyzedInstruction, Primitive32BitCategories);
721                return true;
722            case CMPL_DOUBLE:
723            case CMPG_DOUBLE:
724            case CMP_LONG:
725                handleFloatWideCmp(analyzedInstruction, WideLowCategories);
726                return true;
727            case IF_EQ:
728            case IF_NE:
729                handleIfEqNe(analyzedInstruction);
730                return true;
731            case IF_LT:
732            case IF_GE:
733            case IF_GT:
734            case IF_LE:
735                handleIf(analyzedInstruction);
736                return true;
737            case IF_EQZ:
738            case IF_NEZ:
739                handleIfEqzNez(analyzedInstruction);
740                return true;
741            case IF_LTZ:
742            case IF_GEZ:
743            case IF_GTZ:
744            case IF_LEZ:
745                handleIfz(analyzedInstruction);
746                return true;
747            case AGET:
748                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Integer);
749                return true;
750            case AGET_BOOLEAN:
751                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Boolean);
752                return true;
753            case AGET_BYTE:
754                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Byte);
755                return true;
756            case AGET_CHAR:
757                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Char);
758                return true;
759            case AGET_SHORT:
760                handle32BitPrimitiveAget(analyzedInstruction, RegisterType.Category.Short);
761                return true;
762            case AGET_WIDE:
763                handleAgetWide(analyzedInstruction);
764                return true;
765            case AGET_OBJECT:
766                handleAgetObject(analyzedInstruction);
767                return true;
768            case APUT:
769                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Integer);
770                return true;
771            case APUT_BOOLEAN:
772                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Boolean);
773                return true;
774            case APUT_BYTE:
775                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Byte);
776                return true;
777            case APUT_CHAR:
778                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Char);
779                return true;
780            case APUT_SHORT:
781                handle32BitPrimitiveAput(analyzedInstruction, RegisterType.Category.Short);
782                return true;
783            case APUT_WIDE:
784                handleAputWide(analyzedInstruction);
785                return true;
786            case APUT_OBJECT:
787                handleAputObject(analyzedInstruction);
788                return true;
789            case IGET:
790                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Integer);
791                return true;
792            case IGET_BOOLEAN:
793                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Boolean);
794                return true;
795            case IGET_BYTE:
796                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Byte);
797                return true;
798            case IGET_CHAR:
799                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Char);
800                return true;
801            case IGET_SHORT:
802                handle32BitPrimitiveIget(analyzedInstruction, RegisterType.Category.Short);
803                return true;
804            case IGET_WIDE:
805                handleIgetWide(analyzedInstruction);
806                return true;
807            case IGET_OBJECT:
808                handleIgetObject(analyzedInstruction);
809                return true;
810            case IPUT:
811                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Integer);
812                return true;
813            case IPUT_BOOLEAN:
814                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Boolean);
815                return true;
816            case IPUT_BYTE:
817                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Byte);
818                return true;
819            case IPUT_CHAR:
820                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Char);
821                return true;
822            case IPUT_SHORT:
823                handle32BitPrimitiveIput(analyzedInstruction, RegisterType.Category.Short);
824                return true;
825            case IPUT_WIDE:
826                handleIputWide(analyzedInstruction);
827                return true;
828            case IPUT_OBJECT:
829                handleIputObject(analyzedInstruction);
830                return true;
831            case SGET:
832                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Integer);
833                return true;
834            case SGET_BOOLEAN:
835                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Boolean);
836                return true;
837            case SGET_BYTE:
838                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Byte);
839                return true;
840            case SGET_CHAR:
841                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Char);
842                return true;
843            case SGET_SHORT:
844                handle32BitPrimitiveSget(analyzedInstruction, RegisterType.Category.Short);
845                return true;
846            case SGET_WIDE:
847                handleSgetWide(analyzedInstruction);
848                return true;
849            case SGET_OBJECT:
850                handleSgetObject(analyzedInstruction);
851                return true;
852            case SPUT:
853                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Integer);
854                return true;
855            case SPUT_BOOLEAN:
856                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Boolean);
857                return true;
858            case SPUT_BYTE:
859                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Byte);
860                return true;
861            case SPUT_CHAR:
862                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Char);
863                return true;
864            case SPUT_SHORT:
865                handle32BitPrimitiveSput(analyzedInstruction, RegisterType.Category.Short);
866                return true;
867            case SPUT_WIDE:
868                handleSputWide(analyzedInstruction);
869                return true;
870            case SPUT_OBJECT:
871                handleSputObject(analyzedInstruction);
872                return true;
873            case INVOKE_VIRTUAL:
874                handleInvoke(analyzedInstruction, INVOKE_VIRTUAL);
875                return true;
876            case INVOKE_SUPER:
877                handleInvoke(analyzedInstruction, INVOKE_SUPER);
878                return true;
879            case INVOKE_DIRECT:
880                handleInvoke(analyzedInstruction, INVOKE_DIRECT);
881                return true;
882            case INVOKE_STATIC:
883                handleInvoke(analyzedInstruction, INVOKE_STATIC);
884                return true;
885            case INVOKE_INTERFACE:
886                handleInvoke(analyzedInstruction, INVOKE_INTERFACE);
887                return true;
888            case INVOKE_VIRTUAL_RANGE:
889                handleInvokeRange(analyzedInstruction, INVOKE_VIRTUAL);
890                return true;
891            case INVOKE_SUPER_RANGE:
892                handleInvokeRange(analyzedInstruction, INVOKE_SUPER);
893                return true;
894            case INVOKE_DIRECT_RANGE:
895                handleInvokeRange(analyzedInstruction, INVOKE_DIRECT);
896                return true;
897            case INVOKE_STATIC_RANGE:
898                handleInvokeRange(analyzedInstruction, INVOKE_STATIC);
899                return true;
900            case INVOKE_INTERFACE_RANGE:
901                handleInvokeRange(analyzedInstruction, INVOKE_INTERFACE);
902                return true;
903            case NEG_INT:
904            case NOT_INT:
905                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer);
906                return true;
907            case NEG_LONG:
908            case NOT_LONG:
909                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.LongLo);
910                return true;
911            case NEG_FLOAT:
912                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Float);
913                return true;
914            case NEG_DOUBLE:
915                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.DoubleLo);
916                return true;
917            case INT_TO_LONG:
918                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.LongLo);
919                return true;
920            case INT_TO_FLOAT:
921                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Float);
922                return true;
923            case INT_TO_DOUBLE:
924                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.DoubleLo);
925                return true;
926            case LONG_TO_INT:
927            case DOUBLE_TO_INT:
928                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.Integer);
929                return true;
930            case LONG_TO_FLOAT:
931            case DOUBLE_TO_FLOAT:
932                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.Float);
933                return true;
934            case LONG_TO_DOUBLE:
935                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.DoubleLo);
936                return true;
937            case FLOAT_TO_INT:
938                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer);
939                return true;
940            case FLOAT_TO_LONG:
941                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.LongLo);
942                return true;
943            case FLOAT_TO_DOUBLE:
944                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.DoubleLo);
945                return true;
946            case DOUBLE_TO_LONG:
947                handleUnaryOp(analyzedInstruction, WideLowCategories, RegisterType.Category.LongLo);
948                return true;
949            case INT_TO_BYTE:
950                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Byte);
951                return true;
952            case INT_TO_CHAR:
953                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Char);
954                return true;
955            case INT_TO_SHORT:
956                handleUnaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Short);
957                return true;
958            case ADD_INT:
959            case SUB_INT:
960            case MUL_INT:
961            case DIV_INT:
962            case REM_INT:
963            case SHL_INT:
964            case SHR_INT:
965            case USHR_INT:
966                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
967                        RegisterType.Category.Integer, false);
968                return true;
969            case AND_INT:
970            case OR_INT:
971            case XOR_INT:
972                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
973                        RegisterType.Category.Integer, true);
974                return true;
975            case ADD_LONG:
976            case SUB_LONG:
977            case MUL_LONG:
978            case DIV_LONG:
979            case REM_LONG:
980            case AND_LONG:
981            case OR_LONG:
982            case XOR_LONG:
983                handleBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories, RegisterType.Category.LongLo,
984                        false);
985                return true;
986            case SHL_LONG:
987            case SHR_LONG:
988            case USHR_LONG:
989                handleBinaryOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories,
990                        RegisterType.Category.LongLo, false);
991                return true;
992            case ADD_FLOAT:
993            case SUB_FLOAT:
994            case MUL_FLOAT:
995            case DIV_FLOAT:
996            case REM_FLOAT:
997                handleBinaryOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
998                        RegisterType.Category.Float, false);
999                return true;
1000            case ADD_DOUBLE:
1001            case SUB_DOUBLE:
1002            case MUL_DOUBLE:
1003            case DIV_DOUBLE:
1004            case REM_DOUBLE:
1005                handleBinaryOp(analyzedInstruction, WideLowCategories, WideLowCategories,
1006                        RegisterType.Category.DoubleLo, false);
1007                return true;
1008            case ADD_INT_2ADDR:
1009            case SUB_INT_2ADDR:
1010            case MUL_INT_2ADDR:
1011            case DIV_INT_2ADDR:
1012            case REM_INT_2ADDR:
1013            case SHL_INT_2ADDR:
1014            case SHR_INT_2ADDR:
1015            case USHR_INT_2ADDR:
1016                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
1017                        RegisterType.Category.Integer, false);
1018                return true;
1019            case AND_INT_2ADDR:
1020            case OR_INT_2ADDR:
1021            case XOR_INT_2ADDR:
1022                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
1023                        RegisterType.Category.Integer, true);
1024                return true;
1025            case ADD_LONG_2ADDR:
1026            case SUB_LONG_2ADDR:
1027            case MUL_LONG_2ADDR:
1028            case DIV_LONG_2ADDR:
1029            case REM_LONG_2ADDR:
1030            case AND_LONG_2ADDR:
1031            case OR_LONG_2ADDR:
1032            case XOR_LONG_2ADDR:
1033                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories,
1034                        RegisterType.Category.LongLo, false);
1035                return true;
1036            case SHL_LONG_2ADDR:
1037            case SHR_LONG_2ADDR:
1038            case USHR_LONG_2ADDR:
1039                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, Primitive32BitCategories,
1040                        RegisterType.Category.LongLo, false);
1041                return true;
1042            case ADD_FLOAT_2ADDR:
1043            case SUB_FLOAT_2ADDR:
1044            case MUL_FLOAT_2ADDR:
1045            case DIV_FLOAT_2ADDR:
1046            case REM_FLOAT_2ADDR:
1047                handleBinary2AddrOp(analyzedInstruction, Primitive32BitCategories, Primitive32BitCategories,
1048                        RegisterType.Category.Float, false);
1049                return true;
1050            case ADD_DOUBLE_2ADDR:
1051            case SUB_DOUBLE_2ADDR:
1052            case MUL_DOUBLE_2ADDR:
1053            case DIV_DOUBLE_2ADDR:
1054            case REM_DOUBLE_2ADDR:
1055                handleBinary2AddrOp(analyzedInstruction, WideLowCategories, WideLowCategories,
1056                        RegisterType.Category.DoubleLo, false);
1057                return true;
1058            case ADD_INT_LIT16:
1059            case RSUB_INT:
1060            case MUL_INT_LIT16:
1061            case DIV_INT_LIT16:
1062            case REM_INT_LIT16:
1063                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer,
1064                        false);
1065                return true;
1066            case AND_INT_LIT16:
1067            case OR_INT_LIT16:
1068            case XOR_INT_LIT16:
1069                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer,
1070                        true);
1071                return true;
1072            case ADD_INT_LIT8:
1073            case RSUB_INT_LIT8:
1074            case MUL_INT_LIT8:
1075            case DIV_INT_LIT8:
1076            case REM_INT_LIT8:
1077            case SHL_INT_LIT8:
1078                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer,
1079                        false);
1080                return true;
1081            case AND_INT_LIT8:
1082            case OR_INT_LIT8:
1083            case XOR_INT_LIT8:
1084                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories, RegisterType.Category.Integer,
1085                        true);
1086                return true;
1087            case SHR_INT_LIT8:
1088                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories,
1089                        getDestTypeForLiteralShiftRight(analyzedInstruction, true), false);
1090                return true;
1091            case USHR_INT_LIT8:
1092                handleLiteralBinaryOp(analyzedInstruction, Primitive32BitCategories,
1093                        getDestTypeForLiteralShiftRight(analyzedInstruction, false), false);
1094                return true;
1095            case EXECUTE_INLINE:
1096                handleExecuteInline(analyzedInstruction);
1097                return true;
1098            case EXECUTE_INLINE_RANGE:
1099                handleExecuteInlineRange(analyzedInstruction);
1100                return true;
1101            case INVOKE_DIRECT_EMPTY:
1102                handleInvokeDirectEmpty(analyzedInstruction);
1103                return true;
1104            case IGET_QUICK:
1105            case IGET_WIDE_QUICK:
1106            case IGET_OBJECT_QUICK:
1107                return handleIputIgetQuick(analyzedInstruction, false);
1108            case IPUT_QUICK:
1109            case IPUT_WIDE_QUICK:
1110            case IPUT_OBJECT_QUICK:
1111                return handleIputIgetQuick(analyzedInstruction, true);
1112            case INVOKE_VIRTUAL_QUICK:
1113                return handleInvokeVirtualQuick(analyzedInstruction, false, false);
1114            case INVOKE_SUPER_QUICK:
1115                return handleInvokeVirtualQuick(analyzedInstruction, true, false);
1116            case INVOKE_VIRTUAL_QUICK_RANGE:
1117                return handleInvokeVirtualQuick(analyzedInstruction, false, true);
1118            case INVOKE_SUPER_QUICK_RANGE:
1119                return handleInvokeVirtualQuick(analyzedInstruction, true, true);
1120            default:
1121                assert false;
1122                return true;
1123        }
1124    }
1125
1126    private static final EnumSet<RegisterType.Category> Primitive32BitCategories = EnumSet.of(
1127            RegisterType.Category.Null,
1128            RegisterType.Category.One,
1129            RegisterType.Category.Boolean,
1130            RegisterType.Category.Byte,
1131            RegisterType.Category.PosByte,
1132            RegisterType.Category.Short,
1133            RegisterType.Category.PosShort,
1134            RegisterType.Category.Char,
1135            RegisterType.Category.Integer,
1136            RegisterType.Category.Float);
1137
1138    private static final EnumSet<RegisterType.Category> WideLowCategories = EnumSet.of(
1139            RegisterType.Category.LongLo,
1140            RegisterType.Category.DoubleLo);
1141
1142    private static final EnumSet<RegisterType.Category> WideHighCategories = EnumSet.of(
1143            RegisterType.Category.LongHi,
1144            RegisterType.Category.DoubleHi);
1145
1146    private static final EnumSet<RegisterType.Category> ReferenceCategories = EnumSet.of(
1147            RegisterType.Category.Null,
1148            RegisterType.Category.Reference);
1149
1150    private static final EnumSet<RegisterType.Category> ReferenceOrUninitThisCategories = EnumSet.of(
1151            RegisterType.Category.Null,
1152            RegisterType.Category.UninitThis,
1153            RegisterType.Category.Reference);
1154
1155    private static final EnumSet<RegisterType.Category> ReferenceOrUninitCategories = EnumSet.of(
1156            RegisterType.Category.Null,
1157            RegisterType.Category.UninitRef,
1158            RegisterType.Category.UninitThis,
1159            RegisterType.Category.Reference);
1160
1161    private static final EnumSet<RegisterType.Category> ReferenceAndPrimitive32BitCategories = EnumSet.of(
1162            RegisterType.Category.Null,
1163            RegisterType.Category.One,
1164            RegisterType.Category.Boolean,
1165            RegisterType.Category.Byte,
1166            RegisterType.Category.PosByte,
1167            RegisterType.Category.Short,
1168            RegisterType.Category.PosShort,
1169            RegisterType.Category.Char,
1170            RegisterType.Category.Integer,
1171            RegisterType.Category.Float,
1172            RegisterType.Category.Reference);
1173
1174    private static final EnumSet<RegisterType.Category> BooleanCategories = EnumSet.of(
1175            RegisterType.Category.Null,
1176            RegisterType.Category.One,
1177            RegisterType.Category.Boolean);
1178
1179    private void handleMove(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1180        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1181
1182        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
1183                validCategories);
1184
1185        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, sourceRegisterType);
1186    }
1187
1188    private void handleMoveResult(AnalyzedInstruction analyzedInstruction,
1189                                     EnumSet<RegisterType.Category> allowedCategories) {
1190
1191        //TODO: handle the case when the previous instruction is an odexed instruction
1192
1193        if (analyzedInstruction.instructionIndex == 0) {
1194            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " cannot be the first " +
1195                    "instruction in a method. It must occur after an invoke-*/fill-new-array instruction");
1196        }
1197
1198        AnalyzedInstruction previousInstruction = instructions.valueAt(analyzedInstruction.instructionIndex-1);
1199
1200        if (!previousInstruction.instruction.opcode.setsResult()) {
1201            throw new ValidationException(analyzedInstruction.instruction.opcode.name + " must occur after an " +
1202                    "invoke-*/fill-new-array instruction");
1203        }
1204
1205        //TODO: does dalvik allow a move-result after an invoke with a void return type?
1206        RegisterType resultRegisterType;
1207
1208        InstructionWithReference invokeInstruction = (InstructionWithReference)previousInstruction.instruction;
1209        Item item = invokeInstruction.getReferencedItem();
1210
1211        if (item instanceof MethodIdItem) {
1212            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem(
1213                    ((MethodIdItem)item).getPrototype().getReturnType());
1214        } else {
1215            assert item instanceof TypeIdItem;
1216            resultRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1217        }
1218
1219        if (!allowedCategories.contains(resultRegisterType.category)) {
1220            throw new ValidationException(String.format("Wrong move-result* instruction for return value %s",
1221                    resultRegisterType.toString()));
1222        }
1223
1224        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, resultRegisterType);
1225    }
1226
1227    private void handleMoveException(AnalyzedInstruction analyzedInstruction) {
1228        CodeItem.TryItem[] tries = encodedMethod.codeItem.getTries();
1229        int instructionAddress = getInstructionAddress(analyzedInstruction);
1230
1231        if (tries == null) {
1232            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1233        }
1234
1235        RegisterType exceptionType = null;
1236
1237        for (CodeItem.TryItem tryItem: encodedMethod.codeItem.getTries()) {
1238            if (tryItem.encodedCatchHandler.getCatchAllHandlerAddress() == instructionAddress) {
1239                exceptionType = RegisterType.getRegisterType(RegisterType.Category.Reference,
1240                        ClassPath.getClassDef("Ljava/lang/Throwable;"));
1241                break;
1242            }
1243            for (CodeItem.EncodedTypeAddrPair handler: tryItem.encodedCatchHandler.handlers) {
1244                if (handler.getHandlerAddress() == instructionAddress) {
1245                    exceptionType = RegisterType.getRegisterTypeForTypeIdItem(handler.exceptionType)
1246                            .merge(exceptionType);
1247                }
1248            }
1249        }
1250
1251        if (exceptionType == null) {
1252            throw new ValidationException("move-exception must be the first instruction in an exception handler block");
1253        }
1254
1255        //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)
1256        if (exceptionType.category != RegisterType.Category.Reference) {
1257            throw new ValidationException(String.format("Exception type %s is not a reference type",
1258                    exceptionType.toString()));
1259        }
1260
1261        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, exceptionType);
1262    }
1263
1264    private void handleReturnVoid(AnalyzedInstruction analyzedInstruction) {
1265        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1266        if (returnType.getTypeDescriptor().charAt(0) != 'V') {
1267            //TODO: could add which return-* variation should be used instead
1268            throw new ValidationException("Cannot use return-void with a non-void return type (" +
1269                returnType.getTypeDescriptor() + ")");
1270        }
1271    }
1272
1273    private void handleReturn(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1274        /*if (this.isInstanceConstructor()) {
1275            checkConstructorReturn(analyzedInstruction);
1276        }*/
1277
1278        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1279        int returnRegister = instruction.getRegisterA();
1280        RegisterType returnRegisterType = getAndCheckSourceRegister(analyzedInstruction, returnRegister,
1281                validCategories);
1282
1283        TypeIdItem returnType = encodedMethod.method.getPrototype().getReturnType();
1284        if (returnType.getTypeDescriptor().charAt(0) == 'V') {
1285            throw new ValidationException("Cannot use return with a void return type. Use return-void instead");
1286        }
1287
1288        RegisterType methodReturnRegisterType = RegisterType.getRegisterTypeForTypeIdItem(returnType);
1289
1290        if (!validCategories.contains(methodReturnRegisterType.category)) {
1291            //TODO: could add which return-* variation should be used instead
1292            throw new ValidationException(String.format("Cannot use %s with return type %s",
1293                    analyzedInstruction.instruction.opcode.name, returnType.getTypeDescriptor()));
1294        }
1295
1296        if (validCategories == ReferenceCategories) {
1297            if (methodReturnRegisterType.type.isInterface()) {
1298                if (returnRegisterType.category != RegisterType.Category.Null &&
1299                    !returnRegisterType.type.implementsInterface(methodReturnRegisterType.type)) {
1300                    //TODO: how to handle warnings?
1301                }
1302            } else {
1303                if (returnRegisterType.category == RegisterType.Category.Reference &&
1304                    !returnRegisterType.type.extendsClass(methodReturnRegisterType.type)) {
1305
1306                    throw new ValidationException(String.format("The return value in register v%d (%s) is not " +
1307                            "compatible with the method's return type %s", returnRegister,
1308                            returnRegisterType.type.getClassType(), methodReturnRegisterType.type.getClassType()));
1309                }
1310            }
1311        }
1312    }
1313
1314    private void handleConst(AnalyzedInstruction analyzedInstruction) {
1315        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
1316
1317        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(instruction.getLiteral());
1318
1319        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1320        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1321        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
1322    }
1323
1324    private void handleConstHigh16(AnalyzedInstruction analyzedInstruction) {
1325        LiteralInstruction instruction = (LiteralInstruction)analyzedInstruction.instruction;
1326
1327        long literalValue = instruction.getLiteral() << 16;
1328        RegisterType newDestinationRegisterType = RegisterType.getRegisterTypeForLiteral(literalValue);
1329
1330        //we assume that the literal value is a valid value for the given instruction type, because it's impossible
1331        //to store an invalid literal with the instruction. so we don't need to check the type of the literal
1332        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, newDestinationRegisterType);
1333    }
1334
1335    private void handleWideConst(AnalyzedInstruction analyzedInstruction) {
1336        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1337                RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1338    }
1339
1340    private void handleConstString(AnalyzedInstruction analyzedInstruction) {
1341        ClassPath.ClassDef stringClassDef = ClassPath.getClassDef("Ljava/lang/String;");
1342        RegisterType stringType = RegisterType.getRegisterType(RegisterType.Category.Reference, stringClassDef);
1343        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, stringType);
1344    }
1345
1346    private void handleConstClass(AnalyzedInstruction analyzedInstruction) {
1347        ClassPath.ClassDef classClassDef = ClassPath.getClassDef("Ljava/lang/Class;");
1348        RegisterType classType = RegisterType.getRegisterType(RegisterType.Category.Reference, classClassDef);
1349
1350        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1351        Item item = instruction.getReferencedItem();
1352        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1353
1354        //TODO: need to check class access
1355        //make sure the referenced class is resolvable
1356        ClassPath.getClassDef((TypeIdItem)item);
1357
1358        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, classType);
1359    }
1360
1361    private void handleMonitor(AnalyzedInstruction analyzedInstruction) {
1362        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1363        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), ReferenceCategories);
1364    }
1365
1366    private void handleCheckCast(AnalyzedInstruction analyzedInstruction) {
1367        {
1368            //ensure the "source" register is a reference type
1369            SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1370
1371            RegisterType registerType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
1372                    ReferenceCategories);
1373        }
1374
1375        {
1376            //resolve and verify the class that we're casting to
1377            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1378
1379            Item item = instruction.getReferencedItem();
1380            assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1381
1382            //TODO: need to check class access
1383            RegisterType castRegisterType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1384            if (castRegisterType.category != RegisterType.Category.Reference) {
1385                //TODO: verify that dalvik allows a non-reference type..
1386                //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)
1387            }
1388
1389            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, castRegisterType);
1390        }
1391    }
1392
1393    private void handleInstanceOf(AnalyzedInstruction analyzedInstruction) {
1394        {
1395            //ensure the register that is being checks is a reference type
1396            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1397
1398            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), ReferenceCategories);
1399        }
1400
1401        {
1402            //resolve and verify the class that we're checking against
1403            InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1404
1405            Item item = instruction.getReferencedItem();
1406            assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1407            RegisterType registerType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1408            if (registerType.category != RegisterType.Category.Reference) {
1409                throw new ValidationException(String.format("Cannot use instance-of with a non-reference type %s",
1410                        registerType.toString()));
1411            }
1412
1413            //TODO: is it valid to use an array type?
1414
1415            //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.
1416            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1417                    RegisterType.getRegisterType(RegisterType.Category.Boolean, null));
1418        }
1419    }
1420
1421    private void handleArrayLength(AnalyzedInstruction analyzedInstruction) {
1422        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1423
1424        int arrayRegisterNumber = instruction.getRegisterB();
1425        RegisterType arrayRegisterType = getAndCheckSourceRegister(analyzedInstruction, arrayRegisterNumber,
1426                ReferenceCategories);
1427
1428        if (arrayRegisterType.type != null) {
1429            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1430                throw new ValidationException(String.format("Cannot use array-length with non-array type %s",
1431                        arrayRegisterType.type.getClassType()));
1432            }
1433            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1434        }
1435
1436        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1437                RegisterType.getRegisterType(RegisterType.Category.Integer, null));
1438    }
1439
1440    private void handleNewInstance(AnalyzedInstruction analyzedInstruction) {
1441        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1442
1443        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1444        RegisterType destRegisterType = analyzedInstruction.postRegisterMap[register];
1445        if (destRegisterType.category != RegisterType.Category.Unknown) {
1446            assert destRegisterType.category == RegisterType.Category.UninitRef;
1447
1448            //the "post-instruction" destination register will only be set if we've gone over
1449            //this instruction at least once before. If this is the case, then we need to check
1450            //all the other registers, and make sure that none of them contain the same
1451            //uninitialized reference that is in the destination register.
1452
1453            for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
1454                if (i==register) {
1455                    continue;
1456                }
1457
1458                if (analyzedInstruction.getPreInstructionRegisterType(i) == destRegisterType) {
1459                    throw new ValidationException(String.format("Register v%d contains an uninitialized reference " +
1460                            "that was created by this new-instance instruction.", i));
1461                }
1462            }
1463
1464            return;
1465        }
1466
1467        Item item = instruction.getReferencedItem();
1468        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1469
1470        //TODO: need to check class access
1471        RegisterType classType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1472        if (classType.category != RegisterType.Category.Reference) {
1473            throw new ValidationException(String.format("Cannot use new-instance with a non-reference type %s",
1474                    classType.toString()));
1475        }
1476
1477        if (((TypeIdItem)item).getTypeDescriptor().charAt(0) == '[') {
1478            throw new ValidationException("Cannot use array type \"" + ((TypeIdItem)item).getTypeDescriptor() +
1479                    "\" with new-instance. Use new-array instead.");
1480        }
1481
1482        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1483                RegisterType.getUnitializedReference(classType.type));
1484    }
1485
1486    private void handleNewArray(AnalyzedInstruction analyzedInstruction) {
1487        {
1488            TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1489            getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
1490        }
1491
1492        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1493
1494        Item item = instruction.getReferencedItem();
1495        assert item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1496
1497        RegisterType arrayType = RegisterType.getRegisterTypeForTypeIdItem((TypeIdItem)item);
1498        assert arrayType.type instanceof ClassPath.ArrayClassDef;
1499
1500        if (arrayType.category != RegisterType.Category.Reference) {
1501            throw new ValidationException(String.format("Cannot use new-array with a non-reference type %s",
1502                    arrayType.toString()));
1503        }
1504        if (arrayType.type.getClassType().charAt(0) != '[') {
1505            throw new ValidationException("Cannot use non-array type \"" + arrayType.type.getClassType() +
1506                    "\" with new-array. Use new-instance instead.");
1507        }
1508
1509        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, arrayType);
1510    }
1511
1512    private static interface RegisterIterator {
1513        int getRegister();
1514        boolean moveNext();
1515        int getCount();
1516        boolean pastEnd();
1517    }
1518
1519    private static class Format35cRegisterIterator implements RegisterIterator {
1520        private final int registerCount;
1521        private final int[] registers;
1522        private int currentRegister = 0;
1523
1524        public Format35cRegisterIterator(FiveRegisterInstruction instruction) {
1525            registerCount = instruction.getRegCount();
1526            registers = new int[]{instruction.getRegisterD(), instruction.getRegisterE(),
1527                                  instruction.getRegisterF(), instruction.getRegisterG(),
1528                                  instruction.getRegisterA()};
1529        }
1530
1531        public int getRegister() {
1532            return registers[currentRegister];
1533        }
1534
1535        public boolean moveNext() {
1536            currentRegister++;
1537            return !pastEnd();
1538        }
1539
1540        public int getCount() {
1541            return registerCount;
1542        }
1543
1544        public boolean pastEnd() {
1545            return currentRegister >= registerCount;
1546        }
1547    }
1548
1549    private static class Format3rcRegisterIterator implements RegisterIterator {
1550        private final int startRegister;
1551        private final int registerCount;
1552        private int currentRegister = 0;
1553
1554        public Format3rcRegisterIterator(RegisterRangeInstruction instruction) {
1555            startRegister = instruction.getStartRegister();
1556            registerCount = instruction.getRegCount();
1557        }
1558
1559        public int getRegister() {
1560            return startRegister + currentRegister;
1561        }
1562
1563        public boolean moveNext() {
1564            currentRegister++;
1565            return !pastEnd();
1566        }
1567
1568        public int getCount() {
1569            return registerCount;
1570        }
1571
1572        public boolean pastEnd() {
1573            return currentRegister >= registerCount;
1574        }
1575    }
1576
1577    private void handleFilledNewArrayCommon(AnalyzedInstruction analyzedInstruction,
1578                                               RegisterIterator registerIterator) {
1579        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
1580
1581        RegisterType arrayType;
1582        RegisterType arrayImmediateElementType;
1583
1584        Item item = instruction.getReferencedItem();
1585        assert  item.getItemType() == ItemType.TYPE_TYPE_ID_ITEM;
1586
1587        ClassPath.ClassDef classDef = ClassPath.getClassDef((TypeIdItem)item);
1588
1589        if (classDef.getClassType().charAt(0) != '[') {
1590            throw new ValidationException("Cannot use non-array type \"" + classDef.getClassType() +
1591                "\" with new-array. Use new-instance instead.");
1592        }
1593
1594        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)classDef;
1595        arrayType = RegisterType.getRegisterType(RegisterType.Category.Reference, classDef);
1596        arrayImmediateElementType = RegisterType.getRegisterTypeForType(
1597                arrayClassDef.getImmediateElementClass().getClassType());
1598        String baseElementType = arrayClassDef.getBaseElementClass().getClassType();
1599        if (baseElementType.charAt(0) == 'J' || baseElementType.charAt(0) == 'D') {
1600            throw new ValidationException("Cannot use filled-new-array to create an array of wide values " +
1601                    "(long or double)");
1602        }
1603
1604        do {
1605            int register = registerIterator.getRegister();
1606            RegisterType elementType = analyzedInstruction.getPreInstructionRegisterType(register);
1607            assert elementType != null;
1608
1609            if (!elementType.canBeAssignedTo(arrayImmediateElementType)) {
1610                throw new ValidationException("Register v" + Integer.toString(register) + " is of type " +
1611                        elementType.toString() + " and is incompatible with the array type " +
1612                        arrayType.type.getClassType());
1613            }
1614        } while (registerIterator.moveNext());
1615    }
1616
1617    private void handleFilledNewArray(AnalyzedInstruction analyzedInstruction) {
1618        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
1619        handleFilledNewArrayCommon(analyzedInstruction, new Format35cRegisterIterator(instruction));
1620    }
1621
1622    private void handleFilledNewArrayRange(AnalyzedInstruction analyzedInstruction) {
1623        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
1624
1625        //instruction.getStartRegister() and instruction.getRegCount() both return an int value, but are actually
1626        //unsigned 16 bit values, so we don't have to worry about overflowing an int when adding them together
1627        if (instruction.getStartRegister() + instruction.getRegCount() >= 1<<16) {
1628            throw new ValidationException(String.format("Invalid register range {v%d .. v%d}. The ending register " +
1629                    "is larger than the largest allowed register of v65535.",
1630                    instruction.getStartRegister(),
1631                    instruction.getStartRegister() + instruction.getRegCount() - 1));
1632        }
1633
1634        handleFilledNewArrayCommon(analyzedInstruction, new Format3rcRegisterIterator(instruction));
1635    }
1636
1637    private void handleFillArrayData(AnalyzedInstruction analyzedInstruction) {
1638        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1639
1640        int register = instruction.getRegisterA();
1641        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1642        assert registerType != null;
1643
1644        if (registerType.category == RegisterType.Category.Null) {
1645            return;
1646        }
1647
1648        if (registerType.category != RegisterType.Category.Reference) {
1649            throw new ValidationException(String.format("Cannot use fill-array-data with non-array register v%d of " +
1650                    "type %s", register, registerType.toString()));
1651        }
1652
1653        assert registerType.type instanceof ClassPath.ArrayClassDef;
1654        ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)registerType.type;
1655
1656        if (arrayClassDef.getArrayDimensions() != 1) {
1657            throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can only " +
1658                    "be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1659        }
1660
1661        int elementWidth;
1662        switch (arrayClassDef.getBaseElementClass().getClassType().charAt(0)) {
1663            case 'Z':
1664            case 'B':
1665                elementWidth = 1;
1666                break;
1667            case 'C':
1668            case 'S':
1669                elementWidth = 2;
1670                break;
1671            case 'I':
1672            case 'F':
1673                elementWidth = 4;
1674                break;
1675            case 'J':
1676            case 'D':
1677                elementWidth = 8;
1678                break;
1679            default:
1680                throw new ValidationException(String.format("Cannot use fill-array-data with array type %s. It can " +
1681                        "only be used with a one-dimensional array of primitives.", arrayClassDef.getClassType()));
1682        }
1683
1684
1685        int arrayDataAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1686        int arrayDataCodeAddress = getInstructionAddress(analyzedInstruction) + arrayDataAddressOffset;
1687        AnalyzedInstruction arrayDataInstruction = this.instructions.get(arrayDataCodeAddress);
1688        if (arrayDataInstruction == null || arrayDataInstruction.instruction.getFormat() != Format.ArrayData) {
1689            throw new ValidationException(String.format("Could not find an array data structure at code address 0x%x",
1690                    arrayDataCodeAddress));
1691        }
1692
1693        ArrayDataPseudoInstruction arrayDataPseudoInstruction =
1694                (ArrayDataPseudoInstruction)arrayDataInstruction.instruction;
1695
1696        if (elementWidth != arrayDataPseudoInstruction.getElementWidth()) {
1697            throw new ValidationException(String.format("The array data at code address 0x%x does not have the " +
1698                    "correct element width for array type %s. Expecting element width %d, got element width %d.",
1699                    arrayDataCodeAddress, arrayClassDef.getClassType(), elementWidth,
1700                    arrayDataPseudoInstruction.getElementWidth()));
1701        }
1702    }
1703
1704    private void handleThrow(AnalyzedInstruction analyzedInstruction) {
1705        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1706
1707        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(register);
1708        assert registerType != null;
1709
1710        if (registerType.category == RegisterType.Category.Null) {
1711            return;
1712        }
1713
1714        if (registerType.category != RegisterType.Category.Reference) {
1715            throw new ValidationException(String.format("Cannot use throw with non-reference type %s in register v%d",
1716                    registerType.toString(), register));
1717        }
1718
1719        assert registerType.type != null;
1720
1721        if (!registerType.type.extendsClass(ClassPath.getClassDef("Ljava/lang/Throwable;"))) {
1722            throw new ValidationException(String.format("Cannot use throw with non-throwable type %s in register v%d",
1723                    registerType.type.getClassType(), register));
1724        }
1725    }
1726
1727    private void handleSwitch(AnalyzedInstruction analyzedInstruction, Format expectedSwitchDataFormat) {
1728        int register = ((SingleRegisterInstruction)analyzedInstruction.instruction).getRegisterA();
1729        int switchCodeAddressOffset = ((OffsetInstruction)analyzedInstruction.instruction).getTargetAddressOffset();
1730
1731        getAndCheckSourceRegister(analyzedInstruction, register, Primitive32BitCategories);
1732
1733        int switchDataCodeAddress = this.getInstructionAddress(analyzedInstruction) + switchCodeAddressOffset;
1734        AnalyzedInstruction switchDataAnalyzedInstruction = instructions.get(switchDataCodeAddress);
1735
1736        if (switchDataAnalyzedInstruction == null ||
1737            switchDataAnalyzedInstruction.instruction.getFormat() != expectedSwitchDataFormat) {
1738            throw new ValidationException(String.format("There is no %s structure at code address 0x%x",
1739                    expectedSwitchDataFormat.name(), switchDataCodeAddress));
1740        }
1741    }
1742
1743    private void handleFloatWideCmp(AnalyzedInstruction analyzedInstruction, EnumSet validCategories) {
1744        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1745
1746        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validCategories);
1747        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), validCategories);
1748
1749        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1750                RegisterType.getRegisterType(RegisterType.Category.Byte, null));
1751    }
1752
1753    private void handleIfEqNe(AnalyzedInstruction analyzedInstruction) {
1754        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1755
1756        RegisterType registerType1 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1757        assert registerType1 != null;
1758
1759        RegisterType registerType2 = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1760        assert registerType2 != null;
1761
1762        if (!(
1763                (ReferenceCategories.contains(registerType1.category) &&
1764                ReferenceCategories.contains(registerType2.category))
1765                    ||
1766                (Primitive32BitCategories.contains(registerType1.category) &&
1767                Primitive32BitCategories.contains(registerType2.category))
1768              )) {
1769
1770            throw new ValidationException(String.format("%s cannot be used on registers of dissimilar types %s and " +
1771                    "%s. They must both be a reference type or a primitive 32 bit type.",
1772                    analyzedInstruction.instruction.opcode.name, registerType1.toString(), registerType2.toString()));
1773        }
1774    }
1775
1776    private void handleIf(AnalyzedInstruction analyzedInstruction) {
1777        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
1778
1779        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
1780        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), Primitive32BitCategories);
1781    }
1782
1783    private void handleIfEqzNez(AnalyzedInstruction analyzedInstruction) {
1784        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1785
1786        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
1787                ReferenceAndPrimitive32BitCategories);
1788    }
1789
1790    private void handleIfz(AnalyzedInstruction analyzedInstruction) {
1791        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
1792
1793        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), Primitive32BitCategories);
1794    }
1795
1796    private void handle32BitPrimitiveAget(AnalyzedInstruction analyzedInstruction,
1797                                             RegisterType.Category instructionCategory) {
1798        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1799
1800        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1801
1802        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1803        assert arrayRegisterType != null;
1804
1805        if (arrayRegisterType.category != RegisterType.Category.Null) {
1806            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1807                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1808                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1809            }
1810
1811            assert arrayRegisterType.type != null;
1812            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1813                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1814                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1815            }
1816
1817            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1818            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1819
1820            if (arrayClassDef.getArrayDimensions() != 1) {
1821                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1822                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1823            }
1824
1825            RegisterType arrayBaseType =
1826                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1827            if (!checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1828                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1829                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1830                        arrayRegisterType.type.getClassType()));
1831            }
1832        }
1833
1834        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1835                RegisterType.getRegisterType(instructionCategory, null));
1836    }
1837
1838    private void handleAgetWide(AnalyzedInstruction analyzedInstruction) {
1839        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1840
1841        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1842
1843        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1844        assert arrayRegisterType != null;
1845
1846        if (arrayRegisterType.category != RegisterType.Category.Null) {
1847            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1848                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1849                        arrayRegisterType.category.toString()));
1850            }
1851
1852            assert arrayRegisterType.type != null;
1853            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1854                throw new ValidationException(String.format("Cannot use aget-wide with non-array type %s",
1855                        arrayRegisterType.type.getClassType()));
1856            }
1857
1858            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1859            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1860
1861            if (arrayClassDef.getArrayDimensions() != 1) {
1862                throw new ValidationException(String.format("Cannot use aget-wide with multi-dimensional array type %s",
1863                        arrayRegisterType.type.getClassType()));
1864            }
1865
1866            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1867            if (arrayBaseType == 'J') {
1868                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1869                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1870            } else if (arrayBaseType == 'D') {
1871                setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1872                        RegisterType.getRegisterType(RegisterType.Category.DoubleLo, null));
1873            } else {
1874                throw new ValidationException(String.format("Cannot use aget-wide with array type %s. Incorrect " +
1875                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1876            }
1877        } else {
1878            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1879                        RegisterType.getRegisterType(RegisterType.Category.LongLo, null));
1880        }
1881    }
1882
1883    private void handleAgetObject(AnalyzedInstruction analyzedInstruction) {
1884        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1885
1886        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1887
1888        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1889        assert arrayRegisterType != null;
1890
1891        if (arrayRegisterType.category != RegisterType.Category.Null) {
1892            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1893                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1894                        arrayRegisterType.category.toString()));
1895            }
1896
1897            assert arrayRegisterType.type != null;
1898            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1899                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
1900                        arrayRegisterType.type.getClassType()));
1901            }
1902
1903            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1904            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1905
1906            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
1907            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
1908            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
1909                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
1910                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
1911            }
1912
1913            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1914                    RegisterType.getRegisterType(RegisterType.Category.Reference, elementClassDef));
1915        } else {
1916            setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
1917                    RegisterType.getRegisterType(RegisterType.Category.Null, null));
1918        }
1919    }
1920
1921    private void handle32BitPrimitiveAput(AnalyzedInstruction analyzedInstruction,
1922                                             RegisterType.Category instructionCategory) {
1923        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1924
1925        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1926
1927        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
1928        assert sourceRegisterType != null;
1929        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
1930        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
1931            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
1932                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
1933        }
1934
1935
1936        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1937        assert arrayRegisterType != null;
1938
1939        if (arrayRegisterType.category != RegisterType.Category.Null) {
1940            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1941                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1942                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.category.toString()));
1943            }
1944
1945            assert arrayRegisterType.type != null;
1946            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1947                throw new ValidationException(String.format("Cannot use %s with non-array type %s",
1948                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1949            }
1950
1951            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1952            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1953
1954            if (arrayClassDef.getArrayDimensions() != 1) {
1955                throw new ValidationException(String.format("Cannot use %s with multi-dimensional array type %s",
1956                        analyzedInstruction.instruction.opcode.name, arrayRegisterType.type.getClassType()));
1957            }
1958
1959            RegisterType arrayBaseType =
1960                    RegisterType.getRegisterTypeForType(arrayClassDef.getBaseElementClass().getClassType());
1961            if (!checkArrayFieldAssignment(arrayBaseType.category, instructionCategory)) {
1962                throw new ValidationException(String.format("Cannot use %s with array type %s. Incorrect array type " +
1963                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
1964                        arrayRegisterType.type.getClassType()));
1965            }
1966        }
1967    }
1968
1969    private void handleAputWide(AnalyzedInstruction analyzedInstruction) {
1970        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
1971
1972        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
1973        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
1974
1975        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
1976        assert arrayRegisterType != null;
1977
1978        if (arrayRegisterType.category != RegisterType.Category.Null) {
1979            if (arrayRegisterType.category != RegisterType.Category.Reference) {
1980                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1981                        arrayRegisterType.category.toString()));
1982            }
1983
1984            assert arrayRegisterType.type != null;
1985            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
1986                throw new ValidationException(String.format("Cannot use aput-wide with non-array type %s",
1987                        arrayRegisterType.type.getClassType()));
1988            }
1989
1990            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
1991            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
1992
1993            if (arrayClassDef.getArrayDimensions() != 1) {
1994                throw new ValidationException(String.format("Cannot use aput-wide with multi-dimensional array type %s",
1995                        arrayRegisterType.type.getClassType()));
1996            }
1997
1998            char arrayBaseType = arrayClassDef.getBaseElementClass().getClassType().charAt(0);
1999            if (arrayBaseType != 'J' && arrayBaseType != 'D') {
2000                throw new ValidationException(String.format("Cannot use aput-wide with array type %s. Incorrect " +
2001                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2002            }
2003        }
2004    }
2005
2006    private void handleAputObject(AnalyzedInstruction analyzedInstruction) {
2007        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2008
2009        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(), Primitive32BitCategories);
2010
2011        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2012        assert sourceRegisterType != null;
2013
2014        //TODO: ensure sourceRegisterType is a Reference type?
2015
2016        RegisterType arrayRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterB());
2017        assert arrayRegisterType != null;
2018
2019        if (arrayRegisterType.category != RegisterType.Category.Null) {
2020            //don't check the source type against the array type, just make sure it is an array of reference types
2021
2022            if (arrayRegisterType.category != RegisterType.Category.Reference) {
2023                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2024                        arrayRegisterType.category.toString()));
2025            }
2026
2027            assert arrayRegisterType.type != null;
2028            if (arrayRegisterType.type.getClassType().charAt(0) != '[') {
2029                throw new ValidationException(String.format("Cannot use aget-object with non-array type %s",
2030                        arrayRegisterType.type.getClassType()));
2031            }
2032
2033            assert arrayRegisterType.type instanceof ClassPath.ArrayClassDef;
2034            ClassPath.ArrayClassDef arrayClassDef = (ClassPath.ArrayClassDef)arrayRegisterType.type;
2035
2036            ClassPath.ClassDef elementClassDef = arrayClassDef.getImmediateElementClass();
2037            char elementTypePrefix = elementClassDef.getClassType().charAt(0);
2038            if (elementTypePrefix != 'L' && elementTypePrefix != '[') {
2039                throw new ValidationException(String.format("Cannot use aget-object with array type %s. Incorrect " +
2040                        "array type for the instruction.", arrayRegisterType.type.getClassType()));
2041            }
2042        }
2043    }
2044
2045    private void handle32BitPrimitiveIget(AnalyzedInstruction analyzedInstruction,
2046                                             RegisterType.Category instructionCategory) {
2047        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2048
2049        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2050                ReferenceOrUninitThisCategories);
2051
2052        //TODO: check access
2053        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2054        assert referencedItem instanceof FieldIdItem;
2055        FieldIdItem field = (FieldIdItem)referencedItem;
2056
2057        if (objectRegisterType.category != RegisterType.Category.Null &&
2058            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2059            throw new ValidationException(String.format("Cannot access field %s through type %s",
2060                    field.getFieldString(), objectRegisterType.type.getClassType()));
2061        }
2062
2063        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2064
2065        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2066                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2067                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2068                        field.getFieldString()));
2069        }
2070
2071        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2072                RegisterType.getRegisterType(instructionCategory, null));
2073    }
2074
2075    private void handleIgetWide(AnalyzedInstruction analyzedInstruction) {
2076        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2077
2078        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2079                ReferenceOrUninitThisCategories);
2080
2081        //TODO: check access
2082        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2083        assert referencedItem instanceof FieldIdItem;
2084        FieldIdItem field = (FieldIdItem)referencedItem;
2085
2086        if (objectRegisterType.category != RegisterType.Category.Null &&
2087            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2088            throw new ValidationException(String.format("Cannot access field %s through type %s",
2089                    field.getFieldString(), objectRegisterType.type.getClassType()));
2090        }
2091
2092        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2093
2094        if (!WideLowCategories.contains(fieldType.category)) {
2095            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2096                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2097                    field.getFieldString()));
2098        }
2099
2100        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2101    }
2102
2103    private void handleIgetObject(AnalyzedInstruction analyzedInstruction) {
2104        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2105
2106        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2107                ReferenceOrUninitThisCategories);
2108
2109        //TODO: check access
2110        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2111        assert referencedItem instanceof FieldIdItem;
2112        FieldIdItem field = (FieldIdItem)referencedItem;
2113
2114        if (objectRegisterType.category != RegisterType.Category.Null &&
2115            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2116            throw new ValidationException(String.format("Cannot access field %s through type %s",
2117                    field.getFieldString(), objectRegisterType.type.getClassType()));
2118        }
2119
2120        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2121
2122        if (fieldType.category != RegisterType.Category.Reference) {
2123            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2124                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2125                        field.getFieldString()));
2126        }
2127
2128        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2129    }
2130
2131    private void handle32BitPrimitiveIput(AnalyzedInstruction analyzedInstruction,
2132                                             RegisterType.Category instructionCategory) {
2133        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2134
2135        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2136                ReferenceOrUninitThisCategories);
2137
2138        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2139        assert sourceRegisterType != null;
2140
2141        //per CodeVerify.c in dalvik:
2142        //java generates synthetic functions that write byte values into boolean fields
2143        if (sourceRegisterType.category == RegisterType.Category.Byte &&
2144            instructionCategory == RegisterType.Category.Boolean) {
2145
2146            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
2147        }
2148
2149        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2150        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2151            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2152                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2153        }
2154
2155
2156        //TODO: check access
2157        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2158        assert referencedItem instanceof FieldIdItem;
2159        FieldIdItem field = (FieldIdItem)referencedItem;
2160
2161        if (objectRegisterType.category != RegisterType.Category.Null &&
2162            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2163            throw new ValidationException(String.format("Cannot access field %s through type %s",
2164                    field.getFieldString(), objectRegisterType.type.getClassType()));
2165        }
2166
2167        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2168
2169        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2170                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2171                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2172                        field.getFieldString()));
2173        }
2174    }
2175
2176    private void handleIputWide(AnalyzedInstruction analyzedInstruction) {
2177        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2178
2179        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2180                ReferenceOrUninitThisCategories);
2181
2182        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2183
2184        //TODO: check access
2185        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2186        assert referencedItem instanceof FieldIdItem;
2187        FieldIdItem field = (FieldIdItem)referencedItem;
2188
2189        if (objectRegisterType.category != RegisterType.Category.Null &&
2190                !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2191            throw new ValidationException(String.format("Cannot access field %s through type %s",
2192                    field.getFieldString(), objectRegisterType.type.getClassType()));
2193        }
2194
2195        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2196
2197        if (!WideLowCategories.contains(fieldType.category)) {
2198            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2199                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2200                    field.getFieldString()));
2201        }
2202    }
2203
2204    private void handleIputObject(AnalyzedInstruction analyzedInstruction) {
2205        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2206
2207        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2208                ReferenceOrUninitThisCategories);
2209
2210        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2211                ReferenceCategories);
2212
2213        //TODO: check access
2214        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2215        assert referencedItem instanceof FieldIdItem;
2216        FieldIdItem field = (FieldIdItem)referencedItem;
2217
2218        if (objectRegisterType.category != RegisterType.Category.Null &&
2219            !objectRegisterType.type.extendsClass(ClassPath.getClassDef(field.getContainingClass()))) {
2220            throw new ValidationException(String.format("Cannot access field %s through type %s",
2221                    field.getFieldString(), objectRegisterType.type.getClassType()));
2222        }
2223
2224        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2225
2226        if (fieldType.category != RegisterType.Category.Reference) {
2227            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2228                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2229                        field.getFieldString()));
2230        }
2231
2232        if (sourceRegisterType.category != RegisterType.Category.Null &&
2233            !fieldType.type.isInterface() &&
2234            !sourceRegisterType.type.extendsClass(fieldType.type)) {
2235
2236            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
2237                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
2238        }
2239    }
2240
2241    private void handle32BitPrimitiveSget(AnalyzedInstruction analyzedInstruction,
2242                                             RegisterType.Category instructionCategory) {
2243        //TODO: check access
2244        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2245        assert referencedItem instanceof FieldIdItem;
2246        FieldIdItem field = (FieldIdItem)referencedItem;
2247
2248        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2249
2250        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2251                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2252                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2253                        field.getFieldString()));
2254        }
2255
2256        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2257                RegisterType.getRegisterType(instructionCategory, null));
2258    }
2259
2260    private void handleSgetWide(AnalyzedInstruction analyzedInstruction) {
2261        //TODO: check access
2262        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2263        assert referencedItem instanceof FieldIdItem;
2264        FieldIdItem field = (FieldIdItem)referencedItem;
2265
2266        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2267
2268
2269        if (fieldType.category != RegisterType.Category.LongLo &&
2270            fieldType.category != RegisterType.Category.DoubleLo) {
2271
2272            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2273                    "for the instruction.", analyzedInstruction.instruction.opcode.name,
2274                    field.getFieldString()));
2275        }
2276
2277        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2278    }
2279
2280    private void handleSgetObject(AnalyzedInstruction analyzedInstruction) {
2281        //TODO: check access
2282        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2283        assert referencedItem instanceof FieldIdItem;
2284        FieldIdItem field = (FieldIdItem)referencedItem;
2285
2286        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2287
2288        if (fieldType.category != RegisterType.Category.Reference) {
2289                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2290                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2291                        field.getFieldString()));
2292        }
2293
2294        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction, fieldType);
2295    }
2296
2297    private void handle32BitPrimitiveSput(AnalyzedInstruction analyzedInstruction,
2298                                             RegisterType.Category instructionCategory) {
2299        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2300
2301        RegisterType sourceRegisterType = analyzedInstruction.getPreInstructionRegisterType(instruction.getRegisterA());
2302        assert sourceRegisterType != null;
2303
2304        //per CodeVerify.c in dalvik:
2305        //java generates synthetic functions that write byte values into boolean fields
2306        if (sourceRegisterType.category == RegisterType.Category.Byte &&
2307            instructionCategory == RegisterType.Category.Boolean) {
2308
2309            sourceRegisterType = RegisterType.getRegisterType(RegisterType.Category.Boolean, null);
2310        }
2311
2312        RegisterType instructionRegisterType = RegisterType.getRegisterType(instructionCategory, null);
2313        if (!sourceRegisterType.canBeAssignedTo(instructionRegisterType)) {
2314            throw new ValidationException(String.format("Cannot use %s with source register type %s.",
2315                    analyzedInstruction.instruction.opcode.name, sourceRegisterType.toString()));
2316        }
2317
2318        //TODO: check access
2319        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2320        assert referencedItem instanceof FieldIdItem;
2321        FieldIdItem field = (FieldIdItem)referencedItem;
2322
2323        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2324
2325        if (!checkArrayFieldAssignment(fieldType.category, instructionCategory)) {
2326                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2327                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2328                        field.getFieldString()));
2329        }
2330    }
2331
2332    private void handleSputWide(AnalyzedInstruction analyzedInstruction) {
2333        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2334
2335
2336        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(), WideLowCategories);
2337
2338        //TODO: check access
2339        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2340        assert referencedItem instanceof FieldIdItem;
2341        FieldIdItem field = (FieldIdItem)referencedItem;
2342
2343        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2344
2345        if (!WideLowCategories.contains(fieldType.category)) {
2346                throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2347                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2348                        field.getFieldString()));
2349        }
2350    }
2351
2352    private void handleSputObject(AnalyzedInstruction analyzedInstruction) {
2353        SingleRegisterInstruction instruction = (SingleRegisterInstruction)analyzedInstruction.instruction;
2354
2355        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2356                ReferenceCategories);
2357
2358        //TODO: check access
2359        Item referencedItem = ((InstructionWithReference)analyzedInstruction.instruction).getReferencedItem();
2360        assert referencedItem instanceof FieldIdItem;
2361        FieldIdItem field = (FieldIdItem)referencedItem;
2362
2363        RegisterType fieldType = RegisterType.getRegisterTypeForTypeIdItem(field.getFieldType());
2364
2365        if (fieldType.category != RegisterType.Category.Reference) {
2366            throw new ValidationException(String.format("Cannot use %s with field %s. Incorrect field type " +
2367                        "for the instruction.", analyzedInstruction.instruction.opcode.name,
2368                        field.getFieldString()));
2369        }
2370
2371        if (sourceRegisterType.category != RegisterType.Category.Null &&
2372            !fieldType.type.isInterface() &&
2373            !sourceRegisterType.type.extendsClass(fieldType.type)) {
2374
2375            throw new ValidationException(String.format("Cannot store a value of type %s into a field of type %s",
2376                    sourceRegisterType.type.getClassType(), fieldType.type.getClassType()));
2377        }
2378    }
2379
2380    private void handleInvoke(AnalyzedInstruction analyzedInstruction, int invokeType) {
2381        FiveRegisterInstruction instruction = (FiveRegisterInstruction)analyzedInstruction.instruction;
2382        handleInvokeCommon(analyzedInstruction, false, invokeType, new Format35cRegisterIterator(instruction));
2383    }
2384
2385    private void handleInvokeRange(AnalyzedInstruction analyzedInstruction, int invokeType) {
2386        RegisterRangeInstruction instruction = (RegisterRangeInstruction)analyzedInstruction.instruction;
2387        handleInvokeCommon(analyzedInstruction, true, invokeType, new Format3rcRegisterIterator(instruction));
2388    }
2389
2390    private static final int INVOKE_VIRTUAL = 0x01;
2391    private static final int INVOKE_SUPER = 0x02;
2392    private static final int INVOKE_DIRECT = 0x04;
2393    private static final int INVOKE_INTERFACE = 0x08;
2394    private static final int INVOKE_STATIC = 0x10;
2395
2396    private void handleInvokeCommon(AnalyzedInstruction analyzedInstruction, boolean isRange, int invokeType,
2397                                       RegisterIterator registers) {
2398        InstructionWithReference instruction = (InstructionWithReference)analyzedInstruction.instruction;
2399
2400        //TODO: check access
2401
2402        Item item = instruction.getReferencedItem();
2403        assert item.getItemType() == ItemType.TYPE_METHOD_ID_ITEM;
2404        MethodIdItem methodIdItem = (MethodIdItem)item;
2405
2406        TypeIdItem methodClass = methodIdItem.getContainingClass();
2407        boolean isInit = false;
2408
2409        if (methodIdItem.getMethodName().getStringValue().charAt(0) == '<') {
2410            if ((invokeType & INVOKE_DIRECT) != 0) {
2411                isInit = true;
2412            } else {
2413                throw new ValidationException(String.format("Cannot call constructor %s with %s",
2414                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name));
2415            }
2416        }
2417
2418        ClassPath.ClassDef methodClassDef = ClassPath.getClassDef(methodClass);
2419        if ((invokeType & INVOKE_INTERFACE) != 0) {
2420            if (!methodClassDef.isInterface()) {
2421                throw new ValidationException(String.format("Cannot call method %s with %s. %s is not an interface " +
2422                        "class.", methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
2423                        methodClassDef.getClassType()));
2424            }
2425        } else {
2426            if (methodClassDef.isInterface()) {
2427                throw new ValidationException(String.format("Cannot call method %s with %s. %s is an interface class." +
2428                        " Use invoke-interface or invoke-interface/range instead.", methodIdItem.getMethodString(),
2429                        analyzedInstruction.instruction.opcode.name, methodClassDef.getClassType()));
2430            }
2431        }
2432
2433        if ((invokeType & INVOKE_SUPER) != 0) {
2434            ClassPath.ClassDef currentMethodClassDef = ClassPath.getClassDef(encodedMethod.method.getContainingClass());
2435            if (currentMethodClassDef.getSuperclass() == null) {
2436                throw new ValidationException(String.format("Cannot call method %s with %s. %s has no superclass",
2437                        methodIdItem.getMethodString(), analyzedInstruction.instruction.opcode.name,
2438                        methodClassDef.getSuperclass().getClassType()));
2439            }
2440
2441            if (!currentMethodClassDef.getSuperclass().extendsClass(methodClassDef)) {
2442                throw new ValidationException(String.format("Cannot call method %s with %s. %s is not an ancestor " +
2443                        "of the current class %s", methodIdItem.getMethodString(),
2444                        analyzedInstruction.instruction.opcode.name, methodClass.getTypeDescriptor(),
2445                        encodedMethod.method.getContainingClass().getTypeDescriptor()));
2446            }
2447
2448            if (!currentMethodClassDef.getSuperclass().hasVirtualMethod(methodIdItem.getVirtualMethodString())) {
2449                throw new ValidationException(String.format("Cannot call method %s with %s. The superclass %s has" +
2450                        "no such method", methodIdItem.getMethodString(),
2451                        analyzedInstruction.instruction.opcode.name, methodClassDef.getSuperclass().getClassType()));
2452            }
2453        }
2454
2455        assert isRange || registers.getCount() <= 5;
2456
2457        TypeListItem typeListItem = methodIdItem.getPrototype().getParameters();
2458        int methodParameterRegisterCount;
2459        if (typeListItem == null) {
2460            methodParameterRegisterCount = 0;
2461        } else {
2462            methodParameterRegisterCount = typeListItem.getRegisterCount();
2463        }
2464
2465        if ((invokeType & INVOKE_STATIC) == 0) {
2466            methodParameterRegisterCount++;
2467        }
2468
2469        if (methodParameterRegisterCount != registers.getCount()) {
2470            throw new ValidationException(String.format("The number of registers does not match the number of " +
2471                    "parameters for method %s. Expecting %d registers, got %d.", methodIdItem.getMethodString(),
2472                    methodParameterRegisterCount + 1, registers.getCount()));
2473        }
2474
2475        RegisterType objectRegisterType = null;
2476        int objectRegister = 0;
2477        if ((invokeType & INVOKE_STATIC) == 0) {
2478            objectRegister = registers.getRegister();
2479            registers.moveNext();
2480
2481            objectRegisterType = analyzedInstruction.getPreInstructionRegisterType(objectRegister);
2482            assert objectRegisterType != null;
2483            if (objectRegisterType.category == RegisterType.Category.UninitRef ||
2484                    objectRegisterType.category == RegisterType.Category.UninitThis) {
2485
2486                if (!isInit) {
2487                    throw new ValidationException(String.format("Cannot invoke non-<init> method %s on uninitialized " +
2488                            "reference type %s", methodIdItem.getMethodString(),
2489                            objectRegisterType.type.getClassType()));
2490                }
2491            } else if (objectRegisterType.category == RegisterType.Category.Reference) {
2492                if (isInit) {
2493                    throw new ValidationException(String.format("Cannot invoke %s on initialized reference type %s",
2494                            methodIdItem.getMethodString(), objectRegisterType.type.getClassType()));
2495                }
2496            } else if (objectRegisterType.category == RegisterType.Category.Null) {
2497                if (isInit) {
2498                    throw new ValidationException(String.format("Cannot invoke %s on a null reference",
2499                            methodIdItem.getMethodString()));
2500                }
2501            }
2502            else {
2503                throw new ValidationException(String.format("Cannot invoke %s on non-reference type %s",
2504                        methodIdItem.getMethodString(), objectRegisterType.toString()));
2505            }
2506
2507            if (isInit) {
2508                if (objectRegisterType.type.getSuperclass() == methodClassDef) {
2509                    if (!encodedMethod.method.getMethodName().getStringValue().equals("<init>")) {
2510                        throw new ValidationException(String.format("Cannot call %s on type %s. The object type must " +
2511                                "match the method type exactly", methodIdItem.getMethodString(),
2512                                objectRegisterType.type.getClassType()));
2513                    }
2514                }
2515            }
2516
2517            if ((invokeType & INVOKE_INTERFACE) == 0 && objectRegisterType.category != RegisterType.Category.Null &&
2518                    !objectRegisterType.type.extendsClass(methodClassDef)) {
2519
2520               throw new ValidationException(String.format("Cannot call method %s on an object of type %s, which " +
2521                       "does not extend %s.", methodIdItem.getMethodString(), objectRegisterType.type.getClassType(),
2522                        methodClassDef.getClassType()));
2523            }
2524        }
2525
2526        if (typeListItem != null) {
2527            List<TypeIdItem> parameterTypes = typeListItem.getTypes();
2528            int parameterTypeIndex = 0;
2529            while (!registers.pastEnd()) {
2530                assert parameterTypeIndex < parameterTypes.size();
2531                RegisterType parameterType =
2532                        RegisterType.getRegisterTypeForTypeIdItem(parameterTypes.get(parameterTypeIndex));
2533
2534                int register = registers.getRegister();
2535
2536                RegisterType parameterRegisterType;
2537                if (WideLowCategories.contains(parameterType.category)) {
2538                    parameterRegisterType = getAndCheckSourceRegister(analyzedInstruction, register, WideLowCategories);
2539
2540                    if (!registers.moveNext()) {
2541                        throw new ValidationException(String.format("No 2nd register specified for wide register pair v%d",
2542                                parameterTypeIndex+1));
2543                    }
2544                    int nextRegister = registers.getRegister();
2545
2546                    if (nextRegister != register + 1) {
2547                        throw new ValidationException(String.format("Invalid wide register pair (v%d, v%d). Registers " +
2548                                "must be consecutive.", register, nextRegister));
2549                    }
2550                } else {
2551                    parameterRegisterType = analyzedInstruction.getPreInstructionRegisterType(register);
2552                }
2553
2554                assert parameterRegisterType != null;
2555
2556                if (!parameterRegisterType.canBeAssignedTo(parameterType)) {
2557                    throw new ValidationException(
2558                            String.format("Invalid register type %s for parameter %d %s.",
2559                                    parameterRegisterType.toString(), parameterTypeIndex+1,
2560                                    parameterType.toString()));
2561                }
2562
2563                parameterTypeIndex++;
2564                registers.moveNext();
2565            }
2566        }
2567
2568
2569        //TODO: need to ensure the "this" register is initialized, in a constructor method
2570        if (isInit) {
2571            setPostRegisterTypeAndPropagateChanges(analyzedInstruction, objectRegister,
2572                    RegisterType.getRegisterType(RegisterType.Category.Reference, objectRegisterType.type));
2573
2574            for (int i=0; i<analyzedInstruction.postRegisterMap.length; i++) {
2575                RegisterType postInstructionRegisterType = analyzedInstruction.postRegisterMap[i];
2576                if (postInstructionRegisterType.category == RegisterType.Category.Unknown) {
2577                    RegisterType preInstructionRegisterType =
2578                            analyzedInstruction.getPreInstructionRegisterType(i);
2579
2580                    if (preInstructionRegisterType.category == RegisterType.Category.UninitRef ||
2581                        preInstructionRegisterType.category == RegisterType.Category.UninitThis) {
2582
2583                        RegisterType registerType;
2584                        if (preInstructionRegisterType == objectRegisterType) {
2585                            registerType = analyzedInstruction.postRegisterMap[objectRegister];
2586                        } else {
2587                            registerType = preInstructionRegisterType;
2588                        }
2589
2590                        setPostRegisterTypeAndPropagateChanges(analyzedInstruction, i, registerType);
2591                    }
2592                }
2593            }
2594        }
2595    }
2596
2597    private void handleUnaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSourceCategories,
2598                            RegisterType.Category destRegisterCategory) {
2599        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2600
2601        getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(), validSourceCategories);
2602
2603        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2604                RegisterType.getRegisterType(destRegisterCategory, null));
2605    }
2606
2607    private void handleBinaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
2608                                EnumSet validSource2Categories, RegisterType.Category destRegisterCategory,
2609                                boolean checkForBoolean) {
2610        ThreeRegisterInstruction instruction = (ThreeRegisterInstruction)analyzedInstruction.instruction;
2611
2612        RegisterType source1RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2613                validSource1Categories);
2614        RegisterType source2RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterC(),
2615                validSource2Categories);
2616
2617        if (checkForBoolean) {
2618            if (BooleanCategories.contains(source1RegisterType.category) &&
2619                BooleanCategories.contains(source2RegisterType.category)) {
2620
2621                destRegisterCategory = RegisterType.Category.Boolean;
2622            }
2623        }
2624
2625        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2626                RegisterType.getRegisterType(destRegisterCategory, null));
2627    }
2628
2629    private void handleBinary2AddrOp(AnalyzedInstruction analyzedInstruction, EnumSet validSource1Categories,
2630                                EnumSet validSource2Categories, RegisterType.Category destRegisterCategory,
2631                                boolean checkForBoolean) {
2632        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2633
2634        RegisterType source1RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterA(),
2635                validSource1Categories);
2636        RegisterType source2RegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2637                validSource2Categories);
2638
2639        if (checkForBoolean) {
2640            if (BooleanCategories.contains(source1RegisterType.category) &&
2641                BooleanCategories.contains(source2RegisterType.category)) {
2642
2643                destRegisterCategory = RegisterType.Category.Boolean;
2644            }
2645        }
2646
2647        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2648                RegisterType.getRegisterType(destRegisterCategory, null));
2649    }
2650
2651    private void handleLiteralBinaryOp(AnalyzedInstruction analyzedInstruction, EnumSet validSourceCategories,
2652                                RegisterType.Category destRegisterCategory, boolean checkForBoolean) {
2653        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2654
2655        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2656                validSourceCategories);
2657
2658        if (checkForBoolean) {
2659            if (BooleanCategories.contains(sourceRegisterType.category)) {
2660                long literal = ((LiteralInstruction)analyzedInstruction.instruction).getLiteral();
2661                if (literal == 0 || literal == 1) {
2662                    destRegisterCategory = RegisterType.Category.Boolean;
2663                }
2664            }
2665        }
2666
2667        setDestinationRegisterTypeAndPropagateChanges(analyzedInstruction,
2668                RegisterType.getRegisterType(destRegisterCategory, null));
2669    }
2670
2671    private RegisterType.Category getDestTypeForLiteralShiftRight(AnalyzedInstruction analyzedInstruction,
2672                                                                  boolean signedShift) {
2673        TwoRegisterInstruction instruction = (TwoRegisterInstruction)analyzedInstruction.instruction;
2674
2675        RegisterType sourceRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2676                Primitive32BitCategories);
2677        long literalShift = ((LiteralInstruction)analyzedInstruction.instruction).getLiteral();
2678
2679        if (literalShift == 0) {
2680            return sourceRegisterType.category;
2681        }
2682
2683        RegisterType.Category destRegisterCategory;
2684        if (!signedShift) {
2685            destRegisterCategory = RegisterType.Category.Integer;
2686        } else {
2687            destRegisterCategory = sourceRegisterType.category;
2688        }
2689
2690        if (literalShift >= 32) {
2691            //TODO: add warning
2692            return destRegisterCategory;
2693        }
2694
2695        switch (sourceRegisterType.category) {
2696            case Integer:
2697            case Float:
2698                if (!signedShift) {
2699                    if (literalShift > 24) {
2700                        return RegisterType.Category.PosByte;
2701                    }
2702                    if (literalShift >= 16) {
2703                        return RegisterType.Category.Char;
2704                    }
2705                } else {
2706                    if (literalShift >= 24) {
2707                        return RegisterType.Category.Byte;
2708                    }
2709                    if (literalShift >= 16) {
2710                        return RegisterType.Category.Short;
2711                    }
2712                }
2713                break;
2714            case Short:
2715                if (signedShift && literalShift >= 8) {
2716                    return RegisterType.Category.Byte;
2717                }
2718                break;
2719            case PosShort:
2720                if (literalShift >= 8) {
2721                    return RegisterType.Category.PosByte;
2722                }
2723                break;
2724            case Char:
2725                if (literalShift > 8) {
2726                    return RegisterType.Category.PosByte;
2727                }
2728                break;
2729            case Byte:
2730                break;
2731            case PosByte:
2732                return RegisterType.Category.PosByte;
2733            case Null:
2734            case One:
2735            case Boolean:
2736                return RegisterType.Category.Null;
2737            default:
2738                assert false;
2739        }
2740
2741        return destRegisterCategory;
2742    }
2743
2744
2745    private void handleExecuteInline(AnalyzedInstruction analyzedInstruction) {
2746        if (deodexUtil == null) {
2747            throw new ValidationException("Cannot analyze an odexed instruction unless we are deodexing");
2748        }
2749
2750        Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
2751
2752        int methodIndex = instruction.getMethodIndex();
2753        DeodexUtil.InlineMethod inlineMethod = deodexUtil.lookupInlineMethod(methodIndex);
2754        MethodIdItem inlineMethodIdItem = inlineMethod.getMethodIdItem();
2755        if (inlineMethodIdItem == null) {
2756            throw new ValidationException(String.format("Cannot load inline method with index %d", methodIndex));
2757        }
2758
2759        Opcode deodexedOpcode = null;
2760        switch (inlineMethod.methodType) {
2761            case DeodexUtil.Direct:
2762                deodexedOpcode = Opcode.INVOKE_DIRECT;
2763                break;
2764            case DeodexUtil.Static:
2765                deodexedOpcode = Opcode.INVOKE_STATIC;
2766                break;
2767            case DeodexUtil.Virtual:
2768                deodexedOpcode = Opcode.INVOKE_VIRTUAL;
2769                break;
2770            default:
2771                assert false;
2772        }
2773
2774        Instruction35c deodexedInstruction = new Instruction35c(deodexedOpcode, instruction.getRegCount(),
2775                instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
2776                instruction.getRegisterG(), instruction.getRegisterA(), inlineMethodIdItem);
2777
2778        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
2779
2780        analyzeInstruction(analyzedInstruction);
2781    }
2782
2783    private void handleExecuteInlineRange(AnalyzedInstruction analyzedInstruction) {
2784        if (deodexUtil == null) {
2785            throw new ValidationException("Cannot analyze an odexed instruction unless we are deodexing");
2786        }
2787
2788        Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
2789
2790        int methodIndex = instruction.getMethodIndex();
2791        DeodexUtil.InlineMethod inlineMethod = deodexUtil.lookupInlineMethod(methodIndex);
2792        MethodIdItem inlineMethodIdItem = inlineMethod.getMethodIdItem();
2793        if (inlineMethodIdItem == null) {
2794            throw new ValidationException(String.format("Cannot load inline method with index %d", methodIndex));
2795        }
2796
2797        Opcode deodexedOpcode = null;
2798        switch (inlineMethod.methodType) {
2799            case DeodexUtil.Direct:
2800                deodexedOpcode = Opcode.INVOKE_DIRECT;
2801                break;
2802            case DeodexUtil.Static:
2803                deodexedOpcode = Opcode.INVOKE_STATIC;
2804                break;
2805            case DeodexUtil.Virtual:
2806                deodexedOpcode = Opcode.INVOKE_VIRTUAL;
2807                break;
2808            default:
2809                assert false;
2810        }
2811
2812        Instruction3rc deodexedInstruction = new Instruction3rc(deodexedOpcode, instruction.getRegCount(),
2813                instruction.getStartRegister(), inlineMethodIdItem);
2814
2815        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
2816
2817        analyzeInstruction(analyzedInstruction);
2818    }
2819
2820    private void handleInvokeDirectEmpty(AnalyzedInstruction analyzedInstruction) {
2821        Instruction35s instruction = (Instruction35s)analyzedInstruction.instruction;
2822
2823        Instruction35c deodexedInstruction = new Instruction35c(Opcode.INVOKE_DIRECT, instruction.getRegCount(),
2824                instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
2825                instruction.getRegisterG(), instruction.getRegisterA(), instruction.getReferencedItem());
2826
2827        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
2828
2829        analyzeInstruction(analyzedInstruction);
2830    }
2831
2832    private boolean handleIputIgetQuick(AnalyzedInstruction analyzedInstruction, boolean isIput) {
2833        Instruction22cs instruction = (Instruction22cs)analyzedInstruction.instruction;
2834
2835        int fieldOffset = instruction.getFieldOffset();
2836        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, instruction.getRegisterB(),
2837                ReferenceOrUninitCategories);
2838
2839        if (objectRegisterType.category == RegisterType.Category.Null) {
2840            return false;
2841        }
2842
2843        FieldIdItem fieldIdItem = deodexUtil.lookupField(objectRegisterType.type, fieldOffset);
2844        if (fieldIdItem == null) {
2845            throw new ValidationException(String.format("Could not resolve the field in class %s at offset %d",
2846                    objectRegisterType.type.getClassType(), fieldOffset));
2847        }
2848
2849        String fieldType = fieldIdItem.getFieldType().getTypeDescriptor();
2850
2851        Opcode opcode = getAndCheckIgetIputOpcodeForType(fieldType, instruction.opcode, isIput);
2852
2853        Instruction22c deodexedInstruction = new Instruction22c(opcode, (byte)instruction.getRegisterA(),
2854                (byte)instruction.getRegisterB(), fieldIdItem);
2855        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
2856
2857        analyzeInstruction(analyzedInstruction);
2858
2859        return true;
2860    }
2861
2862    private boolean handleInvokeVirtualQuick(AnalyzedInstruction analyzedInstruction, boolean isSuper, boolean isRange) {
2863        int methodIndex;
2864        int objectRegister;
2865
2866
2867        if (isRange) {
2868            Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
2869            methodIndex = instruction.getMethodIndex();
2870            objectRegister = instruction.getStartRegister();
2871        } else {
2872            Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
2873            methodIndex = instruction.getMethodIndex();
2874            objectRegister = instruction.getRegisterD();
2875        }
2876
2877        RegisterType objectRegisterType = getAndCheckSourceRegister(analyzedInstruction, objectRegister,
2878                ReferenceOrUninitCategories);
2879
2880        if (objectRegisterType.category == RegisterType.Category.Null) {
2881            return false;
2882        }
2883
2884        MethodIdItem methodIdItem = null;
2885        if (isSuper) {
2886            ClassPath.ClassDef classDef = ClassPath.getClassDef(this.encodedMethod.method.getContainingClass(), false);
2887            assert classDef != null;
2888
2889            if (classDef.getSuperclass() != null) {
2890                methodIdItem = deodexUtil.lookupVirtualMethod(classDef.getSuperclass(), methodIndex);
2891            }
2892
2893            if (methodIdItem == null) {
2894                //it's possible that the pre-odexed instruction had used the method from the current class instead
2895                //of from the superclass (although the superclass method is still what would actually be called).
2896                //And so the MethodIdItem for the superclass method may not be in the dex file. Let's try to get the
2897                //MethodIdItem for the method in the current class instead
2898                methodIdItem = deodexUtil.lookupVirtualMethod(classDef, methodIndex);
2899            }
2900        } else{
2901            methodIdItem = deodexUtil.lookupVirtualMethod(objectRegisterType.type, methodIndex);
2902        }
2903
2904        if (methodIdItem == null) {
2905            throw new ValidationException(String.format("Could not resolve the method in class %s at index %d",
2906                    objectRegisterType.type.getClassType(), methodIndex));
2907        }
2908
2909
2910        Instruction deodexedInstruction;
2911        if (isRange) {
2912            Instruction3rms instruction = (Instruction3rms)analyzedInstruction.instruction;
2913            Opcode opcode;
2914            if (isSuper) {
2915                opcode = Opcode.INVOKE_SUPER_RANGE;
2916            } else {
2917                opcode = Opcode.INVOKE_VIRTUAL_RANGE;
2918            }
2919
2920            deodexedInstruction = new Instruction3rc(opcode, instruction.getRegCount(),
2921                    instruction.getStartRegister(), methodIdItem);
2922        } else {
2923            Instruction35ms instruction = (Instruction35ms)analyzedInstruction.instruction;
2924            Opcode opcode;
2925            if (isSuper) {
2926                opcode = Opcode.INVOKE_SUPER;
2927            } else {
2928                opcode = Opcode.INVOKE_VIRTUAL;
2929            }
2930
2931            deodexedInstruction = new Instruction35c(opcode, instruction.getRegCount(),
2932                    instruction.getRegisterD(), instruction.getRegisterE(), instruction.getRegisterF(),
2933                    instruction.getRegisterG(), instruction.getRegisterA(), methodIdItem);
2934        }
2935
2936        analyzedInstruction.setDeodexedInstruction(deodexedInstruction);
2937        analyzeInstruction(analyzedInstruction);
2938
2939        return true;
2940    }
2941
2942    private static Opcode getAndCheckIgetIputOpcodeForType(String fieldType, Opcode odexedOpcode, boolean isIput) {
2943        Opcode opcode;
2944        Opcode validOdexedOpcode;
2945        switch (fieldType.charAt(0)) {
2946            case 'Z':
2947                if (isIput) {
2948                    validOdexedOpcode = Opcode.IPUT_QUICK;
2949                    opcode = Opcode.IPUT_BOOLEAN;
2950                } else {
2951                    validOdexedOpcode = Opcode.IGET_QUICK;
2952                    opcode = Opcode.IGET_BOOLEAN;
2953                }
2954                break;
2955            case 'B':
2956                if (isIput) {
2957                    validOdexedOpcode = Opcode.IPUT_QUICK;
2958                    opcode = Opcode.IPUT_BYTE;
2959                } else {
2960                    validOdexedOpcode = Opcode.IGET_QUICK;
2961                    opcode = Opcode.IGET_BYTE;
2962                }
2963                break;
2964            case 'S':
2965                if (isIput) {
2966                    validOdexedOpcode = Opcode.IPUT_QUICK;
2967                    opcode = Opcode.IPUT_SHORT;
2968                } else {
2969                    validOdexedOpcode = Opcode.IGET_QUICK;
2970                    opcode = Opcode.IGET_SHORT;
2971                }
2972                break;
2973            case 'C':
2974                if (isIput) {
2975                    validOdexedOpcode = Opcode.IPUT_QUICK;
2976                    opcode = Opcode.IPUT_CHAR;
2977                } else {
2978                    validOdexedOpcode = Opcode.IGET_QUICK;
2979                    opcode = Opcode.IGET_CHAR;
2980                }
2981                break;
2982            case 'I':
2983            case 'F':
2984                if (isIput) {
2985                    validOdexedOpcode = Opcode.IPUT_QUICK;
2986                    opcode = Opcode.IPUT;
2987                } else {
2988                    validOdexedOpcode = Opcode.IGET_QUICK;
2989                    opcode = Opcode.IGET;
2990                }
2991                break;
2992            case 'J':
2993            case 'D':
2994                if (isIput) {
2995                    validOdexedOpcode = Opcode.IPUT_WIDE_QUICK;
2996                    opcode = Opcode.IPUT_WIDE;
2997                } else {
2998                    validOdexedOpcode = Opcode.IGET_WIDE_QUICK;
2999                    opcode = Opcode.IGET_WIDE;
3000                }
3001                break;
3002            case 'L':
3003            case '[':
3004                if (isIput) {
3005                    validOdexedOpcode = Opcode.IPUT_OBJECT_QUICK;
3006                    opcode = Opcode.IPUT_OBJECT;
3007                } else {
3008                    validOdexedOpcode = Opcode.IGET_OBJECT_QUICK;
3009                    opcode = Opcode.IGET_OBJECT;
3010                }
3011                break;
3012            default:
3013                throw new RuntimeException(String.format("Unexpected field type %s for %s: ", fieldType,
3014                        odexedOpcode.name));
3015        }
3016
3017        if (odexedOpcode != validOdexedOpcode) {
3018            throw new ValidationException(String.format("Incorrect field type \"%s\" for %s", fieldType,
3019                    odexedOpcode.name));
3020        }
3021
3022        return opcode;
3023    }
3024
3025    private static boolean checkArrayFieldAssignment(RegisterType.Category arrayFieldCategory,
3026                                                  RegisterType.Category instructionCategory) {
3027        if (arrayFieldCategory == instructionCategory) {
3028            return true;
3029        }
3030
3031        if ((arrayFieldCategory == RegisterType.Category.Integer &&
3032             instructionCategory == RegisterType.Category.Float) ||
3033            (arrayFieldCategory == RegisterType.Category.Float &&
3034             instructionCategory == RegisterType.Category.Integer)) {
3035            return true;
3036        }
3037        return false;
3038    }
3039
3040    private static RegisterType getAndCheckSourceRegister(AnalyzedInstruction analyzedInstruction, int registerNumber,
3041                                            EnumSet validCategories) {
3042        assert registerNumber >= 0 && registerNumber < analyzedInstruction.postRegisterMap.length;
3043
3044        RegisterType registerType = analyzedInstruction.getPreInstructionRegisterType(registerNumber);
3045        assert registerType != null;
3046
3047        checkRegister(registerType, registerNumber, validCategories);
3048
3049        if (validCategories == WideLowCategories) {
3050            checkRegister(registerType, registerNumber, WideLowCategories);
3051            checkWidePair(registerNumber, analyzedInstruction);
3052
3053            RegisterType secondRegisterType = analyzedInstruction.getPreInstructionRegisterType(registerNumber + 1);
3054            assert secondRegisterType != null;
3055            checkRegister(secondRegisterType, registerNumber+1, WideHighCategories);
3056        }
3057
3058        return registerType;
3059    }
3060
3061    private static void checkRegister(RegisterType registerType, int registerNumber, EnumSet validCategories) {
3062        if (!validCategories.contains(registerType.category)) {
3063            throw new ValidationException(String.format("Invalid register type %s for register v%d.",
3064                    registerType.toString(), registerNumber));
3065        }
3066    }
3067
3068    private static void checkWidePair(int registerNumber, AnalyzedInstruction analyzedInstruction) {
3069        if (registerNumber + 1 >= analyzedInstruction.postRegisterMap.length) {
3070            throw new ValidationException(String.format("v%d is the last register and not a valid wide register " +
3071                    "pair.", registerNumber));
3072        }
3073    }
3074}
3075