X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FAnalysis%2FSSJava%2FDefinitelyWrittenCheck.java;h=2536171de0ec1049f11cba86a0988f63991ca57f;hb=7ce7b388724430b052de7ce549cc724e9e7cdaec;hp=7cc86f16fda8875a34d6fe8914889b069babe45f;hpb=484e9bd327c7fe5d5cf96bbead147c80aaef6380;p=IRC.git

diff --git a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java
index 7cc86f16..2536171d 100644
--- a/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java
+++ b/Robust/src/Analysis/SSJava/DefinitelyWrittenCheck.java
@@ -6,7 +6,6 @@ import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.Set;
 import java.util.Stack;
-import java.util.Vector;
 
 import Analysis.CallGraph.CallGraph;
 import Analysis.Loops.LoopFinder;
@@ -18,13 +17,17 @@ import IR.State;
 import IR.TypeDescriptor;
 import IR.Flat.FKind;
 import IR.Flat.FlatCall;
+import IR.Flat.FlatElementNode;
 import IR.Flat.FlatFieldNode;
 import IR.Flat.FlatLiteralNode;
 import IR.Flat.FlatMethod;
 import IR.Flat.FlatNode;
 import IR.Flat.FlatOpNode;
+import IR.Flat.FlatSetElementNode;
 import IR.Flat.FlatSetFieldNode;
 import IR.Flat.TempDescriptor;
+import IR.Tree.Modifiers;
+import Util.Pair;
 
 public class DefinitelyWrittenCheck {
 
@@ -63,14 +66,31 @@ public class DefinitelyWrittenCheck {
   // maps a method descriptor to its current summary during the analysis
   // then analysis reaches fixed-point, this mapping will have the final summary
   // for each method descriptor
-  private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToCompleteClearingSummary;
+  private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToCompleteClearingSummary;
 
   // maps a method descriptor to the merged incoming caller's current
   // overwritten status
-  private Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapMethodDescriptorToInitialClearingSummary;
+  private Hashtable<MethodDescriptor, ClearingSummary> mapMethodDescriptorToInitialClearingSummary;
 
   // maps a flat node to current partial results
-  private Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>> mapFlatNodeToClearingSummary;
+  private Hashtable<FlatNode, ClearingSummary> mapFlatNodeToClearingSummary;
+
+  // maps shared location to the set of descriptors which belong to the shared
+  // location
+  private Hashtable<Location, Set<Descriptor>> mapSharedLocation2DescriptorSet;
+
+  // keep current descriptors to visit in fixed-point interprocedural analysis,
+  private Stack<MethodDescriptor> methodDescriptorsToVisitStack;
+
+  // when analyzing flatcall, need to re-schedule set of callee
+  private Set<MethodDescriptor> calleesToEnqueue;
+
+  public static final String arrayElementFieldName = "___element_";
+  static protected Hashtable<TypeDescriptor, FieldDescriptor> mapTypeToArrayField;
+
+  private Set<ClearingSummary> possibleCalleeCompleteSummarySetToCaller;
+
+  private LinkedList<MethodDescriptor> sortedDescriptors;
 
   private FlatNode ssjavaLoopEntrance;
   private LoopFinder ssjavaLoop;
@@ -96,11 +116,14 @@ public class DefinitelyWrittenCheck {
     this.calleeIntersectBoundOverWriteSet = new HashSet<NTuple<Descriptor>>();
 
     this.mapMethodDescriptorToCompleteClearingSummary =
-        new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
+        new Hashtable<MethodDescriptor, ClearingSummary>();
     this.mapMethodDescriptorToInitialClearingSummary =
-        new Hashtable<MethodDescriptor, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
-    this.mapFlatNodeToClearingSummary =
-        new Hashtable<FlatNode, Hashtable<NTuple<Descriptor>, Set<SharedLocState>>>();
+        new Hashtable<MethodDescriptor, ClearingSummary>();
+    this.mapSharedLocation2DescriptorSet = new Hashtable<Location, Set<Descriptor>>();
+    this.methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
+    this.calleesToEnqueue = new HashSet<MethodDescriptor>();
+    this.possibleCalleeCompleteSummarySetToCaller = new HashSet<ClearingSummary>();
+    this.mapTypeToArrayField = new Hashtable<TypeDescriptor, FieldDescriptor>();
     this.LOCAL = new TempDescriptor("LOCAL");
   }
 
@@ -109,67 +132,99 @@ public class DefinitelyWrittenCheck {
       methodReadOverWriteAnalysis();
       writtenAnalyis();
       sharedLocationAnalysis();
+      checkSharedLocationResult();
+    }
+  }
+
+  private void checkSharedLocationResult() {
+
+    // mapping of method containing ssjava loop has the final result of
+    // shared location analysis
+    ClearingSummary result =
+        mapMethodDescriptorToCompleteClearingSummary.get(sortedDescriptors.peekFirst());
+
+
+    Set<NTuple<Descriptor>> hpKeySet = result.keySet();
+    for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
+      NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+      SharedStatus state = result.get(hpKey);
+      Set<Location> locKeySet = state.getLocationSet();
+      for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
+        Location locKey = (Location) iterator2.next();
+        if (!state.getFlag(locKey)) {
+          throw new Error(
+              "Some concrete locations of the shared abstract location are not cleared at the same time.");
+        }
+      }
     }
+
   }
 
   private void sharedLocationAnalysis() {
     // verify that all concrete locations of shared location are cleared out at
     // the same time once per the out-most loop
 
-    Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
-    methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
+    computeReadSharedDescriptorSet();
 
-    LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
+    methodDescriptorsToVisitStack.clear();
 
-    Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
-    Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
-    methodDescriptorToVistSet.addAll(sortedDescriptors);
-
-    while (!sortedDescriptors.isEmpty()) {
-      MethodDescriptor md = sortedDescriptors.removeLast();
-      methodDescriptorsToVisitStack.add(md);
-    }
+    methodDescriptorsToVisitStack.add(sortedDescriptors.peekFirst());
 
     // analyze scheduled methods until there are no more to visit
     while (!methodDescriptorsToVisitStack.isEmpty()) {
       MethodDescriptor md = methodDescriptorsToVisitStack.pop();
-      FlatMethod fm = state.getMethodFlat(md);
 
-      sharedLocation_analyzeMethod(fm, (md.equals(methodContainingSSJavaLoop)));
+      ClearingSummary completeSummary =
+          sharedLocation_analyzeMethod(md, (md.equals(methodContainingSSJavaLoop)));
 
-      if (true) {
+      ClearingSummary prevCompleteSummary = mapMethodDescriptorToCompleteClearingSummary.get(md);
+
+      if (!completeSummary.equals(prevCompleteSummary)) {
+
+        mapMethodDescriptorToCompleteClearingSummary.put(md, completeSummary);
 
         // results for callee changed, so enqueue dependents caller for
         // further analysis
         Iterator<MethodDescriptor> depsItr = getDependents(md).iterator();
         while (depsItr.hasNext()) {
           MethodDescriptor methodNext = depsItr.next();
-          if (!methodDescriptorsToVisitStack.contains(methodNext)
-              && methodDescriptorToVistSet.contains(methodNext)) {
+          if (!methodDescriptorsToVisitStack.contains(methodNext)) {
             methodDescriptorsToVisitStack.add(methodNext);
           }
+        }
 
+        // if there is set of callee to be analyzed,
+        // add this set into the top of stack
+        Iterator<MethodDescriptor> calleeIter = calleesToEnqueue.iterator();
+        while (calleeIter.hasNext()) {
+          MethodDescriptor mdNext = calleeIter.next();
+          if (!methodDescriptorsToVisitStack.contains(mdNext)) {
+            methodDescriptorsToVisitStack.add(mdNext);
+          }
         }
+        calleesToEnqueue.clear();
 
       }
 
     }
 
-    Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
-    flatNodesToVisit.add(ssjavaLoopEntrance);
-
   }
 
-  private void sharedLocation_analyzeMethod(FlatMethod fm, boolean onlyVisitSSJavaLoop) {
+  private ClearingSummary sharedLocation_analyzeMethod(MethodDescriptor md,
+      boolean onlyVisitSSJavaLoop) {
 
     if (state.SSJAVADEBUG) {
-      System.out.println("Definitely written for shared locations Analyzing: " + fm + " "
+      System.out.println("Definitely written for shared locations Analyzing: " + md + " "
           + onlyVisitSSJavaLoop);
     }
 
+    FlatMethod fm = state.getMethodFlat(md);
+
     // intraprocedural analysis
     Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
-    Set<FlatNode> visited = new HashSet<FlatNode>();
+
+    // start a new mapping of partial results for each flat node
+    mapFlatNodeToClearingSummary = new Hashtable<FlatNode, ClearingSummary>();
 
     if (onlyVisitSSJavaLoop) {
       flatNodesToVisit.add(ssjavaLoopEntrance);
@@ -177,26 +232,26 @@ public class DefinitelyWrittenCheck {
       flatNodesToVisit.add(fm);
     }
 
+    Set<FlatNode> returnNodeSet = new HashSet<FlatNode>();
+
     while (!flatNodesToVisit.isEmpty()) {
       FlatNode fn = flatNodesToVisit.iterator().next();
       flatNodesToVisit.remove(fn);
 
-      Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr =
-          new Hashtable<NTuple<Descriptor>, Set<SharedLocState>>();
+      ClearingSummary curr = new ClearingSummary();
 
+      Set<ClearingSummary> prevSet = new HashSet<ClearingSummary>();
       for (int i = 0; i < fn.numPrev(); i++) {
         FlatNode prevFn = fn.getPrev(i);
-        Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in =
-            mapFlatNodeToClearingSummary.get(prevFn);
+        ClearingSummary in = mapFlatNodeToClearingSummary.get(prevFn);
         if (in != null) {
-          mergeSharedAnaylsis(curr, in);
+          prevSet.add(in);
         }
       }
+      mergeSharedLocationAnaylsis(curr, prevSet);
 
-      sharedLocation_nodeActions(fn, curr, onlyVisitSSJavaLoop);
-
-      Hashtable<NTuple<Descriptor>, Set<SharedLocState>> clearingPrev =
-          mapFlatNodeToClearingSummary.get(fn);
+      sharedLocation_nodeActions(md, fn, curr, returnNodeSet, onlyVisitSSJavaLoop);
+      ClearingSummary clearingPrev = mapFlatNodeToClearingSummary.get(fn);
 
       if (!curr.equals(clearingPrev)) {
         mapFlatNodeToClearingSummary.put(fn, curr);
@@ -213,16 +268,55 @@ public class DefinitelyWrittenCheck {
 
     }
 
+    ClearingSummary completeSummary = new ClearingSummary();
+    Set<ClearingSummary> summarySet = new HashSet<ClearingSummary>();
+
+    if (onlyVisitSSJavaLoop) {
+      // when analyzing ssjava loop,
+      // complete summary is merging of all previous nodes of ssjava loop
+      // entrance
+      for (int i = 0; i < ssjavaLoopEntrance.numPrev(); i++) {
+        ClearingSummary frnSummary =
+            mapFlatNodeToClearingSummary.get(ssjavaLoopEntrance.getPrev(i));
+        if (frnSummary != null) {
+          summarySet.add(frnSummary);
+        }
+      }
+    } else {
+      // merging all exit node summary into the complete summary
+      if (!returnNodeSet.isEmpty()) {
+        for (Iterator iterator = returnNodeSet.iterator(); iterator.hasNext();) {
+          FlatNode frn = (FlatNode) iterator.next();
+          ClearingSummary frnSummary = mapFlatNodeToClearingSummary.get(frn);
+          summarySet.add(frnSummary);
+        }
+      }
+    }
+    mergeSharedLocationAnaylsis(completeSummary, summarySet);
+    return completeSummary;
   }
 
-  private void sharedLocation_nodeActions(FlatNode fn,
-      Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr, boolean isSSJavaLoop) {
+  private void sharedLocation_nodeActions(MethodDescriptor caller, FlatNode fn,
+      ClearingSummary curr, Set<FlatNode> returnNodeSet, boolean isSSJavaLoop) {
 
     TempDescriptor lhs;
     TempDescriptor rhs;
     FieldDescriptor fld;
     switch (fn.kind()) {
 
+    case FKind.FlatMethod: {
+      FlatMethod fm = (FlatMethod) fn;
+
+      ClearingSummary summaryFromCaller =
+          mapMethodDescriptorToInitialClearingSummary.get(fm.getMethod());
+
+      Set<ClearingSummary> inSet = new HashSet<ClearingSummary>();
+      inSet.add(summaryFromCaller);
+      mergeSharedLocationAnaylsis(curr, inSet);
+
+    }
+      break;
+
     case FKind.FlatOpNode: {
       FlatOpNode fon = (FlatOpNode) fn;
       lhs = fon.getDest();
@@ -235,8 +329,10 @@ public class DefinitelyWrittenCheck {
           NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
           rhsHeapPath.add(LOCAL);
           lhsHeapPath.add(LOCAL);
-          readLocation(curr, rhsHeapPath, rhs);
-          writeLocation(curr, lhsHeapPath, lhs);
+          if (!lhs.getSymbol().startsWith("neverused")) {
+            readLocation(curr, rhsHeapPath, rhs);
+            writeLocation(curr, lhsHeapPath, lhs);
+          }
         }
       }
 
@@ -254,15 +350,11 @@ public class DefinitelyWrittenCheck {
       // read field
       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
-      fldHeapPath.add(fld);
 
       if (fld.getType().isImmutable()) {
-        // readLocation(f curr);
+        readLocation(curr, fldHeapPath, fld);
       }
 
-      // propagate rhs's heap path to the lhs
-      mapHeapPath.put(lhs, fldHeapPath);
-
     }
       break;
 
@@ -276,78 +368,386 @@ public class DefinitelyWrittenCheck {
       // write(field)
       NTuple<Descriptor> lhsHeapPath = computePath(lhs);
       NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
-      // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
+      if (fld.getType().isImmutable()) {
+        writeLocation(curr, fldHeapPath, fld);
+      } else {
+        // updates reference field case:
+        // 2. if there exists a tuple t in sharing summary that starts with
+        // hp(x) then, set flag of tuple t to 'true'
+        fldHeapPath.add(fld);
+        Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
+        for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
+          NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+          if (hpKey.startsWith(fldHeapPath)) {
+            curr.get(hpKey).updateFlag(true);
+          }
+        }
+      }
 
     }
       break;
 
     case FKind.FlatCall: {
 
+      FlatCall fc = (FlatCall) fn;
+
+      // find out the set of callees
+      MethodDescriptor mdCallee = fc.getMethod();
+      FlatMethod fmCallee = state.getMethodFlat(mdCallee);
+      Set<MethodDescriptor> setPossibleCallees = new HashSet<MethodDescriptor>();
+      TypeDescriptor typeDesc = fc.getThis().getType();
+      setPossibleCallees.addAll(callGraph.getMethods(mdCallee, typeDesc));
+
+      possibleCalleeCompleteSummarySetToCaller.clear();
+
+      for (Iterator iterator = setPossibleCallees.iterator(); iterator.hasNext();) {
+        MethodDescriptor mdPossibleCallee = (MethodDescriptor) iterator.next();
+        FlatMethod calleeFlatMethod = state.getMethodFlat(mdPossibleCallee);
+
+        addDependent(mdPossibleCallee, // callee
+            caller); // caller
+
+        calleesToEnqueue.add(mdPossibleCallee);
+
+        // updates possible callee's initial summary using caller's current
+        // writing status
+        ClearingSummary prevCalleeInitSummary =
+            mapMethodDescriptorToInitialClearingSummary.get(mdPossibleCallee);
+
+        ClearingSummary calleeInitSummary =
+            bindHeapPathOfCalleeCallerEffects(fc, calleeFlatMethod, curr);
+
+        // if changes, update the init summary
+        // and reschedule the callee for analysis
+        if (!calleeInitSummary.equals(prevCalleeInitSummary)) {
+
+          if (!methodDescriptorsToVisitStack.contains(mdPossibleCallee)) {
+            methodDescriptorsToVisitStack.add(mdPossibleCallee);
+          }
+          mapMethodDescriptorToInitialClearingSummary.put(mdPossibleCallee, calleeInitSummary);
+        }
+
+      }
+
+      // contribute callee's writing effects to the caller
+      mergeSharedLocationAnaylsis(curr, possibleCalleeCompleteSummarySetToCaller);
+
+    }
+      break;
+
+    case FKind.FlatReturnNode: {
+      returnNodeSet.add(fn);
     }
       break;
+
     }
 
   }
 
-  private Location getLocation(Descriptor d) {
+  private ClearingSummary bindHeapPathOfCalleeCallerEffects(FlatCall fc,
+      FlatMethod calleeFlatMethod, ClearingSummary curr) {
 
-    if (d instanceof FieldDescriptor) {
-      return (Location) ((FieldDescriptor) d).getType().getExtension();
+    ClearingSummary boundSet = new ClearingSummary();
+
+    // create mapping from arg idx to its heap paths
+    Hashtable<Integer, NTuple<Descriptor>> mapArgIdx2CallerArgHeapPath =
+        new Hashtable<Integer, NTuple<Descriptor>>();
+
+    // arg idx is starting from 'this' arg
+    NTuple<Descriptor> thisHeapPath = mapHeapPath.get(fc.getThis());
+    if (thisHeapPath == null) {
+      // method is called without creating new flat node representing 'this'
+      thisHeapPath = new NTuple<Descriptor>();
+      thisHeapPath.add(fc.getThis());
+    }
+
+    mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(0), thisHeapPath);
+
+    for (int i = 0; i < fc.numArgs(); i++) {
+      TempDescriptor arg = fc.getArg(i);
+      NTuple<Descriptor> argHeapPath = computePath(arg);
+      mapArgIdx2CallerArgHeapPath.put(Integer.valueOf(i + 1), argHeapPath);
+    }
+
+    Hashtable<Integer, TempDescriptor> mapParamIdx2ParamTempDesc =
+        new Hashtable<Integer, TempDescriptor>();
+    for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
+      TempDescriptor param = calleeFlatMethod.getParameter(i);
+      mapParamIdx2ParamTempDesc.put(Integer.valueOf(i), param);
+    }
+
+    // binding caller's writing effects to callee's params
+    for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
+      NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
+      TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
+
+      // iterate over caller's writing effect set
+      Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
+      for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
+        NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+        // current element is reachable caller's arg
+        // so need to bind it to the caller's side and add it to the callee's
+        // init summary
+        if (hpKey.startsWith(argHeapPath)) {
+          NTuple<Descriptor> boundHeapPath = replace(hpKey, argHeapPath, calleeParamHeapPath);
+          boundSet.put(boundHeapPath, curr.get(hpKey).clone());
+        }
+
+      }
+
+    }
+
+    // contribute callee's complete summary into the caller's current summary
+    ClearingSummary calleeCompleteSummary =
+        mapMethodDescriptorToCompleteClearingSummary.get(calleeFlatMethod.getMethod());
+
+    if (calleeCompleteSummary != null) {
+      ClearingSummary boundCalleeEfffects = new ClearingSummary();
+      for (int i = 0; i < calleeFlatMethod.numParameters(); i++) {
+        NTuple<Descriptor> argHeapPath = mapArgIdx2CallerArgHeapPath.get(Integer.valueOf(i));
+        TempDescriptor calleeParamHeapPath = mapParamIdx2ParamTempDesc.get(Integer.valueOf(i));
+
+        // iterate over callee's writing effect set
+        Set<NTuple<Descriptor>> hpKeySet = calleeCompleteSummary.keySet();
+        for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
+          NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+          // current element is reachable caller's arg
+          // so need to bind it to the caller's side and add it to the callee's
+          // init summary
+          if (hpKey.startsWith(calleeParamHeapPath)) {
+
+            NTuple<Descriptor> boundHeapPathForCaller = replace(hpKey, argHeapPath);
+
+            boundCalleeEfffects.put(boundHeapPathForCaller, calleeCompleteSummary.get(hpKey)
+                .clone());
+
+          }
+        }
+      }
+      possibleCalleeCompleteSummarySetToCaller.add(boundCalleeEfffects);
+    }
+
+    return boundSet;
+  }
+
+  private NTuple<Descriptor> replace(NTuple<Descriptor> hpKey, NTuple<Descriptor> argHeapPath) {
+
+    // replace the head of heap path with caller's arg path
+    // for example, heap path 'param.a.b' in callee's side will be replaced with
+    // (corresponding arg heap path).a.b for caller's side
+
+    NTuple<Descriptor> bound = new NTuple<Descriptor>();
+
+    for (int i = 0; i < argHeapPath.size(); i++) {
+      bound.add(argHeapPath.get(i));
+    }
+
+    for (int i = 1; i < hpKey.size(); i++) {
+      bound.add(hpKey.get(i));
+    }
+
+    return bound;
+  }
+
+  private NTuple<Descriptor> replace(NTuple<Descriptor> effectHeapPath,
+      NTuple<Descriptor> argHeapPath, TempDescriptor calleeParamHeapPath) {
+    // replace the head of caller's heap path with callee's param heap path
+
+    NTuple<Descriptor> boundHeapPath = new NTuple<Descriptor>();
+    boundHeapPath.add(calleeParamHeapPath);
+
+    for (int i = argHeapPath.size(); i < effectHeapPath.size(); i++) {
+      boundHeapPath.add(effectHeapPath.get(i));
+    }
+
+    return boundHeapPath;
+  }
+
+  private void computeReadSharedDescriptorSet() {
+    Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
+    methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
+
+    for (Iterator iterator = methodDescriptorsToAnalyze.iterator(); iterator.hasNext();) {
+      MethodDescriptor md = (MethodDescriptor) iterator.next();
+      FlatMethod fm = state.getMethodFlat(md);
+      computeReadSharedDescriptorSet_analyzeMethod(fm, md.equals(methodContainingSSJavaLoop));
+    }
+
+  }
+
+  private void computeReadSharedDescriptorSet_analyzeMethod(FlatMethod fm,
+      boolean onlyVisitSSJavaLoop) {
+
+    Set<FlatNode> flatNodesToVisit = new HashSet<FlatNode>();
+    Set<FlatNode> visited = new HashSet<FlatNode>();
+
+    if (onlyVisitSSJavaLoop) {
+      flatNodesToVisit.add(ssjavaLoopEntrance);
     } else {
-      assert d instanceof TempDescriptor;
-      CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
-      return comp.get(comp.getSize() - 1);
+      flatNodesToVisit.add(fm);
+    }
+
+    while (!flatNodesToVisit.isEmpty()) {
+      FlatNode fn = flatNodesToVisit.iterator().next();
+      flatNodesToVisit.remove(fn);
+      visited.add(fn);
+
+      computeReadSharedDescriptorSet_nodeActions(fn, onlyVisitSSJavaLoop);
+
+      for (int i = 0; i < fn.numNext(); i++) {
+        FlatNode nn = fn.getNext(i);
+        if (!visited.contains(nn)) {
+          if (!onlyVisitSSJavaLoop || (onlyVisitSSJavaLoop && loopIncElements.contains(nn))) {
+            flatNodesToVisit.add(nn);
+          }
+        }
+      }
+
     }
 
   }
 
-  private SharedLocState getSharedLocState(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
-      NTuple<Descriptor> hp, Location loc) {
+  private void computeReadSharedDescriptorSet_nodeActions(FlatNode fn, boolean isSSJavaLoop) {
+
+    TempDescriptor lhs;
+    TempDescriptor rhs;
+    FieldDescriptor fld;
+
+    switch (fn.kind()) {
+    case FKind.FlatOpNode: {
+      FlatOpNode fon = (FlatOpNode) fn;
+      lhs = fon.getDest();
+      rhs = fon.getLeft();
+
+      if (fon.getOp().getOp() == Operation.ASSIGN) {
+        if (rhs.getType().isImmutable() && isSSJavaLoop && (!rhs.getSymbol().startsWith("srctmp"))) {
+          // in ssjavaloop, we need to take care about reading local variables!
+          NTuple<Descriptor> rhsHeapPath = new NTuple<Descriptor>();
+          NTuple<Descriptor> lhsHeapPath = new NTuple<Descriptor>();
+          rhsHeapPath.add(LOCAL);
+          addReadDescriptor(rhsHeapPath, rhs);
+        }
+      }
 
-    Set<SharedLocState> set = curr.get(hp);
-    if (set == null) {
-      set = new HashSet<SharedLocState>();
-      curr.put(hp, set);
     }
+      break;
 
-    SharedLocState state = null;
-    for (Iterator iterator = set.iterator(); iterator.hasNext();) {
-      SharedLocState e = (SharedLocState) iterator.next();
-      if (e.getLoc().equals(loc)) {
-        state = e;
-        break;
+    case FKind.FlatFieldNode:
+    case FKind.FlatElementNode: {
+
+      FlatFieldNode ffn = (FlatFieldNode) fn;
+      lhs = ffn.getDst();
+      rhs = ffn.getSrc();
+      fld = ffn.getField();
+
+      // read field
+      NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
+      NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(srcHeapPath.getList());
+      // fldHeapPath.add(fld);
+
+      if (fld.getType().isImmutable()) {
+        addReadDescriptor(fldHeapPath, fld);
       }
+
+      // propagate rhs's heap path to the lhs
+      mapHeapPath.put(lhs, fldHeapPath);
+
     }
+      break;
+
+    case FKind.FlatSetFieldNode:
+    case FKind.FlatSetElementNode: {
+
+      FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
+      lhs = fsfn.getDst();
+      fld = fsfn.getField();
+
+      // write(field)
+      NTuple<Descriptor> lhsHeapPath = computePath(lhs);
+      NTuple<Descriptor> fldHeapPath = new NTuple<Descriptor>(lhsHeapPath.getList());
+      // writeLocation(curr, fldHeapPath, fld, getLocation(fld));
 
-    if (state == null) {
-      state = new SharedLocState(loc);
-      set.add(state);
     }
+      break;
 
-    return state;
+    }
   }
 
-  private void writeLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
-      NTuple<Descriptor> hp, Descriptor d) {
+  private boolean hasReadingEffectOnSharedLocation(NTuple<Descriptor> hp, Location loc, Descriptor d) {
+    if (!mapSharedLocation2DescriptorSet.containsKey(loc)) {
+      return false;
+    } else {
+      return mapSharedLocation2DescriptorSet.get(loc).contains(d);
+    }
+  }
+
+  private void addReadDescriptor(NTuple<Descriptor> hp, Descriptor d) {
 
     Location loc = getLocation(d);
-    if (ssjava.isSharedLocation(loc)) {
-      SharedLocState state = getSharedLocState(curr, hp, loc);
-      state.addVar(d);
+
+    if (loc != null && ssjava.isSharedLocation(loc)) {
+
+      Set<Descriptor> set = mapSharedLocation2DescriptorSet.get(loc);
+      if (set == null) {
+        set = new HashSet<Descriptor>();
+        mapSharedLocation2DescriptorSet.put(loc, set);
+      }
+      set.add(d);
     }
+
   }
 
-  private void readLocation(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
-      NTuple<Descriptor> hp, Descriptor d) {
-    // remove reading var x from written set
+  private Location getLocation(Descriptor d) {
 
+    if (d instanceof FieldDescriptor) {
+      return (Location) ((FieldDescriptor) d).getType().getExtension();
+    } else {
+      assert d instanceof TempDescriptor;
+      CompositeLocation comp = (CompositeLocation) ((TempDescriptor) d).getType().getExtension();
+      if (comp == null) {
+        return null;
+      } else {
+        return comp.get(comp.getSize() - 1);
+      }
+    }
+
+  }
+
+  private void writeLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
     Location loc = getLocation(d);
-    if (ssjava.isSharedLocation(loc)) {
-      SharedLocState state = getSharedLocState(curr, hp, loc);
-      state.removeVar(d);
+    if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
+
+      // 1. add field x to the clearing set
+      SharedStatus state = getState(curr, hp);
+      state.addVar(loc, d);
+
+      // 3. if the set v contains all of variables belonging to the shared
+      // location, set flag to true
+      Set<Descriptor> sharedVarSet = mapSharedLocation2DescriptorSet.get(loc);
+      if (state.getVarSet(loc).containsAll(sharedVarSet)) {
+        state.updateFlag(loc, true);
+      }
     }
   }
 
+  private void readLocation(ClearingSummary curr, NTuple<Descriptor> hp, Descriptor d) {
+    // remove reading var x from written set
+    Location loc = getLocation(d);
+    if (loc != null && hasReadingEffectOnSharedLocation(hp, loc, d)) {
+      SharedStatus state = getState(curr, hp);
+      state.removeVar(loc, d);
+    }
+  }
+
+  private SharedStatus getState(ClearingSummary curr, NTuple<Descriptor> hp) {
+    SharedStatus state = curr.get(hp);
+    if (state == null) {
+      state = new SharedStatus();
+      curr.put(hp, state);
+    }
+    return state;
+  }
+
   private void writtenAnalyis() {
     // perform second stage analysis: intraprocedural analysis ensure that
     // all
@@ -495,10 +895,23 @@ public class DefinitelyWrittenCheck {
       case FKind.FlatFieldNode:
       case FKind.FlatElementNode: {
 
-        FlatFieldNode ffn = (FlatFieldNode) fn;
-        lhs = ffn.getDst();
-        rhs = ffn.getSrc();
-        fld = ffn.getField();
+        if (fn.kind() == FKind.FlatFieldNode) {
+          FlatFieldNode ffn = (FlatFieldNode) fn;
+          lhs = ffn.getDst();
+          rhs = ffn.getSrc();
+          fld = ffn.getField();
+        } else {
+          FlatElementNode fen = (FlatElementNode) fn;
+          lhs = fen.getDst();
+          rhs = fen.getSrc();
+          TypeDescriptor td = rhs.getType().dereference();
+          fld = getArrayField(td);
+        }
+
+        if (fld.isFinal() /* && fld.isStatic() */) {
+          // if field is final and static, no need to check
+          break;
+        }
 
         // read field
         NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
@@ -518,9 +931,17 @@ public class DefinitelyWrittenCheck {
       case FKind.FlatSetFieldNode:
       case FKind.FlatSetElementNode: {
 
-        FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
-        lhs = fsfn.getDst();
-        fld = fsfn.getField();
+        if (fn.kind() == FKind.FlatSetFieldNode) {
+          FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
+          lhs = fsfn.getDst();
+          fld = fsfn.getField();
+        } else {
+          FlatSetElementNode fsen = (FlatSetElementNode) fn;
+          lhs = fsen.getDst();
+          rhs = fsen.getSrc();
+          TypeDescriptor td = lhs.getType().dereference();
+          fld = getArrayField(td);
+        }
 
         // write(field)
         NTuple<Descriptor> lhsHeapPath = computePath(lhs);
@@ -534,13 +955,13 @@ public class DefinitelyWrittenCheck {
       case FKind.FlatCall: {
         FlatCall fc = (FlatCall) fn;
         bindHeapPathCallerArgWithCaleeParam(fc);
-
         // add <hp,statement,false> in which hp is an element of
         // READ_bound set
         // of callee: callee has 'read' requirement!
+
+        
         for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
           NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
-
           Hashtable<FlatNode, Boolean> gen = curr.get(read);
           if (gen == null) {
             gen = new Hashtable<FlatNode, Boolean>();
@@ -607,7 +1028,6 @@ public class DefinitelyWrittenCheck {
     // transform all READ/OVERWRITE set from the any possible
     // callees to the
     // caller
-
     calleeUnionBoundReadSet.clear();
     calleeIntersectBoundOverWriteSet.clear();
 
@@ -724,21 +1144,25 @@ public class DefinitelyWrittenCheck {
     Set<MethodDescriptor> methodDescriptorsToAnalyze = new HashSet<MethodDescriptor>();
     methodDescriptorsToAnalyze.addAll(ssjava.getAnnotationRequireSet());
 
-    LinkedList<MethodDescriptor> sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
+    sortedDescriptors = topologicalSort(methodDescriptorsToAnalyze);
+
+    LinkedList<MethodDescriptor> descriptorListToAnalyze =
+        (LinkedList<MethodDescriptor>) sortedDescriptors.clone();
 
     // no need to analyze method having ssjava loop
-    methodContainingSSJavaLoop = sortedDescriptors.removeFirst();
+    // methodContainingSSJavaLoop = descriptorListToAnalyze.removeFirst();
+    methodContainingSSJavaLoop = ssjava.getMethodContainingSSJavaLoop();
 
     // current descriptors to visit in fixed-point interprocedural analysis,
     // prioritized by
     // dependency in the call graph
-    Stack<MethodDescriptor> methodDescriptorsToVisitStack = new Stack<MethodDescriptor>();
+    methodDescriptorsToVisitStack.clear();
 
     Set<MethodDescriptor> methodDescriptorToVistSet = new HashSet<MethodDescriptor>();
-    methodDescriptorToVistSet.addAll(sortedDescriptors);
+    methodDescriptorToVistSet.addAll(descriptorListToAnalyze);
 
-    while (!sortedDescriptors.isEmpty()) {
-      MethodDescriptor md = sortedDescriptors.removeFirst();
+    while (!descriptorListToAnalyze.isEmpty()) {
+      MethodDescriptor md = descriptorListToAnalyze.removeFirst();
       methodDescriptorsToVisitStack.add(md);
     }
 
@@ -855,15 +1279,28 @@ public class DefinitelyWrittenCheck {
     }
       break;
 
-    case FKind.FlatFieldNode:
-    case FKind.FlatElementNode: {
+    case FKind.FlatElementNode:
+    case FKind.FlatFieldNode: {
 
       // y=x.f;
 
-      FlatFieldNode ffn = (FlatFieldNode) fn;
-      lhs = ffn.getDst();
-      rhs = ffn.getSrc();
-      fld = ffn.getField();
+      if (fn.kind() == FKind.FlatFieldNode) {
+        FlatFieldNode ffn = (FlatFieldNode) fn;
+        lhs = ffn.getDst();
+        rhs = ffn.getSrc();
+        fld = ffn.getField();
+      } else {
+        FlatElementNode fen = (FlatElementNode) fn;
+        lhs = fen.getDst();
+        rhs = fen.getSrc();
+        TypeDescriptor td = rhs.getType().dereference();
+        fld = getArrayField(td);
+      }
+
+      if (fld.isFinal() /* && fld.isStatic() */) {
+        // if field is final and static, no need to check
+        break;
+      }
 
       // set up heap path
       NTuple<Descriptor> srcHeapPath = mapHeapPath.get(rhs);
@@ -883,8 +1320,7 @@ public class DefinitelyWrittenCheck {
           }
         }
 
-        // need to kill hp(x.f) from WT
-        writtenSet.remove(readingHeapPath);
+        //no need to kill hp(x.f) from WT
       }
 
     }
@@ -894,10 +1330,19 @@ public class DefinitelyWrittenCheck {
     case FKind.FlatSetElementNode: {
 
       // x.f=y;
-      FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
-      lhs = fsfn.getDst();
-      fld = fsfn.getField();
-      rhs = fsfn.getSrc();
+
+      if (fn.kind() == FKind.FlatSetFieldNode) {
+        FlatSetFieldNode fsfn = (FlatSetFieldNode) fn;
+        lhs = fsfn.getDst();
+        fld = fsfn.getField();
+        rhs = fsfn.getSrc();
+      } else {
+        FlatSetElementNode fsen = (FlatSetElementNode) fn;
+        lhs = fsen.getDst();
+        rhs = fsen.getSrc();
+        TypeDescriptor td = lhs.getType().dereference();
+        fld = getArrayField(td);
+      }
 
       // set up heap path
       NTuple<Descriptor> lhsHeapPath = mapHeapPath.get(lhs);
@@ -920,25 +1365,26 @@ public class DefinitelyWrittenCheck {
 
       FlatCall fc = (FlatCall) fn;
 
-      bindHeapPathCallerArgWithCaleeParam(fc);
-
-      // add heap path, which is an element of READ_bound set and is not
-      // an
-      // element of WT set, to the caller's READ set
-      for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
-        NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
-        if (!writtenSet.contains(read)) {
-          readSet.add(read);
+      if (fc.getThis() != null) {
+        bindHeapPathCallerArgWithCaleeParam(fc);
+        
+        // add heap path, which is an element of READ_bound set and is not
+        // an
+        // element of WT set, to the caller's READ set
+        for (Iterator iterator = calleeUnionBoundReadSet.iterator(); iterator.hasNext();) {
+          NTuple<Descriptor> read = (NTuple<Descriptor>) iterator.next();
+          if (!writtenSet.contains(read)) {
+            readSet.add(read);
+          }
         }
-      }
-      writtenSet.removeAll(calleeUnionBoundReadSet);
 
-      // add heap path, which is an element of OVERWRITE_bound set, to the
-      // caller's WT set
-      for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
-        NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
-        writtenSet.add(write);
-      }
+        // add heap path, which is an element of OVERWRITE_bound set, to the
+        // caller's WT set
+        for (Iterator iterator = calleeIntersectBoundOverWriteSet.iterator(); iterator.hasNext();) {
+          NTuple<Descriptor> write = (NTuple<Descriptor>) iterator.next();
+          writtenSet.add(write);
+        }
+      } 
 
     }
       break;
@@ -953,8 +1399,82 @@ public class DefinitelyWrittenCheck {
 
   }
 
-  private void mergeSharedAnaylsis(Hashtable<NTuple<Descriptor>, Set<SharedLocState>> curr,
-      Hashtable<NTuple<Descriptor>, Set<SharedLocState>> in) {
+  static public FieldDescriptor getArrayField(TypeDescriptor td) {
+    FieldDescriptor fd = mapTypeToArrayField.get(td);
+    if (fd == null) {
+      fd =
+          new FieldDescriptor(new Modifiers(Modifiers.PUBLIC), td, arrayElementFieldName, null,
+              false);
+      mapTypeToArrayField.put(td, fd);
+    }
+    return fd;
+  }
+
+  private void mergeSharedLocationAnaylsis(ClearingSummary curr, Set<ClearingSummary> inSet) {
+
+    if (inSet.size() == 0) {
+      return;
+    }
+
+    Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean> mapHeapPathLoc2Flag =
+        new Hashtable<Pair<NTuple<Descriptor>, Location>, Boolean>();
+
+    for (Iterator inIterator = inSet.iterator(); inIterator.hasNext();) {
+
+      ClearingSummary inTable = (ClearingSummary) inIterator.next();
+
+      Set<NTuple<Descriptor>> keySet = inTable.keySet();
+
+      for (Iterator iterator = keySet.iterator(); iterator.hasNext();) {
+        NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+        SharedStatus inState = inTable.get(hpKey);
+
+        SharedStatus currState = curr.get(hpKey);
+        if (currState == null) {
+          currState = new SharedStatus();
+          curr.put(hpKey, currState);
+        }
+        currState.merge(inState);
+
+        Set<Location> locSet = inState.getMap().keySet();
+        for (Iterator iterator2 = locSet.iterator(); iterator2.hasNext();) {
+          Location loc = (Location) iterator2.next();
+          Pair<Set<Descriptor>, Boolean> pair = inState.getMap().get(loc);
+          boolean inFlag = pair.getSecond().booleanValue();
+
+          Pair<NTuple<Descriptor>, Location> flagKey =
+              new Pair<NTuple<Descriptor>, Location>(hpKey, loc);
+          Boolean current = mapHeapPathLoc2Flag.get(flagKey);
+          if (current == null) {
+            current = new Boolean(true);
+          }
+          boolean newInFlag = current.booleanValue() & inFlag;
+          mapHeapPathLoc2Flag.put(flagKey, Boolean.valueOf(newInFlag));
+        }
+
+      }
+
+    }
+
+    // merge flag status
+    Set<NTuple<Descriptor>> hpKeySet = curr.keySet();
+    for (Iterator iterator = hpKeySet.iterator(); iterator.hasNext();) {
+      NTuple<Descriptor> hpKey = (NTuple<Descriptor>) iterator.next();
+      SharedStatus currState = curr.get(hpKey);
+      Set<Location> locKeySet = currState.getMap().keySet();
+      for (Iterator iterator2 = locKeySet.iterator(); iterator2.hasNext();) {
+        Location locKey = (Location) iterator2.next();
+        Pair<Set<Descriptor>, Boolean> pair = currState.getMap().get(locKey);
+        boolean currentFlag = pair.getSecond().booleanValue();
+        Boolean inFlag = mapHeapPathLoc2Flag.get(new Pair(hpKey, locKey));
+        if (inFlag != null) {
+          boolean newFlag = currentFlag | inFlag.booleanValue();
+          if (currentFlag != newFlag) {
+            currState.getMap().put(locKey, new Pair(pair.getFirst(), new Boolean(newFlag)));
+          }
+        }
+      }
+    }
 
   }
 
@@ -1047,16 +1567,13 @@ public class DefinitelyWrittenCheck {
 
     discovered.add(md);
 
-    // otherwise call graph guides DFS
     Iterator itr = callGraph.getCallerSet(md).iterator();
     while (itr.hasNext()) {
       MethodDescriptor dCaller = (MethodDescriptor) itr.next();
-
       // only consider callers in the original set to analyze
       if (!toSort.contains(dCaller)) {
         continue;
       }
-
       if (!discovered.contains(dCaller)) {
         addDependent(md, // callee
             dCaller // caller