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 if (!atomicnodes.contains(fn2)) {
 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     MethodDescriptor md=lb.getMethod();
 252     FlatMethod fm=state.getMethodFlat(md);
 253
 254     HashSet<FlatNode> delayedset=notreadymap.get(lb);
 255     HashSet<FlatNode> otherset=othermap.get(lb);
 256     HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
 257     Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 258     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap);
 259     HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
 260
 261     Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
 262
 263     HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
 264
 265     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 266       FlatNode fn=fnit.next();
 267       if (fn.kind()==FKind.FlatAtomicExitNode) {
 268         Set<TempDescriptor> livetemps=livemap.get(fn);
 269         Hashtable<TempDescriptor, Set<FlatNode>> tempmap=reachingdefsmap.get(fn);
 270         for(Iterator<TempDescriptor> tmpit=livetemps.iterator();tmpit.hasNext();) {
 271           TempDescriptor tmp=tmpit.next();
 272           Set<FlatNode> fnset=tempmap.get(tmp);
 273           boolean inpart1=false;
 274           boolean inpart2=false;
 275           for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 276             FlatNode fn2=fnit2.next();
 277             if (delayedset.contains(fn2)) {
 278               inpart2=true;
 279               if (inpart1)
 280                 break;
 281             } else if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
 282               inpart1=true;
 283               if (inpart2)
 284                 break;
 285             }
 286           }
 287           if (inpart1&&inpart2) {
 288             for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 289               FlatNode fn2=fnit2.next();
 290               if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
 291                 unionset.add(fn2);
 292                 livenodes.add(fn2);
 293               }
 294             }
 295           }
 296         }
 297       }
 298     }
 299
 300     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 301     toanalyze.add(fm);
 302
 303     while(!toanalyze.isEmpty()) {
 304       FlatNode fn=toanalyze.iterator().next();
 305       toanalyze.remove(fn);
 306       Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
 307
 308       //Don't process non-atomic nodes
 309       if (locality.getAtomic(lb).get(fn).intValue()==0) {
 310         if (!map.containsKey(fn)) {
 311           map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
 312           //enqueue next nodes
 313           for(int i=0;i<fn.numNext();i++)
 314             toanalyze.add(fn.getNext(i));
 315         }
 316         continue;
 317       }
 318
 319       //Do merge on incoming edges
 320       for(int i=0;i<fn.numPrev();i++) {
 321         FlatNode fnprev=fn.getPrev(i);
 322         Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
 323         if (prevmap!=null)
 324           for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 325             TempDescriptor tmp=tmpit.next();
 326             if (!tmptofn.containsKey(tmp))
 327               tmptofn.put(tmp, new HashSet<FlatNode>());
 328             tmptofn.get(tmp).addAll(prevmap.get(tmp));
 329           }
 330       }
 331
 332       if (delayedset.contains(fn)) {
 333         //Check our readset
 334         TempDescriptor readset[]=fn.readsTemps();
 335         for(int i=0;i<readset.length;i++) {
 336           TempDescriptor tmp=readset[i];
 337           if (tmptofn.containsKey(tmp)) {
 338             livenodes.addAll(tmptofn.get(tmp)); // add live nodes
 339             unionset.addAll(tmptofn.get(tmp));
 340           }
 341         }
 342
 343         //Do kills
 344         TempDescriptor writeset[]=fn.writesTemps();
 345         for(int i=0;i<writeset.length;i++) {
 346           TempDescriptor tmp=writeset[i];
 347           tmptofn.remove(tmp);
 348         }
 349       } else {
 350         //We write -- our reads are done
 351         TempDescriptor writeset[]=fn.writesTemps();
 352         for(int i=0;i<writeset.length;i++) {
 353           TempDescriptor tmp=writeset[i];
 354           HashSet<FlatNode> set=new HashSet<FlatNode>();
 355           tmptofn.put(tmp,set);
 356           set.add(fn);
 357         }
 358         if (fn.numNext()>1) {
 359           //We have a conditional branch...need to handle this carefully
 360           Set<FlatNode> set0=getNext(fn, 0, unionset, lb, locality, false);
 361           Set<FlatNode> set1=getNext(fn, 1, unionset, lb, locality, false);
 362           if (!set0.equals(set1)||set0.size()>1) {
 363             //This branch is important--need to remember how it goes
 364             livenodes.add(fn);
 365             unionset.add(fn);
 366           }
 367         }
 368       }
 369       if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
 370         map.put(fn, tmptofn);
 371         //enqueue next ndoes
 372         for(int i=0;i<fn.numNext();i++)
 373           toanalyze.add(fn.getNext(i));
 374       }
 375     }
 376     return livenodes;
 377   }
 378
 379   public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
 380     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 381     FlatNode fnnext=fn.getNext(i);
 382     HashSet<FlatNode> reachable=new HashSet<FlatNode>();
 383
 384     if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
 385       reachable.add(fnnext);
 386       return reachable;
 387     }
 388     Stack<FlatNode> nodes=new Stack<FlatNode>();
 389     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 390     nodes.push(fnnext);
 391     if (contpastnode)
 392       visited.add(fn);
 393
 394     while(!nodes.isEmpty()) {
 395       FlatNode fn2=nodes.pop();
 396       if (visited.contains(fn2))
 397         continue;
 398       visited.add(fn2);
 399       for (int j=0;j<fn2.numNext();j++) {
 400         FlatNode fn2next=fn2.getNext(j);
 401         if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
 402           reachable.add(fn2next);
 403         } else
 404           nodes.push(fn2next);
 405       }
 406     }
 407     return reachable;
 408   }
 409
 410   public void analyzeMethod(LocalityBinding lb) {
 411     MethodDescriptor md=lb.getMethod();
 412     FlatMethod fm=state.getMethodFlat(md);
 413     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
 414     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 415     if (lb.isAtomic()) {
 416       //We are in a transaction already...
 417       //skip past this method or something
 418       return;
 419     }
 420
 421     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 422     toanalyze.addAll(fm.getNodeSet());
 423
 424     //Build the hashtables
 425     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 426     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 427     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 428     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 429     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 430
 431     //Effect of adding something to nodelay set is to move it up past everything in delay set
 432     //Have to make sure we can do this commute
 433
 434     while(!toanalyze.isEmpty()) {
 435       FlatNode fn=toanalyze.iterator().next();
 436       toanalyze.remove(fn);
 437
 438       boolean isatomic=atomictable.get(fn).intValue()>0;
 439
 440       if (!isatomic)
 441         continue;
 442       boolean isnodelay=false;
 443
 444       /* Compute incoming nodelay sets */
 445       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
 446       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
 447       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
 448       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
 449       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
 450       for(int i=0;i<fn.numNext();i++) {
 451         if (nodelaytemps.containsKey(fn.getNext(i)))
 452           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
 453         //do field/array write sets
 454         if (nodelayfieldswr.containsKey(fn.getNext(i)))
 455           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
 456         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 457           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 458         //do read sets
 459         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
 460           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
 461         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 462           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 463       }
 464
 465       /* Check our temp write set */
 466
 467       TempDescriptor writeset[]=fn.writesTemps();
 468       for(int i=0;i<writeset.length;i++) {
 469         TempDescriptor tmp=writeset[i];
 470         if (nodelaytempset.contains(tmp)) {
 471           //We are writing to a nodelay temp
 472           //Therefore we are nodelay
 473           isnodelay=true;
 474           //Kill temp we wrote to
 475           nodelaytempset.remove(tmp);
 476         }
 477       }
 478
 479       //See if flatnode is definitely no delay
 480       if (fn.kind()==FKind.FlatCall) {
 481         isnodelay=true;
 482         //Have to deal with fields/arrays
 483         FlatCall fcall=(FlatCall)fn;
 484         MethodDescriptor mdcall=fcall.getMethod();
 485         nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 486         nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 487         //Have to deal with field/array reads
 488         nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 489         nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 490       }
 491
 492       //Delay branches if possible
 493       if (fn.kind()==FKind.FlatCondBranch) {
 494         Set<FlatNode> leftset=getNext(fn, 0, cannotdelay, lb, locality,true);
 495         Set<FlatNode> rightset=getNext(fn, 1, cannotdelay, lb, locality,true);
 496         if (leftset.size()>0&&rightset.size()>0&&
 497             !leftset.equals(rightset)||leftset.size()>1)
 498           isnodelay=true;
 499       }
 500
 501       //Check for field conflicts
 502       if (fn.kind()==FKind.FlatSetFieldNode) {
 503         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 504         //write conflicts
 505         if (nodelayfieldwrset.contains(fd))
 506           isnodelay=true;
 507         //read
 508         if (nodelayfieldrdset.contains(fd))
 509           isnodelay=true;
 510       }
 511
 512       if (fn.kind()==FKind.FlatFieldNode) {
 513         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 514         //write conflicts
 515         if (nodelayfieldwrset.contains(fd))
 516           isnodelay=true;
 517       }
 518
 519       //Check for array conflicts
 520       if (fn.kind()==FKind.FlatSetElementNode) {
 521         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 522         //check for write conflicts
 523         if (nodelayarraywrset.contains(td))
 524           isnodelay=true;
 525         //check for read conflicts
 526         if (nodelayarrayrdset.contains(td))
 527           isnodelay=true;
 528       }
 529       if (fn.kind()==FKind.FlatElementNode) {
 530         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 531         //check for write conflicts
 532         if (nodelayarraywrset.contains(td))
 533           isnodelay=true;
 534       }
 535
 536       //If we are no delay, then the temps we read are no delay
 537       if (isnodelay) {
 538         /* Add our read set */
 539         TempDescriptor readset[]=fn.readsTemps();
 540         for(int i=0;i<readset.length;i++) {
 541           TempDescriptor tmp=readset[i];
 542           nodelaytempset.add(tmp);
 543         }
 544         cannotdelay.add(fn);
 545
 546         /* Do we write to fields */
 547         if (fn.kind()==FKind.FlatSetFieldNode) {
 548           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 549         }
 550         /* Do we read from fields */
 551         if (fn.kind()==FKind.FlatFieldNode) {
 552           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 553         }
 554
 555         /* Do we write to arrays */
 556         if (fn.kind()==FKind.FlatSetElementNode) {
 557           //have to do expansion
 558           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 559         }
 560         /* Do we read from arrays */
 561         if (fn.kind()==FKind.FlatElementNode) {
 562           //have to do expansion
 563           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 564         }
 565       } else {
 566         //Need to know which objects to lock on
 567         switch(fn.kind()) {
 568         case FKind.FlatSetFieldNode: {
 569           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 570           nodelaytempset.add(fsfn.getDst());
 571           break;
 572         }
 573         case FKind.FlatSetElementNode: {
 574           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 575           nodelaytempset.add(fsen.getDst());
 576           break;
 577         }
 578         case FKind.FlatFieldNode: {
 579           FlatFieldNode ffn=(FlatFieldNode)fn;
 580           nodelaytempset.add(ffn.getSrc());
 581           break;
 582         }
 583         case FKind.FlatElementNode: {
 584           FlatElementNode fen=(FlatElementNode)fn;
 585           nodelaytempset.add(fen.getSrc());
 586           break;
 587         }
 588         }
 589       }
 590
 591       boolean changed=false;
 592       //See if we need to propagate changes
 593       if (!nodelaytemps.containsKey(fn)||
 594           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 595         nodelaytemps.put(fn, nodelaytempset);
 596         changed=true;
 597       }
 598
 599       //See if we need to propagate changes
 600       if (!nodelayfieldswr.containsKey(fn)||
 601           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 602         nodelayfieldswr.put(fn, nodelayfieldwrset);
 603         changed=true;
 604       }
 605
 606       //See if we need to propagate changes
 607       if (!nodelayfieldsrd.containsKey(fn)||
 608           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 609         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 610         changed=true;
 611       }
 612
 613       //See if we need to propagate changes
 614       if (!nodelayarrayswr.containsKey(fn)||
 615           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 616         nodelayarrayswr.put(fn, nodelayarraywrset);
 617         changed=true;
 618       }
 619
 620       //See if we need to propagate changes
 621       if (!nodelayarraysrd.containsKey(fn)||
 622           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 623         nodelayarraysrd.put(fn, nodelayarrayrdset);
 624         changed=true;
 625       }
 626
 627       if (changed)
 628         for(int i=0;i<fn.numPrev();i++)
 629           toanalyze.add(fn.getPrev(i));
 630     }//end of while loop
 631
 632     if (lb.getHasAtomic()) {
 633       cannotdelaymap.put(lb, cannotdelay);
 634     }
 635   } //end of method
 636
 637   //Problems:
 638   //1) we acquire locks too early to object we don't need to yet
 639   //2) we don't realize that certain operations have side effects
 640
 641   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 642     //You are in not ready set if:
 643     //I. You read a not ready temp
 644     //II. You access a field or element and
 645     //(A). You are not in the cannot delay set
 646     //(B). You read a field/element in the transactional set
 647     //(C). The source didn't have a transactional read on it
 648
 649     MethodDescriptor md=lb.getMethod();
 650     FlatMethod fm=state.getMethodFlat(md);
 651     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 652
 653     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 654     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 655     toanalyze.addAll(fm.getNodeSet());
 656     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 657
 658     while(!toanalyze.isEmpty()) {
 659       FlatNode fn=toanalyze.iterator().next();
 660       toanalyze.remove(fn);
 661       boolean isatomic=atomictable.get(fn).intValue()>0;
 662
 663       if (!isatomic)
 664         continue;
 665
 666       //Compute initial notready set
 667       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 668       for(int i=0;i<fn.numPrev();i++) {
 669         if (notreadymap.containsKey(fn.getPrev(i)))
 670           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 671       }
 672
 673       //Are we ready
 674       boolean notready=false;
 675
 676       //Test our read set first
 677       TempDescriptor readset[]=fn.readsTemps();
 678       for(int i=0;i<readset.length;i++) {
 679         TempDescriptor tmp=readset[i];
 680         if (notreadyset.contains(tmp)) {
 681           notready=true;
 682           break;
 683         }
 684       }
 685
 686       if (!notready&&!cannotdelay.contains(fn)) {
 687         switch(fn.kind()) {
 688         case FKind.FlatFieldNode: {
 689           FlatFieldNode ffn=(FlatFieldNode)fn;
 690           if (!dcopts.getFields().contains(ffn.getField())) {
 691             break;
 692           }
 693           TempDescriptor tmp=ffn.getSrc();
 694           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 695           if (tfpset!=null) {
 696             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 697               TempFlatPair tfp=tfpit.next();
 698               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 699                 //if a source didn't need a translation and we are
 700                 //accessing it, it did...so therefore we are note
 701                 //ready
 702                 notready=true;
 703                 break;
 704               }
 705             }
 706           }
 707           break;
 708         }
 709         case FKind.FlatSetFieldNode: {
 710           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 711           TempDescriptor tmp=fsfn.getDst();
 712           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 713           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 714
 715           if (tfpset!=null) {
 716             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 717               TempFlatPair tfp=tfpit.next();
 718               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 719                 //if a source didn't need a translation and we are
 720                 //accessing it, it did...so therefore we are note
 721                 //ready
 722                 notready=true;
 723                 break;
 724               }
 725             }
 726           }
 727           break;
 728         }
 729         case FKind.FlatElementNode: {
 730           FlatElementNode fen=(FlatElementNode)fn;
 731           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 732             break;
 733           }
 734           TempDescriptor tmp=fen.getSrc();
 735           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 736           if (tfpset!=null) {
 737             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 738               TempFlatPair tfp=tfpit.next();
 739               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 740                 //if a source didn't need a translation and we are
 741                 //accessing it, it did...so therefore we are note
 742                 //ready
 743                 notready=true;
 744                 break;
 745               }
 746             }
 747           }
 748           break;
 749         }
 750         case FKind.FlatSetElementNode: {
 751           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 752           TempDescriptor tmp=fsen.getDst();
 753           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 754           if (tfpset!=null) {
 755             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 756               TempFlatPair tfp=tfpit.next();
 757               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 758                 //if a source didn't need a translation and we are
 759                 //accessing it, it did...so therefore we are note
 760                 //ready
 761                 notready=true;
 762                 break;
 763               }
 764             }
 765           }
 766           break;
 767         }
 768         }
 769       }
 770
 771       //Fix up things based on our status
 772       if (notready) {
 773         //add us to the list
 774         notreadynodes.add(fn);
 775         //Add our writes
 776         TempDescriptor writeset[]=fn.writesTemps();
 777         for(int i=0;i<writeset.length;i++) {
 778           TempDescriptor tmp=writeset[i];
 779           notreadyset.add(tmp);
 780         }
 781       } else {
 782         //Kill our writes
 783         TempDescriptor writeset[]=fn.writesTemps();
 784         for(int i=0;i<writeset.length;i++) {
 785           TempDescriptor tmp=writeset[i];
 786           notreadyset.remove(tmp);
 787         }
 788       }
 789
 790       //See if we need to propagate changes
 791       if (!notreadymap.containsKey(fn)||
 792           !notreadymap.get(fn).equals(notreadyset)) {
 793         notreadymap.put(fn, notreadyset);
 794         for(int i=0;i<fn.numNext();i++)
 795           toanalyze.add(fn.getNext(i));
 796       }
 797     } //end of while
 798     return notreadynodes;
 799   } //end of computeNotReadySet
 800 } //end of class