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
1446         NTuple<Descriptor> fldHeapPath;
1447         if (srcHeapPath != null) {
1448           fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1449         } else {
1450           // if srcHeapPath is null, it is static reference
1451           System.out.println("##");
1452           System.out.println("rhs=" + rhs + " fd=" + fld);
1453           fldHeapPath = new NTuple<Descriptor>();
1454           fldHeapPath.add(rhs);
1455         }
1456         fldHeapPath.add(fld);
1457
1458         if (fld.getType().isImmutable()) {
1459           readValue(fn, fldHeapPath, curr);
1460         }
1461
1462         // propagate rhs's heap path to the lhs
1463         mapHeapPath.put(lhs, fldHeapPath);
1464
1465       }
1466         break;
1467
1468       case FKind.FlatSetFieldNode:
1469       case FKind.FlatSetElementNode: {
1470
1471         if (fn.kind() == FKind.FlatSetFieldNode) {
1472           FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1473           lhs = fsfn.getDst();
1474           fld = fsfn.getField();
1475         } else {
1476           FlatSetElementNode fsen = (FlatSetElementNode) fn;
1477           lhs = fsen.getDst();
1478           rhs = fsen.getSrc();
1479           TypeDescriptor td = lhs.getType().dereference();
1480           fld = getArrayField(td);
1481         }
1482
1483         // write(field)
1484         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1485         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1486         fldHeapPath.add(fld);
1487         removeHeapPath(curr, fldHeapPath);
1488
1489       }
1490         break;
1491
1492       case FKind.FlatCall: {
1493         FlatCall fc = (FlatCall) fn;
1494
1495         bindHeapPathCallerArgWithCaleeParam(fc);
1496         // add <hp,statement,false> in which hp is an element of
1497         // READ_bound set
1498         // of callee: callee has 'read' requirement!
1499
1500         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1501           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1502           Hashtable<FlatNode, Boolean> gen = curr.get(read);
1503           if (gen == null) {
1504             gen = new Hashtable<FlatNode, Boolean>();
1505             curr.put(read, gen);
1506           }
1507           Boolean currentStatus = gen.get(fn);
1508           if (currentStatus == null) {
1509             gen.put(fn, Boolean.FALSE);
1510           } else {
1511             checkFlag(currentStatus.booleanValue(), fn, read);
1512           }
1513         }
1514
1515         // removes <hp,statement,flag> if hp is an element of
1516         // OVERWRITE_bound
1517         // set of callee. it means that callee will overwrite it
1518         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1519           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1520           removeHeapPath(curr, write);
1521         }
1522       }
1523         break;
1524
1525       }
1526     }
1527
1528   }
1529
1530   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1531       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1532     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1533     if (gen == null) {
1534       gen = new Hashtable<FlatNode, Boolean>();
1535       curr.put(hp, gen);
1536     }
1537     Boolean currentStatus = gen.get(fn);
1538     if (currentStatus == null) {
1539       gen.put(fn, Boolean.FALSE);
1540     } else {
1541       checkFlag(currentStatus.booleanValue(), fn, hp);
1542     }
1543
1544   }
1545
1546   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1547       NTuple<Descriptor> hp) {
1548
1549     // removes all of heap path that starts with prefix 'hp'
1550     // since any reference overwrite along heap path gives overwriting side
1551     // effects on the value
1552
1553     Set<NTuple<Descriptor>> keySet = curr.keySet();
1554     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1555       NTuple<Descriptor> key = iter.next();
1556       if (key.startsWith(hp)) {
1557         curr.put(key, new Hashtable<FlatNode, Boolean>());
1558       }
1559     }
1560
1561   }
1562
1563   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1564     // compute all possible callee set
1565     // transform all READ/OVERWRITE set from the any possible
1566     // callees to the
1567     // caller
1568     calleeUnionBoundReadSet.clear();
1569     calleeIntersectBoundOverWriteSet.clear();
1570     calleeBoundWriteSet.clear();
1571
1572     if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1573       // ssjava util case!
1574       // have write effects on the first argument
1575       TempDescriptor arg = fc.getArg(0);
1576       NTuple<Descriptor> argHeapPath = computePath(arg);
1577       calleeIntersectBoundOverWriteSet.add(argHeapPath);
1578     } else {
1579       MethodDescriptor mdCallee = fc.getMethod();
1580       // FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1581       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1582       // setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1583       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1584
1585       // create mapping from arg idx to its heap paths
1586       Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1587           new Hashtable<Integer, NTuple<Descriptor>>();
1588
1589       // arg idx is starting from 'this' arg
1590       if (fc.getThis() != null) {
1591         NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1592         if (thisHeapPath == null) {
1593           // method is called without creating new flat node representing 'this'
1594           thisHeapPath = new NTuple<Descriptor>();
1595           thisHeapPath.add(fc.getThis());
1596         }
1597
1598         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1599       }
1600
1601       for (int i = 0; i < fc.numArgs(); i++) {
1602         TempDescriptor arg = fc.getArg(i);
1603         NTuple<Descriptor> argHeapPath = computePath(arg);
1604         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1605       }
1606
1607       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1608         MethodDescriptor callee = (MethodDescriptor) iterator.next();
1609         FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1610
1611         // binding caller's args and callee's params
1612
1613         Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1614         if (calleeReadSet == null) {
1615           calleeReadSet = new HashSet<NTuple<Descriptor>>();
1616           mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1617         }
1618
1619         Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1620
1621         if (calleeOverWriteSet == null) {
1622           calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1623           mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1624         }
1625
1626         Set<NTuple<Descriptor>> calleeWriteSet = mapFlatMethodToWrite.get(calleeFlatMethod);
1627
1628         if (calleeWriteSet == null) {
1629           calleeWriteSet = new HashSet<NTuple<Descriptor>>();
1630           mapFlatMethodToWrite.put(calleeFlatMethod, calleeWriteSet);
1631         }
1632
1633         Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1634             new Hashtable<Integer, TempDescriptor>();
1635         int offset = 0;
1636         if (calleeFlatMethod.getMethod().isStatic()) {
1637           // static method does not have implicit 'this' arg
1638           offset = 1;
1639         }
1640         for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1641           TempDescriptor param = calleeFlatMethod.getParameter(i);
1642           mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1643         }
1644
1645         Set<NTuple<Descriptor>> calleeBoundReadSet =
1646             bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1647         // union of the current read set and the current callee's
1648         // read set
1649         calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1650         Set<NTuple<Descriptor>> calleeBoundOverWriteSet =
1651             bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1652         // intersection of the current overwrite set and the current
1653         // callee's
1654         // overwrite set
1655         merge(calleeIntersectBoundOverWriteSet, calleeBoundOverWriteSet);
1656
1657         Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1658             bindSet(calleeWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1659         calleeBoundWriteSet.addAll(boundWriteSetFromCallee);
1660       }
1661
1662     }
1663
1664   }
1665
1666   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1667     if (booleanValue) {
1668       // the definitely written analysis only takes care about locations that
1669       // are written to inside of the SSJava loop
1670       for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1671         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1672         if (hp.startsWith(write)) {
1673           // it has write effect!
1674           // throw new Error(
1675           System.out
1676               .println("###"
1677                   + "There is a variable, which is reachable through references "
1678                   + hp
1679                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1680                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1681                   + fn.getNumLine());
1682           debugcount++;
1683         }
1684       }
1685     }
1686   }
1687
1688   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1689       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1690
1691     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1692     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1693       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1694       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1695
1696       Set<FlatNode> pairKeySet = inPair.keySet();
1697       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1698         FlatNode pairKey = (FlatNode) iterator2.next();
1699         Boolean inFlag = inPair.get(pairKey);
1700
1701         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1702         if (currPair == null) {
1703           currPair = new Hashtable<FlatNode, Boolean>();
1704           curr.put(inKey, currPair);
1705         }
1706
1707         Boolean currFlag = currPair.get(pairKey);
1708         // by default, flag is set by false
1709         if (currFlag == null) {
1710           currFlag = Boolean.FALSE;
1711         }
1712         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1713         currPair.put(pairKey, currFlag);
1714       }
1715
1716     }
1717
1718   }
1719
1720   private void methodReadOverWriteAnalysis() {
1721     // perform method READ/OVERWRITE analysis
1722     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1723     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1724
1725     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1726
1727     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1728         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1729
1730     // no need to analyze method having ssjava loop
1731     // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1732     methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1733
1734     // current descriptors to visit in fixed-point interprocedural analysis,
1735     // prioritized by
1736     // dependency in the call graph
1737     methodDescriptorsToVisitStack.clear();
1738
1739     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1740     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1741
1742     while (!descriptorListToAnalyze.isEmpty()) {
1743       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1744       methodDescriptorsToVisitStack.add(md);
1745     }
1746
1747     // analyze scheduled methods until there are no more to visit
1748     while (!methodDescriptorsToVisitStack.isEmpty()) {
1749       // start to analyze leaf node
1750       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1751       FlatMethod fm = state.getMethodFlat(md);
1752
1753       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1754       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1755       Set<NTuple<Descriptor>> writeSet = new HashSet<NTuple<Descriptor>>();
1756
1757       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet, writeSet);
1758
1759       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1760       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1761       Set<NTuple<Descriptor>> prevWrite = mapFlatMethodToWrite.get(fm);
1762
1763       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite) && writeSet
1764           .equals(prevWrite))) {
1765         mapFlatMethodToRead.put(fm, readSet);
1766         mapFlatMethodToOverWrite.put(fm, overWriteSet);
1767         mapFlatMethodToWrite.put(fm, writeSet);
1768
1769         // results for callee changed, so enqueue dependents caller for
1770         // further
1771         // analysis
1772         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1773         while (depsItr.hasNext()) {
1774           MethodDescriptor methodNext = depsItr.next();
1775           if (!methodDescriptorsToVisitStack.contains(methodNext)
1776               && methodDescriptorToVistSet.contains(methodNext)) {
1777             methodDescriptorsToVisitStack.add(methodNext);
1778           }
1779
1780         }
1781
1782       }
1783
1784     }
1785
1786   }
1787
1788   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1789       Set<NTuple<Descriptor>> overWriteSet, Set<NTuple<Descriptor>> writeSet) {
1790     if (state.SSJAVADEBUG) {
1791       System.out.println("SSJAVA: Definitely written Analyzing: " + fm);
1792     }
1793
1794     // intraprocedural analysis
1795     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1796     flatNodesToVisit.add(fm);
1797
1798     while (!flatNodesToVisit.isEmpty()) {
1799       FlatNode fn = flatNodesToVisit.iterator().next();
1800       flatNodesToVisit.remove(fn);
1801
1802       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1803
1804       for (int i = 0; i < fn.numPrev(); i++) {
1805         FlatNode prevFn = fn.getPrev(i);
1806         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1807         if (in != null) {
1808           merge(curr, in);
1809         }
1810       }
1811
1812       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet, writeSet);
1813
1814       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1815       if (!curr.equals(writtenSetPrev)) {
1816         mapFlatNodeToWrittenSet.put(fn, curr);
1817         for (int i = 0; i < fn.numNext(); i++) {
1818           FlatNode nn = fn.getNext(i);
1819           flatNodesToVisit.add(nn);
1820         }
1821       }
1822
1823     }
1824
1825   }
1826
1827   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1828       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet,
1829       Set<NTuple<Descriptor>> writeSet) {
1830     TempDescriptor lhs;
1831     TempDescriptor rhs;
1832     FieldDescriptor fld;
1833
1834     switch (fn.kind()) {
1835     case FKind.FlatMethod: {
1836
1837       // set up initial heap paths for method parameters
1838       FlatMethod fm = (FlatMethod) fn;
1839       for (int i = 0; i < fm.numParameters(); i++) {
1840         TempDescriptor param = fm.getParameter(i);
1841         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1842         heapPath.add(param);
1843         mapHeapPath.put(param, heapPath);
1844       }
1845     }
1846       break;
1847
1848     case FKind.FlatOpNode: {
1849       FlatOpNode fon = (FlatOpNode) fn;
1850       // for a normal assign node, need to propagate lhs's heap path to
1851       // rhs
1852       if (fon.getOp().getOp() == Operation.ASSIGN) {
1853         rhs = fon.getLeft();
1854         lhs = fon.getDest();
1855
1856         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1857         if (rhsHeapPath != null) {
1858           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1859         }
1860
1861       }
1862     }
1863       break;
1864
1865     case FKind.FlatElementNode:
1866     case FKind.FlatFieldNode: {
1867
1868       // y=x.f;
1869
1870       if (fn.kind() == FKind.FlatFieldNode) {
1871         FlatFieldNode ffn = (FlatFieldNode) fn;
1872         lhs = ffn.getDst();
1873         rhs = ffn.getSrc();
1874         fld = ffn.getField();
1875       } else {
1876         FlatElementNode fen = (FlatElementNode) fn;
1877         lhs = fen.getDst();
1878         rhs = fen.getSrc();
1879         TypeDescriptor td = rhs.getType().dereference();
1880         fld = getArrayField(td);
1881       }
1882
1883       if (fld.isFinal() /* && fld.isStatic() */) {
1884         // if field is final and static, no need to check
1885         break;
1886       }
1887
1888       // set up heap path
1889       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1890       if (srcHeapPath != null) {
1891         // if lhs srcHeapPath is null, it means that it is not reachable from
1892         // callee's parameters. so just ignore it
1893
1894         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1895         readingHeapPath.add(fld);
1896         mapHeapPath.put(lhs, readingHeapPath);
1897
1898         // read (x.f)
1899         if (fld.getType().isImmutable()) {
1900           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1901           if (!writtenSet.contains(readingHeapPath)) {
1902             readSet.add(readingHeapPath);
1903           }
1904         }
1905
1906         // no need to kill hp(x.f) from WT
1907       }
1908
1909     }
1910       break;
1911
1912     case FKind.FlatSetFieldNode:
1913     case FKind.FlatSetElementNode: {
1914
1915       // x.f=y;
1916
1917       if (fn.kind() == FKind.FlatSetFieldNode) {
1918         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1919         lhs = fsfn.getDst();
1920         fld = fsfn.getField();
1921         rhs = fsfn.getSrc();
1922       } else {
1923         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1924         lhs = fsen.getDst();
1925         rhs = fsen.getSrc();
1926         TypeDescriptor td = lhs.getType().dereference();
1927         fld = getArrayField(td);
1928       }
1929
1930       // set up heap path
1931       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1932       if (lhsHeapPath != null) {
1933         // if lhs heap path is null, it means that it is not reachable from
1934         // callee's parameters. so just ignore it
1935         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1936         newHeapPath.add(fld);
1937         mapHeapPath.put(fld, newHeapPath);
1938
1939         // write(x.f)
1940         // need to add hp(y) to WT
1941         writtenSet.add(newHeapPath);
1942
1943         writeSet.add(newHeapPath);
1944       }
1945
1946     }
1947       break;
1948
1949     case FKind.FlatCall: {
1950
1951       FlatCall fc = (FlatCall) fn;
1952
1953       bindHeapPathCallerArgWithCaleeParam(fc);
1954
1955       // add heap path, which is an element of READ_bound set and is not
1956       // an
1957       // element of WT set, to the caller's READ set
1958       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1959         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1960         if (!writtenSet.contains(read)) {
1961           readSet.add(read);
1962         }
1963       }
1964
1965       // add heap path, which is an element of OVERWRITE_bound set, to the
1966       // caller's WT set
1967       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1968         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1969         writtenSet.add(write);
1970       }
1971
1972       // add heap path, which is an element of WRITE_BOUND set, to the
1973       // caller's writeSet
1974       for (Iterator iterator = calleeBoundWriteSet.iterator(); iterator.hasNext();) {
1975         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1976         writeSet.add(write);
1977       }
1978
1979     }
1980       break;
1981
1982     case FKind.FlatExit: {
1983       // merge the current written set with OVERWRITE set
1984       merge(overWriteSet, writtenSet);
1985     }
1986       break;
1987
1988     }
1989
1990   }
1991
1992   static public FieldDescriptor getArrayField(TypeDescriptor td) {
1993     FieldDescriptor fd = mapTypeToArrayField.get(td);
1994     if (fd == null) {
1995       fd =
1996           new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1997               false);
1998       mapTypeToArrayField.put(td, fd);
1999     }
2000     return fd;
2001   }
2002
2003   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
2004     if (inSet.size() == 0) {
2005       return;
2006     }
2007     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
2008         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
2009
2010     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
2011
2012       ClearingSummary inTable = (ClearingSummary) inIterator.next();
2013
2014       Set<NTuple<Descriptor>> keySet = inTable.keySet();
2015
2016       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2017         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2018         SharedStatus inState = inTable.get(hpKey);
2019         SharedStatus currState = curr.get(hpKey);
2020         if (currState == null) {
2021           currState = new SharedStatus();
2022           curr.put(hpKey, currState);
2023         }
2024
2025         currState.merge(inState);
2026
2027         Set<Location> locSet = inState.getMap().keySet();
2028         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
2029           Location loc = (Location) iterator2.next();
2030           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
2031           boolean inFlag = pair.getSecond().booleanValue();
2032
2033           Pair<NTuple<Descriptor>, Location> flagKey =
2034               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
2035           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
2036           if (current == null) {
2037             current = new Boolean(true);
2038           }
2039           boolean newInFlag = current.booleanValue() & inFlag;
2040           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
2041         }
2042
2043       }
2044
2045     }
2046
2047     // merge flag status
2048     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
2049     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2050       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2051       SharedStatus currState = curr.get(hpKey);
2052       Set<Location> locKeySet = currState.getMap().keySet();
2053       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2054         Location locKey = (Location) iterator2.next();
2055         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
2056         boolean currentFlag = pair.getSecond().booleanValue();
2057         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
2058         if (inFlag != null) {
2059           boolean newFlag = currentFlag | inFlag.booleanValue();
2060           if (currentFlag != newFlag) {
2061             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
2062           }
2063         }
2064       }
2065     }
2066
2067   }
2068
2069   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
2070     if (curr.isEmpty()) {
2071       // WrittenSet has a special initial value which covers all possible
2072       // elements
2073       // For the first time of intersection, we can take all previous set
2074       curr.addAll(in);
2075     } else {
2076       // otherwise, current set is the intersection of the two sets
2077       curr.retainAll(in);
2078     }
2079
2080   }
2081
2082   // combine two heap path
2083   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
2084     NTuple<Descriptor> combined = new NTuple<Descriptor>();
2085
2086     for (int i = 0; i < callerIn.size(); i++) {
2087       combined.add(callerIn.get(i));
2088     }
2089
2090     // the first element of callee's heap path represents parameter
2091     // so we skip the first one since it is already added from caller's heap
2092     // path
2093     for (int i = 1; i < calleeIn.size(); i++) {
2094       combined.add(calleeIn.get(i));
2095     }
2096
2097     return combined;
2098   }
2099
2100   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
2101       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2102       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2103
2104     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
2105
2106     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2107     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2108       Integer idx = (Integer) iterator.next();
2109
2110       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2111       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2112       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2113         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2114         if (element.startsWith(calleeParam)) {
2115           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2116           boundedCalleeSet.add(boundElement);
2117         }
2118
2119       }
2120
2121     }
2122     return boundedCalleeSet;
2123
2124   }
2125
2126   // Borrowed it from disjoint analysis
2127   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2128
2129     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2130
2131     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2132
2133     Iterator<MethodDescriptor> itr = toSort.iterator();
2134     while (itr.hasNext()) {
2135       MethodDescriptor d = itr.next();
2136
2137       if (!discovered.contains(d)) {
2138         dfsVisit(d, toSort, sorted, discovered);
2139       }
2140     }
2141
2142     return sorted;
2143   }
2144
2145   // While we're doing DFS on call graph, remember
2146   // dependencies for efficient queuing of methods
2147   // during interprocedural analysis:
2148   //
2149   // a dependent of a method decriptor d for this analysis is:
2150   // 1) a method or task that invokes d
2151   // 2) in the descriptorsToAnalyze set
2152   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2153       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2154
2155     discovered.add(md);
2156
2157     Iterator itr = callGraph.getCallerSet(md).iterator();
2158     while (itr.hasNext()) {
2159       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2160       // only consider callers in the original set to analyze
2161       if (!toSort.contains(dCaller)) {
2162         continue;
2163       }
2164       if (!discovered.contains(dCaller)) {
2165         addDependent(md, // callee
2166             dCaller // caller
2167         );
2168
2169         dfsVisit(dCaller, toSort, sorted, discovered);
2170       }
2171     }
2172
2173     // for leaf-nodes last now!
2174     sorted.addLast(md);
2175   }
2176
2177   // a dependent of a method decriptor d for this analysis is:
2178   // 1) a method or task that invokes d
2179   // 2) in the descriptorsToAnalyze set
2180   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2181     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2182     if (deps == null) {
2183       deps = new HashSet<MethodDescriptor>();
2184     }
2185     deps.add(caller);
2186     mapDescriptorToSetDependents.put(callee, deps);
2187   }
2188
2189   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2190     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2191     if (deps == null) {
2192       deps = new HashSet<MethodDescriptor>();
2193       mapDescriptorToSetDependents.put(callee, deps);
2194     }
2195     return deps;
2196   }
2197
2198   private NTuple<Descriptor> computePath(TempDescriptor td) {
2199     // generate proper path fot input td
2200     // if td is local variable, it just generate one element tuple path
2201     if (mapHeapPath.containsKey(td)) {
2202       return mapHeapPath.get(td);
2203     } else {
2204       NTuple<Descriptor> path = new NTuple<Descriptor>();
2205       path.add(td);
2206       return path;
2207     }
2208   }
2209
2210 }