Robust/src/Analysis/Locality/DelayComputation.java

   1 package Analysis.Locality;
   2 import Analysis.Liveness;
   3 import Analysis.ReachingDefs;
   4 import IR.State;
   5 import IR.MethodDescriptor;
   6 import IR.TypeDescriptor;
   7 import IR.FieldDescriptor;
   8 import IR.Flat.*;
   9 import Analysis.Loops.GlobalFieldType;
  10 import java.util.HashSet;
  11 import java.util.Hashtable;
  12 import java.util.Set;
  13 import java.util.List;
  14 import java.util.Arrays;
  15 import java.util.Stack;
  16 import java.util.Iterator;
  17
  18 public class DelayComputation {
  19   State state;
  20   LocalityAnalysis locality;
  21   TypeAnalysis typeanalysis;
  22   GlobalFieldType gft;
  23   DiscoverConflicts dcopts;
  24   Hashtable<LocalityBinding, HashSet<FlatNode>> notreadymap;
  25   Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap;
  26   Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
  27
  28   public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
  29     this.locality=locality;
  30     this.state=state;
  31     this.typeanalysis=typeanalysis;
  32     this.gft=gft;
  33     this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  34     this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  35     this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  36   }
  37
  38   public DiscoverConflicts getConflicts() {
  39     return dcopts;
  40   }
  41
  42   public void doAnalysis() {
  43     Set<LocalityBinding> localityset=locality.getLocalityBindings();
  44     for(Iterator<LocalityBinding> lb=localityset.iterator();lb.hasNext();) {
  45       analyzeMethod(lb.next());
  46     }
  47   }
  48
  49   public HashSet<FlatNode> getNotReady(LocalityBinding lb) {
  50     return notreadymap.get(lb);
  51   }
  52
  53   public HashSet<FlatNode> getCannotDelay(LocalityBinding lb) {
  54     return cannotdelaymap.get(lb);
  55   }
  56
  57   public HashSet<FlatNode> getOther(LocalityBinding lb) {
  58     return othermap.get(lb);
  59   }
  60
  61   //This method computes which temps are live into the second part
  62   public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
  63     MethodDescriptor md=lb.getMethod();
  64     FlatMethod fm=state.getMethodFlat(md);
  65     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
  66
  67     //Compute second part set of nodes
  68     Set<FlatNode> secondpart=new HashSet<FlatNode>();
  69     secondpart.addAll(getNotReady(lb));
  70     secondpart.addAll(recordset);
  71
  72     //make it just this transaction
  73     secondpart.retainAll(atomicnodes);
  74
  75     HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
  76
  77     for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
  78       FlatNode fn=fnit.next();
  79       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
  80       tempset.addAll(writes);
  81       if (!recordset.contains(fn)) {
  82         List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
  83         tempset.addAll(reads);
  84       }
  85     }
  86
  87     return tempset;
  88   }
  89
  90   //This method computes which temps are live into the second part
  91   public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> liveset) {
  92     MethodDescriptor md=lb.getMethod();
  93     FlatMethod fm=state.getMethodFlat(md);
  94     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
  95
  96     //Compute second part set of nodes
  97     Set<FlatNode> secondpart=new HashSet<FlatNode>();
  98     secondpart.addAll(getNotReady(lb));
  99     secondpart.addAll(liveset);
 100
 101     //make it just this transaction
 102     secondpart.retainAll(atomicnodes);
 103
 104     Set<TempDescriptor> liveinto=new HashSet<TempDescriptor>();
 105     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm);
 106
 107     for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
 108       FlatNode fn=fnit.next();
 109
 110       TempDescriptor readset[]=fn.readsTemps();
 111       for(int i=0;i<readset.length;i++) {
 112         TempDescriptor rtmp=readset[i];
 113         Set<FlatNode> fnset=reachingdefs.get(fn).get(rtmp);
 114         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 115           FlatNode fn2=fnit2.next();
 116           if (secondpart.contains(fn2))
 117             continue;
 118           //otherwise we mark this as live in
 119           liveinto.add(rtmp);
 120           break;
 121         }
 122       }
 123     }
 124     return liveinto;
 125   }
 126
 127   //This method computes which temps are live out of the second part
 128   public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
 129     MethodDescriptor md=lb.getMethod();
 130     FlatMethod fm=state.getMethodFlat(md);
 131     Set<FlatNode> exits=faen.getExits();
 132     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 133     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm);
 134
 135     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 136
 137     Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
 138     secondpart.retainAll(atomicnodes);
 139
 140     Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
 141     //Have list of all live temps
 142
 143     for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
 144       FlatNode fn=fnit.next();
 145       Set<TempDescriptor> tempset=livemap.get(fn);
 146       Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
 147       //Look for reaching defs for all live variables that are in the secondpart
 148
 149       for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
 150         TempDescriptor tmp=tmpit.next();
 151         Set<FlatNode> fnset=reachmap.get(tmp);
 152         boolean outsidenode=false;
 153         boolean insidenode=false;
 154
 155         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 156           FlatNode fn2=fnit2.next();
 157           if (secondpart.contains(fn2)) {
 158             insidenode=true;
 159           } else {
 160             outsidenode=true;
 161           }
 162           if (outsidenode&&insidenode) {
 163             liveset.add(tmp);
 164             break;
 165           }
 166         }
 167       }
 168     }
 169     return liveset;
 170   }
 171
 172   //This method computes which temps are live out of the second part
 173   public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
 174     MethodDescriptor md=lb.getMethod();
 175     FlatMethod fm=state.getMethodFlat(md);
 176     Set<FlatNode> exits=faen.getExits();
 177     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 178     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm);
 179
 180     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 181
 182     Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
 183     secondpart.retainAll(atomicnodes);
 184
 185     Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
 186     //Have list of all live temps
 187
 188     for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
 189       FlatNode fn=fnit.next();
 190       Set<TempDescriptor> tempset=livemap.get(fn);
 191       Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
 192       //Look for reaching defs for all live variables that are in the secondpart
 193
 194       for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
 195         TempDescriptor tmp=tmpit.next();
 196         Set<FlatNode> fnset=reachmap.get(tmp);
 197         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 198           FlatNode fn2=fnit2.next();
 199           if (secondpart.contains(fn2)) {
 200             liveset.add(tmp);
 201             break;
 202           }
 203         }
 204       }
 205     }
 206     return liveset;
 207   }
 208
 209   //This method computes which nodes from the first part of the
 210   //transaction must store their output for the second part
 211   //Note that many nodes don't need to...
 212
 213   public Set<FlatNode> livecode(LocalityBinding lb) {
 214     if (!othermap.containsKey(lb))
 215       return null;
 216     HashSet<FlatNode> delayedset=notreadymap.get(lb);
 217     MethodDescriptor md=lb.getMethod();
 218     FlatMethod fm=state.getMethodFlat(md);
 219     Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
 220
 221     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 222     toanalyze.add(fm);
 223
 224     HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
 225
 226     while(!toanalyze.isEmpty()) {
 227       FlatNode fn=toanalyze.iterator().next();
 228       toanalyze.remove(fn);
 229       Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
 230
 231       //Don't process non-atomic nodes
 232       if (locality.getAtomic(lb).get(fn).intValue()==0) {
 233         if (!map.containsKey(fn)) {
 234           map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
 235           //enqueue next nodes
 236           for(int i=0;i<fn.numNext();i++)
 237             toanalyze.add(fn.getNext(i));
 238         }
 239         continue;
 240       }
 241
 242       //Do merge on incoming edges
 243       for(int i=0;i<fn.numPrev();i++) {
 244         FlatNode fnprev=fn.getPrev(i);
 245         Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
 246         if (prevmap!=null)
 247           for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 248             TempDescriptor tmp=tmpit.next();
 249             if (!tmptofn.containsKey(tmp))
 250               tmptofn.put(tmp, new HashSet<FlatNode>());
 251             tmptofn.get(tmp).addAll(prevmap.get(tmp));
 252           }
 253       }
 254
 255       if (delayedset.contains(fn)) {
 256         //Check our readset
 257         TempDescriptor readset[]=fn.readsTemps();
 258         for(int i=0;i<readset.length;i++) {
 259           TempDescriptor tmp=readset[i];
 260           if (tmptofn.containsKey(tmp))
 261             livenodes.addAll(tmptofn.get(tmp)); // add live nodes
 262         }
 263
 264         //Do kills
 265         TempDescriptor writeset[]=fn.writesTemps();
 266         for(int i=0;i<writeset.length;i++) {
 267           TempDescriptor tmp=writeset[i];
 268           tmptofn.remove(tmp);
 269         }
 270       } else {
 271         //We write -- our reads are done
 272         TempDescriptor writeset[]=fn.writesTemps();
 273         for(int i=0;i<writeset.length;i++) {
 274           TempDescriptor tmp=writeset[i];
 275           HashSet<FlatNode> set=new HashSet<FlatNode>();
 276           tmptofn.put(tmp,set);
 277           set.add(fn);
 278         }
 279         if (fn.numNext()>1) {
 280           //We have a conditional branch...need to handle this carefully
 281           Set<FlatNode> set0=getNext(fn, 0, delayedset);
 282           Set<FlatNode> set1=getNext(fn, 1, delayedset);
 283           if (!set0.equals(set1)||set0.size()>1) {
 284             //This branch is important--need to remember how it goes
 285             livenodes.add(fn);
 286           }
 287         }
 288       }
 289       if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
 290         map.put(fn, tmptofn);
 291         //enqueue next ndoes
 292         for(int i=0;i<fn.numNext();i++)
 293           toanalyze.add(fn.getNext(i));
 294       }
 295     }
 296     return livenodes;
 297   }
 298
 299   //Returns null if more than one possible next
 300
 301   public static Set<FlatNode> getNext(FlatNode fn, int i, HashSet<FlatNode> delayset) {
 302     FlatNode fnnext=fn.getNext(i);
 303     HashSet<FlatNode> reachable=new HashSet<FlatNode>();
 304
 305     if (delayset.contains(fnnext)) {
 306       reachable.add(fnnext);
 307       return reachable;
 308     }
 309     Stack<FlatNode> nodes=new Stack<FlatNode>();
 310     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 311     nodes.push(fnnext);
 312
 313     while(!nodes.isEmpty()) {
 314       FlatNode fn2=nodes.pop();
 315       if (visited.contains(fn2))
 316         continue;
 317       visited.add(fn2);
 318       for (int j=0;j<fn2.numNext();j++) {
 319         FlatNode fn2next=fn2.getNext(j);
 320         if (delayset.contains(fn2next)) {
 321           reachable.add(fn2next);
 322         } else
 323           nodes.push(fn2next);
 324       }
 325     }
 326     return reachable;
 327   }
 328
 329   public void analyzeMethod(LocalityBinding lb) {
 330     MethodDescriptor md=lb.getMethod();
 331     FlatMethod fm=state.getMethodFlat(md);
 332     System.out.println("Analyzing "+md);
 333     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
 334     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 335     if (lb.isAtomic()) {
 336       //We are in a transaction already...
 337       //skip past this method or something
 338       return;
 339     }
 340
 341     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 342     toanalyze.addAll(fm.getNodeSet());
 343
 344     //Build the hashtables
 345     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 346     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 347     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 348     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 349     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 350
 351     //Effect of adding something to nodelay set is to move it up past everything in delay set
 352     //Have to make sure we can do this commute
 353
 354     while(!toanalyze.isEmpty()) {
 355       FlatNode fn=toanalyze.iterator().next();
 356       toanalyze.remove(fn);
 357
 358       boolean isatomic=atomictable.get(fn).intValue()>0;
 359
 360       if (!isatomic)
 361         continue;
 362       boolean isnodelay=false;
 363
 364       /* Compute incoming nodelay sets */
 365       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
 366       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
 367       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
 368       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
 369       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
 370       for(int i=0;i<fn.numNext();i++) {
 371         if (nodelaytemps.containsKey(fn.getNext(i)))
 372           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
 373         //do field/array write sets
 374         if (nodelayfieldswr.containsKey(fn.getNext(i)))
 375           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
 376         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 377           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 378         //do read sets
 379         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
 380           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
 381         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 382           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 383       }
 384
 385       /* Check our temp write set */
 386
 387       TempDescriptor writeset[]=fn.writesTemps();
 388       for(int i=0;i<writeset.length;i++) {
 389         TempDescriptor tmp=writeset[i];
 390         if (nodelaytempset.contains(tmp)) {
 391           //We are writing to a nodelay temp
 392           //Therefore we are nodelay
 393           isnodelay=true;
 394           //Kill temp we wrote to
 395           nodelaytempset.remove(tmp);
 396         }
 397       }
 398
 399       //See if flatnode is definitely no delay
 400       if (fn.kind()==FKind.FlatCall) {
 401         isnodelay=true;
 402         //Have to deal with fields/arrays
 403         FlatCall fcall=(FlatCall)fn;
 404         MethodDescriptor mdcall=fcall.getMethod();
 405         nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 406         nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 407         //Have to deal with field/array reads
 408         nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 409         nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 410       }
 411
 412       // Can't delay branches
 413       if (fn.kind()==FKind.FlatCondBranch) {
 414         isnodelay=true;
 415       }
 416
 417       //Check for field conflicts
 418       if (fn.kind()==FKind.FlatSetFieldNode) {
 419         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 420         //write conflicts
 421         if (nodelayfieldwrset.contains(fd))
 422           isnodelay=true;
 423         //read
 424         if (nodelayfieldrdset.contains(fd))
 425           isnodelay=true;
 426       }
 427
 428       if (fn.kind()==FKind.FlatFieldNode) {
 429         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 430         //write conflicts
 431         if (nodelayfieldwrset.contains(fd))
 432           isnodelay=true;
 433       }
 434
 435       //Check for array conflicts
 436       if (fn.kind()==FKind.FlatSetElementNode) {
 437         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 438         //check for write conflicts
 439         if (nodelayarraywrset.contains(td))
 440           isnodelay=true;
 441         //check for read conflicts
 442         if (nodelayarrayrdset.contains(td))
 443           isnodelay=true;
 444       }
 445       if (fn.kind()==FKind.FlatElementNode) {
 446         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 447         //check for write conflicts
 448         if (nodelayarraywrset.contains(td))
 449           isnodelay=true;
 450       }
 451
 452       //If we are no delay, then the temps we read are no delay
 453       if (isnodelay) {
 454         /* Add our read set */
 455         TempDescriptor readset[]=fn.readsTemps();
 456         for(int i=0;i<readset.length;i++) {
 457           TempDescriptor tmp=readset[i];
 458           nodelaytempset.add(tmp);
 459         }
 460         cannotdelay.add(fn);
 461
 462         /* Do we write to fields */
 463         if (fn.kind()==FKind.FlatSetFieldNode) {
 464           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 465         }
 466         /* Do we read from fields */
 467         if (fn.kind()==FKind.FlatFieldNode) {
 468           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 469         }
 470
 471         /* Do we write to arrays */
 472         if (fn.kind()==FKind.FlatSetElementNode) {
 473           //have to do expansion
 474           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 475         }
 476         /* Do we read from arrays */
 477         if (fn.kind()==FKind.FlatElementNode) {
 478           //have to do expansion
 479           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 480         }
 481       } else {
 482         //Need to know which objects to lock on
 483         switch(fn.kind()) {
 484         case FKind.FlatSetFieldNode: {
 485           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 486           nodelaytempset.add(fsfn.getDst());
 487           break;
 488         }
 489         case FKind.FlatSetElementNode: {
 490           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 491           nodelaytempset.add(fsen.getDst());
 492           break;
 493         }
 494         case FKind.FlatFieldNode: {
 495           FlatFieldNode ffn=(FlatFieldNode)fn;
 496           nodelaytempset.add(ffn.getSrc());
 497           break;
 498         }
 499         case FKind.FlatElementNode: {
 500           FlatElementNode fen=(FlatElementNode)fn;
 501           nodelaytempset.add(fen.getSrc());
 502           break;
 503         }
 504         }
 505       }
 506
 507       boolean changed=false;
 508       //See if we need to propagate changes
 509       if (!nodelaytemps.containsKey(fn)||
 510           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 511         nodelaytemps.put(fn, nodelaytempset);
 512         changed=true;
 513       }
 514
 515       //See if we need to propagate changes
 516       if (!nodelayfieldswr.containsKey(fn)||
 517           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 518         nodelayfieldswr.put(fn, nodelayfieldwrset);
 519         changed=true;
 520       }
 521
 522       //See if we need to propagate changes
 523       if (!nodelayfieldsrd.containsKey(fn)||
 524           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 525         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 526         changed=true;
 527       }
 528
 529       //See if we need to propagate changes
 530       if (!nodelayarrayswr.containsKey(fn)||
 531           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 532         nodelayarrayswr.put(fn, nodelayarraywrset);
 533         changed=true;
 534       }
 535
 536       //See if we need to propagate changes
 537       if (!nodelayarraysrd.containsKey(fn)||
 538           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 539         nodelayarraysrd.put(fn, nodelayarrayrdset);
 540         changed=true;
 541       }
 542
 543       if (changed)
 544         for(int i=0;i<fn.numPrev();i++)
 545           toanalyze.add(fn.getPrev(i));
 546     }//end of while loop
 547     HashSet<FlatNode> notreadyset=computeNotReadySet(lb, cannotdelay);
 548     HashSet<FlatNode> otherset=new HashSet<FlatNode>();
 549     otherset.addAll(fm.getNodeSet());
 550     if (lb.getHasAtomic()) {
 551       otherset.removeAll(notreadyset);
 552       otherset.removeAll(cannotdelay);
 553       notreadymap.put(lb, notreadyset);
 554       cannotdelaymap.put(lb, cannotdelay);
 555       othermap.put(lb, otherset);
 556     }
 557
 558     //We now have:
 559     //(1) Cannot delay set -- stuff that must be done before commit
 560     //(2) Not ready set -- stuff that must wait until commit
 561     //(3) everything else -- stuff that should be done before commit
 562   } //end of method
 563
 564   //Problems:
 565   //1) we acquire locks too early to object we don't need to yet
 566   //2) we don't realize that certain operations have side effects
 567
 568   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 569     //You are in not ready set if:
 570     //I. You read a not ready temp
 571     //II. You access a field or element and
 572     //(A). You are not in the cannot delay set
 573     //(B). You read a field/element in the transactional set
 574     //(C). The source didn't have a transactional read on it
 575
 576     dcopts=new DiscoverConflicts(locality, state, typeanalysis, cannotdelay);
 577     dcopts.doAnalysis();
 578     MethodDescriptor md=lb.getMethod();
 579     FlatMethod fm=state.getMethodFlat(md);
 580     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 581
 582     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 583     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 584     toanalyze.addAll(fm.getNodeSet());
 585     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 586
 587     while(!toanalyze.isEmpty()) {
 588       FlatNode fn=toanalyze.iterator().next();
 589       toanalyze.remove(fn);
 590       boolean isatomic=atomictable.get(fn).intValue()>0;
 591
 592       if (!isatomic)
 593         continue;
 594
 595       //Compute initial notready set
 596       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 597       for(int i=0;i<fn.numPrev();i++) {
 598         if (notreadymap.containsKey(fn.getPrev(i)))
 599           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 600       }
 601
 602       //Are we ready
 603       boolean notready=false;
 604
 605       //Test our read set first
 606       TempDescriptor readset[]=fn.readsTemps();
 607       for(int i=0;i<readset.length;i++) {
 608         TempDescriptor tmp=readset[i];
 609         if (notreadyset.contains(tmp)) {
 610           notready=true;
 611           break;
 612         }
 613       }
 614
 615       if (!notready&&!cannotdelay.contains(fn)) {
 616         switch(fn.kind()) {
 617         case FKind.FlatFieldNode: {
 618           FlatFieldNode ffn=(FlatFieldNode)fn;
 619           if (!dcopts.getFields().contains(ffn.getField())) {
 620             break;
 621           }
 622           TempDescriptor tmp=ffn.getSrc();
 623           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 624           if (tfpset!=null) {
 625             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 626               TempFlatPair tfp=tfpit.next();
 627               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 628                 //if a source didn't need a translation and we are
 629                 //accessing it, it did...so therefore we are note
 630                 //ready
 631                 notready=true;
 632                 break;
 633               }
 634             }
 635           }
 636           break;
 637         }
 638         case FKind.FlatSetFieldNode: {
 639           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 640           TempDescriptor tmp=fsfn.getDst();
 641           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 642           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 643
 644           if (tfpset!=null) {
 645             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 646               TempFlatPair tfp=tfpit.next();
 647               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 648                 //if a source didn't need a translation and we are
 649                 //accessing it, it did...so therefore we are note
 650                 //ready
 651                 notready=true;
 652                 break;
 653               }
 654             }
 655           }
 656           break;
 657         }
 658         case FKind.FlatElementNode: {
 659           FlatElementNode fen=(FlatElementNode)fn;
 660           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 661             break;
 662           }
 663           TempDescriptor tmp=fen.getSrc();
 664           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 665           if (tfpset!=null) {
 666             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 667               TempFlatPair tfp=tfpit.next();
 668               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 669                 //if a source didn't need a translation and we are
 670                 //accessing it, it did...so therefore we are note
 671                 //ready
 672                 notready=true;
 673                 break;
 674               }
 675             }
 676           }
 677           break;
 678         }
 679         case FKind.FlatSetElementNode: {
 680           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 681           TempDescriptor tmp=fsen.getDst();
 682           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 683           if (tfpset!=null) {
 684             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 685               TempFlatPair tfp=tfpit.next();
 686               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 687                 //if a source didn't need a translation and we are
 688                 //accessing it, it did...so therefore we are note
 689                 //ready
 690                 notready=true;
 691                 break;
 692               }
 693             }
 694           }
 695           break;
 696         }
 697         }
 698       }
 699
 700       //Fix up things based on our status
 701       if (notready) {
 702         //add us to the list
 703         notreadynodes.add(fn);
 704         //Add our writes
 705         TempDescriptor writeset[]=fn.writesTemps();
 706         for(int i=0;i<writeset.length;i++) {
 707           TempDescriptor tmp=writeset[i];
 708           notreadyset.add(tmp);
 709         }
 710       } else {
 711         //Kill our writes
 712         TempDescriptor writeset[]=fn.writesTemps();
 713         for(int i=0;i<writeset.length;i++) {
 714           TempDescriptor tmp=writeset[i];
 715           notreadyset.remove(tmp);
 716         }
 717       }
 718
 719       //See if we need to propagate changes
 720       if (!notreadymap.containsKey(fn)||
 721           !notreadymap.get(fn).equals(notreadyset)) {
 722         notreadymap.put(fn, notreadyset);
 723         for(int i=0;i<fn.numNext();i++)
 724           toanalyze.add(fn.getNext(i));
 725       }
 726     } //end of while
 727     return notreadynodes;
 728   } //end of computeNotReadySet
 729 } //end of class