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