Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

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