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>> srcmap;
27 Hashtable<LocalityBinding, Set<FlatNode>> leftsrcmap;
28 Hashtable<LocalityBinding, Set<FlatNode>> rightsrcmap;
29 TypeAnalysis typeanalysis;
30 Hashtable<LocalityBinding, HashSet<FlatNode>>cannotdelaymap;
31 Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>> lbtofnmap;
32 boolean inclusive=false;
33 boolean normalassign=false;
36 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
37 this.locality=locality;
38 this.fields=new HashSet<FieldDescriptor>();
39 this.arrays=new HashSet<TypeDescriptor>();
41 this.typeanalysis=typeanalysis;
42 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
43 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
44 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
45 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
46 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
47 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
49 twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
50 writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
55 public DiscoverConflicts(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap, boolean inclusive, boolean normalassign, GlobalFieldType gft) {
56 this.locality=locality;
57 this.fields=new HashSet<FieldDescriptor>();
58 this.arrays=new HashSet<TypeDescriptor>();
60 this.typeanalysis=typeanalysis;
61 this.cannotdelaymap=cannotdelaymap;
62 transreadmap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
63 treadmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
64 srcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
65 leftsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
66 rightsrcmap=new Hashtable<LocalityBinding, Set<FlatNode>>();
67 lbtofnmap=new Hashtable<LocalityBinding, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>>();
68 this.inclusive=inclusive;
69 this.normalassign=normalassign;
71 twritemap=new Hashtable<LocalityBinding, Set<FlatNode>>();
72 writemap=new Hashtable<LocalityBinding, Set<TempFlatPair>>();
77 public Set<FieldDescriptor> getFields() {
81 public Set<TypeDescriptor> getArrays() {
85 public void doAnalysis() {
86 //Compute fields and arrays for all transactions. Note that we
87 //only look at changes to old objects
89 Set<LocalityBinding> localityset=locality.getLocalityBindings();
90 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
91 computeModified(lb.next());
94 //Compute set of nodes that need transread
95 for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
96 LocalityBinding l=lb.next();
102 //Change flatnode/temp pairs to just flatnodes that need transactional reads
104 public void setNeedReadTrans(LocalityBinding lb) {
105 HashSet<FlatNode> set=new HashSet<FlatNode>();
106 for(Iterator<TempFlatPair> it=transreadmap.get(lb).iterator();it.hasNext();) {
107 TempFlatPair tfp=it.next();
110 treadmap.put(lb, set);
112 //need to translate write map set
113 set=new HashSet<FlatNode>();
114 for(Iterator<TempFlatPair> it=writemap.get(lb).iterator();it.hasNext();) {
115 TempFlatPair tfp=it.next();
118 twritemap.put(lb, set);
122 //We have a set of things we write to, figure out what things this
124 public void expandTypes() {
125 Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
126 for(Iterator<TypeDescriptor> it=arrays.iterator();it.hasNext();) {
127 TypeDescriptor td=it.next();
128 expandedarrays.addAll(typeanalysis.expand(td));
130 arrays=expandedarrays;
133 Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
134 Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
135 for(int i=0;i<fn.numPrev();i++) {
136 FlatNode fprev=fn.getPrev(i);
137 Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
139 for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator();tmpit.hasNext();) {
140 TempDescriptor td=tmpit.next();
141 Set<TempFlatPair> fnset=tabset.get(td);
142 if (!table.containsKey(td))
143 table.put(td, new HashSet<TempFlatPair>());
144 table.get(td).addAll(fnset);
151 public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
152 return srcmap.get(lb);
155 public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
156 return srcmap.get(lb).contains(fn);
159 public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
160 return leftsrcmap.get(lb).contains(fn);
163 public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
164 return rightsrcmap.get(lb).contains(fn);
167 public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
168 return treadmap.get(lb).contains(fn);
171 public boolean getNeedWriteTrans(LocalityBinding lb, FlatNode fn) {
173 return twritemap.get(lb).contains(fn);
174 else throw new Error();
177 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
178 return lbtofnmap.get(lb);
181 private void analyzeLocality(LocalityBinding lb) {
182 MethodDescriptor md=lb.getMethod();
183 FlatMethod fm=state.getMethodFlat(md);
185 //Compute map from flatnode -> (temps -> source of value)
186 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
187 lbtofnmap.put(lb,fnmap);
188 HashSet<TempFlatPair> writeset=null;
190 writeset=new HashSet<TempFlatPair>();
192 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
194 writemap.put(lb, writeset);
197 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
198 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
199 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
200 transreadmap.put(lb, tfset);
201 srcmap.put(lb,srctrans);
202 leftsrcmap.put(lb,leftsrctrans);
203 rightsrcmap.put(lb,rightsrctrans);
205 //compute writes that need translation on source
206 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
207 FlatNode fn=fnit.next();
208 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
209 if (atomictable.get(fn).intValue()>0) {
210 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
213 //We might need to translate arguments to pointer comparison
215 case FKind.FlatOpNode: {
216 FlatOpNode fon=(FlatOpNode)fn;
217 if (fon.getOp().getOp()==Operation.EQUAL||
218 fon.getOp().getOp()==Operation.NOTEQUAL) {
219 if (!fon.getLeft().getType().isPtr())
221 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
222 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
223 //handle left operand
224 if (lefttfpset!=null) {
225 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
226 TempFlatPair tfp=tfpit.next();
227 if (tfset.contains(tfp)||outofscope(tfp)) {
228 leftsrctrans.add(fon);
233 //handle right operand
234 if (righttfpset!=null) {
235 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
236 TempFlatPair tfp=tfpit.next();
237 if (tfset.contains(tfp)||outofscope(tfp)) {
238 rightsrctrans.add(fon);
247 case FKind.FlatGlobalConvNode: {
248 //need to translate these if the value we read from may be a
249 //shadow... check this by seeing if any of the values we
250 //may read are in the transread set or came from our caller
251 //or a method we called
253 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
254 if (fgcn.getLocality()!=lb||
258 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
261 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
262 TempFlatPair tfp=tfpit.next();
263 if (tfset.contains(tfp)||outofscope(tfp)) {
272 case FKind.FlatSetFieldNode: {
273 //need to translate these if the value we read from may be a
274 //shadow... check this by seeing if any of the values we
275 //may read are in the transread set or came from our caller
276 //or a method we called
278 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
279 if (!fsfn.getField().getType().isPtr())
281 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
283 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
284 TempFlatPair tfp=tfpit.next();
285 if (tfset.contains(tfp)||outofscope(tfp)) {
293 case FKind.FlatSetElementNode: {
294 //need to translate these if the value we read from may be a
295 //shadow... check this by seeing if any of the values we
296 //may read are in the transread set or came from our caller
297 //or a method we called
299 FlatSetElementNode fsen=(FlatSetElementNode)fn;
300 if (!fsen.getSrc().getType().isPtr())
302 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
304 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
305 TempFlatPair tfp=tfpit.next();
306 if (tfset.contains(tfp)||outofscope(tfp)) {
320 public boolean outofscope(TempFlatPair tfp) {
322 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
325 private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
326 //inside of transaction, try to convert rw access to ro access
327 MethodDescriptor md=lb.getMethod();
328 FlatMethod fm=state.getMethodFlat(md);
329 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
331 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
332 toanalyze.addAll(fm.getNodeSet());
334 while(!toanalyze.isEmpty()) {
335 FlatNode fn=toanalyze.iterator().next();
336 toanalyze.remove(fn);
337 HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
338 HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
340 //Stop if we aren't in a transaction
341 if (atomictable.get(fn).intValue()==0)
344 //Do merge of all exits
345 for(int i=0;i<fn.numNext();i++) {
346 FlatNode fnnext=fn.getNext(i);
347 if (updatedtypemap.containsKey(fnnext)) {
348 updatetypeset.addAll(updatedtypemap.get(fnnext));
350 if (updatedfieldmap.containsKey(fnnext)) {
351 updatefieldset.addAll(updatedfieldmap.get(fnnext));
356 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
358 case FKind.FlatSetFieldNode: {
359 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
360 updatefieldset.add(fsfn.getField());
363 case FKind.FlatSetElementNode: {
364 FlatSetElementNode fsen=(FlatSetElementNode)fn;
365 updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
368 case FKind.FlatCall: {
369 FlatCall fcall=(FlatCall)fn;
370 MethodDescriptor mdfc=fcall.getMethod();
372 //get modified fields
373 Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
374 updatefieldset.addAll(fields);
376 //get modified arrays
377 Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
378 updatetypeset.addAll(typeanalysis.expandSet(arrays));
384 if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
385 !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
386 updatedtypemap.put(fn, updatetypeset);
387 updatedfieldmap.put(fn, updatefieldset);
388 for(int i=0;i<fn.numPrev();i++) {
389 toanalyze.add(fn.getPrev(i));
396 /** Need to figure out which nodes need a transread to make local
397 copies. Transread conceptually tracks conflicts. This depends on
398 what fields/elements are accessed We iterate over all flatnodes that
399 access fields...If these accesses could conflict, we mark the source
400 tempflat pair as needing a transread */
403 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
404 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
406 //Compute maps from flatnodes -> sets of things that may be updated after this node
407 Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
408 Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
410 if (writeset!=null&&!lb.isAtomic()) {
411 updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
412 updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
413 computeReadOnly(lb, updatedtypemap, updatedfieldmap);
416 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
417 FlatNode fn=fnit.next();
418 //Check whether this node matters for cannot delayed computation
419 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
422 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
423 if (atomictable.get(fn).intValue()>0) {
424 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
426 case FKind.FlatElementNode: {
427 FlatElementNode fen=(FlatElementNode)fn;
428 if (arrays.contains(fen.getSrc().getType())) {
429 //this could cause conflict...figure out conflict set
430 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
432 tfset.addAll(tfpset);
434 if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
435 //this could cause conflict...figure out conflict set
436 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
438 writeset.addAll(tfpset);
442 case FKind.FlatFieldNode: {
443 FlatFieldNode ffn=(FlatFieldNode)fn;
444 if (fields.contains(ffn.getField())) {
445 //this could cause conflict...figure out conflict set
446 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
448 tfset.addAll(tfpset);
450 if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
451 //this could cause conflict...figure out conflict set
452 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
454 writeset.addAll(tfpset);
458 case FKind.FlatSetFieldNode: {
459 //definitely need to translate these
460 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
461 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
463 tfset.addAll(tfpset);
464 if (writeset!=null) {
466 writeset.addAll(tfpset);
470 case FKind.FlatSetElementNode: {
471 //definitely need to translate these
472 FlatSetElementNode fsen=(FlatSetElementNode)fn;
473 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
475 tfset.addAll(tfpset);
476 if (writeset!=null) {
478 writeset.addAll(tfpset);
482 case FKind.FlatCall: //assume pessimistically that calls do bad things
483 case FKind.FlatReturnNode: {
484 TempDescriptor []readarray=fn.readsTemps();
485 for(int i=0;i<readarray.length;i++) {
486 TempDescriptor rtmp=readarray[i];
487 Set<TempFlatPair> tfpset=tmap.get(rtmp);
489 tfset.addAll(tfpset);
490 if (writeset!=null) {
492 writeset.addAll(tfpset);
506 //This method generates as output for each node
507 //A map from from temps to a set of temp/flat pairs that the
508 //original temp points to
509 //A temp/flat pair gives the flatnode that the value was created at
510 //and the original temp
512 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
513 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
514 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
515 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
516 MethodDescriptor md=lb.getMethod();
517 FlatMethod fm=state.getMethodFlat(md);
518 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
519 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
523 while(!tovisit.isEmpty()) {
524 FlatNode fn=tovisit.iterator().next();
526 for(int i=0;i<fn.numNext();i++) {
527 FlatNode fnext=fn.getNext(i);
528 if (!discovered.contains(fnext)) {
529 discovered.add(fnext);
533 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
534 if (atomictable.get(fn).intValue()!=0) {
535 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
536 //atomic node, start with new set
537 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
539 ttofn=doMerge(fn, tmptofnset);
541 case FKind.FlatGlobalConvNode: {
542 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
543 if (lb==fgcn.getLocality()&&
545 TempDescriptor[] writes=fn.writesTemps();
546 for(int i=0;i<writes.length;i++) {
547 TempDescriptor wtmp=writes[i];
548 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
549 set.add(new TempFlatPair(wtmp, fn));
550 ttofn.put(wtmp, set);
555 case FKind.FlatFieldNode:
556 case FKind.FlatElementNode: {
557 TempDescriptor[] writes=fn.writesTemps();
558 for(int i=0;i<writes.length;i++) {
559 TempDescriptor wtmp=writes[i];
560 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
561 set.add(new TempFlatPair(wtmp, fn));
562 ttofn.put(wtmp, set);
567 case FKind.FlatMethod: {
568 TempDescriptor[] writes=fn.writesTemps();
569 for(int i=0;i<writes.length;i++) {
570 TempDescriptor wtmp=writes[i];
571 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
572 set.add(new TempFlatPair(wtmp, fn));
573 ttofn.put(wtmp, set);
577 case FKind.FlatCastNode:
578 case FKind.FlatOpNode:
579 if (fn.kind()==FKind.FlatCastNode) {
580 FlatCastNode fcn=(FlatCastNode)fn;
581 if (fcn.getDst().getType().isPtr()) {
582 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
583 if (ttofn.containsKey(fcn.getSrc()))
584 set.addAll(ttofn.get(fcn.getSrc()));
586 set.add(new TempFlatPair(fcn.getDst(), fn));
587 ttofn.put(fcn.getDst(), set);
590 } else if (fn.kind()==FKind.FlatOpNode) {
591 FlatOpNode fon=(FlatOpNode)fn;
592 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
593 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
594 if (ttofn.containsKey(fon.getLeft()))
595 set.addAll(ttofn.get(fon.getLeft()));
597 set.add(new TempFlatPair(fon.getDest(), fn));
598 ttofn.put(fon.getDest(), set);
603 //Do kill computation
604 TempDescriptor[] writes=fn.writesTemps();
605 for(int i=0;i<writes.length;i++) {
606 TempDescriptor wtmp=writes[i];
607 ttofn.remove(writes[i]);
612 if (!tmptofnset.containsKey(fn)||
613 !tmptofnset.get(fn).equals(ttofn)) {
614 //enqueue nodes to process
615 tmptofnset.put(fn, ttofn);
616 for(int i=0;i<fn.numNext();i++) {
617 FlatNode fnext=fn.getNext(i);
627 /* See what fields and arrays transactions might modify. We only
628 * look at changes to old objects. */
630 //Bug fix: original version forget to check if object is new and
633 public void computeModified(LocalityBinding lb) {
634 MethodDescriptor md=lb.getMethod();
635 FlatMethod fm=state.getMethodFlat(md);
636 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
637 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
638 FlatNode fn=fnit.next();
639 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
640 if (atomictable.get(fn).intValue()>0) {
641 Set<TempDescriptor> oldtemp=oldtemps.get(fn);
643 case FKind.FlatSetFieldNode:
644 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
645 if (oldtemp.contains(fsfn.getDst()))
646 fields.add(fsfn.getField());
648 case FKind.FlatSetElementNode:
649 FlatSetElementNode fsen=(FlatSetElementNode) fn;
650 if (oldtemp.contains(fsen.getDst()))
651 arrays.add(fsen.getDst().getType());
660 //Returns a table that maps a flatnode to a set of temporaries
661 //This set of temporaries is old (meaning they may point to object
662 //allocated before the beginning of the current transaction
664 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
665 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
666 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
667 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
668 MethodDescriptor md=lb.getMethod();
669 FlatMethod fm=state.getMethodFlat(md);
670 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
671 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
675 while(!tovisit.isEmpty()) {
676 FlatNode fn=tovisit.iterator().next();
678 for(int i=0;i<fn.numNext();i++) {
679 FlatNode fnext=fn.getNext(i);
680 if (!discovered.contains(fnext)) {
681 discovered.add(fnext);
685 HashSet<TempDescriptor> oldtemps=null;
686 if (atomictable.get(fn).intValue()!=0) {
687 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
688 //Everything live is old
689 Set<TempDescriptor> lives=livetemps.get(fn);
690 oldtemps=new HashSet<TempDescriptor>();
692 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
693 TempDescriptor tmp=it.next();
694 if (tmp.getType().isPtr()) {
699 oldtemps=new HashSet<TempDescriptor>();
700 //Compute union of old temporaries
701 for(int i=0;i<fn.numPrev();i++) {
702 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
704 oldtemps.addAll(pset);
709 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
711 case FKind.FlatOpNode:
712 case FKind.FlatCastNode:
713 if (fn.kind()==FKind.FlatCastNode) {
714 FlatCastNode fcn=(FlatCastNode)fn;
715 if (fcn.getDst().getType().isPtr()) {
716 if (oldtemps.contains(fcn.getSrc()))
717 oldtemps.add(fcn.getDst());
719 oldtemps.remove(fcn.getDst());
722 } else if (fn.kind()==FKind.FlatOpNode) {
723 FlatOpNode fon=(FlatOpNode)fn;
724 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
725 if (oldtemps.contains(fon.getLeft()))
726 oldtemps.add(fon.getDest());
728 oldtemps.remove(fon.getDest());
733 TempDescriptor[] writes=fn.writesTemps();
734 for(int i=0;i<writes.length;i++) {
735 TempDescriptor wtemp=writes[i];
736 if (wtemp.getType().isPtr())
744 if (oldtemps!=null) {
745 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
746 fntooldtmp.put(fn, oldtemps);
748 for(int i=0;i<fn.numNext();i++) {
749 FlatNode fnext=fn.getNext(i);
762 TempFlatPair(TempDescriptor t, FlatNode f) {
767 public int hashCode() {
768 return f.hashCode()^t.hashCode();
770 public boolean equals(Object o) {
771 TempFlatPair tf=(TempFlatPair)o;
772 return t.equals(tf.t)&&f.equals(tf.f);