UnconditionalValueDerefSet


1   /*
2    * FindBugs - Find Bugs in Java programs
3    * Copyright (C) 2006, University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba.deref;
21  
22  import java.util.BitSet  ;
23  import java.util.Collections  ;
24  import java.util.HashMap  ;
25  import java.util.HashSet  ;
26  import java.util.Iterator  ;
27  import java.util.Map  ;
28  import java.util.Set  ;
29  import java.util.TreeSet  ;
30  
31  import edu.umd.cs.findbugs.annotations.CheckForNull;
32  import edu.umd.cs.findbugs.ba.Location;
33  import edu.umd.cs.findbugs.ba.vna.ValueNumber;
34  import edu.umd.cs.findbugs.ba.vna.ValueNumberFactory;
35  import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
36  
37  /**
38   * A set of values unconditionally dereferenced in the future.
39   * 
40   * @author David Hovemeyer
41   */
42  public class UnconditionalValueDerefSet {
43      /** Number of distinct value numbers in method */
44      private int numValueNumbersInMethod;
45      
46      /** Set of value numbers unconditionally dereferenced */
47      private BitSet   valueNumberSet;
48      
49      /** Map of value numbers to locations */
50      private Map  <ValueNumber, Set  <Location>> derefLocationSetMap;
51      
52      boolean resultsFromBackEdge = false;
53      int backEdgeUpdateCount = 0;
54      private int lastUpdateTimestamp;
55  
56      
57      
58      /**
59       * Constructor.
60       * 
61       * @param numValueNumbersInMethod number of distinct value numbers in method
62       */
63      public UnconditionalValueDerefSet(int numValueNumbersInMethod) {
64          this.numValueNumbersInMethod = numValueNumbersInMethod;
65          this.valueNumberSet = new BitSet  ();
66          this.derefLocationSetMap = new HashMap  <ValueNumber, Set  <Location>>();
67          
68      }
69  
70      /**
71       * Is this the bottom value?
72       * 
73       * @return true if this is the bottom value, false otherwise
74       */
75      public boolean isBottom() {
76          return valueNumberSet.get(numValueNumbersInMethod);
77      }
78      
79      /**
80       * Make this dataflow fact the bottom value.
81       */
82      public void setIsBottom() {
83          clear();
84          valueNumberSet.set(numValueNumbersInMethod);
85      }
86  
87      /**
88       * Is this the top value?
89       * 
90       * @return true if this is the top value, false otherwise
91       */
92      public boolean isTop() {
93          return valueNumberSet.get(numValueNumbersInMethod + 1);
94      }
95      
96      /**
97       * Make this dataflow fact the top value.
98       */
99      public void setIsTop() {
100         clear();
101         valueNumberSet.set(numValueNumbersInMethod + 1);
102         lastUpdateTimestamp = 0;
103     }
104 
105     /**
106      * Clear the deref set.
107      * This sets the fact so it is valid as the dataflow entry fact:
108      * no future dereferences are guaranteed.
109      */
110     void clear() {
111         valueNumberSet.clear();
112         derefLocationSetMap.clear();
113     }
114 
115     /**
116      * Make this dataflow fact the same as the given one.
117      * 
118      * @param source another dataflow fact
119      */
120     public void makeSameAs(UnconditionalValueDerefSet source) {
121         // Copy value numbers
122         valueNumberSet.clear();
123         valueNumberSet.or(source.valueNumberSet);
124         lastUpdateTimestamp = source.lastUpdateTimestamp;
125         // Copy dereference locations for each value number
126         derefLocationSetMap.clear();
127         for (Map.Entry  <ValueNumber, Set  <Location>> sourceEntry : source.derefLocationSetMap.entrySet()) {
128             Set  <Location> derefLocationSet = new HashSet  <Location>();
129             derefLocationSet.addAll(sourceEntry.getValue());
130             derefLocationSetMap.put(sourceEntry.getKey(), derefLocationSet);
131         }
132     }
133 
134     /**
135      * Return whether or not this dataflow fact is identical
136      * to the one given.
137      * 
138      * @param otherFact another dataflow fact
139      * @return true if the other dataflow fact is identical to this one,
140      *          false otherwise
141      */
142     public boolean isSameAs(UnconditionalValueDerefSet otherFact) {
143         return valueNumberSet.equals(otherFact.valueNumberSet)
144             && derefLocationSetMap.equals(otherFact.derefLocationSetMap);
145     }
146 
147     /**
148      * Merge given dataflow fact into this one.
149      * We take the intersection of the unconditional deref value number set,
150      * and union the deref locations.
151      * 
152      * @param fact another dataflow fact
153      * @param skipMe TODO
154      */
155     public void mergeWith(UnconditionalValueDerefSet fact, @CheckForNull ValueNumber skipMe, ValueNumberFactory valueNumberFactory) {
156         if (UnconditionalValueDerefAnalysis.DEBUG) {
157             System.out.println("merge update of # " + System.identityHashCode(this) + " from " + System.identityHashCode(fact));
158             System.out.println("update " + this);
159             System.out.println("with " + fact);
160         }
161         boolean resultForSkippedValue = false;
162         if (skipMe != null) {
163             resultForSkippedValue = valueNumberSet.get(skipMe.getNumber());
164         }
165         // Compute the intersection of the unconditionally dereferenced value sets
166         valueNumberSet.and(fact.valueNumberSet);
167         if (skipMe != null) {
168             valueNumberSet.set(skipMe.getNumber(), resultForSkippedValue);
169         }
170 
171         // For each unconditionally dereferenced value...
172         for (int i = 0; i < numValueNumbersInMethod; i++) {
173             ValueNumber vn = valueNumberFactory.forNumber(i);
174             if (vn.equals(skipMe)) continue;
175             if (valueNumberSet.get(i)) {
176                 // Compute the union of the dereference locations for
177                 // this value number.
178                 Set  <Location> derefLocationSet = derefLocationSetMap.get(vn);
179                 derefLocationSet.addAll(fact.derefLocationSetMap.get(vn));
180             } else {
181                 // The value number is not in the fact:
182                 // remove its location set
183                 derefLocationSetMap.remove(vn);
184             }
185         }
186     }
187     public void unionWith(UnconditionalValueDerefSet fact, ValueNumberFactory valueNumberFactory) {
188         if (UnconditionalValueDerefAnalysis.DEBUG) {
189             System.out.println("union update of # " + System.identityHashCode(this) + " from " + System.identityHashCode(fact));
190         }
191         // Compute the union of the unconditionally dereferenced value sets
192         valueNumberSet.or(fact.valueNumberSet);
193 
194         // For each unconditionally dereferenced value...
195         for (int i = 0; i < numValueNumbersInMethod; i++) {
196             ValueNumber vn = valueNumberFactory.forNumber(i);
197 
198             if (fact.valueNumberSet.get(i)) {
199                 // Compute the union of the dereference locations for
200                 // this value number.
201                 Set  <Location> derefLocationSet = derefLocationSetMap.get(vn);
202                 if (derefLocationSet == null) {
203                     derefLocationSet = new HashSet  <Location>();
204                     derefLocationSetMap.put(vn,derefLocationSet);
205                 }
206                 derefLocationSet.addAll(fact.derefLocationSetMap.get(vn));
207             } else {
208                 derefLocationSetMap.put(vn, new HashSet  <Location>(fact.getDerefLocationSet(vn)));
209             }
210         }
211     }
212 
213     /**
214      * Mark a value as being dereferenced at given Location.
215      * 
216      * @param vn       the value
217      * @param location the Location
218      */
219     public void addDeref(ValueNumber vn, Location location) {
220         if (UnconditionalValueDerefAnalysis.DEBUG) {
221             System.out.println("Adding dereference of " + vn + " to # " + System.identityHashCode(this) + " @ " + location);
222         }
223         valueNumberSet.set(vn.getNumber());
224         Set  <Location> derefLocationSet = getDerefLocationSet(vn);
225         derefLocationSet.add(location);
226     }
227     
228     /**
229      * Set a value as being unconditionally dereferenced at the
230      * given set of locations. 
231      * 
232      * @param vn       the value
233      * @param derefSet the Set of dereference Locations
234      */
235     public void setDerefSet(ValueNumber vn, Set  <Location> derefSet) {
236         if (UnconditionalValueDerefAnalysis.DEBUG) {
237             System.out.println("Adding dereference of " + vn + " for # " + System.identityHashCode(this) + " to " + derefSet);
238         }
239         valueNumberSet.set(vn.getNumber());
240         Set  <Location> derefLocationSet = getDerefLocationSet(vn);
241         derefLocationSet.clear();
242         derefLocationSet.addAll(derefSet);
243     }
244 
245     /**
246      * Clear the set of dereferences for given ValueNumber
247      * 
248      * @param value the ValueNumber
249      */
250     public void clearDerefSet(ValueNumber value) {
251         if (UnconditionalValueDerefAnalysis.DEBUG) {
252             System.out.println("Clearing dereference of " + value + " for # " + System.identityHashCode(this));
253         }
254         valueNumberSet.clear(value.getNumber());
255         derefLocationSetMap.remove(value);
256     }
257 
258     /**
259      * Get the set of dereference Locations for given value number.
260      * 
261      * @param vn the value number
262      * @return the set of dereference Locations
263      */
264     private Set  <Location> getDerefLocationSet(ValueNumber vn) {
265         Set  <Location> derefLocationSet = derefLocationSetMap.get(vn);
266         if (derefLocationSet == null) {
267             derefLocationSet  = new HashSet  <Location>();
268             derefLocationSetMap.put(vn, derefLocationSet);
269         }
270         return derefLocationSet;
271     }
272     
273     /**
274      * Return whether or not the given value number is unconditionally dereferenced.
275      * 
276      * @param vn the value number
277      * @return true if the value is unconditionally dereferenced, false otherwise
278      */
279     public boolean isUnconditionallyDereferenced(ValueNumber vn) {
280         return valueNumberSet.get(vn.getNumber());
281     }
282     
283     public Set  <ValueNumber> getValueNumbersThatAreUnconditionallyDereferenced() {
284         HashSet  <ValueNumber> result = new HashSet  <ValueNumber>();
285         for(Map.Entry  <ValueNumber, Set  <Location>> e : derefLocationSetMap.entrySet()) {
286             if (!e.getValue().isEmpty())
287                 result.add(e.getKey());
288         }
289         return result;
290     }
291     
292     public void retainOnlyTheseValueNumbers(Set  <ValueNumber> valueNumbers) {
293         for(Iterator  <ValueNumber> i = derefLocationSetMap.keySet().iterator(); i.hasNext(); ) {
294             ValueNumber v = i.next();
295             if (!valueNumbers.contains(v)) {
296                 i.remove();
297                 valueNumberSet.clear(v.getNumber());
298             }
299         }
300     }
301     /**
302      * Get the set of Locations where given value is guaranteed to be dereferenced.
303      * (I.e., if non-implicit-exception control paths are followed, one of these
304      * locations will be reached).
305      * 
306      * @param vn the value
307      * @return set of Locations, one of which will definitely be reached
308      *          if non-implicit-exception control paths are followed
309      */
310     public Set  <Location> getUnconditionalDerefLocationSet(ValueNumber vn) {
311         Set  <Location> derefLocationSet = derefLocationSetMap.get(vn);
312         if (derefLocationSet == null ) {
313             derefLocationSet = Collections.EMPTY_SET;
314         }
315         return derefLocationSet;
316     }
317     
318     /* (non-Javadoc)
319      * @see java.lang.Object#toString()
320      */
321     @Override  
322     public String   toString() {
323         if (isTop()) {
324             return "[TOP]";
325         }
326         if (isBottom()) {
327             return "[BOTTOM]";
328         }
329         
330         StringBuffer   buf = new StringBuffer  ();
331         buf.append('[');
332         boolean firstVN = true;
333         for (int i = 0; i < numValueNumbersInMethod; i++)  {
334             if (!valueNumberSet.get(i)) {
335                 continue;
336             }
337             if (firstVN) {
338                 firstVN = false;
339             } else {
340                 buf.append(',');
341             }
342             buf.append('{');
343             buf.append(i);
344             buf.append(':');
345             TreeSet  <Location> derefLocationSet = new TreeSet  <Location>();
346             derefLocationSet.addAll(getDerefLocationSet(i));
347             boolean firstLoc = true;
348             for (Location location : derefLocationSet) {
349                 if (firstLoc) {
350                     firstLoc = false;
351                 } else {
352                     buf.append(',');
353                 }
354                 buf.append(
355                         "(" +
356                                 location.getBasicBlock().getId() +
357                                 ":" +
358                                 location.getHandle().getPosition() +
359                                 ")");
360             }
361             buf.append('}');
362         }
363         buf.append(']');
364         buf.append(" # ");
365         buf.append(System.identityHashCode(this));
366         return buf.toString();
367     }
368 
369     private Set  <Location> getDerefLocationSet(int vn) {
370         for (Map.Entry  <ValueNumber, Set  <Location>> entry : derefLocationSetMap.entrySet()) {
371             if (entry.getKey().getNumber() == vn) {
372                 return Collections.unmodifiableSet(entry.getValue());
373             }
374         }
375         return new HashSet  <Location>();
376     }
377 
378     /**
379      * @param location
380      * @param vnaFrame
381      */
382     public  void cleanDerefSet(@CheckForNull Location location, ValueNumberFrame vnaFrame) {
383 
384         Set  <ValueNumber> valueNumbers = new HashSet  <ValueNumber>(vnaFrame.allSlots());
385         
386         valueNumbers.addAll(vnaFrame.valueNumbersForLoads());
387     
388         if (UnconditionalValueDerefAnalysis.DEBUG) {
389         for(ValueNumber v : getValueNumbersThatAreUnconditionallyDereferenced())
390             if (!valueNumbers.contains(v)) {
391                 System.out.println("\nWhy is " + v + " unconditionally dereferenced in #" + System.identityHashCode(this));
392                 System.out.println("VN: " + vnaFrame);
393                 System.out.println("UD: " + this);
394                 System.out.println("Location: " + location);
395                 System.out.println();
396             }
397         
398         }
399         if (false) return;
400         retainOnlyTheseValueNumbers(valueNumbers);
401     }
402 
403     /**
404      * @param lastUpdateTimestamp The lastUpdateTimestamp to set.
405      */
406     public void setLastUpdateTimestamp(int lastUpdateTimestamp) {
407         this.lastUpdateTimestamp = lastUpdateTimestamp;
408     }
409 
410     /**
411      * @return Returns the lastUpdateTimestamp.
412      */
413     public int getLastUpdateTimestamp() {
414         return lastUpdateTimestamp;
415     }
416 }
417
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags