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


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.visitor.*;
25 import proguard.classfile.attribute.*;
26 import proguard.classfile.attribute.visitor.*;
27 import proguard.classfile.instruction.*;
28 import proguard.classfile.util.*;
29 import proguard.evaluation.*;
30 import proguard.evaluation.value.*;
31 import proguard.optimize.peephole.BranchTargetFinder;
32
33 /**
34  * This AttributeVisitor performs partial evaluation on the code attributes
35  * that it visits.
36  *
37  * @author Eric Lafortune
38  */
39 public class PartialEvaluator
40 extends SimplifiedVisitor
41 implements AttributeVisitor,
42              ExceptionInfoVisitor
43 {
44     //*
45 private static final boolean DEBUG = false;
46     private static final boolean DEBUG_RESULTS = false;
47     /*/
48     private static boolean DEBUG = true;
49     private static boolean DEBUG_RESULTS = true;
50     //*/
51
52     private static final int MAXIMUM_EVALUATION_COUNT = 5;
53
54     public static final int NONE = -2;
55     public static final int AT_METHOD_ENTRY = -1;
56     public static final int AT_CATCH_ENTRY = -1;
57
58     private ValueFactory valueFactory;
59     private InvocationUnit invocationUnit;
60     private boolean evaluateAllCode;
61
62     private InstructionOffsetValue[] varProducerValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH];
63     private InstructionOffsetValue[] stackProducerValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH];
64     private InstructionOffsetValue[] branchOriginValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH];
65     private InstructionOffsetValue[] branchTargetValues = new InstructionOffsetValue[ClassConstants.TYPICAL_CODE_LENGTH];
66     private TracedVariables[] variablesBefore = new TracedVariables[ClassConstants.TYPICAL_CODE_LENGTH];
67     private TracedStack[] stacksBefore = new TracedStack[ClassConstants.TYPICAL_CODE_LENGTH];
68     private TracedVariables[] variablesAfter = new TracedVariables[ClassConstants.TYPICAL_CODE_LENGTH];
69     private TracedStack[] stacksAfter = new TracedStack[ClassConstants.TYPICAL_CODE_LENGTH];
70     private boolean[] generalizedContexts = new boolean[ClassConstants.TYPICAL_CODE_LENGTH];
71     private int[] evaluationCounts = new int[ClassConstants.TYPICAL_CODE_LENGTH];
72     private int[] initializedVariables = new int[ClassConstants.TYPICAL_CODE_LENGTH];
73     private boolean evaluateExceptions;
74
75     private BasicBranchUnit branchUnit;
76     private BranchTargetFinder branchTargetFinder = new BranchTargetFinder();
77 // private ClassCleaner classCleaner = new ClassCleaner();
78
79
80     /**
81      * Creates a new PartialEvaluator.
82      */
83     public PartialEvaluator()
84     {
85         this(new ValueFactory(), new BasicInvocationUnit(), true);
86     }
87
88
89     /**
90      * Creates a new PartialEvaluator.
91      * @param valueFactory the value factory that will create all values
92      * during evaluation.
93      * @param invocationUnit the invocation unit that will handle all
94      * communication with other fields and methods.
95      * @param evaluateAllCode a flag that specifies whether all branch targets
96      * and exception 'catch' blocks should be evaluated,
97      * even if they are unreachable.
98      */
99     public PartialEvaluator(ValueFactory valueFactory,
100                             InvocationUnit invocationUnit,
101                             boolean evaluateAllCode)
102     {
103         this.valueFactory = valueFactory;
104         this.invocationUnit = invocationUnit;
105         this.evaluateAllCode = evaluateAllCode;
106
107         this.branchUnit = evaluateAllCode ?
108             new BasicBranchUnit() :
109             new TracedBranchUnit();
110     }
111
112
113     // Implementations for AttributeVisitor.
114
115     public void visitAnyAttribute(Clazz clazz, Attribute attribute) {}
116
117
118     public void visitCodeAttribute(Clazz clazz, Method method, CodeAttribute codeAttribute)
119     {
120 // DEBUG = DEBUG_RESULTS =
121 // clazz.getName().equals("abc/Def") &&
122 // method.getName(clazz).equals("abc");
123
124         // TODO: Remove this when the partial evaluator has stabilized.
125 // Catch any unexpected exceptions from the actual visiting method.
126 try
127         {
128             // Process the code.
129 visitCodeAttribute0(clazz, method, codeAttribute);
130         }
131         catch (RuntimeException ex)
132         {
133             System.err.println("Unexpected error while performing partial evaluation:");
134             System.err.println(" Class = ["+clazz.getName()+"]");
135             System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
136             System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
137
138             if (DEBUG)
139             {
140                 method.accept(clazz, new ClassPrinter());
141             }
142
143             throw ex;
144         }
145     }
146
147
148     public void visitCodeAttribute0(Clazz clazz, Method method, CodeAttribute codeAttribute)
149     {
150         // Evaluate the instructions, starting at the entry point.
151 if (DEBUG)
152         {
153             System.out.println();
154             System.out.println("Partial evaluation: "+clazz.getName()+"."+method.getName(clazz)+method.getDescriptor(clazz));
155             System.out.println(" Max locals = "+codeAttribute.u2maxLocals);
156             System.out.println(" Max stack = "+codeAttribute.u2maxStack);
157         }
158
159         // Reuse the existing variables and stack objects, ensuring the right size.
160 TracedVariables variables = new TracedVariables(codeAttribute.u2maxLocals);
161         TracedStack stack = new TracedStack(codeAttribute.u2maxStack);
162
163         // Initialize the reusable arrays and variables.
164 initializeVariables(clazz, method, codeAttribute, variables, stack);
165
166         // Find all instruction offsets,...
167 codeAttribute.accept(clazz, method, branchTargetFinder);
168
169         evaluateInstructionBlock(clazz,
170                                  method,
171                                  codeAttribute,
172                                  variables,
173                                  stack,
174                                  0);
175
176         // Evaluate the exception catch blocks, until their entry variables
177 // have stabilized.
178 do
179         {
180             // Reset the flag to stop evaluating.
181 evaluateExceptions = false;
182
183             // Evaluate all relevant exception catch blocks once.
184 codeAttribute.exceptionsAccept(clazz, method, this);
185         }
186         while (evaluateExceptions);
187
188         int codeLength = codeAttribute.u4codeLength;
189
190         if (DEBUG_RESULTS)
191         {
192             System.out.println("Evaluation results:");
193
194             int offset = 0;
195             do
196             {
197                 if (isBranchOrExceptionTarget(offset))
198                 {
199                     System.out.println("Branch target:");
200                     System.out.println(" Vars: "+variablesBefore[offset]);
201                     System.out.println(" Stack: "+stacksBefore[offset]);
202                 }
203
204                 Instruction instruction = InstructionFactory.create(codeAttribute.code,
205                                                                     offset);
206                 System.out.println(instruction.toString(offset));
207
208                 if (isTraced(offset))
209                 {
210                     InstructionOffsetValue varProducerOffsets = varProducerOffsets(offset);
211                     if (varProducerOffsets.instructionOffsetCount() > 0)
212                     {
213                         System.out.println(" has overall been using information from instructions setting vars: "+varProducerOffsets);
214                     }
215
216                     InstructionOffsetValue stackProducerOffsets = stackProducerOffsets(offset);
217                     if (stackProducerOffsets.instructionOffsetCount() > 0)
218                     {
219                         System.out.println(" has overall been using information from instructions setting stack: "+stackProducerOffsets);
220                     }
221
222                     int initializationOffset = branchTargetFinder.initializationOffset(offset);
223                     if (initializationOffset != NONE)
224                     {
225                         System.out.println(" is to be initialized at ["+initializationOffset+"]");
226                     }
227
228                     InstructionOffsetValue branchTargets = branchTargets(offset);
229                     if (branchTargets != null)
230                     {
231                         System.out.println(" has overall been branching to "+branchTargets);
232                     }
233
234                     System.out.println(" Vars: "+variablesAfter[offset]);
235                     System.out.println(" Stack: "+stacksAfter[offset]);
236                 }
237
238                 offset += instruction.length(offset);
239             }
240             while (offset < codeLength);
241         }
242     }
243
244
245     /**
246      * Returns whether a block of instructions is ever used.
247      */
248     public boolean isTraced(int startOffset, int endOffset)
249     {
250         for (int index = startOffset; index < endOffset; index++)
251         {
252             if (isTraced(index))
253             {
254                 return true;
255             }
256         }
257
258         return false;
259     }
260
261
262     /**
263      * Returns whether the instruction at the given offset has ever been
264      * executed during the partial evaluation.
265      */
266     public boolean isTraced(int instructionOffset)
267     {
268         return evaluationCounts[instructionOffset] > 0;
269     }
270
271
272     /**
273      * Returns whether the instruction at the given offset is the target of a
274      * branch instruction or an exception.
275      */
276     public boolean isBranchOrExceptionTarget(int instructionOffset)
277     {
278         return branchTargetFinder.isBranchTarget(instructionOffset) ||
279                branchTargetFinder.isExceptionHandler(instructionOffset);
280     }
281
282
283     /**
284      * Returns whether the instruction at the given offset is part of a
285      * subroutine.
286      */
287     public boolean isSubroutine(int instructionOffset)
288     {
289         return branchTargetFinder.isSubroutine(instructionOffset);
290     }
291
292
293     /**
294      * Returns whether the subroutine at the given offset is ever returning
295      * by means of a regular 'ret' instruction.
296      */
297     public boolean isSubroutineReturning(int instructionOffset)
298     {
299         return branchTargetFinder.isSubroutineReturning(instructionOffset);
300     }
301
302
303     /**
304      * Returns the offset after the subroutine that starts at the given
305      * offset.
306      */
307     public int subroutineEnd(int instructionOffset)
308     {
309         return branchTargetFinder.subroutineEnd(instructionOffset);
310     }
311
312
313     /**
314      * Returns the instruction offset at which the object instance that is
315      * created at the given 'new' instruction offset is initialized, or
316      * <code>NONE</code> if it is not being created.
317      */
318     public int initializationOffset(int instructionOffset)
319     {
320         return branchTargetFinder.initializationOffset(instructionOffset);
321     }
322
323
324     /**
325      * Returns whether the method is an instance initializer.
326      */
327     public boolean isInitializer()
328     {
329         return branchTargetFinder.isInitializer();
330     }
331
332
333     /**
334      * Returns the instruction offset at which this initializer is calling
335      * the "super" or "this" initializer method, or <code>NONE</code> if it is
336      * not an initializer.
337      */
338     public int superInitializationOffset()
339     {
340         return branchTargetFinder.superInitializationOffset();
341     }
342
343
344     /**
345      * Returns the offset of the 'new' instruction that corresponds to the
346      * invocation of the instance initializer at the given offset, or
347      * <code>AT_METHOD_ENTRY</code> if the invocation is calling the "super" or
348      * "this" initializer method, , or <code>NONE</code> if it is not a 'new'
349      * instruction.
350      */
351     public int creationOffset(int offset)
352     {
353         return branchTargetFinder.creationOffset(offset);
354     }
355
356
357     /**
358      * Returns the variables before execution of the instruction at the given
359      * offset.
360      */
361     public TracedVariables getVariablesBefore(int instructionOffset)
362     {
363         return variablesBefore[instructionOffset];
364     }
365
366
367     /**
368      * Returns the variables after execution of the instruction at the given
369      * offset.
370      */
371     public TracedVariables getVariablesAfter(int instructionOffset)
372     {
373         return variablesAfter[instructionOffset];
374     }
375
376
377     /**
378      * Returns the instruction offsets that set the variable that is being
379      * used at the given instruction offset.
380      */
381     public InstructionOffsetValue varProducerOffsets(int instructionOffset)
382     {
383         return varProducerValues[instructionOffset];
384     }
385
386
387     /**
388      * Returns the stack before execution of the instruction at the given
389      * offset.
390      */
391     public TracedStack getStackBefore(int instructionOffset)
392     {
393         return stacksBefore[instructionOffset];
394     }
395
396
397     /**
398      * Returns the stack after execution of the instruction at the given
399      * offset.
400      */
401     public TracedStack getStackAfter(int instructionOffset)
402     {
403         return stacksAfter[instructionOffset];
404     }
405
406
407     /**
408      * Returns the instruction offsets that set the stack entries that are being
409      * used at the given instruction offset.
410      */
411     public InstructionOffsetValue stackProducerOffsets(int instructionOffset)
412     {
413         return stackProducerValues[instructionOffset];
414     }
415
416
417     /**
418      * Returns the instruction offsets that branch to the given instruction
419      * offset.
420      */
421     public InstructionOffsetValue branchOrigins(int instructionOffset)
422     {
423         return branchOriginValues[instructionOffset];
424     }
425
426
427     /**
428      * Returns the instruction offsets to which the given instruction offset
429      * branches.
430      */
431     public InstructionOffsetValue branchTargets(int instructionOffset)
432     {
433         return branchTargetValues[instructionOffset];
434     }
435
436
437     /**
438      * Returns the variable that is initialized at the given instruction offset,
439      * or <code>NONE</code> if no variable was initialized.
440      */
441     public int initializedVariable(int instructionOffset)
442     {
443         return initializedVariables[instructionOffset];
444     }
445
446
447     // Implementations for ExceptionInfoVisitor.
448
449     public void visitExceptionInfo(Clazz clazz, Method method, CodeAttribute codeAttribute, ExceptionInfo exceptionInfo)
450     {
451         int startPC = exceptionInfo.u2startPC;
452         int endPC = exceptionInfo.u2endPC;
453
454         // Do we have to evaluate this exception catch block?
455 if (isTraced(startPC, endPC))
456         {
457             int handlerPC = exceptionInfo.u2handlerPC;
458
459             if (DEBUG) System.out.println("Partial evaluation of exception ["+startPC +","+endPC +"] -> ["+handlerPC+"]:");
460
461             // Reuse the existing variables and stack objects, ensuring the
462 // right size.
463 TracedVariables variables = new TracedVariables(codeAttribute.u2maxLocals);
464             TracedStack stack = new TracedStack(codeAttribute.u2maxStack);
465
466             // Initialize the trace values.
467 Value storeValue = new InstructionOffsetValue(AT_CATCH_ENTRY);
468             variables.setProducerValue(storeValue);
469             stack.setProducerValue(storeValue);
470
471             // Initialize the variables by generalizing the variables of the
472 // try block. Make sure to include the results of the last
473 // instruction for preverification.
474 generalizeVariables(startPC,
475                                 endPC + (evaluateAllCode ? 1 : 0),
476                                 variables);
477
478             // Initialize the the stack.
479 //stack.push(valueFactory.createReference((ClassConstant)((ProgramClass)clazz).getConstant(exceptionInfo.u2catchType), false));
480 String catchType = exceptionInfo.u2catchType != 0 ?
481                  clazz.getClassName(exceptionInfo.u2catchType) :
482                  ClassConstants.INTERNAL_NAME_JAVA_LANG_THROWABLE;
483
484             // TODO: Get catch type class from class constant pool entry.
485 stack.push(valueFactory.createReferenceValue(catchType,
486                                                          null,
487                                                          false));
488
489             int evaluationCount = evaluationCounts[handlerPC];
490
491             // Evaluate the instructions, starting at the entry point.
492 evaluateInstructionBlock(clazz,
493                                      method,
494                                      codeAttribute,
495                                      variables,
496                                      stack,
497                                      handlerPC);
498
499             // Remember to evaluate all exception handlers once more.
500 if (!evaluateExceptions)
501             {
502                 evaluateExceptions = evaluationCount < evaluationCounts[handlerPC];
503             }
504         }
505         else if (evaluateAllCode)
506         {
507             if (DEBUG) System.out.println("No information for partial evaluation of exception ["+startPC +","+endPC +"] -> ["+exceptionInfo.u2handlerPC+"] yet");
508
509             // We don't have any information on the try block yet, but we do
510 // have to evaluate the exception handler.
511 // Remember to evaluate all exception handlers once more.
512 evaluateExceptions = true;
513         }
514         else
515         {
516             if (DEBUG) System.out.println("No information for partial evaluation of exception ["+startPC +","+endPC +"] -> ["+exceptionInfo.u2handlerPC+"]");
517         }
518     }
519
520
521     // Utility methods to evaluate instruction blocks.
522
523     /**
524      * Evaluates a block of instructions, starting at the given offset and ending
525      * at a branch instruction, a return instruction, or a throw instruction.
526      */
527     private void evaluateInstructionBlock(Clazz clazz,
528                                           Method method,
529                                           CodeAttribute codeAttribute,
530                                           TracedVariables variables,
531                                           TracedStack stack,
532                                           int startOffset)
533     {
534         byte[] code = codeAttribute.code;
535
536         if (DEBUG)
537         {
538              System.out.println("Instruction block starting at ["+startOffset+"] in "+
539                                 ClassUtil.externalFullMethodDescription(clazz.getName(),
540                                                                         0,
541                                                                         method.getName(clazz),
542                                                                         method.getDescriptor(clazz)));
543              System.out.println("Init vars: "+variables);
544              System.out.println("Init stack: "+stack);
545         }
546
547         Processor processor = new Processor(variables, stack, valueFactory, branchUnit, invocationUnit);
548
549         int instructionOffset = startOffset;
550
551         int maxOffset = startOffset;
552
553         // Evaluate the subsequent instructions.
554 while (true)
555         {
556             if (maxOffset < instructionOffset)
557             {
558                 maxOffset = instructionOffset;
559             }
560
561             // Maintain a generalized local variable frame and stack at this
562 // instruction offset, before execution.
563 int evaluationCount = evaluationCounts[instructionOffset];
564             if (evaluationCount == 0)
565             {
566                 // First time we're passing by this instruction.
567 if (variablesBefore[instructionOffset] == null)
568                 {
569                     // There's not even a context at this index yet.
570 variablesBefore[instructionOffset] = new TracedVariables(variables);
571                     stacksBefore[instructionOffset] = new TracedStack(stack);
572                 }
573                 else
574                 {
575                     // Reuse the context objects at this index.
576 variablesBefore[instructionOffset].initialize(variables);
577                     stacksBefore[instructionOffset].copy(stack);
578                 }
579
580                 // We'll execute in the generalized context, because it is
581 // the same as the current context.
582 generalizedContexts[instructionOffset] = true;
583             }
584             else
585             {
586                 // Merge in the current context.
587 boolean variablesChanged = variablesBefore[instructionOffset].generalize(variables, true);
588                 boolean stackChanged = stacksBefore[instructionOffset].generalize(stack);
589
590                 // Bail out if the current context is the same as last time.
591 if (!variablesChanged &&
592                     !stackChanged &&
593                     generalizedContexts[instructionOffset])
594                 {
595                     if (DEBUG) System.out.println("Repeated variables, stack, and branch targets");
596
597                     break;
598                 }
599
600                 // See if this instruction has been evaluated an excessive number
601 // of times.
602 if (evaluationCount >= MAXIMUM_EVALUATION_COUNT)
603                 {
604                     if (DEBUG) System.out.println("Generalizing current context after "+evaluationCount+" evaluations");
605
606                     // Continue, but generalize the current context.
607 // Note that the most recent variable values have to remain
608 // last in the generalizations, for the sake of the ret
609 // instruction.
610 variables.generalize(variablesBefore[instructionOffset], false);
611                     stack.generalize(stacksBefore[instructionOffset]);
612
613                     // We'll execute in the generalized context.
614 generalizedContexts[instructionOffset] = true;
615                 }
616                 else
617                 {
618                     // We'll execute in the current context.
619 generalizedContexts[instructionOffset] = false;
620                 }
621             }
622
623             // We'll evaluate this instruction.
624 evaluationCounts[instructionOffset]++;
625
626             // Remember this instruction's offset with any stored value.
627 Value storeValue = new InstructionOffsetValue(instructionOffset);
628             variables.setProducerValue(storeValue);
629             stack.setProducerValue(storeValue);
630
631             // Reset the trace value.
632 InstructionOffsetValue traceValue = InstructionOffsetValue.EMPTY_VALUE;
633             variables.setCollectedProducerValue(traceValue);
634             stack.setCollectedProducerValue(traceValue);
635
636             // Reset the initialization flag.
637 variables.resetInitialization();
638
639             // Note that the instruction is only volatile.
640 Instruction instruction = InstructionFactory.create(code, instructionOffset);
641
642             // By default, the next instruction will be the one after this
643 // instruction.
644 int nextInstructionOffset = instructionOffset +
645                                         instruction.length(instructionOffset);
646             InstructionOffsetValue nextInstructionOffsetValue = new InstructionOffsetValue(nextInstructionOffset);
647             branchUnit.resetCalled();
648             branchUnit.setTraceBranchTargets(nextInstructionOffsetValue);
649
650             if (DEBUG)
651             {
652                 System.out.println(instruction.toString(instructionOffset));
653             }
654
655             try
656             {
657                 // Process the instruction. The processor may modify the
658 // variables and the stack, and it may call the branch unit
659 // and the invocation unit.
660 instruction.accept(clazz,
661                                    method,
662                                    codeAttribute,
663                                    instructionOffset,
664                                    processor);
665             }
666             catch (RuntimeException ex)
667             {
668                 System.err.println("Unexpected error while evaluating instruction:");
669                 System.err.println(" Class = ["+clazz.getName()+"]");
670                 System.err.println(" Method = ["+method.getName(clazz)+method.getDescriptor(clazz)+"]");
671                 System.err.println(" Instruction = "+instruction.toString(instructionOffset));
672                 System.err.println(" Exception = ["+ex.getClass().getName()+"] ("+ex.getMessage()+")");
673
674                 throw ex;
675             }
676
677             // Collect the offsets of the instructions whose results were used.
678 InstructionOffsetValue variablesTraceValue = variables.getCollectedProducerValue().instructionOffsetValue();
679             InstructionOffsetValue stackTraceValue = stack.getCollectedProducerValue().instructionOffsetValue();
680             varProducerValues[instructionOffset] =
681                 varProducerValues[instructionOffset].generalize(variablesTraceValue).instructionOffsetValue();
682             stackProducerValues[instructionOffset] =
683                 stackProducerValues[instructionOffset].generalize(stackTraceValue).instructionOffsetValue();
684             initializedVariables[instructionOffset] = variables.getInitializationIndex();
685
686             // Collect the branch targets from the branch unit.
687 InstructionOffsetValue branchTargets = branchUnit.getTraceBranchTargets();
688             int branchTargetCount = branchTargets.instructionOffsetCount();
689
690             // Stop tracing.
691 variables.setCollectedProducerValue(traceValue);
692             stack.setCollectedProducerValue(traceValue);
693             branchUnit.setTraceBranchTargets(traceValue);
694
695             if (DEBUG)
696             {
697                 if (variablesTraceValue.instructionOffsetCount() > 0)
698                 {
699                     System.out.println(" has used information from instructions setting vars: "+variablesTraceValue);
700                 }
701                 if (stackTraceValue.instructionOffsetCount() > 0)
702                 {
703                     System.out.println(" has used information from instructions setting stack: "+stackTraceValue);
704                 }
705                 if (branchUnit.wasCalled())
706                 {
707                     System.out.println(" is branching to "+branchTargets);
708                 }
709
710                 if (varProducerValues[instructionOffset].instructionOffsetCount() > 0)
711                 {
712                     System.out.println(" has up till now been using information from instructions setting vars: "+varProducerValues[instructionOffset]);
713                 }
714                 if (stackProducerValues[instructionOffset].instructionOffsetCount() > 0)
715                 {
716                     System.out.println(" has up till now been using information from instructions setting stack: "+stackProducerValues[instructionOffset]);
717                 }
718                 if (branchTargetValues[instructionOffset] != null)
719                 {
720                     System.out.println(" has up till now been branching to "+branchTargetValues[instructionOffset]);
721                 }
722
723                 System.out.println(" Vars: "+variables);
724                 System.out.println(" Stack: "+stack);
725             }
726
727             // Maintain a generalized local variable frame and stack at this
728 // instruction offset, after execution.
729 if (evaluationCount == 0)
730             {
731                 // First time we're passing by this instruction.
732 if (variablesAfter[instructionOffset] == null)
733                 {
734                     // There's not even a context at this index yet.
735 variablesAfter[instructionOffset] = new TracedVariables(variables);
736                     stacksAfter[instructionOffset] = new TracedStack(stack);
737                 }
738                 else
739                 {
740                     // Reuse the context objects at this index.
741 variablesAfter[instructionOffset].initialize(variables);
742                     stacksAfter[instructionOffset].copy(stack);
743                 }
744             }
745             else
746             {
747                 // Merge in the current context.
748 variablesAfter[instructionOffset].generalize(variables, true);
749                 stacksAfter[instructionOffset].generalize(stack);
750             }
751
752             // Did the branch unit get called?
753 if (branchUnit.wasCalled())
754             {
755                 // Accumulate the branch targets at this offset.
756 branchTargetValues[instructionOffset] = branchTargetValues[instructionOffset] == null ?
757                     branchTargets :
758                     branchTargetValues[instructionOffset].generalize(branchTargets).instructionOffsetValue();
759
760                 // Are there no branch targets at all?
761 if (branchTargetCount == 0)
762                 {
763                     // Exit from this code block.
764 break;
765                 }
766
767                 // Accumulate the branch origins at the branch target offsets.
768 InstructionOffsetValue instructionOffsetValue = new InstructionOffsetValue(instructionOffset);
769                 for (int index = 0; index < branchTargetCount; index++)
770                 {
771                     int branchTarget = branchTargets.instructionOffset(index);
772                     branchOriginValues[branchTarget] = branchOriginValues[branchTarget] == null ?
773                         instructionOffsetValue:
774                         branchOriginValues[branchTarget].generalize(instructionOffsetValue).instructionOffsetValue();
775                 }
776
777                 // Are there multiple branch targets?
778 if (branchTargetCount > 1)
779                 {
780                     // Handle them recursively and exit from this code block.
781 for (int index = 0; index < branchTargetCount; index++)
782                     {
783                         if (DEBUG) System.out.println("Alternative branch #"+index+" out of "+branchTargetCount+", from ["+instructionOffset+"] to ["+branchTargets.instructionOffset(index)+"]");
784
785                         evaluateInstructionBlock(clazz,
786                                                  method,
787                                                  codeAttribute,
788                                                  new TracedVariables(variables),
789                                                  new TracedStack(stack),
790                                                  branchTargets.instructionOffset(index));
791                     }
792
793                     break;
794                 }
795
796                 if (DEBUG) System.out.println("Definite branch from ["+instructionOffset+"] to ["+branchTargets.instructionOffset(0)+"]");
797             }
798
799             // Just continue with the next instruction.
800 instructionOffset = branchTargets.instructionOffset(0);
801
802             // Clear the context of a subroutine before entering it, in order
803 // to avoid context conflicts across different invocations.
804 if (instruction.opcode == InstructionConstants.OP_JSR ||
805                 instruction.opcode == InstructionConstants.OP_JSR_W)
806             {
807                 // A subroutine has a single entry point and a single exit point,
808 // so we can easily loop over its instructions.
809 int subroutineEnd = branchTargetFinder.subroutineEnd(instructionOffset);
810
811                 if (DEBUG) System.out.println("Clearing context of subroutine from "+instructionOffset+" to "+subroutineEnd);
812
813                 for (int offset = instructionOffset; offset < subroutineEnd; offset++)
814                 {
815                     if (branchTargetFinder.isInstruction(offset))
816                     {
817                         evaluationCounts[offset] = 0;
818                     }
819                 }
820
821                 evaluateInstructionBlock(clazz,
822                                          method,
823                                          codeAttribute,
824                                          new TracedVariables(variables),
825                                          new TracedStack(stack),
826                                          instructionOffset);
827
828                 if (DEBUG) System.out.println("Evaluating exceptions of subroutine from "+instructionOffset+" to "+subroutineEnd);
829
830                 // Evaluate all relevant exception catch blocks once.
831 codeAttribute.exceptionsAccept(clazz,
832                                                method,
833                                                instructionOffset,
834                                                subroutineEnd,
835                                                this);
836
837                 if (DEBUG) System.out.println("Ending subroutine from "+instructionOffset+" to "+subroutineEnd);
838
839                 break;
840             }
841         }
842
843         if (DEBUG) System.out.println("Ending processing of instruction block starting at ["+startOffset+"]");
844     }
845
846
847     // Small utility methods.
848
849     /**
850      * Initializes the data structures for the variables, stack, etc.
851      */
852     private void initializeVariables(Clazz clazz,
853                                      Method method,
854                                      CodeAttribute codeAttribute,
855                                      TracedVariables variables,
856                                      TracedStack stack)
857     {
858         int codeLength = codeAttribute.u4codeLength;
859
860         // Create new arrays for storing information at each instruction offset.
861 if (variablesAfter.length < codeLength)
862         {
863             // Create new arrays.
864 varProducerValues = new InstructionOffsetValue[codeLength];
865             stackProducerValues = new InstructionOffsetValue[codeLength];
866             branchOriginValues = new InstructionOffsetValue[codeLength];
867             branchTargetValues = new InstructionOffsetValue[codeLength];
868             variablesBefore = new TracedVariables[codeLength];
869             stacksBefore = new TracedStack[codeLength];
870             variablesAfter = new TracedVariables[codeLength];
871             stacksAfter = new TracedStack[codeLength];
872             generalizedContexts = new boolean[codeLength];
873             evaluationCounts = new int[codeLength];
874             initializedVariables = new int[codeLength];
875
876             // Reset the arrays.
877 for (int index = 0; index < codeLength; index++)
878             {
879                 varProducerValues[index] = InstructionOffsetValue.EMPTY_VALUE;
880                 stackProducerValues[index] = InstructionOffsetValue.EMPTY_VALUE;
881                 initializedVariables[index] = NONE;
882             }
883         }
884         else
885         {
886             // Reset the arrays.
887 for (int index = 0; index < codeLength; index++)
888             {
889                 varProducerValues[index] = InstructionOffsetValue.EMPTY_VALUE;
890                 stackProducerValues[index] = InstructionOffsetValue.EMPTY_VALUE;
891                 branchOriginValues[index] = null;
892                 branchTargetValues[index] = null;
893                 generalizedContexts[index] = false;
894                 evaluationCounts[index] = 0;
895                 initializedVariables[index] = NONE;
896
897                 if (variablesBefore[index] != null)
898                 {
899                     variablesBefore[index].reset(codeAttribute.u2maxLocals);
900                 }
901
902                 if (stacksBefore[index] != null)
903                 {
904                     stacksBefore[index].reset(codeAttribute.u2maxStack);
905                 }
906
907                 if (variablesAfter[index] != null)
908                 {
909                     variablesAfter[index].reset(codeAttribute.u2maxLocals);
910                 }
911
912                 if (stacksAfter[index] != null)
913                 {
914                     stacksAfter[index].reset(codeAttribute.u2maxStack);
915                 }
916             }
917         }
918
919         // Create the method parameters.
920 TracedVariables parameters = new TracedVariables(codeAttribute.u2maxLocals);
921
922         // Remember this instruction's offset with any stored value.
923 Value storeValue = new InstructionOffsetValue(AT_METHOD_ENTRY);
924         parameters.setProducerValue(storeValue);
925
926         // Reset the trace value.
927 InstructionOffsetValue traceValue = InstructionOffsetValue.EMPTY_VALUE;
928         parameters.setCollectedProducerValue(traceValue);
929
930         // Initialize the method parameters.
931 invocationUnit.enterMethod(clazz, method, parameters);
932
933         if (DEBUG)
934         {
935             System.out.println(" Params: "+parameters);
936         }
937
938         // Initialize the variables with the parameters.
939 variables.initialize(parameters);
940
941         // Set the store value of each parameter variable.
942 InstructionOffsetValue atMethodEntry = new InstructionOffsetValue(AT_METHOD_ENTRY);
943
944         for (int index = 0; index < parameters.size(); index++)
945         {
946             variables.setProducerValue(index, atMethodEntry);
947         }
948     }
949
950
951     /**
952      * Generalize the local variable frames of a block of instructions.
953      */
954     private void generalizeVariables(int startOffset, int endOffset, TracedVariables generalizedVariables)
955     {
956         boolean first = true;
957
958         for (int index = startOffset; index < endOffset; index++)
959         {
960             if (isTraced(index))
961             {
962                 TracedVariables tracedVariables = variablesBefore[index];
963
964                 if (first)
965                 {
966                     // Initialize the variables with the first traced local
967 // variable frame.
968 generalizedVariables.initialize(tracedVariables);
969
970                     first = false;
971                 }
972                 else
973                 {
974                     // Generalize the variables with the traced local variable
975 // frame. We can't use the return value, because local
976 // generalization can be different a couple of times,
977 // with the global generalization being the same.
978 generalizedVariables.generalize(tracedVariables, false);
979                 }
980             }
981         }
982
983         // Just clear the variables if there aren't any traced instructions
984 // in the block.
985 if (first)
986         {
987             generalizedVariables.reset(generalizedVariables.size());
988         }
989     }
990 }
991

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags