View Javadoc

1   /*
2    * Created on Dec 4, 2003
3    *
4    * To change the template for this generated file go to
5    * Window>Preferences>Java>Code Generation>Code and Comments
6    */
7   package joeq.Compiler.Analysis.IPSSA.Utils;
8   
9   import java.util.HashSet;
10  import java.util.Iterator;
11  import java.util.Set;
12  import java.io.PrintStream;
13  import joeq.Compiler.Analysis.IPSSA.SSADefinition;
14  import joeq.Compiler.Analysis.IPSSA.SSAIterator;
15  import joeq.Compiler.Analysis.IPSSA.SSAValue;
16  import jwutil.collections.Pair;
17  import jwutil.util.Assert;
18  
19  /***
20   * @author V.Benjamin Livshits
21   * @version $Id: SSAGraphPrinter.java 1931 2004-09-22 22:17:47Z joewhaley $
22   *
23   * This class provides utilities for printing a SSA connectivity graph.
24   */
25  public class SSAGraphPrinter {
26      private static void collectReachedDefinitions(SSADefinition def, DefinitionSet defs) {
27          if(defs.contains(def)) {
28              // already seen def
29              return;
30          }
31          
32          defs.add(def);
33          for(Iterator useIter = def.getUseIterator(); useIter.hasNext();) {
34              SSAValue value = (SSAValue) useIter.next();
35              
36              SSADefinition lhsDef = value.getDestination();
37              Assert._assert(lhsDef != null);
38              // recurse on lhsDef
39              collectReachedDefinitions(lhsDef, defs);
40          }
41      }
42      
43      private static void printDefinitions(DefinitionSet defs, PrintStream out) {
44          printDefinitions(defs.getDefinitionIterator(), out);
45      }
46      
47      private static void printDefinitions(SSAIterator.DefinitionIterator iter, PrintStream out, boolean skipIsolated) {
48          // 2) Dump them as nodes
49          Set edges = new HashSet();
50          out.println("digraph G {\n");
51          while(iter.hasNext()) {
52              SSADefinition currentDef = iter.nextDefinition();
53              Assert._assert(currentDef != null);
54              if(!skipIsolated) {
55                  // always declare the nodes to get them printed
56                  out.println("\t\""+currentDef + "\" [shape=box];");
57              }
58              
59              SSAIterator.ValueIterator useIter = currentDef.getUseIterator();
60              if(!currentDef.getUseIterator().hasNext()) {
61                  //System.err.println("Definition " + currentDef + " has no uses");
62                  continue;
63              }else {
64                  //System.err.println("Definition " + currentDef + " has uses");
65              }
66                          
67              do {
68                  SSAValue value = useIter.nextValue();            
69                  SSADefinition lhsDef = value.getDestination();
70                  Assert._assert(lhsDef != null, "Destination of " + value + " is null");
71                  // add edge def -> lhsDef
72                  if(currentDef.getID() < lhsDef.getID()) {
73                      edges.add(new Pair(currentDef, lhsDef));
74                  }else {
75                      edges.add(new Pair(lhsDef, currentDef));
76                  }
77              } while(useIter.hasNext());            
78          }
79          out.println("\n");
80                  
81          // 3) Dump the edges
82          for(Iterator edgeIter = edges.iterator(); edgeIter.hasNext();) {
83              Pair pair = (Pair) edgeIter.next();
84              SSADefinition currentDef = (SSADefinition) pair.left;
85              SSADefinition lhsDef     = (SSADefinition) pair.right;
86                      
87              Assert._assert(currentDef != null && lhsDef != null);
88              // add edge def -> lhsDef
89              out.println("\t\"" + currentDef + "\" -> \"" + lhsDef + "\" \n" ); 
90          }
91          out.println("}\n");        
92      }
93      private static void printDefinitions(SSAIterator.DefinitionIterator iter, PrintStream out) {
94          printDefinitions(iter, out, true);
95      }
96  
97      public static void printToDot(DefinitionSet defs, PrintStream out) {
98          DefinitionSet reachedDefs = new DefinitionSet();
99          for(SSAIterator.DefinitionIterator iter = defs.getDefinitionIterator(); iter.hasNext(); ) {
100             SSADefinition def = iter.nextDefinition();
101         
102             collectReachedDefinitions(def, reachedDefs);    
103         }
104         
105         printDefinitions(reachedDefs, out);
106     }
107     
108     /***
109      * Print everything reachable from definition def.
110      * */
111     public static void printToDot(SSADefinition def, PrintStream out) {
112         // 1) Collect all reached definitions by doing a DFS on the graph
113         DefinitionSet defs = new DefinitionSet();
114         collectReachedDefinitions(def, defs);
115         
116         printDefinitions(defs, out);
117     }
118     
119     /***
120      * Print the complete graph on all definitions.
121      * */
122     public static void printAllToDot(PrintStream out) {
123         printDefinitions(SSADefinition.Helper.getAllDefinitionIterator(), out);
124     }
125 }