Robust/src/Analysis/Locality/LocalityAnalysis.java

   1 package Analysis.Locality;
   2
   3 import java.util.Hashtable;
   4 import java.util.Stack;
   5 import java.util.Set;
   6 import java.util.HashSet;
   7 import java.util.Iterator;
   8 import java.util.Arrays;
   9 import Analysis.CallGraph.CallGraph;
  10 import IR.SymbolTable;
  11 import IR.State;
  12 import IR.TypeUtil;
  13 import IR.MethodDescriptor;
  14 import IR.Flat.*;
  15
  16 public class LocalityAnalysis {
  17     State state;
  18     Stack lbtovisit;
  19     Hashtable<LocalityBinding,LocalityBinding> discovered;
  20     Hashtable<LocalityBinding, Set<LocalityBinding>> dependence;
  21     Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>> temptab;
  22     Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>> atomictab;
  23     Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>> tempstosave;
  24
  25     CallGraph callgraph;
  26     TypeUtil typeutil;
  27     public static final Integer LOCAL=new Integer(0);
  28     public static final Integer GLOBAL=new Integer(1);
  29     public static final Integer EITHER=new Integer(2);
  30     public static final Integer CONFLICT=new Integer(3);
  31
  32     public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  33         this.typeutil=typeutil;
  34         this.state=state;
  35         this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
  36         this.dependence=new Hashtable<LocalityBinding, Set<LocalityBinding>>();
  37         this.temptab=new Hashtable<LocalityBinding, Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>>();
  38         this.atomictab=new Hashtable<LocalityBinding, Hashtable<FlatNode, Integer>>();
  39         this.lbtovisit=new Stack();
  40         this.callgraph=callgraph;
  41         this.tempstosave=new Hashtable<LocalityBinding, Hashtable<FlatAtomicEnterNode, Set<TempDescriptor>>>();
  42
  43         doAnalysis();
  44     }
  45
  46     public Set<LocalityBinding> getLocalityBindings() {
  47         return discovered.keySet();
  48     }
  49
  50     public Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> getNodeTempInfo(LocalityBinding lb) {
  51         return temptab.get(lb);
  52     }
  53
  54     public Hashtable<FlatNode, Integer> getAtomic(LocalityBinding lb) {
  55         return atomictab.get(lb);
  56     }
  57
  58     private void doAnalysis() {
  59         computeLocalityBindings();
  60     }
  61
  62     private void computeLocalityBindings() {
  63         LocalityBinding lbmain=new LocalityBinding(typeutil.getMain(), false);
  64         lbmain.setGlobal(0, LOCAL);
  65         lbtovisit.add(lbmain);
  66         discovered.put(lbmain, lbmain);
  67
  68         while(!lbtovisit.empty()) {
  69             LocalityBinding lb=(LocalityBinding) lbtovisit.pop();
  70             Integer returnglobal=lb.getGlobalReturn();
  71             MethodDescriptor md=lb.getMethod();
  72             Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
  73             Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
  74             computeCallsFlags(md, lb, temptable, atomictable);
  75             atomictab.put(lb, atomictable);
  76             temptab.put(lb, temptable);
  77
  78             if (!md.isStatic()&&!returnglobal.equals(lb.getGlobalReturn())) {
  79                 //return type is more precise now
  80                 //rerun everything that call us
  81                 lbtovisit.addAll(dependence.get(lb));
  82             }
  83         }
  84     }
  85
  86
  87     public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
  88         FlatMethod fm=state.getMethodFlat(md);
  89         HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
  90         tovisit.add(fm.getNext(0));
  91         {
  92             // Build table for initial node
  93             Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
  94             temptable.put(fm, table);
  95             atomictable.put(fm, lb.isAtomic()?1:0);
  96             int offset=md.isStatic()?0:1;
  97             if (!md.isStatic()) {
  98                 table.put(fm.getParameter(0), lb.getGlobalThis());
  99             }
 100             for(int i=offset;i<fm.numParameters();i++) {
 101                 TempDescriptor temp=fm.getParameter(i);
 102                 Integer b=lb.isGlobal(i-offset);
 103                 table.put(temp,b);
 104             }
 105         }
 106
 107         while(!tovisit.isEmpty()) {
 108             FlatNode fn=tovisit.iterator().next();
 109             tovisit.remove(fn);
 110             Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
 111             int atomicstate=0;
 112             for(int i=0;i<fn.numPrev();i++) {
 113                 FlatNode prevnode=fn.getPrev(i);
 114                 if (atomictable.containsKey(prevnode)) {
 115                     atomicstate=atomictable.get(prevnode).intValue();
 116                 }
 117                 if (!temptable.containsKey(prevnode))
 118                     continue;
 119                 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
 120                 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator();tempit.hasNext();) {
 121                     TempDescriptor temp=tempit.next();
 122                     Integer tmpint=prevtable.get(temp);
 123                     Integer oldint=currtable.containsKey(temp)?currtable.get(temp):EITHER;
 124                     Integer newint=merge(tmpint, oldint);
 125                     currtable.put(temp, newint);
 126                 }
 127             }
 128             atomictable.put(fn, atomicstate);
 129             // Process this node
 130             switch(fn.kind()) {
 131             case FKind.FlatAtomicEnterNode:
 132                 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
 133                 break;
 134             case FKind.FlatAtomicExitNode:
 135                 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
 136                 break;
 137             case FKind.FlatCall:
 138                 processCallNode(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn));
 139                 break;
 140             case FKind.FlatFieldNode:
 141                 processFieldNode(lb, (FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
 142                 break;
 143             case FKind.FlatSetFieldNode:
 144                 processSetFieldNode(lb, (FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
 145                 break;
 146             case FKind.FlatNew:
 147                 processNew(lb, (FlatNew)fn, isAtomic(atomictable, fn), currtable);
 148                 break;
 149             case FKind.FlatOpNode:
 150                 processOpNode((FlatOpNode)fn, currtable);
 151                 break;
 152             case FKind.FlatCastNode:
 153                 processCastNode((FlatCastNode)fn, currtable);
 154                 break;
 155             case FKind.FlatLiteralNode:
 156                 processLiteralNode((FlatLiteralNode)fn, currtable);
 157                 break;
 158             case FKind.FlatReturnNode:
 159                 processReturnNode(lb, (FlatReturnNode)fn, currtable);
 160                 break;
 161             case FKind.FlatSetElementNode:
 162                 processSetElementNode(lb, (FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
 163                 break;
 164             case FKind.FlatElementNode:
 165                 processElementNode(lb, (FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
 166                 break;
 167             case FKind.FlatCondBranch:
 168             case FKind.FlatBackEdge:
 169             case FKind.FlatNop:
 170                 //No action needed for these
 171                 break;
 172             case FKind.FlatFlagActionNode:
 173             case FKind.FlatCheckNode:
 174             case FKind.FlatTagDeclaration:
 175                 throw new Error("Incompatible with tasks!");
 176             case FKind.FlatMethod:
 177             default:
 178                 throw new Error();
 179             }
 180             Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 181             if (oldtable==null||!oldtable.equals(currtable)) {
 182                 // Update table for this node
 183                 temptable.put(fn, currtable);
 184                 for(int i=0;i<fn.numNext();i++) {
 185                     tovisit.add(fn.getNext(i));
 186                 }
 187             }
 188         }
 189     }
 190
 191     private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
 192         return atomictable.get(fn).intValue()>0;
 193     }
 194
 195     private static Integer merge(Integer a, Integer b) {
 196         if (a==null||a.equals(EITHER))
 197             return b;
 198         if (b==null||b.equals(EITHER))
 199             return a;
 200         if (a.equals(b))
 201             return a;
 202         return CONFLICT;
 203     }
 204
 205     void processCallNode(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 206         MethodDescriptor nodemd=fc.getMethod();
 207         Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
 208             callgraph.getMethods(nodemd, fc.getThis().getType());
 209         Integer currreturnval=EITHER; //Start off with the either value
 210         for(Iterator methodit=methodset.iterator();methodit.hasNext();) {
 211             MethodDescriptor md=(MethodDescriptor) methodit.next();
 212             LocalityBinding lb=new LocalityBinding(md, isatomic);
 213             for(int i=0;i<fc.numArgs();i++) {
 214                 TempDescriptor arg=fc.getArg(i);
 215                 lb.setGlobal(i,currtable.get(arg));
 216             }
 217             if (fc.getThis()!=null) {
 218                 Integer thistype=currtable.get(fc.getThis());
 219                 if (thistype==null)
 220                     thistype=EITHER;
 221                 if(thistype.equals(CONFLICT))
 222                     throw new Error("Using type that can be either local or global in context:\n"+currlb.getExplanation());
 223                 if(thistype.equals(GLOBAL)&&!isatomic)
 224                     throw new Error("Using global object outside of transaction in context:\n"+currlb.getExplanation());
 225                 lb.setGlobalThis(thistype);
 226             } else
 227                 lb.setGlobalThis(EITHER);//default value
 228             //lb is built
 229             if (!discovered.containsKey(lb)) {
 230                 lb.setGlobalReturn(EITHER);
 231                 lb.setParent(currlb);
 232                 lbtovisit.add(lb);
 233                 discovered.put(lb, lb);
 234             } else
 235                 lb=discovered.get(lb);
 236             Integer returnval=lb.getGlobalReturn();
 237             currreturnval=merge(returnval, currreturnval);
 238             if (!dependence.containsKey(lb))
 239                 dependence.put(lb, new HashSet<LocalityBinding>());
 240             dependence.get(lb).add(currlb);
 241         }
 242         if (fc.getReturnTemp()!=null) {
 243             currtable.put(fc.getReturnTemp(), currreturnval);
 244         }
 245     }
 246
 247     void processFieldNode(LocalityBinding lb, FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 248         Integer type=currtable.get(ffn.getSrc());
 249         TempDescriptor dst=ffn.getDst();
 250         if (type.equals(LOCAL)) {
 251             if (ffn.getField().isGlobal())
 252                 currtable.put(dst,GLOBAL);
 253             else
 254                 currtable.put(dst,LOCAL);
 255         } else if (type.equals(GLOBAL)) {
 256             if (!transaction)
 257                 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 258             if (ffn.getField().getType().isPrimitive())
 259                 currtable.put(dst, LOCAL); // primitives are local
 260             else
 261                 currtable.put(dst, GLOBAL);
 262         } else if (type.equals(EITHER)) {
 263             if (ffn.getField().getType().isPrimitive())
 264                 currtable.put(dst, LOCAL); // primitives are local
 265             else
 266                 currtable.put(dst, EITHER);
 267         } else if (type.equals(CONFLICT)) {
 268             throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 269         }
 270     }
 271
 272     //need to handle primitives
 273     void processSetFieldNode(LocalityBinding lb, FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 274         Integer srctype=currtable.get(fsfn.getSrc());
 275         Integer dsttype=currtable.get(fsfn.getDst());
 276
 277         if (dsttype.equals(LOCAL)) {
 278             if (fsfn.getField().isGlobal()) {
 279                 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 280                     throw new Error("Writing possible local reference to global field in context: \n"+lb.getExplanation());
 281             } else {
 282                 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 283                     throw new Error("Writing possible global reference to local object in context: \n"+lb.getExplanation());
 284             }
 285         } else if (dsttype.equals(GLOBAL)) {
 286             if (!transaction)
 287                 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 288             //okay to store primitives in global object
 289             if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive())
 290                 return;
 291             if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 292                 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
 293         } else if (dsttype.equals(EITHER)) {
 294             if (srctype.equals(CONFLICT))
 295                 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 296         } else if (dsttype.equals(CONFLICT)) {
 297             throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 298         }
 299     }
 300
 301     void processNew(LocalityBinding lb, FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 302         if (fn.isGlobal()&&!transaction) {
 303             throw new Error("Allocating global object outside of transaction in context:"+lb.getExplanation());
 304         }
 305         if (fn.isGlobal())
 306             currtable.put(fn.getDst(), GLOBAL);
 307         else
 308             currtable.put(fn.getDst(), LOCAL);
 309     }
 310
 311     void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 312         /* Just propagate value */
 313         currtable.put(fon.getDest(), currtable.get(fon.getLeft()));
 314     }
 315
 316     void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
 317         currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
 318     }
 319
 320     void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
 321         //null is either
 322         if (fln.getValue()==null)
 323             currtable.put(fln.getDst(), EITHER);
 324         else
 325             currtable.put(fln.getDst(), LOCAL);
 326     }
 327
 328     void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
 329         if(frn.getReturnTemp()!=null) {
 330             Integer returntype=currtable.get(frn.getReturnTemp());
 331             lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
 332         }
 333     }
 334
 335     void processSetElementNode(LocalityBinding lb, FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 336         Integer srctype=currtable.get(fsen.getSrc());
 337         Integer dsttype=currtable.get(fsen.getDst());
 338
 339         if (dsttype.equals(LOCAL)) {
 340             if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 341                 throw new Error("Writing possible global reference to local object in context:\n"+lb.getExplanation());
 342         } else if (dsttype.equals(GLOBAL)) {
 343             if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 344                 throw new Error("Writing possible local reference to global object in context:\n"+lb.getExplanation());
 345             if (!isatomic)
 346                 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 347         } else if (dsttype.equals(EITHER)) {
 348             if (srctype.equals(CONFLICT))
 349                 throw new Error("Using reference that could be local or global in context:\n"+lb.getExplanation());
 350         } else if (dsttype.equals(CONFLICT)) {
 351             throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 352         }
 353     }
 354
 355     void processElementNode(LocalityBinding lb, FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 356         Integer type=currtable.get(fen.getSrc());
 357         TempDescriptor dst=fen.getDst();
 358         if (type.equals(LOCAL)) {
 359             currtable.put(dst,LOCAL);
 360         } else if (type.equals(GLOBAL)) {
 361             if (!isatomic)
 362                 throw new Error("Global access outside of a transaction in context:\n"+lb.getExplanation());
 363             currtable.put(dst, GLOBAL);
 364         } else if (type.equals(EITHER)) {
 365             currtable.put(dst, EITHER);
 366         } else if (type.equals(CONFLICT)) {
 367             throw new Error("Access to object that could be either global or local in context:\n"+lb.getExplanation());
 368         }
 369     }
 370
 371     void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
 372         int atomic=atomictable.get(fen).intValue();
 373         atomictable.put(fen, new Integer(atomic+1));
 374     }
 375
 376     void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
 377         int atomic=atomictable.get(fen).intValue();
 378         atomictable.put(fen, new Integer(atomic-1));
 379     }
 380
 381     private Hashtable<FlatNode, Set<TempDescriptor>> computeLiveTemps(FlatMethod fm) {
 382         Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=new Hashtable<FlatNode, Set<TempDescriptor>>();
 383
 384         Set<FlatNode> toprocess=fm.getNodeSet();
 385
 386         while(!toprocess.isEmpty()) {
 387             FlatNode fn=toprocess.iterator().next();
 388             toprocess.remove(fn);
 389             boolean isatomic=atomictab.get(fn).intValue()>0;
 390
 391             List<TempDescriptor> reads=Arrays.asList(fn.readsTemps());
 392             List<TempDescriptor> writes=Arrays.asList(fn.readsTemps());
 393
 394             HashSet<TempDescriptor> tempset=new HashSet<TempDescriptor>();
 395             for(int i=0;i<fn.numNext();i++) {
 396                 FlatNode fnnext=fn.getNext(i);
 397                 if (nodetotemps.containsKey(fnnext))
 398                     tempset.addAll(nodetotemps.get(fnnext));
 399             }
 400             tempset.removeAll(writes);
 401             tempset.addAll(reads);
 402             if (!nodetotemps.containsKey(fn)||
 403                 nodetotemps.get(fn).equals(tempset)) {
 404                 nodetotemps.put(fn, tempset);
 405                 for(int i=0;i<fn.numPrev(i);i++)
 406                     toprocess.add(fn.getPrev(i));
 407             }
 408         }
 409         return nodetotemps;
 410     }
 411
 412     /* Need to checkpoint all temps that could be read from along any
 413      * path that are either:
 414        1) Written to by any assignment inside the transaction
 415        2) Read from a global temp.
 416
 417        Generate tempstosave map from
 418        localitybinding->flatatomicenternode->Set<TempDescriptors>
 419     */
 420
 421     private void computeTempstoCheckpoint(LocalityBinding lb) {
 422         Hashtable<FlatNode, Integer> atomictab=getAtomic(lb);
 423         Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptab=getNodeTempInfo(lb);
 424         MethodDescriptor md=lb.getMethod();
 425         FlatMethod fm=state.getMethodFlat(md);
 426
 427         Hashtable<FlatNode, Set<TempDescriptor>> nodetotemps=computeLiveTemps(md);
 428
 429
 430     }
 431 }