1 salcianu 1.1 // ComputeMuClosure.java, created Tue Oct 8 11:11:44 2002 by salcianu
2 salcianu 1.1 // Copyright (C) 2000 Alexandru Salcianu <salcianu@MIT.EDU>
3 salcianu 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1
6 salcianu 1.1 import harpoon.IR.Quads.CALL;
7 salcianu 1.1 import harpoon.Temp.Temp;
8 salcianu 1.1 import harpoon.Util.DataStructs.Relation;
9 salcianu 1.1 import harpoon.Util.DataStructs.RelationImpl;
10 salcianu 1.2 import harpoon.Util.Util;
11 salcianu 1.2
12 salcianu 1.4 import harpoon.Analysis.MetaMethods.GenType;
13 salcianu 1.4
14 salcianu 1.2 import java.util.Set;
15 salcianu 1.2 import java.util.HashSet;
16 salcianu 1.4 import java.util.Hashtable;
17 salcianu 1.2 import java.util.Iterator;
18 salcianu 1.1
19 salcianu 1.1 /**
20 salcianu 1.1 <code>ComputeMuClosure</code> is a [functional-programming style]
21 salcianu 1.1 closure for the <code>computeInterProcMu method</code>. See the
22 salcianu 1.1 comments around that method for more info.
23 salcianu 1.1
24 salcianu 1.1 @author Alexandru Salcianu <salcianu@MIT.EDU>
25 cananian 1.6 @version $Id: ComputeInterProcMuClosure.java,v 1.6 2004/02/08 03:20:02 cananian Exp $ */
26 salcianu 1.1 public class ComputeInterProcMuClosure {
27 salcianu 1.1
28 salcianu 1.4 static boolean DEBUG = false;
29 salcianu 1.1
30 salcianu 1.1 /** Compute the node mappings for the inter-procedural analysis,
31 salcianu 1.1 according to the method outlined in Alex Salcianu's SM thesis
32 salcianu 1.1 (Figure 2-8, page 39).
33 salcianu 1.1
34 salcianu 1.1 @param call analyzed call site
35 salcianu 1.1 @param pig_caller graph for the point right before the call
36 salcianu 1.1 @param pig_callee summary graph for the end of the callee method
37 salcianu 1.1 @param callee_params PARAM nodes for the callee
38 salcianu 1.1
39 salcianu 1.1 @return node mapping relation */
40 salcianu 1.1 public static Relation computeInterProcMu
41 salcianu 1.1 (CALL call, ParIntGraph pig_caller, ParIntGraph pig_callee,
42 salcianu 1.4 PANode[] callee_params, PointerAnalysis pa) {
43 salcianu 1.3
44 salcianu 1.1 if(DEBUG) {
45 salcianu 1.1 System.out.println
46 salcianu 1.1 ("computeInterProcMu:\n" +
47 salcianu 1.2 "call = " + Util.code2str(call) + "\n" +
48 salcianu 1.3 /*
49 salcianu 1.1 "pig_caller = " + pig_caller + "\n" +
50 salcianu 1.1 "pig_callee = " + pig_callee + "\n" +
51 salcianu 1.3 */
52 salcianu 1.1 "callee_params = {");
53 salcianu 1.1 for(int i = 0; i < callee_params.length; i++)
54 salcianu 1.1 System.out.println(" " + callee_params[i]);
55 salcianu 1.1 System.out.println("}\n");
56 salcianu 1.1 }
57 salcianu 1.1
58 salcianu 1.1 ComputeInterProcMuClosure cmc = new ComputeInterProcMuClosure
59 salcianu 1.4 (call, pig_caller, pig_callee, callee_params, pa);
60 salcianu 1.1 cmc.compute_mu();
61 salcianu 1.3
62 salcianu 1.1 return cmc.mu;
63 salcianu 1.1 }
64 salcianu 1.1
65 salcianu 1.1
66 salcianu 1.1 // no outside entity can create this object
67 salcianu 1.1 private ComputeInterProcMuClosure() {
68 salcianu 1.1 // this will never be executed; it's here only because
69 salcianu 1.1 // otherwise the compiler complains that the final vars are
70 salcianu 1.1 // not initialized.
71 salcianu 1.4 this(null, null, null, null, null);
72 salcianu 1.1 }
73 salcianu 1.1
74 salcianu 1.1 private ComputeInterProcMuClosure
75 salcianu 1.1 (CALL call, ParIntGraph pig_caller, ParIntGraph pig_callee,
76 salcianu 1.4 PANode[] callee_params, PointerAnalysis pa) {
77 salcianu 1.1 this.call = call;
78 salcianu 1.1 this.pig_caller = pig_caller;
79 salcianu 1.1 this.pig_callee = pig_callee;
80 salcianu 1.1 this.callee_params = callee_params;
81 salcianu 1.4 this.pa = pa;
82 salcianu 1.1 }
83 salcianu 1.1
84 salcianu 1.1 // closure fields
85 salcianu 1.1 private final CALL call;
86 salcianu 1.1 private final ParIntGraph pig_caller;
87 salcianu 1.1 private final ParIntGraph pig_callee;
88 salcianu 1.1 private final PANode[] callee_params;
89 salcianu 1.1 private final Relation mu = new RelationImpl();
90 salcianu 1.4 private final PointerAnalysis pa;
91 salcianu 1.1
92 salcianu 1.1 // top-level driver for the node mapping generation
93 salcianu 1.1 private void compute_mu() {
94 salcianu 1.1 // 2.5 and 2.6
95 salcianu 1.1 initialize_mu();
96 salcianu 1.1
97 salcianu 1.1 if(DEBUG)
98 salcianu 1.1 System.out.println("Initial mu: " + mu);
99 salcianu 1.1
100 salcianu 1.1 // 2.7 and 2.8
101 salcianu 1.1 extend_mu();
102 salcianu 1.1
103 salcianu 1.1 if(DEBUG)
104 salcianu 1.1 System.out.println("Middle mu: " + mu);
105 salcianu 1.1
106 salcianu 1.1 // extend mu to obtain mu'
107 salcianu 1.1 compute_final_mu();
108 salcianu 1.1
109 salcianu 1.3 /*
110 salcianu 1.1 if(DEBUG)
111 salcianu 1.1 System.out.println("Final mu: " + mu);
112 salcianu 1.3 */
113 salcianu 1.1 }
114 salcianu 1.1
115 salcianu 1.1
116 salcianu 1.1 // Compute a node mapping initialized by 2.5 and 2.6
117 salcianu 1.1 private void initialize_mu() {
118 salcianu 1.1 // 2.5: map parameters nodes to the actual arguments
119 salcianu 1.1 map_parameters();
120 salcianu 1.1
121 salcianu 1.4 if(!PointerAnalysis.TOPLAS_PAPER) {
122 salcianu 1.4 // 2.6: reflexive mapping of static nodes from callee
123 salcianu 1.4 pig_callee.forAllNodes(new PANodeVisitor() {
124 salcianu 1.4 public void visit(PANode node) {
125 salcianu 1.4 if((node.type == PANode.STATIC) ||
126 salcianu 1.4 // LOST nodes may represent STATIC nodes
127 salcianu 1.4 (PointerAnalysis.COMPRESS_LOST_NODES &&
128 salcianu 1.4 (node.type == PANode.LOST)))
129 salcianu 1.4 mu.add(node, node);
130 salcianu 1.4 }
131 salcianu 1.4 });
132 salcianu 1.4 }
133 salcianu 1.1 }
134 salcianu 1.1
135 salcianu 1.1 // Update the mapping mu to contain the mappings for the parameter nodes
136 salcianu 1.1 private void map_parameters() {
137 salcianu 1.1 Temp[] args = call.params();
138 salcianu 1.1 int object_params_count = 0;
139 salcianu 1.1 // map the object formal parameter nodes to the actual arguments
140 salcianu 1.1 for(int i = 0; i < args.length; i++)
141 salcianu 1.1 if(!call.paramType(i).isPrimitive()) {
142 salcianu 1.4 // null only for some native methods
143 salcianu 1.4 if(callee_params != null)
144 salcianu 1.4 addMappingAll(mu,
145 salcianu 1.4 callee_params[object_params_count],
146 salcianu 1.4 pig_caller.G.I.pointedNodes(args[i]));
147 salcianu 1.1 object_params_count++;
148 salcianu 1.1 }
149 salcianu 1.1
150 salcianu 1.4 assert (callee_params == null) ||
151 salcianu 1.4 (object_params_count == callee_params.length) :
152 salcianu 1.1 "\tDifferent numbers of object formals (" +
153 salcianu 1.1 callee_params.length + ") and object arguments (" +
154 salcianu 1.2 object_params_count + ") for \n\t" + Util.code2str(call);
155 salcianu 1.1 }
156 salcianu 1.1
157 salcianu 1.1
158 salcianu 1.1 // Initially, all the nodes from the callee are put into the
159 salcianu 1.1 // caller's graph except for the PARAM nodes. Later, after
160 salcianu 1.1 // recomputing the escape info, the empty load nodes will be
161 salcianu 1.1 // removed. Thesis equivalent: part 2 of the mapping function
162 salcianu 1.1 // (Figure 2-8), mu is extended to produce mu'
163 salcianu 1.1 private void compute_final_mu() {
164 salcianu 1.1 pig_callee.forAllNodes(new PANodeVisitor() {
165 salcianu 1.1 public void visit(PANode node) {
166 salcianu 1.1 if(node.type != PANode.PARAM)
167 salcianu 1.1 mu.add(node, node);
168 salcianu 1.1 }
169 salcianu 1.1 });
170 salcianu 1.1 }
171 salcianu 1.1
172 salcianu 1.1
173 salcianu 1.1
174 salcianu 1.1 // iteratively apply 2.7 and 2.8 to compute l.f.p. of 2.5-2.8
175 salcianu 1.1 private void extend_mu() {
176 salcianu 1.1 // worklist containing nodes with new mappings
177 salcianu 1.1 W = new PAWorkList();
178 salcianu 1.1 // relation containing the new mappings for nodes from the worklist
179 salcianu 1.1 new_mu = (Relation) mu.clone();
180 salcianu 1.4 rev_mu = mu.revert(new RelationImpl());
181 salcianu 1.1
182 salcianu 1.1 W.addAll(mu.keys());
183 salcianu 1.1 while(!W.isEmpty()) {
184 salcianu 1.1 PANode node = (PANode) W.remove();
185 salcianu 1.1 // apply all newly enabled instances of 2.7
186 salcianu 1.1 match_callee_caller(node);
187 salcianu 1.1 // apply all newly enabled instances of 2.8
188 salcianu 1.4 match_callee_callee(node);
189 salcianu 1.1 }
190 salcianu 1.1
191 salcianu 1.1 W = null;
192 salcianu 1.1 new_mu = null;
193 salcianu 1.1 }
194 salcianu 1.1 // Yeah, I know these should be packaged with extend_mu (and
195 salcianu 1.1 // posibly other methods) into a separate closure! I'm lazy ...
196 salcianu 1.1 private PAWorkList W;
197 salcianu 1.1 private Relation new_mu;
198 salcianu 1.1 private Relation rev_mu;
199 salcianu 1.1
200 salcianu 1.1
201 salcianu 1.4 // add the (potentially new) mapping source -> target; return
202 salcianu 1.1 // true if this is indeed a new mapping
203 salcianu 1.1 private boolean add_mapping_aux(PANode source, PANode target) {
204 salcianu 1.4 if(addMapping(mu, source, target)) {
205 salcianu 1.3 NEWINFO = true;
206 salcianu 1.1 if(DEBUG)
207 salcianu 1.1 System.out.println("new mapping: " + source + " -> " + target);
208 salcianu 1.1 new_mu.add(source, target);
209 salcianu 1.1 rev_mu.add(target, source);
210 salcianu 1.1 return true;
211 salcianu 1.1 }
212 salcianu 1.1 return false;
213 salcianu 1.1 }
214 salcianu 1.1
215 salcianu 1.1 // add one mapping; if this adds new info, source is put into W
216 salcianu 1.1 private void add_mapping(PANode source, PANode target) {
217 salcianu 1.1 if(add_mapping_aux(source, target))
218 salcianu 1.1 W.add(source);
219 salcianu 1.1 }
220 salcianu 1.1
221 salcianu 1.1 // add several mappings; if any new info, source is put into W
222 salcianu 1.1 private void add_mappings(PANode source, Set targets) {
223 salcianu 1.1 if(targets.isEmpty()) return;
224 salcianu 1.1 boolean changed = false;
225 cananian 1.6 for(Object targetO : targets) {
226 cananian 1.6 PANode target = (PANode) targetO;
227 salcianu 1.1 if(add_mapping_aux(source, target))
228 salcianu 1.1 changed = true;
229 salcianu 1.1 }
230 salcianu 1.1 if(changed)
231 salcianu 1.1 W.add(source);
232 salcianu 1.1 }
233 salcianu 1.1
234 salcianu 1.1
235 salcianu 1.1 // try to apply constraint 2.7 for node1
236 salcianu 1.1 private void match_callee_caller(PANode node1) {
237 salcianu 1.1 for(Iterator itf = pig_callee.G.O.allFlagsForNode(node1).iterator();
238 salcianu 1.1 itf.hasNext(); )
239 salcianu 1.1 match_callee_caller(node1, (String) itf.next());
240 salcianu 1.1 }
241 salcianu 1.1
242 salcianu 1.1 // apply 2.7 for the field f
243 salcianu 1.1 private void match_callee_caller(PANode node1, String f) {
244 salcianu 1.1 Set node2s = pig_callee.G.O.pointedNodes(node1, f);
245 salcianu 1.1 if(node2s.isEmpty()) return;
246 salcianu 1.1 Set node4s = pig_caller.G.I.pointedNodes(new_mu.getValues(node1), f);
247 salcianu 1.1 if(node4s.isEmpty()) return;
248 salcianu 1.1
249 salcianu 1.3 NEWINFO = false;
250 salcianu 1.1
251 cananian 1.6 for(Object node2O : node2s) {
252 cananian 1.6 PANode node2 = (PANode) node2O;
253 salcianu 1.1 add_mappings(node2, node4s);
254 salcianu 1.1 }
255 salcianu 1.3
256 salcianu 1.3 if(NEWINFO && DEBUG)
257 salcianu 1.3 System.out.println("2.7 for node1=" + node1 + ", f=" + f + "\n");
258 salcianu 1.1 }
259 salcianu 1.1
260 salcianu 1.1 // try to apply constraint 2.8 for node1/node3 = node
261 salcianu 1.1 private void match_callee_callee(PANode node) {
262 salcianu 1.1 Set nodeps = new HashSet();
263 salcianu 1.1 // We explore the set of possible elements in the set intersection
264 salcianu 1.1 // from the formal rule 2.8; it is safe to look only at the
265 salcianu 1.1 // the new mappings (plus node which is new in 1st iteration)
266 cananian 1.6 for(Object commonO : new_mu.getValues(node)) {
267 cananian 1.6 PANode common = (PANode) commonO;
268 salcianu 1.1 callee_callee_grab_nodep(node, common, nodeps);
269 salcianu 1.1 }
270 salcianu 1.1 callee_callee_grab_nodep(node, node, nodeps);
271 salcianu 1.1
272 cananian 1.6 for(Object node_primeO : nodeps) {
273 cananian 1.6 PANode node_prime = (PANode) node_primeO;
274 salcianu 1.1 match_callee_callee(node, node_prime);
275 salcianu 1.1 match_callee_callee(node_prime, node);
276 salcianu 1.1 }
277 salcianu 1.1 }
278 salcianu 1.1
279 salcianu 1.1 // try to apply 2.8 where the common element of the intersection is
280 salcianu 1.1 private void callee_callee_grab_nodep
281 salcianu 1.1 (PANode node, PANode common, Set nodeps) {
282 salcianu 1.1 // this corresponds to the "\ {n_null}" from the formal rule
283 salcianu 1.1 if(common.type == PANode.NULL)
284 salcianu 1.1 return;
285 salcianu 1.1 nodeps.addAll(rev_mu.getValues(common));
286 salcianu 1.1 }
287 salcianu 1.1
288 salcianu 1.1
289 salcianu 1.1 // "apply" all possible instantiations of 2.8 for node1 and node3
290 salcianu 1.1 private void match_callee_callee(PANode node1, PANode node3) {
291 salcianu 1.3 if( ! ( (node1 != node3) ||
292 salcianu 1.3 ((node1.type == PANode.LOAD) ||
293 salcianu 1.3 (node1.type == PANode.LOST)) ) )
294 salcianu 1.1 return;
295 salcianu 1.1
296 cananian 1.6 for(Object fO : pig_callee.G.O.allFlagsForNode(node1)) {
297 cananian 1.6 String f = (String) fO;
298 salcianu 1.1 Set node2s = pig_callee.G.O.pointedNodes(node1, f);
299 salcianu 1.1 Set node4s = pig_callee.G.I.pointedNodes(node3, f);
300 salcianu 1.1 if(node4s.isEmpty()) continue;
301 salcianu 1.3
302 cananian 1.6 for(Object node2O : node2s) {
303 cananian 1.6 PANode node2 = (PANode) node2O;
304 salcianu 1.1 for(Iterator it4 = node4s.iterator(); it4.hasNext(); ) {
305 salcianu 1.3
306 salcianu 1.3 NEWINFO = false;
307 salcianu 1.3
308 salcianu 1.1 PANode node4 = (PANode) it4.next();
309 salcianu 1.1 if(node4.type != PANode.PARAM)
310 salcianu 1.1 add_mapping(node2, node4);
311 salcianu 1.3
312 salcianu 1.3 if(NEWINFO && DEBUG)
313 salcianu 1.3 System.out.println
314 salcianu 1.3 ("2.8a for node1=" + node1 + ", node2=" + node2 +
315 salcianu 1.3 ", f=" + f +
316 salcianu 1.3 ", node3=" + node3 + ", node4=" + node4 + "\n");
317 salcianu 1.3 NEWINFO = false;
318 salcianu 1.3
319 salcianu 1.1 add_mappings(node2, mu.getValues(node4));
320 salcianu 1.3
321 salcianu 1.3 if(NEWINFO && DEBUG)
322 salcianu 1.3 System.out.println
323 salcianu 1.3 ("2.8b for node1=" + node1 + ", node2=" + node2 +
324 salcianu 1.3 ", f=" + f +
325 salcianu 1.3 ", node3=" + node3 + ", node4=" + node4 + "\n");
326 salcianu 1.1 }
327 salcianu 1.1 }
328 salcianu 1.1 }
329 salcianu 1.1 }
330 salcianu 1.3 private boolean NEWINFO = false;
331 salcianu 1.4
332 salcianu 1.4
333 salcianu 1.4
334 salcianu 1.4 private static boolean USE_TYPE_INFO = true;
335 salcianu 1.4 static {
336 salcianu 1.4 if(USE_TYPE_INFO)
337 salcianu 1.4 System.out.println("USE TYPE INFO IN INTERPROC MAPPING");
338 salcianu 1.4 }
339 salcianu 1.4
340 salcianu 1.4 private boolean addMappingAll(Relation mu, PANode node, Set images) {
341 salcianu 1.4 if(!USE_TYPE_INFO)
342 salcianu 1.4 return mu.addAll(node, images);
343 salcianu 1.4 boolean changed = false;
344 salcianu 1.4 for(Iterator it = images.iterator(); it.hasNext(); ) {
345 salcianu 1.4 if(addMapping(mu, node, (PANode) it.next()))
346 salcianu 1.4 changed = true;
347 salcianu 1.4 }
348 salcianu 1.4 return changed;
349 salcianu 1.4 }
350 salcianu 1.4
351 salcianu 1.4
352 salcianu 1.4 private boolean addMapping(Relation mu, PANode node, PANode image) {
353 salcianu 1.4 if(!USE_TYPE_INFO)
354 salcianu 1.4 return mu.add(node, image);
355 salcianu 1.4 if(mu.contains(node, image)) return false;
356 salcianu 1.4 if(compatible(node, image))
357 salcianu 1.4 return mu.add(node, image);
358 salcianu 1.4 else
359 salcianu 1.4 return false;
360 salcianu 1.4 }
361 salcianu 1.4
362 salcianu 1.4
363 salcianu 1.4 private static class CompatibleQuery {
364 salcianu 1.4 PANode node1;
365 salcianu 1.4 PANode node2;
366 salcianu 1.4 int hash;
367 salcianu 1.4 CompatibleQuery() {} // just to make the compiler happy
368 salcianu 1.4 CompatibleQuery(PANode node1, PANode node2) {
369 salcianu 1.4 init(node1, node2);
370 salcianu 1.4 }
371 salcianu 1.4 private void init(PANode node1, PANode node2) {
372 salcianu 1.4 this.node1 = node1;
373 salcianu 1.4 this.node2 = node2;
374 salcianu 1.4 this.hash = node1.hashCode() ^ node2.hashCode();
375 salcianu 1.4 }
376 salcianu 1.4 public int hashCode() { return hash; }
377 salcianu 1.4 public boolean equals(Object o) {
378 salcianu 1.4 if(this.hashCode() != o.hashCode())
379 salcianu 1.4 return false;
380 salcianu 1.4 CompatibleQuery q = (CompatibleQuery) o;
381 salcianu 1.4 return
382 salcianu 1.4 this.node1.equals(q.node1) &&
383 salcianu 1.4 this.node2.equals(q.node2);
384 salcianu 1.4 }
385 salcianu 1.4 }
386 salcianu 1.4 private boolean compatible(PANode node1, PANode node2) {
387 salcianu 1.4 compatibleQuery.init(node1, node2);
388 salcianu 1.4 Boolean answer = (Boolean) compatibleCache.get(compatibleQuery);
389 salcianu 1.4 if(answer == null) {
390 salcianu 1.4 boolean banswer = _compatible(node1, node2);
391 salcianu 1.4 answer = new Boolean(banswer);
392 salcianu 1.4 compatibleCache.put(new CompatibleQuery(node1, node2), answer);
393 salcianu 1.5 /* // debug code
394 salcianu 1.4 if(!banswer)
395 salcianu 1.4 System.out.println("INCOMPAT: " + node1 + " , " + node2);
396 salcianu 1.5 */
397 salcianu 1.4 }
398 salcianu 1.4 return answer.booleanValue();
399 salcianu 1.4 }
400 salcianu 1.4 private static Hashtable/*<CompatibleQuery,Boolean>*/ compatibleCache =
401 salcianu 1.4 new Hashtable();
402 salcianu 1.4 private CompatibleQuery compatibleQuery = new CompatibleQuery();
403 salcianu 1.4
404 salcianu 1.4 private boolean _compatible(PANode node1, PANode node2) {
405 salcianu 1.4 GenType[] gts1 = node1.getPossibleClasses();
406 salcianu 1.4 GenType[] gts2 = node2.getPossibleClasses();
407 salcianu 1.4 if((gts1 == null) || (gts2 == null))
408 salcianu 1.4 return true;
409 salcianu 1.4 else
410 salcianu 1.4 return !disjoint(pa.getAllConcreteClasses(gts1),
411 salcianu 1.4 pa.getAllConcreteClasses(gts2));
412 salcianu 1.4 }
413 salcianu 1.4
414 salcianu 1.4 private static boolean disjoint(Set set1, Set set2) {
415 salcianu 1.4 if(set1.size() > set2.size()) {
416 salcianu 1.4 Set temp;
417 salcianu 1.4 temp = set1;
418 salcianu 1.4 set1 = set2;
419 salcianu 1.4 set2 = temp;
420 salcianu 1.4 }
421 salcianu 1.4 for(Iterator it = set1.iterator(); it.hasNext(); )
422 salcianu 1.4 if(set2.contains(it.next()))
423 salcianu 1.4 return false;
424 salcianu 1.4 return true;
425 salcianu 1.4 }
426 salcianu 1.1 }