1 salcianu 1.1.2.1 // SmartCallGraph.java, created Tue Mar 21 15:32:43 2000 by salcianu
2 cananian 1.1.2.6 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.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.MetaMethods;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.util.Map;
7 salcianu 1.1.2.1 import java.util.Set;
8 salcianu 1.1.2.4 import java.util.HashSet;
9 salcianu 1.1.2.1 import java.util.HashMap;
10 salcianu 1.1.2.1 import java.util.Iterator;
11 salcianu 1.1.2.1
12 salcianu 1.1.2.1 import harpoon.Analysis.Quads.CallGraph;
13 salcianu 1.3 import harpoon.Analysis.ClassHierarchy;
14 salcianu 1.1.2.1 import harpoon.ClassFile.HMethod;
15 salcianu 1.7 import harpoon.ClassFile.HClass;
16 salcianu 1.3 import harpoon.ClassFile.CachingCodeFactory;
17 salcianu 1.5 import harpoon.ClassFile.Linker;
18 salcianu 1.1.2.1 import harpoon.IR.Quads.CALL;
19 salcianu 1.1.2.1
20 salcianu 1.1.2.2 import harpoon.Util.Util;
21 salcianu 1.1.2.2
22 salcianu 1.1.2.5 import harpoon.Util.DataStructs.Relation;
23 salcianu 1.5 import harpoon.Util.DataStructs.RelationImpl;
24 salcianu 1.1.2.5
25 salcianu 1.3 /** <code>SmartCallGraph</code> is an improved call graph produced by
26 salcianu 1.3 compressing a meta call graph, ie, all metamethods are shrinked
27 salcianu 1.3 down to their originating method). Constructing the call graph at
28 salcianu 1.3 the level of meta methods and shrinking it later to method level
29 salcianu 1.3 is more precise than constructing the call graph for methods
30 salcianu 1.3 directly using some RTA-like algorithm.
31 salcianu 1.3
32 salcianu 1.3 <p>
33 salcianu 1.3 For a simple program that does just a
34 salcianu 1.3 <code>System.out.println()</code>, the size of the largest group
35 salcianu 1.3 of mutually recursive methods (which corresponds to a strongly
36 salcianu 1.3 connected component in the call graph) decreased from 53 to 8.
37 salcianu 1.3
38 salcianu 1.3 @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
39 cananian 1.9 @version $Id: SmartCallGraph.java,v 1.9 2004/02/08 03:19:57 cananian Exp $
40 salcianu 1.5 */
41 salcianu 1.8 public class SmartCallGraph extends CallGraph {
42 salcianu 1.1.2.1
43 salcianu 1.3 /** Creates a <code>SmartCallGraph</code>.
44 salcianu 1.3 @param mcg Meta call graph
45 salcianu 1.3 */
46 salcianu 1.1.2.1 public SmartCallGraph(MetaCallGraph mcg) {
47 salcianu 1.3 construct(mcg);
48 salcianu 1.3 }
49 salcianu 1.3
50 salcianu 1.3 /** Convenient constructor for use in cases when a meta call graph
51 salcianu 1.3 does not already exist.
52 salcianu 1.3
53 salcianu 1.3 @param hcf Caching code factory used to produce the code of the methods
54 salcianu 1.7
55 salcianu 1.5 @param linker Linker to get classes
56 salcianu 1.7
57 salcianu 1.7 @param ch Class hierarchy
58 salcianu 1.7
59 salcianu 1.7 @param roots Set of program roots (the same notion of roots
60 salcianu 1.7 as that used by <code>QuadClassHierarchy</code>).
61 salcianu 1.3
62 salcianu 1.3 The parameters of this constructor are used to construct a
63 salcianu 1.3 meta call graph that is used to create <code>this</code> smart
64 salcianu 1.3 call graph. */
65 salcianu 1.5 public SmartCallGraph(CachingCodeFactory hcf, Linker linker,
66 salcianu 1.7 ClassHierarchy ch, Set roots) {
67 salcianu 1.3 assert
68 salcianu 1.4 hcf.getCodeName().equals(harpoon.IR.Quads.QuadNoSSA.codename) ||
69 salcianu 1.4 hcf.getCodeName().equals(harpoon.IR.Quads.QuadSSA.codename) ||
70 salcianu 1.4 hcf.getCodeName().equals(harpoon.IR.Quads.QuadSSI.codename) :
71 salcianu 1.4 "unsupported quad factory " + hcf;
72 salcianu 1.3 // can't call this(...) because this is not the first statement ...
73 salcianu 1.7 construct(new MetaCallGraphImpl(hcf, linker, ch,
74 salcianu 1.7 constructMRoots(roots, ch)));
75 salcianu 1.1.2.1 }
76 salcianu 1.1.2.1
77 salcianu 1.1.2.1 // empty array to return in case of no callee
78 salcianu 1.1.2.1 private final HMethod[] empty_array = new HMethod[0];
79 salcianu 1.1.2.1
80 salcianu 1.1.2.1 // cache to keep the association caller -> calees
81 salcianu 1.1.2.1 // Generic programming type: Map<HMethod,HMethod[]>
82 salcianu 1.1.2.1 final private Map hm2callees = new HashMap();
83 salcianu 1.1.2.1 /** Returns an array containing all possible methods called by
84 salcianu 1.1.2.1 method <code>m</code>. If <code>hm</code> doesn't call any
85 salcianu 1.1.2.1 method, return an array of length <code>0</code>. */
86 salcianu 1.1.2.1 public final HMethod[] calls(final HMethod hm) {
87 salcianu 1.1.2.1 HMethod[] retval = (HMethod[]) hm2callees.get(hm);
88 salcianu 1.1.2.1 if(retval == null)
89 salcianu 1.1.2.1 return empty_array;
90 salcianu 1.1.2.1 return retval;
91 salcianu 1.1.2.1 }
92 salcianu 1.1.2.1
93 salcianu 1.1.2.1 // cache to keep the association caller -> call_site -> callees
94 salcianu 1.1.2.1 // Generic programming type: Map<HMethod, Map<CALL, HMethod[]>>
95 salcianu 1.1.2.1 final private Map hm2cs2callees = new HashMap();
96 salcianu 1.1.2.1 /** Returns an array containing all possible methods called by
97 salcianu 1.1.2.1 method <code>m</code> at the call site <code>cs</code>.
98 salcianu 1.1.2.1 If there is no known callee for the call site <code>cs>/code>, or if
99 salcianu 1.1.2.1 <code>cs</code> doesn't belong to the code of <code>hm</code>,
100 salcianu 1.1.2.1 return an array pof length <code>0</code>. */
101 salcianu 1.1.2.1 public final HMethod[] calls(final HMethod hm, final CALL cs) {
102 salcianu 1.1.2.1 Map cs2callees = (Map) hm2cs2callees.get(hm);
103 salcianu 1.1.2.1 if(cs2callees == null)
104 salcianu 1.1.2.1 return empty_array;
105 salcianu 1.1.2.1 HMethod[] retval = (HMethod[]) cs2callees.get(cs);
106 salcianu 1.1.2.1 if(retval == null)
107 salcianu 1.1.2.1 return empty_array;
108 salcianu 1.1.2.1 return retval;
109 salcianu 1.1.2.1 }
110 salcianu 1.1.2.1
111 salcianu 1.1.2.1 /** Returns a list of all the <code>CALL</code>s quads in the code
112 salcianu 1.1.2.1 of <code>hm</code>. */
113 salcianu 1.1.2.1 public CALL[] getCallSites(final HMethod hm){
114 salcianu 1.1.2.1 Map map = (Map) hm2cs2callees.get(hm);
115 salcianu 1.1.2.1 if(map == null)
116 salcianu 1.1.2.1 return new CALL[0];
117 salcianu 1.1.2.1 Set css = map.keySet();
118 salcianu 1.1.2.1 return (CALL[]) css.toArray(new CALL[css.size()]);
119 salcianu 1.1.2.1 }
120 salcianu 1.1.2.1
121 salcianu 1.1.2.3 /** Returns the set of all the methods that can be called in the
122 salcianu 1.1.2.3 execution of the program. */
123 salcianu 1.6 public Set callableMethods() {
124 salcianu 1.1.2.2 return hm2callees.keySet();
125 salcianu 1.1.2.2 }
126 salcianu 1.1.2.2
127 salcianu 1.6 public Set getRunMethods() {
128 salcianu 1.6 return run_hms;
129 salcianu 1.6 }
130 salcianu 1.6 private Set run_hms;
131 salcianu 1.6
132 salcianu 1.1.2.1 // Does the main computation: fill the hm2callees and hm2cs2callees
133 salcianu 1.1.2.1 // structures using the info from mcg.
134 salcianu 1.5 private final void construct(final MetaCallGraph mcg) {
135 salcianu 1.5 Relation split = mcg.getSplitRelation();
136 salcianu 1.1.2.1
137 cananian 1.9 for(Object hmO : split.keys()) {
138 cananian 1.9 HMethod hm = (HMethod) hmO;
139 salcianu 1.5 // ac stores all the callees of hm
140 salcianu 1.5 Set ac = new HashSet();
141 salcianu 1.5 // rel stores associations cs -> callees(cs)
142 salcianu 1.5 // where cs is a call site from hm
143 salcianu 1.5 Relation rel = new RelationImpl();
144 salcianu 1.5
145 salcianu 1.5 // iterate over all metamethods corresponding to hm
146 cananian 1.9 for(Object mmO : split.getValues(hm)) {
147 cananian 1.9 MetaMethod mm = (MetaMethod) mmO;
148 salcianu 1.5
149 cananian 1.9 for(Object csO : mcg.getCallSites(mm)) {
150 cananian 1.9 CALL cs = (CALL) csO;
151 salcianu 1.5 // get meta-methods called at cs
152 salcianu 1.5 MetaMethod[] callees = mcg.getCallees(mm, cs);
153 salcianu 1.5 for(int i = 0; i < callees.length; i++) {
154 salcianu 1.1.2.1 HMethod hm_callee = callees[i].getHMethod();
155 salcianu 1.5 rel.add(cs, hm_callee);
156 salcianu 1.5 ac.add(hm_callee);
157 salcianu 1.1.2.1 }
158 salcianu 1.1.2.1 }
159 salcianu 1.1.2.1 }
160 salcianu 1.5
161 salcianu 1.5 hm2callees.put(hm, ac.toArray(new HMethod[ac.size()]));
162 salcianu 1.5
163 salcianu 1.5 // map stores the association cs -> array of callees,
164 salcianu 1.5 // where cs is a call site from the code of hm
165 salcianu 1.5 Map map = new HashMap();
166 salcianu 1.5 // iterate over the call sites from hm to build "map"
167 cananian 1.9 for(Object csO : rel.keys()) {
168 cananian 1.9 CALL cs = (CALL) csO;
169 salcianu 1.5 Set callees = rel.getValues(cs);
170 salcianu 1.5 map.put(cs, callees.toArray(new HMethod[callees.size()]));
171 salcianu 1.5 }
172 salcianu 1.1.2.1 hm2cs2callees.put(hm, map);
173 salcianu 1.6 }
174 salcianu 1.6
175 salcianu 1.6 run_hms = new HashSet();
176 cananian 1.9 for(Object mmO : mcg.getRunMetaMethods()) {
177 cananian 1.9 MetaMethod mm = (MetaMethod) mmO;
178 salcianu 1.6 run_hms.add(mm.getHMethod());
179 salcianu 1.1.2.1 }
180 salcianu 1.1.2.1 }
181 salcianu 1.1.2.1
182 salcianu 1.7
183 salcianu 1.7 /** Constructs the set of method roots for the compiled program.
184 salcianu 1.7 <code>MetaCallGraphImpl<code> has a different definition of
185 salcianu 1.7 roots than <code>QuadClassHierarchy</code>
186 salcianu 1.7 (<code>SAMain</code> uses that definition). Note: the
187 salcianu 1.7 constructor of <code>SmartCallGraph</code> already calls this;
188 salcianu 1.7 no need to call it externally.
189 salcianu 1.7
190 salcianu 1.7 @param roots Set of roots from SAMain (this includes both
191 salcianu 1.7 methods and classes)
192 salcianu 1.7
193 salcianu 1.7 @param ch Class hierarchy for the compiled program.
194 salcianu 1.7
195 salcianu 1.7 @return Set of method roots for the compiled program. This
196 salcianu 1.7 set includes: the main method + all methods that may be called
197 salcianu 1.7 by JVM (including all static initializers).
198 salcianu 1.7
199 salcianu 1.7 TODO: unify the two concepts of roots. */
200 salcianu 1.7 public static Set/*<HMethod>*/ constructMRoots(Set roots,
201 salcianu 1.7 ClassHierarchy ch) {
202 salcianu 1.7 Set/*<HMethod>*/ mroots = new HashSet/*<HMethod>*/();
203 salcianu 1.7 mroots.addAll(select_methods(roots));
204 salcianu 1.7 mroots.addAll(get_static_initializers(ch));
205 salcianu 1.7 return mroots;
206 salcianu 1.7 }
207 salcianu 1.7
208 salcianu 1.7 // returns the set of methods from "set"
209 salcianu 1.7 private static Set select_methods(Set set) {
210 salcianu 1.7 Set retval = new HashSet();
211 salcianu 1.7 for(Iterator it = set.iterator(); it.hasNext(); ) {
212 salcianu 1.7 Object elm = it.next();
213 salcianu 1.7 if(elm instanceof HMethod)
214 salcianu 1.7 retval.add((HMethod) elm);
215 salcianu 1.7 }
216 salcianu 1.7 return retval;
217 salcianu 1.7 }
218 salcianu 1.7
219 salcianu 1.7
220 salcianu 1.7 // Returns the set of static initializers of all the instanciated classes.
221 salcianu 1.7 private static Set get_static_initializers(ClassHierarchy ch) {
222 salcianu 1.7 Set retval = new HashSet();
223 cananian 1.9 for(Object hclassO : ch.classes()) {
224 cananian 1.9 HClass hclass = (HClass) hclassO;
225 salcianu 1.7 HMethod hm = hclass.getClassInitializer();
226 salcianu 1.7 if(hm != null)
227 salcianu 1.7 retval.add(hm);
228 salcianu 1.7 }
229 salcianu 1.7 return retval;
230 salcianu 1.7 }
231 cananian 1.2 }