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 import java.util.Vector;
  10
  11 import Analysis.CallGraph.CallGraph;
  12 import Analysis.Loops.LoopFinder;
  13 import IR.Descriptor;
  14 import IR.FieldDescriptor;
  15 import IR.MethodDescriptor;
  16 import IR.Operation;
  17 import IR.State;
  18 import IR.TypeDescriptor;
  19 import IR.Flat.FKind;
  20 import IR.Flat.FlatCall;
  21 import IR.Flat.FlatFieldNode;
  22 import IR.Flat.FlatLiteralNode;
  23 import IR.Flat.FlatMethod;
  24 import IR.Flat.FlatNode;
  25 import IR.Flat.FlatOpNode;
  26 import IR.Flat.FlatSetFieldNode;
  27 import IR.Flat.TempDescriptor;
  28
  29 public class DefinitelyWrittenCheck {
  30
  31   SSJavaAnalysis ssjava;
  32   State state;
  33   CallGraph callGraph;
  34
  35   // maps a descriptor to its known dependents: namely
  36   // methods or tasks that call the descriptor's method
  37   // AND are part of this analysis (reachable from main)
  38   private Hashtable<Descriptor, Set<MethodDescriptor>> mapDescriptorToSetDependents;
  39
  40   // maps a flat node to its WrittenSet: this keeps all heap path overwritten
  41   // previously.
  42   private Hashtable<FlatNode, Set<NTuple<Descriptor>>> mapFlatNodeToWrittenSet;
  43
  44   // maps a temp descriptor to its heap path
  45   // each temp descriptor has a unique heap path since we do not allow any
  46   // alias.
  47   private Hashtable<Descriptor, NTuple<Descriptor>> mapHeapPath;
  48
  49   // maps a flat method to the READ that is the set of heap path that is
  50   // expected to be written before method invocation
  51   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToRead;
  52
  53   // maps a flat method to the OVERWRITE that is the set of heap path that is
  54   // overwritten on every possible path during method invocation
  55   private Hashtable<FlatMethod, Set<NTuple<Descriptor>>> mapFlatMethodToOverWrite;
  56
  57   // points to method containing SSJAVA Loop
  58   private MethodDescriptor methodContainingSSJavaLoop;
  59
  60   // maps a flatnode to definitely written analysis mapping M
  61   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>> definitelyWrittenResults;
  62
  63   // maps a method descriptor to its current summary during the analysis
  64   // then analysis reaches fixed-point, this mapping will have the final summary
  65   // for each method descriptor
  66   private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToCompleteClearingSummary;
  67
  68   // maps a method descriptor to the merged incoming caller's current
  69   // overwritten status
  70   private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToInitialClearingSummary;
  71
  72   // maps a flat node to current partial results
  73   private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapFlatNodeToClearingSummary;
  74
  75   private FlatNode ssjavaLoopEntrance;
  76   private LoopFinder ssjavaLoop;
  77   private Set<FlatNode> loopIncElements;
  78
  79   private Set<NTuple<Descriptor>> calleeUnionBoundReadSet;
  80   private Set<NTuple<Descriptor>> calleeIntersectBoundOverWriteSet;
  81
  82   private TempDescriptor LOCAL;
  83
  84   public DefinitelyWrittenCheck(SSJavaAnalysis ssjava, State state) {
  85     this.state = state;
  86     this.ssjava = ssjava;
  87     this.callGraph = ssjava.getCallGraph();
  88     this.mapFlatNodeToWrittenSet = new Hashtable<FlatNode, Set<NTuple<Descriptor>>>();
  89     this.mapDescriptorToSetDependents = new Hashtable<Descriptor, Set<MethodDescriptor>>();
  90     this.mapHeapPath = new Hashtable<Descriptor, NTuple<Descriptor>>();
  91     this.mapFlatMethodToRead = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  92     this.mapFlatMethodToOverWrite = new Hashtable<FlatMethod, Set<NTuple<Descriptor>>>();
  93     this.definitelyWrittenResults =
  94         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>>();
  95     this.calleeUnionBoundReadSet = new HashSet<NTuple<Descriptor>>();
  96     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
  97
  98     this.mapMethodDescriptorToCompleteClearingSummary =
  99         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
 100     this.mapMethodDescriptorToInitialClearingSummary =
 101         new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
 102     this.mapFlatNodeToClearingSummary =
 103         new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
 104     this.LOCAL = new TempDescriptor("LOCAL");
 105   }
 106
 107   public void definitelyWrittenCheck() {
 108     if (!ssjava.getAnnotationRequireSet().isEmpty()) {
 109       methodReadOverWriteAnalysis();
 110       writtenAnalyis();
 111       sharedLocationAnalysis();
 112     }
 113   }
 114
 115   private void sharedLocationAnalysis() {
 116     // verify that all concrete locations of shared location are cleared out at
 117     // the same time once per the out-most loop
 118
 119     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 120     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 121
 122     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 123
 124     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 125     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 126     methodDescriptorToVistSet.addAll(sortedDescriptors);
 127
 128     while (!sortedDescriptors.isEmpty()) {
 129       MethodDescriptor md = sortedDescriptors.removeLast();
 130       methodDescriptorsToVisitStack.add(md);
 131     }
 132
 133     // analyze scheduled methods until there are no more to visit
 134     while (!methodDescriptorsToVisitStack.isEmpty()) {
 135       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 136       FlatMethod fm = state.getMethodFlat(md);
 137
 138       sharedLocation_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
 139
 140       if (true) {
 141
 142         // results for callee changed, so enqueue dependents caller for
 143         // further analysis
 144         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 145         while (depsItr.hasNext()) {
 146           MethodDescriptor methodNext = depsItr.next();
 147           if (!methodDescriptorsToVisitStack.contains(methodNext)
 148               && methodDescriptorToVistSet.contains(methodNext)) {
 149             methodDescriptorsToVisitStack.add(methodNext);
 150           }
 151
 152         }
 153
 154       }
 155
 156     }
 157
 158     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 159     flatNodesToVisit.add(ssjavaLoopEntrance);
 160
 161   }
 162
 163   private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
 164
 165     if (state.SSJAVADEBUG) {
 166       System.out.println("Definitely written for shared locations Analyzing: " + fm + " "
 167           + onlyVisitSSJavaLoop);
 168     }
 169
 170     // intraprocedural analysis
 171     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 172     Set<FlatNode> visited = new HashSet<FlatNode>();
 173
 174     if (onlyVisitSSJavaLoop) {
 175       flatNodesToVisit.add(ssjavaLoopEntrance);
 176     } else {
 177       flatNodesToVisit.add(fm);
 178     }
 179
 180     while (!flatNodesToVisit.isEmpty()) {
 181       FlatNode fn = flatNodesToVisit.iterator().next();
 182       flatNodesToVisit.remove(fn);
 183
 184       Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr =
 185           new Hashtable<NTuple<Descriptor>, Set<SharedLocState>>();
 186
 187       for (int i = 0; i < fn.numPrev(); i++) {
 188         FlatNode prevFn = fn.getPrev(i);
 189         Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in =
 190             mapFlatNodeToClearingSummary.get(prevFn);
 191         if (in != null) {
 192           mergeSharedAnaylsis(curr, in);
 193         }
 194       }
 195
 196       sharedLocation_nodeActions(fn, curr, onlyVisitSSJavaLoop);
 197
 198       Hashtable<NTuple<Descriptor>, Set<SharedLocState>> clearingPrev =
 199           mapFlatNodeToClearingSummary.get(fn);
 200
 201       if (!curr.equals(clearingPrev)) {
 202         mapFlatNodeToClearingSummary.put(fn, curr);
 203
 204         for (int i = 0; i < fn.numNext(); i++) {
 205           FlatNode nn = fn.getNext(i);
 206
 207           if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
 208             flatNodesToVisit.add(nn);
 209           }
 210
 211         }
 212       }
 213
 214     }
 215
 216   }
 217
 218   private void sharedLocation_nodeActions(FlatNode fn,
 219       Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr, boolean isSSJavaLoop) {
 220
 221     TempDescriptor lhs;
 222     TempDescriptor rhs;
 223     FieldDescriptor fld;
 224     switch (fn.kind()) {
 225
 226     case FKind.FlatOpNode: {
 227       FlatOpNode fon = (FlatOpNode) fn;
 228       lhs = fon.getDest();
 229       rhs = fon.getLeft();
 230
 231       if (fon.getOp().getOp() == Operation.ASSIGN) {
 232         if (rhs.getType().isImmutable() && isSSJavaLoop) {
 233           // in ssjavaloop, we need to take care about reading local variables!
 234           NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
 235           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
 236           rhsHeapPath.add(LOCAL);
 237           lhsHeapPath.add(LOCAL);
 238           readLocation(curr, rhsHeapPath, rhs);
 239           writeLocation(curr, lhsHeapPath, lhs);
 240         }
 241       }
 242
 243     }
 244       break;
 245
 246     case FKind.FlatFieldNode:
 247     case FKind.FlatElementNode: {
 248
 249       FlatFieldNode ffn = (FlatFieldNode) fn;
 250       lhs = ffn.getDst();
 251       rhs = ffn.getSrc();
 252       fld = ffn.getField();
 253
 254       // read field
 255       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 256       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 257       fldHeapPath.add(fld);
 258
 259       if (fld.getType().isImmutable()) {
 260         // readLocation(f curr);
 261       }
 262
 263       // propagate rhs's heap path to the lhs
 264       mapHeapPath.put(lhs, fldHeapPath);
 265
 266     }
 267       break;
 268
 269     case FKind.FlatSetFieldNode:
 270     case FKind.FlatSetElementNode: {
 271
 272       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 273       lhs = fsfn.getDst();
 274       fld = fsfn.getField();
 275
 276       // write(field)
 277       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 278       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 279       // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 280
 281     }
 282       break;
 283
 284     case FKind.FlatCall: {
 285
 286     }
 287       break;
 288     }
 289
 290   }
 291
 292   private Location getLocation(Descriptor d) {
 293
 294     if (d instanceof FieldDescriptor) {
 295       return (Location) ((FieldDescriptor) d).getType().getExtension();
 296     } else {
 297       assert d instanceof TempDescriptor;
 298       CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
 299       return comp.get(comp.getSize() - 1);
 300     }
 301
 302   }
 303
 304   private SharedLocState getSharedLocState(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
 305       NTuple<Descriptor> hp, Location loc) {
 306
 307     Set<SharedLocState> set = curr.get(hp);
 308     if (set == null) {
 309       set = new HashSet<SharedLocState>();
 310       curr.put(hp, set);
 311     }
 312
 313     SharedLocState state = null;
 314     for (Iterator iterator = set.iterator(); iterator.hasNext();) {
 315       SharedLocState e = (SharedLocState) iterator.next();
 316       if (e.getLoc().equals(loc)) {
 317         state = e;
 318         break;
 319       }
 320     }
 321
 322     if (state == null) {
 323       state = new SharedLocState(loc);
 324       set.add(state);
 325     }
 326
 327     return state;
 328   }
 329
 330   private void writeLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
 331       NTuple<Descriptor> hp, Descriptor d) {
 332
 333     Location loc = getLocation(d);
 334     if (ssjava.isSharedLocation(loc)) {
 335       SharedLocState state = getSharedLocState(curr, hp, loc);
 336       state.addVar(d);
 337     }
 338   }
 339
 340   private void readLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
 341       NTuple<Descriptor> hp, Descriptor d) {
 342     // remove reading var x from written set
 343
 344     Location loc = getLocation(d);
 345     if (ssjava.isSharedLocation(loc)) {
 346       SharedLocState state = getSharedLocState(curr, hp, loc);
 347       state.removeVar(d);
 348     }
 349   }
 350
 351   private void writtenAnalyis() {
 352     // perform second stage analysis: intraprocedural analysis ensure that
 353     // all
 354     // variables are definitely written in-between the same read
 355
 356     // First, identify ssjava loop entrace
 357     FlatMethod fm = state.getMethodFlat(methodContainingSSJavaLoop);
 358     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 359     flatNodesToVisit.add(fm);
 360
 361     LoopFinder loopFinder = new LoopFinder(fm);
 362
 363     while (!flatNodesToVisit.isEmpty()) {
 364       FlatNode fn = flatNodesToVisit.iterator().next();
 365       flatNodesToVisit.remove(fn);
 366
 367       String label = (String) state.fn2labelMap.get(fn);
 368       if (label != null) {
 369
 370         if (label.equals(ssjava.SSJAVA)) {
 371           ssjavaLoopEntrance = fn;
 372           break;
 373         }
 374       }
 375
 376       for (int i = 0; i < fn.numNext(); i++) {
 377         FlatNode nn = fn.getNext(i);
 378         flatNodesToVisit.add(nn);
 379       }
 380     }
 381
 382     assert ssjavaLoopEntrance != null;
 383
 384     // assume that ssjava loop is top-level loop in method, not nested loop
 385     Set nestedLoop = loopFinder.nestedLoops();
 386     for (Iterator loopIter = nestedLoop.iterator(); loopIter.hasNext();) {
 387       LoopFinder lf = (LoopFinder) loopIter.next();
 388       if (lf.loopEntrances().iterator().next().equals(ssjavaLoopEntrance)) {
 389         ssjavaLoop = lf;
 390       }
 391     }
 392
 393     assert ssjavaLoop != null;
 394
 395     writtenAnalysis_analyzeLoop();
 396
 397   }
 398
 399   private void writtenAnalysis_analyzeLoop() {
 400
 401     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 402     flatNodesToVisit.add(ssjavaLoopEntrance);
 403
 404     loopIncElements = (Set<FlatNode>) ssjavaLoop.loopIncElements();
 405
 406     while (!flatNodesToVisit.isEmpty()) {
 407       FlatNode fn = (FlatNode) flatNodesToVisit.iterator().next();
 408       flatNodesToVisit.remove(fn);
 409
 410       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> prev =
 411           definitelyWrittenResults.get(fn);
 412
 413       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr =
 414           new Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>>();
 415       for (int i = 0; i < fn.numPrev(); i++) {
 416         FlatNode nn = fn.getPrev(i);
 417         Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> dwIn =
 418             definitelyWrittenResults.get(nn);
 419         if (dwIn != null) {
 420           merge(curr, dwIn);
 421         }
 422       }
 423
 424       writtenAnalysis_nodeAction(fn, curr, ssjavaLoopEntrance);
 425
 426       // if a new result, schedule forward nodes for analysis
 427       if (!curr.equals(prev)) {
 428         definitelyWrittenResults.put(fn, curr);
 429
 430         for (int i = 0; i < fn.numNext(); i++) {
 431           FlatNode nn = fn.getNext(i);
 432           if (loopIncElements.contains(nn)) {
 433             flatNodesToVisit.add(nn);
 434           }
 435
 436         }
 437       }
 438     }
 439   }
 440
 441   private void writtenAnalysis_nodeAction(FlatNode fn,
 442       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr, FlatNode loopEntrance) {
 443
 444     if (fn.equals(loopEntrance)) {
 445       // it reaches loop entrance: changes all flag to true
 446       Set<NTuple<Descriptor>> keySet = curr.keySet();
 447       for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
 448         NTuple<Descriptor> key = (NTuple<Descriptor>) iterator.next();
 449         Hashtable<FlatNode, Boolean> pair = curr.get(key);
 450         if (pair != null) {
 451           Set<FlatNode> pairKeySet = pair.keySet();
 452           for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 453             FlatNode pairKey = (FlatNode) iterator2.next();
 454             pair.put(pairKey, Boolean.TRUE);
 455           }
 456         }
 457       }
 458     } else {
 459       TempDescriptor lhs;
 460       TempDescriptor rhs;
 461       FieldDescriptor fld;
 462
 463       switch (fn.kind()) {
 464       case FKind.FlatOpNode: {
 465         FlatOpNode fon = (FlatOpNode) fn;
 466         lhs = fon.getDest();
 467         rhs = fon.getLeft();
 468
 469         NTuple<Descriptor> rhsHeapPath = computePath(rhs);
 470         if (!rhs.getType().isImmutable()) {
 471           mapHeapPath.put(lhs, rhsHeapPath);
 472         } else {
 473           if (fon.getOp().getOp() == Operation.ASSIGN) {
 474             // read(rhs)
 475             readValue(fn, rhsHeapPath, curr);
 476           }
 477           // write(lhs)
 478           NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 479           removeHeapPath(curr, lhsHeapPath);
 480         }
 481       }
 482         break;
 483
 484       case FKind.FlatLiteralNode: {
 485         FlatLiteralNode fln = (FlatLiteralNode) fn;
 486         lhs = fln.getDst();
 487
 488         // write(lhs)
 489         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 490         removeHeapPath(curr, lhsHeapPath);
 491
 492       }
 493         break;
 494
 495       case FKind.FlatFieldNode:
 496       case FKind.FlatElementNode: {
 497
 498         FlatFieldNode ffn = (FlatFieldNode) fn;
 499         lhs = ffn.getDst();
 500         rhs = ffn.getSrc();
 501         fld = ffn.getField();
 502
 503         // read field
 504         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 505         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 506         fldHeapPath.add(fld);
 507
 508         if (fld.getType().isImmutable()) {
 509           readValue(fn, fldHeapPath, curr);
 510         }
 511
 512         // propagate rhs's heap path to the lhs
 513         mapHeapPath.put(lhs, fldHeapPath);
 514
 515       }
 516         break;
 517
 518       case FKind.FlatSetFieldNode:
 519       case FKind.FlatSetElementNode: {
 520
 521         FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 522         lhs = fsfn.getDst();
 523         fld = fsfn.getField();
 524
 525         // write(field)
 526         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
 527         NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 528         fldHeapPath.add(fld);
 529         removeHeapPath(curr, fldHeapPath);
 530
 531       }
 532         break;
 533
 534       case FKind.FlatCall: {
 535         FlatCall fc = (FlatCall) fn;
 536         bindHeapPathCallerArgWithCaleeParam(fc);
 537
 538         // add <hp,statement,false> in which hp is an element of
 539         // READ_bound set
 540         // of callee: callee has 'read' requirement!
 541         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 542           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 543
 544           Hashtable<FlatNode, Boolean> gen = curr.get(read);
 545           if (gen == null) {
 546             gen = new Hashtable<FlatNode, Boolean>();
 547             curr.put(read, gen);
 548           }
 549           Boolean currentStatus = gen.get(fn);
 550           if (currentStatus == null) {
 551             gen.put(fn, Boolean.FALSE);
 552           } else {
 553             checkFlag(currentStatus.booleanValue(), fn, read);
 554           }
 555         }
 556
 557         // removes <hp,statement,flag> if hp is an element of
 558         // OVERWRITE_bound
 559         // set of callee. it means that callee will overwrite it
 560         for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 561           NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 562           removeHeapPath(curr, write);
 563         }
 564       }
 565         break;
 566
 567       }
 568     }
 569
 570   }
 571
 572   private void readValue(FlatNode fn, NTuple<Descriptor> hp,
 573       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr) {
 574     Hashtable<FlatNode, Boolean> gen = curr.get(hp);
 575     if (gen == null) {
 576       gen = new Hashtable<FlatNode, Boolean>();
 577       curr.put(hp, gen);
 578     }
 579     Boolean currentStatus = gen.get(fn);
 580     if (currentStatus == null) {
 581       gen.put(fn, Boolean.FALSE);
 582     } else {
 583       checkFlag(currentStatus.booleanValue(), fn, hp);
 584     }
 585
 586   }
 587
 588   private void removeHeapPath(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 589       NTuple<Descriptor> hp) {
 590
 591     // removes all of heap path that starts with prefix 'hp'
 592     // since any reference overwrite along heap path gives overwriting side
 593     // effects on the value
 594
 595     Set<NTuple<Descriptor>> keySet = curr.keySet();
 596     for (Iterator<NTuple<Descriptor>> iter = keySet.iterator(); iter.hasNext();) {
 597       NTuple<Descriptor> key = iter.next();
 598       if (key.startsWith(hp)) {
 599         curr.put(key, new Hashtable<FlatNode, Boolean>());
 600       }
 601     }
 602
 603   }
 604
 605   private void bindHeapPathCallerArgWithCaleeParam(FlatCall fc) {
 606     // compute all possible callee set
 607     // transform all READ/OVERWRITE set from the any possible
 608     // callees to the
 609     // caller
 610
 611     calleeUnionBoundReadSet.clear();
 612     calleeIntersectBoundOverWriteSet.clear();
 613
 614     MethodDescriptor mdCallee = fc.getMethod();
 615     FlatMethod fmCallee = state.getMethodFlat(mdCallee);
 616     Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
 617     TypeDescriptor typeDesc = fc.getThis().getType();
 618     setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
 619
 620     // create mapping from arg idx to its heap paths
 621     Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
 622         new Hashtable<Integer, NTuple<Descriptor>>();
 623
 624     // arg idx is starting from 'this' arg
 625     NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
 626     if (thisHeapPath == null) {
 627       // method is called without creating new flat node representing 'this'
 628       thisHeapPath = new NTuple<Descriptor>();
 629       thisHeapPath.add(fc.getThis());
 630     }
 631
 632     mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
 633
 634     for (int i = 0; i < fc.numArgs(); i++) {
 635       TempDescriptor arg = fc.getArg(i);
 636       NTuple<Descriptor> argHeapPath = computePath(arg);
 637       mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
 638     }
 639
 640     for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
 641       MethodDescriptor callee = (MethodDescriptor) iterator.next();
 642       FlatMethod calleeFlatMethod = state.getMethodFlat(callee);
 643
 644       // binding caller's args and callee's params
 645
 646       Set<NTuple<Descriptor>> calleeReadSet = mapFlatMethodToRead.get(calleeFlatMethod);
 647       if (calleeReadSet == null) {
 648         calleeReadSet = new HashSet<NTuple<Descriptor>>();
 649         mapFlatMethodToRead.put(calleeFlatMethod, calleeReadSet);
 650       }
 651       Set<NTuple<Descriptor>> calleeOverWriteSet = mapFlatMethodToOverWrite.get(calleeFlatMethod);
 652       if (calleeOverWriteSet == null) {
 653         calleeOverWriteSet = new HashSet<NTuple<Descriptor>>();
 654         mapFlatMethodToOverWrite.put(calleeFlatMethod, calleeOverWriteSet);
 655       }
 656
 657       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
 658           new Hashtable<Integer, TempDescriptor>();
 659       for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
 660         TempDescriptor param = calleeFlatMethod.getParameter(i);
 661         mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
 662       }
 663
 664       Set<NTuple<Descriptor>> calleeBoundReadSet =
 665           bindSet(calleeReadSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 666       // union of the current read set and the current callee's
 667       // read set
 668       calleeUnionBoundReadSet.addAll(calleeBoundReadSet);
 669       Set<NTuple<Descriptor>> calleeBoundWriteSet =
 670           bindSet(calleeOverWriteSet, mapParamIdx2ParamTempDesc, mapArgIdx2CallerArgHeapPath);
 671       // intersection of the current overwrite set and the current
 672       // callee's
 673       // overwrite set
 674       merge(calleeIntersectBoundOverWriteSet, calleeBoundWriteSet);
 675     }
 676
 677   }
 678
 679   private void checkFlag(boolean booleanValue, FlatNode fn, NTuple<Descriptor> hp) {
 680     if (booleanValue) {
 681       throw new Error(
 682           "There is a variable, which is reachable through references "
 683               + hp
 684               + ", who comes back to the same read statement without being overwritten at the out-most iteration at "
 685               + methodContainingSSJavaLoop.getClassDesc().getSourceFileName() + "::"
 686               + fn.getNumLine());
 687     }
 688   }
 689
 690   private void merge(Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> curr,
 691       Hashtable<NTuple<Descriptor>, Hashtable<FlatNode, Boolean>> in) {
 692
 693     Set<NTuple<Descriptor>> inKeySet = in.keySet();
 694     for (Iterator iterator = inKeySet.iterator(); iterator.hasNext();) {
 695       NTuple<Descriptor> inKey = (NTuple<Descriptor>) iterator.next();
 696       Hashtable<FlatNode, Boolean> inPair = in.get(inKey);
 697
 698       Set<FlatNode> pairKeySet = inPair.keySet();
 699       for (Iterator iterator2 = pairKeySet.iterator(); iterator2.hasNext();) {
 700         FlatNode pairKey = (FlatNode) iterator2.next();
 701         Boolean inFlag = inPair.get(pairKey);
 702
 703         Hashtable<FlatNode, Boolean> currPair = curr.get(inKey);
 704         if (currPair == null) {
 705           currPair = new Hashtable<FlatNode, Boolean>();
 706           curr.put(inKey, currPair);
 707         }
 708
 709         Boolean currFlag = currPair.get(pairKey);
 710         // by default, flag is set by false
 711         if (currFlag == null) {
 712           currFlag = Boolean.FALSE;
 713         }
 714         currFlag = Boolean.valueOf(inFlag.booleanValue() | currFlag.booleanValue());
 715         currPair.put(pairKey, currFlag);
 716       }
 717
 718     }
 719
 720   }
 721
 722   private void methodReadOverWriteAnalysis() {
 723     // perform method READ/OVERWRITE analysis
 724     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
 725     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 726
 727     LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
 728
 729     // no need to analyze method having ssjava loop
 730     methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
 731
 732     // current descriptors to visit in fixed-point interprocedural analysis,
 733     // prioritized by
 734     // dependency in the call graph
 735     Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
 736
 737     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
 738     methodDescriptorToVistSet.addAll(sortedDescriptors);
 739
 740     while (!sortedDescriptors.isEmpty()) {
 741       MethodDescriptor md = sortedDescriptors.removeFirst();
 742       methodDescriptorsToVisitStack.add(md);
 743     }
 744
 745     // analyze scheduled methods until there are no more to visit
 746     while (!methodDescriptorsToVisitStack.isEmpty()) {
 747       // start to analyze leaf node
 748       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
 749       FlatMethod fm = state.getMethodFlat(md);
 750
 751       Set<NTuple<Descriptor>> readSet = new HashSet<NTuple<Descriptor>>();
 752       Set<NTuple<Descriptor>> overWriteSet = new HashSet<NTuple<Descriptor>>();
 753
 754       methodReadOverWrite_analyzeMethod(fm, readSet, overWriteSet);
 755
 756       Set<NTuple<Descriptor>> prevRead = mapFlatMethodToRead.get(fm);
 757       Set<NTuple<Descriptor>> prevOverWrite = mapFlatMethodToOverWrite.get(fm);
 758
 759       if (!(readSet.equals(prevRead) && overWriteSet.equals(prevOverWrite))) {
 760         mapFlatMethodToRead.put(fm, readSet);
 761         mapFlatMethodToOverWrite.put(fm, overWriteSet);
 762
 763         // results for callee changed, so enqueue dependents caller for
 764         // further
 765         // analysis
 766         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
 767         while (depsItr.hasNext()) {
 768           MethodDescriptor methodNext = depsItr.next();
 769           if (!methodDescriptorsToVisitStack.contains(methodNext)
 770               && methodDescriptorToVistSet.contains(methodNext)) {
 771             methodDescriptorsToVisitStack.add(methodNext);
 772           }
 773
 774         }
 775
 776       }
 777
 778     }
 779
 780   }
 781
 782   private void methodReadOverWrite_analyzeMethod(FlatMethod fm, Set<NTuple<Descriptor>> readSet,
 783       Set<NTuple<Descriptor>> overWriteSet) {
 784     if (state.SSJAVADEBUG) {
 785       System.out.println("Definitely written Analyzing: " + fm);
 786     }
 787
 788     // intraprocedural analysis
 789     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
 790     flatNodesToVisit.add(fm);
 791
 792     while (!flatNodesToVisit.isEmpty()) {
 793       FlatNode fn = flatNodesToVisit.iterator().next();
 794       flatNodesToVisit.remove(fn);
 795
 796       Set<NTuple<Descriptor>> curr = new HashSet<NTuple<Descriptor>>();
 797
 798       for (int i = 0; i < fn.numPrev(); i++) {
 799         FlatNode prevFn = fn.getPrev(i);
 800         Set<NTuple<Descriptor>> in = mapFlatNodeToWrittenSet.get(prevFn);
 801         if (in != null) {
 802           merge(curr, in);
 803         }
 804       }
 805
 806       methodReadOverWrite_nodeActions(fn, curr, readSet, overWriteSet);
 807
 808       Set<NTuple<Descriptor>> writtenSetPrev = mapFlatNodeToWrittenSet.get(fn);
 809       if (!curr.equals(writtenSetPrev)) {
 810         mapFlatNodeToWrittenSet.put(fn, curr);
 811         for (int i = 0; i < fn.numNext(); i++) {
 812           FlatNode nn = fn.getNext(i);
 813           flatNodesToVisit.add(nn);
 814         }
 815       }
 816
 817     }
 818
 819   }
 820
 821   private void methodReadOverWrite_nodeActions(FlatNode fn, Set<NTuple<Descriptor>> writtenSet,
 822       Set<NTuple<Descriptor>> readSet, Set<NTuple<Descriptor>> overWriteSet) {
 823     TempDescriptor lhs;
 824     TempDescriptor rhs;
 825     FieldDescriptor fld;
 826
 827     switch (fn.kind()) {
 828     case FKind.FlatMethod: {
 829
 830       // set up initial heap paths for method parameters
 831       FlatMethod fm = (FlatMethod) fn;
 832       for (int i = 0; i < fm.numParameters(); i++) {
 833         TempDescriptor param = fm.getParameter(i);
 834         NTuple<Descriptor> heapPath = new NTuple<Descriptor>();
 835         heapPath.add(param);
 836         mapHeapPath.put(param, heapPath);
 837       }
 838     }
 839       break;
 840
 841     case FKind.FlatOpNode: {
 842       FlatOpNode fon = (FlatOpNode) fn;
 843       // for a normal assign node, need to propagate lhs's heap path to
 844       // rhs
 845       if (fon.getOp().getOp() == Operation.ASSIGN) {
 846         rhs = fon.getLeft();
 847         lhs = fon.getDest();
 848
 849         NTuple<Descriptor> rhsHeapPath = mapHeapPath.get(rhs);
 850         if (rhsHeapPath != null) {
 851           mapHeapPath.put(lhs, mapHeapPath.get(rhs));
 852         }
 853
 854       }
 855     }
 856       break;
 857
 858     case FKind.FlatFieldNode:
 859     case FKind.FlatElementNode: {
 860
 861       // y=x.f;
 862
 863       FlatFieldNode ffn = (FlatFieldNode) fn;
 864       lhs = ffn.getDst();
 865       rhs = ffn.getSrc();
 866       fld = ffn.getField();
 867
 868       // set up heap path
 869       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
 870       if (srcHeapPath != null) {
 871         // if lhs srcHeapPath is null, it means that it is not reachable from
 872         // callee's parameters. so just ignore it
 873
 874         NTuple<Descriptor> readingHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
 875         readingHeapPath.add(fld);
 876         mapHeapPath.put(lhs, readingHeapPath);
 877
 878         // read (x.f)
 879         if (fld.getType().isImmutable()) {
 880           // if WT doesnot have hp(x.f), add hp(x.f) to READ
 881           if (!writtenSet.contains(readingHeapPath)) {
 882             readSet.add(readingHeapPath);
 883           }
 884         }
 885
 886         // need to kill hp(x.f) from WT
 887         writtenSet.remove(readingHeapPath);
 888       }
 889
 890     }
 891       break;
 892
 893     case FKind.FlatSetFieldNode:
 894     case FKind.FlatSetElementNode: {
 895
 896       // x.f=y;
 897       FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
 898       lhs = fsfn.getDst();
 899       fld = fsfn.getField();
 900       rhs = fsfn.getSrc();
 901
 902       // set up heap path
 903       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
 904       if (lhsHeapPath != null) {
 905         // if lhs heap path is null, it means that it is not reachable from
 906         // callee's parameters. so just ignore it
 907         NTuple<Descriptor> newHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
 908         newHeapPath.add(fld);
 909         mapHeapPath.put(fld, newHeapPath);
 910
 911         // write(x.f)
 912         // need to add hp(y) to WT
 913         writtenSet.add(newHeapPath);
 914       }
 915
 916     }
 917       break;
 918
 919     case FKind.FlatCall: {
 920
 921       FlatCall fc = (FlatCall) fn;
 922
 923       bindHeapPathCallerArgWithCaleeParam(fc);
 924
 925       // add heap path, which is an element of READ_bound set and is not
 926       // an
 927       // element of WT set, to the caller's READ set
 928       for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
 929         NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
 930         if (!writtenSet.contains(read)) {
 931           readSet.add(read);
 932         }
 933       }
 934       writtenSet.removeAll(calleeUnionBoundReadSet);
 935
 936       // add heap path, which is an element of OVERWRITE_bound set, to the
 937       // caller's WT set
 938       for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
 939         NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
 940         writtenSet.add(write);
 941       }
 942
 943     }
 944       break;
 945
 946     case FKind.FlatExit: {
 947       // merge the current written set with OVERWRITE set
 948       merge(overWriteSet, writtenSet);
 949     }
 950       break;
 951
 952     }
 953
 954   }
 955
 956   private void mergeSharedAnaylsis(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
 957       Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in) {
 958
 959   }
 960
 961   private void merge(Set<NTuple<Descriptor>> curr, Set<NTuple<Descriptor>> in) {
 962     if (curr.isEmpty()) {
 963       // WrittenSet has a special initial value which covers all possible
 964       // elements
 965       // For the first time of intersection, we can take all previous set
 966       curr.addAll(in);
 967     } else {
 968       // otherwise, current set is the intersection of the two sets
 969       curr.retainAll(in);
 970     }
 971
 972   }
 973
 974   // combine two heap path
 975   private NTuple<Descriptor> combine(NTuple<Descriptor> callerIn, NTuple<Descriptor> calleeIn) {
 976     NTuple<Descriptor> combined = new NTuple<Descriptor>();
 977
 978     for (int i = 0; i < callerIn.size(); i++) {
 979       combined.add(callerIn.get(i));
 980     }
 981
 982     // the first element of callee's heap path represents parameter
 983     // so we skip the first one since it is already added from caller's heap
 984     // path
 985     for (int i = 1; i < calleeIn.size(); i++) {
 986       combined.add(calleeIn.get(i));
 987     }
 988
 989     return combined;
 990   }
 991
 992   private Set<NTuple<Descriptor>> bindSet(Set<NTuple<Descriptor>> calleeSet,
 993       Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc,
 994       Hashtable<Integer, NTuple<Descriptor>> mapCallerArgIdx2HeapPath) {
 995
 996     Set<NTuple<Descriptor>> boundedCalleeSet = new HashSet<NTuple<Descriptor>>();
 997
 998     Set<Integer> keySet = mapCallerArgIdx2HeapPath.keySet();
 999     for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
1000       Integer idx = (Integer) iterator.next();
1001
1002       NTuple<Descriptor> callerArgHeapPath = mapCallerArgIdx2HeapPath.get(idx);
1003       TempDescriptor calleeParam = mapParamIdx2ParamTempDesc.get(idx);
1004
1005       for (Iterator iterator2 = calleeSet.iterator(); iterator2.hasNext();) {
1006         NTuple<Descriptor> element = (NTuple<Descriptor>) iterator2.next();
1007         if (element.startsWith(calleeParam)) {
1008           NTuple<Descriptor> boundElement = combine(callerArgHeapPath, element);
1009           boundedCalleeSet.add(boundElement);
1010         }
1011
1012       }
1013
1014     }
1015     return boundedCalleeSet;
1016
1017   }
1018
1019   // Borrowed it from disjoint analysis
1020   private LinkedList<MethodDescriptor> topologicalSort(Set<MethodDescriptor> toSort) {
1021
1022     Set<MethodDescriptor> discovered = new HashSet<MethodDescriptor>();
1023
1024     LinkedList<MethodDescriptor> sorted = new LinkedList<MethodDescriptor>();
1025
1026     Iterator<MethodDescriptor> itr = toSort.iterator();
1027     while (itr.hasNext()) {
1028       MethodDescriptor d = itr.next();
1029
1030       if (!discovered.contains(d)) {
1031         dfsVisit(d, toSort, sorted, discovered);
1032       }
1033     }
1034
1035     return sorted;
1036   }
1037
1038   // While we're doing DFS on call graph, remember
1039   // dependencies for efficient queuing of methods
1040   // during interprocedural analysis:
1041   //
1042   // a dependent of a method decriptor d for this analysis is:
1043   // 1) a method or task that invokes d
1044   // 2) in the descriptorsToAnalyze set
1045   private void dfsVisit(MethodDescriptor md, Set<MethodDescriptor> toSort,
1046       LinkedList<MethodDescriptor> sorted, Set<MethodDescriptor> discovered) {
1047
1048     discovered.add(md);
1049
1050     // otherwise call graph guides DFS
1051     Iterator itr = callGraph.getCallerSet(md).iterator();
1052     while (itr.hasNext()) {
1053       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
1054
1055       // only consider callers in the original set to analyze
1056       if (!toSort.contains(dCaller)) {
1057         continue;
1058       }
1059
1060       if (!discovered.contains(dCaller)) {
1061         addDependent(md, // callee
1062             dCaller // caller
1063         );
1064
1065         dfsVisit(dCaller, toSort, sorted, discovered);
1066       }
1067     }
1068
1069     // for leaf-nodes last now!
1070     sorted.addLast(md);
1071   }
1072
1073   // a dependent of a method decriptor d for this analysis is:
1074   // 1) a method or task that invokes d
1075   // 2) in the descriptorsToAnalyze set
1076   private void addDependent(MethodDescriptor callee, MethodDescriptor caller) {
1077     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1078     if (deps == null) {
1079       deps = new HashSet<MethodDescriptor>();
1080     }
1081     deps.add(caller);
1082     mapDescriptorToSetDependents.put(callee, deps);
1083   }
1084
1085   private Set<MethodDescriptor> getDependents(MethodDescriptor callee) {
1086     Set<MethodDescriptor> deps = mapDescriptorToSetDependents.get(callee);
1087     if (deps == null) {
1088       deps = new HashSet<MethodDescriptor>();
1089       mapDescriptorToSetDependents.put(callee, deps);
1090     }
1091     return deps;
1092   }
1093
1094   private NTuple<Descriptor> computePath(TempDescriptor td) {
1095     // generate proper path fot input td
1096     // if td is local variable, it just generate one element tuple path
1097     if (mapHeapPath.containsKey(td)) {
1098       return mapHeapPath.get(td);
1099     } else {
1100       NTuple<Descriptor> path = new NTuple<Descriptor>();
1101       path.add(td);
1102       return path;
1103     }
1104   }
1105
1106 }