EvaluationShrinker.java revision b72c5c2e5482cf10117b2b25f642f7616b2326c3 
1/*
2 * ProGuard -- shrinking, optimization, obfuscation, and preverification
3 *             of Java bytecode.
4 *
5 * Copyright (c) 2002-2009 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.*;
34import proguard.evaluation.value.*;
35import proguard.optimize.info.*;
36
37/**
38 * This AttributeVisitor simplifies the code attributes that it visits, based
39 * on partial evaluation.
40 *
41 * @author Eric Lafortune
42 */
43public class EvaluationShrinker
44extends      SimplifiedVisitor
45implements   AttributeVisitor
46{
47    //*
48    private static final boolean DEBUG_RESULTS  = false;
49    private static final boolean DEBUG          = false;
50    /*/
51    private static boolean DEBUG_RESULTS  = true;
52    private static boolean DEBUG          = true;
53    //*/
54
55    private final InstructionVisitor extraDeletedInstructionVisitor;
56    private final InstructionVisitor extraAddedInstructionVisitor;
57
58    private final PartialEvaluator             partialEvaluator;
59    private final PartialEvaluator             simplePartialEvaluator       = new PartialEvaluator();
60    private final SideEffectInstructionChecker sideEffectInstructionChecker = new SideEffectInstructionChecker(true);
61    private final MyUnusedParameterSimplifier  unusedParameterSimplifier    = new MyUnusedParameterSimplifier();
62    private final MyProducerMarker             producerMarker               = new MyProducerMarker();
63    private final MyStackConsistencyFixer      stackConsistencyFixer        = new MyStackConsistencyFixer();
64    private final CodeAttributeEditor          codeAttributeEditor          = new CodeAttributeEditor(false);
65
66    private boolean[][] variablesNecessaryAfter = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_VARIABLES_SIZE];
67    private boolean[][] stacksNecessaryAfter    = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE];
68    private boolean[][] stacksSimplifiedBefore  = new boolean[ClassConstants.TYPICAL_CODE_LENGTH][ClassConstants.TYPICAL_STACK_SIZE];
69    private boolean[]   instructionsNecessary   = new boolean[ClassConstants.TYPICAL_CODE_LENGTH];
70
71    private int maxMarkedOffset;
72
73
74    /**
75     * Creates a new EvaluationShrinker.
76     */
77    public EvaluationShrinker()
78    {
79        this(new PartialEvaluator(), null, null);
80    }
81
82
83    /**
84     * Creates a new EvaluationShrinker.
85     * @param partialEvaluator               the partial evaluator that will
86     *                                       execute the code and provide
87     *                                       information about the results.
88     * @param extraDeletedInstructionVisitor an optional extra visitor for all
89     *                                       deleted instructions.
90     * @param extraAddedInstructionVisitor   an optional extra visitor for all
91     *                                       added instructions.
92     */
93    public EvaluationShrinker(PartialEvaluator   partialEvaluator,
94                              InstructionVisitor extraDeletedInstructionVisitor,
95                              InstructionVisitor extraAddedInstructionVisitor)
96    {
97        this.partialEvaluator               = partialEvaluator;
98        this.extraDeletedInstructionVisitor = extraDeletedInstructionVisitor;
99        this.extraAddedInstructionVisitor   = extraAddedInstructionVisitor;
100    }
101
102
103    // Implementations for AttributeVisitor.
104
105    public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
106
107
108    public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
109    {
110//        DEBUG = DEBUG_RESULTS =
111//            clazz.getName().equals("abc/Def") &&
112//            method.getName(clazz).equals("abc");
113
114        // TODO: Remove this when the evaluation shrinker has stabilized.
115        // Catch any unexpected exceptions from the actual visiting method.
116        try
117        {
118            // Process the code.
119            visitCodeAttribute0(clazz, method, codeAttribute);
120        }
121        catch (RuntimeException ex)
122        {
123            System.err.println("Unexpected error while shrinking instructions after partial evaluation:");
124            System.err.println("  Class       = ["+clazz.getName()+"]");
125            System.err.println("  Method      = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
126            System.err.println("  Exception   = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
127            System.err.println("Not optimizing this method");
128
129            if (DEBUG)
130            {
131                method.accept(clazz, new ClassPrinter());
132
133                throw ex;
134            }
135        }
136    }
137
138
139    public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
140    {
141        if (DEBUG_RESULTS)
142        {
143            System.out.println();
144            System.out.println("Class "+ClassUtil.externalClassName(clazz.getName()));
145            System.out.println("Method "+ClassUtil.externalFullMethodDescription(clazz.getName(),
146                                                                                 0,
147                                                                                 method.getName(clazz),
148                                                                                 method.getDescriptor(clazz)));
149        }
150
151        // Initialize the necessary array.
152        initializeNecessary(codeAttribute);
153
154        // Evaluate the method.
155        partialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
156
157        int codeLength = codeAttribute.u4codeLength;
158
159        // Reset the code changes.
160        codeAttributeEditor.reset(codeLength);
161
162        // Mark any unused method parameters on the stack.
163        if (DEBUG) System.out.println("Invocation simplification:");
164
165        for (int offset = 0; offset < codeLength; offset++)
166        {
167            if (partialEvaluator.isTraced(offset))
168            {
169                Instruction instruction = InstructionFactory.create(codeAttribute.code,
170                                                                    offset);
171
172                instruction.accept(clazz, method, codeAttribute, offset, unusedParameterSimplifier);
173            }
174        }
175
176        // Mark all essential instructions that have been encountered as used.
177        if (DEBUG) System.out.println("Usage initialization: ");
178
179        maxMarkedOffset = -1;
180
181        // The invocation of the "super" or "this" <init> method inside a
182        // constructor is always necessary.
183        int superInitializationOffset = partialEvaluator.superInitializationOffset();
184        if (superInitializationOffset != PartialEvaluator.NONE)
185        {
186            if (DEBUG) System.out.print("(super.<init>)");
187
188            markInstruction(superInitializationOffset);
189        }
190
191        // Also mark infinite loops and instructions that cause side effects.
192        for (int offset = 0; offset < codeLength; offset++)
193        {
194            if (partialEvaluator.isTraced(offset))
195            {
196                Instruction instruction = InstructionFactory.create(codeAttribute.code,
197                                                                    offset);
198
199                // Mark that the instruction is necessary if it is an infinite loop.
200                if (instruction.opcode == InstructionConstants.OP_GOTO &&
201                    ((BranchInstruction)instruction).branchOffset == 0)
202                {
203                    if (DEBUG) System.out.print("(infinite loop)");
204                    markInstruction(offset);
205                }
206
207                // Mark that the instruction is necessary if it has side effects.
208                else if (sideEffectInstructionChecker.hasSideEffects(clazz,
209                                                                     method,
210                                                                     codeAttribute,
211                                                                     offset,
212                                                                     instruction))
213                {
214                    markInstruction(offset);
215                }
216            }
217        }
218        if (DEBUG) System.out.println();
219
220
221        // Globally mark instructions and their produced variables and stack
222        // entries on which necessary instructions depend.
223        // Instead of doing this recursively, we loop across all instructions,
224        // starting at the highest previously unmarked instruction that has
225        // been been marked.
226        if (DEBUG) System.out.println("Usage marking:");
227
228        while (maxMarkedOffset >= 0)
229        {
230            int offset = maxMarkedOffset;
231
232            maxMarkedOffset = offset - 1;
233
234            if (partialEvaluator.isTraced(offset))
235            {
236                if (isInstructionNecessary(offset))
237                {
238                    Instruction instruction = InstructionFactory.create(codeAttribute.code,
239                                                                        offset);
240
241                    instruction.accept(clazz, method, codeAttribute, offset, producerMarker);
242                }
243
244                // Check if this instruction is a branch origin from a branch
245                // that straddles some marked code.
246                markStraddlingBranches(offset,
247                                       partialEvaluator.branchTargets(offset),
248                                       true);
249
250                // Check if this instruction is a branch target from a branch
251                // that straddles some marked code.
252                markStraddlingBranches(offset,
253                                       partialEvaluator.branchOrigins(offset),
254                                       false);
255            }
256
257            if (DEBUG)
258            {
259                if (maxMarkedOffset > offset)
260                {
261                    System.out.println(" -> "+maxMarkedOffset);
262                }
263            }
264        }
265        if (DEBUG) System.out.println();
266
267
268        // Mark variable initializations, even if they aren't strictly necessary.
269        // The virtual machine's verification step is not smart enough to see
270        // this, and may complain otherwise.
271        if (DEBUG) System.out.println("Initialization marking: ");
272
273        for (int offset = 0; offset < codeLength; offset++)
274        {
275            // Is it a variable initialization that hasn't been marked yet?
276            if (partialEvaluator.isTraced(offset) &&
277                !isInstructionNecessary(offset))
278            {
279                // Is the corresponding variable necessary anywhere in the code,
280                // accoriding to a simple partial evaluation?
281                int variableIndex = partialEvaluator.initializedVariable(offset);
282                if (variableIndex >= 0 &&
283                    isVariableInitializationNecessary(clazz,
284                                                      method,
285                                                      codeAttribute,
286                                                      offset,
287                                                      variableIndex))
288                {
289                    markInstruction(offset);
290                }
291            }
292        }
293        if (DEBUG) System.out.println();
294
295
296        // Locally fix instructions, in order to keep the stack consistent.
297        if (DEBUG) System.out.println("Stack consistency fixing:");
298
299        maxMarkedOffset = codeLength - 1;
300
301        while (maxMarkedOffset >= 0)
302        {
303            int offset = maxMarkedOffset;
304
305            maxMarkedOffset = offset - 1;
306
307            if (partialEvaluator.isTraced(offset))
308            {
309                Instruction instruction = InstructionFactory.create(codeAttribute.code,
310                                                                    offset);
311
312                instruction.accept(clazz, method, codeAttribute, offset, stackConsistencyFixer);
313
314                // Check if this instruction is a branch origin from a branch
315                // that straddles some marked code.
316                markStraddlingBranches(offset,
317                                       partialEvaluator.branchTargets(offset),
318                                       true);
319
320                // Check if this instruction is a branch target from a branch
321                // that straddles some marked code.
322                markStraddlingBranches(offset,
323                                       partialEvaluator.branchOrigins(offset),
324                                       false);
325            }
326        }
327        if (DEBUG) System.out.println();
328
329
330        // Replace traced but unmarked backward branches by infinite loops.
331        // The virtual machine's verification step is not smart enough to see
332        // the code isn't reachable, and may complain otherwise.
333        // Any clearly unreachable code will still be removed elsewhere.
334        if (DEBUG) System.out.println("Infinite loop fixing:");
335
336        for (int offset = 0; offset < codeLength; offset++)
337        {
338            // Is it a traced but unmarked backward branch, without an unmarked
339            // straddling forward branch? Note that this is still a heuristic.
340            if (partialEvaluator.isTraced(offset) &&
341                !isInstructionNecessary(offset)   &&
342                isAllSmallerThanOrEqual(partialEvaluator.branchTargets(offset),
343                                        offset)   &&
344                !isAnyUnnecessaryInstructionBranchingOver(lastNecessaryInstructionOffset(offset),
345                                                          offset))
346            {
347                replaceByInfiniteLoop(clazz, offset);
348            }
349        }
350        if (DEBUG) System.out.println();
351
352
353        // Insert infinite loops after jumps to subroutines that don't return.
354        // The virtual machine's verification step is not smart enough to see
355        // the code isn't reachable, and may complain otherwise.
356        if (DEBUG) System.out.println("Non-returning subroutine fixing:");
357
358        for (int offset = 0; offset < codeLength; offset++)
359        {
360            // Is it a traced but unmarked backward branch, without an unmarked
361            // straddling forward branch? Note that this is still a heuristic.
362            if (isInstructionNecessary(offset) &&
363                partialEvaluator.isSubroutineInvocation(offset))
364            {
365                Instruction instruction = InstructionFactory.create(codeAttribute.code,
366                                                                    offset);
367
368                int nextOffset = offset + instruction.length(offset);
369                if (!isInstructionNecessary(nextOffset))
370                {
371                    replaceByInfiniteLoop(clazz, nextOffset);
372                }
373            }
374        }
375        if (DEBUG) System.out.println();
376
377
378        // Delete all instructions that are not used.
379        int offset = 0;
380        do
381        {
382            Instruction instruction = InstructionFactory.create(codeAttribute.code,
383                                                                offset);
384            if (!isInstructionNecessary(offset))
385            {
386                codeAttributeEditor.deleteInstruction(offset);
387
388                codeAttributeEditor.insertBeforeInstruction(offset, (Instruction)null);
389                codeAttributeEditor.replaceInstruction(offset,      (Instruction)null);
390                codeAttributeEditor.insertAfterInstruction(offset,  (Instruction)null);
391
392                // Visit the instruction, if required.
393                if (extraDeletedInstructionVisitor != null)
394                {
395                    instruction.accept(clazz, method, codeAttribute, offset, extraDeletedInstructionVisitor);
396                }
397            }
398
399            offset += instruction.length(offset);
400        }
401        while (offset < codeLength);
402
403
404        if (DEBUG_RESULTS)
405        {
406            System.out.println("Simplification results:");
407
408            offset = 0;
409            do
410            {
411                Instruction instruction = InstructionFactory.create(codeAttribute.code,
412                                                                    offset);
413                System.out.println((isInstructionNecessary(offset) ? " + " : " - ")+instruction.toString(offset));
414
415                if (partialEvaluator.isTraced(offset))
416                {
417                    int initializationOffset = partialEvaluator.initializationOffset(offset);
418                    if (initializationOffset != PartialEvaluator.NONE)
419                    {
420                        System.out.println("     is to be initialized at ["+initializationOffset+"]");
421                    }
422
423                    InstructionOffsetValue branchTargets = partialEvaluator.branchTargets(offset);
424                    if (branchTargets != null)
425                    {
426                        System.out.println("     has overall been branching to "+branchTargets);
427                    }
428
429                    boolean deleted = codeAttributeEditor.deleted[offset];
430                    if (isInstructionNecessary(offset) && deleted)
431                    {
432                        System.out.println("     is deleted");
433                    }
434
435                    Instruction preInsertion = codeAttributeEditor.preInsertions[offset];
436                    if (preInsertion != null)
437                    {
438                        System.out.println("     is preceded by: "+preInsertion);
439                    }
440
441                    Instruction replacement = codeAttributeEditor.replacements[offset];
442                    if (replacement != null)
443                    {
444                        System.out.println("     is replaced by: "+replacement);
445                    }
446
447                    Instruction postInsertion = codeAttributeEditor.postInsertions[offset];
448                    if (postInsertion != null)
449                    {
450                        System.out.println("     is followed by: "+postInsertion);
451                    }
452                }
453
454                offset += instruction.length(offset);
455            }
456            while (offset < codeLength);
457        }
458
459        // Apply all accumulated changes to the code.
460        codeAttributeEditor.visitCodeAttribute(clazz, method, codeAttribute);
461    }
462
463
464    /**
465     * This MemberVisitor marks stack entries that aren't necessary because
466     * parameters aren't used in the methods that are visited.
467     */
468    private class MyUnusedParameterSimplifier
469    extends       SimplifiedVisitor
470    implements    InstructionVisitor, ConstantVisitor, MemberVisitor
471    {
472        private int                 invocationOffset;
473        private ConstantInstruction invocationInstruction;
474
475
476        // Implementations for InstructionVisitor.
477
478        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction) {}
479
480
481        public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
482        {
483            switch (constantInstruction.opcode)
484            {
485                case InstructionConstants.OP_INVOKEVIRTUAL:
486                case InstructionConstants.OP_INVOKESPECIAL:
487                case InstructionConstants.OP_INVOKESTATIC:
488                case InstructionConstants.OP_INVOKEINTERFACE:
489                    this.invocationOffset      = offset;
490                    this.invocationInstruction = constantInstruction;
491                    clazz.constantPoolEntryAccept(constantInstruction.constantIndex, this);
492                    break;
493            }
494        }
495
496
497        // Implementations for ConstantVisitor.
498
499        public void visitAnyRefConstant(Clazz clazz, RefConstant refConstant)
500        {
501            refConstant.referencedMemberAccept(this);
502        }
503
504
505        // Implementations for MemberVisitor.
506
507        public void visitAnyMember(Clazz clazz, Member member) {}
508
509
510        public void visitProgramMethod(ProgramClass programClass, ProgramMethod programMethod)
511        {
512            // Get the total size of the parameters.
513            int parameterSize = ParameterUsageMarker.getParameterSize(programMethod);
514
515            // Make the method invocation static, if possible.
516            if ((programMethod.getAccessFlags() & ClassConstants.INTERNAL_ACC_STATIC) == 0 &&
517                !ParameterUsageMarker.isParameterUsed(programMethod, 0))
518            {
519                replaceByStaticInvocation(programClass,
520                                          invocationOffset,
521                                          invocationInstruction);
522            }
523
524            // Remove unused parameters.
525            for (int index = 0; index < parameterSize; index++)
526            {
527                if (!ParameterUsageMarker.isParameterUsed(programMethod, index))
528                {
529                    TracedStack stack =
530                        partialEvaluator.getStackBefore(invocationOffset);
531
532                    int stackIndex = stack.size() - parameterSize + index;
533
534                    if (DEBUG)
535                    {
536                        System.out.println("  ["+invocationOffset+"] Ignoring parameter #"+index+" of "+programClass.getName()+"."+programMethod.getName(programClass)+programMethod.getDescriptor(programClass)+"] (stack entry #"+stackIndex+" ["+stack.getBottom(stackIndex)+"])");
537                        System.out.println("    Full stack: "+stack);
538                    }
539
540                    markStackSimplificationBefore(invocationOffset, stackIndex);
541                }
542            }
543        }
544    }
545
546
547    /**
548     * This InstructionVisitor marks the producing instructions and produced
549     * variables and stack entries of the instructions that it visits.
550     * Simplified method arguments are ignored.
551     */
552    private class MyProducerMarker
553    extends       SimplifiedVisitor
554    implements    InstructionVisitor
555    {
556        // Implementations for InstructionVisitor.
557
558        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
559        {
560            markStackProducers(clazz, offset, instruction);
561        }
562
563
564        public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
565        {
566            switch (simpleInstruction.opcode)
567            {
568                case InstructionConstants.OP_DUP:
569                    conditionallyMarkStackEntryProducers(offset, 0, 0);
570                    conditionallyMarkStackEntryProducers(offset, 1, 0);
571                    break;
572                case InstructionConstants.OP_DUP_X1:
573                    conditionallyMarkStackEntryProducers(offset, 0, 0);
574                    conditionallyMarkStackEntryProducers(offset, 1, 1);
575                    conditionallyMarkStackEntryProducers(offset, 2, 0);
576                    break;
577                case InstructionConstants.OP_DUP_X2:
578                    conditionallyMarkStackEntryProducers(offset, 0, 0);
579                    conditionallyMarkStackEntryProducers(offset, 1, 1);
580                    conditionallyMarkStackEntryProducers(offset, 2, 2);
581                    conditionallyMarkStackEntryProducers(offset, 3, 0);
582                    break;
583                case InstructionConstants.OP_DUP2:
584                    conditionallyMarkStackEntryProducers(offset, 0, 0);
585                    conditionallyMarkStackEntryProducers(offset, 1, 1);
586                    conditionallyMarkStackEntryProducers(offset, 2, 0);
587                    conditionallyMarkStackEntryProducers(offset, 3, 1);
588                    break;
589                case InstructionConstants.OP_DUP2_X1:
590                    conditionallyMarkStackEntryProducers(offset, 0, 0);
591                    conditionallyMarkStackEntryProducers(offset, 1, 1);
592                    conditionallyMarkStackEntryProducers(offset, 2, 2);
593                    conditionallyMarkStackEntryProducers(offset, 3, 0);
594                    conditionallyMarkStackEntryProducers(offset, 4, 1);
595                    break;
596                case InstructionConstants.OP_DUP2_X2:
597                    conditionallyMarkStackEntryProducers(offset, 0, 0);
598                    conditionallyMarkStackEntryProducers(offset, 1, 1);
599                    conditionallyMarkStackEntryProducers(offset, 2, 2);
600                    conditionallyMarkStackEntryProducers(offset, 3, 3);
601                    conditionallyMarkStackEntryProducers(offset, 4, 0);
602                    conditionallyMarkStackEntryProducers(offset, 5, 1);
603                    break;
604                case InstructionConstants.OP_SWAP:
605                    conditionallyMarkStackEntryProducers(offset, 0, 1);
606                    conditionallyMarkStackEntryProducers(offset, 1, 0);
607                    break;
608                default:
609                    markStackProducers(clazz, offset, simpleInstruction);
610                    break;
611            }
612        }
613
614
615        public void visitVariableInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, VariableInstruction variableInstruction)
616        {
617            // Is the variable being loaded (or incremented)?
618            if (variableInstruction.opcode < InstructionConstants.OP_ISTORE)
619            {
620                markVariableProducers(offset, variableInstruction.variableIndex);
621            }
622            else
623            {
624                markStackProducers(clazz, offset, variableInstruction);
625            }
626        }
627
628
629        public void visitConstantInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, ConstantInstruction constantInstruction)
630        {
631            // Mark the initializer invocation, if this is a 'new' instruction.
632            if (constantInstruction.opcode == InstructionConstants.OP_NEW)
633            {
634                markInitialization(offset);
635            }
636
637            markStackProducers(clazz, offset, constantInstruction);
638        }
639
640
641        public void visitBranchInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, BranchInstruction branchInstruction)
642        {
643            // Explicitly mark the produced stack entry of a 'jsr' instruction,
644            // because the consuming 'astore' instruction of the subroutine is
645            // cleared every time it is traced.
646            if (branchInstruction.opcode == InstructionConstants.OP_JSR ||
647                branchInstruction.opcode == InstructionConstants.OP_JSR_W)
648            {
649                markStackEntryAfter(offset, 0);
650            }
651            else
652            {
653                markStackProducers(clazz, offset, branchInstruction);
654            }
655        }
656    }
657
658
659    /**
660     * This InstructionVisitor fixes instructions locally, popping any unused
661     * produced stack entries after marked instructions, and popping produced
662     * stack entries and pushing missing stack entries instead of unmarked
663     * instructions.
664     */
665    private class MyStackConsistencyFixer
666    extends       SimplifiedVisitor
667    implements    InstructionVisitor
668    {
669        // Implementations for InstructionVisitor.
670
671        public void visitAnyInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, Instruction instruction)
672        {
673            // Has the instruction been marked?
674            if (isInstructionNecessary(offset))
675            {
676                // Check all stack entries that are popped.
677                // Typical case: a freshly marked variable initialization that
678                // requires some value on the stack.
679                int popCount = instruction.stackPopCount(clazz);
680                if (popCount > 0)
681                {
682                    TracedStack tracedStack =
683                        partialEvaluator.getStackBefore(offset);
684
685                    int top = tracedStack.size() - 1;
686
687                    int requiredPushCount = 0;
688                    for (int stackIndex = 0; stackIndex < popCount; stackIndex++)
689                    {
690                        // Is the stack entry required by other consumers?
691                        if (!isStackSimplifiedBefore(offset, top - stackIndex) &&
692                            !isAnyStackEntryNecessaryAfter(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(), top - stackIndex))
693                        {
694                            // Remember to push it.
695                            requiredPushCount++;
696                        }
697                    }
698
699                    // Push some necessary stack entries.
700                    if (requiredPushCount > 0)
701                    {
702                        if (DEBUG) System.out.println("  Inserting before marked consumer "+instruction.toString(offset));
703
704                        if (requiredPushCount > (instruction.isCategory2() ? 2 : 1))
705                        {
706                            throw new IllegalArgumentException("Unsupported stack size increment ["+requiredPushCount+"]");
707                        }
708
709                        insertPushInstructions(offset, false, tracedStack.getTop(0).computationalType());
710                    }
711                }
712
713                // Check all stack entries that are pushed.
714                // Typical case: a return value that wasn't really required and
715                // that should be popped.
716                int pushCount = instruction.stackPushCount(clazz);
717                if (pushCount > 0)
718                {
719                    TracedStack tracedStack =
720                        partialEvaluator.getStackAfter(offset);
721
722                    int top = tracedStack.size() - 1;
723
724                    int requiredPopCount = 0;
725                    for (int stackIndex = 0; stackIndex < pushCount; stackIndex++)
726                    {
727                        // Is the stack entry required by consumers?
728                        if (!isStackEntryNecessaryAfter(offset, top - stackIndex))
729                        {
730                            // Remember to pop it.
731                            requiredPopCount++;
732                        }
733                    }
734
735                    // Pop the unnecessary stack entries.
736                    if (requiredPopCount > 0)
737                    {
738                        if (DEBUG) System.out.println("  Inserting after marked producer "+instruction.toString(offset));
739
740                        insertPopInstructions(offset, false, requiredPopCount);
741                    }
742                }
743            }
744            else
745            {
746                // Check all stack entries that would be popped.
747                // Typical case: a stack value that is required elsewhere and
748                // that still has to be popped.
749                int popCount = instruction.stackPopCount(clazz);
750                if (popCount > 0)
751                {
752                    TracedStack tracedStack =
753                        partialEvaluator.getStackBefore(offset);
754
755                    int top = tracedStack.size() - 1;
756
757                    int expectedPopCount = 0;
758                    for (int stackIndex = 0; stackIndex < popCount; stackIndex++)
759                    {
760                        // Is the stack entry required by other consumers?
761                        if (isAnyStackEntryNecessaryAfter(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(), top - stackIndex))
762                        {
763                            // Remember to pop it.
764                            expectedPopCount++;
765                        }
766                    }
767
768                    // Pop the unnecessary stack entries.
769                    if (expectedPopCount > 0)
770                    {
771                        if (DEBUG) System.out.println("  Replacing unmarked consumer "+instruction.toString(offset));
772
773                        insertPopInstructions(offset, true, expectedPopCount);
774                    }
775                }
776
777                // Check all stack entries that would be pushed.
778                // Typical case: never.
779                int pushCount = instruction.stackPushCount(clazz);
780                if (pushCount > 0)
781                {
782                    TracedStack tracedStack =
783                        partialEvaluator.getStackAfter(offset);
784
785                    int top = tracedStack.size() - 1;
786
787                    int expectedPushCount = 0;
788                    for (int stackIndex = 0; stackIndex < pushCount; stackIndex++)
789                    {
790                        // Is the stack entry required by consumers?
791                        if (isStackEntryNecessaryAfter(offset, top - stackIndex))
792                        {
793                            // Remember to push it.
794                            expectedPushCount++;
795                        }
796                    }
797
798                    // Push some necessary stack entries.
799                    if (expectedPushCount > 0)
800                    {
801                        if (DEBUG) System.out.println("  Replacing unmarked producer "+instruction.toString(offset));
802
803                        insertPushInstructions(offset, true, tracedStack.getTop(0).computationalType());
804                    }
805                }
806            }
807        }
808
809
810        public void visitSimpleInstruction(Clazz clazz, Method method, CodeAttribute codeAttribute, int offset, SimpleInstruction simpleInstruction)
811        {
812            if (isInstructionNecessary(offset) &&
813                isDupOrSwap(simpleInstruction))
814            {
815                fixDupInstruction(clazz, codeAttribute, offset, simpleInstruction);
816            }
817            else
818            {
819                visitAnyInstruction(clazz, method, codeAttribute, offset, simpleInstruction);
820            }
821        }
822    }
823
824
825    // Small utility methods.
826
827    /**
828     * Marks the variable and the corresponding producing instructions
829     * of the consumer at the given offset.
830     * @param consumerOffset the offset of the consumer.
831     * @param variableIndex  the index of the variable to be marked.
832     */
833    private void markVariableProducers(int consumerOffset,
834                                       int variableIndex)
835    {
836        TracedVariables tracedVariables =
837            partialEvaluator.getVariablesBefore(consumerOffset);
838
839        // Mark the producer of the loaded value.
840        markVariableProducers(tracedVariables.getProducerValue(variableIndex).instructionOffsetValue(),
841                              variableIndex);
842    }
843
844
845    /**
846     * Marks the variable and its producing instructions at the given offsets.
847     * @param producerOffsets the offsets of the producers to be marked.
848     * @param variableIndex   the index of the variable to be marked.
849     */
850    private void markVariableProducers(InstructionOffsetValue producerOffsets,
851                                       int                    variableIndex)
852    {
853        if (producerOffsets != null)
854        {
855            int offsetCount = producerOffsets.instructionOffsetCount();
856            for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
857            {
858                // Make sure the variable and the instruction are marked
859                // at the producing offset.
860                int offset = producerOffsets.instructionOffset(offsetIndex);
861
862                markVariableAfter(offset, variableIndex);
863                markInstruction(offset);
864            }
865        }
866    }
867
868
869    /**
870     * Marks the stack entries and their producing instructions of the
871     * consumer at the given offset.
872     * @param clazz          the containing class.
873     * @param consumerOffset the offset of the consumer.
874     * @param consumer       the consumer of the stack entries.
875     */
876    private void markStackProducers(Clazz       clazz,
877                                    int         consumerOffset,
878                                    Instruction consumer)
879    {
880        // Mark the producers of the popped values.
881        int popCount = consumer.stackPopCount(clazz);
882        for (int stackIndex = 0; stackIndex < popCount; stackIndex++)
883        {
884            markStackEntryProducers(consumerOffset, stackIndex);
885        }
886    }
887
888
889    /**
890     * Marks the stack entry and the corresponding producing instructions
891     * of the consumer at the given offset, if the stack entry of the
892     * consumer is marked.
893     * @param consumerOffset     the offset of the consumer.
894     * @param consumerStackIndex the index of the stack entry to be checked
895     *                           (counting from the top).
896     * @param producerStackIndex the index of the stack entry to be marked
897     *                           (counting from the top).
898     */
899    private void conditionallyMarkStackEntryProducers(int consumerOffset,
900                                                      int consumerStackIndex,
901                                                      int producerStackIndex)
902    {
903        int top = partialEvaluator.getStackAfter(consumerOffset).size() - 1;
904
905        if (isStackEntryNecessaryAfter(consumerOffset, top - consumerStackIndex))
906        {
907            markStackEntryProducers(consumerOffset, producerStackIndex);
908        }
909    }
910
911
912    /**
913     * Marks the stack entry and the corresponding producing instructions
914     * of the consumer at the given offset.
915     * @param consumerOffset the offset of the consumer.
916     * @param stackIndex     the index of the stack entry to be marked
917     *                        (counting from the top).
918     */
919    private void markStackEntryProducers(int consumerOffset,
920                                         int stackIndex)
921    {
922        TracedStack tracedStack =
923            partialEvaluator.getStackBefore(consumerOffset);
924
925        int stackBottomIndex = tracedStack.size() - 1 - stackIndex;
926
927        if (!isStackSimplifiedBefore(consumerOffset, stackBottomIndex))
928        {
929            markStackEntryProducers(tracedStack.getTopProducerValue(stackIndex).instructionOffsetValue(),
930                                    stackBottomIndex);
931        }
932    }
933
934
935    /**
936     * Marks the stack entry and its producing instructions at the given
937     * offsets.
938     * @param producerOffsets the offsets of the producers to be marked.
939     * @param stackIndex      the index of the stack entry to be marked
940     *                        (counting from the bottom).
941     */
942    private void markStackEntryProducers(InstructionOffsetValue producerOffsets,
943                                         int                    stackIndex)
944    {
945        if (producerOffsets != null)
946        {
947            int offsetCount = producerOffsets.instructionOffsetCount();
948            for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
949            {
950                // Make sure the stack entry and the instruction are marked
951                // at the producing offset.
952                int offset = producerOffsets.instructionOffset(offsetIndex);
953
954                markStackEntryAfter(offset, stackIndex);
955                markInstruction(offset);
956            }
957        }
958    }
959
960
961    /**
962     * Marks the stack entry and its initializing instruction
963     * ('invokespecial *.<init>') for the given 'new' instruction offset.
964     * @param newInstructionOffset the offset of the 'new' instruction.
965     */
966    private void markInitialization(int newInstructionOffset)
967    {
968        int initializationOffset =
969            partialEvaluator.initializationOffset(newInstructionOffset);
970
971        TracedStack tracedStack =
972            partialEvaluator.getStackAfter(newInstructionOffset);
973
974        markStackEntryAfter(initializationOffset, tracedStack.size() - 1);
975        markInstruction(initializationOffset);
976    }
977
978
979    /**
980     * Marks the branch instructions of straddling branches, if they straddle
981     * some code that has been marked.
982     * @param instructionOffset   the offset of the branch origin or branch target.
983     * @param branchOffsets       the offsets of the straddling branch targets
984     *                            or branch origins.
985     * @param isPointingToTargets <code>true</code> if the above offsets are
986     *                            branch targets, <code>false</code> if they
987     *                            are branch origins.
988     */
989    private void markStraddlingBranches(int                    instructionOffset,
990                                        InstructionOffsetValue branchOffsets,
991                                        boolean                isPointingToTargets)
992    {
993        if (branchOffsets != null)
994        {
995            // Loop over all branch offsets.
996            int branchCount = branchOffsets.instructionOffsetCount();
997            for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
998            {
999                // Is the branch straddling forward any necessary instructions?
1000                int branchOffset = branchOffsets.instructionOffset(branchIndex);
1001
1002                // Is the offset pointing to a branch origin or to a branch target?
1003                if (isPointingToTargets)
1004                {
1005                    markStraddlingBranch(instructionOffset,
1006                                         branchOffset,
1007                                         instructionOffset,
1008                                         branchOffset);
1009                }
1010                else
1011                {
1012                    markStraddlingBranch(instructionOffset,
1013                                         branchOffset,
1014                                         branchOffset,
1015                                         instructionOffset);
1016                }
1017            }
1018        }
1019    }
1020
1021
1022    private void markStraddlingBranch(int instructionOffsetStart,
1023                                      int instructionOffsetEnd,
1024                                      int branchOrigin,
1025                                      int branchTarget)
1026    {
1027        if (!isInstructionNecessary(branchOrigin) &&
1028            isAnyInstructionNecessary(instructionOffsetStart, instructionOffsetEnd))
1029        {
1030            if (DEBUG) System.out.print("["+branchOrigin+"->"+branchTarget+"]");
1031
1032            // Mark the branch instruction.
1033            markInstruction(branchOrigin);
1034        }
1035    }
1036
1037
1038    /**
1039     * Marks the specified instruction if it is a required dup/swap instruction,
1040     * replacing it by an appropriate variant if necessary.
1041     * @param clazz         the class that is being checked.
1042     * @param codeAttribute the code that is being checked.
1043     * @param dupOffset     the offset of the dup/swap instruction.
1044     * @param instruction   the dup/swap instruction.
1045     */
1046    private void fixDupInstruction(Clazz         clazz,
1047                                   CodeAttribute codeAttribute,
1048                                   int           dupOffset,
1049                                   Instruction   instruction)
1050    {
1051        int top = partialEvaluator.getStackAfter(dupOffset).size() - 1;
1052
1053        byte oldOpcode = instruction.opcode;
1054        byte newOpcode = 0;
1055
1056        // Simplify the popping instruction if possible.
1057        switch (oldOpcode)
1058        {
1059            case InstructionConstants.OP_DUP:
1060            {
1061                boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0);
1062                boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1);
1063
1064                // Should either the original element or the copy be present?
1065                if (stackEntryPresent0 ||
1066                    stackEntryPresent1)
1067                {
1068                    // Should both the original element and the copy be present?
1069                    if (stackEntryPresent0 &&
1070                        stackEntryPresent1)
1071                    {
1072                        newOpcode = InstructionConstants.OP_DUP;
1073                    }
1074                }
1075                break;
1076            }
1077            case InstructionConstants.OP_DUP_X1:
1078            {
1079                boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0);
1080                boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1);
1081                boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2);
1082
1083                // Should either the original element or the copy be present?
1084                if (stackEntryPresent0 ||
1085                    stackEntryPresent2)
1086                {
1087                    // Should the copy be present?
1088                    if (stackEntryPresent2)
1089                    {
1090                        // Compute the number of elements to be skipped.
1091                        int skipCount = stackEntryPresent1 ? 1 : 0;
1092
1093                        // Should the original element be present?
1094                        if (stackEntryPresent0)
1095                        {
1096                            // Copy the original element.
1097                            newOpcode = (byte)(InstructionConstants.OP_DUP + skipCount);
1098                        }
1099                        else if (skipCount == 1)
1100                        {
1101                            // Move the original element.
1102                            newOpcode = InstructionConstants.OP_SWAP;
1103                        }
1104                    }
1105                }
1106                break;
1107            }
1108            case InstructionConstants.OP_DUP_X2:
1109            {
1110                boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0);
1111                boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1);
1112                boolean stackEntryPresent2 = isStackEntryNecessaryAfter(dupOffset, top - 2);
1113                boolean stackEntryPresent3 = isStackEntryNecessaryAfter(dupOffset, top - 3);
1114
1115                // Should either the original element or the copy be present?
1116                if (stackEntryPresent0 ||
1117                    stackEntryPresent3)
1118                {
1119                    // Should the copy be present?
1120                    if (stackEntryPresent3)
1121                    {
1122                        int skipCount = (stackEntryPresent1 ? 1 : 0) +
1123                                        (stackEntryPresent2 ? 1 : 0);
1124
1125                        // Should the original element be present?
1126                        if (stackEntryPresent0)
1127                        {
1128                            // Copy the original element.
1129                            newOpcode = (byte)(InstructionConstants.OP_DUP + skipCount);
1130                        }
1131                        else if (skipCount == 1)
1132                        {
1133                            // Move the original element.
1134                            newOpcode = InstructionConstants.OP_SWAP;
1135                        }
1136                        else if (skipCount == 2)
1137                        {
1138                            // We can't easily move the original element.
1139                            throw new UnsupportedOperationException("Can't handle dup_x2 instruction moving original element across two elements at ["+dupOffset +"]");
1140                        }
1141                    }
1142                }
1143                break;
1144            }
1145            case InstructionConstants.OP_DUP2:
1146            {
1147                boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1);
1148                boolean stackEntriesPresent23 = isStackEntriesNecessaryAfter(dupOffset, top - 2, top - 3);
1149
1150                // Should either the original element or the copy be present?
1151                if (stackEntriesPresent01 ||
1152                    stackEntriesPresent23)
1153                {
1154                    // Should both the original element and the copy be present?
1155                    if (stackEntriesPresent01 &&
1156                        stackEntriesPresent23)
1157                    {
1158                        newOpcode = InstructionConstants.OP_DUP2;
1159                    }
1160                }
1161                break;
1162            }
1163            case InstructionConstants.OP_DUP2_X1:
1164            {
1165                boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1);
1166                boolean stackEntryPresent2    = isStackEntryNecessaryAfter(dupOffset, top - 2);
1167                boolean stackEntriesPresent34 = isStackEntriesNecessaryAfter(dupOffset, top - 3, top - 4);
1168
1169                // Should either the original element or the copy be present?
1170                if (stackEntriesPresent01 ||
1171                    stackEntriesPresent34)
1172                {
1173                    // Should the copy be present?
1174                    if (stackEntriesPresent34)
1175                    {
1176                        int skipCount = stackEntryPresent2 ? 1 : 0;
1177
1178                        // Should the original element be present?
1179                        if (stackEntriesPresent01)
1180                        {
1181                            // Copy the original element.
1182                            newOpcode = (byte)(InstructionConstants.OP_DUP2 + skipCount);
1183                        }
1184                        else if (skipCount > 0)
1185                        {
1186                            // We can't easily move the original element.
1187                            throw new UnsupportedOperationException("Can't handle dup2_x1 instruction moving original element across "+skipCount+" elements at ["+dupOffset +"]");
1188                        }
1189                    }
1190                }
1191                break;
1192            }
1193            case InstructionConstants.OP_DUP2_X2:
1194            {
1195                boolean stackEntriesPresent01 = isStackEntriesNecessaryAfter(dupOffset, top - 0, top - 1);
1196                boolean stackEntryPresent2    = isStackEntryNecessaryAfter(dupOffset, top - 2);
1197                boolean stackEntryPresent3    = isStackEntryNecessaryAfter(dupOffset, top - 3);
1198                boolean stackEntriesPresent45 = isStackEntriesNecessaryAfter(dupOffset, top - 4, top - 5);
1199
1200                // Should either the original element or the copy be present?
1201                if (stackEntriesPresent01 ||
1202                    stackEntriesPresent45)
1203                {
1204                    // Should the copy be present?
1205                    if (stackEntriesPresent45)
1206                    {
1207                        int skipCount = (stackEntryPresent2 ? 1 : 0) +
1208                                        (stackEntryPresent3 ? 1 : 0);
1209
1210                        // Should the original element be present?
1211                        if (stackEntriesPresent01)
1212                        {
1213                            // Copy the original element.
1214                            newOpcode = (byte)(InstructionConstants.OP_DUP2 + skipCount);
1215                        }
1216                        else if (skipCount > 0)
1217                        {
1218                            // We can't easily move the original element.
1219                            throw new UnsupportedOperationException("Can't handle dup2_x2 instruction moving original element across "+skipCount+" elements at ["+dupOffset +"]");
1220                        }
1221                    }
1222                }
1223                break;
1224            }
1225            case InstructionConstants.OP_SWAP:
1226            {
1227                boolean stackEntryPresent0 = isStackEntryNecessaryAfter(dupOffset, top - 0);
1228                boolean stackEntryPresent1 = isStackEntryNecessaryAfter(dupOffset, top - 1);
1229
1230                // Will either element be present?
1231                if (stackEntryPresent0 ||
1232                    stackEntryPresent1)
1233                {
1234                    // Will both elements be present?
1235                    if (stackEntryPresent0 &&
1236                        stackEntryPresent1)
1237                    {
1238                        newOpcode = InstructionConstants.OP_SWAP;
1239                    }
1240                }
1241                break;
1242            }
1243        }
1244
1245        if      (newOpcode == 0)
1246        {
1247            // Delete the instruction.
1248            codeAttributeEditor.deleteInstruction(dupOffset);
1249
1250            if (extraDeletedInstructionVisitor != null)
1251            {
1252                extraDeletedInstructionVisitor.visitSimpleInstruction(null, null, null, dupOffset, null);
1253            }
1254
1255            if (DEBUG) System.out.println("  Marking but deleting instruction "+instruction.toString(dupOffset));
1256        }
1257        else if (newOpcode == oldOpcode)
1258        {
1259            // Leave the instruction unchanged.
1260            codeAttributeEditor.undeleteInstruction(dupOffset);
1261
1262            if (DEBUG) System.out.println("  Marking unchanged instruction "+instruction.toString(dupOffset));
1263        }
1264        else
1265        {
1266            // Replace the instruction.
1267            Instruction replacementInstruction = new SimpleInstruction(newOpcode);
1268            codeAttributeEditor.replaceInstruction(dupOffset,
1269                                                   replacementInstruction);
1270
1271            if (DEBUG) System.out.println("  Replacing instruction "+instruction.toString(dupOffset)+" by "+replacementInstruction.toString());
1272        }
1273    }
1274
1275
1276    /**
1277     * Pushes a specified type of stack entry before or at the given offset.
1278     * The instruction is marked as necessary.
1279     */
1280    private void insertPushInstructions(int     offset,
1281                                        boolean replace,
1282                                        int     computationalType)
1283    {
1284        // Mark this instruction.
1285        markInstruction(offset);
1286
1287        // Create a simple push instrucion.
1288        Instruction replacementInstruction =
1289            new SimpleInstruction(pushOpcode(computationalType));
1290
1291        if (DEBUG) System.out.println(": "+replacementInstruction.toString(offset));
1292
1293        // Replace or insert the push instruction.
1294        if (replace)
1295        {
1296            // Replace the push instruction.
1297            codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1298        }
1299        else
1300        {
1301            // Insert the push instruction.
1302            codeAttributeEditor.insertBeforeInstruction(offset, replacementInstruction);
1303
1304            if (extraAddedInstructionVisitor != null)
1305            {
1306                replacementInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor);
1307            }
1308        }
1309    }
1310
1311
1312    /**
1313     * Returns the opcode of a push instruction corresponding to the given
1314     * computational type.
1315     * @param computationalType the computational type to be pushed on the stack.
1316     */
1317    private byte pushOpcode(int computationalType)
1318    {
1319        switch (computationalType)
1320        {
1321            case Value.TYPE_INTEGER:            return InstructionConstants.OP_ICONST_0;
1322            case Value.TYPE_LONG:               return InstructionConstants.OP_LCONST_0;
1323            case Value.TYPE_FLOAT:              return InstructionConstants.OP_FCONST_0;
1324            case Value.TYPE_DOUBLE:             return InstructionConstants.OP_DCONST_0;
1325            case Value.TYPE_REFERENCE:
1326            case Value.TYPE_INSTRUCTION_OFFSET: return InstructionConstants.OP_ACONST_NULL;
1327        }
1328
1329        throw new IllegalArgumentException("No push opcode for computational type ["+computationalType+"]");
1330    }
1331
1332
1333    /**
1334     * Pops the given number of stack entries at or after the given offset.
1335     * The instructions are marked as necessary.
1336     */
1337    private void insertPopInstructions(int offset, boolean replace, int popCount)
1338    {
1339        // Mark this instruction.
1340        markInstruction(offset);
1341
1342        switch (popCount)
1343        {
1344            case 1:
1345            {
1346                // Replace or insert a single pop instruction.
1347                Instruction popInstruction =
1348                    new SimpleInstruction(InstructionConstants.OP_POP);
1349
1350                if (replace)
1351                {
1352                    codeAttributeEditor.replaceInstruction(offset, popInstruction);
1353                }
1354                else
1355                {
1356                    codeAttributeEditor.insertAfterInstruction(offset, popInstruction);
1357
1358                    if (extraAddedInstructionVisitor != null)
1359                    {
1360                        popInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor);
1361                    }
1362                }
1363                break;
1364            }
1365            case 2:
1366            {
1367                // Replace or insert a single pop2 instruction.
1368                Instruction popInstruction =
1369                    new SimpleInstruction(InstructionConstants.OP_POP2);
1370
1371                if (replace)
1372                {
1373                    codeAttributeEditor.replaceInstruction(offset, popInstruction);
1374                }
1375                else
1376                {
1377                    codeAttributeEditor.insertAfterInstruction(offset, popInstruction);
1378
1379                    if (extraAddedInstructionVisitor != null)
1380                    {
1381                        popInstruction.accept(null, null, null, offset, extraAddedInstructionVisitor);
1382                    }
1383                }
1384                break;
1385            }
1386            default:
1387            {
1388                // Replace or insert the specified number of pop instructions.
1389                Instruction[] popInstructions =
1390                    new Instruction[popCount / 2 + popCount % 2];
1391
1392                Instruction popInstruction =
1393                    new SimpleInstruction(InstructionConstants.OP_POP2);
1394
1395                for (int index = 0; index < popCount / 2; index++)
1396                {
1397                      popInstructions[index] = popInstruction;
1398                }
1399
1400                if (popCount % 2 == 1)
1401                {
1402                    popInstruction =
1403                        new SimpleInstruction(InstructionConstants.OP_POP);
1404
1405                    popInstructions[popCount / 2] = popInstruction;
1406                }
1407
1408                if (replace)
1409                {
1410                    codeAttributeEditor.replaceInstruction(offset, popInstructions);
1411
1412                    for (int index = 1; index < popInstructions.length; index++)
1413                    {
1414                        if (extraAddedInstructionVisitor != null)
1415                        {
1416                            popInstructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor);
1417                        }
1418                    }
1419                }
1420                else
1421                {
1422                    codeAttributeEditor.insertAfterInstruction(offset, popInstructions);
1423
1424                    for (int index = 0; index < popInstructions.length; index++)
1425                    {
1426                        if (extraAddedInstructionVisitor != null)
1427                        {
1428                            popInstructions[index].accept(null, null, null, offset, extraAddedInstructionVisitor);
1429                        }
1430                    }
1431                }
1432                break;
1433            }
1434        }
1435    }
1436
1437
1438    /**
1439     * Replaces the instruction at a given offset by a static invocation.
1440     */
1441    private void replaceByStaticInvocation(Clazz               clazz,
1442                                           int                 offset,
1443                                           ConstantInstruction constantInstruction)
1444    {
1445        // Remember the replacement instruction.
1446        Instruction replacementInstruction =
1447             new ConstantInstruction(InstructionConstants.OP_INVOKESTATIC,
1448                                     constantInstruction.constantIndex).shrink();
1449
1450        if (DEBUG) System.out.println("  Replacing by static invocation "+constantInstruction.toString(offset)+" -> "+replacementInstruction.toString());
1451
1452        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1453    }
1454
1455
1456    /**
1457     * Replaces the given instruction by an infinite loop.
1458     */
1459    private void replaceByInfiniteLoop(Clazz clazz,
1460                                       int   offset)
1461    {
1462        if (DEBUG) System.out.println("  Inserting infinite loop at ["+offset+"]");
1463
1464        // Mark the instruction.
1465        markInstruction(offset);
1466
1467        // Replace the instruction by an infinite loop.
1468        Instruction replacementInstruction =
1469            new BranchInstruction(InstructionConstants.OP_GOTO, 0);
1470
1471        codeAttributeEditor.replaceInstruction(offset, replacementInstruction);
1472    }
1473
1474
1475    // Small utility methods.
1476
1477    /**
1478     * Returns whether the given instruction is a dup or swap instruction
1479     * (dup, dup_x1, dup_x2, dup2, dup2_x1, dup2_x2, swap).
1480     */
1481    private boolean isDupOrSwap(Instruction instruction)
1482    {
1483        return instruction.opcode >= InstructionConstants.OP_DUP &&
1484               instruction.opcode <= InstructionConstants.OP_SWAP;
1485    }
1486
1487
1488    /**
1489     * Returns whether the given instruction is a pop instruction
1490     * (pop, pop2).
1491     */
1492    private boolean isPop(Instruction instruction)
1493    {
1494        return instruction.opcode == InstructionConstants.OP_POP ||
1495               instruction.opcode == InstructionConstants.OP_POP2;
1496    }
1497
1498
1499    /**
1500     * Returns whether any traced but unnecessary instruction between the two
1501     * given offsets is branching over the second given offset.
1502     */
1503    private boolean isAnyUnnecessaryInstructionBranchingOver(int instructionOffset1,
1504                                                             int instructionOffset2)
1505    {
1506        for (int offset = instructionOffset1; offset < instructionOffset2; offset++)
1507        {
1508            // Is it a traced but unmarked straddling branch?
1509            if (partialEvaluator.isTraced(offset) &&
1510                !isInstructionNecessary(offset)   &&
1511                isAnyLargerThan(partialEvaluator.branchTargets(offset),
1512                                instructionOffset2))
1513            {
1514                return true;
1515            }
1516        }
1517
1518        return false;
1519    }
1520
1521
1522    /**
1523     * Returns whether all of the given instruction offsets (at least one)
1524     * are smaller than or equal to the given offset.
1525     */
1526    private boolean isAllSmallerThanOrEqual(InstructionOffsetValue instructionOffsets,
1527                                            int                    instructionOffset)
1528    {
1529        if (instructionOffsets != null)
1530        {
1531            // Loop over all instruction offsets.
1532            int branchCount = instructionOffsets.instructionOffsetCount();
1533            if (branchCount > 0)
1534            {
1535                for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
1536                {
1537                    // Is the offset larger than the reference offset?
1538                    if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset)
1539                    {
1540                        return false;
1541                    }
1542                }
1543
1544                return true;
1545            }
1546        }
1547
1548        return false;
1549    }
1550
1551
1552    /**
1553     * Returns whether any of the given instruction offsets (at least one)
1554     * is larger than the given offset.
1555     */
1556    private boolean isAnyLargerThan(InstructionOffsetValue instructionOffsets,
1557                                    int                    instructionOffset)
1558    {
1559        if (instructionOffsets != null)
1560        {
1561            // Loop over all instruction offsets.
1562            int branchCount = instructionOffsets.instructionOffsetCount();
1563            if (branchCount > 0)
1564            {
1565                for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
1566                {
1567                    // Is the offset larger than the reference offset?
1568                    if (instructionOffsets.instructionOffset(branchIndex) > instructionOffset)
1569                    {
1570                        return true;
1571                    }
1572                }
1573            }
1574        }
1575
1576        return false;
1577    }
1578
1579
1580    /**
1581     * Initializes the necessary data structure.
1582     */
1583    private void initializeNecessary(CodeAttribute codeAttribute)
1584    {
1585        int codeLength = codeAttribute.u4codeLength;
1586        int maxLocals  = codeAttribute.u2maxLocals;
1587        int maxStack   = codeAttribute.u2maxStack;
1588
1589        // Create new arrays for storing information at each instruction offset.
1590        if (variablesNecessaryAfter.length    < codeLength ||
1591            variablesNecessaryAfter[0].length < maxLocals)
1592        {
1593            variablesNecessaryAfter = new boolean[codeLength][maxLocals];
1594        }
1595        else
1596        {
1597            for (int offset = 0; offset < codeLength; offset++)
1598            {
1599                for (int index = 0; index < maxLocals; index++)
1600                {
1601                    variablesNecessaryAfter[offset][index] = false;
1602                }
1603            }
1604        }
1605
1606        if (stacksNecessaryAfter.length    < codeLength ||
1607            stacksNecessaryAfter[0].length < maxStack)
1608        {
1609            stacksNecessaryAfter = new boolean[codeLength][maxStack];
1610        }
1611        else
1612        {
1613            for (int offset = 0; offset < codeLength; offset++)
1614            {
1615                for (int index = 0; index < maxStack; index++)
1616                {
1617                    stacksNecessaryAfter[offset][index] = false;
1618                }
1619            }
1620        }
1621
1622        if (stacksSimplifiedBefore.length    < codeLength ||
1623            stacksSimplifiedBefore[0].length < maxStack)
1624        {
1625            stacksSimplifiedBefore = new boolean[codeLength][maxStack];
1626        }
1627        else
1628        {
1629            for (int offset = 0; offset < codeLength; offset++)
1630            {
1631                for (int index = 0; index < maxStack; index++)
1632                {
1633                    stacksSimplifiedBefore[offset][index] = false;
1634                }
1635            }
1636        }
1637
1638        if (instructionsNecessary.length < codeLength)
1639        {
1640            instructionsNecessary = new boolean[codeLength];
1641        }
1642        else
1643        {
1644            for (int index = 0; index < codeLength; index++)
1645            {
1646                instructionsNecessary[index] = false;
1647            }
1648        }
1649    }
1650
1651
1652    /**
1653     * Returns whether the given stack entry is present after execution of the
1654     * instruction at the given offset.
1655     */
1656    private boolean isStackEntriesNecessaryAfter(int instructionOffset,
1657                                                 int stackIndex1,
1658                                                 int stackIndex2)
1659    {
1660        boolean present1 = isStackEntryNecessaryAfter(instructionOffset, stackIndex1);
1661        boolean present2 = isStackEntryNecessaryAfter(instructionOffset, stackIndex2);
1662
1663//        if (present1 ^ present2)
1664//        {
1665//            throw new UnsupportedOperationException("Can't handle partial use of dup2 instructions");
1666//        }
1667
1668        return present1 || present2;
1669    }
1670
1671
1672    /**
1673     * Returns whether the specified variable must be initialized at the
1674     * specified offset, according to the verifier of the JVM.
1675     */
1676    private boolean isVariableInitializationNecessary(Clazz         clazz,
1677                                                      Method        method,
1678                                                      CodeAttribute codeAttribute,
1679                                                      int           initializationOffset,
1680                                                      int           variableIndex)
1681    {
1682        int codeLength = codeAttribute.u4codeLength;
1683
1684        // Is the variable necessary anywhere at all?
1685        if (isVariableNecessaryAfterAny(0, codeLength, variableIndex))
1686        {
1687            if (DEBUG) System.out.println("Simple partial evaluation for initialization of variable v"+variableIndex+" at ["+initializationOffset+"]");
1688
1689            // Lazily compute perform simple partial evaluation, the way the
1690            // JVM preverifier would do it.
1691            simplePartialEvaluator.visitCodeAttribute(clazz, method, codeAttribute);
1692
1693            if (DEBUG) System.out.println("End of simple partial evaluation for initialization of variable v"+variableIndex+" at ["+initializationOffset+"]");
1694
1695            // Check if the variable is necessary elsewhere.
1696            for (int offset = 0; offset < codeLength; offset++)
1697            {
1698                if (isInstructionNecessary(offset))
1699                {
1700                    Value producer = partialEvaluator.getVariablesBefore(offset).getProducerValue(variableIndex);
1701                    if (producer != null)
1702                    {
1703                        Value simpleProducer = simplePartialEvaluator.getVariablesBefore(offset).getProducerValue(variableIndex);
1704                        if (simpleProducer != null)
1705                        {
1706                            InstructionOffsetValue producerOffsets =
1707                                producer.instructionOffsetValue();
1708                            InstructionOffsetValue simpleProducerOffsets =
1709                                simpleProducer.instructionOffsetValue();
1710
1711                            // Does the sophisticated partial evaluation have fewer
1712                            // producers than the simple one?
1713                            // And does the simple partial evaluation point to an
1714                            // initialization of the variable?
1715                            if (producerOffsets.instructionOffsetCount() <
1716                                simpleProducerOffsets.instructionOffsetCount() &&
1717                                isVariableNecessaryAfterAny(producerOffsets, variableIndex) &&
1718                                simpleProducerOffsets.contains(initializationOffset))
1719                            {
1720                                // Then the initialization is necessary.
1721                                return true;
1722                            }
1723                        }
1724                    }
1725                }
1726            }
1727        }
1728
1729        return false;
1730    }
1731
1732
1733    private void markVariableAfter(int instructionOffset,
1734                                   int variableIndex)
1735    {
1736        if (!isVariableNecessaryAfter(instructionOffset, variableIndex))
1737        {
1738            if (DEBUG) System.out.print("["+instructionOffset+".v"+variableIndex+"],");
1739
1740            variablesNecessaryAfter[instructionOffset][variableIndex] = true;
1741
1742            if (maxMarkedOffset < instructionOffset)
1743            {
1744                maxMarkedOffset = instructionOffset;
1745            }
1746        }
1747    }
1748
1749
1750    /**
1751     * Returns whether the specified variable is ever necessary after any
1752     * instruction in the specified block.
1753     */
1754    private boolean isVariableNecessaryAfterAny(int startOffset,
1755                                                int endOffset,
1756                                                int variableIndex)
1757    {
1758        for (int offset = startOffset; offset < endOffset; offset++)
1759        {
1760            if (isVariableNecessaryAfter(offset, variableIndex))
1761            {
1762                return true;
1763            }
1764        }
1765
1766        return false;
1767    }
1768
1769
1770    /**
1771     * Returns whether the specified variable is ever necessary after any
1772     * instruction in the specified set of instructions offsets.
1773     */
1774    private boolean isVariableNecessaryAfterAny(InstructionOffsetValue instructionOffsetValue,
1775                                                int                    variableIndex)
1776    {
1777        int count = instructionOffsetValue.instructionOffsetCount();
1778
1779        for (int index = 0; index < count; index++)
1780        {
1781            if (isVariableNecessaryAfter(instructionOffsetValue.instructionOffset(index),
1782                                         variableIndex))
1783            {
1784                return true;
1785            }
1786        }
1787
1788        return false;
1789    }
1790
1791
1792    private boolean isVariableNecessaryAfter(int instructionOffset,
1793                                             int variableIndex)
1794    {
1795        return instructionOffset == PartialEvaluator.AT_METHOD_ENTRY ||
1796               variablesNecessaryAfter[instructionOffset][variableIndex];
1797    }
1798
1799
1800    private void markStackEntryAfter(int instructionOffset,
1801                                     int stackIndex)
1802    {
1803        if (!isStackEntryNecessaryAfter(instructionOffset, stackIndex))
1804        {
1805            if (DEBUG) System.out.print("["+instructionOffset+".s"+stackIndex+"],");
1806
1807            stacksNecessaryAfter[instructionOffset][stackIndex] = true;
1808
1809            if (maxMarkedOffset < instructionOffset)
1810            {
1811                maxMarkedOffset = instructionOffset;
1812            }
1813        }
1814    }
1815
1816
1817    private boolean isAnyStackEntryNecessaryAfter(InstructionOffsetValue instructionOffsets,
1818                                                  int                    stackIndex)
1819    {
1820        int offsetCount = instructionOffsets.instructionOffsetCount();
1821
1822        for (int offsetIndex = 0; offsetIndex < offsetCount; offsetIndex++)
1823        {
1824            if (isStackEntryNecessaryAfter(instructionOffsets.instructionOffset(offsetIndex), stackIndex))
1825            {
1826                return true;
1827            }
1828        }
1829
1830        return false;
1831    }
1832
1833
1834    private boolean isStackEntryNecessaryAfter(int instructionOffset,
1835                                               int stackIndex)
1836    {
1837        return instructionOffset == PartialEvaluator.AT_CATCH_ENTRY ||
1838               stacksNecessaryAfter[instructionOffset][stackIndex];
1839    }
1840
1841
1842    private void markStackSimplificationBefore(int instructionOffset,
1843                                               int stackIndex)
1844    {
1845        stacksSimplifiedBefore[instructionOffset][stackIndex] = true;
1846    }
1847
1848
1849    private boolean isStackSimplifiedBefore(int instructionOffset,
1850                                            int stackIndex)
1851    {
1852        return stacksSimplifiedBefore[instructionOffset][stackIndex];
1853    }
1854
1855
1856    private void markInstruction(int instructionOffset)
1857    {
1858        if (!isInstructionNecessary(instructionOffset))
1859        {
1860            if (DEBUG) System.out.print(instructionOffset+",");
1861
1862            instructionsNecessary[instructionOffset] = true;
1863
1864            if (maxMarkedOffset < instructionOffset)
1865            {
1866                maxMarkedOffset = instructionOffset;
1867            }
1868        }
1869    }
1870
1871
1872    private boolean isAnyInstructionNecessary(int instructionOffset1,
1873                                              int instructionOffset2)
1874    {
1875        for (int instructionOffset = instructionOffset1;
1876             instructionOffset < instructionOffset2;
1877             instructionOffset++)
1878        {
1879            if (isInstructionNecessary(instructionOffset))
1880            {
1881                return true;
1882            }
1883        }
1884
1885        return false;
1886    }
1887
1888
1889    /**
1890     * Returns the highest offset of an instruction that has been marked as
1891     * necessary, before the given offset.
1892     */
1893    private int lastNecessaryInstructionOffset(int instructionOffset)
1894    {
1895        for (int offset = instructionOffset-1; offset >= 0; offset--)
1896        {
1897            if (isInstructionNecessary(instructionOffset))
1898            {
1899                return offset;
1900            }
1901        }
1902
1903        return 0;
1904    }
1905
1906
1907    private boolean isInstructionNecessary(int instructionOffset)
1908    {
1909        return instructionOffset == PartialEvaluator.AT_METHOD_ENTRY ||
1910               instructionsNecessary[instructionOffset];
1911    }
1912}