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