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
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
63
64
65 public Collection next(Object node) {
66 return succ.getValues(node);
67 }
68
69
70
71
72 public Collection prev(Object node) {
73 return pred.getValues(node);
74 }
75
76 }
77
78
79
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
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
101
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
128
129
130 public void visitCFG(ControlFlowGraph cfg) {
131 currentMethod = cfg.getMethod();
132 cfg.visitBasicBlocks(this);
133 }
134
135
136
137
138
139 public void visitBasicBlock(BasicBlock bb) {
140 bb.visitQuads(this);
141 }
142
143
144
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
159
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 }