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.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)
215 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
217 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
218 TempFlatPair tfp=tfpit.next();
219 if (tfset.contains(tfp)||outofscope(tfp)) {
228 case FKind.FlatSetFieldNode: {
229 //need to translate these if the value we read from may be a
230 //shadow... check this by seeing if any of the values we
231 //may read are in the transread set or came from our caller
232 //or a method we called
234 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
235 if (!fsfn.getField().getType().isPtr())
237 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
239 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
240 TempFlatPair tfp=tfpit.next();
241 if (tfset.contains(tfp)||outofscope(tfp)) {
249 case FKind.FlatSetElementNode: {
250 //need to translate these if the value we read from may be a
251 //shadow... check this by seeing if any of the values we
252 //may read are in the transread set or came from our caller
253 //or a method we called
255 FlatSetElementNode fsen=(FlatSetElementNode)fn;
256 if (!fsen.getSrc().getType().isPtr())
258 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
260 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
261 TempFlatPair tfp=tfpit.next();
262 if (tfset.contains(tfp)||outofscope(tfp)) {
276 public boolean outofscope(TempFlatPair tfp) {
278 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
282 /** Need to figure out which nodes need a transread to make local
283 copies. Transread conceptually tracks conflicts. This depends on
284 what fields/elements are accessed We iterate over all flatnodes that
285 access fields...If these accesses could conflict, we mark the source
286 tempflat pair as needing a transread */
288 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap) {
289 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
291 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
292 FlatNode fn=fnit.next();
293 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
295 //Check whether this node matters for delayed computation
296 if (cannotdelay!=null&&!cannotdelay.contains(fn))
299 if (atomictable.get(fn).intValue()>0) {
300 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
302 case FKind.FlatElementNode: {
303 FlatElementNode fen=(FlatElementNode)fn;
304 if (arrays.contains(fen.getSrc().getType())) {
305 //this could cause conflict...figure out conflict set
306 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
308 tfset.addAll(tfpset);
312 case FKind.FlatFieldNode: {
313 FlatFieldNode ffn=(FlatFieldNode)fn;
314 if (fields.contains(ffn.getField())) {
315 //this could cause conflict...figure out conflict set
316 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
318 tfset.addAll(tfpset);
322 case FKind.FlatSetFieldNode: {
323 //definitely need to translate these
324 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
325 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
327 tfset.addAll(tfpset);
330 case FKind.FlatSetElementNode: {
331 //definitely need to translate these
332 FlatSetElementNode fsen=(FlatSetElementNode)fn;
333 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
335 tfset.addAll(tfpset);
338 case FKind.FlatCall: //assume pessimistically that calls do bad things
339 case FKind.FlatReturnNode: {
340 TempDescriptor []readarray=fn.readsTemps();
341 for(int i=0;i<readarray.length;i++) {
342 TempDescriptor rtmp=readarray[i];
343 Set<TempFlatPair> tfpset=tmap.get(rtmp);
345 tfset.addAll(tfpset);
358 //This method generates as output for each node
359 //A map from from temps to a set of temp/flat pairs that the
360 //original temp points to
361 //A temp/flat pair gives the flatnode that the value was created at
362 //and the original temp
364 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
365 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
366 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
367 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
368 MethodDescriptor md=lb.getMethod();
369 FlatMethod fm=state.getMethodFlat(md);
370 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
371 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
375 while(!tovisit.isEmpty()) {
376 FlatNode fn=tovisit.iterator().next();
378 for(int i=0;i<fn.numNext();i++) {
379 FlatNode fnext=fn.getNext(i);
380 if (!discovered.contains(fnext)) {
381 discovered.add(fnext);
385 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
386 if (atomictable.get(fn).intValue()!=0) {
387 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
388 //atomic node, start with new set
389 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
391 ttofn=doMerge(fn, tmptofnset);
393 case FKind.FlatGlobalConvNode: {
394 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
395 if (lb==fgcn.getLocality()&&
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);
407 case FKind.FlatFieldNode:
408 case FKind.FlatElementNode: {
409 TempDescriptor[] writes=fn.writesTemps();
410 for(int i=0;i<writes.length;i++) {
411 TempDescriptor wtmp=writes[i];
412 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
413 set.add(new TempFlatPair(wtmp, fn));
414 ttofn.put(wtmp, set);
419 case FKind.FlatMethod: {
420 TempDescriptor[] writes=fn.writesTemps();
421 for(int i=0;i<writes.length;i++) {
422 TempDescriptor wtmp=writes[i];
423 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
424 set.add(new TempFlatPair(wtmp, fn));
425 ttofn.put(wtmp, set);
429 case FKind.FlatOpNode: {
430 FlatOpNode fon=(FlatOpNode)fn;
431 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()&&
432 ttofn.containsKey(fon.getLeft())) {
433 ttofn.put(fon.getDest(), new HashSet<TempFlatPair>(ttofn.get(fon.getLeft())));
438 //Do kill computation
439 TempDescriptor[] writes=fn.writesTemps();
440 for(int i=0;i<writes.length;i++) {
441 TempDescriptor wtmp=writes[i];
442 ttofn.remove(writes[i]);
447 if (!tmptofnset.containsKey(fn)||
448 !tmptofnset.get(fn).equals(ttofn)) {
449 //enqueue nodes to process
450 tmptofnset.put(fn, ttofn);
451 for(int i=0;i<fn.numNext();i++) {
452 FlatNode fnext=fn.getNext(i);
462 /* See what fields and arrays transactions might modify. We only
463 * look at changes to old objects. */
465 public void computeModified(LocalityBinding lb) {
466 MethodDescriptor md=lb.getMethod();
467 FlatMethod fm=state.getMethodFlat(md);
468 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
469 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
470 FlatNode fn=fnit.next();
471 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
472 if (atomictable.get(fn).intValue()>0) {
474 case FKind.FlatSetFieldNode:
475 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
476 fields.add(fsfn.getField());
478 case FKind.FlatSetElementNode:
479 FlatSetElementNode fsen=(FlatSetElementNode) fn;
480 arrays.add(fsen.getDst().getType());
489 //Returns a table that maps a flatnode to a set of temporaries
490 //This set of temporaries is old (meaning they may point to object
491 //allocated before the beginning of the current transaction
493 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
494 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
495 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
496 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
497 MethodDescriptor md=lb.getMethod();
498 FlatMethod fm=state.getMethodFlat(md);
499 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
500 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=locality.computeLiveTemps(fm);
504 while(!tovisit.isEmpty()) {
505 FlatNode fn=tovisit.iterator().next();
507 for(int i=0;i<fn.numNext();i++) {
508 FlatNode fnext=fn.getNext(i);
509 if (!discovered.contains(fnext)) {
510 discovered.add(fnext);
514 HashSet<TempDescriptor> oldtemps=null;
515 if (atomictable.get(fn).intValue()!=0) {
516 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
517 //Everything live is old
518 Set<TempDescriptor> lives=livetemps.get(fn);
519 oldtemps=new HashSet<TempDescriptor>();
521 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
522 TempDescriptor tmp=it.next();
523 if (tmp.getType().isPtr()) {
528 oldtemps=new HashSet<TempDescriptor>();
529 //Compute union of old temporaries
530 for(int i=0;i<fn.numPrev();i++) {
531 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
533 oldtemps.addAll(pset);
538 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
540 case FKind.FlatOpNode: {
541 FlatOpNode fon=(FlatOpNode)fn;
542 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
543 if (oldtemps.contains(fon.getLeft()))
544 oldtemps.add(fon.getDest());
546 oldtemps.remove(fon.getDest());
551 TempDescriptor[] writes=fn.writesTemps();
552 for(int i=0;i<writes.length;i++) {
553 TempDescriptor wtemp=writes[i];
554 if (wtemp.getType().isPtr())
562 if (oldtemps!=null) {
563 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
564 fntooldtmp.put(fn, oldtemps);
566 for(int i=0;i<fn.numNext();i++) {
567 FlatNode fnext=fn.getNext(i);
580 TempFlatPair(TempDescriptor t, FlatNode f) {
585 public int hashCode() {
586 return f.hashCode()^t.hashCode();
588 public boolean equals(Object o) {
589 TempFlatPair tf=(TempFlatPair)o;
590 return t.equals(tf.t)&&f.equals(tf.f);