001: /*
002: * FindBugs - Find Bugs in Java programs
003: * Copyright (C) 2006, University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba.deref;
021:
022: import java.util.BitSet;
023: import java.util.Collection;
024: import java.util.Collections;
025: import java.util.HashMap;
026: import java.util.HashSet;
027: import java.util.Iterator;
028: import java.util.Map;
029: import java.util.Set;
030: import java.util.TreeSet;
031:
032: import edu.umd.cs.findbugs.TigerSubstitutes;
033: import edu.umd.cs.findbugs.annotations.CheckForNull;
034: import edu.umd.cs.findbugs.ba.Location;
035: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
036: import edu.umd.cs.findbugs.ba.vna.ValueNumberFactory;
037: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
038:
039: /**
040: * A set of values unconditionally dereferenced in the future.
041: *
042: * @author David Hovemeyer
043: */
044: public class UnconditionalValueDerefSet {
045: /** Number of distinct value numbers in method */
046: private int numValueNumbersInMethod;
047:
048: /** Set of value numbers unconditionally dereferenced */
049: private BitSet valueNumbersUnconditionallyDereferenced;
050:
051: /** Map of value numbers to locations */
052: private Map<ValueNumber, Set<Location>> derefLocationSetMap;
053:
054: boolean resultsFromBackEdge = false;
055: int backEdgeUpdateCount = 0;
056: private int lastUpdateTimestamp;
057:
058: /**
059: * Constructor.
060: *
061: * @param numValueNumbersInMethod number of distinct value numbers in method
062: */
063: public UnconditionalValueDerefSet(int numValueNumbersInMethod) {
064: this .numValueNumbersInMethod = numValueNumbersInMethod;
065: this .valueNumbersUnconditionallyDereferenced = new BitSet();
066: this .derefLocationSetMap = new HashMap<ValueNumber, Set<Location>>();
067:
068: }
069:
070: /**
071: * Is this the bottom value?
072: *
073: * @return true if this is the bottom value, false otherwise
074: */
075: public boolean isBottom() {
076: return valueNumbersUnconditionallyDereferenced
077: .get(numValueNumbersInMethod);
078: }
079:
080: /**
081: * Make this dataflow fact the bottom value.
082: */
083: public void setIsBottom() {
084: clear();
085: valueNumbersUnconditionallyDereferenced
086: .set(numValueNumbersInMethod);
087: }
088:
089: /**
090: * Is this the top value?
091: *
092: * @return true if this is the top value, false otherwise
093: */
094: public boolean isTop() {
095: return valueNumbersUnconditionallyDereferenced
096: .get(numValueNumbersInMethod + 1);
097: }
098:
099: /**
100: * Make this dataflow fact the top value.
101: */
102: public void setIsTop() {
103: clear();
104: valueNumbersUnconditionallyDereferenced
105: .set(numValueNumbersInMethod + 1);
106: lastUpdateTimestamp = 0;
107: }
108:
109: /**
110: * Clear the deref set.
111: * This sets the fact so it is valid as the dataflow entry fact:
112: * no future dereferences are guaranteed.
113: */
114: void clear() {
115: valueNumbersUnconditionallyDereferenced.clear();
116: derefLocationSetMap.clear();
117: }
118:
119: /**
120: * Make this dataflow fact the same as the given one.
121: *
122: * @param source another dataflow fact
123: */
124: public void makeSameAs(UnconditionalValueDerefSet source) {
125: // Copy value numbers
126: valueNumbersUnconditionallyDereferenced.clear();
127: valueNumbersUnconditionallyDereferenced
128: .or(source.valueNumbersUnconditionallyDereferenced);
129: lastUpdateTimestamp = source.lastUpdateTimestamp;
130: // Copy dereference locations for each value number
131: derefLocationSetMap.clear();
132: if (source.derefLocationSetMap.size() > 0)
133: for (Map.Entry<ValueNumber, Set<Location>> sourceEntry : source.derefLocationSetMap
134: .entrySet()) {
135: Set<Location> derefLocationSet = new HashSet<Location>();
136: derefLocationSet.addAll(sourceEntry.getValue());
137: derefLocationSetMap.put(sourceEntry.getKey(),
138: derefLocationSet);
139: }
140: }
141:
142: /**
143: * Return whether or not this dataflow fact is identical
144: * to the one given.
145: *
146: * @param otherFact another dataflow fact
147: * @return true if the other dataflow fact is identical to this one,
148: * false otherwise
149: */
150: public boolean isSameAs(UnconditionalValueDerefSet otherFact) {
151: return valueNumbersUnconditionallyDereferenced
152: .equals(otherFact.valueNumbersUnconditionallyDereferenced)
153: && derefLocationSetMap
154: .equals(otherFact.derefLocationSetMap);
155: }
156:
157: /**
158: * Merge given dataflow fact into this one.
159: * We take the intersection of the unconditional deref value number set,
160: * and union the deref locations.
161: *
162: * @param fact another dataflow fact
163: * @param skipMe TODO
164: */
165: public void mergeWith(UnconditionalValueDerefSet fact,
166: @CheckForNull
167: ValueNumber skipMe, ValueNumberFactory valueNumberFactory) {
168: if (UnconditionalValueDerefAnalysis.DEBUG) {
169: System.out.println("merge update of # "
170: + System.identityHashCode(this ) + " from "
171: + System.identityHashCode(fact));
172: System.out.println("update " + this );
173: System.out.println("with " + fact);
174:
175: }
176: boolean resultForSkippedValue = false;
177: if (skipMe != null) {
178: resultForSkippedValue = valueNumbersUnconditionallyDereferenced
179: .get(skipMe.getNumber());
180: }
181: // Compute the intersection of the unconditionally dereferenced value sets
182: valueNumbersUnconditionallyDereferenced
183: .and(fact.valueNumbersUnconditionallyDereferenced);
184: if (skipMe != null) {
185: valueNumbersUnconditionallyDereferenced.set(skipMe
186: .getNumber(), resultForSkippedValue);
187: }
188:
189: // For each unconditionally dereferenced value...
190: for (int i = 0; i < numValueNumbersInMethod; i++) {
191: ValueNumber vn = valueNumberFactory.forNumber(i);
192: if (vn.equals(skipMe))
193: continue;
194: Set<Location> factDerefLocationSet = fact.derefLocationSetMap
195: .get(vn);
196: if (valueNumbersUnconditionallyDereferenced.get(i)) {
197: if (factDerefLocationSet != null
198: && !factDerefLocationSet.isEmpty()) {
199: // Compute the union of the dereference locations for
200: // this value number.
201: Set<Location> derefLocationSet = derefLocationSetMap
202: .get(vn);
203: if (derefLocationSet == null) {
204: derefLocationSet = new HashSet<Location>();
205: derefLocationSetMap.put(vn, derefLocationSet);
206: }
207: derefLocationSet.addAll(fact.derefLocationSetMap
208: .get(vn));
209: }
210: } else {
211: Set<Location> removed = derefLocationSetMap.remove(vn);
212: // The value number is not in the fact:
213: // remove its location set
214: if (removed != null) {
215: if (UnconditionalValueDerefAnalysis.DEBUG)
216: System.out.println("Goodbye: " + removed);
217: }
218: }
219: }
220: }
221:
222: public void unionWith(UnconditionalValueDerefSet fact,
223: ValueNumberFactory valueNumberFactory) {
224: if (UnconditionalValueDerefAnalysis.DEBUG) {
225: System.out.println("union update of # "
226: + System.identityHashCode(this ) + " from "
227: + System.identityHashCode(fact));
228: }
229: // Compute the union of the unconditionally dereferenced value sets
230: valueNumbersUnconditionallyDereferenced
231: .or(fact.valueNumbersUnconditionallyDereferenced);
232:
233: // For each unconditionally dereferenced value...
234: for (int i = 0; i < numValueNumbersInMethod; i++) {
235: ValueNumber vn = valueNumberFactory.forNumber(i);
236:
237: if (fact.valueNumbersUnconditionallyDereferenced.get(i)) {
238: // Compute the union of the dereference locations for
239: // this value number.
240: Set<Location> derefLocationSet = derefLocationSetMap
241: .get(vn);
242: if (derefLocationSet == null) {
243: derefLocationSet = new HashSet<Location>();
244: derefLocationSetMap.put(vn, derefLocationSet);
245: }
246: derefLocationSet.addAll(fact.derefLocationSetMap
247: .get(vn));
248: } else {
249: derefLocationSetMap.put(vn, new HashSet<Location>(fact
250: .getDerefLocationSet(vn)));
251: }
252: }
253: }
254:
255: /**
256: * Mark a value as being dereferenced at given Location.
257: *
258: * @param vn the value
259: * @param location the Location
260: */
261: public void addDeref(ValueNumber vn, Location location) {
262: if (UnconditionalValueDerefAnalysis.DEBUG) {
263: System.out.println("Adding dereference of " + vn + " to # "
264: + System.identityHashCode(this ) + " @ " + location);
265: }
266: valueNumbersUnconditionallyDereferenced.set(vn.getNumber());
267:
268: Set<Location> derefLocationSet = getDerefLocationSet(vn);
269: derefLocationSet.add(location);
270: }
271:
272: /**
273: * Set a value as being unconditionally dereferenced at the
274: * given set of locations.
275: *
276: * @param vn the value
277: * @param derefSet the Set of dereference Locations
278: */
279: public void setDerefSet(ValueNumber vn, Set<Location> derefSet) {
280: if (UnconditionalValueDerefAnalysis.DEBUG) {
281: System.out.println("Adding dereference of " + vn
282: + " for # " + System.identityHashCode(this )
283: + " to " + derefSet);
284: }
285: valueNumbersUnconditionallyDereferenced.set(vn.getNumber());
286:
287: Set<Location> derefLocationSet = getDerefLocationSet(vn);
288: derefLocationSet.clear();
289: derefLocationSet.addAll(derefSet);
290: }
291:
292: /**
293: * Clear the set of dereferences for given ValueNumber
294: *
295: * @param value the ValueNumber
296: */
297: public void clearDerefSet(ValueNumber value) {
298: if (UnconditionalValueDerefAnalysis.DEBUG) {
299: System.out.println("Clearing dereference of " + value
300: + " for # " + System.identityHashCode(this ));
301: }
302: valueNumbersUnconditionallyDereferenced
303: .clear(value.getNumber());
304: derefLocationSetMap.remove(value);
305: }
306:
307: /**
308: * Get the set of dereference Locations for given value number.
309: *
310: * @param vn the value number
311: * @return the set of dereference Locations
312: */
313: private Set<Location> getDerefLocationSet(ValueNumber vn) {
314: Set<Location> derefLocationSet = derefLocationSetMap.get(vn);
315: if (derefLocationSet == null) {
316: derefLocationSet = new HashSet<Location>();
317: derefLocationSetMap.put(vn, derefLocationSet);
318: }
319: return derefLocationSet;
320: }
321:
322: /**
323: * Return whether or not the given value number is unconditionally dereferenced.
324: *
325: * @param vn the value number
326: * @return true if the value is unconditionally dereferenced, false otherwise
327: */
328: public boolean isUnconditionallyDereferenced(ValueNumber vn) {
329: return valueNumbersUnconditionallyDereferenced.get(vn
330: .getNumber());
331: }
332:
333: public Set<ValueNumber> getValueNumbersThatAreUnconditionallyDereferenced() {
334: HashSet<ValueNumber> result = new HashSet<ValueNumber>();
335: for (Map.Entry<ValueNumber, Set<Location>> e : derefLocationSetMap
336: .entrySet()) {
337: if (!e.getValue().isEmpty())
338: result.add(e.getKey());
339: }
340: return result;
341: }
342:
343: public void retainOnlyTheseValueNumbers(
344: Collection<ValueNumber> valueNumbers) {
345: for (Iterator<ValueNumber> i = derefLocationSetMap.keySet()
346: .iterator(); i.hasNext();) {
347: ValueNumber v = i.next();
348: if (!valueNumbers.contains(v)) {
349: i.remove();
350: valueNumbersUnconditionallyDereferenced.clear(v
351: .getNumber());
352: }
353: }
354: }
355:
356: /**
357: * Get the set of Locations where given value is guaranteed to be dereferenced.
358: * (I.e., if non-implicit-exception control paths are followed, one of these
359: * locations will be reached).
360: *
361: * @param vn the value
362: * @return set of Locations, one of which will definitely be reached
363: * if non-implicit-exception control paths are followed
364: */
365: public Set<Location> getUnconditionalDerefLocationSet(ValueNumber vn) {
366: Set<Location> derefLocationSet = derefLocationSetMap.get(vn);
367: if (derefLocationSet == null) {
368: derefLocationSet = TigerSubstitutes.emptySet();
369: }
370: return derefLocationSet;
371: }
372:
373: /* (non-Javadoc)
374: * @see java.lang.Object#toString()
375: */
376: @Override
377: public String toString() {
378: if (isTop()) {
379: return "[TOP]";
380: }
381: if (isBottom()) {
382: return "[BOTTOM]";
383: }
384:
385: StringBuffer buf = new StringBuffer();
386: buf.append('[');
387: boolean firstVN = true;
388: for (int i = 0; i < numValueNumbersInMethod; i++) {
389: if (!(valueNumbersUnconditionallyDereferenced.get(i))) {
390: continue;
391: }
392: if (firstVN) {
393: firstVN = false;
394: } else {
395: buf.append(',');
396: }
397: buf.append('{');
398: buf.append(i);
399: if (valueNumbersUnconditionallyDereferenced.get(i))
400: buf.append(':');
401: else
402: buf.append('?');
403: TreeSet<Location> derefLocationSet = new TreeSet<Location>();
404: derefLocationSet.addAll(getDerefLocationSet(i));
405: boolean firstLoc = true;
406: for (Location location : derefLocationSet) {
407: if (firstLoc) {
408: firstLoc = false;
409: } else {
410: buf.append(',');
411: }
412: buf.append("(" + location.getBasicBlock().getLabel()
413: + ":" + location.getHandle().getPosition()
414: + ")");
415: }
416: buf.append('}');
417: }
418: buf.append(']');
419: return buf.toString();
420: }
421:
422: private Set<Location> getDerefLocationSet(int vn) {
423: for (Map.Entry<ValueNumber, Set<Location>> entry : derefLocationSetMap
424: .entrySet()) {
425: if (entry.getKey().getNumber() == vn) {
426: return Collections.unmodifiableSet(entry.getValue());
427: }
428: }
429: return new HashSet<Location>();
430: }
431:
432: /**
433: * @param location
434: * @param vnaFrame
435: */
436: public void cleanDerefSet(@CheckForNull
437: Location location, ValueNumberFrame vnaFrame) {
438:
439: Set<ValueNumber> valueNumbers = new HashSet<ValueNumber>(
440: vnaFrame.allSlots());
441:
442: valueNumbers.addAll(vnaFrame.valueNumbersForLoads());
443:
444: if (UnconditionalValueDerefAnalysis.DEBUG) {
445: for (ValueNumber v : getValueNumbersThatAreUnconditionallyDereferenced())
446: if (!valueNumbers.contains(v)) {
447: System.out.println("\nWhy is " + v
448: + " unconditionally dereferenced in #"
449: + System.identityHashCode(this ));
450: System.out.println("VN: " + vnaFrame);
451: System.out.println("UD: " + this );
452: System.out.println("Location: " + location);
453: System.out.println();
454: }
455:
456: }
457: retainOnlyTheseValueNumbers(valueNumbers);
458: }
459:
460: /**
461: * @param lastUpdateTimestamp The lastUpdateTimestamp to set.
462: */
463: public void setLastUpdateTimestamp(int lastUpdateTimestamp) {
464: this .lastUpdateTimestamp = lastUpdateTimestamp;
465: }
466:
467: /**
468: * @return Returns the lastUpdateTimestamp.
469: */
470: public int getLastUpdateTimestamp() {
471: return lastUpdateTimestamp;
472: }
473:
474: /**
475: * @return
476: */
477: public boolean isEmpty() {
478: return valueNumbersUnconditionallyDereferenced.isEmpty();
479: }
480: }
|