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 flat method to the READ that is the set of heap path that is
  61   // expected to be written before method invocation
  62   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToReadSet;
  63
  64   // maps a flat method to the must-write set that is the set of heap path that
  65   // is overwritten on every possible path during method invocation
  66   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMustWriteSet;
  67
  68   // maps a flat method to the may-wirte set that is the set of heap path that
  69   // might be written to
  70   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToMayWriteSet;
  71
  72   // maps a call site to the read set contributed by all callees
  73   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundReadSet;
  74
  75   // maps a call site to the must write set contributed by all callees
  76   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMustWriteSet;
  77
  78   // maps a call site to the may read set contributed by all callees
  79   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToBoundMayWriteSet;
  80
  81   // points to method containing SSJAVA Loop
  82   private MethodDescriptor methodContainingSSJavaLoop;
  83
  84   // maps a flatnode to definitely written analysis mapping M
  85   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>> mapFlatNodetoEventLoopMap;
  86
  87   // maps a method descriptor to its current summary during the analysis
  88   // then analysis reaches fixed-point, this mapping will have the final summary
  89   // for each method descriptor
  90   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
  91
  92   // maps a method descriptor to the merged incoming caller's current
  93   // overwritten status
  94   private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
  95
  96   // maps a flat node to current partial results
  97   private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
  98
  99   // maps shared location to the set of descriptors which belong to the shared
 100   // location
 101
 102   // keep current descriptors to visit in fixed-point interprocedural analysis,
 103   private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
 104
 105   // when analyzing flatcall, need to re-schedule set of callee
 106   private Set<MethodDescriptor> calleesToEnqueue;
 107
 108   private Set<ReadSummary> possibleCalleeReadSummarySetToCaller;
 109
 110   public static final String arrayElementFieldName = "___element_";
 111   static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
 112
 113   private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
 114
 115   // maps a method descriptor to the merged incoming caller's current
 116   // reading status
 117   // it is for setting clearance flag when all read set is overwritten
 118   private Hashtable<MethodDescriptor, ReadSummary> mapMethodDescriptorToReadSummary;
 119
 120   private Hashtable<Location, Set<Descriptor>> mapSharedLocationToCoverSet;
 121
 122   private LinkedList<MethodDescriptor> sortedDescriptors;
 123
 124   private FlatNode ssjavaLoopEntrance;
 125   private LoopFinder ssjavaLoop;
 126   private Set<FlatNode> loopIncElements;
 127
 128   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
 129   private Set<NTuple<Descriptor>> calleeIntersectBoundMustWriteSet;
 130   private Set<NTuple<Descriptor>> calleeUnionBoundMayWriteSet;
 131
 132   private Hashtable<Descriptor, Location> mapDescToLocation;
 133
 134   private TempDescriptor LOCAL;
 135
 136   public static int MAXAGE = 1;
 137
 138   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
 139     this.state = state;
 140     this.ssjava = ssjava;
 141     this.callGraph = ssjava.getCallGraph();
 142     this.mapFlatNodeToMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 143     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
 144     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
 145     this.mapFlatMethodToReadSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 146     this.mapFlatMethodToMustWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 147     this.mapFlatMethodToMayWriteSet = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
 148     this.mapFlatNodetoEventLoopMap =
 149         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<WriteAge>>>();
 150     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
 151     this.calleeIntersectBoundMustWriteSet = new HashSet<NTuple<Descriptor>>();
 152     this.calleeUnionBoundMayWriteSet = new HashSet<NTuple<Descriptor>>();
 153
 154     this.mapMethodDescriptorToCompleteClearingSummary =
 155         new Hashtable<MethodDescriptor, ClearingSummary>();
 156     this.mapMethodDescriptorToInitialClearingSummary =
 157         new Hashtable<MethodDescriptor, ClearingSummary>();
 158     this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 159     this.calleesToEnqueue = new HashSet<MethodDescriptor>();
 160     this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
 161     this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
 162     this.LOCAL = new TempDescriptor("LOCAL");
 163     this.mapDescToLocation = new Hashtable<Descriptor, Location>();
 164     this.possibleCalleeReadSummarySetToCaller = new HashSet<ReadSummary>();
 165     this.mapMethodDescriptorToReadSummary = new Hashtable<MethodDescriptor, ReadSummary>();
 166     this.mapFlatNodeToBoundReadSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 167     this.mapFlatNodeToBoundMustWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 168     this.mapFlatNodeToBoundMayWriteSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
 169     this.mapSharedLocationToCoverSet = new Hashtable<Location, Set<Descriptor>>();
 170   }
 171
 172   public void definitelyWrittenCheck() {
 173     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 174       initialize();
 175       methodReadWriteSetAnalysis();
 176       methodReadWriteSetAnalysisToEventLoopBody();
 177       eventLoopAnalysis();
 178       computeSharedCoverSet();
 179
 180       System.out.println("#");
 181       System.out.println(mapSharedLocationToCoverSet);
 182       // XXXXXXX
 183       // methodReadWriteSetAnalysis();
 184       // methodReadWriteSetAnalysisToEventLoopBody();
 185       // eventLoopAnalysis();
 186       // XXXXXXX
 187       // sharedLocationAnalysis();
 188       // checkSharedLocationResult();
 189     }
 190   }
 191
 192   private void checkSharedLocationResult() {
 193
 194     // mapping of method containing ssjava loop has the final result of
 195     // shared location analysis
 196
 197     ClearingSummary result =
 198         mapMethodDescriptorToCompleteClearingSummary.get(methodContainingSSJavaLoop);
 199
 200     String str = generateNotClearedResult(result);
 201     if (str.length() > 0) {
 202       throw new Error(
 203           "Following concrete locations of the shared abstract location are not cleared at the same time:\n"
 204               + str);
 205     }
 206
 207   }
 208
 209   private String generateNotClearedResult(ClearingSummary result) {
 210     Set<NTuple<Descriptor>> keySet = result.keySet();
 211
 212     StringBuffer str = new StringBuffer();
 213     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 214       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 215       SharedStatus status = result.get(hpKey);
 216       Hashtable<Location, Pair<Set<Descriptor>, Boolean>> map = status.getMap();
 217       Set<Location> locKeySet = map.keySet();
 218       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
 219         Location locKey = (Location) iterator2.next();
 220         if (status.haveWriteEffect(locKey)) {
 221           Pair<Set<Descriptor>, Boolean> pair = map.get(locKey);
 222           if (!pair.getSecond().booleanValue()) {
 223             // not cleared!
 224             str.append("- Concrete locations of the shared location '" + locKey
 225                 + "' are not cleared out, which are reachable through the heap path '" + hpKey
 226                 + ".\n");
 227           }
 228         }
 229       }
 230     }
 231
 232     return str.toString();
 233
 234   }
 235
 236   private void writeReadMapFile() {
 237
 238     String fileName = "SharedLocationReadMap";
 239
 240     try {
 241       BufferedWriter bw = new BufferedWriter(new FileWriter(fileName + ".txt"));
 242
 243       Set<MethodDescriptor> keySet = mapMethodDescriptorToReadSummary.keySet();
 244       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 245         MethodDescriptor mdKey = (MethodDescriptor) iterator.next();
 246         ReadSummary summary = mapMethodDescriptorToReadSummary.get(mdKey);
 247         bw.write("Method " + mdKey + "::\n");
 248         bw.write(summary + "\n\n");
 249       }
 250       bw.close();
 251     } catch (IOException e) {
 252       e.printStackTrace();
 253     }
 254
 255   }
 256
 257   private void sharedLocationAnalysis() {
 258     // verify that all concrete locations of shared location are cleared out at
 259     // the same time once per the out-most loop
 260
 261     computeSharedCoverSet();
 262
 263     if (state.SSJAVADEBUG) {
 264       writeReadMapFile();
 265     }
 266
 267     // methodDescriptorsToVisitStack.clear();
 268     // methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 269
 270     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 271         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 272
 273     // current descriptors to visit in fixed-point interprocedural analysis,
 274     // prioritized by
 275     // dependency in the call graph
 276     methodDescriptorsToVisitStack.clear();
 277
 278     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 279     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 280
 281     while (!descriptorListToAnalyze.isEmpty()) {
 282       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 283       methodDescriptorsToVisitStack.add(md);
 284     }
 285
 286     // analyze scheduled methods until there are no more to visit
 287     while (!methodDescriptorsToVisitStack.isEmpty()) {
 288       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 289
 290       ClearingSummary completeSummary =
 291           sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 292
 293       ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
 294
 295       if (!completeSummary.equals(prevCompleteSummary)) {
 296
 297         mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 298
 299         // results for callee changed, so enqueue dependents caller for
 300         // further analysis
 301         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 302         while (depsItr.hasNext()) {
 303           MethodDescriptor methodNext = depsItr.next();
 304           if (!methodDescriptorsToVisitStack.contains(methodNext)) {
 305             methodDescriptorsToVisitStack.add(methodNext);
 306           }
 307         }
 308
 309         // if there is set of callee to be analyzed,
 310         // add this set into the top of stack
 311         Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
 312         while (calleeIter.hasNext()) {
 313           MethodDescriptor mdNext = calleeIter.next();
 314           if (!methodDescriptorsToVisitStack.contains(mdNext)) {
 315             methodDescriptorsToVisitStack.add(mdNext);
 316           }
 317         }
 318         calleesToEnqueue.clear();
 319
 320       }
 321
 322     }
 323
 324   }
 325
 326   private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
 327       boolean onlyVisitSSJavaLoop) {
 328
 329     if (state.SSJAVADEBUG) {
 330       System.out.println("SSJAVA: Definite clearance for shared locations Analyzing: " + md);
 331     }
 332
 333     FlatMethod fm = state.getMethodFlat(md);
 334
 335     // intraprocedural analysis
 336     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 337
 338     // start a new mapping of partial results for each flat node
 339     mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
 340
 341     if (onlyVisitSSJavaLoop) {
 342       flatNodesToVisit.add(ssjavaLoopEntrance);
 343     } else {
 344       flatNodesToVisit.add(fm);
 345     }
 346
 347     Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
 348
 349     while (!flatNodesToVisit.isEmpty()) {
 350       FlatNode fn = flatNodesToVisit.iterator().next();
 351       flatNodesToVisit.remove(fn);
 352
 353       ClearingSummary curr = new ClearingSummary();
 354
 355       Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
 356       for (int i = 0; i < fn.numPrev(); i++) {
 357         FlatNode prevFn = fn.getPrev(i);
 358         ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
 359         if (in != null) {
 360           prevSet.add(in);
 361         }
 362       }
 363       mergeSharedLocationAnaylsis(curr, prevSet);
 364
 365       sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
 366       ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 367
 368       if (!curr.equals(clearingPrev)) {
 369         mapFlatNodeToClearingSummary.put(fn, curr);
 370
 371         for (int i = 0; i < fn.numNext(); i++) {
 372           FlatNode nn = fn.getNext(i);
 373
 374           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 375             flatNodesToVisit.add(nn);
 376           }
 377
 378         }
 379       }
 380
 381     }
 382
 383     ClearingSummary completeSummary = new ClearingSummary();
 384     Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
 385
 386     if (onlyVisitSSJavaLoop) {
 387       // when analyzing ssjava loop,
 388       // complete summary is merging of all previous nodes of ssjava loop
 389       // entrance
 390       for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
 391         ClearingSummary frnSummary =
 392             mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
 393         if (frnSummary != null) {
 394           summarySet.add(frnSummary);
 395         }
 396       }
 397     } else {
 398       // merging all exit node summary into the complete summary
 399       if (!returnNodeSet.isEmpty()) {
 400         for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
 401           FlatNode frn = (FlatNode) iterator.next();
 402           ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
 403           summarySet.add(frnSummary);
 404         }
 405       }
 406     }
 407     mergeSharedLocationAnaylsis(completeSummary, summarySet);
 408
 409     return completeSummary;
 410   }
 411
 412   private void sharedLocation_nodeActions(MethodDescriptor md, FlatNode fn, ClearingSummary curr,
 413       Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 414
 415     TempDescriptor lhs;
 416     TempDescriptor rhs;
 417     FieldDescriptor fld;
 418     switch (fn.kind()) {
 419
 420     case FKind.FlatMethod: {
 421       FlatMethod fm = (FlatMethod) fn;
 422
 423       ClearingSummary summaryFromCaller =
 424           mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
 425
 426       Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 427       if (summaryFromCaller != null) {
 428         inSet.add(summaryFromCaller);
 429         mergeSharedLocationAnaylsis(curr, inSet);
 430       }
 431
 432     }
 433       break;
 434
 435     case FKind.FlatOpNode: {
 436       FlatOpNode fon = (FlatOpNode) fn;
 437       lhs = fon.getDest();
 438       rhs = fon.getLeft();
 439
 440       if (fon.getOp().getOp() == Operation.ASSIGN) {
 441         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 442           // in ssjavaloop, we need to take care about reading local variables!
 443           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 444           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 445           rhsHeapPath.add(LOCAL);
 446           lhsHeapPath.add(LOCAL);
 447           if (!lhs.getSymbol().startsWith("neverused")) {
 448             readLocation(md, curr, rhsHeapPath, getLocation(rhs), rhs);
 449             writeLocation(md, curr, lhsHeapPath, getLocation(lhs), lhs);
 450           }
 451         }
 452       }
 453
 454     }
 455       break;
 456
 457     case FKind.FlatFieldNode:
 458     case FKind.FlatElementNode: {
 459
 460       if (fn.kind() == FKind.FlatFieldNode) {
 461         FlatFieldNode ffn = (FlatFieldNode) fn;
 462         lhs = ffn.getDst();
 463         rhs = ffn.getSrc();
 464         fld = ffn.getField();
 465       } else {
 466         FlatElementNode fen = (FlatElementNode) fn;
 467         lhs = fen.getDst();
 468         rhs = fen.getSrc();
 469         TypeDescriptor td = rhs.getType().dereference();
 470         fld = getArrayField(td);
 471       }
 472
 473       // read field
 474       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 475
 476       if (srcHeapPath != null) {
 477         // if lhs srcHeapPath is null, it means that it is not reachable from
 478         // callee's parameters. so just ignore it
 479         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 480
 481         if (!fld.getType().isArray() && fld.getType().isImmutable()) {
 482           Location loc;
 483           if (fn.kind() == FKind.FlatElementNode) {
 484             // array element read case
 485             NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
 486             for (int i = 0; i < fldHeapPath.size() - 1; i++) {
 487               newHeapPath.add(fldHeapPath.get(i));
 488             }
 489
 490             Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
 491             if (desc instanceof FieldDescriptor) {
 492               fld = (FieldDescriptor) desc;
 493               fldHeapPath = newHeapPath;
 494               loc = getLocation(fld);
 495               readLocation(md, curr, fldHeapPath, loc, fld);
 496             }
 497           } else {
 498             loc = getLocation(fld);
 499             readLocation(md, curr, fldHeapPath, loc, fld);
 500           }
 501         } else {
 502
 503           if (fn.kind() != FKind.FlatElementNode) {
 504             // if it is multi dimensional array, do not need to add heap path
 505             // because all accesses from the same array is represented by
 506             // "_element_"
 507             fldHeapPath.add(fld);
 508           }
 509           mapHeapPath.put(lhs, fldHeapPath);
 510         }
 511
 512       }
 513
 514       // }
 515
 516     }
 517       break;
 518
 519     case FKind.FlatSetFieldNode:
 520     case FKind.FlatSetElementNode: {
 521
 522       if (fn.kind() == FKind.FlatSetFieldNode) {
 523         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 524         lhs = fsfn.getDst();
 525         fld = fsfn.getField();
 526         rhs = fsfn.getSrc();
 527       } else {
 528         FlatSetElementNode fsen = (FlatSetElementNode) fn;
 529         lhs = fsen.getDst();
 530         rhs = fsen.getSrc();
 531         TypeDescriptor td = lhs.getType().dereference();
 532         fld = getArrayField(td);
 533       }
 534
 535       // write(field)
 536       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 537       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 538       if (fld.getType().isImmutable()) {
 539         writeLocation(md, curr, fldHeapPath, getLocation(fld), fld);
 540
 541         Descriptor desc = fldHeapPath.get(fldHeapPath.size() - 1);
 542         if (desc instanceof FieldDescriptor) {
 543           NTuple<Descriptor> arrayPath = new NTuple<Descriptor>();
 544           for (int i = 0; i < fldHeapPath.size() - 1; i++) {
 545             arrayPath.add(fldHeapPath.get(i));
 546           }
 547           SharedStatus state = getState(curr, arrayPath);
 548           state.setWriteEffect(getLocation(desc));
 549         }
 550
 551       } else {
 552         // updates reference field case:
 553         fldHeapPath.add(fld);
 554         updateWriteEffectOnReferenceField(curr, fldHeapPath);
 555       }
 556
 557     }
 558       break;
 559
 560     case FKind.FlatCall: {
 561
 562       FlatCall fc = (FlatCall) fn;
 563
 564       if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
 565         // ssjava util case!
 566         // have write effects on the first argument
 567
 568         if (fc.getArg(0).getType().isArray()) {
 569           // updates reference field case:
 570           // 2. if there exists a tuple t in sharing summary that starts with
 571           // hp(x) then, set flag of tuple t to 'true'
 572           NTuple<Descriptor> argHeapPath = computePath(fc.getArg(0));
 573
 574           Location loc = getLocation(fc.getArg(0));
 575           NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>();
 576           for (int i = 0; i < argHeapPath.size() - 1; i++) {
 577             newHeapPath.add(argHeapPath.get(i));
 578           }
 579           fld = (FieldDescriptor) argHeapPath.get(argHeapPath.size() - 1);
 580           argHeapPath = newHeapPath;
 581
 582           writeLocation(md, curr, argHeapPath, loc, fld);
 583         }
 584
 585       } else {
 586         // find out the set of callees
 587         MethodDescriptor mdCallee = fc.getMethod();
 588         FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 589         Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 590         setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
 591
 592         possibleCalleeCompleteSummarySetToCaller.clear();
 593
 594         for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 595           MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
 596           FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
 597
 598           addDependent(mdPossibleCallee, // callee
 599               md); // caller
 600
 601           calleesToEnqueue.add(mdPossibleCallee);
 602
 603           // updates possible callee's initial summary using caller's current
 604           // writing status
 605           ClearingSummary prevCalleeInitSummary =
 606               mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
 607
 608           ClearingSummary calleeInitSummary =
 609               bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
 610
 611           Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
 612           if (prevCalleeInitSummary != null) {
 613             inSet.add(prevCalleeInitSummary);
 614             mergeSharedLocationAnaylsis(calleeInitSummary, inSet);
 615           }
 616
 617           // if changes, update the init summary
 618           // and reschedule the callee for analysis
 619           if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
 620
 621             if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
 622               methodDescriptorsToVisitStack.add(mdPossibleCallee);
 623             }
 624
 625             mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
 626           }
 627
 628         }
 629
 630         // contribute callee's writing effects to the caller
 631         mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
 632
 633       }
 634
 635     }
 636       break;
 637
 638     case FKind.FlatReturnNode: {
 639       returnNodeSet.add(fn);
 640     }
 641       break;
 642
 643     }
 644
 645   }
 646
 647   private void updateWriteEffectOnReferenceField(ClearingSummary curr, NTuple<Descriptor> heapPath) {
 648
 649     // 2. if there exists a tuple t in sharing summary that starts with
 650     // hp(x) then, set flag of tuple t to 'true'
 651     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 652     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 653       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 654       if (hpKey.startsWith(heapPath)) {
 655         curr.get(hpKey).updateFlag(true);
 656       }
 657     }
 658
 659   }
 660
 661   private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
 662       FlatMethod calleeFlatMethod, ClearingSummary curr) {
 663
 664     ClearingSummary boundSet = new ClearingSummary();
 665
 666     // create mapping from arg idx to its heap paths
 667     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 668         new Hashtable<Integer, NTuple<Descriptor>>();
 669
 670     if (fc.getThis() != null) {
 671       // arg idx is starting from 'this' arg
 672       NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 673       if (thisHeapPath == null) {
 674         // method is called without creating new flat node representing 'this'
 675         thisHeapPath = new NTuple<Descriptor>();
 676         thisHeapPath.add(fc.getThis());
 677       }
 678
 679       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 680     }
 681
 682     for (int i = 0; i < fc.numArgs(); i++) {
 683       TempDescriptor arg = fc.getArg(i);
 684       NTuple<Descriptor> argHeapPath = computePath(arg);
 685       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 686     }
 687
 688     Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 689         new Hashtable<Integer, TempDescriptor>();
 690     int offset = 0;
 691     if (calleeFlatMethod.getMethod().isStatic()) {
 692       // static method does not have implicit 'this' arg
 693       offset = 1;
 694     }
 695     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 696       TempDescriptor param = calleeFlatMethod.getParameter(i);
 697       mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
 698     }
 699
 700     // binding caller's writing effects to callee's params
 701     for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 702       NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 703
 704       if (argHeapPath != null) {
 705         // if method is static, the first argument is nulll because static
 706         // method does not have implicit "THIS" arg
 707         TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 708
 709         // iterate over caller's writing effect set
 710         Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
 711         for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 712           NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 713           // current element is reachable caller's arg
 714           // so need to bind it to the caller's side and add it to the
 715           // callee's
 716           // init summary
 717           if (hpKey.startsWith(argHeapPath)) {
 718             NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
 719             boundSet.put(boundHeapPath, curr.get(hpKey).clone());
 720           }
 721
 722         }
 723       }
 724
 725     }
 726
 727     // contribute callee's complete summary into the caller's current summary
 728     ClearingSummary calleeCompleteSummary =
 729         mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
 730     if (calleeCompleteSummary != null) {
 731       ClearingSummary boundCalleeEfffects = new ClearingSummary();
 732       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 733         NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
 734
 735         if (argHeapPath != null) {
 736           // if method is static, the first argument is nulll because static
 737           // method does not have implicit "THIS" arg
 738           TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
 739
 740           // iterate over callee's writing effect set
 741           Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
 742           for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
 743             NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
 744             // current element is reachable caller's arg
 745             // so need to bind it to the caller's side and add it to the
 746             // callee's
 747             // init summary
 748             if (hpKey.startsWith(calleeParamHeapPath)) {
 749
 750               NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
 751
 752               boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
 753                   .clone());
 754
 755             }
 756           }
 757
 758         }
 759
 760       }
 761       possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
 762     }
 763
 764     return boundSet;
 765   }
 766
 767   private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
 768
 769     // replace the head of heap path with caller's arg path
 770     // for example, heap path 'param.a.b' in callee's side will be replaced with
 771     // (corresponding arg heap path).a.b for caller's side
 772
 773     NTuple<Descriptor> bound = new NTuple<Descriptor>();
 774
 775     for (int i = 0; i < argHeapPath.size(); i++) {
 776       bound.add(argHeapPath.get(i));
 777     }
 778
 779     for (int i = 1; i < hpKey.size(); i++) {
 780       bound.add(hpKey.get(i));
 781     }
 782
 783     return bound;
 784   }
 785
 786   private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
 787       NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
 788     // replace the head of caller's heap path with callee's param heap path
 789
 790     NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
 791     boundHeapPath.add(calleeParamHeapPath);
 792
 793     for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
 794       boundHeapPath.add(effectHeapPath.get(i));
 795     }
 796
 797     return boundHeapPath;
 798   }
 799
 800   private void computeSharedCoverSet() {
 801     LinkedList<MethodDescriptor> descriptorListToAnalyze =
 802         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 803
 804     // current descriptors to visit in fixed-point interprocedural analysis,
 805     // prioritized by
 806     // dependency in the call graph
 807     methodDescriptorsToVisitStack.clear();
 808
 809     descriptorListToAnalyze.removeFirst();
 810
 811     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 812     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 813
 814     while (!descriptorListToAnalyze.isEmpty()) {
 815       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
 816       methodDescriptorsToVisitStack.add(md);
 817     }
 818
 819     // analyze scheduled methods until there are no more to visit
 820     while (!methodDescriptorsToVisitStack.isEmpty()) {
 821       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 822
 823       FlatMethod fm = state.getMethodFlat(md);
 824
 825       computeSharedCoverSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
 826
 827     }
 828
 829   }
 830
 831   private void computeSharedCoverSet_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
 832
 833     MethodDescriptor md = fm.getMethod();
 834     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 835
 836     Set<FlatNode> visited = new HashSet<FlatNode>();
 837
 838     if (onlyVisitSSJavaLoop) {
 839       flatNodesToVisit.add(ssjavaLoopEntrance);
 840     } else {
 841       flatNodesToVisit.add(fm);
 842     }
 843
 844     while (!flatNodesToVisit.isEmpty()) {
 845       FlatNode fn = flatNodesToVisit.iterator().next();
 846       flatNodesToVisit.remove(fn);
 847       visited.add(fn);
 848
 849       computeSharedCoverSet_nodeActions(md, fn);
 850
 851       for (int i = 0; i < fn.numNext(); i++) {
 852         FlatNode nn = fn.getNext(i);
 853
 854         if (!visited.contains(nn)) {
 855           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 856             flatNodesToVisit.add(nn);
 857           }
 858         }
 859
 860       }
 861
 862     }
 863
 864   }
 865
 866   private void computeSharedCoverSet_nodeActions(MethodDescriptor md, FlatNode fn) {
 867     TempDescriptor lhs;
 868     TempDescriptor rhs;
 869     FieldDescriptor fld;
 870
 871     switch (fn.kind()) {
 872
 873     case FKind.FlatLiteralNode: {
 874       FlatLiteralNode fln = (FlatLiteralNode) fn;
 875       lhs = fln.getDst();
 876
 877       if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused")
 878           && !lhs.getSymbol().startsWith("srctmp")) {
 879         // only need to care about composite location case here
 880         if (lhs.getType().getExtension() instanceof SSJavaType) {
 881           CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc();
 882           Location lastLocElement = compLoc.get(compLoc.getSize() - 1);
 883           // check if the last one is shared loc
 884           if (ssjava.isSharedLocation(lastLocElement)) {
 885             addSharedLocDescriptor(lastLocElement, lhs);
 886           }
 887         }
 888       }
 889
 890     }
 891       break;
 892
 893     case FKind.FlatOpNode: {
 894       FlatOpNode fon = (FlatOpNode) fn;
 895       // for a normal assign node, need to propagate lhs's heap path to
 896       // rhs
 897       if (fon.getOp().getOp() == Operation.ASSIGN) {
 898         rhs = fon.getLeft();
 899         lhs = fon.getDest();
 900
 901         if (lhs.getType().isPrimitive() && !lhs.getSymbol().startsWith("neverused")
 902             && !lhs.getSymbol().startsWith("srctmp")) {
 903           // only need to care about composite location case here
 904           if (lhs.getType().getExtension() instanceof SSJavaType) {
 905             CompositeLocation compLoc = ((SSJavaType) lhs.getType().getExtension()).getCompLoc();
 906             Location lastLocElement = compLoc.get(compLoc.getSize() - 1);
 907             // check if the last one is shared loc
 908             if (ssjava.isSharedLocation(lastLocElement)) {
 909               addSharedLocDescriptor(lastLocElement, lhs);
 910             }
 911           }
 912         }
 913
 914       }
 915     }
 916       break;
 917
 918     case FKind.FlatSetFieldNode:
 919     case FKind.FlatSetElementNode: {
 920
 921       // x.f=y;
 922
 923       if (fn.kind() == FKind.FlatSetFieldNode) {
 924         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 925         lhs = fsfn.getDst();
 926         fld = fsfn.getField();
 927         rhs = fsfn.getSrc();
 928       } else {
 929         FlatSetElementNode fsen = (FlatSetElementNode) fn;
 930         lhs = fsen.getDst();
 931         rhs = fsen.getSrc();
 932         TypeDescriptor td = lhs.getType().dereference();
 933         fld = getArrayField(td);
 934       }
 935
 936       Location fieldLocation = (Location) fld.getType().getExtension();
 937       if (ssjava.isSharedLocation(fieldLocation)) {
 938         addSharedLocDescriptor(fieldLocation, fld);
 939       }
 940
 941     }
 942       break;
 943
 944     }
 945   }
 946
 947   private void addSharedLocDescriptor(Location sharedLoc, Descriptor desc) {
 948
 949     Set<Descriptor> descSet = mapSharedLocationToCoverSet.get(sharedLoc);
 950     if (descSet == null) {
 951       descSet = new HashSet<Descriptor>();
 952       mapSharedLocationToCoverSet.put(sharedLoc, descSet);
 953     }
 954
 955     System.out.println("add " + desc + " to shared loc" + sharedLoc);
 956     descSet.add(desc);
 957
 958   }
 959
 960   private void mergeReadLocationAnaylsis(ReadSummary curr, Set<ReadSummary> inSet) {
 961
 962     if (inSet.size() == 0) {
 963       return;
 964     }
 965
 966     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
 967       ReadSummary inSummary = (ReadSummary) inIterator.next();
 968       curr.merge(inSummary);
 969     }
 970
 971   }
 972
 973   private boolean hasReadingEffectOnSharedLocation(MethodDescriptor md, NTuple<Descriptor> hp,
 974       Location loc, Descriptor d) {
 975
 976     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
 977
 978     if (summary != null) {
 979       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
 980       if (map != null) {
 981         Set<Descriptor> descSec = map.get(loc);
 982         if (descSec != null) {
 983           return descSec.contains(d);
 984         }
 985       }
 986     }
 987     return false;
 988
 989   }
 990
 991   private Location getLocation(Descriptor d) {
 992
 993     if (d instanceof FieldDescriptor) {
 994       TypeExtension te = ((FieldDescriptor) d).getType().getExtension();
 995       if (te != null) {
 996         return (Location) te;
 997       }
 998     } else {
 999       assert d instanceof TempDescriptor;
1000       TempDescriptor td = (TempDescriptor) d;
1001
1002       TypeExtension te = td.getType().getExtension();
1003       if (te != null) {
1004         if (te instanceof SSJavaType) {
1005           SSJavaType ssType = (SSJavaType) te;
1006           CompositeLocation comp = ssType.getCompLoc();
1007           return comp.get(comp.getSize() - 1);
1008         } else {
1009           return (Location) te;
1010         }
1011       }
1012     }
1013
1014     return mapDescToLocation.get(d);
1015   }
1016
1017   private void writeLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1018       Location loc, Descriptor d) {
1019
1020     SharedStatus state = getState(curr, hp);
1021     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1022       // 1. add field x to the clearing set
1023
1024       state.addVar(loc, d);
1025
1026       // 3. if the set v contains all of variables belonging to the shared
1027       // location, set flag to true
1028       if (isOverWrittenAllDescsOfSharedLoc(md, hp, loc, state.getVarSet(loc))) {
1029         state.updateFlag(loc, true);
1030       }
1031     }
1032     state.setWriteEffect(loc);
1033
1034   }
1035
1036   private boolean isOverWrittenAllDescsOfSharedLoc(MethodDescriptor md, NTuple<Descriptor> hp,
1037       Location loc, Set<Descriptor> writtenSet) {
1038
1039     ReadSummary summary = mapMethodDescriptorToReadSummary.get(md);
1040
1041     if (summary != null) {
1042       Hashtable<Location, Set<Descriptor>> map = summary.get(hp);
1043       if (map != null) {
1044         Set<Descriptor> descSet = map.get(loc);
1045         if (descSet != null) {
1046           return writtenSet.containsAll(descSet);
1047         }
1048       }
1049     }
1050     return false;
1051   }
1052
1053   private void readLocation(MethodDescriptor md, ClearingSummary curr, NTuple<Descriptor> hp,
1054       Location loc, Descriptor d) {
1055     // remove reading var x from written set
1056     if (loc != null && hasReadingEffectOnSharedLocation(md, hp, loc, d)) {
1057       SharedStatus state = getState(curr, hp);
1058       state.removeVar(loc, d);
1059     }
1060   }
1061
1062   private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
1063     SharedStatus state = curr.get(hp);
1064     if (state == null) {
1065       state = new SharedStatus();
1066       curr.put(hp, state);
1067     }
1068     return state;
1069   }
1070
1071   private void eventLoopAnalysis() {
1072     // perform second stage analysis: intraprocedural analysis ensure that
1073     // all
1074     // variables are definitely written in-between the same read
1075
1076     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1077     flatNodesToVisit.add(ssjavaLoopEntrance);
1078
1079     while (!flatNodesToVisit.isEmpty()) {
1080       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
1081       flatNodesToVisit.remove(fn);
1082
1083       Hashtable<NTuple<Descriptor>, Set<WriteAge>> prev = mapFlatNodetoEventLoopMap.get(fn);
1084
1085       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr =
1086           new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1087       for (int i = 0; i < fn.numPrev(); i++) {
1088         FlatNode nn = fn.getPrev(i);
1089         Hashtable<NTuple<Descriptor>, Set<WriteAge>> in = mapFlatNodetoEventLoopMap.get(nn);
1090         if (in != null) {
1091           union(curr, in);
1092         }
1093       }
1094
1095       eventLoopAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
1096
1097       // if a new result, schedule forward nodes for analysis
1098       if (!curr.equals(prev)) {
1099         mapFlatNodetoEventLoopMap.put(fn, curr);
1100
1101         for (int i = 0; i < fn.numNext(); i++) {
1102           FlatNode nn = fn.getNext(i);
1103           if (loopIncElements.contains(nn)) {
1104             flatNodesToVisit.add(nn);
1105           }
1106
1107         }
1108       }
1109     }
1110   }
1111
1112   private void union(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1113       Hashtable<NTuple<Descriptor>, Set<WriteAge>> in) {
1114
1115     Set<NTuple<Descriptor>> inKeySet = in.keySet();
1116     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
1117       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
1118       Set<WriteAge> inSet = in.get(inKey);
1119
1120       Set<WriteAge> currSet = curr.get(inKey);
1121
1122       if (currSet == null) {
1123         currSet = new HashSet<WriteAge>();
1124         curr.put(inKey, currSet);
1125       }
1126       currSet.addAll(inSet);
1127     }
1128
1129   }
1130
1131   private void eventLoopAnalysis_nodeAction(FlatNode fn,
1132       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr, FlatNode loopEntrance) {
1133
1134     Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet =
1135         new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1136     Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet =
1137         new Hashtable<NTuple<Descriptor>, Set<WriteAge>>();
1138
1139     if (fn.equals(loopEntrance)) {
1140       // it reaches loop entrance: changes all flag to true
1141       Set<NTuple<Descriptor>> keySet = curr.keySet();
1142       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1143         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1144         Set<WriteAge> writeAgeSet = curr.get(key);
1145
1146         Set<WriteAge> incSet = new HashSet<WriteAge>();
1147         incSet.addAll(writeAgeSet);
1148         writeAgeSet.clear();
1149
1150         for (Iterator iterator2 = incSet.iterator(); iterator2.hasNext();) {
1151           WriteAge writeAge = (WriteAge) iterator2.next();
1152           WriteAge newWriteAge = writeAge.copy();
1153           newWriteAge.inc();
1154           writeAgeSet.add(newWriteAge);
1155         }
1156
1157       }
1158       // System.out.println("EVENT LOOP ENTRY=" + curr);
1159
1160     } else {
1161       TempDescriptor lhs;
1162       TempDescriptor rhs;
1163       FieldDescriptor fld;
1164
1165       switch (fn.kind()) {
1166
1167       case FKind.FlatOpNode: {
1168         FlatOpNode fon = (FlatOpNode) fn;
1169         lhs = fon.getDest();
1170         rhs = fon.getLeft();
1171
1172         if (!lhs.getSymbol().startsWith("neverused")) {
1173           NTuple<Descriptor> rhsHeapPath = computePath(rhs);
1174           if (!rhs.getType().isImmutable()) {
1175             mapHeapPath.put(lhs, rhsHeapPath);
1176           } else {
1177             // write(lhs)
1178             // NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1179             NTuple<Descriptor> path = new NTuple<Descriptor>();
1180             path.add(lhs);
1181
1182             // System.out.println("WRITE VARIABLE=" + path + " from=" + lhs);
1183
1184             computeKILLSetForWrite(curr, path, KILLSet);
1185             computeGENSetForWrite(path, GENSet);
1186
1187             // System.out.println("#VARIABLE WRITE:" + fn);
1188             // System.out.println("#KILLSET=" + KILLSet);
1189             // System.out.println("#GENSet=" + GENSet);
1190
1191           }
1192         }
1193
1194       }
1195         break;
1196
1197       case FKind.FlatFieldNode:
1198       case FKind.FlatElementNode: {
1199
1200         if (fn.kind() == FKind.FlatFieldNode) {
1201           FlatFieldNode ffn = (FlatFieldNode) fn;
1202           lhs = ffn.getDst();
1203           rhs = ffn.getSrc();
1204           fld = ffn.getField();
1205         } else {
1206           FlatElementNode fen = (FlatElementNode) fn;
1207           lhs = fen.getDst();
1208           rhs = fen.getSrc();
1209           TypeDescriptor td = rhs.getType().dereference();
1210           fld = getArrayField(td);
1211         }
1212
1213         // read field
1214         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1215         NTuple<Descriptor> fldHeapPath;
1216         if (srcHeapPath != null) {
1217           fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1218         } else {
1219           // if srcHeapPath is null, it is static reference
1220           fldHeapPath = new NTuple<Descriptor>();
1221           fldHeapPath.add(rhs);
1222         }
1223         fldHeapPath.add(fld);
1224
1225         Set<WriteAge> writeAgeSet = curr.get(fldHeapPath);
1226         checkWriteAgeSet(writeAgeSet, fldHeapPath, fn);
1227
1228       }
1229         break;
1230
1231       case FKind.FlatSetFieldNode:
1232       case FKind.FlatSetElementNode: {
1233
1234         if (fn.kind() == FKind.FlatSetFieldNode) {
1235           FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1236           lhs = fsfn.getDst();
1237           fld = fsfn.getField();
1238         } else {
1239           FlatSetElementNode fsen = (FlatSetElementNode) fn;
1240           lhs = fsen.getDst();
1241           rhs = fsen.getSrc();
1242           TypeDescriptor td = lhs.getType().dereference();
1243           fld = getArrayField(td);
1244         }
1245
1246         // write(field)
1247         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
1248         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1249         fldHeapPath.add(fld);
1250
1251         computeKILLSetForWrite(curr, fldHeapPath, KILLSet);
1252         computeGENSetForWrite(fldHeapPath, GENSet);
1253
1254         // System.out.println("FIELD WRITE:" + fn);
1255         // System.out.println("KILLSET=" + KILLSet);
1256         // System.out.println("GENSet=" + GENSet);
1257
1258       }
1259         break;
1260
1261       case FKind.FlatCall: {
1262         FlatCall fc = (FlatCall) fn;
1263
1264         generateKILLSetForFlatCall(fc, curr, KILLSet);
1265         generateGENSetForFlatCall(fc, GENSet);
1266
1267         // System.out.println("FLATCALL:" + fn);
1268         // System.out.println("KILLSET=" + KILLSet);
1269         // System.out.println("GENSet=" + GENSet);
1270
1271       }
1272         break;
1273
1274       }
1275
1276       computeNewMapping(curr, KILLSet, GENSet);
1277       // System.out.println("#######" + curr);
1278
1279     }
1280
1281   }
1282
1283   private void checkWriteAgeSet(Set<WriteAge> writeAgeSet, NTuple<Descriptor> path, FlatNode fn) {
1284     if (writeAgeSet != null) {
1285       for (Iterator iterator = writeAgeSet.iterator(); iterator.hasNext();) {
1286         WriteAge writeAge = (WriteAge) iterator.next();
1287         if (writeAge.getAge() >= MAXAGE) {
1288           throw new Error(
1289               "Memory location, which is reachable through references "
1290                   + path
1291                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1292                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1293                   + fn.getNumLine());
1294         }
1295       }
1296     }
1297   }
1298
1299   private void generateGENSetForFlatCall(FlatCall fc,
1300       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1301
1302     Set<NTuple<Descriptor>> boundMayWriteSet = mapFlatNodeToBoundMayWriteSet.get(fc);
1303
1304     for (Iterator iterator = boundMayWriteSet.iterator(); iterator.hasNext();) {
1305       NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1306       // TODO: shared location
1307       Set<WriteAge> set = new HashSet<WriteAge>();
1308       set.add(new WriteAge(0));
1309       GENSet.put(key, set);
1310     }
1311
1312   }
1313
1314   private void generateKILLSetForFlatCall(FlatCall fc,
1315       Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1316       Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1317
1318     Set<NTuple<Descriptor>> boundMustWriteSet = mapFlatNodeToBoundMustWriteSet.get(fc);
1319
1320     for (Iterator iterator = boundMustWriteSet.iterator(); iterator.hasNext();) {
1321       NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
1322       // TODO: shared location
1323       if (curr.get(key) != null) {
1324         KILLSet.put(key, curr.get(key));
1325       }
1326     }
1327
1328   }
1329
1330   private void computeNewMapping(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1331       Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet,
1332       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1333
1334     for (Enumeration<NTuple<Descriptor>> e = KILLSet.keys(); e.hasMoreElements();) {
1335       NTuple<Descriptor> key = e.nextElement();
1336
1337       Set<WriteAge> writeAgeSet = curr.get(key);
1338       if (writeAgeSet == null) {
1339         writeAgeSet = new HashSet<WriteAge>();
1340         curr.put(key, writeAgeSet);
1341       }
1342       writeAgeSet.removeAll(KILLSet.get(key));
1343     }
1344
1345     for (Enumeration<NTuple<Descriptor>> e = GENSet.keys(); e.hasMoreElements();) {
1346       NTuple<Descriptor> key = e.nextElement();
1347       curr.put(key, GENSet.get(key));
1348     }
1349
1350   }
1351
1352   private void computeGENSetForWrite(NTuple<Descriptor> fldHeapPath,
1353       Hashtable<NTuple<Descriptor>, Set<WriteAge>> GENSet) {
1354
1355     // generate write age 0 for the field being written to
1356     Set<WriteAge> writeAgeSet = new HashSet<WriteAge>();
1357     writeAgeSet.add(new WriteAge(0));
1358     GENSet.put(fldHeapPath, writeAgeSet);
1359
1360   }
1361
1362   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
1363       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
1364     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
1365     if (gen == null) {
1366       gen = new Hashtable<FlatNode, Boolean>();
1367       curr.put(hp, gen);
1368     }
1369     Boolean currentStatus = gen.get(fn);
1370     if (currentStatus == null) {
1371       gen.put(fn, Boolean.FALSE);
1372     } else {
1373       checkFlag(currentStatus.booleanValue(), fn, hp);
1374     }
1375
1376   }
1377
1378   private void computeKILLSetForWrite(Hashtable<NTuple<Descriptor>, Set<WriteAge>> curr,
1379       NTuple<Descriptor> hp, Hashtable<NTuple<Descriptor>, Set<WriteAge>> KILLSet) {
1380
1381     // removes all of heap path that starts with prefix 'hp'
1382     // since any reference overwrite along heap path gives overwriting side
1383     // effects on the value
1384
1385     Set<NTuple<Descriptor>> keySet = curr.keySet();
1386     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
1387       NTuple<Descriptor> key = iter.next();
1388       if (key.startsWith(hp)) {
1389         KILLSet.put(key, curr.get(key));
1390       }
1391     }
1392
1393   }
1394
1395   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
1396     // compute all possible callee set
1397     // transform all READ/WRITE set from the any possible
1398     // callees to the caller
1399     calleeUnionBoundReadSet.clear();
1400     calleeIntersectBoundMustWriteSet.clear();
1401     calleeUnionBoundMayWriteSet.clear();
1402
1403     if (ssjava.isSSJavaUtil(fc.getMethod().getClassDesc())) {
1404       // ssjava util case!
1405       // have write effects on the first argument
1406       TempDescriptor arg = fc.getArg(0);
1407       NTuple<Descriptor> argHeapPath = computePath(arg);
1408       calleeIntersectBoundMustWriteSet.add(argHeapPath);
1409       calleeUnionBoundMayWriteSet.add(argHeapPath);
1410     } else {
1411       MethodDescriptor mdCallee = fc.getMethod();
1412       Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
1413       setPossibleCallees.addAll(callGraph.getMethods(mdCallee));
1414
1415       // create mapping from arg idx to its heap paths
1416       Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
1417           new Hashtable<Integer, NTuple<Descriptor>>();
1418
1419       // arg idx is starting from 'this' arg
1420       if (fc.getThis() != null) {
1421         NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
1422         if (thisHeapPath == null) {
1423           // method is called without creating new flat node representing 'this'
1424           thisHeapPath = new NTuple<Descriptor>();
1425           thisHeapPath.add(fc.getThis());
1426         }
1427
1428         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
1429       }
1430
1431       for (int i = 0; i < fc.numArgs(); i++) {
1432         TempDescriptor arg = fc.getArg(i);
1433         NTuple<Descriptor> argHeapPath = computePath(arg);
1434         mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
1435       }
1436
1437       for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
1438         MethodDescriptor callee = (MethodDescriptor) iterator.next();
1439         FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
1440
1441         // binding caller's args and callee's params
1442
1443         Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToReadSet.get(calleeFlatMethod);
1444         if (calleeReadSet == null) {
1445           calleeReadSet = new HashSet<NTuple<Descriptor>>();
1446           mapFlatMethodToReadSet.put(calleeFlatMethod, calleeReadSet);
1447         }
1448
1449         Set<NTuple<Descriptor>> calleeMustWriteSet =
1450             mapFlatMethodToMustWriteSet.get(calleeFlatMethod);
1451
1452         if (calleeMustWriteSet == null) {
1453           calleeMustWriteSet = new HashSet<NTuple<Descriptor>>();
1454           mapFlatMethodToMustWriteSet.put(calleeFlatMethod, calleeMustWriteSet);
1455         }
1456
1457         Set<NTuple<Descriptor>> calleeMayWriteSet =
1458             mapFlatMethodToMayWriteSet.get(calleeFlatMethod);
1459
1460         if (calleeMayWriteSet == null) {
1461           calleeMayWriteSet = new HashSet<NTuple<Descriptor>>();
1462           mapFlatMethodToMayWriteSet.put(calleeFlatMethod, calleeMayWriteSet);
1463         }
1464
1465         Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
1466             new Hashtable<Integer, TempDescriptor>();
1467         int offset = 0;
1468         if (calleeFlatMethod.getMethod().isStatic()) {
1469           // static method does not have implicit 'this' arg
1470           offset = 1;
1471         }
1472         for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
1473           TempDescriptor param = calleeFlatMethod.getParameter(i);
1474           mapParamIdx2ParamTempDesc.put(Integer.valueOf(i + offset), param);
1475         }
1476
1477         Set<NTuple<Descriptor>> calleeBoundReadSet =
1478             bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1479         // union of the current read set and the current callee's
1480         // read set
1481         calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
1482
1483         Set<NTuple<Descriptor>> calleeBoundMustWriteSet =
1484             bindSet(calleeMustWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1485         // intersection of the current overwrite set and the current
1486         // callee's
1487         // overwrite set
1488         merge(calleeIntersectBoundMustWriteSet, calleeBoundMustWriteSet);
1489
1490         Set<NTuple<Descriptor>> boundWriteSetFromCallee =
1491             bindSet(calleeMayWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
1492         calleeUnionBoundMayWriteSet.addAll(boundWriteSetFromCallee);
1493       }
1494
1495     }
1496
1497   }
1498
1499   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
1500     if (booleanValue) {
1501       // the definitely written analysis only takes care about locations that
1502       // are written to inside of the SSJava loop
1503       for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) {
1504         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1505         if (hp.startsWith(write)) {
1506           // it has write effect!
1507           // throw new Error(
1508           System.out
1509               .println("###"
1510                   + "There is a variable, which is reachable through references "
1511                   + hp
1512                   + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
1513                   + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
1514                   + fn.getNumLine());
1515           debugcount++;
1516         }
1517       }
1518     }
1519   }
1520
1521   private void initialize() {
1522     // First, identify ssjava loop entrace
1523
1524     // no need to analyze method having ssjava loop
1525     methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
1526
1527     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
1528     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1529     flatNodesToVisit.add(fm);
1530
1531     LoopFinder loopFinder = new LoopFinder(fm);
1532
1533     while (!flatNodesToVisit.isEmpty()) {
1534       FlatNode fn = flatNodesToVisit.iterator().next();
1535       flatNodesToVisit.remove(fn);
1536
1537       String label = (String) state.fn2labelMap.get(fn);
1538       if (label != null) {
1539
1540         if (label.equals(ssjava.SSJAVA)) {
1541           ssjavaLoopEntrance = fn;
1542           break;
1543         }
1544       }
1545
1546       for (int i = 0; i < fn.numNext(); i++) {
1547         FlatNode nn = fn.getNext(i);
1548         flatNodesToVisit.add(nn);
1549       }
1550     }
1551
1552     assert ssjavaLoopEntrance != null;
1553
1554     // assume that ssjava loop is top-level loop in method, not nested loop
1555     Set nestedLoop = loopFinder.nestedLoops();
1556     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
1557       LoopFinder lf = (LoopFinder) loopIter.next();
1558       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
1559         ssjavaLoop = lf;
1560       }
1561     }
1562
1563     assert ssjavaLoop != null;
1564
1565     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
1566
1567     // perform topological sort over the set of methods accessed by the main
1568     // event loop
1569     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
1570     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
1571     sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
1572   }
1573
1574   private void methodReadWriteSetAnalysis() {
1575     // perform method READ/OVERWRITE analysis
1576     LinkedList<MethodDescriptor> descriptorListToAnalyze =
1577         (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
1578
1579     // current descriptors to visit in fixed-point interprocedural analysis,
1580     // prioritized by
1581     // dependency in the call graph
1582     methodDescriptorsToVisitStack.clear();
1583
1584     descriptorListToAnalyze.removeFirst();
1585
1586     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
1587     methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
1588
1589     while (!descriptorListToAnalyze.isEmpty()) {
1590       MethodDescriptor md = descriptorListToAnalyze.removeFirst();
1591       methodDescriptorsToVisitStack.add(md);
1592     }
1593
1594     // analyze scheduled methods until there are no more to visit
1595     while (!methodDescriptorsToVisitStack.isEmpty()) {
1596       // start to analyze leaf node
1597       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
1598       FlatMethod fm = state.getMethodFlat(md);
1599
1600       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1601       Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
1602       Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
1603
1604       methodReadWriteSet_analyzeMethod(fm, readSet, mustWriteSet, mayWriteSet);
1605
1606       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToReadSet.get(fm);
1607       Set<NTuple<Descriptor>> prevMustWrite = mapFlatMethodToMustWriteSet.get(fm);
1608       Set<NTuple<Descriptor>> prevMayWrite = mapFlatMethodToMayWriteSet.get(fm);
1609
1610       if (!(readSet.equals(prevRead) && mustWriteSet.equals(prevMustWrite) && mayWriteSet
1611           .equals(prevMayWrite))) {
1612         mapFlatMethodToReadSet.put(fm, readSet);
1613         mapFlatMethodToMustWriteSet.put(fm, mustWriteSet);
1614         mapFlatMethodToMayWriteSet.put(fm, mayWriteSet);
1615
1616         // results for callee changed, so enqueue dependents caller for
1617         // further
1618         // analysis
1619         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
1620         while (depsItr.hasNext()) {
1621           MethodDescriptor methodNext = depsItr.next();
1622           if (!methodDescriptorsToVisitStack.contains(methodNext)
1623               && methodDescriptorToVistSet.contains(methodNext)) {
1624             methodDescriptorsToVisitStack.add(methodNext);
1625           }
1626
1627         }
1628
1629       }
1630
1631     }
1632
1633   }
1634
1635   private void methodReadWriteSet_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
1636       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet) {
1637     if (state.SSJAVADEBUG) {
1638       System.out.println("SSJAVA: Definitely written Analyzing: " + fm);
1639     }
1640
1641     methodReadWriteSet_analyzeBody(fm, readSet, mustWriteSet, mayWriteSet, null);
1642
1643   }
1644
1645   private void methodReadWriteSetAnalysisToEventLoopBody() {
1646
1647     // perform method read/write analysis for Event Loop Body
1648
1649     FlatMethod flatMethodContainingSSJavaLoop = state.getMethodFlat(methodContainingSSJavaLoop);
1650
1651     if (state.SSJAVADEBUG) {
1652       System.out.println("SSJAVA: Definitely written Event Loop Analyzing: "
1653           + flatMethodContainingSSJavaLoop);
1654     }
1655
1656     Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
1657     Set<NTuple<Descriptor>> mustWriteSet = new HashSet<NTuple<Descriptor>>();
1658     Set<NTuple<Descriptor>> mayWriteSet = new HashSet<NTuple<Descriptor>>();
1659
1660     mapFlatMethodToReadSet.put(flatMethodContainingSSJavaLoop, readSet);
1661     mapFlatMethodToMustWriteSet.put(flatMethodContainingSSJavaLoop, mustWriteSet);
1662     mapFlatMethodToMayWriteSet.put(flatMethodContainingSSJavaLoop, mayWriteSet);
1663
1664     methodReadWriteSet_analyzeBody(ssjavaLoopEntrance, readSet, mustWriteSet, mayWriteSet,
1665         loopIncElements);
1666
1667   }
1668
1669   private void methodReadWriteSet_analyzeBody(FlatNode startNode, Set<NTuple<Descriptor>> readSet,
1670       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet,
1671       Set<FlatNode> bodyNodeSet) {
1672
1673     // intraprocedural analysis
1674     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
1675     flatNodesToVisit.add(startNode);
1676
1677     while (!flatNodesToVisit.isEmpty()) {
1678       FlatNode fn = flatNodesToVisit.iterator().next();
1679       flatNodesToVisit.remove(fn);
1680
1681       Set<NTuple<Descriptor>> currMustWriteSet = new HashSet<NTuple<Descriptor>>();
1682
1683       for (int i = 0; i < fn.numPrev(); i++) {
1684         FlatNode prevFn = fn.getPrev(i);
1685         Set<NTuple<Descriptor>> in = mapFlatNodeToMustWriteSet.get(prevFn);
1686         if (in != null) {
1687           merge(currMustWriteSet, in);
1688         }
1689       }
1690
1691       methodReadWriteSet_nodeActions(fn, currMustWriteSet, readSet, mustWriteSet, mayWriteSet);
1692
1693       Set<NTuple<Descriptor>> mustSetPrev = mapFlatNodeToMustWriteSet.get(fn);
1694       if (!currMustWriteSet.equals(mustSetPrev)) {
1695         mapFlatNodeToMustWriteSet.put(fn, currMustWriteSet);
1696         for (int i = 0; i < fn.numNext(); i++) {
1697           FlatNode nn = fn.getNext(i);
1698           if (bodyNodeSet == null || bodyNodeSet.contains(nn)) {
1699             flatNodesToVisit.add(nn);
1700           }
1701
1702         }
1703       }
1704
1705     }
1706
1707   }
1708
1709   private void methodReadWriteSet_nodeActions(FlatNode fn,
1710       Set<NTuple<Descriptor>> currMustWriteSet, Set<NTuple<Descriptor>> readSet,
1711       Set<NTuple<Descriptor>> mustWriteSet, Set<NTuple<Descriptor>> mayWriteSet) {
1712     TempDescriptor lhs;
1713     TempDescriptor rhs;
1714     FieldDescriptor fld;
1715
1716     switch (fn.kind()) {
1717     case FKind.FlatMethod: {
1718
1719       // set up initial heap paths for method parameters
1720       FlatMethod fm = (FlatMethod) fn;
1721       for (int i = 0; i < fm.numParameters(); i++) {
1722         TempDescriptor param = fm.getParameter(i);
1723         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1724         heapPath.add(param);
1725         mapHeapPath.put(param, heapPath);
1726       }
1727     }
1728       break;
1729
1730     case FKind.FlatOpNode: {
1731       FlatOpNode fon = (FlatOpNode) fn;
1732       // for a normal assign node, need to propagate lhs's heap path to
1733       // rhs
1734       if (fon.getOp().getOp() == Operation.ASSIGN) {
1735         rhs = fon.getLeft();
1736         lhs = fon.getDest();
1737
1738         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
1739         if (rhsHeapPath != null) {
1740           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
1741         } else {
1742           NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
1743           heapPath.add(rhs);
1744           mapHeapPath.put(lhs, heapPath);
1745         }
1746
1747       }
1748     }
1749       break;
1750
1751     case FKind.FlatElementNode:
1752     case FKind.FlatFieldNode: {
1753
1754       // x=y.f;
1755
1756       if (fn.kind() == FKind.FlatFieldNode) {
1757         FlatFieldNode ffn = (FlatFieldNode) fn;
1758         lhs = ffn.getDst();
1759         rhs = ffn.getSrc();
1760         fld = ffn.getField();
1761       } else {
1762         FlatElementNode fen = (FlatElementNode) fn;
1763         lhs = fen.getDst();
1764         rhs = fen.getSrc();
1765         TypeDescriptor td = rhs.getType().dereference();
1766         fld = getArrayField(td);
1767       }
1768
1769       if (fld.isFinal()) {
1770         // if field is final no need to check
1771         break;
1772       }
1773
1774       // set up heap path
1775       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
1776       if (srcHeapPath != null) {
1777         // if lhs srcHeapPath is null, it means that it is not reachable from
1778         // callee's parameters. so just ignore it
1779
1780         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
1781         readingHeapPath.add(fld);
1782         mapHeapPath.put(lhs, readingHeapPath);
1783
1784         // read (x.f)
1785         if (fld.getType().isImmutable()) {
1786           // if WT doesnot have hp(x.f), add hp(x.f) to READ
1787           if (!currMustWriteSet.contains(readingHeapPath)) {
1788             readSet.add(readingHeapPath);
1789           }
1790         }
1791
1792         // no need to kill hp(x.f) from WT
1793       }
1794
1795     }
1796       break;
1797
1798     case FKind.FlatSetFieldNode:
1799     case FKind.FlatSetElementNode: {
1800
1801       // x.f=y;
1802
1803       if (fn.kind() == FKind.FlatSetFieldNode) {
1804         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
1805         lhs = fsfn.getDst();
1806         fld = fsfn.getField();
1807         rhs = fsfn.getSrc();
1808       } else {
1809         FlatSetElementNode fsen = (FlatSetElementNode) fn;
1810         lhs = fsen.getDst();
1811         rhs = fsen.getSrc();
1812         TypeDescriptor td = lhs.getType().dereference();
1813         fld = getArrayField(td);
1814       }
1815
1816       // set up heap path
1817       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
1818
1819       if (lhsHeapPath != null) {
1820         // if lhs heap path is null, it means that it is not reachable from
1821         // callee's parameters. so just ignore it
1822         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
1823         newHeapPath.add(fld);
1824         mapHeapPath.put(fld, newHeapPath);
1825
1826         // write(x.f)
1827         // need to add hp(y) to WT
1828         currMustWriteSet.add(newHeapPath);
1829         mayWriteSet.add(newHeapPath);
1830
1831       }
1832
1833     }
1834       break;
1835
1836     case FKind.FlatCall: {
1837
1838       FlatCall fc = (FlatCall) fn;
1839
1840       bindHeapPathCallerArgWithCaleeParam(fc);
1841
1842       mapFlatNodeToBoundReadSet.put(fn, calleeUnionBoundReadSet);
1843       mapFlatNodeToBoundMustWriteSet.put(fn, calleeIntersectBoundMustWriteSet);
1844       mapFlatNodeToBoundMayWriteSet.put(fn, calleeUnionBoundMayWriteSet);
1845
1846       // add heap path, which is an element of READ_bound set and is not
1847       // an
1848       // element of WT set, to the caller's READ set
1849       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
1850         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
1851         if (!currMustWriteSet.contains(read)) {
1852           readSet.add(read);
1853         }
1854       }
1855
1856       // add heap path, which is an element of OVERWRITE_bound set, to the
1857       // caller's WT set
1858       for (Iterator iterator = calleeIntersectBoundMustWriteSet.iterator(); iterator.hasNext();) {
1859         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1860         currMustWriteSet.add(write);
1861       }
1862
1863       // add heap path, which is an element of WRITE_BOUND set, to the
1864       // caller's writeSet
1865       for (Iterator iterator = calleeUnionBoundMayWriteSet.iterator(); iterator.hasNext();) {
1866         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
1867         mayWriteSet.add(write);
1868       }
1869
1870     }
1871       break;
1872
1873     case FKind.FlatExit: {
1874       // merge the current written set with OVERWRITE set
1875       merge(mustWriteSet, currMustWriteSet);
1876     }
1877       break;
1878
1879     }
1880
1881   }
1882
1883   static public FieldDescriptor getArrayField(TypeDescriptor td) {
1884     FieldDescriptor fd = mapTypeToArrayField.get(td);
1885     if (fd == null) {
1886       fd =
1887           new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
1888               false);
1889       mapTypeToArrayField.put(td, fd);
1890     }
1891     return fd;
1892   }
1893
1894   private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
1895     if (inSet.size() == 0) {
1896       return;
1897     }
1898     Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
1899         new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
1900
1901     for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
1902
1903       ClearingSummary inTable = (ClearingSummary) inIterator.next();
1904
1905       Set<NTuple<Descriptor>> keySet = inTable.keySet();
1906
1907       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1908         NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1909         SharedStatus inState = inTable.get(hpKey);
1910         SharedStatus currState = curr.get(hpKey);
1911         if (currState == null) {
1912           currState = new SharedStatus();
1913           curr.put(hpKey, currState);
1914         }
1915
1916         currState.merge(inState);
1917
1918         Set<Location> locSet = inState.getMap().keySet();
1919         for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
1920           Location loc = (Location) iterator2.next();
1921           Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
1922           boolean inFlag = pair.getSecond().booleanValue();
1923
1924           Pair<NTuple<Descriptor>, Location> flagKey =
1925               new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
1926           Boolean current = mapHeapPathLoc2Flag.get(flagKey);
1927           if (current == null) {
1928             current = new Boolean(true);
1929           }
1930           boolean newInFlag = current.booleanValue() & inFlag;
1931           mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
1932         }
1933
1934       }
1935
1936     }
1937
1938     // merge flag status
1939     Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
1940     for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
1941       NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
1942       SharedStatus currState = curr.get(hpKey);
1943       Set<Location> locKeySet = currState.getMap().keySet();
1944       for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
1945         Location locKey = (Location) iterator2.next();
1946         Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
1947         boolean currentFlag = pair.getSecond().booleanValue();
1948         Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
1949         if (inFlag != null) {
1950           boolean newFlag = currentFlag | inFlag.booleanValue();
1951           if (currentFlag != newFlag) {
1952             currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
1953           }
1954         }
1955       }
1956     }
1957
1958   }
1959
1960   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
1961     if (curr.isEmpty()) {
1962       // set has a special initial value which covers all possible
1963       // elements
1964       // For the first time of intersection, we can take all previous set
1965       curr.addAll(in);
1966     } else {
1967       // otherwise, current set is the intersection of the two sets
1968       curr.retainAll(in);
1969     }
1970
1971   }
1972
1973   // combine two heap path
1974   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
1975     NTuple<Descriptor> combined = new NTuple<Descriptor>();
1976
1977     for (int i = 0; i < callerIn.size(); i++) {
1978       combined.add(callerIn.get(i));
1979     }
1980
1981     // the first element of callee's heap path represents parameter
1982     // so we skip the first one since it is already added from caller's heap
1983     // path
1984     for (int i = 1; i < calleeIn.size(); i++) {
1985       combined.add(calleeIn.get(i));
1986     }
1987
1988     return combined;
1989   }
1990
1991   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
1992       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
1993       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
1994
1995     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
1996
1997     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
1998     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1999       Integer idx = (Integer) iterator.next();
2000
2001       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
2002       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
2003       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
2004         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
2005         if (element.startsWith(calleeParam)) {
2006           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
2007           boundedCalleeSet.add(boundElement);
2008         }
2009
2010       }
2011
2012     }
2013     return boundedCalleeSet;
2014
2015   }
2016
2017   // Borrowed it from disjoint analysis
2018   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
2019
2020     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
2021
2022     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
2023
2024     Iterator<MethodDescriptor> itr = toSort.iterator();
2025     while (itr.hasNext()) {
2026       MethodDescriptor d = itr.next();
2027
2028       if (!discovered.contains(d)) {
2029         dfsVisit(d, toSort, sorted, discovered);
2030       }
2031     }
2032
2033     return sorted;
2034   }
2035
2036   // While we're doing DFS on call graph, remember
2037   // dependencies for efficient queuing of methods
2038   // during interprocedural analysis:
2039   //
2040   // a dependent of a method decriptor d for this analysis is:
2041   // 1) a method or task that invokes d
2042   // 2) in the descriptorsToAnalyze set
2043   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
2044       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
2045
2046     discovered.add(md);
2047
2048     Iterator itr = callGraph.getCallerSet(md).iterator();
2049     while (itr.hasNext()) {
2050       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
2051       // only consider callers in the original set to analyze
2052       if (!toSort.contains(dCaller)) {
2053         continue;
2054       }
2055       if (!discovered.contains(dCaller)) {
2056         addDependent(md, // callee
2057             dCaller // caller
2058         );
2059
2060         dfsVisit(dCaller, toSort, sorted, discovered);
2061       }
2062     }
2063
2064     // for leaf-nodes last now!
2065     sorted.addLast(md);
2066   }
2067
2068   // a dependent of a method decriptor d for this analysis is:
2069   // 1) a method or task that invokes d
2070   // 2) in the descriptorsToAnalyze set
2071   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
2072     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2073     if (deps == null) {
2074       deps = new HashSet<MethodDescriptor>();
2075     }
2076     deps.add(caller);
2077     mapDescriptorToSetDependents.put(callee, deps);
2078   }
2079
2080   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
2081     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
2082     if (deps == null) {
2083       deps = new HashSet<MethodDescriptor>();
2084       mapDescriptorToSetDependents.put(callee, deps);
2085     }
2086     return deps;
2087   }
2088
2089   private NTuple<Descriptor> computePath(TempDescriptor td) {
2090     // generate proper path fot input td
2091     // if td is local variable, it just generate one element tuple path
2092     if (mapHeapPath.containsKey(td)) {
2093       return mapHeapPath.get(td);
2094     } else {
2095       NTuple<Descriptor> path = new NTuple<Descriptor>();
2096       path.add(td);
2097       return path;
2098     }
2099   }
2100
2101 }