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