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.TypeExtension;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatCall;
  21 import IR.Flat.FlatElementNode;
  22 import IR.Flat.FlatFieldNode;
  23 import IR.Flat.FlatLiteralNode;
  24 import IR.Flat.FlatMethod;
  25 import IR.Flat.FlatNode;
  26 import IR.Flat.FlatOpNode;
  27 import IR.Flat.FlatSetElementNode;
  28 import IR.Flat.FlatSetFieldNode;
  29 import IR.Flat.TempDescriptor;
  30 import IR.Tree.Modifiers;
  31 import Util.Pair;
  32
  33 public class DefinitelyWrittenCheck {
  34
  35   SSJavaAnalysis ssjava;
  36   State state;
  37   CallGraph callGraph;
  38
  39   int debugcount = 0;
  40
  41   // maps a descriptor to its known dependents: namely
  42   // methods or tasks that call the descriptor's method
  43   // AND are part of this analysis (reachable from main)
  44   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  45
  46   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  47   // previously.
  48   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  49
  50   // maps a temp descriptor to its heap path
  51   // each temp descriptor has a unique heap path since we do not allow any
  52   // alias.
  53   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  54
  55   // maps a flat method to the READ that is the set of heap path that is
  56   // expected to be written before method invocation
  57   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  58
  59   // maps a flat method to the OVERWRITE that is the set of heap path that is
  60   // overwritten on every possible path during method invocation
  61   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  62
  63   // maps a flat method to the WRITE that is the set of heap path that is
  64   // written to
  65   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToWrite;
  66
  67   // points to method containing SSJAVA Loop
  68   private MethodDescriptor methodContainingSSJavaLoop;
  69
  70   // maps a flatnode to definitely written analysis mapping M
  71   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  72
  73   // maps a method descriptor to its current summary during the analysis
  74   // then analysis reaches fixed-point, this mapping will have the final summary
  75   // for each method descriptor
  76   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
  77
  78   // maps a method descriptor to the merged incoming caller's current
  79   // overwritten status
  80   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
  81
  82   // maps a flat node to current partial results
  83   private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
  84
  85   private Hashtable<FlatNode, ReadSummary> mapFlatNodeToReadSummary;
  86
  87   // maps shared location to the set of descriptors which belong to the shared
  88   // location
  89
  90   // keep current descriptors to visit in fixed-point interprocedural analysis,
  91   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  92
  93   // when analyzing flatcall, need to re-schedule set of callee
  94   private Set<MethodDescriptor> calleesToEnqueue;
  95
  96   private Set<ReadSummary> possibleCalleeReadSummarySetToCaller;
  97
  98   public static final String arrayElementFieldName = "___element_";
  99   static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
 100
 101   private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
 102
 103   // maps a method descriptor to the merged incoming caller's current
 104   // reading status
 105   // it is for setting clearance flag when all read set is overwritten
 106   private Hashtable<MethodDescriptor, ReadSummary> mapMethodDescriptorToReadSummary;
 107
 108   private LinkedList<MethodDescriptor> sortedDescriptors;
 109
 110   private FlatNode ssjavaLoopEntrance;
 111   private LoopFinder ssjavaLoop;
 112   private Set<FlatNode> loopIncElements;
 113
 114   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
 115   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
 116   private Set<NTuple<Descriptor>> calleeBoundWriteSet;
 117
 118   private Hashtable<Descriptor, Location> mapDescToLocation;
 119
 120   private TempDescriptor LOCAL;
 121
 122   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
 123     this.state = state;
 124     this.ssjava = ssjava;
 125     this.callGraph = ssjava.getCallGraph();
 126     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 127     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 128     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
 129     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 130     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 131     this.mapFlatMethodToWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 132     this.definitelyWrittenResults =
 133         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
 134     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 135     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
 136     this.calleeBoundWriteSet = new HashSet<NTuple<Descriptor>>();
 137
 138     this.mapMethodDescriptorToCompleteClearingSummary =
 139         new Hashtable<MethodDescriptor, ClearingSummary>();
 140     this.mapMethodDescriptorToInitialClearingSummary =
 141         new Hashtable<MethodDescriptor, ClearingSummary>();
 142     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 143     this.calleesToEnqueue = new HashSet<MethodDescriptor>();
 144     this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
 145     this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
 146     this.LOCAL = new TempDescriptor("LOCAL");
 147     this.mapDescToLocation = new Hashtable<Descriptor, Location>();
 148     this.possibleCalleeReadSummarySetToCaller = new HashSet<ReadSummary>();
 149     this.mapMethodDescriptorToReadSummary = new Hashtable<MethodDescriptor, ReadSummary>();
 150     this.mapFlatNodeToReadSummary = new Hashtable<FlatNode, ReadSummary>();
 151   }
 152
 153   public void definitelyWrittenCheck() {
 154     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 155       methodReadOverWriteAnalysis();
 156       writtenAnalyis();
 157       sharedLocationAnalysis();
 158       checkSharedLocationResult();
 159     }
 160   }
 161
 162   private void checkSharedLocationResult() {
 163
 164     // mapping of method containing ssjava loop has the final result of
 165     // shared location analysis
 166
 167     ClearingSummary result =
 168         mapMethodDescriptorToCompleteClearingSummary.get(methodContainingSSJavaLoop);
 169
 170     String str = generateNotClearedResult(result);
 171     if (str.length() > 0) {
 172       throw new Error(
 173           "Following concrete locations of the shared abstract location are not cleared at the same time:\n"
 174               + str);
 175     }
 176
 177   }
 178
 179   private String generateNotClearedResult(ClearingSummary result) {
 180     Set<NTuple<Descriptor>> keySet = result.keySet();
 181
 182     StringBuffer str = new StringBuffer();
 183     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 184       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 185       SharedStatus status = result.get(hpKey);
 186       Hashtable<Location, Pair<Set<Descriptor>, Boolean>> map = status.getMap();
 187       Set<Location> locKeySet = map.keySet();
 188       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 189         Location locKey = (Location) iterator2.next();
 190         if (status.haveWriteEffect(locKey)) {
 191           Pair<Set<Descriptor>, Boolean> pair = map.get(locKey);
 192           if (!pair.getSecond().booleanValue()) {
 193             // not cleared!
 194             str.append("- Concrete locations of the shared location '" + locKey
 195                 + "' are not cleared out, which are reachable through the heap path '" + hpKey
 196                 + ".\n");
 197           }
 198         }
 199       }
 200     }
 201
 202     return str.toString();
 203
 204   }
 205
 206   private void sharedLocationAnalysis() {
 207     // verify that all concrete locations of shared location are cleared out at
 208     // the same time once per the out-most loop
 209
 210     computeReadSharedDescriptorSet();
 211
 212     System.out.println("###");
 213     System.out.println("READ MAP=" + mapMethodDescriptorToReadSummary);
 214
 215     // methodDescriptorsToVisitStack.clear();
 216     // methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 217
 218     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 219         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 220
 221     // current descriptors to visit in fixed-point interprocedural analysis,
 222     // prioritized by
 223     // dependency in the call graph
 224     methodDescriptorsToVisitStack.clear();
 225
 226     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 227     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 228
 229     while (!descriptorListToAnalyze.isEmpty()) {
 230       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 231       methodDescriptorsToVisitStack.add(md);
 232     }
 233
 234     // analyze scheduled methods until there are no more to visit
 235     while (!methodDescriptorsToVisitStack.isEmpty()) {
 236       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 237
 238       ClearingSummary completeSummary =
 239           sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 240
 241       ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
 242
 243       if (!completeSummary.equals(prevCompleteSummary)) {
 244
 245         mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 246
 247         // results for callee changed, so enqueue dependents caller for
 248         // further analysis
 249         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 250         while (depsItr.hasNext()) {
 251           MethodDescriptor methodNext = depsItr.next();
 252           if (!methodDescriptorsToVisitStack.contains(methodNext)) {
 253             methodDescriptorsToVisitStack.add(methodNext);
 254           }
 255         }
 256
 257         // if there is set of callee to be analyzed,
 258         // add this set into the top of stack
 259         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 260         while (calleeIter.hasNext()) {
 261           MethodDescriptor mdNext = calleeIter.next();
 262           if (!methodDescriptorsToVisitStack.contains(mdNext)) {
 263             methodDescriptorsToVisitStack.add(mdNext);
 264           }
 265         }
 266         calleesToEnqueue.clear();
 267
 268       }
 269
 270     }
 271
 272   }
 273
 274   private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
 275       boolean onlyVisitSSJavaLoop) {
 276
 277     if (state.SSJAVADEBUG) {
 278       System.out.println("Definite clearance for shared locations Analyzing: " + md + " "
 279           + onlyVisitSSJavaLoop);
 280     }
 281
 282     FlatMethod fm = state.getMethodFlat(md);
 283
 284     // intraprocedural analysis
 285     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 286
 287     // start a new mapping of partial results for each flat node
 288     mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
 289
 290     if (onlyVisitSSJavaLoop) {
 291       flatNodesToVisit.add(ssjavaLoopEntrance);
 292     } else {
 293       flatNodesToVisit.add(fm);
 294     }
 295
 296     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 297
 298     while (!flatNodesToVisit.isEmpty()) {
 299       FlatNode fn = flatNodesToVisit.iterator().next();
 300       flatNodesToVisit.remove(fn);
 301
 302       ClearingSummary curr = new ClearingSummary();
 303
 304       Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
 305       for (int i = 0; i < fn.numPrev(); i++) {
 306         FlatNode prevFn = fn.getPrev(i);
 307         ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
 308         if (in != null) {
 309           prevSet.add(in);
 310         }
 311       }
 312       mergeSharedLocationAnaylsis(curr, prevSet);
 313
 314       sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 315       ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 316
 317       if (!curr.equals(clearingPrev)) {
 318         mapFlatNodeToClearingSummary.put(fn, curr);
 319
 320         for (int i = 0; i < fn.numNext(); i++) {
 321           FlatNode nn = fn.getNext(i);
 322
 323           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 324             flatNodesToVisit.add(nn);
 325           }
 326
 327         }
 328       }
 329
 330     }
 331
 332     ClearingSummary completeSummary = new ClearingSummary();
 333     Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
 334
 335     if (onlyVisitSSJavaLoop) {
 336       // when analyzing ssjava loop,
 337       // complete summary is merging of all previous nodes of ssjava loop
 338       // entrance
 339       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 340         ClearingSummary frnSummary =
 341             mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
 342         if (frnSummary != null) {
 343           summarySet.add(frnSummary);
 344         }
 345       }
 346     } else {
 347       // merging all exit node summary into the complete summary
 348       if (!returnNodeSet.isEmpty()) {
 349         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 350           FlatNode frn = (FlatNode) iterator.next();
 351           ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
 352           summarySet.add(frnSummary);
 353         }
 354       }
 355     }
 356     mergeSharedLocationAnaylsis(completeSummary, summarySet);
 357
 358     return completeSummary;
 359   }
 360
 361   private void sharedLocation_nodeActions(MethodDescriptor md, FlatNode fn, ClearingSummary curr,
 362       Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 363
 364     TempDescriptor lhs;
 365     TempDescriptor rhs;
 366     FieldDescriptor fld;
 367     switch (fn.kind()) {
 368
 369     case FKind.FlatMethod: {
 370       FlatMethod fm = (FlatMethod) fn;
 371
 372       ClearingSummary summaryFromCaller =
 373           mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
 374
 375       Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 376       if (summaryFromCaller != null) {
 377         inSet.add(summaryFromCaller);
 378         mergeSharedLocationAnaylsis(curr, inSet);
 379       }
 380
 381     }
 382       break;
 383
 384     case FKind.FlatOpNode: {
 385       FlatOpNode fon = (FlatOpNode) fn;
 386       lhs = fon.getDest();
 387       rhs = fon.getLeft();
 388
 389       if (fon.getOp().getOp() == Operation.ASSIGN) {
 390         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 391           // in ssjavaloop, we need to take care about reading local variables!
 392           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 393           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 394           rhsHeapPath.add(LOCAL);
 395           lhsHeapPath.add(LOCAL);
 396           if (!lhs.getSymbol().startsWith("neverused")) {
 397             readLocation(md, curr, rhsHeapPath, getLocation(rhs), rhs);
 398             writeLocation(md, curr, lhsHeapPath, getLocation(lhs), lhs);
 399           }
 400         }
 401       }
 402
 403     }
 404       break;
 405
 406     case FKind.FlatFieldNode:
 407     case FKind.FlatElementNode: {
 408
 409       if (fn.kind() == FKind.FlatFieldNode) {
 410         FlatFieldNode ffn = (FlatFieldNode) fn;
 411         lhs = ffn.getDst();
 412         rhs = ffn.getSrc();
 413         fld = ffn.getField();
 414       } else {
 415         FlatElementNode fen = (FlatElementNode) fn;
 416         lhs = fen.getDst();
 417         rhs = fen.getSrc();
 418         TypeDescriptor td = rhs.getType().dereference();
 419         fld = getArrayField(td);
 420       }
 421
 422       // read field
 423       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 424
 425       if (srcHeapPath != null) {
 426         // if lhs srcHeapPath is null, it means that it is not reachable from
 427         // callee's parameters. so just ignore it
 428         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 429
 430         if (!fld.getType().isArray() && fld.getType().isImmutable()) {
 431           Location loc;
 432           if (fn.kind() == FKind.FlatElementNode) {
 433             // array element read case
 434             NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
 435             for (int i = 0; i < fldHeapPath.size() - 1; i++) {
 436               newHeapPath.add(fldHeapPath.get(i));
 437             }
 438
 439             Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
 440             if (desc instanceof FieldDescriptor) {
 441               fld = (FieldDescriptor) desc;
 442               fldHeapPath = newHeapPath;
 443               loc = getLocation(fld);
 444               readLocation(md, curr, fldHeapPath, loc, fld);
 445             }
 446           } else {
 447             loc = getLocation(fld);
 448             readLocation(md, curr, fldHeapPath, loc, fld);
 449           }
 450         } else {
 451
 452           if (fn.kind() != FKind.FlatElementNode) {
 453             // if it is multi dimensional array, do not need to add heap path
 454             // because all accesses from the same array is represented by
 455             // "_element_"
 456             fldHeapPath.add(fld);
 457           }
 458           mapHeapPath.put(lhs, fldHeapPath);
 459         }
 460
 461       }
 462
 463       // }
 464
 465     }
 466       break;
 467
 468     case FKind.FlatSetFieldNode:
 469     case FKind.FlatSetElementNode: {
 470
 471       if (fn.kind() == FKind.FlatSetFieldNode) {
 472         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 473         lhs = fsfn.getDst();
 474         fld = fsfn.getField();
 475         rhs = fsfn.getSrc();
 476       } else {
 477         FlatSetElementNode fsen = (FlatSetElementNode) fn;
 478         lhs = fsen.getDst();
 479         rhs = fsen.getSrc();
 480         TypeDescriptor td = lhs.getType().dereference();
 481         fld = getArrayField(td);
 482       }
 483
 484       // write(field)
 485       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 486       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 487       if (fld.getType().isImmutable()) {
 488         writeLocation(md, curr, fldHeapPath, getLocation(fld), fld);
 489
 490         Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
 491         if (desc instanceof FieldDescriptor) {
 492           NTuple<Descriptor> arrayPath = new NTuple<Descriptor>();
 493           for (int i = 0; i < fldHeapPath.size() - 1; i++) {
 494             arrayPath.add(fldHeapPath.get(i));
 495           }
 496           SharedStatus state = getState(curr, arrayPath);
 497           state.setWriteEffect(getLocation(desc));
 498         }
 499
 500       } else {
 501         // updates reference field case:
 502         fldHeapPath.add(fld);
 503         updateWriteEffectOnReferenceField(curr, fldHeapPath);
 504       }
 505
 506     }
 507       break;
 508
 509     case FKind.FlatCall: {
 510
 511       FlatCall fc = (FlatCall) fn;
 512
 513       if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
 514         // ssjava util case!
 515         // have write effects on the first argument
 516
 517         if (fc.getArg(0).getType().isArray()) {
 518           // updates reference field case:
 519           // 2. if there exists a tuple t in sharing summary that starts with
 520           // hp(x) then, set flag of tuple t to 'true'
 521           NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
 522
 523           Location loc = getLocation(fc.getArg(0));
 524           NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
 525           for (int i = 0; i < argHeapPath.size() - 1; i++) {
 526             newHeapPath.add(argHeapPath.get(i));
 527           }
 528           fld = (FieldDescriptor) argHeapPath.get(argHeapPath.size() - 1);
 529           argHeapPath = newHeapPath;
 530
 531           writeLocation(md, curr, argHeapPath, loc, fld);
 532         }
 533
 534       } else {
 535         // find out the set of callees
 536         MethodDescriptor mdCallee = fc.getMethod();
 537         FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 538         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 539         setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
 540
 541         possibleCalleeCompleteSummarySetToCaller.clear();
 542
 543         for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 544           MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 545           FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 546
 547           addDependent(mdPossibleCallee, // callee
 548               md); // caller
 549
 550           calleesToEnqueue.add(mdPossibleCallee);
 551
 552           // updates possible callee's initial summary using caller's current
 553           // writing status
 554           ClearingSummary prevCalleeInitSummary =
 555               mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 556
 557           ClearingSummary calleeInitSummary =
 558               bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 559
 560           Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 561           if (prevCalleeInitSummary != null) {
 562             inSet.add(prevCalleeInitSummary);
 563             mergeSharedLocationAnaylsis(calleeInitSummary, inSet);
 564           }
 565
 566           // if changes, update the init summary
 567           // and reschedule the callee for analysis
 568           if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 569
 570             if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
 571               methodDescriptorsToVisitStack.add(mdPossibleCallee);
 572             }
 573
 574             mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 575           }
 576
 577         }
 578
 579         // contribute callee's writing effects to the caller
 580         mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 581
 582       }
 583
 584     }
 585       break;
 586
 587     case FKind.FlatReturnNode: {
 588       returnNodeSet.add(fn);
 589     }
 590       break;
 591
 592     }
 593
 594   }
 595
 596   private void updateWriteEffectOnReferenceField(ClearingSummary curr, NTuple<Descriptor> heapPath) {
 597
 598     // 2. if there exists a tuple t in sharing summary that starts with
 599     // hp(x) then, set flag of tuple t to 'true'
 600     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 601     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 602       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 603       if (hpKey.startsWith(heapPath)) {
 604         curr.get(hpKey).updateFlag(true);
 605       }
 606     }
 607
 608   }
 609
 610   private void bindHeapPathReadSummary(FlatCall fc, FlatMethod calleeFlatMethod, ReadSummary curr) {
 611
 612     ReadSummary boundSet = new ReadSummary();
 613
 614     // create mapping from arg idx to its heap paths
 615     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 616         new Hashtable<Integer, NTuple<Descriptor>>();
 617
 618     if (fc.getThis() != null) {
 619       // arg idx is starting from 'this' arg
 620       NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 621       if (thisHeapPath == null) {
 622         // method is called without creating new flat node representing 'this'
 623         thisHeapPath = new NTuple<Descriptor>();
 624         thisHeapPath.add(fc.getThis());
 625       }
 626
 627       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 628     }
 629
 630     for (int i = 0; i < fc.numArgs(); i++) {
 631       TempDescriptor arg = fc.getArg(i);
 632       NTuple<Descriptor> argHeapPath = computePath(arg);
 633       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 634     }
 635
 636     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 637         new Hashtable<Integer, TempDescriptor>();
 638     int offset = 0;
 639     if (calleeFlatMethod.getMethod().isStatic()) {
 640       // static method does not have implicit 'this' arg
 641       offset = 1;
 642     }
 643     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 644       TempDescriptor param = calleeFlatMethod.getParameter(i);
 645       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
 646     }
 647
 648     // binding caller's read effects to callee's params
 649     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 650       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 651
 652       if (argHeapPath != null) {
 653         // if method is static, the first argument is nulll because static
 654         // method does not have implicit "THIS" arg
 655         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 656
 657         // iterate over caller's writing effect set
 658         Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 659         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 660           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 661           // current element is reachable caller's arg
 662           // so need to bind it to the caller's side and add it to the
 663           // callee's summary
 664           if (hpKey.startsWith(argHeapPath)) {
 665             NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 666             boundSet.put(boundHeapPath, curr.get(hpKey));
 667           }
 668         }
 669       }
 670     }
 671
 672     // merge into callee's previous read set
 673     ReadSummary calleeSummary = mapMethodDescriptorToReadSummary.get(calleeFlatMethod.getMethod());
 674     if (calleeSummary == null) {
 675       calleeSummary = new ReadSummary();
 676       mapMethodDescriptorToReadSummary.put(calleeFlatMethod.getMethod(), calleeSummary);
 677     }
 678     Set<ReadSummary> inSet = new HashSet<ReadSummary>();
 679     inSet.add(boundSet);
 680     mergeReadLocationAnaylsis(calleeSummary, inSet);
 681
 682     // contribute callee's read summary into the caller's current summary
 683     ReadSummary boundCalleeEfffects = new ReadSummary();
 684     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 685       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 686
 687       if (argHeapPath != null) {
 688         // if method is static, the first argument is nulll because static
 689         // method does not have implicit "THIS" arg
 690         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 691
 692         // iterate over callee's writing effect set
 693         Set<NTuple<Descriptor>> hpKeySet = calleeSummary.keySet();
 694         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 695           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 696           // current element is reachable caller's arg
 697           // so need to bind it to the caller's side and add it to the
 698           // callee's
 699           // init summary
 700           if (hpKey.startsWith(calleeParamHeapPath)) {
 701
 702             NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 703
 704             boundCalleeEfffects.put(boundHeapPathForCaller, calleeSummary.get(hpKey));
 705
 706           }
 707         }
 708
 709       }
 710
 711     }
 712     possibleCalleeReadSummarySetToCaller.add(boundCalleeEfffects);
 713
 714   }
 715
 716   private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
 717       FlatMethod calleeFlatMethod, ClearingSummary curr) {
 718
 719     ClearingSummary boundSet = new ClearingSummary();
 720
 721     // create mapping from arg idx to its heap paths
 722     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 723         new Hashtable<Integer, NTuple<Descriptor>>();
 724
 725     if (fc.getThis() != null) {
 726       // arg idx is starting from 'this' arg
 727       NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 728       if (thisHeapPath == null) {
 729         // method is called without creating new flat node representing 'this'
 730         thisHeapPath = new NTuple<Descriptor>();
 731         thisHeapPath.add(fc.getThis());
 732       }
 733
 734       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 735     }
 736
 737     for (int i = 0; i < fc.numArgs(); i++) {
 738       TempDescriptor arg = fc.getArg(i);
 739       NTuple<Descriptor> argHeapPath = computePath(arg);
 740       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 741     }
 742
 743     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 744         new Hashtable<Integer, TempDescriptor>();
 745     int offset = 0;
 746     if (calleeFlatMethod.getMethod().isStatic()) {
 747       // static method does not have implicit 'this' arg
 748       offset = 1;
 749     }
 750     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 751       TempDescriptor param = calleeFlatMethod.getParameter(i);
 752       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
 753     }
 754
 755     // binding caller's writing effects to callee's params
 756     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 757       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 758
 759       if (argHeapPath != null) {
 760         // if method is static, the first argument is nulll because static
 761         // method does not have implicit "THIS" arg
 762         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 763
 764         // iterate over caller's writing effect set
 765         Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 766         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 767           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 768           // current element is reachable caller's arg
 769           // so need to bind it to the caller's side and add it to the
 770           // callee's
 771           // init summary
 772           if (hpKey.startsWith(argHeapPath)) {
 773             NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 774             boundSet.put(boundHeapPath, curr.get(hpKey).clone());
 775           }
 776
 777         }
 778       }
 779
 780     }
 781
 782     // contribute callee's complete summary into the caller's current summary
 783     ClearingSummary calleeCompleteSummary =
 784         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
 785     if (calleeCompleteSummary != null) {
 786       ClearingSummary boundCalleeEfffects = new ClearingSummary();
 787       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 788         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 789
 790         if (argHeapPath != null) {
 791           // if method is static, the first argument is nulll because static
 792           // method does not have implicit "THIS" arg
 793           TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 794
 795           // iterate over callee's writing effect set
 796           Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
 797           for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 798             NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 799             // current element is reachable caller's arg
 800             // so need to bind it to the caller's side and add it to the
 801             // callee's
 802             // init summary
 803             if (hpKey.startsWith(calleeParamHeapPath)) {
 804
 805               NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 806
 807               boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
 808                   .clone());
 809
 810             }
 811           }
 812
 813         }
 814
 815       }
 816       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
 817     }
 818
 819     return boundSet;
 820   }
 821
 822   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
 823
 824     // replace the head of heap path with caller's arg path
 825     // for example, heap path 'param.a.b' in callee's side will be replaced with
 826     // (corresponding arg heap path).a.b for caller's side
 827
 828     NTuple<Descriptor> bound = new NTuple<Descriptor>();
 829
 830     for (int i = 0; i < argHeapPath.size(); i++) {
 831       bound.add(argHeapPath.get(i));
 832     }
 833
 834     for (int i = 1; i < hpKey.size(); i++) {
 835       bound.add(hpKey.get(i));
 836     }
 837
 838     return bound;
 839   }
 840
 841   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
 842       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
 843     // replace the head of caller's heap path with callee's param heap path
 844
 845     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
 846     boundHeapPath.add(calleeParamHeapPath);
 847
 848     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
 849       boundHeapPath.add(effectHeapPath.get(i));
 850     }
 851
 852     return boundHeapPath;
 853   }
 854
 855   private void computeReadSharedDescriptorSet() {
 856     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 857         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 858
 859     // current descriptors to visit in fixed-point interprocedural analysis,
 860     // prioritized by
 861     // dependency in the call graph
 862     methodDescriptorsToVisitStack.clear();
 863
 864     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 865     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 866
 867     while (!descriptorListToAnalyze.isEmpty()) {
 868       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 869       methodDescriptorsToVisitStack.add(md);
 870     }
 871
 872     // analyze scheduled methods until there are no more to visit
 873     while (!methodDescriptorsToVisitStack.isEmpty()) {
 874       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 875
 876       FlatMethod fm = state.getMethodFlat(md);
 877       ReadSummary completeSummary =
 878           computeReadSharedDescriptorSet_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
 879
 880       ReadSummary prevCompleteSummary = mapMethodDescriptorToReadSummary.get(md);
 881
 882       if (!completeSummary.equals(prevCompleteSummary)) {
 883         mapMethodDescriptorToReadSummary.put(md, completeSummary);
 884
 885         // results for callee changed, so enqueue dependents caller for
 886         // further analysis
 887         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 888         while (depsItr.hasNext()) {
 889           MethodDescriptor methodNext = depsItr.next();
 890           if (!methodDescriptorsToVisitStack.contains(methodNext)) {
 891             methodDescriptorsToVisitStack.add(methodNext);
 892           }
 893         }
 894
 895         // if there is set of callee to be analyzed,
 896         // add this set into the top of stack
 897         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 898         while (calleeIter.hasNext()) {
 899           MethodDescriptor mdNext = calleeIter.next();
 900           if (!methodDescriptorsToVisitStack.contains(mdNext)) {
 901             methodDescriptorsToVisitStack.add(mdNext);
 902           }
 903         }
 904         calleesToEnqueue.clear();
 905
 906       }
 907
 908     }
 909
 910   }
 911
 912   private ReadSummary computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
 913       boolean onlyVisitSSJavaLoop) {
 914
 915     MethodDescriptor md = fm.getMethod();
 916     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 917
 918     if (onlyVisitSSJavaLoop) {
 919       flatNodesToVisit.add(ssjavaLoopEntrance);
 920     } else {
 921       flatNodesToVisit.add(fm);
 922     }
 923
 924     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 925
 926     while (!flatNodesToVisit.isEmpty()) {
 927       FlatNode fn = flatNodesToVisit.iterator().next();
 928       flatNodesToVisit.remove(fn);
 929
 930       ReadSummary curr = new ReadSummary();
 931
 932       Set<ReadSummary> prevSet = new HashSet<ReadSummary>();
 933       for (int i = 0; i < fn.numPrev(); i++) {
 934         FlatNode prevFn = fn.getPrev(i);
 935         ReadSummary in = mapFlatNodeToReadSummary.get(prevFn);
 936         if (in != null) {
 937           prevSet.add(in);
 938         }
 939       }
 940
 941       mergeReadLocationAnaylsis(curr, prevSet);
 942
 943       computeReadSharedDescriptorSet_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 944
 945       ReadSummary readPrev = mapFlatNodeToReadSummary.get(fn);
 946
 947       if (!curr.equals(readPrev)) {
 948         mapFlatNodeToReadSummary.put(fn, curr);
 949
 950         for (int i = 0; i < fn.numNext(); i++) {
 951           FlatNode nn = fn.getNext(i);
 952
 953           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 954             flatNodesToVisit.add(nn);
 955           }
 956
 957         }
 958       }
 959
 960     }
 961
 962     ReadSummary completeSummary = new ReadSummary();
 963     Set<ReadSummary> summarySet = new HashSet<ReadSummary>();
 964
 965     if (onlyVisitSSJavaLoop) {
 966       // when analyzing ssjava loop,
 967       // complete summary is merging of all previous nodes of ssjava loop
 968       // entrance
 969       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 970         ReadSummary frnSummary = mapFlatNodeToReadSummary.get(ssjavaLoopEntrance.getPrev(i));
 971         if (frnSummary != null) {
 972           summarySet.add(frnSummary);
 973         }
 974       }
 975     } else {
 976       // merging exit node summary into the complete summary
 977       summarySet.add(mapFlatNodeToReadSummary.get(fm.getFlatExit()));
 978     }
 979     mergeReadLocationAnaylsis(completeSummary, summarySet);
 980
 981     return completeSummary;
 982
 983   }
 984
 985   private void computeReadSharedDescriptorSet_nodeActions(MethodDescriptor caller, FlatNode fn,
 986       ReadSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 987
 988     TempDescriptor lhs;
 989     TempDescriptor rhs;
 990     FieldDescriptor fld;
 991
 992     switch (fn.kind()) {
 993
 994     case FKind.FlatMethod: {
 995       FlatMethod fm = (FlatMethod) fn;
 996
 997       ReadSummary summary = mapMethodDescriptorToReadSummary.get(fm.getMethod());
 998
 999       Set<ReadSummary> inSet = new HashSet<ReadSummary>();
1000       if (summary != null) {
1001         inSet.add(summary);
1002         mergeReadLocationAnaylsis(curr, inSet);
1003       }
1004
1005     }
1006       break;
1007
1008     case FKind.FlatOpNode: {
1009       FlatOpNode fon = (FlatOpNode) fn;
1010       lhs = fon.getDest();
1011       rhs = fon.getLeft();
1012
1013       if (fon.getOp().getOp() == Operation.ASSIGN) {
1014         if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
1015           // in ssjavaloop, we need to take care about reading local variables!
1016           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
1017           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
1018           rhsHeapPath.add(LOCAL);
1019           Location loc = getLocation(rhs);
1020           if (loc != null && ssjava.isSharedLocation(loc)) {
1021             curr.addRead(rhsHeapPath, loc, rhs);
1022           }
1023         }
1024       }
1025
1026     }
1027       break;
1028
1029     case FKind.FlatFieldNode:
1030     case FKind.FlatElementNode: {
1031
1032       if (fn.kind() == FKind.FlatFieldNode) {
1033         FlatFieldNode ffn = (FlatFieldNode) fn;
1034         lhs = ffn.getDst();
1035         rhs = ffn.getSrc();
1036         fld = ffn.getField();
1037       } else {
1038         FlatElementNode fen = (FlatElementNode) fn;
1039         lhs = fen.getDst();
1040         rhs = fen.getSrc();
1041         TypeDescriptor td = rhs.getType().dereference();
1042         fld = getArrayField(td);
1043       }
1044
1045       if (fld.isStatic() && fld.isFinal()) {
1046         break;
1047       }
1048
1049       // read field
1050       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1051       if (srcHeapPath != null) {
1052         // if srcHeapPath is null, it means that it is not reachable from
1053         // callee's parameters. so just ignore it
1054
1055         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1056
1057         if (!fld.getType().isArray() && fld.getType().isImmutable()) {
1058
1059           Location loc;
1060           if (fn.kind() == FKind.FlatElementNode) {
1061             // array element read case
1062             NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
1063             for (int i = 0; i < fldHeapPath.size() - 1; i++) {
1064               newHeapPath.add(fldHeapPath.get(i));
1065             }
1066
1067             Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
1068             if (desc instanceof FieldDescriptor) {
1069               fld = (FieldDescriptor) desc;
1070               loc = getLocation(fld);
1071               fldHeapPath = newHeapPath;
1072               if (loc != null && ssjava.isSharedLocation(loc)) {
1073                 curr.addRead(fldHeapPath, loc, fld);
1074               }
1075             }
1076           } else {
1077             loc = getLocation(fld);
1078             if (loc != null && ssjava.isSharedLocation(loc)) {
1079               curr.addRead(fldHeapPath, loc, fld);
1080             }
1081           }
1082         } else {
1083           // propagate rhs's heap path to the lhs
1084
1085           if (fn.kind() == FKind.FlatElementNode) {
1086             mapDescToLocation.put(lhs, getLocation(rhs));
1087           } else {
1088             fldHeapPath.add(fld);
1089           }
1090           mapHeapPath.put(lhs, fldHeapPath);
1091         }
1092
1093       }
1094
1095     }
1096       break;
1097
1098     case FKind.FlatCall: {
1099
1100       FlatCall fc = (FlatCall) fn;
1101
1102       // find out the set of callees
1103       MethodDescriptor mdCallee = fc.getMethod();
1104       FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1105       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1106       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1107
1108       possibleCalleeReadSummarySetToCaller.clear();
1109
1110       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1111         MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
1112         FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
1113
1114         addDependent(mdPossibleCallee, // callee
1115             caller); // caller
1116
1117         calleesToEnqueue.add(mdPossibleCallee);
1118
1119         // updates possible callee's initial summary using caller's read status
1120         bindHeapPathReadSummary(fc, calleeFlatMethod, curr);
1121
1122       }
1123
1124       // contribute callee's writing effects to the caller
1125       mergeReadLocationAnaylsis(curr, possibleCalleeReadSummarySetToCaller);
1126
1127     }
1128       break;
1129
1130     case FKind.FlatReturnNode: {
1131       returnNodeSet.add(fn);
1132     }
1133       break;
1134
1135     }
1136   }
1137
1138   private void mergeReadLocationAnaylsis(ReadSummary curr, Set<ReadSummary> inSet) {
1139
1140     if (inSet.size() == 0) {
1141       return;
1142     }
1143
1144     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1145       ReadSummary inSummary = (ReadSummary) inIterator.next();
1146       curr.merge(inSummary);
1147     }
1148
1149   }
1150
1151   private boolean hasReadingEffectOnSharedLocation(MethodDescriptor md, NTuple<Descriptor> hp,
1152       Location loc, Descriptor d) {
1153
1154     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1155
1156     if (summary != null) {
1157       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1158       if (map != null) {
1159         Set<Descriptor> descSec = map.get(loc);
1160         if (descSec != null) {
1161           return descSec.contains(d);
1162         }
1163       }
1164     }
1165     return false;
1166
1167   }
1168
1169   private Location getLocation(Descriptor d) {
1170
1171     if (d instanceof FieldDescriptor) {
1172       TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
1173       if (te != null) {
1174         return (Location) te;
1175       }
1176     } else {
1177       assert d instanceof TempDescriptor;
1178       TempDescriptor td = (TempDescriptor) d;
1179
1180       TypeExtension te = td.getType().getExtension();
1181       if (te != null) {
1182         if (te instanceof CompositeLocation) {
1183           CompositeLocation comp = (CompositeLocation) te;
1184
1185           return comp.get(comp.getSize() - 1);
1186         } else {
1187           return (Location) te;
1188         }
1189       }
1190     }
1191
1192     return mapDescToLocation.get(d);
1193   }
1194
1195   private void writeLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1196       Location loc, Descriptor d) {
1197
1198     SharedStatus state = getState(curr, hp);
1199     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1200       // 1. add field x to the clearing set
1201
1202       state.addVar(loc, d);
1203
1204       // 3. if the set v contains all of variables belonging to the shared
1205       // location, set flag to true
1206       if (isOverWrittenAllDescsOfSharedLoc(md, hp, loc, state.getVarSet(loc))) {
1207         state.updateFlag(loc, true);
1208       }
1209     }
1210     state.setWriteEffect(loc);
1211
1212   }
1213
1214   private boolean isOverWrittenAllDescsOfSharedLoc(MethodDescriptor md, NTuple<Descriptor> hp,
1215       Location loc, Set<Descriptor> writtenSet) {
1216
1217     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1218
1219     if (summary != null) {
1220       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1221       if (map != null) {
1222         Set<Descriptor> descSet = map.get(loc);
1223         if (descSet != null) {
1224           return writtenSet.containsAll(descSet);
1225         }
1226       }
1227     }
1228     return false;
1229   }
1230
1231   private void readLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1232       Location loc, Descriptor d) {
1233     // remove reading var x from written set
1234     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1235       SharedStatus state = getState(curr, hp);
1236       state.removeVar(loc, d);
1237     }
1238   }
1239
1240   private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
1241     SharedStatus state = curr.get(hp);
1242     if (state == null) {
1243       state = new SharedStatus();
1244       curr.put(hp, state);
1245     }
1246     return state;
1247   }
1248
1249   private void writtenAnalyis() {
1250     // perform second stage analysis: intraprocedural analysis ensure that
1251     // all
1252     // variables are definitely written in-between the same read
1253
1254     // First, identify ssjava loop entrace
1255     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
1256     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1257     flatNodesToVisit.add(fm);
1258
1259     LoopFinder loopFinder = new LoopFinder(fm);
1260
1261     while (!flatNodesToVisit.isEmpty()) {
1262       FlatNode fn = flatNodesToVisit.iterator().next();
1263       flatNodesToVisit.remove(fn);
1264
1265       String label = (String) state.fn2labelMap.get(fn);
1266       if (label != null) {
1267
1268         if (label.equals(ssjava.SSJAVA)) {
1269           ssjavaLoopEntrance = fn;
1270           break;
1271         }
1272       }
1273
1274       for (int i = 0; i < fn.numNext(); i++) {
1275         FlatNode nn = fn.getNext(i);
1276         flatNodesToVisit.add(nn);
1277       }
1278     }
1279
1280     assert ssjavaLoopEntrance != null;
1281
1282     // assume that ssjava loop is top-level loop in method, not nested loop
1283     Set nestedLoop = loopFinder.nestedLoops();
1284     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
1285       LoopFinder lf = (LoopFinder) loopIter.next();
1286       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
1287         ssjavaLoop = lf;
1288       }
1289     }
1290
1291     assert ssjavaLoop != null;
1292
1293     writtenAnalysis_analyzeLoop();
1294
1295     if (debugcount > 0) {
1296       throw new Error();
1297     }
1298
1299   }
1300
1301   private void writtenAnalysis_analyzeLoop() {
1302
1303     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1304     flatNodesToVisit.add(ssjavaLoopEntrance);
1305
1306     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
1307
1308     while (!flatNodesToVisit.isEmpty()) {
1309       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1310       flatNodesToVisit.remove(fn);
1311
1312       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
1313           definitelyWrittenResults.get(fn);
1314
1315       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
1316           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
1317       for (int i = 0; i < fn.numPrev(); i++) {
1318         FlatNode nn = fn.getPrev(i);
1319         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
1320             definitelyWrittenResults.get(nn);
1321         if (dwIn != null) {
1322           merge(curr, dwIn);
1323         }
1324       }
1325
1326       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
1327
1328       // if a new result, schedule forward nodes for analysis
1329       if (!curr.equals(prev)) {
1330         definitelyWrittenResults.put(fn, curr);
1331
1332         for (int i = 0; i < fn.numNext(); i++) {
1333           FlatNode nn = fn.getNext(i);
1334           if (loopIncElements.contains(nn)) {
1335             flatNodesToVisit.add(nn);
1336           }
1337
1338         }
1339       }
1340     }
1341   }
1342
1343   private void writtenAnalysis_nodeAction(FlatNode fn,
1344       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
1345
1346     if (fn.equals(loopEntrance)) {
1347       // it reaches loop entrance: changes all flag to true
1348       Set<NTuple<Descriptor>> keySet = curr.keySet();
1349       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1350         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1351         Hashtable<FlatNode, Boolean> pair = curr.get(key);
1352         if (pair != null) {
1353           Set<FlatNode> pairKeySet = pair.keySet();
1354           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1355             FlatNode pairKey = (FlatNode) iterator2.next();
1356             pair.put(pairKey, Boolean.TRUE);
1357           }
1358         }
1359       }
1360     } else {
1361       TempDescriptor lhs;
1362       TempDescriptor rhs;
1363       FieldDescriptor fld;
1364
1365       switch (fn.kind()) {
1366       case FKind.FlatOpNode: {
1367         FlatOpNode fon = (FlatOpNode) fn;
1368         lhs = fon.getDest();
1369         rhs = fon.getLeft();
1370
1371         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1372         if (!rhs.getType().isImmutable()) {
1373           mapHeapPath.put(lhs, rhsHeapPath);
1374         } else {
1375           if (fon.getOp().getOp() == Operation.ASSIGN) {
1376             // read(rhs)
1377             readValue(fn, rhsHeapPath, curr);
1378           }
1379           // write(lhs)
1380           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1381           removeHeapPath(curr, lhsHeapPath);
1382         }
1383       }
1384         break;
1385
1386       case FKind.FlatLiteralNode: {
1387         FlatLiteralNode fln = (FlatLiteralNode) fn;
1388         lhs = fln.getDst();
1389
1390         // write(lhs)
1391         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1392         removeHeapPath(curr, lhsHeapPath);
1393
1394       }
1395         break;
1396
1397       case FKind.FlatFieldNode:
1398       case FKind.FlatElementNode: {
1399
1400         if (fn.kind() == FKind.FlatFieldNode) {
1401           FlatFieldNode ffn = (FlatFieldNode) fn;
1402           lhs = ffn.getDst();
1403           rhs = ffn.getSrc();
1404           fld = ffn.getField();
1405         } else {
1406           FlatElementNode fen = (FlatElementNode) fn;
1407           lhs = fen.getDst();
1408           rhs = fen.getSrc();
1409           TypeDescriptor td = rhs.getType().dereference();
1410           fld = getArrayField(td);
1411         }
1412
1413         if (fld.isFinal() /* && fld.isStatic() */) {
1414           // if field is final and static, no need to check
1415           break;
1416         }
1417
1418         // read field
1419         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1420         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1421         fldHeapPath.add(fld);
1422
1423         if (fld.getType().isImmutable()) {
1424           readValue(fn, fldHeapPath, curr);
1425         }
1426
1427         // propagate rhs's heap path to the lhs
1428         mapHeapPath.put(lhs, fldHeapPath);
1429
1430       }
1431         break;
1432
1433       case FKind.FlatSetFieldNode:
1434       case FKind.FlatSetElementNode: {
1435
1436         if (fn.kind() == FKind.FlatSetFieldNode) {
1437           FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1438           lhs = fsfn.getDst();
1439           fld = fsfn.getField();
1440         } else {
1441           FlatSetElementNode fsen = (FlatSetElementNode) fn;
1442           lhs = fsen.getDst();
1443           rhs = fsen.getSrc();
1444           TypeDescriptor td = lhs.getType().dereference();
1445           fld = getArrayField(td);
1446         }
1447
1448         // write(field)
1449         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1450         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1451         fldHeapPath.add(fld);
1452         removeHeapPath(curr, fldHeapPath);
1453
1454       }
1455         break;
1456
1457       case FKind.FlatCall: {
1458         FlatCall fc = (FlatCall) fn;
1459
1460         bindHeapPathCallerArgWithCaleeParam(fc);
1461         // add <hp,statement,false> in which hp is an element of
1462         // READ_bound set
1463         // of callee: callee has 'read' requirement!
1464
1465         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1466           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1467           Hashtable<FlatNode, Boolean> gen = curr.get(read);
1468           if (gen == null) {
1469             gen = new Hashtable<FlatNode, Boolean>();
1470             curr.put(read, gen);
1471           }
1472           Boolean currentStatus = gen.get(fn);
1473           if (currentStatus == null) {
1474             gen.put(fn, Boolean.FALSE);
1475           } else {
1476             checkFlag(currentStatus.booleanValue(), fn, read);
1477           }
1478         }
1479
1480         // removes <hp,statement,flag> if hp is an element of
1481         // OVERWRITE_bound
1482         // set of callee. it means that callee will overwrite it
1483         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1484           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1485           removeHeapPath(curr, write);
1486         }
1487       }
1488         break;
1489
1490       }
1491     }
1492
1493   }
1494
1495   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1496       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1497     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1498     if (gen == null) {
1499       gen = new Hashtable<FlatNode, Boolean>();
1500       curr.put(hp, gen);
1501     }
1502     Boolean currentStatus = gen.get(fn);
1503     if (currentStatus == null) {
1504       gen.put(fn, Boolean.FALSE);
1505     } else {
1506       checkFlag(currentStatus.booleanValue(), fn, hp);
1507     }
1508
1509   }
1510
1511   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1512       NTuple<Descriptor> hp) {
1513
1514     // removes all of heap path that starts with prefix 'hp'
1515     // since any reference overwrite along heap path gives overwriting side
1516     // effects on the value
1517
1518     Set<NTuple<Descriptor>> keySet = curr.keySet();
1519     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1520       NTuple<Descriptor> key = iter.next();
1521       if (key.startsWith(hp)) {
1522         curr.put(key, new Hashtable<FlatNode, Boolean>());
1523       }
1524     }
1525
1526   }
1527
1528   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1529     // compute all possible callee set
1530     // transform all READ/OVERWRITE set from the any possible
1531     // callees to the
1532     // caller
1533     calleeUnionBoundReadSet.clear();
1534     calleeIntersectBoundOverWriteSet.clear();
1535     calleeBoundWriteSet.clear();
1536
1537     if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1538       // ssjava util case!
1539       // have write effects on the first argument
1540       TempDescriptor arg = fc.getArg(0);
1541       NTuple<Descriptor> argHeapPath = computePath(arg);
1542       calleeIntersectBoundOverWriteSet.add(argHeapPath);
1543     } else {
1544       MethodDescriptor mdCallee = fc.getMethod();
1545       // FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1546       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1547       // setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1548       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1549
1550       // create mapping from arg idx to its heap paths
1551       Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1552           new Hashtable<Integer, NTuple<Descriptor>>();
1553
1554       // arg idx is starting from 'this' arg
1555       if (fc.getThis() != null) {
1556         NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1557         if (thisHeapPath == null) {
1558           // method is called without creating new flat node representing 'this'
1559           thisHeapPath = new NTuple<Descriptor>();
1560           thisHeapPath.add(fc.getThis());
1561         }
1562
1563         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1564       }
1565
1566       for (int i = 0; i < fc.numArgs(); i++) {
1567         TempDescriptor arg = fc.getArg(i);
1568         NTuple<Descriptor> argHeapPath = computePath(arg);
1569         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1570       }
1571
1572       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1573         MethodDescriptor callee = (MethodDescriptor) iterator.next();
1574         FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1575
1576         // binding caller's args and callee's params
1577
1578         Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1579         if (calleeReadSet == null) {
1580           calleeReadSet = new HashSet<NTuple<Descriptor>>();
1581           mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1582         }
1583
1584         Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1585
1586         if (calleeOverWriteSet == null) {
1587           calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1588           mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1589         }
1590
1591         Set<NTuple<Descriptor>> calleeWriteSet = mapFlatMethodToWrite.get(calleeFlatMethod);
1592
1593         if (calleeWriteSet == null) {
1594           calleeWriteSet = new HashSet<NTuple<Descriptor>>();
1595           mapFlatMethodToWrite.put(calleeFlatMethod, calleeWriteSet);
1596         }
1597
1598         Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1599             new Hashtable<Integer, TempDescriptor>();
1600         int offset = 0;
1601         if (calleeFlatMethod.getMethod().isStatic()) {
1602           // static method does not have implicit 'this' arg
1603           offset = 1;
1604         }
1605         for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1606           TempDescriptor param = calleeFlatMethod.getParameter(i);
1607           mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1608         }
1609
1610         Set<NTuple<Descriptor>> calleeBoundReadSet =
1611             bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1612         // union of the current read set and the current callee's
1613         // read set
1614         calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1615         Set<NTuple<Descriptor>> calleeBoundOverWriteSet =
1616             bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1617         // intersection of the current overwrite set and the current
1618         // callee's
1619         // overwrite set
1620         merge(calleeIntersectBoundOverWriteSet, calleeBoundOverWriteSet);
1621
1622         Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1623             bindSet(calleeWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1624         calleeBoundWriteSet.addAll(boundWriteSetFromCallee);
1625       }
1626
1627     }
1628
1629   }
1630
1631   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1632     if (booleanValue) {
1633       // the definitely written analysis only takes care about locations that
1634       // are written to inside of the SSJava loop
1635       for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1636         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1637         if (hp.startsWith(write)) {
1638           // it has write effect!
1639           // throw new Error(
1640           System.out
1641               .println("###"
1642                   + "There is a variable, which is reachable through references "
1643                   + hp
1644                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1645                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1646                   + fn.getNumLine());
1647           debugcount++;
1648         }
1649       }
1650     }
1651   }
1652
1653   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1654       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1655
1656     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1657     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1658       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1659       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1660
1661       Set<FlatNode> pairKeySet = inPair.keySet();
1662       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1663         FlatNode pairKey = (FlatNode) iterator2.next();
1664         Boolean inFlag = inPair.get(pairKey);
1665
1666         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1667         if (currPair == null) {
1668           currPair = new Hashtable<FlatNode, Boolean>();
1669           curr.put(inKey, currPair);
1670         }
1671
1672         Boolean currFlag = currPair.get(pairKey);
1673         // by default, flag is set by false
1674         if (currFlag == null) {
1675           currFlag = Boolean.FALSE;
1676         }
1677         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1678         currPair.put(pairKey, currFlag);
1679       }
1680
1681     }
1682
1683   }
1684
1685   private void methodReadOverWriteAnalysis() {
1686     // perform method READ/OVERWRITE analysis
1687     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1688     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1689
1690     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1691
1692     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1693         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1694
1695     // no need to analyze method having ssjava loop
1696     // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1697     methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1698
1699     // current descriptors to visit in fixed-point interprocedural analysis,
1700     // prioritized by
1701     // dependency in the call graph
1702     methodDescriptorsToVisitStack.clear();
1703
1704     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1705     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1706
1707     while (!descriptorListToAnalyze.isEmpty()) {
1708       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1709       methodDescriptorsToVisitStack.add(md);
1710     }
1711
1712     // analyze scheduled methods until there are no more to visit
1713     while (!methodDescriptorsToVisitStack.isEmpty()) {
1714       // start to analyze leaf node
1715       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1716       FlatMethod fm = state.getMethodFlat(md);
1717
1718       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1719       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1720       Set<NTuple<Descriptor>> writeSet = new HashSet<NTuple<Descriptor>>();
1721
1722       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet, writeSet);
1723
1724       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1725       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1726       Set<NTuple<Descriptor>> prevWrite = mapFlatMethodToWrite.get(fm);
1727
1728       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite) && writeSet
1729           .equals(prevWrite))) {
1730         mapFlatMethodToRead.put(fm, readSet);
1731         mapFlatMethodToOverWrite.put(fm, overWriteSet);
1732         mapFlatMethodToWrite.put(fm, writeSet);
1733
1734         // results for callee changed, so enqueue dependents caller for
1735         // further
1736         // analysis
1737         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1738         while (depsItr.hasNext()) {
1739           MethodDescriptor methodNext = depsItr.next();
1740           if (!methodDescriptorsToVisitStack.contains(methodNext)
1741               && methodDescriptorToVistSet.contains(methodNext)) {
1742             methodDescriptorsToVisitStack.add(methodNext);
1743           }
1744
1745         }
1746
1747       }
1748
1749     }
1750
1751   }
1752
1753   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1754       Set<NTuple<Descriptor>> overWriteSet, Set<NTuple<Descriptor>> writeSet) {
1755     if (state.SSJAVADEBUG) {
1756       System.out.println("Definitely written Analyzing: " + fm);
1757     }
1758
1759     // intraprocedural analysis
1760     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1761     flatNodesToVisit.add(fm);
1762
1763     while (!flatNodesToVisit.isEmpty()) {
1764       FlatNode fn = flatNodesToVisit.iterator().next();
1765       flatNodesToVisit.remove(fn);
1766
1767       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1768
1769       for (int i = 0; i < fn.numPrev(); i++) {
1770         FlatNode prevFn = fn.getPrev(i);
1771         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1772         if (in != null) {
1773           merge(curr, in);
1774         }
1775       }
1776
1777       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet, writeSet);
1778
1779       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1780       if (!curr.equals(writtenSetPrev)) {
1781         mapFlatNodeToWrittenSet.put(fn, curr);
1782         for (int i = 0; i < fn.numNext(); i++) {
1783           FlatNode nn = fn.getNext(i);
1784           flatNodesToVisit.add(nn);
1785         }
1786       }
1787
1788     }
1789
1790   }
1791
1792   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1793       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet,
1794       Set<NTuple<Descriptor>> writeSet) {
1795     TempDescriptor lhs;
1796     TempDescriptor rhs;
1797     FieldDescriptor fld;
1798
1799     switch (fn.kind()) {
1800     case FKind.FlatMethod: {
1801
1802       // set up initial heap paths for method parameters
1803       FlatMethod fm = (FlatMethod) fn;
1804       for (int i = 0; i < fm.numParameters(); i++) {
1805         TempDescriptor param = fm.getParameter(i);
1806         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1807         heapPath.add(param);
1808         mapHeapPath.put(param, heapPath);
1809       }
1810     }
1811       break;
1812
1813     case FKind.FlatOpNode: {
1814       FlatOpNode fon = (FlatOpNode) fn;
1815       // for a normal assign node, need to propagate lhs's heap path to
1816       // rhs
1817       if (fon.getOp().getOp() == Operation.ASSIGN) {
1818         rhs = fon.getLeft();
1819         lhs = fon.getDest();
1820
1821         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1822         if (rhsHeapPath != null) {
1823           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1824         }
1825
1826       }
1827     }
1828       break;
1829
1830     case FKind.FlatElementNode:
1831     case FKind.FlatFieldNode: {
1832
1833       // y=x.f;
1834
1835       if (fn.kind() == FKind.FlatFieldNode) {
1836         FlatFieldNode ffn = (FlatFieldNode) fn;
1837         lhs = ffn.getDst();
1838         rhs = ffn.getSrc();
1839         fld = ffn.getField();
1840       } else {
1841         FlatElementNode fen = (FlatElementNode) fn;
1842         lhs = fen.getDst();
1843         rhs = fen.getSrc();
1844         TypeDescriptor td = rhs.getType().dereference();
1845         fld = getArrayField(td);
1846       }
1847
1848       if (fld.isFinal() /* && fld.isStatic() */) {
1849         // if field is final and static, no need to check
1850         break;
1851       }
1852
1853       // set up heap path
1854       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1855       if (srcHeapPath != null) {
1856         // if lhs srcHeapPath is null, it means that it is not reachable from
1857         // callee's parameters. so just ignore it
1858
1859         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1860         readingHeapPath.add(fld);
1861         mapHeapPath.put(lhs, readingHeapPath);
1862
1863         // read (x.f)
1864         if (fld.getType().isImmutable()) {
1865           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1866           if (!writtenSet.contains(readingHeapPath)) {
1867             readSet.add(readingHeapPath);
1868           }
1869         }
1870
1871         // no need to kill hp(x.f) from WT
1872       }
1873
1874     }
1875       break;
1876
1877     case FKind.FlatSetFieldNode:
1878     case FKind.FlatSetElementNode: {
1879
1880       // x.f=y;
1881
1882       if (fn.kind() == FKind.FlatSetFieldNode) {
1883         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1884         lhs = fsfn.getDst();
1885         fld = fsfn.getField();
1886         rhs = fsfn.getSrc();
1887       } else {
1888         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1889         lhs = fsen.getDst();
1890         rhs = fsen.getSrc();
1891         TypeDescriptor td = lhs.getType().dereference();
1892         fld = getArrayField(td);
1893       }
1894
1895       // set up heap path
1896       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1897       if (lhsHeapPath != null) {
1898         // if lhs heap path is null, it means that it is not reachable from
1899         // callee's parameters. so just ignore it
1900         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1901         newHeapPath.add(fld);
1902         mapHeapPath.put(fld, newHeapPath);
1903
1904         // write(x.f)
1905         // need to add hp(y) to WT
1906         writtenSet.add(newHeapPath);
1907
1908         writeSet.add(newHeapPath);
1909       }
1910
1911     }
1912       break;
1913
1914     case FKind.FlatCall: {
1915
1916       FlatCall fc = (FlatCall) fn;
1917
1918       bindHeapPathCallerArgWithCaleeParam(fc);
1919
1920       // add heap path, which is an element of READ_bound set and is not
1921       // an
1922       // element of WT set, to the caller's READ set
1923       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1924         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1925         if (!writtenSet.contains(read)) {
1926           readSet.add(read);
1927         }
1928       }
1929
1930       // add heap path, which is an element of OVERWRITE_bound set, to the
1931       // caller's WT set
1932       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1933         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1934         writtenSet.add(write);
1935       }
1936
1937       // add heap path, which is an element of WRITE_BOUND set, to the
1938       // caller's writeSet
1939       for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1940         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1941         writeSet.add(write);
1942       }
1943
1944     }
1945       break;
1946
1947     case FKind.FlatExit: {
1948       // merge the current written set with OVERWRITE set
1949       merge(overWriteSet, writtenSet);
1950     }
1951       break;
1952
1953     }
1954
1955   }
1956
1957   static public FieldDescriptor getArrayField(TypeDescriptor td) {
1958     FieldDescriptor fd = mapTypeToArrayField.get(td);
1959     if (fd == null) {
1960       fd =
1961           new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1962               false);
1963       mapTypeToArrayField.put(td, fd);
1964     }
1965     return fd;
1966   }
1967
1968   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1969     if (inSet.size() == 0) {
1970       return;
1971     }
1972     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1973         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1974
1975     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1976
1977       ClearingSummary inTable = (ClearingSummary) inIterator.next();
1978
1979       Set<NTuple<Descriptor>> keySet = inTable.keySet();
1980
1981       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1982         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1983         SharedStatus inState = inTable.get(hpKey);
1984         SharedStatus currState = curr.get(hpKey);
1985         if (currState == null) {
1986           currState = new SharedStatus();
1987           curr.put(hpKey, currState);
1988         }
1989
1990         currState.merge(inState);
1991
1992         Set<Location> locSet = inState.getMap().keySet();
1993         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1994           Location loc = (Location) iterator2.next();
1995           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1996           boolean inFlag = pair.getSecond().booleanValue();
1997
1998           Pair<NTuple<Descriptor>, Location> flagKey =
1999               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
2000           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
2001           if (current == null) {
2002             current = new Boolean(true);
2003           }
2004           boolean newInFlag = current.booleanValue() & inFlag;
2005           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
2006         }
2007
2008       }
2009
2010     }
2011
2012     // merge flag status
2013     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
2014     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2015       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2016       SharedStatus currState = curr.get(hpKey);
2017       Set<Location> locKeySet = currState.getMap().keySet();
2018       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2019         Location locKey = (Location) iterator2.next();
2020         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
2021         boolean currentFlag = pair.getSecond().booleanValue();
2022         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
2023         if (inFlag != null) {
2024           boolean newFlag = currentFlag | inFlag.booleanValue();
2025           if (currentFlag != newFlag) {
2026             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
2027           }
2028         }
2029       }
2030     }
2031
2032   }
2033
2034   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
2035     if (curr.isEmpty()) {
2036       // WrittenSet has a special initial value which covers all possible
2037       // elements
2038       // For the first time of intersection, we can take all previous set
2039       curr.addAll(in);
2040     } else {
2041       // otherwise, current set is the intersection of the two sets
2042       curr.retainAll(in);
2043     }
2044
2045   }
2046
2047   // combine two heap path
2048   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
2049     NTuple<Descriptor> combined = new NTuple<Descriptor>();
2050
2051     for (int i = 0; i < callerIn.size(); i++) {
2052       combined.add(callerIn.get(i));
2053     }
2054
2055     // the first element of callee's heap path represents parameter
2056     // so we skip the first one since it is already added from caller's heap
2057     // path
2058     for (int i = 1; i < calleeIn.size(); i++) {
2059       combined.add(calleeIn.get(i));
2060     }
2061
2062     return combined;
2063   }
2064
2065   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
2066       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2067       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2068
2069     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
2070
2071     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2072     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2073       Integer idx = (Integer) iterator.next();
2074
2075       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2076       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2077       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2078         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2079         if (element.startsWith(calleeParam)) {
2080           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2081           boundedCalleeSet.add(boundElement);
2082         }
2083
2084       }
2085
2086     }
2087     return boundedCalleeSet;
2088
2089   }
2090
2091   // Borrowed it from disjoint analysis
2092   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2093
2094     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2095
2096     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2097
2098     Iterator<MethodDescriptor> itr = toSort.iterator();
2099     while (itr.hasNext()) {
2100       MethodDescriptor d = itr.next();
2101
2102       if (!discovered.contains(d)) {
2103         dfsVisit(d, toSort, sorted, discovered);
2104       }
2105     }
2106
2107     return sorted;
2108   }
2109
2110   // While we're doing DFS on call graph, remember
2111   // dependencies for efficient queuing of methods
2112   // during interprocedural analysis:
2113   //
2114   // a dependent of a method decriptor d for this analysis is:
2115   // 1) a method or task that invokes d
2116   // 2) in the descriptorsToAnalyze set
2117   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2118       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2119
2120     discovered.add(md);
2121
2122     Iterator itr = callGraph.getCallerSet(md).iterator();
2123     while (itr.hasNext()) {
2124       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2125       // only consider callers in the original set to analyze
2126       if (!toSort.contains(dCaller)) {
2127         continue;
2128       }
2129       if (!discovered.contains(dCaller)) {
2130         addDependent(md, // callee
2131             dCaller // caller
2132         );
2133
2134         dfsVisit(dCaller, toSort, sorted, discovered);
2135       }
2136     }
2137
2138     // for leaf-nodes last now!
2139     sorted.addLast(md);
2140   }
2141
2142   // a dependent of a method decriptor d for this analysis is:
2143   // 1) a method or task that invokes d
2144   // 2) in the descriptorsToAnalyze set
2145   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2146     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2147     if (deps == null) {
2148       deps = new HashSet<MethodDescriptor>();
2149     }
2150     deps.add(caller);
2151     mapDescriptorToSetDependents.put(callee, deps);
2152   }
2153
2154   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2155     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2156     if (deps == null) {
2157       deps = new HashSet<MethodDescriptor>();
2158       mapDescriptorToSetDependents.put(callee, deps);
2159     }
2160     return deps;
2161   }
2162
2163   private NTuple<Descriptor> computePath(TempDescriptor td) {
2164     // generate proper path fot input td
2165     // if td is local variable, it just generate one element tuple path
2166     if (mapHeapPath.containsKey(td)) {
2167       return mapHeapPath.get(td);
2168     } else {
2169       NTuple<Descriptor> path = new NTuple<Descriptor>();
2170       path.add(td);
2171       return path;
2172     }
2173   }
2174
2175 }