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                 unionset.add(fn2);
 314                 livenodes.add(fn2);
 315               }
 316             }
 317           }
 318         }
 319       }
 320     }
 321
 322     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 323     toanalyze.add(fm);
 324
 325     while(!toanalyze.isEmpty()) {
 326       FlatNode fn=toanalyze.iterator().next();
 327       toanalyze.remove(fn);
 328       Hashtable<TempDescriptor, HashSet<FlatNode>> tmptofn=new Hashtable<TempDescriptor, HashSet<FlatNode>>();
 329
 330       //Don't process non-atomic nodes
 331       if (locality.getAtomic(lb).get(fn).intValue()==0) {
 332         if (!map.containsKey(fn)) {
 333           map.put(fn, new Hashtable<TempDescriptor, HashSet<FlatNode>>());
 334           //enqueue next nodes
 335           for(int i=0;i<fn.numNext();i++)
 336             toanalyze.add(fn.getNext(i));
 337         }
 338         continue;
 339       }
 340
 341       //Do merge on incoming edges
 342       for(int i=0;i<fn.numPrev();i++) {
 343         FlatNode fnprev=fn.getPrev(i);
 344         Hashtable<TempDescriptor, HashSet<FlatNode>> prevmap=map.get(fnprev);
 345         if (prevmap!=null)
 346           for(Iterator<TempDescriptor> tmpit=prevmap.keySet().iterator();tmpit.hasNext();) {
 347             TempDescriptor tmp=tmpit.next();
 348             if (!tmptofn.containsKey(tmp))
 349               tmptofn.put(tmp, new HashSet<FlatNode>());
 350             tmptofn.get(tmp).addAll(prevmap.get(tmp));
 351           }
 352       }
 353
 354       if (delayedset.contains(fn)) {
 355         //If the node is in the second set, check our readset
 356         TempDescriptor readset[]=fn.readsTemps();
 357         for(int i=0;i<readset.length;i++) {
 358           TempDescriptor tmp=readset[i];
 359           if (tmptofn.containsKey(tmp)) {
 360             livenodes.addAll(tmptofn.get(tmp)); //Add live nodes
 361             unionset.addAll(tmptofn.get(tmp));
 362           }
 363         }
 364
 365         //Do kills
 366         TempDescriptor writeset[]=fn.writesTemps();
 367         for(int i=0;i<writeset.length;i++) {
 368           TempDescriptor tmp=writeset[i];
 369           tmptofn.remove(tmp);
 370         }
 371       } else {
 372         //If the node is in the first set, search over what we write
 373         //We write -- our reads are done
 374         TempDescriptor writeset[]=fn.writesTemps();
 375         for(int i=0;i<writeset.length;i++) {
 376           TempDescriptor tmp=writeset[i];
 377           HashSet<FlatNode> set=new HashSet<FlatNode>();
 378           tmptofn.put(tmp,set);
 379           set.add(fn);
 380         }
 381         if (fn.numNext()>1) {
 382           Set<FlatNode> branchset=branchmap.get((FlatCondBranch)fn);
 383           for(Iterator<FlatNode> brit=branchset.iterator();brit.hasNext();) {
 384             FlatNode brfn=brit.next();
 385             if (unionset.contains(brfn)) {
 386               //This branch is important--need to remember how it goes
 387               livenodes.add(fn);
 388               unionset.add(fn);
 389             }
 390           }
 391         }
 392       }
 393       if (!map.containsKey(fn)||!map.get(fn).equals(tmptofn)) {
 394         map.put(fn, tmptofn);
 395         //enqueue next ndoes
 396         for(int i=0;i<fn.numNext();i++)
 397           toanalyze.add(fn.getNext(i));
 398       }
 399     }
 400     return livenodes;
 401   }
 402
 403   public static Set<FlatNode> getNext(FlatNode fn, int i, Set<FlatNode> delayset, LocalityBinding lb, LocalityAnalysis locality, boolean contpastnode) {
 404     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 405     FlatNode fnnext=fn.getNext(i);
 406     HashSet<FlatNode> reachable=new HashSet<FlatNode>();
 407
 408     if (delayset.contains(fnnext)||atomictable.get(fnnext).intValue()==0) {
 409       reachable.add(fnnext);
 410       return reachable;
 411     }
 412     Stack<FlatNode> nodes=new Stack<FlatNode>();
 413     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 414     nodes.push(fnnext);
 415     if (contpastnode)
 416       visited.add(fn);
 417
 418     while(!nodes.isEmpty()) {
 419       FlatNode fn2=nodes.pop();
 420       if (visited.contains(fn2))
 421         continue;
 422       visited.add(fn2);
 423       for (int j=0;j<fn2.numNext();j++) {
 424         FlatNode fn2next=fn2.getNext(j);
 425         if (delayset.contains(fn2next)||atomictable.get(fn2next).intValue()==0) {
 426           reachable.add(fn2next);
 427         } else
 428           nodes.push(fn2next);
 429       }
 430     }
 431     return reachable;
 432   }
 433
 434   public void analyzeMethod(LocalityBinding lb) {
 435     MethodDescriptor md=lb.getMethod();
 436     FlatMethod fm=state.getMethodFlat(md);
 437     HashSet<FlatNode> cannotdelay=new HashSet<FlatNode>();
 438     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 439     if (lb.isAtomic()) {
 440       //We are in a transaction already...
 441       //skip past this method or something
 442       return;
 443     }
 444
 445     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 446     toanalyze.addAll(fm.getNodeSet());
 447
 448     //Build the hashtables
 449     Hashtable<FlatNode, HashSet<TempDescriptor>> nodelaytemps=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 450     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldswr=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 451     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarrayswr=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 452     Hashtable<FlatNode, HashSet<FieldDescriptor>> nodelayfieldsrd=new Hashtable<FlatNode, HashSet<FieldDescriptor>>();
 453     Hashtable<FlatNode, HashSet<TypeDescriptor>> nodelayarraysrd=new Hashtable<FlatNode, HashSet<TypeDescriptor>>();
 454
 455     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 456     //Effect of adding something to nodelay set is to move it up past everything in delay set
 457     //Have to make sure we can do this commute
 458
 459     while(!toanalyze.isEmpty()) {
 460       FlatNode fn=toanalyze.iterator().next();
 461       toanalyze.remove(fn);
 462
 463       boolean isatomic=atomictable.get(fn).intValue()>0;
 464
 465       if (!isatomic)
 466         continue;
 467       boolean isnodelay=false;
 468
 469       /* Compute incoming nodelay sets */
 470       HashSet<TempDescriptor> nodelaytempset=new HashSet<TempDescriptor>();
 471       HashSet<FieldDescriptor> nodelayfieldwrset=new HashSet<FieldDescriptor>();
 472       HashSet<TypeDescriptor> nodelayarraywrset=new HashSet<TypeDescriptor>();
 473       HashSet<FieldDescriptor> nodelayfieldrdset=new HashSet<FieldDescriptor>();
 474       HashSet<TypeDescriptor> nodelayarrayrdset=new HashSet<TypeDescriptor>();
 475       for(int i=0;i<fn.numNext();i++) {
 476         if (nodelaytemps.containsKey(fn.getNext(i)))
 477           nodelaytempset.addAll(nodelaytemps.get(fn.getNext(i)));
 478         //do field/array write sets
 479         if (nodelayfieldswr.containsKey(fn.getNext(i)))
 480           nodelayfieldwrset.addAll(nodelayfieldswr.get(fn.getNext(i)));
 481         if (nodelayarrayswr.containsKey(fn.getNext(i)))
 482           nodelayarraywrset.addAll(nodelayarrayswr.get(fn.getNext(i)));
 483         //do read sets
 484         if (nodelayfieldsrd.containsKey(fn.getNext(i)))
 485           nodelayfieldrdset.addAll(nodelayfieldsrd.get(fn.getNext(i)));
 486         if (nodelayarraysrd.containsKey(fn.getNext(i)))
 487           nodelayarrayrdset.addAll(nodelayarraysrd.get(fn.getNext(i)));
 488       }
 489
 490       /* Check our temp write set */
 491
 492       TempDescriptor writeset[]=fn.writesTemps();
 493       for(int i=0;i<writeset.length;i++) {
 494         TempDescriptor tmp=writeset[i];
 495         if (nodelaytempset.contains(tmp)) {
 496           //We are writing to a nodelay temp
 497           //Therefore we are nodelay
 498           isnodelay=true;
 499           //Kill temp we wrote to
 500           nodelaytempset.remove(tmp);
 501         }
 502       }
 503
 504       //See if flatnode is definitely no delay
 505       if (fn.kind()==FKind.FlatCall) {
 506         isnodelay=true;
 507         //Have to deal with fields/arrays
 508         FlatCall fcall=(FlatCall)fn;
 509         MethodDescriptor mdcall=fcall.getMethod();
 510         nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 511         nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 512         //Have to deal with field/array reads
 513         nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 514         nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 515       }
 516
 517       //Delay branches if possible
 518       if (fn.kind()==FKind.FlatCondBranch) {
 519         Set<FlatNode> leftset=getNext(fn, 0, cannotdelay, lb, locality,true);
 520         Set<FlatNode> rightset=getNext(fn, 1, cannotdelay, lb, locality,true);
 521         if (leftset.size()>0&&rightset.size()>0&&
 522             !leftset.equals(rightset)||leftset.size()>1)
 523           isnodelay=true;
 524       }
 525
 526       //Check for field conflicts
 527       if (fn.kind()==FKind.FlatSetFieldNode) {
 528         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 529         //write conflicts
 530         if (nodelayfieldwrset.contains(fd))
 531           isnodelay=true;
 532         //read
 533         if (nodelayfieldrdset.contains(fd))
 534           isnodelay=true;
 535       }
 536
 537       if (fn.kind()==FKind.FlatFieldNode) {
 538         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 539         //write conflicts
 540         if (nodelayfieldwrset.contains(fd))
 541           isnodelay=true;
 542       }
 543       //Check for array conflicts
 544       if (fn.kind()==FKind.FlatSetElementNode) {
 545         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 546         //check for write conflicts
 547         if (nodelayarraywrset.contains(td))
 548           isnodelay=true;
 549         //check for read conflicts
 550         if (nodelayarrayrdset.contains(td))
 551           isnodelay=true;
 552       }
 553       if (fn.kind()==FKind.FlatElementNode) {
 554         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 555         //check for write conflicts
 556         if (nodelayarraywrset.contains(td))
 557           isnodelay=true;
 558       }
 559
 560       //If we are no delay, then the temps we read are no delay
 561       if (isnodelay) {
 562         /* Add our read set */
 563         TempDescriptor readset[]=fn.readsTemps();
 564         for(int i=0;i<readset.length;i++) {
 565           TempDescriptor tmp=readset[i];
 566           nodelaytempset.add(tmp);
 567         }
 568         cannotdelay.add(fn);
 569
 570         if (branchmap.containsKey(fn)) {
 571           Set<FlatCondBranch> fcbset=branchmap.get(fn);
 572           for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
 573             FlatCondBranch fcb=fcbit.next();
 574             cannotdelay.add(fcb);
 575             nodelaytempset.add(fcb.getTest());
 576           }
 577         }
 578         /* Do we write to fields */
 579         if (fn.kind()==FKind.FlatSetFieldNode) {
 580           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 581         }
 582         /* Do we read from fields */
 583         if (fn.kind()==FKind.FlatFieldNode) {
 584           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 585         }
 586         /* Do we write to arrays */
 587         if (fn.kind()==FKind.FlatSetElementNode) {
 588           //have to do expansion
 589           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 590         }
 591         /* Do we read from arrays */
 592         if (fn.kind()==FKind.FlatElementNode) {
 593           //have to do expansion
 594           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 595         }
 596       } else {
 597         //Need to know which objects to lock on
 598         switch(fn.kind()) {
 599           //TODO: Can improve by only locking if there is a field that requires a lock
 600         case FKind.FlatSetFieldNode: {
 601           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 602           nodelaytempset.add(fsfn.getDst());
 603           break;
 604         }
 605         case FKind.FlatSetElementNode: {
 606           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 607           nodelaytempset.add(fsen.getDst());
 608           break;
 609         }
 610         case FKind.FlatFieldNode: {
 611           FlatFieldNode ffn=(FlatFieldNode)fn;
 612           nodelaytempset.add(ffn.getSrc());
 613           break;
 614         }
 615         case FKind.FlatElementNode: {
 616           FlatElementNode fen=(FlatElementNode)fn;
 617           nodelaytempset.add(fen.getSrc());
 618           break;
 619         }
 620         }
 621       }
 622
 623       boolean changed=false;
 624       //See if we need to propagate changes
 625       if (!nodelaytemps.containsKey(fn)||
 626           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 627         nodelaytemps.put(fn, nodelaytempset);
 628         changed=true;
 629       }
 630
 631       //See if we need to propagate changes
 632       if (!nodelayfieldswr.containsKey(fn)||
 633           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 634         nodelayfieldswr.put(fn, nodelayfieldwrset);
 635         changed=true;
 636       }
 637
 638       //See if we need to propagate changes
 639       if (!nodelayfieldsrd.containsKey(fn)||
 640           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 641         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 642         changed=true;
 643       }
 644
 645       //See if we need to propagate changes
 646       if (!nodelayarrayswr.containsKey(fn)||
 647           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 648         nodelayarrayswr.put(fn, nodelayarraywrset);
 649         changed=true;
 650       }
 651
 652       //See if we need to propagate changes
 653       if (!nodelayarraysrd.containsKey(fn)||
 654           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 655         nodelayarraysrd.put(fn, nodelayarrayrdset);
 656         changed=true;
 657       }
 658
 659       if (changed)
 660         for(int i=0;i<fn.numPrev();i++)
 661           toanalyze.add(fn.getPrev(i));
 662     }//end of while loop
 663
 664     if (lb.getHasAtomic()) {
 665       cannotdelaymap.put(lb, cannotdelay);
 666     }
 667   } //end of method
 668
 669   //Problems:
 670   //1) we acquire locks too early to object we don't need to yet
 671   //2) we don't realize that certain operations have side effects
 672
 673   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 674     //You are in not ready set if:
 675     //I. You read a not ready temp
 676     //II. You access a field or element and
 677     //(A). You are not in the cannot delay set
 678     //(B). You read a field/element in the transactional set
 679     //(C). The source didn't have a transactional read on it
 680
 681     MethodDescriptor md=lb.getMethod();
 682     FlatMethod fm=state.getMethodFlat(md);
 683     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 684     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 685     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 686     toanalyze.addAll(fm.getNodeSet());
 687     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 688
 689     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 690     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 691
 692     while(!toanalyze.isEmpty()) {
 693       FlatNode fn=toanalyze.iterator().next();
 694       toanalyze.remove(fn);
 695       boolean isatomic=atomictable.get(fn).intValue()>0;
 696
 697       if (!isatomic)
 698         continue;
 699
 700       //Compute initial notready set
 701       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 702       for(int i=0;i<fn.numPrev();i++) {
 703         if (notreadymap.containsKey(fn.getPrev(i)))
 704           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 705       }
 706
 707       //Are we ready
 708       boolean notready=false;
 709
 710       //Test our read set first
 711       TempDescriptor readset[]=fn.readsTemps();
 712       for(int i=0;i<readset.length;i++) {
 713         TempDescriptor tmp=readset[i];
 714         if (notreadyset.contains(tmp)) {
 715           notready=true;
 716           break;
 717         }
 718       }
 719
 720       if (!notready&&!cannotdelay.contains(fn)) {
 721         switch(fn.kind()) {
 722         case FKind.FlatFieldNode: {
 723           FlatFieldNode ffn=(FlatFieldNode)fn;
 724           if (!dcopts.getFields().contains(ffn.getField())) {
 725             break;
 726           }
 727           TempDescriptor tmp=ffn.getSrc();
 728           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 729           if (tfpset!=null) {
 730             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 731               TempFlatPair tfp=tfpit.next();
 732               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 733                 //if a source didn't need a translation and we are
 734                 //accessing it, it did...so therefore we are note
 735                 //ready
 736                 notready=true;
 737                 break;
 738               }
 739             }
 740           }
 741           break;
 742         }
 743         case FKind.FlatSetFieldNode: {
 744           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 745           TempDescriptor tmp=fsfn.getDst();
 746           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 747           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 748
 749           if (tfpset!=null) {
 750             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 751               TempFlatPair tfp=tfpit.next();
 752               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 753                 //if a source didn't need a translation and we are
 754                 //accessing it, it did...so therefore we are note
 755                 //ready
 756                 notready=true;
 757                 break;
 758               }
 759             }
 760           }
 761           break;
 762         }
 763         case FKind.FlatElementNode: {
 764           FlatElementNode fen=(FlatElementNode)fn;
 765           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 766             break;
 767           }
 768           TempDescriptor tmp=fen.getSrc();
 769           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 770           if (tfpset!=null) {
 771             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 772               TempFlatPair tfp=tfpit.next();
 773               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 774                 //if a source didn't need a translation and we are
 775                 //accessing it, it did...so therefore we are note
 776                 //ready
 777                 notready=true;
 778                 break;
 779               }
 780             }
 781           }
 782           break;
 783         }
 784         case FKind.FlatSetElementNode: {
 785           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 786           TempDescriptor tmp=fsen.getDst();
 787           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 788           if (tfpset!=null) {
 789             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 790               TempFlatPair tfp=tfpit.next();
 791               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 792                 //if a source didn't need a translation and we are
 793                 //accessing it, it did...so therefore we are note
 794                 //ready
 795                 notready=true;
 796                 break;
 797               }
 798             }
 799           }
 800           break;
 801         }
 802         }
 803       }
 804
 805       if (!notready) {
 806         //See if we depend on a conditional branch that is not ready
 807         Set<FlatCondBranch> branchset=branchmap.get(fn);
 808         if (branchset!=null)
 809           for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
 810             FlatCondBranch fcb=branchit.next();
 811             if (notreadynodes.contains(fcb)) {
 812               //if we depend on a branch that isn't ready, we aren't ready
 813               notready=true;
 814               break;
 815             }
 816           }
 817       }
 818
 819
 820       //Fix up things based on our status
 821       if (notready) {
 822         if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
 823           //enqueue everything in our dependence set
 824           Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
 825           toanalyze.addAll(branchdepset);
 826         }
 827
 828         //add us to the list
 829         notreadynodes.add(fn);
 830
 831         //Add our writes
 832         TempDescriptor writeset[]=fn.writesTemps();
 833         for(int i=0;i<writeset.length;i++) {
 834           TempDescriptor tmp=writeset[i];
 835           notreadyset.add(tmp);
 836         }
 837       } else {
 838         //Kill our writes
 839         TempDescriptor writeset[]=fn.writesTemps();
 840         for(int i=0;i<writeset.length;i++) {
 841           TempDescriptor tmp=writeset[i];
 842           notreadyset.remove(tmp);
 843         }
 844       }
 845
 846       //See if we need to propagate changes
 847       if (!notreadymap.containsKey(fn)||
 848           !notreadymap.get(fn).equals(notreadyset)) {
 849         notreadymap.put(fn, notreadyset);
 850         for(int i=0;i<fn.numNext();i++)
 851           toanalyze.add(fn.getNext(i));
 852       }
 853     } //end of while
 854     return notreadynodes;
 855   } //end of computeNotReadySet
 856
 857   public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
 858     MethodDescriptor md=lb.getMethod();
 859     FlatMethod fm=state.getMethodFlat(md);
 860     Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
 861     DomTree postdt=new DomTree(fm, true);
 862     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 863       FlatNode fn=fnit.next();
 864       if (fn.kind()!=FKind.FlatCondBranch)
 865         continue;
 866       FlatCondBranch fcb=(FlatCondBranch)fn;
 867       //only worry about fcb inside of transactions
 868       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 869         continue;
 870       FlatNode postdom=postdt.idom(fcb);
 871
 872       //Reverse the mapping
 873       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 874       condmap.put(fcb, fnset);
 875     }
 876     return condmap;
 877   }
 878
 879   public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
 880     MethodDescriptor md=lb.getMethod();
 881     FlatMethod fm=state.getMethodFlat(md);
 882     Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
 883     DomTree postdt=new DomTree(fm, true);
 884     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 885       FlatNode fn=fnit.next();
 886       if (fn.kind()!=FKind.FlatCondBranch)
 887         continue;
 888       FlatCondBranch fcb=(FlatCondBranch)fn;
 889       //only worry about fcb inside of transactions
 890       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 891         continue;
 892       FlatNode postdom=postdt.idom(fcb);
 893
 894       //Reverse the mapping
 895       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 896       for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
 897         FlatNode fn2=fnit2.next();
 898         if (!condmap.containsKey(fn2))
 899           condmap.put(fn2,new HashSet<FlatCondBranch>());
 900         condmap.get(fn2).add(fcb);
 901       }
 902     }
 903     return condmap;
 904   }
 905
 906   public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
 907     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 908     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 909     toanalyze.add(first);
 910
 911     while(!toanalyze.isEmpty()) {
 912       FlatNode fn=toanalyze.iterator().next();
 913       toanalyze.remove(fn);
 914
 915       //already examined or exit node
 916       if (visited.contains(fn)||fn==last)
 917         continue;
 918
 919       //out of transaction
 920       if (locality.getAtomic(lb).get(fn).intValue()==0)
 921         continue;
 922
 923       visited.add(fn);
 924       for(int i=0;i<fn.numNext();i++) {
 925         FlatNode fnext=fn.getNext(i);
 926         toanalyze.add(fnext);
 927       }
 928     }
 929     return visited;
 930   } //end of computeBranchSet
 931 } //end of class