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.Enumeration;
   7 import java.util.HashSet;
   8 import java.util.Hashtable;
   9 import java.util.Iterator;
  10 import java.util.LinkedList;
  11 import java.util.Set;
  12 import java.util.Stack;
  13
  14 import Analysis.CallGraph.CallGraph;
  15 import Analysis.Loops.LoopFinder;
  16 import IR.ClassDescriptor;
  17 import IR.Descriptor;
  18 import IR.FieldDescriptor;
  19 import IR.MethodDescriptor;
  20 import IR.Operation;
  21 import IR.State;
  22 import IR.TypeDescriptor;
  23 import IR.TypeExtension;
  24 import IR.Flat.FKind;
  25 import IR.Flat.FlatCall;
  26 import IR.Flat.FlatElementNode;
  27 import IR.Flat.FlatFieldNode;
  28 import IR.Flat.FlatLiteralNode;
  29 import IR.Flat.FlatMethod;
  30 import IR.Flat.FlatNode;
  31 import IR.Flat.FlatOpNode;
  32 import IR.Flat.FlatSetElementNode;
  33 import IR.Flat.FlatSetFieldNode;
  34 import IR.Flat.TempDescriptor;
  35 import IR.Tree.Modifiers;
  36 import Util.Pair;
  37
  38 public class DefinitelyWrittenCheck {
  39
  40   SSJavaAnalysis ssjava;
  41   State state;
  42   CallGraph callGraph;
  43
  44   int debugcount = 0;
  45
  46   // maps a descriptor to its known dependents: namely
  47   // methods or tasks that call the descriptor's method
  48   // AND are part of this analysis (reachable from main)
  49   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  50
  51   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  52   // previously.
  53   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToMustWriteSet;
  54
  55   // maps a temp descriptor to its heap path
  56   // each temp descriptor has a unique heap path since we do not allow any
  57   // alias.
  58   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  59
  60   // maps a temp descriptor to its composite location
  61   private Hashtable<Descriptor, NTuple<Location>> mapDescriptorToLocationStrPath;
  62
  63   // maps a flat method to the READ that is the set of heap path that is
  64   // expected to be written before method invocation
  65   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToReadSet;
  66
  67   // maps a flat method to the must-write set that is the set of heap path that
  68   // is overwritten on every possible path during method invocation
  69   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMustWriteSet;
  70
  71   // maps a flat method to the DELETE SET that is a set of heap path to shared
  72   // locations that are
  73   // written to but not overwritten by the higher value
  74   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToDeleteSet;
  75
  76   // maps a flat method to the S SET that is a set of heap path to shared
  77   // locations that are overwritten by the higher value
  78   private Hashtable<FlatMethod, SharedLocMappingSet> mapFlatMethodToSharedLocMappingSet;
  79
  80   // maps a flat method to the may-wirte set that is the set of heap path that
  81   // might be written to
  82   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMayWriteSet;
  83
  84   // maps a call site to the read set contributed by all callees
  85   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundReadSet;
  86
  87   // maps a call site to the must write set contributed by all callees
  88   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMustWriteSet;
  89
  90   // maps a call site to the may read set contributed by all callees
  91   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMayWriteSet;
  92
  93   // points to method containing SSJAVA Loop
  94   private MethodDescriptor methodContainingSSJavaLoop;
  95
  96   // maps a flatnode to definitely written analysis mapping M
  97   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>> mapFlatNodetoEventLoopMap;
  98
  99   // maps a method descriptor to its current summary during the analysis
 100   // then analysis reaches fixed-point, this mapping will have the final summary
 101   // for each method descriptor
 102   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
 103
 104   // maps a method descriptor to the merged incoming caller's current
 105   // overwritten status
 106   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
 107
 108   // maps a flat node to current partial results
 109   private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
 110
 111   // maps shared location to the set of descriptors which belong to the shared
 112   // location
 113
 114   // keep current descriptors to visit in fixed-point interprocedural analysis,
 115   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
 116
 117   // when analyzing flatcall, need to re-schedule set of callee
 118   private Set<MethodDescriptor> calleesToEnqueue;
 119
 120   private Set<ReadSummary> possibleCalleeReadSummarySetToCaller;
 121
 122   public static final String arrayElementFieldName = "___element_";
 123   static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
 124
 125   private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
 126
 127   // maps a method descriptor to the merged incoming caller's current
 128   // reading status
 129   // it is for setting clearance flag when all read set is overwritten
 130   private Hashtable<MethodDescriptor, ReadSummary> mapMethodDescriptorToReadSummary;
 131
 132   private MultiSourceMap<Location, Descriptor> mapLocationPathToMayWrittenSet;
 133
 134   private Hashtable<MethodDescriptor, MultiSourceMap<Location, Descriptor>> mapMethodToSharedWriteMapping;
 135
 136   private Hashtable<FlatNode, SharedLocMappingSet> mapFlatNodeToSharedLocMapping;
 137
 138   private Hashtable<Location, Set<Descriptor>> mapSharedLocationToCoverSet;
 139
 140   private LinkedList<MethodDescriptor> sortedDescriptors;
 141
 142   private FlatNode ssjavaLoopEntrance;
 143   private LoopFinder ssjavaLoop;
 144   private Set<FlatNode> loopIncElements;
 145
 146   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
 147   private Set<NTuple<Descriptor>> calleeIntersectBoundMustWriteSet;
 148   private Set<NTuple<Descriptor>> calleeUnionBoundMayWriteSet;
 149   private Set<NTuple<Descriptor>> calleeUnionBoundDeleteSet;
 150   private SharedLocMappingSet calleeIntersectBoundSharedSet;
 151
 152   private Hashtable<Descriptor, Location> mapDescToLocation;
 153
 154   private TempDescriptor LOCAL;
 155
 156   public static int MAXAGE = 1;
 157
 158   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
 159     this.state = state;
 160     this.ssjava = ssjava;
 161     this.callGraph = ssjava.getCallGraph();
 162     this.mapFlatNodeToMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 163     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 164     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
 165     this.mapDescriptorToLocationStrPath = new Hashtable<Descriptor, NTuple<Location>>();
 166     this.mapFlatMethodToReadSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 167     this.mapFlatMethodToMustWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 168     this.mapFlatMethodToMayWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 169     this.mapFlatNodetoEventLoopMap =
 170         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>>();
 171     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 172     this.calleeIntersectBoundMustWriteSet = new HashSet<NTuple<Descriptor>>();
 173     this.calleeUnionBoundMayWriteSet = new HashSet<NTuple<Descriptor>>();
 174
 175     this.mapMethodDescriptorToCompleteClearingSummary =
 176         new Hashtable<MethodDescriptor, ClearingSummary>();
 177     this.mapMethodDescriptorToInitialClearingSummary =
 178         new Hashtable<MethodDescriptor, ClearingSummary>();
 179     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 180     this.calleesToEnqueue = new HashSet<MethodDescriptor>();
 181     this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
 182     this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
 183     this.LOCAL = new TempDescriptor("LOCAL");
 184     this.mapDescToLocation = new Hashtable<Descriptor, Location>();
 185     this.possibleCalleeReadSummarySetToCaller = new HashSet<ReadSummary>();
 186     this.mapMethodDescriptorToReadSummary = new Hashtable<MethodDescriptor, ReadSummary>();
 187     this.mapFlatNodeToBoundReadSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 188     this.mapFlatNodeToBoundMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 189     this.mapFlatNodeToBoundMayWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 190     this.mapSharedLocationToCoverSet = new Hashtable<Location, Set<Descriptor>>();
 191     this.mapFlatNodeToSharedLocMapping = new Hashtable<FlatNode, SharedLocMappingSet>();
 192     this.mapFlatMethodToDeleteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 193     this.calleeUnionBoundDeleteSet = new HashSet<NTuple<Descriptor>>();
 194     this.calleeIntersectBoundSharedSet = new SharedLocMappingSet();
 195     this.mapFlatMethodToSharedLocMappingSet = new Hashtable<FlatMethod, SharedLocMappingSet>();
 196     this.mapLocationPathToMayWrittenSet = new MultiSourceMap<Location, Descriptor>();
 197     this.mapMethodToSharedWriteMapping =
 198         new Hashtable<MethodDescriptor, MultiSourceMap<Location, Descriptor>>();
 199   }
 200
 201   public void definitelyWrittenCheck() {
 202     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 203       initialize();
 204       computeSharedCoverSet();
 205
 206       System.out.println("#");
 207       System.out.println(mapLocationPathToMayWrittenSet);
 208
 209       methodReadWriteSetAnalysis();
 210
 211       // sharedLocAnalysis();
 212
 213       // eventLoopAnalysis();
 214
 215       // XXXXXXX
 216       // methodReadWriteSetAnalysis();
 217       // methodReadWriteSetAnalysisToEventLoopBody();
 218       // eventLoopAnalysis();
 219       // XXXXXXX
 220       // sharedLocationAnalysis();
 221       // checkSharedLocationResult();
 222     }
 223   }
 224
 225   private void sharedLocAnalysis() {
 226
 227     // perform method READ/OVERWRITE analysis
 228     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 229         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 230
 231     // current descriptors to visit in fixed-point interprocedural analysis,
 232     // prioritized by
 233     // dependency in the call graph
 234     methodDescriptorsToVisitStack.clear();
 235
 236     descriptorListToAnalyze.removeFirst();
 237
 238     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 239     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 240
 241     while (!descriptorListToAnalyze.isEmpty()) {
 242       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 243       methodDescriptorsToVisitStack.add(md);
 244     }
 245
 246     // analyze scheduled methods until there are no more to visit
 247     while (!methodDescriptorsToVisitStack.isEmpty()) {
 248       // start to analyze leaf node
 249       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 250       FlatMethod fm = state.getMethodFlat(md);
 251
 252       Set<NTuple<Descriptor>> deleteSet = new HashSet<NTuple<Descriptor>>();
 253
 254       sharedLoc_analyzeMethod(fm, deleteSet);
 255       System.out.println("deleteSet result=" + deleteSet);
 256
 257       Set<NTuple<Descriptor>> prevDeleteSet = mapFlatMethodToDeleteSet.get(fm);
 258
 259       if (!deleteSet.equals(prevDeleteSet)) {
 260         mapFlatMethodToDeleteSet.put(fm, deleteSet);
 261
 262         // results for callee changed, so enqueue dependents caller for
 263         // further
 264         // analysis
 265         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 266         while (depsItr.hasNext()) {
 267           MethodDescriptor methodNext = depsItr.next();
 268           if (!methodDescriptorsToVisitStack.contains(methodNext)
 269               && methodDescriptorToVistSet.contains(methodNext)) {
 270             methodDescriptorsToVisitStack.add(methodNext);
 271           }
 272
 273         }
 274
 275       }
 276
 277     }
 278
 279   }
 280
 281   private void sharedLoc_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> deleteSet) {
 282     if (state.SSJAVADEBUG) {
 283       System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + fm);
 284     }
 285
 286     sharedLoc_analyzeBody(fm, deleteSet, false);
 287
 288   }
 289
 290   private void sharedLoc_analyzeBody(FlatNode startNode, Set<NTuple<Descriptor>> deleteSet,
 291       boolean isEventLoopBody) {
 292
 293     // intraprocedural analysis
 294     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 295     flatNodesToVisit.add(startNode);
 296
 297     while (!flatNodesToVisit.isEmpty()) {
 298       FlatNode fn = flatNodesToVisit.iterator().next();
 299       flatNodesToVisit.remove(fn);
 300
 301       SharedLocMappingSet currSharedSet = new SharedLocMappingSet();
 302
 303       for (int i = 0; i < fn.numPrev(); i++) {
 304         FlatNode prevFn = fn.getPrev(i);
 305         SharedLocMappingSet in = mapFlatNodeToSharedLocMapping.get(prevFn);
 306         if (in != null) {
 307           merge(currSharedSet, in);
 308         }
 309       }
 310
 311       sharedLoc_nodeActions(fn, currSharedSet, deleteSet, isEventLoopBody);
 312
 313       SharedLocMappingSet mustSetPrev = mapFlatNodeToSharedLocMapping.get(fn);
 314       if (!currSharedSet.equals(mustSetPrev)) {
 315         mapFlatNodeToSharedLocMapping.put(fn, currSharedSet);
 316         for (int i = 0; i < fn.numNext(); i++) {
 317           FlatNode nn = fn.getNext(i);
 318           if ((!isEventLoopBody) || loopIncElements.contains(nn)) {
 319             flatNodesToVisit.add(nn);
 320           }
 321
 322         }
 323       }
 324
 325     }
 326
 327   }
 328
 329   private void sharedLoc_nodeActions(FlatNode fn, SharedLocMappingSet curr,
 330       Set<NTuple<Descriptor>> deleteSet, boolean isEventLoopBody) {
 331
 332     SharedLocMappingSet killSet = new SharedLocMappingSet();
 333     SharedLocMappingSet genSet = new SharedLocMappingSet();
 334
 335     TempDescriptor lhs;
 336     TempDescriptor rhs;
 337     FieldDescriptor fld;
 338
 339     switch (fn.kind()) {
 340
 341     case FKind.FlatOpNode: {
 342
 343       if (isEventLoopBody) {
 344         FlatOpNode fon = (FlatOpNode) fn;
 345         lhs = fon.getDest();
 346         rhs = fon.getLeft();
 347
 348         if (!lhs.getSymbol().startsWith("neverused")) {
 349
 350           if (rhs.getType().isImmutable()) {
 351             NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 352
 353             if (rhs.getType().getExtension() instanceof Location
 354                 && lhs.getType().getExtension() instanceof CompositeLocation) {
 355               // rhs is field!
 356               Location rhsLoc = (Location) rhs.getType().getExtension();
 357
 358               CompositeLocation lhsCompLoc = (CompositeLocation) lhs.getType().getExtension();
 359               Location dstLoc = lhsCompLoc.get(lhsCompLoc.getSize() - 1);
 360
 361               NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
 362               for (int i = 0; i < rhsHeapPath.size() - 1; i++) {
 363                 heapPath.add(rhsHeapPath.get(i));
 364               }
 365
 366               NTuple<Descriptor> writeHeapPath = new NTuple<Descriptor>();
 367               writeHeapPath.addAll(heapPath);
 368               writeHeapPath.add(lhs);
 369
 370               System.out.println("VAR WRITE:" + fn);
 371               System.out.println("LHS TYPE EXTENSION=" + lhs.getType().getExtension());
 372               System.out.println("RHS TYPE EXTENSION=" + rhs.getType().getExtension()
 373                   + " HEAPPATH=" + rhsHeapPath);
 374
 375               // computing gen/kill set
 376               computeKILLSetForWrite(curr, heapPath, dstLoc, killSet);
 377               if (!dstLoc.equals(rhsLoc)) {
 378                 computeGENSetForHigherWrite(curr, heapPath, dstLoc, lhs, genSet);
 379                 deleteSet.remove(writeHeapPath);
 380               } else {
 381                 computeGENSetForSharedWrite(curr, heapPath, dstLoc, lhs, genSet);
 382                 deleteSet.add(writeHeapPath);
 383               }
 384
 385             }
 386
 387             // System.out.println("fieldLoc=" + fieldLoc + " srcLoc=" + srcLoc);
 388             System.out.println("KILLSET=" + killSet);
 389             System.out.println("GENSet=" + genSet);
 390             System.out.println("DELETESET=" + deleteSet);
 391
 392           }
 393         }
 394       }
 395
 396     }
 397       break;
 398
 399     case FKind.FlatSetFieldNode:
 400     case FKind.FlatSetElementNode: {
 401
 402       if (fn.kind() == FKind.FlatSetFieldNode) {
 403         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 404         lhs = fsfn.getDst();
 405         fld = fsfn.getField();
 406         rhs = fsfn.getSrc();
 407       } else {
 408         FlatSetElementNode fsen = (FlatSetElementNode) fn;
 409         lhs = fsen.getDst();
 410         rhs = fsen.getSrc();
 411         TypeDescriptor td = lhs.getType().dereference();
 412         fld = getArrayField(td);
 413       }
 414
 415       // shared loc extension
 416       Location srcLoc = getLocation(rhs);
 417       Location fieldLoc = (Location) fld.getType().getExtension();
 418       if (ssjava.isSharedLocation(fieldLoc)) {
 419         // only care the case that loc(f) is shared location
 420         // write(field)
 421         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 422         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 423         fldHeapPath.add(fld);
 424
 425         // computing gen/kill set
 426         computeKILLSetForWrite(curr, lhsHeapPath, fieldLoc, killSet);
 427         if (!fieldLoc.equals(srcLoc)) {
 428           System.out.println("LOC IS DIFFERENT");
 429           computeGENSetForHigherWrite(curr, lhsHeapPath, fieldLoc, fld, genSet);
 430           deleteSet.remove(fldHeapPath);
 431         } else {
 432           computeGENSetForSharedWrite(curr, lhsHeapPath, fieldLoc, fld, genSet);
 433           deleteSet.add(fldHeapPath);
 434         }
 435       }
 436
 437       System.out.println("################");
 438       System.out.println("FIELD WRITE:" + fn);
 439       System.out.println("fieldLoc=" + fieldLoc + " srcLoc=" + srcLoc);
 440       System.out.println("KILLSET=" + killSet);
 441       System.out.println("GENSet=" + genSet);
 442       System.out.println("DELETESET=" + deleteSet);
 443
 444     }
 445       break;
 446
 447     case FKind.FlatCall: {
 448       FlatCall fc = (FlatCall) fn;
 449
 450       bindHeapPathCallerArgWithCaleeParamForSharedLoc(fc);
 451
 452       // generateKILLSetForFlatCall(fc, curr, readWriteKillSet);
 453       // generateGENSetForFlatCall(fc, readWriteGenSet);
 454
 455       // System.out.println
 456       // // only care the case that loc(f) is shared location
 457       // // write(field)
 458       // NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 459       // NTuple<Descriptor> fldHeapPath = new
 460       // NTuple<Descriptor>(lhsHeapPath.getList());
 461       // fldHeapPath.add(fld);
 462       //
 463       // // computing gen/kill set
 464       // computeKILLSetForWrite(curr, lhsHeapPath, fieldLoc, killSet);
 465       // if (!fieldLoc.equals(srcLoc)) {
 466       // System.out.println("LOC IS DIFFERENT");
 467       // computeGENSetForHigherWrite(curr, lhsHeapPath, fieldLoc, fld, genSet);
 468       // deleteSet.remove(fldHeapPath);
 469       // } else {
 470       // computeGENSetForSharedWrite(curr, lhsHeapPath, fieldLoc, fld, genSet);
 471       // deleteSet.add(fldHeapPath);
 472       // }
 473       // ("FLATCALL:" + fn);
 474       // System.out.println("bound DELETE Set=" + calleeUnionBoundDeleteSet);
 475       // // System.out.println("KILLSET=" + KILLSet);
 476       // // System.out.println("GENSet=" + GENSet);
 477       //
 478     }
 479     // break;
 480
 481     }
 482
 483     // computeNewMapping(curr, readWriteKillSet, readWriteGenSet);
 484     // System.out.println("#######" + curr);
 485
 486   }
 487
 488   private void computeKILLSetForWrite(SharedLocMappingSet curr, NTuple<Descriptor> hp,
 489       Location loc, SharedLocMappingSet killSet) {
 490
 491     Set<Descriptor> currWriteSet = curr.getWriteSet(hp, loc);
 492     if (!currWriteSet.isEmpty()) {
 493       killSet.addWriteSet(hp, loc, currWriteSet);
 494     }
 495
 496   }
 497
 498   private void computeGENSetForHigherWrite(SharedLocMappingSet curr, NTuple<Descriptor> hp,
 499       Location loc, Descriptor desc, SharedLocMappingSet genSet) {
 500
 501     Set<Descriptor> genWriteSet = new HashSet<Descriptor>();
 502     genWriteSet.addAll(curr.getWriteSet(hp, loc));
 503     genWriteSet.add(desc);
 504
 505     genSet.addWriteSet(hp, loc, genWriteSet);
 506
 507   }
 508
 509   private void computeGENSetForSharedWrite(SharedLocMappingSet curr, NTuple<Descriptor> hp,
 510       Location loc, Descriptor desc, SharedLocMappingSet genSet) {
 511
 512     Set<Descriptor> genWriteSet = new HashSet<Descriptor>();
 513     genWriteSet.addAll(curr.getWriteSet(hp, loc));
 514     genWriteSet.remove(desc);
 515
 516     if (!genWriteSet.isEmpty()) {
 517       genSet.addWriteSet(hp, loc, genWriteSet);
 518     }
 519   }
 520
 521   private void merge(SharedLocMappingSet currSharedSet, SharedLocMappingSet in) {
 522
 523     Set<NTuple<Descriptor>> hpKeySet = in.getHeapPathKeySet();
 524     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 525       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 526       Set<Location> locSet = in.getLocationKeySet(hpKey);
 527       for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
 528         Location locKey = (Location) iterator2.next();
 529         Set<Descriptor> writeSet = in.getWriteSet(hpKey, locKey);
 530         currSharedSet.intersectWriteSet(hpKey, locKey, writeSet);
 531       }
 532     }
 533
 534   }
 535
 536   private void checkSharedLocationResult() {
 537
 538     // mapping of method containing ssjava loop has the final result of
 539     // shared location analysis
 540
 541     ClearingSummary result =
 542         mapMethodDescriptorToCompleteClearingSummary.get(methodContainingSSJavaLoop);
 543
 544     String str = generateNotClearedResult(result);
 545     if (str.length() > 0) {
 546       throw new Error(
 547           "Following concrete locations of the shared abstract location are not cleared at the same time:\n"
 548               + str);
 549     }
 550
 551   }
 552
 553   private String generateNotClearedResult(ClearingSummary result) {
 554     Set<NTuple<Descriptor>> keySet = result.keySet();
 555
 556     StringBuffer str = new StringBuffer();
 557     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 558       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 559       SharedStatus status = result.get(hpKey);
 560       Hashtable<Location, Pair<Set<Descriptor>, Boolean>> map = status.getMap();
 561       Set<Location> locKeySet = map.keySet();
 562       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 563         Location locKey = (Location) iterator2.next();
 564         if (status.haveWriteEffect(locKey)) {
 565           Pair<Set<Descriptor>, Boolean> pair = map.get(locKey);
 566           if (!pair.getSecond().booleanValue()) {
 567             // not cleared!
 568             str.append("- Concrete locations of the shared location '" + locKey
 569                 + "' are not cleared out, which are reachable through the heap path '" + hpKey
 570                 + ".\n");
 571           }
 572         }
 573       }
 574     }
 575
 576     return str.toString();
 577
 578   }
 579
 580   private void writeReadMapFile() {
 581
 582     String fileName = "SharedLocationReadMap";
 583
 584     try {
 585       BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".txt"));
 586
 587       Set<MethodDescriptor> keySet = mapMethodDescriptorToReadSummary.keySet();
 588       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 589         MethodDescriptor mdKey = (MethodDescriptor) iterator.next();
 590         ReadSummary summary = mapMethodDescriptorToReadSummary.get(mdKey);
 591         bw.write("Method " + mdKey + "::\n");
 592         bw.write(summary + "\n\n");
 593       }
 594       bw.close();
 595     } catch (IOException e) {
 596       e.printStackTrace();
 597     }
 598
 599   }
 600
 601   private void sharedLocationAnalysis() {
 602     // verify that all concrete locations of shared location are cleared out at
 603     // the same time once per the out-most loop
 604
 605     computeSharedCoverSet();
 606
 607     if (state.SSJAVADEBUG) {
 608       writeReadMapFile();
 609     }
 610
 611     // methodDescriptorsToVisitStack.clear();
 612     // methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 613
 614     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 615         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 616
 617     // current descriptors to visit in fixed-point interprocedural analysis,
 618     // prioritized by
 619     // dependency in the call graph
 620     methodDescriptorsToVisitStack.clear();
 621
 622     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 623     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 624
 625     while (!descriptorListToAnalyze.isEmpty()) {
 626       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 627       methodDescriptorsToVisitStack.add(md);
 628     }
 629
 630     // analyze scheduled methods until there are no more to visit
 631     while (!methodDescriptorsToVisitStack.isEmpty()) {
 632       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 633
 634       ClearingSummary completeSummary =
 635           sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 636
 637       ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
 638
 639       if (!completeSummary.equals(prevCompleteSummary)) {
 640
 641         mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 642
 643         // results for callee changed, so enqueue dependents caller for
 644         // further analysis
 645         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 646         while (depsItr.hasNext()) {
 647           MethodDescriptor methodNext = depsItr.next();
 648           if (!methodDescriptorsToVisitStack.contains(methodNext)) {
 649             methodDescriptorsToVisitStack.add(methodNext);
 650           }
 651         }
 652
 653         // if there is set of callee to be analyzed,
 654         // add this set into the top of stack
 655         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 656         while (calleeIter.hasNext()) {
 657           MethodDescriptor mdNext = calleeIter.next();
 658           if (!methodDescriptorsToVisitStack.contains(mdNext)) {
 659             methodDescriptorsToVisitStack.add(mdNext);
 660           }
 661         }
 662         calleesToEnqueue.clear();
 663
 664       }
 665
 666     }
 667
 668   }
 669
 670   private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
 671       boolean onlyVisitSSJavaLoop) {
 672
 673     if (state.SSJAVADEBUG) {
 674       System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + md);
 675     }
 676
 677     FlatMethod fm = state.getMethodFlat(md);
 678
 679     // intraprocedural analysis
 680     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 681
 682     // start a new mapping of partial results for each flat node
 683     mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
 684
 685     if (onlyVisitSSJavaLoop) {
 686       flatNodesToVisit.add(ssjavaLoopEntrance);
 687     } else {
 688       flatNodesToVisit.add(fm);
 689     }
 690
 691     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 692
 693     while (!flatNodesToVisit.isEmpty()) {
 694       FlatNode fn = flatNodesToVisit.iterator().next();
 695       flatNodesToVisit.remove(fn);
 696
 697       ClearingSummary curr = new ClearingSummary();
 698
 699       Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
 700       for (int i = 0; i < fn.numPrev(); i++) {
 701         FlatNode prevFn = fn.getPrev(i);
 702         ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
 703         if (in != null) {
 704           prevSet.add(in);
 705         }
 706       }
 707       mergeSharedLocationAnaylsis(curr, prevSet);
 708
 709       sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 710       ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 711
 712       if (!curr.equals(clearingPrev)) {
 713         mapFlatNodeToClearingSummary.put(fn, curr);
 714
 715         for (int i = 0; i < fn.numNext(); i++) {
 716           FlatNode nn = fn.getNext(i);
 717
 718           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 719             flatNodesToVisit.add(nn);
 720           }
 721
 722         }
 723       }
 724
 725     }
 726
 727     ClearingSummary completeSummary = new ClearingSummary();
 728     Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
 729
 730     if (onlyVisitSSJavaLoop) {
 731       // when analyzing ssjava loop,
 732       // complete summary is merging of all previous nodes of ssjava loop
 733       // entrance
 734       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 735         ClearingSummary frnSummary =
 736             mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
 737         if (frnSummary != null) {
 738           summarySet.add(frnSummary);
 739         }
 740       }
 741     } else {
 742       // merging all exit node summary into the complete summary
 743       if (!returnNodeSet.isEmpty()) {
 744         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 745           FlatNode frn = (FlatNode) iterator.next();
 746           ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
 747           summarySet.add(frnSummary);
 748         }
 749       }
 750     }
 751     mergeSharedLocationAnaylsis(completeSummary, summarySet);
 752
 753     return completeSummary;
 754   }
 755
 756   private void sharedLocation_nodeActions(MethodDescriptor md, FlatNode fn, ClearingSummary curr,
 757       Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 758
 759     TempDescriptor lhs;
 760     TempDescriptor rhs;
 761     FieldDescriptor fld;
 762     switch (fn.kind()) {
 763
 764     case FKind.FlatMethod: {
 765       FlatMethod fm = (FlatMethod) fn;
 766
 767       ClearingSummary summaryFromCaller =
 768           mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
 769
 770       Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 771       if (summaryFromCaller != null) {
 772         inSet.add(summaryFromCaller);
 773         mergeSharedLocationAnaylsis(curr, inSet);
 774       }
 775
 776     }
 777       break;
 778
 779     case FKind.FlatOpNode: {
 780       FlatOpNode fon = (FlatOpNode) fn;
 781       lhs = fon.getDest();
 782       rhs = fon.getLeft();
 783
 784       if (fon.getOp().getOp() == Operation.ASSIGN) {
 785         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 786           // in ssjavaloop, we need to take care about reading local variables!
 787           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 788           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 789           rhsHeapPath.add(LOCAL);
 790           lhsHeapPath.add(LOCAL);
 791           if (!lhs.getSymbol().startsWith("neverused")) {
 792             readLocation(md, curr, rhsHeapPath, getLocation(rhs), rhs);
 793             writeLocation(md, curr, lhsHeapPath, getLocation(lhs), lhs);
 794           }
 795         }
 796       }
 797
 798     }
 799       break;
 800
 801     case FKind.FlatSetFieldNode:
 802     case FKind.FlatSetElementNode: {
 803
 804       // x.f=y
 805
 806       if (fn.kind() == FKind.FlatSetFieldNode) {
 807         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 808         lhs = fsfn.getDst();
 809         fld = fsfn.getField();
 810         rhs = fsfn.getSrc();
 811       } else {
 812         FlatSetElementNode fsen = (FlatSetElementNode) fn;
 813         lhs = fsen.getDst();
 814         rhs = fsen.getSrc();
 815         TypeDescriptor td = lhs.getType().dereference();
 816         fld = getArrayField(td);
 817       }
 818
 819       // write(field)
 820       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 821       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 822       if (fld.getType().isImmutable()) {
 823
 824         writeLocation(md, curr, fldHeapPath, getLocation(fld), fld);
 825
 826         Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
 827         if (desc instanceof FieldDescriptor) {
 828           NTuple<Descriptor> arrayPath = new NTuple<Descriptor>();
 829           for (int i = 0; i < fldHeapPath.size() - 1; i++) {
 830             arrayPath.add(fldHeapPath.get(i));
 831           }
 832           SharedStatus state = getState(curr, arrayPath);
 833           state.setWriteEffect(getLocation(desc));
 834         }
 835
 836       } else {
 837         // updates reference field case:
 838         fldHeapPath.add(fld);
 839         updateWriteEffectOnReferenceField(curr, fldHeapPath);
 840       }
 841
 842     }
 843       break;
 844
 845     case FKind.FlatCall: {
 846
 847       FlatCall fc = (FlatCall) fn;
 848
 849       if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
 850         // ssjava util case!
 851         // have write effects on the first argument
 852
 853         if (fc.getArg(0).getType().isArray()) {
 854           // updates reference field case:
 855           // 2. if there exists a tuple t in sharing summary that starts with
 856           // hp(x) then, set flag of tuple t to 'true'
 857           NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
 858
 859           Location loc = getLocation(fc.getArg(0));
 860           NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
 861           for (int i = 0; i < argHeapPath.size() - 1; i++) {
 862             newHeapPath.add(argHeapPath.get(i));
 863           }
 864           fld = (FieldDescriptor) argHeapPath.get(argHeapPath.size() - 1);
 865           argHeapPath = newHeapPath;
 866
 867           writeLocation(md, curr, argHeapPath, loc, fld);
 868         }
 869
 870       } else {
 871         // find out the set of callees
 872         MethodDescriptor mdCallee = fc.getMethod();
 873         FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 874         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 875         setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
 876
 877         possibleCalleeCompleteSummarySetToCaller.clear();
 878
 879         for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 880           MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 881           FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 882
 883           addDependent(mdPossibleCallee, // callee
 884               md); // caller
 885
 886           calleesToEnqueue.add(mdPossibleCallee);
 887
 888           // updates possible callee's initial summary using caller's current
 889           // writing status
 890           ClearingSummary prevCalleeInitSummary =
 891               mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 892
 893           ClearingSummary calleeInitSummary =
 894               bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 895
 896           Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 897           if (prevCalleeInitSummary != null) {
 898             inSet.add(prevCalleeInitSummary);
 899             mergeSharedLocationAnaylsis(calleeInitSummary, inSet);
 900           }
 901
 902           // if changes, update the init summary
 903           // and reschedule the callee for analysis
 904           if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 905
 906             if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
 907               methodDescriptorsToVisitStack.add(mdPossibleCallee);
 908             }
 909
 910             mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 911           }
 912
 913         }
 914
 915         // contribute callee's writing effects to the caller
 916         mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 917
 918       }
 919
 920     }
 921       break;
 922
 923     case FKind.FlatReturnNode: {
 924       returnNodeSet.add(fn);
 925     }
 926       break;
 927
 928     }
 929
 930   }
 931
 932   private void updateWriteEffectOnReferenceField(ClearingSummary curr, NTuple<Descriptor> heapPath) {
 933
 934     // 2. if there exists a tuple t in sharing summary that starts with
 935     // hp(x) then, set flag of tuple t to 'true'
 936     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 937     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 938       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 939       if (hpKey.startsWith(heapPath)) {
 940         curr.get(hpKey).updateFlag(true);
 941       }
 942     }
 943
 944   }
 945
 946   private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
 947       FlatMethod calleeFlatMethod, ClearingSummary curr) {
 948
 949     ClearingSummary boundSet = new ClearingSummary();
 950
 951     // create mapping from arg idx to its heap paths
 952     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 953         new Hashtable<Integer, NTuple<Descriptor>>();
 954
 955     if (fc.getThis() != null) {
 956       // arg idx is starting from 'this' arg
 957       NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 958       if (thisHeapPath == null) {
 959         // method is called without creating new flat node representing 'this'
 960         thisHeapPath = new NTuple<Descriptor>();
 961         thisHeapPath.add(fc.getThis());
 962       }
 963
 964       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 965     }
 966
 967     for (int i = 0; i < fc.numArgs(); i++) {
 968       TempDescriptor arg = fc.getArg(i);
 969       NTuple<Descriptor> argHeapPath = computePath(arg);
 970       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 971     }
 972
 973     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 974         new Hashtable<Integer, TempDescriptor>();
 975     int offset = 0;
 976     if (calleeFlatMethod.getMethod().isStatic()) {
 977       // static method does not have implicit 'this' arg
 978       offset = 1;
 979     }
 980     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 981       TempDescriptor param = calleeFlatMethod.getParameter(i);
 982       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
 983     }
 984
 985     // binding caller's writing effects to callee's params
 986     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 987       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 988
 989       if (argHeapPath != null) {
 990         // if method is static, the first argument is nulll because static
 991         // method does not have implicit "THIS" arg
 992         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 993
 994         // iterate over caller's writing effect set
 995         Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 996         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 997           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 998           // current element is reachable caller's arg
 999           // so need to bind it to the caller's side and add it to the
1000           // callee's
1001           // init summary
1002           if (hpKey.startsWith(argHeapPath)) {
1003             NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
1004             boundSet.put(boundHeapPath, curr.get(hpKey).clone());
1005           }
1006
1007         }
1008       }
1009
1010     }
1011
1012     // contribute callee's complete summary into the caller's current summary
1013     ClearingSummary calleeCompleteSummary =
1014         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
1015     if (calleeCompleteSummary != null) {
1016       ClearingSummary boundCalleeEfffects = new ClearingSummary();
1017       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1018         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
1019
1020         if (argHeapPath != null) {
1021           // if method is static, the first argument is nulll because static
1022           // method does not have implicit "THIS" arg
1023           TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
1024
1025           // iterate over callee's writing effect set
1026           Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
1027           for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1028             NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1029             // current element is reachable caller's arg
1030             // so need to bind it to the caller's side and add it to the
1031             // callee's
1032             // init summary
1033             if (hpKey.startsWith(calleeParamHeapPath)) {
1034
1035               NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
1036
1037               boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
1038                   .clone());
1039
1040             }
1041           }
1042
1043         }
1044
1045       }
1046       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
1047     }
1048
1049     return boundSet;
1050   }
1051
1052   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
1053
1054     // replace the head of heap path with caller's arg path
1055     // for example, heap path 'param.a.b' in callee's side will be replaced with
1056     // (corresponding arg heap path).a.b for caller's side
1057
1058     NTuple<Descriptor> bound = new NTuple<Descriptor>();
1059
1060     for (int i = 0; i < argHeapPath.size(); i++) {
1061       bound.add(argHeapPath.get(i));
1062     }
1063
1064     for (int i = 1; i < hpKey.size(); i++) {
1065       bound.add(hpKey.get(i));
1066     }
1067
1068     return bound;
1069   }
1070
1071   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
1072       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
1073     // replace the head of caller's heap path with callee's param heap path
1074
1075     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
1076     boundHeapPath.add(calleeParamHeapPath);
1077
1078     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
1079       boundHeapPath.add(effectHeapPath.get(i));
1080     }
1081
1082     return boundHeapPath;
1083   }
1084
1085   private void computeSharedCoverSet() {
1086     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1087         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1088
1089     // current descriptors to visit in fixed-point interprocedural analysis,
1090     // prioritized by
1091     // dependency in the call graph
1092     methodDescriptorsToVisitStack.clear();
1093
1094     descriptorListToAnalyze.removeFirst();
1095
1096     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1097     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1098
1099     while (!descriptorListToAnalyze.isEmpty()) {
1100       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1101       methodDescriptorsToVisitStack.add(md);
1102     }
1103
1104     // analyze scheduled methods until there are no more to visit
1105     while (!methodDescriptorsToVisitStack.isEmpty()) {
1106       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1107       FlatMethod fm = state.getMethodFlat(md);
1108       computeSharedCoverSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
1109     }
1110
1111     computeSharedCoverSetForEventLoop();
1112
1113   }
1114
1115   private void computeSharedCoverSetForEventLoop() {
1116     computeSharedCoverSet_analyzeMethod(state.getMethodFlat(methodContainingSSJavaLoop), true);
1117   }
1118
1119   private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
1120
1121     MethodDescriptor md = fm.getMethod();
1122     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1123
1124     Set<FlatNode> visited = new HashSet<FlatNode>();
1125
1126     if (onlyVisitSSJavaLoop) {
1127       flatNodesToVisit.add(ssjavaLoopEntrance);
1128     } else {
1129       flatNodesToVisit.add(fm);
1130     }
1131
1132     while (!flatNodesToVisit.isEmpty()) {
1133       FlatNode fn = flatNodesToVisit.iterator().next();
1134       flatNodesToVisit.remove(fn);
1135       visited.add(fn);
1136
1137       computeSharedCoverSet_nodeActions(md, fn);
1138
1139       for (int i = 0; i < fn.numNext(); i++) {
1140         FlatNode nn = fn.getNext(i);
1141
1142         if (!visited.contains(nn)) {
1143           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
1144             flatNodesToVisit.add(nn);
1145           }
1146         }
1147
1148       }
1149
1150     }
1151
1152   }
1153
1154   private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn) {
1155     TempDescriptor lhs;
1156     TempDescriptor rhs;
1157     FieldDescriptor fld;
1158
1159     switch (fn.kind()) {
1160
1161     case FKind.FlatLiteralNode: {
1162       FlatLiteralNode fln = (FlatLiteralNode) fn;
1163       lhs = fln.getDst();
1164
1165       if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused")
1166           && !lhs.getSymbol().startsWith("srctmp")) {
1167         // only need to care about composite location case here
1168         if (lhs.getType().getExtension() instanceof SSJavaType) {
1169           CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc();
1170           Location lastLocElement = compLoc.get(compLoc.getSize() - 1);
1171           // check if the last one is shared loc
1172           if (ssjava.isSharedLocation(lastLocElement)) {
1173             addSharedLocDescriptor(lastLocElement, lhs);
1174           }
1175         }
1176       }
1177
1178     }
1179       break;
1180
1181     case FKind.FlatOpNode: {
1182       FlatOpNode fon = (FlatOpNode) fn;
1183       // for a normal assign node, need to propagate lhs's location path to
1184       // rhs
1185       if (fon.getOp().getOp() == Operation.ASSIGN) {
1186         rhs = fon.getLeft();
1187         lhs = fon.getDest();
1188
1189         if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused")
1190             && !lhs.getSymbol().startsWith("srctmp") && !lhs.getSymbol().startsWith("leftop")
1191             && !lhs.getSymbol().startsWith("rightop")) {
1192
1193           NTuple<Location> locTuple = deriveLocationTuple(md, rhs);
1194           mapLocationPathToMayWrittenSet.put(locTuple, null, lhs);
1195           addMayWrittenSet(md, locTuple, lhs);
1196
1197         }
1198
1199         if (mapDescriptorToLocationStrPath.containsKey(rhs)) {
1200           mapDescriptorToLocationStrPath.put(lhs, mapDescriptorToLocationStrPath.get(rhs));
1201         } else {
1202           if (rhs.getType().getExtension() instanceof SSJavaType) {
1203             NTuple<Location> locTuple =
1204                 ((SSJavaType) rhs.getType().getExtension()).getCompLoc().getTuple();
1205             mapDescriptorToLocationStrPath.put(lhs, locTuple);
1206           }
1207         }
1208
1209       }
1210     }
1211       break;
1212
1213     case FKind.FlatSetFieldNode:
1214     case FKind.FlatSetElementNode: {
1215
1216       // x.f=y;
1217
1218       if (fn.kind() == FKind.FlatSetFieldNode) {
1219         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1220         lhs = fsfn.getDst();
1221         fld = fsfn.getField();
1222         rhs = fsfn.getSrc();
1223       } else {
1224         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1225         lhs = fsen.getDst();
1226         rhs = fsen.getSrc();
1227         TypeDescriptor td = lhs.getType().dereference();
1228         fld = getArrayField(td);
1229       }
1230
1231       Location fieldLocation = (Location) fld.getType().getExtension();
1232       if (ssjava.isSharedLocation(fieldLocation)) {
1233         addSharedLocDescriptor(fieldLocation, fld);
1234
1235         System.out.println("FIELD WRITE FN=" + fn);
1236         NTuple<Location> locTuple = deriveLocationTuple(md, lhs);
1237         locTuple.addAll(deriveLocationTuple(md, fld));
1238         System.out.println("LOC TUPLE=" + locTuple);
1239
1240         // mapLocationPathToMayWrittenSet.put(locTuple, null, fld);
1241         addMayWrittenSet(md, locTuple, fld);
1242       }
1243
1244     }
1245       break;
1246
1247     case FKind.FlatElementNode:
1248     case FKind.FlatFieldNode: {
1249
1250       // x=y.f;
1251
1252       if (fn.kind() == FKind.FlatFieldNode) {
1253         FlatFieldNode ffn = (FlatFieldNode) fn;
1254         lhs = ffn.getDst();
1255         rhs = ffn.getSrc();
1256         fld = ffn.getField();
1257       } else {
1258         FlatElementNode fen = (FlatElementNode) fn;
1259         lhs = fen.getDst();
1260         rhs = fen.getSrc();
1261         TypeDescriptor td = rhs.getType().dereference();
1262         fld = getArrayField(td);
1263       }
1264
1265       if (fld.isFinal()) {
1266         // if field is final no need to check
1267         break;
1268       }
1269
1270       NTuple<Location> locTuple = deriveLocationTuple(md, rhs);
1271       locTuple.addAll(deriveLocationTuple(md, fld));
1272       mapDescriptorToLocationStrPath.put(lhs, locTuple);
1273
1274     }
1275       break;
1276
1277     case FKind.FlatCall: {
1278
1279       // System.out.println("###FLATCALL=" + fn);
1280       FlatCall fc = (FlatCall) fn;
1281       bindLocationPathCallerArgWithCalleeParam(md, fc);
1282
1283     }
1284       break;
1285
1286     }
1287   }
1288
1289   private void addMayWrittenSet(MethodDescriptor md, NTuple<Location> locTuple, Descriptor d) {
1290
1291     MultiSourceMap<Location, Descriptor> map = mapMethodToSharedWriteMapping.get(md);
1292     if (map == null) {
1293       map = new MultiSourceMap<Location, Descriptor>();
1294       mapMethodToSharedWriteMapping.put(md, map);
1295     }
1296
1297     Set<Descriptor> writeSet = map.get(locTuple);
1298     if (writeSet == null) {
1299       writeSet = new HashSet<Descriptor>();
1300       map.put(locTuple, writeSet);
1301     }
1302     writeSet.add(d);
1303
1304     System.out.println("ADD WRITE DESC=" + d + " TO locTuple=" + locTuple);
1305   }
1306
1307   private void bindLocationPathCallerArgWithCalleeParam(MethodDescriptor mdCaller, FlatCall fc) {
1308
1309     if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1310       // ssjava util case!
1311       // have write effects on the first argument
1312       TempDescriptor arg = fc.getArg(0);
1313       NTuple<Location> argLocationPath = deriveLocationTuple(mdCaller, arg);
1314       NTuple<Descriptor> argHeapPath = computePath(arg);
1315       mapLocationPathToMayWrittenSet.put(argLocationPath, null,
1316           argHeapPath.get(argHeapPath.size() - 1));
1317
1318     } else {
1319
1320       // if arg is not primitive type, we need to propagate maywritten set to
1321       // the caller's location path
1322
1323       MethodDescriptor mdCallee = fc.getMethod();
1324       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1325       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1326
1327       // create mapping from arg idx to its heap paths
1328       Hashtable<Integer, NTuple<Location>> mapArgIdx2CallerAgLocationStrPath =
1329           new Hashtable<Integer, NTuple<Location>>();
1330
1331       // arg idx is starting from 'this' arg
1332       if (fc.getThis() != null) {
1333         NTuple<Location> thisLocationPath = deriveLocationTuple(mdCaller, fc.getThis());
1334         mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(0), thisLocationPath);
1335       }
1336
1337       Hashtable<Integer, Set<Descriptor>> mapParamIdx2WriteSet =
1338           new Hashtable<Integer, Set<Descriptor>>();
1339
1340       for (int i = 0; i < fc.numArgs() + 1; i++) {
1341         mapParamIdx2WriteSet.put(Integer.valueOf(i), new HashSet<Descriptor>());
1342       }
1343
1344       for (int i = 0; i < fc.numArgs(); i++) {
1345         TempDescriptor arg = fc.getArg(i);
1346         NTuple<Location> argLocationPath = deriveLocationTuple(mdCaller, arg);
1347         mapArgIdx2CallerAgLocationStrPath.put(Integer.valueOf(i + 1), argLocationPath);
1348       }
1349
1350       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1351         MethodDescriptor callee = (MethodDescriptor) iterator.next();
1352         FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1353
1354         // binding caller's args and callee's params
1355
1356         Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1357             new Hashtable<Integer, TempDescriptor>();
1358         int offset = 0;
1359         if (calleeFlatMethod.getMethod().isStatic()) {
1360           // static method does not have implicit 'this' arg
1361           offset = 1;
1362         }
1363         for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1364           TempDescriptor param = calleeFlatMethod.getParameter(i);
1365           mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1366         }
1367
1368         Set<Integer> keySet = mapArgIdx2CallerAgLocationStrPath.keySet();
1369         for (Iterator iterator2 = keySet.iterator(); iterator2.hasNext();) {
1370           Integer idx = (Integer) iterator2.next();
1371           NTuple<Location> callerArgLocationStrPath = mapArgIdx2CallerAgLocationStrPath.get(idx);
1372
1373           TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1374           NTuple<Location> calleeLocationPath = deriveLocationTuple(mdCallee, calleeParam);
1375
1376           // System.out.println("#createNewMappingOfMayWrittenSet callee=" +
1377           // callee
1378           // + " callerArgLocationStrPath=" + callerArgLocationStrPath +
1379           // "calleeLocationPath="
1380           // + calleeLocationPath + " idx=" + idx + " writeset=" +
1381           // mapParamIdx2WriteSet.get(idx));
1382           createNewMappingOfMayWrittenSet(callee, callerArgLocationStrPath, calleeLocationPath,
1383               mapParamIdx2WriteSet.get(idx));
1384
1385         }
1386
1387       }
1388
1389     }
1390
1391   }
1392
1393   private void createNewMappingOfMayWrittenSet(MethodDescriptor callee,
1394       NTuple<Location> callerPath, NTuple<Location> calleeParamPath, Set<Descriptor> writeSet) {
1395
1396     // propagate may-written-set associated with the key that is started with
1397     // calleepath to the caller
1398     // 1) makes a new key by combining caller path and callee path(except local
1399     // loc element of param)
1400     // 2) create new mapping of may-written-set of callee path to caller path
1401
1402     // extract all may written effect accessed through callee param path
1403     MultiSourceMap<Location, Descriptor> mapping = mapMethodToSharedWriteMapping.get(callee);
1404
1405     if (mapping == null) {
1406       return;
1407     }
1408
1409     Hashtable<NTuple<Location>, Set<Descriptor>> paramMapping =
1410         mapping.getMappingByStartedWith(calleeParamPath);
1411
1412     Set<NTuple<Location>> calleeKeySet = mapping.keySet();
1413     for (Iterator iterator = calleeKeySet.iterator(); iterator.hasNext();) {
1414       NTuple<Location> calleeKey = (NTuple<Location>) iterator.next();
1415       Set<Descriptor> calleeMayWriteSet = paramMapping.get(calleeKey);
1416
1417       if (calleeMayWriteSet != null) {
1418         writeSet.addAll(calleeMayWriteSet);
1419
1420         NTuple<Location> newKey = new NTuple<Location>();
1421         newKey.addAll(callerPath);
1422         // need to replace the local location with the caller's path so skip the
1423         // local location of the parameter
1424         for (int i = 1; i < calleeKey.size(); i++) {
1425           newKey.add(calleeKey.get(i));
1426         }
1427
1428         System.out.println("calleeParamPath=" + calleeParamPath + " newKey=" + newKey
1429             + " maywriteSet=" + writeSet);
1430         mapLocationPathToMayWrittenSet.put(calleeKey, newKey, writeSet);
1431       }
1432
1433     }
1434
1435   }
1436
1437   private void addSharedLocDescriptor(Location sharedLoc, Descriptor desc) {
1438
1439     Set<Descriptor> descSet = mapSharedLocationToCoverSet.get(sharedLoc);
1440     if (descSet == null) {
1441       descSet = new HashSet<Descriptor>();
1442       mapSharedLocationToCoverSet.put(sharedLoc, descSet);
1443     }
1444
1445     descSet.add(desc);
1446
1447   }
1448
1449   private boolean hasReadingEffectOnSharedLocation(MethodDescriptor md, NTuple<Descriptor> hp,
1450       Location loc, Descriptor d) {
1451
1452     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1453
1454     if (summary != null) {
1455       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1456       if (map != null) {
1457         Set<Descriptor> descSec = map.get(loc);
1458         if (descSec != null) {
1459           return descSec.contains(d);
1460         }
1461       }
1462     }
1463     return false;
1464
1465   }
1466
1467   private Location getLocation(Descriptor d) {
1468
1469     System.out.println("GETLOCATION d=" + d + " d=" + d.getClass());
1470
1471     if (d instanceof FieldDescriptor) {
1472       TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
1473       if (te != null) {
1474         return (Location) te;
1475       }
1476     } else {
1477       assert d instanceof TempDescriptor;
1478       TempDescriptor td = (TempDescriptor) d;
1479
1480       TypeExtension te = td.getType().getExtension();
1481       if (te != null) {
1482         if (te instanceof SSJavaType) {
1483           SSJavaType ssType = (SSJavaType) te;
1484           CompositeLocation comp = ssType.getCompLoc();
1485           return comp.get(comp.getSize() - 1);
1486         } else {
1487           return (Location) te;
1488         }
1489       }
1490     }
1491
1492     return mapDescToLocation.get(d);
1493   }
1494
1495   private void writeLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1496       Location loc, Descriptor d) {
1497
1498     SharedStatus state = getState(curr, hp);
1499     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1500       // 1. add field x to the clearing set
1501
1502       state.addVar(loc, d);
1503
1504       // 3. if the set v contains all of variables belonging to the shared
1505       // location, set flag to true
1506       if (isOverWrittenAllDescsOfSharedLoc(md, hp, loc, state.getVarSet(loc))) {
1507         state.updateFlag(loc, true);
1508       }
1509     }
1510     state.setWriteEffect(loc);
1511
1512   }
1513
1514   private boolean isOverWrittenAllDescsOfSharedLoc(MethodDescriptor md, NTuple<Descriptor> hp,
1515       Location loc, Set<Descriptor> writtenSet) {
1516
1517     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1518
1519     if (summary != null) {
1520       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1521       if (map != null) {
1522         Set<Descriptor> descSet = map.get(loc);
1523         if (descSet != null) {
1524           return writtenSet.containsAll(descSet);
1525         }
1526       }
1527     }
1528     return false;
1529   }
1530
1531   private void readLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1532       Location loc, Descriptor d) {
1533     // remove reading var x from written set
1534     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1535       SharedStatus state = getState(curr, hp);
1536       state.removeVar(loc, d);
1537     }
1538   }
1539
1540   private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
1541     SharedStatus state = curr.get(hp);
1542     if (state == null) {
1543       state = new SharedStatus();
1544       curr.put(hp, state);
1545     }
1546     return state;
1547   }
1548
1549   private void eventLoopAnalysis() {
1550     // perform second stage analysis: intraprocedural analysis ensure that
1551     // all
1552     // variables are definitely written in-between the same read
1553
1554     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1555     flatNodesToVisit.add(ssjavaLoopEntrance);
1556
1557     while (!flatNodesToVisit.isEmpty()) {
1558       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1559       flatNodesToVisit.remove(fn);
1560
1561       Hashtable<NTuple<Descriptor>, Set<WriteAge>> prev = mapFlatNodetoEventLoopMap.get(fn);
1562
1563       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr =
1564           new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1565       for (int i = 0; i < fn.numPrev(); i++) {
1566         FlatNode nn = fn.getPrev(i);
1567         Hashtable<NTuple<Descriptor>, Set<WriteAge>> in = mapFlatNodetoEventLoopMap.get(nn);
1568         if (in != null) {
1569           union(curr, in);
1570         }
1571       }
1572
1573       eventLoopAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
1574
1575       // if a new result, schedule forward nodes for analysis
1576       if (!curr.equals(prev)) {
1577         mapFlatNodetoEventLoopMap.put(fn, curr);
1578
1579         for (int i = 0; i < fn.numNext(); i++) {
1580           FlatNode nn = fn.getNext(i);
1581           if (loopIncElements.contains(nn)) {
1582             flatNodesToVisit.add(nn);
1583           }
1584
1585         }
1586       }
1587     }
1588   }
1589
1590   private void union(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1591       Hashtable<NTuple<Descriptor>, Set<WriteAge>> in) {
1592
1593     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1594     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1595       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1596       Set<WriteAge> inSet = in.get(inKey);
1597
1598       Set<WriteAge> currSet = curr.get(inKey);
1599
1600       if (currSet == null) {
1601         currSet = new HashSet<WriteAge>();
1602         curr.put(inKey, currSet);
1603       }
1604       currSet.addAll(inSet);
1605     }
1606
1607   }
1608
1609   private void eventLoopAnalysis_nodeAction(FlatNode fn,
1610       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, FlatNode loopEntrance) {
1611
1612     Hashtable<NTuple<Descriptor>, Set<WriteAge>> readWriteKillSet =
1613         new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1614     Hashtable<NTuple<Descriptor>, Set<WriteAge>> readWriteGenSet =
1615         new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1616
1617     if (fn.equals(loopEntrance)) {
1618       // it reaches loop entrance: changes all flag to true
1619       Set<NTuple<Descriptor>> keySet = curr.keySet();
1620       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1621         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1622         Set<WriteAge> writeAgeSet = curr.get(key);
1623
1624         Set<WriteAge> incSet = new HashSet<WriteAge>();
1625         incSet.addAll(writeAgeSet);
1626         writeAgeSet.clear();
1627
1628         for (Iterator iterator2 = incSet.iterator(); iterator2.hasNext();) {
1629           WriteAge writeAge = (WriteAge) iterator2.next();
1630           WriteAge newWriteAge = writeAge.copy();
1631           newWriteAge.inc();
1632           writeAgeSet.add(newWriteAge);
1633         }
1634
1635       }
1636       // System.out.println("EVENT LOOP ENTRY=" + curr);
1637
1638     } else {
1639       TempDescriptor lhs;
1640       TempDescriptor rhs;
1641       FieldDescriptor fld;
1642
1643       switch (fn.kind()) {
1644
1645       case FKind.FlatOpNode: {
1646         FlatOpNode fon = (FlatOpNode) fn;
1647         lhs = fon.getDest();
1648         rhs = fon.getLeft();
1649
1650         if (!lhs.getSymbol().startsWith("neverused")) {
1651           NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1652           if (!rhs.getType().isImmutable()) {
1653             mapHeapPath.put(lhs, rhsHeapPath);
1654           } else {
1655             // write(lhs)
1656             // NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1657             NTuple<Descriptor> path = new NTuple<Descriptor>();
1658             path.add(lhs);
1659
1660             // System.out.println("WRITE VARIABLE=" + path + " from=" + lhs);
1661
1662             computeKILLSetForWrite(curr, path, readWriteKillSet);
1663             computeGENSetForWrite(path, readWriteGenSet);
1664
1665             // System.out.println("#VARIABLE WRITE:" + fn);
1666             // System.out.println("#KILLSET=" + KILLSet);
1667             // System.out.println("#GENSet=" + GENSet);
1668
1669           }
1670         }
1671
1672       }
1673         break;
1674
1675       case FKind.FlatFieldNode:
1676       case FKind.FlatElementNode: {
1677
1678         if (fn.kind() == FKind.FlatFieldNode) {
1679           FlatFieldNode ffn = (FlatFieldNode) fn;
1680           lhs = ffn.getDst();
1681           rhs = ffn.getSrc();
1682           fld = ffn.getField();
1683         } else {
1684           FlatElementNode fen = (FlatElementNode) fn;
1685           lhs = fen.getDst();
1686           rhs = fen.getSrc();
1687           TypeDescriptor td = rhs.getType().dereference();
1688           fld = getArrayField(td);
1689         }
1690
1691         // read field
1692         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1693         NTuple<Descriptor> fldHeapPath;
1694         if (srcHeapPath != null) {
1695           fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1696         } else {
1697           // if srcHeapPath is null, it is static reference
1698           fldHeapPath = new NTuple<Descriptor>();
1699           fldHeapPath.add(rhs);
1700         }
1701         fldHeapPath.add(fld);
1702
1703         Set<WriteAge> writeAgeSet = curr.get(fldHeapPath);
1704         checkWriteAgeSet(writeAgeSet, fldHeapPath, fn);
1705
1706       }
1707         break;
1708
1709       case FKind.FlatSetFieldNode:
1710       case FKind.FlatSetElementNode: {
1711
1712         if (fn.kind() == FKind.FlatSetFieldNode) {
1713           FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1714           lhs = fsfn.getDst();
1715           fld = fsfn.getField();
1716         } else {
1717           FlatSetElementNode fsen = (FlatSetElementNode) fn;
1718           lhs = fsen.getDst();
1719           rhs = fsen.getSrc();
1720           TypeDescriptor td = lhs.getType().dereference();
1721           fld = getArrayField(td);
1722         }
1723
1724         // write(field)
1725         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1726         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1727         fldHeapPath.add(fld);
1728
1729         computeKILLSetForWrite(curr, fldHeapPath, readWriteKillSet);
1730         computeGENSetForWrite(fldHeapPath, readWriteGenSet);
1731
1732         // System.out.println("FIELD WRITE:" + fn);
1733         // System.out.println("KILLSET=" + KILLSet);
1734         // System.out.println("GENSet=" + GENSet);
1735
1736       }
1737         break;
1738
1739       case FKind.FlatCall: {
1740         FlatCall fc = (FlatCall) fn;
1741
1742         generateKILLSetForFlatCall(fc, curr, readWriteKillSet);
1743         generateGENSetForFlatCall(fc, readWriteGenSet);
1744
1745         // System.out.println("FLATCALL:" + fn);
1746         // System.out.println("KILLSET=" + KILLSet);
1747         // System.out.println("GENSet=" + GENSet);
1748
1749       }
1750         break;
1751
1752       }
1753
1754       computeNewMapping(curr, readWriteKillSet, readWriteGenSet);
1755       // System.out.println("#######" + curr);
1756
1757     }
1758
1759   }
1760
1761   private void checkWriteAgeSet(Set<WriteAge> writeAgeSet, NTuple<Descriptor> path, FlatNode fn) {
1762     if (writeAgeSet != null) {
1763       for (Iterator iterator = writeAgeSet.iterator(); iterator.hasNext();) {
1764         WriteAge writeAge = (WriteAge) iterator.next();
1765         if (writeAge.getAge() >= MAXAGE) {
1766           throw new Error(
1767               "Memory location, which is reachable through references "
1768                   + path
1769                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1770                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1771                   + fn.getNumLine());
1772         }
1773       }
1774     }
1775   }
1776
1777   private void generateGENSetForFlatCall(FlatCall fc,
1778       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1779
1780     Set<NTuple<Descriptor>> boundMayWriteSet = mapFlatNodeToBoundMayWriteSet.get(fc);
1781
1782     for (Iterator iterator = boundMayWriteSet.iterator(); iterator.hasNext();) {
1783       NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1784       // TODO: shared location
1785       Set<WriteAge> set = new HashSet<WriteAge>();
1786       set.add(new WriteAge(0));
1787       GENSet.put(key, set);
1788     }
1789
1790   }
1791
1792   private void generateKILLSetForFlatCall(FlatCall fc,
1793       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1794       Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1795
1796     Set<NTuple<Descriptor>> boundMustWriteSet = mapFlatNodeToBoundMustWriteSet.get(fc);
1797
1798     for (Iterator iterator = boundMustWriteSet.iterator(); iterator.hasNext();) {
1799       NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1800       // TODO: shared location
1801       if (curr.get(key) != null) {
1802         KILLSet.put(key, curr.get(key));
1803       }
1804     }
1805
1806   }
1807
1808   private void computeNewMapping(SharedLocMappingSet curr, SharedLocMappingSet KILLSet,
1809       SharedLocMappingSet GENSet) {
1810     curr.kill(KILLSet);
1811     curr.add(GENSet);
1812   }
1813
1814   private void computeNewMapping(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1815       Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet,
1816       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1817
1818     for (Enumeration<NTuple<Descriptor>> e = KILLSet.keys(); e.hasMoreElements();) {
1819       NTuple<Descriptor> key = e.nextElement();
1820
1821       Set<WriteAge> writeAgeSet = curr.get(key);
1822       if (writeAgeSet == null) {
1823         writeAgeSet = new HashSet<WriteAge>();
1824         curr.put(key, writeAgeSet);
1825       }
1826       writeAgeSet.removeAll(KILLSet.get(key));
1827     }
1828
1829     for (Enumeration<NTuple<Descriptor>> e = GENSet.keys(); e.hasMoreElements();) {
1830       NTuple<Descriptor> key = e.nextElement();
1831       curr.put(key, GENSet.get(key));
1832     }
1833
1834   }
1835
1836   private void computeGENSetForWrite(NTuple<Descriptor> fldHeapPath,
1837       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1838
1839     // generate write age 0 for the field being written to
1840     Set<WriteAge> writeAgeSet = new HashSet<WriteAge>();
1841     writeAgeSet.add(new WriteAge(0));
1842     GENSet.put(fldHeapPath, writeAgeSet);
1843
1844   }
1845
1846   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1847       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1848     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1849     if (gen == null) {
1850       gen = new Hashtable<FlatNode, Boolean>();
1851       curr.put(hp, gen);
1852     }
1853     Boolean currentStatus = gen.get(fn);
1854     if (currentStatus == null) {
1855       gen.put(fn, Boolean.FALSE);
1856     } else {
1857       checkFlag(currentStatus.booleanValue(), fn, hp);
1858     }
1859
1860   }
1861
1862   private void computeKILLSetForWrite(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1863       NTuple<Descriptor> hp, Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1864
1865     // removes all of heap path that starts with prefix 'hp'
1866     // since any reference overwrite along heap path gives overwriting side
1867     // effects on the value
1868
1869     Set<NTuple<Descriptor>> keySet = curr.keySet();
1870     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1871       NTuple<Descriptor> key = iter.next();
1872       if (key.startsWith(hp)) {
1873         KILLSet.put(key, curr.get(key));
1874       }
1875     }
1876
1877   }
1878
1879   private void bindHeapPathCallerArgWithCalleeParam(FlatCall fc) {
1880     // compute all possible callee set
1881     // transform all READ/WRITE set from the any possible
1882     // callees to the caller
1883     calleeUnionBoundReadSet.clear();
1884     calleeIntersectBoundMustWriteSet.clear();
1885     calleeUnionBoundMayWriteSet.clear();
1886
1887     if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1888       // ssjava util case!
1889       // have write effects on the first argument
1890       TempDescriptor arg = fc.getArg(0);
1891       NTuple<Descriptor> argHeapPath = computePath(arg);
1892       calleeIntersectBoundMustWriteSet.add(argHeapPath);
1893       calleeUnionBoundMayWriteSet.add(argHeapPath);
1894     } else {
1895       MethodDescriptor mdCallee = fc.getMethod();
1896       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1897       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1898
1899       // create mapping from arg idx to its heap paths
1900       Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1901           new Hashtable<Integer, NTuple<Descriptor>>();
1902
1903       // arg idx is starting from 'this' arg
1904       if (fc.getThis() != null) {
1905         NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1906         if (thisHeapPath == null) {
1907           // method is called without creating new flat node representing 'this'
1908           thisHeapPath = new NTuple<Descriptor>();
1909           thisHeapPath.add(fc.getThis());
1910         }
1911
1912         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1913       }
1914
1915       for (int i = 0; i < fc.numArgs(); i++) {
1916         TempDescriptor arg = fc.getArg(i);
1917         NTuple<Descriptor> argHeapPath = computePath(arg);
1918         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1919       }
1920
1921       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1922         MethodDescriptor callee = (MethodDescriptor) iterator.next();
1923         FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1924
1925         // binding caller's args and callee's params
1926
1927         Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToReadSet.get(calleeFlatMethod);
1928         if (calleeReadSet == null) {
1929           calleeReadSet = new HashSet<NTuple<Descriptor>>();
1930           mapFlatMethodToReadSet.put(calleeFlatMethod, calleeReadSet);
1931         }
1932
1933         Set<NTuple<Descriptor>> calleeMustWriteSet =
1934             mapFlatMethodToMustWriteSet.get(calleeFlatMethod);
1935
1936         if (calleeMustWriteSet == null) {
1937           calleeMustWriteSet = new HashSet<NTuple<Descriptor>>();
1938           mapFlatMethodToMustWriteSet.put(calleeFlatMethod, calleeMustWriteSet);
1939         }
1940
1941         Set<NTuple<Descriptor>> calleeMayWriteSet =
1942             mapFlatMethodToMayWriteSet.get(calleeFlatMethod);
1943
1944         if (calleeMayWriteSet == null) {
1945           calleeMayWriteSet = new HashSet<NTuple<Descriptor>>();
1946           mapFlatMethodToMayWriteSet.put(calleeFlatMethod, calleeMayWriteSet);
1947         }
1948
1949         Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1950             new Hashtable<Integer, TempDescriptor>();
1951         int offset = 0;
1952         if (calleeFlatMethod.getMethod().isStatic()) {
1953           // static method does not have implicit 'this' arg
1954           offset = 1;
1955         }
1956         for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1957           TempDescriptor param = calleeFlatMethod.getParameter(i);
1958           mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1959         }
1960
1961         Set<NTuple<Descriptor>> calleeBoundReadSet =
1962             bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1963         // union of the current read set and the current callee's
1964         // read set
1965         calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1966
1967         Set<NTuple<Descriptor>> calleeBoundMustWriteSet =
1968             bindSet(calleeMustWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1969         // intersection of the current overwrite set and the current
1970         // callee's
1971         // overwrite set
1972         merge(calleeIntersectBoundMustWriteSet, calleeBoundMustWriteSet);
1973
1974         Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1975             bindSet(calleeMayWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1976         calleeUnionBoundMayWriteSet.addAll(boundWriteSetFromCallee);
1977       }
1978
1979     }
1980
1981   }
1982
1983   private void bindHeapPathCallerArgWithCaleeParamForSharedLoc(FlatCall fc) {
1984     // compute all possible callee set
1985     // transform all DELETE set from the any possible
1986     // callees to the caller
1987     calleeUnionBoundDeleteSet.clear();
1988     calleeIntersectBoundSharedSet.clear();
1989
1990     MethodDescriptor mdCallee = fc.getMethod();
1991     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1992     setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1993
1994     // create mapping from arg idx to its heap paths
1995     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1996         new Hashtable<Integer, NTuple<Descriptor>>();
1997
1998     // arg idx is starting from 'this' arg
1999     if (fc.getThis() != null) {
2000       NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
2001       if (thisHeapPath == null) {
2002         // method is called without creating new flat node representing 'this'
2003         thisHeapPath = new NTuple<Descriptor>();
2004         thisHeapPath.add(fc.getThis());
2005       }
2006
2007       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
2008     }
2009
2010     for (int i = 0; i < fc.numArgs(); i++) {
2011       TempDescriptor arg = fc.getArg(i);
2012       NTuple<Descriptor> argHeapPath = computePath(arg);
2013       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
2014     }
2015
2016     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
2017       MethodDescriptor callee = (MethodDescriptor) iterator.next();
2018       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
2019
2020       // binding caller's args and callee's params
2021
2022       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToDeleteSet.get(calleeFlatMethod);
2023       if (calleeReadSet == null) {
2024         calleeReadSet = new HashSet<NTuple<Descriptor>>();
2025         mapFlatMethodToDeleteSet.put(calleeFlatMethod, calleeReadSet);
2026       }
2027
2028       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
2029           new Hashtable<Integer, TempDescriptor>();
2030       int offset = 0;
2031       if (calleeFlatMethod.getMethod().isStatic()) {
2032         // static method does not have implicit 'this' arg
2033         offset = 1;
2034       }
2035       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
2036         TempDescriptor param = calleeFlatMethod.getParameter(i);
2037         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
2038       }
2039
2040       Set<NTuple<Descriptor>> calleeBoundDeleteSet =
2041           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
2042       // union of the current read set and the current callee's
2043       // read set
2044       calleeUnionBoundDeleteSet.addAll(calleeBoundDeleteSet);
2045
2046       SharedLocMappingSet calleeSharedLocMap =
2047           mapFlatMethodToSharedLocMappingSet.get(calleeFlatMethod);
2048
2049       Set<NTuple<Descriptor>> calleeHeapPathKeySet = calleeSharedLocMap.getHeapPathKeySet();
2050
2051       for (Iterator iterator2 = calleeHeapPathKeySet.iterator(); iterator2.hasNext();) {
2052         NTuple<Descriptor> calleeHeapPathKey = (NTuple<Descriptor>) iterator2.next();
2053
2054         NTuple<Descriptor> calleeBoundHeapPathKey =
2055             bind(calleeHeapPathKey, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
2056
2057         Set<Location> calleeLocSet = calleeSharedLocMap.getLocationKeySet(calleeHeapPathKey);
2058
2059         for (Iterator iterator3 = calleeLocSet.iterator(); iterator3.hasNext();) {
2060           Location calleeLocKey = (Location) iterator3.next();
2061           Set<Descriptor> calleeWriteSet =
2062               calleeSharedLocMap.getWriteSet(calleeHeapPathKey, calleeLocKey);
2063
2064           calleeIntersectBoundSharedSet.intersectWriteSet(calleeBoundHeapPathKey, calleeLocKey,
2065               calleeWriteSet);
2066
2067         }
2068
2069       }
2070
2071     }
2072
2073   }
2074
2075   private NTuple<Descriptor> bind(NTuple<Descriptor> calleeHeapPathKey,
2076       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2077       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2078
2079     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2080     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2081       Integer idx = (Integer) iterator.next();
2082       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2083       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2084       if (calleeHeapPathKey.startsWith(calleeParam)) {
2085         NTuple<Descriptor> boundElement = combine(callerArgHeapPath, calleeHeapPathKey);
2086         return boundElement;
2087       }
2088     }
2089     return null;
2090   }
2091
2092   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
2093     if (booleanValue) {
2094       // the definitely written analysis only takes care about locations that
2095       // are written to inside of the SSJava loop
2096       for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) {
2097         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
2098         if (hp.startsWith(write)) {
2099           // it has write effect!
2100           // throw new Error(
2101           System.out
2102               .println("###"
2103                   + "There is a variable, which is reachable through references "
2104                   + hp
2105                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
2106                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
2107                   + fn.getNumLine());
2108           debugcount++;
2109         }
2110       }
2111     }
2112   }
2113
2114   private void initialize() {
2115     // First, identify ssjava loop entrace
2116
2117     // no need to analyze method having ssjava loop
2118     methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
2119
2120     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
2121     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2122     flatNodesToVisit.add(fm);
2123
2124     LoopFinder loopFinder = new LoopFinder(fm);
2125
2126     while (!flatNodesToVisit.isEmpty()) {
2127       FlatNode fn = flatNodesToVisit.iterator().next();
2128       flatNodesToVisit.remove(fn);
2129
2130       String label = (String) state.fn2labelMap.get(fn);
2131       if (label != null) {
2132
2133         if (label.equals(ssjava.SSJAVA)) {
2134           ssjavaLoopEntrance = fn;
2135           break;
2136         }
2137       }
2138
2139       for (int i = 0; i < fn.numNext(); i++) {
2140         FlatNode nn = fn.getNext(i);
2141         flatNodesToVisit.add(nn);
2142       }
2143     }
2144
2145     assert ssjavaLoopEntrance != null;
2146
2147     // assume that ssjava loop is top-level loop in method, not nested loop
2148     Set nestedLoop = loopFinder.nestedLoops();
2149     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
2150       LoopFinder lf = (LoopFinder) loopIter.next();
2151       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
2152         ssjavaLoop = lf;
2153       }
2154     }
2155
2156     assert ssjavaLoop != null;
2157
2158     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
2159
2160     // perform topological sort over the set of methods accessed by the main
2161     // event loop
2162     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
2163     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
2164     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
2165   }
2166
2167   private void methodReadWriteSetAnalysis() {
2168     // perform method READ/OVERWRITE analysis
2169     LinkedList<MethodDescriptor> descriptorListToAnalyze =
2170         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
2171
2172     // current descriptors to visit in fixed-point interprocedural analysis,
2173     // prioritized by
2174     // dependency in the call graph
2175     methodDescriptorsToVisitStack.clear();
2176
2177     descriptorListToAnalyze.removeFirst();
2178
2179     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
2180     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
2181
2182     while (!descriptorListToAnalyze.isEmpty()) {
2183       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
2184       methodDescriptorsToVisitStack.add(md);
2185     }
2186
2187     // analyze scheduled methods until there are no more to visit
2188     while (!methodDescriptorsToVisitStack.isEmpty()) {
2189       // start to analyze leaf node
2190       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
2191       FlatMethod fm = state.getMethodFlat(md);
2192
2193       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
2194       Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
2195       Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
2196       SharedLocMappingSet sharedLocMapping = new SharedLocMappingSet();
2197       Set<NTuple<Descriptor>> deleteSet = new HashSet<NTuple<Descriptor>>();
2198
2199       methodReadWriteSet_analyzeMethod(fm, readSet, mustWriteSet, mayWriteSet, sharedLocMapping,
2200           deleteSet);
2201
2202       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToReadSet.get(fm);
2203       Set<NTuple<Descriptor>> prevMustWrite = mapFlatMethodToMustWriteSet.get(fm);
2204       Set<NTuple<Descriptor>> prevMayWrite = mapFlatMethodToMayWriteSet.get(fm);
2205       SharedLocMappingSet prevSharedLocMapping = mapFlatMethodToSharedLocMappingSet.get(fm);
2206       Set<NTuple<Descriptor>> prevDeleteSet = mapFlatMethodToDeleteSet.get(fm);
2207
2208       if (!(readSet.equals(prevRead) && mustWriteSet.equals(prevMustWrite)
2209           && mayWriteSet.equals(prevMayWrite) && sharedLocMapping.equals(prevSharedLocMapping) && deleteSet
2210             .equals(prevDeleteSet))) {
2211         mapFlatMethodToReadSet.put(fm, readSet);
2212         mapFlatMethodToMustWriteSet.put(fm, mustWriteSet);
2213         mapFlatMethodToMayWriteSet.put(fm, mayWriteSet);
2214         mapFlatMethodToSharedLocMappingSet.put(fm, sharedLocMapping);
2215         mapFlatMethodToDeleteSet.put(fm, deleteSet);
2216
2217         // results for callee changed, so enqueue dependents caller for
2218         // further
2219         // analysis
2220         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
2221         while (depsItr.hasNext()) {
2222           MethodDescriptor methodNext = depsItr.next();
2223           if (!methodDescriptorsToVisitStack.contains(methodNext)
2224               && methodDescriptorToVistSet.contains(methodNext)) {
2225             methodDescriptorsToVisitStack.add(methodNext);
2226           }
2227
2228         }
2229
2230       }
2231
2232     }
2233
2234     methodReadWriteSetAnalysisToEventLoopBody();
2235
2236   }
2237
2238   private void methodReadWriteSet_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
2239       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
2240       SharedLocMappingSet sharedLocMapping, Set<NTuple<Descriptor>> deleteSet) {
2241     if (state.SSJAVADEBUG) {
2242       System.out.println("SSJAVA: Definitely written Analyzing: " + fm);
2243     }
2244
2245     methodReadWriteSet_analyzeBody(fm, readSet, mustWriteSet, mayWriteSet, sharedLocMapping,
2246         deleteSet, false);
2247
2248   }
2249
2250   private void methodReadWriteSetAnalysisToEventLoopBody() {
2251
2252     // perform method read/write analysis for Event Loop Body
2253
2254     FlatMethod flatMethodContainingSSJavaLoop = state.getMethodFlat(methodContainingSSJavaLoop);
2255
2256     if (state.SSJAVADEBUG) {
2257       System.out.println("SSJAVA: Definitely written Event Loop Analyzing: "
2258           + flatMethodContainingSSJavaLoop);
2259     }
2260
2261     Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
2262     Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
2263     Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
2264     SharedLocMappingSet sharedLocMapping = new SharedLocMappingSet();
2265     Set<NTuple<Descriptor>> deleteSet = new HashSet<NTuple<Descriptor>>();
2266
2267     mapFlatMethodToReadSet.put(flatMethodContainingSSJavaLoop, readSet);
2268     mapFlatMethodToMustWriteSet.put(flatMethodContainingSSJavaLoop, mustWriteSet);
2269     mapFlatMethodToMayWriteSet.put(flatMethodContainingSSJavaLoop, mayWriteSet);
2270     mapFlatMethodToSharedLocMappingSet.put(flatMethodContainingSSJavaLoop, sharedLocMapping);
2271     mapFlatMethodToDeleteSet.put(flatMethodContainingSSJavaLoop, deleteSet);
2272
2273     methodReadWriteSet_analyzeBody(ssjavaLoopEntrance, readSet, mustWriteSet, mayWriteSet,
2274         sharedLocMapping, deleteSet, true);
2275
2276   }
2277
2278   private void methodReadWriteSet_analyzeBody(FlatNode startNode, Set<NTuple<Descriptor>> readSet,
2279       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
2280       SharedLocMappingSet sharedLocMapping, Set<NTuple<Descriptor>> deleteSet,
2281       boolean isEventLoopBody) {
2282
2283     // intraprocedural analysis
2284     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
2285     flatNodesToVisit.add(startNode);
2286
2287     while (!flatNodesToVisit.isEmpty()) {
2288       FlatNode fn = flatNodesToVisit.iterator().next();
2289       flatNodesToVisit.remove(fn);
2290
2291       SharedLocMappingSet currSharedLocMapping = new SharedLocMappingSet();
2292       Set<NTuple<Descriptor>> currMustWriteSet = new HashSet<NTuple<Descriptor>>();
2293
2294       for (int i = 0; i < fn.numPrev(); i++) {
2295         FlatNode prevFn = fn.getPrev(i);
2296         Set<NTuple<Descriptor>> in = mapFlatNodeToMustWriteSet.get(prevFn);
2297         SharedLocMappingSet inSharedLoc = mapFlatNodeToSharedLocMapping.get(prevFn);
2298         if (in != null) {
2299           merge(currMustWriteSet, in);
2300           merge(currSharedLocMapping, inSharedLoc);
2301         }
2302       }
2303
2304       methodReadWriteSet_nodeActions(fn, currMustWriteSet, readSet, mustWriteSet, mayWriteSet,
2305           currSharedLocMapping, sharedLocMapping, deleteSet, isEventLoopBody);
2306
2307       SharedLocMappingSet prevSharedLocSet = mapFlatNodeToSharedLocMapping.get(fn);
2308       Set<NTuple<Descriptor>> mustSetPrev = mapFlatNodeToMustWriteSet.get(fn);
2309
2310       if ((!currMustWriteSet.equals(mustSetPrev))
2311           || (!currSharedLocMapping.equals(prevSharedLocSet))) {
2312         mapFlatNodeToMustWriteSet.put(fn, currMustWriteSet);
2313         mapFlatNodeToSharedLocMapping.put(fn, currSharedLocMapping);
2314         for (int i = 0; i < fn.numNext(); i++) {
2315           FlatNode nn = fn.getNext(i);
2316           if ((!isEventLoopBody) || loopIncElements.contains(nn)) {
2317             flatNodesToVisit.add(nn);
2318           }
2319
2320         }
2321       }
2322
2323     }
2324
2325   }
2326
2327   private void methodReadWriteSet_nodeActions(FlatNode fn,
2328       Set<NTuple<Descriptor>> currMustWriteSet, Set<NTuple<Descriptor>> readSet,
2329       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
2330       SharedLocMappingSet currSharedLocMapping, SharedLocMappingSet sharedLocMapping,
2331       Set<NTuple<Descriptor>> deleteSet, boolean isEventLoopBody) {
2332
2333     SharedLocMappingSet killSetSharedLoc = new SharedLocMappingSet();
2334     SharedLocMappingSet genSetSharedLoc = new SharedLocMappingSet();
2335
2336     TempDescriptor lhs;
2337     TempDescriptor rhs;
2338     FieldDescriptor fld;
2339
2340     switch (fn.kind()) {
2341     case FKind.FlatMethod: {
2342
2343       // set up initial heap paths for method parameters
2344       FlatMethod fm = (FlatMethod) fn;
2345       for (int i = 0; i < fm.numParameters(); i++) {
2346         TempDescriptor param = fm.getParameter(i);
2347         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2348         heapPath.add(param);
2349         mapHeapPath.put(param, heapPath);
2350       }
2351     }
2352       break;
2353
2354     case FKind.FlatOpNode: {
2355       FlatOpNode fon = (FlatOpNode) fn;
2356       // for a normal assign node, need to propagate lhs's heap path to
2357       // rhs
2358       if (fon.getOp().getOp() == Operation.ASSIGN) {
2359         rhs = fon.getLeft();
2360         lhs = fon.getDest();
2361
2362         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
2363         if (rhsHeapPath != null) {
2364           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
2365         } else {
2366           NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2367           heapPath.add(rhs);
2368           mapHeapPath.put(lhs, heapPath);
2369         }
2370
2371         // shared loc extension
2372         if (isEventLoopBody) {
2373           if (!lhs.getSymbol().startsWith("neverused") && rhs.getType().isImmutable()) {
2374
2375             if (rhs.getType().getExtension() instanceof Location
2376                 && lhs.getType().getExtension() instanceof CompositeLocation) {
2377               // rhs is field!
2378               Location rhsLoc = (Location) rhs.getType().getExtension();
2379
2380               CompositeLocation lhsCompLoc = (CompositeLocation) lhs.getType().getExtension();
2381               Location dstLoc = lhsCompLoc.get(lhsCompLoc.getSize() - 1);
2382
2383               NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
2384               for (int i = 0; i < rhsHeapPath.size() - 1; i++) {
2385                 heapPath.add(rhsHeapPath.get(i));
2386               }
2387
2388               NTuple<Descriptor> writeHeapPath = new NTuple<Descriptor>();
2389               writeHeapPath.addAll(heapPath);
2390               writeHeapPath.add(lhs);
2391
2392               System.out.println("VAR WRITE:" + fn);
2393               System.out.println("LHS TYPE EXTENSION=" + lhs.getType().getExtension());
2394               System.out.println("RHS TYPE EXTENSION=" + rhs.getType().getExtension()
2395                   + " HEAPPATH=" + rhsHeapPath);
2396
2397               // computing gen/kill set
2398               computeKILLSetForWrite(currSharedLocMapping, heapPath, dstLoc, killSetSharedLoc);
2399               if (!dstLoc.equals(rhsLoc)) {
2400                 computeGENSetForHigherWrite(currSharedLocMapping, heapPath, dstLoc, lhs,
2401                     genSetSharedLoc);
2402                 deleteSet.remove(writeHeapPath);
2403               } else {
2404                 computeGENSetForSharedWrite(currSharedLocMapping, heapPath, dstLoc, lhs,
2405                     genSetSharedLoc);
2406                 deleteSet.add(writeHeapPath);
2407               }
2408
2409             }
2410           }
2411         }
2412
2413       }
2414     }
2415       break;
2416
2417     case FKind.FlatElementNode:
2418     case FKind.FlatFieldNode: {
2419
2420       // x=y.f;
2421
2422       if (fn.kind() == FKind.FlatFieldNode) {
2423         FlatFieldNode ffn = (FlatFieldNode) fn;
2424         lhs = ffn.getDst();
2425         rhs = ffn.getSrc();
2426         fld = ffn.getField();
2427       } else {
2428         FlatElementNode fen = (FlatElementNode) fn;
2429         lhs = fen.getDst();
2430         rhs = fen.getSrc();
2431         TypeDescriptor td = rhs.getType().dereference();
2432         fld = getArrayField(td);
2433       }
2434
2435       if (fld.isFinal()) {
2436         // if field is final no need to check
2437         break;
2438       }
2439
2440       // set up heap path
2441       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
2442       if (srcHeapPath != null) {
2443         // if lhs srcHeapPath is null, it means that it is not reachable from
2444         // callee's parameters. so just ignore it
2445
2446         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
2447         readingHeapPath.add(fld);
2448         mapHeapPath.put(lhs, readingHeapPath);
2449
2450         // read (x.f)
2451         if (fld.getType().isImmutable()) {
2452           // if WT doesnot have hp(x.f), add hp(x.f) to READ
2453           if (!currMustWriteSet.contains(readingHeapPath)) {
2454             readSet.add(readingHeapPath);
2455           }
2456         }
2457
2458         // no need to kill hp(x.f) from WT
2459       }
2460
2461     }
2462       break;
2463
2464     case FKind.FlatSetFieldNode:
2465     case FKind.FlatSetElementNode: {
2466
2467       // x.f=y;
2468
2469       if (fn.kind() == FKind.FlatSetFieldNode) {
2470         SharedLocMappingSet killSet = new SharedLocMappingSet();
2471         SharedLocMappingSet genSet = new SharedLocMappingSet();
2472         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
2473         lhs = fsfn.getDst();
2474         fld = fsfn.getField();
2475         rhs = fsfn.getSrc();
2476       } else {
2477         FlatSetElementNode fsen = (FlatSetElementNode) fn;
2478         lhs = fsen.getDst();
2479         rhs = fsen.getSrc();
2480         TypeDescriptor td = lhs.getType().dereference();
2481         fld = getArrayField(td);
2482       }
2483
2484       // set up heap path
2485       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
2486
2487       if (lhsHeapPath != null) {
2488         // if lhs heap path is null, it means that it is not reachable from
2489         // callee's parameters. so just ignore it
2490         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
2491         fldHeapPath.add(fld);
2492         mapHeapPath.put(fld, fldHeapPath);
2493
2494         // write(x.f)
2495         // need to add hp(y) to WT
2496         currMustWriteSet.add(fldHeapPath);
2497         mayWriteSet.add(fldHeapPath);
2498
2499         // shared loc extension
2500         Location srcLoc = getLocation(rhs);
2501         Location fieldLoc = (Location) fld.getType().getExtension();
2502         if (ssjava.isSharedLocation(fieldLoc)) {
2503           // only care the case that loc(f) is shared location
2504           // write(field)
2505
2506           computeKILLSetForWrite(currSharedLocMapping, lhsHeapPath, fieldLoc, killSetSharedLoc);
2507           if (!fieldLoc.equals(srcLoc)) {
2508             computeGENSetForHigherWrite(currSharedLocMapping, lhsHeapPath, fieldLoc, fld,
2509                 genSetSharedLoc);
2510             deleteSet.remove(fldHeapPath);
2511           } else {
2512             computeGENSetForSharedWrite(currSharedLocMapping, lhsHeapPath, fieldLoc, fld,
2513                 genSetSharedLoc);
2514             deleteSet.add(fldHeapPath);
2515           }
2516         }
2517
2518         System.out.println("################");
2519         System.out.println("FIELD WRITE:" + fn);
2520         System.out.println("fieldLoc=" + fieldLoc + " srcLoc=" + srcLoc);
2521         System.out.println("KILLSET=" + killSetSharedLoc);
2522         System.out.println("GENSet=" + genSetSharedLoc);
2523         System.out.println("DELETESET=" + deleteSet);
2524
2525       }
2526
2527     }
2528       break;
2529
2530     case FKind.FlatCall: {
2531
2532       FlatCall fc = (FlatCall) fn;
2533
2534       bindHeapPathCallerArgWithCalleeParam(fc);
2535
2536       mapFlatNodeToBoundReadSet.put(fn, calleeUnionBoundReadSet);
2537       mapFlatNodeToBoundMustWriteSet.put(fn, calleeIntersectBoundMustWriteSet);
2538       mapFlatNodeToBoundMayWriteSet.put(fn, calleeUnionBoundMayWriteSet);
2539
2540       // add heap path, which is an element of READ_bound set and is not
2541       // an
2542       // element of WT set, to the caller's READ set
2543       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
2544         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
2545         if (!currMustWriteSet.contains(read)) {
2546           readSet.add(read);
2547         }
2548       }
2549
2550       // add heap path, which is an element of OVERWRITE_bound set, to the
2551       // caller's WT set
2552       for (Iterator iterator = calleeIntersectBoundMustWriteSet.iterator(); iterator.hasNext();) {
2553         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
2554         currMustWriteSet.add(write);
2555       }
2556
2557       // add heap path, which is an element of WRITE_BOUND set, to the
2558       // caller's writeSet
2559       for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) {
2560         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
2561         mayWriteSet.add(write);
2562       }
2563
2564       // shared loc extension
2565       bindHeapPathCallerArgWithCaleeParamForSharedLoc(fc);
2566
2567       generateKILLSharedSetForFlatCall(currSharedLocMapping, killSetSharedLoc);
2568       generateGENSharedSetForFlatCall(currSharedLocMapping, genSetSharedLoc);
2569
2570       System.out.println("### Analyzing FC=" + fc);
2571       System.out.println("### BOUNDSET=" + calleeIntersectBoundSharedSet);
2572       System.out.println("### GEN=" + genSetSharedLoc);
2573       System.out.println("### KILL=" + killSetSharedLoc);
2574     }
2575       break;
2576
2577     case FKind.FlatExit: {
2578       // merge the current written set with OVERWRITE set
2579       merge(mustWriteSet, currMustWriteSet);
2580
2581       // shared loc extension
2582       merge(sharedLocMapping, currSharedLocMapping);
2583     }
2584       break;
2585
2586     }
2587
2588     computeNewMapping(currSharedLocMapping, killSetSharedLoc, genSetSharedLoc);
2589
2590   }
2591
2592   private void generateGENSharedSetForFlatCall(SharedLocMappingSet currSharedLocMapping,
2593       SharedLocMappingSet genSetSharedLoc) {
2594
2595     Set<NTuple<Descriptor>> hpKeySet = calleeIntersectBoundSharedSet.getHeapPathKeySet();
2596     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2597       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2598       Set<Location> locKeySet = calleeIntersectBoundSharedSet.getLocationKeySet(hpKey);
2599       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2600         Location locKey = (Location) iterator2.next();
2601
2602         Set<Descriptor> calleeBoundWriteSet =
2603             calleeIntersectBoundSharedSet.getWriteSet(hpKey, locKey);
2604         System.out.println("calleeBoundWriteSet=" + calleeBoundWriteSet + " hp=" + hpKey + " loc="
2605             + locKey);
2606         Set<Descriptor> removeSet = computeRemoveSet(hpKey, locKey);
2607
2608         Set<Descriptor> currWriteSet = currSharedLocMapping.getWriteSet(hpKey, locKey);
2609
2610         genSetSharedLoc.addWriteSet(hpKey, locKey, currWriteSet);
2611         genSetSharedLoc.addWriteSet(hpKey, locKey, calleeBoundWriteSet);
2612         genSetSharedLoc.removeWriteSet(hpKey, locKey, removeSet);
2613
2614       }
2615     }
2616
2617   }
2618
2619   public NTuple<Descriptor> getPrefix(NTuple<Descriptor> in) {
2620     return in.subList(0, in.size() - 1);
2621   }
2622
2623   public NTuple<Descriptor> getSuffix(NTuple<Descriptor> in) {
2624     return in.subList(in.size() - 1, in.size());
2625   }
2626
2627   private Set<Descriptor> computeRemoveSet(NTuple<Descriptor> hpKey, Location locKey) {
2628     Set<Descriptor> removeSet = new HashSet<Descriptor>();
2629
2630     for (Iterator iterator = calleeUnionBoundDeleteSet.iterator(); iterator.hasNext();) {
2631       NTuple<Descriptor> removeHeapPath = (NTuple<Descriptor>) iterator.next();
2632       if (getPrefix(removeHeapPath).equals(hpKey)) {
2633         removeSet.add(getSuffix(removeHeapPath).get(0));
2634       }
2635     }
2636
2637     return removeSet;
2638   }
2639
2640   private void generateKILLSharedSetForFlatCall(SharedLocMappingSet currSharedLocMapping,
2641       SharedLocMappingSet killSetSharedLoc) {
2642
2643     Set<NTuple<Descriptor>> hpKeySet = calleeIntersectBoundSharedSet.getHeapPathKeySet();
2644     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2645       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2646       Set<Location> locKeySet = calleeIntersectBoundSharedSet.getLocationKeySet(hpKey);
2647       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2648         Location locKey = (Location) iterator2.next();
2649         Set<Descriptor> currWriteSet = currSharedLocMapping.getWriteSet(hpKey, locKey);
2650         killSetSharedLoc.addWriteSet(hpKey, locKey, currWriteSet);
2651       }
2652     }
2653   }
2654
2655   static public FieldDescriptor getArrayField(TypeDescriptor td) {
2656     FieldDescriptor fd = mapTypeToArrayField.get(td);
2657     if (fd == null) {
2658       fd =
2659           new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
2660               false);
2661       mapTypeToArrayField.put(td, fd);
2662     }
2663     return fd;
2664   }
2665
2666   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
2667     if (inSet.size() == 0) {
2668       return;
2669     }
2670     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
2671         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
2672
2673     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
2674
2675       ClearingSummary inTable = (ClearingSummary) inIterator.next();
2676
2677       Set<NTuple<Descriptor>> keySet = inTable.keySet();
2678
2679       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2680         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2681         SharedStatus inState = inTable.get(hpKey);
2682         SharedStatus currState = curr.get(hpKey);
2683         if (currState == null) {
2684           currState = new SharedStatus();
2685           curr.put(hpKey, currState);
2686         }
2687
2688         currState.merge(inState);
2689
2690         Set<Location> locSet = inState.getMap().keySet();
2691         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
2692           Location loc = (Location) iterator2.next();
2693           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
2694           boolean inFlag = pair.getSecond().booleanValue();
2695
2696           Pair<NTuple<Descriptor>, Location> flagKey =
2697               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
2698           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
2699           if (current == null) {
2700             current = new Boolean(true);
2701           }
2702           boolean newInFlag = current.booleanValue() & inFlag;
2703           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
2704         }
2705
2706       }
2707
2708     }
2709
2710     // merge flag status
2711     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
2712     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
2713       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
2714       SharedStatus currState = curr.get(hpKey);
2715       Set<Location> locKeySet = currState.getMap().keySet();
2716       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
2717         Location locKey = (Location) iterator2.next();
2718         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
2719         boolean currentFlag = pair.getSecond().booleanValue();
2720         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
2721         if (inFlag != null) {
2722           boolean newFlag = currentFlag | inFlag.booleanValue();
2723           if (currentFlag != newFlag) {
2724             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
2725           }
2726         }
2727       }
2728     }
2729
2730   }
2731
2732   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
2733     if (curr.isEmpty()) {
2734       // set has a special initial value which covers all possible
2735       // elements
2736       // For the first time of intersection, we can take all previous set
2737       curr.addAll(in);
2738     } else {
2739       // otherwise, current set is the intersection of the two sets
2740       curr.retainAll(in);
2741     }
2742
2743   }
2744
2745   // combine two heap path
2746   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
2747     NTuple<Descriptor> combined = new NTuple<Descriptor>();
2748
2749     for (int i = 0; i < callerIn.size(); i++) {
2750       combined.add(callerIn.get(i));
2751     }
2752
2753     // the first element of callee's heap path represents parameter
2754     // so we skip the first one since it is already added from caller's heap
2755     // path
2756     for (int i = 1; i < calleeIn.size(); i++) {
2757       combined.add(calleeIn.get(i));
2758     }
2759
2760     return combined;
2761   }
2762
2763   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
2764       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
2765       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
2766
2767     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
2768
2769     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
2770     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
2771       Integer idx = (Integer) iterator.next();
2772
2773       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2774       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2775       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2776         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2777         if (element.startsWith(calleeParam)) {
2778           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2779           boundedCalleeSet.add(boundElement);
2780         }
2781
2782       }
2783
2784     }
2785     return boundedCalleeSet;
2786
2787   }
2788
2789   // Borrowed it from disjoint analysis
2790   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2791
2792     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2793
2794     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2795
2796     Iterator<MethodDescriptor> itr = toSort.iterator();
2797     while (itr.hasNext()) {
2798       MethodDescriptor d = itr.next();
2799
2800       if (!discovered.contains(d)) {
2801         dfsVisit(d, toSort, sorted, discovered);
2802       }
2803     }
2804
2805     return sorted;
2806   }
2807
2808   // While we're doing DFS on call graph, remember
2809   // dependencies for efficient queuing of methods
2810   // during interprocedural analysis:
2811   //
2812   // a dependent of a method decriptor d for this analysis is:
2813   // 1) a method or task that invokes d
2814   // 2) in the descriptorsToAnalyze set
2815   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2816       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2817
2818     discovered.add(md);
2819
2820     Iterator itr = callGraph.getCallerSet(md).iterator();
2821     while (itr.hasNext()) {
2822       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2823       // only consider callers in the original set to analyze
2824       if (!toSort.contains(dCaller)) {
2825         continue;
2826       }
2827       if (!discovered.contains(dCaller)) {
2828         addDependent(md, // callee
2829             dCaller // caller
2830         );
2831
2832         dfsVisit(dCaller, toSort, sorted, discovered);
2833       }
2834     }
2835
2836     // for leaf-nodes last now!
2837     sorted.addLast(md);
2838   }
2839
2840   // a dependent of a method decriptor d for this analysis is:
2841   // 1) a method or task that invokes d
2842   // 2) in the descriptorsToAnalyze set
2843   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2844     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2845     if (deps == null) {
2846       deps = new HashSet<MethodDescriptor>();
2847     }
2848     deps.add(caller);
2849     mapDescriptorToSetDependents.put(callee, deps);
2850   }
2851
2852   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2853     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2854     if (deps == null) {
2855       deps = new HashSet<MethodDescriptor>();
2856       mapDescriptorToSetDependents.put(callee, deps);
2857     }
2858     return deps;
2859   }
2860
2861   private NTuple<Descriptor> computePath(TempDescriptor td) {
2862     // generate proper path fot input td
2863     // if td is local variable, it just generate one element tuple path
2864     if (mapHeapPath.containsKey(td)) {
2865       return mapHeapPath.get(td);
2866     } else {
2867       NTuple<Descriptor> path = new NTuple<Descriptor>();
2868       path.add(td);
2869       return path;
2870     }
2871   }
2872
2873   private NTuple<Location> deriveThisLocationTuple(MethodDescriptor md) {
2874     String thisLocIdentifier = ssjava.getMethodLattice(md).getThisLoc();
2875     Location thisLoc = new Location(md, thisLocIdentifier);
2876     NTuple<Location> locTuple = new NTuple<Location>();
2877     locTuple.add(thisLoc);
2878     return locTuple;
2879   }
2880
2881   private NTuple<Location> deriveLocationTuple(MethodDescriptor md, TempDescriptor td) {
2882
2883     assert td.getType() != null;
2884
2885     if (mapDescriptorToLocationStrPath.containsKey(td)) {
2886       return mapDescriptorToLocationStrPath.get(td);
2887     } else {
2888       if (td.getSymbol().startsWith("this")) {
2889         return deriveThisLocationTuple(md);
2890       } else {
2891         NTuple<Location> locTuple =
2892             ((SSJavaType) td.getType().getExtension()).getCompLoc().getTuple();
2893         return locTuple;
2894       }
2895     }
2896
2897   }
2898
2899   private NTuple<Location> deriveLocationTuple(MethodDescriptor md, FieldDescriptor fld) {
2900
2901     assert fld.getType() != null;
2902
2903     Location fieldLoc = (Location) fld.getType().getExtension();
2904     NTuple<Location> locTuple = new NTuple<Location>();
2905     locTuple.add(fieldLoc);
2906     return locTuple;
2907   }
2908
2909 }