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         isnodelay=true;
 513         //Have to deal with fields/arrays
 514         FlatCall fcall=(FlatCall)fn;
 515         MethodDescriptor mdcall=fcall.getMethod();
 516         nodelayfieldwrset.addAll(gft.getFieldsAll(mdcall));
 517         nodelayarraywrset.addAll(typeanalysis.expandSet(gft.getArraysAll(mdcall)));
 518         //Have to deal with field/array reads
 519         nodelayfieldrdset.addAll(gft.getFieldsRdAll(mdcall));
 520         nodelayarrayrdset.addAll(typeanalysis.expandSet(gft.getArraysRdAll(mdcall)));
 521       }
 522
 523       //Delay branches if possible
 524       if (fn.kind()==FKind.FlatCondBranch) {
 525         Set<FlatNode> leftset=getNext(fn, 0, cannotdelay, lb, locality,true);
 526         Set<FlatNode> rightset=getNext(fn, 1, cannotdelay, lb, locality,true);
 527         if (leftset.size()>0&&rightset.size()>0&&
 528             !leftset.equals(rightset)||leftset.size()>1)
 529           isnodelay=true;
 530       }
 531
 532       //Check for field conflicts
 533       if (fn.kind()==FKind.FlatSetFieldNode) {
 534         FieldDescriptor fd=((FlatSetFieldNode)fn).getField();
 535         //write conflicts
 536         if (nodelayfieldwrset.contains(fd))
 537           isnodelay=true;
 538         //read
 539         if (nodelayfieldrdset.contains(fd))
 540           isnodelay=true;
 541       }
 542
 543       if (fn.kind()==FKind.FlatFieldNode) {
 544         FieldDescriptor fd=((FlatFieldNode)fn).getField();
 545         //write conflicts
 546         if (nodelayfieldwrset.contains(fd))
 547           isnodelay=true;
 548       }
 549       //Check for array conflicts
 550       if (fn.kind()==FKind.FlatSetElementNode) {
 551         TypeDescriptor td=((FlatSetElementNode)fn).getDst().getType();
 552         //check for write conflicts
 553         if (nodelayarraywrset.contains(td))
 554           isnodelay=true;
 555         //check for read conflicts
 556         if (nodelayarrayrdset.contains(td))
 557           isnodelay=true;
 558       }
 559       if (fn.kind()==FKind.FlatElementNode) {
 560         TypeDescriptor td=((FlatElementNode)fn).getSrc().getType();
 561         //check for write conflicts
 562         if (nodelayarraywrset.contains(td))
 563           isnodelay=true;
 564       }
 565
 566       //If we are no delay, then the temps we read are no delay
 567       if (isnodelay) {
 568         /* Add our read set */
 569         TempDescriptor readset[]=fn.readsTemps();
 570         for(int i=0;i<readset.length;i++) {
 571           TempDescriptor tmp=readset[i];
 572           nodelaytempset.add(tmp);
 573         }
 574         cannotdelay.add(fn);
 575
 576         if (branchmap.containsKey(fn)) {
 577           Set<FlatCondBranch> fcbset=branchmap.get(fn);
 578           for(Iterator<FlatCondBranch> fcbit=fcbset.iterator();fcbit.hasNext();) {
 579             FlatCondBranch fcb=fcbit.next();
 580             cannotdelay.add(fcb);
 581             nodelaytempset.add(fcb.getTest());
 582           }
 583         }
 584         /* Do we write to fields */
 585         if (fn.kind()==FKind.FlatSetFieldNode) {
 586           nodelayfieldwrset.add(((FlatSetFieldNode)fn).getField());
 587         }
 588         /* Do we read from fields */
 589         if (fn.kind()==FKind.FlatFieldNode) {
 590           nodelayfieldrdset.add(((FlatFieldNode)fn).getField());
 591         }
 592         /* Do we write to arrays */
 593         if (fn.kind()==FKind.FlatSetElementNode) {
 594           //have to do expansion
 595           nodelayarraywrset.addAll(typeanalysis.expand(((FlatSetElementNode)fn).getDst().getType()));
 596         }
 597         /* Do we read from arrays */
 598         if (fn.kind()==FKind.FlatElementNode) {
 599           //have to do expansion
 600           nodelayarrayrdset.addAll(typeanalysis.expand(((FlatElementNode)fn).getSrc().getType()));
 601         }
 602       } else {
 603         //Need to know which objects to lock on
 604         switch(fn.kind()) {
 605           //TODO: Can improve by only locking if there is a field that requires a lock
 606         case FKind.FlatSetFieldNode: {
 607           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 608           nodelaytempset.add(fsfn.getDst());
 609           break;
 610         }
 611         case FKind.FlatSetElementNode: {
 612           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 613           nodelaytempset.add(fsen.getDst());
 614           break;
 615         }
 616         case FKind.FlatFieldNode: {
 617           FlatFieldNode ffn=(FlatFieldNode)fn;
 618           nodelaytempset.add(ffn.getSrc());
 619           break;
 620         }
 621         case FKind.FlatElementNode: {
 622           FlatElementNode fen=(FlatElementNode)fn;
 623           nodelaytempset.add(fen.getSrc());
 624           break;
 625         }
 626         }
 627       }
 628
 629       boolean changed=false;
 630       //See if we need to propagate changes
 631       if (!nodelaytemps.containsKey(fn)||
 632           !nodelaytemps.get(fn).equals(nodelaytempset)) {
 633         nodelaytemps.put(fn, nodelaytempset);
 634         changed=true;
 635       }
 636
 637       //See if we need to propagate changes
 638       if (!nodelayfieldswr.containsKey(fn)||
 639           !nodelayfieldswr.get(fn).equals(nodelayfieldwrset)) {
 640         nodelayfieldswr.put(fn, nodelayfieldwrset);
 641         changed=true;
 642       }
 643
 644       //See if we need to propagate changes
 645       if (!nodelayfieldsrd.containsKey(fn)||
 646           !nodelayfieldsrd.get(fn).equals(nodelayfieldrdset)) {
 647         nodelayfieldsrd.put(fn, nodelayfieldrdset);
 648         changed=true;
 649       }
 650
 651       //See if we need to propagate changes
 652       if (!nodelayarrayswr.containsKey(fn)||
 653           !nodelayarrayswr.get(fn).equals(nodelayarraywrset)) {
 654         nodelayarrayswr.put(fn, nodelayarraywrset);
 655         changed=true;
 656       }
 657
 658       //See if we need to propagate changes
 659       if (!nodelayarraysrd.containsKey(fn)||
 660           !nodelayarraysrd.get(fn).equals(nodelayarrayrdset)) {
 661         nodelayarraysrd.put(fn, nodelayarrayrdset);
 662         changed=true;
 663       }
 664
 665       if (changed)
 666         for(int i=0;i<fn.numPrev();i++)
 667           toanalyze.add(fn.getPrev(i));
 668     }//end of while loop
 669
 670     if (lb.getHasAtomic()) {
 671       cannotdelaymap.put(lb, cannotdelay);
 672     }
 673   } //end of method
 674
 675   //Problems:
 676   //1) we acquire locks too early to object we don't need to yet
 677   //2) we don't realize that certain operations have side effects
 678
 679   public HashSet<FlatNode> computeNotReadySet(LocalityBinding lb, HashSet<FlatNode> cannotdelay) {
 680     //You are in not ready set if:
 681     //I. You read a not ready temp
 682     //II. You access a field or element and
 683     //(A). You are not in the cannot delay set
 684     //(B). You read a field/element in the transactional set
 685     //(C). The source didn't have a transactional read on it
 686
 687     MethodDescriptor md=lb.getMethod();
 688     FlatMethod fm=state.getMethodFlat(md);
 689     Hashtable<FlatNode, Integer> atomictable=locality.getAtomic(lb);
 690     HashSet<FlatNode> notreadynodes=new HashSet<FlatNode>();
 691     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 692     toanalyze.addAll(fm.getNodeSet());
 693     Hashtable<FlatNode, HashSet<TempDescriptor>> notreadymap=new Hashtable<FlatNode, HashSet<TempDescriptor>>();
 694
 695     Hashtable<FlatCondBranch, Set<FlatNode>> revbranchmap=revGetBranchSet(lb);
 696     Hashtable<FlatNode, Set<FlatCondBranch>> branchmap=getBranchSet(lb);
 697
 698     while(!toanalyze.isEmpty()) {
 699       FlatNode fn=toanalyze.iterator().next();
 700       toanalyze.remove(fn);
 701       boolean isatomic=atomictable.get(fn).intValue()>0;
 702
 703       if (!isatomic)
 704         continue;
 705
 706       //Compute initial notready set
 707       HashSet<TempDescriptor> notreadyset=new HashSet<TempDescriptor>();
 708       for(int i=0;i<fn.numPrev();i++) {
 709         if (notreadymap.containsKey(fn.getPrev(i)))
 710           notreadyset.addAll(notreadymap.get(fn.getPrev(i)));
 711       }
 712
 713       //Are we ready
 714       boolean notready=false;
 715
 716       //Test our read set first
 717       TempDescriptor readset[]=fn.readsTemps();
 718       for(int i=0;i<readset.length;i++) {
 719         TempDescriptor tmp=readset[i];
 720         if (notreadyset.contains(tmp)) {
 721           notready=true;
 722           break;
 723         }
 724       }
 725
 726       if (!notready&&!cannotdelay.contains(fn)) {
 727         switch(fn.kind()) {
 728         case FKind.FlatFieldNode: {
 729           FlatFieldNode ffn=(FlatFieldNode)fn;
 730           if (!dcopts.getFields().contains(ffn.getField())) {
 731             break;
 732           }
 733           TempDescriptor tmp=ffn.getSrc();
 734           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 735           if (tfpset!=null) {
 736             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 737               TempFlatPair tfp=tfpit.next();
 738               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 739                 //if a source didn't need a translation and we are
 740                 //accessing it, it did...so therefore we are note
 741                 //ready
 742                 notready=true;
 743                 break;
 744               }
 745             }
 746           }
 747           break;
 748         }
 749         case FKind.FlatSetFieldNode: {
 750           FlatSetFieldNode fsfn=(FlatSetFieldNode)fn;
 751           TempDescriptor tmp=fsfn.getDst();
 752           Hashtable<TempDescriptor, Set<TempFlatPair>> tmpmap=dcopts.getMap(lb).get(fn);
 753           Set<TempFlatPair> tfpset=tmpmap!=null?tmpmap.get(tmp):null;
 754
 755           if (tfpset!=null) {
 756             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 757               TempFlatPair tfp=tfpit.next();
 758               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 759                 //if a source didn't need a translation and we are
 760                 //accessing it, it did...so therefore we are note
 761                 //ready
 762                 notready=true;
 763                 break;
 764               }
 765             }
 766           }
 767           break;
 768         }
 769         case FKind.FlatElementNode: {
 770           FlatElementNode fen=(FlatElementNode)fn;
 771           if (!dcopts.getArrays().contains(fen.getSrc().getType())) {
 772             break;
 773           }
 774           TempDescriptor tmp=fen.getSrc();
 775           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 776           if (tfpset!=null) {
 777             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 778               TempFlatPair tfp=tfpit.next();
 779               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 780                 //if a source didn't need a translation and we are
 781                 //accessing it, it did...so therefore we are note
 782                 //ready
 783                 notready=true;
 784                 break;
 785               }
 786             }
 787           }
 788           break;
 789         }
 790         case FKind.FlatSetElementNode: {
 791           FlatSetElementNode fsen=(FlatSetElementNode)fn;
 792           TempDescriptor tmp=fsen.getDst();
 793           Set<TempFlatPair> tfpset=dcopts.getMap(lb).get(fn).get(tmp);
 794           if (tfpset!=null) {
 795             for(Iterator<TempFlatPair> tfpit=tfpset.iterator();tfpit.hasNext();) {
 796               TempFlatPair tfp=tfpit.next();
 797               if (!dcopts.getNeedSrcTrans(lb, tfp.f)) {
 798                 //if a source didn't need a translation and we are
 799                 //accessing it, it did...so therefore we are note
 800                 //ready
 801                 notready=true;
 802                 break;
 803               }
 804             }
 805           }
 806           break;
 807         }
 808         }
 809       }
 810
 811       if (!notready) {
 812         //See if we depend on a conditional branch that is not ready
 813         Set<FlatCondBranch> branchset=branchmap.get(fn);
 814         if (branchset!=null)
 815           for(Iterator<FlatCondBranch> branchit=branchset.iterator();branchit.hasNext();) {
 816             FlatCondBranch fcb=branchit.next();
 817             if (notreadynodes.contains(fcb)) {
 818               //if we depend on a branch that isn't ready, we aren't ready
 819               notready=true;
 820               break;
 821             }
 822           }
 823       }
 824
 825
 826       //Fix up things based on our status
 827       if (notready) {
 828         if (fn.kind()==FKind.FlatCondBranch&&!notreadynodes.contains(fn)) {
 829           //enqueue everything in our dependence set
 830           Set<FlatNode> branchdepset=revbranchmap.get((FlatCondBranch)fn);
 831           toanalyze.addAll(branchdepset);
 832         }
 833
 834         //add us to the list
 835         notreadynodes.add(fn);
 836
 837         //Add our writes
 838         TempDescriptor writeset[]=fn.writesTemps();
 839         for(int i=0;i<writeset.length;i++) {
 840           TempDescriptor tmp=writeset[i];
 841           notreadyset.add(tmp);
 842         }
 843       } else {
 844         //Kill our writes
 845         TempDescriptor writeset[]=fn.writesTemps();
 846         for(int i=0;i<writeset.length;i++) {
 847           TempDescriptor tmp=writeset[i];
 848           notreadyset.remove(tmp);
 849         }
 850       }
 851
 852       //See if we need to propagate changes
 853       if (!notreadymap.containsKey(fn)||
 854           !notreadymap.get(fn).equals(notreadyset)) {
 855         notreadymap.put(fn, notreadyset);
 856         for(int i=0;i<fn.numNext();i++)
 857           toanalyze.add(fn.getNext(i));
 858       }
 859     } //end of while
 860     return notreadynodes;
 861   } //end of computeNotReadySet
 862
 863   public Hashtable<FlatCondBranch, Set<FlatNode>> revGetBranchSet(LocalityBinding lb) {
 864     MethodDescriptor md=lb.getMethod();
 865     FlatMethod fm=state.getMethodFlat(md);
 866     Hashtable<FlatCondBranch, Set<FlatNode>> condmap=new Hashtable<FlatCondBranch, Set<FlatNode>>();
 867     DomTree postdt=new DomTree(fm, true);
 868     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 869       FlatNode fn=fnit.next();
 870       if (fn.kind()!=FKind.FlatCondBranch)
 871         continue;
 872       FlatCondBranch fcb=(FlatCondBranch)fn;
 873       //only worry about fcb inside of transactions
 874       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 875         continue;
 876       FlatNode postdom=postdt.idom(fcb);
 877
 878       //Reverse the mapping
 879       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 880       condmap.put(fcb, fnset);
 881     }
 882     return condmap;
 883   }
 884
 885   public Hashtable<FlatNode, Set<FlatCondBranch>> getBranchSet(LocalityBinding lb) {
 886     MethodDescriptor md=lb.getMethod();
 887     FlatMethod fm=state.getMethodFlat(md);
 888     Hashtable<FlatNode, Set<FlatCondBranch>> condmap=new Hashtable<FlatNode, Set<FlatCondBranch>>();
 889     DomTree postdt=new DomTree(fm, true);
 890     for(Iterator<FlatNode> fnit=fm.getNodeSet().iterator();fnit.hasNext();) {
 891       FlatNode fn=fnit.next();
 892       if (fn.kind()!=FKind.FlatCondBranch)
 893         continue;
 894       FlatCondBranch fcb=(FlatCondBranch)fn;
 895       //only worry about fcb inside of transactions
 896       if (locality.getAtomic(lb).get(fcb).intValue()==0)
 897         continue;
 898       FlatNode postdom=postdt.idom(fcb);
 899
 900       //Reverse the mapping
 901       Set<FlatNode> fnset=computeBranchSet(lb, fcb, postdom);
 902       for(Iterator<FlatNode>fnit2=fnset.iterator();fnit2.hasNext();) {
 903         FlatNode fn2=fnit2.next();
 904         if (!condmap.containsKey(fn2))
 905           condmap.put(fn2,new HashSet<FlatCondBranch>());
 906         condmap.get(fn2).add(fcb);
 907       }
 908     }
 909     return condmap;
 910   }
 911
 912   public Set<FlatNode> computeBranchSet(LocalityBinding lb, FlatNode first, FlatNode last) {
 913     HashSet<FlatNode> toanalyze=new HashSet<FlatNode>();
 914     HashSet<FlatNode> visited=new HashSet<FlatNode>();
 915     toanalyze.add(first);
 916
 917     while(!toanalyze.isEmpty()) {
 918       FlatNode fn=toanalyze.iterator().next();
 919       toanalyze.remove(fn);
 920
 921       //already examined or exit node
 922       if (visited.contains(fn)||fn==last)
 923         continue;
 924
 925       //out of transaction
 926       if (locality.getAtomic(lb).get(fn).intValue()==0)
 927         continue;
 928
 929       visited.add(fn);
 930       for(int i=0;i<fn.numNext();i++) {
 931         FlatNode fnext=fn.getNext(i);
 932         toanalyze.add(fnext);
 933       }
 934     }
 935     return visited;
 936   } //end of computeBranchSet
 937 } //end of class