Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.LinkedList;
   7 import java.util.Set;
   8
   9 import Analysis.CallGraph.CallGraph;
  10 import IR.Descriptor;
  11 import IR.FieldDescriptor;
  12 import IR.MethodDescriptor;
  13 import IR.Operation;
  14 import IR.State;
  15 import IR.Flat.FKind;
  16 import IR.Flat.FlatFieldNode;
  17 import IR.Flat.FlatLiteralNode;
  18 import IR.Flat.FlatMethod;
  19 import IR.Flat.FlatNode;
  20 import IR.Flat.FlatOpNode;
  21 import IR.Flat.FlatSetFieldNode;
  22 import IR.Flat.TempDescriptor;
  23
  24 public class DefinitelyWrittenCheck {
  25
  26   SSJavaAnalysis ssjava;
  27   State state;
  28   CallGraph callGraph;
  29
  30   // maps a descriptor to its known dependents: namely
  31   // methods or tasks that call the descriptor's method
  32   // AND are part of this analysis (reachable from main)
  33   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  34
  35   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  36   // previously.
  37   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  38
  39   // maps a temp descriptor to its heap path
  40   // each temp descriptor has a unique heap path since we do not allow any
  41   // alias.
  42   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  43
  44   // maps a flat method to the READ that is the set of heap path that is
  45   // expected to be written before method invocation
  46   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  47
  48   // maps a flat method to the OVERWRITE that is the set of heap path that is
  49   // overwritten on every possible path during method invocation
  50   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  51
  52   private Hashtable<FlatNode, Hashtable<Descriptor, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  53
  54   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  55     this.state = state;
  56     this.ssjava = ssjava;
  57     this.callGraph = ssjava.getCallGraph();
  58     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
  59     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
  60     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
  61     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  62     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  63   }
  64
  65   public void definitelyWrittenCheck() {
  66
  67     analyzeMethods();
  68   }
  69
  70   private void analyzeMethods() {
  71     // perform method READ/OVERWRITE analysis
  72
  73     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
  74     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
  75
  76     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
  77
  78     // no need to analyze method having ssjava loop
  79     sortedDescriptors.removeFirst();
  80
  81     // analyze scheduled methods until there are no more to visit
  82     while (!sortedDescriptors.isEmpty()) {
  83       // start to analyze leaf node
  84       MethodDescriptor md = sortedDescriptors.removeLast();
  85       analyzeMethod(md);
  86     }
  87
  88   }
  89
  90   private void analyzeMethod(MethodDescriptor md) {
  91     if (state.SSJAVADEBUG) {
  92       System.out.println("Definitely written Analyzing: " + md);
  93     }
  94
  95     FlatMethod fm = state.getMethodFlat(md);
  96
  97     Set<NTuple<Descriptor>> readSet = mapFlatMethodToRead.get(fm);
  98     if (readSet == null) {
  99       readSet = new HashSet<NTuple<Descriptor>>();
 100       mapFlatMethodToRead.put(fm, readSet);
 101     }
 102
 103     Set<NTuple<Descriptor>> overWriteSet = mapFlatMethodToOverWrite.get(fm);
 104     if (overWriteSet == null) {
 105       overWriteSet = new HashSet<NTuple<Descriptor>>();
 106       mapFlatMethodToOverWrite.put(fm, overWriteSet);
 107     }
 108
 109     // intraprocedural analysis
 110     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 111     flatNodesToVisit.add(fm);
 112
 113     while (!flatNodesToVisit.isEmpty()) {
 114       FlatNode fn = flatNodesToVisit.iterator().next();
 115       flatNodesToVisit.remove(fn);
 116
 117       Set<NTuple<Descriptor>> prev = mapFlatNodeToWrittenSet.get(fn);
 118       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
 119
 120       for (int i = 0; i < fn.numPrev(); i++) {
 121         FlatNode prevFn = fn.getPrev(i);
 122         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
 123         if (in != null) {
 124           merge(curr, in);
 125         }
 126       }
 127
 128       analyzeFlatNode(fn, curr, readSet, overWriteSet);
 129
 130       // if a new result, schedule forward nodes for analysis
 131       if (!curr.equals(prev)) {
 132         mapFlatNodeToWrittenSet.put(fn, curr);
 133
 134         for (int i = 0; i < fn.numNext(); i++) {
 135           FlatNode nn = fn.getNext(i);
 136           flatNodesToVisit.add(nn);
 137         }
 138       }
 139
 140     }
 141
 142     System.out.println("READSET=" + mapFlatMethodToRead.get(fm));
 143     System.out.println("OVERWRITESET=" + mapFlatMethodToOverWrite.get(fm));
 144
 145   }
 146
 147   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
 148
 149     if (curr.isEmpty()) {
 150       // WrittenSet has a special initial value which covers all possible
 151       // elements
 152       // For the first time of intersection, we can take all previous set
 153       curr.addAll(in);
 154     } else {
 155       // otherwise, current set is the intersection of the two sets
 156       curr.retainAll(in);
 157     }
 158
 159   }
 160
 161   private void analyzeFlatNode(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
 162       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
 163     TempDescriptor lhs;
 164     TempDescriptor rhs;
 165     FieldDescriptor fld;
 166
 167     switch (fn.kind()) {
 168     case FKind.FlatMethod: {
 169
 170       // set up initial heap paths for method parameters
 171       FlatMethod fm = (FlatMethod) fn;
 172       for (int i = 0; i < fm.numParameters(); i++) {
 173         TempDescriptor param = fm.getParameter(i);
 174         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
 175         heapPath.add(param);
 176         mapHeapPath.put(param, heapPath);
 177       }
 178     }
 179       break;
 180
 181     case FKind.FlatOpNode: {
 182       FlatOpNode fon = (FlatOpNode) fn;
 183       // for a normal assign node, need to propagate lhs's heap path to rhs
 184       if (fon.getOp().getOp() == Operation.ASSIGN) {
 185         rhs = fon.getLeft();
 186         lhs = fon.getDest();
 187
 188         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
 189         if (rhsHeapPath != null) {
 190           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
 191         }
 192
 193       }
 194     }
 195       break;
 196
 197     case FKind.FlatFieldNode:
 198     case FKind.FlatElementNode: {
 199
 200       // y=x.f;
 201
 202       FlatFieldNode ffn = (FlatFieldNode) fn;
 203       lhs = ffn.getDst();
 204       rhs = ffn.getSrc();
 205       fld = ffn.getField();
 206
 207       // set up heap path
 208       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 209       NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 210       readingHeapPath.add(fld);
 211       mapHeapPath.put(lhs, readingHeapPath);
 212
 213       // read (x.f)
 214       // if WT doesnot have hp(x.f), add hp(x.f) to READ
 215       if (!writtenSet.contains(readingHeapPath)) {
 216         readSet.add(readingHeapPath);
 217       }
 218
 219       // need to kill hp(x.f) from WT
 220       writtenSet.remove(readingHeapPath);
 221
 222     }
 223       break;
 224
 225     case FKind.FlatSetFieldNode:
 226     case FKind.FlatSetElementNode: {
 227
 228       // x.f=y;
 229       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 230       lhs = fsfn.getDst();
 231       fld = fsfn.getField();
 232       rhs = fsfn.getSrc();
 233
 234       // set up heap path
 235       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
 236       NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 237       newHeapPath.add(fld);
 238       mapHeapPath.put(fld, newHeapPath);
 239
 240       // write(x.f)
 241       // need to add hp(y) to WT
 242       writtenSet.add(newHeapPath);
 243
 244     }
 245       break;
 246
 247     case FKind.FlatExit: {
 248       // merge the current written set with OVERWRITE set
 249       merge(overWriteSet, writtenSet);
 250     }
 251       break;
 252
 253     }
 254   }
 255
 256   // Borrowed it from disjoint analysis
 257   protected LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
 258
 259     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
 260
 261     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
 262
 263     Iterator<MethodDescriptor> itr = toSort.iterator();
 264     while (itr.hasNext()) {
 265       MethodDescriptor d = itr.next();
 266
 267       if (!discovered.contains(d)) {
 268         dfsVisit(d, toSort, sorted, discovered);
 269       }
 270     }
 271
 272     return sorted;
 273   }
 274
 275   // While we're doing DFS on call graph, remember
 276   // dependencies for efficient queuing of methods
 277   // during interprocedural analysis:
 278   //
 279   // a dependent of a method decriptor d for this analysis is:
 280   // 1) a method or task that invokes d
 281   // 2) in the descriptorsToAnalyze set
 282   protected void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
 283       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
 284
 285     discovered.add(md);
 286
 287     // otherwise call graph guides DFS
 288     Iterator itr = callGraph.getCallerSet(md).iterator();
 289     while (itr.hasNext()) {
 290       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
 291
 292       // only consider callers in the original set to analyze
 293       if (!toSort.contains(dCaller)) {
 294         continue;
 295       }
 296
 297       if (!discovered.contains(dCaller)) {
 298         addDependent(md, // callee
 299             dCaller // caller
 300         );
 301
 302         dfsVisit(dCaller, toSort, sorted, discovered);
 303       }
 304     }
 305
 306     // for leaf-nodes last now!
 307     sorted.addLast(md);
 308   }
 309
 310   // a dependent of a method decriptor d for this analysis is:
 311   // 1) a method or task that invokes d
 312   // 2) in the descriptorsToAnalyze set
 313   protected void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
 314     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
 315     if (deps == null) {
 316       deps = new HashSet<MethodDescriptor>();
 317     }
 318     deps.add(caller);
 319     mapDescriptorToSetDependents.put(callee, deps);
 320   }
 321
 322   private void definitelyWrittenForward(FlatNode entrance) {
 323
 324     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 325     flatNodesToVisit.add(entrance);
 326
 327     while (!flatNodesToVisit.isEmpty()) {
 328       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 329       flatNodesToVisit.remove(fn);
 330
 331       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> prev = definitelyWrittenResults.get(fn);
 332
 333       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr =
 334           new Hashtable<Descriptor, Hashtable<FlatNode, Boolean>>();
 335       for (int i = 0; i < fn.numPrev(); i++) {
 336         FlatNode nn = fn.getPrev(i);
 337         Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> dwIn = definitelyWrittenResults.get(nn);
 338         if (dwIn != null) {
 339           mergeResults(curr, dwIn);
 340         }
 341       }
 342
 343       definitelyWritten_nodeActions(fn, curr, entrance);
 344
 345       // if a new result, schedule forward nodes for analysis
 346       if (!curr.equals(prev)) {
 347         definitelyWrittenResults.put(fn, curr);
 348
 349         for (int i = 0; i < fn.numNext(); i++) {
 350           FlatNode nn = fn.getNext(i);
 351           flatNodesToVisit.add(nn);
 352         }
 353       }
 354     }
 355   }
 356
 357   private void mergeResults(Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr,
 358       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> in) {
 359
 360     Set<Descriptor> inKeySet = in.keySet();
 361     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
 362       Descriptor inKey = (Descriptor) iterator.next();
 363       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 364
 365       Set<FlatNode> pairKeySet = inPair.keySet();
 366       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 367         FlatNode pairKey = (FlatNode) iterator2.next();
 368         Boolean inFlag = inPair.get(pairKey);
 369
 370         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 371         if (currPair == null) {
 372           currPair = new Hashtable<FlatNode, Boolean>();
 373           curr.put(inKey, currPair);
 374         }
 375
 376         Boolean currFlag = currPair.get(pairKey);
 377         // by default, flag is set by false
 378         if (currFlag == null) {
 379           currFlag = Boolean.FALSE;
 380         }
 381         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 382         currPair.put(pairKey, currFlag);
 383       }
 384
 385     }
 386
 387   }
 388
 389   private void definitelyWritten_nodeActions(FlatNode fn,
 390       Hashtable<Descriptor, Hashtable<FlatNode, Boolean>> curr, FlatNode entrance) {
 391
 392     if (fn == entrance) {
 393
 394       Set<Descriptor> keySet = curr.keySet();
 395       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 396         Descriptor key = (Descriptor) iterator.next();
 397         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 398         if (pair != null) {
 399           Set<FlatNode> pairKeySet = pair.keySet();
 400           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 401             FlatNode pairKey = (FlatNode) iterator2.next();
 402             pair.put(pairKey, Boolean.TRUE);
 403           }
 404         }
 405       }
 406
 407     } else {
 408       TempDescriptor lhs;
 409       TempDescriptor rhs;
 410       FieldDescriptor fld;
 411
 412       switch (fn.kind()) {
 413
 414       case FKind.FlatOpNode: {
 415
 416         FlatOpNode fon = (FlatOpNode) fn;
 417         lhs = fon.getDest();
 418         rhs = fon.getLeft();
 419         System.out.println("\nfon=" + fon);
 420
 421         if (fon.getOp().getOp() == Operation.ASSIGN) {
 422
 423           // read(rhs)
 424           Hashtable<FlatNode, Boolean> gen = curr.get(rhs);
 425           if (gen == null) {
 426             gen = new Hashtable<FlatNode, Boolean>();
 427             curr.put(rhs, gen);
 428           }
 429           System.out.println("READ LOC=" + rhs.getType().getExtension());
 430
 431           Boolean currentStatus = gen.get(fn);
 432           if (currentStatus == null) {
 433             gen.put(fn, Boolean.FALSE);
 434           }
 435         }
 436         // write(lhs)
 437         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 438         System.out.println("WRITING LOC=" + lhs.getType().getExtension());
 439
 440       }
 441         break;
 442
 443       case FKind.FlatLiteralNode: {
 444         FlatLiteralNode fln = (FlatLiteralNode) fn;
 445         lhs = fln.getDst();
 446
 447         // write(lhs)
 448         curr.put(lhs, new Hashtable<FlatNode, Boolean>());
 449
 450         System.out.println("WRITING LOC=" + lhs.getType().getExtension());
 451
 452       }
 453         break;
 454
 455       case FKind.FlatFieldNode:
 456       case FKind.FlatElementNode: {
 457
 458         FlatFieldNode ffn = (FlatFieldNode) fn;
 459         lhs = ffn.getSrc();
 460         fld = ffn.getField();
 461
 462         // read field
 463         Hashtable<FlatNode, Boolean> gen = curr.get(fld);
 464         if (gen == null) {
 465           gen = new Hashtable<FlatNode, Boolean>();
 466           curr.put(fld, gen);
 467         }
 468         Boolean currentStatus = gen.get(fn);
 469         if (currentStatus == null) {
 470           gen.put(fn, Boolean.FALSE);
 471         }
 472
 473         System.out.println("\nffn=" + ffn);
 474         System.out.println("READ LOCfld=" + fld.getType().getExtension());
 475         System.out.println("READ LOClhs=" + lhs.getType().getExtension());
 476
 477       }
 478         break;
 479
 480       case FKind.FlatSetFieldNode:
 481       case FKind.FlatSetElementNode: {
 482
 483         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 484         fld = fsfn.getField();
 485
 486         // write(field)
 487         curr.put(fld, new Hashtable<FlatNode, Boolean>());
 488
 489         System.out.println("\nfsfn=" + fsfn);
 490         System.out.println("WRITELOC LOC=" + fld.getType().getExtension());
 491
 492       }
 493         break;
 494
 495       case FKind.FlatCall: {
 496
 497       }
 498         break;
 499
 500       }
 501     }
 502
 503   }
 504
 505 }