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