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