View Javadoc

1   package joeq.Compiler.Analysis.IPSSA.Utils;
2   
3   import java.util.Collection;
4   import java.util.HashSet;
5   import java.util.Iterator;
6   import java.util.LinkedList;
7   import java.util.Set;
8   import joeq.Compiler.Analysis.IPSSA.SSADefinition;
9   import joeq.Compiler.Analysis.IPSSA.SSAIterator;
10  import joeq.Compiler.Analysis.IPSSA.SSAValue;
11  
12  /***
13   * Implements a trace of SSADefinitions.
14   * @author V.Benjamin Livshits
15   * @version $Id: ReachabilityTrace.java 1931 2004-09-22 22:17:47Z joewhaley $
16   * */
17  public class ReachabilityTrace implements Cloneable {
18      LinkedList _definitions;
19      
20      ReachabilityTrace(){
21          _definitions = new LinkedList();
22      }
23      
24      SSAIterator.DefinitionIterator getDefinitionIterator(){
25          return new SSAIterator.DefinitionIterator(_definitions.iterator());
26      }
27      
28      public Object clone() {
29          ReachabilityTrace result = new ReachabilityTrace();
30          
31          for(SSAIterator.DefinitionIterator iter = getDefinitionIterator(); iter.hasNext();) {
32              result.appendDefinition(iter.nextDefinition());
33          }
34          
35          return result;
36      }
37      
38      public static class Algorithms {    
39          public static Collection collectReachabilityTraces(SSADefinition def1, SSADefinition def2) {
40              Collection result = new LinkedList();
41  
42              // do DF rechability and fill in result
43              followTrace(new ReachabilityTrace(), def1, def2, new HashSet(), result);
44                      
45              return result;
46          }
47      }
48      
49      private static void followTrace(ReachabilityTrace trace, SSADefinition last, SSADefinition stop, Set seen, Collection result) {
50          if(last == stop) {
51              // terminate
52              result.add(trace);
53              return;
54          }
55  
56          if(seen.contains(last)) {
57              return;
58          } else {
59              seen.add(last);
60          }
61          trace.appendDefinition(last);
62          Iterator iter = last.getUseIterator();
63          if (iter.hasNext()) { 
64              do {
65                  SSADefinition succ = ((SSAValue)iter.next()).getDestination();
66                         
67                  ReachabilityTrace newTrace = (ReachabilityTrace)trace.clone();
68                  newTrace.appendDefinition(succ);
69                  System.err.println("Considering " + succ); 
70                  followTrace(newTrace, succ, stop, seen, result);
71              } while(iter.hasNext());
72          } else {
73              System.err.println("Definition " + last + " is not used");
74          }
75      }
76      
77      void appendDefinition(SSADefinition def) {
78          _definitions.addLast(def);
79      }
80      
81      int size() {return _definitions.size();}
82      
83      public String toString() {
84          StringBuffer result = new StringBuffer("[ ");
85          for(Iterator iter = _definitions.iterator(); iter.hasNext(); ) {
86              SSADefinition def = (SSADefinition)iter.next();
87              result.append(def.toString());
88              result.append(" ");
89          }
90          result.append("]");
91       
92          return result.toString();
93      }
94  }
95