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
  10 import Analysis.CallGraph.CallGraph;
  11 import Analysis.Loops.LoopFinder;
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14 import IR.MethodDescriptor;
  15 import IR.Operation;
  16 import IR.State;
  17 import IR.TypeDescriptor;
  18 import IR.Flat.FKind;
  19 import IR.Flat.FlatCall;
  20 import IR.Flat.FlatFieldNode;
  21 import IR.Flat.FlatLiteralNode;
  22 import IR.Flat.FlatMethod;
  23 import IR.Flat.FlatNode;
  24 import IR.Flat.FlatOpNode;
  25 import IR.Flat.FlatSetFieldNode;
  26 import IR.Flat.TempDescriptor;
  27 import Util.Pair;
  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<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToCompleteClearingSummary;
  67
  68   // maps a method descriptor to the merged incoming caller's current
  69   // overwritten status
  70   private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>> mapMethodDescriptorToInitialClearingSummary;
  71
  72   // maps a flat node to current partial results
  73   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>> mapFlatNodeToClearingSummary;
  74
  75   // maps shared location to the set of descriptors which belong to the shared
  76   // location
  77   private Hashtable<Pair<NTuple<Descriptor>, Location>, Set<Descriptor>> mapSharedLocation2DescriptorSet;
  78
  79   // data structure for merging current state
  80   private Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLocation2Flag;
  81
  82   private FlatNode ssjavaLoopEntrance;
  83   private LoopFinder ssjavaLoop;
  84   private Set<FlatNode> loopIncElements;
  85
  86   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  87   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  88
  89   private TempDescriptor LOCAL;
  90
  91   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  92     this.state = state;
  93     this.ssjava = ssjava;
  94     this.callGraph = ssjava.getCallGraph();
  95     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
  96     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
  97     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
  98     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  99     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 100     this.definitelyWrittenResults =
 101         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
 102     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 103     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
 104
 105     this.mapMethodDescriptorToCompleteClearingSummary =
 106         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 107     this.mapMethodDescriptorToInitialClearingSummary =
 108         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 109     this.mapFlatNodeToClearingSummary =
 110         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, SharedLocState>>();
 111     this.mapSharedLocation2DescriptorSet =
 112         new Hashtable<Pair<NTuple<Descriptor>, Location>, Set<Descriptor>>();
 113     this.mapHeapPathLocation2Flag = new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
 114     this.LOCAL = new TempDescriptor("LOCAL");
 115   }
 116
 117   public void definitelyWrittenCheck() {
 118     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 119       methodReadOverWriteAnalysis();
 120       writtenAnalyis();
 121       sharedLocationAnalysis();
 122       checkSharedLocationResult();
 123     }
 124   }
 125
 126   private void checkSharedLocationResult() {
 127
 128     Hashtable<NTuple<Descriptor>, SharedLocState> result =
 129         mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance);
 130     System.out.println("checkSharedLocationResult=" + result);
 131     Set<NTuple<Descriptor>> hpKeySet = result.keySet();
 132     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 133       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 134       SharedLocState state = result.get(hpKey);
 135       Set<Location> locKeySet = state.getLocationSet();
 136       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 137         Location locKey = (Location) iterator2.next();
 138         if (!state.getFlag(locKey)) {
 139           throw new Error(
 140               "Some concrete locations of the shared abstract location are not cleared at the same time.");
 141         }
 142       }
 143     }
 144
 145   }
 146
 147   private void sharedLocationAnalysis() {
 148     // verify that all concrete locations of shared location are cleared out at
 149     // the same time once per the out-most loop
 150
 151     computeReadSharedDescriptorSet();
 152
 153     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 154     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 155
 156     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 157
 158     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 159     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 160     methodDescriptorToVistSet.addAll(sortedDescriptors);
 161
 162     while (!sortedDescriptors.isEmpty()) {
 163       MethodDescriptor md = sortedDescriptors.removeLast();
 164       methodDescriptorsToVisitStack.add(md);
 165     }
 166
 167     // analyze scheduled methods until there are no more to visit
 168     while (!methodDescriptorsToVisitStack.isEmpty()) {
 169       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 170       FlatMethod fm = state.getMethodFlat(md);
 171
 172       sharedLocation_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
 173
 174       if (true) {
 175
 176         // results for callee changed, so enqueue dependents caller for
 177         // further analysis
 178         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 179         while (depsItr.hasNext()) {
 180           MethodDescriptor methodNext = depsItr.next();
 181           if (!methodDescriptorsToVisitStack.contains(methodNext)
 182               && methodDescriptorToVistSet.contains(methodNext)) {
 183             methodDescriptorsToVisitStack.add(methodNext);
 184           }
 185
 186         }
 187
 188       }
 189
 190     }
 191
 192     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 193     flatNodesToVisit.add(ssjavaLoopEntrance);
 194
 195   }
 196
 197   private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
 198
 199     if (state.SSJAVADEBUG) {
 200       System.out.println("Definitely written for shared locations Analyzing: " + fm + " "
 201           + onlyVisitSSJavaLoop);
 202     }
 203
 204     // intraprocedural analysis
 205     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 206
 207     if (onlyVisitSSJavaLoop) {
 208       flatNodesToVisit.add(ssjavaLoopEntrance);
 209     } else {
 210       flatNodesToVisit.add(fm);
 211     }
 212
 213     while (!flatNodesToVisit.isEmpty()) {
 214       FlatNode fn = flatNodesToVisit.iterator().next();
 215       flatNodesToVisit.remove(fn);
 216
 217       Hashtable<NTuple<Descriptor>, SharedLocState> curr =
 218           new Hashtable<NTuple<Descriptor>, SharedLocState>();
 219
 220       mapHeapPathLocation2Flag.clear();
 221       for (int i = 0; i < fn.numPrev(); i++) {
 222         FlatNode prevFn = fn.getPrev(i);
 223         Hashtable<NTuple<Descriptor>, SharedLocState> in = mapFlatNodeToClearingSummary.get(prevFn);
 224         if (in != null) {
 225           mergeSharedAnaylsis(curr, in);
 226         }
 227       }
 228       // merge flag status
 229       Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 230       for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 231         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 232         SharedLocState currState = curr.get(hpKey);
 233         Set<Location> locKeySet = currState.getMap().keySet();
 234         for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 235           Location locKey = (Location) iterator2.next();
 236           Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
 237           boolean currentFlag = pair.getSecond().booleanValue();
 238           Boolean inFlag = mapHeapPathLocation2Flag.get(new Pair(hpKey, locKey));
 239           boolean newFlag = currentFlag | inFlag.booleanValue();
 240           if (currentFlag != newFlag) {
 241             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
 242           }
 243         }
 244       }
 245
 246       sharedLocation_nodeActions(fn, curr, onlyVisitSSJavaLoop);
 247
 248       Hashtable<NTuple<Descriptor>, SharedLocState> clearingPrev =
 249           mapFlatNodeToClearingSummary.get(fn);
 250
 251       if (!curr.equals(clearingPrev)) {
 252         mapFlatNodeToClearingSummary.put(fn, curr);
 253
 254         for (int i = 0; i < fn.numNext(); i++) {
 255           FlatNode nn = fn.getNext(i);
 256
 257           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 258             flatNodesToVisit.add(nn);
 259           }
 260
 261         }
 262       }
 263
 264     }
 265
 266   }
 267
 268   private void sharedLocation_nodeActions(FlatNode fn,
 269       Hashtable<NTuple<Descriptor>, SharedLocState> curr, boolean isSSJavaLoop) {
 270
 271     TempDescriptor lhs;
 272     TempDescriptor rhs;
 273     FieldDescriptor fld;
 274     switch (fn.kind()) {
 275
 276     case FKind.FlatOpNode: {
 277       FlatOpNode fon = (FlatOpNode) fn;
 278       lhs = fon.getDest();
 279       rhs = fon.getLeft();
 280
 281       if (fon.getOp().getOp() == Operation.ASSIGN) {
 282         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 283           // in ssjavaloop, we need to take care about reading local variables!
 284           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 285           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 286           rhsHeapPath.add(LOCAL);
 287           lhsHeapPath.add(LOCAL);
 288           if (!lhs.getSymbol().startsWith("neverused")) {
 289             readLocation(curr, rhsHeapPath, rhs);
 290             writeLocation(curr, lhsHeapPath, lhs);
 291           }
 292         }
 293       }
 294
 295     }
 296       break;
 297
 298     case FKind.FlatFieldNode:
 299     case FKind.FlatElementNode: {
 300
 301       FlatFieldNode ffn = (FlatFieldNode) fn;
 302       lhs = ffn.getDst();
 303       rhs = ffn.getSrc();
 304       fld = ffn.getField();
 305
 306       // read field
 307       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 308       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 309
 310       if (fld.getType().isImmutable()) {
 311         readLocation(curr, fldHeapPath, fld);
 312       }
 313
 314     }
 315       break;
 316
 317     case FKind.FlatSetFieldNode:
 318     case FKind.FlatSetElementNode: {
 319
 320       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 321       lhs = fsfn.getDst();
 322       fld = fsfn.getField();
 323
 324       // write(field)
 325       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 326       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 327
 328       if (fld.getType().isImmutable()) {
 329         writeLocation(curr, fldHeapPath, fld);
 330       }
 331
 332     }
 333       break;
 334
 335     case FKind.FlatCall: {
 336
 337     }
 338       break;
 339     }
 340
 341   }
 342
 343   private void computeReadSharedDescriptorSet() {
 344     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 345     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 346
 347     for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
 348       MethodDescriptor md = (MethodDescriptor) iterator.next();
 349       FlatMethod fm = state.getMethodFlat(md);
 350       computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
 351     }
 352
 353   }
 354
 355   private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
 356       boolean onlyVisitSSJavaLoop) {
 357
 358     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 359     Set<FlatNode> visited = new HashSet<FlatNode>();
 360
 361     if (onlyVisitSSJavaLoop) {
 362       flatNodesToVisit.add(ssjavaLoopEntrance);
 363     } else {
 364       flatNodesToVisit.add(fm);
 365     }
 366
 367     while (!flatNodesToVisit.isEmpty()) {
 368       FlatNode fn = flatNodesToVisit.iterator().next();
 369       flatNodesToVisit.remove(fn);
 370       visited.add(fn);
 371
 372       computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
 373
 374       for (int i = 0; i < fn.numNext(); i++) {
 375         FlatNode nn = fn.getNext(i);
 376         if (!visited.contains(nn)) {
 377           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 378             flatNodesToVisit.add(nn);
 379           }
 380         }
 381       }
 382
 383     }
 384
 385   }
 386
 387   private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
 388
 389     TempDescriptor lhs;
 390     TempDescriptor rhs;
 391     FieldDescriptor fld;
 392
 393     switch (fn.kind()) {
 394     case FKind.FlatOpNode: {
 395       FlatOpNode fon = (FlatOpNode) fn;
 396       lhs = fon.getDest();
 397       rhs = fon.getLeft();
 398
 399       if (fon.getOp().getOp() == Operation.ASSIGN) {
 400         if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
 401           // in ssjavaloop, we need to take care about reading local variables!
 402           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 403           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 404           rhsHeapPath.add(LOCAL);
 405           addReadDescriptor(rhsHeapPath, rhs);
 406         }
 407       }
 408
 409     }
 410       break;
 411
 412     case FKind.FlatFieldNode:
 413     case FKind.FlatElementNode: {
 414
 415       FlatFieldNode ffn = (FlatFieldNode) fn;
 416       lhs = ffn.getDst();
 417       rhs = ffn.getSrc();
 418       fld = ffn.getField();
 419
 420       // read field
 421       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 422       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 423       // fldHeapPath.add(fld);
 424
 425       if (fld.getType().isImmutable()) {
 426         addReadDescriptor(fldHeapPath, fld);
 427       }
 428
 429       // propagate rhs's heap path to the lhs
 430       mapHeapPath.put(lhs, fldHeapPath);
 431
 432     }
 433       break;
 434
 435     case FKind.FlatSetFieldNode:
 436     case FKind.FlatSetElementNode: {
 437
 438       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 439       lhs = fsfn.getDst();
 440       fld = fsfn.getField();
 441
 442       // write(field)
 443       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 444       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 445       // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 446
 447     }
 448       break;
 449
 450     }
 451   }
 452
 453   private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
 454
 455     Location loc = getLocation(d);
 456
 457     if (loc != null && ssjava.isSharedLocation(loc)) {
 458
 459       Pair key = new Pair(hp, loc);
 460       Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(key);
 461       if (set == null) {
 462         set = new HashSet<Descriptor>();
 463         mapSharedLocation2DescriptorSet.put(key, set);
 464       }
 465       set.add(d);
 466     }
 467
 468   }
 469
 470   private Location getLocation(Descriptor d) {
 471
 472     if (d instanceof FieldDescriptor) {
 473       return (Location) ((FieldDescriptor) d).getType().getExtension();
 474     } else {
 475       assert d instanceof TempDescriptor;
 476       CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
 477       if (comp == null) {
 478         return null;
 479       } else {
 480         return comp.get(comp.getSize() - 1);
 481       }
 482     }
 483
 484   }
 485
 486   private void writeLocation(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 487       NTuple<Descriptor> hp, Descriptor d) {
 488     Location loc = getLocation(d);
 489     if (loc != null && ssjava.isSharedLocation(loc)) {
 490       SharedLocState state = getState(curr, hp);
 491       state.addVar(loc, d);
 492
 493       // if the set v contains all of variables belonging to the shared
 494       // location, set flag to true
 495
 496       Set<Descriptor> sharedVarSet =
 497           mapSharedLocation2DescriptorSet.get(new Pair<NTuple<Descriptor>, Location>(hp, loc));
 498
 499       if (state.getVarSet(loc).containsAll(sharedVarSet)) {
 500         state.updateFlag(loc, true);
 501       }
 502     }
 503   }
 504
 505   private void readLocation(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 506       NTuple<Descriptor> hp, Descriptor d) {
 507     // remove reading var x from written set
 508     Location loc = getLocation(d);
 509     if (loc != null && ssjava.isSharedLocation(loc)) {
 510       SharedLocState state = getState(curr, hp);
 511       state.removeVar(loc, d);
 512     }
 513   }
 514
 515   private SharedLocState getState(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
 516       NTuple<Descriptor> hp) {
 517     SharedLocState state = curr.get(hp);
 518     if (state == null) {
 519       state = new SharedLocState();
 520       curr.put(hp, state);
 521     }
 522     return state;
 523   }
 524
 525   private void writtenAnalyis() {
 526     // perform second stage analysis: intraprocedural analysis ensure that
 527     // all
 528     // variables are definitely written in-between the same read
 529
 530     // First, identify ssjava loop entrace
 531     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 532     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 533     flatNodesToVisit.add(fm);
 534
 535     LoopFinder loopFinder = new LoopFinder(fm);
 536
 537     while (!flatNodesToVisit.isEmpty()) {
 538       FlatNode fn = flatNodesToVisit.iterator().next();
 539       flatNodesToVisit.remove(fn);
 540
 541       String label = (String) state.fn2labelMap.get(fn);
 542       if (label != null) {
 543
 544         if (label.equals(ssjava.SSJAVA)) {
 545           ssjavaLoopEntrance = fn;
 546           break;
 547         }
 548       }
 549
 550       for (int i = 0; i < fn.numNext(); i++) {
 551         FlatNode nn = fn.getNext(i);
 552         flatNodesToVisit.add(nn);
 553       }
 554     }
 555
 556     assert ssjavaLoopEntrance != null;
 557
 558     // assume that ssjava loop is top-level loop in method, not nested loop
 559     Set nestedLoop = loopFinder.nestedLoops();
 560     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 561       LoopFinder lf = (LoopFinder) loopIter.next();
 562       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 563         ssjavaLoop = lf;
 564       }
 565     }
 566
 567     assert ssjavaLoop != null;
 568
 569     writtenAnalysis_analyzeLoop();
 570
 571   }
 572
 573   private void writtenAnalysis_analyzeLoop() {
 574
 575     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 576     flatNodesToVisit.add(ssjavaLoopEntrance);
 577
 578     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 579
 580     while (!flatNodesToVisit.isEmpty()) {
 581       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 582       flatNodesToVisit.remove(fn);
 583
 584       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 585           definitelyWrittenResults.get(fn);
 586
 587       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 588           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 589       for (int i = 0; i < fn.numPrev(); i++) {
 590         FlatNode nn = fn.getPrev(i);
 591         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 592             definitelyWrittenResults.get(nn);
 593         if (dwIn != null) {
 594           merge(curr, dwIn);
 595         }
 596       }
 597
 598       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 599
 600       // if a new result, schedule forward nodes for analysis
 601       if (!curr.equals(prev)) {
 602         definitelyWrittenResults.put(fn, curr);
 603
 604         for (int i = 0; i < fn.numNext(); i++) {
 605           FlatNode nn = fn.getNext(i);
 606           if (loopIncElements.contains(nn)) {
 607             flatNodesToVisit.add(nn);
 608           }
 609
 610         }
 611       }
 612     }
 613   }
 614
 615   private void writtenAnalysis_nodeAction(FlatNode fn,
 616       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 617
 618     if (fn.equals(loopEntrance)) {
 619       // it reaches loop entrance: changes all flag to true
 620       Set<NTuple<Descriptor>> keySet = curr.keySet();
 621       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 622         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 623         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 624         if (pair != null) {
 625           Set<FlatNode> pairKeySet = pair.keySet();
 626           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 627             FlatNode pairKey = (FlatNode) iterator2.next();
 628             pair.put(pairKey, Boolean.TRUE);
 629           }
 630         }
 631       }
 632     } else {
 633       TempDescriptor lhs;
 634       TempDescriptor rhs;
 635       FieldDescriptor fld;
 636
 637       switch (fn.kind()) {
 638       case FKind.FlatOpNode: {
 639         FlatOpNode fon = (FlatOpNode) fn;
 640         lhs = fon.getDest();
 641         rhs = fon.getLeft();
 642
 643         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 644         if (!rhs.getType().isImmutable()) {
 645           mapHeapPath.put(lhs, rhsHeapPath);
 646         } else {
 647           if (fon.getOp().getOp() == Operation.ASSIGN) {
 648             // read(rhs)
 649             readValue(fn, rhsHeapPath, curr);
 650           }
 651           // write(lhs)
 652           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 653           removeHeapPath(curr, lhsHeapPath);
 654         }
 655       }
 656         break;
 657
 658       case FKind.FlatLiteralNode: {
 659         FlatLiteralNode fln = (FlatLiteralNode) fn;
 660         lhs = fln.getDst();
 661
 662         // write(lhs)
 663         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 664         removeHeapPath(curr, lhsHeapPath);
 665
 666       }
 667         break;
 668
 669       case FKind.FlatFieldNode:
 670       case FKind.FlatElementNode: {
 671
 672         FlatFieldNode ffn = (FlatFieldNode) fn;
 673         lhs = ffn.getDst();
 674         rhs = ffn.getSrc();
 675         fld = ffn.getField();
 676
 677         // read field
 678         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 679         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 680         fldHeapPath.add(fld);
 681
 682         if (fld.getType().isImmutable()) {
 683           readValue(fn, fldHeapPath, curr);
 684         }
 685
 686         // propagate rhs's heap path to the lhs
 687         mapHeapPath.put(lhs, fldHeapPath);
 688
 689       }
 690         break;
 691
 692       case FKind.FlatSetFieldNode:
 693       case FKind.FlatSetElementNode: {
 694
 695         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 696         lhs = fsfn.getDst();
 697         fld = fsfn.getField();
 698
 699         // write(field)
 700         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 701         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 702         fldHeapPath.add(fld);
 703         removeHeapPath(curr, fldHeapPath);
 704
 705       }
 706         break;
 707
 708       case FKind.FlatCall: {
 709         FlatCall fc = (FlatCall) fn;
 710         bindHeapPathCallerArgWithCaleeParam(fc);
 711
 712         // add <hp,statement,false> in which hp is an element of
 713         // READ_bound set
 714         // of callee: callee has 'read' requirement!
 715         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 716           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 717
 718           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 719           if (gen == null) {
 720             gen = new Hashtable<FlatNode, Boolean>();
 721             curr.put(read, gen);
 722           }
 723           Boolean currentStatus = gen.get(fn);
 724           if (currentStatus == null) {
 725             gen.put(fn, Boolean.FALSE);
 726           } else {
 727             checkFlag(currentStatus.booleanValue(), fn, read);
 728           }
 729         }
 730
 731         // removes <hp,statement,flag> if hp is an element of
 732         // OVERWRITE_bound
 733         // set of callee. it means that callee will overwrite it
 734         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 735           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 736           removeHeapPath(curr, write);
 737         }
 738       }
 739         break;
 740
 741       }
 742     }
 743
 744   }
 745
 746   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 747       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 748     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 749     if (gen == null) {
 750       gen = new Hashtable<FlatNode, Boolean>();
 751       curr.put(hp, gen);
 752     }
 753     Boolean currentStatus = gen.get(fn);
 754     if (currentStatus == null) {
 755       gen.put(fn, Boolean.FALSE);
 756     } else {
 757       checkFlag(currentStatus.booleanValue(), fn, hp);
 758     }
 759
 760   }
 761
 762   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 763       NTuple<Descriptor> hp) {
 764
 765     // removes all of heap path that starts with prefix 'hp'
 766     // since any reference overwrite along heap path gives overwriting side
 767     // effects on the value
 768
 769     Set<NTuple<Descriptor>> keySet = curr.keySet();
 770     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 771       NTuple<Descriptor> key = iter.next();
 772       if (key.startsWith(hp)) {
 773         curr.put(key, new Hashtable<FlatNode, Boolean>());
 774       }
 775     }
 776
 777   }
 778
 779   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
 780     // compute all possible callee set
 781     // transform all READ/OVERWRITE set from the any possible
 782     // callees to the
 783     // caller
 784
 785     calleeUnionBoundReadSet.clear();
 786     calleeIntersectBoundOverWriteSet.clear();
 787
 788     MethodDescriptor mdCallee = fc.getMethod();
 789     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 790     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 791     TypeDescriptor typeDesc = fc.getThis().getType();
 792     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 793
 794     // create mapping from arg idx to its heap paths
 795     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 796         new Hashtable<Integer, NTuple<Descriptor>>();
 797
 798     // arg idx is starting from 'this' arg
 799     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 800     if (thisHeapPath == null) {
 801       // method is called without creating new flat node representing 'this'
 802       thisHeapPath = new NTuple<Descriptor>();
 803       thisHeapPath.add(fc.getThis());
 804     }
 805
 806     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 807
 808     for (int i = 0; i < fc.numArgs(); i++) {
 809       TempDescriptor arg = fc.getArg(i);
 810       NTuple<Descriptor> argHeapPath = computePath(arg);
 811       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 812     }
 813
 814     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 815       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 816       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
 817
 818       // binding caller's args and callee's params
 819
 820       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
 821       if (calleeReadSet == null) {
 822         calleeReadSet = new HashSet<NTuple<Descriptor>>();
 823         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
 824       }
 825       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
 826       if (calleeOverWriteSet == null) {
 827         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
 828         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
 829       }
 830
 831       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 832           new Hashtable<Integer, TempDescriptor>();
 833       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 834         TempDescriptor param = calleeFlatMethod.getParameter(i);
 835         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 836       }
 837
 838       Set<NTuple<Descriptor>> calleeBoundReadSet =
 839           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 840       // union of the current read set and the current callee's
 841       // read set
 842       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
 843       Set<NTuple<Descriptor>> calleeBoundWriteSet =
 844           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 845       // intersection of the current overwrite set and the current
 846       // callee's
 847       // overwrite set
 848       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
 849     }
 850
 851   }
 852
 853   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
 854     if (booleanValue) {
 855       throw new Error(
 856           "There is a variable, which is reachable through references "
 857               + hp
 858               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
 859               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
 860               + fn.getNumLine());
 861     }
 862   }
 863
 864   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 865       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
 866
 867     Set<NTuple<Descriptor>> inKeySet = in.keySet();
 868     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
 869       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
 870       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 871
 872       Set<FlatNode> pairKeySet = inPair.keySet();
 873       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 874         FlatNode pairKey = (FlatNode) iterator2.next();
 875         Boolean inFlag = inPair.get(pairKey);
 876
 877         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 878         if (currPair == null) {
 879           currPair = new Hashtable<FlatNode, Boolean>();
 880           curr.put(inKey, currPair);
 881         }
 882
 883         Boolean currFlag = currPair.get(pairKey);
 884         // by default, flag is set by false
 885         if (currFlag == null) {
 886           currFlag = Boolean.FALSE;
 887         }
 888         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 889         currPair.put(pairKey, currFlag);
 890       }
 891
 892     }
 893
 894   }
 895
 896   private void methodReadOverWriteAnalysis() {
 897     // perform method READ/OVERWRITE analysis
 898     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 899     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 900
 901     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 902
 903     // no need to analyze method having ssjava loop
 904     methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
 905
 906     // current descriptors to visit in fixed-point interprocedural analysis,
 907     // prioritized by
 908     // dependency in the call graph
 909     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 910
 911     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 912     methodDescriptorToVistSet.addAll(sortedDescriptors);
 913
 914     while (!sortedDescriptors.isEmpty()) {
 915       MethodDescriptor md = sortedDescriptors.removeFirst();
 916       methodDescriptorsToVisitStack.add(md);
 917     }
 918
 919     // analyze scheduled methods until there are no more to visit
 920     while (!methodDescriptorsToVisitStack.isEmpty()) {
 921       // start to analyze leaf node
 922       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 923       FlatMethod fm = state.getMethodFlat(md);
 924
 925       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
 926       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
 927
 928       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
 929
 930       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
 931       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
 932
 933       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
 934         mapFlatMethodToRead.put(fm, readSet);
 935         mapFlatMethodToOverWrite.put(fm, overWriteSet);
 936
 937         // results for callee changed, so enqueue dependents caller for
 938         // further
 939         // analysis
 940         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 941         while (depsItr.hasNext()) {
 942           MethodDescriptor methodNext = depsItr.next();
 943           if (!methodDescriptorsToVisitStack.contains(methodNext)
 944               && methodDescriptorToVistSet.contains(methodNext)) {
 945             methodDescriptorsToVisitStack.add(methodNext);
 946           }
 947
 948         }
 949
 950       }
 951
 952     }
 953
 954   }
 955
 956   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
 957       Set<NTuple<Descriptor>> overWriteSet) {
 958     if (state.SSJAVADEBUG) {
 959       System.out.println("Definitely written Analyzing: " + fm);
 960     }
 961
 962     // intraprocedural analysis
 963     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 964     flatNodesToVisit.add(fm);
 965
 966     while (!flatNodesToVisit.isEmpty()) {
 967       FlatNode fn = flatNodesToVisit.iterator().next();
 968       flatNodesToVisit.remove(fn);
 969
 970       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
 971
 972       for (int i = 0; i < fn.numPrev(); i++) {
 973         FlatNode prevFn = fn.getPrev(i);
 974         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
 975         if (in != null) {
 976           merge(curr, in);
 977         }
 978       }
 979
 980       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
 981
 982       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
 983       if (!curr.equals(writtenSetPrev)) {
 984         mapFlatNodeToWrittenSet.put(fn, curr);
 985         for (int i = 0; i < fn.numNext(); i++) {
 986           FlatNode nn = fn.getNext(i);
 987           flatNodesToVisit.add(nn);
 988         }
 989       }
 990
 991     }
 992
 993   }
 994
 995   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
 996       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
 997     TempDescriptor lhs;
 998     TempDescriptor rhs;
 999     FieldDescriptor fld;
1000
1001     switch (fn.kind()) {
1002     case FKind.FlatMethod: {
1003
1004       // set up initial heap paths for method parameters
1005       FlatMethod fm = (FlatMethod) fn;
1006       for (int i = 0; i < fm.numParameters(); i++) {
1007         TempDescriptor param = fm.getParameter(i);
1008         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1009         heapPath.add(param);
1010         mapHeapPath.put(param, heapPath);
1011       }
1012     }
1013       break;
1014
1015     case FKind.FlatOpNode: {
1016       FlatOpNode fon = (FlatOpNode) fn;
1017       // for a normal assign node, need to propagate lhs's heap path to
1018       // rhs
1019       if (fon.getOp().getOp() == Operation.ASSIGN) {
1020         rhs = fon.getLeft();
1021         lhs = fon.getDest();
1022
1023         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1024         if (rhsHeapPath != null) {
1025           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1026         }
1027
1028       }
1029     }
1030       break;
1031
1032     case FKind.FlatFieldNode:
1033     case FKind.FlatElementNode: {
1034
1035       // y=x.f;
1036
1037       FlatFieldNode ffn = (FlatFieldNode) fn;
1038       lhs = ffn.getDst();
1039       rhs = ffn.getSrc();
1040       fld = ffn.getField();
1041
1042       // set up heap path
1043       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1044       if (srcHeapPath != null) {
1045         // if lhs srcHeapPath is null, it means that it is not reachable from
1046         // callee's parameters. so just ignore it
1047
1048         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1049         readingHeapPath.add(fld);
1050         mapHeapPath.put(lhs, readingHeapPath);
1051
1052         // read (x.f)
1053         if (fld.getType().isImmutable()) {
1054           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1055           if (!writtenSet.contains(readingHeapPath)) {
1056             readSet.add(readingHeapPath);
1057           }
1058         }
1059
1060         // need to kill hp(x.f) from WT
1061         writtenSet.remove(readingHeapPath);
1062       }
1063
1064     }
1065       break;
1066
1067     case FKind.FlatSetFieldNode:
1068     case FKind.FlatSetElementNode: {
1069
1070       // x.f=y;
1071       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1072       lhs = fsfn.getDst();
1073       fld = fsfn.getField();
1074       rhs = fsfn.getSrc();
1075
1076       // set up heap path
1077       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1078       if (lhsHeapPath != null) {
1079         // if lhs heap path is null, it means that it is not reachable from
1080         // callee's parameters. so just ignore it
1081         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1082         newHeapPath.add(fld);
1083         mapHeapPath.put(fld, newHeapPath);
1084
1085         // write(x.f)
1086         // need to add hp(y) to WT
1087         writtenSet.add(newHeapPath);
1088       }
1089
1090     }
1091       break;
1092
1093     case FKind.FlatCall: {
1094
1095       FlatCall fc = (FlatCall) fn;
1096
1097       bindHeapPathCallerArgWithCaleeParam(fc);
1098
1099       // add heap path, which is an element of READ_bound set and is not
1100       // an
1101       // element of WT set, to the caller's READ set
1102       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1103         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1104         if (!writtenSet.contains(read)) {
1105           readSet.add(read);
1106         }
1107       }
1108       writtenSet.removeAll(calleeUnionBoundReadSet);
1109
1110       // add heap path, which is an element of OVERWRITE_bound set, to the
1111       // caller's WT set
1112       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1113         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1114         writtenSet.add(write);
1115       }
1116
1117     }
1118       break;
1119
1120     case FKind.FlatExit: {
1121       // merge the current written set with OVERWRITE set
1122       merge(overWriteSet, writtenSet);
1123     }
1124       break;
1125
1126     }
1127
1128   }
1129
1130   private void mergeSharedAnaylsis(Hashtable<NTuple<Descriptor>, SharedLocState> curr,
1131       Hashtable<NTuple<Descriptor>, SharedLocState> in) {
1132
1133     Set<NTuple<Descriptor>> keySet = in.keySet();
1134     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1135       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1136       SharedLocState inState = in.get(hpKey);
1137
1138       SharedLocState currState = curr.get(hpKey);
1139       if (currState == null) {
1140         currState = new SharedLocState();
1141         curr.put(hpKey, currState);
1142       }
1143       currState.merge(inState);
1144
1145       Set<Location> locSet = inState.getMap().keySet();
1146       for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1147         Location loc = (Location) iterator2.next();
1148         Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1149         boolean inFlag = pair.getSecond().booleanValue();
1150
1151         Pair<NTuple<Descriptor>, Location> flagKey =
1152             new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1153         Boolean current = mapHeapPathLocation2Flag.get(flagKey);
1154         if (current == null) {
1155           current = new Boolean(true);
1156         }
1157         boolean newInFlag = current.booleanValue() & inFlag;
1158         mapHeapPathLocation2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1159       }
1160
1161     }
1162
1163   }
1164
1165   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1166     if (curr.isEmpty()) {
1167       // WrittenSet has a special initial value which covers all possible
1168       // elements
1169       // For the first time of intersection, we can take all previous set
1170       curr.addAll(in);
1171     } else {
1172       // otherwise, current set is the intersection of the two sets
1173       curr.retainAll(in);
1174     }
1175
1176   }
1177
1178   // combine two heap path
1179   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1180     NTuple<Descriptor> combined = new NTuple<Descriptor>();
1181
1182     for (int i = 0; i < callerIn.size(); i++) {
1183       combined.add(callerIn.get(i));
1184     }
1185
1186     // the first element of callee's heap path represents parameter
1187     // so we skip the first one since it is already added from caller's heap
1188     // path
1189     for (int i = 1; i < calleeIn.size(); i++) {
1190       combined.add(calleeIn.get(i));
1191     }
1192
1193     return combined;
1194   }
1195
1196   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1197       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1198       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1199
1200     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1201
1202     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1203     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1204       Integer idx = (Integer) iterator.next();
1205
1206       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1207       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1208
1209       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1210         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1211         if (element.startsWith(calleeParam)) {
1212           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1213           boundedCalleeSet.add(boundElement);
1214         }
1215
1216       }
1217
1218     }
1219     return boundedCalleeSet;
1220
1221   }
1222
1223   // Borrowed it from disjoint analysis
1224   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1225
1226     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1227
1228     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1229
1230     Iterator<MethodDescriptor> itr = toSort.iterator();
1231     while (itr.hasNext()) {
1232       MethodDescriptor d = itr.next();
1233
1234       if (!discovered.contains(d)) {
1235         dfsVisit(d, toSort, sorted, discovered);
1236       }
1237     }
1238
1239     return sorted;
1240   }
1241
1242   // While we're doing DFS on call graph, remember
1243   // dependencies for efficient queuing of methods
1244   // during interprocedural analysis:
1245   //
1246   // a dependent of a method decriptor d for this analysis is:
1247   // 1) a method or task that invokes d
1248   // 2) in the descriptorsToAnalyze set
1249   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1250       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1251
1252     discovered.add(md);
1253
1254     // otherwise call graph guides DFS
1255     Iterator itr = callGraph.getCallerSet(md).iterator();
1256     while (itr.hasNext()) {
1257       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1258
1259       // only consider callers in the original set to analyze
1260       if (!toSort.contains(dCaller)) {
1261         continue;
1262       }
1263
1264       if (!discovered.contains(dCaller)) {
1265         addDependent(md, // callee
1266             dCaller // caller
1267         );
1268
1269         dfsVisit(dCaller, toSort, sorted, discovered);
1270       }
1271     }
1272
1273     // for leaf-nodes last now!
1274     sorted.addLast(md);
1275   }
1276
1277   // a dependent of a method decriptor d for this analysis is:
1278   // 1) a method or task that invokes d
1279   // 2) in the descriptorsToAnalyze set
1280   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1281     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1282     if (deps == null) {
1283       deps = new HashSet<MethodDescriptor>();
1284     }
1285     deps.add(caller);
1286     mapDescriptorToSetDependents.put(callee, deps);
1287   }
1288
1289   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1290     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1291     if (deps == null) {
1292       deps = new HashSet<MethodDescriptor>();
1293       mapDescriptorToSetDependents.put(callee, deps);
1294     }
1295     return deps;
1296   }
1297
1298   private NTuple<Descriptor> computePath(TempDescriptor td) {
1299     // generate proper path fot input td
1300     // if td is local variable, it just generate one element tuple path
1301     if (mapHeapPath.containsKey(td)) {
1302       return mapHeapPath.get(td);
1303     } else {
1304       NTuple<Descriptor> path = new NTuple<Descriptor>();
1305       path.add(td);
1306       return path;
1307     }
1308   }
1309
1310 }