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