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