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