Robust/src/Analysis/Locality/LocalityAnalysis.java

   1 package Analysis.Locality;
   2
   3 import java.util.*;
   4 import Analysis.CallGraph.CallGraph;
   5 import IR.SymbolTable;
   6 import IR.State;
   7 import IR.TypeUtil;
   8 import IR.MethodDescriptor;
   9 import IR.Flat.*;
  10 import IR.ClassDescriptor;
  11
  12 public class LocalityAnalysis {
  13   State state;
  14   Stack lbtovisit;
  15   Hashtable<LocalityBinding,LocalityBinding> discovered;
  16   Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
  17   Hashtable<LocalityBinding, Set<LocalityBinding>> calldep;
  18   Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
  19   Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
  20   Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
  21   Hashtable<ClassDescriptor, Set<LocalityBinding>> classtolb;
  22   Hashtable<MethodDescriptor, Set<LocalityBinding>> methodtolb;
  23   private LocalityBinding lbmain;
  24   private LocalityBinding lbrun;
  25
  26   CallGraph callgraph;
  27   TypeUtil typeutil;
  28   public static final Integer LOCAL=new Integer(0);
  29   public static final Integer GLOBAL=new Integer(1);
  30   public static final Integer EITHER=new Integer(2);
  31   public static final Integer CONFLICT=new Integer(3);
  32
  33   public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  34     this.typeutil=typeutil;
  35     this.state=state;
  36     this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
  37     this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
  38     this.calldep=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
  39     this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
  40     this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
  41     this.lbtovisit=new Stack();
  42     this.callgraph=callgraph;
  43     this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
  44     this.classtolb=new Hashtable<ClassDescriptor, Set<LocalityBinding>>();
  45     this.methodtolb=new Hashtable<MethodDescriptor, Set<LocalityBinding>>();
  46     doAnalysis();
  47   }
  48
  49   public LocalityBinding getMain() {
  50     return lbmain;
  51   }
  52
  53   /** This method returns the set of LocalityBindings that a given
  54    * flatcall could invoke */
  55
  56   public LocalityBinding getBinding(LocalityBinding currlb, FlatCall fc) {
  57     boolean isatomic=getAtomic(currlb).get(fc).intValue()>0;
  58     Hashtable<TempDescriptor, Integer> currtable=getNodePreTempInfo(currlb,fc);
  59     MethodDescriptor md=fc.getMethod();
  60
  61     boolean isnative=md.getModifiers().isNative();
  62
  63     LocalityBinding lb=new LocalityBinding(md, isatomic);
  64
  65     for(int i=0; i<fc.numArgs(); i++) {
  66       TempDescriptor arg=fc.getArg(i);
  67       lb.setGlobal(i,currtable.get(arg));
  68     }
  69     if (fc.getThis()!=null) {
  70       Integer thistype=currtable.get(fc.getThis());
  71       if (thistype==null)
  72         thistype=EITHER;
  73       lb.setGlobalThis(thistype);
  74     }    // else
  75          // lb.setGlobalThis(EITHER);//default value
  76     if (discovered.containsKey(lb))
  77       lb=discovered.get(lb);
  78     else throw new Error();
  79     return lb;
  80   }
  81
  82
  83   /** This method returns a set of LocalityBindings for the parameter class. */
  84   public Set<LocalityBinding> getClassBindings(ClassDescriptor cd) {
  85     return classtolb.get(cd);
  86   }
  87
  88   /** This method returns a set of LocalityBindings for the parameter method. */
  89
  90   public Set<LocalityBinding> getMethodBindings(MethodDescriptor md) {
  91     return methodtolb.get(md);
  92   }
  93
  94   public Set<MethodDescriptor> getMethods() {
  95     return methodtolb.keySet();
  96   }
  97
  98   /** This method returns a set of LocalityBindings.  A
  99    * LocalityBinding specifies a context a method can be invoked in.
 100    * It specifies whether the method is in a transaction and whether
 101    * its parameter objects are locals or globals.  */
 102
 103   public Set<LocalityBinding> getLocalityBindings() {
 104     return discovered.keySet();
 105   }
 106
 107   /** This method returns a hashtable for a given LocalityBinding
 108    * that tells the current local/global status of temps at the each
 109    * node in the flat representation. */
 110
 111   public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
 112     return temptab.get(lb);
 113   }
 114
 115   /** This method returns a hashtable for a given LocalityBinding
 116    * that tells the current local/global status of temps at the
 117    * beginning of each node in the flat representation. */
 118
 119   public Hashtable<TempDescriptor, Integer> getNodePreTempInfo(LocalityBinding lb, FlatNode fn) {
 120     Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 121     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable=getNodeTempInfo(lb);
 122
 123     for(int i=0; i<fn.numPrev(); i++) {
 124       FlatNode prevnode=fn.getPrev(i);
 125       Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 126       for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext();) {
 127         TempDescriptor temp=tempit.next();
 128         Integer tmpint=prevtable.get(temp);
 129         Integer oldint=currtable.containsKey(temp) ? currtable.get(temp) : EITHER;
 130         Integer newint=merge(tmpint, oldint);
 131         currtable.put(temp, newint);
 132       }
 133     }
 134     return currtable;
 135   }
 136
 137   /** This method returns an hashtable for a given LocalitBinding
 138    * that tells whether a node in the flat represenation is in a
 139    * transaction or not.  Integer values greater than 0 indicate
 140    * that the node is in a transaction and give the nesting depth.
 141    * The outermost AtomicEnterNode will have a value of 1 and the
 142    * outermost AtomicExitNode will have a value of 0. */
 143
 144   public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
 145     return atomictab.get(lb);
 146   }
 147
 148   /** This methods returns a hashtable for a given LocalityBinding
 149    * that tells which temps needs to be saved for each
 150    * AtomicEnterNode.  */
 151
 152   public Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> getTemps(LocalityBinding lb) {
 153     return tempstosave.get(lb);
 154   }
 155
 156   public Set<TempDescriptor> getTempSet(LocalityBinding lb) {
 157     HashSet<TempDescriptor> set=new HashSet<TempDescriptor>();
 158     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> table=getTemps(lb);
 159     if (table!=null)
 160       for(Iterator<FlatAtomicEnterNode> faenit=table.keySet().iterator(); faenit.hasNext();) {
 161         FlatAtomicEnterNode faen=faenit.next();
 162         set.addAll(table.get(faen));
 163       }
 164     return set;
 165   }
 166
 167   private void doAnalysis() {
 168     computeLocalityBindings();
 169     computeTempstoSave();
 170     cleanSets();
 171   }
 172
 173   private void cleanSets() {
 174     HashSet<LocalityBinding> lbset=new HashSet<LocalityBinding>();
 175     Stack<LocalityBinding> lbstack=new Stack<LocalityBinding>();
 176     lbstack.add(lbmain);
 177     lbstack.add(lbrun);
 178     lbset.add(lbmain);
 179     lbset.add(lbrun);
 180     while(!lbstack.isEmpty()) {
 181       LocalityBinding lb=lbstack.pop();
 182       if (calldep.containsKey(lb)) {
 183         Set<LocalityBinding> set=new HashSet<LocalityBinding>();
 184         set.addAll(calldep.get(lb));
 185         set.removeAll(lbset);
 186         lbstack.addAll(set);
 187         lbset.addAll(set);
 188       }
 189     }
 190     for(Iterator<LocalityBinding> lbit=discovered.keySet().iterator(); lbit.hasNext();) {
 191       LocalityBinding lb=lbit.next();
 192       if (!lbset.contains(lb)) {
 193         lbit.remove();
 194         classtolb.get(lb.getMethod().getClassDesc()).remove(lb);
 195         methodtolb.get(lb.getMethod()).remove(lb);
 196       }
 197     }
 198   }
 199
 200   private void computeLocalityBindings() {
 201     lbmain=new LocalityBinding(typeutil.getMain(), false);
 202     lbmain.setGlobalReturn(EITHER);
 203     lbmain.setGlobal(0, LOCAL);
 204     lbtovisit.add(lbmain);
 205     discovered.put(lbmain, lbmain);
 206     if (!classtolb.containsKey(lbmain.getMethod().getClassDesc()))
 207       classtolb.put(lbmain.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 208     classtolb.get(lbmain.getMethod().getClassDesc()).add(lbmain);
 209
 210     if (!methodtolb.containsKey(lbmain.getMethod()))
 211       methodtolb.put(lbmain.getMethod(), new HashSet<LocalityBinding>());
 212     methodtolb.get(lbmain.getMethod()).add(lbmain);
 213
 214     //Do this to force a virtual table number for the run method
 215     lbrun=new LocalityBinding(typeutil.getRun(), false);
 216     lbrun.setGlobalReturn(EITHER);
 217     lbrun.setGlobalThis(GLOBAL);
 218     lbtovisit.add(lbrun);
 219     discovered.put(lbrun, lbrun);
 220     if (!classtolb.containsKey(lbrun.getMethod().getClassDesc()))
 221       classtolb.put(lbrun.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 222     classtolb.get(lbrun.getMethod().getClassDesc()).add(lbrun);
 223
 224     if (!methodtolb.containsKey(lbrun.getMethod()))
 225       methodtolb.put(lbrun.getMethod(), new HashSet<LocalityBinding>());
 226     methodtolb.get(lbrun.getMethod()).add(lbrun);
 227
 228     while(!lbtovisit.empty()) {
 229       LocalityBinding lb=(LocalityBinding) lbtovisit.pop();
 230       Integer returnglobal=lb.getGlobalReturn();
 231       MethodDescriptor md=lb.getMethod();
 232       Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
 233       Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
 234       calldep.remove(lb);
 235       try {
 236         computeCallsFlags(md, lb, temptable, atomictable);
 237       } catch (Error e) {
 238         System.out.println("Error in "+md+" context "+lb);
 239         e.printStackTrace();
 240         System.exit(-1);
 241       }
 242       atomictab.put(lb, atomictable);
 243       temptab.put(lb, temptable);
 244
 245       if (md.getReturnType()!=null&&!returnglobal.equals(lb.getGlobalReturn())) {
 246         //return type is more precise now
 247         //rerun everything that call us
 248         lbtovisit.addAll(dependence.get(lb));
 249       }
 250     }
 251   }
 252
 253   public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
 254     FlatMethod fm=state.getMethodFlat(md);
 255     HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
 256     tovisit.add(fm.getNext(0));
 257     {
 258       // Build table for initial node
 259       Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
 260       temptable.put(fm, table);
 261       atomictable.put(fm, lb.isAtomic() ? 1 : 0);
 262       int offset=md.isStatic() ? 0 : 1;
 263       if (!md.isStatic()) {
 264         table.put(fm.getParameter(0), lb.getGlobalThis());
 265       }
 266       for(int i=offset; i<fm.numParameters(); i++) {
 267         TempDescriptor temp=fm.getParameter(i);
 268         Integer b=lb.isGlobal(i-offset);
 269         table.put(temp,b);
 270       }
 271     }
 272
 273     while(!tovisit.isEmpty()) {
 274       FlatNode fn=tovisit.iterator().next();
 275       tovisit.remove(fn);
 276       Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 277       int atomicstate=0;
 278       for(int i=0; i<fn.numPrev(); i++) {
 279         FlatNode prevnode=fn.getPrev(i);
 280         if (atomictable.containsKey(prevnode)) {
 281           atomicstate=atomictable.get(prevnode).intValue();
 282         }
 283         if (!temptable.containsKey(prevnode))
 284           continue;
 285         Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 286         for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator(); tempit.hasNext();) {
 287           TempDescriptor temp=tempit.next();
 288           Integer tmpint=prevtable.get(temp);
 289           Integer oldint=currtable.containsKey(temp) ? currtable.get(temp) : EITHER;
 290           Integer newint=merge(tmpint, oldint);
 291           currtable.put(temp, newint);
 292         }
 293       }
 294       atomictable.put(fn, atomicstate);
 295       // Process this node
 296       switch(fn.kind()) {
 297       case FKind.FlatAtomicEnterNode:
 298         processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
 299         if (!lb.isAtomic())
 300           lb.setHasAtomic();
 301         break;
 302
 303       case FKind.FlatAtomicExitNode:
 304         processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
 305         break;
 306
 307       case FKind.FlatCall:
 308         processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn));
 309         break;
 310
 311       case FKind.FlatFieldNode:
 312         processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
 313         break;
 314
 315       case FKind.FlatSetFieldNode:
 316         processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
 317         break;
 318
 319       case FKind.FlatNew:
 320         processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
 321         break;
 322
 323       case FKind.FlatOpNode:
 324         processOpNode((FlatOpNode)fn, currtable);
 325         break;
 326
 327       case FKind.FlatCastNode:
 328         processCastNode((FlatCastNode)fn, currtable);
 329         break;
 330
 331       case FKind.FlatLiteralNode:
 332         processLiteralNode((FlatLiteralNode)fn, currtable);
 333         break;
 334
 335       case FKind.FlatReturnNode:
 336         processReturnNode(lb, (FlatReturnNode)fn, currtable);
 337         break;
 338
 339       case FKind.FlatSetElementNode:
 340         processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
 341         break;
 342
 343       case FKind.FlatElementNode:
 344         processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
 345         break;
 346
 347       case FKind.FlatCondBranch:
 348       case FKind.FlatBackEdge:
 349       case FKind.FlatNop:
 350       case FKind.FlatPrefetchNode:
 351         //No action needed for these
 352         break;
 353
 354       case FKind.FlatFlagActionNode:
 355       case FKind.FlatCheckNode:
 356       case FKind.FlatTagDeclaration:
 357         throw new Error("Incompatible with tasks!");
 358
 359       case FKind.FlatMethod:
 360
 361       case FKind.FlatOffsetNode:
 362         processOffsetNode((FlatOffsetNode)fn, currtable);
 363         break;
 364
 365       default:
 366         throw new Error();
 367       }
 368       Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 369       if (oldtable==null||!oldtable.equals(currtable)) {
 370         // Update table for this node
 371         temptable.put(fn, currtable);
 372         for(int i=0; i<fn.numNext(); i++) {
 373           tovisit.add(fn.getNext(i));
 374         }
 375       }
 376     }
 377   }
 378
 379   private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
 380     return atomictable.get(fn).intValue()>0;
 381   }
 382
 383   private static Integer merge(Integer a, Integer b) {
 384     if (a==null||a.equals(EITHER))
 385       return b;
 386     if (b==null||b.equals(EITHER))
 387       return a;
 388     if (a.equals(b))
 389       return a;
 390     return CONFLICT;
 391   }
 392
 393   void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 394     MethodDescriptor nodemd=fc.getMethod();
 395     Set methodset=null;
 396     Set runmethodset=null;
 397
 398     if (nodemd.isStatic()||nodemd.getReturnType()==null) {
 399       methodset=new HashSet();
 400       methodset.add(nodemd);
 401     } else {
 402       methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
 403       // Build start -> run link
 404       if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
 405           nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
 406           nodemd.numParameters()==1&&nodemd.getParamType(0).isInt()) {
 407         assert(nodemd.getModifiers().isNative());
 408
 409         MethodDescriptor runmd=null;
 410         for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext();) {
 411           MethodDescriptor md=(MethodDescriptor) methodit.next();
 412           if (md.numParameters()!=0||md.getModifiers().isStatic())
 413             continue;
 414           runmd=md;
 415           break;
 416         }
 417         if (runmd!=null) {
 418           runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
 419           methodset.addAll(runmethodset);
 420         } else throw new Error("Can't find run method");
 421       }
 422     }
 423
 424     Integer currreturnval=EITHER;     //Start off with the either value
 425     for(Iterator methodit=methodset.iterator(); methodit.hasNext();) {
 426       MethodDescriptor md=(MethodDescriptor) methodit.next();
 427
 428       boolean isnative=md.getModifiers().isNative();
 429       boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
 430       boolean isObjectgetType = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("getType");
 431       boolean isObjecthashCode = md.getClassDesc().getSymbol().equals("Object") && md.getSymbol().equals("nativehashCode");
 432
 433       LocalityBinding lb=new LocalityBinding(md, isatomic);
 434       if (isnative&&isatomic) {
 435         System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
 436       }
 437       if (runmethodset==null||!runmethodset.contains(md)) {
 438         //Skip this part if it is a run method
 439         for(int i=0; i<fc.numArgs(); i++) {
 440           TempDescriptor arg=fc.getArg(i);
 441           if(isnative&&(currtable.get(arg).equals(GLOBAL)||
 442                         currtable.get(arg).equals(CONFLICT))&& !(nodemd.getSymbol().equals("rangePrefetch"))) {
 443             throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
 444           }
 445           lb.setGlobal(i,currtable.get(arg));
 446         }
 447       }
 448
 449       if (fc.getThis()!=null) {
 450         Integer thistype=currtable.get(fc.getThis());
 451         if (thistype==null)
 452           thistype=EITHER;
 453
 454         if(runmethodset!=null&&runmethodset.contains(md)&&thistype.equals(LOCAL))
 455           throw new Error("Starting thread on local object not allowed in context:\n"+currlb.getExplanation());
 456         if(isjoin&&thistype.equals(LOCAL))
 457           throw new Error("Joining thread on local object not allowed in context:\n"+currlb.getExplanation());
 458         if(thistype.equals(CONFLICT))
 459           throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
 460         if(runmethodset==null&&thistype.equals(GLOBAL)&&!isatomic && !isjoin)
 461           throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
 462         if (runmethodset==null&&isnative&&thistype.equals(GLOBAL) && !isjoin && !isObjectgetType && !isObjecthashCode)
 463           throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
 464         lb.setGlobalThis(thistype);
 465       }
 466       //lb is built
 467       if (!discovered.containsKey(lb)) {
 468         if (isnative)
 469           lb.setGlobalReturn(LOCAL);
 470         else
 471           lb.setGlobalReturn(EITHER);
 472         lb.setParent(currlb);
 473         lbtovisit.add(lb);
 474         discovered.put(lb, lb);
 475         if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
 476           classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 477         classtolb.get(lb.getMethod().getClassDesc()).add(lb);
 478         if (!methodtolb.containsKey(lb.getMethod()))
 479           methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
 480         methodtolb.get(lb.getMethod()).add(lb);
 481       } else
 482         lb=discovered.get(lb);
 483       Integer returnval=lb.getGlobalReturn();
 484       currreturnval=merge(returnval, currreturnval);
 485       if (!dependence.containsKey(lb))
 486         dependence.put(lb, new HashSet<LocalityBinding>());
 487       dependence.get(lb).add(currlb);
 488
 489       if (!calldep.containsKey(currlb))
 490         calldep.put(currlb, new HashSet<LocalityBinding>());
 491       calldep.get(currlb).add(lb);
 492     }
 493     if (fc.getReturnTemp()!=null) {
 494       currtable.put(fc.getReturnTemp(), currreturnval);
 495     }
 496   }
 497
 498   void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 499     Integer type=currtable.get(ffn.getSrc());
 500     TempDescriptor dst=ffn.getDst();
 501     if (type.equals(LOCAL)) {
 502       if (ffn.getField().isGlobal())
 503         currtable.put(dst,GLOBAL);
 504       else
 505         currtable.put(dst,LOCAL);
 506     } else if (type.equals(GLOBAL)) {
 507       if (!transaction)
 508         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 509       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
 510         currtable.put(dst, LOCAL);         // primitives are local
 511       else
 512         currtable.put(dst, GLOBAL);
 513     } else if (type.equals(EITHER)) {
 514       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
 515         currtable.put(dst, LOCAL);         // primitives are local
 516       else if (ffn.getField().isGlobal())
 517         currtable.put(dst, GLOBAL);
 518       else
 519         currtable.put(dst, EITHER);
 520     } else if (type.equals(CONFLICT)) {
 521       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 522     }
 523   }
 524
 525   //need to handle primitives
 526   void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 527     Integer srctype=currtable.get(fsfn.getSrc());
 528     Integer dsttype=currtable.get(fsfn.getDst());
 529
 530     if (dsttype.equals(LOCAL)) {
 531       if (fsfn.getField().isGlobal()) {
 532         if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 533           throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
 534       } else {
 535         if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 536           throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
 537       }
 538     } else if (dsttype.equals(GLOBAL)) {
 539       if (!transaction)
 540         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 541       //okay to store primitives in global object
 542       if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive() && !fsfn.getField().getType().isArray())
 543         return;
 544       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 545         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
 546     } else if (dsttype.equals(EITHER)) {
 547       if (srctype.equals(CONFLICT))
 548         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 549     } else if (dsttype.equals(CONFLICT)) {
 550       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 551     }
 552   }
 553
 554   void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 555     if (fn.isGlobal()&&!transaction) {
 556       throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
 557     }
 558     if (fn.isGlobal())
 559       currtable.put(fn.getDst(), GLOBAL);
 560     else
 561       currtable.put(fn.getDst(), LOCAL);
 562   }
 563
 564   void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 565     /* Just propagate value */
 566     Integer srcvalue=currtable.get(fon.getLeft());
 567
 568     if (srcvalue==null) {
 569       if (!fon.getLeft().getType().isPtr()) {
 570         srcvalue=LOCAL;
 571       } else
 572         throw new Error(fon.getLeft()+" is undefined!");
 573     }
 574     currtable.put(fon.getDest(), srcvalue);
 575   }
 576
 577   void processOffsetNode(FlatOffsetNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 578     /* Just propagate value */
 579     currtable.put(fon.getDst(), LOCAL);
 580   }
 581
 582   void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
 583     currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
 584   }
 585
 586   void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
 587     //null is either
 588     if (fln.getValue()==null)
 589       currtable.put(fln.getDst(), EITHER);
 590     else
 591       currtable.put(fln.getDst(), LOCAL);
 592   }
 593
 594   void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
 595     if(frn.getReturnTemp()!=null) {
 596       Integer returntype=currtable.get(frn.getReturnTemp());
 597       lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
 598     }
 599   }
 600
 601   void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 602     Integer srctype=currtable.get(fsen.getSrc());
 603     Integer dsttype=currtable.get(fsen.getDst());
 604
 605     if (dsttype.equals(LOCAL)) {
 606       if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 607         throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation()+fsen);
 608     } else if (dsttype.equals(GLOBAL)) {
 609       if (srctype.equals(LOCAL) && fsen.getDst().getType().dereference().isPrimitive() && !fsen.getDst().getType().dereference().isArray())
 610         return;
 611       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 612         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
 613       if (!isatomic)
 614         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 615     } else if (dsttype.equals(EITHER)) {
 616       if (srctype.equals(CONFLICT))
 617         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 618     } else if (dsttype.equals(CONFLICT)) {
 619       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 620     }
 621   }
 622
 623   void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 624     Integer type=currtable.get(fen.getSrc());
 625     TempDescriptor dst=fen.getDst();
 626     if (type.equals(LOCAL)) {
 627       currtable.put(dst,LOCAL);
 628     } else if (type.equals(GLOBAL)) {
 629       if (!isatomic)
 630         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 631       if(fen.getSrc().getType().dereference().isPrimitive()&&
 632          !fen.getSrc().getType().dereference().isArray())
 633         currtable.put(dst, LOCAL);
 634       else
 635         currtable.put(dst, GLOBAL);
 636     } else if (type.equals(EITHER)) {
 637       if(fen.getSrc().getType().dereference().isPrimitive()&&
 638          !fen.getSrc().getType().dereference().isArray())
 639         currtable.put(dst, LOCAL);
 640       else
 641         currtable.put(dst, EITHER);
 642     } else if (type.equals(CONFLICT)) {
 643       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 644     }
 645   }
 646
 647   void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
 648     int atomic=atomictable.get(fen).intValue();
 649     atomictable.put(fen, new Integer(atomic+1));
 650   }
 651
 652   void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
 653     int atomic=atomictable.get(fen).intValue();
 654     atomictable.put(fen, new Integer(atomic-1));
 655   }
 656
 657   private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
 658     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
 659
 660     Set<FlatNode> toprocess=fm.getNodeSet();
 661
 662     while(!toprocess.isEmpty()) {
 663       FlatNode fn=toprocess.iterator().next();
 664       toprocess.remove(fn);
 665
 666       List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 667       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
 668
 669       HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
 670       for(int i=0; i<fn.numNext(); i++) {
 671         FlatNode fnnext=fn.getNext(i);
 672         if (nodetotemps.containsKey(fnnext))
 673           tempset.addAll(nodetotemps.get(fnnext));
 674       }
 675       tempset.removeAll(writes);
 676       tempset.addAll(reads);
 677       if (!nodetotemps.containsKey(fn)||
 678           !nodetotemps.get(fn).equals(tempset)) {
 679         nodetotemps.put(fn, tempset);
 680         for(int i=0; i<fn.numPrev(); i++)
 681           toprocess.add(fn.getPrev(i));
 682       }
 683     }
 684     return nodetotemps;
 685   }
 686
 687   private void computeTempstoSave() {
 688     for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator(); lbit.hasNext();) {
 689       LocalityBinding lb=lbit.next();
 690       computeTempstoSave(lb);
 691     }
 692   }
 693
 694   /* Need to checkpoint all temps that could be read from along any
 695    * path that are either:
 696      1) Written to by any assignment inside the transaction
 697      2) Read from a global temp.
 698
 699      Generate tempstosave map from
 700      localitybinding->flatatomicenternode->Set<TempDescriptors>
 701    */
 702
 703   private void computeTempstoSave(LocalityBinding lb) {
 704     if (lb.isAtomic())
 705       return;
 706     Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
 707     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
 708     MethodDescriptor md=lb.getMethod();
 709     FlatMethod fm=state.getMethodFlat(md);
 710     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=computeLiveTemps(fm);
 711     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
 712     tempstosave.put(lb, nodetosavetemps);
 713     Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
 714     HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
 715     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 716     toprocess.add(fm);
 717     discovered.add(fm);
 718     while(!toprocess.isEmpty()) {
 719       FlatNode fn=toprocess.iterator().next();
 720       toprocess.remove(fn);
 721       boolean isatomic=atomictab.get(fn).intValue()>0;
 722       if (isatomic&&
 723           atomictab.get(fn.getPrev(0)).intValue()==0) {
 724         assert(fn.getPrev(0).kind()==FKind.FlatAtomicEnterNode);
 725         nodemap.put(fn, (FlatAtomicEnterNode)fn);
 726         nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
 727       } else if (isatomic) {
 728         FlatAtomicEnterNode atomicnode=nodemap.get(fn);
 729         Set<TempDescriptor> livetemps=nodetotemps.get(fn);
 730         List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 731         List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
 732
 733         for(Iterator<TempDescriptor> tempit=livetemps.iterator(); tempit.hasNext();) {
 734           TempDescriptor tmp=tempit.next();
 735           if (writes.contains(tmp)) {
 736             nodetosavetemps.get(atomicnode).add(tmp);
 737           } else if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
 738             nodetosavetemps.get(atomicnode).add(tmp);
 739           }
 740         }
 741       }
 742       for(int i=0; i<fn.numNext(); i++) {
 743         FlatNode fnnext=fn.getNext(i);
 744         if (!discovered.contains(fnnext)) {
 745           discovered.add(fnnext);
 746           toprocess.add(fnnext);
 747           if(isatomic) {
 748             nodemap.put(fnnext, nodemap.get(fn));
 749           }
 750         }
 751       }
 752     }
 753   }
 754 }