1 package Analysis.Locality;
5 import java.util.Arrays;
6 import java.util.HashSet;
7 import java.util.Iterator;
8 import java.util.Hashtable;
11 import IR.TypeDescriptor;
12 import IR.MethodDescriptor;
13 import IR.FieldDescriptor;
15 public class DiscoverConflicts {
16 Set<FieldDescriptor> fields;
17 Set<TypeDescriptor> arrays;
18 LocalityAnalysis locality;
20 Hashtable<LocalityBinding, Set<FlatNode>> treadmap;
21 Hashtable<LocalityBinding, Set<TempFlatPair>> transreadmap;
22 Hashtable<LocalityBinding, Set<FlatNode>> srcmap;
23 Hashtable<LocalityBinding, Set<FlatNode>> leftsrcmap;
24 Hashtable<LocalityBinding, Set<FlatNode>> rightsrcmap;
25 TypeAnalysis typeanalysis;
26 HashSet<FlatNode>cannotdelay;
27 Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>> lbtofnmap;
30 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis) {
31 this.locality=locality;
32 this.fields=new HashSet<FieldDescriptor>();
33 this.arrays=new HashSet<TypeDescriptor>();
35 this.typeanalysis=typeanalysis;
36 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
37 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
38 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
39 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
40 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
41 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
44 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, HashSet<FlatNode> cannotdelay) {
45 this.locality=locality;
46 this.fields=new HashSet<FieldDescriptor>();
47 this.arrays=new HashSet<TypeDescriptor>();
49 this.typeanalysis=typeanalysis;
50 this.cannotdelay=cannotdelay;
51 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
52 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
53 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
54 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
55 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
56 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
59 public Set<FieldDescriptor> getFields() {
63 public Set<TypeDescriptor> getArrays() {
67 public void doAnalysis() {
68 //Compute fields and arrays for all transactions. Note that we
69 //only look at changes to old objects
71 Set<LocalityBinding> localityset=locality.getLocalityBindings();
72 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
73 computeModified(lb.next());
76 //Compute set of nodes that need transread
77 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
78 LocalityBinding l=lb.next();
84 //Change flatnode/temp pairs to just flatnodes that need transactional reads
86 public void setNeedReadTrans(LocalityBinding lb) {
87 HashSet<FlatNode> set=new HashSet<FlatNode>();
88 for(Iterator<TempFlatPair> it=transreadmap.get(lb).iterator();it.hasNext();) {
89 TempFlatPair tfp=it.next();
92 treadmap.put(lb, set);
95 //We have a set of things we write to, figure out what things this
97 public void expandTypes() {
98 Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
99 for(Iterator<TypeDescriptor> it=arrays.iterator();it.hasNext();) {
100 TypeDescriptor td=it.next();
101 expandedarrays.addAll(typeanalysis.expand(td));
103 arrays=expandedarrays;
106 Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
107 Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
108 for(int i=0;i<fn.numPrev();i++) {
109 FlatNode fprev=fn.getPrev(i);
110 Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
112 for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
113 TempDescriptor td=tmpit.next();
114 Set<TempFlatPair> fnset=tabset.get(td);
115 if (!table.containsKey(td))
116 table.put(td, new HashSet<TempFlatPair>());
117 table.get(td).addAll(fnset);
124 public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
125 return srcmap.get(lb);
128 public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
129 return srcmap.get(lb).contains(fn);
132 public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
133 return leftsrcmap.get(lb).contains(fn);
136 public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
137 return rightsrcmap.get(lb).contains(fn);
140 public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
141 return treadmap.get(lb).contains(fn);
144 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
145 return lbtofnmap.get(lb);
148 private void analyzeLocality(LocalityBinding lb) {
149 MethodDescriptor md=lb.getMethod();
150 FlatMethod fm=state.getMethodFlat(md);
151 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
152 lbtofnmap.put(lb,fnmap);
153 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap);
154 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
155 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
156 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
157 transreadmap.put(lb, tfset);
158 srcmap.put(lb,srctrans);
159 leftsrcmap.put(lb,leftsrctrans);
160 rightsrcmap.put(lb,rightsrctrans);
162 //compute writes that need translation on source
164 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
165 FlatNode fn=fnit.next();
166 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
167 if (atomictable.get(fn).intValue()>0) {
168 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
171 //We might need to translate arguments to pointer comparison
173 case FKind.FlatOpNode: {
174 FlatOpNode fon=(FlatOpNode)fn;
175 if (fon.getOp().getOp()==Operation.EQUAL||
176 fon.getOp().getOp()==Operation.NOTEQUAL) {
177 if (!fon.getLeft().getType().isPtr())
179 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
180 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
181 //handle left operand
182 if (lefttfpset!=null) {
183 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
184 TempFlatPair tfp=tfpit.next();
185 if (tfset.contains(tfp)||outofscope(tfp)) {
186 leftsrctrans.add(fon);
191 //handle right operand
192 if (righttfpset!=null) {
193 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
194 TempFlatPair tfp=tfpit.next();
195 if (tfset.contains(tfp)||outofscope(tfp)) {
196 rightsrctrans.add(fon);
205 case FKind.FlatSetFieldNode: {
206 //need to translate these if the value we read from may be a
207 //shadow... check this by seeing if any of the values we
208 //may read are in the transread set or came from our caller
209 //or a method we called
211 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
212 if (!fsfn.getField().getType().isPtr())
214 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
216 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
217 TempFlatPair tfp=tfpit.next();
218 if (tfset.contains(tfp)||outofscope(tfp)) {
226 case FKind.FlatSetElementNode: {
227 //need to translate these if the value we read from may be a
228 //shadow... check this by seeing if any of the values we
229 //may read are in the transread set or came from our caller
230 //or a method we called
232 FlatSetElementNode fsen=(FlatSetElementNode)fn;
233 if (!fsen.getSrc().getType().isPtr())
235 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
237 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
238 TempFlatPair tfp=tfpit.next();
239 if (tfset.contains(tfp)||outofscope(tfp)) {
253 public boolean outofscope(TempFlatPair tfp) {
255 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
259 /** Need to figure out which nodes need a transread to make local
260 copies. Transread conceptually tracks conflicts. This depends on
261 what fields/elements are accessed We iterate over all flatnodes that
262 access fields...If these accesses could conflict, we mark the source
263 tempflat pair as needing a transread */
265 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap) {
266 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
268 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
269 FlatNode fn=fnit.next();
270 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
272 //Check whether this node matters for delayed computation
273 if (cannotdelay!=null&&!cannotdelay.contains(fn))
276 if (atomictable.get(fn).intValue()>0) {
277 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
279 case FKind.FlatElementNode: {
280 FlatElementNode fen=(FlatElementNode)fn;
281 if (arrays.contains(fen.getSrc().getType())) {
282 //this could cause conflict...figure out conflict set
283 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
285 tfset.addAll(tfpset);
289 case FKind.FlatFieldNode: {
290 FlatFieldNode ffn=(FlatFieldNode)fn;
291 if (fields.contains(ffn.getField())) {
292 //this could cause conflict...figure out conflict set
293 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
295 tfset.addAll(tfpset);
299 case FKind.FlatSetFieldNode: {
300 //definitely need to translate these
301 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
302 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
304 tfset.addAll(tfpset);
307 case FKind.FlatSetElementNode: {
308 //definitely need to translate these
309 FlatSetElementNode fsen=(FlatSetElementNode)fn;
310 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
312 tfset.addAll(tfpset);
315 case FKind.FlatCall: //assume pessimistically that calls do bad things
316 case FKind.FlatReturnNode: {
317 TempDescriptor []readarray=fn.readsTemps();
318 for(int i=0;i<readarray.length;i++) {
319 TempDescriptor rtmp=readarray[i];
320 Set<TempFlatPair> tfpset=tmap.get(rtmp);
322 tfset.addAll(tfpset);
335 //This method generates as output for each node
336 //A map from from temps to a set of temp/flat pairs that the
337 //original temp points to
338 //A temp/flat pair gives the flatnode that the value was created at
339 //and the original temp
341 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
342 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
343 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
344 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
345 MethodDescriptor md=lb.getMethod();
346 FlatMethod fm=state.getMethodFlat(md);
347 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
348 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
352 while(!tovisit.isEmpty()) {
353 FlatNode fn=tovisit.iterator().next();
355 for(int i=0;i<fn.numNext();i++) {
356 FlatNode fnext=fn.getNext(i);
357 if (!discovered.contains(fnext)) {
358 discovered.add(fnext);
362 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
363 if (atomictable.get(fn).intValue()!=0) {
364 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
365 //atomic node, start with new set
366 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
368 ttofn=doMerge(fn, tmptofnset);
370 case FKind.FlatGlobalConvNode: {
371 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
372 if (lb==fgcn.getLocality()&&
374 TempDescriptor[] writes=fn.writesTemps();
375 for(int i=0;i<writes.length;i++) {
376 TempDescriptor wtmp=writes[i];
377 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
378 set.add(new TempFlatPair(wtmp, fn));
379 ttofn.put(wtmp, set);
384 case FKind.FlatFieldNode:
385 case FKind.FlatElementNode: {
386 TempDescriptor[] writes=fn.writesTemps();
387 for(int i=0;i<writes.length;i++) {
388 TempDescriptor wtmp=writes[i];
389 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
390 set.add(new TempFlatPair(wtmp, fn));
391 ttofn.put(wtmp, set);
396 case FKind.FlatMethod: {
397 TempDescriptor[] writes=fn.writesTemps();
398 for(int i=0;i<writes.length;i++) {
399 TempDescriptor wtmp=writes[i];
400 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
401 set.add(new TempFlatPair(wtmp, fn));
402 ttofn.put(wtmp, set);
406 case FKind.FlatOpNode: {
407 FlatOpNode fon=(FlatOpNode)fn;
408 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()&&
409 ttofn.containsKey(fon.getLeft())) {
410 ttofn.put(fon.getDest(), new HashSet<TempFlatPair>(ttofn.get(fon.getLeft())));
415 //Do kill computation
416 TempDescriptor[] writes=fn.writesTemps();
417 for(int i=0;i<writes.length;i++) {
418 TempDescriptor wtmp=writes[i];
419 ttofn.remove(writes[i]);
424 if (!tmptofnset.containsKey(fn)||
425 !tmptofnset.get(fn).equals(ttofn)) {
426 //enqueue nodes to process
427 tmptofnset.put(fn, ttofn);
428 for(int i=0;i<fn.numNext();i++) {
429 FlatNode fnext=fn.getNext(i);
439 /* See what fields and arrays transactions might modify. We only
440 * look at changes to old objects. */
442 public void computeModified(LocalityBinding lb) {
443 MethodDescriptor md=lb.getMethod();
444 FlatMethod fm=state.getMethodFlat(md);
445 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
446 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
447 FlatNode fn=fnit.next();
448 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
449 if (atomictable.get(fn).intValue()>0) {
451 case FKind.FlatSetFieldNode:
452 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
453 fields.add(fsfn.getField());
455 case FKind.FlatSetElementNode:
456 FlatSetElementNode fsen=(FlatSetElementNode) fn;
457 arrays.add(fsen.getDst().getType());
466 //Returns a table that maps a flatnode to a set of temporaries
467 //This set of temporaries is old (meaning they may point to object
468 //allocated before the beginning of the current transaction
470 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
471 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
472 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
473 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
474 MethodDescriptor md=lb.getMethod();
475 FlatMethod fm=state.getMethodFlat(md);
476 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
477 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
481 while(!tovisit.isEmpty()) {
482 FlatNode fn=tovisit.iterator().next();
484 for(int i=0;i<fn.numNext();i++) {
485 FlatNode fnext=fn.getNext(i);
486 if (!discovered.contains(fnext)) {
487 discovered.add(fnext);
491 HashSet<TempDescriptor> oldtemps=null;
492 if (atomictable.get(fn).intValue()!=0) {
493 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
494 //Everything live is old
495 Set<TempDescriptor> lives=livetemps.get(fn);
496 oldtemps=new HashSet<TempDescriptor>();
498 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
499 TempDescriptor tmp=it.next();
500 if (tmp.getType().isPtr()) {
505 oldtemps=new HashSet<TempDescriptor>();
506 //Compute union of old temporaries
507 for(int i=0;i<fn.numPrev();i++) {
508 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
510 oldtemps.addAll(pset);
515 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
517 case FKind.FlatOpNode: {
518 FlatOpNode fon=(FlatOpNode)fn;
519 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
520 if (oldtemps.contains(fon.getLeft()))
521 oldtemps.add(fon.getDest());
523 oldtemps.remove(fon.getDest());
528 TempDescriptor[] writes=fn.writesTemps();
529 for(int i=0;i<writes.length;i++) {
530 TempDescriptor wtemp=writes[i];
531 if (wtemp.getType().isPtr())
539 if (oldtemps!=null) {
540 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
541 fntooldtmp.put(fn, oldtemps);
543 for(int i=0;i<fn.numNext();i++) {
544 FlatNode fnext=fn.getNext(i);
557 TempFlatPair(TempDescriptor t, FlatNode f) {
562 public int hashCode() {
563 return f.hashCode()^t.hashCode();
565 public boolean equals(Object o) {
566 TempFlatPair tf=(TempFlatPair)o;
567 return t.equals(tf.t)&&f.equals(tf.f);