Robust/src/Analysis/Locality/LocalityAnalysis.java

   1 package Analysis.Locality;
   2
   3 import Analysis.Liveness;
   4 import java.util.*;
   5 import Analysis.CallGraph.CallGraph;
   6 import IR.SymbolTable;
   7 import IR.State;
   8 import IR.TypeUtil;
   9 import IR.MethodDescriptor;
  10 import IR.Flat.*;
  11 import Analysis.Liveness;
  12 import IR.ClassDescriptor;
  13
  14 public class LocalityAnalysis {
  15   State state;
  16   Set lbtovisit;
  17   Hashtable<LocalityBinding,LocalityBinding> discovered;
  18   Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
  19   Hashtable<LocalityBinding, Set<LocalityBinding>> calldep;
  20   Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
  21   Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
  22   Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
  23   Hashtable<ClassDescriptor, Set<LocalityBinding>> classtolb;
  24   Hashtable<MethodDescriptor, Set<LocalityBinding>> methodtolb;
  25   private LocalityBinding lbmain;
  26   private LocalityBinding lbrun;
  27   private LocalityBinding lbexecute;
  28
  29   CallGraph callgraph;
  30   TypeUtil typeutil;
  31   public static final Integer LOCAL=new Integer(0);
  32   public static final Integer GLOBAL=new Integer(1);
  33   public static final Integer EITHER=new Integer(2);
  34   public static final Integer CONFLICT=new Integer(3);
  35
  36   public static final Integer STMEITHER=new Integer(0);
  37   public static final Integer SCRATCH=new Integer(4);
  38   public static final Integer NORMAL=new Integer(8);
  39   public static final Integer STMCONFLICT=new Integer(12);
  40
  41   public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  42     this.typeutil=typeutil;
  43     this.state=state;
  44     this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
  45     this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
  46     this.calldep=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
  47     this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
  48     this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
  49     this.lbtovisit=new HashSet();
  50     this.callgraph=callgraph;
  51     this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
  52     this.classtolb=new Hashtable<ClassDescriptor, Set<LocalityBinding>>();
  53     this.methodtolb=new Hashtable<MethodDescriptor, Set<LocalityBinding>>();
  54     doAnalysis();
  55   }
  56
  57   public LocalityBinding getMain() {
  58     return lbmain;
  59   }
  60
  61   /** This method returns the set of LocalityBindings that a given
  62    * flatcall could invoke */
  63
  64   public LocalityBinding getBinding(LocalityBinding currlb, FlatCall fc) {
  65     boolean isatomic=getAtomic(currlb).get(fc).intValue()>0;
  66     Hashtable<TempDescriptor, Integer> currtable=getNodePreTempInfo(currlb,fc);
  67     MethodDescriptor md=fc.getMethod();
  68
  69     boolean isnative=md.getModifiers().isNative();
  70
  71     LocalityBinding lb=new LocalityBinding(md, isatomic);
  72
  73     for(int i=0; i<fc.numArgs(); i++) {
  74       TempDescriptor arg=fc.getArg(i);
  75       lb.setGlobal(i,currtable.get(arg));
  76     }
  77
  78     if (state.DSM&&fc.getThis()!=null) {
  79       Integer thistype=currtable.get(fc.getThis());
  80       if (thistype==null)
  81         thistype=EITHER;
  82       lb.setGlobalThis(thistype);
  83     } else if (state.SINGLETM&&fc.getThis()!=null) {
  84       Integer thistype=currtable.get(fc.getThis());
  85       if (thistype==null)
  86         thistype=STMEITHER;
  87       lb.setGlobalThis(thistype);
  88     }
  89     // else
  90     // lb.setGlobalThis(EITHER);//default value
  91     if (discovered.containsKey(lb))
  92       lb=discovered.get(lb);
  93     else throw new Error();
  94     return lb;
  95   }
  96
  97
  98   /** This method returns a set of LocalityBindings for the parameter class. */
  99   public Set<LocalityBinding> getClassBindings(ClassDescriptor cd) {
 100     return classtolb.get(cd);
 101   }
 102
 103   /** This method returns a set of LocalityBindings for the parameter method. */
 104
 105   public Set<LocalityBinding> getMethodBindings(MethodDescriptor md) {
 106     return methodtolb.get(md);
 107   }
 108
 109   public Set<MethodDescriptor> getMethods() {
 110     return methodtolb.keySet();
 111   }
 112
 113   /** This method returns a set of LocalityBindings.  A
 114    * LocalityBinding specifies a context a method can be invoked in.
 115    * It specifies whether the method is in a transaction and whether
 116    * its parameter objects are locals or globals.  */
 117
 118   public Set<LocalityBinding> getLocalityBindings() {
 119     return discovered.keySet();
 120   }
 121
 122   /** This method returns a hashtable for a given LocalityBinding
 123    * that tells the current local/global status of temps at the each
 124    * node in the flat representation. */
 125
 126   public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
 127     return temptab.get(lb);
 128   }
 129
 130   /** This method returns a hashtable for a given LocalityBinding
 131    * that tells the current local/global status of temps at the
 132    * beginning of each node in the flat representation. */
 133
 134   public Hashtable<TempDescriptor, Integer> getNodePreTempInfo(LocalityBinding lb, FlatNode fn) {
 135     Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 136     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable=getNodeTempInfo(lb);
 137
 138     for(int i=0; i<fn.numPrev(); i++) {
 139       FlatNode prevnode=fn.getPrev(i);
 140       Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 141       for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
 142         TempDescriptor temp=tempit.next();
 143         Integer tmpint=prevtable.get(temp);
 144         Integer oldint=currtable.containsKey(temp)?currtable.get(temp):(state.DSM?EITHER:STMEITHER);
 145         Integer newint=state.DSM?merge(tmpint, oldint):mergestm(tmpint, oldint);
 146         currtable.put(temp, newint);
 147       }
 148     }
 149     return currtable;
 150   }
 151
 152   /** This method returns an hashtable for a given LocalitBinding
 153    * that tells whether a node in the flat represenation is in a
 154    * transaction or not.  Integer values greater than 0 indicate
 155    * that the node is in a transaction and give the nesting depth.
 156    * The outermost AtomicEnterNode will have a value of 1 and the
 157    * outermost AtomicExitNode will have a value of 0. */
 158
 159   public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
 160     return atomictab.get(lb);
 161   }
 162
 163   /** This methods returns a hashtable for a given LocalityBinding
 164    * that tells which temps needs to be saved for each
 165    * AtomicEnterNode.  */
 166
 167   public Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> getTemps(LocalityBinding lb) {
 168     return tempstosave.get(lb);
 169   }
 170
 171   public Set<TempDescriptor> getTempSet(LocalityBinding lb) {
 172     HashSet<TempDescriptor> set=new HashSet<TempDescriptor>();
 173     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> table=getTemps(lb);
 174     if (table!=null)
 175       for(Iterator<FlatAtomicEnterNode> faenit=table.keySet().iterator(); faenit.hasNext(); ) {
 176         FlatAtomicEnterNode faen=faenit.next();
 177         set.addAll(table.get(faen));
 178       }
 179     return set;
 180   }
 181
 182   private void doAnalysis() {
 183     if (state.SINGLETM)
 184       computeLocalityBindingsSTM();
 185     else
 186       computeLocalityBindings();
 187     computeTempstoSave();
 188     cleanSets();
 189   }
 190
 191   private void cleanSets() {
 192     HashSet<LocalityBinding> lbset=new HashSet<LocalityBinding>();
 193     Stack<LocalityBinding> lbstack=new Stack<LocalityBinding>();
 194     lbstack.add(lbmain);
 195     lbstack.add(lbrun);
 196
 197     lbset.add(lbmain);
 198     lbset.add(lbrun);
 199
 200     if(state.DSMTASK) {       // when Task.java is used
 201       lbstack.add(lbexecute);
 202       lbset.add(lbexecute);
 203     }
 204     while(!lbstack.isEmpty()) {
 205       LocalityBinding lb=lbstack.pop();
 206       if (calldep.containsKey(lb)) {
 207         Set<LocalityBinding> set=new HashSet<LocalityBinding>();
 208         set.addAll(calldep.get(lb));
 209         set.removeAll(lbset);
 210         lbstack.addAll(set);
 211         lbset.addAll(set);
 212       }
 213     }
 214     for(Iterator<LocalityBinding> lbit=discovered.keySet().iterator(); lbit.hasNext(); ) {
 215       LocalityBinding lb=lbit.next();
 216       if (!lbset.contains(lb)) {
 217         lbit.remove();
 218         classtolb.get(lb.getMethod().getClassDesc()).remove(lb);
 219         methodtolb.get(lb.getMethod()).remove(lb);
 220       }
 221     }
 222   }
 223
 224   public MethodDescriptor getStart() {
 225     ClassDescriptor cd=typeutil.getClass(TypeUtil.ThreadClass);
 226     for(Iterator methodit=cd.getMethodTable().getSet("staticStart").iterator(); methodit
 227         .hasNext(); ) {
 228       MethodDescriptor md=(MethodDescriptor) methodit.next();
 229       if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
 230         continue;
 231       return md;
 232     }
 233     throw new Error("Can't find Thread.run");
 234   }
 235
 236
 237   private void computeLocalityBindingsSTM() {
 238     lbmain=new LocalityBinding(typeutil.getMain(), false);
 239     lbmain.setGlobalReturn(STMEITHER);
 240     lbmain.setGlobal(0, NORMAL);
 241     lbtovisit.add(lbmain);
 242     discovered.put(lbmain, lbmain);
 243     if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
 244       classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 245     classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
 246
 247     if (!methodtolb.containsKey(lbmain.getMethod()))
 248       methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
 249     methodtolb.get(lbmain.getMethod()).add(lbmain);
 250
 251     //Do this to force a virtual table number for the run method
 252     lbrun=new LocalityBinding(getStart(), false);
 253     lbrun.setGlobalReturn(STMEITHER);
 254     lbrun.setGlobal(0,NORMAL);
 255     lbtovisit.add(lbrun);
 256     discovered.put(lbrun, lbrun);
 257     if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
 258       classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 259     classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
 260
 261     if (!methodtolb.containsKey(lbrun.getMethod()))
 262       methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
 263     methodtolb.get(lbrun.getMethod()).add(lbrun);
 264
 265     while(!lbtovisit.isEmpty()) {
 266       LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
 267       lbtovisit.remove(lb);
 268
 269       System.out.println("Analyzing "+lb);
 270
 271       Integer returnglobal=lb.getGlobalReturn();
 272       MethodDescriptor md=lb.getMethod();
 273       Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
 274       Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
 275       calldep.remove(lb);
 276       try {
 277         computeCallsFlagsSTM(md, lb, temptable, atomictable);
 278       } catch (Error e) {
 279         System.out.println("Error in "+md+" context "+lb);
 280         e.printStackTrace();
 281         System.exit(-1);
 282       }
 283       temptab.put(lb, temptable);
 284       atomictab.put(lb, atomictable);
 285
 286       if (md.getReturnType()!=null&&md.getReturnType().isPtr()&&!returnglobal.equals(lb.getGlobalReturn())) {
 287         //return type is more precise now
 288         //rerun everything that call us
 289         lbtovisit.addAll(dependence.get(lb));
 290       }
 291     }
 292   }
 293
 294   private static Integer mergestm(Integer a, Integer b) {
 295     if (a==null||a.equals(STMEITHER))
 296       return b;
 297     if (b==null||b.equals(STMEITHER))
 298       return a;
 299     if (a.equals(b))
 300       return a;
 301     return STMCONFLICT;
 302   }
 303
 304   public void computeCallsFlagsSTM(MethodDescriptor md, LocalityBinding lb,  Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
 305     FlatMethod fm=state.getMethodFlat(md);
 306     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 307     tovisit.add(fm.getNext(0));
 308
 309     {
 310       // Build table for initial node
 311       Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
 312       temptable.put(fm, table);
 313       atomictable.put(fm, lb.isAtomic()?1:0);
 314       int offset=md.isStatic()?0:1;
 315       if (!md.isStatic()) {
 316         table.put(fm.getParameter(0), lb.getGlobalThis());
 317       }
 318       for(int i=offset; i<fm.numParameters(); i++) {
 319         TempDescriptor temp=fm.getParameter(i);
 320         Integer b=lb.isGlobal(i-offset);
 321         if (b!=null)
 322           table.put(temp,b);
 323       }
 324     }
 325
 326     Hashtable<FlatNode, Set<TempDescriptor>> livemap=Liveness.computeLiveTemps(fm);
 327
 328     while(!tovisit.isEmpty()) {
 329       FlatNode fn=tovisit.iterator().next();
 330       tovisit.remove(fn);
 331       Set<TempDescriptor> liveset=livemap.get(fn);
 332       Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 333       int atomicstate=0;
 334       for(int i=0; i<fn.numPrev(); i++) {
 335         FlatNode prevnode=fn.getPrev(i);
 336         if (atomictable.containsKey(prevnode)) {
 337           atomicstate=atomictable.get(prevnode).intValue();
 338         }
 339         if (!temptable.containsKey(prevnode))
 340           continue;
 341         Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 342         for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
 343           TempDescriptor temp=tempit.next();
 344           if (!liveset.contains(temp))
 345             continue;
 346           Integer tmpint=prevtable.get(temp);
 347           Integer oldint=currtable.containsKey(temp)?currtable.get(temp):STMEITHER;
 348           Integer newint=mergestm(tmpint, oldint);
 349           currtable.put(temp, newint);
 350         }
 351       }
 352       atomictable.put(fn, atomicstate);
 353
 354       // Process this node
 355       switch(fn.kind()) {
 356       case FKind.FlatAtomicEnterNode:
 357         processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
 358         if (!lb.isAtomic())
 359           lb.setHasAtomic();
 360         break;
 361
 362       case FKind.FlatAtomicExitNode:
 363         processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
 364         break;
 365
 366       case FKind.FlatCall:
 367         processCallNodeSTM(lb, (FlatCall)fn, isAtomic(atomictable, fn), currtable, temptable.get(fn));
 368         break;
 369
 370       case FKind.FlatNew:
 371         processNewSTM(lb, (FlatNew) fn, currtable);
 372         break;
 373
 374       case FKind.FlatFieldNode:
 375         processFieldNodeSTM(lb, (FlatFieldNode) fn, currtable);
 376         break;
 377
 378       case FKind.FlatSetFieldNode:
 379         processSetFieldNodeSTM(lb, (FlatSetFieldNode) fn, currtable);
 380         break;
 381
 382       case FKind.FlatSetElementNode:
 383         processSetElementNodeSTM(lb, (FlatSetElementNode) fn, currtable);
 384         break;
 385
 386       case FKind.FlatElementNode:
 387         processElementNodeSTM(lb, (FlatElementNode) fn, currtable);
 388         break;
 389
 390       case FKind.FlatOpNode:
 391         processOpNodeSTM(lb, (FlatOpNode)fn, currtable);
 392         break;
 393
 394       case FKind.FlatCastNode:
 395         processCastNodeSTM((FlatCastNode)fn, currtable);
 396         break;
 397
 398       case FKind.FlatReturnNode:
 399         processReturnNodeSTM(lb, (FlatReturnNode)fn, currtable);
 400         break;
 401
 402       case FKind.FlatLiteralNode:
 403         processLiteralNodeSTM((FlatLiteralNode)fn, currtable);
 404         break;
 405
 406       case FKind.FlatMethod:
 407       case FKind.FlatOffsetNode:
 408       case FKind.FlatInstanceOfNode:
 409       case FKind.FlatCondBranch:
 410       case FKind.FlatBackEdge:
 411       case FKind.FlatNop:
 412       case FKind.FlatPrefetchNode:
 413       case FKind.FlatExit:
 414         //No action needed for these
 415         break;
 416
 417       case FKind.FlatFlagActionNode:
 418       case FKind.FlatCheckNode:
 419       case FKind.FlatTagDeclaration:
 420         throw new Error("Incompatible with tasks!");
 421
 422       default:
 423         throw new Error("In finding fn.kind()= " + fn.kind());
 424       }
 425
 426
 427
 428       Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 429       if (oldtable==null||!oldtable.equals(currtable)) {
 430         // Update table for this node
 431         temptable.put(fn, currtable);
 432         for(int i=0; i<fn.numNext(); i++) {
 433           tovisit.add(fn.getNext(i));
 434         }
 435       }
 436     }
 437   }
 438
 439   void processNewSTM(LocalityBinding lb, FlatNew fn, Hashtable<TempDescriptor, Integer> currtable) {
 440     if (fn.isScratch())
 441       currtable.put(fn.getDst(), SCRATCH);
 442     else
 443       currtable.put(fn.getDst(), NORMAL);
 444   }
 445
 446   void processCallNodeSTM(LocalityBinding currlb, FlatCall fc, boolean isatomic, Hashtable<TempDescriptor, Integer> currtable, Hashtable<TempDescriptor, Integer> oldtable) {
 447     MethodDescriptor nodemd=fc.getMethod();
 448     Set methodset=null;
 449     Set runmethodset=null;
 450
 451     if (nodemd.isStatic()||nodemd.getReturnType()==null) {
 452       methodset=new HashSet();
 453       methodset.add(nodemd);
 454     } else {
 455       methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
 456       // Build start -> run link
 457       if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
 458           nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
 459           nodemd.numParameters()==0) {
 460         assert(nodemd.getModifiers().isNative());
 461
 462         MethodDescriptor runmd=null;
 463         for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("staticStart").iterator(); methodit.hasNext(); ) {
 464           MethodDescriptor md=(MethodDescriptor) methodit.next();
 465           if (md.numParameters()!=1||!md.getModifiers().isStatic()||!md.getParamType(0).getSymbol().equals(TypeUtil.ThreadClass))
 466             continue;
 467           runmd=md;
 468           break;
 469         }
 470         if (runmd!=null) {
 471           runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
 472           methodset.addAll(runmethodset);
 473         } else throw new Error("Can't find run method");
 474       }
 475     }
 476
 477     Integer currreturnval=STMEITHER;     //Start off with the either value
 478     if (oldtable!=null&&fc.getReturnTemp()!=null&&
 479         oldtable.get(fc.getReturnTemp())!=null) {
 480       //ensure termination
 481       currreturnval=mergestm(currreturnval, oldtable.get(fc.getReturnTemp()));
 482     }
 483
 484     for(Iterator methodit=methodset.iterator(); methodit.hasNext(); ) {
 485       MethodDescriptor md=(MethodDescriptor) methodit.next();
 486
 487       boolean isnative=md.getModifiers().isNative();
 488       boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
 489       boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
 490       boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
 491
 492       LocalityBinding lb=new LocalityBinding(md, isatomic);
 493       if (isnative&&isatomic) {
 494         System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
 495       }
 496
 497       if (runmethodset==null||!runmethodset.contains(md)) {
 498         for(int i=0; i<fc.numArgs(); i++) {
 499           TempDescriptor arg=fc.getArg(i);
 500           if (currtable.containsKey(arg))
 501             lb.setGlobal(i,currtable.get(arg));
 502         }
 503         if (fc.getThis()!=null) {
 504           Integer thistype=currtable.get(fc.getThis());
 505           if (thistype==null)
 506             thistype=STMEITHER;
 507
 508           if(thistype.equals(STMCONFLICT))
 509             throw new Error("Using type that can be either normal or scratch in context:\n"+currlb.getExplanation());
 510           lb.setGlobalThis(thistype);
 511         }
 512       } else {
 513         Integer thistype=currtable.get(fc.getThis());
 514         if (!thistype.equals(NORMAL)&&!thistype.equals(STMEITHER)) {
 515           throw new Error("Called start on possible scratch object"+thistype);
 516         }
 517         lb.setGlobal(0,currtable.get(fc.getThis()));
 518       }
 519       //lb is built
 520       if (!discovered.containsKey(lb)) {
 521         if (isnative) {
 522           if (nodemd.getReturnType()!=null&&nodemd.getReturnType().isPtr())
 523             lb.setGlobalReturn(NORMAL);
 524         } else
 525           lb.setGlobalReturn(STMEITHER);
 526
 527         lb.setParent(currlb);
 528         lbtovisit.add(lb);
 529         System.out.println("New lb:"+lb);
 530         discovered.put(lb, lb);
 531         if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
 532           classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 533         classtolb.get(lb.getMethod().getClassDesc()).add(lb);
 534         if (!methodtolb.containsKey(lb.getMethod()))
 535           methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
 536         methodtolb.get(lb.getMethod()).add(lb);
 537       } else
 538         lb=discovered.get(lb);
 539       Integer returnval=lb.getGlobalReturn();
 540       currreturnval=mergestm(returnval, currreturnval);
 541       if (!dependence.containsKey(lb))
 542         dependence.put(lb, new HashSet<LocalityBinding>());
 543       dependence.get(lb).add(currlb);
 544
 545       if (!calldep.containsKey(currlb))
 546         calldep.put(currlb, new HashSet<LocalityBinding>());
 547       calldep.get(currlb).add(lb);
 548     }
 549     if (fc.getReturnTemp()!=null&&fc.getReturnTemp().getType().isPtr()) {
 550       currtable.put(fc.getReturnTemp(), currreturnval);
 551     }
 552   }
 553
 554   void processFieldNodeSTM(LocalityBinding lb, FlatFieldNode ffn, Hashtable<TempDescriptor, Integer> currtable) {
 555     Integer type=currtable.get(ffn.getSrc());
 556     TempDescriptor dst=ffn.getDst();
 557     if (!ffn.getDst().getType().isPtr())
 558       return;
 559
 560     if (type.equals(SCRATCH)) {
 561       currtable.put(dst,SCRATCH);
 562     } else if (type.equals(NORMAL)) {
 563       currtable.put(dst, NORMAL);
 564     } else if (type.equals(STMEITHER)) {
 565       currtable.put(dst, STMEITHER);
 566     } else if (type.equals(STMCONFLICT)) {
 567       throw new Error("Access to object that could be either normal or scratch in context:\n"+ffn+"  "+lb.getExplanation());
 568     }
 569   }
 570
 571   //need to handle primitives
 572   void processSetFieldNodeSTM(LocalityBinding lb, FlatSetFieldNode fsfn, Hashtable<TempDescriptor, Integer> currtable) {
 573     Integer srctype=currtable.get(fsfn.getSrc());
 574     Integer dsttype=currtable.get(fsfn.getDst());
 575     if (!fsfn.getSrc().getType().isPtr())
 576       return;
 577
 578     if (dsttype==null)
 579       System.out.println(fsfn);
 580     if (dsttype.equals(SCRATCH)) {
 581       if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
 582         throw new Error("Writing possible normal reference to scratch object in context: \n"+lb.getExplanation());
 583     } else if (dsttype.equals(NORMAL)) {
 584       //okay to store primitives in global object
 585       if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
 586         throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
 587     } else if (dsttype.equals(STMEITHER)) {
 588       if (srctype.equals(STMCONFLICT))
 589         throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
 590     } else if (dsttype.equals(STMCONFLICT)) {
 591       throw new Error("Access to object that could be either scratch or normal in context:\n"+lb.getExplanation());
 592     }
 593   }
 594
 595   void processSetElementNodeSTM(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable) {
 596     Integer srctype=currtable.get(fsen.getSrc());
 597     Integer dsttype=currtable.get(fsen.getDst());
 598     if (!fsen.getSrc().getType().isPtr())
 599       return;
 600
 601     if (dsttype.equals(SCRATCH)) {
 602       if (!(srctype.equals(SCRATCH)||srctype.equals(STMEITHER)))
 603         throw new Error("Writing possible normal reference to scratch object in context:\n"+lb.getExplanation()+fsen);
 604     } else if (dsttype.equals(NORMAL)) {
 605       if (!(srctype.equals(NORMAL)||srctype.equals(STMEITHER)))
 606         throw new Error("Writing possible scratch reference to normal object in context:\n"+lb.getExplanation());
 607     } else if (dsttype.equals(STMEITHER)) {
 608       if (srctype.equals(STMCONFLICT))
 609         throw new Error("Using reference that could be scratch or normal in context:\n"+lb.getExplanation());
 610     } else if (dsttype.equals(STMCONFLICT)) {
 611       throw new Error("Access to object that could be either normal or scratch in context:\n"+lb.getExplanation());
 612     }
 613   }
 614
 615   void processOpNodeSTM(LocalityBinding lb, FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 616     /* Just propagate value */
 617     if (!fon.getLeft().getType().isPtr())
 618       return;
 619
 620     Integer srcvalue=currtable.get(fon.getLeft());
 621
 622     if (srcvalue==null) {
 623       System.out.println(fon);
 624       MethodDescriptor md=lb.getMethod();
 625       FlatMethod fm=state.getMethodFlat(md);
 626       System.out.println(fm.printMethod());
 627       throw new Error(fon.getLeft()+" is undefined!");
 628     }
 629     currtable.put(fon.getDest(), srcvalue);
 630   }
 631
 632   void processCastNodeSTM(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
 633     if (currtable.containsKey(fcn.getSrc()))
 634       currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
 635   }
 636
 637   void processReturnNodeSTM(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
 638     if(frn.getReturnTemp()!=null&&frn.getReturnTemp().getType().isPtr()) {
 639       Integer returntype=currtable.get(frn.getReturnTemp());
 640       lb.setGlobalReturn(mergestm(returntype, lb.getGlobalReturn()));
 641     }
 642   }
 643
 644   void processLiteralNodeSTM(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
 645     //null is either
 646     if (fln.getType().isNull())
 647       currtable.put(fln.getDst(), STMEITHER);
 648     else if (fln.getType().isPtr())
 649       currtable.put(fln.getDst(), NORMAL);
 650   }
 651
 652   void processElementNodeSTM(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable) {
 653     Integer type=currtable.get(fen.getSrc());
 654     TempDescriptor dst=fen.getDst();
 655     if (!fen.getDst().getType().isPtr())
 656       return;
 657
 658     if (type==null) {
 659       System.out.println(fen +" in "+lb+" may access undefined variable");
 660       MethodDescriptor md=lb.getMethod();
 661       FlatMethod fm=state.getMethodFlat(md);
 662       System.out.println(fm.printMethod());
 663       System.exit(-1);
 664     } else if (type.equals(SCRATCH)) {
 665       currtable.put(dst,SCRATCH);
 666     } else if (type.equals(NORMAL)) {
 667       currtable.put(dst, NORMAL);
 668     } else if (type.equals(STMEITHER)) {
 669       currtable.put(dst, STMEITHER);
 670     } else if (type.equals(STMCONFLICT)) {
 671       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 672     }
 673   }
 674
 675   private void computeLocalityBindings() {
 676     lbmain=new LocalityBinding(typeutil.getMain(), false);
 677     lbmain.setGlobalReturn(EITHER);
 678     lbmain.setGlobal(0, LOCAL);
 679     lbtovisit.add(lbmain);
 680     discovered.put(lbmain, lbmain);
 681     if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
 682       classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 683     classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
 684
 685     if (!methodtolb.containsKey(lbmain.getMethod()))
 686       methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
 687     methodtolb.get(lbmain.getMethod()).add(lbmain);
 688
 689     //Do this to force a virtual table number for the run method
 690     lbrun=new LocalityBinding(typeutil.getRun(), false);
 691     lbrun.setGlobalReturn(EITHER);
 692     lbrun.setGlobalThis(GLOBAL);
 693     lbtovisit.add(lbrun);
 694     discovered.put(lbrun, lbrun);
 695     if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
 696       classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 697     classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
 698
 699     if (!methodtolb.containsKey(lbrun.getMethod()))
 700       methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
 701     methodtolb.get(lbrun.getMethod()).add(lbrun);
 702
 703     if(state.DSMTASK) {
 704       lbexecute = new LocalityBinding(typeutil.getExecute(), false);
 705       lbexecute.setGlobalReturn(EITHER);
 706       lbexecute.setGlobalThis(GLOBAL);
 707       lbtovisit.add(lbexecute);
 708       discovered.put(lbexecute, lbexecute);
 709       if (!classtolb.containsKey(lbexecute.getMethod().getClassDesc()))
 710         classtolb.put(lbexecute.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 711       classtolb.get(lbexecute.getMethod().getClassDesc()).add(lbexecute);
 712
 713       if (!methodtolb.containsKey(lbexecute.getMethod()))
 714         methodtolb.put(lbexecute.getMethod(), new HashSet<LocalityBinding>());
 715       methodtolb.get(lbexecute.getMethod()).add(lbexecute);
 716     }
 717
 718     while(!lbtovisit.isEmpty()) {
 719       LocalityBinding lb=(LocalityBinding) lbtovisit.iterator().next();
 720       lbtovisit.remove(lb);
 721
 722       System.out.println("Analyzing "+lb);
 723       Integer returnglobal=lb.getGlobalReturn();
 724       MethodDescriptor md=lb.getMethod();
 725       Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
 726       Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
 727       calldep.remove(lb);
 728       try {
 729         computeCallsFlags(md, lb, temptable, atomictable);
 730       } catch (Error e) {
 731         System.out.println("Error in "+md+" context "+lb);
 732         e.printStackTrace();
 733         System.exit(-1);
 734       }
 735       temptab.put(lb, temptable);
 736       atomictab.put(lb, atomictable);
 737
 738       if (md.getReturnType()!=null&&!returnglobal.equals(lb.getGlobalReturn())) {
 739         //return type is more precise now
 740         //rerun everything that call us
 741         lbtovisit.addAll(dependence.get(lb));
 742       }
 743     }
 744   }
 745
 746
 747
 748
 749   public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
 750     FlatMethod fm=state.getMethodFlat(md);
 751     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 752     tovisit.add(fm.getNext(0));
 753     {
 754       // Build table for initial node
 755       Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
 756       temptable.put(fm, table);
 757       atomictable.put(fm, lb.isAtomic()?1:0);
 758       int offset=md.isStatic()?0:1;
 759       if (!md.isStatic()) {
 760         table.put(fm.getParameter(0), lb.getGlobalThis());
 761       }
 762       for(int i=offset; i<fm.numParameters(); i++) {
 763         TempDescriptor temp=fm.getParameter(i);
 764         Integer b=lb.isGlobal(i-offset);
 765         table.put(temp,b);
 766       }
 767     }
 768
 769     while(!tovisit.isEmpty()) {
 770       FlatNode fn=tovisit.iterator().next();
 771       tovisit.remove(fn);
 772       Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 773       int atomicstate=0;
 774       for(int i=0; i<fn.numPrev(); i++) {
 775         FlatNode prevnode=fn.getPrev(i);
 776         if (atomictable.containsKey(prevnode)) {
 777           atomicstate=atomictable.get(prevnode).intValue();
 778         }
 779         if (!temptable.containsKey(prevnode))
 780           continue;
 781         Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 782         for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext(); ) {
 783           TempDescriptor temp=tempit.next();
 784           Integer tmpint=prevtable.get(temp);
 785           Integer oldint=currtable.containsKey(temp)?currtable.get(temp):EITHER;
 786           Integer newint=merge(tmpint, oldint);
 787           currtable.put(temp, newint);
 788         }
 789       }
 790       atomictable.put(fn, atomicstate);
 791
 792       // Process this node
 793       switch(fn.kind()) {
 794       case FKind.FlatAtomicEnterNode:
 795         processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
 796         if (!lb.isAtomic())
 797           lb.setHasAtomic();
 798         break;
 799
 800       case FKind.FlatAtomicExitNode:
 801         processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
 802         break;
 803
 804       case FKind.FlatCall:
 805         processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn), temptable.get(fn));
 806         break;
 807
 808       case FKind.FlatFieldNode:
 809         processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
 810         break;
 811
 812       case FKind.FlatSetFieldNode:
 813         processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
 814         break;
 815
 816       case FKind.FlatNew:
 817         processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
 818         break;
 819
 820       case FKind.FlatOpNode:
 821         processOpNode((FlatOpNode)fn, currtable);
 822         break;
 823
 824       case FKind.FlatCastNode:
 825         processCastNode((FlatCastNode)fn, currtable);
 826         break;
 827
 828       case FKind.FlatLiteralNode:
 829         processLiteralNode((FlatLiteralNode)fn, currtable);
 830         break;
 831
 832       case FKind.FlatReturnNode:
 833         processReturnNode(lb, (FlatReturnNode)fn, currtable);
 834         break;
 835
 836       case FKind.FlatSetElementNode:
 837         processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
 838         break;
 839
 840       case FKind.FlatElementNode:
 841         processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
 842         break;
 843
 844       case FKind.FlatInstanceOfNode:
 845       case FKind.FlatCondBranch:
 846       case FKind.FlatBackEdge:
 847       case FKind.FlatNop:
 848       case FKind.FlatExit:
 849       case FKind.FlatPrefetchNode:
 850         //No action needed for these
 851         break;
 852
 853       case FKind.FlatFlagActionNode:
 854       case FKind.FlatCheckNode:
 855       case FKind.FlatTagDeclaration:
 856         throw new Error("Incompatible with tasks!");
 857
 858       case FKind.FlatMethod:
 859         break;
 860
 861       case FKind.FlatOffsetNode:
 862         processOffsetNode((FlatOffsetNode)fn, currtable);
 863         break;
 864
 865       default:
 866         throw new Error("In finding fn.kind()= " + fn.kind());
 867       }
 868       Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 869       if (oldtable==null||!oldtable.equals(currtable)) {
 870         // Update table for this node
 871         temptable.put(fn, currtable);
 872         for(int i=0; i<fn.numNext(); i++) {
 873           tovisit.add(fn.getNext(i));
 874         }
 875       }
 876     }
 877   }
 878
 879   private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
 880     return atomictable.get(fn).intValue()>0;
 881   }
 882
 883   private static Integer merge(Integer a, Integer b) {
 884     if (a==null||a.equals(EITHER))
 885       return b;
 886     if (b==null||b.equals(EITHER))
 887       return a;
 888     if (a.equals(b))
 889       return a;
 890     return CONFLICT;
 891   }
 892
 893   void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic, Hashtable<TempDescriptor,Integer> oldtable) {
 894     MethodDescriptor nodemd=fc.getMethod();
 895     Set methodset=null;
 896     Set runmethodset=null;
 897     Set executemethodset=null;
 898
 899     if (nodemd.isStatic()||nodemd.getReturnType()==null) {
 900       methodset=new HashSet();
 901       methodset.add(nodemd);
 902     } else {
 903       methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
 904       // Build start -> run link
 905       if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
 906           nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
 907           nodemd.numParameters()==1&&nodemd.getParamType(0).isInt()) {
 908         assert(nodemd.getModifiers().isNative());
 909
 910         MethodDescriptor runmd=null;
 911
 912         for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext(); ) {
 913           MethodDescriptor md=(MethodDescriptor) methodit.next();
 914
 915           if (md.numParameters()!=0||md.getModifiers().isStatic())
 916             continue;
 917           runmd=md;
 918           break;
 919         }
 920         if (runmd!=null) {
 921           runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
 922           methodset.addAll(runmethodset);
 923         } else throw new Error("Can't find run method");
 924       }
 925
 926       if(state.DSMTASK) {
 927         if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.TaskClass) &&
 928             nodemd.getSymbol().equals("execution") && !nodemd.getModifiers().isStatic() &&
 929             nodemd.numParameters() == 0) {
 930
 931           assert(nodemd.getModifiers().isNative());
 932           MethodDescriptor exemd = null;
 933
 934           for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("execute").iterator(); methodit.hasNext(); ) {
 935             MethodDescriptor md = (MethodDescriptor) methodit.next();
 936
 937             if (md.numParameters() != 0 || md.getModifiers().isStatic())
 938               continue;
 939             exemd = md;
 940             break;
 941           }
 942
 943           if (exemd != null) {
 944             executemethodset = callgraph.getMethods(exemd, fc.getThis().getType());
 945             methodset.addAll(executemethodset);
 946           } else throw new Error("Can't find execute method");
 947         }
 948       }
 949     }
 950
 951     Integer currreturnval=EITHER;     //Start off with the either value
 952     if (oldtable!=null&&fc.getReturnTemp()!=null&&
 953         oldtable.get(fc.getReturnTemp())!=null) {
 954       //ensure termination
 955       currreturnval=merge(currreturnval, oldtable.get(fc.getReturnTemp()));
 956     }
 957
 958     for(Iterator methodit=methodset.iterator(); methodit.hasNext(); ) {
 959       MethodDescriptor md=(MethodDescriptor) methodit.next();
 960
 961       boolean isnative=md.getModifiers().isNative();
 962       boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
 963       boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
 964       boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
 965
 966       LocalityBinding lb=new LocalityBinding(md, isatomic);
 967       if (isnative&&isatomic) {
 968         System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
 969       }
 970
 971       if ((runmethodset==null||!runmethodset.contains(md)) &&( executemethodset == null || !executemethodset.contains(md))) {
 972         //Skip this part if it is a run method or execute method
 973         for(int i=0; i<fc.numArgs(); i++) {
 974           TempDescriptor arg=fc.getArg(i);
 975           if(isnative&&(currtable.get(arg).equals(GLOBAL)||
 976                         currtable.get(arg).equals(CONFLICT))&& !(nodemd.getSymbol().equals("rangePrefetch"))) {
 977             throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
 978           }
 979           lb.setGlobal(i,currtable.get(arg));
 980         }
 981       }
 982
 983       if (fc.getThis()!=null) {
 984         Integer thistype=currtable.get(fc.getThis());
 985         if (thistype==null)
 986           thistype=EITHER;
 987
 988         if(runmethodset!=null&&runmethodset.contains(md)&&thistype.equals(LOCAL) && executemethodset != null && executemethodset.contains(md))
 989           throw new Error("Starting thread on local object not allowed in context:\n"+currlb.getExplanation());
 990         if(isjoin&&thistype.equals(LOCAL))
 991           throw new Error("Joining thread on local object not allowed in context:\n"+currlb.getExplanation());
 992         if(thistype.equals(CONFLICT))
 993           throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
 994         if(runmethodset==null&&thistype.equals(GLOBAL)&&!isatomic && !isjoin && executemethodset == null) {
 995           throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
 996         }
 997         if (runmethodset==null&&isnative&&thistype.equals(GLOBAL) && !isjoin && executemethodset == null && !isObjectgetType && !isObjecthashCode)
 998           throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
 999         lb.setGlobalThis(thistype);
1000       }
1001       //lb is built
1002       if (!discovered.containsKey(lb)) {
1003         if (isnative)
1004           lb.setGlobalReturn(LOCAL);
1005         else
1006           lb.setGlobalReturn(EITHER);
1007         lb.setParent(currlb);
1008         lbtovisit.add(lb);
1009         discovered.put(lb, lb);
1010         if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
1011           classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
1012         classtolb.get(lb.getMethod().getClassDesc()).add(lb);
1013         if (!methodtolb.containsKey(lb.getMethod()))
1014           methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
1015         methodtolb.get(lb.getMethod()).add(lb);
1016       } else
1017         lb=discovered.get(lb);
1018       Integer returnval=lb.getGlobalReturn();
1019       currreturnval=merge(returnval, currreturnval);
1020       if (!dependence.containsKey(lb))
1021         dependence.put(lb, new HashSet<LocalityBinding>());
1022       dependence.get(lb).add(currlb);
1023
1024       if (!calldep.containsKey(currlb))
1025         calldep.put(currlb, new HashSet<LocalityBinding>());
1026       calldep.get(currlb).add(lb);
1027     }
1028     if (fc.getReturnTemp()!=null) {
1029       currtable.put(fc.getReturnTemp(), currreturnval);
1030     }
1031   }
1032
1033   void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1034     Integer type=currtable.get(ffn.getSrc());
1035     TempDescriptor dst=ffn.getDst();
1036     if (type.equals(LOCAL)) {
1037       if (ffn.getField().isGlobal())
1038         currtable.put(dst,GLOBAL);
1039       else
1040         currtable.put(dst,LOCAL);
1041     } else if (type.equals(GLOBAL)) {
1042       if (!transaction)
1043         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1044       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1045         currtable.put(dst, LOCAL);         // primitives are local
1046       else
1047         currtable.put(dst, GLOBAL);
1048     } else if (type.equals(EITHER)) {
1049       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
1050         currtable.put(dst, LOCAL);         // primitives are local
1051       else if (ffn.getField().isGlobal())
1052         currtable.put(dst, GLOBAL);
1053       else
1054         currtable.put(dst, EITHER);
1055     } else if (type.equals(CONFLICT)) {
1056       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1057     }
1058   }
1059
1060   //need to handle primitives
1061   void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1062     Integer srctype=currtable.get(fsfn.getSrc());
1063     Integer dsttype=currtable.get(fsfn.getDst());
1064
1065     if (dsttype.equals(LOCAL)) {
1066       if (fsfn.getField().isGlobal()) {
1067         if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1068           throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
1069       } else {
1070         if (!(srctype.equals(LOCAL)||srctype.equals(EITHER))) {
1071           throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
1072         }
1073       }
1074     } else if (dsttype.equals(GLOBAL)) {
1075       if (!transaction)
1076         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1077       //okay to store primitives in global object
1078       if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive() && !fsfn.getField().getType().isArray())
1079         return;
1080       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1081         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
1082     } else if (dsttype.equals(EITHER)) {
1083       if (srctype.equals(CONFLICT))
1084         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1085     } else if (dsttype.equals(CONFLICT)) {
1086       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1087     }
1088   }
1089
1090   void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
1091     if (fn.isGlobal()&&!transaction) {
1092       throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
1093     }
1094     if (fn.isGlobal())
1095       currtable.put(fn.getDst(), GLOBAL);
1096     else
1097       currtable.put(fn.getDst(), LOCAL);
1098   }
1099
1100   void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
1101     /* Just propagate value */
1102     Integer srcvalue=currtable.get(fon.getLeft());
1103
1104     if (srcvalue==null) {
1105       if (!fon.getLeft().getType().isPtr()) {
1106         srcvalue=LOCAL;
1107       } else
1108         throw new Error(fon.getLeft()+" is undefined!");
1109     }
1110     currtable.put(fon.getDest(), srcvalue);
1111   }
1112
1113   void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
1114     currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
1115   }
1116
1117   void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1118     //null is either
1119     if (fln.getValue()==null)
1120       currtable.put(fln.getDst(), EITHER);
1121     else
1122       currtable.put(fln.getDst(), LOCAL);
1123   }
1124
1125   void processOffsetNode(FlatOffsetNode fln, Hashtable<TempDescriptor, Integer> currtable) {
1126     currtable.put(fln.getDst(), LOCAL);
1127   }
1128
1129   void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
1130     if(frn.getReturnTemp()!=null) {
1131       Integer returntype=currtable.get(frn.getReturnTemp());
1132       lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
1133     }
1134   }
1135
1136   void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1137     Integer srctype=currtable.get(fsen.getSrc());
1138     Integer dsttype=currtable.get(fsen.getDst());
1139
1140     if (dsttype.equals(LOCAL)) {
1141       if (!(srctype.equals(LOCAL)||srctype.equals(EITHER))) {
1142         throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation()+fsen);
1143       }
1144     } else if (dsttype.equals(GLOBAL)) {
1145       if (srctype.equals(LOCAL) && fsen.getDst().getType().dereference().isPrimitive() && !fsen.getDst().getType().dereference().isArray())
1146         return;
1147       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
1148         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
1149       if (!isatomic)
1150         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1151     } else if (dsttype.equals(EITHER)) {
1152       if (srctype.equals(CONFLICT))
1153         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
1154     } else if (dsttype.equals(CONFLICT)) {
1155       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1156     }
1157   }
1158
1159   void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
1160     Integer type=currtable.get(fen.getSrc());
1161     TempDescriptor dst=fen.getDst();
1162     if (type.equals(LOCAL)) {
1163       currtable.put(dst,LOCAL);
1164     } else if (type.equals(GLOBAL)) {
1165       if (!isatomic)
1166         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
1167       if(fen.getSrc().getType().dereference().isPrimitive()&&
1168          !fen.getSrc().getType().dereference().isArray())
1169         currtable.put(dst, LOCAL);
1170       else
1171         currtable.put(dst, GLOBAL);
1172     } else if (type.equals(EITHER)) {
1173       if(fen.getSrc().getType().dereference().isPrimitive()&&
1174          !fen.getSrc().getType().dereference().isArray())
1175         currtable.put(dst, LOCAL);
1176       else
1177         currtable.put(dst, EITHER);
1178     } else if (type.equals(CONFLICT)) {
1179       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
1180     }
1181   }
1182
1183   void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
1184     int atomic=atomictable.get(fen).intValue();
1185     atomictable.put(fen, new Integer(atomic+1));
1186   }
1187
1188   void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
1189     int atomic=atomictable.get(fen).intValue();
1190     atomictable.put(fen, new Integer(atomic-1));
1191   }
1192
1193   private void computeTempstoSave() {
1194     for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator(); lbit.hasNext(); ) {
1195       LocalityBinding lb=lbit.next();
1196       computeTempstoSave(lb);
1197     }
1198   }
1199
1200   /* Need to checkpoint all temps that could be read from along any
1201    * path that are either:
1202      1) Written to by any assignment inside the transaction
1203      2) Read from a global temp.
1204
1205      Generate tempstosave map from
1206      localitybinding->flatatomicenternode->Set<TempDescriptors>
1207    */
1208
1209   private void computeTempstoSave(LocalityBinding lb) {
1210     if (lb.isAtomic())
1211       return;
1212     Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
1213     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
1214     MethodDescriptor md=lb.getMethod();
1215     FlatMethod fm=state.getMethodFlat(md);
1216     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=Liveness.computeLiveTemps(fm);
1217     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
1218     tempstosave.put(lb, nodetosavetemps);
1219     Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
1220     HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
1221     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
1222     toprocess.add(fm);
1223     discovered.add(fm);
1224     while(!toprocess.isEmpty()) {
1225       FlatNode fn=toprocess.iterator().next();
1226       toprocess.remove(fn);
1227       boolean isatomic=atomictab.get(fn).intValue()>0;
1228       if (isatomic&&
1229           atomictab.get(fn.getPrev(0)).intValue()==0) {
1230         assert(fn.kind()==FKind.FlatAtomicEnterNode);
1231         nodemap.put(fn, (FlatAtomicEnterNode)fn);
1232         nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
1233       } else if (isatomic) {
1234         FlatAtomicEnterNode atomicnode=nodemap.get(fn);
1235         Set<TempDescriptor> livetemps=nodetotemps.get(atomicnode);
1236         List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
1237         List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
1238
1239         for(Iterator<TempDescriptor> tempit=livetemps.iterator(); tempit.hasNext(); ) {
1240           TempDescriptor tmp=tempit.next();
1241           if (writes.contains(tmp)) {
1242             nodetosavetemps.get(atomicnode).add(tmp);
1243           } else if (state.DSM) {
1244             if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
1245               nodetosavetemps.get(atomicnode).add(tmp);
1246             }
1247           } else if (state.SINGLETM) {
1248             if (reads.contains(tmp)&&tmp.getType().isPtr()&&temptab.get(fn).get(tmp)==NORMAL) {
1249               nodetosavetemps.get(atomicnode).add(tmp);
1250             }
1251           }
1252         }
1253       }
1254       for(int i=0; i<fn.numNext(); i++) {
1255         FlatNode fnnext=fn.getNext(i);
1256         if (!discovered.contains(fnnext)) {
1257           discovered.add(fnnext);
1258           toprocess.add(fnnext);
1259           if(isatomic) {
1260             nodemap.put(fnnext, nodemap.get(fn));
1261           }
1262         }
1263       }
1264     }
1265   }
1266 }