1 salcianu 1.1.2.1 // CallGraphImpl.java, created Sun Oct 11 12:56:36 1998 by cananian
2 salcianu 1.1.2.1 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.Quads;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 salcianu 1.1.2.1 import harpoon.ClassFile.HClass;
8 salcianu 1.1.2.1 import harpoon.ClassFile.HCode;
9 salcianu 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
10 salcianu 1.1.2.1 import harpoon.ClassFile.HMethod;
11 salcianu 1.1.2.1 import harpoon.IR.Quads.Quad;
12 salcianu 1.6 import harpoon.IR.Quads.QuadKind;
13 salcianu 1.1.2.1 import harpoon.IR.Quads.CALL;
14 salcianu 1.6 import harpoon.IR.Quads.Code;
15 salcianu 1.1.2.1 import harpoon.Util.Util;
16 cananian 1.11 import net.cscott.jutil.WorkSet;
17 salcianu 1.1.2.1
18 salcianu 1.1.2.1 import java.util.Arrays;
19 salcianu 1.1.2.1 import java.util.HashMap;
20 salcianu 1.1.2.1 import java.util.HashSet;
21 salcianu 1.1.2.1 import java.util.Iterator;
22 salcianu 1.1.2.1 import java.util.Map;
23 salcianu 1.1.2.1 import java.util.Set;
24 salcianu 1.1.2.1
25 salcianu 1.1.2.1 /**
26 salcianu 1.1.2.1 * <code>CallGraphImpl</code> constructs a simple directed call graph.
27 salcianu 1.1.2.1 This is the most conservative implementation of <code>CallGraph</code>.
28 salcianu 1.1.2.1 *
29 salcianu 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
30 cananian 1.11 * @version $Id: CallGraphImpl.java,v 1.11 2004/02/08 01:53:14 cananian Exp $
31 salcianu 1.1.2.1 */
32 salcianu 1.6 public class CallGraphImpl extends AbstrCallGraph {
33 salcianu 1.1.2.1 final ClassHierarchy ch;
34 salcianu 1.1.2.1 /** Creates a <code>CallGraph</code> using the specified
35 salcianu 1.1.2.1 * <code>ClassHierarchy</code>. <code>hcf</code> must be a code
36 salcianu 1.1.2.1 * factory that generates quad-ssi or quad-no-ssa form. */
37 salcianu 1.1.2.1 public CallGraphImpl(ClassHierarchy ch, HCodeFactory hcf) {
38 salcianu 1.1.2.1 // this is maybe a little too draconian
39 salcianu 1.8 assert (hcf.getCodeName().equals(harpoon.IR.Quads.QuadSSI.codename) ||
40 salcianu 1.8 hcf.getCodeName().equals(harpoon.IR.Quads.QuadSSA.codename) ||
41 salcianu 1.8 hcf.getCodeName().equals(harpoon.IR.Quads.QuadNoSSA.codename));
42 salcianu 1.1.2.1 this.ch = ch;
43 salcianu 1.1.2.1 this.hcf = hcf;
44 salcianu 1.1.2.1 }
45 salcianu 1.1.2.1
46 salcianu 1.1.2.1 /** Return a list of all possible methods called by this method. */
47 salcianu 1.1.2.1 public HMethod[] calls(final HMethod m) {
48 cananian 1.9 HMethod[] retval = cache.get(m);
49 salcianu 1.1.2.1 if (retval==null) {
50 cananian 1.9 final Set<HMethod> s = new HashSet<HMethod>();
51 cananian 1.9 final HCode<Quad> hc = hcf.convert(m);
52 salcianu 1.1.2.1 if (hc==null) { cache.put(m,new HMethod[0]); return calls(m); }
53 cananian 1.9 for (Iterator<Quad> it = hc.getElementsI(); it.hasNext(); ) {
54 cananian 1.9 Quad q = it.next();
55 salcianu 1.1.2.1 if (!(q instanceof CALL)) continue;
56 salcianu 1.1.2.1 HMethod cm = ((CALL)q).method();
57 salcianu 1.1.2.1 if (s.contains(cm)) continue; // duplicate.
58 salcianu 1.1.2.1 s.addAll(Arrays.asList(calls(m, (CALL)q)));
59 salcianu 1.1.2.1 }
60 salcianu 1.1.2.1 // finally, copy result vector to retval array.
61 salcianu 1.1.2.1 retval = (HMethod[]) s.toArray(new HMethod[s.size()]);
62 salcianu 1.1.2.1 // and cache result.
63 salcianu 1.1.2.1 cache.put(m, retval);
64 salcianu 1.1.2.1 }
65 salcianu 1.1.2.1 return retval;
66 salcianu 1.1.2.1 }
67 cananian 1.9 final private Map<HMethod,HMethod[]> cache =
68 cananian 1.9 new HashMap<HMethod,HMethod[]>();
69 salcianu 1.1.2.1
70 salcianu 1.4 /** Return an array containing all possible methods called by this
71 salcianu 1.4 * method at a particular call site. */
72 salcianu 1.1.2.1 public HMethod[] calls(final HMethod m, final CALL cs) {
73 salcianu 1.1.2.1 HMethod cm = cs.method();
74 salcianu 1.1.2.1 // for 'special' invocations, we know the method exactly.
75 salcianu 1.1.2.1 if ((!cs.isVirtual()) || cs.isStatic()) return new HMethod[]{ cm };
76 cananian 1.9 final Set<HMethod> s = new HashSet<HMethod>();
77 salcianu 1.1.2.1 // all methods of children of this class are reachable.
78 cananian 1.9 WorkSet<HClass> W = new WorkSet<HClass>();
79 salcianu 1.1.2.1 W.add(cm.getDeclaringClass());
80 salcianu 1.1.2.1 while (!W.isEmpty()) {
81 cananian 1.9 HClass c = W.pop();
82 salcianu 1.1.2.1 // if this class can be instatiated, then its
83 salcianu 1.1.2.1 // implementation of the method should be added to the set.
84 salcianu 1.1.2.1 if (ch.instantiatedClasses().contains(c))
85 salcianu 1.1.2.1 try {
86 salcianu 1.1.2.1 s.add(c.getMethod(cm.getName(),
87 salcianu 1.1.2.1 cm.getDescriptor()));
88 salcianu 1.1.2.1 } catch (NoSuchMethodError nsme) { }
89 salcianu 1.1.2.1 // recurse through all children of this method's class.
90 cananian 1.9 for (Iterator<HClass> it=ch.children(c).iterator(); it.hasNext(); )
91 salcianu 1.1.2.1 W.add(it.next());
92 salcianu 1.1.2.1 }
93 salcianu 1.1.2.1 // finally, copy result vector to retval array.
94 salcianu 1.1.2.1 return (HMethod[]) s.toArray(new HMethod[s.size()]);
95 salcianu 1.1.2.1 }
96 salcianu 1.1.2.2
97 salcianu 1.1.2.2 /** Returns the set of all the methods that can be called in the
98 salcianu 1.1.2.2 execution of the program. */
99 cananian 1.9 public Set<HMethod> callableMethods(){
100 salcianu 1.1.2.2 return ch.callableMethods();
101 salcianu 1.1.2.2 }
102 cananian 1.2 }