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>> derefmap;
28 Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
30 public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
31 this.locality=locality;
33 this.typeanalysis=typeanalysis;
35 this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
36 this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
37 if (state.STMARRAY&&!state.DUALVIEW)
38 this.derefmap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
39 this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
42 public DiscoverConflicts getConflicts() {
46 public Hashtable<LocalityBinding, HashSet<FlatNode>> getCannotDelayMap() {
47 return cannotdelaymap;
51 public HashSet<FlatNode> getDeref(LocalityBinding lb) {
52 return derefmap.get(lb);
55 public void doAnalysis() {
56 //first dcopts...use to figure out what we need to lock
57 dcopts=new DiscoverConflicts(locality, state, typeanalysis, null);
60 //compute cannotdelaymap
61 Set<LocalityBinding> localityset=locality.getLocalityBindings();
62 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
63 analyzeMethod(lbit.next());
66 //ignore things that aren't in the map
67 dcopts=new DiscoverConflicts(locality, state, typeanalysis, cannotdelaymap, false, false, state.READSET?gft:null);
71 for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
72 LocalityBinding lb=lbit.next();
74 MethodDescriptor md=lb.getMethod();
75 FlatMethod fm=state.getMethodFlat(md);
79 if (lb.getHasAtomic()) {
80 HashSet<FlatNode> cannotdelay=cannotdelaymap.get(lb);
81 HashSet<FlatNode> notreadyset=computeNotReadySet(lb, cannotdelay);
82 HashSet<FlatNode> otherset=new HashSet<FlatNode>();
83 otherset.addAll(fm.getNodeSet());
84 otherset.removeAll(notreadyset);
85 otherset.removeAll(cannotdelay);
87 Hashtable<FlatNode, Integer> atomicmap=locality.getAtomic(lb);
88 for(Iterator<FlatNode> fnit=otherset.iterator();fnit.hasNext();) {
89 FlatNode fn=fnit.next();
90 if (atomicmap.get(fn).intValue()>0&&
91 fn.kind()!=FKind.FlatAtomicEnterNode&&
92 fn.kind()!=FKind.FlatGlobalConvNode) {
93 //remove non-atomic flatnodes
100 notreadymap.put(lb, notreadyset);
101 othermap.put(lb, otherset);
105 //(1) Cannot delay set -- stuff that must be done before commit
106 //(2) Not ready set -- stuff that must wait until commit
107 //(3) everything else -- stuff that should be done before commit
111 public HashSet<FlatNode> computeWriteSet(LocalityBinding lb) {
112 HashSet<FlatNode> writeset=new HashSet<FlatNode>();
113 Set<FlatNode> storeset=livecode(lb);
114 HashSet<FlatNode> delayedset=getNotReady(lb);
115 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<TempFlatPair>>> fnmap=dcopts.getMap(lb);
116 for(Iterator<FlatNode> fnit=delayedset.iterator();fnit.hasNext();) {
117 FlatNode fn=fnit.next();
118 Hashtable<TempDescriptor, Set<TempFlatPair>> tempmap=fnmap.get(fn);
119 if (fn.kind()==FKind.FlatSetElementNode) {
120 FlatSetElementNode fsen=(FlatSetElementNode) fn;
121 Set<TempFlatPair> tfpset=tempmap.get(fsen.getDst());
123 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
124 TempFlatPair tfp=tfpit.next();
125 if (storeset.contains(tfp.f))
129 } else if (fn.kind()==FKind.FlatSetFieldNode) {
130 FlatSetFieldNode fsfn=(FlatSetFieldNode) fn;
131 Set<TempFlatPair> tfpset=tempmap.get(fsfn.getDst());
133 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
134 TempFlatPair tfp=tfpit.next();
135 if (storeset.contains(tfp.f))
145 public HashSet<FlatNode> getNotReady(LocalityBinding lb) {
146 return notreadymap.get(lb);
149 public HashSet<FlatNode> getCannotDelay(LocalityBinding lb) {
150 return cannotdelaymap.get(lb);
153 public HashSet<FlatNode> getOther(LocalityBinding lb) {
154 return othermap.get(lb);
157 //This method computes which temps are live into the second part
158 public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
159 MethodDescriptor md=lb.getMethod();
160 FlatMethod fm=state.getMethodFlat(md);
161 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
163 //Compute second part set of nodes
164 Set<FlatNode> secondpart=new HashSet<FlatNode>();
165 secondpart.addAll(getNotReady(lb));
166 secondpart.addAll(recordset);
168 //make it just this transaction
169 secondpart.retainAll(atomicnodes);
171 HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
173 for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
174 FlatNode fn=fnit.next();
175 List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
176 tempset.addAll(writes);
177 if (!recordset.contains(fn)) {
178 List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
179 tempset.addAll(reads);
186 //This method computes which temps are live into the second part
187 public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
188 MethodDescriptor md=lb.getMethod();
189 FlatMethod fm=state.getMethodFlat(md);
190 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
192 //Compute second part set of nodes
193 Set<FlatNode> secondpart=new HashSet<FlatNode>();
194 secondpart.addAll(getNotReady(lb));
195 secondpart.addAll(recordset);
197 //make it just this transaction
198 secondpart.retainAll(atomicnodes);
200 Set<TempDescriptor> liveinto=new HashSet<TempDescriptor>();
202 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
204 for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
205 FlatNode fn=fnit.next();
206 if (recordset.contains(fn))
208 TempDescriptor readset[]=fn.readsTemps();
209 for(int i=0;i<readset.length;i++) {
210 TempDescriptor rtmp=readset[i];
211 Set<FlatNode> fnset=reachingdefs.get(fn).get(rtmp);
212 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
213 FlatNode fn2=fnit2.next();
214 if (secondpart.contains(fn2))
216 //otherwise we mark this as live in
225 //This method computes which temps are live out of the second part
226 public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
227 MethodDescriptor md=lb.getMethod();
228 FlatMethod fm=state.getMethodFlat(md);
229 Set<FlatNode> exits=faen.getExits();
230 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
231 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
233 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
235 Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
236 secondpart.retainAll(atomicnodes);
238 Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
239 //Have list of all live temps
241 for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
242 FlatNode fn=fnit.next();
243 Set<TempDescriptor> tempset=livemap.get(fn);
244 Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
245 //Look for reaching defs for all live variables that are in the secondpart
247 for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
248 TempDescriptor tmp=tmpit.next();
249 Set<FlatNode> fnset=reachmap.get(tmp);
250 boolean outsidenode=false;
251 boolean insidenode=false;
253 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
254 FlatNode fn2=fnit2.next();
255 if (secondpart.contains(fn2)) {
257 } else if (!atomicnodes.contains(fn2)) {
260 if (outsidenode&&insidenode) {
270 //This method computes which temps are live out of the second part
271 public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
272 MethodDescriptor md=lb.getMethod();
273 FlatMethod fm=state.getMethodFlat(md);
274 Set<FlatNode> exits=faen.getExits();
275 Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
276 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, livemap, true);
278 Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
280 Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
281 secondpart.retainAll(atomicnodes);
283 Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
284 //Have list of all live temps
286 for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
287 FlatNode fn=fnit.next();
288 Set<TempDescriptor> tempset=livemap.get(fn);
289 Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
290 //Look for reaching defs for all live variables that are in the secondpart
292 for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
293 TempDescriptor tmp=tmpit.next();
294 Set<FlatNode> fnset=reachmap.get(tmp);
296 System.out.println("null temp set for"+fn+" tmp="+tmp);
297 System.out.println(fm.printMethod());
299 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
300 FlatNode fn2=fnit2.next();
301 if (secondpart.contains(fn2)) {
311 //This method computes which nodes from the first part of the
312 //transaction must store their output for the second part
313 //Note that many nodes don't need to...
315 public Set<FlatNode> livecode(LocalityBinding lb) {
316 if (!othermap.containsKey(lb))
318 MethodDescriptor md=lb.getMethod();
319 FlatMethod fm=state.getMethodFlat(md);
321 HashSet<FlatNode> delayedset=notreadymap.get(lb);
322 HashSet<FlatNode> derefset=null;
323 if (state.STMARRAY&&!state.DUALVIEW)
324 derefset=derefmap.get(lb);
325 HashSet<FlatNode> otherset=othermap.get(lb);
326 HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
327 Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
328 Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true);
329 HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
330 Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
331 HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
332 Hashtable<FlatCondBranch, Set<FlatNode>> branchmap=revGetBranchSet(lb);
334 //Here we check for temps that are live out on the transaction...
335 //If both parts can contribute to the temp, then we need to do
336 //reads to make sure that liveout set has the right values
338 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
339 FlatNode fn=fnit.next();
340 if (fn.kind()==FKind.FlatAtomicExitNode) {
341 Set<TempDescriptor> livetemps=livemap.get(fn);
342 Hashtable<TempDescriptor, Set<FlatNode>> tempmap=reachingdefsmap.get(fn);
344 //Iterate over the temps that are live into this node
345 for(Iterator<TempDescriptor> tmpit=livetemps.iterator();tmpit.hasNext();) {
346 TempDescriptor tmp=tmpit.next();
347 Set<FlatNode> fnset=tempmap.get(tmp);
348 boolean inpart1=false;
349 boolean inpart2=false;
351 //iterate over the reaching definitions for the temp
352 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
353 FlatNode fn2=fnit2.next();
354 if (delayedset.contains(fn2)) {
358 } else if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
364 if (inpart1&&inpart2) {
365 for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
366 FlatNode fn2=fnit2.next();
367 if ((otherset.contains(fn2)||cannotdelayset.contains(fn2))&&
368 locality.getAtomic(lb).get(fn2).intValue()>0) {
378 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
381 while(!toanalyze.isEmpty()) {
382 FlatNode fn=toanalyze.iterator().next();
383 toanalyze.remove(fn);
384 Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
386 //Don't process non-atomic nodes
387 if (locality.getAtomic(lb).get(fn).intValue()==0) {
388 if (!map.containsKey(fn)) {
389 map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
391 for(int i=0;i<fn.numNext();i++)
392 toanalyze.add(fn.getNext(i));
397 Set<TempDescriptor> liveset=livemap.get(fn);
398 //Do merge on incoming edges
399 for(int i=0;i<fn.numPrev();i++) {
400 FlatNode fnprev=fn.getPrev(i);
401 Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
403 for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
404 TempDescriptor tmp=tmpit.next();
405 if (!liveset.contains(tmp)) //skip dead temps
407 if (!tmptofn.containsKey(tmp))
408 tmptofn.put(tmp, new HashSet<FlatNode>());
409 tmptofn.get(tmp).addAll(prevmap.get(tmp));
413 if (delayedset.contains(fn)) {
414 if(state.STMARRAY&&!state.DUALVIEW&&derefset.contains(fn)) {
415 //FlatElementNodes don't read anything...
416 if (fn.kind()==FKind.FlatSetElementNode) {
417 //check only the source read tmp
418 TempDescriptor tmp=((FlatSetElementNode)fn).getSrc();
419 if (tmptofn.containsKey(tmp)) {
420 livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
421 unionset.addAll(tmptofn.get(tmp));
425 //If the node is in the second set, check our readset
426 TempDescriptor readset[]=fn.readsTemps();
427 for(int i=0;i<readset.length;i++) {
428 TempDescriptor tmp=readset[i];
429 if (tmptofn.containsKey(tmp)) {
430 livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
431 unionset.addAll(tmptofn.get(tmp));
436 TempDescriptor writeset[]=fn.writesTemps();
437 for(int i=0;i<writeset.length;i++) {
438 TempDescriptor tmp=writeset[i];
442 //If the node is in the first set, search over what we write
443 //We write -- our reads are done
444 TempDescriptor writeset[]=fn.writesTemps();
445 for(int i=0;i<writeset.length;i++) {
446 TempDescriptor tmp=writeset[i];
447 HashSet<FlatNode> set=new HashSet<FlatNode>();
448 tmptofn.put(tmp,set);
451 if (fn.numNext()>1) {
452 Set<FlatNode> branchset=branchmap.get((FlatCondBranch)fn);
453 for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
454 FlatNode brfn=brit.next();
455 if (unionset.contains(brfn)) {
456 //This branch is important--need to remember how it goes
463 if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
464 map.put(fn, tmptofn);
466 for(int i=0;i<fn.numNext();i++)
467 toanalyze.add(fn.getNext(i));
473 public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
474 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
475 FlatNode fnnext=fn.getNext(i);
476 HashSet<FlatNode> reachable=new HashSet<FlatNode>();
478 if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
479 reachable.add(fnnext);
482 Stack<FlatNode> nodes=new Stack<FlatNode>();
483 HashSet<FlatNode> visited=new HashSet<FlatNode>();
488 while(!nodes.isEmpty()) {
489 FlatNode fn2=nodes.pop();
490 if (visited.contains(fn2))
493 for (int j=0;j<fn2.numNext();j++) {
494 FlatNode fn2next=fn2.getNext(j);
495 if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
496 reachable.add(fn2next);
504 //Computes cannotdelayset---flatnodes that must be evaluated in the
505 //speculative component.
507 public void analyzeMethod(LocalityBinding lb) {
508 MethodDescriptor md=lb.getMethod();
509 FlatMethod fm=state.getMethodFlat(md);
510 HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
511 HashSet<FlatNode> derefset=new HashSet<FlatNode>();
512 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
514 //We are in a transaction already...
515 //skip past this method or something
519 Hashtable<FlatNode, Set<TempDescriptor>> oldtempmap=dcopts.computeOldTemps(lb);
521 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
522 toanalyze.addAll(fm.getNodeSet());
524 //Build the hashtables
525 Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
526 Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
527 Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
528 Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
529 Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
531 Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
532 Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
533 //Effect of adding something to nodelay set is to move it up past everything in delay set
534 //Have to make sure we can do this commute
536 while(!toanalyze.isEmpty()) {
537 FlatNode fn=toanalyze.iterator().next();
538 toanalyze.remove(fn);
540 boolean isatomic=atomictable.get(fn).intValue()>0;
544 boolean isnodelay=false;
546 /* Compute incoming nodelay sets */
547 HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
548 HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
549 HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
550 HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
551 HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
552 for(int i=0;i<fn.numNext();i++) {
553 if (nodelaytemps.containsKey(fn.getNext(i)))
554 nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
555 //do field/array write sets
556 if (nodelayfieldswr.containsKey(fn.getNext(i)))
557 nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
558 if (nodelayarrayswr.containsKey(fn.getNext(i)))
559 nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
561 if (nodelayfieldsrd.containsKey(fn.getNext(i)))
562 nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
563 if (nodelayarraysrd.containsKey(fn.getNext(i)))
564 nodelayarrayrdset.addAll(nodelayarraysrd.get(fn.getNext(i)));
567 /* Check our temp write set */
569 TempDescriptor writeset[]=fn.writesTemps();
570 for(int i=0;i<writeset.length;i++) {
571 TempDescriptor tmp=writeset[i];
572 if (nodelaytempset.contains(tmp)) {
573 //We are writing to a nodelay temp
574 //Therefore we are nodelay
576 //Kill temp we wrote to
577 nodelaytempset.remove(tmp);
581 //See if flatnode is definitely no delay
582 if (fn.kind()==FKind.FlatCall) {
583 FlatCall fcall=(FlatCall)fn;
584 MethodDescriptor mdcall=fcall.getMethod();
585 if (!mdcall.getClassDesc().getSymbol().equals("System")||
586 (!mdcall.getSymbol().equals("println")&&!mdcall.getSymbol().equals("printString")))
590 //Delay branches if possible
591 if (fn.kind()==FKind.FlatCondBranch) {
592 Set<FlatNode> branchset=revbranchmap.get((FlatCondBranch)fn);
593 for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
594 FlatNode branchnode=brit.next();
595 if (cannotdelay.contains(branchnode)||(state.STMARRAY&&!state.DUALVIEW&&derefset.contains(branchnode))) {
602 //Check for field conflicts
603 if (fn.kind()==FKind.FlatSetFieldNode) {
604 FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
606 if (nodelayfieldwrset.contains(fd))
609 if (nodelayfieldrdset.contains(fd))
613 if (fn.kind()==FKind.FlatFieldNode) {
614 FieldDescriptor fd=((FlatFieldNode)fn).getField();
616 if (nodelayfieldwrset.contains(fd))
619 //Check for array conflicts
620 if (fn.kind()==FKind.FlatSetElementNode) {
621 TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
622 //check for write conflicts
623 if (nodelayarraywrset.contains(td))
625 //check for read conflicts
626 if (nodelayarrayrdset.contains(td))
629 if (fn.kind()==FKind.FlatElementNode) {
630 TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
631 //check for write conflicts
632 if (nodelayarraywrset.contains(td))
636 //If we are no delay, then the temps we read are no delay
638 /* Add our read set */
639 TempDescriptor readset[]=fn.readsTemps();
640 for(int i=0;i<readset.length;i++) {
641 TempDescriptor tmp=readset[i];
642 nodelaytempset.add(tmp);
646 if (branchmap.containsKey(fn)) {
647 Set<FlatCondBranch> fcbset=branchmap.get(fn);
648 for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
649 FlatCondBranch fcb=fcbit.next();
650 //enqueue flatcondbranch node for reanalysis
651 if (!cannotdelay.contains(fcb)) {
652 cannotdelay.add(fcb);
657 /* Do we write to fields */
658 if (fn.kind()==FKind.FlatSetFieldNode) {
659 nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
661 /* Do we read from fields */
662 if (fn.kind()==FKind.FlatFieldNode) {
663 nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
665 /* Do we write to arrays */
666 if (fn.kind()==FKind.FlatSetElementNode) {
667 //have to do expansion
668 nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
670 /* Do we read from arrays */
671 if (fn.kind()==FKind.FlatElementNode) {
672 //have to do expansion
673 nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
676 //See if flatnode is definitely no delay
677 if (fn.kind()==FKind.FlatCall) {
678 //Have to deal with fields/arrays
679 FlatCall fcall=(FlatCall)fn;
680 MethodDescriptor mdcall=fcall.getMethod();
681 nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
682 nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
683 //Have to deal with field/array reads
684 nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
685 nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
688 //Need to know which objects to lock on
689 Set<TempDescriptor> oldtemps=oldtempmap.get(fn);
691 case FKind.FlatSetFieldNode: {
692 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
693 if (oldtemps.contains(fsfn.getDst())) {
694 nodelaytempset.add(fsfn.getDst());
698 case FKind.FlatSetElementNode: {
699 FlatSetElementNode fsen=(FlatSetElementNode)fn;
700 if (oldtemps.contains(fsen.getDst())) {
701 nodelaytempset.add(fsen.getDst());
702 //Word Array support requires index
703 if (state.STMARRAY&&!state.DUALVIEW) {
704 nodelaytempset.add(fsen.getIndex());
710 case FKind.FlatFieldNode: {
711 FlatFieldNode ffn=(FlatFieldNode)fn;
712 if (oldtemps.contains(ffn.getSrc())&&
713 dcopts.getFields().contains(ffn.getField())) {
714 nodelaytempset.add(ffn.getSrc());
718 case FKind.FlatElementNode: {
719 FlatElementNode fen=(FlatElementNode)fn;
720 if (oldtemps.contains(fen.getSrc())&&
721 dcopts.getArrays().contains(fen.getSrc().getType())) {
722 nodelaytempset.add(fen.getSrc());
723 //Word Array support requires index
724 if (state.STMARRAY&&!state.DUALVIEW) {
725 nodelaytempset.add(fen.getIndex());
734 boolean changed=false;
735 //See if we need to propagate changes
736 if (!nodelaytemps.containsKey(fn)||
737 !nodelaytemps.get(fn).equals(nodelaytempset)) {
738 nodelaytemps.put(fn, nodelaytempset);
742 //See if we need to propagate changes
743 if (!nodelayfieldswr.containsKey(fn)||
744 !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
745 nodelayfieldswr.put(fn, nodelayfieldwrset);
749 //See if we need to propagate changes
750 if (!nodelayfieldsrd.containsKey(fn)||
751 !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
752 nodelayfieldsrd.put(fn, nodelayfieldrdset);
756 //See if we need to propagate changes
757 if (!nodelayarrayswr.containsKey(fn)||
758 !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
759 nodelayarrayswr.put(fn, nodelayarraywrset);
763 //See if we need to propagate changes
764 if (!nodelayarraysrd.containsKey(fn)||
765 !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
766 nodelayarraysrd.put(fn, nodelayarrayrdset);
771 for(int i=0;i<fn.numPrev();i++)
772 toanalyze.add(fn.getPrev(i));
775 if (lb.getHasAtomic()) {
776 if (state.STMARRAY&&!state.DUALVIEW)
777 derefmap.put(lb, derefset);
778 cannotdelaymap.put(lb, cannotdelay);
783 //1) we acquire locks too early to object we don't need to yet
784 //2) we don't realize that certain operations have side effects
786 public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
787 //You are in not ready set if:
788 //I. You read a not ready temp
789 //II. You access a field or element and
790 //(A). You are not in the cannot delay set
791 //(B). You read a field/element in the transactional set
792 //(C). The source didn't have a transactional read on it
794 MethodDescriptor md=lb.getMethod();
795 FlatMethod fm=state.getMethodFlat(md);
796 Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
797 HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
798 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
799 toanalyze.addAll(fm.getNodeSet());
800 Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
802 Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
803 Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
805 while(!toanalyze.isEmpty()) {
806 FlatNode fn=toanalyze.iterator().next();
807 toanalyze.remove(fn);
808 boolean isatomic=atomictable.get(fn).intValue()>0;
813 //Compute initial notready set
814 HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
815 for(int i=0;i<fn.numPrev();i++) {
816 if (notreadymap.containsKey(fn.getPrev(i)))
817 notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
821 boolean notready=false;
823 //Test our read set first
824 TempDescriptor readset[]=fn.readsTemps();
825 for(int i=0;i<readset.length;i++) {
826 TempDescriptor tmp=readset[i];
827 if (notreadyset.contains(tmp)) {
833 if (!notready&&!cannotdelay.contains(fn)) {
835 case FKind.FlatFieldNode: {
836 FlatFieldNode ffn=(FlatFieldNode)fn;
837 if (!dcopts.getFields().contains(ffn.getField())) {
840 TempDescriptor tmp=ffn.getSrc();
841 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
843 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
844 TempFlatPair tfp=tfpit.next();
845 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
846 //if a source didn't need a translation and we are
847 //accessing it, it did...so therefore we are note
856 case FKind.FlatSetFieldNode: {
857 FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
858 TempDescriptor tmp=fsfn.getDst();
859 Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
860 Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
863 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
864 TempFlatPair tfp=tfpit.next();
865 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
866 //if a source didn't need a translation and we are
867 //accessing it, it did...so therefore we are note
876 case FKind.FlatElementNode: {
877 FlatElementNode fen=(FlatElementNode)fn;
878 if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
881 TempDescriptor tmp=fen.getSrc();
882 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
884 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
885 TempFlatPair tfp=tfpit.next();
886 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
887 //if a source didn't need a translation and we are
888 //accessing it, it did...so therefore we are note
897 case FKind.FlatSetElementNode: {
898 FlatSetElementNode fsen=(FlatSetElementNode)fn;
899 TempDescriptor tmp=fsen.getDst();
900 Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
902 for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
903 TempFlatPair tfp=tfpit.next();
904 if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
905 //if a source didn't need a translation and we are
906 //accessing it, it did...so therefore we are note
919 //See if we depend on a conditional branch that is not ready
920 Set<FlatCondBranch> branchset=branchmap.get(fn);
922 for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
923 FlatCondBranch fcb=branchit.next();
924 if (notreadynodes.contains(fcb)) {
925 //if we depend on a branch that isn't ready, we aren't ready
933 //Fix up things based on our status
935 if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
936 //enqueue everything in our dependence set
937 Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
938 toanalyze.addAll(branchdepset);
942 notreadynodes.add(fn);
945 TempDescriptor writeset[]=fn.writesTemps();
946 for(int i=0;i<writeset.length;i++) {
947 TempDescriptor tmp=writeset[i];
948 notreadyset.add(tmp);
952 TempDescriptor writeset[]=fn.writesTemps();
953 for(int i=0;i<writeset.length;i++) {
954 TempDescriptor tmp=writeset[i];
955 notreadyset.remove(tmp);
959 //See if we need to propagate changes
960 if (!notreadymap.containsKey(fn)||
961 !notreadymap.get(fn).equals(notreadyset)) {
962 notreadymap.put(fn, notreadyset);
963 for(int i=0;i<fn.numNext();i++)
964 toanalyze.add(fn.getNext(i));
967 return notreadynodes;
968 } //end of computeNotReadySet
970 public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
971 MethodDescriptor md=lb.getMethod();
972 FlatMethod fm=state.getMethodFlat(md);
973 Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
974 DomTree postdt=new DomTree(fm, true);
975 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
976 FlatNode fn=fnit.next();
977 if (fn.kind()!=FKind.FlatCondBranch)
979 FlatCondBranch fcb=(FlatCondBranch)fn;
980 //only worry about fcb inside of transactions
981 if (locality.getAtomic(lb).get(fcb).intValue()==0)
983 FlatNode postdom=postdt.idom(fcb);
985 //Reverse the mapping
986 Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
987 condmap.put(fcb, fnset);
992 public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
993 MethodDescriptor md=lb.getMethod();
994 FlatMethod fm=state.getMethodFlat(md);
995 Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
996 DomTree postdt=new DomTree(fm, true);
997 for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
998 FlatNode fn=fnit.next();
999 if (fn.kind()!=FKind.FlatCondBranch)
1001 FlatCondBranch fcb=(FlatCondBranch)fn;
1002 //only worry about fcb inside of transactions
1003 if (locality.getAtomic(lb).get(fcb).intValue()==0)
1005 FlatNode postdom=postdt.idom(fcb);
1007 //Reverse the mapping
1008 Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
1009 for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
1010 FlatNode fn2=fnit2.next();
1011 if (!condmap.containsKey(fn2))
1012 condmap.put(fn2,new HashSet<FlatCondBranch>());
1013 condmap.get(fn2).add(fcb);
1019 public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
1020 HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
1021 HashSet<FlatNode> visited=new HashSet<FlatNode>();
1022 toanalyze.add(first);
1024 while(!toanalyze.isEmpty()) {
1025 FlatNode fn=toanalyze.iterator().next();
1026 toanalyze.remove(fn);
1028 //already examined or exit node
1029 if (visited.contains(fn)||fn==last)
1032 //out of transaction
1033 if (locality.getAtomic(lb).get(fn).intValue()==0)
1037 for(int i=0;i<fn.numNext();i++) {
1038 FlatNode fnext=fn.getNext(i);
1039 toanalyze.add(fnext);
1043 } //end of computeBranchSet