1 cananian 1.1.2.1 // CallGraphImpl.java, created Sun Oct 11 12:56:36 1998 by cananian
2 cananian 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.Maps.ExactTypeMap;
8 cananian 1.1.2.1 import harpoon.Analysis.ReachingDefs;
9 cananian 1.1.2.1 import harpoon.Analysis.SSxReachingDefsImpl;
10 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
12 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
13 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
14 cananian 1.1.2.1 import harpoon.IR.Quads.Quad;
15 cananian 1.1.2.1 import harpoon.IR.Quads.CALL;
16 cananian 1.1.2.1 import harpoon.Temp.Temp;
17 cananian 1.1.2.1 import harpoon.Util.Util;
18 cananian 1.6 import net.cscott.jutil.WorkSet;
19 cananian 1.1.2.1
20 cananian 1.1.2.1 import java.util.Arrays;
21 cananian 1.1.2.1 import java.util.Collections;
22 cananian 1.1.2.1 import java.util.HashMap;
23 cananian 1.1.2.1 import java.util.HashSet;
24 cananian 1.1.2.1 import java.util.Iterator;
25 cananian 1.1.2.1 import java.util.List;
26 cananian 1.1.2.1 import java.util.Map;
27 cananian 1.1.2.1 import java.util.Set;
28 cananian 1.1.2.1 import java.util.Vector;
29 cananian 1.1.2.1
30 cananian 1.1.2.1 /**
31 cananian 1.1.2.1 * <code>CallGraphImpl2</code> constructs a simple directed call graph.
32 cananian 1.1.2.1 * This version pays closer attention to types for a more precise
33 cananian 1.1.2.1 * result. To quantify this a bit, the standard <code>CallGraphImpl</code>
34 cananian 1.1.2.1 * yields a 510-node call graph on the "Hello, World" program, compared
35 cananian 1.1.2.1 * to the 370-node graph that <code>CallGraphImpl2</code> gives you.
36 cananian 1.1.2.1 * <p>
37 cananian 1.1.2.1 * <code>CallGraphImpl2</code> only works on SSI form.
38 cananian 1.1.2.1 *
39 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
40 cananian 1.7 * @version $Id: CallGraphImpl2.java,v 1.7 2004/02/08 03:20:10 cananian Exp $
41 cananian 1.1.2.1 */
42 salcianu 1.5 public class CallGraphImpl2 extends harpoon.Analysis.CallGraph {
43 cananian 1.1.2.1 final HCodeFactory hcf;
44 cananian 1.1.2.1 final ClassHierarchy ch;
45 cananian 1.1.2.1 /** Creates a <code>CallGraph</code> using the specified
46 cananian 1.1.2.1 * <code>ClassHierarchy</code>. <code>hcf</code> must be a code
47 cananian 1.1.2.1 * factory that generates quad-ssi form. */
48 cananian 1.1.2.1 public CallGraphImpl2(ClassHierarchy ch, HCodeFactory hcf) {
49 cananian 1.1.2.1 // this is maybe a little too draconian
50 cananian 1.3.2.1 assert hcf.getCodeName()
51 cananian 1.3.2.1 .equals(harpoon.IR.Quads.QuadSSI.codename);
52 cananian 1.1.2.1 this.ch = ch;
53 cananian 1.1.2.1 this.hcf = hcf;
54 cananian 1.1.2.1 }
55 cananian 1.1.2.1
56 cananian 1.1.2.1 /** Return a list of all possible methods called by this method. */
57 cananian 1.1.2.1 public HMethod[] calls(final HMethod m) {
58 cananian 1.1.2.1 HMethod[] retval = (HMethod[]) cache.get(m);
59 cananian 1.1.2.1 if (retval==null) {
60 cananian 1.1.2.1 final Set s = new HashSet();
61 cananian 1.1.2.1 final HCode hc = hcf.convert(m);
62 cananian 1.1.2.1 if (hc==null) { cache.put(m,new HMethod[0]); return calls(m); }
63 cananian 1.1.2.1 ExactTypeMap etm = new TypeInfo((harpoon.IR.Quads.QuadSSI)hc);
64 cananian 1.1.2.1 ReachingDefs rd = new SSxReachingDefsImpl(hc);
65 cananian 1.7 for (Object qO : getCallSites(m, hc)) {
66 cananian 1.7 CALL q = (CALL) qO;
67 cananian 1.1.2.1 HMethod cm = q.method();
68 cananian 1.1.2.1 if (s.contains(cm)) continue; // duplicate.
69 cananian 1.1.2.1 s.addAll(Arrays.asList(calls((CALL)q, rd, etm)));
70 cananian 1.1.2.1 }
71 cananian 1.1.2.1 // finally, copy result vector to retval array.
72 cananian 1.1.2.1 retval = (HMethod[]) s.toArray(new HMethod[s.size()]);
73 cananian 1.1.2.1 // and cache result.
74 cananian 1.1.2.1 cache.put(m, retval);
75 cananian 1.1.2.1 }
76 cananian 1.1.2.1 return retval;
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1 final private Map cache = new HashMap();
79 cananian 1.1.2.1
80 cananian 1.1.2.1 /** Returns a List of all the <code>CALL</code>s quads in the code
81 cananian 1.1.2.1 of <code>hm</code> (in representation <code>hc</code>). */
82 cananian 1.1.2.1 private List getCallSites(final HMethod hm, final HCode hc){
83 cananian 1.1.2.1 if (hc==null) return Collections.EMPTY_LIST;
84 cananian 1.3.2.1 assert hc.getMethod().equals(hm);
85 cananian 1.1.2.1 if (cache_cs.containsKey(hc)) return (List) cache_cs.get(hc);
86 cananian 1.1.2.1
87 cananian 1.1.2.1 final Vector v = new Vector();
88 cananian 1.1.2.1 for (Iterator it = hc.getElementsI(); it.hasNext(); ) {
89 cananian 1.1.2.1 Quad q = (Quad) it.next();
90 cananian 1.1.2.1 if (q instanceof CALL) v.add(q);
91 cananian 1.1.2.1 }
92 cananian 1.1.2.1 cache_cs.put(hc, Collections.unmodifiableList(v));
93 cananian 1.1.2.1 return getCallSites(hm, hc);
94 cananian 1.1.2.1 }
95 cananian 1.1.2.1 final private Map cache_cs = new HashMap();
96 cananian 1.1.2.1
97 cananian 1.1.2.1 /** Return a list of all possible methods called by this method at
98 cananian 1.1.2.1 * a particular call site. */
99 cananian 1.1.2.1 public HMethod[] calls(final CALL cs,
100 cananian 1.1.2.1 ReachingDefs rd, ExactTypeMap etm) {
101 cananian 1.1.2.1 HMethod cm = cs.method();
102 cananian 1.1.2.1 // for 'special' invocations, we know the method exactly.
103 cananian 1.1.2.1 if ((!cs.isVirtual()) || cs.isStatic()) return new HMethod[]{ cm };
104 cananian 1.1.2.1 // find type of receiver
105 cananian 1.1.2.1 Temp receiver = cs.params(0);
106 cananian 1.1.2.1 Quad def = (Quad) rd.reachingDefs(cs, receiver).iterator().next();
107 cananian 1.1.2.1 HClass rtype = etm.typeMap(def, receiver);
108 cananian 1.1.2.1 // if the type is exact, we know the method exactly.
109 cananian 1.1.2.1 if (etm.isExactType(def, receiver))
110 cananian 1.1.2.1 try {
111 cananian 1.1.2.1 return new HMethod[]
112 cananian 1.1.2.1 { rtype.getMethod(cm.getName(),cm.getDescriptor()) };
113 cananian 1.1.2.1 } catch (NoSuchMethodError nsme) {//hm, no matching method.
114 cananian 1.1.2.1 return new HMethod[0];
115 cananian 1.1.2.1 }
116 cananian 1.1.2.1 // otherwise, compute set of methods:
117 cananian 1.1.2.1 final Set s = new HashSet();
118 cananian 1.1.2.1 // all methods of the type and its children are reachable.
119 cananian 1.1.2.1 WorkSet W = new WorkSet();
120 cananian 1.1.2.1 W.add(rtype);
121 cananian 1.1.2.1 while (!W.isEmpty()) {
122 cananian 1.1.2.1 HClass c = (HClass) W.pop();
123 cananian 1.1.2.1 // if this class can be instatiated, then its
124 cananian 1.1.2.1 // implementation of the method should be added to the set.
125 cananian 1.1.2.1 if (ch.instantiatedClasses().contains(c))
126 cananian 1.1.2.1 try {
127 cananian 1.1.2.1 s.add(c.getMethod(cm.getName(),
128 cananian 1.1.2.1 cm.getDescriptor()));
129 cananian 1.1.2.1 } catch (NoSuchMethodError nsme) { }
130 cananian 1.1.2.1 // recurse through all children of this method's class.
131 cananian 1.1.2.1 for (Iterator it=ch.children(c).iterator(); it.hasNext(); )
132 cananian 1.1.2.1 W.add(it.next());
133 cananian 1.1.2.1 }
134 cananian 1.1.2.1 // finally, copy result vector to retval array.
135 cananian 1.1.2.1 return (HMethod[]) s.toArray(new HMethod[s.size()]);
136 cananian 1.1.2.1 }
137 cananian 1.1.2.1
138 cananian 1.1.2.1 /** Returns the set of all the methods that can be called in the
139 cananian 1.1.2.1 execution of the program. */
140 cananian 1.1.2.1 public Set callableMethods(){
141 cananian 1.1.2.1 return ch.callableMethods();
142 cananian 1.1.2.1 }
143 cananian 1.1.2.1
144 cananian 1.2 }