|
1
19
20 package edu.umd.cs.findbugs.ba.vna;
21
22 import java.util.ArrayList  ;
23 import java.util.Arrays ;
24 import java.util.Collection ;
25 import java.util.Collections ;
26 import java.util.HashMap ;
27 import java.util.HashSet ;
28 import java.util.Iterator ;
29 import java.util.Map ;
30
31 import edu.umd.cs.findbugs.annotations.CheckForNull;
32 import edu.umd.cs.findbugs.annotations.NonNull;
33 import edu.umd.cs.findbugs.ba.Frame;
34 import edu.umd.cs.findbugs.ba.XField;
35 import edu.umd.cs.findbugs.util.Strings;
36
37
45 public class ValueNumberFrame extends Frame<ValueNumber> implements ValueNumberAnalysisFeatures {
46
47 private ArrayList <ValueNumber> mergedValueList;
48 private Map <AvailableLoad, ValueNumber[]> availableLoadMap;
49 private Map <AvailableLoad,ValueNumber> mergedLoads ;
50 private Map <ValueNumber, AvailableLoad> previouslyKnownAs;
51 public boolean phiNodeForLoads;
52
53 public ValueNumberFrame(int numLocals) {
54 super(numLocals);
55 if (REDUNDANT_LOAD_ELIMINATION) {
56 setAvailableLoadMap(Collections.EMPTY_MAP);
57 setMergedLoads(Collections.EMPTY_MAP);
58 setPreviouslyKnownAs(Collections.EMPTY_MAP);
59 }
60 }
61
62 public String availableLoadMapAsString() {
63 StringBuffer buf = new StringBuffer ("{ ");
64 for(Map.Entry <AvailableLoad, ValueNumber[]> e : getAvailableLoadMap().entrySet()) {
65 buf.append(e.getKey());
66 buf.append("=");
67 for(ValueNumber v : e.getValue())
68 buf.append(v).append(",");
69 buf.append("; ");
70 }
71
72 buf.append(" }");
73 return buf.toString();
74 }
75 public @CheckForNull AvailableLoad getLoad(ValueNumber v) {
76 for(Map.Entry <AvailableLoad, ValueNumber[]> e : getAvailableLoadMap().entrySet()) {
77 if (e.getValue() != null)
78 for(ValueNumber v2 : e.getValue())
79 if (v.equals(v2)) return e.getKey();
80 }
81 return null;
82 }
83
89 public ValueNumber[] getAvailableLoad(AvailableLoad availableLoad) {
90 return getAvailableLoadMap().get(availableLoad);
91 }
92
93
99 public void addAvailableLoad(AvailableLoad availableLoad, @NonNull ValueNumber[] value) {
100 if (value == null) throw new IllegalStateException ();
101 getUpdateableAvailableLoadMap().put(availableLoad, value);
102
103 for(ValueNumber v : value) {
104 getUpdateablePreviouslyKnownAs().put(v, availableLoad);
105 if (RLE_DEBUG) {
106 System.out.println("Adding available load of " + availableLoad + " for " + v + " to " + System.identityHashCode(this));
107 }
108 }
109 }
110
111
116 public void killLoadsOfField(XField field) {
117 Iterator <AvailableLoad> i = getAvailableLoadMap().keySet().iterator();
118 while (i.hasNext()) {
119 AvailableLoad availableLoad = i.next();
120 if (availableLoad.getField().equals(field)) {
121 if (RLE_DEBUG)
122 System.out.println("KILLING Load of " + availableLoad + " in " + this);
123 i.remove();
124 }
125 }
126 }
127
128
133 public void killAllLoads() {
134 if (REDUNDANT_LOAD_ELIMINATION) {
135 for(Iterator <AvailableLoad> i = getAvailableLoadMap().keySet().iterator(); i.hasNext(); ) {
136 AvailableLoad availableLoad = i.next();
137 if (!availableLoad.getField().isFinal()) {
138 if (RLE_DEBUG)
139 System.out.println("KILLING load of " + availableLoad + " in " + this);
140 i.remove();
141 }
142 }
143 }
144 }
145
150 public void killAllLoadsOf(@CheckForNull ValueNumber v) {
151 if (REDUNDANT_LOAD_ELIMINATION) {
152 for(Iterator <AvailableLoad> i = getAvailableLoadMap().keySet().iterator(); i.hasNext(); ) {
153 AvailableLoad availableLoad = i.next();
154 if (!availableLoad.getField().isFinal() && availableLoad.getReference() == v) {
155 if (RLE_DEBUG) System.out.println("Killing load of " + availableLoad + " in " + this);
156 i.remove();
157 }
158 }
159 }
160 }
161
162 void mergeAvailableLoadSets(ValueNumberFrame other, ValueNumberFactory factory, MergeTree mergeTree) {
163 if (REDUNDANT_LOAD_ELIMINATION) {
164 String s = "";
168 if (RLE_DEBUG) {
169 s = "Merging " + this.availableLoadMapAsString() + " and " + other.availableLoadMapAsString();
170 }
171 boolean changed = false;
172 if (other.isBottom()) {
173 changed = !this.getAvailableLoadMap().isEmpty();
174 setAvailableLoadMap(Collections.EMPTY_MAP);
175 }
176 else if (!other.isTop()) {
177 for(Map.Entry <AvailableLoad,ValueNumber[]> e : getAvailableLoadMap().entrySet()) {
178 AvailableLoad load = e.getKey();
179 ValueNumber[] myVN = e.getValue();
180 ValueNumber[] otherVN = other.getAvailableLoadMap().get(load);
181 if (false && this.phiNodeForLoads && myVN != null && myVN.length == 1 && myVN[0].hasFlag(ValueNumber.PHI_NODE))
182 continue;
183 if (!Arrays.equals(myVN, otherVN)) {
184
185 ValueNumber phi = getMergedLoads().get(load);
186 if (phi == null) {
187 phi = factory.createFreshValue();
188 int flags = ValueNumber.PHI_NODE;
189
190 getUpdateableMergedLoads().put(load, phi);
191 for(ValueNumber vn : myVN) {
192 mergeTree.mapInputToOutput(vn, phi);
193 flags |= vn.getFlags();
194 }
195 if (otherVN != null) for(ValueNumber vn : otherVN) {
196 mergeTree.mapInputToOutput(vn, phi);
197 flags |= vn.getFlags();
198 }
199 phi.setFlag(flags);
200 if (RLE_DEBUG)
201 System.out.println("Creating phi node " + phi + " for " + load + " from " + Strings.toString(myVN) + " x " + Strings.toString(otherVN) + " in " + System.identityHashCode(this));
202 changed = true;
203 e.setValue(new ValueNumber[] { phi });
204 } else {
205 if (RLE_DEBUG)
206 System.out.println("Reusing phi node : " + phi + " for " + load + " from "+ Strings.toString(myVN) + " x " + Strings.toString(otherVN)+ " in " + System.identityHashCode(this));
207 if (myVN.length != 0 || !myVN[0].equals(phi))
208 e.setValue(new ValueNumber[] { phi });
209 }
210
211 }
212
213 }
214 }
215 Map <ValueNumber, AvailableLoad> previouslyKnownAsOther = other.getPreviouslyKnownAs();
216 if (previouslyKnownAsOther.size() != 0)
217 getUpdateablePreviouslyKnownAs().putAll(previouslyKnownAsOther);
218 if (changed)
219 this.phiNodeForLoads = true;
220 if (changed && RLE_DEBUG) {
221 System.out.println(s);
222 System.out.println(" Result is " + this.availableLoadMapAsString());
223 System.out.println(" Set phi for " + System.identityHashCode(this));
224 }
225 }
226 }
227
228
229 ValueNumber getMergedValue(int slot) {
230 return mergedValueList.get(slot);
231 }
232
233 void setMergedValue(int slot, ValueNumber value) {
234 mergedValueList.set(slot, value);
235 }
236
237 @Override
238 public void copyFrom(Frame<ValueNumber> other) {
239 if (mergedValueList == null && other.isValid()) {
241 mergedValueList = new ArrayList <ValueNumber>();
244 int numSlots = other.getNumSlots();
245 for (int i = 0; i < numSlots; ++i)
246 mergedValueList.add(null);
247 }
248
249 if (REDUNDANT_LOAD_ELIMINATION) {
250 Map <AvailableLoad, ValueNumber[]> availableLoadMapOther = ((ValueNumberFrame) other).getAvailableLoadMap();
252 if (availableLoadMapOther.size() == 0)
253 setAvailableLoadMap(Collections.EMPTY_MAP);
254 else {
255 getUpdateableAvailableLoadMap().clear();
256 getUpdateableAvailableLoadMap().putAll(availableLoadMapOther);
257 }
258 Map <ValueNumber, AvailableLoad> previouslyKnownAsOther = ((ValueNumberFrame) other).getPreviouslyKnownAs();
259 if (previouslyKnownAsOther.size() == 0)
260 setPreviouslyKnownAs(Collections.EMPTY_MAP);
261 else {
262 getUpdateablePreviouslyKnownAs().clear();
263 getUpdateablePreviouslyKnownAs().putAll(previouslyKnownAsOther);
264 }
265
266 }
267
268 super.copyFrom(other);
269 }
270
271 @Override
272 public String toString() {
273 String frameValues = super.toString();
274 if (RLE_DEBUG) {
275 StringBuffer buf = new StringBuffer ();
276 buf.append(frameValues);
277
278 Iterator <AvailableLoad> i = getAvailableLoadMap().keySet().iterator();
279 boolean first = true;
280 while (i.hasNext()) {
281 AvailableLoad key = i.next();
282 ValueNumber[] value = getAvailableLoadMap().get(key);
283 if (first)
284 first = false;
285 else
286 buf.append(',');
287 buf.append(key + "=" + valueToString(value));
288 }
289
290 buf.append(" #");
291 buf.append(System.identityHashCode(this));
292 if (phiNodeForLoads) buf.append(" phi");
293 return buf.toString();
294 } else {
295 return frameValues;
296 }
297 }
298
299 private static String valueToString(ValueNumber[] valueNumberList) {
300 StringBuffer buf = new StringBuffer ();
301 buf.append('[');
302 boolean first = true;
303 for (ValueNumber aValueNumberList : valueNumberList) {
304 if (first)
305 first = false;
306 else
307 buf.append(',');
308 buf.append(aValueNumberList.getNumber());
309 }
310 buf.append(']');
311 return buf.toString();
312 }
313
314 public boolean fuzzyMatch(ValueNumber v1, ValueNumber v2) {
315 return v1.equals(v2) || fromMatchingLoads(v1, v2) || haveMatchingFlags(v1, v2);
316 }
317
318 public boolean fromMatchingLoads(ValueNumber v1, ValueNumber v2) {
319 AvailableLoad load1 = getLoad(v1);
320 if (load1 == null) load1 = getPreviouslyKnownAs().get(v1);
321 if (load1 == null) return false;
322 AvailableLoad load2 = getLoad(v2);
323 if (load2 == null) load2 = getPreviouslyKnownAs().get(v2);
324 if (load2 == null) return false;
325 return load1.equals(load2);
326 }
327
328
333 public boolean haveMatchingFlags(ValueNumber v1, ValueNumber v2) {
334 int flag1 = v1.getFlags();
335 int flag2 = v2.getFlags();
336 return (flag1 & flag2) != 0;
337 }
338
339 public Collection <ValueNumber> valueNumbersForLoads() {
340 HashSet <ValueNumber> result = new HashSet <ValueNumber>();
341 if (REDUNDANT_LOAD_ELIMINATION)
342 for(Map.Entry <AvailableLoad, ValueNumber[]> e : getAvailableLoadMap().entrySet()) {
343 if (e.getValue() != null)
344 for(ValueNumber v2 : e.getValue())
345 result.add(v2);
346 }
347
348 return result;
349 }
350
351
354 private void setAvailableLoadMap(Map <AvailableLoad, ValueNumber[]> availableLoadMap) {
355 this.availableLoadMap = availableLoadMap;
356 }
357
358
361 private Map <AvailableLoad, ValueNumber[]> getAvailableLoadMap() {
362 return availableLoadMap;
363 }
364 private Map <AvailableLoad, ValueNumber[]> getUpdateableAvailableLoadMap() {
365 if (!(availableLoadMap instanceof HashMap ))
366 availableLoadMap = new HashMap <AvailableLoad, ValueNumber[]>();
367 return availableLoadMap;
368 }
369
372 private void setMergedLoads(Map <AvailableLoad,ValueNumber> mergedLoads) {
373 this.mergedLoads = mergedLoads;
374 }
375
376
379 private Map <AvailableLoad,ValueNumber> getMergedLoads() {
380 return mergedLoads;
381 }
382 private Map <AvailableLoad,ValueNumber> getUpdateableMergedLoads() {
383 if (!(mergedLoads instanceof HashMap ))
384 mergedLoads = new HashMap <AvailableLoad, ValueNumber>();
385
386 return mergedLoads;
387 }
388
389
392 private void setPreviouslyKnownAs(Map <ValueNumber, AvailableLoad> previouslyKnownAs) {
393 this.previouslyKnownAs = previouslyKnownAs;
394 }
395
396
399 private Map <ValueNumber, AvailableLoad> getPreviouslyKnownAs() {
400 return previouslyKnownAs;
401 }
402 private Map <ValueNumber, AvailableLoad> getUpdateablePreviouslyKnownAs() {
403 if (!(previouslyKnownAs instanceof HashMap ))
404 previouslyKnownAs = new HashMap <ValueNumber, AvailableLoad>();
405
406
407 return previouslyKnownAs;
408 }
409
410
411 }
412
413 |
Popular Tags |
Java API By Example, From Geeks To Geeks.