1 salcianu 1.1.2.1 // PointsToGraph.java, created Sat Jan 8 23:33:34 2000 by salcianu
2 cananian 1.1.2.4 // 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.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.29 import java.util.Collection;
7 salcianu 1.7 import java.util.Collections;
8 salcianu 1.1.2.1 import java.util.HashSet;
9 salcianu 1.1.2.1 import java.util.Set;
10 salcianu 1.1.2.15 import java.util.Map;
11 salcianu 1.1.2.3 import java.util.Iterator;
12 salcianu 1.1.2.15 import java.util.Enumeration;
13 salcianu 1.1.2.16 import java.util.LinkedList;
14 salcianu 1.1.2.1
15 salcianu 1.1.2.9 import harpoon.Temp.Temp;
16 salcianu 1.1.2.9 import harpoon.Util.Util;
17 salcianu 1.1.2.9
18 cananian 1.8 import net.cscott.jutil.LinearSet;
19 salcianu 1.1.2.32 import harpoon.Util.DataStructs.Relation;
20 salcianu 1.1.2.9
21 salcianu 1.1.2.1 /**
22 salcianu 1.1.2.15 * <code>PointsToGraph</code> models the memory, as specified by the
23 salcianu 1.1.2.15 abstraction of the object creation sites. Each "node" in our
24 salcianu 1.1.2.15 abstraction models one or moree objects and the graph of concrete objects
25 salcianu 1.1.2.15 is modelled as a graph of nodes. In addition, we preserve some escape
26 salcianu 1.1.2.15 information.
27 salcianu 1.1.2.15 Look into one of Martin and John Whaley papers for the complete definition.
28 salcianu 1.1.2.15 *
29 cananian 1.1.2.39 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
30 cananian 1.9 * @version $Id: PointsToGraph.java,v 1.9 2004/02/08 03:20:03 cananian Exp $
31 salcianu 1.1.2.1 */
32 salcianu 1.1.2.37 public class PointsToGraph implements Cloneable, java.io.Serializable{
33 salcianu 1.1.2.20
34 salcianu 1.1.2.31 public static boolean DEBUG = false;
35 salcianu 1.1.2.1
36 salcianu 1.1.2.3 /** The set of the outside edges. */
37 salcianu 1.1.2.1 public PAEdgeSet O;
38 salcianu 1.1.2.3 /** The set of the inside edges. */
39 salcianu 1.1.2.1 public PAEdgeSet I;
40 salcianu 1.1.2.1
41 salcianu 1.1.2.3 /** The escape function. */
42 salcianu 1.1.2.1 public PAEscapeFunc e;
43 salcianu 1.1.2.1
44 salcianu 1.1.2.5 /** The set of normally returned objects */
45 salcianu 1.1.2.15 public Set r;
46 salcianu 1.1.2.5
47 salcianu 1.1.2.5 /** The set of objects which are returned as exception */
48 salcianu 1.1.2.15 public Set excp;
49 salcianu 1.1.2.1
50 salcianu 1.1.2.1 /** Creates a <code>PointsToGraph</code>. */
51 salcianu 1.1.2.1 public PointsToGraph() {
52 salcianu 1.1.2.30 this(new LightPAEdgeSet(), new LightPAEdgeSet(),
53 salcianu 1.1.2.32 new PAEscapeFunc(), new LinearSet(), new LinearSet());
54 salcianu 1.1.2.1 }
55 salcianu 1.1.2.1
56 salcianu 1.1.2.16 // set of nodes reachable from nodes from r (r included)
57 salcianu 1.1.2.16 private Set reachable_from_r = null;
58 salcianu 1.1.2.16 // set of nodes reachable from nodes from excp (excp included)
59 vivien 1.1.2.36 public Set reachable_from_excp = null;
60 salcianu 1.1.2.28
61 salcianu 1.1.2.28 /** Flushes the internal caches in this <code>PointsToGraph</code>. */
62 salcianu 1.1.2.28 public void flushCaches(){
63 salcianu 1.1.2.28 reachable_from_r = null;
64 salcianu 1.1.2.28 reachable_from_excp = null;
65 salcianu 1.1.2.28 }
66 salcianu 1.1.2.16
67 salcianu 1.1.2.16 /** Computes the set of nodes reachable from nodes in <code>roots</code>
68 salcianu 1.1.2.16 through paths that use inside and outside edges. The argument must
69 salcianu 1.1.2.16 be a set of <code>PANode</code>s. The <code>roots</code> set is
70 salcianu 1.1.2.16 included in the returned set (i.e. 0-length paths are considered). */
71 salcianu 1.1.2.16 public final Set reachableNodes(final Set roots){
72 salcianu 1.1.2.16 // Invariant 1: set contains all the reached nodes
73 salcianu 1.1.2.16 final Set set = new HashSet();
74 salcianu 1.1.2.16 // Invariant 2: W contains all the reached nodes whose out-edges
75 salcianu 1.1.2.16 // have not been explored yet.
76 salcianu 1.1.2.16 // Obs: W is used as a stack (addLast + removeLast) which corresponds
77 salcianu 1.1.2.16 // to an "in depth" graph exploration.
78 salcianu 1.1.2.16 final LinkedList W = new LinkedList();
79 salcianu 1.1.2.16 // visitor for exploring reached nodes
80 salcianu 1.1.2.16 final PANodeVisitor nvisitor =
81 salcianu 1.1.2.16 new PANodeVisitor(){
82 salcianu 1.1.2.16 public void visit(PANode n){
83 salcianu 1.1.2.16 if(set.add(n)) // newly reached node
84 salcianu 1.1.2.16 W.addLast(n); // add it to the worklist
85 salcianu 1.1.2.16 // note that a node can be added to W at most once!
86 salcianu 1.1.2.16 }
87 salcianu 1.1.2.16 };
88 salcianu 1.1.2.16
89 salcianu 1.1.2.16 set.addAll(roots);
90 salcianu 1.1.2.16 W.addAll(roots);
91 salcianu 1.1.2.16
92 salcianu 1.1.2.16 while(!W.isEmpty()){
93 salcianu 1.1.2.16 PANode node = (PANode) W.removeLast();
94 salcianu 1.1.2.16 O.forAllPointedNodes(node, nvisitor);
95 salcianu 1.1.2.16 I.forAllPointedNodes(node, nvisitor);
96 salcianu 1.1.2.16 }
97 salcianu 1.1.2.16
98 salcianu 1.1.2.16 return set;
99 salcianu 1.1.2.16 }
100 salcianu 1.1.2.23
101 salcianu 1.1.2.23
102 salcianu 1.1.2.23 /** Returns the set of nodes reachable from the returned nodes
103 salcianu 1.1.2.40 (including the returned nodes). */
104 salcianu 1.1.2.23 public Set getReachableFromR(){
105 salcianu 1.1.2.23 if(reachable_from_r == null)
106 salcianu 1.1.2.23 reachable_from_r = reachableNodes(r);
107 salcianu 1.1.2.23
108 salcianu 1.1.2.23 return reachable_from_r;
109 salcianu 1.1.2.23 }
110 salcianu 1.1.2.23
111 salcianu 1.1.2.23
112 salcianu 1.1.2.23 /** Returns the set of nodes reachable from the exceptionally returned
113 salcianu 1.1.2.40 nodes (including the exceptionally returned nodes). */
114 salcianu 1.1.2.23 public Set getReachableFromExcp(){
115 salcianu 1.1.2.23 if(reachable_from_excp == null)
116 salcianu 1.1.2.23 reachable_from_excp = reachableNodes(excp);
117 salcianu 1.1.2.23
118 salcianu 1.1.2.23 return reachable_from_excp;
119 salcianu 1.1.2.23 }
120 salcianu 1.1.2.23
121 salcianu 1.1.2.16
122 salcianu 1.1.2.18 /** Checks whether node <code>node</code> will escape because
123 salcianu 1.1.2.18 it is returned or because it is reachable from a returned node.
124 salcianu 1.1.2.18 Both kinds of returns - <code>return</code> and <code>throw</code> -
125 salcianu 1.1.2.18 are considered. */
126 salcianu 1.1.2.18 public boolean willEscape(PANode node){
127 salcianu 1.1.2.16 if(reachable_from_r == null)
128 salcianu 1.1.2.16 reachable_from_r = reachableNodes(r);
129 salcianu 1.1.2.16 if(reachable_from_excp== null)
130 salcianu 1.1.2.16 reachable_from_excp = reachableNodes(excp);
131 salcianu 1.1.2.18
132 salcianu 1.1.2.18 return
133 salcianu 1.1.2.18 reachable_from_r.contains(node) ||
134 salcianu 1.1.2.18 reachable_from_excp.contains(node);
135 salcianu 1.1.2.18 }
136 salcianu 1.1.2.18
137 salcianu 1.1.2.18 /** Tests whether node <code>node</code> is an escaped node.
138 salcianu 1.1.2.18 An <i>escaped</i> node is a node which has escaped through some node
139 salcianu 1.1.2.18 or method hole or is reachable (possibly through a 0-length path)
140 salcianu 1.1.2.18 from a node which is returned as a normal result or as an exception,
141 salcianu 1.1.2.18 from the method. */
142 salcianu 1.1.2.18 public boolean escaped(PANode node){
143 salcianu 1.1.2.16 return
144 salcianu 1.1.2.18 e.hasEscaped(node) ||
145 salcianu 1.1.2.18 willEscape(node);
146 salcianu 1.1.2.1 }
147 salcianu 1.1.2.13
148 salcianu 1.1.2.18 /** Tests whether node <code>node</code> is captured.
149 salcianu 1.1.2.13 * This method is simply the negation of <code>escaped</code>. */
150 salcianu 1.7 public boolean captured(PANode node) {
151 salcianu 1.1.2.18 return !escaped(node);
152 salcianu 1.1.2.13 }
153 salcianu 1.1.2.13
154 salcianu 1.1.2.1
155 salcianu 1.1.2.3 /** <code>join</code> is called in the control-flow join points. */
156 salcianu 1.7 public void join(PointsToGraph G2) {
157 salcianu 1.7 Set ppgRoots = PointerAnalysis.CONDENSED_ESCAPE_INFO ?
158 salcianu 1.7 new HashSet() : null;
159 salcianu 1.7
160 salcianu 1.7 O.union(G2.O, ppgRoots);
161 salcianu 1.7 I.union(G2.I, ppgRoots);
162 salcianu 1.7 e.union(G2.e, ppgRoots);
163 salcianu 1.1.2.1 r.addAll(G2.r);
164 salcianu 1.1.2.5 excp.addAll(G2.excp);
165 vivien 1.1.2.36 flushCaches();
166 salcianu 1.7
167 salcianu 1.7 if(PointerAnalysis.CONDENSED_ESCAPE_INFO)
168 salcianu 1.7 propagate(ppgRoots);
169 salcianu 1.7 else
170 salcianu 1.7 propagate();
171 salcianu 1.1.2.10 }
172 salcianu 1.1.2.10
173 salcianu 1.1.2.10 /** Remove all the <code>PANode</code>s that appear in <code>set</code>
174 salcianu 1.1.2.10 from <code>this</code> points-to graph. */
175 salcianu 1.1.2.10 public void remove(Set set){
176 vivien 1.1.2.36 //tbu
177 salcianu 1.1.2.10 O.remove(set);
178 salcianu 1.1.2.10 I.remove(set);
179 salcianu 1.1.2.10 e.remove(set);
180 salcianu 1.1.2.10 r.removeAll(set);
181 salcianu 1.1.2.10 excp.removeAll(set);
182 salcianu 1.1.2.33 flushCaches();
183 salcianu 1.1.2.9 }
184 salcianu 1.1.2.9
185 salcianu 1.1.2.38
186 salcianu 1.1.2.38 /** Inserts the image of <code>G2</code> points-to graph through
187 salcianu 1.1.2.38 the <code>mu</code> node mapping into <code>this</code>
188 salcianu 1.1.2.38 object. This method is designed to be called - indirectly
189 salcianu 1.1.2.38 through <code>ParIntGraph.insertAllButArEo</code> - at the end
190 salcianu 1.1.2.38 of the caller/callee or starter/startee interaction. <br>
191 salcianu 1.1.2.38
192 salcianu 1.1.2.38 <code>principal</code> controls whether the return and
193 salcianu 1.1.2.38 exception set are inserted. */
194 salcianu 1.7 public void insert(PointsToGraph G2, Relation mu, boolean principal,
195 salcianu 1.7 Set noholes) {
196 salcianu 1.7 insert(G2, mu, principal, noholes, null, false);
197 salcianu 1.7 }
198 salcianu 1.7
199 salcianu 1.7 void insert(PointsToGraph G2, Relation mu, boolean principal,
200 salcianu 1.7 Set noholes, Set/*<PANode>*/ ppgRoots, boolean fullProj) {
201 salcianu 1.7 insert_edges(G2.O, G2.I, mu, ppgRoots, fullProj);
202 salcianu 1.7 e.insert(G2.e, mu, noholes, ppgRoots);
203 salcianu 1.7 if(principal) {
204 vivien 1.1.2.36 insert_set(G2.r , mu , r );
205 vivien 1.1.2.36 insert_set(G2.excp , mu , excp );
206 salcianu 1.1.2.11 }
207 salcianu 1.1.2.9 }
208 salcianu 1.1.2.9
209 vivien 1.1.2.36
210 vivien 1.1.2.36 public void insert(PointsToGraph G2,
211 vivien 1.1.2.36 Relation mu,
212 vivien 1.1.2.36 Set noholes,
213 vivien 1.1.2.36 ODInformation odi_org,
214 vivien 1.1.2.36 Set holes_b4_callee,
215 salcianu 1.5 ODInformation odi_new) {
216 vivien 1.1.2.36
217 vivien 1.1.2.36 insert_edges(G2.O, G2.I,
218 vivien 1.1.2.36 mu,
219 vivien 1.1.2.36 odi_org,
220 vivien 1.1.2.36 holes_b4_callee,
221 vivien 1.1.2.36 odi_new);
222 vivien 1.1.2.36
223 salcianu 1.7 e.insert(G2.e, mu, noholes, null);
224 vivien 1.1.2.36 }
225 vivien 1.1.2.36
226 vivien 1.1.2.36 public void insert(PAEdgeSet O_org,
227 vivien 1.1.2.36 PAEdgeSet I_org,
228 vivien 1.1.2.36 Relation mu,
229 vivien 1.1.2.36 ODInformation odi_tmp,
230 salcianu 1.5 ODParIntGraph pig) {
231 vivien 1.1.2.36
232 vivien 1.1.2.36 insert_edges(O_org,
233 vivien 1.1.2.36 I_org,
234 vivien 1.1.2.36 mu,
235 vivien 1.1.2.36 odi_tmp,
236 vivien 1.1.2.36 pig);
237 vivien 1.1.2.36 }
238 vivien 1.1.2.36
239 salcianu 1.7
240 salcianu 1.1.2.9 // Insert the outside edges O2 and the inside edges I2 into this graph,
241 salcianu 1.1.2.9 // transforming them through the mu mapping.
242 salcianu 1.7 // FV changed from private to public
243 salcianu 1.7 public void insert_edges(PAEdgeSet O2, PAEdgeSet I2, final Relation mu) {
244 salcianu 1.7 insert_edges(O2, I2, mu, null, false);
245 salcianu 1.7 }
246 salcianu 1.7
247 salcianu 1.7 // if fullProj is true, even the target of the load edges will be
248 salcianu 1.7 // projected through the mu relation.
249 salcianu 1.7 // if ppgRoots != null, collect in ppgRoots all nodes that are
250 salcianu 1.7 // starting points for new edges (Note: works only if !fullProj)
251 salcianu 1.7 void insert_edges(PAEdgeSet O2, PAEdgeSet I2, final Relation mu,
252 salcianu 1.7 final Set/*<PANode>*/ ppgRoots,
253 salcianu 1.7 final boolean fullProj) {
254 salcianu 1.7
255 salcianu 1.7 assert !((ppgRoots != null) && fullProj) :
256 salcianu 1.7 "ppgRoots != null does not work with fullProj";
257 salcianu 1.1.2.9
258 salcianu 1.1.2.9 // visitor for the outside edges
259 salcianu 1.7 PAEdgeVisitor visitor_O = new PAEdgeVisitor() {
260 salcianu 1.7 public void visit(Temp var, PANode node) {
261 salcianu 1.7 assert false : " var2node edge in O: " + var + "->" + node;
262 salcianu 1.7 }
263 salcianu 1.7 public void visit(PANode node1, String f, PANode node2) {
264 salcianu 1.7 if(fullProj) {
265 salcianu 1.7 O.addEdges(mu.getValues(node1), f, mu.getValues(node2));
266 salcianu 1.7 return;
267 salcianu 1.7 }
268 salcianu 1.7 // TODO: why is this test here? it doesn't
269 salcianu 1.7 // appear in the formalism; try without it
270 salcianu 1.7 if(!mu.contains(node2, node2)) return;
271 salcianu 1.7 Set mu_node1 = mu.getValues(node1);
272 cananian 1.9 for(Object node1_imgO : mu_node1) {
273 cananian 1.9 PANode node1_img = (PANode) node1_imgO;
274 salcianu 1.7 if(PointerAnalysis.CONSIDER_TYPES &&
275 salcianu 1.7 !PointerAnalysis.hasField(node1_img, f)) continue;
276 salcianu 1.7 if(O.addEdge(node1_img, f, node2) && (ppgRoots != null))
277 salcianu 1.7 ppgRoots.add(node1_img);
278 salcianu 1.1.2.9 }
279 salcianu 1.7 }
280 salcianu 1.7 };
281 salcianu 1.1.2.9
282 salcianu 1.1.2.9 O2.forAllEdges(visitor_O);
283 salcianu 1.1.2.9
284 salcianu 1.1.2.9 // visitor for the inside edges
285 salcianu 1.7 PAEdgeVisitor visitor_I = new PAEdgeVisitor() {
286 salcianu 1.7 public void visit(Temp var, PANode node) {
287 salcianu 1.7 Set mu_node = mu.getValues(node);
288 salcianu 1.7 I.addEdges(var, mu_node);
289 salcianu 1.7 }
290 salcianu 1.7 public void visit(PANode node1, String f, PANode node2) {
291 salcianu 1.7 Set mu_node1 = mu.getValues(node1);
292 salcianu 1.7 Set mu_node2 = mu.getValues(node2);
293 cananian 1.9 for(Object node1_imgO : mu_node1) {
294 cananian 1.9 PANode node1_img = (PANode) node1_imgO;
295 salcianu 1.7 if(PointerAnalysis.CONSIDER_TYPES &&
296 salcianu 1.7 !PointerAnalysis.hasField(node1_img, f)) continue;
297 salcianu 1.7 if(I.addEdges(node1_img, f, mu_node2) &&
298 salcianu 1.7 (ppgRoots != null))
299 salcianu 1.7 ppgRoots.add(node1_img);
300 salcianu 1.1.2.9 }
301 salcianu 1.7 }
302 salcianu 1.7 };
303 salcianu 1.1.2.9
304 salcianu 1.1.2.9 I2.forAllEdges(visitor_I);
305 salcianu 1.1.2.9 }
306 salcianu 1.1.2.9
307 vivien 1.1.2.36
308 vivien 1.1.2.36 public void insert_edges(PAEdgeSet O2, PAEdgeSet I2,
309 vivien 1.1.2.36 final Relation mu,
310 vivien 1.1.2.36 final ODInformation odi_org,
311 vivien 1.1.2.36 final Set holes_b4_callee,
312 vivien 1.1.2.36 final ODInformation odi_new)
313 vivien 1.1.2.36 {
314 vivien 1.1.2.36 // visitor for the outside edges
315 salcianu 1.7 PAEdgeVisitor visitor_O = new PAEdgeVisitor() {
316 salcianu 1.7 public void visit(Temp var, PANode node) {
317 salcianu 1.7 assert false : " v->n edge in O: " + var + "->" + node;
318 salcianu 1.7 }
319 salcianu 1.7 public void visit(PANode node1,String f, PANode node2) {
320 salcianu 1.7 if(!mu.contains(node2,node2)) return;
321 salcianu 1.7 Set mu_node1 =
322 salcianu 1.7 (node1.type == PANode.LOST) ?
323 salcianu 1.7 // don't project LOST
324 salcianu 1.7 Collections.singleton(node1) :
325 salcianu 1.7 mu.getValues(node1);
326 salcianu 1.7 O.addEdges(mu_node1, f, node2);
327 salcianu 1.7 odi_new.addOutsideEdges(node1, f, node2,
328 salcianu 1.7 odi_org,
329 salcianu 1.7 mu_node1, holes_b4_callee);
330 salcianu 1.7 }
331 salcianu 1.7 };
332 vivien 1.1.2.36
333 vivien 1.1.2.36 O2.forAllEdges(visitor_O);
334 vivien 1.1.2.36
335 vivien 1.1.2.36 // visitor for the inside edges
336 vivien 1.1.2.36 PAEdgeVisitor visitor_I = new PAEdgeVisitor(){
337 vivien 1.1.2.36 public void visit(Temp var, PANode node){
338 vivien 1.1.2.36 Set mu_node = mu.getValues(node);
339 vivien 1.1.2.36 I.addEdges(var,mu_node);
340 vivien 1.1.2.36 }
341 vivien 1.1.2.36 public void visit(PANode node1,String f, PANode node2){
342 vivien 1.1.2.36 Set mu_node1 = mu.getValues(node1);
343 vivien 1.1.2.36 Set mu_node2 = mu.getValues(node2);
344 vivien 1.1.2.36 I.addEdges(mu_node1,f,mu_node2);
345 vivien 1.1.2.36 odi_new.addInsideEdges(node1, f, node2,
346 vivien 1.1.2.36 odi_org,
347 vivien 1.1.2.36 mu_node1, mu_node2,
348 vivien 1.1.2.36 holes_b4_callee);
349 vivien 1.1.2.36 }
350 vivien 1.1.2.36 };
351 vivien 1.1.2.36
352 vivien 1.1.2.36 I2.forAllEdges(visitor_I);
353 vivien 1.1.2.36 }
354 vivien 1.1.2.36
355 vivien 1.1.2.36 public void insert_edges(final PAEdgeSet O_org,
356 vivien 1.1.2.36 final PAEdgeSet I_org,
357 vivien 1.1.2.36 final Relation mu,
358 vivien 1.1.2.36 final ODInformation odi_tmp,
359 vivien 1.1.2.36 final ODParIntGraph pig)
360 vivien 1.1.2.36 {
361 vivien 1.1.2.36 final ODInformation odi_org = pig.odi;
362 vivien 1.1.2.36
363 vivien 1.1.2.36 // visitor for the outside edges
364 vivien 1.1.2.36 PAEdgeVisitor visitor_O = new PAEdgeVisitor(){
365 vivien 1.1.2.36 public void visit(Temp var, PANode node){
366 salcianu 1.7 assert false : " var2node edge in O: " + var + "->" + node;
367 vivien 1.1.2.36 }
368 vivien 1.1.2.36 public void visit(PANode node1,String f, PANode node2){
369 vivien 1.1.2.36 Set mu_node1 = mu.getValues(node1);
370 vivien 1.1.2.36 if ((mu_node1==null) || (mu_node1.isEmpty())) return;
371 vivien 1.1.2.36
372 vivien 1.1.2.36 O.addEdges(mu_node1, f, node2);
373 vivien 1.1.2.36 odi_tmp.addOutsideEdges(node1, f, node2,
374 vivien 1.1.2.36 odi_org,
375 vivien 1.1.2.36 mu_node1);
376 vivien 1.1.2.36 }
377 vivien 1.1.2.36 };
378 vivien 1.1.2.36
379 vivien 1.1.2.36 O_org.forAllEdges(visitor_O);
380 vivien 1.1.2.36
381 vivien 1.1.2.36 // visitor for the inside edges
382 vivien 1.1.2.36 PAEdgeVisitor visitor_I = new PAEdgeVisitor(){
383 vivien 1.1.2.36 public void visit(Temp var, PANode node){
384 vivien 1.1.2.36 Set mu_node = mu.getValues(node);
385 vivien 1.1.2.36 I.addEdges(var,mu_node);
386 vivien 1.1.2.36 }
387 vivien 1.1.2.36 public void visit(PANode node1,String f, PANode node2){
388 vivien 1.1.2.36 int n_projected = 2;
389 vivien 1.1.2.36
390 vivien 1.1.2.36 Set mu_node1 = mu.getValues(node1);
391 vivien 1.1.2.36 if ((mu_node1==null) || (mu_node1.isEmpty())) {
392 vivien 1.1.2.36 mu_node1 = new HashSet();
393 vivien 1.1.2.36 n_projected--;
394 vivien 1.1.2.36 }
395 vivien 1.1.2.36 mu_node1.add(node1);
396 vivien 1.1.2.36
397 vivien 1.1.2.36 Set mu_node2 = mu.getValues(node2);
398 vivien 1.1.2.36 if ((mu_node2==null) || (mu_node2.isEmpty())) {
399 vivien 1.1.2.36 mu_node2 = new HashSet();
400 vivien 1.1.2.36 n_projected--;
401 vivien 1.1.2.36 }
402 vivien 1.1.2.36 mu_node2.add(node2);
403 vivien 1.1.2.36
404 vivien 1.1.2.36 // node of the two nodes are projected, there is
405 vivien 1.1.2.36 // nothing to do here.
406 vivien 1.1.2.36 if (n_projected==0) return;
407 vivien 1.1.2.36
408 vivien 1.1.2.36 I.addEdges(mu_node1,f,mu_node2);
409 vivien 1.1.2.36 odi_tmp.addInsideEdges(node1, f, node2,
410 vivien 1.1.2.36 odi_org,
411 vivien 1.1.2.36 mu_node1, mu_node2);
412 vivien 1.1.2.36 }
413 vivien 1.1.2.36 };
414 vivien 1.1.2.36
415 vivien 1.1.2.36 I_org.forAllEdges(visitor_I);
416 vivien 1.1.2.36 }
417 salcianu 1.1.2.15 /* Specializes <code>this</code> <code>PointsToGraph</code> according to
418 salcianu 1.1.2.15 <code>map</code>, a mapping from <code>PANode<code> to
419 salcianu 1.1.2.15 <code>PANode</code>. Each node which is not explicitly mapped is
420 salcianu 1.1.2.15 considered to be mapped to itself. */
421 salcianu 1.1.2.15 public PointsToGraph specialize(final Map map){
422 salcianu 1.1.2.15 return
423 salcianu 1.1.2.15 new PointsToGraph(O.specialize(map), I.specialize(map),
424 salcianu 1.1.2.15 e.specialize(map),
425 salcianu 1.1.2.15 PANode.specialize_set(r,map),
426 salcianu 1.1.2.15 PANode.specialize_set(excp,map));
427 salcianu 1.1.2.15 }
428 salcianu 1.1.2.9
429 salcianu 1.1.2.9 // Insert the image of the source set through the mu mapping into
430 salcianu 1.1.2.9 // dest. Forall node in source, addAll mu(node) to dest. source
431 salcianu 1.1.2.9 // and dest should both be sets of PANodes.
432 salcianu 1.1.2.9 private void insert_set(Set source, Relation mu, Set dest){
433 cananian 1.9 for (Object nodeO : source){
434 cananian 1.9 PANode node = (PANode) nodeO;
435 salcianu 1.1.2.32 Set node_image = mu.getValues(node);
436 salcianu 1.1.2.9 dest.addAll(node_image);
437 salcianu 1.1.2.9 }
438 salcianu 1.1.2.1 }
439 salcianu 1.1.2.1
440 salcianu 1.7 /** Propagates the escape information along the edges. */
441 salcianu 1.7 public void propagate(Collection/*<PANode>*/ escaped) {
442 salcianu 1.7 final PAWorkList/*<PANode>*/ W_prop = new PAWorkList/*<PANode>*/();
443 salcianu 1.7
444 salcianu 1.7 // We generate one visitor for each call to propagate (instead
445 salcianu 1.7 // of one for each analyzed node). The downside is that we
446 salcianu 1.7 // need to initialize it (by calling init), for each analyzed
447 salcianu 1.7 // node.
448 salcianu 1.7 final class PropagateNodeVisitor implements PANodeVisitor {
449 salcianu 1.7 PANode current_node;
450 salcianu 1.7 Set/*<HMethod>*/ method_holes;
451 salcianu 1.7
452 salcianu 1.7 void init(PANode current_node, Set method_holes) {
453 salcianu 1.7 this.current_node = current_node;
454 salcianu 1.7 this.method_holes = method_holes;
455 salcianu 1.7 }
456 salcianu 1.1.2.19
457 salcianu 1.7 public final void visit(PANode node) {
458 salcianu 1.7 boolean changed = false;
459 salcianu 1.1.2.19
460 salcianu 1.7 if(e.addNodeHoles(node, e.nodeHolesSet(current_node))) {
461 salcianu 1.7 changed = true;
462 salcianu 1.7 if(PointerAnalysis.MEGA_DEBUG &&
463 salcianu 1.7 e.nodeHolesSet(current_node).contains
464 salcianu 1.7 (NodeRepository.LOST_SUMMARY))
465 salcianu 1.7 System.out.println(node + " due to " + current_node);
466 salcianu 1.7 }
467 salcianu 1.7
468 salcianu 1.7 ///// if(e.getEscapedIntoMH().contains(current_node) &&
469 salcianu 1.7 ///// e.addMethodHole(node, null))
470 salcianu 1.7 ///// changed = true;
471 salcianu 1.7 if(!method_holes.isEmpty()) {
472 salcianu 1.7 if(PointerAnalysis.CONDENSED_ESCAPE_INFO) {
473 salcianu 1.7 if(e.methodHolesSet(node).isEmpty()) {
474 salcianu 1.7 e.addMethodHoles(node, method_holes);
475 salcianu 1.1.2.19 changed = true;
476 vivien 1.1.2.36 }
477 salcianu 1.7 }
478 salcianu 1.7 else { /* !PointerAnalysis.CONDENSED_ESCAPE_INFO */
479 salcianu 1.7 if(e.addMethodHoles(node, method_holes))
480 salcianu 1.1.2.19 changed = true;
481 salcianu 1.1.2.11 }
482 salcianu 1.7 }
483 salcianu 1.7
484 salcianu 1.7 if(changed)
485 salcianu 1.7 W_prop.add(node);
486 salcianu 1.7 }
487 salcianu 1.7 };
488 salcianu 1.7 PropagateNodeVisitor p_visitor = new PropagateNodeVisitor();
489 salcianu 1.1.2.19
490 salcianu 1.7 W_prop.addAll(escaped);
491 salcianu 1.7 while(!W_prop.isEmpty()) {
492 salcianu 1.7 PANode current_node = (PANode) W_prop.remove();
493 salcianu 1.7 p_visitor.init(current_node, e.methodHolesSet(current_node));
494 salcianu 1.7
495 salcianu 1.1.2.19 I.forAllPointedNodes(current_node, p_visitor);
496 salcianu 1.1.2.19 O.forAllPointedNodes(current_node, p_visitor);
497 salcianu 1.1.2.1 }
498 salcianu 1.1.2.11 }
499 salcianu 1.1.2.11
500 salcianu 1.7
501 salcianu 1.7 /** Convenient function that recomputes all the escape info.
502 salcianu 1.1.2.11 Equivalent to <code>propagate(e.escapedNodes())</code>. */
503 salcianu 1.7 public void propagate(){
504 salcianu 1.7 //return
505 salcianu 1.7 propagate(e.escapedNodes());
506 salcianu 1.1.2.1 }
507 salcianu 1.1.2.7
508 salcianu 1.1.2.3 /** Checks the equality of two <code>PointsToGraph</code>s. */
509 salcianu 1.1.2.2 public boolean equals(Object o){
510 salcianu 1.7 if((o == null) || !(o instanceof PointsToGraph))
511 salcianu 1.7 return false;
512 salcianu 1.7 PointsToGraph G2 = (PointsToGraph) o;
513 salcianu 1.7 if(!O.equals(G2.O)) {
514 salcianu 1.7 if(ParIntGraph.DEBUG2 || DEBUG) {
515 salcianu 1.1.2.8 System.out.println("different O's");
516 salcianu 1.7 AbstrPAEdgeSet.show_evolution(O, G2.O);
517 salcianu 1.1.2.21 }
518 salcianu 1.1.2.5 return false;
519 salcianu 1.1.2.5 }
520 salcianu 1.7 if(!I.equals(G2.I)) {
521 salcianu 1.7 if(ParIntGraph.DEBUG2 || DEBUG) {
522 salcianu 1.1.2.8 System.out.println("different I's");
523 salcianu 1.7 AbstrPAEdgeSet.show_evolution(I, G2.I);
524 salcianu 1.1.2.21 }
525 salcianu 1.1.2.5 return false;
526 salcianu 1.1.2.5 }
527 salcianu 1.7 if(!r.equals(G2.r)) {
528 salcianu 1.1.2.30 if(ParIntGraph.DEBUG2 || DEBUG)
529 salcianu 1.1.2.8 System.out.println("different r's");
530 salcianu 1.1.2.5 return false;
531 salcianu 1.1.2.5 }
532 salcianu 1.7 if(!excp.equals(G2.excp)) {
533 salcianu 1.1.2.30 if(ParIntGraph.DEBUG2 || DEBUG)
534 salcianu 1.1.2.8 System.out.println("different excp's");
535 salcianu 1.1.2.25 return false;
536 salcianu 1.1.2.25 }
537 salcianu 1.7 if(!e.equals(G2.e)) {
538 salcianu 1.1.2.30 if(ParIntGraph.DEBUG2 || DEBUG) {
539 salcianu 1.1.2.25 System.out.println("different e's");
540 salcianu 1.1.2.25 System.out.println("this.e : " + e);
541 salcianu 1.1.2.25 System.out.println("G2.e : " + G2.e);
542 salcianu 1.1.2.25 }
543 salcianu 1.1.2.5 return false;
544 salcianu 1.1.2.5 }
545 salcianu 1.1.2.5 return true;
546 salcianu 1.1.2.2 }
547 salcianu 1.1.2.1
548 salcianu 1.1.2.3 /** Private constructor for the <code>clone</code> method. */
549 salcianu 1.1.2.1 private PointsToGraph(PAEdgeSet _O, PAEdgeSet _I,
550 salcianu 1.1.2.15 PAEscapeFunc _e, Set _r, Set _excp){
551 salcianu 1.1.2.1 O = _O;
552 salcianu 1.1.2.1 I = _I;
553 salcianu 1.1.2.1 e = _e;
554 salcianu 1.1.2.1 r = _r;
555 salcianu 1.1.2.5 excp = _excp;
556 salcianu 1.1.2.1 }
557 salcianu 1.1.2.1
558 salcianu 1.1.2.3
559 salcianu 1.1.2.3 /** Deep copy of a <code>PointsToGraph</code>. */
560 salcianu 1.1.2.32 public Object clone() {
561 salcianu 1.1.2.32 try {
562 salcianu 1.1.2.32 PointsToGraph newptg = (PointsToGraph) super.clone();
563 salcianu 1.1.2.32 newptg.O = (PAEdgeSet) O.clone();
564 salcianu 1.1.2.32 newptg.I = (PAEdgeSet) I.clone();
565 salcianu 1.1.2.32 newptg.e = (PAEscapeFunc) e.clone();
566 salcianu 1.1.2.32 newptg.r = (Set) ((LinearSet) r).clone();
567 salcianu 1.1.2.32 newptg.excp = (Set) ((LinearSet) excp).clone();
568 salcianu 1.1.2.32 return newptg;
569 salcianu 1.1.2.32 } catch(CloneNotSupportedException e) {
570 salcianu 1.1.2.32 throw new InternalError();
571 salcianu 1.1.2.32 }
572 salcianu 1.1.2.1 }
573 salcianu 1.1.2.3
574 salcianu 1.1.2.3
575 salcianu 1.1.2.3 /** Finds the static nodes that appear as source nodes in the set of
576 salcianu 1.1.2.7 edges <code>E</code> and add them to <code>set</code> */
577 salcianu 1.1.2.7 private void grab_static_roots(PAEdgeSet E, Set set){
578 cananian 1.9 for(Object nodeO : E.allSourceNodes()) {
579 cananian 1.9 PANode node = (PANode) nodeO;
580 salcianu 1.1.2.6 if(node.type == PANode.STATIC)
581 salcianu 1.1.2.7 set.add(node);
582 salcianu 1.1.2.3 }
583 salcianu 1.1.2.3 }
584 salcianu 1.1.2.3
585 salcianu 1.1.2.3 /** Produces a <code>PointsToGraph</code> containing just the nodes
586 salcianu 1.6 that are reachable from <i>root nodes</i>: the nodes that could be
587 salcianu 1.1.2.7 reached from outside
588 salcianu 1.1.2.7 code (e.g. the caller): the parameter nodes (received in
589 salcianu 1.1.2.7 the <code>params</code>) and the returned nodes (found
590 salcianu 1.1.2.7 in <code>this.r</code>).
591 salcianu 1.1.2.7 The static nodes are implicitly considered roots
592 salcianu 1.1.2.7 for all the methods except "main"
593 salcianu 1.1.2.7 (<code>is_main=true</code>).<br>
594 salcianu 1.1.2.7 In addition to returning the new, reduced graph, this method builds
595 salcianu 1.1.2.7 the set of nodes that are in the new graph. This set is put in
596 salcianu 1.1.2.7 <code>remaining_nodes</code> */
597 salcianu 1.1.2.6 public PointsToGraph keepTheEssential(PANode[] params,
598 salcianu 1.1.2.6 final Set remaining_nodes,
599 salcianu 1.7 boolean is_main) {
600 salcianu 1.1.2.30 PAEdgeSet _O = new LightPAEdgeSet();
601 salcianu 1.1.2.30 PAEdgeSet _I = new LightPAEdgeSet();
602 salcianu 1.1.2.5 // the same sets of return nodes and exceptions
603 salcianu 1.1.2.32 Set _r = (Set) ((LinearSet) r).clone();
604 salcianu 1.1.2.32 Set _excp = (Set) ((LinearSet) excp).clone();
605 salcianu 1.1.2.6
606 salcianu 1.1.2.3 // Put the parameter nodes in the root set
607 salcianu 1.1.2.17 for(int i = 0; i < params.length; i++)
608 salcianu 1.1.2.6 remaining_nodes.add(params[i]);
609 salcianu 1.1.2.7
610 salcianu 1.1.2.3 // In the case of the main method, the static nodes are no longer
611 salcianu 1.1.2.3 // considered to be roots; for all the other methods they must be,
612 salcianu 1.1.2.3 // because they can be accessed by code outside the analyzed
613 salcianu 1.1.2.3 // procedure (e.g. the caller)
614 salcianu 1.1.2.3 if(!is_main){
615 salcianu 1.1.2.7 grab_static_roots(O, remaining_nodes);
616 salcianu 1.1.2.7 grab_static_roots(I, remaining_nodes);
617 salcianu 1.1.2.3 }
618 salcianu 1.1.2.3
619 salcianu 1.1.2.7 // Add the normal return & exception nodes to the set of roots
620 salcianu 1.1.2.6 remaining_nodes.addAll(r);
621 salcianu 1.1.2.6 remaining_nodes.addAll(excp);
622 salcianu 1.1.2.3
623 salcianu 1.1.2.7 // worklist of "to be explored" nodes
624 salcianu 1.1.2.7 final PAWorkList worklist = new PAWorkList();
625 salcianu 1.1.2.7 // put all the roots in the worklist
626 salcianu 1.1.2.7 worklist.addAll(remaining_nodes);
627 salcianu 1.1.2.7
628 salcianu 1.1.2.3 // copy the relevant edges and build the set of essential_nodes
629 salcianu 1.1.2.6 PANodeVisitor visitor = new PANodeVisitor(){
630 salcianu 1.1.2.6 public final void visit(PANode node){
631 salcianu 1.1.2.6 if(remaining_nodes.add(node))
632 salcianu 1.1.2.6 worklist.add(node);
633 salcianu 1.6 }
634 salcianu 1.1.2.6 };
635 salcianu 1.1.2.6 while(!worklist.isEmpty()){
636 salcianu 1.1.2.6 PANode node = (PANode)worklist.remove();
637 salcianu 1.1.2.3 O.copyEdges(node,_O);
638 salcianu 1.1.2.3 I.copyEdges(node,_I);
639 salcianu 1.1.2.3 O.forAllPointedNodes(node,visitor);
640 salcianu 1.1.2.3 I.forAllPointedNodes(node,visitor);
641 salcianu 1.1.2.3 }
642 salcianu 1.1.2.11
643 salcianu 1.1.2.17 // System.out.println("\nREMAINING NODES: " + remaining_nodes);
644 salcianu 1.1.2.3
645 salcianu 1.1.2.7 // retain only the escape information for the remaining nodes
646 salcianu 1.1.2.7 PAEscapeFunc _e = e.select(remaining_nodes);
647 salcianu 1.1.2.6
648 salcianu 1.1.2.7 return new PointsToGraph(_O,_I,_e,_r,_excp);
649 salcianu 1.1.2.3 }
650 salcianu 1.1.2.3
651 salcianu 1.1.2.34
652 salcianu 1.1.2.34 // TODO: keep the essential should be modified to use this method.
653 salcianu 1.1.2.34 // there is a lot of code duplication here.
654 salcianu 1.1.2.35 PointsToGraph copy_from_roots(final Set vars, final Set roots,
655 salcianu 1.1.2.35 final Set remaining_nodes) {
656 salcianu 1.1.2.34 remaining_nodes.addAll(roots);
657 salcianu 1.1.2.34
658 salcianu 1.1.2.35 final PAEdgeSet _O = new LightPAEdgeSet();
659 salcianu 1.1.2.35 final PAEdgeSet _I = new LightPAEdgeSet();
660 salcianu 1.1.2.35
661 salcianu 1.1.2.35 for(Iterator it = vars.iterator(); it.hasNext(); ) {
662 salcianu 1.1.2.35 final Temp v = (Temp) it.next();
663 salcianu 1.1.2.35 I.forAllPointedNodes
664 salcianu 1.1.2.35 (v,
665 salcianu 1.7 new PANodeVisitor() {
666 salcianu 1.1.2.35 public void visit(PANode node) {
667 salcianu 1.1.2.35 _I.addEdge(v, node);
668 salcianu 1.1.2.35 remaining_nodes.add(node);
669 salcianu 1.1.2.35 }
670 salcianu 1.1.2.35 });
671 salcianu 1.1.2.35 }
672 salcianu 1.1.2.34
673 salcianu 1.1.2.34 // the same sets of return nodes and exceptions
674 salcianu 1.1.2.34 Set _r = (Set) ((LinearSet) r).clone();
675 salcianu 1.1.2.34 Set _excp = (Set) ((LinearSet) excp).clone();
676 salcianu 1.1.2.34
677 salcianu 1.1.2.34 // worklist of "to be explored" nodes
678 salcianu 1.1.2.34 final PAWorkList worklist = new PAWorkList();
679 salcianu 1.1.2.34 // put all the roots in the worklist
680 salcianu 1.1.2.34 worklist.addAll(remaining_nodes);
681 salcianu 1.1.2.34
682 salcianu 1.1.2.34 // copy the relevant edges and build the set of essential_nodes
683 salcianu 1.1.2.34 PANodeVisitor visitor = new PANodeVisitor(){
684 salcianu 1.1.2.34 public final void visit(PANode node){
685 salcianu 1.1.2.34 if(remaining_nodes.add(node))
686 salcianu 1.1.2.34 worklist.add(node);
687 salcianu 1.1.2.34 }
688 salcianu 1.1.2.34 };
689 salcianu 1.1.2.34
690 salcianu 1.1.2.34 while(!worklist.isEmpty()){
691 salcianu 1.1.2.35 PANode node = (PANode) worklist.remove();
692 salcianu 1.1.2.34 O.copyEdges(node, _O);
693 salcianu 1.1.2.34 I.copyEdges(node, _I);
694 salcianu 1.1.2.34 O.forAllPointedNodes(node, visitor);
695 salcianu 1.1.2.34 I.forAllPointedNodes(node, visitor);
696 salcianu 1.1.2.34 }
697 salcianu 1.1.2.34
698 salcianu 1.1.2.34 // retain only the escape information for the remaining nodes
699 salcianu 1.1.2.34 PAEscapeFunc _e = e.select(remaining_nodes);
700 salcianu 1.1.2.34
701 salcianu 1.1.2.34 return new PointsToGraph(_O,_I,_e,_r,_excp);
702 salcianu 1.1.2.34 }
703 salcianu 1.1.2.34
704 salcianu 1.1.2.8 /** Pretty-print function for debug purposes.
705 salcianu 1.1.2.8 Two equal <code>PointsToGraph</code>s are guaranteed to have the same
706 salcianu 1.1.2.8 string representation. */
707 salcianu 1.1.2.1 public String toString(){
708 salcianu 1.1.2.1 return
709 salcianu 1.1.2.8 " Outside edges:" + O +
710 salcianu 1.1.2.8 " Inside edges:" + I +
711 salcianu 1.1.2.8 e +
712 salcianu 1.1.2.8 " Return set:" + Debug.stringImg(r) + "\n" +
713 salcianu 1.1.2.8 " Exceptions:" + Debug.stringImg(excp) + "\n";
714 salcianu 1.1.2.1 }
715 salcianu 1.1.2.1
716 cananian 1.2 }