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