|
1
19
20 package edu.umd.cs.findbugs.ba.vna;
21
22 import java.util.BitSet  ;
23 import java.util.HashMap ;
24 import java.util.IdentityHashMap ;
25 import java.util.Iterator ;
26
27 import org.apache.bcel.classfile.Method;
28 import org.apache.bcel.generic.InstructionHandle;
29 import org.apache.bcel.generic.MethodGen;
30
31 import edu.umd.cs.findbugs.SystemProperties;
32 import edu.umd.cs.findbugs.ba.BasicBlock;
33 import edu.umd.cs.findbugs.ba.CFGBuilderException;
34 import edu.umd.cs.findbugs.ba.ClassContext;
35 import edu.umd.cs.findbugs.ba.Dataflow;
36 import edu.umd.cs.findbugs.ba.DataflowAnalysisException;
37 import edu.umd.cs.findbugs.ba.DataflowTestDriver;
38 import edu.umd.cs.findbugs.ba.DepthFirstSearch;
39 import edu.umd.cs.findbugs.ba.Edge;
40 import edu.umd.cs.findbugs.ba.Frame;
41 import edu.umd.cs.findbugs.ba.FrameDataflowAnalysis;
42 import edu.umd.cs.findbugs.ba.Location;
43 import edu.umd.cs.findbugs.ba.RepositoryLookupFailureCallback;
44
45
56 public class ValueNumberAnalysis extends FrameDataflowAnalysis<ValueNumber, ValueNumberFrame> {
57
58 public static final boolean DEBUG = SystemProperties.getBoolean("vna.debug");
59
60 private MethodGen methodGen;
61 private ValueNumberFactory factory;
62 private ValueNumberFrameModelingVisitor visitor;
63 private ValueNumber[] entryLocalValueList;
64 private IdentityHashMap <BasicBlock, ValueNumber> exceptionHandlerValueNumberMap;
65 private ValueNumber thisValue;
66 private HashMap <Location, ValueNumberFrame> factAtLocationMap;
67 private HashMap <Location, ValueNumberFrame> factAfterLocationMap;
68 private MergeTree mergeTree;
69
70 public ValueNumberAnalysis(MethodGen methodGen, DepthFirstSearch dfs,
71 LoadedFieldSet loadedFieldSet,
72 RepositoryLookupFailureCallback lookupFailureCallback) {
73
74 super(dfs);
75 this.methodGen = methodGen;
76 this.factory = new ValueNumberFactory();
77 ValueNumberCache cache = new ValueNumberCache();
78 this.visitor = new ValueNumberFrameModelingVisitor(methodGen, factory, cache,
79 loadedFieldSet,
80 lookupFailureCallback);
81
82 int numLocals = methodGen.getMaxLocals();
83 this.entryLocalValueList = new ValueNumber[numLocals];
84 for (int i = 0; i < numLocals; ++i)
85 this.entryLocalValueList[i] = factory.createFreshValue();
86
87 this.exceptionHandlerValueNumberMap = new IdentityHashMap <BasicBlock, ValueNumber>();
88
89 if (!methodGen.isStatic())
92 this.thisValue = entryLocalValueList[0];
93
94 this.factAtLocationMap = new HashMap <Location, ValueNumberFrame>();
95 this.factAfterLocationMap = new HashMap <Location, ValueNumberFrame>();
96 if (DEBUG) System.out.println("VNA Analysis " + methodGen.getClassName() + "." + methodGen.getName() + " : " + methodGen.getSignature());
97
98 }
99 public ValueNumber getClassObjectValue(String className) {
100 return visitor.getClassObjectValue(className);
101 }
102 public void setMergeTree(MergeTree mergeTree) {
103 this.mergeTree = mergeTree;
104 }
105
106 public MergeTree getMergeTree() {
107 return mergeTree;
108 }
109
110 public ValueNumberFactory getFactory() {
111 return factory;
112 }
113
114 public int getNumValuesAllocated() {
115 return factory.getNumValuesAllocated();
116 }
117
118 public boolean isThisValue(ValueNumber value) {
119 return thisValue != null && thisValue.getNumber() == value.getNumber();
120 }
121
122 public ValueNumber getThisValue() {
123 return thisValue;
124 }
125
126 public ValueNumber getEntryValue(int local) {
127 return entryLocalValueList[local];
128 }
129
130 public ValueNumberFrame createFact() {
131 return new ValueNumberFrame(methodGen.getMaxLocals());
132 }
133
134 public void initEntryFact(ValueNumberFrame result) {
135 result.setValid();
137
138 int numSlots = result.getNumSlots();
140 for (int i = 0; i < numSlots; ++i)
141 result.setValue(i, entryLocalValueList[i]);
142 }
143
144 @Override
145 public void transferInstruction(InstructionHandle handle, BasicBlock basicBlock, ValueNumberFrame fact)
146 throws DataflowAnalysisException {
147
148 Location location = new Location(handle, basicBlock);
149
150 ValueNumberFrame atLocation = getFactAtLocation(location);
151 copy(fact, atLocation);
152
153 visitor.setFrameAndLocation(fact, new Location(handle, basicBlock));
154 visitor.setHandle(handle);
155 visitor.analyzeInstruction(handle.getInstruction());
156
157 ValueNumberFrame afterLocation = getFactAfterLocation(location);
158 copy(fact, afterLocation);
159 }
160
161 public void meetInto(ValueNumberFrame fact, Edge edge, ValueNumberFrame result) throws DataflowAnalysisException {
162 if (edge.getTarget().isExceptionHandler() && fact.isValid()) {
163
168 BasicBlock handlerBlock = edge.getTarget();
170 ValueNumber exceptionValueNumber = getExceptionValueNumber(handlerBlock);
171
172 ValueNumberFrame tmpFact = createFact();
174 tmpFact.copyFrom(fact);
175 tmpFact.clearStack();
176 tmpFact.pushValue(exceptionValueNumber);
177 fact = tmpFact;
178 }
179
180 mergeInto(fact, result);
181 }
182
183 @Override
184 protected void mergeInto(ValueNumberFrame frame, ValueNumberFrame result) throws DataflowAnalysisException {
185 result.mergeAvailableLoadSets(frame, factory, mergeTree);
186 super.mergeInto(frame, result);
187 }
188
189 @Override
190 protected void mergeValues(ValueNumberFrame otherFrame, ValueNumberFrame resultFrame, int slot) throws DataflowAnalysisException {
191 ValueNumber value =
192 mergeValues(resultFrame, slot, resultFrame.getValue(slot), otherFrame.getValue(slot));
193 resultFrame.setValue(slot, value);
194 }
195
196 private ValueNumber mergeValues(ValueNumberFrame frame, int slot, ValueNumber mine, ValueNumber other)
197 throws DataflowAnalysisException {
198
199
210
213 if (mine != frame.getValue(slot)) throw new IllegalStateException ();
214
215 if (mine.equals(other))
216 return mine;
217
218 ValueNumber mergedValue = frame.getMergedValue(slot);
219 if (mergedValue == null) {
220 mergedValue = factory.createFreshValue();
221 mergedValue.setFlags(mine.getFlags() | other.getFlags() | ValueNumber.PHI_NODE);
222 frame.setMergedValue(slot, mergedValue);
223
224 }
225
226 if (mergeTree != null) {
227 mergeTree.mapInputToOutput(mine, mergedValue);
228 mergeTree.mapInputToOutput(other, mergedValue);
229 }
230
231 return mergedValue;
232 }
233
234 @Override
235 public ValueNumberFrame getFactAtLocation(Location location) {
236 ValueNumberFrame fact = factAtLocationMap.get(location);
237 if (fact == null) {
238 fact = createFact();
239 makeFactTop(fact);
240 factAtLocationMap.put(location, fact);
241 }
242 return fact;
243 }
244
245 @Override
246 public ValueNumberFrame getFactAfterLocation(Location location) {
247 ValueNumberFrame fact = factAfterLocationMap.get(location);
248 if (fact == null) {
249 fact = createFact();
250 makeFactTop(fact);
251 factAfterLocationMap.put(location, fact);
252 }
253 return fact;
254 }
255
256
262 public Iterator <ValueNumberFrame> factIterator() {
263 return factAtLocationMap.values().iterator();
264 }
265
266 private static class ValueCompacter {
268 public final BitSet valuesUsed;
269 public int numValuesUsed;
270 public final int[] discovered;
271
272 public ValueCompacter(int origNumValuesAllocated) {
273 valuesUsed = new BitSet ();
274 numValuesUsed = 0;
275
276 discovered = new int[origNumValuesAllocated];
281 for (int i = 0; i < discovered.length; ++i)
282 discovered[i] = -1;
283 }
284
285 public boolean isUsed(int number) {
286 return valuesUsed.get(number);
287 }
288
289 public void setUsed(int number) {
290 valuesUsed.set(number, true);
291 }
292
293 public int allocateValue() {
294 return numValuesUsed++;
295 }
296 }
297
298
311 public void compactValueNumbers(Dataflow<ValueNumberFrame, ValueNumberAnalysis> dataflow) {
312 ValueCompacter compacter = new ValueCompacter(factory.getNumValuesAllocated());
313
314 for (Iterator <ValueNumberFrame> i = factIterator(); i.hasNext();) {
317 ValueNumberFrame frame = i.next();
318 markFrameValues(frame, compacter);
319 }
320 for (Iterator <ValueNumberFrame> i = resultFactIterator(); i.hasNext();) {
321 ValueNumberFrame frame = i.next();
322 markFrameValues(frame, compacter);
323 }
324
325 int before = factory.getNumValuesAllocated();
326
327 factory.compact(compacter.discovered, compacter.numValuesUsed);
329
330 int after = factory.getNumValuesAllocated();
331
332 if (DEBUG && after < before && before > 0)
333 System.out.println("Value compaction: " + after + "/" + before + " (" +
334 ((after * 100) / before) + "%)");
335
336 }
337
338
341 private static void markFrameValues(ValueNumberFrame frame, ValueCompacter compacter) {
342 if (!frame.isValid())
344 return;
345
346 for (int j = 0; j < frame.getNumSlots(); ++j) {
347 ValueNumber value = frame.getValue(j);
348 int number = value.getNumber();
349
350 if (!compacter.isUsed(number)) {
351 compacter.discovered[number] = compacter.allocateValue();
352 compacter.setUsed(number);
353 }
354 }
355 }
356
357
360 public static void main(String [] argv) {
361 try {
362 if (argv.length != 1) {
363 System.out.println("Usage: edu.umd.cs.findbugs.ba.ValueNumberAnalysis <filename>");
364 System.exit(1);
365 }
366
367 DataflowTestDriver<ValueNumberFrame, ValueNumberAnalysis> driver =
368 new DataflowTestDriver<ValueNumberFrame, ValueNumberAnalysis>() {
369 @Override
370 public Dataflow<ValueNumberFrame, ValueNumberAnalysis> createDataflow(ClassContext classContext, Method method)
371 throws CFGBuilderException, DataflowAnalysisException {
372 return classContext.getValueNumberDataflow(method);
373 }
374 };
375
376 driver.execute(argv[0]);
377
378 } catch (Exception e) {
379 e.printStackTrace();
380 }
381 }
382
383 private ValueNumber getExceptionValueNumber(BasicBlock handlerBlock) {
384 ValueNumber valueNumber = exceptionHandlerValueNumberMap.get(handlerBlock);
385 if (valueNumber == null) {
386 valueNumber = factory.createFreshValue();
387 exceptionHandlerValueNumberMap.put(handlerBlock, valueNumber);
388 }
389 return valueNumber;
390 }
391 }
392
393 |
Popular Tags |
Java API By Example, From Geeks To Geeks.