1
2
3
4 package joeq.Compiler.Quad;
5
6 import java.util.Collections;
7 import java.util.HashMap;
8 import java.util.HashSet;
9 import java.util.Iterator;
10 import java.util.LinkedHashSet;
11 import java.util.LinkedList;
12 import java.util.Map;
13 import java.util.Set;
14 import joeq.Class.PrimordialClassLoader;
15 import joeq.Class.jq_Class;
16 import joeq.Class.jq_ClassInitializer;
17 import joeq.Class.jq_Field;
18 import joeq.Class.jq_Initializer;
19 import joeq.Class.jq_Method;
20 import joeq.Class.jq_Reference;
21 import joeq.Class.jq_StaticField;
22 import joeq.Class.jq_Type;
23 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
24 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.CallSite;
25 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ConcreteTypeNode;
26 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.FieldNode;
27 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.GlobalNode;
28 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.Node;
29 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.NodeSet;
30 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.OutsideNode;
31 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ParamNode;
32 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.PassedParameter;
33 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ReturnValueNode;
34 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.ThrownExceptionNode;
35 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.UnknownTypeNode;
36 import joeq.Compiler.Analysis.IPA.ProgramLocation;
37 import joeq.Compiler.BytecodeAnalysis.CallTargets;
38 import jwutil.collections.HashCodeComparator;
39 import jwutil.collections.LinearSet;
40 import jwutil.collections.Pair;
41 import jwutil.collections.SetFactory;
42 import jwutil.collections.SetRepository;
43 import jwutil.collections.SortedArraySet;
44 import jwutil.strings.Strings;
45 import jwutil.util.Assert;
46
47 /***
48 *
49 * @author John Whaley <jwhaley@alum.mit.edu>
50 * @version $Id: AndersenPointerAnalysis.java 2465 2006-06-07 23:03:17Z joewhaley $
51 */
52 public class AndersenPointerAnalysis {
53
54 /***
55 * Output stream for trace information.
56 */
57 public static java.io.PrintStream out = System.out;
58
59 /***
60 * Controls the output of trace information.
61 * This is useful in debugging the analysis, but causes
62 * a LOT of information to be dumped.
63 */
64 public static
65
66 /***
67 * Output the cause of the *first* change in each iteration.
68 */
69 public static final boolean TRACE_CHANGE = false;
70
71 /***
72 * Output debugging information on the collapsing of cycles.
73 */
74 public static final boolean TRACE_CYCLES = false;
75
76 /***
77 * Enable/disable assertion checking.
78 */
79 public static final boolean VerifyAssertions = false;
80
81 /***
82 * Dump the call graph after analysis has completed.
83 */
84 public static boolean FULL_DUMP = false;
85
86 /***
87 * Compare our result to RTA, and dump the statistics.
88 */
89 public static boolean COMPARE_RTA = false;
90
91 /***
92 * Do the analysis twice, and report timings for each.
93 */
94 public static boolean DO_TWICE = false;
95
96 /***
97 * Don't explicitly model the calling of <clinit> methods.
98 */
99 public static boolean IGNORE_CLINIT = false;
100
101 /***
102 * Controls the handling of references that escape to native
103 * methods or threads.
104 * "true" means it takes a pessimistic view of threads and
105 * native methods, assuming that they can update any reference
106 * passed into them in arbitrary ways.
107 * "false" means it takes an optimistic view, assuming that
108 * they make no modifications that will matter to the pointer
109 * analysis.
110 */
111 public static final boolean HANDLE_ESCAPE = false;
112
113 /***
114 * Controls the use of soft references for the lookup cache.
115 */
116 public static final boolean USE_SOFT_REFERENCES = false;
117
118 /***
119 * Force a garbage collection after every iteration of the algorithm.
120 */
121 public static boolean FORCE_GC = false;
122
123 /***
124 * Reuse the lookup cache across multiple iterations of the algorithm.
125 */
126 public static final boolean REUSE_CACHES = true;
127
128 /***
129 * Keep track of whether cache entries change between iterations,
130 * to avoid the reconstruction and reduce the number of set union
131 * operations.
132 */
133 public static final boolean TRACK_CHANGES = true;
134
135 /***
136 * Track which fields have changed between iterations.
137 * ***DOESN'T GIVE CORRECT ANSWERS IN SOME CASES***
138 */
139 public static final boolean TRACK_CHANGED_FIELDS = false;
140
141 /***
142 * Keep track of the reason why each inclusion edge was
143 * added to the graph.
144 */
145 public static boolean TRACK_REASONS = true;
146
147 /***
148 * Keep track of inclusion back edges.
149 */
150 public static final boolean INCLUSION_BACK_EDGES = false;
151
152 /***
153 * Use a set repository, rather than a set factory.
154 * The set repository attempts to reduce memory usage by
155 * reusing set data structures.
156 */
157 public static final boolean USE_SET_REPOSITORY = false;
158
159 private static MethodSummary getMethodSummary(jq_Method method) {
160
161
162
163
164
165
166 MethodSummary s = MethodSummary.getSummary(CodeCache.getCode((jq_Method)method));
167 s.mergeGlobal();
168 return s;
169 }
170
171 private static MethodSummary getMethodSummary(jq_Method method, CallSite cs) {
172
173
174
175
176
177
178 MethodSummary s = MethodSummary.getSummary(CodeCache.getCode((jq_Method)method), cs);
179 s.mergeGlobal();
180 return s;
181 }
182
183 /***
184 * Add a control flow graph to the root set.
185 * We get the method summary for the given control flow graph, and add
186 * that to the root set.
187 *
188 * @param cfg control flow graph to add
189 * @return boolean whether the root set changed
190 */
191 public boolean addToRootSet(ControlFlowGraph cfg) {
192 if (TRACE) out.println("Adding "+cfg.getMethod()+" to root set.");
193 MethodSummary s = MethodSummary.getSummary(cfg);
194 s.mergeGlobal();
195 return this.rootSet.add(s);
196 }
197
198 public boolean addToRootSet(MethodSummary s) {
199 if (TRACE) out.println("Adding "+s.getMethod()+" to root set.");
200 return this.rootSet.add(s);
201 }
202
203 public static final class Visitor implements ControlFlowGraphVisitor {
204 public static boolean added_hook = false;
205 public void visitCFG(ControlFlowGraph cfg) {
206 INSTANCE.addToRootSet(cfg);
207 if (!added_hook) {
208 added_hook = true;
209 Runtime.getRuntime().addShutdownHook(new Thread() {
210 public void run() {
211 doIt();
212 }
213 });
214 if (TRACE) out.println("Added Andersen shutdown hook.");
215 }
216 }
217 public static void doIt() {
218 Set rootSet = INSTANCE.rootSet;
219 long time = System.currentTimeMillis();
220 INSTANCE.iterate();
221 time = System.currentTimeMillis() - time;
222 System.out.println("First time: "+time);
223
224 if (DO_TWICE) {
225 long mem1 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
226 System.out.println("Used memory before gc: "+mem1);
227 INSTANCE = new AndersenPointerAnalysis(true);
228 INSTANCE.rootSet.addAll(rootSet);
229 System.gc();
230 long mem2 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
231 System.out.println("Used memory after gc: "+mem2);
232 time = System.currentTimeMillis();
233 INSTANCE.iterate();
234 time = System.currentTimeMillis() - time;
235
236 long mem3 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
237 System.out.println("Used memory before gc: "+mem3);
238 System.gc();
239 long mem4 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
240 System.out.println("Used memory after gc: "+mem4);
241
242 System.out.println("Our analysis: "+(time/1000.)+" seconds, "+(mem2-mem2)+" bytes of memory");
243 }
244
245 System.out.println("Result of Andersen pointer analysis:");
246 CallGraph cg = INSTANCE.getCallGraph();
247 if (FULL_DUMP)
248 System.out.println(cg);
249 System.out.println(INSTANCE.computeStats());
250 System.out.println(cg.computeHistogram("call site", "target"));
251
252 if (COMPARE_RTA) {
253 calcRTA();
254
255 System.out.println("Compare to CHA/RTA:");
256 HashMap cha_rta_callSiteToTargets = new HashMap();
257 for (Iterator i=INSTANCE.callSiteToTargets.entrySet().iterator(); i.hasNext(); ) {
258 Map.Entry e = (Map.Entry)i.next();
259 CallSite cs = (CallSite)e.getKey();
260 CallTargets ct = getCallTargets_CHA(cs.getLocation());
261 cha_rta_callSiteToTargets.put(cs, ct);
262 }
263 cg = CallGraph.makeCallGraph(INSTANCE.rootSet, cha_rta_callSiteToTargets);
264 if (FULL_DUMP)
265 System.out.println(cg);
266 System.out.println(cg.computeHistogram("call site", "target"));
267 }
268 }
269 public static void calcRTA() {
270 for (;;) {
271 int numTypes = PrimordialClassLoader.loader.getNumTypes();
272 jq_Type[] types = PrimordialClassLoader.loader.getAllTypes();
273 for (int i = 0; i < numTypes; ++i) {
274 jq_Type t = types[i];
275 t.prepare();
276 }
277 if (false || PrimordialClassLoader.loader.getNumTypes() == numTypes)
278 break;
279 }
280 int numTypes = PrimordialClassLoader.loader.getNumTypes();
281 System.out.println("Number of RTA classes: "+numTypes);
282 jq_Type[] types = PrimordialClassLoader.loader.getAllTypes();
283 Set methods = new HashSet();
284 for (int i = 0; i < numTypes; ++i) {
285 jq_Type t = types[i];
286 if (t instanceof jq_Class) {
287 jq_Class k = (jq_Class)t;
288 k.load();
289 jq_Method[] ms = k.getDeclaredInstanceMethods();
290 for (int j=0; j<ms.length; ++j) {
291 methods.add(ms[j]);
292 }
293 ms = k.getDeclaredStaticMethods();
294 for (int j=0; j<ms.length; ++j) {
295 methods.add(ms[j]);
296 }
297 }
298 }
299 System.out.println("Number of RTA methods: "+methods.size());
300 int nInvokes = 0, nTargets = 0; long nBytecodes = 0;
301 Iterator k = methods.iterator();
302 while (k.hasNext()) {
303 jq_Method m = (jq_Method)k.next();
304 if (m.getBytecode() == null) continue;
305 nBytecodes += m.getBytecode().length;
306 InvokeCounter ic = new InvokeCounter(m);
307 ic.forwardTraversal();
308 nInvokes += ic.invokeCount; nTargets += ic.targetCount;
309 }
310 System.out.println("Number of RTA invocations: "+nInvokes);
311 System.out.println("Number of RTA call graph edges: "+nTargets);
312 System.out.println("Number of RTA bytecodes: "+nBytecodes);
313 }
314
315 static class InvokeCounter extends joeq.Compiler.BytecodeAnalysis.BytecodeVisitor {
316 int invokeCount = 0; int targetCount = 0;
317 InvokeCounter(jq_Method m) { super(m); }
318 void visitInvoke(byte op, jq_Method f) {
319 invokeCount++;
320 CallTargets ct = CallTargets.getTargets(method.getDeclaringClass(), f, op, true);
321 targetCount += ct.size();
322 }
323 public void visitIINVOKE(byte op, jq_Method f) {
324 visitInvoke(op, f);
325 }
326 public void visitLINVOKE(byte op, jq_Method f) {
327 visitInvoke(op, f);
328 }
329 public void visitFINVOKE(byte op, jq_Method f) {
330 visitInvoke(op, f);
331 }
332 public void visitDINVOKE(byte op, jq_Method f) {
333 visitInvoke(op, f);
334 }
335 public void visitAINVOKE(byte op, jq_Method f) {
336 visitInvoke(op, f);
337 }
338 public void visitVINVOKE(byte op, jq_Method f) {
339 visitInvoke(op, f);
340 }
341 }
342
343 public static void doIt_output() {
344 INSTANCE.iterate();
345 System.out.println("Result of Andersen pointer analysis:");
346 CallGraph cg = INSTANCE.getCallGraph();
347 System.out.println(cg);
348 System.out.println(INSTANCE.computeStats());
349 System.out.println(cg.computeHistogram("call site", "target"));
350
351 if (COMPARE_RTA) {
352 System.out.println("Compare to CHA/RTA:");
353 calcRTA();
354 HashMap cha_rta_callSiteToTargets = new HashMap();
355 for (Iterator i=INSTANCE.callSiteToTargets.entrySet().iterator(); i.hasNext(); ) {
356 Map.Entry e = (Map.Entry)i.next();
357 CallSite cs = (CallSite)e.getKey();
358 CallTargets ct = getCallTargets_CHA(cs.getLocation());
359 cha_rta_callSiteToTargets.put(cs, ct);
360 }
361 cg = CallGraph.makeCallGraph(INSTANCE.rootSet, cha_rta_callSiteToTargets);
362 System.out.println(cg);
363 System.out.println(cg.computeHistogram("call site", "target"));
364 }
365 }
366 }
367
368 public void initializeStatics(boolean addMethodsToVisit) {
369
370 jq_Class fd = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/FileDescriptor;");
371 fd.load();
372 ConcreteTypeNode fd_n1 = ConcreteTypeNode.get(fd);
373 jq_Initializer fd_init = (jq_Initializer)fd.getOrCreateInstanceMethod("<init>", "(I)V");
374 Assert._assert(fd_init.isLoaded());
375 ProgramLocation mc_fd_init = new ProgramLocation.QuadProgramLocation(fd_init, null);
376 fd_n1.recordPassedParameter(mc_fd_init, 0);
377
378 jq_Class fis = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/FileInputStream;");
379 fis.load();
380 ConcreteTypeNode fis_n = ConcreteTypeNode.get(fis);
381 jq_Initializer fis_init = (jq_Initializer)fis.getOrCreateInstanceMethod("<init>", "(Ljava/io/FileDescriptor;)V");
382 Assert._assert(fis_init.isLoaded());
383 ProgramLocation mc_fis_init = new ProgramLocation.QuadProgramLocation(fis_init, null);
384 fis_n.recordPassedParameter(mc_fis_init, 0);
385 fd_n1.recordPassedParameter(mc_fis_init, 1);
386 jq_Class bis = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/BufferedInputStream;");
387 bis.load();
388 ConcreteTypeNode bis_n = ConcreteTypeNode.get(bis);
389 jq_Initializer bis_init = (jq_Initializer)bis.getOrCreateInstanceMethod("<init>", "(Ljava/io/InputStream;)V");
390 Assert._assert(bis_init.isLoaded());
391 ProgramLocation mc_bis_init = new ProgramLocation.QuadProgramLocation(bis_init, null);
392 bis_n.recordPassedParameter(mc_bis_init, 0);
393 fis_n.recordPassedParameter(mc_bis_init, 1);
394
395 jq_Class jls = PrimordialClassLoader.getJavaLangSystem();
396 jls.load();
397 jq_StaticField si = jls.getOrCreateStaticField("in", "Ljava/io/InputStream;");
398 Assert._assert(si.isLoaded());
399 GlobalNode.GLOBAL.addEdge(si, bis_n);
400
401 MethodSummary fd_init_summary = getMethodSummary(fd_init);
402 OutsideNode on = fd_init_summary.getParamNode(0);
403 addInclusionEdge(on, fd_n1, null);
404 MethodSummary fis_init_summary = getMethodSummary(fis_init);
405 on = fis_init_summary.getParamNode(0);
406 addInclusionEdge(on, fis_n, null);
407 on = fis_init_summary.getParamNode(1);
408 addInclusionEdge(on, fd_n1, null);
409 MethodSummary bis_init_summary = getMethodSummary(bis_init);
410 on = bis_init_summary.getParamNode(0);
411 addInclusionEdge(on, bis_n, null);
412 on = bis_init_summary.getParamNode(1);
413 addInclusionEdge(on, fis_n, null);
414
415 ConcreteTypeNode fd_n2 = ConcreteTypeNode.get(fd);
416 fd_n2.recordPassedParameter(mc_fd_init, 0);
417 jq_Class fos = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/FileOutputStream;");
418 fos.load();
419 ConcreteTypeNode fos_n1 = ConcreteTypeNode.get(fos);
420 jq_Initializer fos_init = (jq_Initializer)fos.getOrCreateInstanceMethod("<init>", "(Ljava/io/FileDescriptor;)V");
421 Assert._assert(fos_init.isLoaded());
422 ProgramLocation mc_fos_init = new ProgramLocation.QuadProgramLocation(fos_init, null);
423 fos_n1.recordPassedParameter(mc_fos_init, 0);
424 fd_n2.recordPassedParameter(mc_fos_init, 1);
425 jq_Class bos = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/BufferedOutputStream;");
426 bos.load();
427 ConcreteTypeNode bos_n1 = ConcreteTypeNode.get(bos);
428 jq_Initializer bos_init = (jq_Initializer)bos.getOrCreateInstanceMethod("<init>", "(Ljava/io/OutputStream;I)V");
429 Assert._assert(bos_init.isLoaded());
430 ProgramLocation mc_bos_init = new ProgramLocation.QuadProgramLocation(bos_init, null);
431 bos_n1.recordPassedParameter(mc_bos_init, 0);
432 fos_n1.recordPassedParameter(mc_bos_init, 1);
433
434 jq_Class ps = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljava/io/PrintStream;");
435 ps.load();
436 ConcreteTypeNode ps_n1 = ConcreteTypeNode.get(ps);
437 jq_Initializer ps_init = (jq_Initializer)ps.getOrCreateInstanceMethod("<init>", "(Ljava/io/OutputStream;Z)V");
438 Assert._assert(ps_init.isLoaded());
439 ProgramLocation mc_ps_init = new ProgramLocation.QuadProgramLocation(ps_init, null);
440 ps_n1.recordPassedParameter(mc_ps_init, 0);
441 bos_n1.recordPassedParameter(mc_ps_init, 1);
442
443 jq_StaticField so = jls.getOrCreateStaticField("out", "Ljava/io/PrintStream;");
444 Assert._assert(so.isLoaded());
445 GlobalNode.GLOBAL.addEdge(so, ps_n1);
446
447 ConcreteTypeNode fd_n3 = ConcreteTypeNode.get(fd);
448 fd_n3.recordPassedParameter(mc_fd_init, 0);
449 ConcreteTypeNode fos_n2 = ConcreteTypeNode.get(fos);
450 fos_n2.recordPassedParameter(mc_fos_init, 0);
451 fd_n3.recordPassedParameter(mc_fos_init, 1);
452 ConcreteTypeNode bos_n2 = ConcreteTypeNode.get(bos);
453 bos_n2.recordPassedParameter(mc_bos_init, 0);
454 fos_n2.recordPassedParameter(mc_bos_init, 1);
455 ConcreteTypeNode ps_n2 = ConcreteTypeNode.get(ps);
456 ps_n2.recordPassedParameter(mc_ps_init, 0);
457 bos_n2.recordPassedParameter(mc_ps_init, 1);
458
459 so = jls.getOrCreateStaticField("err", "Ljava/io/PrintStream;");
460 Assert._assert(so.isLoaded());
461 GlobalNode.GLOBAL.addEdge(so, ps_n2);
462
463 on = fd_init_summary.getParamNode(0);
464 addInclusionEdge(on, fd_n2, null);
465 addInclusionEdge(on, fd_n3, null);
466 MethodSummary fos_init_summary = getMethodSummary(fos_init);
467 on = fos_init_summary.getParamNode(0);
468 addInclusionEdge(on, fos_n1, null);
469 addInclusionEdge(on, fos_n2, null);
470 on = fos_init_summary.getParamNode(1);
471 addInclusionEdge(on, fd_n2, null);
472 addInclusionEdge(on, fd_n3, null);
473 MethodSummary bos_init_summary = getMethodSummary(bos_init);
474 on = bos_init_summary.getParamNode(0);
475 addInclusionEdge(on, bos_n1, null);
476 addInclusionEdge(on, bos_n2, null);
477 on = bos_init_summary.getParamNode(1);
478 addInclusionEdge(on, fos_n1, null);
479 addInclusionEdge(on, fos_n2, null);
480 MethodSummary ps_init_summary = getMethodSummary(ps_init);
481 on = ps_init_summary.getParamNode(0);
482 addInclusionEdge(on, ps_n1, null);
483 addInclusionEdge(on, ps_n2, null);
484 on = ps_init_summary.getParamNode(1);
485 addInclusionEdge(on, bos_n1, null);
486 addInclusionEdge(on, bos_n2, null);
487
488 jq_Class nt = (jq_Class)PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Scheduler/jq_NativeThread;");
489 nt.load();
490 ConcreteTypeNode nt_n1 = ConcreteTypeNode.get(nt);
491
492
493
494
495
496
497
498
499
500
501
502
503
504 if (addMethodsToVisit) {
505 methodSummariesToVisit.add(fd_init_summary);
506 methodSummariesToVisit.add(fis_init_summary);
507 methodSummariesToVisit.add(bis_init_summary);
508 methodSummariesToVisit.add(fos_init_summary);
509 methodSummariesToVisit.add(bos_init_summary);
510 methodSummariesToVisit.add(ps_init_summary);
511
512
513 }
514 }
515
516 /*** Cache: Maps a node to its set of corresponding concrete nodes. */
517 final HashMap nodeToConcreteNodes;
518
519 /*** Maps a node to its set of outgoing inclusion edges. */
520 final HashMap nodeToInclusionEdges;
521
522 /*** Maps a node to its set of incoming inclusion edges.
523 * Only used if INCLUSION_BACK_EDGES is set. */
524 final HashMap nodeToIncomingInclusionEdges;
525
526 /*** Maps an inclusion edge to the ProgramLocation that caused the edge.
527 * Only used if TRACK_REASONS is set. */
528 final HashMap edgesToReasons;
529
530 /*** Set of all MethodSummary's that we care about. */
531 final Set rootSet;
532 final Set methodSummariesToVisit;
533
534 /*** Maps a call site to its set of targets. */
535 final HashMap callSiteToTargets;
536
537 /*** The set of method call->targets that have already been linked. */
538 final HashSet linkedTargets;
539
540 /*** Records if the cache for the node is current, and whether it has changed
541 * since the last iteration. Only used if REUSE_CACHES is true. */
542 final HashMap cacheIsCurrent;
543
544 /*** Records edges that have not yet been propagated.
545 * Only used if TRACK_CHANGES is true. */
546 final HashSet unpropagatedEdges;
547
548 /*** Records nodes that have been collapsed, and which predecessors have
549 * seen the collapse. Only used if TRACK_CHANGES is true. */
550 final HashMap collapsedNodes;
551
552 /*** Records what fields have changed. Only used if TRACK_CHANGED_FIELDS is true. */
553 HashSet oldChangedFields;
554 HashSet newChangedFields;
555 HashSet changedFields_Methods;
556
557 SetFactory cacheSetFactory;
558 SetFactory inclusionEdgeSetFactory;
559
560 /*** Change flag, for iterations. */
561 boolean change;
562
563 /*** Creates new AndersenPointerAnalysis */
564 public AndersenPointerAnalysis(boolean addDefaults) {
565 nodeToConcreteNodes = new HashMap();
566 nodeToInclusionEdges = new HashMap();
567 if (INCLUSION_BACK_EDGES)
568 nodeToIncomingInclusionEdges = new HashMap();
569 else
570 nodeToIncomingInclusionEdges = null;
571 rootSet = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
572 methodSummariesToVisit = new LinkedHashSet();
573 callSiteToTargets = new HashMap();
574 linkedTargets = new HashSet();
575 if (REUSE_CACHES)
576 cacheIsCurrent = new HashMap();
577 else
578 cacheIsCurrent = null;
579 if (TRACK_CHANGES) {
580 unpropagatedEdges = new HashSet();
581 collapsedNodes = new HashMap();
582 } else {
583 unpropagatedEdges = null;
584 collapsedNodes = null;
585 }
586 if (TRACK_REASONS)
587 edgesToReasons = new HashMap();
588 else
589 edgesToReasons = null;
590 if (TRACK_CHANGED_FIELDS) {
591
592 changedFields_Methods = new HashSet();
593 }
594 if (USE_SET_REPOSITORY) {
595 cacheSetFactory = new SetRepository();
596 } else {
597
598
599 cacheSetFactory = NodeSet.FACTORY;
600 }
601
602
603 inclusionEdgeSetFactory = NodeSet.FACTORY;
604 this.initializeStatics(addDefaults);
605 }
606
607 public static AndersenPointerAnalysis INSTANCE = new AndersenPointerAnalysis(true);
608
609 public String computeStats() {
610 StringBuffer sb = new StringBuffer();
611 HashSet classes = new HashSet();
612 HashSet methods = new HashSet();
613 long bytecodes = 0;
614 for (Iterator i=methodSummariesToVisit.iterator(); i.hasNext(); ) {
615 MethodSummary ms = (MethodSummary)i.next();
616 methods.add(ms.getMethod());
617 bytecodes += ((jq_Method)ms.getMethod()).getBytecode().length;
618 jq_Class c = ((jq_Method)ms.getMethod()).getDeclaringClass();
619 while (c != null) {
620 classes.add(c);
621 c.load();
622 c = c.getSuperclass();
623 }
624 }
625 sb.append(" Classes: ");
626 sb.append(classes.size());
627 sb.append(" Methods: ");
628 sb.append(methods.size());
629 sb.append(" Summaries: ");
630 sb.append(methodSummariesToVisit.size());
631 sb.append(" Calls: ");
632 sb.append(callSiteToTargets.size());
633 sb.append(" Bytecodes ");
634 sb.append(bytecodes);
635 sb.append(" Iteration ");
636 sb.append(count);
637 sb.append(Strings.lineSep);
638 return sb.toString();
639 }
640 public static Map buildOriginalCallGraph(Map m) {
641 HashMap newCG = new HashMap();
642 for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
643 Map.Entry e = (Map.Entry)i.next();
644 CallSite cs = (CallSite)e.getKey();
645 Set s = (Set)e.getValue();
646 ProgramLocation mc = cs.getLocation();
647 Set s2 = (Set) newCG.get(mc);
648 if (s2 == null)
649 newCG.put(mc, s2 = new HashSet());
650 s2.addAll(s);
651 }
652 return newCG;
653 }
654 public static String compareWithOriginal(Map cg, Map original) {
655 HashMap table = new HashMap();
656 for (Iterator i=cg.entrySet().iterator(); i.hasNext(); ) {
657 Map.Entry e = (Map.Entry)i.next();
658 CallSite cs = (CallSite)e.getKey();
659 Set s = (Set)e.getValue();
660 int x = s.size();
661 ProgramLocation mc = cs.getLocation();
662 Set s_orig = (Set)original.get(mc);
663 int y = s_orig.size();
664 Object key = new Pair(new Integer(y),new Integer(x));
665 HashSet k = (HashSet) table.get(key);
666 if (k == null) table.put(key, k = new HashSet());
667 k.add(mc);
668 }
669 StringBuffer sb = new StringBuffer();
670 for (Iterator i=table.entrySet().iterator(); i.hasNext(); ) {
671 Map.Entry e = (Map.Entry)i.next();
672 sb.append(e.getKey());
673 sb.append(": ");
674 Set s = (Set) e.getValue();
675 sb.append(s.size());
676 sb.append(Strings.lineSep);
677 }
678 return sb.toString();
679 }
680 public static final int HISTOGRAM_SIZE = 100;
681 public static String computeHistogram2(Map m) {
682 HashMap table = new HashMap();
683 for (Iterator i=m.entrySet().iterator(); i.hasNext(); ) {
684 Map.Entry e = (Map.Entry)i.next();
685 CallSite cs = (CallSite)e.getKey();
686 ProgramLocation mc = cs.getLocation();
687 Set s = (Set)e.getValue();
688 Set s2 = (Set)table.get(mc);
689 if (s2 == null) table.put(mc, s2 = new LinearSet());
690 s2.add(s);
691 }
692 StringBuffer sb = new StringBuffer();
693 int[] histogram = new int[HISTOGRAM_SIZE];
694 long total = 0;
695 for (Iterator i=table.entrySet().iterator(); i.hasNext(); ) {
696 Map.Entry e = (Map.Entry)i.next();
697 Set s = (Set)e.getValue();
698 int x = s.size();
699 int y = 0;
700 for (Iterator j=s.iterator(); j.hasNext(); ) {
701 y += ((Set)j.next()).size();
702 }
703 int foo = y / x;
704 if (foo >= HISTOGRAM_SIZE) foo = HISTOGRAM_SIZE-1;
705 histogram[foo]++;
706 total += foo;
707 }
708 sb.append(" Total # of call graph edges: ");
709 sb.append(total);
710 sb.append('/');
711 sb.append(total+histogram[0]);
712 sb.append(Strings.lineSep);
713 for (int i=0; i<HISTOGRAM_SIZE; ++i) {
714 if (histogram[i] > 0) {
715 if (i == HISTOGRAM_SIZE-1) sb.append(">=");
716 sb.append(i);
717 sb.append(" targets:\t");
718 sb.append(histogram[i]);
719 sb.append(" call site");
720 if (histogram[i] > 1) sb.append('s');
721 sb.append(Strings.lineSep);
722 }
723 }
724 sb.append("Average # of targets: "+(double)total/(double)table.size());
725 sb.append(Strings.lineSep);
726 long total_multi = total - histogram[1];
727 long cs_multi = table.size() - histogram[1] - histogram[0];
728 sb.append("# of multi-target calls: "+cs_multi);
729 sb.append(Strings.lineSep);
730 sb.append("Total targets for multi-target calls: "+total_multi);
731 sb.append(Strings.lineSep);
732 sb.append("Average # of targets for multi: "+(double)total_multi/(double)cs_multi);
733 sb.append(Strings.lineSep);
734 return sb.toString();
735 }
736
737 int count;
738
739 public void iterate() {
740 methodSummariesToVisit.addAll(rootSet);
741 count = 1;
742 for (;;) {
743 this.change = false;
744 System.err.println("Iteration "+count+": "+methodSummariesToVisit.size()+" methods "+callSiteToTargets.size()+" call sites "+linkedTargets.size()+" call graph edges");
745 doGlobals();
746 LinkedList ll = new LinkedList();
747 ll.addAll(methodSummariesToVisit);
748 for (Iterator i=ll.iterator(); i.hasNext(); ) {
749 MethodSummary ms = (MethodSummary)i.next();
750 visitMethod(ms);
751 }
752 if (!change) break;
753 if (REUSE_CACHES)
754 cacheIsCurrent.clear();
755 else
756 nodeToConcreteNodes.clear();
757 if (TRACK_CHANGED_FIELDS) {
758 oldChangedFields = newChangedFields;
759 System.err.println(oldChangedFields.size()+" changed fields");
760 newChangedFields = new HashSet();
761 }
762 if (FORCE_GC) System.gc();
763 ++count;
764 }
765 }
766
767 void doGlobals() {
768 if (TRACE) out.println("Doing global variables...");
769 LinkedHashSet lhs = new LinkedHashSet();
770 lhs.addAll(GlobalNode.GLOBAL.getAccessPathEdges());
771 for (Iterator j=lhs.iterator(); j.hasNext(); ) {
772 Map.Entry e = (Map.Entry)j.next();
773 jq_Field f = (jq_Field)e.getKey();
774 Object o = e.getValue();
775 if (!IGNORE_CLINIT && !MethodSummary.IGNORE_STATIC_FIELDS) {
776 jq_Class c = f.getDeclaringClass();
777 if (TRACE) out.println("Visiting edge: "+o+" = "+c+"."+f.getName());
778 c.load();
779 jq_ClassInitializer clinit = c.getClassInitializer();
780 if (clinit != null) {
781 MethodSummary ms = getMethodSummary(clinit);
782 if (methodSummariesToVisit.add(ms)) {
783 if ((TRACE_CHANGE && !this.change) || TRACE) {
784 out.println("Changed! New clinit method: "+clinit);
785 }
786 this.change = true;
787 }
788 }
789 }
790
791 if (o instanceof Set) {
792 addGlobalEdges((Set)o, f);
793 } else {
794 addGlobalEdges((FieldNode)o, f);
795 }
796 }
797 }
798
799
800
801
802
803
804
805
806
807 void visitMethod(MethodSummary ms) {
808 if (TRACE) out.println("Visiting method: "+ms.getMethod());
809
810 for (Iterator i=ms.nodeIterator(); i.hasNext(); ) {
811 Node n = (Node)i.next();
812 for (Iterator j=n.getNonEscapingEdges().iterator(); j.hasNext(); ) {
813 Map.Entry e = (Map.Entry)j.next();
814 jq_Field f = (jq_Field)e.getKey();
815 if (TRACK_CHANGED_FIELDS) {
816 if (!changedFields_Methods.contains(ms.getMethod())) {
817 newChangedFields.add(f);
818 }
819 }
820 Object o = e.getValue();
821 if (TRACE) out.println("Visiting edge: "+n+((f==null)?"[]":("."+f.getName()))+" = "+o);
822
823 if (o instanceof Set) {
824 addEdgesFromConcreteNodes(n, f, (Set)o);
825 } else {
826 addEdgesFromConcreteNodes(n, f, (Node)o);
827 }
828 }
829 if (HANDLE_ESCAPE) {
830 if (n instanceof OutsideNode && n.getEscapes()) {
831 Set s = getConcreteNodes(n);
832 if (TRACE) out.println("Escaping node "+n+" corresponds to concrete nodes "+s);
833 for (Iterator j=s.iterator(); j.hasNext(); ) {
834 Node n2 = (Node)j.next();
835 if (!n2.getEscapes()) {
836 n2.setEscapes();
837 if ((TRACE_CHANGE && !this.change) || TRACE) {
838 out.println("Changed! Concrete node "+n2+" escapes");
839 }
840 this.change = true;
841 }
842 }
843 }
844 }
845 for (Iterator j=n.getAccessPathEdges().iterator(); j.hasNext(); ) {
846 Map.Entry e = (Map.Entry)j.next();
847 jq_Field f = (jq_Field)e.getKey();
848 if (TRACK_CHANGED_FIELDS) {
849 if (!changedFields_Methods.contains(ms.getMethod())) {
850 changedFields_Methods.add(ms.getMethod());
851 } else if (oldChangedFields != null && !oldChangedFields.contains(f) && !newChangedFields.contains(f)) continue;
852 }
853 Object o = e.getValue();
854 if (TRACE) out.println("Visiting edge: "+o+" = "+n+((f==null)?"[]":("."+f.getName())));
855
856 if (o instanceof Set) {
857 addInclusionEdgesToConcreteNodes((Set)o, n, f);
858 } else {
859 addInclusionEdgesToConcreteNodes((FieldNode)o, n, f);
860 }
861 }
862 }
863
864
865 for (Iterator i=ms.getCalls().iterator(); i.hasNext(); ) {
866 ProgramLocation mc = (ProgramLocation)i.next();
867 CallSite cs = new CallSite(ms, mc);
868 if (TRACE) out.println("Found call: "+ms+": "+mc.toString());
869 CallTargets ct = getCallTargets_CHA(mc);
870 if (TRACE) out.println("Possible targets ignoring type information: "+ct);
871 Set definite_targets = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
872
873 callSiteToTargets.put(cs, definite_targets);
874 if (ct.size() == 1 && ct.isComplete()) {
875
876 if (TRACE) out.println("Call is statically resolved to a single target.");
877 definite_targets.add(ct.iterator().next());
878 } else {
879
880 PassedParameter pp = new PassedParameter(mc, 0);
881 Set set = ms.getNodesThatCall(pp);
882 if (TRACE) out.println("Possible nodes for receiver object: "+set);
883 for (Iterator j=set.iterator(); j.hasNext(); ) {
884 Node base = (Node)j.next();
885 if (TRACE) out.println("Checking base node: "+base);
886 Set s_cn = getConcreteNodes(base);
887 Set targets = getCallTargets(mc, s_cn);
888 definite_targets.addAll(targets);
889 }
890 }
891 if (TRACE) out.println("Set of definite targets of "+mc+": "+definite_targets);
892 for (Iterator j=definite_targets.iterator(); j.hasNext(); ) {
893 jq_Method callee = (jq_Method)j.next();
894
895 if (callee == joeq.Runtime.Arrays._multinewarray) continue;
896 callee.getDeclaringClass().load();
897 if (!callee.isBodyLoaded()) {
898 CallSite cs2 = new CallSite(null, mc);
899 if (linkedTargets.contains(cs2)) continue;
900 linkedTargets.add(cs2);
901 if ((TRACE_CHANGE && !this.change) || TRACE) {
902 out.println("Changed! New target for "+mc+": "+callee+" (unanalyzable)");
903 }
904 this.change = true;
905 if (TRACE) out.println(callee+" is a native method, skipping analysis...");
906 addParameterAndReturnMappings_native(ms, mc);
907 continue;
908 }
909 MethodSummary callee_summary = getMethodSummary(callee, cs);
910 CallSite cs2 = new CallSite(callee_summary, mc);
911 if (linkedTargets.contains(cs2)) continue;
912 linkedTargets.add(cs2);
913 if ((TRACE_CHANGE && !this.change) || TRACE) {
914 out.println("Changed! New target for "+mc+": "+callee_summary.getMethod());
915 }
916 this.change = true;
917 addParameterAndReturnMappings(ms, mc, callee_summary);
918 methodSummariesToVisit.add(callee_summary);
919 }
920 }
921 }
922
923 public static CallTargets getCallTargets_CHA(ProgramLocation pl) {
924 jq_Method target = pl.getTargetMethod();
925 byte type = pl.getInvocationType();
926 return CallTargets.getTargets(target.getDeclaringClass(), target, type, true);
927 }
928 public static CallTargets getCallTargets(ProgramLocation pl, Set nodes) {
929 byte type = pl.getInvocationType();
930 jq_Method target = pl.getTargetMethod();
931 Set exact_types = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
932 Set notexact_types = SortedArraySet.FACTORY.makeSet(HashCodeComparator.INSTANCE);
933
934 for (Iterator i=nodes.iterator(); i.hasNext(); ) {
935 Node n = (Node)i.next();
936 Set s = (n instanceof ConcreteTypeNode)?exact_types:notexact_types;
937 if (n.getDeclaredType() != null)
938 s.add(n.getDeclaredType());
939 }
940 if (notexact_types.isEmpty())
941 return CallTargets.getTargets(target.getDeclaringClass(), target, type, exact_types, true, true);
942 if (exact_types.isEmpty())
943 return CallTargets.getTargets(target.getDeclaringClass(), target, type, notexact_types, false, true);
944 CallTargets ct = CallTargets.getTargets(target.getDeclaringClass(), target, type, exact_types, true, true);
945 if (ct==null) return null;
946 ct = ct.union(CallTargets.getTargets(target.getDeclaringClass(), target, type, notexact_types, false, true));
947 return ct;
948 }
949
950 void addParameterAndReturnMappings_native(MethodSummary caller, ProgramLocation mc) {
951 if (TRACE) out.println("Adding parameter and return mappings for "+mc+" from "+caller.getMethod()+" to an unanalyzable method.");
952
953
954 jq_Method targetMethod = mc.getTargetMethod();
955 jq_Type[] types = mc.getParamTypes();
956 for (int i=0; i<types.length; ++i) {
957 jq_Type t = types[i];
958 if (!(t instanceof jq_Reference)) continue;
959
960 PassedParameter pp = new PassedParameter(mc, i);
961 Set s = caller.getNodesThatCall(pp);
962 for (Iterator j=s.iterator(); j.hasNext(); ) {
963 Node n = (Node)j.next();
964 if (!n.getEscapes()) {
965 n.setEscapes();
966 if ((TRACE_CHANGE && !this.change) || TRACE) {
967 out.println("Changed! Node "+n+" escapes");
968 }
969 this.change = true;
970 }
971
972 }
973 }
974 ReturnValueNode rvn = caller.getRVN(mc);
975 if (rvn != null) {
976 UnknownTypeNode utn = UnknownTypeNode.get((jq_Reference)targetMethod.getReturnType());
977 if (TRACE) out.println("Adding return mapping "+rvn+" to "+utn);
978 OutsideNode on = rvn;
979 while (on.skip != null) on = on.skip;
980 addInclusionEdge(on, utn, mc);
981 }
982 ThrownExceptionNode ten = caller.getTEN(mc);
983 if (ten != null) {
984 UnknownTypeNode utn = UnknownTypeNode.get((jq_Reference)PrimordialClassLoader.getJavaLangObject());
985 if (TRACE) out.println("Adding thrown mapping "+ten+" to "+utn);
986 OutsideNode on = ten;
987 while (on.skip != null) on = on.skip;
988 addInclusionEdge(on, utn, mc);
989 }
990 }
991
992 void addParameterAndReturnMappings(MethodSummary caller, ProgramLocation mc, MethodSummary callee) {
993 if (TRACE) out.println("Adding parameter and return mappings for "+mc+" from "+caller.getMethod()+" to "+callee.getMethod());
994
995 jq_Type[] paramTypes = mc.getParamTypes();
996 for (int i=0; i<paramTypes.length; ++i) {
997
998 if (i >= callee.getNumOfParams()) break;
999 ParamNode pn = callee.getParamNode(i);
1000 if (pn == null) continue;
1001 PassedParameter pp = new PassedParameter(mc, i);
1002 Set s = caller.getNodesThatCall(pp);
1003 if (TRACE) out.println("Adding parameter mapping "+pn+" to set "+s);
1004 OutsideNode on = pn;
1005 while (on.skip != null) on = on.skip;
1006 addInclusionEdges(on, s, mc);
1007 }
1008 ReturnValueNode rvn = caller.getRVN(mc);
1009 if (rvn != null) {
1010 Set s = callee.getReturned();
1011 if (TRACE) out.println("Adding return mapping "+rvn+" to set "+s);
1012 OutsideNode on = rvn;
1013 while (on.skip != null) on = on.skip;
1014 addInclusionEdges(on, s, mc);
1015 }
1016 ThrownExceptionNode ten = caller.getTEN(mc);
1017 if (ten != null) {
1018 Set s = callee.getThrown();
1019 if (TRACE) out.println("Adding thrown mapping "+ten+" to set "+s);
1020 OutsideNode on = ten;
1021 while (on.skip != null) on = on.skip;
1022 addInclusionEdges(on, s, mc);
1023 }
1024 }
1025
1026 void addInclusionBackEdge(OutsideNode n, Node n2) {
1027 Set s2 = (Set) nodeToIncomingInclusionEdges.get(n2);
1028 if (s2 == null) {
1029 nodeToIncomingInclusionEdges.put(n2, s2 = inclusionEdgeSetFactory.makeSet());
1030 }
1031 s2.add(n);
1032 }
1033
1034 void addInclusionBackEdges(OutsideNode n, Set s) {
1035 for (Iterator i=s.iterator(); i.hasNext(); ) {
1036 Object o = i.next();
1037 if (o instanceof OutsideNode) {
1038 OutsideNode on = (OutsideNode) o;
1039 while (on.skip != null) {
1040 on = on.skip;
1041 }
1042 o = on;
1043 }
1044 addInclusionBackEdge(n, (Node) o);
1045 }
1046 }
1047
1048 boolean addInclusionEdges(OutsideNode n, Set s, Object mc) {
1049 if (VerifyAssertions) Assert._assert(n.skip == null);
1050 Set s2 = (Set)nodeToInclusionEdges.get(n);
1051 if (s2 == null) {
1052 s = inclusionEdgeSetFactory.makeSet(s);
1053 nodeToInclusionEdges.put(n, s);
1054 if (INCLUSION_BACK_EDGES)
1055 addInclusionBackEdges(n, s);
1056 if ((TRACE_CHANGE && !this.change) || TRACE) {
1057 out.println("Changed! New set of inclusion edges for node "+n);
1058 }
1059 this.change = true;
1060 if (TRACK_CHANGES) {
1061
1062
1063 if (cacheContains(n)) {
1064 for (Iterator i=s.iterator(); i.hasNext(); ) {
1065 Object o = i.next();
1066 if (o instanceof OutsideNode) {
1067 if (TRACE) out.println("Adding "+n+"->"+o+" as an unpropagated edge...");
1068 recordUnpropagatedEdge(n, (OutsideNode)o);
1069 }
1070 }
1071 }
1072 }
1073 if (TRACK_REASONS) {
1074 for (Iterator i=s.iterator(); i.hasNext(); ) {
1075 Object o = i.next();
1076 edgesToReasons.put(new Pair(n, o), mc);
1077 }
1078 }
1079 return true;
1080 } else {
1081 for (Iterator i=s.iterator(); i.hasNext(); ) {
1082 Object o = i.next();
1083 if (o instanceof OutsideNode) {
1084 OutsideNode on = (OutsideNode)o;
1085 while (on.skip != null) {
1086 on = on.skip;
1087 }
1088 o = on;
1089 }
1090 if (n == o) continue;
1091 if (s2.add(o)) {
1092 if (INCLUSION_BACK_EDGES)
1093 addInclusionBackEdge(n, (Node) o);
1094 if ((TRACE_CHANGE && !this.change) || TRACE) {
1095 out.println("Changed! New inclusion edge for node "+n+": "+o);
1096 }
1097 this.change = true;
1098 if (TRACK_CHANGES) {
1099 if (o instanceof OutsideNode) {
1100
1101
1102 if (cacheContains(n)) {
1103 if (TRACE) out.println("Adding "+n+"->"+o+" as an unpropagated edge...");
1104 recordUnpropagatedEdge(n, (OutsideNode)o);
1105 }
1106 }
1107 }
1108 if (TRACK_REASONS) {
1109 edgesToReasons.put(new Pair(n, o), mc);
1110 }
1111 }
1112 }
1113 return false;
1114 }
1115 }
1116
1117 void addInclusionEdge(OutsideNode n, Node s, Object mc) {
1118 if (VerifyAssertions) Assert._assert(n.skip == null);
1119 if (s instanceof OutsideNode) {
1120 OutsideNode on = (OutsideNode)s;
1121 while (on.skip != null) {
1122 on = on.skip;
1123 }
1124 s = on;
1125 }
1126 if (n == s) return;
1127 Set s2 = (Set)nodeToInclusionEdges.get(n);
1128 if (s2 == null) {
1129 s2 = inclusionEdgeSetFactory.makeSet(); s2.add(s);
1130 nodeToInclusionEdges.put(n, s2);
1131 if (INCLUSION_BACK_EDGES)
1132 addInclusionBackEdge(n, s);
1133 if ((TRACE_CHANGE && !this.change) || TRACE) {
1134 out.println("Changed! New set of inclusion edges for node "+n);
1135 }
1136 this.change = true;
1137 if (TRACK_CHANGES) {
1138 if (s instanceof OutsideNode) {
1139
1140
1141 if (cacheContains(n)) {
1142 if (TRACE) out.println("Adding "+n+"->"+s+" as an unpropagated edge...");
1143 recordUnpropagatedEdge(n, (OutsideNode)s);
1144 }
1145 }
1146 }
1147 if (TRACK_REASONS) {
1148 edgesToReasons.put(new Pair(n, s), mc);
1149 }
1150 } else if (s2.add(s)) {
1151 if (INCLUSION_BACK_EDGES)
1152 addInclusionBackEdge(n, s);
1153 if ((TRACE_CHANGE && !this.change) || TRACE) {
1154 out.println("Changed! New inclusion edge for node "+n+": "+s);
1155 }
1156 this.change = true;
1157 if (TRACK_CHANGES) {
1158 if (s instanceof OutsideNode) {
1159
1160
1161 if (cacheContains(n)) {
1162 if (TRACE) out.println("Adding "+n+"->"+s+" as an unpropagated edge...");
1163 recordUnpropagatedEdge(n, (OutsideNode)s);
1164 }
1165 }
1166 }
1167 if (TRACK_REASONS) {
1168 edgesToReasons.put(new Pair(n, s), mc);
1169 }
1170 }
1171 }
1172
1173 Set getInclusionEdges(Node n) { return (Set)nodeToInclusionEdges.get(n); }
1174
1175 Set getFromCache(OutsideNode n) {
1176 if (USE_SOFT_REFERENCES) {
1177 java.lang.ref.SoftReference r = (java.lang.ref.SoftReference)nodeToConcreteNodes.get(n);
1178 return r != null ? (Set)r.get() : null;
1179 } else {
1180 return (Set)nodeToConcreteNodes.get(n);
1181 }
1182 }
1183
1184 void addToCache(OutsideNode n, Set s) {
1185 if (USE_SOFT_REFERENCES) {
1186 nodeToConcreteNodes.put(n, new java.lang.ref.SoftReference(s));
1187 } else {
1188 nodeToConcreteNodes.put(n, s);
1189 }
1190 }
1191
1192 boolean cacheContains(OutsideNode n) {
1193
1194 if (false) {
1195 java.lang.ref.SoftReference r = (java.lang.ref.SoftReference)nodeToConcreteNodes.get(n);
1196 return r == null || r.get() == null;
1197 } else {
1198 return nodeToConcreteNodes.containsKey(n);
1199 }
1200 }
1201
1202 static boolean checkInvalidFieldAccess(Node n, jq_Field f) {
1203 jq_Reference rtype = n.getDeclaredType();
1204 if (rtype == null) {
1205 if (TRACE) out.println("Node "+n+" is null, so cannot hold field access");
1206 return true;
1207 }
1208 if (MethodSummary.IGNORE_INSTANCE_FIELDS) return false;
1209 if (f == null) {
1210 if (rtype instanceof jq_Class) {
1211 if (TRACE) out.println("Node "+n+" is a class type, so it cannot hold array access");
1212 return true;
1213 }
1214 } else {
1215 if (!(rtype instanceof jq_Class)) {
1216 if (TRACE) out.println("Node "+n+" is an array type, so it cannot hold field access");
1217 return true;
1218 }
1219 jq_Class rclass = (jq_Class)rtype;
1220 rclass.load();
1221 if (rclass.getInstanceField(f.getNameAndDesc()) != f) {
1222 if (TRACE) out.println("Node "+n+" does not contain field "+f);
1223 return true;
1224 }
1225 }
1226 return false;
1227 }
1228
1229
1230 void addEdgesFromConcreteNodes(Node from, jq_Field f, Set to) {
1231 Set s = getConcreteNodes(from);
1232 if (TRACE) out.println("Node "+from+" corresponds to concrete nodes "+s);
1233 for (Iterator i=s.iterator(); i.hasNext(); ) {
1234 Node n = (Node)i.next();
1235 if (checkInvalidFieldAccess(n, f)) continue;
1236 if (n.addEdges(f, to)) {
1237 if ((TRACE_CHANGE && !this.change) || TRACE) {
1238 out.println("Changed! New edges for concrete node "+n+"."+f+": "+to);
1239 }
1240 if (TRACK_CHANGED_FIELDS) newChangedFields.add(f);
1241 this.change = true;
1242 }
1243 }
1244 }
1245
1246
1247 void addEdgesFromConcreteNodes(Node from, jq_Field f, Node to) {
1248 Set s = getConcreteNodes(from);
1249 if (TRACE) out.println("Node "+from+" corresponds to concrete nodes "+s);
1250 for (Iterator i=s.iterator(); i.hasNext(); ) {
1251 Node n = (Node)i.next();
1252 if (checkInvalidFieldAccess(n, f)) continue;
1253 if (n.addEdge(f, to)) {
1254 if ((TRACE_CHANGE && !this.change) || TRACE) {
1255 out.println("Changed! New edge for concrete node "+n+"."+f+": "+to);
1256 }
1257 if (TRACK_CHANGED_FIELDS) newChangedFields.add(f);
1258 this.change = true;
1259 }
1260 }
1261 }
1262
1263
1264 void addGlobalEdges(OutsideNode from, jq_Field f) {
1265 Set result = GlobalNode.GLOBAL.getNonEscapingEdges(f);
1266 while (from.skip != null) from = from.skip;
1267 FieldNode fn = FieldNode.get(GlobalNode.GLOBAL, f, null);
1268 addInclusionEdges(from, result, fn);
1269 }
1270
1271
1272 void addGlobalEdges(Set from, jq_Field f) {
1273 Set result = GlobalNode.GLOBAL.getNonEscapingEdges(f);
1274 FieldNode fn = FieldNode.get(GlobalNode.GLOBAL, f, null);
1275 for (Iterator j=from.iterator(); j.hasNext(); ) {
1276 OutsideNode n2 = (OutsideNode)j.next();
1277 while (n2.skip != null) n2 = n2.skip;
1278 addInclusionEdges(n2, result, fn);
1279 }
1280 }
1281
1282
1283 void addInclusionEdgesToConcreteNodes(Set from, Node base, jq_Field f) {
1284 Set s = getConcreteNodes(base);
1285 if (TRACE) out.println("Node "+base+" corresponds to concrete nodes "+s);
1286 Set result = NodeSet.FACTORY.makeSet();
1287 for (Iterator j=s.iterator(); j.hasNext(); ) {
1288 Node n2 = (Node)j.next();
1289 n2.getAllEdges(f, result);
1290 }
1291 if (TRACE) out.println("Edges from "+base+((f==null)?"[]":("."+f.getName()))+" : "+result);
1292 for (Iterator j=from.iterator(); j.hasNext(); ) {
1293 OutsideNode n2 = (OutsideNode)j.next();
1294 while (n2.skip != null) n2 = n2.skip;
1295 addInclusionEdges(n2, result, base);
1296 }
1297 }
1298
1299
1300 void addInclusionEdgesToConcreteNodes(OutsideNode from, Node base, jq_Field f) {
1301 Set s = getConcreteNodes(base);
1302 if (TRACE) out.println("Node "+base+" corresponds to concrete nodes "+s);
1303 Set result = NodeSet.FACTORY.makeSet();
1304 for (Iterator j=s.iterator(); j.hasNext(); ) {
1305 Node n2 = (Node)j.next();
1306 n2.getAllEdges(f, result);
1307 }
1308 if (TRACE) out.println("Edges from "+base+((f==null)?"[]":("."+f.getName()))+" : "+result);
1309 while (from.skip != null) from = from.skip;
1310 addInclusionEdges(from, result, base);
1311 }
1312
1313 Set getConcreteNodes(Node from, AccessPath ap) {
1314 Set s = getConcreteNodes(from);
1315 if (ap == null) return s;
1316 jq_Field f = ap.first();
1317 Set result = NodeSet.FACTORY.makeSet();
1318 for (Iterator j=s.iterator(); j.hasNext(); ) {
1319 Node n2 = (Node)j.next();
1320 n2.getAllEdges(f, result);
1321 }
1322 Set result2 = NodeSet.FACTORY.makeSet();
1323 ap = ap.next();
1324 for (Iterator j=result.iterator(); j.hasNext(); ) {
1325 Node n2 = (Node)j.next();
1326 result2.addAll(getConcreteNodes(n2, ap));
1327 }
1328 return result2;
1329 }
1330
1331 Set getConcreteNodes(Node from) {
1332 if (from instanceof OutsideNode)
1333 return getConcreteNodes((OutsideNode)from, (Path)null);
1334 else
1335 return Collections.singleton(from);
1336 }
1337
1338 boolean temp_change;
1339
1340 Set getConcreteNodes(OutsideNode from, Path p) {
1341 while (from.skip != null) {
1342 from = from.skip;
1343 }
1344 if (from.visited) {
1345 if (TRACE_CYCLES) out.println("cycle detected! node="+from+" path="+p);
1346 Set s = (Set)nodeToInclusionEdges.get(from);
1347 if (VerifyAssertions) Assert._assert(s != null);
1348 for (;; p = p.cdr()) {
1349 OutsideNode n = p.car();
1350 if (TRACK_CHANGES) markCollapsedNode(n);
1351 if (n == from) break;
1352 if (TRACE) out.println("next in path: "+n+", merging into: "+from);
1353 if (VerifyAssertions) Assert._assert(n.skip == null);
1354 n.skip = from;
1355 Set s2 = (Set)nodeToInclusionEdges.get(n);
1356 if (TRACE) out.println("Set of inclusion edges from node "+n+": "+s2);
1357 s.addAll(s2);
1358 nodeToInclusionEdges.put(n, s);
1359 if (INCLUSION_BACK_EDGES)
1360 addInclusionBackEdges(n, s);
1361 }
1362 for (Iterator i=s.iterator(); i.hasNext(); ) {
1363 Object o = i.next();
1364 if (o instanceof OutsideNode) {
1365 OutsideNode on = (OutsideNode)o;
1366 while (on.skip != null) on = on.skip;
1367 o = on;
1368 }
1369 if (from == o) {
1370 if (TRACE) out.println("Node "+from+" contains transitive self-edge, removing.");
1371 i.remove();
1372 }
1373 }
1374 if (TRACE) out.println("Final set of inclusion edges from node "+from+": "+s);
1375 return null;
1376 }
1377 Set result = getFromCache(from);
1378 boolean brand_new = false;
1379 if (REUSE_CACHES) {
1380 if (result == null) {
1381 if (TRACE) out.println("No cache for "+from+" yet, creating.");
1382 result = cacheSetFactory.makeSet();
1383 addToCache(from, result);
1384 brand_new = true;
1385 } else {
1386 Object b = cacheIsCurrent.get(from);
1387 if (b != null) {
1388 if (TRACE) out.println("Cache for "+from+" is current: "+result+" changed since last iteration: "+b);
1389 if (TRACK_CHANGES) this.temp_change = ((Boolean)b).booleanValue();
1390 return result;
1391 } else {
1392 if (TRACE) out.println("Cache for "+from+" "+result+" is not current, updating.");
1393 }
1394 }
1395 } else {
1396 if (result != null) {
1397 if (TRACE) out.println("Using cached result for "+from+".");
1398 return result;
1399 }
1400 result = cacheSetFactory.makeSet();
1401 addToCache(from, result);
1402 }
1403 Set s = (Set)nodeToInclusionEdges.get(from);
1404 if (s == null) {
1405 if (TRACE) out.println("No inclusion edges for "+from+", returning.");
1406 if (TRACK_CHANGES) {
1407 cacheIsCurrent.put(from, Boolean.FALSE);
1408 this.temp_change = false;
1409 } else if (REUSE_CACHES) {
1410 cacheIsCurrent.put(from, from);
1411 }
1412 return result;
1413 }
1414 p = new Path(from, p);
1415 boolean local_change = false;
1416 for (;;) {
1417 Iterator i = s.iterator();
1418 for (;;) {
1419 if (!i.hasNext()) {
1420 if (TRACE) out.println("Finishing exploring "+from+", change in cache="+local_change+", cache="+result);
1421 if (REUSE_CACHES) {
1422 if (TRACK_CHANGES) {
1423 cacheIsCurrent.put(from, local_change?Boolean.TRUE:Boolean.FALSE);
1424 this.temp_change = local_change;
1425 } else {
1426 cacheIsCurrent.put(from, from);
1427 }
1428 }
1429 return result;
1430 }
1431 Node to = (Node)i.next();
1432 if (to instanceof OutsideNode) {
1433 if (TRACE) out.println("Visiting inclusion edge "+from+" --> "+to+"...");
1434 from.visited = true;
1435 Set s2 = getConcreteNodes((OutsideNode)to, p);
1436 from.visited = false;
1437 if (from.skip != null) {
1438 if (TRACE) out.println("Node "+from+" is skipped...");
1439 return null;
1440 }
1441 if (s2 == null) {
1442 if (TRACE) out.println("Nodes were merged into "+from);
1443 if (TRACE) out.println("redoing iteration on "+s);
1444 if (TRACK_CHANGES) brand_new = true;
1445 if (VerifyAssertions) Assert._assert(nodeToInclusionEdges.get(from) == s);
1446 break;
1447 } else {
1448 if (TRACK_CHANGES) {
1449 boolean b = removeUnpropagatedEdge(from, (OutsideNode)to);
1450 if (!brand_new && !b && !this.temp_change) {
1451 if (TRACE) out.println("No change in cache of target "+to+", skipping union operation");
1452 if (VerifyAssertions) Assert._assert(result.containsAll(s2), from+" result "+result+" should contain all of "+to+" result "+s2);
1453 continue;
1454 }
1455 }
1456 boolean change_from_union;
1457 if (USE_SET_REPOSITORY) {
1458 Set result2 = ((SetRepository.SharedSet)result).copyAndAddAll(s2, false);
1459 if (result != result2) {
1460 change_from_union = true;
1461 addToCache(from, result = result2);
1462 } else {
1463 change_from_union = false;
1464 }
1465 } else {
1466 change_from_union = result.addAll(s2);
1467 }
1468 if (change_from_union) {
1469 if (TRACE) out.println("Unioning cache of target "+to+" changed our cache");
1470 local_change = true;
1471 }
1472 }
1473 } else {
1474 boolean change_from_add;
1475 if (USE_SET_REPOSITORY) {
1476 Set result2 = ((SetRepository.SharedSet)result).copyAndAddAll(Collections.singleton(to), false);
1477 if (result != result2) {
1478 change_from_add = true;
1479 addToCache(from, result = result2);
1480 } else {
1481 change_from_add = false;
1482 }
1483 } else {
1484 change_from_add = result.add(to);
1485 }
1486 if (change_from_add) {
1487 if (TRACE) out.println("Adding concrete node "+to+" changed our cache");
1488 local_change = true;
1489 }
1490 }
1491 }
1492 }
1493 }
1494
1495 void recordUnpropagatedEdge(OutsideNode from, OutsideNode to) {
1496 unpropagatedEdges.add(new Pair(from, to));
1497 }
1498 boolean removeUnpropagatedEdge(OutsideNode from, OutsideNode to) {
1499 if (unpropagatedEdges.remove(getPair(from, to))) return true;
1500 Set s = (Set)collapsedNodes.get(to);
1501 if (s == null) return false;
1502 if (s.contains(from)) return false;
1503 s.add(from);
1504 return true;
1505 }
1506 void markCollapsedNode(OutsideNode n) {
1507 Set s = (Set)collapsedNodes.get(n);
1508 if (s == null) collapsedNodes.put(n, s = new HashSet());
1509 else s.clear();
1510 }
1511
1512 final Pair my_pair_list = new Pair(null, null);
1513 public Pair getPair(Object left, Object right) {
1514 my_pair_list.left = left; my_pair_list.right = right; return my_pair_list;
1515 }
1516
1517 public static class Path {
1518 private final OutsideNode s;
1519 private final Path next;
1520 Path(OutsideNode s, Path n) { this.s = s; this.next = n; }
1521 OutsideNode car() { return s; }
1522 Path cdr() { return next; }
1523 public String toString() {
1524 if (next == null) return s.toString();
1525 return s.toString()+"->"+next.toString();
1526 }
1527 }
1528
1529 public CallGraph getCallGraph() {
1530 return CallGraph.makeCallGraph(rootSet, callSiteToTargets);
1531 }
1532
1533 public static class AccessPath {
1534 jq_Field f;
1535 Node node;
1536 AccessPath n;
1537
1538 public int length() {
1539 if (n == null) return 1;
1540 return 1+n.length();
1541 }
1542
1543 public jq_Field first() { return f; }
1544
1545 public AccessPath next() { return n; }
1546
1547 public String toString() {
1548 String s;
1549 if (f == null) s = "[]";
1550 else s = "."+f.getName().toString();
1551 if (n == null) return s;
1552 return s+n.toString();
1553 }
1554
1555 public boolean equals(Object o) {
1556 return equals((AccessPath)o);
1557 }
1558
1559 public boolean equals(AccessPath that) {
1560 if (that == null) return false;
1561 if (this.f != that.f) return false;
1562 if (this.n == that.n) return true;
1563 if (this.n == null || that.n == null) return false;
1564 return this.n.equals(that.n);
1565 }
1566
1567 public int hashCode() {
1568 int hashcode = f==null?0x1337:f.hashCode();
1569 if (n != null) hashcode ^= (n.hashCode() << 1);
1570 return hashcode;
1571 }
1572
1573 public AccessPath findNode(Node node) {
1574 if (this.node == node) return this;
1575 else if (this.n == null) return null;
1576 else return this.n.findNode(node);
1577 }
1578 public static AccessPath create(jq_Field f, Node node, AccessPath n) {
1579 AccessPath ap;
1580 if (n != null) {
1581 ap = n.findNode(node);
1582 if (ap != null) return null;
1583 if (n.length() >= 3) return null;
1584 }
1585 ap = new AccessPath();
1586 ap.f = f; ap.node = node; ap.n = n;
1587 return ap;
1588 }
1589 }
1590
1591 }