1 salcianu 1.1.2.1 // ActionRepository.java, created Mon Feb 7 15:03:29 2000 by salcianu
2 cananian 1.1.2.28 // 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
7 salcianu 1.1.2.1 import java.util.HashSet;
8 salcianu 1.1.2.1 import java.util.Set;
9 salcianu 1.1.2.1 import java.util.Iterator;
10 salcianu 1.1.2.1 import java.util.Enumeration;
11 salcianu 1.1.2.1 import java.util.Hashtable;
12 salcianu 1.1.2.1 import java.util.Map;
13 salcianu 1.1.2.17 import java.util.HashMap;
14 salcianu 1.1.2.10 import java.util.Collections;
15 salcianu 1.1.2.1
16 salcianu 1.1.2.17 import harpoon.IR.Quads.CALL;
17 salcianu 1.1.2.17 import harpoon.Analysis.MetaMethods.MetaMethod;
18 salcianu 1.1.2.17 import harpoon.ClassFile.HCodeElement;
19 cananian 1.5 import net.cscott.jutil.FilterIterator;
20 salcianu 1.1.2.17
21 salcianu 1.1.2.21 import harpoon.Util.PredicateWrapper;
22 salcianu 1.1.2.21 import harpoon.Util.DataStructs.Relation;
23 salcianu 1.1.2.21 import harpoon.Util.DataStructs.LightRelation;
24 salcianu 1.1.2.21 import harpoon.Util.DataStructs.RelationEntryVisitor;
25 salcianu 1.1.2.21
26 salcianu 1.1.2.27 import harpoon.Util.Util;
27 salcianu 1.1.2.27
28 salcianu 1.1.2.1 /**
29 salcianu 1.1.2.3 * <code>ActionRepository</code> merges together the <code>alpha</code> and
30 salcianu 1.1.2.3 <code>pi</code> sets from the original paper of Martin Rinard & John Whaley.
31 salcianu 1.1.2.3 More specifically, an <code>ActionRepository</code> maintains information
32 salcianu 1.1.2.11 about the actions executed by the analyzed part of the program (that's the
33 salcianu 1.1.2.11 meaning of alpha in the original paper) and about the
34 salcianu 1.1.2.3 ordering relation between these actions and the threads that are launched
35 salcianu 1.1.2.11 by the analyzed part (the pi structure).<br>
36 salcianu 1.1.2.5 Currently, only two kinds of actions are supported:
37 salcianu 1.1.2.3 <ul>
38 salcianu 1.1.2.3 <li><code>ld</code> - loading of a node by reading an outside edges;
39 salcianu 1.1.2.3 <li><code>sync</code> - synchronization (lock acquire/release) on a node.
40 salcianu 1.1.2.3 </ul>
41 salcianu 1.1.2.3 The implementation has been specially optimized for these two types of actions
42 salcianu 1.1.2.3 and for the queries that are done for synchronization removal.<br>
43 salcianu 1.1.2.3 Of course, there is no problem in modifying it to support new types of
44 salcianu 1.1.2.3 actions.
45 salcianu 1.1.2.1 *
46 cananian 1.1.2.28 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
47 cananian 1.6 * @version $Id: ActionRepository.java,v 1.6 2004/02/08 05:09:36 cananian Exp $
48 salcianu 1.1.2.1 */
49 salcianu 1.1.2.25 public class ActionRepository implements java.io.Serializable {
50 salcianu 1.1.2.1
51 salcianu 1.1.2.11 /** Fake thread node that stands for the main thread of the analyzed
52 salcianu 1.1.2.11 scope. This is used as the author thread for the actions done
53 salcianu 1.1.2.11 by the main thread of the analyzed procedure/scope, not by one of
54 salcianu 1.1.2.3 the threads it is starting. */
55 salcianu 1.1.2.14 public static final PANode THIS_THREAD =
56 salcianu 1.1.2.14 NodeRepository.getNewNode(PANode.INSIDE);
57 salcianu 1.1.2.1
58 salcianu 1.1.2.1 /** Creates a <code>ActionRepository</code>. */
59 salcianu 1.1.2.1 public ActionRepository() {
60 salcianu 1.1.2.1 alpha_ld = new HashSet();
61 salcianu 1.1.2.21 pi_ld = new LightRelation();
62 salcianu 1.1.2.21 alpha_sync = new LightRelation();
63 salcianu 1.1.2.1 pi_sync = new Hashtable();
64 salcianu 1.1.2.1 }
65 salcianu 1.1.2.1
66 salcianu 1.1.2.1
67 salcianu 1.1.2.1 // Set<PALoad>
68 salcianu 1.1.2.1 HashSet alpha_ld;
69 salcianu 1.1.2.17 // Relation<PANode,PALoad>; nt -> loads performed in // with nt
70 salcianu 1.1.2.1 Relation pi_ld;
71 salcianu 1.1.2.1
72 salcianu 1.1.2.17 // Relation<PANode,PASync>; n -> syncs performed on n
73 salcianu 1.1.2.11 Relation alpha_sync;
74 salcianu 1.1.2.20 // Hashtable<PANode,Relation<PANode,PASync>>
75 salcianu 1.1.2.17 // nt2 -> n -> syncs on n in // with nt2
76 salcianu 1.1.2.11 Hashtable pi_sync;
77 salcianu 1.1.2.20
78 salcianu 1.1.2.20
79 salcianu 1.1.2.20 /** Displays the differences between <code>this</code> action repository
80 salcianu 1.1.2.20 and <code>ar2</code>. For debug purposes. */
81 salcianu 1.1.2.20 private void print_difference(final ActionRepository ar2) {
82 salcianu 1.1.2.20 System.out.println("--- LD actions:");
83 cananian 1.6 for(Object loadO : alpha_ld){
84 cananian 1.6 PALoad load = (PALoad) loadO;
85 salcianu 1.1.2.20 if(!ar2.alpha_ld.contains(load))
86 salcianu 1.1.2.20 System.out.println(load);
87 salcianu 1.1.2.20 }
88 salcianu 1.1.2.20
89 salcianu 1.1.2.20 System.out.println("--- LD || nt pairs:");
90 salcianu 1.1.2.20 pi_ld.forAllEntries(new RelationEntryVisitor(){
91 salcianu 1.1.2.20 public void visit(Object key, Object value){
92 salcianu 1.1.2.20 PANode nt = (PANode) key;
93 salcianu 1.1.2.20 PALoad load = (PALoad) value;
94 salcianu 1.1.2.20 if(!ar2.pi_ld.contains(nt, load))
95 salcianu 1.1.2.20 System.out.println(load + " || " + nt);
96 salcianu 1.1.2.20 }
97 salcianu 1.1.2.20 });
98 salcianu 1.1.2.20
99 salcianu 1.1.2.20 System.out.println("--- SYNC actions:");
100 salcianu 1.1.2.20 alpha_sync.forAllEntries(new RelationEntryVisitor(){
101 salcianu 1.1.2.20 public void visit(Object key, Object value){
102 salcianu 1.1.2.20 PANode n = (PANode) key;
103 salcianu 1.1.2.20 PASync sync = (PASync) value;
104 salcianu 1.1.2.20 if(!ar2.alpha_sync.contains(key, value))
105 salcianu 1.1.2.20 System.out.println(sync);
106 salcianu 1.1.2.20 }
107 salcianu 1.1.2.20 });
108 salcianu 1.1.2.20
109 salcianu 1.1.2.20 System.out.println("--- SYNC || nt pairs:");
110 salcianu 1.1.2.20 for(Iterator it = pi_sync.entrySet().iterator(); it.hasNext(); ) {
111 salcianu 1.1.2.20 final Map.Entry entry = (Map.Entry) it.next();
112 salcianu 1.1.2.20 final PANode nt2 = (PANode) entry.getKey();
113 salcianu 1.1.2.20 final Relation rel = (Relation) entry.getValue();
114 salcianu 1.1.2.20 final Relation rel2 = (Relation) ar2.pi_sync.get(nt2);
115 salcianu 1.1.2.20 rel.forAllEntries(new RelationEntryVisitor() {
116 salcianu 1.1.2.20 public void visit(Object key, Object value) {
117 salcianu 1.1.2.20 PANode n = (PANode) key;
118 salcianu 1.1.2.20 PASync sync = (PASync) value;
119 salcianu 1.1.2.20 if(!rel2.contains(n ,sync))
120 salcianu 1.1.2.20 System.out.println(sync + " || " + nt2);
121 salcianu 1.1.2.20 }
122 salcianu 1.1.2.20 });
123 salcianu 1.1.2.20 }
124 salcianu 1.1.2.20 }
125 salcianu 1.1.2.20
126 salcianu 1.1.2.20
127 salcianu 1.1.2.20 /** Shows the evolution from <code>ar2</code> to <code>this</code>:
128 salcianu 1.1.2.20 newly added stuff and removed stuff. Debug purposes. */
129 salcianu 1.1.2.20 public void show_evolution(final ActionRepository ar2){
130 salcianu 1.1.2.20 System.out.println("====== NEWLY ADDED STUFF:");
131 salcianu 1.1.2.20 print_difference(ar2);
132 salcianu 1.1.2.20 if(ar2 != null){
133 salcianu 1.1.2.20 System.out.println("===== REMOVED STUFF:");
134 salcianu 1.1.2.20 ar2.print_difference(this);
135 salcianu 1.1.2.20 }
136 salcianu 1.1.2.20 }
137 salcianu 1.1.2.20
138 salcianu 1.1.2.11
139 salcianu 1.1.2.11 // A. The most primitive operations on the action repository, they are
140 salcianu 1.1.2.11 // designed to be used internally; the usage pattern of the user has
141 salcianu 1.1.2.11 // been optimized into some specialized, high-level methods.
142 salcianu 1.1.2.11
143 salcianu 1.1.2.11 // A.1. Operations on alpha, the repository of actions
144 salcianu 1.1.2.11
145 salcianu 1.1.2.11 // Adds a "ld" action.
146 salcianu 1.1.2.11 private final void alpha_add_ld(PALoad load){
147 salcianu 1.1.2.1 alpha_ld.add(load);
148 salcianu 1.1.2.11 }
149 salcianu 1.1.2.11
150 salcianu 1.1.2.11 // Adds a "sync" action.
151 salcianu 1.1.2.17 private final void alpha_add_sync(PASync sync){
152 salcianu 1.1.2.17 alpha_sync.add(sync.n, sync);
153 salcianu 1.1.2.11 }
154 salcianu 1.1.2.11
155 salcianu 1.1.2.11 // A.2. Operations on pi, the relation of parallelism
156 salcianu 1.1.2.11 // between actions and threads
157 salcianu 1.1.2.11
158 salcianu 1.1.2.11 // Adds a parallel relation between a "ld" action and a thread.
159 salcianu 1.1.2.11 private final void pi_add_ld(PALoad load, PANode nt){
160 salcianu 1.1.2.11 pi_ld.add(nt,load);
161 salcianu 1.1.2.11 }
162 salcianu 1.1.2.11
163 salcianu 1.1.2.11 // Adds a parallel relation between a "sync" action and a thread.
164 salcianu 1.1.2.17 private final void pi_add_sync(PASync sync, PANode nt2){
165 salcianu 1.1.2.11 Relation rel = (Relation) pi_sync.get(nt2);
166 salcianu 1.1.2.11 if(rel == null){
167 salcianu 1.1.2.21 rel = new LightRelation();
168 salcianu 1.1.2.11 pi_sync.put(nt2,rel);
169 salcianu 1.1.2.11 }
170 salcianu 1.1.2.17 rel.add(sync.n, sync);
171 salcianu 1.1.2.11 }
172 salcianu 1.1.2.11
173 salcianu 1.1.2.11 // B. User level function: usually when a user introduces an action,
174 salcianu 1.1.2.11 // he also gives a set of threads that are running in parallel: in a
175 salcianu 1.1.2.11 // single method, we update alpha and pi.
176 salcianu 1.1.2.11
177 salcianu 1.1.2.11 /** Adds a "ld" action in parallel with all the
178 salcianu 1.1.2.11 <code>active_threads</code>. */
179 salcianu 1.1.2.11 private final void add_ld(PALoad load, Set active_threads){
180 salcianu 1.1.2.11 alpha_add_ld(load);
181 salcianu 1.1.2.1
182 salcianu 1.1.2.1 if(active_threads == null) return;
183 salcianu 1.1.2.1
184 salcianu 1.1.2.1 Iterator it = active_threads.iterator();
185 salcianu 1.1.2.1 while(it.hasNext())
186 salcianu 1.1.2.11 pi_add_ld(load, (PANode)it.next());
187 salcianu 1.1.2.1 }
188 salcianu 1.1.2.1
189 salcianu 1.1.2.10 /** Adds a <code>ld</code> action.
190 salcianu 1.1.2.10 The thread <code>nt</code> read the outside edge from <code>n1</code>
191 salcianu 1.1.2.10 to <code>n2</code> through field <code>f</code>, in parallel with
192 salcianu 1.1.2.10 all the threads from <code>active_threads</code>. */
193 salcianu 1.1.2.11 public final void add_ld(PANode n1, String f, PANode n2, PANode nt,
194 salcianu 1.1.2.10 Set active_threads){
195 salcianu 1.1.2.10 add_ld(new PALoad(n1,f,n2,nt),active_threads);
196 salcianu 1.1.2.10 }
197 salcianu 1.1.2.10
198 salcianu 1.1.2.11 /** Convenient function used in the intra-procedural analysis,
199 salcianu 1.1.2.11 in the rule for a load operation.
200 salcianu 1.1.2.3 It iterates over <code>set_n1</code>, repeatedly calling
201 salcianu 1.1.2.3 <code>add_ld(n1,f,n2,nt,active_threads)</code> for each
202 salcianu 1.1.2.3 <code>n1</code> in <code>set_n1</code>. */
203 salcianu 1.1.2.11 public final void add_ld(Set set_n1, String f, PANode n2, PANode nt,
204 salcianu 1.1.2.3 Set active_threads){
205 salcianu 1.1.2.11 if(set_n1.isEmpty()) return;
206 cananian 1.6 for (Object n1O : set_n1){
207 cananian 1.6 PANode n1 = (PANode) n1O;
208 salcianu 1.1.2.1 add_ld(n1,f,n2,nt,active_threads);
209 salcianu 1.1.2.1 }
210 salcianu 1.1.2.1 }
211 salcianu 1.1.2.1
212 salcianu 1.1.2.11 /** Convenient function used by the inter-procedural and
213 salcianu 1.1.2.11 inter-thread analysis (when a thread node can be mapped to
214 salcianu 1.1.2.11 a set of nodes).
215 salcianu 1.1.2.3 It iterates over <code>set_nt</code>, repeatedly calling
216 salcianu 1.1.2.3 <code>add_ld(set_n1,f,n2,nt,active_threads)</code> for each
217 salcianu 1.1.2.3 <code>nt</code> in <code>set_nt</code>. */
218 salcianu 1.1.2.11 public final void add_ld(Set set_n1, String f, PANode n2, Set set_nt,
219 salcianu 1.1.2.3 Set active_threads){
220 salcianu 1.1.2.11 if(set_nt.isEmpty()) return;
221 cananian 1.6 for (Object ntO : set_nt){
222 cananian 1.6 PANode nt = (PANode) ntO;
223 vivien 1.1.2.24 add_ld(set_n1,f,n2,nt,active_threads);
224 vivien 1.1.2.24 }
225 vivien 1.1.2.24 }
226 vivien 1.1.2.24
227 vivien 1.1.2.24
228 vivien 1.1.2.24 /** Convenient function used by the inter-procedural and
229 vivien 1.1.2.24 inter-thread analysis (when a load node can be mapped to
230 vivien 1.1.2.24 a set of nodes).
231 vivien 1.1.2.24 It iterates over <code>set_n2</code>, repeatedly calling
232 vivien 1.1.2.24 <code>add_ld(set_n1,f,n2,set_nt,active_threads)</code> for each
233 vivien 1.1.2.24 <code>n2</code> in <code>set_n2</code>. */
234 vivien 1.1.2.24 public final void add_ld(Set set_n1, String f, Set set_n2, Set set_nt,
235 vivien 1.1.2.24 Set active_threads){
236 vivien 1.1.2.24 if(set_n2.isEmpty()) return;
237 cananian 1.6 for (Object n2O : set_n2){
238 cananian 1.6 PANode n2 = (PANode) n2O;
239 vivien 1.1.2.24 add_ld(set_n1,f,n2,set_nt,active_threads);
240 vivien 1.1.2.24 }
241 vivien 1.1.2.24 }
242 vivien 1.1.2.24
243 vivien 1.1.2.24 public final void add_ld(Set set_n1, String f, Set set_n2, PANode nt,
244 vivien 1.1.2.24 Set active_threads){
245 vivien 1.1.2.24 if(set_n2.isEmpty()) return;
246 cananian 1.6 for (Object n2O : set_n2){
247 cananian 1.6 PANode n2 = (PANode) n2O;
248 salcianu 1.1.2.1 add_ld(set_n1,f,n2,nt,active_threads);
249 salcianu 1.1.2.1 }
250 salcianu 1.1.2.1 }
251 salcianu 1.1.2.1
252 salcianu 1.1.2.1
253 salcianu 1.1.2.3 /** Adds a <code>sync</code> action.
254 salcianu 1.1.2.3 The thread <code>nt</code> synchronized on <code>n</code> in
255 salcianu 1.1.2.3 parallel with all the threads from <code>active_threads</code>. */
256 salcianu 1.1.2.17 public final void add_sync(PASync sync, Set active_threads){
257 salcianu 1.1.2.17 alpha_add_sync(sync);
258 salcianu 1.1.2.1
259 salcianu 1.1.2.4 if((active_threads == null) || active_threads.isEmpty()) return;
260 salcianu 1.1.2.4
261 salcianu 1.1.2.4 if(PointerAnalysis.DEBUG2){
262 salcianu 1.1.2.17 System.out.print("WONDERFUL: < sync , " + sync.n + " , " +
263 salcianu 1.1.2.17 sync.nt + " > || [");
264 salcianu 1.1.2.4
265 salcianu 1.1.2.4 Iterator it2 = active_threads.iterator();
266 salcianu 1.1.2.4 while(it2.hasNext())
267 salcianu 1.1.2.4 System.out.print(it2.next() + " ");
268 salcianu 1.1.2.4
269 salcianu 1.1.2.4 System.out.println("]");
270 salcianu 1.1.2.4 }
271 salcianu 1.1.2.1
272 cananian 1.6 for (Object nt2O : active_threads){
273 cananian 1.6 PANode nt2 = (PANode) nt2O;
274 salcianu 1.1.2.17 pi_add_sync(sync,nt2);
275 salcianu 1.1.2.1 }
276 salcianu 1.1.2.1 }
277 salcianu 1.1.2.1
278 salcianu 1.1.2.17 /** Convenient fiunction for recording a set of <code>sync</code>
279 salcianu 1.1.2.17 actions in parallel with all the threads from the set
280 salcianu 1.1.2.17 <code>active_threads</code>. */
281 salcianu 1.1.2.17 public final void add_sync(Set syncs, Set active_threads){
282 salcianu 1.1.2.17 for(Iterator it = syncs.iterator(); it.hasNext(); )
283 salcianu 1.1.2.17 add_sync((PASync) it.next(), active_threads);
284 salcianu 1.1.2.1 }
285 salcianu 1.1.2.11 // END of the "add" functions
286 salcianu 1.1.2.11
287 salcianu 1.1.2.3 /** Checks the equality of two <code>ActionRepository</code>s. */
288 salcianu 1.1.2.11 public final boolean equals(Object o){
289 salcianu 1.1.2.1 ActionRepository ar2 = (ActionRepository)o;
290 salcianu 1.1.2.4 if (this == ar2) return true;
291 salcianu 1.1.2.1 return
292 salcianu 1.1.2.1 alpha_ld.equals(ar2.alpha_ld) &&
293 salcianu 1.1.2.1 alpha_sync.equals(ar2.alpha_sync) &&
294 salcianu 1.1.2.1 pi_ld.equals(ar2.pi_ld) &&
295 salcianu 1.1.2.1 pi_sync.equals(ar2.pi_sync);
296 salcianu 1.1.2.1 }
297 salcianu 1.1.2.1
298 salcianu 1.1.2.4 /** Adds the information about actions and action-thread ordering from
299 salcianu 1.1.2.4 <code>ar2</code> to <code>this</code> action repository.
300 salcianu 1.1.2.1 This method is called in the control-flow join points. */
301 salcianu 1.1.2.11 public final void join(ActionRepository ar2){
302 salcianu 1.1.2.1 // these first three are really easy
303 salcianu 1.1.2.27
304 cananian 1.3.2.1 assert alpha_ld != null : "alpha_ld == null";
305 cananian 1.3.2.1 assert ar2 != null : "ar2 == null";
306 salcianu 1.1.2.27
307 salcianu 1.1.2.1 alpha_ld.addAll(ar2.alpha_ld);
308 salcianu 1.1.2.1 pi_ld.union(ar2.pi_ld);
309 salcianu 1.1.2.1 alpha_sync.union(ar2.alpha_sync);
310 salcianu 1.1.2.1 // this one is a bit more difficult; we have to do it by hand
311 cananian 1.6 for (Object entryO : ar2.pi_sync.entrySet()){
312 cananian 1.6 Map.Entry entry = (Map.Entry) entryO;
313 salcianu 1.1.2.4 PANode nt2 = (PANode) entry.getKey();
314 salcianu 1.1.2.4 Relation rel2 = (Relation) entry.getValue();
315 salcianu 1.1.2.1 Relation rel1 = (Relation) pi_sync.get(nt2);
316 salcianu 1.1.2.1 if(rel1 == null)
317 salcianu 1.1.2.21 pi_sync.put(nt2, (Relation) rel2.clone());
318 salcianu 1.1.2.1 else
319 salcianu 1.1.2.1 rel1.union(rel2);
320 salcianu 1.1.2.1 }
321 salcianu 1.1.2.1 }
322 salcianu 1.1.2.1
323 salcianu 1.1.2.3 /** Visits all the actions from this repository.
324 salcianu 1.1.2.3 It calls <code>visitor.visit_ld</code> on the <code>ld</code> actions
325 salcianu 1.1.2.3 and <code>visitor.visit_sync</code> on the <code>sync</code>. */
326 salcianu 1.1.2.11 public final void forAllActions(ActionVisitor visitor){
327 salcianu 1.1.2.3 // visit all the "ld" actions
328 salcianu 1.1.2.17 for(Iterator it_ld = alpha_ld.iterator(); it_ld.hasNext(); ){
329 salcianu 1.1.2.17 visitor.visit_ld((PALoad) it_ld.next());
330 salcianu 1.1.2.1 }
331 salcianu 1.1.2.3 // visit all the "sync" actions
332 cananian 1.6 for(Object nO : alpha_sync.keys()){
333 cananian 1.6 PANode n = (PANode) nO;
334 salcianu 1.1.2.21 Iterator it_sync = alpha_sync.getValues(n).iterator();
335 salcianu 1.1.2.21 while(it_sync.hasNext())
336 salcianu 1.1.2.17 visitor.visit_sync((PASync) it_sync.next());
337 salcianu 1.1.2.1 }
338 salcianu 1.1.2.3 }
339 salcianu 1.1.2.3
340 salcianu 1.1.2.1
341 salcianu 1.1.2.3 /** Visits all the "parallel action" items of information from this
342 salcianu 1.1.2.3 repository (i.e. all the <code> action || thread </code> elements.
343 salcianu 1.1.2.3 It calls <code>visitor.visit_par_ld</code> or
344 salcianu 1.1.2.3 <code>visitor.visit_par_sync</code> according to the type of the
345 salcianu 1.1.2.3 <code>action</code>. */
346 salcianu 1.1.2.11 public final void forAllParActions(ParActionVisitor visitor){
347 salcianu 1.1.2.17 // visit all the "ld" || nt entries
348 cananian 1.6 for(Object nt2O : pi_ld.keys()) {
349 cananian 1.6 PANode nt2 = (PANode) nt2O;
350 cananian 1.6 for (Object loadO : pi_ld.getValues(nt2)){
351 cananian 1.6 PALoad load = (PALoad) loadO;
352 salcianu 1.1.2.3 visitor.visit_par_ld(load,nt2);
353 salcianu 1.1.2.2 }
354 salcianu 1.1.2.2 }
355 salcianu 1.1.2.17
356 salcianu 1.1.2.17 // visit all the "sync" || nt entries
357 cananian 1.6 for(Object nt2O : pi_sync.keySet()){
358 cananian 1.6 PANode nt2 = (PANode) nt2O;
359 salcianu 1.1.2.2 Relation rel = (Relation) pi_sync.get(nt2);
360 cananian 1.6 for(Object nO : rel.keys()){
361 cananian 1.6 PANode n = (PANode) nO;
362 salcianu 1.1.2.21 Iterator it_sync = rel.getValues(n).iterator();
363 salcianu 1.1.2.21 while(it_sync.hasNext())
364 salcianu 1.1.2.21 visitor.visit_par_sync((PASync) it_sync.next(), nt2);
365 salcianu 1.1.2.2 }
366 salcianu 1.1.2.2 }
367 salcianu 1.1.2.6 }
368 salcianu 1.1.2.6
369 salcianu 1.1.2.6
370 salcianu 1.1.2.6 /** Returns an iterator over the set of loads that are performed in
371 salcianu 1.1.2.7 parallel with an <code>nt</code> thread. <code>O(1)</code> time. */
372 salcianu 1.1.2.11 public final Iterator parallelLoads(PANode nt){
373 salcianu 1.1.2.21 return pi_ld.getValues(nt).iterator();
374 salcianu 1.1.2.1 }
375 salcianu 1.1.2.1
376 salcianu 1.1.2.9
377 salcianu 1.1.2.8 /** Removes all the information related to edges containing nodes from
378 salcianu 1.1.2.8 <code>nodes</code>. */
379 salcianu 1.1.2.11 public final void removeNodes(final Set nodes){
380 salcianu 1.1.2.17 // CLEAN alpha_ld
381 salcianu 1.1.2.17 for(Iterator it_paload = alpha_ld.iterator(); it_paload.hasNext(); ){
382 salcianu 1.1.2.9 PALoad load = (PALoad) it_paload.next();
383 salcianu 1.1.2.12 if(load.isBad(nodes)) it_paload.remove();
384 salcianu 1.1.2.9 }
385 salcianu 1.1.2.9
386 salcianu 1.1.2.17 // CLEAN pi_ld
387 salcianu 1.1.2.9 PredicateWrapper node_predicate = new PredicateWrapper(){
388 salcianu 1.1.2.9 public boolean check(Object obj){
389 salcianu 1.1.2.9 return nodes.contains((PANode) obj);
390 salcianu 1.1.2.9 }
391 salcianu 1.1.2.9 };
392 salcianu 1.1.2.17 PredicateWrapper load_predicate = new PredicateWrapper(){
393 salcianu 1.1.2.9 public boolean check(Object obj){
394 salcianu 1.1.2.9 return ((PALoad) obj).isBad(nodes);
395 salcianu 1.1.2.9 }
396 salcianu 1.1.2.17 };
397 salcianu 1.1.2.17 pi_ld.removeKeys(node_predicate);
398 salcianu 1.1.2.17 pi_ld.removeValues(load_predicate);
399 salcianu 1.1.2.9
400 salcianu 1.1.2.17 // CLEAN alpha_sync
401 salcianu 1.1.2.17 PredicateWrapper sync_predicate = new PredicateWrapper(){
402 salcianu 1.1.2.17 public boolean check(Object obj){
403 salcianu 1.1.2.17 PASync sync = (PASync) obj;
404 salcianu 1.1.2.17 return
405 salcianu 1.1.2.17 nodes.contains(sync.n) ||
406 salcianu 1.1.2.17 nodes.contains(sync.nt);
407 salcianu 1.1.2.17 }
408 salcianu 1.1.2.17 };
409 salcianu 1.1.2.17 alpha_sync.removeKeys(node_predicate);
410 salcianu 1.1.2.17 alpha_sync.removeValues(sync_predicate);
411 salcianu 1.1.2.9
412 salcianu 1.1.2.17 // CLEAN pi_sync
413 salcianu 1.1.2.17 // 1. remove the entries in the map for non-remaining nodes nt2
414 salcianu 1.1.2.17 for(Iterator it_nodes = nodes.iterator(); it_nodes.hasNext(); )
415 salcianu 1.1.2.9 pi_sync.remove((PANode) it_nodes.next());
416 salcianu 1.1.2.17 // 2. check the relation attached to each remaining nt2 and
417 salcianu 1.1.2.17 // eliminate the bad syncs
418 salcianu 1.1.2.17 for(Iterator it_nt2 = pi_sync.keySet().iterator(); it_nt2.hasNext();){
419 salcianu 1.1.2.17 PANode nt2 = (PANode) it_nt2.next();
420 salcianu 1.1.2.17 Relation rel = (Relation) pi_sync.get(nt2);
421 salcianu 1.1.2.17 rel.removeKeys(node_predicate);
422 salcianu 1.1.2.17 rel.removeValues(sync_predicate);
423 salcianu 1.1.2.17 // if the relation is empty, delete the entry for nt2.
424 salcianu 1.1.2.17 if(rel.isEmpty()) it_nt2.remove();
425 salcianu 1.1.2.9 }
426 salcianu 1.1.2.9
427 salcianu 1.1.2.8 }
428 salcianu 1.1.2.8
429 salcianu 1.1.2.8 /** Removes all the information related to <code>ld</code> actions
430 salcianu 1.1.2.9 using the edges from <code>edges</code>.
431 salcianu 1.1.2.9 <code>edges</code> is supposed to be a set of <code>PAEdge</code>s. */
432 salcianu 1.1.2.11 public final void removeEdges(final Set edges){
433 salcianu 1.1.2.9
434 salcianu 1.1.2.12 // hack - we need a temporary edge just for testing the apartenence of
435 salcianu 1.1.2.12 // a load edge to the set edges; instead of stressing the GC with
436 salcianu 1.1.2.12 // repeated allocations, we allocate it once and for all
437 salcianu 1.1.2.12 final PAEdge edge = new PAEdge(null,"",null);
438 salcianu 1.1.2.12
439 salcianu 1.1.2.9 // clean alpha_ld
440 salcianu 1.1.2.9 Iterator it_paload = alpha_ld.iterator();
441 salcianu 1.1.2.9 while(it_paload.hasNext()){
442 salcianu 1.1.2.9 PALoad load = (PALoad) it_paload.next();
443 salcianu 1.1.2.12 edge.n1 = load.n1;
444 salcianu 1.1.2.12 edge.f = load.f;
445 salcianu 1.1.2.12 edge.n2 = load.n2;
446 salcianu 1.1.2.12 if(edges.contains(edge))
447 salcianu 1.1.2.12 it_paload.remove();
448 salcianu 1.1.2.9 }
449 salcianu 1.1.2.9
450 salcianu 1.1.2.9 // clean pi_ld
451 salcianu 1.1.2.9 pi_ld.removeValues(new PredicateWrapper(){
452 salcianu 1.1.2.9 public boolean check(Object obj){
453 salcianu 1.1.2.9 PALoad load = (PALoad) obj;
454 salcianu 1.1.2.12 edge.n1 = load.n1;
455 salcianu 1.1.2.12 edge.f = load.f;
456 salcianu 1.1.2.12 edge.n2 = load.n2;
457 salcianu 1.1.2.12 return edges.contains(edge);
458 salcianu 1.1.2.9 }
459 salcianu 1.1.2.9 });
460 salcianu 1.1.2.8 }
461 salcianu 1.1.2.3
462 salcianu 1.1.2.3 /** Checks if all the <code>sync</code> operation on <code>n</code>
463 salcianu 1.1.2.3 are independent (temporarily speaking) or not.
464 salcianu 1.1.2.3 If it returns <code>false</code>, two threads could synchonize
465 salcianu 1.1.2.3 on it at the same time (i.e. they can simultaneously access it);
466 salcianu 1.1.2.3 in this case, the synchonizations are really necessary and should
467 salcianu 1.1.2.3 NOT be removed. */
468 salcianu 1.1.2.26 public final boolean independent(PANode n) {
469 salcianu 1.1.2.23 System.out.println("n = " + n);
470 salcianu 1.1.2.3 // Goes through all the threads nt2 that are synchronizing on n
471 salcianu 1.1.2.21 Iterator it_sync = alpha_sync.getValues(n).iterator();
472 salcianu 1.1.2.21 while(it_sync.hasNext()) {
473 salcianu 1.1.2.17 PANode nt2 = ((PASync) it_sync.next()).nt;
474 salcianu 1.1.2.17 // if(nt2 == THIS_THREAD) continue;
475 salcianu 1.1.2.3 // Find the set of all the threads nt1 that synchronize
476 salcianu 1.1.2.23 // on n in || with nt2.
477 salcianu 1.1.2.23 // the relation nt -> Syncs done by nt on n in parallel with nt2
478 salcianu 1.1.2.23 Relation rel = (Relation) pi_sync.get(nt2);
479 salcianu 1.1.2.23 Set concurrent_syncs =
480 salcianu 1.1.2.23 rel == null ? Collections.EMPTY_SET : rel.getValues(n);
481 salcianu 1.1.2.23 // If there are such threads, we can have concurrent syncs.
482 salcianu 1.1.2.23 if(!concurrent_syncs.isEmpty())
483 salcianu 1.1.2.3 return false;
484 salcianu 1.1.2.3 }
485 salcianu 1.1.2.3 return true;
486 salcianu 1.1.2.3 }
487 salcianu 1.1.2.3
488 jwhaley 1.1.2.22 // Returns the sync ops performed by the thread nt on the node n.
489 jwhaley 1.1.2.22 public final Iterator syncsOn(final PANode n, final PANode nt){
490 jwhaley 1.1.2.22 FilterIterator.Filter f =
491 jwhaley 1.1.2.22 new FilterIterator.Filter() {
492 jwhaley 1.1.2.22 public boolean isElement(Object o) {
493 jwhaley 1.1.2.22 return ((PASync)o).nt == nt;
494 jwhaley 1.1.2.22 }
495 jwhaley 1.1.2.22 };
496 jwhaley 1.1.2.22 return new FilterIterator(alpha_sync.getValues(n).iterator(), f);
497 jwhaley 1.1.2.22 }
498 jwhaley 1.1.2.22
499 salcianu 1.1.2.18 /** Checks whether any <code>sync</code> action is done on the node
500 salcianu 1.1.2.18 <code>node</code>. */
501 salcianu 1.1.2.18 public boolean isSyncOn(PANode node){
502 salcianu 1.1.2.21 return !alpha_sync.getValues(node).isEmpty();
503 salcianu 1.1.2.18 }
504 salcianu 1.1.2.3
505 salcianu 1.1.2.10 // Private constructor for clone and keepTheEssential
506 salcianu 1.1.2.1 private ActionRepository(HashSet alpha_ld, Relation pi_ld,
507 salcianu 1.1.2.1 Relation alpha_sync, Hashtable pi_sync){
508 salcianu 1.1.2.1 this.alpha_ld = alpha_ld;
509 salcianu 1.1.2.1 this.pi_ld = pi_ld;
510 salcianu 1.1.2.1 this.alpha_sync = alpha_sync;
511 salcianu 1.1.2.1 this.pi_sync = pi_sync;
512 salcianu 1.1.2.1 }
513 salcianu 1.1.2.10
514 salcianu 1.1.2.10 /** Produces an <code>ActionRepository</code> containing only the \
515 salcianu 1.1.2.10 nodes that could be reached from the outside.
516 salcianu 1.1.2.10 (i.e. via parameters,
517 salcianu 1.1.2.10 class nodes, normally or exceptionally returned nodes or the
518 salcianu 1.1.2.10 started thread nodes) */
519 salcianu 1.1.2.16 final ActionRepository keepTheEssential(final Set remaining_nodes){
520 salcianu 1.1.2.11 final ActionRepository ar2 = new ActionRepository();
521 salcianu 1.1.2.16
522 salcianu 1.1.2.16 // commonsense rule
523 salcianu 1.1.2.16 remaining_nodes.add(THIS_THREAD);
524 salcianu 1.1.2.10
525 salcianu 1.1.2.11 // select only the actions referring only to remaining nodes
526 salcianu 1.1.2.10 forAllActions(new ActionVisitor(){
527 salcianu 1.1.2.10 public void visit_ld(PALoad load){
528 salcianu 1.1.2.10 if(load.isGood(remaining_nodes))
529 salcianu 1.1.2.11 ar2.alpha_add_ld(load);
530 salcianu 1.1.2.10 }
531 salcianu 1.1.2.17 public void visit_sync(PASync sync){
532 salcianu 1.1.2.17 if(remaining_nodes.contains(sync.n) &&
533 salcianu 1.1.2.17 remaining_nodes.contains(sync.nt))
534 salcianu 1.1.2.17 ar2.alpha_add_sync(sync);
535 salcianu 1.1.2.10 }
536 salcianu 1.1.2.10 });
537 salcianu 1.1.2.11
538 salcianu 1.1.2.11 // select only the parallel action info referring only to
539 salcianu 1.1.2.11 // remaining nodes
540 salcianu 1.1.2.10 forAllParActions(new ParActionVisitor(){
541 salcianu 1.1.2.10 public void visit_par_ld(PALoad load, PANode nt2){
542 salcianu 1.1.2.10 if(load.isGood(remaining_nodes) &&
543 salcianu 1.1.2.10 remaining_nodes.contains(nt2))
544 salcianu 1.1.2.17 ar2.pi_add_ld(load, nt2);
545 salcianu 1.1.2.10 }
546 salcianu 1.1.2.17 public void visit_par_sync(PASync sync, PANode nt2){
547 salcianu 1.1.2.17 if(remaining_nodes.contains(sync.n) &&
548 salcianu 1.1.2.17 remaining_nodes.contains(sync.nt) &&
549 salcianu 1.1.2.10 remaining_nodes.contains(nt2))
550 salcianu 1.1.2.17 ar2.pi_add_sync(sync, nt2);
551 salcianu 1.1.2.10 }
552 salcianu 1.1.2.10 });
553 salcianu 1.1.2.10
554 salcianu 1.1.2.11 return ar2;
555 salcianu 1.1.2.10 }
556 salcianu 1.1.2.10
557 salcianu 1.1.2.17 /* Specializes <code>this</code> <code>ActionRepository</code> for the
558 salcianu 1.1.2.17 call site <code>call</code>, according
559 salcianu 1.1.2.17 to <code>map</code>, a mapping from <code>PANode<code> to
560 salcianu 1.1.2.17 <code>PANode</code>. Each node which is not explicitly mapped is
561 salcianu 1.1.2.17 considered to be mapped to itself. */
562 salcianu 1.1.2.17 public final ActionRepository csSpecialize(final Map map,
563 salcianu 1.1.2.17 final CALL call){
564 salcianu 1.1.2.17 final ActionRepository ar2 = new ActionRepository();
565 salcianu 1.1.2.17
566 salcianu 1.1.2.17 // some cache to avoid generating specializations for the same
567 salcianu 1.1.2.17 // sync action twice
568 salcianu 1.1.2.17 final Map sync2sync = new HashMap();
569 salcianu 1.1.2.1
570 salcianu 1.1.2.17 forAllActions(new ActionVisitor(){
571 salcianu 1.1.2.14 public void visit_ld(PALoad load){
572 salcianu 1.1.2.17 ar2.alpha_add_ld(load.specialize(map));
573 salcianu 1.1.2.14 }
574 salcianu 1.1.2.17 public void visit_sync(PASync sync){
575 salcianu 1.1.2.17 PASync sync2 = sync.csSpecialize(map, call);
576 salcianu 1.1.2.17 ar2.alpha_add_sync(sync2);
577 salcianu 1.1.2.17 sync2sync.put(sync, sync2);
578 salcianu 1.1.2.17 }
579 salcianu 1.1.2.17 });
580 salcianu 1.1.2.14
581 salcianu 1.1.2.17 forAllParActions(new ParActionVisitor(){
582 salcianu 1.1.2.14 public void visit_par_ld(PALoad load, PANode nt2){
583 salcianu 1.1.2.17 ar2.pi_add_ld(load.specialize(map),
584 salcianu 1.1.2.17 PANode.translate(nt2, map));
585 salcianu 1.1.2.14 }
586 salcianu 1.1.2.17 public void visit_par_sync(PASync sync, PANode nt2){
587 salcianu 1.1.2.17 ar2.pi_add_sync((PASync) sync2sync.get(sync),
588 salcianu 1.1.2.17 PANode.translate(nt2, map));
589 salcianu 1.1.2.14 }
590 salcianu 1.1.2.17 });
591 salcianu 1.1.2.14
592 salcianu 1.1.2.17 return ar2;
593 salcianu 1.1.2.15 }
594 salcianu 1.1.2.15
595 salcianu 1.1.2.17 /* Specializes <code>this</code> <code>ActionRepository</code> for the
596 salcianu 1.1.2.17 thread whose run method is <code>run</code>, according
597 salcianu 1.1.2.15 to <code>map</code>, a mapping from <code>PANode<code> to
598 salcianu 1.1.2.15 <code>PANode</code>. Each node which is not explicitly mapped is
599 salcianu 1.1.2.15 considered to be mapped to itself. */
600 salcianu 1.1.2.17 public final ActionRepository tSpecialize(final Map map,
601 salcianu 1.1.2.17 final MetaMethod run){
602 salcianu 1.1.2.15 final ActionRepository ar2 = new ActionRepository();
603 salcianu 1.1.2.17
604 salcianu 1.1.2.17 // some cache to avoid generating specializations for the same
605 salcianu 1.1.2.17 // sync action twice
606 salcianu 1.1.2.17 final Map sync2sync = new HashMap();
607 salcianu 1.1.2.15
608 salcianu 1.1.2.15 forAllActions(new ActionVisitor(){
609 salcianu 1.1.2.15 public void visit_ld(PALoad load){
610 salcianu 1.1.2.15 ar2.alpha_add_ld(load.specialize(map));
611 salcianu 1.1.2.15 }
612 salcianu 1.1.2.17 public void visit_sync(PASync sync){
613 salcianu 1.1.2.17 PASync sync2 = sync.tSpecialize(map, run);
614 salcianu 1.1.2.17 ar2.alpha_add_sync(sync2);
615 salcianu 1.1.2.17 sync2sync.put(sync, sync2);
616 salcianu 1.1.2.15 }
617 salcianu 1.1.2.15 });
618 salcianu 1.1.2.15
619 salcianu 1.1.2.15 forAllParActions(new ParActionVisitor(){
620 salcianu 1.1.2.15 public void visit_par_ld(PALoad load, PANode nt2){
621 salcianu 1.1.2.15 ar2.pi_add_ld(load.specialize(map),
622 salcianu 1.1.2.15 PANode.translate(nt2, map));
623 salcianu 1.1.2.15 }
624 salcianu 1.1.2.17 public void visit_par_sync(PASync sync, PANode nt2){
625 salcianu 1.1.2.17 ar2.pi_add_sync((PASync) sync2sync.get(sync),
626 salcianu 1.1.2.15 PANode.translate(nt2, map));
627 salcianu 1.1.2.15 }
628 salcianu 1.1.2.15 });
629 salcianu 1.1.2.15
630 salcianu 1.1.2.15 return ar2;
631 salcianu 1.1.2.14 }
632 salcianu 1.1.2.1
633 salcianu 1.1.2.17
634 salcianu 1.1.2.17 /** Produces a copy of <code>this</code> object.
635 salcianu 1.1.2.1 The new object is totally independent from the old one: you can
636 salcianu 1.1.2.1 add/remove actions to/from it without affecting the original. */
637 salcianu 1.1.2.11 public final Object clone(){
638 salcianu 1.1.2.4 HashSet new_alpha_ld = (HashSet) alpha_ld.clone();
639 salcianu 1.1.2.4 Relation new_pi_ld = (Relation) pi_ld.clone();
640 salcianu 1.1.2.1 Relation new_alpha_sync = (Relation) alpha_sync.clone();
641 salcianu 1.1.2.1
642 salcianu 1.1.2.1 Hashtable new_pi_sync = new Hashtable();
643 cananian 1.6 for (Object entryO : pi_sync.entrySet()){
644 cananian 1.6 Map.Entry entry = (Map.Entry) entryO;
645 salcianu 1.1.2.4 PANode nt2 = (PANode) entry.getKey();
646 salcianu 1.1.2.1 Relation rel2 = (Relation) entry.getValue();
647 salcianu 1.1.2.1 new_pi_sync.put(nt2,(Relation) rel2.clone());
648 salcianu 1.1.2.1 }
649 salcianu 1.1.2.1
650 salcianu 1.1.2.1 return new ActionRepository(new_alpha_ld, new_pi_ld,
651 salcianu 1.1.2.1 new_alpha_sync, new_pi_sync);
652 salcianu 1.1.2.1 }
653 salcianu 1.1.2.1
654 salcianu 1.1.2.1
655 salcianu 1.1.2.4 /** Pretty-printer for debug purposes.
656 salcianu 1.1.2.14 <code>ar1.equals(ar2) <==>
657 salcianu 1.1.2.14 ar1.toString().equals(ar2.toString()).</code> */
658 salcianu 1.1.2.11 public final String toString(){
659 salcianu 1.1.2.4 StringBuffer buffer = new StringBuffer();
660 salcianu 1.1.2.4 final Set strings = new HashSet();
661 salcianu 1.1.2.1
662 salcianu 1.1.2.3 ActionVisitor act_visitor = new ActionVisitor(){
663 salcianu 1.1.2.3 public void visit_ld(PALoad load){
664 salcianu 1.1.2.4 strings.add(" " + load + "\n");
665 salcianu 1.1.2.3 }
666 salcianu 1.1.2.17 public void visit_sync(PASync sync){
667 salcianu 1.1.2.17 strings.add(" " + sync + "\n");
668 salcianu 1.1.2.3 }
669 salcianu 1.1.2.3 };
670 salcianu 1.1.2.1
671 salcianu 1.1.2.3 forAllActions(act_visitor);
672 salcianu 1.1.2.1
673 salcianu 1.1.2.4 Object[] strs = Debug.sortedSet(strings);
674 salcianu 1.1.2.17 buffer.append(" Alpha:\n");
675 salcianu 1.1.2.4 for(int i = 0 ; i < strs.length ; i++)
676 salcianu 1.1.2.4 buffer.append(strs[i]);
677 salcianu 1.1.2.4
678 salcianu 1.1.2.4 strings.clear();
679 salcianu 1.1.2.4
680 salcianu 1.1.2.3 ParActionVisitor par_act_visitor = new ParActionVisitor(){
681 salcianu 1.1.2.3 public void visit_par_ld(PALoad load, PANode nt2){
682 salcianu 1.1.2.4 strings.add(" " + load + " || " + nt2 + "\n");
683 salcianu 1.1.2.3 }
684 salcianu 1.1.2.17 public void visit_par_sync(PASync sync, PANode nt2){
685 salcianu 1.1.2.17 strings.add(" " + sync + " || " + nt2 + "\n");
686 salcianu 1.1.2.1 }
687 salcianu 1.1.2.3 };
688 salcianu 1.1.2.3 forAllParActions(par_act_visitor);
689 salcianu 1.1.2.4
690 salcianu 1.1.2.4 strs = Debug.sortedSet(strings);
691 salcianu 1.1.2.17 buffer.append(" Pi:\n");
692 salcianu 1.1.2.4 for(int i = 0 ; i < strs.length ; i++)
693 salcianu 1.1.2.4 buffer.append(strs[i]);
694 salcianu 1.1.2.3
695 salcianu 1.1.2.1 return buffer.toString();
696 salcianu 1.1.2.1 }
697 salcianu 1.1.2.1 }
698 salcianu 1.1.2.14
699 salcianu 1.1.2.14
700 salcianu 1.1.2.14
701 salcianu 1.1.2.1
702 cananian 1.2