1 package Analysis.Locality;
2 import Analysis.Liveness;
3 import Analysis.ReachingDefs;
4 import Analysis.Loops.DomTree;
6 import IR.MethodDescriptor;
7 import IR.TypeDescriptor;
8 import IR.FieldDescriptor;
10 import Analysis.Loops.GlobalFieldType;
11 import java.util.HashSet;
12 import java.util.Hashtable;
14 import java.util.List;
15 import java.util.Arrays;
16 import java.util.Stack;
17 import java.util.Iterator;
19 public class DelayComputation {
21 LocalityAnalysis locality;
22 TypeAnalysis typeanalysis;
24 DiscoverConflicts dcopts;
25 Hashtable<LocalityBinding, HashSet<FlatNode>> notreadymap;
26 Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap;
27 Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
29 public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
30 this.locality=locality;
32 this.typeanalysis=typeanalysis;
34 this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
35 this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
36 this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
39 public DiscoverConflicts getConflicts() {
43 public Hashtable<LocalityBinding, HashSet<FlatNode>> getCannotDelayMap() {
44 return cannotdelaymap;
47 public void doAnalysis() {
48 Set<LocalityBinding> localityset=locality.getLocalityBindings();
49 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
50 analyzeMethod(lbit.next());
53 //ignore things that aren't in the map
54 dcopts=new DiscoverConflicts(locality, state, typeanalysis, cannotdelaymap, false, false);
58 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
59 LocalityBinding lb=lbit.next();
61 MethodDescriptor md=lb.getMethod();
62 FlatMethod fm=state.getMethodFlat(md);
66 if (lb.getHasAtomic()) {
67 HashSet<FlatNode> cannotdelay=cannotdelaymap.get(lb);
68 HashSet<FlatNode> notreadyset=computeNotReadySet(lb, cannotdelay);
69 HashSet<FlatNode> otherset=new HashSet<FlatNode>();
70 otherset.addAll(fm.getNodeSet());
71 otherset.removeAll(notreadyset);
72 otherset.removeAll(cannotdelay);
74 Hashtable<FlatNode, Integer> atomicmap=locality.getAtomic(lb);
75 for(Iterator<FlatNode> fnit=otherset.iterator();fnit.hasNext();) {
76 FlatNode fn=fnit.next();
77 if (atomicmap.get(fn).intValue()>0&&
78 fn.kind()!=FKind.FlatAtomicEnterNode&&
79 fn.kind()!=FKind.FlatGlobalConvNode) {
80 //remove non-atomic flatnodes
87 notreadymap.put(lb, notreadyset);
88 othermap.put(lb, otherset);
92 //(1) Cannot delay set -- stuff that must be done before commit
93 //(2) Not ready set -- stuff that must wait until commit
94 //(3) everything else -- stuff that should be done before commit
98 public HashSet<FlatNode> getNotReady(LocalityBinding lb) {
99 return notreadymap.get(lb);
102 public HashSet<FlatNode> getCannotDelay(LocalityBinding lb) {
103 return cannotdelaymap.get(lb);
106 public HashSet<FlatNode> getOther(LocalityBinding lb) {
107 return othermap.get(lb);
110 //This method computes which temps are live into the second part
111 public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
112 MethodDescriptor md=lb.getMethod();
113 FlatMethod fm=state.getMethodFlat(md);
114 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
116 //Compute second part set of nodes
117 Set<FlatNode> secondpart=new HashSet<FlatNode>();
118 secondpart.addAll(getNotReady(lb));
119 secondpart.addAll(recordset);
121 //make it just this transaction
122 secondpart.retainAll(atomicnodes);
124 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
126 for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
127 FlatNode fn=fnit.next();
128 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
129 tempset.addAll(writes);
130 if (!recordset.contains(fn)) {
131 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
132 tempset.addAll(reads);
139 //This method computes which temps are live into the second part
140 public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
141 MethodDescriptor md=lb.getMethod();
142 FlatMethod fm=state.getMethodFlat(md);
143 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
145 //Compute second part set of nodes
146 Set<FlatNode> secondpart=new HashSet<FlatNode>();
147 secondpart.addAll(getNotReady(lb));
148 secondpart.addAll(recordset);
150 //make it just this transaction
151 secondpart.retainAll(atomicnodes);
153 Set<TempDescriptor> liveinto=new HashSet<TempDescriptor>();
155 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
157 for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
158 FlatNode fn=fnit.next();
159 if (recordset.contains(fn))
161 TempDescriptor readset[]=fn.readsTemps();
162 for(int i=0;i<readset.length;i++) {
163 TempDescriptor rtmp=readset[i];
164 Set<FlatNode> fnset=reachingdefs.get(fn).get(rtmp);
165 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
166 FlatNode fn2=fnit2.next();
167 if (secondpart.contains(fn2))
169 //otherwise we mark this as live in
178 //This method computes which temps are live out of the second part
179 public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
180 MethodDescriptor md=lb.getMethod();
181 FlatMethod fm=state.getMethodFlat(md);
182 Set<FlatNode> exits=faen.getExits();
183 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
184 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
186 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
188 Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
189 secondpart.retainAll(atomicnodes);
191 Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
192 //Have list of all live temps
194 for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
195 FlatNode fn=fnit.next();
196 Set<TempDescriptor> tempset=livemap.get(fn);
197 Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
198 //Look for reaching defs for all live variables that are in the secondpart
200 for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
201 TempDescriptor tmp=tmpit.next();
202 Set<FlatNode> fnset=reachmap.get(tmp);
203 boolean outsidenode=false;
204 boolean insidenode=false;
206 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
207 FlatNode fn2=fnit2.next();
208 if (secondpart.contains(fn2)) {
210 } else if (!atomicnodes.contains(fn2)) {
213 if (outsidenode&&insidenode) {
223 //This method computes which temps are live out of the second part
224 public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
225 MethodDescriptor md=lb.getMethod();
226 FlatMethod fm=state.getMethodFlat(md);
227 Set<FlatNode> exits=faen.getExits();
228 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
229 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, livemap, true);
231 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
233 Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
234 secondpart.retainAll(atomicnodes);
236 Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
237 //Have list of all live temps
239 for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
240 FlatNode fn=fnit.next();
241 Set<TempDescriptor> tempset=livemap.get(fn);
242 Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
243 //Look for reaching defs for all live variables that are in the secondpart
245 for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
246 TempDescriptor tmp=tmpit.next();
247 Set<FlatNode> fnset=reachmap.get(tmp);
249 System.out.println("null temp set for"+fn+" tmp="+tmp);
250 System.out.println(fm.printMethod());
252 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
253 FlatNode fn2=fnit2.next();
254 if (secondpart.contains(fn2)) {
264 //This method computes which nodes from the first part of the
265 //transaction must store their output for the second part
266 //Note that many nodes don't need to...
268 public Set<FlatNode> livecode(LocalityBinding lb) {
269 if (!othermap.containsKey(lb))
271 MethodDescriptor md=lb.getMethod();
272 FlatMethod fm=state.getMethodFlat(md);
274 HashSet<FlatNode> delayedset=notreadymap.get(lb);
275 HashSet<FlatNode> otherset=othermap.get(lb);
276 HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
277 Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
278 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true);
279 HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
280 Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
281 HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
282 Hashtable<FlatCondBranch, Set<FlatNode>> branchmap=revGetBranchSet(lb);
284 //Here we check for temps that are live out on the transaction...
285 //If both parts can contribute to the temp, then we need to do
286 //reads to make sure that liveout set has the right values
288 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
289 FlatNode fn=fnit.next();
290 if (fn.kind()==FKind.FlatAtomicExitNode) {
291 Set<TempDescriptor> livetemps=livemap.get(fn);
292 Hashtable<TempDescriptor, Set<FlatNode>> tempmap=reachingdefsmap.get(fn);
294 //Iterate over the temps that are live into this node
295 for(Iterator<TempDescriptor> tmpit=livetemps.iterator();tmpit.hasNext();) {
296 TempDescriptor tmp=tmpit.next();
297 Set<FlatNode> fnset=tempmap.get(tmp);
298 boolean inpart1=false;
299 boolean inpart2=false;
301 //iterate over the reaching definitions for the temp
302 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
303 FlatNode fn2=fnit2.next();
304 if (delayedset.contains(fn2)) {
308 } else if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
314 if (inpart1&&inpart2) {
315 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
316 FlatNode fn2=fnit2.next();
317 if ((otherset.contains(fn2)||cannotdelayset.contains(fn2))&&
318 locality.getAtomic(lb).get(fn2).intValue()>0) {
328 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
331 while(!toanalyze.isEmpty()) {
332 FlatNode fn=toanalyze.iterator().next();
333 toanalyze.remove(fn);
334 Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
336 //Don't process non-atomic nodes
337 if (locality.getAtomic(lb).get(fn).intValue()==0) {
338 if (!map.containsKey(fn)) {
339 map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
341 for(int i=0;i<fn.numNext();i++)
342 toanalyze.add(fn.getNext(i));
347 //Do merge on incoming edges
348 for(int i=0;i<fn.numPrev();i++) {
349 FlatNode fnprev=fn.getPrev(i);
350 Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
352 for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
353 TempDescriptor tmp=tmpit.next();
354 if (!tmptofn.containsKey(tmp))
355 tmptofn.put(tmp, new HashSet<FlatNode>());
356 tmptofn.get(tmp).addAll(prevmap.get(tmp));
360 if (delayedset.contains(fn)) {
361 //If the node is in the second set, check our readset
362 TempDescriptor readset[]=fn.readsTemps();
363 for(int i=0;i<readset.length;i++) {
364 TempDescriptor tmp=readset[i];
365 if (tmptofn.containsKey(tmp)) {
366 livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
367 unionset.addAll(tmptofn.get(tmp));
372 TempDescriptor writeset[]=fn.writesTemps();
373 for(int i=0;i<writeset.length;i++) {
374 TempDescriptor tmp=writeset[i];
378 //If the node is in the first set, search over what we write
379 //We write -- our reads are done
380 TempDescriptor writeset[]=fn.writesTemps();
381 for(int i=0;i<writeset.length;i++) {
382 TempDescriptor tmp=writeset[i];
383 HashSet<FlatNode> set=new HashSet<FlatNode>();
384 tmptofn.put(tmp,set);
387 if (fn.numNext()>1) {
388 Set<FlatNode> branchset=branchmap.get((FlatCondBranch)fn);
389 for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
390 FlatNode brfn=brit.next();
391 if (unionset.contains(brfn)) {
392 //This branch is important--need to remember how it goes
399 if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
400 map.put(fn, tmptofn);
402 for(int i=0;i<fn.numNext();i++)
403 toanalyze.add(fn.getNext(i));
409 public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
410 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
411 FlatNode fnnext=fn.getNext(i);
412 HashSet<FlatNode> reachable=new HashSet<FlatNode>();
414 if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
415 reachable.add(fnnext);
418 Stack<FlatNode> nodes=new Stack<FlatNode>();
419 HashSet<FlatNode> visited=new HashSet<FlatNode>();
424 while(!nodes.isEmpty()) {
425 FlatNode fn2=nodes.pop();
426 if (visited.contains(fn2))
429 for (int j=0;j<fn2.numNext();j++) {
430 FlatNode fn2next=fn2.getNext(j);
431 if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
432 reachable.add(fn2next);
440 public void analyzeMethod(LocalityBinding lb) {
441 MethodDescriptor md=lb.getMethod();
442 FlatMethod fm=state.getMethodFlat(md);
443 HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
444 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
446 //We are in a transaction already...
447 //skip past this method or something
451 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
452 toanalyze.addAll(fm.getNodeSet());
454 //Build the hashtables
455 Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
456 Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
457 Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
458 Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
459 Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
461 Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
462 //Effect of adding something to nodelay set is to move it up past everything in delay set
463 //Have to make sure we can do this commute
465 while(!toanalyze.isEmpty()) {
466 FlatNode fn=toanalyze.iterator().next();
467 toanalyze.remove(fn);
469 boolean isatomic=atomictable.get(fn).intValue()>0;
473 boolean isnodelay=false;
475 /* Compute incoming nodelay sets */
476 HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
477 HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
478 HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
479 HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
480 HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
481 for(int i=0;i<fn.numNext();i++) {
482 if (nodelaytemps.containsKey(fn.getNext(i)))
483 nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
484 //do field/array write sets
485 if (nodelayfieldswr.containsKey(fn.getNext(i)))
486 nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
487 if (nodelayarrayswr.containsKey(fn.getNext(i)))
488 nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
490 if (nodelayfieldsrd.containsKey(fn.getNext(i)))
491 nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
492 if (nodelayarraysrd.containsKey(fn.getNext(i)))
493 nodelayarrayrdset.addAll(nodelayarraysrd.get(fn.getNext(i)));
496 /* Check our temp write set */
498 TempDescriptor writeset[]=fn.writesTemps();
499 for(int i=0;i<writeset.length;i++) {
500 TempDescriptor tmp=writeset[i];
501 if (nodelaytempset.contains(tmp)) {
502 //We are writing to a nodelay temp
503 //Therefore we are nodelay
505 //Kill temp we wrote to
506 nodelaytempset.remove(tmp);
510 //See if flatnode is definitely no delay
511 if (fn.kind()==FKind.FlatCall) {
513 //Have to deal with fields/arrays
514 FlatCall fcall=(FlatCall)fn;
515 MethodDescriptor mdcall=fcall.getMethod();
516 nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
517 nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
518 //Have to deal with field/array reads
519 nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
520 nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
523 //Delay branches if possible
524 if (fn.kind()==FKind.FlatCondBranch) {
525 Set<FlatNode> leftset=getNext(fn, 0, cannotdelay, lb, locality,true);
526 Set<FlatNode> rightset=getNext(fn, 1, cannotdelay, lb, locality,true);
527 if (leftset.size()>0&&rightset.size()>0&&
528 !leftset.equals(rightset)||leftset.size()>1)
532 //Check for field conflicts
533 if (fn.kind()==FKind.FlatSetFieldNode) {
534 FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
536 if (nodelayfieldwrset.contains(fd))
539 if (nodelayfieldrdset.contains(fd))
543 if (fn.kind()==FKind.FlatFieldNode) {
544 FieldDescriptor fd=((FlatFieldNode)fn).getField();
546 if (nodelayfieldwrset.contains(fd))
549 //Check for array conflicts
550 if (fn.kind()==FKind.FlatSetElementNode) {
551 TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
552 //check for write conflicts
553 if (nodelayarraywrset.contains(td))
555 //check for read conflicts
556 if (nodelayarrayrdset.contains(td))
559 if (fn.kind()==FKind.FlatElementNode) {
560 TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
561 //check for write conflicts
562 if (nodelayarraywrset.contains(td))
566 //If we are no delay, then the temps we read are no delay
568 /* Add our read set */
569 TempDescriptor readset[]=fn.readsTemps();
570 for(int i=0;i<readset.length;i++) {
571 TempDescriptor tmp=readset[i];
572 nodelaytempset.add(tmp);
576 if (branchmap.containsKey(fn)) {
577 Set<FlatCondBranch> fcbset=branchmap.get(fn);
578 for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
579 FlatCondBranch fcb=fcbit.next();
580 cannotdelay.add(fcb);
581 nodelaytempset.add(fcb.getTest());
584 /* Do we write to fields */
585 if (fn.kind()==FKind.FlatSetFieldNode) {
586 nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
588 /* Do we read from fields */
589 if (fn.kind()==FKind.FlatFieldNode) {
590 nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
592 /* Do we write to arrays */
593 if (fn.kind()==FKind.FlatSetElementNode) {
594 //have to do expansion
595 nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
597 /* Do we read from arrays */
598 if (fn.kind()==FKind.FlatElementNode) {
599 //have to do expansion
600 nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
603 //Need to know which objects to lock on
605 //TODO: Can improve by only locking if there is a field that requires a lock
606 case FKind.FlatSetFieldNode: {
607 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
608 nodelaytempset.add(fsfn.getDst());
611 case FKind.FlatSetElementNode: {
612 FlatSetElementNode fsen=(FlatSetElementNode)fn;
613 nodelaytempset.add(fsen.getDst());
616 case FKind.FlatFieldNode: {
617 FlatFieldNode ffn=(FlatFieldNode)fn;
618 nodelaytempset.add(ffn.getSrc());
621 case FKind.FlatElementNode: {
622 FlatElementNode fen=(FlatElementNode)fn;
623 nodelaytempset.add(fen.getSrc());
629 boolean changed=false;
630 //See if we need to propagate changes
631 if (!nodelaytemps.containsKey(fn)||
632 !nodelaytemps.get(fn).equals(nodelaytempset)) {
633 nodelaytemps.put(fn, nodelaytempset);
637 //See if we need to propagate changes
638 if (!nodelayfieldswr.containsKey(fn)||
639 !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
640 nodelayfieldswr.put(fn, nodelayfieldwrset);
644 //See if we need to propagate changes
645 if (!nodelayfieldsrd.containsKey(fn)||
646 !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
647 nodelayfieldsrd.put(fn, nodelayfieldrdset);
651 //See if we need to propagate changes
652 if (!nodelayarrayswr.containsKey(fn)||
653 !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
654 nodelayarrayswr.put(fn, nodelayarraywrset);
658 //See if we need to propagate changes
659 if (!nodelayarraysrd.containsKey(fn)||
660 !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
661 nodelayarraysrd.put(fn, nodelayarrayrdset);
666 for(int i=0;i<fn.numPrev();i++)
667 toanalyze.add(fn.getPrev(i));
670 if (lb.getHasAtomic()) {
671 cannotdelaymap.put(lb, cannotdelay);
676 //1) we acquire locks too early to object we don't need to yet
677 //2) we don't realize that certain operations have side effects
679 public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
680 //You are in not ready set if:
681 //I. You read a not ready temp
682 //II. You access a field or element and
683 //(A). You are not in the cannot delay set
684 //(B). You read a field/element in the transactional set
685 //(C). The source didn't have a transactional read on it
687 MethodDescriptor md=lb.getMethod();
688 FlatMethod fm=state.getMethodFlat(md);
689 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
690 HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
691 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
692 toanalyze.addAll(fm.getNodeSet());
693 Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
695 Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
696 Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
698 while(!toanalyze.isEmpty()) {
699 FlatNode fn=toanalyze.iterator().next();
700 toanalyze.remove(fn);
701 boolean isatomic=atomictable.get(fn).intValue()>0;
706 //Compute initial notready set
707 HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
708 for(int i=0;i<fn.numPrev();i++) {
709 if (notreadymap.containsKey(fn.getPrev(i)))
710 notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
714 boolean notready=false;
716 //Test our read set first
717 TempDescriptor readset[]=fn.readsTemps();
718 for(int i=0;i<readset.length;i++) {
719 TempDescriptor tmp=readset[i];
720 if (notreadyset.contains(tmp)) {
726 if (!notready&&!cannotdelay.contains(fn)) {
728 case FKind.FlatFieldNode: {
729 FlatFieldNode ffn=(FlatFieldNode)fn;
730 if (!dcopts.getFields().contains(ffn.getField())) {
733 TempDescriptor tmp=ffn.getSrc();
734 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
736 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
737 TempFlatPair tfp=tfpit.next();
738 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
739 //if a source didn't need a translation and we are
740 //accessing it, it did...so therefore we are note
749 case FKind.FlatSetFieldNode: {
750 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
751 TempDescriptor tmp=fsfn.getDst();
752 Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
753 Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
756 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
757 TempFlatPair tfp=tfpit.next();
758 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
759 //if a source didn't need a translation and we are
760 //accessing it, it did...so therefore we are note
769 case FKind.FlatElementNode: {
770 FlatElementNode fen=(FlatElementNode)fn;
771 if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
774 TempDescriptor tmp=fen.getSrc();
775 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
777 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
778 TempFlatPair tfp=tfpit.next();
779 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
780 //if a source didn't need a translation and we are
781 //accessing it, it did...so therefore we are note
790 case FKind.FlatSetElementNode: {
791 FlatSetElementNode fsen=(FlatSetElementNode)fn;
792 TempDescriptor tmp=fsen.getDst();
793 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
795 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
796 TempFlatPair tfp=tfpit.next();
797 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
798 //if a source didn't need a translation and we are
799 //accessing it, it did...so therefore we are note
812 //See if we depend on a conditional branch that is not ready
813 Set<FlatCondBranch> branchset=branchmap.get(fn);
815 for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
816 FlatCondBranch fcb=branchit.next();
817 if (notreadynodes.contains(fcb)) {
818 //if we depend on a branch that isn't ready, we aren't ready
826 //Fix up things based on our status
828 if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
829 //enqueue everything in our dependence set
830 Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
831 toanalyze.addAll(branchdepset);
835 notreadynodes.add(fn);
838 TempDescriptor writeset[]=fn.writesTemps();
839 for(int i=0;i<writeset.length;i++) {
840 TempDescriptor tmp=writeset[i];
841 notreadyset.add(tmp);
845 TempDescriptor writeset[]=fn.writesTemps();
846 for(int i=0;i<writeset.length;i++) {
847 TempDescriptor tmp=writeset[i];
848 notreadyset.remove(tmp);
852 //See if we need to propagate changes
853 if (!notreadymap.containsKey(fn)||
854 !notreadymap.get(fn).equals(notreadyset)) {
855 notreadymap.put(fn, notreadyset);
856 for(int i=0;i<fn.numNext();i++)
857 toanalyze.add(fn.getNext(i));
860 return notreadynodes;
861 } //end of computeNotReadySet
863 public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
864 MethodDescriptor md=lb.getMethod();
865 FlatMethod fm=state.getMethodFlat(md);
866 Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
867 DomTree postdt=new DomTree(fm, true);
868 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
869 FlatNode fn=fnit.next();
870 if (fn.kind()!=FKind.FlatCondBranch)
872 FlatCondBranch fcb=(FlatCondBranch)fn;
873 //only worry about fcb inside of transactions
874 if (locality.getAtomic(lb).get(fcb).intValue()==0)
876 FlatNode postdom=postdt.idom(fcb);
878 //Reverse the mapping
879 Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
880 condmap.put(fcb, fnset);
885 public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
886 MethodDescriptor md=lb.getMethod();
887 FlatMethod fm=state.getMethodFlat(md);
888 Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
889 DomTree postdt=new DomTree(fm, true);
890 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
891 FlatNode fn=fnit.next();
892 if (fn.kind()!=FKind.FlatCondBranch)
894 FlatCondBranch fcb=(FlatCondBranch)fn;
895 //only worry about fcb inside of transactions
896 if (locality.getAtomic(lb).get(fcb).intValue()==0)
898 FlatNode postdom=postdt.idom(fcb);
900 //Reverse the mapping
901 Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
902 for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
903 FlatNode fn2=fnit2.next();
904 if (!condmap.containsKey(fn2))
905 condmap.put(fn2,new HashSet<FlatCondBranch>());
906 condmap.get(fn2).add(fcb);
912 public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
913 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
914 HashSet<FlatNode> visited=new HashSet<FlatNode>();
915 toanalyze.add(first);
917 while(!toanalyze.isEmpty()) {
918 FlatNode fn=toanalyze.iterator().next();
919 toanalyze.remove(fn);
921 //already examined or exit node
922 if (visited.contains(fn)||fn==last)
926 if (locality.getAtomic(lb).get(fn).intValue()==0)
930 for(int i=0;i<fn.numNext();i++) {
931 FlatNode fnext=fn.getNext(i);
932 toanalyze.add(fnext);
936 } //end of computeBranchSet