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