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