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> writeset=(state.READSET&&gft!=null)?twritemap.get(lb):treadmap.get(lb);
127 FlatMethod fm=state.getMethodFlat(lb.getMethod());
128 HashSet<FlatNode> needsget=new HashSet<FlatNode>();
129 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
130 FlatNode fn=fnit.next();
131 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
132 if (atomictable.get(fn).intValue()>0&&fn.kind()==FKind.FlatElementNode) {
133 FlatElementNode fen=(FlatElementNode)fn;
134 Set<TempFlatPair> tfpset=fnmap.get(fen).get(fen.getSrc());
136 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
137 TempFlatPair tfp=tfpit.next();
138 if (writeset.contains(tfp.f)) {
147 getmap.put(lb, needsget);
150 //We have a set of things we write to, figure out what things this
152 public void expandTypes() {
153 Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
154 for(Iterator<TypeDescriptor> it=arrays.iterator();it.hasNext();) {
155 TypeDescriptor td=it.next();
156 expandedarrays.addAll(typeanalysis.expand(td));
158 arrays=expandedarrays;
161 Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
162 Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
163 for(int i=0;i<fn.numPrev();i++) {
164 FlatNode fprev=fn.getPrev(i);
165 Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
167 for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
168 TempDescriptor td=tmpit.next();
169 Set<TempFlatPair> fnset=tabset.get(td);
170 if (!table.containsKey(td))
171 table.put(td, new HashSet<TempFlatPair>());
172 table.get(td).addAll(fnset);
179 public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
180 return srcmap.get(lb);
183 public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
184 return srcmap.get(lb).contains(fn);
187 public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
188 return leftsrcmap.get(lb).contains(fn);
191 public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
192 return rightsrcmap.get(lb).contains(fn);
195 public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
196 return treadmap.get(lb).contains(fn);
199 public boolean getNeedGet(LocalityBinding lb, FlatNode fn) {
201 return getmap.get(lb).contains(fn);
202 else throw new Error();
205 public boolean getNeedWriteTrans(LocalityBinding lb, FlatNode fn) {
207 return twritemap.get(lb).contains(fn);
208 else throw new Error();
211 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
212 return lbtofnmap.get(lb);
215 private void analyzeLocality(LocalityBinding lb) {
216 MethodDescriptor md=lb.getMethod();
217 FlatMethod fm=state.getMethodFlat(md);
219 //Compute map from flatnode -> (temps -> source of value)
220 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
221 lbtofnmap.put(lb,fnmap);
222 HashSet<TempFlatPair> writeset=null;
224 writeset=new HashSet<TempFlatPair>();
226 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
228 writemap.put(lb, writeset);
231 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
232 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
233 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
234 transreadmap.put(lb, tfset);
235 srcmap.put(lb,srctrans);
236 leftsrcmap.put(lb,leftsrctrans);
237 rightsrcmap.put(lb,rightsrctrans);
239 //compute writes that need translation on source
240 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
241 FlatNode fn=fnit.next();
242 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
243 if (atomictable.get(fn).intValue()>0) {
244 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
246 //We might need to translate arguments to pointer comparison
248 case FKind.FlatOpNode: {
249 FlatOpNode fon=(FlatOpNode)fn;
250 if (fon.getOp().getOp()==Operation.EQUAL||
251 fon.getOp().getOp()==Operation.NOTEQUAL) {
252 if (!fon.getLeft().getType().isPtr())
254 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
255 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
256 //handle left operand
257 if (lefttfpset!=null) {
258 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
259 TempFlatPair tfp=tfpit.next();
260 if (tfset.contains(tfp)||outofscope(tfp)) {
261 leftsrctrans.add(fon);
266 //handle right operand
267 if (righttfpset!=null) {
268 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
269 TempFlatPair tfp=tfpit.next();
270 if (tfset.contains(tfp)||outofscope(tfp)) {
271 rightsrctrans.add(fon);
280 case FKind.FlatGlobalConvNode: {
281 //need to translate these if the value we read from may be a
282 //shadow... check this by seeing if any of the values we
283 //may read are in the transread set or came from our caller
284 //or a method we called
286 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
287 if (fgcn.getLocality()!=lb||
291 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
294 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
295 TempFlatPair tfp=tfpit.next();
296 if (tfset.contains(tfp)||outofscope(tfp)) {
305 case FKind.FlatSetFieldNode: {
306 //need to translate these if the value we read from may be a
307 //shadow... check this by seeing if any of the values we
308 //may read are in the transread set or came from our caller
309 //or a method we called
311 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
312 if (!fsfn.getField().getType().isPtr())
314 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
316 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
317 TempFlatPair tfp=tfpit.next();
318 if (tfset.contains(tfp)||outofscope(tfp)) {
326 case FKind.FlatSetElementNode: {
327 //need to translate these if the value we read from may be a
328 //shadow... check this by seeing if any of the values we
329 //may read are in the transread set or came from our caller
330 //or a method we called
332 FlatSetElementNode fsen=(FlatSetElementNode)fn;
333 if (!fsen.getSrc().getType().isPtr())
335 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
337 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
338 TempFlatPair tfp=tfpit.next();
339 if (tfset.contains(tfp)||outofscope(tfp)) {
352 setNeedReadTrans(lb);
353 computeneedsarrayget(lb, fnmap);
356 public boolean outofscope(TempFlatPair tfp) {
358 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
361 private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
362 //inside of transaction, try to convert rw access to ro access
363 MethodDescriptor md=lb.getMethod();
364 FlatMethod fm=state.getMethodFlat(md);
365 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
367 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
368 toanalyze.addAll(fm.getNodeSet());
370 while(!toanalyze.isEmpty()) {
371 FlatNode fn=toanalyze.iterator().next();
372 toanalyze.remove(fn);
373 HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
374 HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
376 //Stop if we aren't in a transaction
377 if (atomictable.get(fn).intValue()==0)
380 //Do merge of all exits
381 for(int i=0;i<fn.numNext();i++) {
382 FlatNode fnnext=fn.getNext(i);
383 if (updatedtypemap.containsKey(fnnext)) {
384 updatetypeset.addAll(updatedtypemap.get(fnnext));
386 if (updatedfieldmap.containsKey(fnnext)) {
387 updatefieldset.addAll(updatedfieldmap.get(fnnext));
392 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
394 case FKind.FlatSetFieldNode: {
395 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
396 updatefieldset.add(fsfn.getField());
399 case FKind.FlatSetElementNode: {
400 FlatSetElementNode fsen=(FlatSetElementNode)fn;
401 updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
404 case FKind.FlatCall: {
405 FlatCall fcall=(FlatCall)fn;
406 MethodDescriptor mdfc=fcall.getMethod();
408 //get modified fields
409 Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
410 updatefieldset.addAll(fields);
412 //get modified arrays
413 Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
414 updatetypeset.addAll(typeanalysis.expandSet(arrays));
420 if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
421 !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
422 updatedtypemap.put(fn, updatetypeset);
423 updatedfieldmap.put(fn, updatefieldset);
424 for(int i=0;i<fn.numPrev();i++) {
425 toanalyze.add(fn.getPrev(i));
432 /** Need to figure out which nodes need a transread to make local
433 copies. Transread conceptually tracks conflicts. This depends on
434 what fields/elements are accessed We iterate over all flatnodes that
435 access fields...If these accesses could conflict, we mark the source
436 tempflat pair as needing a transread */
439 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
440 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
442 //Compute maps from flatnodes -> sets of things that may be updated after this node
443 Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
444 Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
446 if (writeset!=null&&!lb.isAtomic()) {
447 updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
448 updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
449 computeReadOnly(lb, updatedtypemap, updatedfieldmap);
452 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
453 FlatNode fn=fnit.next();
454 //Check whether this node matters for cannot delayed computation
455 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
458 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
459 if (atomictable.get(fn).intValue()>0) {
460 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
462 case FKind.FlatElementNode: {
463 FlatElementNode fen=(FlatElementNode)fn;
464 if (arrays.contains(fen.getSrc().getType())) {
465 //this could cause conflict...figure out conflict set
466 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
468 tfset.addAll(tfpset);
470 if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
471 //this could cause conflict...figure out conflict set
472 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
474 writeset.addAll(tfpset);
478 case FKind.FlatFieldNode: {
479 FlatFieldNode ffn=(FlatFieldNode)fn;
480 if (fields.contains(ffn.getField())) {
481 //this could cause conflict...figure out conflict set
482 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
484 tfset.addAll(tfpset);
486 if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
487 //this could cause conflict...figure out conflict set
488 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
490 writeset.addAll(tfpset);
494 case FKind.FlatSetFieldNode: {
495 //definitely need to translate these
496 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
497 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
499 tfset.addAll(tfpset);
500 if (writeset!=null) {
502 writeset.addAll(tfpset);
506 case FKind.FlatSetElementNode: {
507 //definitely need to translate these
508 FlatSetElementNode fsen=(FlatSetElementNode)fn;
509 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
511 tfset.addAll(tfpset);
512 if (writeset!=null) {
514 writeset.addAll(tfpset);
518 case FKind.FlatCall: //assume pessimistically that calls do bad things
519 case FKind.FlatReturnNode: {
520 TempDescriptor []readarray=fn.readsTemps();
521 for(int i=0;i<readarray.length;i++) {
522 TempDescriptor rtmp=readarray[i];
523 Set<TempFlatPair> tfpset=tmap.get(rtmp);
525 tfset.addAll(tfpset);
526 if (writeset!=null) {
528 writeset.addAll(tfpset);
542 //This method generates as output for each node
543 //A map from from temps to a set of temp/flat pairs that the
544 //original temp points to
545 //A temp/flat pair gives the flatnode that the value was created at
546 //and the original temp
548 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
549 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
550 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
551 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
552 MethodDescriptor md=lb.getMethod();
553 FlatMethod fm=state.getMethodFlat(md);
554 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
555 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
559 while(!tovisit.isEmpty()) {
560 FlatNode fn=tovisit.iterator().next();
562 for(int i=0;i<fn.numNext();i++) {
563 FlatNode fnext=fn.getNext(i);
564 if (!discovered.contains(fnext)) {
565 discovered.add(fnext);
569 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
570 if (atomictable.get(fn).intValue()!=0) {
571 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
572 //atomic node, start with new set
573 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
575 ttofn=doMerge(fn, tmptofnset);
577 case FKind.FlatGlobalConvNode: {
578 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
579 if (lb==fgcn.getLocality()&&
581 TempDescriptor[] writes=fn.writesTemps();
582 for(int i=0;i<writes.length;i++) {
583 TempDescriptor wtmp=writes[i];
584 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
585 set.add(new TempFlatPair(wtmp, fn));
586 ttofn.put(wtmp, set);
591 case FKind.FlatFieldNode:
592 case FKind.FlatElementNode: {
593 TempDescriptor[] writes=fn.writesTemps();
594 for(int i=0;i<writes.length;i++) {
595 TempDescriptor wtmp=writes[i];
596 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
597 set.add(new TempFlatPair(wtmp, fn));
598 ttofn.put(wtmp, set);
603 case FKind.FlatMethod: {
604 TempDescriptor[] writes=fn.writesTemps();
605 for(int i=0;i<writes.length;i++) {
606 TempDescriptor wtmp=writes[i];
607 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
608 set.add(new TempFlatPair(wtmp, fn));
609 ttofn.put(wtmp, set);
613 case FKind.FlatCastNode:
614 case FKind.FlatOpNode:
615 if (fn.kind()==FKind.FlatCastNode) {
616 FlatCastNode fcn=(FlatCastNode)fn;
617 if (fcn.getDst().getType().isPtr()) {
618 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
619 if (ttofn.containsKey(fcn.getSrc()))
620 set.addAll(ttofn.get(fcn.getSrc()));
622 set.add(new TempFlatPair(fcn.getDst(), fn));
623 ttofn.put(fcn.getDst(), set);
626 } else if (fn.kind()==FKind.FlatOpNode) {
627 FlatOpNode fon=(FlatOpNode)fn;
628 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
629 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
630 if (ttofn.containsKey(fon.getLeft()))
631 set.addAll(ttofn.get(fon.getLeft()));
633 set.add(new TempFlatPair(fon.getDest(), fn));
634 ttofn.put(fon.getDest(), set);
639 //Do kill computation
640 TempDescriptor[] writes=fn.writesTemps();
641 for(int i=0;i<writes.length;i++) {
642 TempDescriptor wtmp=writes[i];
643 ttofn.remove(writes[i]);
648 if (!tmptofnset.containsKey(fn)||
649 !tmptofnset.get(fn).equals(ttofn)) {
650 //enqueue nodes to process
651 tmptofnset.put(fn, ttofn);
652 for(int i=0;i<fn.numNext();i++) {
653 FlatNode fnext=fn.getNext(i);
663 /* See what fields and arrays transactions might modify. We only
664 * look at changes to old objects. */
666 //Bug fix: original version forget to check if object is new and
669 public void computeModified(LocalityBinding lb) {
670 MethodDescriptor md=lb.getMethod();
671 FlatMethod fm=state.getMethodFlat(md);
672 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
673 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
674 FlatNode fn=fnit.next();
675 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
676 if (atomictable.get(fn).intValue()>0) {
677 Set<TempDescriptor> oldtemp=oldtemps.get(fn);
679 case FKind.FlatSetFieldNode:
680 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
681 if (oldtemp.contains(fsfn.getDst()))
682 fields.add(fsfn.getField());
684 case FKind.FlatSetElementNode:
685 FlatSetElementNode fsen=(FlatSetElementNode) fn;
686 if (oldtemp.contains(fsen.getDst()))
687 arrays.add(fsen.getDst().getType());
696 //Returns a table that maps a flatnode to a set of temporaries
697 //This set of temporaries is old (meaning they may point to object
698 //allocated before the beginning of the current transaction
700 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
701 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
702 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
703 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
704 MethodDescriptor md=lb.getMethod();
705 FlatMethod fm=state.getMethodFlat(md);
706 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
707 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
711 while(!tovisit.isEmpty()) {
712 FlatNode fn=tovisit.iterator().next();
714 for(int i=0;i<fn.numNext();i++) {
715 FlatNode fnext=fn.getNext(i);
716 if (!discovered.contains(fnext)) {
717 discovered.add(fnext);
721 HashSet<TempDescriptor> oldtemps=null;
722 if (atomictable.get(fn).intValue()!=0) {
723 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
724 //Everything live is old
725 Set<TempDescriptor> lives=livetemps.get(fn);
726 oldtemps=new HashSet<TempDescriptor>();
728 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
729 TempDescriptor tmp=it.next();
730 if (tmp.getType().isPtr()) {
735 oldtemps=new HashSet<TempDescriptor>();
736 //Compute union of old temporaries
737 for(int i=0;i<fn.numPrev();i++) {
738 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
740 oldtemps.addAll(pset);
745 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
747 case FKind.FlatOpNode:
748 case FKind.FlatCastNode:
749 if (fn.kind()==FKind.FlatCastNode) {
750 FlatCastNode fcn=(FlatCastNode)fn;
751 if (fcn.getDst().getType().isPtr()) {
752 if (oldtemps.contains(fcn.getSrc()))
753 oldtemps.add(fcn.getDst());
755 oldtemps.remove(fcn.getDst());
758 } else if (fn.kind()==FKind.FlatOpNode) {
759 FlatOpNode fon=(FlatOpNode)fn;
760 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
761 if (oldtemps.contains(fon.getLeft()))
762 oldtemps.add(fon.getDest());
764 oldtemps.remove(fon.getDest());
769 TempDescriptor[] writes=fn.writesTemps();
770 for(int i=0;i<writes.length;i++) {
771 TempDescriptor wtemp=writes[i];
772 if (wtemp.getType().isPtr())
780 if (oldtemps!=null) {
781 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
782 fntooldtmp.put(fn, oldtemps);
784 for(int i=0;i<fn.numNext();i++) {
785 FlatNode fnext=fn.getNext(i);
798 TempFlatPair(TempDescriptor t, FlatNode f) {
803 public int hashCode() {
804 return f.hashCode()^t.hashCode();
806 public boolean equals(Object o) {
807 TempFlatPair tf=(TempFlatPair)o;
808 return t.equals(tf.t)&&f.equals(tf.f);