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       default:
 361         throw new Error();
 362       }
 363       Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 364       if (oldtable==null||!oldtable.equals(currtable)) {
 365         // Update table for this node
 366         temptable.put(fn, currtable);
 367         for(int i=0; i<fn.numNext(); i++) {
 368           tovisit.add(fn.getNext(i));
 369         }
 370       }
 371     }
 372   }
 373
 374   private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
 375     return atomictable.get(fn).intValue()>0;
 376   }
 377
 378   private static Integer merge(Integer a, Integer b) {
 379     if (a==null||a.equals(EITHER))
 380       return b;
 381     if (b==null||b.equals(EITHER))
 382       return a;
 383     if (a.equals(b))
 384       return a;
 385     return CONFLICT;
 386   }
 387
 388   void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 389     MethodDescriptor nodemd=fc.getMethod();
 390     Set methodset=null;
 391     Set runmethodset=null;
 392
 393     if (nodemd.isStatic()||nodemd.getReturnType()==null) {
 394       methodset=new HashSet();
 395       methodset.add(nodemd);
 396     } else {
 397       methodset=callgraph.getMethods(nodemd, fc.getThis().getType());
 398       // Build start -> run link
 399       if (nodemd.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&
 400           nodemd.getSymbol().equals("start")&&!nodemd.getModifiers().isStatic()&&
 401           nodemd.numParameters()==1&&nodemd.getParamType(0).isInt()) {
 402         assert(nodemd.getModifiers().isNative());
 403
 404         MethodDescriptor runmd=null;
 405         for(Iterator methodit=nodemd.getClassDesc().getMethodTable().getSet("run").iterator(); methodit.hasNext();) {
 406           MethodDescriptor md=(MethodDescriptor) methodit.next();
 407           if (md.numParameters()!=0||md.getModifiers().isStatic())
 408             continue;
 409           runmd=md;
 410           break;
 411         }
 412         if (runmd!=null) {
 413           runmethodset=callgraph.getMethods(runmd,fc.getThis().getType());
 414           methodset.addAll(runmethodset);
 415         } else throw new Error("Can't find run method");
 416       }
 417     }
 418
 419     Integer currreturnval=EITHER;     //Start off with the either value
 420     for(Iterator methodit=methodset.iterator(); methodit.hasNext();) {
 421       MethodDescriptor md=(MethodDescriptor) methodit.next();
 422
 423       boolean isnative=md.getModifiers().isNative();
 424       boolean isjoin = md.getClassDesc().getSymbol().equals(TypeUtil.ThreadClass)&&!nodemd.getModifiers().isStatic()&&nodemd.numParameters()==0&&md.getSymbol().equals("join");
 425
 426       LocalityBinding lb=new LocalityBinding(md, isatomic);
 427       if (isnative&&isatomic) {
 428         System.out.println("Don't call native methods in atomic blocks!"+currlb.getMethod());
 429       }
 430       if (runmethodset==null||!runmethodset.contains(md)) {
 431         //Skip this part if it is a run method
 432         for(int i=0; i<fc.numArgs(); i++) {
 433           TempDescriptor arg=fc.getArg(i);
 434           if(isnative&&(currtable.get(arg).equals(GLOBAL)||
 435                         currtable.get(arg).equals(CONFLICT)))
 436             throw new Error("Potential call to native method "+md+" with global parameter:\n"+currlb.getExplanation());
 437           lb.setGlobal(i,currtable.get(arg));
 438         }
 439       }
 440
 441       if (fc.getThis()!=null) {
 442         Integer thistype=currtable.get(fc.getThis());
 443         if (thistype==null)
 444           thistype=EITHER;
 445
 446         if(runmethodset!=null&&runmethodset.contains(md)&&thistype.equals(LOCAL))
 447           throw new Error("Starting thread on local object not allowed in context:\n"+currlb.getExplanation());
 448         if(isjoin&&thistype.equals(LOCAL))
 449           throw new Error("Joining thread on local object not allowed in context:\n"+currlb.getExplanation());
 450         if(thistype.equals(CONFLICT))
 451           throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
 452         if(runmethodset==null&&thistype.equals(GLOBAL)&&!isatomic && !isjoin)
 453           throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
 454         if (runmethodset==null&&isnative&&thistype.equals(GLOBAL) && !isjoin)
 455           throw new Error("Potential call to native method "+md+" on global objects:\n"+currlb.getExplanation());
 456         lb.setGlobalThis(thistype);
 457       }
 458       //lb is built
 459       if (!discovered.containsKey(lb)) {
 460         if (isnative)
 461           lb.setGlobalReturn(LOCAL);
 462         else
 463           lb.setGlobalReturn(EITHER);
 464         lb.setParent(currlb);
 465         lbtovisit.add(lb);
 466         discovered.put(lb, lb);
 467         if (!classtolb.containsKey(lb.getMethod().getClassDesc()))
 468           classtolb.put(lb.getMethod().getClassDesc(), new HashSet<LocalityBinding>());
 469         classtolb.get(lb.getMethod().getClassDesc()).add(lb);
 470         if (!methodtolb.containsKey(lb.getMethod()))
 471           methodtolb.put(lb.getMethod(), new HashSet<LocalityBinding>());
 472         methodtolb.get(lb.getMethod()).add(lb);
 473       } else
 474         lb=discovered.get(lb);
 475       Integer returnval=lb.getGlobalReturn();
 476       currreturnval=merge(returnval, currreturnval);
 477       if (!dependence.containsKey(lb))
 478         dependence.put(lb, new HashSet<LocalityBinding>());
 479       dependence.get(lb).add(currlb);
 480
 481       if (!calldep.containsKey(currlb))
 482         calldep.put(currlb, new HashSet<LocalityBinding>());
 483       calldep.get(currlb).add(lb);
 484     }
 485     if (fc.getReturnTemp()!=null) {
 486       currtable.put(fc.getReturnTemp(), currreturnval);
 487     }
 488   }
 489
 490   void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 491     Integer type=currtable.get(ffn.getSrc());
 492     TempDescriptor dst=ffn.getDst();
 493     if (type.equals(LOCAL)) {
 494       if (ffn.getField().isGlobal())
 495         currtable.put(dst,GLOBAL);
 496       else
 497         currtable.put(dst,LOCAL);
 498     } else if (type.equals(GLOBAL)) {
 499       if (!transaction)
 500         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 501       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
 502         currtable.put(dst, LOCAL);         // primitives are local
 503       else
 504         currtable.put(dst, GLOBAL);
 505     } else if (type.equals(EITHER)) {
 506       if (ffn.getField().getType().isPrimitive()&&!ffn.getField().getType().isArray())
 507         currtable.put(dst, LOCAL);         // primitives are local
 508       else if (ffn.getField().isGlobal())
 509         currtable.put(dst, GLOBAL);
 510       else
 511         currtable.put(dst, EITHER);
 512     } else if (type.equals(CONFLICT)) {
 513       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 514     }
 515   }
 516
 517   //need to handle primitives
 518   void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 519     Integer srctype=currtable.get(fsfn.getSrc());
 520     Integer dsttype=currtable.get(fsfn.getDst());
 521
 522     if (dsttype.equals(LOCAL)) {
 523       if (fsfn.getField().isGlobal()) {
 524         if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 525           throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
 526       } else {
 527         if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 528           throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
 529       }
 530     } else if (dsttype.equals(GLOBAL)) {
 531       if (!transaction)
 532         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 533       //okay to store primitives in global object
 534       if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive() && !fsfn.getField().getType().isArray())
 535         return;
 536       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 537         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation()+" for FlatFieldNode "+fsfn);
 538     } else if (dsttype.equals(EITHER)) {
 539       if (srctype.equals(CONFLICT))
 540         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 541     } else if (dsttype.equals(CONFLICT)) {
 542       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 543     }
 544   }
 545
 546   void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 547     if (fn.isGlobal()&&!transaction) {
 548       throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
 549     }
 550     if (fn.isGlobal())
 551       currtable.put(fn.getDst(), GLOBAL);
 552     else
 553       currtable.put(fn.getDst(), LOCAL);
 554   }
 555
 556   void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 557     /* Just propagate value */
 558     Integer srcvalue=currtable.get(fon.getLeft());
 559
 560     if (srcvalue==null) {
 561       if (!fon.getLeft().getType().isPtr()) {
 562         srcvalue=LOCAL;
 563       } else
 564         throw new Error(fon.getLeft()+" is undefined!");
 565     }
 566     currtable.put(fon.getDest(), srcvalue);
 567   }
 568
 569   void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
 570     currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
 571   }
 572
 573   void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
 574     //null is either
 575     if (fln.getValue()==null)
 576       currtable.put(fln.getDst(), EITHER);
 577     else
 578       currtable.put(fln.getDst(), LOCAL);
 579   }
 580
 581   void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
 582     if(frn.getReturnTemp()!=null) {
 583       Integer returntype=currtable.get(frn.getReturnTemp());
 584       lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
 585     }
 586   }
 587
 588   void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 589     Integer srctype=currtable.get(fsen.getSrc());
 590     Integer dsttype=currtable.get(fsen.getDst());
 591
 592     if (dsttype.equals(LOCAL)) {
 593       if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 594         throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation()+fsen);
 595     } else if (dsttype.equals(GLOBAL)) {
 596       if (srctype.equals(LOCAL) && fsen.getDst().getType().dereference().isPrimitive() && !fsen.getDst().getType().dereference().isArray())
 597         return;
 598       if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 599         throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
 600       if (!isatomic)
 601         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 602     } else if (dsttype.equals(EITHER)) {
 603       if (srctype.equals(CONFLICT))
 604         throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 605     } else if (dsttype.equals(CONFLICT)) {
 606       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 607     }
 608   }
 609
 610   void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 611     Integer type=currtable.get(fen.getSrc());
 612     TempDescriptor dst=fen.getDst();
 613     if (type.equals(LOCAL)) {
 614       currtable.put(dst,LOCAL);
 615     } else if (type.equals(GLOBAL)) {
 616       if (!isatomic)
 617         throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 618       if(fen.getSrc().getType().dereference().isPrimitive()&&
 619          !fen.getSrc().getType().dereference().isArray())
 620         currtable.put(dst, LOCAL);
 621       else
 622         currtable.put(dst, GLOBAL);
 623     } else if (type.equals(EITHER)) {
 624       if(fen.getSrc().getType().dereference().isPrimitive()&&
 625          !fen.getSrc().getType().dereference().isArray())
 626         currtable.put(dst, LOCAL);
 627       else
 628         currtable.put(dst, EITHER);
 629     } else if (type.equals(CONFLICT)) {
 630       throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 631     }
 632   }
 633
 634   void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
 635     int atomic=atomictable.get(fen).intValue();
 636     atomictable.put(fen, new Integer(atomic+1));
 637   }
 638
 639   void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
 640     int atomic=atomictable.get(fen).intValue();
 641     atomictable.put(fen, new Integer(atomic-1));
 642   }
 643
 644   private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
 645     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
 646
 647     Set<FlatNode> toprocess=fm.getNodeSet();
 648
 649     while(!toprocess.isEmpty()) {
 650       FlatNode fn=toprocess.iterator().next();
 651       toprocess.remove(fn);
 652
 653       List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 654       List<TempDescriptor> writes=Arrays.asList(fn.writesTemps());
 655
 656       HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
 657       for(int i=0; i<fn.numNext(); i++) {
 658         FlatNode fnnext=fn.getNext(i);
 659         if (nodetotemps.containsKey(fnnext))
 660           tempset.addAll(nodetotemps.get(fnnext));
 661       }
 662       tempset.removeAll(writes);
 663       tempset.addAll(reads);
 664       if (!nodetotemps.containsKey(fn)||
 665           !nodetotemps.get(fn).equals(tempset)) {
 666         nodetotemps.put(fn, tempset);
 667         for(int i=0; i<fn.numPrev(); i++)
 668           toprocess.add(fn.getPrev(i));
 669       }
 670     }
 671     return nodetotemps;
 672   }
 673
 674   private void computeTempstoSave() {
 675     for(Iterator<LocalityBinding> lbit=getLocalityBindings().iterator(); lbit.hasNext();) {
 676       LocalityBinding lb=lbit.next();
 677       computeTempstoSave(lb);
 678     }
 679   }
 680
 681   /* Need to checkpoint all temps that could be read from along any
 682    * path that are either:
 683      1) Written to by any assignment inside the transaction
 684      2) Read from a global temp.
 685
 686      Generate tempstosave map from
 687      localitybinding->flatatomicenternode->Set<TempDescriptors>
 688    */
 689
 690   private void computeTempstoSave(LocalityBinding lb) {
 691     if (lb.isAtomic())
 692       return;
 693     Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
 694     Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
 695     MethodDescriptor md=lb.getMethod();
 696     FlatMethod fm=state.getMethodFlat(md);
 697     Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=computeLiveTemps(fm);
 698     Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>> nodetosavetemps=new Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>();
 699     tempstosave.put(lb, nodetosavetemps);
 700     Hashtable<FlatNode, FlatAtomicEnterNode> nodemap=new Hashtable<FlatNode, FlatAtomicEnterNode>();
 701     HashSet<FlatNode> toprocess=new HashSet<FlatNode>();
 702     HashSet<FlatNode> discovered=new HashSet<FlatNode>();
 703     toprocess.add(fm);
 704     discovered.add(fm);
 705     while(!toprocess.isEmpty()) {
 706       FlatNode fn=toprocess.iterator().next();
 707       toprocess.remove(fn);
 708       boolean isatomic=atomictab.get(fn).intValue()>0;
 709       if (isatomic&&
 710           atomictab.get(fn.getPrev(0)).intValue()==0) {
 711         assert(fn.getPrev(0).kind()==FKind.FlatAtomicEnterNode);
 712         nodemap.put(fn, (FlatAtomicEnterNode)fn);
 713         nodetosavetemps.put((FlatAtomicEnterNode)fn, new HashSet<TempDescriptor>());
 714       } else if (isatomic) {
 715         FlatAtomicEnterNode atomicnode=nodemap.get(fn);
 716         Set<TempDescriptor> livetemps=nodetotemps.get(fn);
 717         List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 718         List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
 719
 720         for(Iterator<TempDescriptor> tempit=livetemps.iterator(); tempit.hasNext();) {
 721           TempDescriptor tmp=tempit.next();
 722           if (writes.contains(tmp)) {
 723             nodetosavetemps.get(atomicnode).add(tmp);
 724           } else if (reads.contains(tmp)&&temptab.get(fn).get(tmp)==GLOBAL) {
 725             nodetosavetemps.get(atomicnode).add(tmp);
 726           }
 727         }
 728       }
 729       for(int i=0; i<fn.numNext(); i++) {
 730         FlatNode fnnext=fn.getNext(i);
 731         if (!discovered.contains(fnnext)) {
 732           discovered.add(fnnext);
 733           toprocess.add(fnnext);
 734           if(isatomic) {
 735             nodemap.put(fnnext, nodemap.get(fn));
 736           }
 737         }
 738       }
 739     }
 740   }
 741 }