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