1 salcianu 1.1.2.1 // InterThreadPA.java, created Mon Jan 31 20:52:46 2000 by salcianu
2 cananian 1.1.2.39 // 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.1 import java.util.Set;
7 salcianu 1.1.2.2 import java.util.HashSet;
8 salcianu 1.1.2.7 import java.util.Iterator;
9 salcianu 1.1.2.1 import java.util.Enumeration;
10 salcianu 1.1.2.6 import java.util.Collections;
11 salcianu 1.1.2.5 import java.util.Date;
12 salcianu 1.1.2.1
13 salcianu 1.1.2.1 import harpoon.Util.Util;
14 salcianu 1.1.2.1 import harpoon.ClassFile.HMethod;
15 salcianu 1.1.2.4 import harpoon.ClassFile.HClass;
16 salcianu 1.1.2.1 import harpoon.Temp.Temp;
17 salcianu 1.1.2.1
18 salcianu 1.1.2.4 import harpoon.IR.Quads.NEW;
19 salcianu 1.1.2.21 import harpoon.IR.Quads.Quad;
20 salcianu 1.1.2.4
21 salcianu 1.1.2.16 import harpoon.Analysis.MetaMethods.MetaMethod;
22 salcianu 1.1.2.16 import harpoon.Analysis.MetaMethods.GenType;
23 salcianu 1.1.2.18 import harpoon.Analysis.MetaMethods.MetaCallGraph;
24 salcianu 1.1.2.16
25 salcianu 1.1.2.31 import harpoon.Util.DataStructs.Relation;
26 salcianu 1.1.2.38 import harpoon.Util.DataStructs.RelationImpl;
27 salcianu 1.1.2.31 import harpoon.Util.DataStructs.LightRelation;
28 salcianu 1.1.2.31 import harpoon.Util.DataStructs.RelationEntryVisitor;
29 salcianu 1.1.2.31
30 salcianu 1.1.2.4
31 salcianu 1.1.2.1 /**
32 salcianu 1.1.2.12 * <code>InterThreadPA</code> groups together the functions related to the
33 salcianu 1.1.2.27 * inter-thread analysis. Normally, this should be a part of the
34 salcianu 1.1.2.27 * <code>PointerAnalysis</code> class, but that class is
35 salcianu 1.1.2.27 * already too big and some code segmentation is always good!<br>
36 salcianu 1.1.2.27 *
37 salcianu 1.1.2.27 * In the implementation of this class, some of the methods are static and
38 salcianu 1.1.2.27 * have <code>PointerAnalysis pa</code> as their first parameter.
39 salcianu 1.1.2.27 * <code>pa</code> stands for the <code>this</code> <i>hidden</i> parameter
40 salcianu 1.1.2.27 * that would exist if all those methods were in the
41 salcianu 1.1.2.27 * <code>PointerAnalysis</code> class.
42 salcianu 1.1.2.1 *
43 cananian 1.1.2.39 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
44 cananian 1.7 * @version $Id: InterThreadPA.java,v 1.7 2004/02/08 03:20:02 cananian Exp $
45 salcianu 1.1.2.1 */
46 salcianu 1.1.2.35 public abstract class InterThreadPA implements java.io.Serializable {
47 salcianu 1.1.2.28
48 salcianu 1.1.2.27 /** Activates a lot of debug messages. */
49 salcianu 1.1.2.36 public static final boolean DEBUG = true;
50 salcianu 1.1.2.27 /** Activates even more debug messages! */
51 salcianu 1.1.2.19 public static final boolean DEBUG2 = false;
52 salcianu 1.1.2.27 /** Displays some time statistics. */
53 salcianu 1.1.2.37 public static boolean TIMING = true;
54 salcianu 1.1.2.5
55 salcianu 1.1.2.27 /* Set of all the processed threads (thread nodes). PANodes keep
56 salcianu 1.1.2.27 accumulating here since the beginning of the inter-thread analysis,
57 salcianu 1.1.2.27 without any clear(), even if some thread nodes are reanalyzed when the
58 salcianu 1.1.2.27 graph has changed. */
59 salcianu 1.1.2.12 private static final Set processed_threads = new HashSet();
60 salcianu 1.1.2.12
61 salcianu 1.1.2.27 /** Do the inter-thread analysis for a method.
62 salcianu 1.1.2.27 *
63 salcianu 1.1.2.27 * @param pa The <code>PointerAnalysis</code> object that called
64 salcianu 1.1.2.27 * this method and that generated <code>noit_pig</code>. This parameter
65 salcianu 1.1.2.27 * stands for the <i>hidden</i> <code>this</code> parameter that would
66 salcianu 1.1.2.27 * exist if the methods of this class were part of the
67 salcianu 1.1.2.27 * <code>PointerAnalysis</code> class.
68 salcianu 1.1.2.27 * @param noit_pig The Parallel Interaction Graph at the end of
69 salcianu 1.1.2.27 * the method, as produced by the intra and inter-procedural analysis.
70 salcianu 1.1.2.27 *
71 salcianu 1.1.2.27 * @return the Parallel Interaction Graph modeling the interaction
72 salcianu 1.1.2.27 * between the method (that is just a part of the thread that launched
73 salcianu 1.1.2.27 * it) and the threads it transitively starts.
74 salcianu 1.1.2.27 */
75 salcianu 1.1.2.27 public static ParIntGraph resolve_threads(PointerAnalysis pa,
76 salcianu 1.1.2.27 ParIntGraph noit_pig) {
77 salcianu 1.1.2.18 // This is the set of all the analyzed threads. When the graph has
78 salcianu 1.1.2.18 // changed, this set is cleared, so that some of the threads are
79 salcianu 1.1.2.18 // reanalyzed.
80 salcianu 1.1.2.18 final Set analyzed_threads = new HashSet();
81 salcianu 1.1.2.5
82 salcianu 1.1.2.26 if(DEBUG)
83 salcianu 1.1.2.26 System.out.println("Inter-thread analysis started ...");
84 salcianu 1.1.2.25
85 salcianu 1.1.2.15 long begin_time = 0;
86 salcianu 1.1.2.12 if(TIMING) begin_time = System.currentTimeMillis();
87 salcianu 1.1.2.12
88 salcianu 1.1.2.12 processed_threads.clear();
89 salcianu 1.1.2.2
90 salcianu 1.1.2.24 ParIntGraph pig = (ParIntGraph) noit_pig.clone();
91 salcianu 1.1.2.6
92 salcianu 1.1.2.38 if(DEBUG2)
93 salcianu 1.1.2.28 System.out.println("Initial thread map:" + pig.tau);
94 salcianu 1.1.2.28
95 salcianu 1.1.2.38 PANode nt;
96 salcianu 1.1.2.38
97 salcianu 1.1.2.38 // process first the threads nt with tau(nt) = 1
98 salcianu 1.1.2.38 /*
99 salcianu 1.1.2.38 while((nt = pick_an_unanalyzed_thread(pig,analyzed_threads)) != null) {
100 salcianu 1.1.2.38 analyzed_threads.add(nt);
101 salcianu 1.1.2.38 if(pig.tau.getValue(nt) != 1)
102 salcianu 1.1.2.38 continue;
103 salcianu 1.1.2.38
104 salcianu 1.1.2.38 MetaMethod[] ops = get_run_mmethods(pa, nt);
105 salcianu 1.1.2.38 pig = interaction_nt(pa, pig, nt, ops);
106 salcianu 1.1.2.38
107 salcianu 1.1.2.38 if(pig.tau.getValue(nt) == 1) {
108 salcianu 1.1.2.38 pig.G.e.removeNodeHoleFromAll(nt);
109 salcianu 1.1.2.38 pig.removeEmptyLoads();
110 salcianu 1.1.2.38 pig.tau.setToZero(nt);
111 cananian 1.3.2.1 assert pig.tau.getValue(nt) == 0 : "Error";
112 salcianu 1.1.2.38 }
113 salcianu 1.1.2.38 }
114 salcianu 1.1.2.38 analyzed_threads.clear();
115 salcianu 1.1.2.38
116 salcianu 1.1.2.38 nt = pick_an_unanalyzed_thread(pig, analyzed_threads);
117 salcianu 1.1.2.38 if(nt == null) return pig;
118 salcianu 1.1.2.38
119 salcianu 1.1.2.38 int old_tau_nt = pig.tau.getValue(nt);
120 salcianu 1.1.2.38 if(old_tau_nt == 1) {
121 salcianu 1.1.2.38 MetaMethod[] ops = get_run_mmethods(pa, nt);
122 salcianu 1.1.2.38 pig = interaction_nt(pa, pig, nt, ops);
123 salcianu 1.1.2.38 int new_tau_nt = pig.tau.getValue(nt);
124 salcianu 1.1.2.38 System.out.println("nt = " + nt);
125 salcianu 1.1.2.38 System.out.println("old_tau_nt = " + old_tau_nt);
126 salcianu 1.1.2.38 System.out.println("new_tau_nt = " + new_tau_nt);
127 salcianu 1.1.2.38 pig.G.e.removeNodeHoleFromAll(nt);
128 salcianu 1.1.2.38 pig.tau.setToZero(nt);
129 cananian 1.3.2.1 assert pig.tau.getValue(nt) == 0 : "Error";
130 salcianu 1.1.2.38 pig.removeEmptyLoads();
131 salcianu 1.1.2.38 System.out.println("RESULTING PIG (after cleaning)" + pig);
132 salcianu 1.1.2.38 }
133 salcianu 1.1.2.38 */
134 salcianu 1.1.2.38
135 salcianu 1.1.2.38 while((nt = pick_an_unanalyzed_thread(pig,analyzed_threads)) != null) {
136 salcianu 1.1.2.2
137 salcianu 1.1.2.26 if(DEBUG)
138 salcianu 1.1.2.5 System.out.println(nt + " was chosen");
139 salcianu 1.1.2.5
140 salcianu 1.1.2.27 MetaMethod[] ops = get_run_mmethods(pa, nt);
141 salcianu 1.1.2.2 analyzed_threads.add(nt);
142 salcianu 1.1.2.5 if((ops == null) || (ops.length==0) ||
143 salcianu 1.1.2.27 !analyzable_run_mmethods(pa, ops)) continue;
144 salcianu 1.1.2.5
145 salcianu 1.1.2.24 ParIntGraph old_pig = pig;
146 salcianu 1.1.2.27 pig = interaction_nt(pa, pig, nt, ops);
147 salcianu 1.1.2.2
148 salcianu 1.1.2.33 // ParIntGraph.DEBUG2 = true;
149 salcianu 1.1.2.22 if(!pig.equals(old_pig)){
150 salcianu 1.1.2.22 if(DEBUG)
151 salcianu 1.1.2.22 System.out.println("The graph has changed");
152 salcianu 1.1.2.2 analyzed_threads.clear();
153 salcianu 1.1.2.22 }
154 salcianu 1.1.2.33 // ParIntGraph.DEBUG2 = false;
155 salcianu 1.1.2.18
156 salcianu 1.1.2.18 analyzed_threads.add(nt);
157 salcianu 1.1.2.18 processed_threads.add(nt);
158 salcianu 1.1.2.2 }
159 salcianu 1.1.2.22
160 salcianu 1.1.2.22 // the threads that have been analyzed are no longer holes
161 salcianu 1.1.2.38 for(Iterator it = processed_threads.iterator(); it.hasNext();) {
162 salcianu 1.1.2.38 nt = (PANode) it.next();
163 salcianu 1.1.2.22 if(DEBUG)
164 salcianu 1.1.2.22 System.out.println("Removed thread hole: " + nt);
165 salcianu 1.1.2.22 pig.G.e.removeNodeHoleFromAll(nt);
166 salcianu 1.1.2.22 }
167 salcianu 1.1.2.28 // clean up some of the useless LOAD nodes
168 salcianu 1.1.2.22 pig.removeEmptyLoads();
169 salcianu 1.1.2.22
170 salcianu 1.1.2.38 if(DEBUG2)
171 salcianu 1.1.2.38 System.out.println("RESULTING PIG (WITHOUT EMPTY LOADS): " + pig);
172 salcianu 1.1.2.38
173 salcianu 1.1.2.6 if(TIMING){
174 salcianu 1.1.2.10 long total_time = System.currentTimeMillis() - begin_time;
175 salcianu 1.1.2.6 System.out.println("Inter-thread analysis done in " +
176 salcianu 1.1.2.6 total_time + "ms");
177 salcianu 1.1.2.5 }
178 salcianu 1.1.2.5
179 salcianu 1.1.2.5 return pig;
180 salcianu 1.1.2.5 }
181 salcianu 1.1.2.5
182 salcianu 1.1.2.5
183 salcianu 1.1.2.27 /* See if the run method(s) that could be the body of a thread are
184 salcianu 1.1.2.27 analyzable with regard to <code>pa</code> (i.e. <code>pa</code>
185 salcianu 1.1.2.27 can satisfy queries about these methods.) */
186 salcianu 1.1.2.27 private static boolean analyzable_run_mmethods(PointerAnalysis pa,
187 salcianu 1.1.2.27 MetaMethod[] ops) {
188 salcianu 1.1.2.5 for(int i = 0 ; i < ops.length ; i++)
189 salcianu 1.1.2.5 if((ops[i] == null) || (pa.getExtParIntGraph(ops[i]) == null))
190 salcianu 1.1.2.5 return false;
191 salcianu 1.1.2.16 return true;
192 salcianu 1.1.2.2 }
193 salcianu 1.1.2.2
194 salcianu 1.1.2.2
195 salcianu 1.1.2.27 /* Finds an active thread node (i.e. tau(nt) != 0) whose interactions
196 salcianu 1.1.2.27 with the Starter haven't been analyzed yet. */
197 salcianu 1.1.2.2 private static PANode pick_an_unanalyzed_thread(ParIntGraph pig,
198 salcianu 1.1.2.2 Set analyzed_threads){
199 cananian 1.6 Enumeration _enum_ = pig.tau.activeThreads();
200 cananian 1.6 while(_enum_.hasMoreElements()){
201 cananian 1.6 PANode nt = (PANode) _enum_.nextElement();
202 salcianu 1.1.2.4 if((nt.type == PANode.INSIDE) && !analyzed_threads.contains(nt))
203 salcianu 1.1.2.2 return nt;
204 salcianu 1.1.2.2 }
205 salcianu 1.1.2.2 return null;
206 salcianu 1.1.2.2 }
207 salcianu 1.1.2.2
208 salcianu 1.1.2.27
209 salcianu 1.1.2.27 /* Returns a vector containing all the run() methods that could be
210 salcianu 1.1.2.27 the body of the threads abstracted by nt. */
211 salcianu 1.1.2.27 private static MetaMethod[] get_run_mmethods(PointerAnalysis pa,
212 salcianu 1.1.2.27 PANode nt) {
213 salcianu 1.1.2.12 // TODO: think about the LOAD && PARAM thread nodes (not only INSIDE)
214 salcianu 1.1.2.24 Quad quad = (Quad) pa.getNodeRepository().node2Code(nt.getRoot());
215 salcianu 1.5 assert (quad instanceof NEW) :
216 salcianu 1.5 nt + " has a strange instr." +
217 salcianu 1.5 " nt type: " + nt.type + " != PANode.INSIDE";
218 salcianu 1.5
219 salcianu 1.1.2.21 NEW q = (NEW) quad;
220 cananian 1.3.2.1 assert q != null : "Creation of " + nt + " not found!";
221 salcianu 1.1.2.4
222 salcianu 1.1.2.19 HClass hclass = q.hclass();
223 salcianu 1.1.2.4 HMethod[] hms = hclass.getMethods();
224 salcianu 1.1.2.4 HMethod hm = null;
225 salcianu 1.1.2.4 for(int i = 0 ; i < hms.length ; i++)
226 salcianu 1.1.2.5 if(hms[i].getName().equals("run") &&
227 salcianu 1.1.2.4 (hms[i].getParameterTypes().length == 0)){
228 salcianu 1.1.2.4 hm = hms[i];
229 salcianu 1.1.2.4 break;
230 salcianu 1.1.2.4 }
231 salcianu 1.1.2.4
232 salcianu 1.1.2.4 if(hm == null) return null;
233 salcianu 1.1.2.4
234 salcianu 1.1.2.16 MetaMethod mm_run =
235 salcianu 1.1.2.16 new MetaMethod(hm,new GenType[]{new GenType(hclass,GenType.MONO)});
236 salcianu 1.1.2.18
237 salcianu 1.1.2.18 // some hack to cope with the fake meta call graph when every
238 salcianu 1.1.2.18 // method is polymorphic in its arguments.
239 salcianu 1.1.2.18 // TODO: try to find something more intelligent!
240 salcianu 1.1.2.18 MetaCallGraph mcg = pa.getMetaCallGraph();
241 salcianu 1.1.2.18 if(!mcg.getAllMetaMethods().contains(mm_run))
242 salcianu 1.1.2.18 mm_run = new MetaMethod(hm,
243 salcianu 1.1.2.18 new GenType[]{new GenType(hclass, GenType.POLY)});
244 salcianu 1.1.2.16
245 salcianu 1.1.2.16 return new MetaMethod[]{mm_run};
246 salcianu 1.1.2.1 }
247 salcianu 1.1.2.1
248 salcianu 1.1.2.1
249 salcianu 1.1.2.27 /* Computes the interactions with all the threads launched by the node
250 salcianu 1.1.2.27 nt. If tau(nt)==1 (at most one such thread could exist), this method
251 salcianu 1.1.2.27 computes the interaction of the Starter with only one instance of an
252 salcianu 1.1.2.27 nt-thread. If tau(nt)==2 (there could be more than one thread, anything
253 salcianu 1.1.2.27 between 0 and infinity) a fixed-point algorithm is necessary. */
254 salcianu 1.1.2.27 private static ParIntGraph interaction_nt(PointerAnalysis pa,
255 salcianu 1.1.2.27 ParIntGraph pig, PANode nt,
256 salcianu 1.1.2.27 MetaMethod[] ops) {
257 salcianu 1.1.2.22
258 salcianu 1.1.2.22 ParIntGraph new_pig = null; /* it will point to the resulting pig */
259 salcianu 1.1.2.1 boolean only_once = (pig.tau.getValue(nt)==1);
260 salcianu 1.1.2.1
261 salcianu 1.1.2.26 if(DEBUG)
262 salcianu 1.1.2.22 System.out.println("interaction_nt: " + nt +
263 salcianu 1.1.2.22 (only_once?" only once":" many times"));
264 salcianu 1.1.2.5
265 salcianu 1.1.2.7 // save the old outside edge set
266 salcianu 1.1.2.7 PAEdgeSet old_O = pig.G.O;
267 salcianu 1.1.2.22 // consider only the outside edges read in // with an "nt" thread.
268 salcianu 1.1.2.22 pig.G.O = construct_new_O(pig, nt);
269 salcianu 1.1.2.22
270 salcianu 1.1.2.22 if(only_once){ // a single interaction is enough
271 salcianu 1.1.2.24 // make sure this is the only one the thread interaction is
272 salcianu 1.1.2.24 // resolved for the thread "nt" (because it is launched only once).
273 salcianu 1.1.2.22 pig.tau.dec(nt);
274 salcianu 1.1.2.27 new_pig = interact_once(pa, pig, nt, ops);
275 salcianu 1.1.2.22 }
276 salcianu 1.1.2.22 else{ // a fixed-point algorithm is necessary in this case
277 salcianu 1.1.2.24 new_pig = pig; // before the 1st iteration
278 salcianu 1.1.2.38 while(true) {
279 salcianu 1.1.2.22 ParIntGraph previous_pig = new_pig;
280 salcianu 1.1.2.27 new_pig = interact_once(pa, previous_pig, nt, ops);
281 salcianu 1.1.2.22 if(new_pig.equals(previous_pig)) break;
282 salcianu 1.1.2.1 }
283 salcianu 1.1.2.1 }
284 salcianu 1.1.2.1
285 salcianu 1.1.2.22 // add the old, unconsidered outside edges to the new graph ...
286 salcianu 1.1.2.22 new_pig.G.O.union(old_O);
287 salcianu 1.1.2.22 // [propagate the escape info on the newly added edges]
288 salcianu 1.1.2.22 new_pig.G.propagate();
289 salcianu 1.1.2.22 // and restore the graph received as argument
290 salcianu 1.1.2.22 pig.G.O = old_O;
291 salcianu 1.1.2.8
292 salcianu 1.1.2.38 if(DEBUG2)
293 salcianu 1.1.2.38 System.out.println("RESULTING PIG (unclean yet)" + new_pig);
294 salcianu 1.1.2.38
295 salcianu 1.1.2.22 return new_pig;
296 salcianu 1.1.2.7 }
297 salcianu 1.1.2.7
298 salcianu 1.1.2.7
299 salcianu 1.1.2.27 /* Constructs a new set of outside edges for pig, containing only those
300 salcianu 1.1.2.27 outside edges that are read in parallel with an nt thread.
301 salcianu 1.1.2.27 Returns the new set of edges. */
302 salcianu 1.1.2.34 private static PAEdgeSet construct_new_O(ParIntGraph pig, PANode nt) {
303 salcianu 1.1.2.7
304 salcianu 1.1.2.34 if(PointerAnalysis.RECORD_ACTIONS) {
305 salcianu 1.1.2.34 PAEdgeSet new_O = new LightPAEdgeSet();
306 salcianu 1.1.2.34
307 salcianu 1.1.2.34 Iterator it_loads = pig.ar.parallelLoads(nt);
308 salcianu 1.1.2.34 while(it_loads.hasNext()){
309 salcianu 1.1.2.34 PALoad load = (PALoad) it_loads.next();
310 salcianu 1.1.2.34 new_O.addEdge(load.n1, load.f, load.n2);
311 salcianu 1.1.2.34 }
312 salcianu 1.1.2.7
313 salcianu 1.1.2.34 return new_O;
314 salcianu 1.1.2.34 }
315 salcianu 1.1.2.34 else
316 salcianu 1.1.2.34 return (PAEdgeSet) pig.G.O.clone();
317 salcianu 1.1.2.1 }
318 salcianu 1.1.2.1
319 salcianu 1.1.2.27 /* Computes the interaction with a SINGLE instance of a thread launched
320 salcianu 1.1.2.27 by the nt node. This involves separately computing the interactions
321 salcianu 1.1.2.27 with all the possible run() methods (the body of the thread) and
322 salcianu 1.1.2.27 joining the results. */
323 salcianu 1.1.2.27 private static ParIntGraph interact_once(PointerAnalysis pa,
324 salcianu 1.1.2.27 ParIntGraph pig, PANode nt,
325 salcianu 1.1.2.27 MetaMethod[] ops) {
326 salcianu 1.1.2.1 int nb_ops = ops.length;
327 cananian 1.3.2.1 assert nb_ops > 0 : "No run method for the thread" + nt;
328 salcianu 1.1.2.1
329 salcianu 1.1.2.1 // compute the first term of the join operation:
330 salcianu 1.1.2.1 // the interaction with the first run() method
331 salcianu 1.1.2.27 ParIntGraph pig_after = interact_once_op(pa, pig, nt, ops[0]);
332 salcianu 1.1.2.1
333 salcianu 1.1.2.1 // join to it all the other terms (interactions with all the
334 salcianu 1.1.2.5 // other run() methods).
335 salcianu 1.1.2.5 for(int i = 1 ; i < nb_ops ; i++)
336 salcianu 1.1.2.27 pig_after.join(interact_once_op(pa, pig, nt, ops[i]));
337 salcianu 1.1.2.1
338 salcianu 1.1.2.1 return pig_after;
339 salcianu 1.1.2.1 }
340 salcianu 1.1.2.1
341 salcianu 1.1.2.1
342 salcianu 1.1.2.27 /* Computes the interaction between the Starter and a SINGLE thread having
343 salcianu 1.1.2.27 the node nt as a receiver and op as the run() body function. */
344 salcianu 1.1.2.27 private static ParIntGraph interact_once_op(PointerAnalysis pa,
345 salcianu 1.1.2.27 ParIntGraph pig_starter,
346 salcianu 1.1.2.27 PANode nt, MetaMethod op) {
347 salcianu 1.1.2.1 ParIntGraph pig[] = new ParIntGraph[2];
348 salcianu 1.1.2.1 pig[0] = pig_starter;
349 salcianu 1.1.2.17
350 salcianu 1.1.2.26 if(DEBUG)
351 salcianu 1.1.2.22 System.out.println("interact_once_op; op = " + op.getHMethod());
352 salcianu 1.1.2.22
353 salcianu 1.1.2.17 // some thread specialization if necessary
354 salcianu 1.1.2.17 if(PointerAnalysis.THREAD_SENSITIVE ||
355 salcianu 1.1.2.17 PointerAnalysis.WEAKLY_THREAD_SENSITIVE)
356 salcianu 1.1.2.17 pig[1] = pa.getSpecializedExtParIntGraph(op);
357 salcianu 1.1.2.17 else
358 salcianu 1.1.2.17 pig[1] = pa.getExtParIntGraph(op);
359 salcianu 1.1.2.5
360 rinard 1.1.2.32 if(DEBUG2){
361 salcianu 1.1.2.5 System.out.println("interact_once_op:");
362 salcianu 1.1.2.5 System.out.println(" nt node: " + nt);
363 salcianu 1.1.2.5 System.out.println(" run method: " + op);
364 salcianu 1.1.2.5 System.out.println("PIG STARTER: " + pig[0]);
365 salcianu 1.1.2.5 System.out.println("PIG STARTEE: " + pig[1]);
366 rinard 1.1.2.32 }
367 salcianu 1.1.2.1
368 salcianu 1.1.2.1 PANode[] params = pa.getParamNodes(op);
369 salcianu 1.1.2.38
370 salcianu 1.1.2.38 Relation mu[] = compute_mappings(pig, nt, params);
371 salcianu 1.1.2.1
372 salcianu 1.1.2.38 Set actives = active_threads_outside_startee(pa, pig[0]);
373 salcianu 1.1.2.38
374 salcianu 1.1.2.38 if(DEBUG2)
375 salcianu 1.1.2.38 System.out.println("interact_once_op: actives: " + actives);
376 salcianu 1.1.2.38
377 salcianu 1.1.2.38 ParIntGraph new_pig = build_new_pig(pig,mu,params[0],nt,actives);
378 salcianu 1.1.2.5
379 salcianu 1.1.2.6 if(DEBUG2){
380 salcianu 1.1.2.38 System.out.println("NEW GRAPH:");
381 salcianu 1.1.2.38 System.out.println(new_pig);
382 salcianu 1.1.2.38 }
383 salcianu 1.1.2.38
384 salcianu 1.1.2.38 return new_pig;
385 salcianu 1.1.2.38 }
386 salcianu 1.1.2.38
387 salcianu 1.1.2.38
388 salcianu 1.1.2.38 // activates the use of the new mapping constraints
389 salcianu 1.1.2.38 private static boolean NEW_MAPPING_CONSTRAINTS = true;
390 salcianu 1.1.2.38 public static boolean VERY_NEW_MAPPINGS = true;
391 salcianu 1.1.2.38 static {
392 salcianu 1.1.2.38 if(NEW_MAPPING_CONSTRAINTS) {
393 salcianu 1.1.2.38 System.out.println("InterThreadPA: NEW_MAPPING_CONSTRAINTS");
394 salcianu 1.1.2.38 if(VERY_NEW_MAPPINGS)
395 salcianu 1.1.2.38 System.out.println("InterThreadPA: VERY_NEW_MAPPING");
396 salcianu 1.1.2.38 }
397 salcianu 1.1.2.38 }
398 salcianu 1.1.2.38 // generates lots of debug messages about the construction of mu
399 salcianu 1.1.2.38 private static boolean DEBUG_MU = false;
400 salcianu 1.1.2.38
401 salcianu 1.1.2.38
402 salcianu 1.1.2.38 private static Relation[] compute_mappings
403 salcianu 1.1.2.38 (ParIntGraph pig[], PANode nt, PANode[] params) {
404 salcianu 1.1.2.38
405 salcianu 1.1.2.38 if(NEW_MAPPING_CONSTRAINTS)
406 salcianu 1.1.2.38 return compute_mu(pig, nt, params[0]);
407 salcianu 1.1.2.38
408 salcianu 1.1.2.38 Relation mu[] = compute_initial_mappings(pig, nt, params);
409 salcianu 1.1.2.38
410 salcianu 1.1.2.38 if(DEBUG_MU) {
411 salcianu 1.1.2.5 System.out.println("INITIAL MAPPINGS:");
412 salcianu 1.1.2.5 System.out.println("starter -> startee:" + mu[0]);
413 salcianu 1.1.2.5 System.out.println("startee -> starter:" + mu[1]);
414 salcianu 1.1.2.5 }
415 salcianu 1.1.2.1
416 salcianu 1.1.2.38 concretize_loads(pig, mu);
417 salcianu 1.1.2.38
418 salcianu 1.1.2.38 if(DEBUG_MU) {
419 salcianu 1.1.2.5 System.out.println("AFTER CONCRETIZE LOADS:");
420 salcianu 1.1.2.5 System.out.println("starter -> startee:" + mu[0]);
421 salcianu 1.1.2.5 System.out.println("startee -> starter:" + mu[1]);
422 salcianu 1.1.2.5 }
423 salcianu 1.1.2.5
424 salcianu 1.1.2.1 compute_final_mappings(pig,mu,nt);
425 salcianu 1.1.2.5
426 salcianu 1.1.2.38 if(DEBUG_MU) {
427 salcianu 1.1.2.5 System.out.println("FINAL MAPPINGS:");
428 salcianu 1.1.2.5 System.out.println("starter -> startee:" + mu[0]);
429 salcianu 1.1.2.5 System.out.println("startee -> starter:" + mu[1]);
430 salcianu 1.1.2.5 }
431 salcianu 1.1.2.5
432 salcianu 1.1.2.38 return mu;
433 salcianu 1.1.2.1 }
434 salcianu 1.1.2.1
435 salcianu 1.1.2.27
436 salcianu 1.1.2.27 /* Sets the initial mappings: class nodes, parameter->thread node.
437 salcianu 1.1.2.27 Parameters:
438 salcianu 1.1.2.27 pig[0] - the parallel interaction graph of the Starter;
439 salcianu 1.1.2.27 pig[1] - the parallel interaction graph of the Startee.
440 salcianu 1.1.2.27
441 salcianu 1.1.2.27 Returns:
442 salcianu 1.1.2.27 mu[0] - the mapping of the nodes from the Starter <br>;
443 salcianu 1.1.2.27 mu[1] - the mapping of the nodes from the Startee <br>. */
444 salcianu 1.1.2.1 private static Relation[] compute_initial_mappings(ParIntGraph[] pig,
445 salcianu 1.1.2.1 PANode nt,
446 salcianu 1.1.2.1 PANode[] params){
447 salcianu 1.1.2.1 // Paranoic debug! Trust no one!
448 cananian 1.3.2.1 assert params.length == 1 : "Thread function with too many args";
449 salcianu 1.1.2.1
450 salcianu 1.1.2.31 Relation mu0 = new LightRelation();
451 salcianu 1.1.2.1 map_static_nodes(pig[0],mu0);
452 salcianu 1.1.2.1
453 salcianu 1.1.2.31 Relation mu1 = new LightRelation();
454 salcianu 1.1.2.1 mu1.add(params[0],nt);
455 salcianu 1.1.2.1 map_static_nodes(pig[1],mu1);
456 salcianu 1.1.2.1
457 salcianu 1.1.2.1 return (new Relation[]{mu0,mu1});
458 salcianu 1.1.2.1 }
459 salcianu 1.1.2.1
460 salcianu 1.1.2.1
461 salcianu 1.1.2.1 /* Maps the static nodes that appear in pig to themselves. Only those
462 salcianu 1.1.2.1 static nodes that appear as sources of arcs need to be mapped; if
463 salcianu 1.1.2.1 necessary, the others wil be mapped by the rest of the algorithm.
464 salcianu 1.1.2.1 (the matching goes always "forward" on the edges, never "backward", so
465 salcianu 1.1.2.1 it's necessary to trigger it just in the sources of the edges. */
466 salcianu 1.1.2.30 private static void map_static_nodes(ParIntGraph pig, Relation mu) {
467 salcianu 1.1.2.30 process_STATICs(pig.G.O.allSourceNodes(), mu);
468 salcianu 1.1.2.30 process_STATICs(pig.G.I.allSourceNodes(), mu);
469 salcianu 1.1.2.30 }
470 salcianu 1.1.2.30 // aux method for map_static_nodes
471 salcianu 1.1.2.30 private static void process_STATICs(final Set set, final Relation mu) {
472 cananian 1.7 for(Object nodeO : set) {
473 cananian 1.7 PANode node = (PANode) nodeO;
474 salcianu 1.1.2.1 if(node.type == PANode.STATIC)
475 salcianu 1.1.2.1 mu.add(node,node);
476 salcianu 1.1.2.1 }
477 salcianu 1.1.2.1 }
478 salcianu 1.1.2.30
479 salcianu 1.1.2.1
480 salcianu 1.1.2.1
481 salcianu 1.1.2.27 /* Computes the mappings by matching outside edges from one graph
482 salcianu 1.1.2.27 against inside edges from the other one. */
483 salcianu 1.1.2.38 private static void concretize_loads(ParIntGraph[] pig, Relation[] mu) {
484 salcianu 1.1.2.5
485 salcianu 1.1.2.1 PAWorkList W[] = { new PAWorkList(), new PAWorkList() };
486 salcianu 1.1.2.5
487 salcianu 1.1.2.1 Relation new_info[] = { (Relation)(mu[0].clone()),
488 salcianu 1.1.2.1 (Relation)(mu[1].clone()) };
489 salcianu 1.1.2.1
490 salcianu 1.1.2.31 W[0].addAll(mu[0].keys());
491 salcianu 1.1.2.31 W[1].addAll(mu[1].keys());
492 salcianu 1.1.2.1
493 salcianu 1.1.2.1 while(true){
494 salcianu 1.1.2.1 int i,ib;
495 salcianu 1.1.2.1 if(!W[0].isEmpty()) { i=0; ib=1; }
496 salcianu 1.1.2.1 else
497 salcianu 1.1.2.1 if(!W[1].isEmpty()) { i=1; ib=0; }
498 salcianu 1.1.2.11 else{
499 salcianu 1.1.2.38 Matching.rule0(mu, W, new_info);
500 salcianu 1.1.2.11 if(W[0].isEmpty() && W[1].isEmpty()) break;
501 salcianu 1.1.2.11 else continue;
502 salcianu 1.1.2.11 }
503 salcianu 1.1.2.1
504 salcianu 1.1.2.1 PANode node = (PANode) W[i].remove();
505 salcianu 1.1.2.1
506 salcianu 1.1.2.5 // new mappings for node
507 salcianu 1.1.2.31 Set new_mappings = new HashSet(new_info[i].getValues(node));
508 salcianu 1.1.2.31 new_info[i].removeKey(node);
509 salcianu 1.1.2.5
510 salcianu 1.1.2.11 // Matching.rule0(node,new_mappings,pig,W,mu,new_info,i,ib);
511 rinard 1.1.2.32
512 salcianu 1.1.2.5 Matching.rule2(node,new_mappings,pig,W,mu,new_info,i,ib);
513 salcianu 1.1.2.11 Matching.rule22(node,new_mappings,pig,W,mu,new_info,i,ib);
514 salcianu 1.1.2.5 Matching.rule3(node,new_mappings,pig,W,mu,new_info,i,ib);
515 salcianu 1.1.2.11 Matching.rule32(node,new_mappings,pig,W,mu,new_info,i,ib);
516 salcianu 1.1.2.1 }
517 salcianu 1.1.2.1 }
518 salcianu 1.1.2.1
519 salcianu 1.1.2.1
520 salcianu 1.1.2.27 /* Computes the final mappings. Every node from the Starter and the Startee
521 salcianu 1.1.2.27 will be put in the new graph (node-mu->node) except for the parameter
522 salcianu 1.1.2.27 node of the Startee run() method; this one will be mapped to nt. */
523 salcianu 1.1.2.1 private static void compute_final_mappings(final ParIntGraph[] pig,
524 salcianu 1.1.2.1 final Relation[] mu,
525 salcianu 1.1.2.1 final PANode nt){
526 salcianu 1.1.2.1 PANodeVisitor visitor_starter = new PANodeVisitor(){
527 salcianu 1.1.2.1 public void visit(PANode node){
528 salcianu 1.1.2.24 mu[0].add(node, node);
529 salcianu 1.1.2.1 }
530 salcianu 1.1.2.1 };
531 salcianu 1.1.2.1
532 salcianu 1.1.2.24 pig[0].forAllNodes(visitor_starter);
533 salcianu 1.1.2.1
534 salcianu 1.1.2.1 PANodeVisitor visitor_startee = new PANodeVisitor(){
535 salcianu 1.1.2.1 public void visit(PANode node){
536 salcianu 1.1.2.1 int type = node.type();
537 rinard 1.1.2.32 if ((type == PANode.PARAM) ||
538 rinard 1.1.2.32 (node == ActionRepository.THIS_THREAD))
539 salcianu 1.1.2.24 mu[1].add(node, nt);
540 salcianu 1.1.2.1 else
541 salcianu 1.1.2.24 mu[1].add(node, node);
542 salcianu 1.1.2.1 }
543 salcianu 1.1.2.1 };
544 salcianu 1.1.2.1
545 salcianu 1.1.2.24 pig[1].forAllNodes(visitor_startee);
546 salcianu 1.1.2.1 }
547 salcianu 1.1.2.38
548 salcianu 1.1.2.38
549 salcianu 1.1.2.38
550 salcianu 1.1.2.38 /////////////////////////////////////////////////////////////////////
551 salcianu 1.1.2.38 ////////////////// New mapping constraints START ////////////////////
552 salcianu 1.1.2.38
553 salcianu 1.1.2.38 private static boolean USE_BAR = false;
554 salcianu 1.1.2.38 static {
555 salcianu 1.1.2.38 if(USE_BAR)
556 salcianu 1.1.2.38 System.out.println("USE_BAR");
557 salcianu 1.1.2.38 }
558 salcianu 1.1.2.38
559 salcianu 1.1.2.38 // Compute the mappings using the new constraints
560 salcianu 1.1.2.38 private static Relation[] compute_mu
561 salcianu 1.1.2.38 (ParIntGraph pig[], PANode nt, PANode param) {
562 salcianu 1.1.2.38
563 salcianu 1.1.2.38 ParIntGraph initial_pig1 = pig[1];
564 salcianu 1.1.2.38 if(USE_BAR) {
565 salcianu 1.1.2.38 pig[1] = pig[1].getBarVersion();
566 salcianu 1.1.2.38 }
567 salcianu 1.1.2.38
568 salcianu 1.1.2.38 //System.out.println("Beginning of compute_mu:");
569 salcianu 1.1.2.38 //System.out.println("initial_pig1.G.O = " + initial_pig1.G.O);
570 salcianu 1.1.2.38 //System.out.println("pig[1].G.O = " + pig[1].G.O);
571 salcianu 1.1.2.38
572 salcianu 1.1.2.38
573 salcianu 1.1.2.38 // initialize the mappings mu
574 salcianu 1.1.2.38 Relation mu[] = get_initial_mu(pig, nt, param);
575 salcianu 1.1.2.38 if(DEBUG_MU) {
576 salcianu 1.1.2.38 System.out.println("INITIAL MAPPINGS:");
577 salcianu 1.1.2.38 System.out.println("starter -> startee:" + mu[0]);
578 salcianu 1.1.2.38 System.out.println("startee -> starter:" + mu[1]);
579 salcianu 1.1.2.38 }
580 salcianu 1.1.2.38
581 salcianu 1.1.2.38 //System.out.println("BEFORE extend_mu pig[0] = " + pig[0]);
582 salcianu 1.1.2.38 //System.out.println("BEFORE extend_mu pig[1] = " + pig[1]);
583 salcianu 1.1.2.38
584 salcianu 1.1.2.38 // extend the mappings mu according to the inference rules
585 salcianu 1.1.2.38 extend_mu(mu, pig);
586 salcianu 1.1.2.38 if(DEBUG_MU) {
587 salcianu 1.1.2.38 System.out.println("MAPPINGS AFTER extend_mu:");
588 salcianu 1.1.2.38 System.out.println("starter -> startee:" + mu[0]);
589 salcianu 1.1.2.38 System.out.println("startee -> starter:" + mu[1]);
590 salcianu 1.1.2.38 }
591 salcianu 1.1.2.38
592 salcianu 1.1.2.38 if(VERY_NEW_MAPPINGS) {
593 salcianu 1.1.2.38 compute_final_mappings(pig, mu, nt);
594 salcianu 1.1.2.38 if(DEBUG_MU) {
595 salcianu 1.1.2.38 System.out.println("MAPPINGS AFTER extend_mu:");
596 salcianu 1.1.2.38 System.out.println("starter -> startee:" + mu[0]);
597 salcianu 1.1.2.38 System.out.println("startee -> starter:" + mu[1]);
598 salcianu 1.1.2.38 }
599 salcianu 1.1.2.38 }
600 salcianu 1.1.2.38
601 salcianu 1.1.2.38 if(USE_BAR)
602 salcianu 1.1.2.38 mu = get_adjusted_mu(mu);
603 salcianu 1.1.2.38
604 salcianu 1.1.2.38 if(DEBUG_MU) {
605 salcianu 1.1.2.38 System.out.println("FINAL MAPPINGS:");
606 salcianu 1.1.2.38 System.out.println("starter -> startee:" + mu[0]);
607 salcianu 1.1.2.38 System.out.println("startee -> starter:" + mu[1]);
608 salcianu 1.1.2.38 }
609 salcianu 1.1.2.38
610 salcianu 1.1.2.38 if(USE_BAR) {
611 salcianu 1.1.2.38 // restore the initial graph
612 salcianu 1.1.2.38 pig[1] = initial_pig1;
613 salcianu 1.1.2.38 }
614 salcianu 1.1.2.38
615 salcianu 1.1.2.38 return mu;
616 salcianu 1.1.2.38 }
617 salcianu 1.1.2.38
618 salcianu 1.1.2.38 // Get the pair of initial mappings: each node in entity i
619 salcianu 1.1.2.38 // (starter/startee) is mapped to itself in mu[i], except for the
620 salcianu 1.1.2.38 // only param node of the
621 salcianu 1.1.2.38 private static Relation[] get_initial_mu
622 salcianu 1.1.2.38 (ParIntGraph pig[], PANode nt, PANode param) {
623 salcianu 1.1.2.38
624 salcianu 1.1.2.38 Relation mu[] =
625 salcianu 1.1.2.38 new Relation[] { new RelationImpl(), new RelationImpl() };
626 salcianu 1.1.2.38
627 salcianu 1.1.2.38 // map the "this" param node of the startee to the thread node nt
628 salcianu 1.1.2.38 mu[1].add(param, nt);
629 salcianu 1.1.2.38 // map the dummy current thread from the startee to nt
630 salcianu 1.1.2.38 mu[1].add(ActionRepository.THIS_THREAD, nt);
631 salcianu 1.1.2.38
632 salcianu 1.1.2.38 if(VERY_NEW_MAPPINGS) {
633 salcianu 1.1.2.38 // map each static node to itself
634 salcianu 1.1.2.38 for(int i = 0; i < 2; i++) {
635 cananian 1.7 for(Object nodeO : pig[i].allNodes()) {
636 cananian 1.7 PANode node = (PANode) nodeO;
637 salcianu 1.1.2.38 if(node.type == PANode.STATIC)
638 salcianu 1.1.2.38 mu[i].add(node, node);
639 salcianu 1.1.2.38 }
640 salcianu 1.1.2.38 }
641 salcianu 1.1.2.38 return mu;
642 salcianu 1.1.2.38 }
643 salcianu 1.1.2.38
644 salcianu 1.1.2.38 // map every node to itself, except the "this" param node of the
645 salcianu 1.1.2.38 // startee that will disappear after the thread interaction
646 salcianu 1.1.2.38 // a. first map node to node, \forall node
647 salcianu 1.1.2.38 for(int i = 0; i < 2; i++) {
648 cananian 1.7 for(Object nodeO : pig[i].allNodes()) {
649 cananian 1.7 PANode node = (PANode) nodeO;
650 salcianu 1.1.2.38 mu[i].add(node, node);
651 salcianu 1.1.2.38 }
652 salcianu 1.1.2.38 }
653 salcianu 1.1.2.38 // b. now, delete the mapping params[0], params[0]
654 salcianu 1.1.2.38 mu[1].remove(param, param);
655 salcianu 1.1.2.38
656 salcianu 1.1.2.38 mu[1].remove(ActionRepository.THIS_THREAD,
657 salcianu 1.1.2.38 ActionRepository.THIS_THREAD);
658 salcianu 1.1.2.38
659 salcianu 1.1.2.38 return mu;
660 salcianu 1.1.2.38 }
661 salcianu 1.1.2.38
662 salcianu 1.1.2.38
663 salcianu 1.1.2.38 // extend the mappings using the inference rules coded into Matching
664 salcianu 1.1.2.38 private static void extend_mu(Relation mu[], ParIntGraph pig[]) {
665 salcianu 1.1.2.38 PAWorkList W[] = { new PAWorkList(), new PAWorkList() };
666 salcianu 1.1.2.38
667 salcianu 1.1.2.38 Relation new_info[] = { (Relation)(mu[0].clone()),
668 salcianu 1.1.2.38 (Relation)(mu[1].clone()) };
669 salcianu 1.1.2.38
670 salcianu 1.1.2.38 W[0].addAll(mu[0].keys());
671 salcianu 1.1.2.38 W[1].addAll(mu[1].keys());
672 salcianu 1.1.2.38
673 salcianu 1.1.2.38 while(true){
674 salcianu 1.1.2.38 int i,ib;
675 salcianu 1.1.2.38
676 salcianu 1.1.2.38 if(!W[0].isEmpty()) { i=0; ib=1; }
677 salcianu 1.1.2.38 else
678 salcianu 1.1.2.38 if(!W[1].isEmpty()) { i=1; ib=0; }
679 salcianu 1.1.2.38 else {
680 salcianu 1.1.2.38 Matching.rule0(mu, W, new_info);
681 salcianu 1.1.2.38
682 salcianu 1.1.2.38 for(int k = 0; k < 2; k++)
683 salcianu 1.1.2.38 Matching.aliasingSameScopeRule
684 salcianu 1.1.2.38 (mu[k], pig[k], W[k], new_info[k]);
685 salcianu 1.1.2.38
686 salcianu 1.1.2.38 if(W[0].isEmpty() && W[1].isEmpty()) break;
687 salcianu 1.1.2.38 else continue;
688 salcianu 1.1.2.38 }
689 salcianu 1.1.2.38
690 salcianu 1.1.2.38 PANode node = (PANode) W[i].remove();
691 salcianu 1.1.2.38
692 salcianu 1.1.2.38 // new mappings for node
693 salcianu 1.1.2.38 Set new_mappings = new HashSet(new_info[i].getValues(node));
694 salcianu 1.1.2.38 new_info[i].removeKey(node);
695 salcianu 1.1.2.38
696 salcianu 1.1.2.38 Matching.rule2(node,new_mappings,pig,W,mu,new_info,i,ib);
697 salcianu 1.1.2.38 Matching.rule22(node,new_mappings,pig,W,mu,new_info,i,ib);
698 salcianu 1.1.2.38 Matching.rule3(node,new_mappings,pig,W,mu,new_info,i,ib);
699 salcianu 1.1.2.38 Matching.rule32(node,new_mappings,pig,W,mu,new_info,i,ib);
700 salcianu 1.1.2.38 }
701 salcianu 1.1.2.38
702 salcianu 1.1.2.38 }
703 salcianu 1.1.2.38
704 salcianu 1.1.2.38
705 salcianu 1.1.2.38 // Adjust the relations mu[0], mu[1]: bar(n) -> n, \forall n.
706 salcianu 1.1.2.38 private static Relation[] get_adjusted_mu(Relation[] mu) {
707 salcianu 1.1.2.38 return
708 salcianu 1.1.2.38 new Relation[] { get_adjusted_mu(mu[0]),
709 salcianu 1.1.2.38 get_adjusted_mu(mu[1]) };
710 salcianu 1.1.2.38 }
711 salcianu 1.1.2.38
712 salcianu 1.1.2.38
713 salcianu 1.1.2.38 // Go over the mapping mu and replace every node with its
714 salcianu 1.1.2.38 // genuine version.
715 salcianu 1.1.2.38 private static Relation get_adjusted_mu(Relation mu) {
716 salcianu 1.1.2.38 final Relation unbar_mu = new RelationImpl();
717 salcianu 1.1.2.38 mu.forAllEntries(new RelationEntryVisitor() {
718 salcianu 1.1.2.38 public void visit(Object key, Object value) {
719 salcianu 1.1.2.38 PANode node1 = ((PANode) key).getGenuine();
720 salcianu 1.1.2.38 PANode node2 = ((PANode) value).getGenuine();
721 salcianu 1.1.2.38 unbar_mu.add(node1, node2);
722 salcianu 1.1.2.38 }
723 salcianu 1.1.2.38 });
724 salcianu 1.1.2.38 return unbar_mu;
725 salcianu 1.1.2.38 }
726 salcianu 1.1.2.38
727 salcianu 1.1.2.38 ////////////////// New mapping constraints END //////////////////////
728 salcianu 1.1.2.38 /////////////////////////////////////////////////////////////////////
729 salcianu 1.1.2.1
730 salcianu 1.1.2.1
731 salcianu 1.1.2.27 /* Builds the new graph using the graphs from the starter and the startee
732 salcianu 1.1.2.27 and the mu mappings. */
733 salcianu 1.1.2.6 private static ParIntGraph build_new_pig(ParIntGraph[] pig, Relation[] mu,
734 salcianu 1.1.2.12 PANode nparam, PANode nt,
735 salcianu 1.1.2.28 Set active_threads_in_starter) {
736 salcianu 1.1.2.1
737 salcianu 1.1.2.1 ParIntGraph new_pig = new ParIntGraph();
738 salcianu 1.1.2.1
739 salcianu 1.1.2.14 new_pig.insertAllButArEo(pig[0],mu[0], true);
740 salcianu 1.1.2.14 new_pig.insertAllButArEo(pig[1],mu[1], false,
741 salcianu 1.1.2.14 Collections.singleton(nparam));
742 salcianu 1.1.2.6
743 salcianu 1.1.2.7 // compute the escape function for the new graph
744 salcianu 1.1.2.8 new_pig.G.propagate();
745 salcianu 1.1.2.7
746 salcianu 1.1.2.34 if(PointerAnalysis.RECORD_ACTIONS) {
747 salcianu 1.1.2.34 // all the actions from starter run in parallel with the threads
748 salcianu 1.1.2.34 // that are started by the startee (it is not necessary to do a
749 salcianu 1.1.2.34 // transitive closure, the threads that are indirectly launched
750 salcianu 1.1.2.34 // by the startee will be considered when their direct started
751 salcianu 1.1.2.34 // is analyzed.
752 salcianu 1.1.2.34 bring_starter_actions(pig[0], new_pig, mu[0],
753 salcianu 1.1.2.34 pig[1].tau.activeThreadSet(), nt);
754 salcianu 1.1.2.34
755 salcianu 1.1.2.34 // all the actions from startee run in parallel with all the other
756 salcianu 1.1.2.34 // threads that could be (transitively) started by the starter.
757 salcianu 1.1.2.34 // Transitive closure is necessary since we may never revisit this
758 salcianu 1.1.2.34 // actions (we must put the parallel relation action || thread now)
759 salcianu 1.1.2.34 bring_startee_actions(pig[1], new_pig, mu[1],
760 salcianu 1.1.2.34 active_threads_in_starter, nt);
761 salcianu 1.1.2.34 }
762 salcianu 1.1.2.1
763 salcianu 1.1.2.1 return new_pig;
764 salcianu 1.1.2.1 }
765 salcianu 1.1.2.1
766 salcianu 1.1.2.27
767 salcianu 1.1.2.27 /* Returns the set of all the threads that can run in parallel with the
768 salcianu 1.1.2.27 startee thread: the threads that have already been processed +
769 salcianu 1.1.2.27 the threads that are still unanalyzed and the transitive closure of
770 salcianu 1.1.2.27 them (the threads that are directly/indirectly started by them)
771 salcianu 1.1.2.27 This method is expected to be called after adjusting the tau function
772 salcianu 1.1.2.27 for the startee node; that's why it doesn'y need to take it as an
773 salcianu 1.1.2.27 argument. */
774 salcianu 1.1.2.27 private static Set active_threads_outside_startee(PointerAnalysis pa,
775 salcianu 1.1.2.27 ParIntGraph pig_starter){
776 salcianu 1.1.2.12 Set active_threads = new HashSet(pig_starter.tau.activeThreadSet());
777 salcianu 1.1.2.27 thread_closure(pa, active_threads);
778 salcianu 1.1.2.12 active_threads.addAll(processed_threads);
779 salcianu 1.1.2.12 return active_threads;
780 salcianu 1.1.2.12 }
781 salcianu 1.1.2.12
782 salcianu 1.1.2.27
783 salcianu 1.1.2.27 /* Transitively extends the set "threads" according to the
784 salcianu 1.1.2.27 relation "thread nt1 launched thread nt2" */
785 salcianu 1.1.2.27 private static void thread_closure(PointerAnalysis pa, Set threads){
786 salcianu 1.1.2.12 PAWorkList W = new PAWorkList();
787 salcianu 1.1.2.12 W.addAll(threads);
788 salcianu 1.1.2.12
789 salcianu 1.1.2.12 while(!W.isEmpty()){
790 salcianu 1.1.2.12 PANode nt1 = (PANode) W.remove();
791 salcianu 1.1.2.21
792 salcianu 1.1.2.21 if(nt1.type != PANode.INSIDE) continue;
793 salcianu 1.1.2.21
794 salcianu 1.1.2.27 MetaMethod[] ops = get_run_mmethods(pa, nt1);
795 salcianu 1.1.2.27 if(!analyzable_run_mmethods(pa, ops)) continue;
796 salcianu 1.1.2.16 for(int i = 0; i < ops.length; i++){
797 salcianu 1.1.2.12 PAThreadMap tau_nt1 = pa.getExtParIntGraph(ops[i]).tau;
798 cananian 1.6 Enumeration _enum_ = tau_nt1.activeThreads();
799 cananian 1.6 while(_enum_.hasMoreElements()){
800 cananian 1.6 PANode nt2 = (PANode) _enum_.nextElement();
801 salcianu 1.1.2.12 if(threads.add(nt2)) W.add(nt2);
802 salcianu 1.1.2.12 }
803 salcianu 1.1.2.12 }
804 salcianu 1.1.2.12 }
805 salcianu 1.1.2.12 }
806 salcianu 1.1.2.1
807 salcianu 1.1.2.27
808 salcianu 1.1.2.27 /* Adds the actions from the starter to the new graph. */
809 salcianu 1.1.2.6 private static void bring_starter_actions(final ParIntGraph pig_starter,
810 salcianu 1.1.2.6 final ParIntGraph new_pig,
811 salcianu 1.1.2.6 final Relation mu_starter,
812 salcianu 1.1.2.6 final Set startee_active_threads,
813 salcianu 1.1.2.6 final PANode nt){
814 salcianu 1.1.2.6
815 salcianu 1.1.2.6 mu_starter.add(ActionRepository.THIS_THREAD,
816 salcianu 1.1.2.6 ActionRepository.THIS_THREAD);
817 salcianu 1.1.2.6
818 salcianu 1.1.2.6 ActionVisitor act_visitor_starter = new ActionVisitor(){
819 salcianu 1.1.2.6 public void visit_ld(PALoad load){
820 cananian 1.3.2.1 assert mu_starter.contains(load.n2,load.n2) : load.n2 + "->" + load.n2 +
821 cananian 1.3.2.1 " should be in mu_starter";
822 salcianu 1.1.2.24
823 salcianu 1.1.2.31 new_pig.ar.add_ld(mu_starter.getValues(load.n1),
824 salcianu 1.1.2.6 load.f,
825 salcianu 1.1.2.6 load.n2,
826 salcianu 1.1.2.31 mu_starter.getValues(load.nt),
827 salcianu 1.1.2.6 Collections.EMPTY_SET);
828 salcianu 1.1.2.6 }
829 salcianu 1.1.2.20 public void visit_sync(PASync sync){
830 salcianu 1.1.2.20 new_pig.ar.add_sync(sync.project(mu_starter),
831 salcianu 1.1.2.6 Collections.EMPTY_SET);
832 salcianu 1.1.2.6 }
833 salcianu 1.1.2.6 };
834 salcianu 1.1.2.6
835 salcianu 1.1.2.6 pig_starter.ar.forAllActions(act_visitor_starter);
836 salcianu 1.1.2.6
837 salcianu 1.1.2.28 ParActionVisitor par_act_visitor_starter = new ParActionVisitor() {
838 salcianu 1.1.2.6
839 salcianu 1.1.2.6 public void visit_par_ld(PALoad load, PANode nt2){
840 cananian 1.3.2.1 assert mu_starter.contains(load.n2,load.n2) : load.n2 + "->" + load.n2 +
841 cananian 1.3.2.1 " should be in mu_starter";
842 salcianu 1.1.2.6
843 salcianu 1.1.2.28 Set parallel_threads =
844 salcianu 1.1.2.31 new HashSet(mu_starter.getValues(nt2));
845 salcianu 1.1.2.28
846 salcianu 1.1.2.6 if(nt2 == nt)
847 salcianu 1.1.2.6 parallel_threads.addAll(startee_active_threads);
848 salcianu 1.1.2.6
849 salcianu 1.1.2.31 new_pig.ar.add_ld(mu_starter.getValues(load.n1),
850 salcianu 1.1.2.6 load.f,
851 salcianu 1.1.2.6 load.n2,
852 salcianu 1.1.2.31 mu_starter.getValues(load.nt),
853 salcianu 1.1.2.6 parallel_threads);
854 salcianu 1.1.2.6 }
855 salcianu 1.1.2.6
856 salcianu 1.1.2.20 public void visit_par_sync(PASync sync, PANode nt2){
857 salcianu 1.1.2.28 Set parallel_threads =
858 salcianu 1.1.2.31 new HashSet(mu_starter.getValues(nt2));
859 salcianu 1.1.2.6
860 salcianu 1.1.2.6 if(nt2 == nt)
861 salcianu 1.1.2.6 parallel_threads.addAll(startee_active_threads);
862 salcianu 1.1.2.6
863 salcianu 1.1.2.20 new_pig.ar.add_sync(sync.project(mu_starter),
864 salcianu 1.1.2.6 parallel_threads);
865 salcianu 1.1.2.6 }
866 salcianu 1.1.2.6 };
867 salcianu 1.1.2.6
868 salcianu 1.1.2.6 pig_starter.ar.forAllParActions(par_act_visitor_starter);
869 salcianu 1.1.2.6 }
870 salcianu 1.1.2.6
871 salcianu 1.1.2.6
872 salcianu 1.1.2.27 /* Adds the actions from the startee to the new graph. */
873 salcianu 1.1.2.6 private static void bring_startee_actions(final ParIntGraph pig_startee,
874 salcianu 1.1.2.6 final ParIntGraph new_pig,
875 salcianu 1.1.2.6 final Relation mu_startee,
876 salcianu 1.1.2.6 final Set starter_active_threads,
877 salcianu 1.1.2.6 final PANode nt){
878 salcianu 1.1.2.6
879 salcianu 1.1.2.24 mu_startee.add(ActionRepository.THIS_THREAD, nt);
880 salcianu 1.1.2.6
881 salcianu 1.1.2.6 ActionVisitor act_visitor_startee = new ActionVisitor(){
882 salcianu 1.1.2.6 public void visit_ld(PALoad load){
883 salcianu 1.1.2.6 if(!mu_startee.contains(load.n2,load.n2)) return;
884 salcianu 1.1.2.31 new_pig.ar.add_ld(mu_startee.getValues(load.n1),
885 salcianu 1.1.2.6 load.f,
886 salcianu 1.1.2.6 load.n2,
887 salcianu 1.1.2.31 mu_startee.getValues(load.nt),
888 salcianu 1.1.2.6 starter_active_threads);
889 salcianu 1.1.2.6 }
890 salcianu 1.1.2.20 public void visit_sync(PASync sync){
891 salcianu 1.1.2.20 new_pig.ar.add_sync(sync.project(mu_startee),
892 salcianu 1.1.2.6 starter_active_threads);
893 salcianu 1.1.2.6 }
894 salcianu 1.1.2.6 };
895 salcianu 1.1.2.6
896 salcianu 1.1.2.6 pig_startee.ar.forAllActions(act_visitor_startee);
897 salcianu 1.1.2.6
898 salcianu 1.1.2.6 ParActionVisitor par_act_visitor_startee = new ParActionVisitor(){
899 salcianu 1.1.2.6 public void visit_par_ld(PALoad load, PANode nt2){
900 salcianu 1.1.2.6 if(!mu_startee.contains(load.n2,load.n2)) return;
901 salcianu 1.1.2.31 new_pig.ar.add_ld(mu_startee.getValues(load.n1),
902 salcianu 1.1.2.6 load.f,
903 salcianu 1.1.2.6 load.n2,
904 salcianu 1.1.2.31 mu_startee.getValues(load.nt),
905 salcianu 1.1.2.31 mu_startee.getValues(nt2));
906 salcianu 1.1.2.6 }
907 salcianu 1.1.2.20 public void visit_par_sync(PASync sync, PANode nt2){
908 salcianu 1.1.2.20 new_pig.ar.add_sync(sync.project(mu_startee),
909 salcianu 1.1.2.31 mu_startee.getValues(nt2));
910 salcianu 1.1.2.6 }
911 salcianu 1.1.2.6 };
912 salcianu 1.1.2.6
913 salcianu 1.1.2.6 pig_startee.ar.forAllParActions(par_act_visitor_startee);
914 salcianu 1.1.2.6
915 salcianu 1.1.2.1 }
916 salcianu 1.1.2.1
917 cananian 1.2 }