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 import java.util.Stack;
   9 import java.util.Vector;
  10
  11 import Analysis.CallGraph.CallGraph;
  12 import Analysis.Loops.LoopFinder;
  13 import IR.Descriptor;
  14 import IR.FieldDescriptor;
  15 import IR.MethodDescriptor;
  16 import IR.Operation;
  17 import IR.State;
  18 import IR.TypeDescriptor;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatCall;
  21 import IR.Flat.FlatFieldNode;
  22 import IR.Flat.FlatLiteralNode;
  23 import IR.Flat.FlatMethod;
  24 import IR.Flat.FlatNode;
  25 import IR.Flat.FlatOpNode;
  26 import IR.Flat.FlatSetFieldNode;
  27 import IR.Flat.TempDescriptor;
  28
  29 public class DefinitelyWrittenCheck {
  30
  31   SSJavaAnalysis ssjava;
  32   State state;
  33   CallGraph callGraph;
  34
  35   // maps a descriptor to its known dependents: namely
  36   // methods or tasks that call the descriptor's method
  37   // AND are part of this analysis (reachable from main)
  38   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  39
  40   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  41   // previously.
  42   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  43
  44   // maps a temp descriptor to its heap path
  45   // each temp descriptor has a unique heap path since we do not allow any
  46   // alias.
  47   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  48
  49   // maps a flat method to the READ that is the set of heap path that is
  50   // expected to be written before method invocation
  51   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  52
  53   // maps a flat method to the OVERWRITE that is the set of heap path that is
  54   // overwritten on every possible path during method invocation
  55   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  56
  57   // points to method containing SSJAVA Loop
  58   private MethodDescriptor methodContainingSSJavaLoop;
  59
  60   // maps a flatnode to definitely written analysis mapping M
  61   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  62
  63   // maps a method descriptor to its current summary during the analysis
  64   // then analysis reaches fixed-point, this mapping will have the final summary
  65   // for each method descriptor
  66   private Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>> mapMethodDescriptorToCompleteClearingSummary;
  67
  68   // maps a method descriptor to the merged incoming caller's current
  69   // overwritten status
  70   private Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>> mapMethodDescriptorToInitialClearingSummary;
  71
  72   // maps a flat node to current partial results
  73   private Hashtable<FlatNode, Hashtable<Location, Vector<Object>>> mapFlatNodeToClearingSummary;
  74
  75   private FlatNode ssjavaLoopEntrance;
  76   private LoopFinder ssjavaLoop;
  77   private Set<FlatNode> loopIncElements;
  78
  79   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  80   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  81
  82   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  83     this.state = state;
  84     this.ssjava = ssjava;
  85     this.callGraph = ssjava.getCallGraph();
  86     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
  87     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
  88     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
  89     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  90     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  91     this.definitelyWrittenResults =
  92         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
  93     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
  94     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
  95     this.mapMethodDescriptorToCompleteClearingSummary =
  96         new Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>>();
  97     this.mapMethodDescriptorToInitialClearingSummary =
  98         new Hashtable<MethodDescriptor, Hashtable<Location, Vector<Object>>>();
  99     this.mapFlatNodeToClearingSummary =
 100         new Hashtable<FlatNode, Hashtable<Location, Vector<Object>>>();
 101   }
 102
 103   public void definitelyWrittenCheck() {
 104     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 105       methodReadOverWriteAnalysis();
 106       writtenAnalyis();
 107 //      sharedLocationAnalysis();
 108     }
 109   }
 110
 111   private void sharedLocationAnalysis() {
 112     // verify that all concrete locations of shared location are cleared out at
 113     // the same time once per the out-most loop
 114
 115     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 116     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 117
 118     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 119
 120     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 121     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 122     methodDescriptorToVistSet.addAll(sortedDescriptors);
 123
 124     while (!sortedDescriptors.isEmpty()) {
 125       MethodDescriptor md = sortedDescriptors.removeLast();
 126       methodDescriptorsToVisitStack.add(md);
 127     }
 128
 129     // analyze scheduled methods until there are no more to visit
 130     while (!methodDescriptorsToVisitStack.isEmpty()) {
 131       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 132       FlatMethod fm = state.getMethodFlat(md);
 133
 134       sharedLocation_analyzeMethod(fm, (fm.equals(methodContainingSSJavaLoop)));
 135
 136       if (true) {
 137
 138         // results for callee changed, so enqueue dependents caller for
 139         // further analysis
 140         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 141         while (depsItr.hasNext()) {
 142           MethodDescriptor methodNext = depsItr.next();
 143           if (!methodDescriptorsToVisitStack.contains(methodNext)
 144               && methodDescriptorToVistSet.contains(methodNext)) {
 145             methodDescriptorsToVisitStack.add(methodNext);
 146           }
 147
 148         }
 149
 150       }
 151
 152     }
 153
 154     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 155     flatNodesToVisit.add(ssjavaLoopEntrance);
 156
 157   }
 158
 159   private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
 160
 161     if (state.SSJAVADEBUG) {
 162       System.out.println("Definitely written for shared locations Analyzing: " + fm);
 163     }
 164
 165     // intraprocedural analysis
 166     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 167     Set<FlatNode> visited = new HashSet<FlatNode>();
 168
 169     if (onlyVisitSSJavaLoop) {
 170       flatNodesToVisit.add(ssjavaLoopEntrance);
 171     } else {
 172       flatNodesToVisit.add(fm);
 173     }
 174
 175     while (!flatNodesToVisit.isEmpty()) {
 176       FlatNode fn = flatNodesToVisit.iterator().next();
 177       flatNodesToVisit.remove(fn);
 178
 179       Hashtable<Location, Vector<Object>> curr = new Hashtable<Location, Vector<Object>>();
 180
 181       for (int i = 0; i < fn.numPrev(); i++) {
 182         FlatNode prevFn = fn.getPrev(i);
 183         Hashtable<Location, Vector<Object>> in = mapFlatNodeToClearingSummary.get(prevFn);
 184         if (in != null) {
 185           mergeSharedAnaylsis(curr, in);
 186         }
 187       }
 188
 189       sharedLocation_nodeActions(fn, curr);
 190
 191       Hashtable<Location, Vector<Object>> clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 192
 193       if (!curr.equals(clearingPrev)) {
 194         mapFlatNodeToClearingSummary.put(fn, curr);
 195
 196         for (int i = 0; i < fn.numNext(); i++) {
 197           FlatNode nn = fn.getNext(i);
 198
 199           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 200             flatNodesToVisit.add(nn);
 201           }
 202
 203         }
 204       }
 205
 206     }
 207
 208   }
 209
 210   private void sharedLocation_nodeActions(FlatNode fn, Hashtable<Location, Vector<Object>> curr) {
 211
 212     TempDescriptor lhs;
 213     TempDescriptor rhs;
 214     FieldDescriptor fld;
 215
 216     System.out.println("fn="+fn);
 217     switch (fn.kind()) {
 218     case FKind.FlatFieldNode:
 219     case FKind.FlatElementNode: {
 220
 221       FlatFieldNode ffn = (FlatFieldNode) fn;
 222       lhs = ffn.getDst();
 223       rhs = ffn.getSrc();
 224       fld = ffn.getField();
 225
 226       // read field
 227       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 228       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 229       fldHeapPath.add(fld);
 230
 231       if (fld.getType().isImmutable()) {
 232         readLocation(fn, fldHeapPath, curr);
 233       }
 234
 235       // propagate rhs's heap path to the lhs
 236       mapHeapPath.put(lhs, fldHeapPath);
 237
 238     }
 239       break;
 240
 241     case FKind.FlatSetFieldNode:
 242     case FKind.FlatSetElementNode: {
 243
 244       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 245       lhs = fsfn.getDst();
 246       fld = fsfn.getField();
 247
 248       // write(field)
 249       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 250       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 251       writeLocation(curr, fldHeapPath, fld);
 252
 253     }
 254       break;
 255
 256     case FKind.FlatCall: {
 257
 258     }
 259       break;
 260     }
 261
 262   }
 263
 264   private void writeLocation(Hashtable<Location, Vector<Object>> curr,
 265       NTuple<Descriptor> fldHeapPath, FieldDescriptor fld) {
 266
 267     Location fieldLoc = (Location) fld.getType().getExtension();
 268     if (ssjava.isSharedLocation(fieldLoc)) {
 269
 270       Vector<Object> v = curr.get(fieldLoc);
 271       if (v == null) {
 272         v = new Vector<Object>();
 273         curr.put(fieldLoc, v);
 274         v.add(0, fldHeapPath);
 275         v.add(1, new HashSet());
 276         v.add(2, new Boolean(false));
 277       }
 278       ((Set) v.get(1)).add(fld);
 279     }
 280   }
 281
 282   private void readLocation(FlatNode fn, NTuple<Descriptor> fldHeapPath,
 283       Hashtable<Location, Vector<Object>> curr) {
 284     // TODO Auto-generated method stub
 285
 286   }
 287
 288   private void writtenAnalyis() {
 289     // perform second stage analysis: intraprocedural analysis ensure that
 290     // all
 291     // variables are definitely written in-between the same read
 292
 293     // First, identify ssjava loop entrace
 294     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 295     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 296     flatNodesToVisit.add(fm);
 297
 298     LoopFinder loopFinder = new LoopFinder(fm);
 299
 300     while (!flatNodesToVisit.isEmpty()) {
 301       FlatNode fn = flatNodesToVisit.iterator().next();
 302       flatNodesToVisit.remove(fn);
 303
 304       String label = (String) state.fn2labelMap.get(fn);
 305       if (label != null) {
 306
 307         if (label.equals(ssjava.SSJAVA)) {
 308           ssjavaLoopEntrance = fn;
 309           break;
 310         }
 311       }
 312
 313       for (int i = 0; i < fn.numNext(); i++) {
 314         FlatNode nn = fn.getNext(i);
 315         flatNodesToVisit.add(nn);
 316       }
 317     }
 318
 319     assert ssjavaLoopEntrance != null;
 320
 321     // assume that ssjava loop is top-level loop in method, not nested loop
 322     Set nestedLoop = loopFinder.nestedLoops();
 323     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 324       LoopFinder lf = (LoopFinder) loopIter.next();
 325       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 326         ssjavaLoop = lf;
 327       }
 328     }
 329
 330     assert ssjavaLoop != null;
 331
 332     writtenAnalysis_analyzeLoop();
 333
 334   }
 335
 336   private void writtenAnalysis_analyzeLoop() {
 337
 338     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 339     flatNodesToVisit.add(ssjavaLoopEntrance);
 340
 341     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 342
 343     while (!flatNodesToVisit.isEmpty()) {
 344       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 345       flatNodesToVisit.remove(fn);
 346
 347       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 348           definitelyWrittenResults.get(fn);
 349
 350       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 351           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 352       for (int i = 0; i < fn.numPrev(); i++) {
 353         FlatNode nn = fn.getPrev(i);
 354         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 355             definitelyWrittenResults.get(nn);
 356         if (dwIn != null) {
 357           merge(curr, dwIn);
 358         }
 359       }
 360
 361       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 362
 363       // if a new result, schedule forward nodes for analysis
 364       if (!curr.equals(prev)) {
 365         definitelyWrittenResults.put(fn, curr);
 366
 367         for (int i = 0; i < fn.numNext(); i++) {
 368           FlatNode nn = fn.getNext(i);
 369           if (loopIncElements.contains(nn)) {
 370             flatNodesToVisit.add(nn);
 371           }
 372
 373         }
 374       }
 375     }
 376   }
 377
 378   private void writtenAnalysis_nodeAction(FlatNode fn,
 379       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 380
 381     if (fn.equals(loopEntrance)) {
 382       // it reaches loop entrance: changes all flag to true
 383       Set<NTuple<Descriptor>> keySet = curr.keySet();
 384       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 385         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 386         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 387         if (pair != null) {
 388           Set<FlatNode> pairKeySet = pair.keySet();
 389           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 390             FlatNode pairKey = (FlatNode) iterator2.next();
 391             pair.put(pairKey, Boolean.TRUE);
 392           }
 393         }
 394       }
 395     } else {
 396       TempDescriptor lhs;
 397       TempDescriptor rhs;
 398       FieldDescriptor fld;
 399
 400       switch (fn.kind()) {
 401       case FKind.FlatOpNode: {
 402         FlatOpNode fon = (FlatOpNode) fn;
 403         lhs = fon.getDest();
 404         rhs = fon.getLeft();
 405
 406         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 407         if (!rhs.getType().isImmutable()) {
 408           mapHeapPath.put(lhs, rhsHeapPath);
 409         } else {
 410           if (fon.getOp().getOp() == Operation.ASSIGN) {
 411             // read(rhs)
 412             readValue(fn, rhsHeapPath, curr);
 413           }
 414           // write(lhs)
 415           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 416           removeHeapPath(curr, lhsHeapPath);
 417         }
 418       }
 419         break;
 420
 421       case FKind.FlatLiteralNode: {
 422         FlatLiteralNode fln = (FlatLiteralNode) fn;
 423         lhs = fln.getDst();
 424
 425         // write(lhs)
 426         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 427         removeHeapPath(curr, lhsHeapPath);
 428
 429       }
 430         break;
 431
 432       case FKind.FlatFieldNode:
 433       case FKind.FlatElementNode: {
 434
 435         FlatFieldNode ffn = (FlatFieldNode) fn;
 436         lhs = ffn.getDst();
 437         rhs = ffn.getSrc();
 438         fld = ffn.getField();
 439
 440         // read field
 441         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 442         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 443         fldHeapPath.add(fld);
 444
 445         if (fld.getType().isImmutable()) {
 446           readValue(fn, fldHeapPath, curr);
 447         }
 448
 449         // propagate rhs's heap path to the lhs
 450         mapHeapPath.put(lhs, fldHeapPath);
 451
 452       }
 453         break;
 454
 455       case FKind.FlatSetFieldNode:
 456       case FKind.FlatSetElementNode: {
 457
 458         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 459         lhs = fsfn.getDst();
 460         fld = fsfn.getField();
 461
 462         // write(field)
 463         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 464         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 465         fldHeapPath.add(fld);
 466         removeHeapPath(curr, fldHeapPath);
 467
 468       }
 469         break;
 470
 471       case FKind.FlatCall: {
 472         FlatCall fc = (FlatCall) fn;
 473         bindHeapPathCallerArgWithCaleeParam(fc);
 474
 475         // add <hp,statement,false> in which hp is an element of
 476         // READ_bound set
 477         // of callee: callee has 'read' requirement!
 478         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 479           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 480
 481           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 482           if (gen == null) {
 483             gen = new Hashtable<FlatNode, Boolean>();
 484             curr.put(read, gen);
 485           }
 486           Boolean currentStatus = gen.get(fn);
 487           if (currentStatus == null) {
 488             gen.put(fn, Boolean.FALSE);
 489           } else {
 490             checkFlag(currentStatus.booleanValue(), fn, read);
 491           }
 492         }
 493
 494         // removes <hp,statement,flag> if hp is an element of
 495         // OVERWRITE_bound
 496         // set of callee. it means that callee will overwrite it
 497         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 498           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 499           removeHeapPath(curr, write);
 500         }
 501       }
 502         break;
 503
 504       }
 505     }
 506
 507   }
 508
 509   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 510       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 511     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 512     if (gen == null) {
 513       gen = new Hashtable<FlatNode, Boolean>();
 514       curr.put(hp, gen);
 515     }
 516     Boolean currentStatus = gen.get(fn);
 517     if (currentStatus == null) {
 518       gen.put(fn, Boolean.FALSE);
 519     } else {
 520       checkFlag(currentStatus.booleanValue(), fn, hp);
 521     }
 522
 523   }
 524
 525   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 526       NTuple<Descriptor> hp) {
 527
 528     // removes all of heap path that starts with prefix 'hp'
 529     // since any reference overwrite along heap path gives overwriting side
 530     // effects on the value
 531
 532     Set<NTuple<Descriptor>> keySet = curr.keySet();
 533     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 534       NTuple<Descriptor> key = iter.next();
 535       if (key.startsWith(hp)) {
 536         curr.put(key, new Hashtable<FlatNode, Boolean>());
 537       }
 538     }
 539
 540   }
 541
 542   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
 543     // compute all possible callee set
 544     // transform all READ/OVERWRITE set from the any possible
 545     // callees to the
 546     // caller
 547
 548     calleeUnionBoundReadSet.clear();
 549     calleeIntersectBoundOverWriteSet.clear();
 550
 551     MethodDescriptor mdCallee = fc.getMethod();
 552     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 553     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 554     TypeDescriptor typeDesc = fc.getThis().getType();
 555     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 556
 557     // create mapping from arg idx to its heap paths
 558     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 559         new Hashtable<Integer, NTuple<Descriptor>>();
 560
 561     // arg idx is starting from 'this' arg
 562     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 563     if (thisHeapPath == null) {
 564       // method is called without creating new flat node representing 'this'
 565       thisHeapPath = new NTuple<Descriptor>();
 566       thisHeapPath.add(fc.getThis());
 567     }
 568
 569     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 570
 571     for (int i = 0; i < fc.numArgs(); i++) {
 572       TempDescriptor arg = fc.getArg(i);
 573       NTuple<Descriptor> argHeapPath = computePath(arg);
 574       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 575     }
 576
 577     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 578       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 579       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
 580
 581       // binding caller's args and callee's params
 582
 583       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
 584       if (calleeReadSet == null) {
 585         calleeReadSet = new HashSet<NTuple<Descriptor>>();
 586         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
 587       }
 588       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
 589       if (calleeOverWriteSet == null) {
 590         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
 591         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
 592       }
 593
 594       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 595           new Hashtable<Integer, TempDescriptor>();
 596       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 597         TempDescriptor param = calleeFlatMethod.getParameter(i);
 598         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 599       }
 600
 601       Set<NTuple<Descriptor>> calleeBoundReadSet =
 602           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 603       // union of the current read set and the current callee's
 604       // read set
 605       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
 606       Set<NTuple<Descriptor>> calleeBoundWriteSet =
 607           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 608       // intersection of the current overwrite set and the current
 609       // callee's
 610       // overwrite set
 611       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
 612     }
 613
 614   }
 615
 616   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
 617     if (booleanValue) {
 618       throw new Error(
 619           "There is a variable, which is reachable through references "
 620               + hp
 621               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
 622               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
 623               + fn.getNumLine());
 624     }
 625   }
 626
 627   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 628       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
 629
 630     Set<NTuple<Descriptor>> inKeySet = in.keySet();
 631     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
 632       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
 633       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 634
 635       Set<FlatNode> pairKeySet = inPair.keySet();
 636       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 637         FlatNode pairKey = (FlatNode) iterator2.next();
 638         Boolean inFlag = inPair.get(pairKey);
 639
 640         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 641         if (currPair == null) {
 642           currPair = new Hashtable<FlatNode, Boolean>();
 643           curr.put(inKey, currPair);
 644         }
 645
 646         Boolean currFlag = currPair.get(pairKey);
 647         // by default, flag is set by false
 648         if (currFlag == null) {
 649           currFlag = Boolean.FALSE;
 650         }
 651         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 652         currPair.put(pairKey, currFlag);
 653       }
 654
 655     }
 656
 657   }
 658
 659   private void methodReadOverWriteAnalysis() {
 660     // perform method READ/OVERWRITE analysis
 661     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 662     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 663
 664     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 665
 666     // no need to analyze method having ssjava loop
 667     methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
 668
 669     // current descriptors to visit in fixed-point interprocedural analysis,
 670     // prioritized by
 671     // dependency in the call graph
 672     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 673
 674     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 675     methodDescriptorToVistSet.addAll(sortedDescriptors);
 676
 677     while (!sortedDescriptors.isEmpty()) {
 678       MethodDescriptor md = sortedDescriptors.removeFirst();
 679       methodDescriptorsToVisitStack.add(md);
 680     }
 681
 682     // analyze scheduled methods until there are no more to visit
 683     while (!methodDescriptorsToVisitStack.isEmpty()) {
 684       // start to analyze leaf node
 685       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 686       FlatMethod fm = state.getMethodFlat(md);
 687
 688       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
 689       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
 690
 691       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
 692
 693       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
 694       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
 695
 696       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
 697         mapFlatMethodToRead.put(fm, readSet);
 698         mapFlatMethodToOverWrite.put(fm, overWriteSet);
 699
 700         // results for callee changed, so enqueue dependents caller for
 701         // further
 702         // analysis
 703         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 704         while (depsItr.hasNext()) {
 705           MethodDescriptor methodNext = depsItr.next();
 706           if (!methodDescriptorsToVisitStack.contains(methodNext)
 707               && methodDescriptorToVistSet.contains(methodNext)) {
 708             methodDescriptorsToVisitStack.add(methodNext);
 709           }
 710
 711         }
 712
 713       }
 714
 715     }
 716
 717   }
 718
 719   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
 720       Set<NTuple<Descriptor>> overWriteSet) {
 721     if (state.SSJAVADEBUG) {
 722       System.out.println("Definitely written Analyzing: " + fm);
 723     }
 724
 725     // intraprocedural analysis
 726     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 727     flatNodesToVisit.add(fm);
 728
 729     while (!flatNodesToVisit.isEmpty()) {
 730       FlatNode fn = flatNodesToVisit.iterator().next();
 731       flatNodesToVisit.remove(fn);
 732
 733       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
 734
 735       for (int i = 0; i < fn.numPrev(); i++) {
 736         FlatNode prevFn = fn.getPrev(i);
 737         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
 738         if (in != null) {
 739           merge(curr, in);
 740         }
 741       }
 742
 743       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
 744
 745       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
 746       if (!curr.equals(writtenSetPrev)) {
 747         mapFlatNodeToWrittenSet.put(fn, curr);
 748         for (int i = 0; i < fn.numNext(); i++) {
 749           FlatNode nn = fn.getNext(i);
 750           flatNodesToVisit.add(nn);
 751         }
 752       }
 753
 754     }
 755
 756   }
 757
 758   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
 759       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
 760     TempDescriptor lhs;
 761     TempDescriptor rhs;
 762     FieldDescriptor fld;
 763
 764     switch (fn.kind()) {
 765     case FKind.FlatMethod: {
 766
 767       // set up initial heap paths for method parameters
 768       FlatMethod fm = (FlatMethod) fn;
 769       for (int i = 0; i < fm.numParameters(); i++) {
 770         TempDescriptor param = fm.getParameter(i);
 771         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
 772         heapPath.add(param);
 773         mapHeapPath.put(param, heapPath);
 774       }
 775     }
 776       break;
 777
 778     case FKind.FlatOpNode: {
 779       FlatOpNode fon = (FlatOpNode) fn;
 780       // for a normal assign node, need to propagate lhs's heap path to
 781       // rhs
 782       if (fon.getOp().getOp() == Operation.ASSIGN) {
 783         rhs = fon.getLeft();
 784         lhs = fon.getDest();
 785
 786         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
 787         if (rhsHeapPath != null) {
 788           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
 789         }
 790
 791       }
 792     }
 793       break;
 794
 795     case FKind.FlatFieldNode:
 796     case FKind.FlatElementNode: {
 797
 798       // y=x.f;
 799
 800       FlatFieldNode ffn = (FlatFieldNode) fn;
 801       lhs = ffn.getDst();
 802       rhs = ffn.getSrc();
 803       fld = ffn.getField();
 804
 805       // set up heap path
 806       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 807       if (srcHeapPath != null) {
 808         // if lhs srcHeapPath is null, it means that it is not reachable from
 809         // callee's parameters. so just ignore it
 810
 811         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 812         readingHeapPath.add(fld);
 813         mapHeapPath.put(lhs, readingHeapPath);
 814
 815         // read (x.f)
 816         if (fld.getType().isImmutable()) {
 817           // if WT doesnot have hp(x.f), add hp(x.f) to READ
 818           if (!writtenSet.contains(readingHeapPath)) {
 819             readSet.add(readingHeapPath);
 820           }
 821         }
 822
 823         // need to kill hp(x.f) from WT
 824         writtenSet.remove(readingHeapPath);
 825       }
 826
 827     }
 828       break;
 829
 830     case FKind.FlatSetFieldNode:
 831     case FKind.FlatSetElementNode: {
 832
 833       // x.f=y;
 834       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 835       lhs = fsfn.getDst();
 836       fld = fsfn.getField();
 837       rhs = fsfn.getSrc();
 838
 839       // set up heap path
 840       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
 841       if (lhsHeapPath != null) {
 842         // if lhs heap path is null, it means that it is not reachable from
 843         // callee's parameters. so just ignore it
 844         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 845         newHeapPath.add(fld);
 846         mapHeapPath.put(fld, newHeapPath);
 847
 848         // write(x.f)
 849         // need to add hp(y) to WT
 850         writtenSet.add(newHeapPath);
 851       }
 852
 853     }
 854       break;
 855
 856     case FKind.FlatCall: {
 857
 858       FlatCall fc = (FlatCall) fn;
 859
 860       bindHeapPathCallerArgWithCaleeParam(fc);
 861
 862       // add heap path, which is an element of READ_bound set and is not
 863       // an
 864       // element of WT set, to the caller's READ set
 865       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 866         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 867         if (!writtenSet.contains(read)) {
 868           readSet.add(read);
 869         }
 870       }
 871       writtenSet.removeAll(calleeUnionBoundReadSet);
 872
 873       // add heap path, which is an element of OVERWRITE_bound set, to the
 874       // caller's WT set
 875       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 876         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 877         writtenSet.add(write);
 878       }
 879
 880     }
 881       break;
 882
 883     case FKind.FlatExit: {
 884       // merge the current written set with OVERWRITE set
 885       merge(overWriteSet, writtenSet);
 886     }
 887       break;
 888
 889     }
 890
 891   }
 892
 893   private void mergeSharedAnaylsis(Hashtable<Location, Vector<Object>> curr,
 894       Hashtable<Location, Vector<Object>> in) {
 895
 896   }
 897
 898   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
 899     if (curr.isEmpty()) {
 900       // WrittenSet has a special initial value which covers all possible
 901       // elements
 902       // For the first time of intersection, we can take all previous set
 903       curr.addAll(in);
 904     } else {
 905       // otherwise, current set is the intersection of the two sets
 906       curr.retainAll(in);
 907     }
 908
 909   }
 910
 911   // combine two heap path
 912   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
 913     NTuple<Descriptor> combined = new NTuple<Descriptor>();
 914
 915     for (int i = 0; i < callerIn.size(); i++) {
 916       combined.add(callerIn.get(i));
 917     }
 918
 919     // the first element of callee's heap path represents parameter
 920     // so we skip the first one since it is already added from caller's heap
 921     // path
 922     for (int i = 1; i < calleeIn.size(); i++) {
 923       combined.add(calleeIn.get(i));
 924     }
 925
 926     return combined;
 927   }
 928
 929   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
 930       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
 931       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
 932
 933     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
 934
 935     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
 936     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 937       Integer idx = (Integer) iterator.next();
 938
 939       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
 940       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
 941
 942       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
 943         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
 944         if (element.startsWith(calleeParam)) {
 945           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
 946           boundedCalleeSet.add(boundElement);
 947         }
 948
 949       }
 950
 951     }
 952     return boundedCalleeSet;
 953
 954   }
 955
 956   // Borrowed it from disjoint analysis
 957   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
 958
 959     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
 960
 961     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
 962
 963     Iterator<MethodDescriptor> itr = toSort.iterator();
 964     while (itr.hasNext()) {
 965       MethodDescriptor d = itr.next();
 966
 967       if (!discovered.contains(d)) {
 968         dfsVisit(d, toSort, sorted, discovered);
 969       }
 970     }
 971
 972     return sorted;
 973   }
 974
 975   // While we're doing DFS on call graph, remember
 976   // dependencies for efficient queuing of methods
 977   // during interprocedural analysis:
 978   //
 979   // a dependent of a method decriptor d for this analysis is:
 980   // 1) a method or task that invokes d
 981   // 2) in the descriptorsToAnalyze set
 982   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
 983       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
 984
 985     discovered.add(md);
 986
 987     // otherwise call graph guides DFS
 988     Iterator itr = callGraph.getCallerSet(md).iterator();
 989     while (itr.hasNext()) {
 990       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
 991
 992       // only consider callers in the original set to analyze
 993       if (!toSort.contains(dCaller)) {
 994         continue;
 995       }
 996
 997       if (!discovered.contains(dCaller)) {
 998         addDependent(md, // callee
 999             dCaller // caller
1000         );
1001
1002         dfsVisit(dCaller, toSort, sorted, discovered);
1003       }
1004     }
1005
1006     // for leaf-nodes last now!
1007     sorted.addLast(md);
1008   }
1009
1010   // a dependent of a method decriptor d for this analysis is:
1011   // 1) a method or task that invokes d
1012   // 2) in the descriptorsToAnalyze set
1013   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1014     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1015     if (deps == null) {
1016       deps = new HashSet<MethodDescriptor>();
1017     }
1018     deps.add(caller);
1019     mapDescriptorToSetDependents.put(callee, deps);
1020   }
1021
1022   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1023     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1024     if (deps == null) {
1025       deps = new HashSet<MethodDescriptor>();
1026       mapDescriptorToSetDependents.put(callee, deps);
1027     }
1028     return deps;
1029   }
1030
1031   private NTuple<Descriptor> computePath(TempDescriptor td) {
1032     // generate proper path fot input td
1033     // if td is local variable, it just generate one element tuple path
1034     if (mapHeapPath.containsKey(td)) {
1035       return mapHeapPath.get(td);
1036     } else {
1037       NTuple<Descriptor> path = new NTuple<Descriptor>();
1038       path.add(td);
1039       return path;
1040     }
1041   }
1042
1043 }