Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java

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