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&&!state.DUALVIEW)
  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=null;
 289     if (state.STMARRAY&&!state.DUALVIEW)
 290       derefset=derefmap.get(lb);
 291     HashSet<FlatNode> otherset=othermap.get(lb);
 292     HashSet<FlatNode> cannotdelayset=cannotdelaymap.get(lb);
 293     Hashtable<FlatNode,Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 294     Hashtable<FlatNode, Hashtable<TempDescriptor, Set<FlatNode>>> reachingdefsmap=ReachingDefs.computeReachingDefs(fm, livemap, true);
 295     HashSet<FlatNode> unionset=new HashSet<FlatNode>(delayedset);
 296     Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>> map=new Hashtable<FlatNode, Hashtable<TempDescriptor, HashSet<FlatNode>>>();
 297     HashSet<FlatNode> livenodes=new HashSet<FlatNode>();
 298     Hashtable<FlatCondBranch, Set<FlatNode>> branchmap=revGetBranchSet(lb);
 299
 300     //Here we check for temps that are live out on the transaction...
 301     //If both parts can contribute to the temp, then we need to do
 302     //reads to make sure that liveout set has the right values
 303
 304     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 305       FlatNode fn=fnit.next();
 306       if (fn.kind()==FKind.FlatAtomicExitNode) {
 307         Set<TempDescriptor> livetemps=livemap.get(fn);
 308         Hashtable<TempDescriptor, Set<FlatNode>> tempmap=reachingdefsmap.get(fn);
 309
 310         //Iterate over the temps that are live into this node
 311         for(Iterator<TempDescriptor> tmpit=livetemps.iterator();tmpit.hasNext();) {
 312           TempDescriptor tmp=tmpit.next();
 313           Set<FlatNode> fnset=tempmap.get(tmp);
 314           boolean inpart1=false;
 315           boolean inpart2=false;
 316
 317           //iterate over the reaching definitions for the temp
 318           for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 319             FlatNode fn2=fnit2.next();
 320             if (delayedset.contains(fn2)) {
 321               inpart2=true;
 322               if (inpart1)
 323                 break;
 324             } else if (otherset.contains(fn2)||cannotdelayset.contains(fn2)) {
 325               inpart1=true;
 326               if (inpart2)
 327                 break;
 328             }
 329           }
 330           if (inpart1&&inpart2) {
 331             for(Iterator<FlatNode> fnit2=fnset.iterator();fnit2.hasNext();) {
 332               FlatNode fn2=fnit2.next();
 333               if ((otherset.contains(fn2)||cannotdelayset.contains(fn2))&&
 334                   locality.getAtomic(lb).get(fn2).intValue()>0) {
 335                 unionset.add(fn2);
 336                 livenodes.add(fn2);
 337               }
 338             }
 339           }
 340         }
 341       }
 342     }
 343
 344     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 345     toanalyze.add(fm);
 346
 347     while(!toanalyze.isEmpty()) {
 348       FlatNode fn=toanalyze.iterator().next();
 349       toanalyze.remove(fn);
 350       Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
 351
 352       //Don't process non-atomic nodes
 353       if (locality.getAtomic(lb).get(fn).intValue()==0) {
 354         if (!map.containsKey(fn)) {
 355           map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
 356           //enqueue next nodes
 357           for(int i=0;i<fn.numNext();i++)
 358             toanalyze.add(fn.getNext(i));
 359         }
 360         continue;
 361       }
 362
 363       //Do merge on incoming edges
 364       for(int i=0;i<fn.numPrev();i++) {
 365         FlatNode fnprev=fn.getPrev(i);
 366         Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
 367         if (prevmap!=null)
 368           for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 369             TempDescriptor tmp=tmpit.next();
 370             if (!tmptofn.containsKey(tmp))
 371               tmptofn.put(tmp, new HashSet<FlatNode>());
 372             tmptofn.get(tmp).addAll(prevmap.get(tmp));
 373           }
 374       }
 375
 376       if (delayedset.contains(fn)) {
 377         if(state.STMARRAY&&!state.DUALVIEW&&derefset.contains(fn)) {
 378           //FlatElementNodes don't read anything...
 379           if (fn.kind()==FKind.FlatSetElementNode) {
 380             //check only the source read tmp
 381             TempDescriptor tmp=((FlatSetElementNode)fn).getSrc();
 382             if (tmptofn.containsKey(tmp)) {
 383               livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
 384               unionset.addAll(tmptofn.get(tmp));
 385             }
 386           }
 387         } else {
 388           //If the node is in the second set, check our readset
 389           TempDescriptor readset[]=fn.readsTemps();
 390           for(int i=0;i<readset.length;i++) {
 391             TempDescriptor tmp=readset[i];
 392             if (tmptofn.containsKey(tmp)) {
 393               livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
 394               unionset.addAll(tmptofn.get(tmp));
 395             }
 396           }
 397         }
 398         //Do kills
 399         TempDescriptor writeset[]=fn.writesTemps();
 400         for(int i=0;i<writeset.length;i++) {
 401           TempDescriptor tmp=writeset[i];
 402           tmptofn.remove(tmp);
 403         }
 404       } else {
 405         //If the node is in the first set, search over what we write
 406         //We write -- our reads are done
 407         TempDescriptor writeset[]=fn.writesTemps();
 408         for(int i=0;i<writeset.length;i++) {
 409           TempDescriptor tmp=writeset[i];
 410           HashSet<FlatNode> set=new HashSet<FlatNode>();
 411           tmptofn.put(tmp,set);
 412           set.add(fn);
 413         }
 414         if (fn.numNext()>1) {
 415           Set<FlatNode> branchset=branchmap.get((FlatCondBranch)fn);
 416           for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
 417             FlatNode brfn=brit.next();
 418             if (unionset.contains(brfn)) {
 419               //This branch is important--need to remember how it goes
 420               livenodes.add(fn);
 421               unionset.add(fn);
 422             }
 423           }
 424         }
 425       }
 426       if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
 427         map.put(fn, tmptofn);
 428         //enqueue next ndoes
 429         for(int i=0;i<fn.numNext();i++)
 430           toanalyze.add(fn.getNext(i));
 431       }
 432     }
 433     return livenodes;
 434   }
 435
 436   public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
 437     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 438     FlatNode fnnext=fn.getNext(i);
 439     HashSet<FlatNode> reachable=new HashSet<FlatNode>();
 440
 441     if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
 442       reachable.add(fnnext);
 443       return reachable;
 444     }
 445     Stack<FlatNode> nodes=new Stack<FlatNode>();
 446     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 447     nodes.push(fnnext);
 448     if (contpastnode)
 449       visited.add(fn);
 450
 451     while(!nodes.isEmpty()) {
 452       FlatNode fn2=nodes.pop();
 453       if (visited.contains(fn2))
 454         continue;
 455       visited.add(fn2);
 456       for (int j=0;j<fn2.numNext();j++) {
 457         FlatNode fn2next=fn2.getNext(j);
 458         if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
 459           reachable.add(fn2next);
 460         } else
 461           nodes.push(fn2next);
 462       }
 463     }
 464     return reachable;
 465   }
 466
 467   //Computes cannotdelayset---flatnodes that must be evaluated in the
 468   //speculative component.
 469
 470   public void analyzeMethod(LocalityBinding lb) {
 471     MethodDescriptor md=lb.getMethod();
 472     FlatMethod fm=state.getMethodFlat(md);
 473     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
 474     HashSet<FlatNode> derefset=new HashSet<FlatNode>();
 475     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 476     if (lb.isAtomic()) {
 477       //We are in a transaction already...
 478       //skip past this method or something
 479       return;
 480     }
 481
 482     Hashtable<FlatNode, Set<TempDescriptor>> oldtempmap=dcopts.computeOldTemps(lb);
 483
 484     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 485     toanalyze.addAll(fm.getNodeSet());
 486
 487     //Build the hashtables
 488     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 489     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 490     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 491     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 492     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 493
 494     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 495     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 496     //Effect of adding something to nodelay set is to move it up past everything in delay set
 497     //Have to make sure we can do this commute
 498
 499     while(!toanalyze.isEmpty()) {
 500       FlatNode fn=toanalyze.iterator().next();
 501       toanalyze.remove(fn);
 502
 503       boolean isatomic=atomictable.get(fn).intValue()>0;
 504
 505       if (!isatomic)
 506         continue;
 507       boolean isnodelay=false;
 508
 509       /* Compute incoming nodelay sets */
 510       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
 511       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
 512       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
 513       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
 514       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
 515       for(int i=0;i<fn.numNext();i++) {
 516         if (nodelaytemps.containsKey(fn.getNext(i)))
 517           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
 518         //do field/array write sets
 519         if (nodelayfieldswr.containsKey(fn.getNext(i)))
 520           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
 521         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 522           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 523         //do read sets
 524         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
 525           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
 526         if (nodelayarraysrd.containsKey(fn.getNext(i)))
 527           nodelayarrayrdset.addAll(nodelayarraysrd.get(fn.getNext(i)));
 528       }
 529
 530       /* Check our temp write set */
 531
 532       TempDescriptor writeset[]=fn.writesTemps();
 533       for(int i=0;i<writeset.length;i++) {
 534         TempDescriptor tmp=writeset[i];
 535         if (nodelaytempset.contains(tmp)) {
 536           //We are writing to a nodelay temp
 537           //Therefore we are nodelay
 538           isnodelay=true;
 539           //Kill temp we wrote to
 540           nodelaytempset.remove(tmp);
 541         }
 542       }
 543
 544       //See if flatnode is definitely no delay
 545       if (fn.kind()==FKind.FlatCall) {
 546         FlatCall fcall=(FlatCall)fn;
 547         MethodDescriptor mdcall=fcall.getMethod();
 548         if (!mdcall.getClassDesc().getSymbol().equals("System")||
 549             (!mdcall.getSymbol().equals("println")&&!mdcall.getSymbol().equals("printString")))
 550           isnodelay=true;
 551       }
 552
 553       //Delay branches if possible
 554       if (fn.kind()==FKind.FlatCondBranch) {
 555         Set<FlatNode> branchset=revbranchmap.get((FlatCondBranch)fn);
 556         for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
 557           FlatNode branchnode=brit.next();
 558           if (cannotdelay.contains(branchnode)||(state.STMARRAY&&!state.DUALVIEW&&derefset.contains(branchnode))) {
 559             isnodelay=true;
 560             break;
 561           }
 562         }
 563       }
 564
 565       //Check for field conflicts
 566       if (fn.kind()==FKind.FlatSetFieldNode) {
 567         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 568         //write conflicts
 569         if (nodelayfieldwrset.contains(fd))
 570           isnodelay=true;
 571         //read
 572         if (nodelayfieldrdset.contains(fd))
 573           isnodelay=true;
 574       }
 575
 576       if (fn.kind()==FKind.FlatFieldNode) {
 577         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 578         //write conflicts
 579         if (nodelayfieldwrset.contains(fd))
 580           isnodelay=true;
 581       }
 582       //Check for array conflicts
 583       if (fn.kind()==FKind.FlatSetElementNode) {
 584         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 585         //check for write conflicts
 586         if (nodelayarraywrset.contains(td))
 587           isnodelay=true;
 588         //check for read conflicts
 589         if (nodelayarrayrdset.contains(td))
 590           isnodelay=true;
 591       }
 592       if (fn.kind()==FKind.FlatElementNode) {
 593         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 594         //check for write conflicts
 595         if (nodelayarraywrset.contains(td))
 596           isnodelay=true;
 597       }
 598
 599       //If we are no delay, then the temps we read are no delay
 600       if (isnodelay) {
 601         /* Add our read set */
 602         TempDescriptor readset[]=fn.readsTemps();
 603         for(int i=0;i<readset.length;i++) {
 604           TempDescriptor tmp=readset[i];
 605           nodelaytempset.add(tmp);
 606         }
 607         cannotdelay.add(fn);
 608
 609         if (branchmap.containsKey(fn)) {
 610           Set<FlatCondBranch> fcbset=branchmap.get(fn);
 611           for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
 612             FlatCondBranch fcb=fcbit.next();
 613             //enqueue flatcondbranch node for reanalysis
 614             if (!cannotdelay.contains(fcb)) {
 615               cannotdelay.add(fcb);
 616               toanalyze.add(fcb);
 617             }
 618           }
 619         }
 620         /* Do we write to fields */
 621         if (fn.kind()==FKind.FlatSetFieldNode) {
 622           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 623         }
 624         /* Do we read from fields */
 625         if (fn.kind()==FKind.FlatFieldNode) {
 626           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 627         }
 628         /* Do we write to arrays */
 629         if (fn.kind()==FKind.FlatSetElementNode) {
 630           //have to do expansion
 631           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 632         }
 633         /* Do we read from arrays */
 634         if (fn.kind()==FKind.FlatElementNode) {
 635           //have to do expansion
 636           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 637         }
 638
 639         //See if flatnode is definitely no delay
 640         if (fn.kind()==FKind.FlatCall) {
 641           //Have to deal with fields/arrays
 642           FlatCall fcall=(FlatCall)fn;
 643           MethodDescriptor mdcall=fcall.getMethod();
 644           nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 645           nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 646           //Have to deal with field/array reads
 647           nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 648           nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 649         }
 650       } else {
 651         //Need to know which objects to lock on
 652         Set<TempDescriptor> oldtemps=oldtempmap.get(fn);
 653         switch(fn.kind()) {
 654         case FKind.FlatSetFieldNode: {
 655           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 656           if (oldtemps.contains(fsfn.getDst())) {
 657             nodelaytempset.add(fsfn.getDst());
 658           }
 659           break;
 660         }
 661         case FKind.FlatSetElementNode: {
 662           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 663           if (oldtemps.contains(fsen.getDst())) {
 664             nodelaytempset.add(fsen.getDst());
 665             //Word Array support requires index
 666             if (state.STMARRAY&&!state.DUALVIEW) {
 667               nodelaytempset.add(fsen.getIndex());
 668               derefset.add(fsen);
 669             }
 670           }
 671           break;
 672         }
 673         case FKind.FlatFieldNode: {
 674           FlatFieldNode ffn=(FlatFieldNode)fn;
 675           if (oldtemps.contains(ffn.getSrc())&&
 676               dcopts.getFields().contains(ffn.getField())) {
 677             nodelaytempset.add(ffn.getSrc());
 678           }
 679           break;
 680         }
 681         case FKind.FlatElementNode: {
 682           FlatElementNode fen=(FlatElementNode)fn;
 683           if (oldtemps.contains(fen.getSrc())&&
 684               dcopts.getArrays().contains(fen.getSrc().getType())) {
 685             nodelaytempset.add(fen.getSrc());
 686             //Word Array support requires index
 687             if (state.STMARRAY&&!state.DUALVIEW) {
 688               nodelaytempset.add(fen.getIndex());
 689               derefset.add(fen);
 690             }
 691           }
 692           break;
 693         }
 694         }
 695       }
 696
 697       boolean changed=false;
 698       //See if we need to propagate changes
 699       if (!nodelaytemps.containsKey(fn)||
 700           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 701         nodelaytemps.put(fn, nodelaytempset);
 702         changed=true;
 703       }
 704
 705       //See if we need to propagate changes
 706       if (!nodelayfieldswr.containsKey(fn)||
 707           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 708         nodelayfieldswr.put(fn, nodelayfieldwrset);
 709         changed=true;
 710       }
 711
 712       //See if we need to propagate changes
 713       if (!nodelayfieldsrd.containsKey(fn)||
 714           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 715         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 716         changed=true;
 717       }
 718
 719       //See if we need to propagate changes
 720       if (!nodelayarrayswr.containsKey(fn)||
 721           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 722         nodelayarrayswr.put(fn, nodelayarraywrset);
 723         changed=true;
 724       }
 725
 726       //See if we need to propagate changes
 727       if (!nodelayarraysrd.containsKey(fn)||
 728           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 729         nodelayarraysrd.put(fn, nodelayarrayrdset);
 730         changed=true;
 731       }
 732
 733       if (changed)
 734         for(int i=0;i<fn.numPrev();i++)
 735           toanalyze.add(fn.getPrev(i));
 736     }//end of while loop
 737
 738     if (lb.getHasAtomic()) {
 739       if (state.STMARRAY&&!state.DUALVIEW)
 740         derefmap.put(lb, derefset);
 741       cannotdelaymap.put(lb, cannotdelay);
 742     }
 743   } //end of method
 744
 745   //Problems:
 746   //1) we acquire locks too early to object we don't need to yet
 747   //2) we don't realize that certain operations have side effects
 748
 749   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 750     //You are in not ready set if:
 751     //I. You read a not ready temp
 752     //II. You access a field or element and
 753     //(A). You are not in the cannot delay set
 754     //(B). You read a field/element in the transactional set
 755     //(C). The source didn't have a transactional read on it
 756
 757     MethodDescriptor md=lb.getMethod();
 758     FlatMethod fm=state.getMethodFlat(md);
 759     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 760     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 761     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 762     toanalyze.addAll(fm.getNodeSet());
 763     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 764
 765     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 766     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 767
 768     while(!toanalyze.isEmpty()) {
 769       FlatNode fn=toanalyze.iterator().next();
 770       toanalyze.remove(fn);
 771       boolean isatomic=atomictable.get(fn).intValue()>0;
 772
 773       if (!isatomic)
 774         continue;
 775
 776       //Compute initial notready set
 777       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 778       for(int i=0;i<fn.numPrev();i++) {
 779         if (notreadymap.containsKey(fn.getPrev(i)))
 780           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 781       }
 782
 783       //Are we ready
 784       boolean notready=false;
 785
 786       //Test our read set first
 787       TempDescriptor readset[]=fn.readsTemps();
 788       for(int i=0;i<readset.length;i++) {
 789         TempDescriptor tmp=readset[i];
 790         if (notreadyset.contains(tmp)) {
 791           notready=true;
 792           break;
 793         }
 794       }
 795
 796       if (!notready&&!cannotdelay.contains(fn)) {
 797         switch(fn.kind()) {
 798         case FKind.FlatFieldNode: {
 799           FlatFieldNode ffn=(FlatFieldNode)fn;
 800           if (!dcopts.getFields().contains(ffn.getField())) {
 801             break;
 802           }
 803           TempDescriptor tmp=ffn.getSrc();
 804           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 805           if (tfpset!=null) {
 806             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 807               TempFlatPair tfp=tfpit.next();
 808               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 809                 //if a source didn't need a translation and we are
 810                 //accessing it, it did...so therefore we are note
 811                 //ready
 812                 notready=true;
 813                 break;
 814               }
 815             }
 816           }
 817           break;
 818         }
 819         case FKind.FlatSetFieldNode: {
 820           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 821           TempDescriptor tmp=fsfn.getDst();
 822           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 823           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 824
 825           if (tfpset!=null) {
 826             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 827               TempFlatPair tfp=tfpit.next();
 828               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 829                 //if a source didn't need a translation and we are
 830                 //accessing it, it did...so therefore we are note
 831                 //ready
 832                 notready=true;
 833                 break;
 834               }
 835             }
 836           }
 837           break;
 838         }
 839         case FKind.FlatElementNode: {
 840           FlatElementNode fen=(FlatElementNode)fn;
 841           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 842             break;
 843           }
 844           TempDescriptor tmp=fen.getSrc();
 845           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 846           if (tfpset!=null) {
 847             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 848               TempFlatPair tfp=tfpit.next();
 849               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 850                 //if a source didn't need a translation and we are
 851                 //accessing it, it did...so therefore we are note
 852                 //ready
 853                 notready=true;
 854                 break;
 855               }
 856             }
 857           }
 858           break;
 859         }
 860         case FKind.FlatSetElementNode: {
 861           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 862           TempDescriptor tmp=fsen.getDst();
 863           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 864           if (tfpset!=null) {
 865             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 866               TempFlatPair tfp=tfpit.next();
 867               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 868                 //if a source didn't need a translation and we are
 869                 //accessing it, it did...so therefore we are note
 870                 //ready
 871                 notready=true;
 872                 break;
 873               }
 874             }
 875           }
 876           break;
 877         }
 878         }
 879       }
 880
 881       if (!notready) {
 882         //See if we depend on a conditional branch that is not ready
 883         Set<FlatCondBranch> branchset=branchmap.get(fn);
 884         if (branchset!=null)
 885           for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
 886             FlatCondBranch fcb=branchit.next();
 887             if (notreadynodes.contains(fcb)) {
 888               //if we depend on a branch that isn't ready, we aren't ready
 889               notready=true;
 890               break;
 891             }
 892           }
 893       }
 894
 895
 896       //Fix up things based on our status
 897       if (notready) {
 898         if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
 899           //enqueue everything in our dependence set
 900           Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
 901           toanalyze.addAll(branchdepset);
 902         }
 903
 904         //add us to the list
 905         notreadynodes.add(fn);
 906
 907         //Add our writes
 908         TempDescriptor writeset[]=fn.writesTemps();
 909         for(int i=0;i<writeset.length;i++) {
 910           TempDescriptor tmp=writeset[i];
 911           notreadyset.add(tmp);
 912         }
 913       } else {
 914         //Kill our writes
 915         TempDescriptor writeset[]=fn.writesTemps();
 916         for(int i=0;i<writeset.length;i++) {
 917           TempDescriptor tmp=writeset[i];
 918           notreadyset.remove(tmp);
 919         }
 920       }
 921
 922       //See if we need to propagate changes
 923       if (!notreadymap.containsKey(fn)||
 924           !notreadymap.get(fn).equals(notreadyset)) {
 925         notreadymap.put(fn, notreadyset);
 926         for(int i=0;i<fn.numNext();i++)
 927           toanalyze.add(fn.getNext(i));
 928       }
 929     } //end of while
 930     return notreadynodes;
 931   } //end of computeNotReadySet
 932
 933   public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
 934     MethodDescriptor md=lb.getMethod();
 935     FlatMethod fm=state.getMethodFlat(md);
 936     Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
 937     DomTree postdt=new DomTree(fm, true);
 938     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 939       FlatNode fn=fnit.next();
 940       if (fn.kind()!=FKind.FlatCondBranch)
 941         continue;
 942       FlatCondBranch fcb=(FlatCondBranch)fn;
 943       //only worry about fcb inside of transactions
 944       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 945         continue;
 946       FlatNode postdom=postdt.idom(fcb);
 947
 948       //Reverse the mapping
 949       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 950       condmap.put(fcb, fnset);
 951     }
 952     return condmap;
 953   }
 954
 955   public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
 956     MethodDescriptor md=lb.getMethod();
 957     FlatMethod fm=state.getMethodFlat(md);
 958     Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
 959     DomTree postdt=new DomTree(fm, true);
 960     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 961       FlatNode fn=fnit.next();
 962       if (fn.kind()!=FKind.FlatCondBranch)
 963         continue;
 964       FlatCondBranch fcb=(FlatCondBranch)fn;
 965       //only worry about fcb inside of transactions
 966       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 967         continue;
 968       FlatNode postdom=postdt.idom(fcb);
 969
 970       //Reverse the mapping
 971       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 972       for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
 973         FlatNode fn2=fnit2.next();
 974         if (!condmap.containsKey(fn2))
 975           condmap.put(fn2,new HashSet<FlatCondBranch>());
 976         condmap.get(fn2).add(fcb);
 977       }
 978     }
 979     return condmap;
 980   }
 981
 982   public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
 983     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 984     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 985     toanalyze.add(first);
 986
 987     while(!toanalyze.isEmpty()) {
 988       FlatNode fn=toanalyze.iterator().next();
 989       toanalyze.remove(fn);
 990
 991       //already examined or exit node
 992       if (visited.contains(fn)||fn==last)
 993         continue;
 994
 995       //out of transaction
 996       if (locality.getAtomic(lb).get(fn).intValue()==0)
 997         continue;
 998
 999       visited.add(fn);
1000       for(int i=0;i<fn.numNext();i++) {
1001         FlatNode fnext=fn.getNext(i);
1002         toanalyze.add(fnext);
1003       }
1004     }
1005     return visited;
1006   } //end of computeBranchSet
1007 } //end of class