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 if (state.READSET&&gft!=null) {
128 if (twritemap.get(lb).size()==0) {
129 getmap.put(lb, new HashSet<FlatNode>());
134 Set<FlatNode> gwriteset=treadmap.get(lb);
135 FlatMethod fm=state.getMethodFlat(lb.getMethod());
136 HashSet<FlatNode> needsget=new HashSet<FlatNode>();
137 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext(); ) {
138 FlatNode fn=fnit.next();
139 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
140 if (atomictable.get(fn).intValue()>0&&fn.kind()==FKind.FlatElementNode) {
141 FlatElementNode fen=(FlatElementNode)fn;
142 Set<TempFlatPair> tfpset=fnmap.get(fen).get(fen.getSrc());
144 for(Iterator<TempFlatPair> tfpit=tfpset.iterator(); tfpit.hasNext(); ) {
145 TempFlatPair tfp=tfpit.next();
146 if (gwriteset.contains(tfp.f)) {
154 getmap.put(lb, needsget);
157 //We have a set of things we write to, figure out what things this
159 public void expandTypes() {
160 Set<TypeDescriptor> expandedarrays=new HashSet<TypeDescriptor>();
161 for(Iterator<TypeDescriptor> it=arrays.iterator(); it.hasNext(); ) {
162 TypeDescriptor td=it.next();
163 expandedarrays.addAll(typeanalysis.expand(td));
165 arrays=expandedarrays;
168 Hashtable<TempDescriptor, Set<TempFlatPair>> doMerge(FlatNode fn, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset) {
169 Hashtable<TempDescriptor, Set<TempFlatPair>> table=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
170 for(int i=0; i<fn.numPrev(); i++) {
171 FlatNode fprev=fn.getPrev(i);
172 Hashtable<TempDescriptor, Set<TempFlatPair>> tabset=tmptofnset.get(fprev);
174 for(Iterator<TempDescriptor> tmpit=tabset.keySet().iterator(); tmpit.hasNext(); ) {
175 TempDescriptor td=tmpit.next();
176 Set<TempFlatPair> fnset=tabset.get(td);
177 if (!table.containsKey(td))
178 table.put(td, new HashSet<TempFlatPair>());
179 table.get(td).addAll(fnset);
186 public Set<FlatNode> getNeedSrcTrans(LocalityBinding lb) {
187 return srcmap.get(lb);
190 public boolean getNeedSrcTrans(LocalityBinding lb, FlatNode fn) {
191 return srcmap.get(lb).contains(fn);
194 public boolean getNeedLeftSrcTrans(LocalityBinding lb, FlatNode fn) {
195 return leftsrcmap.get(lb).contains(fn);
198 public boolean getNeedRightSrcTrans(LocalityBinding lb, FlatNode fn) {
199 return rightsrcmap.get(lb).contains(fn);
202 public boolean getNeedTrans(LocalityBinding lb, FlatNode fn) {
203 return treadmap.get(lb).contains(fn);
206 public boolean getNeedGet(LocalityBinding lb, FlatNode fn) {
208 return getmap.get(lb).contains(fn);
209 else throw new Error();
212 public boolean getNeedWriteTrans(LocalityBinding lb, FlatNode fn) {
214 return twritemap.get(lb).contains(fn);
215 else throw new Error();
218 public Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> getMap(LocalityBinding lb) {
219 return lbtofnmap.get(lb);
222 private void analyzeLocality(LocalityBinding lb) {
223 MethodDescriptor md=lb.getMethod();
224 FlatMethod fm=state.getMethodFlat(md);
226 //Compute map from flatnode -> (temps -> source of value)
227 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=computeTempSets(lb);
228 lbtofnmap.put(lb,fnmap);
229 HashSet<TempFlatPair> writeset=null;
231 writeset=new HashSet<TempFlatPair>();
233 HashSet<TempFlatPair> tfset=computeTranslationSet(lb, fm, fnmap, writeset);
235 writemap.put(lb, writeset);
238 HashSet<FlatNode> srctrans=new HashSet<FlatNode>();
239 HashSet<FlatNode> leftsrctrans=new HashSet<FlatNode>();
240 HashSet<FlatNode> rightsrctrans=new HashSet<FlatNode>();
241 transreadmap.put(lb, tfset);
242 srcmap.put(lb,srctrans);
243 leftsrcmap.put(lb,leftsrctrans);
244 rightsrcmap.put(lb,rightsrctrans);
246 //compute writes that need translation on source
247 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext(); ) {
248 FlatNode fn=fnit.next();
249 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
250 if (atomictable.get(fn).intValue()>0) {
251 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
253 //We might need to translate arguments to pointer comparison
255 case FKind.FlatOpNode: {
256 FlatOpNode fon=(FlatOpNode)fn;
257 if (fon.getOp().getOp()==Operation.EQUAL||
258 fon.getOp().getOp()==Operation.NOTEQUAL) {
259 if (!fon.getLeft().getType().isPtr())
261 Set<TempFlatPair> lefttfpset=tmap.get(fon.getLeft());
262 Set<TempFlatPair> righttfpset=tmap.get(fon.getRight());
263 //handle left operand
264 if (lefttfpset!=null) {
265 for(Iterator<TempFlatPair> tfpit=lefttfpset.iterator(); tfpit.hasNext(); ) {
266 TempFlatPair tfp=tfpit.next();
267 if (tfset.contains(tfp)||outofscope(tfp)) {
268 leftsrctrans.add(fon);
273 //handle right operand
274 if (righttfpset!=null) {
275 for(Iterator<TempFlatPair> tfpit=righttfpset.iterator(); tfpit.hasNext(); ) {
276 TempFlatPair tfp=tfpit.next();
277 if (tfset.contains(tfp)||outofscope(tfp)) {
278 rightsrctrans.add(fon);
287 case FKind.FlatGlobalConvNode: {
288 //need to translate these if the value we read from may be a
289 //shadow... check this by seeing if any of the values we
290 //may read are in the transread set or came from our caller
291 //or a method we called
293 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
294 if (fgcn.getLocality()!=lb||
298 Set<TempFlatPair> tfpset=tmap.get(fgcn.getSrc());
301 for(Iterator<TempFlatPair> tfpit=tfpset.iterator(); tfpit.hasNext(); ) {
302 TempFlatPair tfp=tfpit.next();
303 if (tfset.contains(tfp)||outofscope(tfp)) {
312 case FKind.FlatSetFieldNode: {
313 //need to translate these if the value we read from may be a
314 //shadow... check this by seeing if any of the values we
315 //may read are in the transread set or came from our caller
316 //or a method we called
318 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
319 if (!fsfn.getField().getType().isPtr())
321 Set<TempFlatPair> tfpset=tmap.get(fsfn.getSrc());
323 for(Iterator<TempFlatPair> tfpit=tfpset.iterator(); tfpit.hasNext(); ) {
324 TempFlatPair tfp=tfpit.next();
325 if (tfset.contains(tfp)||outofscope(tfp)) {
334 case FKind.FlatSetElementNode: {
335 //need to translate these if the value we read from may be a
336 //shadow... check this by seeing if any of the values we
337 //may read are in the transread set or came from our caller
338 //or a method we called
340 FlatSetElementNode fsen=(FlatSetElementNode)fn;
341 if (!fsen.getSrc().getType().isPtr())
343 Set<TempFlatPair> tfpset=tmap.get(fsen.getSrc());
345 for(Iterator<TempFlatPair> tfpit=tfpset.iterator(); tfpit.hasNext(); ) {
346 TempFlatPair tfp=tfpit.next();
347 if (tfset.contains(tfp)||outofscope(tfp)) {
361 setNeedReadTrans(lb);
362 computeneedsarrayget(lb, fnmap);
365 public boolean outofscope(TempFlatPair tfp) {
367 return fn.kind()==FKind.FlatCall||fn.kind()==FKind.FlatMethod;
370 private void computeReadOnly(LocalityBinding lb, Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap, Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap) {
371 //inside of transaction, try to convert rw access to ro access
372 MethodDescriptor md=lb.getMethod();
373 FlatMethod fm=state.getMethodFlat(md);
374 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
376 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
377 toanalyze.addAll(fm.getNodeSet());
379 while(!toanalyze.isEmpty()) {
380 FlatNode fn=toanalyze.iterator().next();
381 toanalyze.remove(fn);
382 HashSet<TypeDescriptor> updatetypeset=new HashSet<TypeDescriptor>();
383 HashSet<FieldDescriptor> updatefieldset=new HashSet<FieldDescriptor>();
385 //Stop if we aren't in a transaction
386 if (atomictable.get(fn).intValue()==0)
389 //Do merge of all exits
390 for(int i=0; i<fn.numNext(); i++) {
391 FlatNode fnnext=fn.getNext(i);
392 if (updatedtypemap.containsKey(fnnext)) {
393 updatetypeset.addAll(updatedtypemap.get(fnnext));
395 if (updatedfieldmap.containsKey(fnnext)) {
396 updatefieldset.addAll(updatedfieldmap.get(fnnext));
401 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)!=inclusive) {
403 case FKind.FlatSetFieldNode: {
404 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
405 updatefieldset.add(fsfn.getField());
409 case FKind.FlatSetElementNode: {
410 FlatSetElementNode fsen=(FlatSetElementNode)fn;
411 updatetypeset.addAll(typeanalysis.expand(fsen.getDst().getType()));
415 case FKind.FlatCall: {
416 FlatCall fcall=(FlatCall)fn;
417 MethodDescriptor mdfc=fcall.getMethod();
419 //get modified fields
420 Set<FieldDescriptor> fields=gft.getFieldsAll(mdfc);
421 updatefieldset.addAll(fields);
423 //get modified arrays
424 Set<TypeDescriptor> arrays=gft.getArraysAll(mdfc);
425 updatetypeset.addAll(typeanalysis.expandSet(arrays));
431 if (!updatedtypemap.containsKey(fn)||!updatedfieldmap.containsKey(fn)||
432 !updatedtypemap.get(fn).equals(updatetypeset)||!updatedfieldmap.get(fn).equals(updatefieldset)) {
433 updatedtypemap.put(fn, updatetypeset);
434 updatedfieldmap.put(fn, updatefieldset);
435 for(int i=0; i<fn.numPrev(); i++) {
436 toanalyze.add(fn.getPrev(i));
443 /** Need to figure out which nodes need a transread to make local
444 copies. Transread conceptually tracks conflicts. This depends on
445 what fields/elements are accessed We iterate over all flatnodes that
446 access fields...If these accesses could conflict, we mark the source
447 tempflat pair as needing a transread */
450 HashSet<TempFlatPair> computeTranslationSet(LocalityBinding lb, FlatMethod fm, Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap, Set<TempFlatPair> writeset) {
451 HashSet<TempFlatPair> tfset=new HashSet<TempFlatPair>();
453 //Compute maps from flatnodes -> sets of things that may be updated after this node
454 Hashtable<FlatNode, Set<TypeDescriptor>> updatedtypemap=null;
455 Hashtable<FlatNode, Set<FieldDescriptor>> updatedfieldmap=null;
457 if (writeset!=null&&!lb.isAtomic()) {
458 updatedtypemap=new Hashtable<FlatNode, Set<TypeDescriptor>>();
459 updatedfieldmap=new Hashtable<FlatNode, Set<FieldDescriptor>>();
460 computeReadOnly(lb, updatedtypemap, updatedfieldmap);
463 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext(); ) {
464 FlatNode fn=fnit.next();
465 //Check whether this node matters for cannot delayed computation
466 if (cannotdelaymap!=null&&cannotdelaymap.containsKey(lb)&&cannotdelaymap.get(lb).contains(fn)==inclusive)
469 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
470 if (atomictable.get(fn).intValue()>0) {
471 Hashtable<TempDescriptor, Set<TempFlatPair>> tmap=fnmap.get(fn);
473 case FKind.FlatElementNode: {
474 FlatElementNode fen=(FlatElementNode)fn;
475 if (arrays.contains(fen.getSrc().getType())) {
476 //this could cause conflict...figure out conflict set
477 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
479 tfset.addAll(tfpset);
481 if (updatedtypemap!=null&&updatedtypemap.get(fen).contains(fen.getSrc().getType())) {
482 //this could cause conflict...figure out conflict set
483 Set<TempFlatPair> tfpset=tmap.get(fen.getSrc());
485 tfset.addAll(tfpset);
490 case FKind.FlatFieldNode: {
491 FlatFieldNode ffn=(FlatFieldNode)fn;
492 if (fields.contains(ffn.getField())) {
493 //this could cause conflict...figure out conflict set
494 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
496 tfset.addAll(tfpset);
498 if (updatedfieldmap!=null&&updatedfieldmap.get(ffn).contains(ffn.getField())) {
499 //this could cause conflict...figure out conflict set
500 Set<TempFlatPair> tfpset=tmap.get(ffn.getSrc());
502 tfset.addAll(tfpset);
507 case FKind.FlatSetFieldNode: {
508 //definitely need to translate these
509 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
510 Set<TempFlatPair> tfpset=tmap.get(fsfn.getDst());
512 tfset.addAll(tfpset);
513 if (writeset!=null) {
515 writeset.addAll(tfpset);
520 case FKind.FlatSetElementNode: {
521 //definitely need to translate these
522 FlatSetElementNode fsen=(FlatSetElementNode)fn;
523 Set<TempFlatPair> tfpset=tmap.get(fsen.getDst());
525 tfset.addAll(tfpset);
526 if (writeset!=null) {
528 writeset.addAll(tfpset);
533 case FKind.FlatCall: //assume pessimistically that calls do bad things
534 case FKind.FlatReturnNode: {
535 TempDescriptor [] readarray=fn.readsTemps();
536 for(int i=0; i<readarray.length; i++) {
537 TempDescriptor rtmp=readarray[i];
538 Set<TempFlatPair> tfpset=tmap.get(rtmp);
540 tfset.addAll(tfpset);
541 if (writeset!=null) {
543 writeset.addAll(tfpset);
558 //This method generates as output for each node
559 //A map from from temps to a set of temp/flat pairs that the
560 //original temp points to
561 //A temp/flat pair gives the flatnode that the value was created at
562 //and the original temp
564 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> computeTempSets(LocalityBinding lb) {
565 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> tmptofnset=new Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>>();
566 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
567 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
568 MethodDescriptor md=lb.getMethod();
569 FlatMethod fm=state.getMethodFlat(md);
570 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
571 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
575 while(!tovisit.isEmpty()) {
576 FlatNode fn=tovisit.iterator().next();
578 for(int i=0; i<fn.numNext(); i++) {
579 FlatNode fnext=fn.getNext(i);
580 if (!discovered.contains(fnext)) {
581 discovered.add(fnext);
585 Hashtable<TempDescriptor, Set<TempFlatPair>> ttofn=null;
586 if (atomictable.get(fn).intValue()!=0) {
587 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
588 //atomic node, start with new set
589 ttofn=new Hashtable<TempDescriptor, Set<TempFlatPair>>();
591 ttofn=doMerge(fn, tmptofnset);
593 case FKind.FlatGlobalConvNode: {
594 FlatGlobalConvNode fgcn=(FlatGlobalConvNode)fn;
595 if (lb==fgcn.getLocality()&&
597 TempDescriptor[] writes=fn.writesTemps();
598 for(int i=0; i<writes.length; i++) {
599 TempDescriptor wtmp=writes[i];
600 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
601 set.add(new TempFlatPair(wtmp, fn));
602 ttofn.put(wtmp, set);
608 case FKind.FlatFieldNode:
609 case FKind.FlatElementNode: {
610 TempDescriptor[] writes=fn.writesTemps();
611 for(int i=0; i<writes.length; i++) {
612 TempDescriptor wtmp=writes[i];
613 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
614 set.add(new TempFlatPair(wtmp, fn));
615 ttofn.put(wtmp, set);
621 case FKind.FlatMethod: {
622 TempDescriptor[] writes=fn.writesTemps();
623 for(int i=0; i<writes.length; i++) {
624 TempDescriptor wtmp=writes[i];
625 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
626 set.add(new TempFlatPair(wtmp, fn));
627 ttofn.put(wtmp, set);
632 case FKind.FlatCastNode:
633 case FKind.FlatOpNode:
634 if (fn.kind()==FKind.FlatCastNode) {
635 FlatCastNode fcn=(FlatCastNode)fn;
636 if (fcn.getDst().getType().isPtr()) {
637 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
638 if (ttofn.containsKey(fcn.getSrc()))
639 set.addAll(ttofn.get(fcn.getSrc()));
641 set.add(new TempFlatPair(fcn.getDst(), fn));
642 ttofn.put(fcn.getDst(), set);
645 } else if (fn.kind()==FKind.FlatOpNode) {
646 FlatOpNode fon=(FlatOpNode)fn;
647 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
648 HashSet<TempFlatPair> set=new HashSet<TempFlatPair>();
649 if (ttofn.containsKey(fon.getLeft()))
650 set.addAll(ttofn.get(fon.getLeft()));
652 set.add(new TempFlatPair(fon.getDest(), fn));
653 ttofn.put(fon.getDest(), set);
659 //Do kill computation
660 TempDescriptor[] writes=fn.writesTemps();
661 for(int i=0; i<writes.length; i++) {
662 TempDescriptor wtmp=writes[i];
663 ttofn.remove(writes[i]);
668 if (!tmptofnset.containsKey(fn)||
669 !tmptofnset.get(fn).equals(ttofn)) {
670 //enqueue nodes to process
671 tmptofnset.put(fn, ttofn);
672 for(int i=0; i<fn.numNext(); i++) {
673 FlatNode fnext=fn.getNext(i);
683 /* See what fields and arrays transactions might modify. We only
684 * look at changes to old objects. */
686 //Bug fix: original version forget to check if object is new and
689 public void computeModified(LocalityBinding lb) {
690 MethodDescriptor md=lb.getMethod();
691 FlatMethod fm=state.getMethodFlat(md);
692 Hashtable<FlatNode, Set<TempDescriptor>> oldtemps=computeOldTemps(lb);
693 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator(); fnit.hasNext(); ) {
694 FlatNode fn=fnit.next();
695 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
696 if (atomictable.get(fn).intValue()>0) {
697 Set<TempDescriptor> oldtemp=oldtemps.get(fn);
699 case FKind.FlatSetFieldNode:
700 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
701 if (oldtemp.contains(fsfn.getDst()))
702 fields.add(fsfn.getField());
705 case FKind.FlatSetElementNode:
706 FlatSetElementNode fsen=(FlatSetElementNode) fn;
707 if (oldtemp.contains(fsen.getDst()))
708 arrays.add(fsen.getDst().getType());
718 //Returns a table that maps a flatnode to a set of temporaries
719 //This set of temporaries is old (meaning they may point to object
720 //allocated before the beginning of the current transaction
722 Hashtable<FlatNode, Set<TempDescriptor>> computeOldTemps(LocalityBinding lb) {
723 Hashtable<FlatNode, Set<TempDescriptor>> fntooldtmp=new Hashtable<FlatNode, Set<TempDescriptor>>();
724 HashSet<FlatNode> discovered=new HashSet<FlatNode>();
725 HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
726 MethodDescriptor md=lb.getMethod();
727 FlatMethod fm=state.getMethodFlat(md);
728 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
729 Hashtable<FlatNode, Set<TempDescriptor>> livetemps=Liveness.computeLiveTemps(fm);
733 while(!tovisit.isEmpty()) {
734 FlatNode fn=tovisit.iterator().next();
736 for(int i=0; i<fn.numNext(); i++) {
737 FlatNode fnext=fn.getNext(i);
738 if (!discovered.contains(fnext)) {
739 discovered.add(fnext);
743 HashSet<TempDescriptor> oldtemps=null;
744 if (atomictable.get(fn).intValue()!=0) {
745 if ((fn.numPrev()>0)&&atomictable.get(fn.getPrev(0)).intValue()==0) {
746 //Everything live is old
747 Set<TempDescriptor> lives=livetemps.get(fn);
748 oldtemps=new HashSet<TempDescriptor>();
750 for(Iterator<TempDescriptor> it=lives.iterator(); it.hasNext(); ) {
751 TempDescriptor tmp=it.next();
752 if (tmp.getType().isPtr()) {
757 oldtemps=new HashSet<TempDescriptor>();
758 //Compute union of old temporaries
759 for(int i=0; i<fn.numPrev(); i++) {
760 Set<TempDescriptor> pset=fntooldtmp.get(fn.getPrev(i));
762 oldtemps.addAll(pset);
767 oldtemps.removeAll(Arrays.asList(fn.readsTemps()));
770 case FKind.FlatOpNode:
771 case FKind.FlatCastNode:
772 if (fn.kind()==FKind.FlatCastNode) {
773 FlatCastNode fcn=(FlatCastNode)fn;
774 if (fcn.getDst().getType().isPtr()) {
775 if (oldtemps.contains(fcn.getSrc()))
776 oldtemps.add(fcn.getDst());
778 oldtemps.remove(fcn.getDst());
781 } else if (fn.kind()==FKind.FlatOpNode) {
782 FlatOpNode fon=(FlatOpNode)fn;
783 if (fon.getOp().getOp()==Operation.ASSIGN&&fon.getDest().getType().isPtr()) {
784 if (oldtemps.contains(fon.getLeft()))
785 oldtemps.add(fon.getDest());
787 oldtemps.remove(fon.getDest());
793 TempDescriptor[] writes=fn.writesTemps();
794 for(int i=0; i<writes.length; i++) {
795 TempDescriptor wtemp=writes[i];
796 if (wtemp.getType().isPtr())
804 if (oldtemps!=null) {
805 if (!fntooldtmp.containsKey(fn)||!fntooldtmp.get(fn).equals(oldtemps)) {
806 fntooldtmp.put(fn, oldtemps);
808 for(int i=0; i<fn.numNext(); i++) {
809 FlatNode fnext=fn.getNext(i);
822 TempFlatPair(TempDescriptor t, FlatNode f) {
827 public int hashCode() {
828 return f.hashCode()^t.hashCode();
830 public boolean equals(Object o) {
831 TempFlatPair tf=(TempFlatPair)o;
832 return t.equals(tf.t)&&f.equals(tf.f);
834 public String toString() {
835 return f.toString()+" "+t.toString();