View Javadoc

1   package joeq.Compiler.Analysis.IPA;
2   
3   import java.util.Collection;
4   import java.util.HashSet;
5   import java.util.Iterator;
6   import java.util.Set;
7   import java.io.BufferedWriter;
8   import java.io.FileWriter;
9   import java.io.IOException;
10  import java.io.PrintStream;
11  import joeq.Class.jq_Class;
12  import joeq.Class.jq_Method;
13  import joeq.Class.jq_Reference;
14  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
15  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteObjectNode;
16  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteTypeNode;
17  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
18  import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.UnknownTypeNode;
19  import joeq.Compiler.Quad.BasicBlock;
20  import joeq.Compiler.Quad.BasicBlockVisitor;
21  import joeq.Compiler.Quad.CallGraph;
22  import joeq.Compiler.Quad.CodeCache;
23  import joeq.Compiler.Quad.ControlFlowGraph;
24  import joeq.Compiler.Quad.ControlFlowGraphVisitor;
25  import joeq.Compiler.Quad.LoadedCallGraph;
26  import joeq.Compiler.Quad.Quad;
27  import joeq.Compiler.Quad.QuadVisitor;
28  import joeq.Compiler.Quad.Operator.New;
29  import joeq.Compiler.Quad.Operator.NewArray;
30  import joeq.Main.HostedVM;
31  import jwutil.collections.GenericMultiMap;
32  import jwutil.collections.MultiMap;
33  import jwutil.graphs.Graph;
34  import jwutil.graphs.Navigator;
35  import jwutil.graphs.SCCPathNumbering;
36  import jwutil.graphs.Traversals;
37  
38  /***
39   * @author jwhaley
40   */
41  public class ObjectCreationGraph extends QuadVisitor.EmptyVisitor
42      implements ControlFlowGraphVisitor, BasicBlockVisitor, Graph
43  {
44  
45      boolean TRACE = false;
46      PrintStream out = System.out;
47      boolean MERGE_SITES = !System.getProperty("os.merge", "no").equals("no");
48      
49      jq_Method currentMethod;
50      Set/*jq_Class*/ roots = new HashSet();
51      MultiMap succ = new GenericMultiMap(), pred = new GenericMultiMap();
52  
53      public Set getAllNodes() {
54          HashSet s = new HashSet();
55          s.addAll(succ.keySet());
56          s.addAll(pred.keySet());
57          return s;
58      }
59      
60      class Nav implements Navigator {
61  
62          /* (non-Javadoc)
63           * @see jwutil.graphs.Navigator#next(java.lang.Object)
64           */
65          public Collection next(Object node) {
66              return succ.getValues(node);
67          }
68  
69          /* (non-Javadoc)
70           * @see jwutil.graphs.Navigator#prev(java.lang.Object)
71           */
72          public Collection prev(Object node) {
73              return pred.getValues(node);
74          }
75          
76      }
77      
78      /* (non-Javadoc)
79       * @see jwutil.graphs.Graph#getRoots()
80       */
81      public Collection getRoots() {
82          HashSet set = new HashSet();
83          set.addAll(succ.keySet());
84          set.removeAll(succ.values());
85          set.addAll(roots);
86          
87          for (;;) {
88              // some cycles may not be reachable.
89              HashSet set2 = new HashSet(succ.keySet());
90              set2.removeAll(Traversals.reversePostOrder(getNavigator(), set));
91              if (set2.isEmpty()) break;
92              Object o = set2.iterator().next();
93              if (TRACE) System.out.println("Breaking cycle: choosing "+o);
94              set.add(o);
95          }
96          if (TRACE) System.out.println("Roots = "+roots);
97          return set;
98      }
99  
100     /* (non-Javadoc)
101      * @see jwutil.graphs.Graph#getNavigator()
102      */
103     public Navigator getNavigator() {
104         return new Nav();
105     }
106 
107     public void visitMethodSummary(MethodSummary ms) {
108         for (Iterator j = ms.nodeIterator(); j.hasNext(); ) {
109             Node n = (Node) j.next();
110             visitNode(n);
111         }
112     }
113     
114     public void visitNode(Node n) {
115         if (n instanceof ConcreteTypeNode ||
116             n instanceof UnknownTypeNode ||
117             n instanceof ConcreteObjectNode) {
118             jq_Reference type = n.getDeclaredType(); 
119             if (type != null) {
120                 jq_Class c = currentMethod.isStatic() ? null : currentMethod.getDeclaringClass();
121                 addEdge(c, n, type);
122             }
123         }
124         
125     }
126     
127     /* (non-Javadoc)
128      * @see joeq.Compiler.Quad.ControlFlowGraphVisitor#visitCFG(joeq.Compiler.Quad.ControlFlowGraph)
129      */
130     public void visitCFG(ControlFlowGraph cfg) {
131         currentMethod = cfg.getMethod();
132         cfg.visitBasicBlocks(this);
133     }
134     
135 
136     /* (non-Javadoc)
137      * @see joeq.Compiler.Quad.BasicBlockVisitor#visitBasicBlock(joeq.Compiler.Quad.BasicBlock)
138      */
139     public void visitBasicBlock(BasicBlock bb) {
140         bb.visitQuads(this);
141     }
142     
143     /* (non-Javadoc)
144      * @see joeq.Compiler.Quad.QuadVisitor#visitNew(joeq.Compiler.Quad.Quad)
145      */
146     public void visitNew(Quad obj) {
147         jq_Reference c1, c2;
148         if (currentMethod.isStatic()) {
149             c1 = null;
150         } else {
151             c1 = currentMethod.getDeclaringClass();
152         }
153         c2 = (jq_Reference) New.getType(obj).getType();
154         ProgramLocation pl = new ProgramLocation.QuadProgramLocation(currentMethod, obj);
155         addEdge(c1, pl, c2);
156     }
157     
158     /* (non-Javadoc)
159      * @see joeq.Compiler.Quad.QuadVisitor#visitNew(joeq.Compiler.Quad.Quad)
160      */
161     public void visitNewArray(Quad obj) {
162         jq_Reference c1, c2;
163         if (currentMethod.isStatic()) {
164             c1 = null;
165         } else {
166             c1 = currentMethod.getDeclaringClass();
167         }
168         c2 = (jq_Reference) NewArray.getType(obj).getType();
169         ProgramLocation pl = new ProgramLocation.QuadProgramLocation(currentMethod, obj);
170         addEdge(c1, pl, c2);
171     }
172     
173     public void addRoot(jq_Class c) {
174         if (TRACE) out.println("Adding root "+c);
175         roots.add(c);
176     }
177     
178     public void addEdge(jq_Reference c1, Node n, jq_Reference c2) {
179         if (MERGE_SITES || n == null) {
180             if (TRACE) out.println("Adding edge "+c1+" -> "+c2);
181             succ.add(c1, c2);
182             pred.add(c2, c1);
183         } else {
184             if (TRACE) out.println("Adding edge "+c1+" -> "+n+" -> "+c2);
185             succ.add(c1, n);
186             succ.add(n, c2);
187             pred.add(c2, n);
188             pred.add(n, c1);
189         }
190     }
191     
192     public void addEdge(jq_Reference c1, ProgramLocation pl, jq_Reference c2) {
193         if (MERGE_SITES || pl == null) {
194             if (TRACE) out.println("Adding edge "+c1+" -> "+c2);
195             succ.add(c1, c2);
196             pred.add(c2, c1);
197         } else {
198             if (TRACE) out.println("Adding edge "+c1+" -> "+pl+" -> "+c2);
199             succ.add(c1, pl);
200             succ.add(pl, c2);
201             pred.add(c2, pl);
202             pred.add(pl, c1);
203         }
204     }
205     
206     public void handleCallGraph(CallGraph cg) {
207         addRoot(null);
208         int j = 0;
209         for (Iterator i = cg.getAllMethods().iterator(); i.hasNext(); ++j) {
210             jq_Method m = (jq_Method) i.next();
211             if (m.getBytecode() == null) continue;
212             ControlFlowGraph cfg = CodeCache.getCode(m);
213             visitCFG(cfg);
214             if (j % 100 == 0)
215                 System.out.print("Visited methods: "+j+"\r");
216         }
217         System.out.println("Visited methods: "+j);
218     }
219     
220     public static void main(String[] args) throws IOException {
221         HostedVM.initialize();
222         CodeCache.AlwaysMap = true;
223         
224         ObjectCreationGraph g = new ObjectCreationGraph();
225         String callgraphFile = System.getProperty("callgraph", "callgraph");
226         System.out.println("Loading from callgraph \""+callgraphFile+"\"");
227         CallGraph cg = new LoadedCallGraph(callgraphFile);
228         
229         g.handleCallGraph(cg);
230         
231         SCCPathNumbering n = new SCCPathNumbering();
232         Number paths = n.countPaths(g);
233         System.out.println("Number of paths: "+paths.longValue());
234         
235         for (Iterator i = Traversals.reversePostOrder(g.getNavigator(), (Object)null).iterator(); i.hasNext(); ) {
236             Object c = i.next();
237             long v = n.numberOfPathsTo(c).longValue();
238             if (v > 1L) {
239                 System.out.println(v+" paths to "+c);
240             }
241         }
242         
243         BufferedWriter out = new BufferedWriter(new FileWriter("creation_graph.dot"));
244         n.dotGraph(out, g.getRoots(), g.getNavigator());
245         out.close();
246     }
247 
248 }