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 Hashtable<LocalityBinding, HashSet<FlatNode>>cannotdelaymap;
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, Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap) {
45 this.locality=locality;
46 this.fields=new HashSet<FieldDescriptor>();
47 this.arrays=new HashSet<TypeDescriptor>();
49 this.typeanalysis=typeanalysis;
50 this.cannotdelaymap=cannotdelaymap;
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.FlatGlobalConvNode: {
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 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
212 if (fgcn.getLocality()!=lb||
216 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
219 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
220 TempFlatPair tfp=tfpit.next();
221 if (tfset.contains(tfp)||outofscope(tfp)) {
230 case FKind.FlatSetFieldNode: {
231 //need to translate these if the value we read from may be a
232 //shadow... check this by seeing if any of the values we
233 //may read are in the transread set or came from our caller
234 //or a method we called
236 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
237 if (!fsfn.getField().getType().isPtr())
239 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
241 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
242 TempFlatPair tfp=tfpit.next();
243 if (tfset.contains(tfp)||outofscope(tfp)) {
251 case FKind.FlatSetElementNode: {
252 //need to translate these if the value we read from may be a
253 //shadow... check this by seeing if any of the values we
254 //may read are in the transread set or came from our caller
255 //or a method we called
257 FlatSetElementNode fsen=(FlatSetElementNode)fn;
258 if (!fsen.getSrc().getType().isPtr())
260 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
262 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
263 TempFlatPair tfp=tfpit.next();
264 if (tfset.contains(tfp)||outofscope(tfp)) {
278 public boolean outofscope(TempFlatPair tfp) {
280 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
284 /** Need to figure out which nodes need a transread to make local
285 copies. Transread conceptually tracks conflicts. This depends on
286 what fields/elements are accessed We iterate over all flatnodes that
287 access fields...If these accesses could conflict, we mark the source
288 tempflat pair as needing a transread */
290 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap) {
291 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
293 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
294 FlatNode fn=fnit.next();
295 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
297 //Check whether this node matters for delayed computation
298 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&!cannotdelaymap.get(lb).contains(fn))
301 if (atomictable.get(fn).intValue()>0) {
302 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
304 case FKind.FlatElementNode: {
305 FlatElementNode fen=(FlatElementNode)fn;
306 if (arrays.contains(fen.getSrc().getType())) {
307 //this could cause conflict...figure out conflict set
308 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
310 tfset.addAll(tfpset);
314 case FKind.FlatFieldNode: {
315 FlatFieldNode ffn=(FlatFieldNode)fn;
316 if (fields.contains(ffn.getField())) {
317 //this could cause conflict...figure out conflict set
318 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
320 tfset.addAll(tfpset);
324 case FKind.FlatSetFieldNode: {
325 //definitely need to translate these
326 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
327 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
329 tfset.addAll(tfpset);
332 case FKind.FlatSetElementNode: {
333 //definitely need to translate these
334 FlatSetElementNode fsen=(FlatSetElementNode)fn;
335 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
337 tfset.addAll(tfpset);
340 case FKind.FlatCall: //assume pessimistically that calls do bad things
341 case FKind.FlatReturnNode: {
342 TempDescriptor []readarray=fn.readsTemps();
343 for(int i=0;i<readarray.length;i++) {
344 TempDescriptor rtmp=readarray[i];
345 Set<TempFlatPair> tfpset=tmap.get(rtmp);
347 tfset.addAll(tfpset);
360 //This method generates as output for each node
361 //A map from from temps to a set of temp/flat pairs that the
362 //original temp points to
363 //A temp/flat pair gives the flatnode that the value was created at
364 //and the original temp
366 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
367 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
368 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
369 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
370 MethodDescriptor md=lb.getMethod();
371 FlatMethod fm=state.getMethodFlat(md);
372 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
373 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
377 while(!tovisit.isEmpty()) {
378 FlatNode fn=tovisit.iterator().next();
380 for(int i=0;i<fn.numNext();i++) {
381 FlatNode fnext=fn.getNext(i);
382 if (!discovered.contains(fnext)) {
383 discovered.add(fnext);
387 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
388 if (atomictable.get(fn).intValue()!=0) {
389 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
390 //atomic node, start with new set
391 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
393 ttofn=doMerge(fn, tmptofnset);
395 case FKind.FlatGlobalConvNode: {
396 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
397 if (lb==fgcn.getLocality()&&
399 TempDescriptor[] writes=fn.writesTemps();
400 for(int i=0;i<writes.length;i++) {
401 TempDescriptor wtmp=writes[i];
402 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
403 set.add(new TempFlatPair(wtmp, fn));
404 ttofn.put(wtmp, set);
409 case FKind.FlatFieldNode:
410 case FKind.FlatElementNode: {
411 TempDescriptor[] writes=fn.writesTemps();
412 for(int i=0;i<writes.length;i++) {
413 TempDescriptor wtmp=writes[i];
414 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
415 set.add(new TempFlatPair(wtmp, fn));
416 ttofn.put(wtmp, set);
421 case FKind.FlatMethod: {
422 TempDescriptor[] writes=fn.writesTemps();
423 for(int i=0;i<writes.length;i++) {
424 TempDescriptor wtmp=writes[i];
425 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
426 set.add(new TempFlatPair(wtmp, fn));
427 ttofn.put(wtmp, set);
431 case FKind.FlatOpNode: {
432 FlatOpNode fon=(FlatOpNode)fn;
433 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()&&
434 ttofn.containsKey(fon.getLeft())) {
435 ttofn.put(fon.getDest(), new HashSet<TempFlatPair>(ttofn.get(fon.getLeft())));
440 //Do kill computation
441 TempDescriptor[] writes=fn.writesTemps();
442 for(int i=0;i<writes.length;i++) {
443 TempDescriptor wtmp=writes[i];
444 ttofn.remove(writes[i]);
449 if (!tmptofnset.containsKey(fn)||
450 !tmptofnset.get(fn).equals(ttofn)) {
451 //enqueue nodes to process
452 tmptofnset.put(fn, ttofn);
453 for(int i=0;i<fn.numNext();i++) {
454 FlatNode fnext=fn.getNext(i);
464 /* See what fields and arrays transactions might modify. We only
465 * look at changes to old objects. */
467 public void computeModified(LocalityBinding lb) {
468 MethodDescriptor md=lb.getMethod();
469 FlatMethod fm=state.getMethodFlat(md);
470 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
471 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
472 FlatNode fn=fnit.next();
473 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
474 if (atomictable.get(fn).intValue()>0) {
476 case FKind.FlatSetFieldNode:
477 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
478 fields.add(fsfn.getField());
480 case FKind.FlatSetElementNode:
481 FlatSetElementNode fsen=(FlatSetElementNode) fn;
482 arrays.add(fsen.getDst().getType());
491 //Returns a table that maps a flatnode to a set of temporaries
492 //This set of temporaries is old (meaning they may point to object
493 //allocated before the beginning of the current transaction
495 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
496 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
497 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
498 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
499 MethodDescriptor md=lb.getMethod();
500 FlatMethod fm=state.getMethodFlat(md);
501 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
502 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
506 while(!tovisit.isEmpty()) {
507 FlatNode fn=tovisit.iterator().next();
509 for(int i=0;i<fn.numNext();i++) {
510 FlatNode fnext=fn.getNext(i);
511 if (!discovered.contains(fnext)) {
512 discovered.add(fnext);
516 HashSet<TempDescriptor> oldtemps=null;
517 if (atomictable.get(fn).intValue()!=0) {
518 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
519 //Everything live is old
520 Set<TempDescriptor> lives=livetemps.get(fn);
521 oldtemps=new HashSet<TempDescriptor>();
523 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
524 TempDescriptor tmp=it.next();
525 if (tmp.getType().isPtr()) {
530 oldtemps=new HashSet<TempDescriptor>();
531 //Compute union of old temporaries
532 for(int i=0;i<fn.numPrev();i++) {
533 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
535 oldtemps.addAll(pset);
540 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
542 case FKind.FlatOpNode: {
543 FlatOpNode fon=(FlatOpNode)fn;
544 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
545 if (oldtemps.contains(fon.getLeft()))
546 oldtemps.add(fon.getDest());
548 oldtemps.remove(fon.getDest());
553 TempDescriptor[] writes=fn.writesTemps();
554 for(int i=0;i<writes.length;i++) {
555 TempDescriptor wtemp=writes[i];
556 if (wtemp.getType().isPtr())
564 if (oldtemps!=null) {
565 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
566 fntooldtmp.put(fn, oldtemps);
568 for(int i=0;i<fn.numNext();i++) {
569 FlatNode fnext=fn.getNext(i);
582 TempFlatPair(TempDescriptor t, FlatNode f) {
587 public int hashCode() {
588 return f.hashCode()^t.hashCode();
590 public boolean equals(Object o) {
591 TempFlatPair tf=(TempFlatPair)o;
592 return t.equals(tf.t)&&f.equals(tf.f);