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 IR.Descriptor;
  12 import IR.FieldDescriptor;
  13 import IR.MethodDescriptor;
  14 import IR.Operation;
  15 import IR.State;
  16 import IR.TypeDescriptor;
  17 import IR.Flat.FKind;
  18 import IR.Flat.FlatCall;
  19 import IR.Flat.FlatFieldNode;
  20 import IR.Flat.FlatLiteralNode;
  21 import IR.Flat.FlatMethod;
  22 import IR.Flat.FlatNode;
  23 import IR.Flat.FlatOpNode;
  24 import IR.Flat.FlatSetFieldNode;
  25 import IR.Flat.TempDescriptor;
  26
  27 public class DefinitelyWrittenCheck {
  28
  29   SSJavaAnalysis ssjava;
  30   State state;
  31   CallGraph callGraph;
  32
  33   // maps a descriptor to its known dependents: namely
  34   // methods or tasks that call the descriptor's method
  35   // AND are part of this analysis (reachable from main)
  36   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  37
  38   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  39   // previously.
  40   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  41
  42   // maps a temp descriptor to its heap path
  43   // each temp descriptor has a unique heap path since we do not allow any
  44   // alias.
  45   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  46
  47   // maps a flat method to the READ that is the set of heap path that is
  48   // expected to be written before method invocation
  49   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  50
  51   // maps a flat method to the OVERWRITE that is the set of heap path that is
  52   // overwritten on every possible path during method invocation
  53   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  54
  55   // points to method containing SSJAVA Loop
  56   private MethodDescriptor methodContainingSSJavaLoop;
  57
  58   // maps a flatnode to definitely written analysis mapping M
  59   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  60
  61   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  62   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  63
  64   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  65     this.state = state;
  66     this.ssjava = ssjava;
  67     this.callGraph = ssjava.getCallGraph();
  68     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
  69     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
  70     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
  71     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  72     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  73     this.definitelyWrittenResults =
  74         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
  75     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
  76     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
  77   }
  78
  79   public void definitelyWrittenCheck() {
  80     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
  81       methodReadOverWriteAnalysis();
  82       writtenAnalyis();
  83     }
  84   }
  85
  86   private void writtenAnalyis() {
  87     // perform second stage analysis: intraprocedural analysis ensure that
  88     // all
  89     // variables are definitely written in-between the same read
  90
  91     // First, identify ssjava loop entrace
  92     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
  93     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
  94     flatNodesToVisit.add(fm);
  95
  96     FlatNode entrance = null;
  97
  98     while (!flatNodesToVisit.isEmpty()) {
  99       FlatNode fn = flatNodesToVisit.iterator().next();
 100       flatNodesToVisit.remove(fn);
 101
 102       String label = (String) state.fn2labelMap.get(fn);
 103       if (label != null) {
 104
 105         if (label.equals(ssjava.SSJAVA)) {
 106           entrance = fn;
 107           break;
 108         }
 109       }
 110
 111       for (int i = 0; i < fn.numNext(); i++) {
 112         FlatNode nn = fn.getNext(i);
 113         flatNodesToVisit.add(nn);
 114       }
 115     }
 116
 117     assert entrance != null;
 118
 119     writtenAnalysis_analyzeLoop(entrance);
 120
 121   }
 122
 123   private void writtenAnalysis_analyzeLoop(FlatNode entrance) {
 124
 125     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 126     flatNodesToVisit.add(entrance);
 127
 128     while (!flatNodesToVisit.isEmpty()) {
 129       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 130       flatNodesToVisit.remove(fn);
 131
 132       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 133           definitelyWrittenResults.get(fn);
 134
 135       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 136           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 137       for (int i = 0; i < fn.numPrev(); i++) {
 138         FlatNode nn = fn.getPrev(i);
 139         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 140             definitelyWrittenResults.get(nn);
 141         if (dwIn != null) {
 142           merge(curr, dwIn);
 143         }
 144       }
 145
 146       writtenAnalysis_nodeAction(fn, curr, entrance);
 147
 148       // if a new result, schedule forward nodes for analysis
 149       if (!curr.equals(prev)) {
 150         definitelyWrittenResults.put(fn, curr);
 151
 152         for (int i = 0; i < fn.numNext(); i++) {
 153           FlatNode nn = fn.getNext(i);
 154           flatNodesToVisit.add(nn);
 155         }
 156       }
 157     }
 158   }
 159
 160   private void writtenAnalysis_nodeAction(FlatNode fn,
 161       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 162
 163     if (fn.equals(loopEntrance)) {
 164       // it reaches loop entrance: changes all flag to true
 165       Set<NTuple<Descriptor>> keySet = curr.keySet();
 166       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 167         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 168         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 169         if (pair != null) {
 170           Set<FlatNode> pairKeySet = pair.keySet();
 171           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 172             FlatNode pairKey = (FlatNode) iterator2.next();
 173             pair.put(pairKey, Boolean.TRUE);
 174           }
 175         }
 176       }
 177     } else {
 178       TempDescriptor lhs;
 179       TempDescriptor rhs;
 180       FieldDescriptor fld;
 181
 182       switch (fn.kind()) {
 183       case FKind.FlatOpNode: {
 184         FlatOpNode fon = (FlatOpNode) fn;
 185         lhs = fon.getDest();
 186         rhs = fon.getLeft();
 187
 188         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 189         if (!rhs.getType().isImmutable()) {
 190           mapHeapPath.put(lhs, rhsHeapPath);
 191         } else {
 192           if (fon.getOp().getOp() == Operation.ASSIGN) {
 193             // read(rhs)
 194             readValue(fn, rhsHeapPath, curr);
 195           }
 196           // write(lhs)
 197           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 198           removeHeapPath(curr, lhsHeapPath);
 199         }
 200       }
 201         break;
 202
 203       case FKind.FlatLiteralNode: {
 204         FlatLiteralNode fln = (FlatLiteralNode) fn;
 205         lhs = fln.getDst();
 206
 207         // write(lhs)
 208         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 209         removeHeapPath(curr, lhsHeapPath);
 210
 211       }
 212         break;
 213
 214       case FKind.FlatFieldNode:
 215       case FKind.FlatElementNode: {
 216
 217         FlatFieldNode ffn = (FlatFieldNode) fn;
 218         lhs = ffn.getDst();
 219         rhs = ffn.getSrc();
 220         fld = ffn.getField();
 221
 222         // read field
 223         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 224         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 225         fldHeapPath.add(fld);
 226
 227         if (fld.getType().isImmutable()) {
 228           readValue(fn, fldHeapPath, curr);
 229         }
 230
 231         // propagate rhs's heap path to the lhs
 232         mapHeapPath.put(lhs, fldHeapPath);
 233
 234       }
 235         break;
 236
 237       case FKind.FlatSetFieldNode:
 238       case FKind.FlatSetElementNode: {
 239
 240         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 241         lhs = fsfn.getDst();
 242         fld = fsfn.getField();
 243
 244         // write(field)
 245         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 246         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 247         fldHeapPath.add(fld);
 248         removeHeapPath(curr, fldHeapPath);
 249
 250       }
 251         break;
 252
 253       case FKind.FlatCall: {
 254         FlatCall fc = (FlatCall) fn;
 255         bindHeapPathCallerArgWithCaleeParam(fc);
 256
 257         // add <hp,statement,false> in which hp is an element of
 258         // READ_bound set
 259         // of callee: callee has 'read' requirement!
 260         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 261           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 262
 263           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 264           if (gen == null) {
 265             gen = new Hashtable<FlatNode, Boolean>();
 266             curr.put(read, gen);
 267           }
 268           Boolean currentStatus = gen.get(fn);
 269           if (currentStatus == null) {
 270             gen.put(fn, Boolean.FALSE);
 271           } else {
 272             checkFlag(currentStatus.booleanValue(), fn, read);
 273           }
 274         }
 275
 276         // removes <hp,statement,flag> if hp is an element of
 277         // OVERWRITE_bound
 278         // set of callee. it means that callee will overwrite it
 279         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 280           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 281           removeHeapPath(curr, write);
 282         }
 283       }
 284         break;
 285
 286       }
 287     }
 288
 289   }
 290
 291   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 292       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 293     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 294     if (gen == null) {
 295       gen = new Hashtable<FlatNode, Boolean>();
 296       curr.put(hp, gen);
 297     }
 298     Boolean currentStatus = gen.get(fn);
 299     if (currentStatus == null) {
 300       gen.put(fn, Boolean.FALSE);
 301     } else {
 302       checkFlag(currentStatus.booleanValue(), fn, hp);
 303     }
 304
 305   }
 306
 307   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 308       NTuple<Descriptor> hp) {
 309
 310     // removes all of heap path that starts with prefix 'hp'
 311     // since any reference overwrite along heap path gives overwriting side
 312     // effects on the value
 313
 314     Set<NTuple<Descriptor>> keySet = curr.keySet();
 315     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 316       NTuple<Descriptor> key = iter.next();
 317       if (key.startsWith(hp)) {
 318         curr.put(key, new Hashtable<FlatNode, Boolean>());
 319       }
 320     }
 321
 322   }
 323
 324   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
 325     // compute all possible callee set
 326     // transform all READ/OVERWRITE set from the any possible
 327     // callees to the
 328     // caller
 329
 330     calleeUnionBoundReadSet.clear();
 331     calleeIntersectBoundOverWriteSet.clear();
 332
 333     MethodDescriptor mdCallee = fc.getMethod();
 334     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 335     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 336     TypeDescriptor typeDesc = fc.getThis().getType();
 337     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 338
 339     // create mapping from arg idx to its heap paths
 340     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 341         new Hashtable<Integer, NTuple<Descriptor>>();
 342
 343     // arg idx is starting from 'this' arg
 344     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 345     if (thisHeapPath == null) {
 346       // method is called without creating new flat node representing 'this'
 347       thisHeapPath = new NTuple<Descriptor>();
 348       thisHeapPath.add(fc.getThis());
 349     }
 350
 351     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 352
 353     for (int i = 0; i < fc.numArgs(); i++) {
 354       TempDescriptor arg = fc.getArg(i);
 355       NTuple<Descriptor> argHeapPath = computePath(arg);
 356       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 357     }
 358
 359     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 360       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 361       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
 362
 363       // binding caller's args and callee's params
 364
 365       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
 366       if (calleeReadSet == null) {
 367         calleeReadSet = new HashSet<NTuple<Descriptor>>();
 368         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
 369       }
 370       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
 371       if (calleeOverWriteSet == null) {
 372         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
 373         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
 374       }
 375
 376       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 377           new Hashtable<Integer, TempDescriptor>();
 378       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 379         TempDescriptor param = calleeFlatMethod.getParameter(i);
 380         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 381       }
 382
 383       Set<NTuple<Descriptor>> calleeBoundReadSet =
 384           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 385       // union of the current read set and the current callee's
 386       // read set
 387       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
 388       Set<NTuple<Descriptor>> calleeBoundWriteSet =
 389           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 390       // intersection of the current overwrite set and the current
 391       // callee's
 392       // overwrite set
 393       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
 394     }
 395
 396   }
 397
 398   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
 399     if (booleanValue) {
 400       throw new Error(
 401           "There is a variable, which is reachable through references "
 402               + hp
 403               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
 404               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
 405               + fn.getNumLine());
 406     }
 407   }
 408
 409   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 410       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
 411
 412     Set<NTuple<Descriptor>> inKeySet = in.keySet();
 413     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
 414       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
 415       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 416
 417       Set<FlatNode> pairKeySet = inPair.keySet();
 418       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 419         FlatNode pairKey = (FlatNode) iterator2.next();
 420         Boolean inFlag = inPair.get(pairKey);
 421
 422         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 423         if (currPair == null) {
 424           currPair = new Hashtable<FlatNode, Boolean>();
 425           curr.put(inKey, currPair);
 426         }
 427
 428         Boolean currFlag = currPair.get(pairKey);
 429         // by default, flag is set by false
 430         if (currFlag == null) {
 431           currFlag = Boolean.FALSE;
 432         }
 433         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 434         currPair.put(pairKey, currFlag);
 435       }
 436
 437     }
 438
 439   }
 440
 441   private void methodReadOverWriteAnalysis() {
 442     // perform method READ/OVERWRITE analysis
 443     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 444     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 445
 446     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 447
 448     // no need to analyze method having ssjava loop
 449     methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
 450
 451     // current descriptors to visit in fixed-point interprocedural analysis,
 452     // prioritized by
 453     // dependency in the call graph
 454     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 455
 456     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 457     methodDescriptorToVistSet.addAll(sortedDescriptors);
 458
 459     while (!sortedDescriptors.isEmpty()) {
 460       MethodDescriptor md = sortedDescriptors.removeFirst();
 461       methodDescriptorsToVisitStack.add(md);
 462     }
 463
 464     // analyze scheduled methods until there are no more to visit
 465     while (!methodDescriptorsToVisitStack.isEmpty()) {
 466       // start to analyze leaf node
 467       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 468       FlatMethod fm = state.getMethodFlat(md);
 469
 470       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
 471       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
 472
 473       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
 474
 475       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
 476       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
 477
 478       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
 479         mapFlatMethodToRead.put(fm, readSet);
 480         mapFlatMethodToOverWrite.put(fm, overWriteSet);
 481
 482         // results for callee changed, so enqueue dependents caller for
 483         // further
 484         // analysis
 485         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 486         while (depsItr.hasNext()) {
 487           MethodDescriptor methodNext = depsItr.next();
 488           if (!methodDescriptorsToVisitStack.contains(methodNext)
 489               && methodDescriptorToVistSet.contains(methodNext)) {
 490             methodDescriptorsToVisitStack.add(methodNext);
 491           }
 492
 493         }
 494
 495       }
 496
 497     }
 498
 499   }
 500
 501   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
 502       Set<NTuple<Descriptor>> overWriteSet) {
 503     if (state.SSJAVADEBUG) {
 504       System.out.println("Definitely written Analyzing: " + fm);
 505     }
 506
 507     // intraprocedural analysis
 508     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 509     Set<FlatNode> visited = new HashSet<FlatNode>();
 510     flatNodesToVisit.add(fm);
 511
 512     while (!flatNodesToVisit.isEmpty()) {
 513       FlatNode fn = flatNodesToVisit.iterator().next();
 514       flatNodesToVisit.remove(fn);
 515       visited.add(fn);
 516
 517       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
 518
 519       for (int i = 0; i < fn.numPrev(); i++) {
 520         FlatNode prevFn = fn.getPrev(i);
 521         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
 522         if (in != null) {
 523           merge(curr, in);
 524         }
 525       }
 526
 527       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
 528
 529       mapFlatNodeToWrittenSet.put(fn, curr);
 530
 531       for (int i = 0; i < fn.numNext(); i++) {
 532         FlatNode nn = fn.getNext(i);
 533         if (!visited.contains(nn)) {
 534           flatNodesToVisit.add(nn);
 535         }
 536       }
 537
 538     }
 539
 540   }
 541
 542   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
 543       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
 544     TempDescriptor lhs;
 545     TempDescriptor rhs;
 546     FieldDescriptor fld;
 547
 548     switch (fn.kind()) {
 549     case FKind.FlatMethod: {
 550
 551       // set up initial heap paths for method parameters
 552       FlatMethod fm = (FlatMethod) fn;
 553       for (int i = 0; i < fm.numParameters(); i++) {
 554         TempDescriptor param = fm.getParameter(i);
 555         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
 556         heapPath.add(param);
 557         mapHeapPath.put(param, heapPath);
 558       }
 559     }
 560       break;
 561
 562     case FKind.FlatOpNode: {
 563       FlatOpNode fon = (FlatOpNode) fn;
 564       // for a normal assign node, need to propagate lhs's heap path to
 565       // rhs
 566       if (fon.getOp().getOp() == Operation.ASSIGN) {
 567         rhs = fon.getLeft();
 568         lhs = fon.getDest();
 569
 570         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
 571         if (rhsHeapPath != null) {
 572           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
 573         }
 574
 575       }
 576     }
 577       break;
 578
 579     case FKind.FlatFieldNode:
 580     case FKind.FlatElementNode: {
 581
 582       // y=x.f;
 583
 584       FlatFieldNode ffn = (FlatFieldNode) fn;
 585       lhs = ffn.getDst();
 586       rhs = ffn.getSrc();
 587       fld = ffn.getField();
 588
 589       // set up heap path
 590       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 591       if (srcHeapPath != null) {
 592         // if lhs srcHeapPath is null, it means that it is not reachable from
 593         // callee's parameters. so just ignore it
 594
 595         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 596         readingHeapPath.add(fld);
 597         mapHeapPath.put(lhs, readingHeapPath);
 598
 599         // read (x.f)
 600         if (fld.getType().isImmutable()) {
 601           // if WT doesnot have hp(x.f), add hp(x.f) to READ
 602           if (!writtenSet.contains(readingHeapPath)) {
 603             readSet.add(readingHeapPath);
 604           }
 605         }
 606
 607         // need to kill hp(x.f) from WT
 608         writtenSet.remove(readingHeapPath);
 609       }
 610
 611     }
 612       break;
 613
 614     case FKind.FlatSetFieldNode:
 615     case FKind.FlatSetElementNode: {
 616
 617       // x.f=y;
 618       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 619       lhs = fsfn.getDst();
 620       fld = fsfn.getField();
 621       rhs = fsfn.getSrc();
 622
 623       // set up heap path
 624       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
 625       if (lhsHeapPath != null) {
 626         // if lhs heap path is null, it means that it is not reachable from
 627         // callee's parameters. so just ignore it
 628         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 629         newHeapPath.add(fld);
 630         mapHeapPath.put(fld, newHeapPath);
 631
 632         // write(x.f)
 633         // need to add hp(y) to WT
 634         writtenSet.add(newHeapPath);
 635       }
 636
 637     }
 638       break;
 639
 640     case FKind.FlatCall: {
 641
 642       FlatCall fc = (FlatCall) fn;
 643
 644       bindHeapPathCallerArgWithCaleeParam(fc);
 645
 646       // add heap path, which is an element of READ_bound set and is not
 647       // an
 648       // element of WT set, to the caller's READ set
 649       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 650         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 651         if (!writtenSet.contains(read)) {
 652           readSet.add(read);
 653         }
 654       }
 655       writtenSet.removeAll(calleeUnionBoundReadSet);
 656
 657       // add heap path, which is an element of OVERWRITE_bound set, to the
 658       // caller's WT set
 659       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 660         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 661         writtenSet.add(write);
 662       }
 663
 664     }
 665       break;
 666
 667     case FKind.FlatExit: {
 668       // merge the current written set with OVERWRITE set
 669       merge(overWriteSet, writtenSet);
 670     }
 671       break;
 672
 673     }
 674
 675   }
 676
 677   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
 678     if (curr.isEmpty()) {
 679       // WrittenSet has a special initial value which covers all possible
 680       // elements
 681       // For the first time of intersection, we can take all previous set
 682       curr.addAll(in);
 683     } else {
 684       // otherwise, current set is the intersection of the two sets
 685       curr.retainAll(in);
 686     }
 687
 688   }
 689
 690   // combine two heap path
 691   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
 692     NTuple<Descriptor> combined = new NTuple<Descriptor>();
 693
 694     for (int i = 0; i < callerIn.size(); i++) {
 695       combined.add(callerIn.get(i));
 696     }
 697
 698     // the first element of callee's heap path represents parameter
 699     // so we skip the first one since it is already added from caller's heap
 700     // path
 701     for (int i = 1; i < calleeIn.size(); i++) {
 702       combined.add(calleeIn.get(i));
 703     }
 704
 705     return combined;
 706   }
 707
 708   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
 709       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
 710       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
 711
 712     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
 713
 714     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
 715     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 716       Integer idx = (Integer) iterator.next();
 717
 718       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
 719       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
 720
 721       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
 722         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
 723         if (element.startsWith(calleeParam)) {
 724           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
 725           boundedCalleeSet.add(boundElement);
 726         }
 727
 728       }
 729
 730     }
 731     return boundedCalleeSet;
 732
 733   }
 734
 735   // Borrowed it from disjoint analysis
 736   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
 737
 738     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
 739
 740     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
 741
 742     Iterator<MethodDescriptor> itr = toSort.iterator();
 743     while (itr.hasNext()) {
 744       MethodDescriptor d = itr.next();
 745
 746       if (!discovered.contains(d)) {
 747         dfsVisit(d, toSort, sorted, discovered);
 748       }
 749     }
 750
 751     return sorted;
 752   }
 753
 754   // While we're doing DFS on call graph, remember
 755   // dependencies for efficient queuing of methods
 756   // during interprocedural analysis:
 757   //
 758   // a dependent of a method decriptor d for this analysis is:
 759   // 1) a method or task that invokes d
 760   // 2) in the descriptorsToAnalyze set
 761   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
 762       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
 763
 764     discovered.add(md);
 765
 766     // otherwise call graph guides DFS
 767     Iterator itr = callGraph.getCallerSet(md).iterator();
 768     while (itr.hasNext()) {
 769       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
 770
 771       // only consider callers in the original set to analyze
 772       if (!toSort.contains(dCaller)) {
 773         continue;
 774       }
 775
 776       if (!discovered.contains(dCaller)) {
 777         addDependent(md, // callee
 778             dCaller // caller
 779         );
 780
 781         dfsVisit(dCaller, toSort, sorted, discovered);
 782       }
 783     }
 784
 785     // for leaf-nodes last now!
 786     sorted.addLast(md);
 787   }
 788
 789   // a dependent of a method decriptor d for this analysis is:
 790   // 1) a method or task that invokes d
 791   // 2) in the descriptorsToAnalyze set
 792   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
 793     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
 794     if (deps == null) {
 795       deps = new HashSet<MethodDescriptor>();
 796     }
 797     deps.add(caller);
 798     mapDescriptorToSetDependents.put(callee, deps);
 799   }
 800
 801   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
 802     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
 803     if (deps == null) {
 804       deps = new HashSet<MethodDescriptor>();
 805       mapDescriptorToSetDependents.put(callee, deps);
 806     }
 807     return deps;
 808   }
 809
 810   private NTuple<Descriptor> computePath(TempDescriptor td) {
 811     // generate proper path fot input td
 812     // if td is local variable, it just generate one element tuple path
 813     if (mapHeapPath.containsKey(td)) {
 814       return mapHeapPath.get(td);
 815     } else {
 816       NTuple<Descriptor> path = new NTuple<Descriptor>();
 817       path.add(td);
 818       return path;
 819     }
 820   }
 821
 822 }