Robust/src/Analysis/Locality/DelayComputation.java

   1 package Analysis.Locality;
   2 import Analysis.Liveness;
   3 import Analysis.ReachingDefs;
   4 import Analysis.Loops.DomTree;
   5 import IR.State;
   6 import IR.MethodDescriptor;
   7 import IR.TypeDescriptor;
   8 import IR.FieldDescriptor;
   9 import IR.Flat.*;
  10 import Analysis.Loops.GlobalFieldType;
  11 import java.util.HashSet;
  12 import java.util.Hashtable;
  13 import java.util.Set;
  14 import java.util.List;
  15 import java.util.Arrays;
  16 import java.util.Stack;
  17 import java.util.Iterator;
  18
  19 public class DelayComputation {
  20   State state;
  21   LocalityAnalysis locality;
  22   TypeAnalysis typeanalysis;
  23   GlobalFieldType gft;
  24   DiscoverConflicts dcopts;
  25   Hashtable<LocalityBinding, HashSet<FlatNode>> notreadymap;
  26   Hashtable<LocalityBinding, HashSet<FlatNode>> cannotdelaymap;
  27   Hashtable<LocalityBinding, HashSet<FlatNode>> derefmap;
  28   Hashtable<LocalityBinding, HashSet<FlatNode>> othermap;
  29
  30   public DelayComputation(LocalityAnalysis locality, State state, TypeAnalysis typeanalysis, GlobalFieldType gft) {
  31     this.locality=locality;
  32     this.state=state;
  33     this.typeanalysis=typeanalysis;
  34     this.gft=gft;
  35     this.notreadymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  36     this.cannotdelaymap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  37     if (state.STMARRAY)
  38       this.derefmap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  39     this.othermap=new Hashtable<LocalityBinding, HashSet<FlatNode>>();
  40   }
  41
  42   public DiscoverConflicts getConflicts() {
  43     return dcopts;
  44   }
  45
  46   public Hashtable<LocalityBinding, HashSet<FlatNode>> getCannotDelayMap() {
  47     return cannotdelaymap;
  48   }
  49
  50
  51   public HashSet<FlatNode> getDeref(LocalityBinding lb) {
  52     return derefmap.get(lb);
  53   }
  54
  55   public void doAnalysis() {
  56     //first dcopts...use to figure out what we need to lock
  57     dcopts=new DiscoverConflicts(locality, state, typeanalysis, null);
  58     dcopts.doAnalysis();
  59
  60     //compute cannotdelaymap
  61     Set<LocalityBinding> localityset=locality.getLocalityBindings();
  62     for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
  63       analyzeMethod(lbit.next());
  64     }
  65
  66     //ignore things that aren't in the map
  67     dcopts=new DiscoverConflicts(locality, state, typeanalysis, cannotdelaymap, false, false, state.READSET?gft:null);
  68     dcopts.doAnalysis();
  69
  70
  71     for(Iterator<LocalityBinding> lbit=localityset.iterator();lbit.hasNext();) {
  72       LocalityBinding lb=lbit.next();
  73
  74       MethodDescriptor md=lb.getMethod();
  75       FlatMethod fm=state.getMethodFlat(md);
  76       if (lb.isAtomic())
  77         continue;
  78
  79       if (lb.getHasAtomic()) {
  80         HashSet<FlatNode> cannotdelay=cannotdelaymap.get(lb);
  81         HashSet<FlatNode> notreadyset=computeNotReadySet(lb, cannotdelay);
  82         HashSet<FlatNode> otherset=new HashSet<FlatNode>();
  83         otherset.addAll(fm.getNodeSet());
  84         otherset.removeAll(notreadyset);
  85         otherset.removeAll(cannotdelay);
  86         if (state.MINIMIZE) {
  87           Hashtable<FlatNode, Integer> atomicmap=locality.getAtomic(lb);
  88           for(Iterator<FlatNode> fnit=otherset.iterator();fnit.hasNext();) {
  89             FlatNode fn=fnit.next();
  90             if (atomicmap.get(fn).intValue()>0&&
  91                 fn.kind()!=FKind.FlatAtomicEnterNode&&
  92                 fn.kind()!=FKind.FlatGlobalConvNode) {
  93               //remove non-atomic flatnodes
  94               fnit.remove();
  95               notreadyset.add(fn);
  96             }
  97           }
  98         }
  99
 100         notreadymap.put(lb, notreadyset);
 101         othermap.put(lb, otherset);
 102       }
 103
 104       //We now have:
 105       //(1) Cannot delay set -- stuff that must be done before commit
 106       //(2) Not ready set -- stuff that must wait until commit
 107       //(3) everything else -- stuff that should be done before commit
 108     }
 109   }
 110
 111   public HashSet<FlatNode> getNotReady(LocalityBinding lb) {
 112     return notreadymap.get(lb);
 113   }
 114
 115   public HashSet<FlatNode> getCannotDelay(LocalityBinding lb) {
 116     return cannotdelaymap.get(lb);
 117   }
 118
 119   public HashSet<FlatNode> getOther(LocalityBinding lb) {
 120     return othermap.get(lb);
 121   }
 122
 123   //This method computes which temps are live into the second part
 124   public Set<TempDescriptor> alltemps(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
 125     MethodDescriptor md=lb.getMethod();
 126     FlatMethod fm=state.getMethodFlat(md);
 127     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 128
 129     //Compute second part set of nodes
 130     Set<FlatNode> secondpart=new HashSet<FlatNode>();
 131     secondpart.addAll(getNotReady(lb));
 132     secondpart.addAll(recordset);
 133
 134     //make it just this transaction
 135     secondpart.retainAll(atomicnodes);
 136
 137     HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
 138
 139     for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
 140       FlatNode fn=fnit.next();
 141       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
 142       tempset.addAll(writes);
 143       if (!recordset.contains(fn)) {
 144         List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 145         tempset.addAll(reads);
 146       }
 147     }
 148
 149     return tempset;
 150   }
 151
 152   //This method computes which temps are live into the second part
 153   public Set<TempDescriptor> liveinto(LocalityBinding lb, FlatAtomicEnterNode faen, Set<FlatNode> recordset) {
 154     MethodDescriptor md=lb.getMethod();
 155     FlatMethod fm=state.getMethodFlat(md);
 156     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 157
 158     //Compute second part set of nodes
 159     Set<FlatNode> secondpart=new HashSet<FlatNode>();
 160     secondpart.addAll(getNotReady(lb));
 161     secondpart.addAll(recordset);
 162
 163     //make it just this transaction
 164     secondpart.retainAll(atomicnodes);
 165
 166     Set<TempDescriptor> liveinto=new HashSet<TempDescriptor>();
 167
 168     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
 169
 170     for(Iterator<FlatNode> fnit=secondpart.iterator();fnit.hasNext();) {
 171       FlatNode fn=fnit.next();
 172       if (recordset.contains(fn))
 173         continue;
 174       TempDescriptor readset[]=fn.readsTemps();
 175       for(int i=0;i<readset.length;i++) {
 176         TempDescriptor rtmp=readset[i];
 177         Set<FlatNode> fnset=reachingdefs.get(fn).get(rtmp);
 178         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 179           FlatNode fn2=fnit2.next();
 180           if (secondpart.contains(fn2))
 181             continue;
 182           //otherwise we mark this as live in
 183           liveinto.add(rtmp);
 184           break;
 185         }
 186       }
 187     }
 188     return liveinto;
 189   }
 190
 191   //This method computes which temps are live out of the second part
 192   public Set<TempDescriptor> liveoutvirtualread(LocalityBinding lb, FlatAtomicEnterNode faen) {
 193     MethodDescriptor md=lb.getMethod();
 194     FlatMethod fm=state.getMethodFlat(md);
 195     Set<FlatNode> exits=faen.getExits();
 196     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 197     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, Liveness.computeLiveTemps(fm), true);
 198
 199     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 200
 201     Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
 202     secondpart.retainAll(atomicnodes);
 203
 204     Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
 205     //Have list of all live temps
 206
 207     for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
 208       FlatNode fn=fnit.next();
 209       Set<TempDescriptor> tempset=livemap.get(fn);
 210       Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
 211       //Look for reaching defs for all live variables that are in the secondpart
 212
 213       for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
 214         TempDescriptor tmp=tmpit.next();
 215         Set<FlatNode> fnset=reachmap.get(tmp);
 216         boolean outsidenode=false;
 217         boolean insidenode=false;
 218
 219         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 220           FlatNode fn2=fnit2.next();
 221           if (secondpart.contains(fn2)) {
 222             insidenode=true;
 223           } else if (!atomicnodes.contains(fn2)) {
 224             outsidenode=true;
 225           }
 226           if (outsidenode&&insidenode) {
 227             liveset.add(tmp);
 228             break;
 229           }
 230         }
 231       }
 232     }
 233     return liveset;
 234   }
 235
 236   //This method computes which temps are live out of the second part
 237   public Set<TempDescriptor> liveout(LocalityBinding lb, FlatAtomicEnterNode faen) {
 238     MethodDescriptor md=lb.getMethod();
 239     FlatMethod fm=state.getMethodFlat(md);
 240     Set<FlatNode> exits=faen.getExits();
 241     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 242     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefs=ReachingDefs.computeReachingDefs(fm, livemap, true);
 243
 244     Set<FlatNode> atomicnodes=faen.getReachableSet(faen.getExits());
 245
 246     Set<FlatNode> secondpart=new HashSet<FlatNode>(getNotReady(lb));
 247     secondpart.retainAll(atomicnodes);
 248
 249     Set<TempDescriptor> liveset=new HashSet<TempDescriptor>();
 250     //Have list of all live temps
 251
 252     for(Iterator<FlatNode> fnit=exits.iterator();fnit.hasNext();) {
 253       FlatNode fn=fnit.next();
 254       Set<TempDescriptor> tempset=livemap.get(fn);
 255       Hashtable<TempDescriptor, Set<FlatNode>> reachmap=reachingdefs.get(fn);
 256       //Look for reaching defs for all live variables that are in the secondpart
 257
 258       for(Iterator<TempDescriptor> tmpit=tempset.iterator();tmpit.hasNext();) {
 259         TempDescriptor tmp=tmpit.next();
 260         Set<FlatNode> fnset=reachmap.get(tmp);
 261         if (fnset==null) {
 262           System.out.println("null temp set for"+fn+" tmp="+tmp);
 263           System.out.println(fm.printMethod());
 264         }
 265         for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 266           FlatNode fn2=fnit2.next();
 267           if (secondpart.contains(fn2)) {
 268             liveset.add(tmp);
 269             break;
 270           }
 271         }
 272       }
 273     }
 274     return liveset;
 275   }
 276
 277   //This method computes which nodes from the first part of the
 278   //transaction must store their output for the second part
 279   //Note that many nodes don't need to...
 280
 281   public Set<FlatNode> livecode(LocalityBinding lb) {
 282     if (!othermap.containsKey(lb))
 283       return null;
 284     MethodDescriptor md=lb.getMethod();
 285     FlatMethod fm=state.getMethodFlat(md);
 286
 287     HashSet<FlatNode> delayedset=notreadymap.get(lb);
 288     HashSet<FlatNode> derefset=derefmap.get(lb);
 289     HashSet<FlatNode> otherset=othermap.get(lb);
 290     HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
 291     Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 292     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true);
 293     HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
 294     Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
 295     HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
 296     Hashtable<FlatCondBranch, Set<FlatNode>> branchmap=revGetBranchSet(lb);
 297
 298     //Here we check for temps that are live out on the transaction...
 299     //If both parts can contribute to the temp, then we need to do
 300     //reads to make sure that liveout set has the right values
 301
 302     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 303       FlatNode fn=fnit.next();
 304       if (fn.kind()==FKind.FlatAtomicExitNode) {
 305         Set<TempDescriptor> livetemps=livemap.get(fn);
 306         Hashtable<TempDescriptor, Set<FlatNode>> tempmap=reachingdefsmap.get(fn);
 307
 308         //Iterate over the temps that are live into this node
 309         for(Iterator<TempDescriptor> tmpit=livetemps.iterator();tmpit.hasNext();) {
 310           TempDescriptor tmp=tmpit.next();
 311           Set<FlatNode> fnset=tempmap.get(tmp);
 312           boolean inpart1=false;
 313           boolean inpart2=false;
 314
 315           //iterate over the reaching definitions for the temp
 316           for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 317             FlatNode fn2=fnit2.next();
 318             if (delayedset.contains(fn2)) {
 319               inpart2=true;
 320               if (inpart1)
 321                 break;
 322             } else if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
 323               inpart1=true;
 324               if (inpart2)
 325                 break;
 326             }
 327           }
 328           if (inpart1&&inpart2) {
 329             for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 330               FlatNode fn2=fnit2.next();
 331               if ((otherset.contains(fn2)||cannotdelayset.contains(fn2))&&
 332                   locality.getAtomic(lb).get(fn2).intValue()>0) {
 333                 unionset.add(fn2);
 334                 livenodes.add(fn2);
 335               }
 336             }
 337           }
 338         }
 339       }
 340     }
 341
 342     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 343     toanalyze.add(fm);
 344
 345     while(!toanalyze.isEmpty()) {
 346       FlatNode fn=toanalyze.iterator().next();
 347       toanalyze.remove(fn);
 348       Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
 349
 350       //Don't process non-atomic nodes
 351       if (locality.getAtomic(lb).get(fn).intValue()==0) {
 352         if (!map.containsKey(fn)) {
 353           map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
 354           //enqueue next nodes
 355           for(int i=0;i<fn.numNext();i++)
 356             toanalyze.add(fn.getNext(i));
 357         }
 358         continue;
 359       }
 360
 361       //Do merge on incoming edges
 362       for(int i=0;i<fn.numPrev();i++) {
 363         FlatNode fnprev=fn.getPrev(i);
 364         Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
 365         if (prevmap!=null)
 366           for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 367             TempDescriptor tmp=tmpit.next();
 368             if (!tmptofn.containsKey(tmp))
 369               tmptofn.put(tmp, new HashSet<FlatNode>());
 370             tmptofn.get(tmp).addAll(prevmap.get(tmp));
 371           }
 372       }
 373
 374       if (delayedset.contains(fn)) {
 375         if(state.STMARRAY&&derefset.contains(fn)) {
 376           //FlatElementNodes don't read anything...
 377           if (fn.kind()==FKind.FlatSetElementNode) {
 378             //check only the source read tmp
 379             TempDescriptor tmp=((FlatSetElementNode)fn).getSrc();
 380             if (tmptofn.containsKey(tmp)) {
 381               livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
 382               unionset.addAll(tmptofn.get(tmp));
 383             }
 384           }
 385         } else {
 386           //If the node is in the second set, check our readset
 387           TempDescriptor readset[]=fn.readsTemps();
 388           for(int i=0;i<readset.length;i++) {
 389             TempDescriptor tmp=readset[i];
 390             if (tmptofn.containsKey(tmp)) {
 391               livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
 392               unionset.addAll(tmptofn.get(tmp));
 393             }
 394           }
 395         }
 396         //Do kills
 397         TempDescriptor writeset[]=fn.writesTemps();
 398         for(int i=0;i<writeset.length;i++) {
 399           TempDescriptor tmp=writeset[i];
 400           tmptofn.remove(tmp);
 401         }
 402       } else {
 403         //If the node is in the first set, search over what we write
 404         //We write -- our reads are done
 405         TempDescriptor writeset[]=fn.writesTemps();
 406         for(int i=0;i<writeset.length;i++) {
 407           TempDescriptor tmp=writeset[i];
 408           HashSet<FlatNode> set=new HashSet<FlatNode>();
 409           tmptofn.put(tmp,set);
 410           set.add(fn);
 411         }
 412         if (fn.numNext()>1) {
 413           Set<FlatNode> branchset=branchmap.get((FlatCondBranch)fn);
 414           for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
 415             FlatNode brfn=brit.next();
 416             if (unionset.contains(brfn)) {
 417               //This branch is important--need to remember how it goes
 418               livenodes.add(fn);
 419               unionset.add(fn);
 420             }
 421           }
 422         }
 423       }
 424       if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
 425         map.put(fn, tmptofn);
 426         //enqueue next ndoes
 427         for(int i=0;i<fn.numNext();i++)
 428           toanalyze.add(fn.getNext(i));
 429       }
 430     }
 431     return livenodes;
 432   }
 433
 434   public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
 435     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 436     FlatNode fnnext=fn.getNext(i);
 437     HashSet<FlatNode> reachable=new HashSet<FlatNode>();
 438
 439     if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
 440       reachable.add(fnnext);
 441       return reachable;
 442     }
 443     Stack<FlatNode> nodes=new Stack<FlatNode>();
 444     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 445     nodes.push(fnnext);
 446     if (contpastnode)
 447       visited.add(fn);
 448
 449     while(!nodes.isEmpty()) {
 450       FlatNode fn2=nodes.pop();
 451       if (visited.contains(fn2))
 452         continue;
 453       visited.add(fn2);
 454       for (int j=0;j<fn2.numNext();j++) {
 455         FlatNode fn2next=fn2.getNext(j);
 456         if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
 457           reachable.add(fn2next);
 458         } else
 459           nodes.push(fn2next);
 460       }
 461     }
 462     return reachable;
 463   }
 464
 465   //Computes cannotdelayset---flatnodes that must be evaluated in the
 466   //speculative component.
 467
 468   public void analyzeMethod(LocalityBinding lb) {
 469     MethodDescriptor md=lb.getMethod();
 470     FlatMethod fm=state.getMethodFlat(md);
 471     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
 472     HashSet<FlatNode> derefset=new HashSet<FlatNode>();
 473     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 474     if (lb.isAtomic()) {
 475       //We are in a transaction already...
 476       //skip past this method or something
 477       return;
 478     }
 479
 480     Hashtable<FlatNode, Set<TempDescriptor>> oldtempmap=dcopts.computeOldTemps(lb);
 481
 482     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 483     toanalyze.addAll(fm.getNodeSet());
 484
 485     //Build the hashtables
 486     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 487     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 488     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 489     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 490     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 491
 492     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 493     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 494     //Effect of adding something to nodelay set is to move it up past everything in delay set
 495     //Have to make sure we can do this commute
 496
 497     while(!toanalyze.isEmpty()) {
 498       FlatNode fn=toanalyze.iterator().next();
 499       toanalyze.remove(fn);
 500
 501       boolean isatomic=atomictable.get(fn).intValue()>0;
 502
 503       if (!isatomic)
 504         continue;
 505       boolean isnodelay=false;
 506
 507       /* Compute incoming nodelay sets */
 508       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
 509       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
 510       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
 511       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
 512       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
 513       for(int i=0;i<fn.numNext();i++) {
 514         if (nodelaytemps.containsKey(fn.getNext(i)))
 515           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
 516         //do field/array write sets
 517         if (nodelayfieldswr.containsKey(fn.getNext(i)))
 518           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
 519         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 520           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 521         //do read sets
 522         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
 523           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
 524         if (nodelayarraysrd.containsKey(fn.getNext(i)))
 525           nodelayarrayrdset.addAll(nodelayarraysrd.get(fn.getNext(i)));
 526       }
 527
 528       /* Check our temp write set */
 529
 530       TempDescriptor writeset[]=fn.writesTemps();
 531       for(int i=0;i<writeset.length;i++) {
 532         TempDescriptor tmp=writeset[i];
 533         if (nodelaytempset.contains(tmp)) {
 534           //We are writing to a nodelay temp
 535           //Therefore we are nodelay
 536           isnodelay=true;
 537           //Kill temp we wrote to
 538           nodelaytempset.remove(tmp);
 539         }
 540       }
 541
 542       //See if flatnode is definitely no delay
 543       if (fn.kind()==FKind.FlatCall) {
 544         FlatCall fcall=(FlatCall)fn;
 545         MethodDescriptor mdcall=fcall.getMethod();
 546         if (!mdcall.getClassDesc().getSymbol().equals("System")||
 547             (!mdcall.getSymbol().equals("println")&&!mdcall.getSymbol().equals("printString")))
 548           isnodelay=true;
 549       }
 550
 551       //Delay branches if possible
 552       if (fn.kind()==FKind.FlatCondBranch) {
 553         Set<FlatNode> branchset=revbranchmap.get(lb);
 554         for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
 555           FlatNode branchnode=brit.next();
 556           if (cannotdelay.contains(branchnode)||(state.STMARRAY&&derefset.contains(branchnode))) {
 557             isnodelay=true;
 558             break;
 559           }
 560         }
 561       }
 562
 563       //Check for field conflicts
 564       if (fn.kind()==FKind.FlatSetFieldNode) {
 565         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 566         //write conflicts
 567         if (nodelayfieldwrset.contains(fd))
 568           isnodelay=true;
 569         //read
 570         if (nodelayfieldrdset.contains(fd))
 571           isnodelay=true;
 572       }
 573
 574       if (fn.kind()==FKind.FlatFieldNode) {
 575         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 576         //write conflicts
 577         if (nodelayfieldwrset.contains(fd))
 578           isnodelay=true;
 579       }
 580       //Check for array conflicts
 581       if (fn.kind()==FKind.FlatSetElementNode) {
 582         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 583         //check for write conflicts
 584         if (nodelayarraywrset.contains(td))
 585           isnodelay=true;
 586         //check for read conflicts
 587         if (nodelayarrayrdset.contains(td))
 588           isnodelay=true;
 589       }
 590       if (fn.kind()==FKind.FlatElementNode) {
 591         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 592         //check for write conflicts
 593         if (nodelayarraywrset.contains(td))
 594           isnodelay=true;
 595       }
 596
 597       //If we are no delay, then the temps we read are no delay
 598       if (isnodelay) {
 599         /* Add our read set */
 600         TempDescriptor readset[]=fn.readsTemps();
 601         for(int i=0;i<readset.length;i++) {
 602           TempDescriptor tmp=readset[i];
 603           nodelaytempset.add(tmp);
 604         }
 605         cannotdelay.add(fn);
 606
 607         if (branchmap.containsKey(fn)) {
 608           Set<FlatCondBranch> fcbset=branchmap.get(fn);
 609           for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
 610             FlatCondBranch fcb=fcbit.next();
 611             //enqueue flatcondbranch node for reanalysis
 612             if (cannotdelay.contains(fcb)) {
 613               cannotdelay.add(fcb);
 614               toanalyze.add(fcb);
 615             }
 616           }
 617         }
 618         /* Do we write to fields */
 619         if (fn.kind()==FKind.FlatSetFieldNode) {
 620           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 621         }
 622         /* Do we read from fields */
 623         if (fn.kind()==FKind.FlatFieldNode) {
 624           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 625         }
 626         /* Do we write to arrays */
 627         if (fn.kind()==FKind.FlatSetElementNode) {
 628           //have to do expansion
 629           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 630         }
 631         /* Do we read from arrays */
 632         if (fn.kind()==FKind.FlatElementNode) {
 633           //have to do expansion
 634           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 635         }
 636
 637         //See if flatnode is definitely no delay
 638         if (fn.kind()==FKind.FlatCall) {
 639           //Have to deal with fields/arrays
 640           FlatCall fcall=(FlatCall)fn;
 641           MethodDescriptor mdcall=fcall.getMethod();
 642           nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 643           nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 644           //Have to deal with field/array reads
 645           nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 646           nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 647         }
 648       } else {
 649         //Need to know which objects to lock on
 650         Set<TempDescriptor> oldtemps=oldtempmap.get(fn);
 651         switch(fn.kind()) {
 652         case FKind.FlatSetFieldNode: {
 653           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 654           if (oldtemps.contains(fsfn.getDst())) {
 655             nodelaytempset.add(fsfn.getDst());
 656           }
 657           break;
 658         }
 659         case FKind.FlatSetElementNode: {
 660           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 661           if (oldtemps.contains(fsen.getDst())) {
 662             nodelaytempset.add(fsen.getDst());
 663             //Word Array support requires index
 664             if (state.STMARRAY) {
 665               nodelaytempset.add(fsen.getIndex());
 666               derefset.add(fsen);
 667             }
 668           }
 669           break;
 670         }
 671         case FKind.FlatFieldNode: {
 672           FlatFieldNode ffn=(FlatFieldNode)fn;
 673           if (oldtemps.contains(ffn.getSrc())&&
 674               dcopts.getFields().contains(ffn.getField())) {
 675             nodelaytempset.add(ffn.getSrc());
 676           }
 677           break;
 678         }
 679         case FKind.FlatElementNode: {
 680           FlatElementNode fen=(FlatElementNode)fn;
 681           if (oldtemps.contains(fen.getSrc())&&
 682               dcopts.getArrays().contains(fen.getSrc().getType())) {
 683             nodelaytempset.add(fen.getSrc());
 684             //Word Array support requires index
 685             if (state.STMARRAY) {
 686               nodelaytempset.add(fen.getIndex());
 687               derefset.add(fen);
 688             }
 689           }
 690           break;
 691         }
 692         }
 693       }
 694
 695       boolean changed=false;
 696       //See if we need to propagate changes
 697       if (!nodelaytemps.containsKey(fn)||
 698           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 699         nodelaytemps.put(fn, nodelaytempset);
 700         changed=true;
 701       }
 702
 703       //See if we need to propagate changes
 704       if (!nodelayfieldswr.containsKey(fn)||
 705           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 706         nodelayfieldswr.put(fn, nodelayfieldwrset);
 707         changed=true;
 708       }
 709
 710       //See if we need to propagate changes
 711       if (!nodelayfieldsrd.containsKey(fn)||
 712           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 713         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 714         changed=true;
 715       }
 716
 717       //See if we need to propagate changes
 718       if (!nodelayarrayswr.containsKey(fn)||
 719           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 720         nodelayarrayswr.put(fn, nodelayarraywrset);
 721         changed=true;
 722       }
 723
 724       //See if we need to propagate changes
 725       if (!nodelayarraysrd.containsKey(fn)||
 726           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 727         nodelayarraysrd.put(fn, nodelayarrayrdset);
 728         changed=true;
 729       }
 730
 731       if (changed)
 732         for(int i=0;i<fn.numPrev();i++)
 733           toanalyze.add(fn.getPrev(i));
 734     }//end of while loop
 735
 736     if (lb.getHasAtomic()) {
 737       if (state.STMARRAY)
 738         derefmap.put(lb, derefset);
 739       cannotdelaymap.put(lb, cannotdelay);
 740     }
 741   } //end of method
 742
 743   //Problems:
 744   //1) we acquire locks too early to object we don't need to yet
 745   //2) we don't realize that certain operations have side effects
 746
 747   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 748     //You are in not ready set if:
 749     //I. You read a not ready temp
 750     //II. You access a field or element and
 751     //(A). You are not in the cannot delay set
 752     //(B). You read a field/element in the transactional set
 753     //(C). The source didn't have a transactional read on it
 754
 755     MethodDescriptor md=lb.getMethod();
 756     FlatMethod fm=state.getMethodFlat(md);
 757     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 758     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 759     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 760     toanalyze.addAll(fm.getNodeSet());
 761     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 762
 763     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 764     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 765
 766     while(!toanalyze.isEmpty()) {
 767       FlatNode fn=toanalyze.iterator().next();
 768       toanalyze.remove(fn);
 769       boolean isatomic=atomictable.get(fn).intValue()>0;
 770
 771       if (!isatomic)
 772         continue;
 773
 774       //Compute initial notready set
 775       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 776       for(int i=0;i<fn.numPrev();i++) {
 777         if (notreadymap.containsKey(fn.getPrev(i)))
 778           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 779       }
 780
 781       //Are we ready
 782       boolean notready=false;
 783
 784       //Test our read set first
 785       TempDescriptor readset[]=fn.readsTemps();
 786       for(int i=0;i<readset.length;i++) {
 787         TempDescriptor tmp=readset[i];
 788         if (notreadyset.contains(tmp)) {
 789           notready=true;
 790           break;
 791         }
 792       }
 793
 794       if (!notready&&!cannotdelay.contains(fn)) {
 795         switch(fn.kind()) {
 796         case FKind.FlatFieldNode: {
 797           FlatFieldNode ffn=(FlatFieldNode)fn;
 798           if (!dcopts.getFields().contains(ffn.getField())) {
 799             break;
 800           }
 801           TempDescriptor tmp=ffn.getSrc();
 802           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 803           if (tfpset!=null) {
 804             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 805               TempFlatPair tfp=tfpit.next();
 806               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 807                 //if a source didn't need a translation and we are
 808                 //accessing it, it did...so therefore we are note
 809                 //ready
 810                 notready=true;
 811                 break;
 812               }
 813             }
 814           }
 815           break;
 816         }
 817         case FKind.FlatSetFieldNode: {
 818           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 819           TempDescriptor tmp=fsfn.getDst();
 820           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 821           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 822
 823           if (tfpset!=null) {
 824             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 825               TempFlatPair tfp=tfpit.next();
 826               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 827                 //if a source didn't need a translation and we are
 828                 //accessing it, it did...so therefore we are note
 829                 //ready
 830                 notready=true;
 831                 break;
 832               }
 833             }
 834           }
 835           break;
 836         }
 837         case FKind.FlatElementNode: {
 838           FlatElementNode fen=(FlatElementNode)fn;
 839           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 840             break;
 841           }
 842           TempDescriptor tmp=fen.getSrc();
 843           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 844           if (tfpset!=null) {
 845             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 846               TempFlatPair tfp=tfpit.next();
 847               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 848                 //if a source didn't need a translation and we are
 849                 //accessing it, it did...so therefore we are note
 850                 //ready
 851                 notready=true;
 852                 break;
 853               }
 854             }
 855           }
 856           break;
 857         }
 858         case FKind.FlatSetElementNode: {
 859           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 860           TempDescriptor tmp=fsen.getDst();
 861           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 862           if (tfpset!=null) {
 863             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 864               TempFlatPair tfp=tfpit.next();
 865               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 866                 //if a source didn't need a translation and we are
 867                 //accessing it, it did...so therefore we are note
 868                 //ready
 869                 notready=true;
 870                 break;
 871               }
 872             }
 873           }
 874           break;
 875         }
 876         }
 877       }
 878
 879       if (!notready) {
 880         //See if we depend on a conditional branch that is not ready
 881         Set<FlatCondBranch> branchset=branchmap.get(fn);
 882         if (branchset!=null)
 883           for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
 884             FlatCondBranch fcb=branchit.next();
 885             if (notreadynodes.contains(fcb)) {
 886               //if we depend on a branch that isn't ready, we aren't ready
 887               notready=true;
 888               break;
 889             }
 890           }
 891       }
 892
 893
 894       //Fix up things based on our status
 895       if (notready) {
 896         if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
 897           //enqueue everything in our dependence set
 898           Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
 899           toanalyze.addAll(branchdepset);
 900         }
 901
 902         //add us to the list
 903         notreadynodes.add(fn);
 904
 905         //Add our writes
 906         TempDescriptor writeset[]=fn.writesTemps();
 907         for(int i=0;i<writeset.length;i++) {
 908           TempDescriptor tmp=writeset[i];
 909           notreadyset.add(tmp);
 910         }
 911       } else {
 912         //Kill our writes
 913         TempDescriptor writeset[]=fn.writesTemps();
 914         for(int i=0;i<writeset.length;i++) {
 915           TempDescriptor tmp=writeset[i];
 916           notreadyset.remove(tmp);
 917         }
 918       }
 919
 920       //See if we need to propagate changes
 921       if (!notreadymap.containsKey(fn)||
 922           !notreadymap.get(fn).equals(notreadyset)) {
 923         notreadymap.put(fn, notreadyset);
 924         for(int i=0;i<fn.numNext();i++)
 925           toanalyze.add(fn.getNext(i));
 926       }
 927     } //end of while
 928     return notreadynodes;
 929   } //end of computeNotReadySet
 930
 931   public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
 932     MethodDescriptor md=lb.getMethod();
 933     FlatMethod fm=state.getMethodFlat(md);
 934     Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
 935     DomTree postdt=new DomTree(fm, true);
 936     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 937       FlatNode fn=fnit.next();
 938       if (fn.kind()!=FKind.FlatCondBranch)
 939         continue;
 940       FlatCondBranch fcb=(FlatCondBranch)fn;
 941       //only worry about fcb inside of transactions
 942       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 943         continue;
 944       FlatNode postdom=postdt.idom(fcb);
 945
 946       //Reverse the mapping
 947       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 948       condmap.put(fcb, fnset);
 949     }
 950     return condmap;
 951   }
 952
 953   public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
 954     MethodDescriptor md=lb.getMethod();
 955     FlatMethod fm=state.getMethodFlat(md);
 956     Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
 957     DomTree postdt=new DomTree(fm, true);
 958     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 959       FlatNode fn=fnit.next();
 960       if (fn.kind()!=FKind.FlatCondBranch)
 961         continue;
 962       FlatCondBranch fcb=(FlatCondBranch)fn;
 963       //only worry about fcb inside of transactions
 964       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 965         continue;
 966       FlatNode postdom=postdt.idom(fcb);
 967
 968       //Reverse the mapping
 969       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 970       for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
 971         FlatNode fn2=fnit2.next();
 972         if (!condmap.containsKey(fn2))
 973           condmap.put(fn2,new HashSet<FlatCondBranch>());
 974         condmap.get(fn2).add(fcb);
 975       }
 976     }
 977     return condmap;
 978   }
 979
 980   public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
 981     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 982     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 983     toanalyze.add(first);
 984
 985     while(!toanalyze.isEmpty()) {
 986       FlatNode fn=toanalyze.iterator().next();
 987       toanalyze.remove(fn);
 988
 989       //already examined or exit node
 990       if (visited.contains(fn)||fn==last)
 991         continue;
 992
 993       //out of transaction
 994       if (locality.getAtomic(lb).get(fn).intValue()==0)
 995         continue;
 996
 997       visited.add(fn);
 998       for(int i=0;i<fn.numNext();i++) {
 999         FlatNode fnext=fn.getNext(i);
1000         toanalyze.add(fnext);
1001       }
1002     }
1003     return visited;
1004   } //end of computeBranchSet
1005 } //end of class