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 tovisit;
  19     Hashtable<LocalityBinding,LocalityBinding> discovered;
  20     Hashtable<MethodDescriptor, MethodDescriptor> dependence;
  21     CallGraph callgraph;
  22     TypeUtil typeutil;
  23     public static final Integer LOCAL=new Integer(0);
  24     public static final Integer GLOBAL=new Integer(1);
  25     public static final Integer EITHER=new Integer(2);
  26     public static final Integer CONFLICT=new Integer(3);
  27
  28
  29     public LocalityAnalysis(State state, CallGraph callgraph, TypeUtil typeutil) {
  30         this.state=state;
  31         this.discovered=new Hashtable<LocalityBinding,LocalityBinding>();
  32         this.dependence=new Hashtable<MethodDescriptor, MethodDescriptor>();
  33         this.tovisit=new Stack();
  34         this.callgraph=callgraph;
  35         doAnalysis();
  36     }
  37
  38     private void doAnalysis() {
  39         computeLocalityBindings();
  40     }
  41
  42     private void computeLocalityBindings() {
  43         LocalityBinding lbmain=new LocalityBinding(typeutil.getMain(), false);
  44         tovisit.add(lbmain);
  45         discovered.put(lbmain, lbmain);
  46
  47         while(!tovisit.empty()) {
  48             LocalityBinding lb=(LocalityBinding) tovisit.pop();
  49             MethodDescriptor md=lb.getMethod();
  50             Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>> temptable=new Hashtable<FlatNode,Hashtable<TempDescriptor, Integer>>();
  51             Hashtable<FlatNode, Integer> atomictable=new Hashtable<FlatNode, Integer>();
  52             computeCallsFlags(md, lb, temptable, atomictable);
  53         }
  54     }
  55
  56     public void computeCallsFlags(MethodDescriptor md, LocalityBinding lb, Hashtable<FlatNode, Hashtable<TempDescriptor, Integer>> temptable, Hashtable<FlatNode, Integer> atomictable) {
  57         FlatMethod fm=state.getMethodFlat(md);
  58         HashSet<FlatNode> tovisit=new HashSet<FlatNode>();
  59         tovisit.add(fm.getNext(0));
  60
  61         {
  62             // Build table for initial node
  63             Hashtable<TempDescriptor,Integer> table=new Hashtable<TempDescriptor,Integer>();
  64             temptable.put(fm, table);
  65             atomictable.put(fm, lb.isAtomic()?1:0);
  66             for(int i=0;i<fm.numParameters();i++) {
  67                 TempDescriptor temp=fm.getParameter(i);
  68                 Integer b=lb.isGlobal(i);
  69                 table.put(temp,b);
  70             }
  71         }
  72
  73         while(!tovisit.isEmpty()) {
  74             FlatNode fn=tovisit.iterator().next();
  75             Hashtable<TempDescriptor, Integer> currtable=new Hashtable<TempDescriptor, Integer>();
  76             int atomicstate=0;
  77             for(int i=0;i<fn.numPrev();i++) {
  78                 FlatNode prevnode=fn.getPrev(i);
  79                 if (atomictable.containsKey(prevnode)) {
  80                     atomicstate=atomictable.get(prevnode).intValue();
  81                 }
  82                 if (!temptable.containsKey(prevnode))
  83                     continue;
  84                 Hashtable<TempDescriptor, Integer> prevtable=temptable.get(prevnode);
  85                 for(Iterator<TempDescriptor> tempit=prevtable.keySet().iterator();tempit.hasNext();) {
  86                     TempDescriptor temp=tempit.next();
  87                     Integer tmpint=prevtable.get(temp);
  88                     Integer oldint=currtable.containsKey(temp)?currtable.get(temp):null;
  89                     Integer newint=merge(tmpint, oldint);
  90                     currtable.put(temp, newint);
  91                 }
  92             }
  93             atomictable.put(fn, atomicstate);
  94             // Process this node
  95             switch(fn.kind()) {
  96             case FKind.FlatAtomicEnterNode:
  97                 processAtomicEnterNode((FlatAtomicEnterNode)fn, atomictable);
  98                 break;
  99             case FKind.FlatAtomicExitNode:
 100                 processAtomicExitNode((FlatAtomicExitNode)fn, atomictable);
 101                 break;
 102             case FKind.FlatCall:
 103                 processCall(lb, (FlatCall)fn, currtable, isAtomic(atomictable, fn));
 104                 break;
 105             case FKind.FlatFieldNode:
 106                 processFieldNode((FlatFieldNode)fn, isAtomic(atomictable, fn), currtable);
 107                 break;
 108             case FKind.FlatSetFieldNode:
 109                 processSetFieldNode((FlatSetFieldNode)fn, isAtomic(atomictable,fn), currtable);
 110                 break;
 111             case FKind.FlatNew:
 112                 processNew((FlatNew)fn, isAtomic(atomictable, fn), currtable);
 113                 break;
 114             case FKind.FlatOpNode:
 115                 processOpNode((FlatOpNode)fn, currtable);
 116                 break;
 117             case FKind.FlatCastNode:
 118                 processCastNode((FlatCastNode)fn, currtable);
 119                 break;
 120             case FKind.FlatLiteralNode:
 121                 processLiteralNode((FlatLiteralNode)fn, currtable);
 122                 break;
 123             case FKind.FlatReturnNode:
 124                 processReturnNode(lb, (FlatReturnNode)fn, currtable);
 125                 break;
 126             case FKind.FlatSetElementNode:
 127                 processSetElementNode((FlatSetElementNode)fn, currtable, isAtomic(atomictable, fn));
 128                 break;
 129             case FKind.FlatElementNode:
 130                 processElementNode((FlatElementNode)fn, currtable, isAtomic(atomictable, fn));
 131                 break;
 132             case FKind.FlatCondBranch:
 133             case FKind.FlatBackEdge:
 134             case FKind.FlatNop:
 135                 //No action needed for these
 136                 break;
 137             case FKind.FlatFlagActionNode:
 138             case FKind.FlatCheckNode:
 139             case FKind.FlatTagDeclaration:
 140                 throw new Error("Incompatible with tasks!");
 141             case FKind.FlatMethod:
 142             default:
 143                 throw new Error();
 144             }
 145             Hashtable<TempDescriptor,Integer> oldtable=temptable.get(fn);
 146             if (oldtable==null||!oldtable.equals(currtable)) {
 147                 // Update table for this node
 148                 temptable.put(fn, currtable);
 149                 for(int i=0;i<fn.numNext();i++) {
 150                     tovisit.add(fn.getNext(i));
 151                 }
 152             }
 153         }
 154     }
 155
 156     private static boolean isAtomic(Hashtable<FlatNode, Integer> atomictable, FlatNode fn) {
 157         return atomictable.get(fn).intValue()>0;
 158     }
 159
 160     private static Integer merge(Integer a, Integer b) {
 161         if (a==null||a.equals(EITHER))
 162             return b;
 163         if (b==null||b.equals(EITHER))
 164             return a;
 165         if (a.equals(b))
 166             return a;
 167         return CONFLICT;
 168     }
 169
 170     void processCall(LocalityBinding currlb, FlatCall fc, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 171         MethodDescriptor nodemd=fc.getMethod();
 172         Set methodset=fc.getThis()==null?callgraph.getMethods(nodemd):
 173             callgraph.getMethods(nodemd, fc.getThis().getType());
 174         Integer currreturnval=null;
 175         for(Iterator methodit=methodset.iterator();methodit.hasNext();) {
 176             MethodDescriptor md=(MethodDescriptor) methodit.next();
 177             LocalityBinding lb=new LocalityBinding(md, isatomic);
 178             for(int i=0;i<fc.numArgs();i++) {
 179                 TempDescriptor arg=fc.getArg(i);
 180                 lb.setGlobal(i,currtable.get(arg));
 181             }
 182             if (fc.getThis()!=null) {
 183                 Integer thistype=currtable.get(fc.getThis());
 184                 if(thistype.equals(CONFLICT))
 185                     throw new Error("Using type that can be either local or global");
 186                 if(thistype.equals(GLOBAL)&&!isatomic)
 187                     throw new Error("Using global object outside of transaction");
 188                 lb.setGlobalThis(thistype);
 189             } else
 190                 lb.setGlobalThis(EITHER);//default value
 191             //lb is built
 192             if (!discovered.containsKey(lb)) {
 193                 lb.setGlobalReturn(EITHER);
 194                 tovisit.add(lb);
 195                 discovered.put(lb, lb);
 196             } else
 197                 lb=discovered.get(lb);
 198             Integer returnval=lb.getGlobalReturn();
 199             currreturnval=merge(returnval, currreturnval);
 200             dependence.put(md, currlb.getMethod());
 201         }
 202         currtable.put(fc.getReturnTemp(), currreturnval);
 203     }
 204
 205     void processFieldNode(FlatFieldNode ffn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 206         Integer type=currtable.get(ffn.getSrc());
 207         TempDescriptor dst=ffn.getDst();
 208         if (type.equals(LOCAL)) {
 209             if (ffn.getField().isGlobal())
 210                 currtable.put(dst,GLOBAL);
 211             else
 212                 currtable.put(dst,LOCAL);
 213         } else if (type.equals(GLOBAL)) {
 214             if (!transaction)
 215                 throw new Error("Global access outside of a transaction");
 216             if (ffn.getField().getType().isPrimitive())
 217                 currtable.put(dst, LOCAL); // primitives are local
 218             else
 219                 currtable.put(dst, GLOBAL);
 220         } else if (type.equals(EITHER)) {
 221             if (ffn.getField().getType().isPrimitive())
 222                 currtable.put(dst, LOCAL); // primitives are local
 223             else
 224                 currtable.put(dst, EITHER);
 225         } else if (type.equals(CONFLICT)) {
 226             throw new Error("Access to object that could be either global or local");
 227         }
 228     }
 229
 230     //need to handle primitives
 231     void processSetFieldNode(FlatSetFieldNode fsfn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 232         Integer srctype=currtable.get(fsfn.getSrc());
 233         Integer dsttype=currtable.get(fsfn.getDst());
 234
 235         if (dsttype.equals(LOCAL)) {
 236             if (fsfn.getField().isGlobal()) {
 237                 if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 238                     throw new Error("Writing possible local reference to global field");
 239             } else {
 240                 if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 241                     throw new Error("Writing possible global reference to local object");
 242             }
 243         } else if (dsttype.equals(GLOBAL)) {
 244             if (!transaction)
 245                 throw new Error("Global access outside of a transaction");
 246             //okay to store primitives in global object
 247             if (srctype.equals(LOCAL) && fsfn.getField().getType().isPrimitive())
 248                 return;
 249             if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 250                 throw new Error("Writing possible local reference to global object");
 251         } else if (dsttype.equals(EITHER)) {
 252             if (srctype.equals(CONFLICT))
 253                 throw new Error("Using reference that could be local or global");
 254         } else if (dsttype.equals(CONFLICT)) {
 255             throw new Error("Access to object that could be either global or local");
 256         }
 257     }
 258
 259     void processNew(FlatNew fn, boolean transaction, Hashtable<TempDescriptor, Integer> currtable) {
 260         if (fn.isGlobal()&&!transaction) {
 261             throw new Error("Allocating global object outside of transaction");
 262         }
 263         if (fn.isGlobal())
 264             currtable.put(fn.getDst(), GLOBAL);
 265         else
 266             currtable.put(fn.getDst(), LOCAL);
 267     }
 268
 269     void processOpNode(FlatOpNode fon, Hashtable<TempDescriptor, Integer> currtable) {
 270         /* Just propagate value */
 271         currtable.put(fon.getDest(), currtable.get(fon.getLeft()));
 272     }
 273
 274     void processCastNode(FlatCastNode fcn, Hashtable<TempDescriptor, Integer> currtable) {
 275         currtable.put(fcn.getDst(), currtable.get(fcn.getSrc()));
 276     }
 277
 278     void processLiteralNode(FlatLiteralNode fln, Hashtable<TempDescriptor, Integer> currtable) {
 279         //null is either
 280         if (fln.getValue()==null)
 281             currtable.put(fln.getDst(), EITHER);
 282         else
 283             currtable.put(fln.getDst(), LOCAL);
 284     }
 285
 286     void processReturnNode(LocalityBinding lb, FlatReturnNode frn, Hashtable<TempDescriptor, Integer> currtable) {
 287         if(frn.getReturnTemp()!=null) {
 288             Integer returntype=currtable.get(frn.getReturnTemp());
 289             lb.setGlobalReturn(merge(returntype, lb.getGlobalReturn()));
 290         }
 291     }
 292
 293     void processSetElementNode(FlatSetElementNode fsen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 294         Integer srctype=currtable.get(fsen.getSrc());
 295         Integer dsttype=currtable.get(fsen.getDst());
 296
 297         if (dsttype.equals(LOCAL)) {
 298             if (!(srctype.equals(LOCAL)||srctype.equals(EITHER)))
 299                 throw new Error("Writing possible global reference to local object");
 300         } else if (dsttype.equals(GLOBAL)) {
 301             if (!(srctype.equals(GLOBAL)||srctype.equals(EITHER)))
 302                 throw new Error("Writing possible local reference to global object");
 303             if (!isatomic)
 304                 throw new Error("Global access outside of a transaction");
 305         } else if (dsttype.equals(EITHER)) {
 306             if (srctype.equals(CONFLICT))
 307                 throw new Error("Using reference that could be local or global");
 308         } else if (dsttype.equals(CONFLICT)) {
 309             throw new Error("Access to object that could be either global or local");
 310         }
 311     }
 312
 313     void processElementNode(FlatElementNode fen, Hashtable<TempDescriptor, Integer> currtable, boolean isatomic) {
 314         Integer type=currtable.get(fen.getSrc());
 315         TempDescriptor dst=fen.getDst();
 316         if (type.equals(LOCAL)) {
 317             currtable.put(dst,LOCAL);
 318         } else if (type.equals(GLOBAL)) {
 319             if (!isatomic)
 320                 throw new Error("Global access outside of a transaction");
 321             currtable.put(dst, GLOBAL);
 322         } else if (type.equals(EITHER)) {
 323             currtable.put(dst, EITHER);
 324         } else if (type.equals(CONFLICT)) {
 325             throw new Error("Access to object that could be either global or local");
 326         }
 327     }
 328     void processAtomicEnterNode(FlatAtomicEnterNode fen, Hashtable<FlatNode, Integer> atomictable) {
 329         int atomic=atomictable.get(fen).intValue();
 330         atomictable.put(fen, new Integer(atomic+1));
 331     }
 332
 333     void processAtomicExitNode(FlatAtomicExitNode fen, Hashtable<FlatNode, Integer> atomictable) {
 334         int atomic=atomictable.get(fen).intValue();
 335         atomictable.put(fen, new Integer(atomic-1));
 336     }
 337 }