1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2014 Eric Lafortune (eric@graphics.cornell.edu)
6 *
7 * This program is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the Free
9 * Software Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * more details.
16 *
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21package proguard.optimize.evaluation;
22
23import proguard.classfile.*;
24import proguard.classfile.attribute.*;
25import proguard.classfile.attribute.visitor.AttributeVisitor;
26import proguard.classfile.constant.RefConstant;
27import proguard.classfile.constant.visitor.ConstantVisitor;
28import proguard.classfile.editor.CodeAttributeEditor;
29import proguard.classfile.instruction.*;
30import proguard.classfile.instruction.visitor.InstructionVisitor;
31import proguard.classfile.util.*;
32import proguard.classfile.visitor.*;
33import proguard.evaluation.TracedStack;
34import proguard.evaluation.value.*;
35import proguard.optimize.info.*;
36
37import java.util.Arrays;
38
39/**
40 * This AttributeVisitor simplifies the code attributes that it visits, based
41 * on partial evaluation.
42 *
43 * @author Eric Lafortune
44 */
45public class EvaluationShrinker
46extends      SimplifiedVisitor
47implements   AttributeVisitor
48{
49    //*
50    private static final boolean DEBUG_RESULTS  = false;
51    private static final boolean DEBUG          = false;
52    /*/
53    private static boolean DEBUG          = System.getProperty("es") != null;
54    private static boolean DEBUG_RESULTS  = DEBUG;
55    //*/
56
57    private static final int UNSUPPORTED      = -1;
58    private static final int NOP              = InstructionConstants.OP_NOP     & 0xff;
59    private static final int POP              = InstructionConstants.OP_POP     & 0xff;
60    private static final int POP2             = InstructionConstants.OP_POP2    & 0xff;
61    private static final int DUP              = InstructionConstants.OP_DUP     & 0xff;
62    private static final int DUP_X1           = InstructionConstants.OP_DUP_X1  & 0xff;
63    private static final int DUP_X2           = InstructionConstants.OP_DUP_X2  & 0xff;
64    private static final int DUP2             = InstructionConstants.OP_DUP2    & 0xff;
65    private static final int DUP2_X1          = InstructionConstants.OP_DUP2_X1 & 0xff;
66    private static final int DUP2_X2          = InstructionConstants.OP_DUP2_X2 & 0xff;
67    private static final int SWAP             = InstructionConstants.OP_SWAP    & 0xff;
68    private static final int MOV_X2           = DUP_X2  | (POP    << 8);
69    private static final int MOV2_X1          = DUP2_X1 | (POP2   << 8);
70    private static final int MOV2_X2          = DUP2_X2 | (POP2   << 8);
71    private static final int POP_X1           = SWAP    | (POP    << 8);
72    private static final int POP_X2           = DUP2_X1 | (POP2   << 8) | (POP    << 16);
73    private static final int POP_X3           = UNSUPPORTED;
74    private static final int POP2_X1          = DUP_X2  | (POP    << 8) | (POP2   << 16);
75    private static final int POP2_X2          = DUP2_X2 | (POP2   << 8) | (POP2   << 16);
76    private static final int POP3             = POP2    | (POP    << 8);
77    private static final int POP4             = POP2    | (POP2   << 8);
78    private static final int POP_DUP          = POP     | (DUP    << 8);
79    private static final int POP_SWAP_POP     = POP     | (SWAP   << 8) | (POP    << 16);
80    private static final int POP2_SWAP_POP    = POP2    | (SWAP   << 8) | (POP    << 16);
81    private static final int SWAP_DUP_X1      = SWAP    | (DUP_X1 << 8);
82    private static final int SWAP_DUP_X1_SWAP = SWAP    | (DUP_X1 << 8) | (SWAP   << 16);
83    private static final int SWAP_POP_DUP     = SWAP    | (POP    << 8) | (DUP    << 16);
84    private static final int SWAP_POP_DUP_X1  = SWAP    | (POP    << 8) | (DUP_X1 << 16);
85    private static final int DUP_X2_POP2      = DUP_X2  | (POP2   << 8);
86    private static final int DUP2_X1_POP3     = DUP2_X1 | (POP2   << 8) | (POP    << 16);
87    private static final int DUP2_X2_POP3     = DUP2_X2 | (POP2   << 8) | (POP    << 16);
88    private static final int DUP2_X2_SWAP_POP = DUP2_X2 | (SWAP   << 8) | (POP    << 16);
89
90
91    private final InstructionVisitor extraDeletedInstructionVisitor;
92    private final InstructionVisitor extraAddedInstructionVisitor;
93
94    private final PartialEvaluator               partialEvaluator;
95    private final PartialEvaluator               simplePartialEvaluator       = new PartialEvaluator();
96    private final SideEffectInstructionChecker   sideEffectInstructionChecker = new SideEffectInstructionChecker(true, true);
97    private final MyUnusedParameterSimplifier    unusedParameterSimplifier    = new MyUnusedParameterSimplifier();
98    private final MyProducerMarker               producerMarker               = new MyProducerMarker();
99    private final MyVariableInitializationMarker variableInitializationMarker = new MyVariableInitializationMarker();
100    private final MyStackConsistencyFixer        stackConsistencyFixer        = new MyStackConsistencyFixer();
101    private final CodeAttributeEditor            codeAttributeEditor          = new CodeAttributeEditor(false, false);
102
103    private boolean[][] stacksNecessaryAfter   = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE];
104    private boolean[][] stacksSimplifiedBefore = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE];
105    private boolean[]   instructionsNecessary  = new boolean[ClassConstants.TYPICAL_CODE_LENGTH];
106
107    private int maxMarkedOffset;
108
109
110    /**
111     * Creates a new EvaluationShrinker.
112     */
113    public EvaluationShrinker()
114    {
115        this(new PartialEvaluator(), null, null);
116    }
117
118
119    /**
120     * Creates a new EvaluationShrinker.
121     * @param partialEvaluator               the partial evaluator that will
122     *                                       execute the code and provide
123     *                                       information about the results.
124     * @param extraDeletedInstructionVisitor an optional extra visitor for all
125     *                                       deleted instructions.
126     * @param extraAddedInstructionVisitor   an optional extra visitor for all
127     *                                       added instructions.
128     */
129    public EvaluationShrinker(PartialEvaluator   partialEvaluator,
130                              InstructionVisitor extraDeletedInstructionVisitor,
131                              InstructionVisitor extraAddedInstructionVisitor)
132    {
133        this.partialEvaluator               = partialEvaluator;
134        this.extraDeletedInstructionVisitor = extraDeletedInstructionVisitor;
135        this.extraAddedInstructionVisitor   = extraAddedInstructionVisitor;
136    }
137
138
139    // Implementations for AttributeVisitor.
140
141    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
142
143
144    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
145    {
146//        DEBUG = DEBUG_RESULTS =
147//            clazz.getName().equals("abc/Def") &&
148//            method.getName(clazz).equals("abc");
149
150        // TODO: Remove this when the evaluation shrinker has stabilized.
151        // Catch any unexpected exceptions from the actual visiting method.
152        try
153        {
154            // Process the code.
155            visitCodeAttribute0(clazz, method, codeAttribute);
156        }
157        catch (RuntimeException ex)
158        {
159            System.err.println("Unexpected error while shrinking instructions after partial evaluation:");
160            System.err.println("  Class       = ["+clazz.getName()+"]");
161            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
162            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
163            System.err.println("Not optimizing this method");
164
165            if (DEBUG)
166            {
167                method.accept(clazz, new ClassPrinter());
168
169                throw ex;
170            }
171        }
172    }
173
174
175    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
176    {
177        if (DEBUG_RESULTS)
178        {
179            System.out.println();
180            System.out.println("EvaluationShrinker ["+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz)+"]");
181        }
182
183        // Initialize the necessary array.
184        initializeNecessary(codeAttribute);
185
186        // Evaluate the method.
187        partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
188
189        // Evaluate the method the way the JVM verifier would do it.
190        simplePartialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
191
192        int codeLength = codeAttribute.u4codeLength;
193
194        // Reset the code changes.
195        codeAttributeEditor.reset(codeLength);
196
197        // Mark any unused method parameters on the stack.
198        if (DEBUG) System.out.println("Invocation simplification:");
199
200        for (int offset = 0; offset < codeLength; offset++)
201        {
202            if (partialEvaluator.isTraced(offset))
203            {
204                Instruction instruction = InstructionFactory.create(codeAttribute.code,
205                                                                    offset);
206
207                instruction.accept(clazz, method, codeAttribute, offset, unusedParameterSimplifier);
208            }
209        }
210
211        // Mark all essential instructions that have been encountered as used.
212        if (DEBUG) System.out.println("Usage initialization: ");
213
214        maxMarkedOffset = -1;
215
216        // The invocation of the "super" or "this" <init> method inside a
217        // constructor is always necessary.
218        int superInitializationOffset = partialEvaluator.superInitializationOffset();
219        if (superInitializationOffset != PartialEvaluator.NONE)
220        {
221            if (DEBUG) System.out.print("(super.<init>)");
222
223            markInstruction(superInitializationOffset);
224        }
225
226        // Also mark infinite loops and instructions that cause side effects.
227        for (int offset = 0; offset < codeLength; offset++)
228        {
229            if (partialEvaluator.isTraced(offset))
230            {
231                Instruction instruction = InstructionFactory.create(codeAttribute.code,
232                                                                    offset);
233
234                // Mark that the instruction is necessary if it is an infinite loop.
235                if (instruction.opcode == InstructionConstants.OP_GOTO &&
236                    ((BranchInstruction)instruction).branchOffset == 0)
237                {
238                    if (DEBUG) System.out.print("(infinite loop)");
239                    markInstruction(offset);
240                }
241
242                // Mark that the instruction is necessary if it has side effects.
243                else if (sideEffectInstructionChecker.hasSideEffects(clazz,
244                                                                     method,
245                                                                     codeAttribute,
246                                                                     offset,
247                                                                     instruction))
248                {
249                    markInstruction(offset);
250                }
251            }
252        }
253        if (DEBUG) System.out.println();
254
255
256        // Globally mark instructions and their produced variables and stack
257        // entries on which necessary instructions depend.
258        // Instead of doing this recursively, we loop across all instructions,
259        // starting at the highest previously unmarked instruction that has
260        // been been marked.
261        if (DEBUG) System.out.println("Usage marking:");
262
263        while (maxMarkedOffset >= 0)
264        {
265            int offset = maxMarkedOffset;
266
267            maxMarkedOffset = offset - 1;
268
269            if (partialEvaluator.isTraced(offset))
270            {
271                if (isInstructionNecessary(offset))
272                {
273                    Instruction instruction = InstructionFactory.create(codeAttribute.code,
274                                                                        offset);
275
276                    instruction.accept(clazz, method, codeAttribute, offset, producerMarker);
277                }
278
279                // Check if this instruction is a branch origin from a branch
280                // that straddles some marked code.
281                markStraddlingBranches(offset,
282                                       partialEvaluator.branchTargets(offset),
283                                       true);
284
285                // Check if this instruction is a branch target from a branch
286                // that straddles some marked code.
287                markStraddlingBranches(offset,
288                                       partialEvaluator.branchOrigins(offset),
289                                       false);
290            }
291
292            if (DEBUG)
293            {
294                if (maxMarkedOffset > offset)
295                {
296                    System.out.println(" -> "+maxMarkedOffset);
297                }
298            }
299        }
300        if (DEBUG) System.out.println();
301
302
303        // Mark variable initializations, even if they aren't strictly necessary.
304        // The virtual machine's verification step is not smart enough to see
305        // this, and may complain otherwise.
306        if (DEBUG) System.out.println("Initialization marking: ");
307
308        for (int offset = 0; offset < codeLength; offset++)
309        {
310            if (isInstructionNecessary(offset))
311            {
312                // Mark initializations of the required instruction.
313                Instruction instruction = InstructionFactory.create(codeAttribute.code,
314                                                                    offset);
315
316                instruction.accept(clazz, method, codeAttribute, offset, variableInitializationMarker);
317            }
318        }
319        if (DEBUG) System.out.println();
320
321
322        // Locally fix instructions, in order to keep the stack consistent.
323        if (DEBUG) System.out.println("Stack consistency fixing:");
324
325        maxMarkedOffset = codeLength - 1;
326
327        while (maxMarkedOffset >= 0)
328        {
329            int offset = maxMarkedOffset;
330
331            maxMarkedOffset = offset - 1;
332
333            if (partialEvaluator.isTraced(offset))
334            {
335                Instruction instruction = InstructionFactory.create(codeAttribute.code,
336                                                                    offset);
337
338                instruction.accept(clazz, method, codeAttribute, offset, stackConsistencyFixer);
339
340                // Check if this instruction is a branch origin from a branch
341                // that straddles some marked code.
342                markStraddlingBranches(offset,
343                                       partialEvaluator.branchTargets(offset),
344                                       true);
345
346                // Check if this instruction is a branch target from a branch
347                // that straddles some marked code.
348                markStraddlingBranches(offset,
349                                       partialEvaluator.branchOrigins(offset),
350                                       false);
351            }
352        }
353        if (DEBUG) System.out.println();
354
355
356        // Replace traced but unmarked backward branches by infinite loops.
357        // The virtual machine's verification step is not smart enough to see
358        // the code isn't reachable, and may complain otherwise.
359        // Any clearly unreachable code will still be removed elsewhere.
360        if (DEBUG) System.out.println("Infinite loop fixing:");
361
362        for (int offset = 0; offset < codeLength; offset++)
363        {
364            // Is it a traced but unmarked backward branch, without an unmarked
365            // straddling forward branch? Note that this is still a heuristic.
366            if (partialEvaluator.isTraced(offset) &&
367                !isInstructionNecessary(offset)   &&
368                isAllSmallerThanOrEqual(partialEvaluator.branchTargets(offset),
369                                        offset)   &&
370                !isAnyUnnecessaryInstructionBranchingOver(lastNecessaryInstructionOffset(offset),
371                                                          offset))
372            {
373                replaceByInfiniteLoop(clazz, offset);
374            }
375        }
376        if (DEBUG) System.out.println();
377
378
379        // Insert infinite loops after jumps to subroutines that don't return.
380        // The virtual machine's verification step is not smart enough to see
381        // the code isn't reachable, and may complain otherwise.
382        if (DEBUG) System.out.println("Non-returning subroutine fixing:");
383
384        for (int offset = 0; offset < codeLength; offset++)
385        {
386            // Is it a traced but unmarked backward branch, without an unmarked
387            // straddling forward branch? Note that this is still a heuristic.
388            if (isInstructionNecessary(offset) &&
389                partialEvaluator.isSubroutineInvocation(offset))
390            {
391                Instruction instruction = InstructionFactory.create(codeAttribute.code,
392                                                                    offset);
393
394                int nextOffset = offset + instruction.length(offset);
395                if (!isInstructionNecessary(nextOffset))
396                {
397                    replaceByInfiniteLoop(clazz, nextOffset);
398                }
399            }
400        }
401        if (DEBUG) System.out.println();
402
403
404        // Delete all instructions that are not used.
405        int offset = 0;
406        do
407        {
408            Instruction instruction = InstructionFactory.create(codeAttribute.code,
409                                                                offset);
410            if (!isInstructionNecessary(offset))
411            {
412                codeAttributeEditor.clearModifications(offset);
413                codeAttributeEditor.deleteInstruction(offset);
414
415                // Visit the instruction, if required.
416                if (extraDeletedInstructionVisitor != null)
417                {
418                    instruction.accept(clazz, method, codeAttribute, offset, extraDeletedInstructionVisitor);
419                }
420            }
421
422            offset += instruction.length(offset);
423        }
424        while (offset < codeLength);
425
426
427        if (DEBUG_RESULTS)
428        {
429            System.out.println("Simplification results:");
430
431            offset = 0;
432            do
433            {
434                Instruction instruction = InstructionFactory.create(codeAttribute.code,
435                                                                    offset);
436                System.out.println((isInstructionNecessary(offset) ? " + " : " - ")+instruction.toString(offset));
437
438                if (partialEvaluator.isTraced(offset))
439                {
440                    int initializationOffset = partialEvaluator.initializationOffset(offset);
441                    if (initializationOffset != PartialEvaluator.NONE)
442                    {
443                        System.out.println("     is to be initialized at ["+initializationOffset+"]");
444                    }
445
446                    InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
447                    if (branchTargets != null)
448                    {
449                        System.out.println("     has overall been branching to "+branchTargets);
450                    }
451
452                    boolean deleted = codeAttributeEditor.deleted[offset];
453                    if (isInstructionNecessary(offset) && deleted)
454                    {
455                        System.out.println("     is deleted");
456                    }
457
458                    Instruction preInsertion = codeAttributeEditor.preInsertions[offset];
459                    if (preInsertion != null)
460                    {
461                        System.out.println("     is preceded by: "+preInsertion);
462                    }
463
464                    Instruction replacement = codeAttributeEditor.replacements[offset];
465                    if (replacement != null)
466                    {
467                        System.out.println("     is replaced by: "+replacement);
468                    }
469
470                    Instruction postInsertion = codeAttributeEditor.postInsertions[offset];
471                    if (postInsertion != null)
472                    {
473                        System.out.println("     is followed by: "+postInsertion);
474                    }
475                }
476
477                offset += instruction.length(offset);
478            }
479            while (offset < codeLength);
480        }
481
482        // Apply all accumulated changes to the code.
483        codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute);
484    }
485
486
487    /**
488     * This MemberVisitor marks stack entries that aren't necessary because
489     * parameters aren't used in the methods that are visited.
490     */
491    private class MyUnusedParameterSimplifier
492    extends       SimplifiedVisitor
493    implements    InstructionVisitor,
494                  ConstantVisitor,
495                  MemberVisitor
496    {
497        private int                 invocationOffset;
498        private ConstantInstruction invocationInstruction;
499
500
501        // Implementations for InstructionVisitor.
502
503        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {}
504
505
506        public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
507        {
508            switch (constantInstruction.opcode)
509            {
510                case InstructionConstants.OP_INVOKEVIRTUAL:
511                case InstructionConstants.OP_INVOKESPECIAL:
512                case InstructionConstants.OP_INVOKESTATIC:
513                case InstructionConstants.OP_INVOKEINTERFACE:
514                    this.invocationOffset      = offset;
515                    this.invocationInstruction = constantInstruction;
516                    clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this);
517                    break;
518            }
519        }
520
521
522        // Implementations for ConstantVisitor.
523
524        public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant)
525        {
526            refConstant.referencedMemberAccept(this);
527        }
528
529
530        // Implementations for MemberVisitor.
531
532        public void visitAnyMember(Clazz clazz, Member member) {}
533
534
535        public void visitProgramMethod(ProgramClass programClass, ProgramMethod programMethod)
536        {
537            // Get the total size of the parameters.
538            int parameterSize = ParameterUsageMarker.getParameterSize(programMethod);
539
540            // Make the method invocation static, if possible.
541            if ((programMethod.getAccessFlags() & ClassConstants.ACC_STATIC) == 0 &&
542                !ParameterUsageMarker.isParameterUsed(programMethod, 0))
543            {
544                replaceByStaticInvocation(programClass,
545                                          invocationOffset,
546                                          invocationInstruction);
547            }
548
549            // Remove unused parameters.
550            for (int index = 0; index < parameterSize; index++)
551            {
552                if (!ParameterUsageMarker.isParameterUsed(programMethod, index))
553                {
554                    TracedStack stack =
555                        partialEvaluator.getStackBefore(invocationOffset);
556
557                    int stackIndex = stack.size() - parameterSize + index;
558
559                    if (DEBUG)
560                    {
561                        System.out.println("  ["+invocationOffset+"] Ignoring parameter #"+index+" of "+programClass.getName()+"."+programMethod.getName(programClass)+programMethod.getDescriptor(programClass)+"] (stack entry #"+stackIndex+" ["+stack.getBottom(stackIndex)+"])");
562                        System.out.println("    Full stack: "+stack);
563                    }
564
565                    markStackSimplificationBefore(invocationOffset, stackIndex);
566                }
567            }
568        }
569    }
570
571
572    /**
573     * This InstructionVisitor marks the producing instructions and produced
574     * variables and stack entries of the instructions that it visits.
575     * Simplified method arguments are ignored.
576     */
577    private class MyProducerMarker
578    extends       SimplifiedVisitor
579    implements    InstructionVisitor
580    {
581        // Implementations for InstructionVisitor.
582
583        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
584        {
585            markStackProducers(clazz, offset, instruction);
586        }
587
588
589        public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
590        {
591            switch (simpleInstruction.opcode)
592            {
593                case InstructionConstants.OP_DUP:
594                    conditionallyMarkStackEntryProducers(offset, 0, 0);
595                    conditionallyMarkStackEntryProducers(offset, 1, 0);
596                    break;
597                case InstructionConstants.OP_DUP_X1:
598                    conditionallyMarkStackEntryProducers(offset, 0, 0);
599                    conditionallyMarkStackEntryProducers(offset, 1, 1);
600                    conditionallyMarkStackEntryProducers(offset, 2, 0);
601                    break;
602                case InstructionConstants.OP_DUP_X2:
603                    conditionallyMarkStackEntryProducers(offset, 0, 0);
604                    conditionallyMarkStackEntryProducers(offset, 1, 1);
605                    conditionallyMarkStackEntryProducers(offset, 2, 2);
606                    conditionallyMarkStackEntryProducers(offset, 3, 0);
607                    break;
608                case InstructionConstants.OP_DUP2:
609                    conditionallyMarkStackEntryProducers(offset, 0, 0);
610                    conditionallyMarkStackEntryProducers(offset, 1, 1);
611                    conditionallyMarkStackEntryProducers(offset, 2, 0);
612                    conditionallyMarkStackEntryProducers(offset, 3, 1);
613                    break;
614                case InstructionConstants.OP_DUP2_X1:
615                    conditionallyMarkStackEntryProducers(offset, 0, 0);
616                    conditionallyMarkStackEntryProducers(offset, 1, 1);
617                    conditionallyMarkStackEntryProducers(offset, 2, 2);
618                    conditionallyMarkStackEntryProducers(offset, 3, 0);
619                    conditionallyMarkStackEntryProducers(offset, 4, 1);
620                    break;
621                case InstructionConstants.OP_DUP2_X2:
622                    conditionallyMarkStackEntryProducers(offset, 0, 0);
623                    conditionallyMarkStackEntryProducers(offset, 1, 1);
624                    conditionallyMarkStackEntryProducers(offset, 2, 2);
625                    conditionallyMarkStackEntryProducers(offset, 3, 3);
626                    conditionallyMarkStackEntryProducers(offset, 4, 0);
627                    conditionallyMarkStackEntryProducers(offset, 5, 1);
628                    break;
629                case InstructionConstants.OP_SWAP:
630                    conditionallyMarkStackEntryProducers(offset, 0, 1);
631                    conditionallyMarkStackEntryProducers(offset, 1, 0);
632                    break;
633                default:
634                    markStackProducers(clazz, offset, simpleInstruction);
635                    break;
636            }
637        }
638
639
640        public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
641        {
642            // Is the variable being loaded or incremented?
643            if (variableInstruction.isLoad())
644            {
645                markVariableProducers(offset, variableInstruction.variableIndex);
646            }
647            else
648            {
649                markStackProducers(clazz, offset, variableInstruction);
650            }
651        }
652
653
654        public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
655        {
656            // Mark the initializer invocation, if this is a 'new' instruction.
657            if (constantInstruction.opcode == InstructionConstants.OP_NEW)
658            {
659                markInitialization(offset);
660            }
661
662            markStackProducers(clazz, offset, constantInstruction);
663        }
664
665
666        public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
667        {
668            // Explicitly mark the produced stack entry of a 'jsr' instruction,
669            // because the consuming 'astore' instruction of the subroutine is
670            // cleared every time it is traced.
671            if (branchInstruction.opcode == InstructionConstants.OP_JSR ||
672                branchInstruction.opcode == InstructionConstants.OP_JSR_W)
673            {
674                markStackEntryAfter(offset, 0);
675            }
676            else
677            {
678                markStackProducers(clazz, offset, branchInstruction);
679            }
680        }
681    }
682
683
684    /**
685     * This InstructionVisitor marks variable initializations that are
686     * necessary to appease the JVM.
687     */
688    private class MyVariableInitializationMarker
689    extends       SimplifiedVisitor
690    implements    InstructionVisitor
691    {
692        // Implementations for InstructionVisitor.
693
694        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {}
695
696
697        public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
698        {
699            // Is the variable being loaded or incremented?
700            if (variableInstruction.isLoad())
701            {
702                // Mark any variable initializations for this variable load that
703                // are required according to the JVM.
704                markVariableInitializersBefore(offset, variableInstruction.variableIndex);
705            }
706        }
707    }
708
709
710    /**
711     * This InstructionVisitor fixes instructions locally, popping any unused
712     * produced stack entries after marked instructions, and popping produced
713     * stack entries and pushing missing stack entries instead of unmarked
714     * instructions.
715     */
716    private class MyStackConsistencyFixer
717    extends       SimplifiedVisitor
718    implements    InstructionVisitor
719    {
720        // Implementations for InstructionVisitor.
721
722        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
723        {
724            // Has the instruction been marked?
725            if (isInstructionNecessary(offset))
726            {
727                // Check all stack entries that are popped.
728                // Unusual case: an exception handler with an exception that is
729                // no longer consumed directly by a method.
730                // Typical case: a freshly marked variable initialization that
731                // requires some value on the stack.
732                int popCount = instruction.stackPopCount(clazz);
733                if (popCount > 0)
734                {
735                    TracedStack tracedStack =
736                        partialEvaluator.getStackBefore(offset);
737
738                    int stackSize = tracedStack.size();
739
740                    int requiredPopCount  = 0;
741                    int requiredPushCount = 0;
742                    for (int stackIndex = stackSize - popCount; stackIndex < stackSize; stackIndex++)
743                    {
744                        boolean stackSimplifiedBefore =
745                            isStackSimplifiedBefore(offset, stackIndex);
746                        boolean stackEntryPresentBefore =
747                            isStackEntryPresentBefore(offset, stackIndex);
748
749                        if (stackSimplifiedBefore)
750                        {
751                            // Is this stack entry pushed by any producer
752                            // (maybe an exception in an exception handler)?
753                            if (isStackEntryPresentBefore(offset, stackIndex))
754                            {
755                                // Mark all produced stack entries.
756                                markStackEntryProducers(offset, stackIndex);
757
758                                // Remember to pop it.
759                                requiredPopCount++;
760                            }
761                        }
762                        else
763                        {
764                            // Is this stack entry pushed by any producer
765                            // (because it is required by other consumers)?
766                            if (stackEntryPresentBefore)
767                            {
768                                // Mark all produced stack entries.
769                                markStackEntryProducers(offset, stackIndex);
770                            }
771                            else
772                            {
773                                // Remember to push it.
774                                requiredPushCount++;
775                            }
776                        }
777                    }
778
779                    // Pop some unnecessary stack entries.
780                    if (requiredPopCount > 0)
781                    {
782                        if (DEBUG) System.out.println("  Inserting before marked consumer "+instruction.toString(offset));
783
784                        insertPopInstructions(offset, false, true, popCount);
785                    }
786
787                    // Push some necessary stack entries.
788                    if (requiredPushCount > 0)
789                    {
790                        if (DEBUG) System.out.println("  Inserting before marked consumer "+instruction.toString(offset));
791
792                        if (requiredPushCount > (instruction.isCategory2() ? 2 : 1))
793                        {
794                            throw new IllegalArgumentException("Unsupported stack size increment ["+requiredPushCount+"] at ["+offset+"]");
795                        }
796
797                        insertPushInstructions(offset, false, true, tracedStack.getTop(0).computationalType());
798                    }
799                }
800
801                // Check all other stack entries, if this is a return
802                // instruction.
803                // Typical case: the code returns, but there are still other
804                // entries left on the stack. These have to be consistent.
805                InstructionOffsetValue branchTargets =
806                    partialEvaluator.branchTargets(offset);
807                if (branchTargets != null &&
808                    branchTargets.instructionOffsetCount() == 0)
809                {
810                    TracedStack tracedStack =
811                        partialEvaluator.getStackBefore(offset);
812
813                    int unpoppedStackSize = tracedStack.size() - popCount;
814
815                    for (int stackIndex = 0; stackIndex < unpoppedStackSize; stackIndex++)
816                    {
817                        // Is this stack entry pushed by any producer
818                        // (because it is required by other consumers)?
819                        if (isStackEntryPresentBefore(offset, stackIndex))
820                        {
821                            // Mark all produced stack entries.
822                            markStackEntryProducers(offset, stackIndex);
823                        }
824                    }
825                }
826
827                // Check all stack entries that are pushed.
828                // Typical case: a return value that wasn't really required and
829                // that should be popped.
830                int pushCount = instruction.stackPushCount(clazz);
831                if (pushCount > 0)
832                {
833                    TracedStack tracedStack =
834                        partialEvaluator.getStackAfter(offset);
835
836                    int stackSize = tracedStack.size();
837
838                    int requiredPopCount = 0;
839                    for (int stackIndex = stackSize - pushCount; stackIndex < stackSize; stackIndex++)
840                    {
841                        // Is the stack entry required by consumers?
842                        if (!isStackEntryNecessaryAfter(offset, stackIndex))
843                        {
844                            // Remember to pop it.
845                            requiredPopCount++;
846                        }
847                    }
848
849                    // Pop the unnecessary stack entries.
850                    if (requiredPopCount > 0)
851                    {
852                        if (DEBUG) System.out.println("  Inserting after marked producer "+instruction.toString(offset));
853
854                        insertPopInstructions(offset, false, false, requiredPopCount);
855                    }
856                }
857            }
858            else
859            {
860                // Check all stack entries that would be popped.
861                // Typical case: a stack value that is required elsewhere and
862                // that still has to be popped.
863                int popCount = instruction.stackPopCount(clazz);
864                if (popCount > 0)
865                {
866                    TracedStack tracedStack =
867                        partialEvaluator.getStackBefore(offset);
868
869                    int stackSize = tracedStack.size();
870
871                    int expectedPopCount = 0;
872                    for (int stackIndex = stackSize - popCount; stackIndex < stackSize; stackIndex++)
873                    {
874                        // Is this stack entry pushed by any producer
875                        // (because it is required by other consumers)?
876                        if (isStackEntryPresentBefore(offset, stackIndex))
877                        {
878                            // Mark all produced stack entries.
879                            markStackEntryProducers(offset, stackIndex);
880
881                            // Remember to pop it.
882                            expectedPopCount++;
883                        }
884                    }
885
886                    // Pop the unnecessary stack entries.
887                    if (expectedPopCount > 0)
888                    {
889                        if (DEBUG) System.out.println("  Replacing unmarked consumer "+instruction.toString(offset));
890
891                        insertPopInstructions(offset, true, false, expectedPopCount);
892                    }
893                }
894
895                // Check all stack entries that would be pushed.
896                // Typical case: never.
897                int pushCount = instruction.stackPushCount(clazz);
898                if (pushCount > 0)
899                {
900                    TracedStack tracedStack =
901                        partialEvaluator.getStackAfter(offset);
902
903                    int stackSize = tracedStack.size();
904
905                    int expectedPushCount = 0;
906                    for (int stackIndex = stackSize - pushCount; stackIndex < stackSize; stackIndex++)
907                    {
908                        // Is the stack entry required by consumers?
909                        if (isStackEntryNecessaryAfter(offset, stackIndex))
910                        {
911                            // Remember to push it.
912                            expectedPushCount++;
913                        }
914                    }
915
916                    // Push some necessary stack entries.
917                    if (expectedPushCount > 0)
918                    {
919                        if (DEBUG) System.out.println("  Replacing unmarked producer "+instruction.toString(offset));
920
921                        insertPushInstructions(offset, true, false, tracedStack.getTop(0).computationalType());
922                    }
923                }
924            }
925        }
926
927
928        public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
929        {
930            if (isInstructionNecessary(offset) &&
931                isDupOrSwap(simpleInstruction))
932            {
933                int stackSizeBefore = partialEvaluator.getStackBefore(offset).size();
934
935                // Check all stack entries that are popped.
936                // Typical case: a freshly marked variable initialization that
937                // requires some value on the stack.
938                int popCount = simpleInstruction.stackPopCount(clazz);
939                if (popCount > 0)
940                {
941                    for (int stackIndex = stackSizeBefore - popCount; stackIndex < stackSizeBefore; stackIndex++)
942                    {
943                        // Is this stack entry pushed by any producer
944                        // (because it is required by other consumers)?
945                        if (isStackEntryPresentBefore(offset, stackIndex))
946                        {
947                            // Mark all produced stack entries.
948                            markStackEntryProducers(offset, stackIndex);
949                        }
950                    }
951                }
952
953                int topBefore = stackSizeBefore - 1;
954                int topAfter  = partialEvaluator.getStackAfter(offset).size() - 1;
955
956                byte oldOpcode = simpleInstruction.opcode;
957
958                // Simplify the dup/swap instruction if possible.
959                int newOpcodes = fixDupSwap(offset, oldOpcode, topBefore, topAfter);
960
961                // Did we find a suitabe (extended) opcode?
962                if (newOpcodes == UNSUPPORTED)
963                {
964                    // We can't easily emulate some constructs.
965                    throw new UnsupportedOperationException("Can't handle "+simpleInstruction.toString()+" instruction at ["+offset +"]");
966                }
967
968                // Is there a single replacement opcode?
969                if ((newOpcodes & ~0xff) == 0)
970                {
971                    byte newOpcode = (byte)newOpcodes;
972
973                    if      (newOpcode == InstructionConstants.OP_NOP)
974                    {
975                        // Delete the instruction.
976                        codeAttributeEditor.deleteInstruction(offset);
977
978                        if (extraDeletedInstructionVisitor != null)
979                        {
980                            extraDeletedInstructionVisitor.visitSimpleInstruction(null, null, null, offset, null);
981                        }
982
983                        if (DEBUG) System.out.println("  Deleting marked instruction "+simpleInstruction.toString(offset));
984                    }
985                    else if (newOpcode == oldOpcode)
986                    {
987                        // Leave the instruction unchanged.
988                        codeAttributeEditor.undeleteInstruction(offset);
989
990                        if (DEBUG) System.out.println("  Marking unchanged instruction "+simpleInstruction.toString(offset));
991                    }
992                    else
993                    {
994                        // Replace the instruction.
995                        Instruction replacementInstruction = new SimpleInstruction(newOpcode);
996                        codeAttributeEditor.replaceInstruction(offset,
997                                                               replacementInstruction);
998
999                        if (DEBUG) System.out.println("  Replacing instruction "+simpleInstruction.toString(offset)+" by "+replacementInstruction.toString());
1000                    }
1001                }
1002                else
1003                {
1004                    // Collect the replacement instructions.
1005                    Instruction[] replacementInstructions = new Instruction[4];
1006
1007                    if (DEBUG) System.out.println("  Replacing instruction "+simpleInstruction.toString(offset)+" by");
1008                    int count = 0;
1009                    while (newOpcodes != 0)
1010                    {
1011                        SimpleInstruction replacementInstruction = new SimpleInstruction((byte)newOpcodes);
1012                        replacementInstructions[count++] = replacementInstruction;
1013
1014                        if (DEBUG) System.out.println("    "+replacementInstruction.toString());
1015                        newOpcodes >>>= 8;
1016                    }
1017
1018                    // Create a properly sized array.
1019                    if (count < 4)
1020                    {
1021                        Instruction[] newInstructions = new Instruction[count];
1022                        System.arraycopy(replacementInstructions, 0, newInstructions, 0, count);
1023                        replacementInstructions = newInstructions;
1024                    }
1025
1026                    codeAttributeEditor.replaceInstruction(offset,
1027                                                           replacementInstructions);
1028                }
1029            }
1030            else
1031            {
1032                visitAnyInstruction(clazz, method, codeAttribute, offset, simpleInstruction);
1033            }
1034        }
1035
1036
1037        /**
1038         * Returns a dup/swap opcode that is corrected for the stack entries
1039         * that are present before the instruction and necessary after the
1040         * instruction. The returned integer opcode may contain multiple byte
1041         * opcodes (least significant byte first).
1042         * @param instructionOffset the offset of the dup/swap instruction.
1043         * @param dupSwapOpcode     the original dup/swap opcode.
1044         * @param topBefore         the index of the top stack entry before
1045         *                          the instruction (counting from the bottom).
1046         * @param topAfter          the index of the top stack entry after
1047         *                          the instruction (counting from the bottom).
1048         * @return the corrected opcode.
1049         */
1050        private int fixDupSwap(int  instructionOffset,
1051                               byte dupSwapOpcode,
1052                               int  topBefore,
1053                               int  topAfter)
1054        {
1055            switch (dupSwapOpcode)
1056            {
1057                case InstructionConstants.OP_DUP:     return fixedDup    (instructionOffset, topBefore, topAfter);
1058                case InstructionConstants.OP_DUP_X1:  return fixedDup_x1 (instructionOffset, topBefore, topAfter);
1059                case InstructionConstants.OP_DUP_X2:  return fixedDup_x2 (instructionOffset, topBefore, topAfter);
1060                case InstructionConstants.OP_DUP2:    return fixedDup2   (instructionOffset, topBefore, topAfter);
1061                case InstructionConstants.OP_DUP2_X1: return fixedDup2_x1(instructionOffset, topBefore, topAfter);
1062                case InstructionConstants.OP_DUP2_X2: return fixedDup2_x2(instructionOffset, topBefore, topAfter);
1063                case InstructionConstants.OP_SWAP:    return fixedSwap   (instructionOffset, topBefore, topAfter);
1064                default: throw new IllegalArgumentException("Not a dup/swap opcode ["+dupSwapOpcode+"]");
1065            }
1066        }
1067
1068
1069        private int fixedDup(int instructionOffset, int topBefore, int topAfter)
1070        {
1071            boolean stackEntryPresent0 = isStackEntryPresentBefore(instructionOffset, topBefore - 0);
1072
1073            boolean stackEntryNecessary0 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 0);
1074            boolean stackEntryNecessary1 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 1);
1075
1076            // Figure out which stack entries should be moved,
1077            // copied, or removed.
1078            return
1079                stackEntryNecessary0 ?
1080                    stackEntryNecessary1 ? DUP : // ...O -> ...OO
1081                                           NOP : // ...O -> ...O
1082                stackEntryNecessary1     ? NOP : // ...O -> ...O
1083                stackEntryPresent0       ? POP : // ...O -> ...
1084                                           NOP;  // ...  -> ...
1085        }
1086
1087
1088        private int fixedDup_x1(int instructionOffset, int topBefore, int topAfter)
1089        {
1090            boolean stackEntryPresent0 = isStackEntryPresentBefore(instructionOffset, topBefore - 0);
1091            boolean stackEntryPresent1 = isStackEntryPresentBefore(instructionOffset, topBefore - 1);
1092
1093            boolean stackEntryNecessary0 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 0);
1094            boolean stackEntryNecessary1 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 1);
1095            boolean stackEntryNecessary2 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 2);
1096
1097            // Figure out which stack entries should be moved,
1098            // copied, or removed.
1099            return
1100                stackEntryNecessary1 ?
1101                    stackEntryNecessary2 ?
1102                        stackEntryNecessary0 ? DUP_X1       : // ...XO -> ...OXO
1103                                               SWAP         : // ...XO -> ...OX
1104                    // !stackEntryNecessary2
1105                        stackEntryNecessary0 ? NOP          : // ...XO -> ...XO
1106                        stackEntryPresent0   ? POP          : // ...XO -> ...X
1107                                               NOP          : // ...X  -> ...X
1108                stackEntryPresent1 ?
1109                    stackEntryNecessary2 ?
1110                        stackEntryNecessary0 ? SWAP_POP_DUP : // ...XO -> ...OO
1111                                               POP_X1       : // ...XO -> ...O
1112                    // !stackEntryNecessary2
1113                        stackEntryNecessary0 ? POP_X1       : // ...XO -> ...O
1114                        stackEntryPresent0   ? POP2         : // ...XO -> ...
1115                                               POP          : // ...X  -> ...
1116                // !stackEntryPresent1
1117                    stackEntryNecessary2 ?
1118                        stackEntryNecessary0 ? DUP          : // ...O -> ...OO
1119                                               NOP          : // ...O -> ...O
1120                    // !stackEntryNecessary2
1121                        stackEntryNecessary0 ? NOP          : // ...O -> ...O
1122                        stackEntryPresent0   ? POP          : // ...O -> ...
1123                                               NOP;           // ...  -> ...
1124        }
1125
1126
1127        private int fixedDup_x2(int instructionOffset, int topBefore, int topAfter)
1128        {
1129            boolean stackEntryPresent0 = isStackEntryPresentBefore(instructionOffset, topBefore - 0);
1130            boolean stackEntryPresent1 = isStackEntryPresentBefore(instructionOffset, topBefore - 1);
1131            boolean stackEntryPresent2 = isStackEntryPresentBefore(instructionOffset, topBefore - 2);
1132
1133            boolean stackEntryNecessary0 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 0);
1134            boolean stackEntryNecessary1 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 1);
1135            boolean stackEntryNecessary2 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 2);
1136            boolean stackEntryNecessary3 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 3);
1137
1138            // Figure out which stack entries should be moved,
1139            // copied, or removed.
1140            return
1141                stackEntryNecessary1 ?
1142                    stackEntryNecessary2 ?
1143                        stackEntryNecessary3 ?
1144                            stackEntryNecessary0 ? DUP_X2          : // ...XYO -> ...OXYO
1145                                                   MOV_X2          : // ...XYO -> ...OXY
1146                        // !stackEntryNecessary3
1147                            stackEntryNecessary0 ? NOP             : // ...XYO -> ...XYO
1148                            stackEntryPresent0   ? POP             : // ...XYO -> ...XY
1149                                                   NOP             : // ...XY  -> ...XY
1150                    stackEntryPresent2 ?
1151                        stackEntryNecessary3 ?
1152                        //  stackEntryNecessary0 ? UNSUPPORTED     : // ...XYO -> ...OYO
1153                                                   UNSUPPORTED     : // ...XYO -> ...OY
1154                        // !stackEntryNecessary3
1155                            stackEntryNecessary0 ? POP_X2          : // ...XYO -> ...YO
1156                            stackEntryPresent0   ? POP_SWAP_POP    : // ...XYO -> ...Y
1157                                                   POP_X1          : // ...XY  -> ...Y
1158                    // !stackEntryPresent2
1159                        stackEntryNecessary3 ?
1160                            stackEntryNecessary0 ? DUP_X1          : // ...YO -> ...OYO
1161                                                   SWAP            : // ...YO -> ...OY
1162                        // !stackEntryNecessary3
1163                            stackEntryNecessary0 ? NOP             : // ...YO -> ...YO
1164                            stackEntryPresent0   ? POP             : // ...YO -> ...Y
1165                                                   NOP             : // ...Y  -> ...Y
1166                stackEntryPresent1 ?
1167                    stackEntryNecessary2 ?
1168                        stackEntryNecessary3 ?
1169                            stackEntryNecessary0 ? SWAP_POP_DUP_X1 : // ...XYO -> ...OXO
1170                                                   DUP_X2_POP2     : // ...XYO -> ...OX
1171                        // !stackEntryNecessary3
1172                            stackEntryNecessary0 ? POP_X1          : // ...XYO -> ...XO
1173                            stackEntryPresent0   ? POP2            : // ...XYO -> ...X
1174                                                   POP             : // ...XY  -> ...X
1175                    stackEntryPresent2 ?
1176                        stackEntryNecessary3 ?
1177                            stackEntryNecessary0 ? UNSUPPORTED     : // ...XYO -> ...OO
1178                                                   POP2_X1         : // ...XYO -> ...O
1179                        // !stackEntryNecessary3
1180                            stackEntryNecessary0 ? POP2_X1         : // ...XYO -> ...O
1181                            stackEntryPresent0   ? POP3            : // ...XYO -> ...
1182                                                   POP2            : // ...XY  -> ...
1183                    // !stackEntryPresent2
1184                        stackEntryNecessary3 ?
1185                            stackEntryNecessary0 ? SWAP_POP_DUP    : // ...YO -> ...OO
1186                                                   POP_X1          : // ...YO -> ...O
1187                        // !stackEntryNecessary3
1188                            stackEntryNecessary0 ? POP_X1          : // ...YO -> ...O
1189                            stackEntryPresent0   ? POP2            : // ...YO -> ...
1190                                                   POP             : // ...Y  -> ...
1191                // !stackEntryPresent1
1192                    stackEntryNecessary2 ?
1193                        stackEntryNecessary3 ?
1194                            stackEntryNecessary0 ? DUP_X1          : // ...XO -> ...OXO
1195                                                   SWAP            : // ...XO -> ...OX
1196                        // !stackEntryNecessary3
1197                            stackEntryNecessary0 ? NOP             : // ...XO -> ...XO
1198                            stackEntryPresent0   ? POP             : // ...XO -> ...X
1199                                                   NOP             : // ...X  -> ...X
1200                    stackEntryPresent2 ?
1201                        stackEntryNecessary3 ?
1202                            stackEntryNecessary0 ? SWAP_POP_DUP    : // ...XO -> ...OO
1203                                                   POP_X1          : // ...XO -> ...O
1204                        // !stackEntryNecessary3
1205                            stackEntryNecessary0 ? POP_X1          : // ...XO -> ...O
1206                            stackEntryPresent0   ? POP2            : // ...XO -> ...
1207                                                   POP             : // ...X  -> ...
1208                    // !stackEntryPresent2
1209                        stackEntryNecessary3 ?
1210                            stackEntryNecessary0 ? DUP             : // ...O -> ...OO
1211                                                   NOP             : // ...O -> ...O
1212                        // !stackEntryNecessary3
1213                            stackEntryNecessary0 ? NOP             : // ...O -> ...O
1214                            stackEntryPresent0   ? POP             : // ...O -> ...
1215                                                   NOP;              // ...  -> ...
1216        }
1217
1218
1219        private int fixedDup2(int instructionOffset, int topBefore, int topAfter)
1220        {
1221            boolean stackEntryPresent0 = isStackEntryPresentBefore(instructionOffset, topBefore - 0);
1222            boolean stackEntryPresent1 = isStackEntryPresentBefore(instructionOffset, topBefore - 1);
1223
1224            boolean stackEntryNecessary0 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 0);
1225            boolean stackEntryNecessary1 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 1);
1226            boolean stackEntryNecessary2 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 2);
1227            boolean stackEntryNecessary3 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 3);
1228
1229            return
1230                stackEntryNecessary3 ?
1231                    stackEntryNecessary2 ?
1232                        stackEntryNecessary1 ?
1233                            stackEntryNecessary0 ? DUP2             : // ...AB -> ...ABAB
1234                                                   SWAP_DUP_X1      : // ...AB -> ...ABA
1235                        // !stackEntryNecessary1
1236                            stackEntryNecessary0 ? DUP              : // ...AB -> ...ABB
1237                                                   NOP              : // ...AB -> ...AB
1238                    // !stackEntryNecessary2
1239                        stackEntryNecessary1 ?
1240                            stackEntryNecessary0 ? SWAP_DUP_X1_SWAP : // ...AB -> ...AAB
1241                            stackEntryPresent0   ? POP_DUP          : // ...AB -> ...AA
1242                                                   DUP              : // ...A  -> ...AA
1243                        // !stackEntryNecessary1
1244                            stackEntryNecessary0 ? NOP              : // ...AB -> ...AB
1245                            stackEntryPresent0   ? POP              : // ...AB -> ...A
1246                                                   NOP              : // ...A  -> ...A
1247                // !stackEntryNecessary3
1248                    stackEntryNecessary2 ?
1249                        stackEntryNecessary1 ?
1250                            stackEntryNecessary0 ? DUP_X1           : // ...AB -> ...BAB
1251                                                   SWAP             : // ...AB -> ...BA
1252                        stackEntryPresent1 ?
1253                            stackEntryNecessary0 ? SWAP_POP_DUP     : // ...AB -> ...BB
1254                                                   POP_X1           : // ...AB -> ...B
1255                        // !stackEntryPresent1
1256                            stackEntryNecessary0 ? POP              : // ...B  -> ...BB
1257                                                   NOP              : // ...B  -> ...B
1258                    // !stackEntryNecessary2
1259                        stackEntryNecessary1 ?
1260                            stackEntryNecessary0 ? NOP              : // ...AB -> ...AB
1261                            stackEntryPresent0   ? POP              : // ...AB -> ...A
1262                                                   NOP              : // ...A  -> ...A
1263                        stackEntryPresent1 ?
1264                            stackEntryNecessary0 ? POP_X1           : // ...AB -> ...B
1265                            stackEntryPresent0   ? POP2             : // ...AB -> ...
1266                                                   POP              : // ...A  -> ...
1267                        // !stackEntryPresent1
1268                            stackEntryNecessary0 ? NOP              : // ...B  -> ...B
1269                            stackEntryPresent0   ? POP              : // ...B  -> ...
1270                                                   NOP;               // ...   -> ...
1271        }
1272
1273
1274        private int fixedDup2_x1(int instructionOffset, int topBefore, int topAfter)
1275        {
1276            // We're currently assuming the value to be duplicated
1277            // is a long or a double, taking up two slots, or at
1278            // least consistent.
1279            boolean stackEntriesPresent01 = isStackEntriesPresentBefore(instructionOffset, topBefore - 0, topBefore - 1);
1280            boolean stackEntryPresent2    = isStackEntryPresentBefore(  instructionOffset, topBefore - 2);
1281
1282            boolean stackEntriesNecessary01 = isStackEntriesNecessaryAfter(instructionOffset, topAfter - 0, topAfter - 1);
1283            boolean stackEntryNecessary2    = isStackEntryNecessaryAfter(  instructionOffset, topAfter - 2);
1284            boolean stackEntriesNecessary34 = isStackEntriesNecessaryAfter(instructionOffset, topAfter - 3, topAfter - 4);
1285
1286            // Figure out which stack entries should be moved,
1287            // copied, or removed.
1288            return
1289                stackEntryNecessary2 ?
1290                    stackEntriesNecessary34 ?
1291                        stackEntriesNecessary01 ? DUP2_X1      : // ...XAB -> ...ABXAB
1292                                                  MOV2_X1      : // ...XAB -> ...ABX
1293                    // !stackEntriesNecessary34
1294                        stackEntriesNecessary01 ? NOP          : // ...XAB -> ...XAB
1295                        stackEntriesPresent01   ? POP2         : // ...XAB -> ...X
1296                                                  NOP          : // ...X   -> ...X
1297                stackEntryPresent2 ?
1298                    stackEntriesNecessary34 ?
1299                        stackEntriesNecessary01 ? UNSUPPORTED  : // ...XAB -> ...ABAB
1300                                                  POP_X2       : // ...XAB -> ...AB
1301                    // !stackEntriesNecessary34
1302                        stackEntriesNecessary01 ? DUP2_X1_POP3 : // ...XAB -> ...AB
1303                        stackEntriesPresent01   ? POP3         : // ...XAB -> ...
1304                                                  POP          : // ...X   -> ...
1305                // !stackEntryPresent2
1306                    stackEntriesNecessary34 ?
1307                        stackEntriesNecessary01 ? DUP2         : // ...AB -> ...ABAB
1308                                                  NOP          : // ...AB -> ...AB
1309                    // !stackEntriesNecessary34
1310                        stackEntriesNecessary01 ? NOP          : // ...AB -> ...AB
1311                        stackEntriesPresent01   ? POP2         : // ...AB -> ...
1312                                                  NOP;           // ...   -> ...
1313        }
1314
1315
1316        private int fixedDup2_x2(int instructionOffset, int topBefore, int topAfter)
1317        {
1318            // We're currently assuming the value to be duplicated
1319            // is a long or a double, taking up two slots, or at
1320            // least consistent.
1321            boolean stackEntriesPresent01 = isStackEntriesPresentBefore(instructionOffset, topBefore - 0, topBefore - 1);
1322            boolean stackEntryPresent2    = isStackEntryPresentBefore(  instructionOffset, topBefore - 2);
1323            boolean stackEntryPresent3    = isStackEntryPresentBefore(  instructionOffset, topBefore - 3);
1324
1325            boolean stackEntriesNecessary01 = isStackEntriesNecessaryAfter(instructionOffset, topAfter - 0, topAfter - 1);
1326            boolean stackEntryNecessary2    = isStackEntryNecessaryAfter(  instructionOffset, topAfter - 2);
1327            boolean stackEntryNecessary3    = isStackEntryNecessaryAfter(  instructionOffset, topAfter - 3);
1328            boolean stackEntriesNecessary45 = isStackEntriesNecessaryAfter(instructionOffset, topAfter - 4, topAfter - 5);
1329
1330            // Figure out which stack entries should be moved,
1331            // copied, or removed.
1332            return
1333                stackEntryNecessary2 ?
1334                    stackEntryNecessary3 ?
1335                        stackEntriesNecessary45 ?
1336                            stackEntriesNecessary01 ? DUP2_X2          : // ...XYAB -> ...ABXYAB
1337                                                      MOV2_X2          : // ...XYAB -> ...ABXY
1338                        // !stackEntriesNecessary45
1339                            stackEntriesNecessary01 ? NOP              : // ...XYAB -> ...XYAB
1340                            stackEntriesPresent01   ? POP2             : // ...XYAB -> ...XY
1341                                                      NOP              : // ...XY   -> ...XY
1342                    stackEntryPresent3 ?
1343                        stackEntriesNecessary45 ?
1344                            stackEntriesNecessary01 ? UNSUPPORTED      : // ...XYAB -> ...ABYAB
1345                                                      DUP2_X2_SWAP_POP : // ...XYAB -> ...ABY
1346                        // !stackEntriesNecessary45
1347                            stackEntriesNecessary01 ? POP_X3           : // ...XYAB -> ...YAB
1348                            stackEntriesPresent01   ? POP2_SWAP_POP    : // ...XYAB -> ...Y
1349                                                      POP_X1           : // ...XY   -> ...Y
1350                    // !stackEntryPresent3
1351                        stackEntriesNecessary45 ?
1352                            stackEntriesNecessary01 ? DUP2_X1          : // ...YAB -> ...ABYAB
1353                                                      MOV2_X1          : // ...YAB -> ...ABY
1354                        // !stackEntriesNecessary45
1355                            stackEntriesNecessary01 ? NOP              : // ...YAB -> ...YAB
1356                            stackEntriesPresent01   ? POP2             : // ...YAB -> ...Y
1357                                                      NOP              : // ...Y   -> ...Y
1358                stackEntryPresent2 ?
1359                    stackEntryNecessary3 ?
1360                        stackEntriesNecessary45 ?
1361                            stackEntriesNecessary01 ? UNSUPPORTED      : // ...XYAB -> ...ABXAB
1362                                                      DUP2_X2_POP3     : // ...XYAB -> ...ABX
1363                        // !stackEntriesNecessary45
1364                            stackEntriesNecessary01 ? POP_X2           : // ...XYAB -> ...XAB
1365                            stackEntriesPresent01   ? POP3             : // ...XYAB -> ...X
1366                                                      POP              : // ...XY   -> ...X
1367                    stackEntryPresent3 ?
1368                        stackEntriesNecessary45 ?
1369                            stackEntriesNecessary01 ? UNSUPPORTED      : // ...XYAB -> ...ABAB
1370                                                      POP2_X2          : // ...XYAB -> ...AB
1371                        // !stackEntriesNecessary45
1372                            stackEntriesNecessary01 ? POP2_X2          : // ...XYAB -> ...AB
1373                            stackEntriesPresent01   ? POP4             : // ...XYAB -> ...
1374                                                      POP2             : // ...XY   -> ...
1375                    // !stackEntryPresent3
1376                        stackEntriesNecessary45 ?
1377                            stackEntriesNecessary01 ? UNSUPPORTED      : // ...YAB -> ...ABAB
1378                                                      POP_X2           : // ...YAB -> ...AB
1379                        // !stackEntriesNecessary45
1380                            stackEntriesNecessary01 ? POP_X2           : // ...YAB -> ...AB
1381                            stackEntriesPresent01   ? POP3             : // ...YAB -> ...
1382                                                      POP              : // ...Y   -> ...
1383                // !stackEntryPresent2
1384                    stackEntryNecessary3 ?
1385                        stackEntriesNecessary45 ?
1386                            stackEntriesNecessary01 ? DUP2_X1          : // ...XAB -> ...ABXAB
1387                                                      MOV2_X1          : // ...XAB -> ...ABX
1388                        // !stackEntriesNecessary45
1389                            stackEntriesNecessary01 ? NOP              : // ...XAB -> ...XAB
1390                            stackEntriesPresent01   ? POP2             : // ...XAB -> ...X
1391                                                      NOP              : // ...X   -> ...X
1392                    stackEntryPresent3 ?
1393                        stackEntriesNecessary45 ?
1394                            stackEntriesNecessary01 ? UNSUPPORTED      : // ...XAB -> ...ABAB
1395                                                      POP_X2           : // ...XAB -> ...AB
1396                        // !stackEntriesNecessary45
1397                            stackEntriesNecessary01 ? POP_X2           : // ...XAB -> ...AB
1398                            stackEntriesPresent01   ? POP3             : // ...XAB -> ...
1399                                                      POP              : // ...X   -> ...
1400                    // !stackEntryPresent3
1401                        stackEntriesNecessary45 ?
1402                            stackEntriesNecessary01 ? DUP2             : // ...AB -> ...ABAB
1403                                                      NOP              : // ...AB -> ...AB
1404                        // !stackEntriesNecessary45
1405                            stackEntriesNecessary01 ? NOP              : // ...AB -> ...AB
1406                            stackEntriesPresent01   ? POP2             : // ...AB -> ...
1407                                                      NOP;               // ...   -> ...
1408        }
1409
1410
1411        private int fixedSwap(int instructionOffset, int topBefore, int topAfter)
1412        {
1413            boolean stackEntryPresent0 = isStackEntryPresentBefore(instructionOffset, topBefore - 0);
1414            boolean stackEntryPresent1 = isStackEntryPresentBefore(instructionOffset, topBefore - 1);
1415
1416            boolean stackEntryNecessary0 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 0);
1417            boolean stackEntryNecessary1 = isStackEntryNecessaryAfter(instructionOffset, topAfter - 1);
1418
1419            // Figure out which stack entries should be moved
1420            // or removed.
1421            return
1422                stackEntryNecessary0 ?
1423                    stackEntryNecessary1 ? SWAP   : // ...AB -> ...BA
1424                    stackEntryPresent0   ? POP    : // ...AB -> ...A
1425                                           NOP    : // ...A  -> ...A
1426                stackEntryPresent1       ? POP_X1 : // ...AB -> ...B
1427                                           NOP;     // ...B -> ...B
1428        }
1429    }
1430
1431
1432    // Small utility methods.
1433
1434    /**
1435     * Marks the producing instructions of the variable consumer at the given
1436     * offset.
1437     * @param consumerOffset the offset of the variable consumer.
1438     * @param variableIndex  the index of the variable that is loaded.
1439     */
1440    private void markVariableProducers(int consumerOffset,
1441                                       int variableIndex)
1442    {
1443        InstructionOffsetValue producerOffsets =
1444            partialEvaluator.getVariablesBefore(consumerOffset).getProducerValue(variableIndex).instructionOffsetValue();
1445
1446        if (producerOffsets != null)
1447        {
1448            int offsetCount = producerOffsets.instructionOffsetCount();
1449            for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
1450            {
1451                // Make sure the variable and the instruction are marked
1452                // at the producing offset.
1453                int offset = producerOffsets.instructionOffset(offsetIndex);
1454
1455                markInstruction(offset);
1456            }
1457        }
1458    }
1459
1460
1461    /**
1462     * Ensures that the given variable is initialized before the specified
1463     * consumer of that variable, in the JVM's view.
1464     * @param consumerOffset the instruction offset before which the variable
1465     *                       needs to be initialized.
1466     * @param variableIndex  the index of the variable.
1467     */
1468    private void markVariableInitializersBefore(int consumerOffset,
1469                                                int variableIndex)
1470    {
1471        // Make sure the variable is initialized after all producers.
1472        // Use the simple evaluator, to get the JVM's view of what is
1473        // initialized.
1474        InstructionOffsetValue producerOffsets =
1475            simplePartialEvaluator.getVariablesBefore(consumerOffset).getProducerValue(variableIndex).instructionOffsetValue();
1476
1477        int offsetCount = producerOffsets.instructionOffsetCount();
1478        for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
1479        {
1480            // Avoid infinite loops by only looking at producers before
1481            // the consumer.
1482            int producerOffset =
1483                producerOffsets.instructionOffset(offsetIndex);
1484            if (producerOffset < consumerOffset)
1485            {
1486                markVariableInitializersAfter(producerOffset, variableIndex);
1487            }
1488        }
1489    }
1490
1491
1492    /**
1493     * Ensures that the given variable is initialized after the specified
1494     * producer of that variable, in the JVM's view.
1495     * @param producerOffset the instruction offset after which the variable
1496     *                       needs to be initialized.
1497     * @param variableIndex  the index of the variable.
1498     */
1499    private void markVariableInitializersAfter(int producerOffset,
1500                                               int variableIndex)
1501    {
1502        // No problem if the producer has already been marked.
1503        if (!isInstructionNecessary(producerOffset))
1504        {
1505            // Is the unmarked producer a variable initialization?
1506            if (isVariableInitialization(producerOffset, variableIndex))
1507            {
1508                // Mark the producer.
1509                if (DEBUG) System.out.print("  Marking initialization of v"+variableIndex+" at ");
1510
1511                markInstruction(producerOffset);
1512
1513                if (DEBUG) System.out.println();
1514            }
1515            else
1516            {
1517                // Don't mark the producer, but recursively look at the
1518                // preceding producers of the same variable. Their values
1519                // will fall through, replacing this producer.
1520                markVariableInitializersBefore(producerOffset, variableIndex);
1521            }
1522        }
1523    }
1524
1525
1526    /**
1527     * Marks the stack entries and their producing instructions of the
1528     * consumer at the given offset.
1529     * @param clazz          the containing class.
1530     * @param consumerOffset the offset of the consumer.
1531     * @param consumer       the consumer of the stack entries.
1532     */
1533    private void markStackProducers(Clazz       clazz,
1534                                    int         consumerOffset,
1535                                    Instruction consumer)
1536    {
1537        TracedStack tracedStack =
1538            partialEvaluator.getStackBefore(consumerOffset);
1539
1540        int stackSize = tracedStack.size();
1541
1542        // Mark the producers of the popped values.
1543        int popCount = consumer.stackPopCount(clazz);
1544        for (int stackIndex = stackSize - popCount; stackIndex < stackSize; stackIndex++)
1545        {
1546            markStackEntryProducers(consumerOffset, stackIndex);
1547        }
1548    }
1549
1550
1551    /**
1552     * Marks the stack entry and the corresponding producing instructions
1553     * of the consumer at the given offset, if the stack entry of the
1554     * consumer is marked.
1555     * @param consumerOffset     the offset of the consumer.
1556     * @param consumerTopStackIndex the index of the stack entry to be checked
1557     *                           (counting from the top).
1558     * @param producerTopStackIndex the index of the stack entry to be marked
1559     *                           (counting from the top).
1560     */
1561    private void conditionallyMarkStackEntryProducers(int consumerOffset,
1562                                                      int consumerTopStackIndex,
1563                                                      int producerTopStackIndex)
1564    {
1565        int consumerBottomStackIndex = partialEvaluator.getStackAfter(consumerOffset).size() - consumerTopStackIndex - 1;
1566
1567        if (isStackEntryNecessaryAfter(consumerOffset, consumerBottomStackIndex))
1568        {
1569            int producerBottomStackIndex = partialEvaluator.getStackBefore(consumerOffset).size() - producerTopStackIndex - 1;
1570
1571            markStackEntryProducers(consumerOffset, producerBottomStackIndex);
1572        }
1573    }
1574
1575
1576    /**
1577     * Marks the stack entry and the corresponding producing instructions
1578     * of the consumer at the given offset.
1579     * @param consumerOffset the offset of the consumer.
1580     * @param stackIndex     the index of the stack entry to be marked
1581     *                        (counting from the bottom).
1582     */
1583    private void markStackEntryProducers(int consumerOffset,
1584                                         int stackIndex)
1585    {
1586        if (!isStackSimplifiedBefore(consumerOffset, stackIndex))
1587        {
1588            markStackEntryProducers(partialEvaluator.getStackBefore(consumerOffset).getBottomProducerValue(stackIndex).instructionOffsetValue(),
1589                                    stackIndex);
1590        }
1591    }
1592
1593
1594    /**
1595     * Marks the stack entry and its producing instructions at the given
1596     * offsets.
1597     * @param producerOffsets the offsets of the producers to be marked.
1598     * @param stackIndex      the index of the stack entry to be marked
1599     *                        (counting from the bottom).
1600     */
1601    private void markStackEntryProducers(InstructionOffsetValue producerOffsets,
1602                                         int                    stackIndex)
1603    {
1604        if (producerOffsets != null)
1605        {
1606            int offsetCount = producerOffsets.instructionOffsetCount();
1607            for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
1608            {
1609                // Make sure the stack entry and the instruction are marked
1610                // at the producing offset.
1611                int offset = producerOffsets.instructionOffset(offsetIndex);
1612
1613                markStackEntryAfter(offset, stackIndex);
1614                markInstruction(offset);
1615            }
1616        }
1617    }
1618
1619
1620    /**
1621     * Marks the stack entry and its initializing instruction
1622     * ('invokespecial *.<init>') for the given 'new' instruction offset.
1623     * @param newInstructionOffset the offset of the 'new' instruction.
1624     */
1625    private void markInitialization(int newInstructionOffset)
1626    {
1627        int initializationOffset =
1628            partialEvaluator.initializationOffset(newInstructionOffset);
1629
1630        TracedStack tracedStack =
1631            partialEvaluator.getStackAfter(newInstructionOffset);
1632
1633        markStackEntryAfter(initializationOffset, tracedStack.size() - 1);
1634        markInstruction(initializationOffset);
1635    }
1636
1637
1638    /**
1639     * Marks the branch instructions of straddling branches, if they straddle
1640     * some code that has been marked.
1641     * @param instructionOffset   the offset of the branch origin or branch target.
1642     * @param branchOffsets       the offsets of the straddling branch targets
1643     *                            or branch origins.
1644     * @param isPointingToTargets <code>true</code> if the above offsets are
1645     *                            branch targets, <code>false</code> if they
1646     *                            are branch origins.
1647     */
1648    private void markStraddlingBranches(int                    instructionOffset,
1649                                        InstructionOffsetValue branchOffsets,
1650                                        boolean                isPointingToTargets)
1651    {
1652        if (branchOffsets != null)
1653        {
1654            // Loop over all branch offsets.
1655            int branchCount = branchOffsets.instructionOffsetCount();
1656            for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
1657            {
1658                // Is the branch straddling forward any necessary instructions?
1659                int branchOffset = branchOffsets.instructionOffset(branchIndex);
1660
1661                // Is the offset pointing to a branch origin or to a branch target?
1662                if (isPointingToTargets)
1663                {
1664                    markStraddlingBranch(instructionOffset,
1665                                         branchOffset,
1666                                         instructionOffset,
1667                                         branchOffset);
1668                }
1669                else
1670                {
1671                    markStraddlingBranch(instructionOffset,
1672                                         branchOffset,
1673                                         branchOffset,
1674                                         instructionOffset);
1675                }
1676            }
1677        }
1678    }
1679
1680
1681    private void markStraddlingBranch(int instructionOffsetStart,
1682                                      int instructionOffsetEnd,
1683                                      int branchOrigin,
1684                                      int branchTarget)
1685    {
1686        if (!isInstructionNecessary(branchOrigin) &&
1687            isAnyInstructionNecessary(instructionOffsetStart, instructionOffsetEnd))
1688        {
1689            if (DEBUG) System.out.print("["+branchOrigin+"->"+branchTarget+"]");
1690
1691            // Mark the branch instruction.
1692            markInstruction(branchOrigin);
1693        }
1694    }
1695
1696
1697    /**
1698     * Pushes a specified type of stack entry before or at the given offset.
1699     * The instruction is marked as necessary.
1700     */
1701    private void insertPushInstructions(int     offset,
1702                                        boolean replace,
1703                                        boolean before,
1704                                        int     computationalType)
1705    {
1706        // Mark this instruction.
1707        markInstruction(offset);
1708
1709        // Create a simple push instrucion.
1710        Instruction replacementInstruction =
1711            new SimpleInstruction(pushOpcode(computationalType));
1712
1713        if (DEBUG) System.out.println(": "+replacementInstruction.toString(offset));
1714
1715        // Replace or insert the push instruction.
1716        insertInstruction(offset, replace, before, replacementInstruction);
1717    }
1718
1719
1720    /**
1721     * Returns the opcode of a push instruction corresponding to the given
1722     * computational type.
1723     * @param computationalType the computational type to be pushed on the stack.
1724     */
1725    private byte pushOpcode(int computationalType)
1726    {
1727        switch (computationalType)
1728        {
1729            case Value.TYPE_INTEGER:            return InstructionConstants.OP_ICONST_0;
1730            case Value.TYPE_LONG:               return InstructionConstants.OP_LCONST_0;
1731            case Value.TYPE_FLOAT:              return InstructionConstants.OP_FCONST_0;
1732            case Value.TYPE_DOUBLE:             return InstructionConstants.OP_DCONST_0;
1733            case Value.TYPE_REFERENCE:
1734            case Value.TYPE_INSTRUCTION_OFFSET: return InstructionConstants.OP_ACONST_NULL;
1735        }
1736
1737        throw new IllegalArgumentException("No push opcode for computational type ["+computationalType+"]");
1738    }
1739
1740
1741    /**
1742     * Pops the given number of stack entries at or after the given offset.
1743     * The instructions are marked as necessary.
1744     */
1745    private void insertPopInstructions(int     offset,
1746                                       boolean replace,
1747                                       boolean before,
1748                                       int     popCount)
1749    {
1750        // Mark this instruction.
1751        markInstruction(offset);
1752
1753        switch (popCount)
1754        {
1755            case 1:
1756            {
1757                // Replace or insert a single pop instruction.
1758                Instruction popInstruction =
1759                    new SimpleInstruction(InstructionConstants.OP_POP);
1760
1761                insertInstruction(offset, replace, before, popInstruction);
1762                break;
1763            }
1764            case 2:
1765            {
1766                // Replace or insert a single pop2 instruction.
1767                Instruction popInstruction =
1768                    new SimpleInstruction(InstructionConstants.OP_POP2);
1769
1770                insertInstruction(offset, replace, before, popInstruction);
1771                break;
1772            }
1773            default:
1774            {
1775                // Replace or insert the specified number of pop instructions.
1776                Instruction[] popInstructions =
1777                    new Instruction[popCount / 2 + popCount % 2];
1778
1779                Instruction popInstruction =
1780                    new SimpleInstruction(InstructionConstants.OP_POP2);
1781
1782                for (int index = 0; index < popCount / 2; index++)
1783                {
1784                      popInstructions[index] = popInstruction;
1785                }
1786
1787                if (popCount % 2 == 1)
1788                {
1789                    popInstruction =
1790                        new SimpleInstruction(InstructionConstants.OP_POP);
1791
1792                    popInstructions[popCount / 2] = popInstruction;
1793                }
1794
1795                insertInstructions(offset,
1796                                   replace,
1797                                   before,
1798                                   popInstruction,
1799                                   popInstructions);
1800                break;
1801            }
1802        }
1803    }
1804
1805
1806    /**
1807     * Inserts or replaces the given instruction at the given offset.
1808     */
1809    private void insertInstruction(int         offset,
1810                                   boolean     replace,
1811                                   boolean     before,
1812                                   Instruction instruction)
1813    {
1814        if (replace)
1815        {
1816            codeAttributeEditor.replaceInstruction(offset, instruction);
1817        }
1818        else
1819        {
1820            if (before)
1821            {
1822                codeAttributeEditor.insertBeforeInstruction(offset, instruction);
1823            }
1824            else
1825            {
1826                codeAttributeEditor.insertAfterInstruction(offset, instruction);
1827            }
1828
1829            if (extraAddedInstructionVisitor != null)
1830            {
1831                instruction.accept(null, null, null, offset, extraAddedInstructionVisitor);
1832            }
1833        }
1834    }
1835
1836
1837    /**
1838     * Inserts or replaces the given instruction at the given offset.
1839     */
1840    private void insertInstructions(int           offset,
1841                                    boolean       replace,
1842                                    boolean       before,
1843                                    Instruction   instruction,
1844                                    Instruction[] instructions)
1845    {
1846        if (replace)
1847        {
1848            codeAttributeEditor.replaceInstruction(offset, instructions);
1849
1850            if (extraAddedInstructionVisitor != null)
1851            {
1852                for (int index = 1; index < instructions.length; index++)
1853                {
1854                    instructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor);
1855                }
1856            }
1857        }
1858        else
1859        {
1860            if (before)
1861            {
1862                codeAttributeEditor.insertBeforeInstruction(offset, instructions);
1863            }
1864            else
1865            {
1866                codeAttributeEditor.insertAfterInstruction(offset, instructions);
1867            }
1868
1869            for (int index = 0; index < instructions.length; index++)
1870            {
1871                if (extraAddedInstructionVisitor != null)
1872                {
1873                    instructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor);
1874                }
1875            }
1876        }
1877    }
1878
1879
1880    /**
1881     * Replaces the instruction at a given offset by a static invocation.
1882     */
1883    private void replaceByStaticInvocation(Clazz               clazz,
1884                                           int                 offset,
1885                                           ConstantInstruction constantInstruction)
1886    {
1887        // Remember the replacement instruction.
1888        Instruction replacementInstruction =
1889             new ConstantInstruction(InstructionConstants.OP_INVOKESTATIC,
1890                                     constantInstruction.constantIndex);
1891
1892        if (DEBUG) System.out.println("  Replacing by static invocation "+constantInstruction.toString(offset)+" -> "+replacementInstruction.toString());
1893
1894        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1895    }
1896
1897
1898    /**
1899     * Replaces the given instruction by an infinite loop.
1900     */
1901    private void replaceByInfiniteLoop(Clazz clazz,
1902                                       int   offset)
1903    {
1904        if (DEBUG) System.out.println("  Inserting infinite loop at ["+offset+"]");
1905
1906        // Mark the instruction.
1907        markInstruction(offset);
1908
1909        // Replace the instruction by an infinite loop.
1910        Instruction replacementInstruction =
1911            new BranchInstruction(InstructionConstants.OP_GOTO, 0);
1912
1913        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1914    }
1915
1916
1917    // Small utility methods.
1918
1919    /**
1920     * Returns whether the given instruction is a dup or swap instruction
1921     * (dup, dup_x1, dup_x2, dup2, dup2_x1, dup2_x2, swap).
1922     */
1923    private boolean isDupOrSwap(Instruction instruction)
1924    {
1925        return instruction.opcode >= InstructionConstants.OP_DUP &&
1926               instruction.opcode <= InstructionConstants.OP_SWAP;
1927    }
1928
1929
1930    /**
1931     * Returns whether the given instruction is a pop instruction
1932     * (pop, pop2).
1933     */
1934    private boolean isPop(Instruction instruction)
1935    {
1936        return instruction.opcode == InstructionConstants.OP_POP ||
1937               instruction.opcode == InstructionConstants.OP_POP2;
1938    }
1939
1940
1941    /**
1942     * Returns whether any traced but unnecessary instruction between the two
1943     * given offsets is branching over the second given offset.
1944     */
1945    private boolean isAnyUnnecessaryInstructionBranchingOver(int instructionOffset1,
1946                                                             int instructionOffset2)
1947    {
1948        for (int offset = instructionOffset1; offset < instructionOffset2; offset++)
1949        {
1950            // Is it a traced but unmarked straddling branch?
1951            if (partialEvaluator.isTraced(offset) &&
1952                !isInstructionNecessary(offset)   &&
1953                isAnyLargerThan(partialEvaluator.branchTargets(offset),
1954                                instructionOffset2))
1955            {
1956                return true;
1957            }
1958        }
1959
1960        return false;
1961    }
1962
1963
1964    /**
1965     * Returns whether all of the given instruction offsets (at least one)
1966     * are smaller than or equal to the given offset.
1967     */
1968    private boolean isAllSmallerThanOrEqual(InstructionOffsetValue instructionOffsets,
1969                                            int                    instructionOffset)
1970    {
1971        if (instructionOffsets != null)
1972        {
1973            // Loop over all instruction offsets.
1974            int branchCount = instructionOffsets.instructionOffsetCount();
1975            if (branchCount > 0)
1976            {
1977                for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
1978                {
1979                    // Is the offset larger than the reference offset?
1980                    if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset)
1981                    {
1982                        return false;
1983                    }
1984                }
1985
1986                return true;
1987            }
1988        }
1989
1990        return false;
1991    }
1992
1993
1994    /**
1995     * Returns whether any of the given instruction offsets (at least one)
1996     * is larger than the given offset.
1997     */
1998    private boolean isAnyLargerThan(InstructionOffsetValue instructionOffsets,
1999                                    int                    instructionOffset)
2000    {
2001        if (instructionOffsets != null)
2002        {
2003            // Loop over all instruction offsets.
2004            int branchCount = instructionOffsets.instructionOffsetCount();
2005            if (branchCount > 0)
2006            {
2007                for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
2008                {
2009                    // Is the offset larger than the reference offset?
2010                    if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset)
2011                    {
2012                        return true;
2013                    }
2014                }
2015            }
2016        }
2017
2018        return false;
2019    }
2020
2021
2022    /**
2023     * Initializes the necessary data structure.
2024     */
2025    private void initializeNecessary(CodeAttribute codeAttribute)
2026    {
2027        int codeLength = codeAttribute.u4codeLength;
2028        int maxLocals  = codeAttribute.u2maxLocals;
2029        int maxStack   = codeAttribute.u2maxStack;
2030
2031        // Create new arrays for storing information at each instruction offset.
2032        if (stacksNecessaryAfter.length    < codeLength ||
2033            stacksNecessaryAfter[0].length < maxStack)
2034        {
2035            stacksNecessaryAfter = new boolean[codeLength][maxStack];
2036        }
2037        else
2038        {
2039            for (int offset = 0; offset < codeLength; offset++)
2040            {
2041                Arrays.fill(stacksNecessaryAfter[offset], 0, maxStack, false);
2042            }
2043        }
2044
2045        if (stacksSimplifiedBefore.length    < codeLength ||
2046            stacksSimplifiedBefore[0].length < maxStack)
2047        {
2048            stacksSimplifiedBefore = new boolean[codeLength][maxStack];
2049        }
2050        else
2051        {
2052            for (int offset = 0; offset < codeLength; offset++)
2053            {
2054                Arrays.fill(stacksSimplifiedBefore[offset], 0, maxStack, false);
2055            }
2056        }
2057
2058        if (instructionsNecessary.length < codeLength)
2059        {
2060            instructionsNecessary = new boolean[codeLength];
2061        }
2062        else
2063        {
2064            Arrays.fill(instructionsNecessary, 0, codeLength, false);
2065        }
2066    }
2067
2068
2069    /**
2070     * Returns whether the specified variable is initialized at the specified
2071     * offset.
2072     */
2073    private boolean isVariableInitialization(int instructionOffset,
2074                                             int variableIndex)
2075    {
2076        // Wasn't the variable set yet?
2077        Value valueBefore = simplePartialEvaluator.getVariablesBefore(instructionOffset).getValue(variableIndex);
2078        if (valueBefore == null)
2079        {
2080            return true;
2081        }
2082
2083        // Is the computational type different now?
2084        Value valueAfter = simplePartialEvaluator.getVariablesAfter(instructionOffset).getValue(variableIndex);
2085        if (valueAfter.computationalType() != valueBefore.computationalType())
2086        {
2087            return true;
2088        }
2089
2090        // Is the reference type different now?
2091        if (valueAfter.computationalType() == Value.TYPE_REFERENCE &&
2092            (valueAfter.referenceValue().isNull() == Value.ALWAYS ||
2093             !valueAfter.referenceValue().getType().equals(valueBefore.referenceValue().getType())))
2094        {
2095            return true;
2096        }
2097
2098        // Was the producer an argument (which may be removed)?
2099        Value producersBefore = simplePartialEvaluator.getVariablesBefore(instructionOffset).getProducerValue(variableIndex);
2100        return producersBefore.instructionOffsetValue().instructionOffsetCount() == 1 &&
2101               producersBefore.instructionOffsetValue().instructionOffset(0) == PartialEvaluator.AT_METHOD_ENTRY;
2102    }
2103
2104
2105    /**
2106     * Marks the stack entry after the given offset.
2107     * @param instructionOffset the offset of the stack entry to be marked.
2108     * @param stackIndex        the index of the stack entry to be marked
2109     *                          (counting from the bottom).
2110     */
2111    private void markStackEntryAfter(int instructionOffset,
2112                                     int stackIndex)
2113    {
2114        if (!isStackEntryNecessaryAfter(instructionOffset, stackIndex))
2115        {
2116            if (DEBUG) System.out.print("["+instructionOffset+".s"+stackIndex+"],");
2117
2118            stacksNecessaryAfter[instructionOffset][stackIndex] = true;
2119
2120            if (maxMarkedOffset < instructionOffset)
2121            {
2122                maxMarkedOffset = instructionOffset;
2123            }
2124        }
2125    }
2126
2127
2128
2129    /**
2130     * Returns whether the stack specified entries before the given offset are
2131     * present.
2132     */
2133    private boolean isStackEntriesPresentBefore(int instructionOffset,
2134                                                int stackIndex1,
2135                                                int stackIndex2)
2136    {
2137        boolean present1 = isStackEntryPresentBefore(instructionOffset, stackIndex1);
2138        boolean present2 = isStackEntryPresentBefore(instructionOffset, stackIndex2);
2139
2140//        if (present1 ^ present2)
2141//        {
2142//            throw new UnsupportedOperationException("Can't handle partial use of dup2 instructions");
2143//        }
2144
2145        return present1 || present2;
2146    }
2147
2148
2149    /**
2150     * Returns whether the specified stack entry before the given offset is
2151     * present.
2152     * @param instructionOffset the offset of the stack entry to be checked.
2153     * @param stackIndex        the index of the stack entry to be checked
2154     *                          (counting from the bottom).
2155     */
2156    private boolean isStackEntryPresentBefore(int instructionOffset,
2157                                              int stackIndex)
2158    {
2159        TracedStack tracedStack =
2160            partialEvaluator.getStackBefore(instructionOffset);
2161
2162        InstructionOffsetValue producerOffsets =
2163            tracedStack.getBottomProducerValue(stackIndex).instructionOffsetValue();
2164
2165        return isAnyStackEntryNecessaryAfter(producerOffsets, stackIndex);
2166    }
2167
2168
2169    /**
2170     * Returns whether the stack specified entries after the given offset are
2171     * necessary.
2172     */
2173    private boolean isStackEntriesNecessaryAfter(int instructionOffset,
2174                                                 int stackIndex1,
2175                                                 int stackIndex2)
2176    {
2177        boolean present1 = isStackEntryNecessaryAfter(instructionOffset, stackIndex1);
2178        boolean present2 = isStackEntryNecessaryAfter(instructionOffset, stackIndex2);
2179
2180//        if (present1 ^ present2)
2181//        {
2182//            throw new UnsupportedOperationException("Can't handle partial use of dup2 instructions");
2183//        }
2184
2185        return present1 || present2;
2186    }
2187
2188
2189    /**
2190     * Returns whether any of the stack entries after the given offsets are
2191     * necessary.
2192     * @param instructionOffsets the offsets of the stack entries to be checked.
2193     * @param stackIndex         the index of the stack entries to be checked
2194     *                           (counting from the bottom).
2195     */
2196    private boolean isAnyStackEntryNecessaryAfter(InstructionOffsetValue instructionOffsets,
2197                                                  int                    stackIndex)
2198    {
2199        int offsetCount = instructionOffsets.instructionOffsetCount();
2200
2201        for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
2202        {
2203            if (isStackEntryNecessaryAfter(instructionOffsets.instructionOffset(offsetIndex), stackIndex))
2204            {
2205                return true;
2206            }
2207        }
2208
2209        return false;
2210    }
2211
2212
2213    /**
2214     * Returns whether the specified stack entry after the given offset is
2215     * necessary.
2216     * @param instructionOffset the offset of the stack entry to be checked.
2217     * @param stackIndex        the index of the stack entry to be checked
2218     *                          (counting from the bottom).
2219     */
2220    private boolean isStackEntryNecessaryAfter(int instructionOffset,
2221                                               int stackIndex)
2222    {
2223        return instructionOffset == PartialEvaluator.AT_CATCH_ENTRY ||
2224               stacksNecessaryAfter[instructionOffset][stackIndex];
2225    }
2226
2227
2228    private void markStackSimplificationBefore(int instructionOffset,
2229                                               int stackIndex)
2230    {
2231        stacksSimplifiedBefore[instructionOffset][stackIndex] = true;
2232    }
2233
2234
2235    private boolean isStackSimplifiedBefore(int instructionOffset,
2236                                            int stackIndex)
2237    {
2238        return stacksSimplifiedBefore[instructionOffset][stackIndex];
2239    }
2240
2241
2242    private void markInstruction(int instructionOffset)
2243    {
2244        if (!isInstructionNecessary(instructionOffset))
2245        {
2246            if (DEBUG) System.out.print(instructionOffset+",");
2247
2248            instructionsNecessary[instructionOffset] = true;
2249
2250            if (maxMarkedOffset < instructionOffset)
2251            {
2252                maxMarkedOffset = instructionOffset;
2253            }
2254        }
2255    }
2256
2257
2258    private boolean isAnyInstructionNecessary(int instructionOffset1,
2259                                              int instructionOffset2)
2260    {
2261        for (int instructionOffset = instructionOffset1;
2262             instructionOffset < instructionOffset2;
2263             instructionOffset++)
2264        {
2265            if (isInstructionNecessary(instructionOffset))
2266            {
2267                return true;
2268            }
2269        }
2270
2271        return false;
2272    }
2273
2274
2275    /**
2276     * Returns the highest offset of an instruction that has been marked as
2277     * necessary, before the given offset.
2278     */
2279    private int lastNecessaryInstructionOffset(int instructionOffset)
2280    {
2281        for (int offset = instructionOffset-1; offset >= 0; offset--)
2282        {
2283            if (isInstructionNecessary(instructionOffset))
2284            {
2285                return offset;
2286            }
2287        }
2288
2289        return 0;
2290    }
2291
2292
2293    private boolean isInstructionNecessary(int instructionOffset)
2294    {
2295        return instructionOffset == PartialEvaluator.AT_METHOD_ENTRY ||
2296               instructionsNecessary[instructionOffset];
2297    }
2298}
2299