1
2
3
4 package joeq.Compiler.Quad;
5
6 import java.util.Collection;
7 import java.util.Comparator;
8 import java.util.HashMap;
9 import java.util.HashSet;
10 import java.util.Iterator;
11 import java.util.LinkedHashMap;
12 import java.util.LinkedHashSet;
13 import java.util.LinkedList;
14 import java.util.List;
15 import java.util.Map;
16 import java.util.Set;
17 import java.util.SortedSet;
18 import java.util.TreeSet;
19 import java.io.BufferedReader;
20 import java.io.IOException;
21 import java.io.InputStreamReader;
22 import joeq.Class.jq_Class;
23 import joeq.Class.jq_Field;
24 import joeq.Class.jq_Method;
25 import joeq.Class.jq_Type;
26 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary;
27 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.CallSite;
28 import joeq.Compiler.Analysis.FlowInsensitive.MethodSummary.PassedParameter;
29 import joeq.Compiler.Analysis.IPA.ProgramLocation;
30 import joeq.Compiler.Quad.AndersenPointerAnalysis.AccessPath;
31 import joeq.Main.HostedVM;
32 import jwutil.collections.Filter;
33 import jwutil.collections.FilterIterator;
34 import jwutil.collections.LinearSet;
35 import jwutil.collections.Pair;
36 import jwutil.util.Assert;
37
38 /***
39 *
40 * @author John Whaley <jwhaley@alum.mit.edu>
41 * @version $Id: PointerExplorer.java 2465 2006-06-07 23:03:17Z joewhaley $
42 */
43 public class PointerExplorer {
44
45 public static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
46
47 public static jq_Method getMethod(Set
48 int which, count = 0;
49 for (Iterator i=set.iterator(); i.hasNext(); ) {
50 jq_Method m = (jq_Method)i.next();
51 System.out.println((++count)+": "+m);
52 }
53 for (;;) {
54 System.out.print("Which method? ");
55 String s = in.readLine();
56 try {
57 which = Integer.parseInt(s);
58 if ((which >= 1) && (which <= count))
59 break;
60 System.out.println("Out of range: "+which);
61 } catch (NumberFormatException x) {
62 System.out.println("Not a number: "+s);
63 }
64 }
65 for (Iterator i=set.iterator(); ; ) {
66 jq_Method m = (jq_Method)i.next();
67 if ((++count) == which) return m;
68 }
69 }
70
71 public static jq_Method getMethod() throws IOException {
72 return getMethod((String[])null, 0);
73 }
74
75 public static jq_Method getMethod(String[] args, int start) throws IOException {
76 String mainClassName;
77 if (args != null && args.length > start) {
78 mainClassName = args[start];
79 } else {
80 System.out.print("Enter the name of the class: ");
81 mainClassName = in.readLine();
82 }
83 jq_Type t = jq_Type.parseType(mainClassName);
84 if (!(t instanceof jq_Class)) {
85 System.out.println("Error, "+mainClassName+" ("+t+") is not a valid class.");
86 System.exit(-1);
87 }
88
89 jq_Class klass = (jq_Class)t;
90 klass.prepare();
91 String name = (args != null && args.length > start+1) ? args[start+1] : null;
92 return getMethod(klass, name);
93 }
94
95 public static jq_Method getMethod(jq_Class klass, String name) throws IOException {
96 jq_Method method;
97 if (name != null) {
98 String methodName = name;
99 boolean static_or_instance = false;
100 uphere1:
101 for (;;) {
102 jq_Method[] m = static_or_instance?(jq_Method[])klass.getDeclaredStaticMethods():(jq_Method[])klass.getDeclaredInstanceMethods();
103 for (int i=0; i<m.length; ++i) {
104 if (methodName.equals(m[i].getName().toString())) {
105 method = m[i];
106 break uphere1;
107 }
108 }
109 if (static_or_instance) {
110 System.out.println("Error, no method named "+methodName+" is declared in class "+klass.getName());
111 System.exit(-1);
112 }
113 static_or_instance = true;
114 }
115 } else {
116 boolean static_or_instance = true;
117 uphere2:
118 for (;;) {
119 System.out.println((static_or_instance?"Static":"Instance")+" methods:");
120 jq_Method[] m = static_or_instance?(jq_Method[])klass.getDeclaredStaticMethods():(jq_Method[])klass.getDeclaredInstanceMethods();
121 for (int i=0; i<m.length; ++i) {
122 System.out.println((i+1)+": "+m[i]);
123 }
124 int which;
125 for (;;) {
126 System.out.print("Which method, or "+(static_or_instance?"'i' for instance":"'s' for static")+" methods: ");
127 String s = in.readLine();
128 try {
129 if (s.equalsIgnoreCase("s")) {
130 static_or_instance = true;
131 continue uphere2;
132 }
133 if (s.equalsIgnoreCase("i")) {
134 static_or_instance = false;
135 continue uphere2;
136 }
137 which = Integer.parseInt(s);
138 if ((which >= 1) && (which <= m.length))
139 break;
140 System.out.println("Out of range: "+which);
141 } catch (NumberFormatException x) {
142 System.out.println("Not a number: "+s);
143 }
144 }
145 method = m[which-1];
146 break;
147 }
148 }
149 return method;
150 }
151
152 public static SortedSet sortByNumberOfTargets(Map callGraph) {
153 TreeSet ts = new TreeSet(
154 new Comparator() {
155 public int compare(Object o1, Object o2) {
156 Map.Entry e1 = (Map.Entry)o1;
157 CallSite cs1 = (CallSite)e1.getKey();
158 Set s1 = (Set)e1.getValue();
159 Map.Entry e2 = (Map.Entry)o2;
160 CallSite cs2 = (CallSite)e2.getKey();
161 Set s2 = (Set)e2.getValue();
162 int s1s = s1.size(); int s2s = s2.size();
163 if (s1s < s2s) return 1;
164 else if (s1s > s2s) return -1;
165 else return cs1.toString().compareTo(cs2.toString());
166 }
167 });
168 ts.addAll(callGraph.entrySet());
169 return ts;
170 }
171
172 public static AndersenPointerAnalysis apa;
173 public static Map callGraph;
174 public static Set rootSet = new LinkedHashSet();
175 public static Set selectedCallSites = new LinkedHashSet();
176 public static Map methodToCallSites = new HashMap();
177 public static Map toInline = new LinkedHashMap();
178 public static List inlineCommands = new LinkedList();
179
180 public static void selectCallSites(String desc, Iterator i, Iterator i2) throws IOException {
181 System.out.println("Call sites with "+desc+": ");
182 int count = 0;
183 while (i2.hasNext()) {
184 Map.Entry e = (Map.Entry)i2.next();
185 Set s = (Set)e.getValue();
186 System.out.println((++count)+": "+e.getKey()+"="+s.size()+" targets");
187 }
188 int which;
189 for (;;) {
190 System.out.print("Enter your selection, or 'a' for all: ");
191 String input = in.readLine();
192 if (input.equalsIgnoreCase("a")) {
193 which = -1;
194 break;
195 } else if (input.equalsIgnoreCase("q")) {
196 which = -2;
197 break;
198 } else {
199 try {
200 which = Integer.parseInt(input);
201 if ((which >= 1) && (which <= count))
202 break;
203 } catch (NumberFormatException x) {
204 System.out.println("Cannot parse number: "+input);
205 }
206 }
207 }
208 for (int j=0; j<count; ++j) {
209 Map.Entry e = (Map.Entry)i.next();
210 if (which == j+1 || which == -1)
211 selectedCallSites.add(e.getKey());
212 if (which == j+1) {
213 System.out.println("Selected "+e);
214 }
215 }
216 }
217
218 static void printAllInclusionEdges(HashSet visited, MethodSummary.Node pnode, MethodSummary.Node node, String indent, boolean all, jq_Field f, boolean verbose) throws IOException {
219 if (verbose) System.out.print(indent+"Node: "+node);
220 if (pnode != null) {
221 Object q = apa.edgesToReasons.get(new Pair(pnode, node));
222 if (q != null)
223 if (verbose) System.out.print(" from "+q);
224 }
225 if (visited.contains(node)) {
226 if (verbose) System.out.println(" <duplicate>, skipping.");
227 return;
228 }
229 visited.add(node);
230 if (verbose) System.out.println();
231 if (node instanceof MethodSummary.OutsideNode) {
232 MethodSummary.OutsideNode onode = (MethodSummary.OutsideNode)node;
233 while (onode.skip != null) {
234 if (verbose) System.out.println(indent+onode+" equivalent to "+onode.skip);
235 onode = onode.skip;
236 }
237 if (onode instanceof MethodSummary.FieldNode) {
238 MethodSummary.FieldNode fnode = (MethodSummary.FieldNode)onode;
239 jq_Field field = fnode.getField();
240 Set inEdges = fnode.getAccessPathPredecessors();
241 System.out.println(indent+"Field "+field.getName().toString()+" Parent nodes: "+inEdges);
242 System.out.print(indent+"Type 'w' to find matching writes to parent nodes, 'u' to go up: ");
243 String s = in.readLine();
244 if (s != null) {
245 if (s.equalsIgnoreCase("u")) {
246 for (Iterator it3 = inEdges.iterator(); it3.hasNext(); ) {
247 MethodSummary.Node node4 = (MethodSummary.Node)it3.next();
248 printAllInclusionEdges(visited, null, node4, indent+"<", all, field, true);
249 }
250 } else if (s.equalsIgnoreCase("w")) {
251 for (Iterator it3 = inEdges.iterator(); it3.hasNext(); ) {
252 MethodSummary.Node node4 = (MethodSummary.Node)it3.next();
253 printAllInclusionEdges(visited, null, node4, indent+"<", all, field, false);
254 }
255 }
256 }
257 }
258 Set outEdges = (Set)apa.nodeToInclusionEdges.get(onode);
259 if (outEdges != null) {
260 boolean yes = all || !verbose;
261 if (!yes) {
262 System.out.print(indent+outEdges.size()+" out edges, print them? ('y' for yes, 'a' for all) ");
263 String s = in.readLine();
264 if (s.equalsIgnoreCase("y")) yes = true;
265 else if (s.equalsIgnoreCase("a")) all = yes = true;
266 }
267 if (yes) {
268 for (Iterator it3 = outEdges.iterator(); it3.hasNext(); ) {
269 MethodSummary.Node node2 = (MethodSummary.Node)it3.next();
270 printAllInclusionEdges(visited, onode, node2, indent+" ", all, null, verbose);
271 }
272 }
273 }
274 } else {
275 Set s = node.getNonEscapingEdges(f);
276 if (s.size() > 0) {
277 System.out.println(indent+s.size()+" write edges match field "+((f==null)?"[]":f.getName().toString()));
278 for (Iterator i=s.iterator(); i.hasNext(); ) {
279 MethodSummary.Node node2 = (MethodSummary.Node)i.next();
280
281
282
283 printAllInclusionEdges(visited, null, node2, indent+">", all, null, verbose);
284 }
285 }
286 }
287 }
288
289 public static class InlineSet extends java.util.AbstractSet {
290 final Set backing_set;
291 boolean is_complete;
292
293 public InlineSet(Set s, boolean c) {
294 this.backing_set = s;
295 this.is_complete = c;
296 }
297
298 public boolean isComplete() { return is_complete; }
299
300 public Iterator iterator() { return backing_set.iterator(); }
301 public int size() { return backing_set.size(); }
302 public boolean containsAll(Collection arg0) {
303 return backing_set.containsAll(arg0);
304 }
305
306 }
307
308 public static void recalculateInliningCompleteness() {
309 int total = 0;
310 for (Iterator it = toInline.entrySet().iterator(); it.hasNext(); ) {
311 Map.Entry e = (Map.Entry) it.next();
312 CallSite cs = (CallSite) e.getKey();
313 InlineSet is = (InlineSet) e.getValue();
314
315 Set targets = (Set) callGraph.get(cs);
316 if (targets != null && is.containsAll(targets)) {
317 total++;
318 is.is_complete = true;
319 }
320 }
321 System.out.println(total+" inlining sites are complete.");
322 }
323
324 public static void doInlining(Set inline) {
325 for (Iterator it = inline.iterator(); it.hasNext(); ) {
326 Map.Entry e = (Map.Entry)it.next();
327 CallSite cs = (CallSite)e.getKey();
328 MethodSummary caller = MethodSummary.getSummary(CodeCache.getCode((jq_Method)cs.getCaller().getMethod()));
329 ProgramLocation mc = cs.getLocation();
330 cs = new CallSite(caller, mc);
331 InlineSet targets = (InlineSet)e.getValue();
332 Iterator it2 = targets.iterator();
333 if (!it2.hasNext()) {
334 System.out.println("No targets to inline for "+cs);
335 } else {
336 for (;;) {
337 jq_Method target_m = (jq_Method)it2.next();
338 boolean removeCall = !it2.hasNext() && targets.isComplete();
339 if (target_m.getBytecode() == null) {
340
341 } else {
342 MethodSummary callee = MethodSummary.getSummary(CodeCache.getCode(target_m));
343 MethodSummary caller2 = caller.copy();
344 MethodSummary callee2 = callee.copy();
345 if (caller == callee || callee.getCalls().contains(mc)) {
346 System.out.println("Inlining of recursive call not supported yet: "+cs);
347 } else if (!caller.getCalls().contains(mc)) {
348 System.out.println("Error: cannot find call site "+cs);
349 } else {
350 try {
351 MethodSummary.instantiate(caller, mc, callee, removeCall);
352 } catch (Throwable t) {
353 System.err.println("EXCEPTION while instantiating "+callee+" into "+caller+" mc="+mc);
354 t.printStackTrace();
355 MethodSummary.TRACE_INST = true;
356 MethodSummary.TRACE_INTRA = true;
357 MethodSummary.TRACE_INTER = true;
358 MethodSummary.instantiate(caller2, mc, callee2, removeCall);
359 }
360 }
361 }
362 if (!it2.hasNext()) break;
363 }
364 }
365 }
366 }
367
368 static int setDepth(LinkedHashSet path, HashMap visited, jq_Method m) {
369 if (path.contains(m)) {
370 System.out.println("Attempting to inline recursive cycle: method "+m);
371 return -1;
372 }
373 Integer result = (Integer)visited.get(m);
374 if (result != null) return result.intValue();
375 path.add(m);
376 HashSet s = (HashSet)methodToCallSites.get(m);
377 int current = 0;
378 if (s != null) {
379 uphere:
380 for (Iterator i=s.iterator(); i.hasNext(); ) {
381 CallSite cs = (CallSite)i.next();
382 InlineSet t = (InlineSet)toInline.get(cs);
383 for (Iterator j=t.iterator(); j.hasNext(); ) {
384 jq_Method m2 = (jq_Method)j.next();
385 int r = setDepth(path, visited, m2);
386 if (r == -1) {
387 System.out.println("Removing call site "+cs+" from inline set");
388 i.remove();
389 toInline.remove(cs);
390 continue uphere;
391 }
392 current = Math.max(current, r+1);
393 }
394 }
395 }
396 visited.put(m, result = new Integer(current));
397 path.remove(m);
398 return current;
399 }
400
401 public static Set[] reorderInlineSites(Map toInline) {
402 if (toInline.isEmpty()) return new Set[0];
403
404 System.out.println("Reordering call sites to inline...");
405
406
407 methodToCallSites.clear();
408 for (Iterator i=toInline.keySet().iterator(); i.hasNext(); ) {
409 CallSite cs = (CallSite)i.next();
410 HashSet s = (HashSet)methodToCallSites.get(cs.getCaller().getMethod());
411 if (s == null) {
412 methodToCallSites.put(cs.getCaller().getMethod(), s = new HashSet());
413 }
414 s.add(cs);
415 }
416
417 System.out.println(methodToCallSites.size()+" methods contain sites to inline");
418
419 HashMap depths = new HashMap();
420 LinkedHashSet path = new LinkedHashSet();
421 int maxDepth = 0;
422 for (Iterator j=methodToCallSites.keySet().iterator(); j.hasNext(); ) {
423 jq_Method m = (jq_Method)j.next();
424 if (depths.containsKey(m)) continue;
425 int depth = setDepth(path, depths, m);
426
427 maxDepth = Math.max(maxDepth, depth+1);
428 }
429 System.out.println("Longest inlining chain: "+maxDepth);
430 Set[] result = new Set[maxDepth];
431 for (int i=0; i<maxDepth; ++i) {
432 result[i] = new LinkedHashSet();
433 }
434 for (Iterator i=depths.entrySet().iterator(); i.hasNext(); ) {
435 Map.Entry e = (Map.Entry)i.next();
436 jq_Method m = (jq_Method)e.getKey();
437 Integer j = (Integer)e.getValue();
438 Set s = (Set)methodToCallSites.get(m);
439 if (s != null) {
440 for (Iterator k = s.iterator(); k.hasNext(); ) {
441 final CallSite cs = (CallSite)k.next();
442 final InlineSet targets = (InlineSet)toInline.get(cs);
443 result[j.intValue()].add(new Map.Entry() {
444 public Object getKey() { return cs; }
445 public Object getValue() { return targets; }
446 public Object setValue(Object x) { throw new UnsupportedOperationException(); }
447 });
448 }
449 }
450 }
451 return result;
452 }
453
454 public static void doInlining() {
455 if (!toInline.isEmpty()) {
456 inlineCommands.add(toInline);
457 }
458 for (Iterator ii=inlineCommands.iterator(); ii.hasNext(); ) {
459 toInline = (LinkedHashMap) ii.next();
460 System.out.println("Inlining "+toInline.size()+" call sites.");
461 Set[] sitesToInline = reorderInlineSites(toInline);
462 for (int i=0; i<sitesToInline.length; ++i) {
463 doInlining(sitesToInline[i]);
464 }
465 }
466 toInline = new LinkedHashMap();
467 }
468
469 static int setDepth_clone(HashMap methodToSpecializations,
470 HashMap to_clone,
471 LinkedHashSet path,
472 HashMap visited,
473 jq_Method m) {
474 if (path.contains(m)) {
475 System.out.println("Attempting to clone recursive cycle: method "+m);
476 return -1;
477 }
478 Integer result = (Integer) visited.get(m);
479 if (result != null) return result.intValue();
480 path.add(m);
481 Set s = (Set) methodToSpecializations.get(m);
482 int current = 0;
483 if (s != null) {
484 for (Iterator i=s.iterator(); i.hasNext(); ) {
485 Specialization s2 = (Specialization) i.next();
486 Assert._assert(s2.target.getMethod() == m);
487 Set s3 = (Set) to_clone.get(s2);
488 for (Iterator j=s3.iterator(); j.hasNext(); ) {
489 ProgramLocation mc = (ProgramLocation) j.next();
490 jq_Method source_m = mc.getMethod();
491 int r = setDepth_clone(methodToSpecializations, to_clone, path, visited, source_m);
492 if (r == -1) {
493
494
495 continue;
496 }
497 current = Math.max(current, r+1);
498 }
499 if (s3.isEmpty()) {
500 System.out.println("Removed all specializations for method "+m);
501 i.remove();
502 }
503 }
504 }
505 visited.put(m, result = new Integer(current));
506 path.remove(m);
507 return current;
508 }
509
510 public static class Specialization {
511 ControlFlowGraph target;
512 Set
513 Specialization(ControlFlowGraph t, SpecializationParameter s) {
514 this.target = t; this.set = new LinearSet(); this.set.add(s);
515 }
516 Specialization(ControlFlowGraph t, Set s) {
517 this.target = t; this.set = s;
518 }
519 public boolean equals(Object o) {
520 return equals((Specialization) o);
521 }
522 public boolean equals(Specialization that) {
523 if (this.target != that.target) {
524 return false;
525 }
526 if (!this.set.equals(that.set)) {
527 return false;
528 }
529 return true;
530 }
531 public int hashCode() { return target.hashCode() ^ set.hashCode(); }
532
533 public String toString() {
534 return "Specialization of "+target.getMethod()+" on "+set;
535 }
536 }
537
538 public static class SpecializationParameter {
539 int paramNum;
540 AccessPath ap;
541 Set types;
542 SpecializationParameter(int paramNum, AccessPath ap, Set types) {
543 this.paramNum = paramNum; this.ap = ap; this.types = types;
544 }
545 public boolean equals(Object o) {
546 return equals((SpecializationParameter) o);
547 }
548 public boolean equals(SpecializationParameter that) {
549 if (this.paramNum != that.paramNum || !this.types.equals(that.types)) return false;
550 if (this.ap == that.ap) return true;
551 if (this.ap == null || that.ap == null) return false;
552 return this.ap.equals(that.ap);
553 }
554 public int hashCode() {
555 int aphash = ap==null?0:ap.hashCode();
556 return paramNum ^ types.hashCode() ^ aphash;
557 }
558 public String toString() {
559 if (ap == null)
560 return "Param#"+paramNum+" types: "+types;
561 return "Param#"+paramNum+ap.toString()+" types: "+types;
562 }
563 }
564
565 public static void buildCloneCache(HashMap
566 System.out.println(to_clone.size()+" specializations");
567 HashMap methodToSpecializations = new HashMap();
568 for (Iterator i = to_clone.keySet().iterator(); i.hasNext(); ) {
569 Specialization s = (Specialization) i.next();
570 jq_Method target_m = s.target.getMethod();
571 Set s2 = (Set) methodToSpecializations.get(target_m);
572 if (s2 == null) methodToSpecializations.put(target_m, s2 = new LinkedHashSet());
573 boolean change = s2.add(s);
574 Assert._assert(change, s.toString());
575 }
576 System.out.println(methodToSpecializations.size()+" different methods are to be specialized");
577
578 LinkedHashSet path = new LinkedHashSet();
579 HashMap visited = new HashMap();
580 int maxdepth = 0;
581 for (Iterator i = methodToSpecializations.keySet().iterator(); i.hasNext(); ) {
582 jq_Method m = (jq_Method) i.next();
583 int depth = setDepth_clone(methodToSpecializations, to_clone, path, visited, m);
584 maxdepth = Math.max(maxdepth, depth);
585 }
586
587 System.out.println("Max cloning depth: "+maxdepth);
588 Collection[] cloneme = new Collection[maxdepth+1];
589 for (int i=0; i<cloneme.length; ++i) {
590 cloneme[i] = new LinkedList();
591 }
592 for (Iterator i = visited.entrySet().iterator(); i.hasNext(); ) {
593 Map.Entry e = (Map.Entry)i.next();
594 jq_Method m = (jq_Method) e.getKey();
595 Integer ii = (Integer) e.getValue();
596 cloneme[ii.intValue()].add(m);
597 }
598
599 HashMap specialToMS = new HashMap();
600 for (int i=0; i < cloneme.length; ++i) {
601 Collection c = cloneme[i];
602
603 for (Iterator j=c.iterator(); j.hasNext(); ) {
604 jq_Method m = (jq_Method) j.next();
605 Set s2 = (Set) methodToSpecializations.get(m);
606 if (s2 == null) continue;
607 ControlFlowGraph cfg = CodeCache.getCode(m);
608 for (Iterator k=s2.iterator(); k.hasNext(); ) {
609 Specialization special = (Specialization) k.next();
610 MethodSummary ms = MethodSummary.getSummary(cfg).copy();
611 Assert._assert(specialToMS.get(special) == null);
612 specialToMS.put(special, ms);
613 }
614 }
615 }
616 int totalCallSites = 0;
617 for (Iterator i=specialToMS.entrySet().iterator(); i.hasNext(); ) {
618 Map.Entry e = (Map.Entry)i.next();
619 Specialization s = (Specialization) e.getKey();
620 MethodSummary target_ms = (MethodSummary) e.getValue();
621 Set s2 = (Set) to_clone.get(s);
622 totalCallSites += s2.size();
623
624 for (Iterator j=s2.iterator(); j.hasNext(); ) {
625 ProgramLocation mc = (ProgramLocation) j.next();
626 jq_Method source_m = mc.getMethod();
627 Set s3 = (Set) methodToSpecializations.get(source_m);
628 if (s3 != null) {
629 for (Iterator k=s3.iterator(); k.hasNext(); ) {
630 Specialization s4 = (Specialization) k.next();
631 MethodSummary source_ms = (MethodSummary) specialToMS.get(s4);
632 CallSite cs = new CallSite(source_ms, mc);
633 ControlFlowGraph target_cfg = CodeCache.getCode((jq_Method)target_ms.getMethod());
634 MethodSummary.clone_cache.put(new Pair(target_cfg, cs), target_ms);
635
636 }
637 }
638 ControlFlowGraph target_cfg = CodeCache.getCode((jq_Method)target_ms.getMethod());
639 ControlFlowGraph source_cfg = CodeCache.getCode((jq_Method)source_m);
640 MethodSummary source_ms = MethodSummary.getSummary(source_cfg);
641 CallSite cs = new CallSite(source_ms, mc);
642 MethodSummary.clone_cache.put(new Pair(target_cfg, cs), target_ms);
643 }
644 }
645 System.out.println("Specializing a total of "+totalCallSites+" call sites.");
646 }
647
648 public static void main(String[] args) throws IOException {
649 HostedVM.initialize();
650
651 int index = 0; int index0 = -1;
652 while (index != index0 && index < args.length) {
653 index = joeq.Main.TraceFlags.setTraceFlag(args, index0 = index);
654 }
655
656 System.out.println("Select the root method.");
657 jq_Method m = getMethod(args, index);
658 rootSet.add(m);
659 ControlFlowGraph cfg = CodeCache.getCode(m);
660 apa = new AndersenPointerAnalysis(false);
661 apa.addToRootSet(cfg);
662 System.out.println("Performing initial context-insensitive analysis...");
663 long time = System.currentTimeMillis();
664 apa.iterate();
665 time = System.currentTimeMillis() - time;
666 System.out.println("Time to complete: "+time);
667 callGraph = apa.getCallGraph();
668 SortedSet sorted = sortByNumberOfTargets(callGraph);
669
670 for (;;) {
671 System.out.print("Enter command: ");
672 String s = in.readLine();
673 if (s == null) {
674 System.out.println("Exiting.");
675 System.exit(0);
676 }
677 if (s.startsWith("histogram")) {
678
679
680
681
682 Map original = AndersenPointerAnalysis.buildOriginalCallGraph(callGraph);
683 System.out.println("Comparison:");
684 System.out.println(AndersenPointerAnalysis.compareWithOriginal(callGraph, original));
685 continue;
686 }
687 if (s.startsWith("stats")) {
688 System.out.println(apa.computeStats());
689 continue;
690 }
691 if (s.startsWith("callgraph")) {
692 System.out.println(apa.getCallGraph());
693 continue;
694 }
695 if (s.startsWith("addroot")) {
696 m = getMethod();
697 rootSet.add(m);
698
699
700 continue;
701 }
702 if (s.startsWith("trace summary ")) {
703 boolean b = s.substring(14).equals("on");
704 MethodSummary.TRACE_INTRA = b;
705 System.out.println("Trace summary: "+b);
706 continue;
707 }
708 if (s.startsWith("trace inline ")) {
709 boolean b = s.substring(13).equals("on");
710 MethodSummary.TRACE_INTER = b;
711 MethodSummary.TRACE_INST = b;
712 System.out.println("Trace inline: "+b);
713 continue;
714 }
715 if (s.startsWith("trace andersen ")) {
716 boolean b = s.substring(15).equals("on");
717 AndersenPointerAnalysis.TRACE = b;
718 System.out.println("Trace Andersen: "+b);
719 continue;
720 }
721 if (s.startsWith("inline")) {
722 System.out.println("Marking "+selectedCallSites.size()+" call sites for inlining.");
723 int size=0;
724 for (Iterator it = selectedCallSites.iterator(); it.hasNext(); ) {
725 CallSite cs = (CallSite)it.next();
726 Set set = (Set)callGraph.get(cs);
727 if (set == null) {
728 System.out.println("Error: call site "+cs+" not found in call graph.");
729 } else {
730 InlineSet is = new InlineSet(set, true);
731 toInline.put(cs, is);
732 size += set.size();
733 }
734 }
735 System.out.println("Total number of target methods: "+size);
736 continue;
737 }
738 if (s.startsWith("run")) {
739 MethodSummary.clone_cache = null;
740 MethodSummary.clearSummaryCache();
741 doInlining();
742 selectedCallSites.clear();
743 System.gc();
744 apa = new AndersenPointerAnalysis(false);
745 for (Iterator it = rootSet.iterator(); it.hasNext(); ) {
746 m = (jq_Method)it.next();
747 cfg = CodeCache.getCode(m);
748 apa.addToRootSet(cfg);
749 }
750 System.out.println("Re-running context-insensitive analysis...");
751 time = System.currentTimeMillis();
752 try {
753 apa.iterate();
754 } catch (Throwable t) {
755 System.err.println("EXCEPTION while iterating: "+t);
756 t.printStackTrace();
757 }
758 time = System.currentTimeMillis() - time;
759 System.out.println("Time to complete: "+time);
760 callGraph = apa.getCallGraph();
761 sorted = sortByNumberOfTargets(callGraph);
762 continue;
763 }
764 if (s.startsWith("source")) {
765 final jq_Method m2 = getMethod();
766 Filter f = new Filter() {
767 public boolean isElement(Object o) {
768 Map.Entry e = (Map.Entry)o;
769 CallSite cs = (CallSite)e.getKey();
770 return (cs.getCaller().getMethod() == m2);
771 }
772 };
773 FilterIterator it1 = new FilterIterator(sorted.iterator(), f);
774 FilterIterator it2 = new FilterIterator(sorted.iterator(), f);
775 selectCallSites("caller="+m, it1, it2);
776 continue;
777 }
778 if (s.startsWith("targets")) {
779 m = getMethod();
780 int total = 0;
781 for (Iterator it = callGraph.entrySet().iterator(); it.hasNext(); ) {
782 Map.Entry e = (Map.Entry)it.next();
783 Set set = (Set)e.getValue();
784 if (set.contains(m)) {
785 selectedCallSites.add(e.getKey());
786 ++total;
787 }
788 }
789 System.out.println("Selected "+total+" call sites.");
790 continue;
791 }
792 if (s.startsWith("basepointers")) {
793 for (Iterator it = selectedCallSites.iterator(); it.hasNext(); ) {
794 CallSite cs = (CallSite)it.next();
795 System.out.println("For call site: "+cs);
796 MethodSummary ms = cs.getCaller();
797 LinkedHashSet set = new LinkedHashSet();
798 PassedParameter pp = new PassedParameter(cs.getLocation(), 0);
799 ms.getNodesThatCall(pp, set);
800 for (Iterator it2 = set.iterator(); it2.hasNext(); ) {
801 MethodSummary.Node node = (MethodSummary.Node)it2.next();
802 printAllInclusionEdges(new HashSet(), null, node, "", false, null, true);
803 }
804 }
805 continue;
806 }
807 if (s.startsWith("clearselection")) {
808 selectedCallSites.clear();
809 continue;
810 }
811 if (s.startsWith("printselection")) {
812 System.out.println(selectedCallSites);
813 continue;
814 }
815 if (s.startsWith("summary")) {
816 m = getMethod();
817 MethodSummary ms = MethodSummary.getSummary(CodeCache.getCode(m));
818 System.out.println(ms);
819 continue;
820 }
821 if (s.startsWith("printsize ")) {
822 try {
823 final int size = Integer.parseInt(s.substring(10));
824 Filter f = new Filter() {
825 public boolean isElement(Object o) {
826 Map.Entry e = (Map.Entry)o;
827 Set set = (Set)e.getValue();
828 return set.size() >= size;
829 }
830 };
831 FilterIterator it1 = new FilterIterator(sorted.iterator(), f);
832 while (it1.hasNext()) {
833 System.out.println(it1.next());
834 }
835 } catch (NumberFormatException x) {
836 System.out.println("Invalid size: "+s.substring(5));
837 }
838 continue;
839 }
840 if (s.startsWith("selectmultitarget")) {
841 Filter f = new Filter() {
842 public boolean isElement(Object o) {
843 Map.Entry e = (Map.Entry)o;
844 Set set = (Set)e.getValue();
845 return set.size() > 1;
846 }
847 };
848 FilterIterator it1 = new FilterIterator(sorted.iterator(), f);
849 while (it1.hasNext()) {
850 Map.Entry e = (Map.Entry) it1.next();
851 selectedCallSites.add(e.getKey());
852 }
853 System.out.println(selectedCallSites.size()+" call sites selected");
854 continue;
855 }
856 if (s.startsWith("size ")) {
857 try {
858 final int size = Integer.parseInt(s.substring(5));
859 Filter f = new Filter() {
860 public boolean isElement(Object o) {
861 Map.Entry e = (Map.Entry)o;
862 Set set = (Set)e.getValue();
863 return set.size() == size;
864 }
865 };
866 FilterIterator it1 = new FilterIterator(sorted.iterator(), f);
867 FilterIterator it2 = new FilterIterator(sorted.iterator(), f);
868 selectCallSites("size="+size, it1, it2);
869 } catch (NumberFormatException x) {
870 System.out.println("Invalid size: "+s.substring(5));
871 }
872 continue;
873 }
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971 if (s.startsWith("exit") || s.startsWith("quit")) {
972 System.exit(0);
973 }
974 System.out.println("Unknown command: "+s);
975 }
976
977 }
978
979 }