1 vivien 1.1.2.1 // ODParIntGraph.java, created Sun Jan 9 15:40:59 2000 by salcianu
2 cananian 1.1.2.2 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 vivien 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 vivien 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 vivien 1.1.2.1
6 vivien 1.1.2.1
7 vivien 1.1.2.1 import java.util.Set;
8 vivien 1.1.2.1 import java.util.HashSet;
9 vivien 1.1.2.1 import java.util.Map;
10 vivien 1.1.2.1 import java.util.HashMap;
11 vivien 1.1.2.1 import java.util.Iterator;
12 vivien 1.1.2.1 import java.util.Collections;
13 vivien 1.1.2.1
14 vivien 1.1.2.1 import harpoon.Temp.Temp;
15 vivien 1.1.2.1 import harpoon.IR.Quads.CALL;
16 vivien 1.1.2.1 import harpoon.Analysis.MetaMethods.MetaMethod;
17 vivien 1.1.2.1 import harpoon.Util.Util;
18 vivien 1.1.2.1
19 vivien 1.1.2.1 import harpoon.Util.DataStructs.Relation;
20 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightRelation;
21 vivien 1.1.2.1 import harpoon.Util.DataStructs.RelationEntryVisitor;
22 vivien 1.1.2.1 import harpoon.Util.DataStructs.LightMap;
23 vivien 1.1.2.1
24 vivien 1.1.2.1
25 vivien 1.1.2.1 /**
26 vivien 1.1.2.1 * <code>ODParIntGraph</code> models a Parallel Interaction Graph data
27 vivien 1.1.2.1 structure. Most of its fields retain the original name from the paper
28 vivien 1.1.2.1 of Martin and John Whaley.
29 vivien 1.1.2.1 *
30 cananian 1.1.2.2 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
31 cananian 1.5 * @version $Id: ODParIntGraph.java,v 1.5 2004/02/08 03:20:02 cananian Exp $
32 vivien 1.1.2.1 */
33 vivien 1.1.2.1 public class ODParIntGraph {
34 vivien 1.1.2.1
35 vivien 1.1.2.1 public static boolean DEBUG = false;
36 vivien 1.1.2.1 public static boolean DEBUG2 = false;
37 vivien 1.1.2.1
38 vivien 1.1.2.1 /** Debug for the aggressive shrinking. */
39 vivien 1.1.2.1 public static boolean DEBUG_AS = false;
40 vivien 1.1.2.1
41 vivien 1.1.2.1 /** Activates the aggressive shrinking. Buggy for the moment ... */
42 vivien 1.1.2.1 public static boolean AGGRESSIVE_SHRINKING = false;
43 vivien 1.1.2.1
44 vivien 1.1.2.1 /** Default (empty) graph. It doesn't contain any information. */
45 vivien 1.1.2.1 public static final ODParIntGraph EMPTY_GRAPH = new ODParIntGraph();
46 vivien 1.1.2.1
47 vivien 1.1.2.1 /** Points-to escape graph that summarizes the points-to and escape
48 vivien 1.1.2.1 information for the current thread. */
49 vivien 1.1.2.1 public PointsToGraph G;
50 vivien 1.1.2.1
51 vivien 1.1.2.1 /** The paralel thread map; it attaches to each thread node nT, an
52 vivien 1.1.2.1 integer from the set {0,1,2} where 2 signifies the possibility
53 vivien 1.1.2.1 that multiple instances of nT execute in parallel with the current
54 vivien 1.1.2.1 thread. */
55 vivien 1.1.2.1 public PAThreadMap tau;
56 vivien 1.1.2.1
57 vivien 1.1.2.1 /** The set of thread objects that are accessed after they are started.
58 vivien 1.1.2.1 This is not exactly part of the PA, but we need it for the thread
59 vivien 1.1.2.1 specific heaps; Martin intend to allocate even the thread object in
60 vivien 1.1.2.1 the thread heap - it is atomically collected at the end of the thread.
61 vivien 1.1.2.1 For the moment, this info is accurate only for captured nodes
62 vivien 1.1.2.1 (it is not carried over in the inter-procedural phase). */
63 vivien 1.1.2.1 public Set touched_threads;
64 vivien 1.1.2.1
65 vivien 1.1.2.1 /** Maintains the actions executed by the analysed code and the parallel
66 vivien 1.1.2.1 action relation. <code>alpha</code> and <code>pi</code> from the
67 vivien 1.1.2.1 original paper have been merged into this single field for efficiency
68 vivien 1.1.2.1 reasons. */
69 vivien 1.1.2.1 public ActionRepository ar;
70 vivien 1.1.2.1
71 vivien 1.1.2.1 /** Maintains the (conservative) ordering relations between the inside
72 vivien 1.1.2.1 and the outside edges. <code>before(ei,eo)</code> is true if the
73 vivien 1.1.2.1 inside edge ei might be created before the ouside edge eo was read. */
74 vivien 1.1.2.1 public EdgeOrdering eo;
75 vivien 1.1.2.1
76 vivien 1.1.2.1
77 vivien 1.1.2.1 /** Data structures necessary for the ODA. */
78 vivien 1.1.2.1 public ODInformation odi = null;
79 vivien 1.1.2.1
80 vivien 1.1.2.1 // public Map in_edge_always;
81 vivien 1.1.2.1 // public Map out_edge_always;
82 vivien 1.1.2.1 // public Map out_edge_maybe;
83 vivien 1.1.2.1 // public Set method_holes;
84 vivien 1.1.2.1 // public Relation holes_history;
85 vivien 1.1.2.1 // public Relation locks;
86 vivien 1.1.2.1
87 vivien 1.1.2.1
88 vivien 1.1.2.1
89 vivien 1.1.2.1
90 vivien 1.1.2.1 /** Creates a <code>ODParIntGraph</code>. */
91 vivien 1.1.2.1 public ODParIntGraph() {
92 vivien 1.1.2.1 G = new PointsToGraph();
93 vivien 1.1.2.1 tau = new PAThreadMap();
94 vivien 1.1.2.1 ar = new ActionRepository();
95 vivien 1.1.2.1 odi = new ODInformation();
96 vivien 1.1.2.1
97 vivien 1.1.2.1 eo = PointerAnalysis.IGNORE_EO ? null : new EdgeOrdering();
98 vivien 1.1.2.1
99 vivien 1.1.2.1 touched_threads = new HashSet();
100 vivien 1.1.2.1 }
101 vivien 1.1.2.1
102 vivien 1.1.2.1
103 vivien 1.1.2.1 /** <code>join</code> combines two <code>ODParIntGraph</code>s in \
104 vivien 1.1.2.1 a control-flow join point. */
105 vivien 1.1.2.1 public void join(ODParIntGraph pig2){
106 vivien 1.1.2.1
107 vivien 1.1.2.1 // System.out.println("Before join " + this);
108 vivien 1.1.2.1
109 vivien 1.1.2.1 G.join(pig2.G);
110 vivien 1.1.2.1 tau.join(pig2.tau);
111 vivien 1.1.2.1 ar.join(pig2.ar);
112 vivien 1.1.2.1
113 vivien 1.1.2.1 if (ODPointerAnalysis.ON_DEMAND_ANALYSIS)
114 vivien 1.1.2.1 odi.join(pig2.odi);
115 vivien 1.1.2.1
116 vivien 1.1.2.1 if(!PointerAnalysis.IGNORE_EO)
117 vivien 1.1.2.1 eo.join(pig2.eo);
118 vivien 1.1.2.1
119 vivien 1.1.2.1 touched_threads.addAll(pig2.touched_threads);
120 vivien 1.1.2.1 // System.out.println("After join " + this);
121 vivien 1.1.2.1 }
122 vivien 1.1.2.1
123 vivien 1.1.2.1
124 vivien 1.1.2.1 /** Inserts the image of <code>pig2</code> parallel interaction graph
125 vivien 1.1.2.1 through the <code>mu</code> node mapping into <code>this</code> object.
126 vivien 1.1.2.1 This method is designed to be called at the end of the caller/callee
127 vivien 1.1.2.1 or starter/startee interaction. It is *not* manipulating the action
128 vivien 1.1.2.1 repository nor the edge ordering; those manipulations are too complex
129 vivien 1.1.2.1 and variate to be done here.<br>
130 vivien 1.1.2.1 <code>principal</code> controls whether the return and exception set
131 vivien 1.1.2.1 are inserted. */
132 vivien 1.1.2.1 void insertAllButArEo(ODParIntGraph pig2, Relation mu,
133 vivien 1.1.2.1 boolean principal, Set noholes){
134 vivien 1.1.2.1 G.insert(pig2.G, mu, principal, noholes);
135 vivien 1.1.2.1 tau.insert(pig2.tau, mu);
136 vivien 1.1.2.1 }
137 vivien 1.1.2.1
138 vivien 1.1.2.1 void insertAllButArEoTau(ODParIntGraph pig2, Relation mu,
139 vivien 1.1.2.1 Set noholes,
140 vivien 1.1.2.1 Set holes_b4_callee,
141 vivien 1.1.2.1 ODInformation new_odi){
142 vivien 1.1.2.1
143 vivien 1.1.2.1 G.insert(pig2.G, mu, noholes,
144 vivien 1.1.2.1 pig2.odi,
145 vivien 1.1.2.1 holes_b4_callee,
146 vivien 1.1.2.1 new_odi);
147 vivien 1.1.2.1 }
148 vivien 1.1.2.1
149 vivien 1.1.2.1 void insertAllButArEoTau(PAEdgeSet O_org,
150 vivien 1.1.2.1 PAEdgeSet I_org,
151 vivien 1.1.2.1 Relation mu,
152 vivien 1.1.2.1 ODInformation odi_tmp)
153 vivien 1.1.2.1 {
154 vivien 1.1.2.1 G.insert(O_org,
155 vivien 1.1.2.1 I_org,
156 vivien 1.1.2.1 mu,
157 vivien 1.1.2.1 odi_tmp,
158 vivien 1.1.2.1 this);
159 vivien 1.1.2.1 }
160 vivien 1.1.2.1
161 vivien 1.1.2.1 /** Convenient function equivalent to
162 vivien 1.1.2.1 <code>insertAllButArEo(pig2,mu,principal,Collections.EMPTY_SET). */
163 vivien 1.1.2.1 void insertAllButArEo(ODParIntGraph pig2, Relation mu, boolean principal){
164 vivien 1.1.2.1 insertAllButArEo(pig2,mu,principal,Collections.EMPTY_SET);
165 vivien 1.1.2.1 }
166 vivien 1.1.2.1
167 vivien 1.1.2.1
168 vivien 1.1.2.1 /** Check the equality of two <code>ODParIntGraph</code>s. */
169 vivien 1.1.2.1 public boolean equals(Object obj){
170 vivien 1.1.2.1 if(obj == null) return false;
171 vivien 1.1.2.1
172 vivien 1.1.2.1 System.out.println("Graph equality not fully implemented");
173 vivien 1.1.2.1
174 vivien 1.1.2.1 //tbu
175 vivien 1.1.2.1
176 vivien 1.1.2.1 ODParIntGraph pig2 = (ODParIntGraph) obj;
177 vivien 1.1.2.1 if(!G.equals(pig2.G)){
178 vivien 1.1.2.1 if(DEBUG2)
179 vivien 1.1.2.1 System.out.println("The graphs are different");
180 vivien 1.1.2.1 return false;
181 vivien 1.1.2.1 }
182 vivien 1.1.2.1 if(!tau.equals(pig2.tau)){
183 vivien 1.1.2.1 if(DEBUG2)
184 vivien 1.1.2.1 System.out.println("The tau's are different");
185 vivien 1.1.2.1 return false;
186 vivien 1.1.2.1 }
187 vivien 1.1.2.1 if(!ar.equals(pig2.ar)){
188 vivien 1.1.2.1 if(DEBUG2){
189 vivien 1.1.2.1 System.out.println("The ar's are different");
190 vivien 1.1.2.1 ar.show_evolution(pig2.ar);
191 vivien 1.1.2.1 }
192 vivien 1.1.2.1 return false;
193 vivien 1.1.2.1 }
194 vivien 1.1.2.1
195 vivien 1.1.2.1 if(!PointerAnalysis.IGNORE_EO)
196 vivien 1.1.2.1 if(!eo.equals(pig2.eo)){
197 vivien 1.1.2.1 if(DEBUG2)
198 vivien 1.1.2.1 System.out.println("The eo's are different");
199 vivien 1.1.2.1 return false;
200 vivien 1.1.2.1 }
201 vivien 1.1.2.1
202 vivien 1.1.2.1 if(!touched_threads.equals(pig2.touched_threads)){
203 vivien 1.1.2.1 if(DEBUG2)
204 vivien 1.1.2.1 System.out.println("The touched_thread's are different");
205 vivien 1.1.2.1 return false;
206 vivien 1.1.2.1 }
207 vivien 1.1.2.1 return true;
208 vivien 1.1.2.1 }
209 vivien 1.1.2.1
210 vivien 1.1.2.1 /** Private constructor for <code>clone</code> and
211 vivien 1.1.2.1 <code>keepTheEssential</code>. */
212 vivien 1.1.2.1 private ODParIntGraph(PointsToGraph G, PAThreadMap tau, ActionRepository ar,
213 vivien 1.1.2.1 EdgeOrdering eo, Set touched_threads){
214 vivien 1.1.2.1 this.G = G;
215 vivien 1.1.2.1 this.tau = tau;
216 vivien 1.1.2.1 this.ar = ar;
217 vivien 1.1.2.1 this.eo = eo;
218 vivien 1.1.2.1 this.touched_threads = touched_threads;
219 vivien 1.1.2.1 System.out.println("FV: dangerous constructor");
220 vivien 1.1.2.1 }
221 vivien 1.1.2.1
222 vivien 1.1.2.1 private ODParIntGraph(PointsToGraph G, PAThreadMap tau, ActionRepository ar,
223 vivien 1.1.2.1 EdgeOrdering eo, Set touched_threads,
224 vivien 1.1.2.1 ODInformation odi){
225 vivien 1.1.2.1 this.G = G;
226 vivien 1.1.2.1 this.tau = tau;
227 vivien 1.1.2.1 this.ar = ar;
228 vivien 1.1.2.1 this.eo = eo;
229 vivien 1.1.2.1 this.touched_threads = touched_threads;
230 vivien 1.1.2.1 this.odi = odi;
231 vivien 1.1.2.1 // System.out.println("After clone " + this);
232 vivien 1.1.2.1 }
233 vivien 1.1.2.1
234 vivien 1.1.2.1 /** Records the fact that the started thread nt is accessed by its
235 vivien 1.1.2.1 direct startee. */
236 vivien 1.1.2.1 public final void touch_thread(PANode nt){
237 vivien 1.1.2.1 touched_threads.add(nt);
238 vivien 1.1.2.1 }
239 vivien 1.1.2.1
240 vivien 1.1.2.1 /** <code>clone</code> produces a copy of the <code>this</code>
241 vivien 1.1.2.1 Parallel Interaction Graph. */
242 vivien 1.1.2.1 public Object clone(){
243 vivien 1.1.2.1 // System.out.println("Before clone " + this);
244 vivien 1.1.2.1
245 vivien 1.1.2.1 EdgeOrdering _eo =
246 vivien 1.1.2.1 PointerAnalysis.IGNORE_EO ? null : (EdgeOrdering)eo.clone();
247 vivien 1.1.2.1
248 vivien 1.1.2.1 if (touched_threads.isEmpty())
249 vivien 1.1.2.1 return new ODParIntGraph((PointsToGraph)G.clone(),
250 vivien 1.1.2.1 (PAThreadMap)tau.clone(),
251 vivien 1.1.2.1 (ActionRepository)ar.clone(),
252 vivien 1.1.2.1 _eo,
253 vivien 1.1.2.1 Collections.EMPTY_SET,
254 vivien 1.1.2.1 (ODInformation)odi.clone()
255 vivien 1.1.2.1 );
256 vivien 1.1.2.1 else
257 vivien 1.1.2.1 return new ODParIntGraph((PointsToGraph)G.clone(),
258 vivien 1.1.2.1 (PAThreadMap)tau.clone(),
259 vivien 1.1.2.1 (ActionRepository)ar.clone(),
260 vivien 1.1.2.1 _eo,
261 vivien 1.1.2.1 (HashSet)((HashSet)touched_threads).clone(),
262 vivien 1.1.2.1 (ODInformation)odi.clone()
263 vivien 1.1.2.1 );
264 vivien 1.1.2.1 // test introduced by FV
265 vivien 1.1.2.1 }
266 vivien 1.1.2.1
267 vivien 1.1.2.1 /** Produces a <code>ODParIntGraph</code> containing only the
268 vivien 1.1.2.1 nodes that could be reached from the outside.
269 vivien 1.1.2.1 (i.e. via parameters,
270 vivien 1.1.2.1 class nodes, normally or exceptionally returned nodes or the
271 vivien 1.1.2.1 started thread nodes) */
272 vivien 1.1.2.1 public ODParIntGraph keepTheEssential(PANode[] params, boolean is_main){
273 vivien 1.1.2.1 ODParIntGraph pig2 = retain_essential(params, is_main);
274 vivien 1.1.2.1
275 vivien 1.1.2.1 if(AGGRESSIVE_SHRINKING){
276 vivien 1.1.2.1 pig2.aggressiveShrinking();
277 vivien 1.1.2.1 pig2 = retain_essential(params, is_main);
278 vivien 1.1.2.1 }
279 vivien 1.1.2.1
280 vivien 1.1.2.1 return pig2;
281 vivien 1.1.2.1 }
282 vivien 1.1.2.1
283 vivien 1.1.2.1 private final ODParIntGraph retain_essential(PANode[] params,
284 vivien 1.1.2.1 boolean is_main){
285 vivien 1.1.2.1
286 vivien 1.1.2.1 HashSet remaining_nodes = new HashSet();
287 vivien 1.1.2.1 remaining_nodes.addAll(tau.activeThreadSet());
288 vivien 1.1.2.1
289 vivien 1.1.2.1 PointsToGraph _G =
290 vivien 1.1.2.1 G.keepTheEssential(params, remaining_nodes, is_main);
291 vivien 1.1.2.1
292 vivien 1.1.2.1 PAThreadMap _tau = (PAThreadMap) tau.clone();
293 vivien 1.1.2.1
294 vivien 1.1.2.1 ActionRepository _ar = ar.keepTheEssential(remaining_nodes);
295 vivien 1.1.2.1
296 vivien 1.1.2.1 EdgeOrdering _eo =
297 vivien 1.1.2.1 PointerAnalysis.IGNORE_EO ? null :
298 vivien 1.1.2.1 eo.keepTheEssential(remaining_nodes);
299 vivien 1.1.2.1
300 vivien 1.1.2.1 // the "touched_threads" info is valid only for captured threads
301 vivien 1.1.2.1 // i.e. not for the remaining nodes (accessible from the outside).
302 vivien 1.1.2.1
303 vivien 1.1.2.1 ODInformation _odi = (ODInformation) odi.clone();
304 vivien 1.1.2.1
305 vivien 1.1.2.1
306 vivien 1.1.2.1 return new ODParIntGraph(_G, _tau, _ar, _eo, Collections.EMPTY_SET, _odi);
307 vivien 1.1.2.1 }
308 vivien 1.1.2.1
309 vivien 1.1.2.1 /** Remove the load nodes that don't lead to anything interesting.
310 vivien 1.1.2.1 This nodes are useless for our analysis (although they could
311 vivien 1.1.2.1 be interesting for other analysis, such as determining the
312 vivien 1.1.2.1 memory area which is read by an application, etc.) and so,
313 vivien 1.1.2.1 we decide not to carry it over the entire call graph. */
314 vivien 1.1.2.1 private final void aggressiveShrinking(){
315 vivien 1.1.2.1
316 vivien 1.1.2.1 final Set unuseful_loads = new HashSet();
317 vivien 1.1.2.1 forAllNodes(new PANodeVisitor(){
318 vivien 1.1.2.1 public void visit(PANode node){
319 vivien 1.1.2.1 if(node.type != PANode.LOAD) return;
320 vivien 1.1.2.1 if(!ODParIntGraph.this.interesting(node))
321 vivien 1.1.2.1 unuseful_loads.add(node);
322 vivien 1.1.2.1 }
323 vivien 1.1.2.1 });
324 vivien 1.1.2.1
325 vivien 1.1.2.1 if(!unuseful_loads.isEmpty()){
326 vivien 1.1.2.1 if(DEBUG_AS){
327 vivien 1.1.2.1 System.out.println("Unuseful loads: " + unuseful_loads);
328 vivien 1.1.2.1 System.out.println("Before aggressive shrinking : " + this);
329 vivien 1.1.2.1 }
330 vivien 1.1.2.1 remove(unuseful_loads);
331 vivien 1.1.2.1 if(DEBUG_AS)
332 vivien 1.1.2.1 System.out.println("After aggressive shrinking : " + this);
333 vivien 1.1.2.1 }
334 vivien 1.1.2.1 }
335 vivien 1.1.2.1
336 vivien 1.1.2.1 /** A node is directly interesting if there is a sync action executed
337 vivien 1.1.2.1 on him or it coudl be returned (normally or exceptionally) from
338 vivien 1.1.2.1 the method. (Normally, we should also analyze the case when the
339 vivien 1.1.2.1 node is a started thread node but anyway, our analysis deal only
340 vivien 1.1.2.1 with INSIDE thread nodes). */
341 vivien 1.1.2.1 private final boolean directlyInteresting(PANode node){
342 vivien 1.1.2.1 if(ar.isSyncOn(node)) return true;
343 vivien 1.1.2.1 if(G.r.contains(node) || G.excp.contains(node)) return true;
344 vivien 1.1.2.1 return false;
345 vivien 1.1.2.1 }
346 vivien 1.1.2.1
347 vivien 1.1.2.1 private boolean important = false;
348 vivien 1.1.2.1 private final boolean interesting(PANode node){
349 cananian 1.3.2.1 assert node.type == PANode.LOAD : "not a LOAD node";
350 vivien 1.1.2.1
351 vivien 1.1.2.1 if(directlyInteresting(node)) return true;
352 vivien 1.1.2.1
353 vivien 1.1.2.1 important = false;
354 vivien 1.1.2.1
355 vivien 1.1.2.1 final Set set = new HashSet();
356 vivien 1.1.2.1 final PAWorkList W = new PAWorkList();
357 vivien 1.1.2.1 set.add(node);
358 vivien 1.1.2.1 W.add(node);
359 vivien 1.1.2.1 while(!W.isEmpty()){
360 vivien 1.1.2.1 PANode n = (PANode) W.remove();
361 vivien 1.1.2.1 G.I.forAllPointedNodes(n, new PANodeVisitor(){
362 vivien 1.1.2.1 public void visit(PANode n2){
363 vivien 1.1.2.1 important = true;
364 vivien 1.1.2.1 }
365 vivien 1.1.2.1 });
366 vivien 1.1.2.1 if(important) return true;
367 vivien 1.1.2.1 G.O.forAllPointedNodes(n, new PANodeVisitor(){
368 vivien 1.1.2.1 public void visit(PANode n2){
369 vivien 1.1.2.1 // add to the worklist newly discovered nodes
370 vivien 1.1.2.1 if(set.add(n2)){
371 vivien 1.1.2.1 if(directlyInteresting(n2))
372 vivien 1.1.2.1 important = true;
373 vivien 1.1.2.1 W.add(n2);
374 vivien 1.1.2.1 }
375 vivien 1.1.2.1 }
376 vivien 1.1.2.1 });
377 vivien 1.1.2.1 if(important) return true;
378 vivien 1.1.2.1 }
379 vivien 1.1.2.1
380 vivien 1.1.2.1 return false;
381 vivien 1.1.2.1 }
382 vivien 1.1.2.1
383 vivien 1.1.2.1
384 vivien 1.1.2.1 // Visits all the nodes from set_nodes.
385 vivien 1.1.2.1 private void forSet(Set set_nodes, PANodeVisitor visitor){
386 vivien 1.1.2.1 Iterator it_nodes = set_nodes.iterator();
387 vivien 1.1.2.1 while(it_nodes.hasNext())
388 vivien 1.1.2.1 visitor.visit((PANode) it_nodes.next());
389 vivien 1.1.2.1 }
390 vivien 1.1.2.1
391 vivien 1.1.2.1 /** Visits all the nodes that appear in <code>this</code> graph. */
392 vivien 1.1.2.1 public void forAllNodes(final PANodeVisitor visitor){
393 vivien 1.1.2.1 G.O.forAllNodes(visitor);
394 vivien 1.1.2.1 G.I.forAllNodes(visitor);
395 vivien 1.1.2.1 forSet(G.r,visitor);
396 vivien 1.1.2.1 forSet(G.excp,visitor);
397 vivien 1.1.2.1 forSet(G.e.escapedNodes(),visitor);
398 vivien 1.1.2.1 forSet(tau.activeThreadSet(),visitor);
399 vivien 1.1.2.1
400 vivien 1.1.2.1 ar.forAllActions(new ActionVisitor(){
401 vivien 1.1.2.1 public void visit_ld(PALoad load){
402 vivien 1.1.2.1 visitor.visit(load.n1);
403 vivien 1.1.2.1 visitor.visit(load.n2);
404 vivien 1.1.2.1 visitor.visit(load.nt);
405 vivien 1.1.2.1 }
406 vivien 1.1.2.1 public void visit_sync(PASync sync){
407 vivien 1.1.2.1 visitor.visit(sync.n);
408 vivien 1.1.2.1 visitor.visit(sync.nt);
409 vivien 1.1.2.1 }
410 vivien 1.1.2.1 });
411 vivien 1.1.2.1
412 vivien 1.1.2.1 ar.forAllParActions(new ParActionVisitor() {
413 vivien 1.1.2.1 public void visit_par_ld(PALoad load, PANode nt2) {
414 vivien 1.1.2.1 visitor.visit(nt2);
415 vivien 1.1.2.1 }
416 vivien 1.1.2.1 public void visit_par_sync(PASync sync, PANode nt2) {
417 vivien 1.1.2.1 visitor.visit(nt2);
418 vivien 1.1.2.1 }
419 vivien 1.1.2.1 });
420 vivien 1.1.2.1
421 vivien 1.1.2.1 // the edges appearing in the edge ordering relation are also
422 vivien 1.1.2.1 // present into G.O and G.I and so, they have been already visited
423 vivien 1.1.2.1 }
424 vivien 1.1.2.1
425 vivien 1.1.2.1
426 vivien 1.1.2.1 private Set all_nodes = null;
427 vivien 1.1.2.1
428 vivien 1.1.2.1 /** Returns the set of all the nodes that appear in <code>this</code>
429 vivien 1.1.2.1 parallel interaction graph.<br>
430 vivien 1.1.2.1 <b>Warning:</b> This method should be called only on graphs that
431 vivien 1.1.2.1 are final (ie they won't be modified through something as an edge
432 vivien 1.1.2.1 addition, etc.). */
433 vivien 1.1.2.1 public Set allNodes(){
434 vivien 1.1.2.1 // if(all_nodes == null){
435 vivien 1.1.2.1 final Set nodes = new HashSet();
436 vivien 1.1.2.1 forAllNodes(new PANodeVisitor(){
437 vivien 1.1.2.1 public void visit(PANode node){
438 vivien 1.1.2.1 nodes.add(node);
439 vivien 1.1.2.1 }
440 vivien 1.1.2.1 });
441 vivien 1.1.2.1 all_nodes = nodes;
442 vivien 1.1.2.1 // }
443 vivien 1.1.2.1 all_nodes.remove(ActionRepository.THIS_THREAD);
444 vivien 1.1.2.1 return all_nodes;
445 vivien 1.1.2.1 }
446 vivien 1.1.2.1
447 vivien 1.1.2.1 /* Specialize <code>this</code> <code>ODParIntGraph</code> for the call
448 vivien 1.1.2.1 site <code>q</code>. */
449 vivien 1.1.2.1 final ODParIntGraph csSpecialize(final CALL call){
450 vivien 1.1.2.1 /* contains mappings old node -> specialized node; each unmapped
451 vivien 1.1.2.1 node is supposed to be mapped to itself. */
452 vivien 1.1.2.1 all_nodes = null;
453 vivien 1.1.2.1 final Map map = new HashMap();
454 vivien 1.1.2.1 final Map total_map = new HashMap();
455 cananian 1.5 for(Object nodeO : allNodes()){
456 cananian 1.5 PANode node = (PANode) nodeO;
457 vivien 1.1.2.1 if(node.type == PANode.INSIDE){
458 vivien 1.1.2.1 map.put(node, node.csSpecialize(call));
459 vivien 1.1.2.1 total_map.put(node, node.csSpecialize(call));
460 vivien 1.1.2.1 }
461 vivien 1.1.2.1 else {
462 vivien 1.1.2.1 total_map.put(node, node);
463 vivien 1.1.2.1 }
464 vivien 1.1.2.1 }
465 vivien 1.1.2.1
466 vivien 1.1.2.1 return new ODParIntGraph(G.specialize(map), tau.specialize(map),
467 vivien 1.1.2.1 ar.csSpecialize(map, call),
468 vivien 1.1.2.1 PointerAnalysis.IGNORE_EO? null:eo.specialize(map),
469 vivien 1.1.2.1 PANode.specialize_set(touched_threads, map),
470 vivien 1.1.2.1 odi.specialize(total_map));
471 vivien 1.1.2.1 }
472 vivien 1.1.2.1
473 vivien 1.1.2.1 /* Specializes <code>this</code> <code>ActionRepository</code> for the
474 vivien 1.1.2.1 thread whose run method is <code>run</code>. */
475 vivien 1.1.2.1 final ODParIntGraph tSpecialize(final MetaMethod run){
476 vivien 1.1.2.1 // contains mappings old node -> speciaized node; each unmapped
477 vivien 1.1.2.1 // node is supposed to be mapped to itself.
478 vivien 1.1.2.1 final Map map = new HashMap();
479 cananian 1.5 for(Object nodeO : allNodes()){
480 cananian 1.5 PANode node = (PANode) nodeO;
481 vivien 1.1.2.1 if((node.type != PANode.PARAM) && (node.type != PANode.STATIC)){
482 vivien 1.1.2.1 PANode node2 = node.tSpecialize(run);
483 vivien 1.1.2.1 map.put(node, node2);
484 vivien 1.1.2.1 }
485 vivien 1.1.2.1 }
486 vivien 1.1.2.1
487 vivien 1.1.2.1 System.err.println("******* WTF ????????? *******");
488 vivien 1.1.2.1
489 vivien 1.1.2.1 return
490 vivien 1.1.2.1 new ODParIntGraph(G.specialize(map), tau.specialize(map),
491 vivien 1.1.2.1 ar.tSpecialize(map, run),
492 vivien 1.1.2.1 PointerAnalysis.IGNORE_EO? null: eo.specialize(map),
493 vivien 1.1.2.1 PANode.specialize_set(touched_threads, map));
494 vivien 1.1.2.1 }
495 vivien 1.1.2.1
496 vivien 1.1.2.1 // weak thread specialization
497 vivien 1.1.2.1 final ODParIntGraph wtSpecialize(final MetaMethod run){
498 vivien 1.1.2.1 // contains mappings old node -> speciaized node; each unmapped
499 vivien 1.1.2.1 // node is supposed to be mapped to itself.
500 vivien 1.1.2.1 final Map map = new HashMap();
501 cananian 1.5 for(Object nodeO : allNodes()){
502 cananian 1.5 PANode node = (PANode) nodeO;
503 vivien 1.1.2.1 if((node.type != PANode.PARAM) && (node.type != PANode.STATIC)){
504 vivien 1.1.2.1 PANode node2 = node.wtSpecialize();
505 vivien 1.1.2.1 map.put(node, node2);
506 vivien 1.1.2.1 }
507 vivien 1.1.2.1 }
508 vivien 1.1.2.1
509 vivien 1.1.2.1 System.err.println("******* WTF ????????? *******");
510 vivien 1.1.2.1
511 vivien 1.1.2.1
512 vivien 1.1.2.1 return
513 vivien 1.1.2.1 new ODParIntGraph(G.specialize(map), tau.specialize(map),
514 vivien 1.1.2.1 ar.tSpecialize(map, run),
515 vivien 1.1.2.1 PointerAnalysis.IGNORE_EO?null:eo.specialize(map),
516 vivien 1.1.2.1 PANode.specialize_set(touched_threads, map));
517 vivien 1.1.2.1 }
518 vivien 1.1.2.1
519 vivien 1.1.2.1
520 vivien 1.1.2.1 /** Removes the nodes from <code>nodes</code> from <code>this</code>
521 vivien 1.1.2.1 graph. */
522 vivien 1.1.2.1 public void remove(Set nodes){
523 vivien 1.1.2.1 G.remove(nodes);
524 vivien 1.1.2.1 tau.remove(nodes);
525 vivien 1.1.2.1 ar.removeNodes(nodes);
526 vivien 1.1.2.1
527 vivien 1.1.2.1 if(!PointerAnalysis.IGNORE_EO)
528 vivien 1.1.2.1 eo.removeNodes(nodes);
529 vivien 1.1.2.1
530 vivien 1.1.2.1 touched_threads.removeAll(nodes);
531 vivien 1.1.2.1 }
532 vivien 1.1.2.1
533 vivien 1.1.2.1 /** Simplify <code>this</code> parallel interaction graph by removing the
534 vivien 1.1.2.1 loads that don't escape anywhere (and hence, don't represent any
535 vivien 1.1.2.1 object). In addition, the <code><<n1,f>,n2></code>
536 vivien 1.1.2.1 ouside (load) edges where <code>n1</code> is an unescaped node are
537 vivien 1.1.2.1 removed too. */
538 vivien 1.1.2.1 public void removeEmptyLoads(){
539 vivien 1.1.2.1 final Set empty_loads = new HashSet();
540 vivien 1.1.2.1 final Set fake_outside_edges = new HashSet();
541 vivien 1.1.2.1
542 vivien 1.1.2.1 G.O.forAllEdges(new PAEdgeVisitor(){
543 vivien 1.1.2.1 public void visit(Temp var, PANode node){}
544 vivien 1.1.2.1 public void visit(PANode node1, String f, PANode node2){
545 vivien 1.1.2.1 if(!G.e.hasEscaped(node1))
546 vivien 1.1.2.1 fake_outside_edges.add(new PAEdge(node1,f,node2));
547 vivien 1.1.2.1 if(!G.e.hasEscaped(node2))
548 vivien 1.1.2.1 empty_loads.add(node2);
549 vivien 1.1.2.1 }
550 vivien 1.1.2.1 });
551 vivien 1.1.2.1
552 vivien 1.1.2.1 if(DEBUG){
553 vivien 1.1.2.1 System.out.println("Empty loads:" + empty_loads);
554 vivien 1.1.2.1 System.out.println("Fake outside edges: " + fake_outside_edges);
555 vivien 1.1.2.1 }
556 vivien 1.1.2.1
557 vivien 1.1.2.1 remove(empty_loads);
558 vivien 1.1.2.1
559 cananian 1.5 for (Object edgeO : fake_outside_edges){
560 cananian 1.5 PAEdge edge = (PAEdge) edgeO;
561 vivien 1.1.2.1 G.O.removeEdge(edge.n1,edge.f,edge.n2);
562 vivien 1.1.2.1 }
563 vivien 1.1.2.1
564 vivien 1.1.2.1 ar.removeEdges(fake_outside_edges);
565 vivien 1.1.2.1
566 vivien 1.1.2.1 if(!PointerAnalysis.IGNORE_EO)
567 vivien 1.1.2.1 eo.removeEdges(fake_outside_edges);
568 vivien 1.1.2.1 }
569 vivien 1.1.2.1
570 vivien 1.1.2.1 public void removeEmptyLoads(final Set empty_loads,
571 vivien 1.1.2.1 final Set fake_outside_edges)
572 vivien 1.1.2.1 {
573 vivien 1.1.2.1 G.O.forAllEdges(new PAEdgeVisitor(){
574 vivien 1.1.2.1 public void visit(Temp var, PANode node){}
575 vivien 1.1.2.1 public void visit(PANode node1, String f, PANode node2){
576 vivien 1.1.2.1 if(!G.e.hasEscaped(node1))
577 vivien 1.1.2.1 fake_outside_edges.add(new PAEdge(node1,f,node2));
578 vivien 1.1.2.1 if(!G.e.hasEscaped(node2))
579 vivien 1.1.2.1 empty_loads.add(node2);
580 vivien 1.1.2.1 }
581 vivien 1.1.2.1 });
582 vivien 1.1.2.1
583 vivien 1.1.2.1 if(DEBUG){
584 vivien 1.1.2.1 System.out.println("Empty loads:" + empty_loads);
585 vivien 1.1.2.1 System.out.println("Fake outside edges: " + fake_outside_edges);
586 vivien 1.1.2.1 }
587 vivien 1.1.2.1
588 vivien 1.1.2.1 remove(empty_loads);
589 vivien 1.1.2.1
590 cananian 1.5 for (Object edgeO : fake_outside_edges){
591 cananian 1.5 PAEdge edge = (PAEdge) edgeO;
592 vivien 1.1.2.1 G.O.removeEdge(edge.n1,edge.f,edge.n2);
593 vivien 1.1.2.1 }
594 vivien 1.1.2.1
595 vivien 1.1.2.1 ar.removeEdges(fake_outside_edges);
596 vivien 1.1.2.1
597 vivien 1.1.2.1 if(!PointerAnalysis.IGNORE_EO)
598 vivien 1.1.2.1 eo.removeEdges(fake_outside_edges);
599 vivien 1.1.2.1 }
600 vivien 1.1.2.1
601 vivien 1.1.2.1 /** Pretty-print function for debug purposes.
602 vivien 1.1.2.1 Two equal <code>ODParIntGraph</code>s are guaranteed to have the same
603 vivien 1.1.2.1 string representation. */
604 vivien 1.1.2.1 public String toString(){
605 vivien 1.1.2.1
606 vivien 1.1.2.1
607 vivien 1.1.2.1 final StringBuffer buffer = new StringBuffer();
608 vivien 1.1.2.1
609 vivien 1.1.2.1 return
610 vivien 1.1.2.1 "\nODParIntGraph{\n" + buffer + G + " " + tau +
611 vivien 1.1.2.1 " Touched threads: " + touchedToString() + "\n" +
612 vivien 1.1.2.1 ar +
613 vivien 1.1.2.1 (PointerAnalysis.IGNORE_EO ? "" : eo.toString()) +
614 vivien 1.1.2.1 odi +
615 vivien 1.1.2.1 "}";
616 vivien 1.1.2.1 }
617 vivien 1.1.2.1
618 vivien 1.1.2.1 // Produces a string representation of the
619 vivien 1.1.2.1 // captured, started but touched threads.
620 vivien 1.1.2.1 private String touchedToString(){
621 vivien 1.1.2.1 StringBuffer buffer = new StringBuffer();
622 vivien 1.1.2.1
623 cananian 1.5 for (Object ntO : touched_threads){
624 cananian 1.5 PANode nt = (PANode) ntO;
625 vivien 1.1.2.1 if(G.captured(nt))
626 vivien 1.1.2.1 buffer.append(nt + " ");
627 vivien 1.1.2.1 }
628 vivien 1.1.2.1 return buffer.toString();
629 vivien 1.1.2.1 }
630 vivien 1.1.2.1
631 vivien 1.1.2.1
632 vivien 1.1.2.1 /** Checks whether two <code>ODParIntGraph</code>s are equal or not. In
633 vivien 1.1.2.1 addition to the <code>equals</code> method, this handles the
634 vivien 1.1.2.1 comparisom of <code>null</code> objects. */
635 vivien 1.1.2.1 public static boolean identical(ODParIntGraph pig1, ODParIntGraph pig2){
636 vivien 1.1.2.1 if((pig1 == null) || (pig2 == null))
637 vivien 1.1.2.1 return (pig1 == pig2);
638 vivien 1.1.2.1 return pig1.equals(pig2);
639 vivien 1.1.2.1 }
640 vivien 1.1.2.1
641 vivien 1.1.2.1 public boolean isCoherent(){
642 vivien 1.1.2.1 // HashSet reference = new HashSet(method_holes);
643 vivien 1.1.2.1 // reference.add(ODPointerAnalysis.BottomHole);
644 vivien 1.1.2.1
645 vivien 1.1.2.1 // //System.out.println("*** Entering isCoherent ");
646 vivien 1.1.2.1
647 vivien 1.1.2.1 // // System.out.println("history_holes");
648 vivien 1.1.2.1 // HashSet history_holes = new HashSet();
649 vivien 1.1.2.1 // history_holes.addAll(holes_history.keys());
650 vivien 1.1.2.1 // for(Iterator h_it=holes_history.keys().iterator(); h_it.hasNext(); )
651 vivien 1.1.2.1 // history_holes.addAll(holes_history.getValues(h_it.next()));
652 vivien 1.1.2.1 // if (!(reference.containsAll(history_holes))){
653 vivien 1.1.2.1 // System.err.println("Inconsistent holes_history: ");
654 vivien 1.1.2.1 // System.out.println("Inconsistent holes_history: ");
655 vivien 1.1.2.1 // Set f_nodes = history_holes;
656 vivien 1.1.2.1 // f_nodes.removeAll(reference);
657 vivien 1.1.2.1 // System.out.println("faulty holes: " + f_nodes);
658 vivien 1.1.2.1 // System.out.println("holes: " + reference);
659 vivien 1.1.2.1 // System.out.println("*** Leaving isCoherent ");
660 vivien 1.1.2.1 // return false;
661 vivien 1.1.2.1 // }
662 vivien 1.1.2.1
663 vivien 1.1.2.1 // // System.out.println("in_edge_always");
664 vivien 1.1.2.1 // if (!(reference.containsAll
665 vivien 1.1.2.1 // (ODPointerAnalysis.extractHoles(in_edge_always)))){
666 vivien 1.1.2.1 // System.err.println("Inconsistent in_edge_always: ");
667 vivien 1.1.2.1 // System.out.println("Inconsistent in_edge_always: ");
668 vivien 1.1.2.1 // Set f_nodes = ODPointerAnalysis.extractHoles(in_edge_always);
669 vivien 1.1.2.1 // f_nodes.removeAll(reference);
670 vivien 1.1.2.1 // System.out.println("faulty holes: " + f_nodes);
671 vivien 1.1.2.1 // System.out.println("holes: " + reference);
672 vivien 1.1.2.1 // System.out.println("*** Leaving isCoherent ");
673 vivien 1.1.2.1 // return false;
674 vivien 1.1.2.1 // }
675 vivien 1.1.2.1
676 vivien 1.1.2.1 // // System.out.println("out_edge_always");
677 vivien 1.1.2.1 // if (!(reference.containsAll
678 vivien 1.1.2.1 // (ODPointerAnalysis.extractHoles(out_edge_always)))){
679 vivien 1.1.2.1 // System.err.println("Inconsistent out_edge_always: ");
680 vivien 1.1.2.1 // System.out.println("Inconsistent out_edge_always: ");
681 vivien 1.1.2.1 // Set f_nodes = ODPointerAnalysis.extractHoles(out_edge_always);
682 vivien 1.1.2.1 // f_nodes.removeAll(reference);
683 vivien 1.1.2.1 // System.out.println("faulty holes: " + f_nodes);
684 vivien 1.1.2.1 // System.out.println("holes: " + reference);
685 vivien 1.1.2.1 // System.out.println("*** Leaving isCoherent ");
686 vivien 1.1.2.1 // return false;
687 vivien 1.1.2.1 // }
688 vivien 1.1.2.1
689 vivien 1.1.2.1 // // System.out.println("out_edge_maybe");
690 vivien 1.1.2.1 // if (!(reference.containsAll
691 vivien 1.1.2.1 // (ODPointerAnalysis.extractHoles(out_edge_maybe)))){
692 vivien 1.1.2.1 // System.err.println("Inconsistent out_edge_maybe: ");
693 vivien 1.1.2.1 // System.out.println("Inconsistent out_edge_maybe: ");
694 vivien 1.1.2.1 // Set f_nodes = ODPointerAnalysis.extractHoles(out_edge_maybe);
695 vivien 1.1.2.1 // f_nodes.removeAll(reference);
696 vivien 1.1.2.1 // System.out.println("faulty holes: " + f_nodes);
697 vivien 1.1.2.1 // System.out.println("holes: " + reference);
698 vivien 1.1.2.1 // System.out.println("*** Leaving isCoherent ");
699 vivien 1.1.2.1 // return false;
700 vivien 1.1.2.1 // }
701 vivien 1.1.2.1
702 vivien 1.1.2.1 // // System.out.println("locks");
703 vivien 1.1.2.1 // HashSet locks_holes = new HashSet();
704 vivien 1.1.2.1 // for(Iterator l_it=locks.keys().iterator(); l_it.hasNext(); )
705 vivien 1.1.2.1 // locks_holes.addAll(locks.getValues(l_it.next()));
706 vivien 1.1.2.1 // if (!(reference.containsAll(locks_holes))){
707 vivien 1.1.2.1 // System.err.println("Inconsistent locks: ");
708 vivien 1.1.2.1 // System.out.println("Inconsistent locks: ");
709 vivien 1.1.2.1 // Set f_nodes = locks_holes;
710 vivien 1.1.2.1 // f_nodes.removeAll(reference);
711 vivien 1.1.2.1 // System.out.println("faulty holes: " + f_nodes);
712 vivien 1.1.2.1 // System.out.println("holes: " + reference);
713 vivien 1.1.2.1 // System.out.println("*** Leaving isCoherent ");
714 vivien 1.1.2.1 // return false;
715 vivien 1.1.2.1 // }
716 vivien 1.1.2.1
717 vivien 1.1.2.1 // // System.out.println("*** Leaving isCoherent ");
718 vivien 1.1.2.1 return true;
719 vivien 1.1.2.1 }
720 vivien 1.1.2.1
721 cananian 1.2 }