Programming Languages Research Group: Git - IRC.git/blob

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