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       }
 369
 370     }
 371       break;
 372
 373     case FKind.FlatCall: {
 374
 375       FlatCall fc = (FlatCall) fn;
 376
 377       // find out the set of callees
 378       MethodDescriptor mdCallee = fc.getMethod();
 379       FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 380       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 381       TypeDescriptor typeDesc = fc.getThis().getType();
 382       setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 383
 384       possibleCalleeCompleteSummarySetToCaller.clear();
 385
 386       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 387         MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 388         FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 389
 390         addDependent(mdPossibleCallee, // callee
 391             caller); // caller
 392
 393         calleesToEnqueue.add(mdPossibleCallee);
 394
 395         // updates possible callee's initial summary using caller's current
 396         // writing status
 397         ClearingSummary prevCalleeInitSummary =
 398             mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 399
 400         ClearingSummary calleeInitSummary =
 401             bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 402
 403         // if changes, update the init summary
 404         // and reschedule the callee for analysis
 405         if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 406
 407           if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
 408             methodDescriptorsToVisitStack.add(mdPossibleCallee);
 409           }
 410           mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 411         }
 412
 413       }
 414
 415       // contribute callee's writing effects to the caller
 416       mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 417
 418     }
 419       break;
 420
 421     case FKind.FlatReturnNode: {
 422       returnNodeSet.add(fn);
 423     }
 424       break;
 425
 426     }
 427
 428   }
 429
 430   private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
 431       FlatMethod calleeFlatMethod, ClearingSummary curr) {
 432
 433     ClearingSummary boundSet = new ClearingSummary();
 434
 435     // create mapping from arg idx to its heap paths
 436     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 437         new Hashtable<Integer, NTuple<Descriptor>>();
 438
 439     // arg idx is starting from 'this' arg
 440     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 441     if (thisHeapPath == null) {
 442       // method is called without creating new flat node representing 'this'
 443       thisHeapPath = new NTuple<Descriptor>();
 444       thisHeapPath.add(fc.getThis());
 445     }
 446
 447     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 448
 449     for (int i = 0; i < fc.numArgs(); i++) {
 450       TempDescriptor arg = fc.getArg(i);
 451       NTuple<Descriptor> argHeapPath = computePath(arg);
 452       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 453     }
 454
 455     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 456         new Hashtable<Integer, TempDescriptor>();
 457     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 458       TempDescriptor param = calleeFlatMethod.getParameter(i);
 459       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 460     }
 461
 462     // binding caller's writing effects to callee's params
 463     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 464       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 465       TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 466
 467       // iterate over caller's writing effect set
 468       Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 469       for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 470         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 471         // current element is reachable caller's arg
 472         // so need to bind it to the caller's side and add it to the callee's
 473         // init summary
 474         if (hpKey.startsWith(argHeapPath)) {
 475           NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 476           boundSet.put(boundHeapPath, curr.get(hpKey).clone());
 477         }
 478
 479       }
 480
 481     }
 482
 483     // contribute callee's complete summary into the caller's current summary
 484     ClearingSummary calleeCompleteSummary =
 485         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
 486
 487     if (calleeCompleteSummary != null) {
 488       ClearingSummary boundCalleeEfffects = new ClearingSummary();
 489       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 490         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 491         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 492
 493         // iterate over callee's writing effect set
 494         Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
 495         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 496           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 497           // current element is reachable caller's arg
 498           // so need to bind it to the caller's side and add it to the callee's
 499           // init summary
 500           if (hpKey.startsWith(calleeParamHeapPath)) {
 501
 502             NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 503
 504             boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
 505                 .clone());
 506
 507           }
 508         }
 509       }
 510       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
 511     }
 512
 513     return boundSet;
 514   }
 515
 516   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
 517
 518     // replace the head of heap path with caller's arg path
 519     // for example, heap path 'param.a.b' in callee's side will be replaced with
 520     // (corresponding arg heap path).a.b for caller's side
 521
 522     NTuple<Descriptor> bound = new NTuple<Descriptor>();
 523
 524     for (int i = 0; i < argHeapPath.size(); i++) {
 525       bound.add(argHeapPath.get(i));
 526     }
 527
 528     for (int i = 1; i < hpKey.size(); i++) {
 529       bound.add(hpKey.get(i));
 530     }
 531
 532     return bound;
 533   }
 534
 535   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
 536       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
 537     // replace the head of caller's heap path with callee's param heap path
 538
 539     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
 540     boundHeapPath.add(calleeParamHeapPath);
 541
 542     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
 543       boundHeapPath.add(effectHeapPath.get(i));
 544     }
 545
 546     return boundHeapPath;
 547   }
 548
 549   private void computeReadSharedDescriptorSet() {
 550     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 551     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 552
 553     for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
 554       MethodDescriptor md = (MethodDescriptor) iterator.next();
 555       FlatMethod fm = state.getMethodFlat(md);
 556       computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
 557     }
 558
 559   }
 560
 561   private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
 562       boolean onlyVisitSSJavaLoop) {
 563
 564     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 565     Set<FlatNode> visited = new HashSet<FlatNode>();
 566
 567     if (onlyVisitSSJavaLoop) {
 568       flatNodesToVisit.add(ssjavaLoopEntrance);
 569     } else {
 570       flatNodesToVisit.add(fm);
 571     }
 572
 573     while (!flatNodesToVisit.isEmpty()) {
 574       FlatNode fn = flatNodesToVisit.iterator().next();
 575       flatNodesToVisit.remove(fn);
 576       visited.add(fn);
 577
 578       computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
 579
 580       for (int i = 0; i < fn.numNext(); i++) {
 581         FlatNode nn = fn.getNext(i);
 582         if (!visited.contains(nn)) {
 583           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 584             flatNodesToVisit.add(nn);
 585           }
 586         }
 587       }
 588
 589     }
 590
 591   }
 592
 593   private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
 594
 595     TempDescriptor lhs;
 596     TempDescriptor rhs;
 597     FieldDescriptor fld;
 598
 599     switch (fn.kind()) {
 600     case FKind.FlatOpNode: {
 601       FlatOpNode fon = (FlatOpNode) fn;
 602       lhs = fon.getDest();
 603       rhs = fon.getLeft();
 604
 605       if (fon.getOp().getOp() == Operation.ASSIGN) {
 606         if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
 607           // in ssjavaloop, we need to take care about reading local variables!
 608           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 609           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 610           rhsHeapPath.add(LOCAL);
 611           addReadDescriptor(rhsHeapPath, rhs);
 612         }
 613       }
 614
 615     }
 616       break;
 617
 618     case FKind.FlatFieldNode:
 619     case FKind.FlatElementNode: {
 620
 621       FlatFieldNode ffn = (FlatFieldNode) fn;
 622       lhs = ffn.getDst();
 623       rhs = ffn.getSrc();
 624       fld = ffn.getField();
 625
 626       // read field
 627       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 628       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 629       // fldHeapPath.add(fld);
 630
 631       if (fld.getType().isImmutable()) {
 632         addReadDescriptor(fldHeapPath, fld);
 633       }
 634
 635       // propagate rhs's heap path to the lhs
 636       mapHeapPath.put(lhs, fldHeapPath);
 637
 638     }
 639       break;
 640
 641     case FKind.FlatSetFieldNode:
 642     case FKind.FlatSetElementNode: {
 643
 644       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 645       lhs = fsfn.getDst();
 646       fld = fsfn.getField();
 647
 648       // write(field)
 649       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 650       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 651       // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 652
 653     }
 654       break;
 655
 656     }
 657   }
 658
 659   private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
 660     if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
 661       return false;
 662     } else {
 663       return mapSharedLocation2DescriptorSet.get(loc).contains(d);
 664     }
 665   }
 666
 667   private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
 668
 669     Location loc = getLocation(d);
 670
 671     if (loc != null && ssjava.isSharedLocation(loc)) {
 672
 673       Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
 674       if (set == null) {
 675         set = new HashSet<Descriptor>();
 676         mapSharedLocation2DescriptorSet.put(loc, set);
 677       }
 678       set.add(d);
 679     }
 680
 681   }
 682
 683   private Location getLocation(Descriptor d) {
 684
 685     if (d instanceof FieldDescriptor) {
 686       return (Location) ((FieldDescriptor) d).getType().getExtension();
 687     } else {
 688       assert d instanceof TempDescriptor;
 689       CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
 690       if (comp == null) {
 691         return null;
 692       } else {
 693         return comp.get(comp.getSize() - 1);
 694       }
 695     }
 696
 697   }
 698
 699   private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
 700     Location loc = getLocation(d);
 701     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 702       SharedStatus state = getState(curr, hp);
 703       state.addVar(loc, d);
 704
 705       // if the set v contains all of variables belonging to the shared
 706       // location, set flag to true
 707
 708       Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
 709
 710       if (state.getVarSet(loc).containsAll(sharedVarSet)) {
 711         state.updateFlag(loc, true);
 712       }
 713     }
 714   }
 715
 716   private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
 717     // remove reading var x from written set
 718     Location loc = getLocation(d);
 719     if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
 720       SharedStatus state = getState(curr, hp);
 721       state.removeVar(loc, d);
 722     }
 723   }
 724
 725   private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
 726     SharedStatus state = curr.get(hp);
 727     if (state == null) {
 728       state = new SharedStatus();
 729       curr.put(hp, state);
 730     }
 731     return state;
 732   }
 733
 734   private void writtenAnalyis() {
 735     // perform second stage analysis: intraprocedural analysis ensure that
 736     // all
 737     // variables are definitely written in-between the same read
 738
 739     // First, identify ssjava loop entrace
 740     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 741     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 742     flatNodesToVisit.add(fm);
 743
 744     LoopFinder loopFinder = new LoopFinder(fm);
 745
 746     while (!flatNodesToVisit.isEmpty()) {
 747       FlatNode fn = flatNodesToVisit.iterator().next();
 748       flatNodesToVisit.remove(fn);
 749
 750       String label = (String) state.fn2labelMap.get(fn);
 751       if (label != null) {
 752
 753         if (label.equals(ssjava.SSJAVA)) {
 754           ssjavaLoopEntrance = fn;
 755           break;
 756         }
 757       }
 758
 759       for (int i = 0; i < fn.numNext(); i++) {
 760         FlatNode nn = fn.getNext(i);
 761         flatNodesToVisit.add(nn);
 762       }
 763     }
 764
 765     assert ssjavaLoopEntrance != null;
 766
 767     // assume that ssjava loop is top-level loop in method, not nested loop
 768     Set nestedLoop = loopFinder.nestedLoops();
 769     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 770       LoopFinder lf = (LoopFinder) loopIter.next();
 771       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 772         ssjavaLoop = lf;
 773       }
 774     }
 775
 776     assert ssjavaLoop != null;
 777
 778     writtenAnalysis_analyzeLoop();
 779
 780   }
 781
 782   private void writtenAnalysis_analyzeLoop() {
 783
 784     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 785     flatNodesToVisit.add(ssjavaLoopEntrance);
 786
 787     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 788
 789     while (!flatNodesToVisit.isEmpty()) {
 790       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 791       flatNodesToVisit.remove(fn);
 792
 793       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 794           definitelyWrittenResults.get(fn);
 795
 796       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 797           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 798       for (int i = 0; i < fn.numPrev(); i++) {
 799         FlatNode nn = fn.getPrev(i);
 800         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 801             definitelyWrittenResults.get(nn);
 802         if (dwIn != null) {
 803           merge(curr, dwIn);
 804         }
 805       }
 806
 807       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 808
 809       // if a new result, schedule forward nodes for analysis
 810       if (!curr.equals(prev)) {
 811         definitelyWrittenResults.put(fn, curr);
 812
 813         for (int i = 0; i < fn.numNext(); i++) {
 814           FlatNode nn = fn.getNext(i);
 815           if (loopIncElements.contains(nn)) {
 816             flatNodesToVisit.add(nn);
 817           }
 818
 819         }
 820       }
 821     }
 822   }
 823
 824   private void writtenAnalysis_nodeAction(FlatNode fn,
 825       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 826
 827     if (fn.equals(loopEntrance)) {
 828       // it reaches loop entrance: changes all flag to true
 829       Set<NTuple<Descriptor>> keySet = curr.keySet();
 830       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 831         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 832         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 833         if (pair != null) {
 834           Set<FlatNode> pairKeySet = pair.keySet();
 835           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 836             FlatNode pairKey = (FlatNode) iterator2.next();
 837             pair.put(pairKey, Boolean.TRUE);
 838           }
 839         }
 840       }
 841     } else {
 842       TempDescriptor lhs;
 843       TempDescriptor rhs;
 844       FieldDescriptor fld;
 845
 846       switch (fn.kind()) {
 847       case FKind.FlatOpNode: {
 848         FlatOpNode fon = (FlatOpNode) fn;
 849         lhs = fon.getDest();
 850         rhs = fon.getLeft();
 851
 852         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 853         if (!rhs.getType().isImmutable()) {
 854           mapHeapPath.put(lhs, rhsHeapPath);
 855         } else {
 856           if (fon.getOp().getOp() == Operation.ASSIGN) {
 857             // read(rhs)
 858             readValue(fn, rhsHeapPath, curr);
 859           }
 860           // write(lhs)
 861           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 862           removeHeapPath(curr, lhsHeapPath);
 863         }
 864       }
 865         break;
 866
 867       case FKind.FlatLiteralNode: {
 868         FlatLiteralNode fln = (FlatLiteralNode) fn;
 869         lhs = fln.getDst();
 870
 871         // write(lhs)
 872         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 873         removeHeapPath(curr, lhsHeapPath);
 874
 875       }
 876         break;
 877
 878       case FKind.FlatFieldNode:
 879       case FKind.FlatElementNode: {
 880
 881         FlatFieldNode ffn = (FlatFieldNode) fn;
 882         lhs = ffn.getDst();
 883         rhs = ffn.getSrc();
 884         fld = ffn.getField();
 885
 886         // read field
 887         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 888         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 889         fldHeapPath.add(fld);
 890
 891         if (fld.getType().isImmutable()) {
 892           readValue(fn, fldHeapPath, curr);
 893         }
 894
 895         // propagate rhs's heap path to the lhs
 896         mapHeapPath.put(lhs, fldHeapPath);
 897
 898       }
 899         break;
 900
 901       case FKind.FlatSetFieldNode:
 902       case FKind.FlatSetElementNode: {
 903
 904         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 905         lhs = fsfn.getDst();
 906         fld = fsfn.getField();
 907
 908         // write(field)
 909         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 910         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 911         fldHeapPath.add(fld);
 912         removeHeapPath(curr, fldHeapPath);
 913
 914       }
 915         break;
 916
 917       case FKind.FlatCall: {
 918         FlatCall fc = (FlatCall) fn;
 919         bindHeapPathCallerArgWithCaleeParam(fc);
 920
 921         // add <hp,statement,false> in which hp is an element of
 922         // READ_bound set
 923         // of callee: callee has 'read' requirement!
 924         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 925           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 926
 927           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 928           if (gen == null) {
 929             gen = new Hashtable<FlatNode, Boolean>();
 930             curr.put(read, gen);
 931           }
 932           Boolean currentStatus = gen.get(fn);
 933           if (currentStatus == null) {
 934             gen.put(fn, Boolean.FALSE);
 935           } else {
 936             checkFlag(currentStatus.booleanValue(), fn, read);
 937           }
 938         }
 939
 940         // removes <hp,statement,flag> if hp is an element of
 941         // OVERWRITE_bound
 942         // set of callee. it means that callee will overwrite it
 943         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 944           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 945           removeHeapPath(curr, write);
 946         }
 947       }
 948         break;
 949
 950       }
 951     }
 952
 953   }
 954
 955   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 956       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 957     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 958     if (gen == null) {
 959       gen = new Hashtable<FlatNode, Boolean>();
 960       curr.put(hp, gen);
 961     }
 962     Boolean currentStatus = gen.get(fn);
 963     if (currentStatus == null) {
 964       gen.put(fn, Boolean.FALSE);
 965     } else {
 966       checkFlag(currentStatus.booleanValue(), fn, hp);
 967     }
 968
 969   }
 970
 971   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 972       NTuple<Descriptor> hp) {
 973
 974     // removes all of heap path that starts with prefix 'hp'
 975     // since any reference overwrite along heap path gives overwriting side
 976     // effects on the value
 977
 978     Set<NTuple<Descriptor>> keySet = curr.keySet();
 979     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 980       NTuple<Descriptor> key = iter.next();
 981       if (key.startsWith(hp)) {
 982         curr.put(key, new Hashtable<FlatNode, Boolean>());
 983       }
 984     }
 985
 986   }
 987
 988   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
 989     // compute all possible callee set
 990     // transform all READ/OVERWRITE set from the any possible
 991     // callees to the
 992     // caller
 993
 994     calleeUnionBoundReadSet.clear();
 995     calleeIntersectBoundOverWriteSet.clear();
 996
 997     MethodDescriptor mdCallee = fc.getMethod();
 998     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 999     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1000     TypeDescriptor typeDesc = fc.getThis().getType();
1001     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
1002
1003     // create mapping from arg idx to its heap paths
1004     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1005         new Hashtable<Integer, NTuple<Descriptor>>();
1006
1007     // arg idx is starting from 'this' arg
1008     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1009     if (thisHeapPath == null) {
1010       // method is called without creating new flat node representing 'this'
1011       thisHeapPath = new NTuple<Descriptor>();
1012       thisHeapPath.add(fc.getThis());
1013     }
1014
1015     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1016
1017     for (int i = 0; i < fc.numArgs(); i++) {
1018       TempDescriptor arg = fc.getArg(i);
1019       NTuple<Descriptor> argHeapPath = computePath(arg);
1020       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1021     }
1022
1023     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1024       MethodDescriptor callee = (MethodDescriptor) iterator.next();
1025       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1026
1027       // binding caller's args and callee's params
1028
1029       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
1030       if (calleeReadSet == null) {
1031         calleeReadSet = new HashSet<NTuple<Descriptor>>();
1032         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
1033       }
1034       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
1035       if (calleeOverWriteSet == null) {
1036         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
1037         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
1038       }
1039
1040       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1041           new Hashtable<Integer, TempDescriptor>();
1042       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1043         TempDescriptor param = calleeFlatMethod.getParameter(i);
1044         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
1045       }
1046
1047       Set<NTuple<Descriptor>> calleeBoundReadSet =
1048           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1049       // union of the current read set and the current callee's
1050       // read set
1051       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1052       Set<NTuple<Descriptor>> calleeBoundWriteSet =
1053           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1054       // intersection of the current overwrite set and the current
1055       // callee's
1056       // overwrite set
1057       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
1058     }
1059
1060   }
1061
1062   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1063     if (booleanValue) {
1064       throw new Error(
1065           "There is a variable, which is reachable through references "
1066               + hp
1067               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1068               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1069               + fn.getNumLine());
1070     }
1071   }
1072
1073   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
1074       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
1075
1076     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1077     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1078       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1079       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
1080
1081       Set<FlatNode> pairKeySet = inPair.keySet();
1082       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
1083         FlatNode pairKey = (FlatNode) iterator2.next();
1084         Boolean inFlag = inPair.get(pairKey);
1085
1086         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
1087         if (currPair == null) {
1088           currPair = new Hashtable<FlatNode, Boolean>();
1089           curr.put(inKey, currPair);
1090         }
1091
1092         Boolean currFlag = currPair.get(pairKey);
1093         // by default, flag is set by false
1094         if (currFlag == null) {
1095           currFlag = Boolean.FALSE;
1096         }
1097         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
1098         currPair.put(pairKey, currFlag);
1099       }
1100
1101     }
1102
1103   }
1104
1105   private void methodReadOverWriteAnalysis() {
1106     // perform method READ/OVERWRITE analysis
1107     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1108     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1109
1110     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1111
1112     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1113         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1114
1115     // no need to analyze method having ssjava loop
1116     methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
1117
1118     // current descriptors to visit in fixed-point interprocedural analysis,
1119     // prioritized by
1120     // dependency in the call graph
1121     methodDescriptorsToVisitStack.clear();
1122
1123     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1124     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1125
1126     while (!descriptorListToAnalyze.isEmpty()) {
1127       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1128       methodDescriptorsToVisitStack.add(md);
1129     }
1130
1131     // analyze scheduled methods until there are no more to visit
1132     while (!methodDescriptorsToVisitStack.isEmpty()) {
1133       // start to analyze leaf node
1134       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1135       FlatMethod fm = state.getMethodFlat(md);
1136
1137       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1138       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
1139
1140       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
1141
1142       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
1143       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
1144
1145       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
1146         mapFlatMethodToRead.put(fm, readSet);
1147         mapFlatMethodToOverWrite.put(fm, overWriteSet);
1148
1149         // results for callee changed, so enqueue dependents caller for
1150         // further
1151         // analysis
1152         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1153         while (depsItr.hasNext()) {
1154           MethodDescriptor methodNext = depsItr.next();
1155           if (!methodDescriptorsToVisitStack.contains(methodNext)
1156               && methodDescriptorToVistSet.contains(methodNext)) {
1157             methodDescriptorsToVisitStack.add(methodNext);
1158           }
1159
1160         }
1161
1162       }
1163
1164     }
1165
1166   }
1167
1168   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1169       Set<NTuple<Descriptor>> overWriteSet) {
1170     if (state.SSJAVADEBUG) {
1171       System.out.println("Definitely written Analyzing: " + fm);
1172     }
1173
1174     // intraprocedural analysis
1175     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1176     flatNodesToVisit.add(fm);
1177
1178     while (!flatNodesToVisit.isEmpty()) {
1179       FlatNode fn = flatNodesToVisit.iterator().next();
1180       flatNodesToVisit.remove(fn);
1181
1182       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
1183
1184       for (int i = 0; i < fn.numPrev(); i++) {
1185         FlatNode prevFn = fn.getPrev(i);
1186         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
1187         if (in != null) {
1188           merge(curr, in);
1189         }
1190       }
1191
1192       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
1193
1194       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
1195       if (!curr.equals(writtenSetPrev)) {
1196         mapFlatNodeToWrittenSet.put(fn, curr);
1197         for (int i = 0; i < fn.numNext(); i++) {
1198           FlatNode nn = fn.getNext(i);
1199           flatNodesToVisit.add(nn);
1200         }
1201       }
1202
1203     }
1204
1205   }
1206
1207   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
1208       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
1209     TempDescriptor lhs;
1210     TempDescriptor rhs;
1211     FieldDescriptor fld;
1212
1213     switch (fn.kind()) {
1214     case FKind.FlatMethod: {
1215
1216       // set up initial heap paths for method parameters
1217       FlatMethod fm = (FlatMethod) fn;
1218       for (int i = 0; i < fm.numParameters(); i++) {
1219         TempDescriptor param = fm.getParameter(i);
1220         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1221         heapPath.add(param);
1222         mapHeapPath.put(param, heapPath);
1223       }
1224     }
1225       break;
1226
1227     case FKind.FlatOpNode: {
1228       FlatOpNode fon = (FlatOpNode) fn;
1229       // for a normal assign node, need to propagate lhs's heap path to
1230       // rhs
1231       if (fon.getOp().getOp() == Operation.ASSIGN) {
1232         rhs = fon.getLeft();
1233         lhs = fon.getDest();
1234
1235         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1236         if (rhsHeapPath != null) {
1237           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1238         }
1239
1240       }
1241     }
1242       break;
1243
1244     case FKind.FlatFieldNode:
1245     case FKind.FlatElementNode: {
1246
1247       // y=x.f;
1248
1249       FlatFieldNode ffn = (FlatFieldNode) fn;
1250       lhs = ffn.getDst();
1251       rhs = ffn.getSrc();
1252       fld = ffn.getField();
1253
1254       // set up heap path
1255       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1256       if (srcHeapPath != null) {
1257         // if lhs srcHeapPath is null, it means that it is not reachable from
1258         // callee's parameters. so just ignore it
1259
1260         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1261         readingHeapPath.add(fld);
1262         mapHeapPath.put(lhs, readingHeapPath);
1263
1264         // read (x.f)
1265         if (fld.getType().isImmutable()) {
1266           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1267           if (!writtenSet.contains(readingHeapPath)) {
1268             readSet.add(readingHeapPath);
1269           }
1270         }
1271
1272         // need to kill hp(x.f) from WT
1273         writtenSet.remove(readingHeapPath);
1274       }
1275
1276     }
1277       break;
1278
1279     case FKind.FlatSetFieldNode:
1280     case FKind.FlatSetElementNode: {
1281
1282       // x.f=y;
1283       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1284       lhs = fsfn.getDst();
1285       fld = fsfn.getField();
1286       rhs = fsfn.getSrc();
1287
1288       // set up heap path
1289       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1290       if (lhsHeapPath != null) {
1291         // if lhs heap path is null, it means that it is not reachable from
1292         // callee's parameters. so just ignore it
1293         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1294         newHeapPath.add(fld);
1295         mapHeapPath.put(fld, newHeapPath);
1296
1297         // write(x.f)
1298         // need to add hp(y) to WT
1299         writtenSet.add(newHeapPath);
1300       }
1301
1302     }
1303       break;
1304
1305     case FKind.FlatCall: {
1306
1307       FlatCall fc = (FlatCall) fn;
1308
1309       bindHeapPathCallerArgWithCaleeParam(fc);
1310
1311       // add heap path, which is an element of READ_bound set and is not
1312       // an
1313       // element of WT set, to the caller's READ set
1314       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1315         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1316         if (!writtenSet.contains(read)) {
1317           readSet.add(read);
1318         }
1319       }
1320       writtenSet.removeAll(calleeUnionBoundReadSet);
1321
1322       // add heap path, which is an element of OVERWRITE_bound set, to the
1323       // caller's WT set
1324       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
1325         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1326         writtenSet.add(write);
1327       }
1328
1329     }
1330       break;
1331
1332     case FKind.FlatExit: {
1333       // merge the current written set with OVERWRITE set
1334       merge(overWriteSet, writtenSet);
1335     }
1336       break;
1337
1338     }
1339
1340   }
1341
1342   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1343
1344     if (inSet.size() == 0) {
1345       return;
1346     }
1347
1348     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1349         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1350
1351     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1352
1353       ClearingSummary inTable = (ClearingSummary) inIterator.next();
1354
1355       Set<NTuple<Descriptor>> keySet = inTable.keySet();
1356
1357       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1358         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1359         SharedStatus inState = inTable.get(hpKey);
1360
1361         SharedStatus currState = curr.get(hpKey);
1362         if (currState == null) {
1363           currState = new SharedStatus();
1364           curr.put(hpKey, currState);
1365         }
1366         currState.merge(inState);
1367
1368         Set<Location> locSet = inState.getMap().keySet();
1369         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1370           Location loc = (Location) iterator2.next();
1371           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1372           boolean inFlag = pair.getSecond().booleanValue();
1373
1374           Pair<NTuple<Descriptor>, Location> flagKey =
1375               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1376           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1377           if (current == null) {
1378             current = new Boolean(true);
1379           }
1380           boolean newInFlag = current.booleanValue() & inFlag;
1381           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1382         }
1383
1384       }
1385
1386     }
1387
1388     // merge flag status
1389     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1390     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1391       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1392       SharedStatus currState = curr.get(hpKey);
1393       Set<Location> locKeySet = currState.getMap().keySet();
1394       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1395         Location locKey = (Location) iterator2.next();
1396         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1397         boolean currentFlag = pair.getSecond().booleanValue();
1398         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1399         if (inFlag != null) {
1400           boolean newFlag = currentFlag | inFlag.booleanValue();
1401           if (currentFlag != newFlag) {
1402             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1403           }
1404         }
1405       }
1406     }
1407
1408   }
1409
1410   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1411     if (curr.isEmpty()) {
1412       // WrittenSet has a special initial value which covers all possible
1413       // elements
1414       // For the first time of intersection, we can take all previous set
1415       curr.addAll(in);
1416     } else {
1417       // otherwise, current set is the intersection of the two sets
1418       curr.retainAll(in);
1419     }
1420
1421   }
1422
1423   // combine two heap path
1424   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1425     NTuple<Descriptor> combined = new NTuple<Descriptor>();
1426
1427     for (int i = 0; i < callerIn.size(); i++) {
1428       combined.add(callerIn.get(i));
1429     }
1430
1431     // the first element of callee's heap path represents parameter
1432     // so we skip the first one since it is already added from caller's heap
1433     // path
1434     for (int i = 1; i < calleeIn.size(); i++) {
1435       combined.add(calleeIn.get(i));
1436     }
1437
1438     return combined;
1439   }
1440
1441   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1442       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1443       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1444
1445     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1446
1447     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1448     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1449       Integer idx = (Integer) iterator.next();
1450
1451       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1452       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1453
1454       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1455         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1456         if (element.startsWith(calleeParam)) {
1457           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1458           boundedCalleeSet.add(boundElement);
1459         }
1460
1461       }
1462
1463     }
1464     return boundedCalleeSet;
1465
1466   }
1467
1468   // Borrowed it from disjoint analysis
1469   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1470
1471     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1472
1473     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1474
1475     Iterator<MethodDescriptor> itr = toSort.iterator();
1476     while (itr.hasNext()) {
1477       MethodDescriptor d = itr.next();
1478
1479       if (!discovered.contains(d)) {
1480         dfsVisit(d, toSort, sorted, discovered);
1481       }
1482     }
1483
1484     return sorted;
1485   }
1486
1487   // While we're doing DFS on call graph, remember
1488   // dependencies for efficient queuing of methods
1489   // during interprocedural analysis:
1490   //
1491   // a dependent of a method decriptor d for this analysis is:
1492   // 1) a method or task that invokes d
1493   // 2) in the descriptorsToAnalyze set
1494   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1495       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1496
1497     discovered.add(md);
1498
1499     Iterator itr = callGraph.getCallerSet(md).iterator();
1500     while (itr.hasNext()) {
1501       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1502       // only consider callers in the original set to analyze
1503       if (!toSort.contains(dCaller)) {
1504         continue;
1505       }
1506       if (!discovered.contains(dCaller)) {
1507         addDependent(md, // callee
1508             dCaller // caller
1509         );
1510
1511         dfsVisit(dCaller, toSort, sorted, discovered);
1512       }
1513     }
1514
1515     // for leaf-nodes last now!
1516     sorted.addLast(md);
1517   }
1518
1519   // a dependent of a method decriptor d for this analysis is:
1520   // 1) a method or task that invokes d
1521   // 2) in the descriptorsToAnalyze set
1522   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1523     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1524     if (deps == null) {
1525       deps = new HashSet<MethodDescriptor>();
1526     }
1527     deps.add(caller);
1528     mapDescriptorToSetDependents.put(callee, deps);
1529   }
1530
1531   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1532     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1533     if (deps == null) {
1534       deps = new HashSet<MethodDescriptor>();
1535       mapDescriptorToSetDependents.put(callee, deps);
1536     }
1537     return deps;
1538   }
1539
1540   private NTuple<Descriptor> computePath(TempDescriptor td) {
1541     // generate proper path fot input td
1542     // if td is local variable, it just generate one element tuple path
1543     if (mapHeapPath.containsKey(td)) {
1544       return mapHeapPath.get(td);
1545     } else {
1546       NTuple<Descriptor> path = new NTuple<Descriptor>();
1547       path.add(td);
1548       return path;
1549     }
1550   }
1551
1552 }