Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

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