Java > Open Source Codes > proguard > optimize > evaluation > EvaluationSimplifier


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags