Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

   1 package Analysis.SSJava;
   2
   3 import java.util.HashSet;
   4 import java.util.Hashtable;
   5 import java.util.Iterator;
   6 import java.util.LinkedList;
   7 import java.util.Set;
   8 import java.util.Stack;
   9
  10 import Analysis.CallGraph.CallGraph;
  11 import Analysis.Loops.LoopFinder;
  12 import IR.Descriptor;
  13 import IR.FieldDescriptor;
  14 import IR.MethodDescriptor;
  15 import IR.Operation;
  16 import IR.State;
  17 import IR.TypeDescriptor;
  18 import IR.Flat.FKind;
  19 import IR.Flat.FlatCall;
  20 import IR.Flat.FlatFieldNode;
  21 import IR.Flat.FlatLiteralNode;
  22 import IR.Flat.FlatMethod;
  23 import IR.Flat.FlatNode;
  24 import IR.Flat.FlatOpNode;
  25 import IR.Flat.FlatSetFieldNode;
  26 import IR.Flat.TempDescriptor;
  27 import Util.Pair;
  28
  29 public class DefinitelyWrittenCheck {
  30
  31   SSJavaAnalysis ssjava;
  32   State state;
  33   CallGraph callGraph;
  34
  35   // maps a descriptor to its known dependents: namely
  36   // methods or tasks that call the descriptor's method
  37   // AND are part of this analysis (reachable from main)
  38   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  39
  40   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  41   // previously.
  42   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  43
  44   // maps a temp descriptor to its heap path
  45   // each temp descriptor has a unique heap path since we do not allow any
  46   // alias.
  47   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  48
  49   // maps a flat method to the READ that is the set of heap path that is
  50   // expected to be written before method invocation
  51   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  52
  53   // maps a flat method to the OVERWRITE that is the set of heap path that is
  54   // overwritten on every possible path during method invocation
  55   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  56
  57   // points to method containing SSJAVA Loop
  58   private MethodDescriptor methodContainingSSJavaLoop;
  59
  60   // maps a flatnode to definitely written analysis mapping M
  61   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  62
  63   // maps a method descriptor to its current summary during the analysis
  64   // then analysis reaches fixed-point, this mapping will have the final summary
  65   // for each method descriptor
  66   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
  67
  68   // maps a method descriptor to the merged incoming caller's current
  69   // overwritten status
  70   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
  71
  72   // maps a flat node to current partial results
  73   private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
  74
  75   // maps shared location to the set of descriptors which belong to the shared
  76   // location
  77   private Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
  78
  79   // keep current descriptors to visit in fixed-point interprocedural analysis,
  80   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
  81
  82   // when analyzing flatcall, need to re-schedule set of callee
  83   private Set<MethodDescriptor> calleesToEnqueue;
  84
  85   private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
  86
  87   private LinkedList<MethodDescriptor> sortedDescriptors;
  88
  89   private FlatNode ssjavaLoopEntrance;
  90   private LoopFinder ssjavaLoop;
  91   private Set<FlatNode> loopIncElements;
  92
  93   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  94   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  95
  96   private TempDescriptor LOCAL;
  97
  98   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  99     this.state = state;
 100     this.ssjava = ssjava;
 101     this.callGraph = ssjava.getCallGraph();
 102     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 103     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 104     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
 105     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 106     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 107     this.definitelyWrittenResults =
 108         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
 109     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 110     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
 111
 112     this.mapMethodDescriptorToCompleteClearingSummary =
 113         new Hashtable<MethodDescriptor, ClearingSummary>();
 114     this.mapMethodDescriptorToInitialClearingSummary =
 115         new Hashtable<MethodDescriptor, ClearingSummary>();
 116     this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
 117     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 118     this.calleesToEnqueue = new HashSet<MethodDescriptor>();
 119     this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
 120     this.LOCAL = new TempDescriptor("LOCAL");
 121   }
 122
 123   public void definitelyWrittenCheck() {
 124     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 125       methodReadOverWriteAnalysis();
 126       writtenAnalyis();
 127       sharedLocationAnalysis();
 128       checkSharedLocationResult();
 129     }
 130   }
 131
 132   private void checkSharedLocationResult() {
 133
 134     // mapping of method containing ssjava loop has the final result of
 135     // shared location analysis
 136     ClearingSummary result =
 137         mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
 138
 139     System.out.println("checkSharedLocationResult=" + result);
 140
 141     Set<NTuple<Descriptor>> hpKeySet = result.keySet();
 142     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 143       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 144       SharedStatus state = result.get(hpKey);
 145       Set<Location> locKeySet = state.getLocationSet();
 146       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 147         Location locKey = (Location) iterator2.next();
 148         if (!state.getFlag(locKey)) {
 149           throw new Error(
 150               "Some concrete locations of the shared abstract location are not cleared at the same time.");
 151         }
 152       }
 153     }
 154
 155   }
 156
 157   private void sharedLocationAnalysis() {
 158     // verify that all concrete locations of shared location are cleared out at
 159     // the same time once per the out-most loop
 160
 161     computeReadSharedDescriptorSet();
 162     System.out.println("Reading Shared Location=" + mapSharedLocation2DescriptorSet);
 163
 164     methodDescriptorsToVisitStack.clear();
 165
 166     methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 167
 168     // analyze scheduled methods until there are no more to visit
 169     while (!methodDescriptorsToVisitStack.isEmpty()) {
 170       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 171
 172       ClearingSummary completeSummary =
 173           sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 174
 175       ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
 176
 177       if (!completeSummary.equals(prevCompleteSummary)) {
 178
 179         mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 180
 181         // results for callee changed, so enqueue dependents caller for
 182         // further analysis
 183         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 184         while (depsItr.hasNext()) {
 185           MethodDescriptor methodNext = depsItr.next();
 186           if (!methodDescriptorsToVisitStack.contains(methodNext)) {
 187             methodDescriptorsToVisitStack.add(methodNext);
 188           }
 189         }
 190
 191         // if there is set of callee to be analyzed,
 192         // add this set into the top of stack
 193         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 194         while (calleeIter.hasNext()) {
 195           MethodDescriptor mdNext = calleeIter.next();
 196           if (!methodDescriptorsToVisitStack.contains(mdNext)) {
 197             methodDescriptorsToVisitStack.add(mdNext);
 198           }
 199         }
 200         calleesToEnqueue.clear();
 201
 202       }
 203
 204     }
 205
 206   }
 207
 208   private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
 209       boolean onlyVisitSSJavaLoop) {
 210
 211     if (state.SSJAVADEBUG) {
 212       System.out.println("Definitely written for shared locations Analyzing: " + md + " "
 213           + onlyVisitSSJavaLoop);
 214     }
 215
 216     FlatMethod fm = state.getMethodFlat(md);
 217
 218     // intraprocedural analysis
 219     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 220
 221     // start a new mapping of partial results for each flat node
 222     mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
 223
 224     if (onlyVisitSSJavaLoop) {
 225       flatNodesToVisit.add(ssjavaLoopEntrance);
 226     } else {
 227       flatNodesToVisit.add(fm);
 228     }
 229
 230     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 231
 232     while (!flatNodesToVisit.isEmpty()) {
 233       FlatNode fn = flatNodesToVisit.iterator().next();
 234       flatNodesToVisit.remove(fn);
 235
 236       ClearingSummary curr = new ClearingSummary();
 237
 238       Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
 239       for (int i = 0; i < fn.numPrev(); i++) {
 240         FlatNode prevFn = fn.getPrev(i);
 241         ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
 242         if (in != null) {
 243           prevSet.add(in);
 244         }
 245       }
 246       mergeSharedLocationAnaylsis(curr, prevSet);
 247
 248       sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 249       ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 250
 251       if (!curr.equals(clearingPrev)) {
 252         mapFlatNodeToClearingSummary.put(fn, curr);
 253
 254         for (int i = 0; i < fn.numNext(); i++) {
 255           FlatNode nn = fn.getNext(i);
 256
 257           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 258             flatNodesToVisit.add(nn);
 259           }
 260
 261         }
 262       }
 263
 264     }
 265
 266     ClearingSummary completeSummary = new ClearingSummary();
 267     Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
 268
 269     if (onlyVisitSSJavaLoop) {
 270       // when analyzing ssjava loop,
 271       // complete summary is merging of all previous nodes of ssjava loop
 272       // entrance
 273       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 274         ClearingSummary frnSummary =
 275             mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
 276         if (frnSummary != null) {
 277           summarySet.add(frnSummary);
 278         }
 279       }
 280     } else {
 281       // merging all exit node summary into the complete summary
 282       if (!returnNodeSet.isEmpty()) {
 283         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 284           FlatNode frn = (FlatNode) iterator.next();
 285           ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
 286           summarySet.add(frnSummary);
 287         }
 288       }
 289     }
 290     mergeSharedLocationAnaylsis(completeSummary, summarySet);
 291     return completeSummary;
 292   }
 293
 294   private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
 295       ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 296
 297     TempDescriptor lhs;
 298     TempDescriptor rhs;
 299     FieldDescriptor fld;
 300     switch (fn.kind()) {
 301
 302     case FKind.FlatMethod: {
 303       FlatMethod fm = (FlatMethod) fn;
 304
 305       ClearingSummary summaryFromCaller =
 306           mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
 307
 308       Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 309       inSet.add(summaryFromCaller);
 310       mergeSharedLocationAnaylsis(curr, inSet);
 311
 312     }
 313       break;
 314
 315     case FKind.FlatOpNode: {
 316       FlatOpNode fon = (FlatOpNode) fn;
 317       lhs = fon.getDest();
 318       rhs = fon.getLeft();
 319
 320       if (fon.getOp().getOp() == Operation.ASSIGN) {
 321         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 322           // in ssjavaloop, we need to take care about reading local variables!
 323           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 324           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 325           rhsHeapPath.add(LOCAL);
 326           lhsHeapPath.add(LOCAL);
 327           if (!lhs.getSymbol().startsWith("neverused")) {
 328             readLocation(curr, rhsHeapPath, rhs);
 329             writeLocation(curr, lhsHeapPath, lhs);
 330           }
 331         }
 332       }
 333
 334     }
 335       break;
 336
 337     case FKind.FlatFieldNode:
 338     case FKind.FlatElementNode: {
 339
 340       FlatFieldNode ffn = (FlatFieldNode) fn;
 341       lhs = ffn.getDst();
 342       rhs = ffn.getSrc();
 343       fld = ffn.getField();
 344
 345       // read field
 346       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 347       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 348
 349       if (fld.getType().isImmutable()) {
 350         readLocation(curr, fldHeapPath, fld);
 351       }
 352
 353     }
 354       break;
 355
 356     case FKind.FlatSetFieldNode:
 357     case FKind.FlatSetElementNode: {
 358
 359       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 360       lhs = fsfn.getDst();
 361       fld = fsfn.getField();
 362
 363       // write(field)
 364       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 365       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 366       if (fld.getType().isImmutable()) {
 367         writeLocation(curr, fldHeapPath, fld);
 368       } else {
 369         // updates reference field case:
 370         // 2. if there exists a tuple t in sharing summary that starts with
 371         // hp(x) then, set flag of tuple t to 'true'
 372         fldHeapPath.add(fld);
 373         Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 374         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 375           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 376           if (hpKey.startsWith(fldHeapPath)) {
 377             curr.get(hpKey).updateFlag(true);
 378           }
 379         }
 380       }
 381
 382     }
 383       break;
 384
 385     case FKind.FlatCall: {
 386
 387       FlatCall fc = (FlatCall) fn;
 388
 389       // find out the set of callees
 390       MethodDescriptor mdCallee = fc.getMethod();
 391       FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 392       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 393       TypeDescriptor typeDesc = fc.getThis().getType();
 394       setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 395
 396       possibleCalleeCompleteSummarySetToCaller.clear();
 397
 398       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 399         MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 400         FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 401
 402         addDependent(mdPossibleCallee, // callee
 403             caller); // caller
 404
 405         calleesToEnqueue.add(mdPossibleCallee);
 406
 407         // updates possible callee's initial summary using caller's current
 408         // writing status
 409         ClearingSummary prevCalleeInitSummary =
 410             mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 411
 412         ClearingSummary calleeInitSummary =
 413             bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 414
 415         // if changes, update the init summary
 416         // and reschedule the callee for analysis
 417         if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 418
 419           if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
 420             methodDescriptorsToVisitStack.add(mdPossibleCallee);
 421           }
 422           mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 423         }
 424
 425       }
 426
 427       // contribute callee's writing effects to the caller
 428       mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 429
 430     }
 431       break;
 432
 433     case FKind.FlatReturnNode: {
 434       returnNodeSet.add(fn);
 435     }
 436       break;
 437
 438     }
 439
 440   }
 441
 442   private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
 443       FlatMethod calleeFlatMethod, ClearingSummary curr) {
 444
 445     ClearingSummary boundSet = new ClearingSummary();
 446
 447     // create mapping from arg idx to its heap paths
 448     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 449         new Hashtable<Integer, NTuple<Descriptor>>();
 450
 451     // arg idx is starting from 'this' arg
 452     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 453     if (thisHeapPath == null) {
 454       // method is called without creating new flat node representing 'this'
 455       thisHeapPath = new NTuple<Descriptor>();
 456       thisHeapPath.add(fc.getThis());
 457     }
 458
 459     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 460
 461     for (int i = 0; i < fc.numArgs(); i++) {
 462       TempDescriptor arg = fc.getArg(i);
 463       NTuple<Descriptor> argHeapPath = computePath(arg);
 464       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 465     }
 466
 467     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 468         new Hashtable<Integer, TempDescriptor>();
 469     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 470       TempDescriptor param = calleeFlatMethod.getParameter(i);
 471       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 472     }
 473
 474     // binding caller's writing effects to callee's params
 475     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 476       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 477       TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 478
 479       // iterate over caller's writing effect set
 480       Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 481       for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 482         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 483         // current element is reachable caller's arg
 484         // so need to bind it to the caller's side and add it to the callee's
 485         // init summary
 486         if (hpKey.startsWith(argHeapPath)) {
 487           NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 488           boundSet.put(boundHeapPath, curr.get(hpKey).clone());
 489         }
 490
 491       }
 492
 493     }
 494
 495     // contribute callee's complete summary into the caller's current summary
 496     ClearingSummary calleeCompleteSummary =
 497         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
 498
 499     if (calleeCompleteSummary != null) {
 500       ClearingSummary boundCalleeEfffects = new ClearingSummary();
 501       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 502         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 503         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 504
 505         // iterate over callee's writing effect set
 506         Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
 507         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 508           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 509           // current element is reachable caller's arg
 510           // so need to bind it to the caller's side and add it to the callee's
 511           // init summary
 512           if (hpKey.startsWith(calleeParamHeapPath)) {
 513
 514             NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 515
 516             boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
 517                 .clone());
 518
 519           }
 520         }
 521       }
 522       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
 523     }
 524
 525     return boundSet;
 526   }
 527
 528   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
 529
 530     // replace the head of heap path with caller's arg path
 531     // for example, heap path 'param.a.b' in callee's side will be replaced with
 532     // (corresponding arg heap path).a.b for caller's side
 533
 534     NTuple<Descriptor> bound = new NTuple<Descriptor>();
 535
 536     for (int i = 0; i < argHeapPath.size(); i++) {
 537       bound.add(argHeapPath.get(i));
 538     }
 539
 540     for (int i = 1; i < hpKey.size(); i++) {
 541       bound.add(hpKey.get(i));
 542     }
 543
 544     return bound;
 545   }
 546
 547   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
 548       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
 549     // replace the head of caller's heap path with callee's param heap path
 550
 551     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
 552     boundHeapPath.add(calleeParamHeapPath);
 553
 554     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
 555       boundHeapPath.add(effectHeapPath.get(i));
 556     }
 557
 558     return boundHeapPath;
 559   }
 560
 561   private void computeReadSharedDescriptorSet() {
 562     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 563     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 564
 565     for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
 566       MethodDescriptor md = (MethodDescriptor) iterator.next();
 567       FlatMethod fm = state.getMethodFlat(md);
 568       computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
 569     }
 570
 571   }
 572
 573   private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
 574       boolean onlyVisitSSJavaLoop) {
 575
 576     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 577     Set<FlatNode> visited = new HashSet<FlatNode>();
 578
 579     if (onlyVisitSSJavaLoop) {
 580       flatNodesToVisit.add(ssjavaLoopEntrance);
 581     } else {
 582       flatNodesToVisit.add(fm);
 583     }
 584
 585     while (!flatNodesToVisit.isEmpty()) {
 586       FlatNode fn = flatNodesToVisit.iterator().next();
 587       flatNodesToVisit.remove(fn);
 588       visited.add(fn);
 589
 590       computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
 591
 592       for (int i = 0; i < fn.numNext(); i++) {
 593         FlatNode nn = fn.getNext(i);
 594         if (!visited.contains(nn)) {
 595           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 596             flatNodesToVisit.add(nn);
 597           }
 598         }
 599       }
 600
 601     }
 602
 603   }
 604
 605   private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
 606
 607     TempDescriptor lhs;
 608     TempDescriptor rhs;
 609     FieldDescriptor fld;
 610
 611     switch (fn.kind()) {
 612     case FKind.FlatOpNode: {
 613       FlatOpNode fon = (FlatOpNode) fn;
 614       lhs = fon.getDest();
 615       rhs = fon.getLeft();
 616
 617       if (fon.getOp().getOp() == Operation.ASSIGN) {
 618         if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
 619           // in ssjavaloop, we need to take care about reading local variables!
 620           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 621           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 622           rhsHeapPath.add(LOCAL);
 623           addReadDescriptor(rhsHeapPath, rhs);
 624         }
 625       }
 626
 627     }
 628       break;
 629
 630     case FKind.FlatFieldNode:
 631     case FKind.FlatElementNode: {
 632
 633       FlatFieldNode ffn = (FlatFieldNode) fn;
 634       lhs = ffn.getDst();
 635       rhs = ffn.getSrc();
 636       fld = ffn.getField();
 637
 638       // read field
 639       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 640       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 641       // fldHeapPath.add(fld);
 642
 643       if (fld.getType().isImmutable()) {
 644         addReadDescriptor(fldHeapPath, fld);
 645       }
 646
 647       // propagate rhs's heap path to the lhs
 648       mapHeapPath.put(lhs, fldHeapPath);
 649
 650     }
 651       break;
 652
 653     case FKind.FlatSetFieldNode:
 654     case FKind.FlatSetElementNode: {
 655
 656       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 657       lhs = fsfn.getDst();
 658       fld = fsfn.getField();
 659
 660       // write(field)
 661       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 662       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 663       // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 664
 665     }
 666       break;
 667
 668     }
 669   }
 670
 671   private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
 672     if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
 673       return false;
 674     } else {
 675       return mapSharedLocation2DescriptorSet.get(loc).contains(d);
 676     }
 677   }
 678
 679   private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
 680
 681     Location loc = getLocation(d);
 682
 683     if (loc != null && ssjava.isSharedLocation(loc)) {
 684
 685       Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
 686       if (set == null) {
 687         set = new HashSet<Descriptor>();
 688         mapSharedLocation2DescriptorSet.put(loc, set);
 689       }
 690       set.add(d);
 691     }
 692
 693   }
 694
 695   private Location getLocation(Descriptor d) {
 696
 697     if (d instanceof FieldDescriptor) {
 698       return (Location) ((FieldDescriptor) d).getType().getExtension();
 699     } else {
 700       assert d instanceof TempDescriptor;
 701       CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
 702       if (comp == null) {
 703         return null;
 704       } else {
 705         return comp.get(comp.getSize() - 1);
 706       }
 707     }
 708
 709   }
 710
 711   private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
 712     Location loc = getLocation(d);
 713     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 714
 715       // 1. add field x to the clearing set
 716       SharedStatus state = getState(curr, hp);
 717       state.addVar(loc, d);
 718
 719       // 3. if the set v contains all of variables belonging to the shared
 720       // location, set flag to true
 721       Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
 722       if (state.getVarSet(loc).containsAll(sharedVarSet)) {
 723         state.updateFlag(loc, true);
 724       }
 725     }
 726   }
 727
 728   private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
 729     // remove reading var x from written set
 730     Location loc = getLocation(d);
 731     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 732       SharedStatus state = getState(curr, hp);
 733       state.removeVar(loc, d);
 734     }
 735   }
 736
 737   private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
 738     SharedStatus state = curr.get(hp);
 739     if (state == null) {
 740       state = new SharedStatus();
 741       curr.put(hp, state);
 742     }
 743     return state;
 744   }
 745
 746   private void writtenAnalyis() {
 747     // perform second stage analysis: intraprocedural analysis ensure that
 748     // all
 749     // variables are definitely written in-between the same read
 750
 751     // First, identify ssjava loop entrace
 752     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 753     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 754     flatNodesToVisit.add(fm);
 755
 756     LoopFinder loopFinder = new LoopFinder(fm);
 757
 758     while (!flatNodesToVisit.isEmpty()) {
 759       FlatNode fn = flatNodesToVisit.iterator().next();
 760       flatNodesToVisit.remove(fn);
 761
 762       String label = (String) state.fn2labelMap.get(fn);
 763       if (label != null) {
 764
 765         if (label.equals(ssjava.SSJAVA)) {
 766           ssjavaLoopEntrance = fn;
 767           break;
 768         }
 769       }
 770
 771       for (int i = 0; i < fn.numNext(); i++) {
 772         FlatNode nn = fn.getNext(i);
 773         flatNodesToVisit.add(nn);
 774       }
 775     }
 776
 777     assert ssjavaLoopEntrance != null;
 778
 779     // assume that ssjava loop is top-level loop in method, not nested loop
 780     Set nestedLoop = loopFinder.nestedLoops();
 781     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 782       LoopFinder lf = (LoopFinder) loopIter.next();
 783       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 784         ssjavaLoop = lf;
 785       }
 786     }
 787
 788     assert ssjavaLoop != null;
 789
 790     writtenAnalysis_analyzeLoop();
 791
 792   }
 793
 794   private void writtenAnalysis_analyzeLoop() {
 795
 796     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 797     flatNodesToVisit.add(ssjavaLoopEntrance);
 798
 799     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 800
 801     while (!flatNodesToVisit.isEmpty()) {
 802       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 803       flatNodesToVisit.remove(fn);
 804
 805       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 806           definitelyWrittenResults.get(fn);
 807
 808       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 809           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 810       for (int i = 0; i < fn.numPrev(); i++) {
 811         FlatNode nn = fn.getPrev(i);
 812         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 813             definitelyWrittenResults.get(nn);
 814         if (dwIn != null) {
 815           merge(curr, dwIn);
 816         }
 817       }
 818
 819       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 820
 821       // if a new result, schedule forward nodes for analysis
 822       if (!curr.equals(prev)) {
 823         definitelyWrittenResults.put(fn, curr);
 824
 825         for (int i = 0; i < fn.numNext(); i++) {
 826           FlatNode nn = fn.getNext(i);
 827           if (loopIncElements.contains(nn)) {
 828             flatNodesToVisit.add(nn);
 829           }
 830
 831         }
 832       }
 833     }
 834   }
 835
 836   private void writtenAnalysis_nodeAction(FlatNode fn,
 837       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 838
 839     if (fn.equals(loopEntrance)) {
 840       // it reaches loop entrance: changes all flag to true
 841       Set<NTuple<Descriptor>> keySet = curr.keySet();
 842       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 843         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 844         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 845         if (pair != null) {
 846           Set<FlatNode> pairKeySet = pair.keySet();
 847           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 848             FlatNode pairKey = (FlatNode) iterator2.next();
 849             pair.put(pairKey, Boolean.TRUE);
 850           }
 851         }
 852       }
 853     } else {
 854       TempDescriptor lhs;
 855       TempDescriptor rhs;
 856       FieldDescriptor fld;
 857
 858       switch (fn.kind()) {
 859       case FKind.FlatOpNode: {
 860         FlatOpNode fon = (FlatOpNode) fn;
 861         lhs = fon.getDest();
 862         rhs = fon.getLeft();
 863
 864         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 865         if (!rhs.getType().isImmutable()) {
 866           mapHeapPath.put(lhs, rhsHeapPath);
 867         } else {
 868           if (fon.getOp().getOp() == Operation.ASSIGN) {
 869             // read(rhs)
 870             readValue(fn, rhsHeapPath, curr);
 871           }
 872           // write(lhs)
 873           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 874           removeHeapPath(curr, lhsHeapPath);
 875         }
 876       }
 877         break;
 878
 879       case FKind.FlatLiteralNode: {
 880         FlatLiteralNode fln = (FlatLiteralNode) fn;
 881         lhs = fln.getDst();
 882
 883         // write(lhs)
 884         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 885         removeHeapPath(curr, lhsHeapPath);
 886
 887       }
 888         break;
 889
 890       case FKind.FlatFieldNode:
 891       case FKind.FlatElementNode: {
 892
 893         FlatFieldNode ffn = (FlatFieldNode) fn;
 894         lhs = ffn.getDst();
 895         rhs = ffn.getSrc();
 896         fld = ffn.getField();
 897
 898         // read field
 899         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 900         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 901         fldHeapPath.add(fld);
 902
 903         if (fld.getType().isImmutable()) {
 904           readValue(fn, fldHeapPath, curr);
 905         }
 906
 907         // propagate rhs's heap path to the lhs
 908         mapHeapPath.put(lhs, fldHeapPath);
 909
 910       }
 911         break;
 912
 913       case FKind.FlatSetFieldNode:
 914       case FKind.FlatSetElementNode: {
 915
 916         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 917         lhs = fsfn.getDst();
 918         fld = fsfn.getField();
 919
 920         // write(field)
 921         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 922         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 923         fldHeapPath.add(fld);
 924         removeHeapPath(curr, fldHeapPath);
 925
 926       }
 927         break;
 928
 929       case FKind.FlatCall: {
 930         FlatCall fc = (FlatCall) fn;
 931         bindHeapPathCallerArgWithCaleeParam(fc);
 932
 933         // add <hp,statement,false> in which hp is an element of
 934         // READ_bound set
 935         // of callee: callee has 'read' requirement!
 936         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 937           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 938
 939           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 940           if (gen == null) {
 941             gen = new Hashtable<FlatNode, Boolean>();
 942             curr.put(read, gen);
 943           }
 944           Boolean currentStatus = gen.get(fn);
 945           if (currentStatus == null) {
 946             gen.put(fn, Boolean.FALSE);
 947           } else {
 948             checkFlag(currentStatus.booleanValue(), fn, read);
 949           }
 950         }
 951
 952         // removes <hp,statement,flag> if hp is an element of
 953         // OVERWRITE_bound
 954         // set of callee. it means that callee will overwrite it
 955         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 956           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 957           removeHeapPath(curr, write);
 958         }
 959       }
 960         break;
 961
 962       }
 963     }
 964
 965   }
 966
 967   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 968       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 969     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 970     if (gen == null) {
 971       gen = new Hashtable<FlatNode, Boolean>();
 972       curr.put(hp, gen);
 973     }
 974     Boolean currentStatus = gen.get(fn);
 975     if (currentStatus == null) {
 976       gen.put(fn, Boolean.FALSE);
 977     } else {
 978       checkFlag(currentStatus.booleanValue(), fn, hp);
 979     }
 980
 981   }
 982
 983   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 984       NTuple<Descriptor> hp) {
 985
 986     // removes all of heap path that starts with prefix 'hp'
 987     // since any reference overwrite along heap path gives overwriting side
 988     // effects on the value
 989
 990     Set<NTuple<Descriptor>> keySet = curr.keySet();
 991     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 992       NTuple<Descriptor> key = iter.next();
 993       if (key.startsWith(hp)) {
 994         curr.put(key, new Hashtable<FlatNode, Boolean>());
 995       }
 996     }
 997
 998   }
 999
1000   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1001     // compute all possible callee set
1002     // transform all READ/OVERWRITE set from the any possible
1003     // callees to the
1004     // caller
1005
1006     calleeUnionBoundReadSet.clear();
1007     calleeIntersectBoundOverWriteSet.clear();
1008
1009     MethodDescriptor mdCallee = fc.getMethod();
1010     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
1011     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1012     TypeDescriptor typeDesc = fc.getThis().getType();
1013     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1014
1015     // create mapping from arg idx to its heap paths
1016     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1017         new Hashtable<Integer, NTuple<Descriptor>>();
1018
1019     // arg idx is starting from 'this' arg
1020     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1021     if (thisHeapPath == null) {
1022       // method is called without creating new flat node representing 'this'
1023       thisHeapPath = new NTuple<Descriptor>();
1024       thisHeapPath.add(fc.getThis());
1025     }
1026
1027     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1028
1029     for (int i = 0; i < fc.numArgs(); i++) {
1030       TempDescriptor arg = fc.getArg(i);
1031       NTuple<Descriptor> argHeapPath = computePath(arg);
1032       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1033     }
1034
1035     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1036       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1037       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1038
1039       // binding caller's args and callee's params
1040
1041       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1042       if (calleeReadSet == null) {
1043         calleeReadSet = new HashSet<NTuple<Descriptor>>();
1044         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1045       }
1046       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1047       if (calleeOverWriteSet == null) {
1048         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1049         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1050       }
1051
1052       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1053           new Hashtable<Integer, TempDescriptor>();
1054       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1055         TempDescriptor param = calleeFlatMethod.getParameter(i);
1056         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1057       }
1058
1059       Set<NTuple<Descriptor>> calleeBoundReadSet =
1060           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1061       // union of the current read set and the current callee's
1062       // read set
1063       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1064       Set<NTuple<Descriptor>> calleeBoundWriteSet =
1065           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1066       // intersection of the current overwrite set and the current
1067       // callee's
1068       // overwrite set
1069       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1070     }
1071
1072   }
1073
1074   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1075     if (booleanValue) {
1076       throw new Error(
1077           "There is a variable, which is reachable through references "
1078               + hp
1079               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1080               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1081               + fn.getNumLine());
1082     }
1083   }
1084
1085   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1086       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1087
1088     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1089     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1090       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1091       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1092
1093       Set<FlatNode> pairKeySet = inPair.keySet();
1094       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1095         FlatNode pairKey = (FlatNode) iterator2.next();
1096         Boolean inFlag = inPair.get(pairKey);
1097
1098         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1099         if (currPair == null) {
1100           currPair = new Hashtable<FlatNode, Boolean>();
1101           curr.put(inKey, currPair);
1102         }
1103
1104         Boolean currFlag = currPair.get(pairKey);
1105         // by default, flag is set by false
1106         if (currFlag == null) {
1107           currFlag = Boolean.FALSE;
1108         }
1109         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1110         currPair.put(pairKey, currFlag);
1111       }
1112
1113     }
1114
1115   }
1116
1117   private void methodReadOverWriteAnalysis() {
1118     // perform method READ/OVERWRITE analysis
1119     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1120     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1121
1122     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1123
1124     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1125         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1126
1127     // no need to analyze method having ssjava loop
1128     methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1129
1130     // current descriptors to visit in fixed-point interprocedural analysis,
1131     // prioritized by
1132     // dependency in the call graph
1133     methodDescriptorsToVisitStack.clear();
1134
1135     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1136     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1137
1138     while (!descriptorListToAnalyze.isEmpty()) {
1139       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1140       methodDescriptorsToVisitStack.add(md);
1141     }
1142
1143     // analyze scheduled methods until there are no more to visit
1144     while (!methodDescriptorsToVisitStack.isEmpty()) {
1145       // start to analyze leaf node
1146       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1147       FlatMethod fm = state.getMethodFlat(md);
1148
1149       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1150       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1151
1152       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1153
1154       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1155       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1156
1157       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1158         mapFlatMethodToRead.put(fm, readSet);
1159         mapFlatMethodToOverWrite.put(fm, overWriteSet);
1160
1161         // results for callee changed, so enqueue dependents caller for
1162         // further
1163         // analysis
1164         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1165         while (depsItr.hasNext()) {
1166           MethodDescriptor methodNext = depsItr.next();
1167           if (!methodDescriptorsToVisitStack.contains(methodNext)
1168               && methodDescriptorToVistSet.contains(methodNext)) {
1169             methodDescriptorsToVisitStack.add(methodNext);
1170           }
1171
1172         }
1173
1174       }
1175
1176     }
1177
1178   }
1179
1180   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1181       Set<NTuple<Descriptor>> overWriteSet) {
1182     if (state.SSJAVADEBUG) {
1183       System.out.println("Definitely written Analyzing: " + fm);
1184     }
1185
1186     // intraprocedural analysis
1187     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1188     flatNodesToVisit.add(fm);
1189
1190     while (!flatNodesToVisit.isEmpty()) {
1191       FlatNode fn = flatNodesToVisit.iterator().next();
1192       flatNodesToVisit.remove(fn);
1193
1194       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1195
1196       for (int i = 0; i < fn.numPrev(); i++) {
1197         FlatNode prevFn = fn.getPrev(i);
1198         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1199         if (in != null) {
1200           merge(curr, in);
1201         }
1202       }
1203
1204       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1205
1206       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1207       if (!curr.equals(writtenSetPrev)) {
1208         mapFlatNodeToWrittenSet.put(fn, curr);
1209         for (int i = 0; i < fn.numNext(); i++) {
1210           FlatNode nn = fn.getNext(i);
1211           flatNodesToVisit.add(nn);
1212         }
1213       }
1214
1215     }
1216
1217   }
1218
1219   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1220       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1221     TempDescriptor lhs;
1222     TempDescriptor rhs;
1223     FieldDescriptor fld;
1224
1225     switch (fn.kind()) {
1226     case FKind.FlatMethod: {
1227
1228       // set up initial heap paths for method parameters
1229       FlatMethod fm = (FlatMethod) fn;
1230       for (int i = 0; i < fm.numParameters(); i++) {
1231         TempDescriptor param = fm.getParameter(i);
1232         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1233         heapPath.add(param);
1234         mapHeapPath.put(param, heapPath);
1235       }
1236     }
1237       break;
1238
1239     case FKind.FlatOpNode: {
1240       FlatOpNode fon = (FlatOpNode) fn;
1241       // for a normal assign node, need to propagate lhs's heap path to
1242       // rhs
1243       if (fon.getOp().getOp() == Operation.ASSIGN) {
1244         rhs = fon.getLeft();
1245         lhs = fon.getDest();
1246
1247         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1248         if (rhsHeapPath != null) {
1249           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1250         }
1251
1252       }
1253     }
1254       break;
1255
1256     case FKind.FlatFieldNode:
1257     case FKind.FlatElementNode: {
1258
1259       // y=x.f;
1260
1261       FlatFieldNode ffn = (FlatFieldNode) fn;
1262       lhs = ffn.getDst();
1263       rhs = ffn.getSrc();
1264       fld = ffn.getField();
1265
1266       // set up heap path
1267       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1268       if (srcHeapPath != null) {
1269         // if lhs srcHeapPath is null, it means that it is not reachable from
1270         // callee's parameters. so just ignore it
1271
1272         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1273         readingHeapPath.add(fld);
1274         mapHeapPath.put(lhs, readingHeapPath);
1275
1276         // read (x.f)
1277         if (fld.getType().isImmutable()) {
1278           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1279           if (!writtenSet.contains(readingHeapPath)) {
1280             readSet.add(readingHeapPath);
1281           }
1282         }
1283
1284         // need to kill hp(x.f) from WT
1285         writtenSet.remove(readingHeapPath);
1286       }
1287
1288     }
1289       break;
1290
1291     case FKind.FlatSetFieldNode:
1292     case FKind.FlatSetElementNode: {
1293
1294       // x.f=y;
1295       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1296       lhs = fsfn.getDst();
1297       fld = fsfn.getField();
1298       rhs = fsfn.getSrc();
1299
1300       // set up heap path
1301       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1302       if (lhsHeapPath != null) {
1303         // if lhs heap path is null, it means that it is not reachable from
1304         // callee's parameters. so just ignore it
1305         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1306         newHeapPath.add(fld);
1307         mapHeapPath.put(fld, newHeapPath);
1308
1309         // write(x.f)
1310         // need to add hp(y) to WT
1311         writtenSet.add(newHeapPath);
1312       }
1313
1314     }
1315       break;
1316
1317     case FKind.FlatCall: {
1318
1319       FlatCall fc = (FlatCall) fn;
1320
1321       bindHeapPathCallerArgWithCaleeParam(fc);
1322
1323       // add heap path, which is an element of READ_bound set and is not
1324       // an
1325       // element of WT set, to the caller's READ set
1326       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1327         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1328         if (!writtenSet.contains(read)) {
1329           readSet.add(read);
1330         }
1331       }
1332       writtenSet.removeAll(calleeUnionBoundReadSet);
1333
1334       // add heap path, which is an element of OVERWRITE_bound set, to the
1335       // caller's WT set
1336       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1337         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1338         writtenSet.add(write);
1339       }
1340
1341     }
1342       break;
1343
1344     case FKind.FlatExit: {
1345       // merge the current written set with OVERWRITE set
1346       merge(overWriteSet, writtenSet);
1347     }
1348       break;
1349
1350     }
1351
1352   }
1353
1354   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1355
1356     if (inSet.size() == 0) {
1357       return;
1358     }
1359
1360     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1361         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1362
1363     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1364
1365       ClearingSummary inTable = (ClearingSummary) inIterator.next();
1366
1367       Set<NTuple<Descriptor>> keySet = inTable.keySet();
1368
1369       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1370         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1371         SharedStatus inState = inTable.get(hpKey);
1372
1373         SharedStatus currState = curr.get(hpKey);
1374         if (currState == null) {
1375           currState = new SharedStatus();
1376           curr.put(hpKey, currState);
1377         }
1378         currState.merge(inState);
1379
1380         Set<Location> locSet = inState.getMap().keySet();
1381         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1382           Location loc = (Location) iterator2.next();
1383           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1384           boolean inFlag = pair.getSecond().booleanValue();
1385
1386           Pair<NTuple<Descriptor>, Location> flagKey =
1387               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1388           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1389           if (current == null) {
1390             current = new Boolean(true);
1391           }
1392           boolean newInFlag = current.booleanValue() & inFlag;
1393           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1394         }
1395
1396       }
1397
1398     }
1399
1400     // merge flag status
1401     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1402     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1403       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1404       SharedStatus currState = curr.get(hpKey);
1405       Set<Location> locKeySet = currState.getMap().keySet();
1406       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1407         Location locKey = (Location) iterator2.next();
1408         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1409         boolean currentFlag = pair.getSecond().booleanValue();
1410         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1411         if (inFlag != null) {
1412           boolean newFlag = currentFlag | inFlag.booleanValue();
1413           if (currentFlag != newFlag) {
1414             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1415           }
1416         }
1417       }
1418     }
1419
1420   }
1421
1422   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1423     if (curr.isEmpty()) {
1424       // WrittenSet has a special initial value which covers all possible
1425       // elements
1426       // For the first time of intersection, we can take all previous set
1427       curr.addAll(in);
1428     } else {
1429       // otherwise, current set is the intersection of the two sets
1430       curr.retainAll(in);
1431     }
1432
1433   }
1434
1435   // combine two heap path
1436   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1437     NTuple<Descriptor> combined = new NTuple<Descriptor>();
1438
1439     for (int i = 0; i < callerIn.size(); i++) {
1440       combined.add(callerIn.get(i));
1441     }
1442
1443     // the first element of callee's heap path represents parameter
1444     // so we skip the first one since it is already added from caller's heap
1445     // path
1446     for (int i = 1; i < calleeIn.size(); i++) {
1447       combined.add(calleeIn.get(i));
1448     }
1449
1450     return combined;
1451   }
1452
1453   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1454       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1455       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1456
1457     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1458
1459     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1460     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1461       Integer idx = (Integer) iterator.next();
1462
1463       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1464       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1465
1466       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1467         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1468         if (element.startsWith(calleeParam)) {
1469           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1470           boundedCalleeSet.add(boundElement);
1471         }
1472
1473       }
1474
1475     }
1476     return boundedCalleeSet;
1477
1478   }
1479
1480   // Borrowed it from disjoint analysis
1481   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1482
1483     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1484
1485     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1486
1487     Iterator<MethodDescriptor> itr = toSort.iterator();
1488     while (itr.hasNext()) {
1489       MethodDescriptor d = itr.next();
1490
1491       if (!discovered.contains(d)) {
1492         dfsVisit(d, toSort, sorted, discovered);
1493       }
1494     }
1495
1496     return sorted;
1497   }
1498
1499   // While we're doing DFS on call graph, remember
1500   // dependencies for efficient queuing of methods
1501   // during interprocedural analysis:
1502   //
1503   // a dependent of a method decriptor d for this analysis is:
1504   // 1) a method or task that invokes d
1505   // 2) in the descriptorsToAnalyze set
1506   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1507       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1508
1509     discovered.add(md);
1510
1511     Iterator itr = callGraph.getCallerSet(md).iterator();
1512     while (itr.hasNext()) {
1513       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1514       // only consider callers in the original set to analyze
1515       if (!toSort.contains(dCaller)) {
1516         continue;
1517       }
1518       if (!discovered.contains(dCaller)) {
1519         addDependent(md, // callee
1520             dCaller // caller
1521         );
1522
1523         dfsVisit(dCaller, toSort, sorted, discovered);
1524       }
1525     }
1526
1527     // for leaf-nodes last now!
1528     sorted.addLast(md);
1529   }
1530
1531   // a dependent of a method decriptor d for this analysis is:
1532   // 1) a method or task that invokes d
1533   // 2) in the descriptorsToAnalyze set
1534   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1535     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1536     if (deps == null) {
1537       deps = new HashSet<MethodDescriptor>();
1538     }
1539     deps.add(caller);
1540     mapDescriptorToSetDependents.put(callee, deps);
1541   }
1542
1543   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1544     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1545     if (deps == null) {
1546       deps = new HashSet<MethodDescriptor>();
1547       mapDescriptorToSetDependents.put(callee, deps);
1548     }
1549     return deps;
1550   }
1551
1552   private NTuple<Descriptor> computePath(TempDescriptor td) {
1553     // generate proper path fot input td
1554     // if td is local variable, it just generate one element tuple path
1555     if (mapHeapPath.containsKey(td)) {
1556       return mapHeapPath.get(td);
1557     } else {
1558       NTuple<Descriptor> path = new NTuple<Descriptor>();
1559       path.add(td);
1560       return path;
1561     }
1562   }
1563
1564 }