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