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