Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

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