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