23
23
import proguard.classfile.*;
24
24
import proguard.classfile.attribute.*;
25
import proguard.classfile.attribute.annotation.*;
26
import proguard.classfile.editor.*;
27
25
import proguard.classfile.instruction.*;
28
import proguard.classfile.util.*;
29
import proguard.classfile.visitor.*;
30
import proguard.optimize.*;
26
import proguard.classfile.util.ClassUtil;
31
27
import proguard.optimize.evaluation.value.*;
28
import proguard.optimize.peephole.BranchTargetFinder;
34
* This MemberInfoVisitor performs partial evaluation on the program methods
31
* This class performs partial evaluation.
37
33
* @author Eric Lafortune
39
35
public class PartialEvaluator
40
implements MemberInfoVisitor,
36
implements ExceptionInfoVisitor,
47
private static final boolean DEBUG_RESULTS = false;
48
private static final boolean DEBUG_ANALYSIS = false;
49
private static final boolean DEBUG = false;
40
private static final boolean DEBUG = false;
41
private static final boolean DEBUG_RESULTS = false;
51
private static boolean DEBUG_RESULTS = true;
52
private static boolean DEBUG_ANALYSIS = true;
53
private static boolean DEBUG = true;
43
private static boolean DEBUG = true;
44
private static boolean DEBUG_RESULTS = true;
56
47
private static final int INITIAL_CODE_LENGTH = 1024;
57
48
private static final int INITIAL_VALUE_COUNT = 32;
59
private static final int MAXIMUM_EVALUATION_COUNT = 100;
62
private InstructionOffsetValue[] varTraceValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
63
private InstructionOffsetValue[] stackTraceValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
64
private InstructionOffsetValue[] branchOriginValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
65
private InstructionOffsetValue[] branchTargetValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
66
private TracedVariables[] vars = new TracedVariables[INITIAL_CODE_LENGTH];
67
private TracedStack[] stacks = new TracedStack[INITIAL_CODE_LENGTH];
68
private int[] evaluationCounts = new int[INITIAL_CODE_LENGTH];
69
private boolean[] initialization = new boolean[INITIAL_CODE_LENGTH];
70
private boolean[] isNecessary = new boolean[INITIAL_CODE_LENGTH];
50
//private static final int MAXIMUM_EVALUATION_COUNT = 100;
52
public static final int AT_METHOD_ENTRY = -1;
53
public static final int AT_CATCH_ENTRY = -1;
54
public static final int NONE = -1;
56
private BranchTargetFinder branchTargetFinder = new BranchTargetFinder(1024);
58
private InstructionOffsetValue[] varProducerValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
59
private InstructionOffsetValue[] stackProducerValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
60
private InstructionOffsetValue[] unusedProducerValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
61
private InstructionOffsetValue[] branchOriginValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
62
private InstructionOffsetValue[] branchTargetValues = new InstructionOffsetValue[INITIAL_CODE_LENGTH];
63
private TracedVariables[] vars = new TracedVariables[INITIAL_CODE_LENGTH];
64
private TracedStack[] stacks = new TracedStack[INITIAL_CODE_LENGTH];
65
private int[] evaluationCounts = new int[INITIAL_CODE_LENGTH];
66
private int[] initializedVariables = new int[INITIAL_CODE_LENGTH];
71
67
private boolean evaluateExceptions;
73
private TracedVariables parameters = new TracedVariables(INITIAL_VALUE_COUNT);
74
69
private TracedVariables variables = new TracedVariables(INITIAL_VALUE_COUNT);
75
70
private TracedStack stack = new TracedStack(INITIAL_VALUE_COUNT);
76
71
private TracedBranchUnit branchUnit = new TracedBranchUnit();
78
private ClassFileCleaner classFileCleaner = new ClassFileCleaner();
79
private SideEffectInstructionChecker sideEffectInstructionChecker = new SideEffectInstructionChecker(true);
80
private CodeAttrInfoEditor codeAttrInfoEditor = new CodeAttrInfoEditor(INITIAL_CODE_LENGTH);
82
private boolean isInitializer;
85
// Implementations for MemberInfoVisitor.
87
public void visitProgramFieldInfo(ProgramClassFile programClassFile, ProgramFieldInfo programFieldInfo) {}
90
public void visitProgramMethodInfo(ProgramClassFile programClassFile, ProgramMethodInfo programMethodInfo)
92
// DEBUG = DEBUG_ANALYSIS = DEBUG_RESULTS =
93
// programClassFile.getName().equals("abc/Def") &&
94
// programMethodInfo.getName(programClassFile).equals("abc");
96
// Initialize the parameters.
98
(programMethodInfo.u2accessFlags & ClassConstants.INTERNAL_ACC_STATIC) != 0;
100
// Count the number of parameters, taking into account their Categories.
101
String parameterDescriptor = programMethodInfo.getDescriptor(programClassFile);
102
int count = (isStatic ? 0 : 1) +
103
ClassUtil.internalMethodParameterSize(parameterDescriptor);
105
// Reuse the existing parameters object, ensuring the right size.
106
parameters.reset(count);
108
// Go over the parameters again.
109
InternalTypeEnumeration internalTypeEnumeration =
110
new InternalTypeEnumeration(parameterDescriptor);
114
// Clear the store value of each parameter.
115
parameters.setStoreValue(InstructionOffsetValueFactory.create());
117
// Put the caller's reference in parameter 0.
120
parameters.store(index++, ReferenceValueFactory.create(false));
123
while (internalTypeEnumeration.hasMoreTypes())
125
String type = internalTypeEnumeration.nextType();
127
// Get a generic corresponding value.
128
Value value = ValueFactory.create(type);
130
// Store the value in the parameter.
131
parameters.store(index, value);
133
// Increment the index according to the Category of the value.
134
index += value.isCategory2() ? 2 : 1;
137
// Reset the return value.
138
branchUnit.setTraceReturnValue(null);
143
programMethodInfo.attributesAccept(programClassFile, this);
145
catch (RuntimeException ex)
147
// TODO: Remove this when the partial evaluator has stabilized.
148
System.err.println("Unexpected error while optimizing after partial evaluation:");
149
System.err.println(" ClassFile = ["+programClassFile.getName()+"]");
150
System.err.println(" Method = ["+programMethodInfo.getName(programClassFile)+programMethodInfo.getDescriptor(programClassFile)+"]");
151
System.err.println("Not optimizing this method");
161
Value returnValue = branchUnit.getTraceReturnValue();
162
if (returnValue != null)
164
System.out.println("Return value for method "+
165
ClassUtil.externalFullMethodDescription(programClassFile.getName(),
167
programMethodInfo.getName(programClassFile),
168
programMethodInfo.getDescriptor(programClassFile))+
169
" -> ["+returnValue.toString()+"]");
170
System.out.println();
176
public void visitLibraryFieldInfo(LibraryClassFile libraryClassFile, LibraryFieldInfo libraryFieldInfo) {}
177
public void visitLibraryMethodInfo(LibraryClassFile libraryClassFile, LibraryMethodInfo libraryMethodInfo) {}
180
// Implementations for AttrInfoVisitor.
182
public void visitUnknownAttrInfo(ClassFile classFile, UnknownAttrInfo unknownAttrInfo) {}
183
public void visitInnerClassesAttrInfo(ClassFile classFile, InnerClassesAttrInfo innerClassesAttrInfo) {}
184
public void visitEnclosingMethodAttrInfo(ClassFile classFile, EnclosingMethodAttrInfo enclosingMethodAttrInfo) {}
185
public void visitConstantValueAttrInfo(ClassFile classFile, FieldInfo fieldInfo, ConstantValueAttrInfo constantValueAttrInfo) {}
186
public void visitExceptionsAttrInfo(ClassFile classFile, MethodInfo methodInfo, ExceptionsAttrInfo exceptionsAttrInfo) {}
187
public void visitLineNumberTableAttrInfo(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, LineNumberTableAttrInfo lineNumberTableAttrInfo) {}
188
public void visitLocalVariableTableAttrInfo(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, LocalVariableTableAttrInfo localVariableTableAttrInfo) {}
189
public void visitLocalVariableTypeTableAttrInfo(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, LocalVariableTypeTableAttrInfo localVariableTypeTableAttrInfo) {}
190
public void visitSourceFileAttrInfo(ClassFile classFile, SourceFileAttrInfo sourceFileAttrInfo) {}
191
public void visitSourceDirAttrInfo(ClassFile classFile, SourceDirAttrInfo sourceDirAttrInfo) {}
192
public void visitDeprecatedAttrInfo(ClassFile classFile, DeprecatedAttrInfo deprecatedAttrInfo) {}
193
public void visitSyntheticAttrInfo(ClassFile classFile, SyntheticAttrInfo syntheticAttrInfo) {}
194
public void visitSignatureAttrInfo(ClassFile classFile, SignatureAttrInfo signatureAttrInfo) {}
195
public void visitRuntimeVisibleAnnotationAttrInfo(ClassFile classFile, RuntimeVisibleAnnotationsAttrInfo runtimeVisibleAnnotationsAttrInfo) {}
196
public void visitRuntimeInvisibleAnnotationAttrInfo(ClassFile classFile, RuntimeInvisibleAnnotationsAttrInfo runtimeInvisibleAnnotationsAttrInfo) {}
197
public void visitRuntimeVisibleParameterAnnotationAttrInfo(ClassFile classFile, RuntimeVisibleParameterAnnotationsAttrInfo runtimeVisibleParameterAnnotationsAttrInfo) {}
198
public void visitRuntimeInvisibleParameterAnnotationAttrInfo(ClassFile classFile, RuntimeInvisibleParameterAnnotationsAttrInfo runtimeInvisibleParameterAnnotationsAttrInfo) {}
199
public void visitAnnotationDefaultAttrInfo(ClassFile classFile, AnnotationDefaultAttrInfo annotationDefaultAttrInfo) {}
202
public void visitCodeAttrInfo(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo)
206
System.out.println();
207
System.out.println("Class "+ClassUtil.externalClassName(classFile.getName()));
208
System.out.println("Method "+ClassUtil.externalFullMethodDescription(classFile.getName(),
210
methodInfo.getName(classFile),
211
methodInfo.getDescriptor(classFile)));
212
System.out.println(" Params:"+parameters);
215
int codeLength = codeAttrInfo.u4codeLength;
217
// Reset the code changes.
218
codeAttrInfoEditor.reset(codeLength);
222
System.out.println(" Max locals = "+codeAttrInfo.u2maxLocals);
223
System.out.println(" Max stack = "+codeAttrInfo.u2maxStack);
226
// Create new arrays for storing a stack and a set of variables at each
228
if (isNecessary.length < codeLength)
230
varTraceValues = new InstructionOffsetValue[codeLength];
231
stackTraceValues = new InstructionOffsetValue[codeLength];
232
branchOriginValues = new InstructionOffsetValue[codeLength];
233
branchTargetValues = new InstructionOffsetValue[codeLength];
234
vars = new TracedVariables[codeLength];
235
stacks = new TracedStack[codeLength];
236
evaluationCounts = new int[codeLength];
237
initialization = new boolean[codeLength];
238
isNecessary = new boolean[codeLength];
242
for (int index = 0; index < codeLength; index++)
244
varTraceValues[index] = null;
245
stackTraceValues[index] = null;
246
branchOriginValues[index] = null;
247
branchTargetValues[index] = null;
248
evaluationCounts[index] = 0;
249
initialization[index] = false;
250
isNecessary[index] = false;
252
if (vars[index] != null)
254
vars[index].reset(codeAttrInfo.u2maxLocals);
257
if (stacks[index] != null)
259
stacks[index].reset(codeAttrInfo.u2maxStack);
264
// Reuse the existing variables and stack objects, ensuring the right size.
265
variables.reset(codeAttrInfo.u2maxLocals);
266
stack.reset(codeAttrInfo.u2maxStack);
268
// Initialize the local variables with the parameters.
269
variables.initialize(parameters);
75
* Performs partial evaluation of the given method with the given parameters.
76
* @param classFile the method's class file.
77
* @param methodInfo the method's header.
78
* @param codeAttrInfo the method's code.
79
* @param parameters the method parameters.
80
* @return the partial result.
82
public Value evaluate(ClassFile classFile,
83
MethodInfo methodInfo,
84
CodeAttrInfo codeAttrInfo,
87
// Initialize the reusable arrays and variables.
88
initializeVariables(codeAttrInfo, parameters);
90
// Find all instruction offsets,...
91
codeAttrInfo.accept(classFile, methodInfo, branchTargetFinder);
271
93
// Evaluate the instructions, starting at the entry point.
272
94
if (DEBUG) System.out.println("Partial evaluation: ");
292
114
while (evaluateExceptions);
294
// Clean up the visitor information in the exceptions right away.
295
codeAttrInfo.exceptionsAccept(classFile, methodInfo, classFileCleaner);
297
// Replace any instructions that can be simplified.
298
if (DEBUG_ANALYSIS) System.out.println("Instruction simplification:");
300
codeAttrInfo.instructionsAccept(classFile, methodInfo, this);
303
// Mark all essential instructions that have been encountered as used.
304
if (DEBUG_ANALYSIS) System.out.println("Usage initialization: ");
306
// The invocation of the "super" or "this" <init> method inside a
307
// constructor is always necessary, even if it is assumed to have no
309
boolean markSuperOrThis =
310
methodInfo.getName(classFile).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT);
319
Instruction instruction = InstructionFactory.create(codeAttrInfo.code,
322
// Remember the most recent aload0 instruction index.
323
if (instruction.opcode == InstructionConstants.OP_ALOAD_0)
328
// Mark the instruction as necessary if it is the first
329
// invocation of the "super" or "this" <init> method
330
// inside a constructor.
331
else if (markSuperOrThis &&
332
instruction.opcode == InstructionConstants.OP_INVOKESPECIAL &&
333
stackTraceValues[index].contains(aload0Index))
335
markSuperOrThis = false;
337
if (DEBUG_ANALYSIS) System.out.print(index+",");
338
isNecessary[index] = true;
341
// Mark the instruction as necessary if it has side effects.
342
else if (sideEffectInstructionChecker.hasSideEffects(classFile,
348
if (DEBUG_ANALYSIS) System.out.print(index+",");
349
isNecessary[index] = true;
355
while (index < codeLength);
356
if (DEBUG_ANALYSIS) System.out.println();
359
// Mark all other instructions on which the essential instructions
360
// depend. Instead of doing this recursively, we loop across all
361
// instructions, starting at the last one, and restarting at any
362
// higher, previously unmarked instruction that is being marked.
363
if (DEBUG_ANALYSIS) System.out.println("Usage marking:");
365
int lowestNecessaryIndex = codeLength;
366
index = codeLength - 1;
369
int nextIndex = index - 1;
371
// Update the lowest index of all marked instructions higher up.
372
if (isNecessary[index])
374
lowestNecessaryIndex = index;
377
// Check if this instruction is a branch origin from a branch that
378
// straddles some marked code.
379
nextIndex = markStraddlingBranches(index,
380
branchTargetValues[index],
382
lowestNecessaryIndex,
385
// Mark the instructions on which this instruction depends.
386
nextIndex = markDependencies(index,
389
// Update the lowest index of all marked instructions higher up.
390
if (isNecessary[index])
392
lowestNecessaryIndex = index;
395
// Check if this instruction is a branch target from a branch that
396
// straddles some marked code.
397
nextIndex = markStraddlingBranches(index,
398
branchOriginValues[index],
400
lowestNecessaryIndex,
405
if (nextIndex >= index)
407
System.out.println();
411
// Update the lowest index of all marked instructions higher up.
412
if (isNecessary[index])
414
lowestNecessaryIndex = index;
417
// Update the index of the instruction to be investigated next.
421
if (DEBUG_ANALYSIS) System.out.println();
424
// Insert pop instructions where necessary, to keep the stack consistent.
425
if (DEBUG_ANALYSIS) System.out.println("Stack consistency marking:");
427
index = codeLength - 1;
430
if (isTraced(index) &&
433
// Make sure the stack is always consistent at this offset.
434
fixStackConsistency(classFile,
442
if (DEBUG_ANALYSIS) System.out.println();
445
// Fix dup/swap instructions where necessary, to keep the stack consistent.
446
if (DEBUG_ANALYSIS) System.out.println("Dup/swap fixing:");
451
if (isNecessary[index])
453
// Make sure any dup/swap instructions are always consistent at this offset.
454
fixDupInstruction(codeAttrInfo,
460
while (index < codeLength);
461
if (DEBUG_ANALYSIS) System.out.println();
464
// Mark branches straddling just inserted push/pop instructions.
465
if (DEBUG_ANALYSIS) System.out.println("Final straddling branch marking:");
467
lowestNecessaryIndex = codeLength;
468
index = codeLength - 1;
471
int nextIndex = index - 1;
473
// Update the lowest index of all marked instructions higher up.
474
if (isNecessary[index])
476
lowestNecessaryIndex = index;
479
// Check if this instruction is a branch origin from a branch that
480
// straddles some marked code.
481
nextIndex = markAndSimplifyStraddlingBranches(index,
482
branchTargetValues[index],
483
lowestNecessaryIndex,
486
// Update the lowest index of all marked instructions higher up.
487
if (isNecessary[index])
489
lowestNecessaryIndex = index;
492
// Check if this instruction is a branch target from a branch that
493
// straddles some marked code.
494
nextIndex = markAndSimplifyStraddlingBranches(branchOriginValues[index],
496
lowestNecessaryIndex,
501
if (nextIndex >= index)
503
System.out.println();
507
// Update the lowest index of all marked instructions higher up.
508
if (isNecessary[index])
510
lowestNecessaryIndex = index;
513
// Update the index of the instruction to be investigated next.
517
if (DEBUG_ANALYSIS) System.out.println();
520
// Mark variable initializations, even if they aren't strictly necessary.
521
// The virtual machine is not smart enough to see this, and may complain
523
if (DEBUG_ANALYSIS) System.out.println("Initialization marking: ");
525
// TODO: Find a better way.
529
// Is it an initialization that hasn't been marked yet?
530
if (initialization[index] &&
533
if (DEBUG_ANALYSIS) System.out.println(index+",");
535
// Figure out what kind of initialization value has to be stored.
536
int pushInstructionOffset = stackTraceValues[index].instructionOffset(0);
537
int pushComputationalType = stacks[pushInstructionOffset].getTop(0).computationalType();
538
increaseStackSize(index, pushComputationalType, false);
543
while (index < codeLength);
544
if (DEBUG_ANALYSIS) System.out.println();
547
116
if (DEBUG_RESULTS)
549
System.out.println("Results:");
118
System.out.println("Evaluation results:");
120
int codeLength = codeAttrInfo.u4codeLength;
553
125
Instruction instruction = InstructionFactory.create(codeAttrInfo.code,
555
System.out.println((isNecessary[offset] ? " + " : " - ")+instruction.toString(offset));
127
System.out.println(instruction.toString(offset));
556
128
if (isTraced(offset))
558
if (varTraceValues[offset] != null &&
559
varTraceValues[offset].instructionOffsetCount() > 0)
561
System.out.println(" has overall been using information from instructions setting vars: "+varTraceValues[offset]);
563
if (stackTraceValues[offset] != null &&
564
stackTraceValues[offset].instructionOffsetCount() > 0)
566
System.out.println(" has overall been using information from instructions setting stack: "+stackTraceValues[offset]);
568
if (branchTargetValues[offset] != null)
570
System.out.println(" has overall been branching to "+branchTargetValues[offset]);
572
if (codeAttrInfoEditor.preInsertions[offset] != null)
574
System.out.println(" is preceded by: "+codeAttrInfoEditor.preInsertions[offset]);
576
if (codeAttrInfoEditor.postInsertions[offset] != null)
578
System.out.println(" is followed by: "+codeAttrInfoEditor.preInsertions[offset]);
130
InstructionOffsetValue varProducerOffsets = varProducerOffsets(offset);
131
if (varProducerOffsets.instructionOffsetCount() > 0)
133
System.out.println(" has overall been using information from instructions setting vars: "+varProducerOffsets);
136
InstructionOffsetValue stackProducerOffsets = stackProducerOffsets(offset);
137
if (stackProducerOffsets.instructionOffsetCount() > 0)
139
System.out.println(" has overall been using information from instructions setting stack: "+stackProducerOffsets);
142
InstructionOffsetValue unusedProducerOffsets = unusedProducerOffsets(offset);
143
if (unusedProducerOffsets.instructionOffsetCount() > 0)
145
System.out.println(" no longer needs information from instructions setting stack: "+unusedProducerOffsets);
148
InstructionOffsetValue branchTargets = branchTargets(offset);
149
if (branchTargets != null)
151
System.out.println(" has overall been branching to "+branchTargets);
580
154
System.out.println(" Vars: "+vars[offset]);
581
155
System.out.println(" Stack: "+stacks[offset]);
586
160
while (offset < codeLength);
589
// Delete all instructions that are not used.
593
Instruction instruction = InstructionFactory.create(codeAttrInfo.code,
595
if (!isNecessary[offset])
597
codeAttrInfoEditor.replaceInstruction(offset, null);
598
codeAttrInfoEditor.replaceInstruction2(offset, null);
601
offset += instruction.length(offset);
603
while (offset < codeLength);
605
// Apply all accumulated changes to the code.
606
codeAttrInfoEditor.visitCodeAttrInfo(classFile, methodInfo, codeAttrInfo);
611
* Marks the instructions at the given offsets, if the current instruction
612
* itself has been marked.
613
* @param index the offset of the current instruction.
614
* @param nextIndex the index of the instruction to be investigated next.
615
* @return the updated index of the instruction to be investigated next.
616
* It is always greater than or equal, because instructions are
617
* investigated starting at the highest index.
619
private int markDependencies(int index,
622
if (isNecessary[index] &&
623
!codeAttrInfoEditor.isModified(index))
625
if (DEBUG_ANALYSIS) System.out.print(index);
627
// Mark all instructions whose variable values are used.
628
nextIndex = markDependencies(varTraceValues[index], nextIndex);
630
// Mark all instructions whose stack values are used.
631
nextIndex = markDependencies(stackTraceValues[index], nextIndex);
633
if (DEBUG_ANALYSIS) System.out.print(",");
641
* Marks the instructions at the given offsets.
642
* @param traceOffsetValue the offsets of the instructions to be marked.
643
* @param nextIndex the index of the instruction to be investigated
645
* @return the updated index of the instruction to be investigated next.
646
* It is always greater than or equal, because instructions are
647
* investigated starting at the highest index.
649
private int markDependencies(InstructionOffsetValue traceOffsetValue,
652
if (traceOffsetValue != null)
654
int traceOffsetCount = traceOffsetValue.instructionOffsetCount();
655
for (int traceOffsetIndex = 0; traceOffsetIndex < traceOffsetCount; traceOffsetIndex++)
657
// Has the other instruction been marked yet?
658
int traceOffset = traceOffsetValue.instructionOffset(traceOffsetIndex);
659
if (!isNecessary[traceOffset])
661
if (DEBUG_ANALYSIS) System.out.print("["+traceOffset+"]");
664
isNecessary[traceOffset] = true;
666
// Restart at this instruction if it has a higher offset.
667
if (nextIndex < traceOffset)
669
if (DEBUG_ANALYSIS) System.out.print("!");
671
nextIndex = traceOffset;
682
* Marks the branch instructions of straddling branches, if they straddle
683
* some code that has been marked.
684
* @param index the offset of the branch origin or branch target.
685
* @param branchValue the offsets of the straddling branch targets
687
* @param isPointingToTargets <code>true</code> if the above offsets are
688
* branch targets, <code>false</code> if they
689
* are branch origins.
690
* @param lowestNecessaryIndex the lowest offset of all instructions marked
692
* @param nextIndex the index of the instruction to be investigated
694
* @return the updated index of the instruction to be investigated next.
695
* It is always greater than or equal the original index, because
696
* instructions are investigated starting at the highest index.
698
private int markStraddlingBranches(int index,
699
InstructionOffsetValue branchValue,
700
boolean isPointingToTargets,
701
int lowestNecessaryIndex,
704
if (branchValue != null)
706
// Loop over all branch origins.
707
int branchCount = branchValue.instructionOffsetCount();
708
for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
710
// Is the branch straddling any necessary instructions?
711
int branch = branchValue.instructionOffset(branchIndex);
713
// Is the offset pointing to a branch origin or to a branch target?
714
nextIndex = isPointingToTargets ?
715
markStraddlingBranch(index, branch, lowestNecessaryIndex, nextIndex) :
716
markStraddlingBranch(branch, index, lowestNecessaryIndex, nextIndex);
725
* Marks the given branch instruction, if it straddles some code that has
727
* @param branchOrigin the branch origin.
728
* @param branchTarget the branch target.
729
* @param lowestNecessaryIndex the lowest offset of all instructions marked
731
* @param nextIndex the index of the instruction to be investigated
733
* @return the updated index of the instruction to be investigated next.
734
* It is always greater than or equal the original index, because
735
* instructions are investigated starting at the highest index.
737
private int markStraddlingBranch(int branchOrigin,
739
int lowestNecessaryIndex,
742
// Has the branch origin been marked yet, and is it straddling the
743
// lowest necessary instruction?
744
if (!isNecessary[branchOrigin] &&
745
isStraddlingBranch(branchOrigin, branchTarget, lowestNecessaryIndex))
747
if (DEBUG_ANALYSIS) System.out.print("["+branchOrigin+"->"+branchTarget+"]");
749
// Mark the branch origin.
750
isNecessary[branchOrigin] = true;
752
// Restart at the branch origin if it has a higher offset.
753
if (nextIndex < branchOrigin)
755
if (DEBUG_ANALYSIS) System.out.print("!");
757
nextIndex = branchOrigin;
766
* Marks and simplifies the branch instructions of straddling branches,
767
* if they straddle some code that has been marked.
768
* @param branchOrigin the branch origin.
769
* @param branchTargets the branch targets.
770
* @param lowestNecessaryIndex the lowest offset of all instructions marked
772
* @param nextIndex the index of the instruction to be investigated
774
* @return the updated index of the instruction to be investigated next.
775
* It is always greater than or equal the original index, because
776
* instructions are investigated starting at the highest index.
778
private int markAndSimplifyStraddlingBranches(int branchOrigin,
779
InstructionOffsetValue branchTargets,
780
int lowestNecessaryIndex,
783
if (branchTargets != null &&
784
!isNecessary[branchOrigin])
786
// Loop over all branch targets.
787
int branchCount = branchTargets.instructionOffsetCount();
790
for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
792
// Is the branch straddling any necessary instructions?
793
int branchTarget = branchTargets.instructionOffset(branchIndex);
795
if (!isStraddlingBranch(branchOrigin,
797
lowestNecessaryIndex))
803
nextIndex = markAndSimplifyStraddlingBranch(branchOrigin,
804
branchTargets.instructionOffset(0),
805
lowestNecessaryIndex,
815
* Marks and simplifies the branch instructions of straddling branches,
816
* if they straddle some code that has been marked.
817
* @param branchOrigins the branch origins.
818
* @param branchTarget the branch target.
819
* @param lowestNecessaryIndex the lowest offset of all instructions marked
821
* @param nextIndex the index of the instruction to be investigated
823
* @return the updated index of the instruction to be investigated next.
824
* It is always greater than or equal the original index, because
825
* instructions are investigated starting at the highest index.
827
private int markAndSimplifyStraddlingBranches(InstructionOffsetValue branchOrigins,
829
int lowestNecessaryIndex,
832
if (branchOrigins != null)
834
// Loop over all branch origins.
835
int branchCount = branchOrigins.instructionOffsetCount();
836
for (int branchIndex = 0; branchIndex < branchCount; branchIndex++)
838
// Is the branch straddling any necessary instructions?
839
int branchOrigin = branchOrigins.instructionOffset(branchIndex);
841
nextIndex = markAndSimplifyStraddlingBranch(branchOrigin,
843
lowestNecessaryIndex,
853
* Marks and simplifies the given branch instruction, if it straddles some
854
* code that has been marked.
855
* @param branchOrigin the branch origin.
856
* @param branchTarget the branch target.
857
* @param lowestNecessaryIndex the lowest offset of all instructions marked
859
* @param nextIndex the index of the instruction to be investigated
861
* @return the updated index of the instruction to be investigated next.
862
* It is always greater than or equal the original index, because
863
* instructions are investigated starting at the highest index.
865
private int markAndSimplifyStraddlingBranch(int branchOrigin,
867
int lowestNecessaryIndex,
870
// Has the branch origin been marked yet, and is it straddling the
871
// lowest necessary instruction?
872
if (!isNecessary[branchOrigin] &&
873
isStraddlingBranch(branchOrigin, branchTarget, lowestNecessaryIndex))
875
if (DEBUG_ANALYSIS) System.out.print("["+branchOrigin+"->"+branchTarget+"]");
877
// Mark the branch origin.
878
isNecessary[branchOrigin] = true;
880
// Replace the branch instruction by a simple branch instrucion.
881
Instruction replacementInstruction =
882
new BranchInstruction(InstructionConstants.OP_GOTO_W,
883
branchTarget - branchOrigin).shrink();
885
codeAttrInfoEditor.replaceInstruction(branchOrigin,
886
replacementInstruction);
888
// Restart at the branch origin if it has a higher offset.
889
if (nextIndex < branchOrigin)
891
if (DEBUG_ANALYSIS) System.out.print("!");
893
nextIndex = branchOrigin;
902
* Returns whether the given branch straddling some code that has been marked.
903
* @param branchOrigin the branch origin.
904
* @param branchTarget the branch target.
905
* @param lowestNecessaryIndex the lowest offset of all instructions marked
908
private boolean isStraddlingBranch(int branchOrigin,
910
int lowestNecessaryIndex)
912
return branchOrigin <= lowestNecessaryIndex ^
913
branchTarget <= lowestNecessaryIndex;
918
* Inserts pop instructions where necessary, in order to make sure the
919
* stack is consistent at the given index.
920
* @param classFile the class file that is being checked.
921
* @param codeAttrInfo the code that is being checked.
922
* @param index the offset of the dependent instruction.
924
private void fixStackConsistency(ClassFile classFile,
925
CodeAttrInfo codeAttrInfo,
928
// Is the unnecessary instruction popping values (but not a dup/swap
930
Instruction popInstruction = InstructionFactory.create(codeAttrInfo.code,
932
byte popOpcode = popInstruction.opcode;
934
int popCount = popInstruction.stackPopCount(classFile);
935
if (popCount > 0) // &&
936
//popOpcode != InstructionConstants.OP_DUP &&
937
//popOpcode != InstructionConstants.OP_DUP_X1 &&
938
//popOpcode != InstructionConstants.OP_DUP_X2 &&
939
//popOpcode != InstructionConstants.OP_DUP2 &&
940
//popOpcode != InstructionConstants.OP_DUP2_X1 &&
941
//popOpcode != InstructionConstants.OP_DUP2_X2 &&
942
//popOpcode != InstructionConstants.OP_SWAP)
944
// Check the instructions on which it depends.
945
InstructionOffsetValue traceOffsetValue = stackTraceValues[index];
946
int traceOffsetCount = traceOffsetValue.instructionOffsetCount();
949
isAllNecessary(traceOffsetValue))
951
if (popOpcode == InstructionConstants.OP_POP ||
952
popOpcode == InstructionConstants.OP_POP2)
954
if (DEBUG_ANALYSIS) System.out.println(" Popping value again at "+popInstruction.toString(index)+" (pushed at all "+traceOffsetValue.instructionOffsetCount()+" offsets)");
956
// Simply mark pop and pop2 instructions.
957
isNecessary[index] = true;
961
if (DEBUG_ANALYSIS) System.out.println(" Popping value instead of "+popInstruction.toString(index)+" (pushed at all "+traceOffsetValue.instructionOffsetCount()+" offsets)");
963
// Make sure the pushed value is popped again,
964
// right before this instruction.
965
decreaseStackSize(index, popCount, true, true);
968
//else if (popCount == (popInstruction.isCategory2() ? 4 : 2) &&
969
// traceOffsetCount == 2 &&
970
// isAnyNecessary(traceOffsetValue))
972
// if (DEBUG_ANALYSIS) System.out.println(" Popping single value instead of "+popInstruction.toString(index)+" (pushed at some of "+traceOffsetValue.instructionOffsetCount()+" offsets)");
974
// // Make sure the single pushed value is popped again,
975
// // right before this instruction.
976
// decreaseStackSize(index, popCount / 2, true, true);
978
else if (isAnyNecessary(traceOffsetValue))
980
if (DEBUG_ANALYSIS) System.out.println(" Popping value somewhere before "+index+" (pushed at some of "+traceOffsetValue.instructionOffsetCount()+" offsets):");
982
// Go over all stack pushing instructions.
983
for (int traceOffsetIndex = 0; traceOffsetIndex < traceOffsetCount; traceOffsetIndex++)
985
// Has the push instruction been marked?
986
int pushInstructionOffset = traceOffsetValue.instructionOffset(traceOffsetIndex);
987
if (isNecessary[pushInstructionOffset])
989
Instruction pushInstruction = InstructionFactory.create(codeAttrInfo.code,
990
pushInstructionOffset);
992
int lastOffset = lastPopInstructionOffset(pushInstructionOffset,
994
pushInstructionOffset);
996
if (DEBUG_ANALYSIS) System.out.println(" Popping value right after "+lastOffset+", due to push at "+pushInstructionOffset);
998
// Make sure the pushed value is popped again,
999
// right after the instruction that pushes it
1000
// (or after the dup instruction that still uses it).
1001
decreaseStackSize(lastOffset,
1002
pushInstruction.stackPushCount(classFile),
1012
* Returns the last offset of the necessary instruction that depends on the
1013
* stack result of the instruction at the given index.
1014
* @param startOffset the start offset in the search.
1015
* @param endOffset the end offset in the search.
1016
* @param pushInstructionOffset the offset of the instruction that pushes
1017
* a result onto the stack.
1018
* @return the last offset of the necessary instruction that uses the
1021
private int lastPopInstructionOffset(int startOffset,
1023
int pushInstructionOffset)
1025
int lastOffset = startOffset;
165
Value returnValue = branchUnit.getTraceReturnValue();
166
if (returnValue != null)
168
System.out.println("Return value for method "+
169
ClassUtil.externalFullMethodDescription(classFile.getName(),
171
methodInfo.getName(classFile),
172
methodInfo.getDescriptor(classFile))+
173
" -> ["+returnValue.toString()+"]");
174
System.out.println();
178
// Mark special dependencies of constructors.
179
codeAttrInfo.instructionsAccept(classFile, methodInfo, this);
181
return branchUnit.getTraceReturnValue();
186
* Returns whether a block of instructions is ever used.
188
public boolean isTraced(int startOffset, int endOffset)
1027
190
for (int index = startOffset; index < endOffset; index++)
1029
if (isNecessary[index] &&
1030
stackTraceValues[index].contains(pushInstructionOffset))
1041
* Puts the required push instruction before the given index. The
1042
* instruction is marked as necessary.
1043
* @param index the offset of the instruction.
1044
* @param computationalType the computational type on the stack, for
1045
* push instructions.
1046
* @param delete specifies whether the instruction should be
1049
private void increaseStackSize(int index,
1050
int computationalType,
1053
// Mark this instruction.
1054
isNecessary[index] = true;
1056
// Create a simple push instrucion.
1057
byte replacementOpcode =
1058
computationalType == Value.TYPE_INTEGER ? InstructionConstants.OP_ICONST_0 :
1059
computationalType == Value.TYPE_LONG ? InstructionConstants.OP_LCONST_0 :
1060
computationalType == Value.TYPE_FLOAT ? InstructionConstants.OP_FCONST_0 :
1061
computationalType == Value.TYPE_DOUBLE ? InstructionConstants.OP_DCONST_0 :
1062
computationalType == Value.TYPE_REFERENCE ? InstructionConstants.OP_ACONST_NULL :
1063
InstructionConstants.OP_NOP;
1065
Instruction replacementInstruction = new SimpleInstruction(replacementOpcode);
1067
// Insert the pop or push instruction.
1068
codeAttrInfoEditor.insertBeforeInstruction(index,
1069
replacementInstruction);
1071
// Delete the original instruction if necessary.
1074
codeAttrInfoEditor.deleteInstruction(index);
1080
* Puts the required pop instruction at the given index. The
1081
* instruction is marked as necessary.
1082
* @param offset the offset of the instruction.
1083
* @param popCount the required reduction of the stack size.
1084
* @param before specifies whether the pop instruction should be inserted
1085
* before or after the present instruction.
1086
* @param delete specifies whether the instruction should be deleted.
1088
private void decreaseStackSize(int offset,
1093
boolean after = !before;
1095
// Special case: we may replace the instruction by two pop instructions.
1096
if (delete && popCount > 2)
1105
throw new IllegalArgumentException("Unsupported stack size reduction ["+popCount+"]");
1108
// Mark this instruction.
1109
isNecessary[offset] = true;
1113
// Create a simple pop instrucion.
1114
byte replacementOpcode = popCount == 1 || popCount == 3 ?
1115
InstructionConstants.OP_POP :
1116
InstructionConstants.OP_POP2;
1118
Instruction replacementInstruction = new SimpleInstruction(replacementOpcode);
1120
// Insert the pop instruction.
1121
codeAttrInfoEditor.insertBeforeInstruction(offset,
1122
replacementInstruction);
1127
// Create a simple pop instrucion.
1128
byte replacementOpcode = popCount == 1 ?
1129
InstructionConstants.OP_POP :
1130
InstructionConstants.OP_POP2;
1132
Instruction replacementInstruction = new SimpleInstruction(replacementOpcode);
1134
if (DEBUG_ANALYSIS) System.out.println(" Pop instruction after ["+offset+"]: "+replacementInstruction);
1136
// Insert the pop instruction.
1137
codeAttrInfoEditor.insertAfterInstruction(offset,
1138
replacementInstruction);
1141
// Delete the original instruction if necessary.
1144
codeAttrInfoEditor.deleteInstruction(offset);
1150
* Replaces the specified instruction by the proper dup/swap variant,
1151
* if necessary, depending on the state of the stack.
1152
* @param codeAttrInfo the code that is being checked.
1153
* @param offset the offset of the instruction.
1155
private void fixDupInstruction(CodeAttrInfo codeAttrInfo,
1158
byte replacementOpcode = 0;
1160
// Simplify the popping instruction if possible.
1161
switch (codeAttrInfo.code[offset])
1163
case InstructionConstants.OP_DUP_X1:
1164
if (!isStackEntryPresent(offset, 1))
1166
replacementOpcode = InstructionConstants.OP_DUP;
1170
case InstructionConstants.OP_DUP_X2:
1171
if (!isStackEntryPresent(offset, 1) ||
1172
!isStackEntryPresent(offset, 2))
1174
if (isStackEntryPresent(offset, 1) ||
1175
isStackEntryPresent(offset, 2))
1177
replacementOpcode = InstructionConstants.OP_DUP_X1;
1181
replacementOpcode = InstructionConstants.OP_DUP;
1186
case InstructionConstants.OP_DUP2_X1:
1187
if (!isStackEntryPresent(offset, 2))
1189
replacementOpcode = InstructionConstants.OP_DUP2;
1193
case InstructionConstants.OP_DUP2_X2:
1194
if (!isStackEntryPresent(offset, 2) ||
1195
!isStackEntryPresent(offset, 3))
1197
if (isStackEntryPresent(offset, 2) ||
1198
isStackEntryPresent(offset, 3))
1200
replacementOpcode = InstructionConstants.OP_DUP2_X1;
1204
replacementOpcode = InstructionConstants.OP_DUP2;
1209
case InstructionConstants.OP_SWAP:
1210
if (!isStackEntryPresent(offset, 0))
1212
isNecessary[offset] = false;
1217
// Actually replace the instruction with the new opcde, if any.
1218
if (replacementOpcode != 0)
1220
Instruction replacementInstruction = new SimpleInstruction(replacementOpcode);
1221
codeAttrInfoEditor.replaceInstruction(offset,
1222
replacementInstruction);
1224
if (DEBUG_ANALYSIS) System.out.println(" Replacing instruction at ["+offset+"] by "+replacementInstruction.toString());
1230
* Returns whether the given stack entry is present after execution of the
1231
* instruction at the given offset.
1233
private boolean isStackEntryPresent(int instructionOffset, int stackIndex)
1235
return isAnyNecessary(stacks[instructionOffset].getTopTraceValue(stackIndex).instructionOffsetValue());
203
* Returns whether the instruction at the given offset has ever been
204
* executed during the partial evaluation.
206
public boolean isTraced(int instructionOffset)
208
return evaluationCounts[instructionOffset] > 0;
213
* Returns the variable value at the given instruction offset and variable
216
public Value variableValue(int instructionOffset,
219
return vars[instructionOffset].load(variableIndex);
224
* Returns the instruction offsets that set the variable value at at the given
225
* instruction offset and variable index.
227
public InstructionOffsetValue variableProducerOffsets(int instructionOffset,
230
return vars[instructionOffset].getStoredTraceValue(variableIndex).instructionOffsetValue();
235
* Returns the instruction offsets that set the variable that is being
236
* used at the given instruction offset.
238
public InstructionOffsetValue varProducerOffsets(int instructionOffset)
240
return varProducerValues[instructionOffset];
245
* Returns the stack value at the given instruction offset and stack index.
247
public Value stackTopValue(int instructionOffset,
250
return stacks[instructionOffset].getTop(stackIndex);
255
* Returns the instruction offsets that set the stack value at at the given
256
* instruction offset and stack index.
258
public InstructionOffsetValue stackTopProducerOffsets(int instructionOffset,
261
return stacks[instructionOffset].getTopProducerValue(stackIndex).instructionOffsetValue();
266
* Returns the instruction offsets that set the stack entries that are being
267
* used at the given instruction offset.
269
public InstructionOffsetValue stackProducerOffsets(int instructionOffset)
271
return stackProducerValues[instructionOffset];
276
* Returns the instruction offsets that use the stack value at at the given
277
* instruction offset and stack index.
279
public InstructionOffsetValue stackTopConsumerOffsets(int instructionOffset,
282
return stacks[instructionOffset].getTopConsumerValue(stackIndex).instructionOffsetValue();
287
* Returns the instruction offsets that set stack entries that are not being
288
* used at the given instruction offset (e.g. because the parameters are not
291
public InstructionOffsetValue unusedProducerOffsets(int instructionOffset)
293
return unusedProducerValues[instructionOffset];
298
* Returns the instruction offsets that branch to the given instruction
301
public InstructionOffsetValue branchOrigins(int instructionOffset)
303
return branchOriginValues[instructionOffset];
308
* Returns the instruction offsets to which the given instruction offset
311
public InstructionOffsetValue branchTargets(int instructionOffset)
313
return branchTargetValues[instructionOffset];
318
* Returns the variable that is initialized at the given instruction offset,
319
* or NONE if no variable was initialized.
321
public int initializedVariable(int instructionOffset)
323
return initializedVariables[instructionOffset];
1582
// Implementations for InstructionVisitor.
1584
public void visitSimpleInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, SimpleInstruction simpleInstruction)
1586
if (isTraced(offset))
1588
switch (simpleInstruction.opcode)
1590
case InstructionConstants.OP_IALOAD:
1591
case InstructionConstants.OP_BALOAD:
1592
case InstructionConstants.OP_CALOAD:
1593
case InstructionConstants.OP_SALOAD:
1594
case InstructionConstants.OP_IADD:
1595
case InstructionConstants.OP_ISUB:
1596
case InstructionConstants.OP_IMUL:
1597
case InstructionConstants.OP_IDIV:
1598
case InstructionConstants.OP_IREM:
1599
case InstructionConstants.OP_INEG:
1600
case InstructionConstants.OP_ISHL:
1601
case InstructionConstants.OP_ISHR:
1602
case InstructionConstants.OP_IUSHR:
1603
case InstructionConstants.OP_IAND:
1604
case InstructionConstants.OP_IOR:
1605
case InstructionConstants.OP_IXOR:
1606
case InstructionConstants.OP_L2I:
1607
case InstructionConstants.OP_F2I:
1608
case InstructionConstants.OP_D2I:
1609
case InstructionConstants.OP_I2B:
1610
case InstructionConstants.OP_I2C:
1611
case InstructionConstants.OP_I2S:
1612
replaceIntegerPushInstruction(offset, simpleInstruction);
1615
case InstructionConstants.OP_LALOAD:
1616
case InstructionConstants.OP_LADD:
1617
case InstructionConstants.OP_LSUB:
1618
case InstructionConstants.OP_LMUL:
1619
case InstructionConstants.OP_LDIV:
1620
case InstructionConstants.OP_LREM:
1621
case InstructionConstants.OP_LNEG:
1622
case InstructionConstants.OP_LSHL:
1623
case InstructionConstants.OP_LSHR:
1624
case InstructionConstants.OP_LUSHR:
1625
case InstructionConstants.OP_LAND:
1626
case InstructionConstants.OP_LOR:
1627
case InstructionConstants.OP_LXOR:
1628
case InstructionConstants.OP_I2L:
1629
case InstructionConstants.OP_F2L:
1630
case InstructionConstants.OP_D2L:
1631
replaceLongPushInstruction(offset, simpleInstruction);
1634
case InstructionConstants.OP_FALOAD:
1635
case InstructionConstants.OP_FADD:
1636
case InstructionConstants.OP_FSUB:
1637
case InstructionConstants.OP_FMUL:
1638
case InstructionConstants.OP_FDIV:
1639
case InstructionConstants.OP_FREM:
1640
case InstructionConstants.OP_FNEG:
1641
case InstructionConstants.OP_I2F:
1642
case InstructionConstants.OP_L2F:
1643
case InstructionConstants.OP_D2F:
1644
replaceFloatPushInstruction(offset, simpleInstruction);
1647
case InstructionConstants.OP_DALOAD:
1648
case InstructionConstants.OP_DADD:
1649
case InstructionConstants.OP_DSUB:
1650
case InstructionConstants.OP_DMUL:
1651
case InstructionConstants.OP_DDIV:
1652
case InstructionConstants.OP_DREM:
1653
case InstructionConstants.OP_DNEG:
1654
case InstructionConstants.OP_I2D:
1655
case InstructionConstants.OP_L2D:
1656
case InstructionConstants.OP_F2D:
1657
replaceDoublePushInstruction(offset, simpleInstruction);
1660
case InstructionConstants.OP_AALOAD:
1661
replaceReferencePushInstruction(offset, simpleInstruction);
1668
public void visitVariableInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, VariableInstruction variableInstruction)
1670
if (isTraced(offset))
1672
switch (variableInstruction.opcode)
1674
case InstructionConstants.OP_ILOAD:
1675
case InstructionConstants.OP_ILOAD_0:
1676
case InstructionConstants.OP_ILOAD_1:
1677
case InstructionConstants.OP_ILOAD_2:
1678
case InstructionConstants.OP_ILOAD_3:
1679
replaceIntegerPushInstruction(offset, variableInstruction);
1682
case InstructionConstants.OP_LLOAD:
1683
case InstructionConstants.OP_LLOAD_0:
1684
case InstructionConstants.OP_LLOAD_1:
1685
case InstructionConstants.OP_LLOAD_2:
1686
case InstructionConstants.OP_LLOAD_3:
1687
replaceLongPushInstruction(offset, variableInstruction);
1690
case InstructionConstants.OP_FLOAD:
1691
case InstructionConstants.OP_FLOAD_0:
1692
case InstructionConstants.OP_FLOAD_1:
1693
case InstructionConstants.OP_FLOAD_2:
1694
case InstructionConstants.OP_FLOAD_3:
1695
replaceFloatPushInstruction(offset, variableInstruction);
1698
case InstructionConstants.OP_DLOAD:
1699
case InstructionConstants.OP_DLOAD_0:
1700
case InstructionConstants.OP_DLOAD_1:
1701
case InstructionConstants.OP_DLOAD_2:
1702
case InstructionConstants.OP_DLOAD_3:
1703
replaceDoublePushInstruction(offset, variableInstruction);
1706
case InstructionConstants.OP_ALOAD:
1707
case InstructionConstants.OP_ALOAD_0:
1708
case InstructionConstants.OP_ALOAD_1:
1709
case InstructionConstants.OP_ALOAD_2:
1710
case InstructionConstants.OP_ALOAD_3:
1711
replaceReferencePushInstruction(offset, variableInstruction);
1719
public void visitCpInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, CpInstruction cpInstruction)
1721
// Make sure 'new' instructions (or subsequent 'dup' instructions)
1722
// depend on the subsequent initializer calls, in case these calls
1723
// are marked as not having any side effects.
1724
if (isTraced(offset) &&
1725
cpInstruction.opcode == InstructionConstants.OP_INVOKESPECIAL)
1727
// Check if the invoked method is an initalizer.
1728
classFile.constantPoolEntryAccept(cpInstruction.cpIndex, this);
1732
// Find the previous instruction (assuming there was no branch).
1733
int previousOffset = offset - 1;
1734
while (!isTraced(previousOffset))
1739
// Compute the stack index of the uninitialized object.
1740
int stackIndex = stacks[offset].size();
1742
// Get the (first and presumably only) offset of the instruction
1743
// that put it there. This is typically a dup instruction.
1744
int newOffset = stacks[previousOffset].getBottomTraceValue(stackIndex).instructionOffsetValue().instructionOffset(0);
1746
// Add a reverse dependency. The source instruction depends on
1747
// the initializer instruction, thus making sure that the latter
1748
// is preserved whenever the former is used.
1749
stackTraceValues[newOffset] = stackTraceValues[newOffset].generalize(InstructionOffsetValueFactory.create(offset)).instructionOffsetValue();
1755
public void visitBranchInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, BranchInstruction branchInstruction)
1757
replaceBranchInstruction(offset, branchInstruction);
1761
public void visitTableSwitchInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, TableSwitchInstruction tableSwitchInstruction)
1763
replaceBranchInstruction(offset, tableSwitchInstruction);
1767
public void visitLookUpSwitchInstruction(ClassFile classFile, MethodInfo methodInfo, CodeAttrInfo codeAttrInfo, int offset, LookUpSwitchInstruction lookUpSwitchInstruction)
1769
replaceBranchInstruction(offset, lookUpSwitchInstruction);
1773
// Small utility methods.
1776
* Replaces the given integer instruction by a simpler push instruction,
1779
private void replaceIntegerPushInstruction(int offset, Instruction instruction)
1781
Stack stack = stacks[offset];
1782
Value pushedValue = stack.getTop(0);
1783
if (pushedValue.isSpecific())
1785
int value = pushedValue.integerValue().value();
1786
if (value << 16 >> 16 == value)
1788
replacePushInstruction(offset,
1789
InstructionConstants.OP_SIPUSH,
1797
* Replaces the given long instruction by a simpler push instruction,
1800
private void replaceLongPushInstruction(int offset, Instruction instruction)
1802
Stack stack = stacks[offset];
1803
Value pushedValue = stack.getTop(0);
1804
if (pushedValue.isSpecific())
1806
long value = pushedValue.longValue().value();
1810
replacePushInstruction(offset,
1811
(byte)(InstructionConstants.OP_LCONST_0 + value),
1819
* Replaces the given float instruction by a simpler push instruction,
1822
private void replaceFloatPushInstruction(int offset, Instruction instruction)
1824
Stack stack = stacks[offset];
1825
Value pushedValue = stack.getTop(0);
1826
if (pushedValue.isSpecific())
1828
float value = pushedValue.floatValue().value();
1833
replacePushInstruction(offset,
1834
(byte)(InstructionConstants.OP_FCONST_0 + value),
1842
* Replaces the given double instruction by a simpler push instruction,
1845
private void replaceDoublePushInstruction(int offset, Instruction instruction)
1847
Stack stack = stacks[offset];
1848
Value pushedValue = stack.getTop(0);
1849
if (pushedValue.isSpecific())
1851
double value = pushedValue.doubleValue().value();
1855
replacePushInstruction(offset,
1856
(byte)(InstructionConstants.OP_DCONST_0 + value),
1864
* Replaces the given reference instruction by a simpler push instruction,
1867
private void replaceReferencePushInstruction(int offset, Instruction instruction)
1869
Stack stack = stacks[offset];
1870
Value pushedValue = stack.getTop(0);
1871
if (pushedValue.isSpecific())
1873
ReferenceValue value = pushedValue.referenceValue();
1874
if (value.isNull() == Value.ALWAYS)
1876
replacePushInstruction(offset,
1877
InstructionConstants.OP_ACONST_NULL,
1885
* Replaces the instruction at a given offset by a given push instruction.
1887
private void replacePushInstruction(int offset, byte opcode, int value)
1889
// Remember the replacement instruction.
1890
Instruction replacementInstruction =
1891
new SimpleInstruction(opcode, value).shrink();
1893
if (DEBUG_ANALYSIS) System.out.println(" Replacing instruction at ["+offset+"] by "+replacementInstruction.toString());
1895
codeAttrInfoEditor.replaceInstruction(offset, replacementInstruction);
1900
* Deletes the given branch instruction, or replaces it by a simpler branch
1901
* instruction, if possible.
1903
private void replaceBranchInstruction(int offset, Instruction instruction)
1905
if (isTraced(offset))
1907
InstructionOffsetValue branchTargetValue = branchTargetValues[offset];
1909
// Is there exactly one branch target (not from a goto or jsr)?
1910
if (branchTargetValue != null &&
1911
branchTargetValue.instructionOffsetCount() == 1 &&
1912
instruction.opcode != InstructionConstants.OP_GOTO &&
1913
instruction.opcode != InstructionConstants.OP_GOTO_W &&
1914
instruction.opcode != InstructionConstants.OP_JSR &&
1915
instruction.opcode != InstructionConstants.OP_JSR_W)
1917
// Is it branching to the next instruction?
1918
int branchOffset = branchTargetValue.instructionOffset(0) - offset;
1919
if (branchOffset == instruction.length(offset))
1921
if (DEBUG_ANALYSIS) System.out.println(" Deleting zero branch instruction at ["+offset+"]");
1923
// Delete the branch instruction.
1924
codeAttrInfoEditor.deleteInstruction(offset);
1928
// Replace the branch instruction by a simple branch instrucion.
1929
Instruction replacementInstruction =
1930
new BranchInstruction(InstructionConstants.OP_GOTO_W,
1931
branchOffset).shrink();
1933
if (DEBUG_ANALYSIS) System.out.println(" Replacing branch instruction at ["+offset+"] by "+replacementInstruction.toString());
1935
codeAttrInfoEditor.replaceInstruction2(offset,
1936
replacementInstruction);
1943
// Implementations for CpInfoVisitor.
1945
public void visitIntegerCpInfo(ClassFile classFile, IntegerCpInfo integerCpInfo) {}
1946
public void visitLongCpInfo(ClassFile classFile, LongCpInfo longCpInfo) {}
1947
public void visitFloatCpInfo(ClassFile classFile, FloatCpInfo floatCpInfo) {}
1948
public void visitDoubleCpInfo(ClassFile classFile, DoubleCpInfo doubleCpInfo) {}
1949
public void visitStringCpInfo(ClassFile classFile, StringCpInfo stringCpInfo) {}
1950
public void visitUtf8CpInfo(ClassFile classFile, Utf8CpInfo utf8CpInfo) {}
1951
public void visitFieldrefCpInfo(ClassFile classFile, FieldrefCpInfo fieldrefCpInfo) {}
1952
public void visitInterfaceMethodrefCpInfo(ClassFile classFile, InterfaceMethodrefCpInfo interfaceMethodrefCpInfo) {}
1953
public void visitClassCpInfo(ClassFile classFile, ClassCpInfo classCpInfo) {}
1954
public void visitNameAndTypeCpInfo(ClassFile classFile, NameAndTypeCpInfo nameAndTypeCpInfo) {}
1957
public void visitMethodrefCpInfo(ClassFile classFile, MethodrefCpInfo methodrefCpInfo)
1959
isInitializer = methodrefCpInfo.getName(classFile).equals(ClassConstants.INTERNAL_METHOD_NAME_INIT);
1963
// Small utility methods.
1966
* Returns whether any of the instructions at the given offsets are marked as
1969
private boolean isAnyNecessary(InstructionOffsetValue traceValue)
1971
int traceCount = traceValue.instructionOffsetCount();
1972
if (traceCount == 0)
1977
for (int traceIndex = 0; traceIndex < traceCount; traceIndex++)
1979
if (isNecessary[traceValue.instructionOffset(traceIndex)])
1990
* Returns whether all of the instructions at the given offsets are marked as
1993
private boolean isAllNecessary(InstructionOffsetValue traceValue)
1995
int traceCount = traceValue.instructionOffsetCount();
1996
for (int traceIndex = 0; traceIndex < traceCount; traceIndex++)
1998
if (!isNecessary[traceValue.instructionOffset(traceIndex)])
2009
* Returns whether the instruction at the given offset has ever been
2010
* executed during the partial evaluation.
2012
private boolean isTraced(int instructionOffset)
2014
return evaluationCounts[instructionOffset] > 0;
697
// Small utility methods.
700
* Initializes the data structures for the variables, stack, etc.
702
private void initializeVariables(CodeAttrInfo codeAttrInfo,
703
Variables parameters)
705
int codeLength = codeAttrInfo.u4codeLength;
709
System.out.println(" Max locals = "+codeAttrInfo.u2maxLocals);
710
System.out.println(" Max stack = "+codeAttrInfo.u2maxStack);
713
// Create new arrays for storing information at each instruction offset.
714
if (vars.length < codeLength)
716
varProducerValues = new InstructionOffsetValue[codeLength];
717
stackProducerValues = new InstructionOffsetValue[codeLength];
718
unusedProducerValues = new InstructionOffsetValue[codeLength];
719
branchOriginValues = new InstructionOffsetValue[codeLength];
720
branchTargetValues = new InstructionOffsetValue[codeLength];
721
vars = new TracedVariables[codeLength];
722
stacks = new TracedStack[codeLength];
723
evaluationCounts = new int[codeLength];
724
initializedVariables = new int[codeLength];
726
for (int index = 0; index < codeLength; index++)
728
initializedVariables[index] = NONE;
733
for (int index = 0; index < codeLength; index++)
735
varProducerValues[index] = null;
736
stackProducerValues[index] = null;
737
unusedProducerValues[index] = null;
738
branchOriginValues[index] = null;
739
branchTargetValues[index] = null;
740
evaluationCounts[index] = 0;
741
initializedVariables[index] = NONE;
743
if (vars[index] != null)
745
vars[index].reset(codeAttrInfo.u2maxLocals);
748
if (stacks[index] != null)
750
stacks[index].reset(codeAttrInfo.u2maxStack);
755
// Reuse the existing variables and stack objects, ensuring the right size.
756
variables.reset(codeAttrInfo.u2maxLocals);
757
stack.reset(codeAttrInfo.u2maxStack);
759
// Initialize the variables with the parameters.
760
variables.initialize(parameters);
762
// Set the store value of each parameter variable.
763
InstructionOffsetValue atMethodEntry = InstructionOffsetValueFactory.create(PartialEvaluator.AT_METHOD_ENTRY);
765
for (int index = 0; index < parameters.size(); index++)
767
variables.setStoredTraceValue(index, atMethodEntry);
770
// Reset the return value.
771
branchUnit.setTraceReturnValue(null);
776
* Generalize the local variable frames of a block of instructions.
778
private void generalizeVariables(int startOffset, int endOffset, TracedVariables generalizedVariables)
780
for (int index = startOffset; index < endOffset; index++)
784
// We can't use the return value, because local generalization
785
// can be different a couple of times, with the global
786
// generalization being the same.
787
generalizedVariables.generalize(vars[index]);