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