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