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