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) {
172 return twritemap.get(lb).contains(fn);
175 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
176 return lbtofnmap.get(lb);
179 private void analyzeLocality(LocalityBinding lb) {
180 MethodDescriptor md=lb.getMethod();
181 FlatMethod fm=state.getMethodFlat(md);
183 //Compute map from flatnode -> (temps -> source of value)
184 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
185 lbtofnmap.put(lb,fnmap);
186 HashSet<TempFlatPair> writeset=null;
188 writeset=new HashSet<TempFlatPair>();
190 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
192 writemap.put(lb, writeset);
195 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
196 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
197 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
198 transreadmap.put(lb, tfset);
199 srcmap.put(lb,srctrans);
200 leftsrcmap.put(lb,leftsrctrans);
201 rightsrcmap.put(lb,rightsrctrans);
203 //compute writes that need translation on source
204 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
205 FlatNode fn=fnit.next();
206 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
207 if (atomictable.get(fn).intValue()>0) {
208 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
211 //We might need to translate arguments to pointer comparison
213 case FKind.FlatOpNode: {
214 FlatOpNode fon=(FlatOpNode)fn;
215 if (fon.getOp().getOp()==Operation.EQUAL||
216 fon.getOp().getOp()==Operation.NOTEQUAL) {
217 if (!fon.getLeft().getType().isPtr())
219 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
220 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
221 //handle left operand
222 if (lefttfpset!=null) {
223 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator();tfpit.hasNext();) {
224 TempFlatPair tfp=tfpit.next();
225 if (tfset.contains(tfp)||outofscope(tfp)) {
226 leftsrctrans.add(fon);
231 //handle right operand
232 if (righttfpset!=null) {
233 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator();tfpit.hasNext();) {
234 TempFlatPair tfp=tfpit.next();
235 if (tfset.contains(tfp)||outofscope(tfp)) {
236 rightsrctrans.add(fon);
245 case FKind.FlatGlobalConvNode: {
246 //need to translate these if the value we read from may be a
247 //shadow... check this by seeing if any of the values we
248 //may read are in the transread set or came from our caller
249 //or a method we called
251 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
252 if (fgcn.getLocality()!=lb||
256 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
259 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
260 TempFlatPair tfp=tfpit.next();
261 if (tfset.contains(tfp)||outofscope(tfp)) {
270 case FKind.FlatSetFieldNode: {
271 //need to translate these if the value we read from may be a
272 //shadow... check this by seeing if any of the values we
273 //may read are in the transread set or came from our caller
274 //or a method we called
276 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
277 if (!fsfn.getField().getType().isPtr())
279 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
281 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
282 TempFlatPair tfp=tfpit.next();
283 if (tfset.contains(tfp)||outofscope(tfp)) {
291 case FKind.FlatSetElementNode: {
292 //need to translate these if the value we read from may be a
293 //shadow... check this by seeing if any of the values we
294 //may read are in the transread set or came from our caller
295 //or a method we called
297 FlatSetElementNode fsen=(FlatSetElementNode)fn;
298 if (!fsen.getSrc().getType().isPtr())
300 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
302 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
303 TempFlatPair tfp=tfpit.next();
304 if (tfset.contains(tfp)||outofscope(tfp)) {
318 public boolean outofscope(TempFlatPair tfp) {
320 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
323 private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
324 //inside of transaction, try to convert rw access to ro access
325 MethodDescriptor md=lb.getMethod();
326 FlatMethod fm=state.getMethodFlat(md);
327 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
329 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
330 toanalyze.addAll(fm.getNodeSet());
332 while(!toanalyze.isEmpty()) {
333 FlatNode fn=toanalyze.iterator().next();
334 toanalyze.remove(fn);
335 HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
336 HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
338 //Stop if we aren't in a transaction
339 if (atomictable.get(fn).intValue()==0)
342 //Do merge of all exits
343 for(int i=0;i<fn.numNext();i++) {
344 FlatNode fnnext=fn.getNext(i);
345 if (updatedtypemap.containsKey(fnnext)) {
346 updatetypeset.addAll(updatedtypemap.get(fnnext));
348 if (updatedfieldmap.containsKey(fnnext)) {
349 updatefieldset.addAll(updatedfieldmap.get(fnnext));
354 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
356 case FKind.FlatSetFieldNode: {
357 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
358 updatefieldset.add(fsfn.getField());
361 case FKind.FlatSetElementNode: {
362 FlatSetElementNode fsen=(FlatSetElementNode)fn;
363 updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
366 case FKind.FlatCall: {
367 FlatCall fcall=(FlatCall)fn;
368 MethodDescriptor mdfc=fcall.getMethod();
370 //get modified fields
371 Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
372 updatefieldset.addAll(fields);
374 //get modified arrays
375 Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
376 updatetypeset.addAll(typeanalysis.expandSet(arrays));
382 if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
383 !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
384 updatedtypemap.put(fn, updatetypeset);
385 updatedfieldmap.put(fn, updatefieldset);
386 for(int i=0;i<fn.numPrev();i++) {
387 toanalyze.add(fn.getPrev(i));
394 /** Need to figure out which nodes need a transread to make local
395 copies. Transread conceptually tracks conflicts. This depends on
396 what fields/elements are accessed We iterate over all flatnodes that
397 access fields...If these accesses could conflict, we mark the source
398 tempflat pair as needing a transread */
401 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
402 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
404 //Compute maps from flatnodes -> sets of things that may be updated after this node
405 Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
406 Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
408 if (writeset!=null&&!lb.isAtomic()) {
409 updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
410 updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
411 computeReadOnly(lb, updatedtypemap, updatedfieldmap);
414 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
415 FlatNode fn=fnit.next();
416 //Check whether this node matters for cannot delayed computation
417 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
420 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
421 if (atomictable.get(fn).intValue()>0) {
422 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
424 case FKind.FlatElementNode: {
425 FlatElementNode fen=(FlatElementNode)fn;
426 if (arrays.contains(fen.getSrc().getType())) {
427 //this could cause conflict...figure out conflict set
428 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
430 tfset.addAll(tfpset);
432 if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
433 //this could cause conflict...figure out conflict set
434 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
436 writeset.addAll(tfpset);
440 case FKind.FlatFieldNode: {
441 FlatFieldNode ffn=(FlatFieldNode)fn;
442 if (fields.contains(ffn.getField())) {
443 //this could cause conflict...figure out conflict set
444 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
446 tfset.addAll(tfpset);
448 if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
449 //this could cause conflict...figure out conflict set
450 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
452 writeset.addAll(tfpset);
456 case FKind.FlatSetFieldNode: {
457 //definitely need to translate these
458 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
459 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
461 tfset.addAll(tfpset);
462 if (writeset!=null) {
464 writeset.addAll(tfpset);
468 case FKind.FlatSetElementNode: {
469 //definitely need to translate these
470 FlatSetElementNode fsen=(FlatSetElementNode)fn;
471 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
473 tfset.addAll(tfpset);
474 if (writeset!=null) {
476 writeset.addAll(tfpset);
480 case FKind.FlatCall: //assume pessimistically that calls do bad things
481 case FKind.FlatReturnNode: {
482 TempDescriptor []readarray=fn.readsTemps();
483 for(int i=0;i<readarray.length;i++) {
484 TempDescriptor rtmp=readarray[i];
485 Set<TempFlatPair> tfpset=tmap.get(rtmp);
487 tfset.addAll(tfpset);
488 if (writeset!=null) {
490 writeset.addAll(tfpset);
504 //This method generates as output for each node
505 //A map from from temps to a set of temp/flat pairs that the
506 //original temp points to
507 //A temp/flat pair gives the flatnode that the value was created at
508 //and the original temp
510 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
511 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
512 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
513 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
514 MethodDescriptor md=lb.getMethod();
515 FlatMethod fm=state.getMethodFlat(md);
516 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
517 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
521 while(!tovisit.isEmpty()) {
522 FlatNode fn=tovisit.iterator().next();
524 for(int i=0;i<fn.numNext();i++) {
525 FlatNode fnext=fn.getNext(i);
526 if (!discovered.contains(fnext)) {
527 discovered.add(fnext);
531 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
532 if (atomictable.get(fn).intValue()!=0) {
533 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
534 //atomic node, start with new set
535 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
537 ttofn=doMerge(fn, tmptofnset);
539 case FKind.FlatGlobalConvNode: {
540 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
541 if (lb==fgcn.getLocality()&&
543 TempDescriptor[] writes=fn.writesTemps();
544 for(int i=0;i<writes.length;i++) {
545 TempDescriptor wtmp=writes[i];
546 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
547 set.add(new TempFlatPair(wtmp, fn));
548 ttofn.put(wtmp, set);
553 case FKind.FlatFieldNode:
554 case FKind.FlatElementNode: {
555 TempDescriptor[] writes=fn.writesTemps();
556 for(int i=0;i<writes.length;i++) {
557 TempDescriptor wtmp=writes[i];
558 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
559 set.add(new TempFlatPair(wtmp, fn));
560 ttofn.put(wtmp, set);
565 case FKind.FlatMethod: {
566 TempDescriptor[] writes=fn.writesTemps();
567 for(int i=0;i<writes.length;i++) {
568 TempDescriptor wtmp=writes[i];
569 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
570 set.add(new TempFlatPair(wtmp, fn));
571 ttofn.put(wtmp, set);
575 case FKind.FlatOpNode: {
576 FlatOpNode fon=(FlatOpNode)fn;
577 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
578 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
579 if (ttofn.containsKey(fon.getLeft()))
580 set.addAll(ttofn.get(fon.getLeft()));
582 set.add(new TempFlatPair(fon.getDest(), fn));
583 ttofn.put(fon.getDest(), set);
588 //Do kill computation
589 TempDescriptor[] writes=fn.writesTemps();
590 for(int i=0;i<writes.length;i++) {
591 TempDescriptor wtmp=writes[i];
592 ttofn.remove(writes[i]);
597 if (!tmptofnset.containsKey(fn)||
598 !tmptofnset.get(fn).equals(ttofn)) {
599 //enqueue nodes to process
600 tmptofnset.put(fn, ttofn);
601 for(int i=0;i<fn.numNext();i++) {
602 FlatNode fnext=fn.getNext(i);
612 /* See what fields and arrays transactions might modify. We only
613 * look at changes to old objects. */
615 public void computeModified(LocalityBinding lb) {
616 MethodDescriptor md=lb.getMethod();
617 FlatMethod fm=state.getMethodFlat(md);
618 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
619 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
620 FlatNode fn=fnit.next();
621 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
622 if (atomictable.get(fn).intValue()>0) {
624 case FKind.FlatSetFieldNode:
625 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
626 fields.add(fsfn.getField());
628 case FKind.FlatSetElementNode:
629 FlatSetElementNode fsen=(FlatSetElementNode) fn;
630 arrays.add(fsen.getDst().getType());
639 //Returns a table that maps a flatnode to a set of temporaries
640 //This set of temporaries is old (meaning they may point to object
641 //allocated before the beginning of the current transaction
643 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
644 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
645 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
646 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
647 MethodDescriptor md=lb.getMethod();
648 FlatMethod fm=state.getMethodFlat(md);
649 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
650 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
654 while(!tovisit.isEmpty()) {
655 FlatNode fn=tovisit.iterator().next();
657 for(int i=0;i<fn.numNext();i++) {
658 FlatNode fnext=fn.getNext(i);
659 if (!discovered.contains(fnext)) {
660 discovered.add(fnext);
664 HashSet<TempDescriptor> oldtemps=null;
665 if (atomictable.get(fn).intValue()!=0) {
666 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
667 //Everything live is old
668 Set<TempDescriptor> lives=livetemps.get(fn);
669 oldtemps=new HashSet<TempDescriptor>();
671 for(Iterator<TempDescriptor> it=lives.iterator();it.hasNext();) {
672 TempDescriptor tmp=it.next();
673 if (tmp.getType().isPtr()) {
678 oldtemps=new HashSet<TempDescriptor>();
679 //Compute union of old temporaries
680 for(int i=0;i<fn.numPrev();i++) {
681 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
683 oldtemps.addAll(pset);
688 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
690 case FKind.FlatOpNode: {
691 FlatOpNode fon=(FlatOpNode)fn;
692 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
693 if (oldtemps.contains(fon.getLeft()))
694 oldtemps.add(fon.getDest());
696 oldtemps.remove(fon.getDest());
701 TempDescriptor[] writes=fn.writesTemps();
702 for(int i=0;i<writes.length;i++) {
703 TempDescriptor wtemp=writes[i];
704 if (wtemp.getType().isPtr())
712 if (oldtemps!=null) {
713 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
714 fntooldtmp.put(fn, oldtemps);
716 for(int i=0;i<fn.numNext();i++) {
717 FlatNode fnext=fn.getNext(i);
730 TempFlatPair(TempDescriptor t, FlatNode f) {
735 public int hashCode() {
736 return f.hashCode()^t.hashCode();
738 public boolean equals(Object o) {
739 TempFlatPair tf=(TempFlatPair)o;
740 return t.equals(tf.t)&&f.equals(tf.f);