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;
14 import Analysis.Liveness;
15 import Analysis.Loops.GlobalFieldType;
17 public class DiscoverConflicts {
18 Set<FieldDescriptor> fields;
19 Set<TypeDescriptor> arrays;
20 LocalityAnalysis locality;
22 Hashtable<LocalityBinding, Set<FlatNode>> treadmap;
23 Hashtable<LocalityBinding, Set<TempFlatPair>> transreadmap;
24 Hashtable<LocalityBinding, Set<FlatNode>> twritemap;
25 Hashtable<LocalityBinding, Set<TempFlatPair>> writemap;
26 Hashtable<LocalityBinding, Set<FlatNode>> getmap;
28 Hashtable<LocalityBinding, Set<FlatNode>> srcmap;
29 Hashtable<LocalityBinding, Set<FlatNode>> leftsrcmap;
30 Hashtable<LocalityBinding, Set<FlatNode>> rightsrcmap;
31 TypeAnalysis typeanalysis;
32 Hashtable<LocalityBinding, HashSet<FlatNode>>cannotdelaymap;
33 Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>> lbtofnmap;
34 boolean inclusive=false;
35 boolean normalassign=false;
38 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
39 this.locality=locality;
40 this.fields=new HashSet<FieldDescriptor>();
41 this.arrays=new HashSet<TypeDescriptor>();
43 this.typeanalysis=typeanalysis;
44 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
45 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
46 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
47 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
48 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
49 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
51 twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
52 writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
54 getmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
58 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap, boolean inclusive, boolean normalassign, GlobalFieldType gft) {
59 this.locality=locality;
60 this.fields=new HashSet<FieldDescriptor>();
61 this.arrays=new HashSet<TypeDescriptor>();
63 this.typeanalysis=typeanalysis;
64 this.cannotdelaymap=cannotdelaymap;
65 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
66 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
67 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
68 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
69 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
70 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
71 this.inclusive=inclusive;
72 this.normalassign=normalassign;
74 twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
75 writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
77 getmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
81 public Set<FieldDescriptor> getFields() {
85 public Set<TypeDescriptor> getArrays() {
89 public void doAnalysis() {
90 //Compute fields and arrays for all transactions. Note that we
91 //only look at changes to old objects
93 Set<LocalityBinding> localityset=locality.getLocalityBindings();
94 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
95 computeModified(lb.next());
98 //Compute set of nodes that need transread
99 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
100 LocalityBinding l=lb.next();
105 //Change flatnode/temp pairs to just flatnodes that need transactional reads
107 private void setNeedReadTrans(LocalityBinding lb) {
108 HashSet<FlatNode> set=new HashSet<FlatNode>();
109 for(Iterator<TempFlatPair> it=transreadmap.get(lb).iterator();it.hasNext();) {
110 TempFlatPair tfp=it.next();
113 treadmap.put(lb, set);
115 //need to translate write map set
116 set=new HashSet<FlatNode>();
117 for(Iterator<TempFlatPair> it=writemap.get(lb).iterator();it.hasNext();) {
118 TempFlatPair tfp=it.next();
121 twritemap.put(lb, set);
125 private void computeneedsarrayget(LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap) {
126 // Set<FlatNode> gwriteset=(state.READSET&&gft!=null)?twritemap.get(lb):treadmap.get(lb);
127 Set<FlatNode> gwriteset=treadmap.get(lb);
128 FlatMethod fm=state.getMethodFlat(lb.getMethod());
129 HashSet<FlatNode> needsget=new HashSet<FlatNode>();
130 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
131 FlatNode fn=fnit.next();
132 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
133 if (atomictable.get(fn).intValue()>0&&fn.kind()==FKind.FlatElementNode) {
134 FlatElementNode fen=(FlatElementNode)fn;
135 Set<TempFlatPair> tfpset=fnmap.get(fen).get(fen.getSrc());
137 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
138 TempFlatPair tfp=tfpit.next();
139 if (gwriteset.contains(tfp.f)) {
148 getmap.put(lb, needsget);
151 //We have a set of things we write to, figure out what things this
153 public void expandTypes() {
154 Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
155 for(Iterator<TypeDescriptor> it=arrays.iterator();it.hasNext();) {
156 TypeDescriptor td=it.next();
157 expandedarrays.addAll(typeanalysis.expand(td));
159 arrays=expandedarrays;
162 Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
163 Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
164 for(int i=0;i<fn.numPrev();i++) {
165 FlatNode fprev=fn.getPrev(i);
166 Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
168 for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
169 TempDescriptor td=tmpit.next();
170 Set<TempFlatPair> fnset=tabset.get(td);
171 if (!table.containsKey(td))
172 table.put(td, new HashSet<TempFlatPair>());
173 table.get(td).addAll(fnset);
180 public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
181 return srcmap.get(lb);
184 public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
185 return srcmap.get(lb).contains(fn);
188 public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
189 return leftsrcmap.get(lb).contains(fn);
192 public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
193 return rightsrcmap.get(lb).contains(fn);
196 public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
197 return treadmap.get(lb).contains(fn);
200 public boolean getNeedGet(LocalityBinding lb, FlatNode fn) {
202 return getmap.get(lb).contains(fn);
203 else throw new Error();
206 public boolean getNeedWriteTrans(LocalityBinding lb, FlatNode fn) {
208 return twritemap.get(lb).contains(fn);
209 else throw new Error();
212 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
213 return lbtofnmap.get(lb);
216 private void analyzeLocality(LocalityBinding lb) {
217 MethodDescriptor md=lb.getMethod();
218 FlatMethod fm=state.getMethodFlat(md);
220 //Compute map from flatnode -> (temps -> source of value)
221 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
222 lbtofnmap.put(lb,fnmap);
223 HashSet<TempFlatPair> writeset=null;
225 writeset=new HashSet<TempFlatPair>();
227 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
229 writemap.put(lb, writeset);
232 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
233 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
234 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
235 transreadmap.put(lb, tfset);
236 srcmap.put(lb,srctrans);
237 leftsrcmap.put(lb,leftsrctrans);
238 rightsrcmap.put(lb,rightsrctrans);
240 //compute writes that need translation on source
241 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
242 FlatNode fn=fnit.next();
243 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
244 if (atomictable.get(fn).intValue()>0) {
245 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
247 //We might need to translate arguments to pointer comparison
249 case FKind.FlatOpNode: {
250 FlatOpNode fon=(FlatOpNode)fn;
251 if (fon.getOp().getOp()==Operation.EQUAL||
252 fon.getOp().getOp()==Operation.NOTEQUAL) {
253 if (!fon.getLeft().getType().isPtr())
255 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
256 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
257 //handle left operand
258 if (lefttfpset!=null) {
259 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
260 TempFlatPair tfp=tfpit.next();
261 if (tfset.contains(tfp)||outofscope(tfp)) {
262 leftsrctrans.add(fon);
267 //handle right operand
268 if (righttfpset!=null) {
269 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
270 TempFlatPair tfp=tfpit.next();
271 if (tfset.contains(tfp)||outofscope(tfp)) {
272 rightsrctrans.add(fon);
281 case FKind.FlatGlobalConvNode: {
282 //need to translate these if the value we read from may be a
283 //shadow... check this by seeing if any of the values we
284 //may read are in the transread set or came from our caller
285 //or a method we called
287 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
288 if (fgcn.getLocality()!=lb||
292 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
295 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
296 TempFlatPair tfp=tfpit.next();
297 if (tfset.contains(tfp)||outofscope(tfp)) {
306 case FKind.FlatSetFieldNode: {
307 //need to translate these if the value we read from may be a
308 //shadow... check this by seeing if any of the values we
309 //may read are in the transread set or came from our caller
310 //or a method we called
312 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
313 if (!fsfn.getField().getType().isPtr())
315 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
317 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
318 TempFlatPair tfp=tfpit.next();
319 if (tfset.contains(tfp)||outofscope(tfp)) {
327 case FKind.FlatSetElementNode: {
328 //need to translate these if the value we read from may be a
329 //shadow... check this by seeing if any of the values we
330 //may read are in the transread set or came from our caller
331 //or a method we called
333 FlatSetElementNode fsen=(FlatSetElementNode)fn;
334 if (!fsen.getSrc().getType().isPtr())
336 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
338 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
339 TempFlatPair tfp=tfpit.next();
340 if (tfset.contains(tfp)||outofscope(tfp)) {
353 setNeedReadTrans(lb);
354 computeneedsarrayget(lb, fnmap);
357 public boolean outofscope(TempFlatPair tfp) {
359 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
362 private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
363 //inside of transaction, try to convert rw access to ro access
364 MethodDescriptor md=lb.getMethod();
365 FlatMethod fm=state.getMethodFlat(md);
366 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
368 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
369 toanalyze.addAll(fm.getNodeSet());
371 while(!toanalyze.isEmpty()) {
372 FlatNode fn=toanalyze.iterator().next();
373 toanalyze.remove(fn);
374 HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
375 HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
377 //Stop if we aren't in a transaction
378 if (atomictable.get(fn).intValue()==0)
381 //Do merge of all exits
382 for(int i=0;i<fn.numNext();i++) {
383 FlatNode fnnext=fn.getNext(i);
384 if (updatedtypemap.containsKey(fnnext)) {
385 updatetypeset.addAll(updatedtypemap.get(fnnext));
387 if (updatedfieldmap.containsKey(fnnext)) {
388 updatefieldset.addAll(updatedfieldmap.get(fnnext));
393 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
395 case FKind.FlatSetFieldNode: {
396 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
397 updatefieldset.add(fsfn.getField());
400 case FKind.FlatSetElementNode: {
401 FlatSetElementNode fsen=(FlatSetElementNode)fn;
402 updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
405 case FKind.FlatCall: {
406 FlatCall fcall=(FlatCall)fn;
407 MethodDescriptor mdfc=fcall.getMethod();
409 //get modified fields
410 Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
411 updatefieldset.addAll(fields);
413 //get modified arrays
414 Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
415 updatetypeset.addAll(typeanalysis.expandSet(arrays));
421 if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
422 !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
423 updatedtypemap.put(fn, updatetypeset);
424 updatedfieldmap.put(fn, updatefieldset);
425 for(int i=0;i<fn.numPrev();i++) {
426 toanalyze.add(fn.getPrev(i));
433 /** Need to figure out which nodes need a transread to make local
434 copies. Transread conceptually tracks conflicts. This depends on
435 what fields/elements are accessed We iterate over all flatnodes that
436 access fields...If these accesses could conflict, we mark the source
437 tempflat pair as needing a transread */
440 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
441 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
443 //Compute maps from flatnodes -> sets of things that may be updated after this node
444 Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
445 Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
447 if (writeset!=null&&!lb.isAtomic()) {
448 updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
449 updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
450 computeReadOnly(lb, updatedtypemap, updatedfieldmap);
453 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
454 FlatNode fn=fnit.next();
455 //Check whether this node matters for cannot delayed computation
456 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
459 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
460 if (atomictable.get(fn).intValue()>0) {
461 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
463 case FKind.FlatElementNode: {
464 FlatElementNode fen=(FlatElementNode)fn;
465 if (arrays.contains(fen.getSrc().getType())) {
466 //this could cause conflict...figure out conflict set
467 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
469 tfset.addAll(tfpset);
471 if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
472 //this could cause conflict...figure out conflict set
473 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
475 writeset.addAll(tfpset);
479 case FKind.FlatFieldNode: {
480 FlatFieldNode ffn=(FlatFieldNode)fn;
481 if (fields.contains(ffn.getField())) {
482 //this could cause conflict...figure out conflict set
483 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
485 tfset.addAll(tfpset);
487 if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
488 //this could cause conflict...figure out conflict set
489 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
491 writeset.addAll(tfpset);
495 case FKind.FlatSetFieldNode: {
496 //definitely need to translate these
497 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
498 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
500 tfset.addAll(tfpset);
501 if (writeset!=null) {
503 writeset.addAll(tfpset);
507 case FKind.FlatSetElementNode: {
508 //definitely need to translate these
509 FlatSetElementNode fsen=(FlatSetElementNode)fn;
510 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
512 tfset.addAll(tfpset);
513 if (writeset!=null) {
515 writeset.addAll(tfpset);
519 case FKind.FlatCall: //assume pessimistically that calls do bad things
520 case FKind.FlatReturnNode: {
521 TempDescriptor []readarray=fn.readsTemps();
522 for(int i=0;i<readarray.length;i++) {
523 TempDescriptor rtmp=readarray[i];
524 Set<TempFlatPair> tfpset=tmap.get(rtmp);
526 tfset.addAll(tfpset);
527 if (writeset!=null) {
529 writeset.addAll(tfpset);
543 //This method generates as output for each node
544 //A map from from temps to a set of temp/flat pairs that the
545 //original temp points to
546 //A temp/flat pair gives the flatnode that the value was created at
547 //and the original temp
549 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
550 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
551 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
552 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
553 MethodDescriptor md=lb.getMethod();
554 FlatMethod fm=state.getMethodFlat(md);
555 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
556 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
560 while(!tovisit.isEmpty()) {
561 FlatNode fn=tovisit.iterator().next();
563 for(int i=0;i<fn.numNext();i++) {
564 FlatNode fnext=fn.getNext(i);
565 if (!discovered.contains(fnext)) {
566 discovered.add(fnext);
570 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
571 if (atomictable.get(fn).intValue()!=0) {
572 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
573 //atomic node, start with new set
574 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
576 ttofn=doMerge(fn, tmptofnset);
578 case FKind.FlatGlobalConvNode: {
579 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
580 if (lb==fgcn.getLocality()&&
582 TempDescriptor[] writes=fn.writesTemps();
583 for(int i=0;i<writes.length;i++) {
584 TempDescriptor wtmp=writes[i];
585 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
586 set.add(new TempFlatPair(wtmp, fn));
587 ttofn.put(wtmp, set);
592 case FKind.FlatFieldNode:
593 case FKind.FlatElementNode: {
594 TempDescriptor[] writes=fn.writesTemps();
595 for(int i=0;i<writes.length;i++) {
596 TempDescriptor wtmp=writes[i];
597 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
598 set.add(new TempFlatPair(wtmp, fn));
599 ttofn.put(wtmp, set);
604 case FKind.FlatMethod: {
605 TempDescriptor[] writes=fn.writesTemps();
606 for(int i=0;i<writes.length;i++) {
607 TempDescriptor wtmp=writes[i];
608 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
609 set.add(new TempFlatPair(wtmp, fn));
610 ttofn.put(wtmp, set);
614 case FKind.FlatCastNode:
615 case FKind.FlatOpNode:
616 if (fn.kind()==FKind.FlatCastNode) {
617 FlatCastNode fcn=(FlatCastNode)fn;
618 if (fcn.getDst().getType().isPtr()) {
619 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
620 if (ttofn.containsKey(fcn.getSrc()))
621 set.addAll(ttofn.get(fcn.getSrc()));
623 set.add(new TempFlatPair(fcn.getDst(), fn));
624 ttofn.put(fcn.getDst(), set);
627 } else if (fn.kind()==FKind.FlatOpNode) {
628 FlatOpNode fon=(FlatOpNode)fn;
629 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
630 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
631 if (ttofn.containsKey(fon.getLeft()))
632 set.addAll(ttofn.get(fon.getLeft()));
634 set.add(new TempFlatPair(fon.getDest(), fn));
635 ttofn.put(fon.getDest(), set);
640 //Do kill computation
641 TempDescriptor[] writes=fn.writesTemps();
642 for(int i=0;i<writes.length;i++) {
643 TempDescriptor wtmp=writes[i];
644 ttofn.remove(writes[i]);
649 if (!tmptofnset.containsKey(fn)||
650 !tmptofnset.get(fn).equals(ttofn)) {
651 //enqueue nodes to process
652 tmptofnset.put(fn, ttofn);
653 for(int i=0;i<fn.numNext();i++) {
654 FlatNode fnext=fn.getNext(i);
664 /* See what fields and arrays transactions might modify. We only
665 * look at changes to old objects. */
667 //Bug fix: original version forget to check if object is new and
670 public void computeModified(LocalityBinding lb) {
671 MethodDescriptor md=lb.getMethod();
672 FlatMethod fm=state.getMethodFlat(md);
673 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
674 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
675 FlatNode fn=fnit.next();
676 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
677 if (atomictable.get(fn).intValue()>0) {
678 Set<TempDescriptor> oldtemp=oldtemps.get(fn);
680 case FKind.FlatSetFieldNode:
681 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
682 if (oldtemp.contains(fsfn.getDst()))
683 fields.add(fsfn.getField());
685 case FKind.FlatSetElementNode:
686 FlatSetElementNode fsen=(FlatSetElementNode) fn;
687 if (oldtemp.contains(fsen.getDst()))
688 arrays.add(fsen.getDst().getType());
697 //Returns a table that maps a flatnode to a set of temporaries
698 //This set of temporaries is old (meaning they may point to object
699 //allocated before the beginning of the current transaction
701 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
702 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
703 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
704 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
705 MethodDescriptor md=lb.getMethod();
706 FlatMethod fm=state.getMethodFlat(md);
707 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
708 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
712 while(!tovisit.isEmpty()) {
713 FlatNode fn=tovisit.iterator().next();
715 for(int i=0;i<fn.numNext();i++) {
716 FlatNode fnext=fn.getNext(i);
717 if (!discovered.contains(fnext)) {
718 discovered.add(fnext);
722 HashSet<TempDescriptor> oldtemps=null;
723 if (atomictable.get(fn).intValue()!=0) {
724 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
725 //Everything live is old
726 Set<TempDescriptor> lives=livetemps.get(fn);
727 oldtemps=new HashSet<TempDescriptor>();
729 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
730 TempDescriptor tmp=it.next();
731 if (tmp.getType().isPtr()) {
736 oldtemps=new HashSet<TempDescriptor>();
737 //Compute union of old temporaries
738 for(int i=0;i<fn.numPrev();i++) {
739 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
741 oldtemps.addAll(pset);
746 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
748 case FKind.FlatOpNode:
749 case FKind.FlatCastNode:
750 if (fn.kind()==FKind.FlatCastNode) {
751 FlatCastNode fcn=(FlatCastNode)fn;
752 if (fcn.getDst().getType().isPtr()) {
753 if (oldtemps.contains(fcn.getSrc()))
754 oldtemps.add(fcn.getDst());
756 oldtemps.remove(fcn.getDst());
759 } else if (fn.kind()==FKind.FlatOpNode) {
760 FlatOpNode fon=(FlatOpNode)fn;
761 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
762 if (oldtemps.contains(fon.getLeft()))
763 oldtemps.add(fon.getDest());
765 oldtemps.remove(fon.getDest());
770 TempDescriptor[] writes=fn.writesTemps();
771 for(int i=0;i<writes.length;i++) {
772 TempDescriptor wtemp=writes[i];
773 if (wtemp.getType().isPtr())
781 if (oldtemps!=null) {
782 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
783 fntooldtmp.put(fn, oldtemps);
785 for(int i=0;i<fn.numNext();i++) {
786 FlatNode fnext=fn.getNext(i);
799 TempFlatPair(TempDescriptor t, FlatNode f) {
804 public int hashCode() {
805 return f.hashCode()^t.hashCode();
807 public boolean equals(Object o) {
808 TempFlatPair tf=(TempFlatPair)o;
809 return t.equals(tf.t)&&f.equals(tf.f);