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       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         case FKind.FlatSetElementNode: {
 699           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 700           if (oldtemps.contains(fsen.getDst())) {
 701             nodelaytempset.add(fsen.getDst());
 702             //Word Array support requires index
 703             if (state.STMARRAY&&!state.DUALVIEW) {
 704               nodelaytempset.add(fsen.getIndex());
 705               derefset.add(fsen);
 706             }
 707           }
 708           break;
 709         }
 710         case FKind.FlatFieldNode: {
 711           FlatFieldNode ffn=(FlatFieldNode)fn;
 712           if (oldtemps.contains(ffn.getSrc())&&
 713               dcopts.getFields().contains(ffn.getField())) {
 714             nodelaytempset.add(ffn.getSrc());
 715           }
 716           break;
 717         }
 718         case FKind.FlatElementNode: {
 719           FlatElementNode fen=(FlatElementNode)fn;
 720           if (oldtemps.contains(fen.getSrc())&&
 721               dcopts.getArrays().contains(fen.getSrc().getType())) {
 722             nodelaytempset.add(fen.getSrc());
 723             //Word Array support requires index
 724             if (state.STMARRAY&&!state.DUALVIEW) {
 725               nodelaytempset.add(fen.getIndex());
 726               derefset.add(fen);
 727             }
 728           }
 729           break;
 730         }
 731         }
 732       }
 733
 734       boolean changed=false;
 735       //See if we need to propagate changes
 736       if (!nodelaytemps.containsKey(fn)||
 737           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 738         nodelaytemps.put(fn, nodelaytempset);
 739         changed=true;
 740       }
 741
 742       //See if we need to propagate changes
 743       if (!nodelayfieldswr.containsKey(fn)||
 744           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 745         nodelayfieldswr.put(fn, nodelayfieldwrset);
 746         changed=true;
 747       }
 748
 749       //See if we need to propagate changes
 750       if (!nodelayfieldsrd.containsKey(fn)||
 751           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 752         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 753         changed=true;
 754       }
 755
 756       //See if we need to propagate changes
 757       if (!nodelayarrayswr.containsKey(fn)||
 758           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 759         nodelayarrayswr.put(fn, nodelayarraywrset);
 760         changed=true;
 761       }
 762
 763       //See if we need to propagate changes
 764       if (!nodelayarraysrd.containsKey(fn)||
 765           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 766         nodelayarraysrd.put(fn, nodelayarrayrdset);
 767         changed=true;
 768       }
 769
 770       if (changed)
 771         for(int i=0;i<fn.numPrev();i++)
 772           toanalyze.add(fn.getPrev(i));
 773     }//end of while loop
 774
 775     if (lb.getHasAtomic()) {
 776       if (state.STMARRAY&&!state.DUALVIEW)
 777         derefmap.put(lb, derefset);
 778       cannotdelaymap.put(lb, cannotdelay);
 779     }
 780   } //end of method
 781
 782   //Problems:
 783   //1) we acquire locks too early to object we don't need to yet
 784   //2) we don't realize that certain operations have side effects
 785
 786   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 787     //You are in not ready set if:
 788     //I. You read a not ready temp
 789     //II. You access a field or element and
 790     //(A). You are not in the cannot delay set
 791     //(B). You read a field/element in the transactional set
 792     //(C). The source didn't have a transactional read on it
 793
 794     MethodDescriptor md=lb.getMethod();
 795     FlatMethod fm=state.getMethodFlat(md);
 796     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 797     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 798     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 799     toanalyze.addAll(fm.getNodeSet());
 800     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 801
 802     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 803     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 804
 805     while(!toanalyze.isEmpty()) {
 806       FlatNode fn=toanalyze.iterator().next();
 807       toanalyze.remove(fn);
 808       boolean isatomic=atomictable.get(fn).intValue()>0;
 809
 810       if (!isatomic)
 811         continue;
 812
 813       //Compute initial notready set
 814       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 815       for(int i=0;i<fn.numPrev();i++) {
 816         if (notreadymap.containsKey(fn.getPrev(i)))
 817           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 818       }
 819
 820       //Are we ready
 821       boolean notready=false;
 822
 823       //Test our read set first
 824       TempDescriptor readset[]=fn.readsTemps();
 825       for(int i=0;i<readset.length;i++) {
 826         TempDescriptor tmp=readset[i];
 827         if (notreadyset.contains(tmp)) {
 828           notready=true;
 829           break;
 830         }
 831       }
 832
 833       if (!notready&&!cannotdelay.contains(fn)) {
 834         switch(fn.kind()) {
 835         case FKind.FlatFieldNode: {
 836           FlatFieldNode ffn=(FlatFieldNode)fn;
 837           if (!dcopts.getFields().contains(ffn.getField())) {
 838             break;
 839           }
 840           TempDescriptor tmp=ffn.getSrc();
 841           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 842           if (tfpset!=null) {
 843             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 844               TempFlatPair tfp=tfpit.next();
 845               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 846                 //if a source didn't need a translation and we are
 847                 //accessing it, it did...so therefore we are note
 848                 //ready
 849                 notready=true;
 850                 break;
 851               }
 852             }
 853           }
 854           break;
 855         }
 856         case FKind.FlatSetFieldNode: {
 857           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 858           TempDescriptor tmp=fsfn.getDst();
 859           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 860           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 861
 862           if (tfpset!=null) {
 863             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 864               TempFlatPair tfp=tfpit.next();
 865               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 866                 //if a source didn't need a translation and we are
 867                 //accessing it, it did...so therefore we are note
 868                 //ready
 869                 notready=true;
 870                 break;
 871               }
 872             }
 873           }
 874           break;
 875         }
 876         case FKind.FlatElementNode: {
 877           FlatElementNode fen=(FlatElementNode)fn;
 878           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 879             break;
 880           }
 881           TempDescriptor tmp=fen.getSrc();
 882           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 883           if (tfpset!=null) {
 884             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 885               TempFlatPair tfp=tfpit.next();
 886               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 887                 //if a source didn't need a translation and we are
 888                 //accessing it, it did...so therefore we are note
 889                 //ready
 890                 notready=true;
 891                 break;
 892               }
 893             }
 894           }
 895           break;
 896         }
 897         case FKind.FlatSetElementNode: {
 898           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 899           TempDescriptor tmp=fsen.getDst();
 900           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 901           if (tfpset!=null) {
 902             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 903               TempFlatPair tfp=tfpit.next();
 904               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 905                 //if a source didn't need a translation and we are
 906                 //accessing it, it did...so therefore we are note
 907                 //ready
 908                 notready=true;
 909                 break;
 910               }
 911             }
 912           }
 913           break;
 914         }
 915         }
 916       }
 917
 918       if (!notready) {
 919         //See if we depend on a conditional branch that is not ready
 920         Set<FlatCondBranch> branchset=branchmap.get(fn);
 921         if (branchset!=null)
 922           for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
 923             FlatCondBranch fcb=branchit.next();
 924             if (notreadynodes.contains(fcb)) {
 925               //if we depend on a branch that isn't ready, we aren't ready
 926               notready=true;
 927               break;
 928             }
 929           }
 930       }
 931
 932
 933       //Fix up things based on our status
 934       if (notready) {
 935         if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
 936           //enqueue everything in our dependence set
 937           Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
 938           toanalyze.addAll(branchdepset);
 939         }
 940
 941         //add us to the list
 942         notreadynodes.add(fn);
 943
 944         //Add our writes
 945         TempDescriptor writeset[]=fn.writesTemps();
 946         for(int i=0;i<writeset.length;i++) {
 947           TempDescriptor tmp=writeset[i];
 948           notreadyset.add(tmp);
 949         }
 950       } else {
 951         //Kill our writes
 952         TempDescriptor writeset[]=fn.writesTemps();
 953         for(int i=0;i<writeset.length;i++) {
 954           TempDescriptor tmp=writeset[i];
 955           notreadyset.remove(tmp);
 956         }
 957       }
 958
 959       //See if we need to propagate changes
 960       if (!notreadymap.containsKey(fn)||
 961           !notreadymap.get(fn).equals(notreadyset)) {
 962         notreadymap.put(fn, notreadyset);
 963         for(int i=0;i<fn.numNext();i++)
 964           toanalyze.add(fn.getNext(i));
 965       }
 966     } //end of while
 967     return notreadynodes;
 968   } //end of computeNotReadySet
 969
 970   public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
 971     MethodDescriptor md=lb.getMethod();
 972     FlatMethod fm=state.getMethodFlat(md);
 973     Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
 974     DomTree postdt=new DomTree(fm, true);
 975     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 976       FlatNode fn=fnit.next();
 977       if (fn.kind()!=FKind.FlatCondBranch)
 978         continue;
 979       FlatCondBranch fcb=(FlatCondBranch)fn;
 980       //only worry about fcb inside of transactions
 981       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 982         continue;
 983       FlatNode postdom=postdt.idom(fcb);
 984
 985       //Reverse the mapping
 986       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 987       condmap.put(fcb, fnset);
 988     }
 989     return condmap;
 990   }
 991
 992   public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
 993     MethodDescriptor md=lb.getMethod();
 994     FlatMethod fm=state.getMethodFlat(md);
 995     Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
 996     DomTree postdt=new DomTree(fm, true);
 997     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 998       FlatNode fn=fnit.next();
 999       if (fn.kind()!=FKind.FlatCondBranch)
1000         continue;
1001       FlatCondBranch fcb=(FlatCondBranch)fn;
1002       //only worry about fcb inside of transactions
1003       if (locality.getAtomic(lb).get(fcb).intValue()==0)
1004         continue;
1005       FlatNode postdom=postdt.idom(fcb);
1006
1007       //Reverse the mapping
1008       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
1009       for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
1010         FlatNode fn2=fnit2.next();
1011         if (!condmap.containsKey(fn2))
1012           condmap.put(fn2,new HashSet<FlatCondBranch>());
1013         condmap.get(fn2).add(fcb);
1014       }
1015     }
1016     return condmap;
1017   }
1018
1019   public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
1020     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
1021     HashSet<FlatNode> visited=new HashSet<FlatNode>();
1022     toanalyze.add(first);
1023
1024     while(!toanalyze.isEmpty()) {
1025       FlatNode fn=toanalyze.iterator().next();
1026       toanalyze.remove(fn);
1027
1028       //already examined or exit node
1029       if (visited.contains(fn)||fn==last)
1030         continue;
1031
1032       //out of transaction
1033       if (locality.getAtomic(lb).get(fn).intValue()==0)
1034         continue;
1035
1036       visited.add(fn);
1037       for(int i=0;i<fn.numNext();i++) {
1038         FlatNode fnext=fn.getNext(i);
1039         toanalyze.add(fnext);
1040       }
1041     }
1042     return visited;
1043   } //end of computeBranchSet
1044 } //end of class