This is a fairly large patch, which resulted from a cascade of changes

made to RegionStore (and related classes) in order to handle some
analyzer failures involving casts and manipulation of symbolic memory.

The root of the change is in StoreManager::CastRegion().  Instead of
using ad hoc heuristics to decide when to layer an ElementRegion on a
casted MemRegion, we now always layer an ElementRegion when the cast
type is different than the original type of the region.  This carries
the current cast information associated with a region around without
resorting to the error prone recording of "casted types" in GRState.

Along with this new policy of layering ElementRegions, I added a new
algorithm to strip away existing ElementRegions when they simply
represented casts of a base memory object.  This algorithm computes
the raw "byte offset" that an ElementRegion represents from the base
region, and allows the new ElementRegion to be based off that offset.
The added benefit is that this naturally handles a series of casts of
a MemRegion without building up a set of redundant ElementRegions
(thus canonicalizing the region view).

Other related changes that cascaded from this one (as tests were
failing in RegionStore):

- Revamped RegionStoreManager::InvalidateRegion() to completely remove
  all bindings and default values from a region and all subregions.
  Now invalidated fields are not bound directly to new symbolic
  values; instead the base region has a "default" symbol value from
  which "derived symbols" can be created.  The main advantage of this
  approach is that it allows us to invalidate a region hierarchy and
  then lazily instantiate new values no matter how deep the hierarchy
  went (i.e., regardless of the number of field accesses,
  e.g. x->f->y->z->...).  The previous approach did not do this.

- Slightly reworked RegionStoreManager::RemoveDeadBindings() to also
  incorporate live symbols and live regions that do not have direct
  bindings but also have "default values" used for lazy instantiation.
  The changes to 'InvalidateRegion' revealed that these were necessary
  in order to achieve lazy instantiation of values in the region store
  with those bindings being removed too early.

- The changes to InvalidateRegion() and RemoveDeadBindings() revealed
  a serious bug in 'getSubRegionMap()' where not all region -> subregion
  relationships involved in actually bindings (explicit and implicit)
  were being recorded.  This has been fixed by using a worklist algorithm
  to iteratively fill in the region map.

- Added special support to RegionStoreManager::Bind()/Retrieve() to handle
  OSAtomicCompareAndSwap in light of the new 'CastRegion' changes and the
  layering of ElementRegions.

- Fixed a bug in SymbolReaper::isLive() where derived symbols were not
  being marked live if the symbol they were derived from was also live.
  This fix was critical for getting lazy instantiation in RegionStore
  to work.

- Tidied up the implementation of ValueManager::getXXXSymbolVal() methods
  to use SymbolManager::canSymbolicate() to decide whether or not a
  symbol should be symbolicated.

- 'test/Analysis/misc-ps-xfail.m' now passes; that test case has been
  moved to 'test/Analysis/misc-ps.m'.

- Tweaked some pretty-printing of MemRegions, and implemented
  'ElementRegion::getRawOffset()' for use with the CastRegion changes.



git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@77782 91177308-0d34-0410-b5e6-96231b3b80d8

10 files changed, 507 insertions, 280 deletions

diff --git a/include/clang/Analysis/PathSensitive/MemRegion.h b/include/clang/Analysis/PathSensitive/MemRegion.h
index 3cfcc5cd5d..5d4c6137bc 100644
--- a/include/clang/Analysis/PathSensitive/MemRegion.h
+++ b/include/clang/Analysis/PathSensitive/MemRegion.h
@@ -35,6 +35,10 @@ namespace clang {
 class MemRegionManager;
 class MemSpaceRegion;  
       
+//===----------------------------------------------------------------------===//
+// Base region classes.
+//===----------------------------------------------------------------------===//
+  
 /// MemRegion - The root abstract class for all memory regions.
 class MemRegion : public llvm::FoldingSetNode {
 public:
@@ -134,13 +138,39 @@ public:
   }
   
   MemRegionManager* getMemRegionManager() const;
-
+  
   bool isSubRegionOf(const MemRegion* R) const;
-
+  
   static bool classof(const MemRegion* R) {
     return R->getKind() > MemSpaceRegionKind;
   }
 };
+ 
+//===----------------------------------------------------------------------===//
+// Auxillary data classes for use with MemRegions.
+//===----------------------------------------------------------------------===//
+
+class ElementRegion;
+  
+class RegionRawOffset : public std::pair<const MemRegion*, int64_t> {
+private:
+  friend class ElementRegion;
+
+  RegionRawOffset(const MemRegion* reg, int64_t offset = 0)
+    : std::pair<const MemRegion*, int64_t>(reg, offset) {}
+
+public: 
+  // FIXME: Eventually support symbolic offsets.
+  int64_t getByteOffset() const { return second; }
+  const MemRegion *getRegion() const { return first; }
+
+  void dumpToStream(llvm::raw_ostream& os) const;
+  void dump() const;
+};
+
+//===----------------------------------------------------------------------===//
+// MemRegion subclasses.
+//===----------------------------------------------------------------------===//  
 
 /// AllocaRegion - A region that represents an untyped blob of bytes created
 ///  by a call to 'alloca'.
@@ -523,6 +553,8 @@ public:
     return ElementType;
   }
   
+  RegionRawOffset getAsRawOffset() const;
+  
   void dumpToStream(llvm::raw_ostream& os) const;
 
   void Profile(llvm::FoldingSetNodeID& ID) const;
@@ -531,7 +563,7 @@ public:
     return R->getKind() == ElementRegionKind;
   }
 };
-  
+
 template<typename RegionTy>
 const RegionTy* MemRegion::getAs() const {
   if (const RegionTy* RT = dyn_cast<RegionTy>(this))
@@ -627,6 +659,7 @@ public:
   ///   object).
   ObjCIvarRegion* getObjCIvarRegion(const ObjCIvarDecl* ivd,
                                     const MemRegion* superRegion);
+  
   CodeTextRegion* getCodeTextRegion(SymbolRef sym, QualType t);
   CodeTextRegion* getCodeTextRegion(const FunctionDecl* fd, QualType t);
   
diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h
index c897b374a1..759a80eff4 100644
--- a/include/clang/Analysis/PathSensitive/Store.h
+++ b/include/clang/Analysis/PathSensitive/Store.h
@@ -198,7 +198,8 @@ public:
 
 private:
   CastResult MakeElementRegion(const GRState *state, const MemRegion *region,
-                               QualType pointeeTy, QualType castToTy);
+                               QualType pointeeTy, QualType castToTy,
+                               uint64_t index = 0);
 };
 
 // FIXME: Do we still need this?
diff --git a/include/clang/Analysis/PathSensitive/ValueManager.h b/include/clang/Analysis/PathSensitive/ValueManager.h
index 9a535b5415..711ac4a8bc 100644
--- a/include/clang/Analysis/PathSensitive/ValueManager.h
+++ b/include/clang/Analysis/PathSensitive/ValueManager.h
@@ -50,11 +50,11 @@ class ValueManager {
 public:
   ValueManager(llvm::BumpPtrAllocator &alloc, ASTContext &context,
                GRStateManager &stateMgr)
-               : Context(context), BasicVals(Context, alloc),
-                 SymMgr(Context, BasicVals, alloc),
-                 MemMgr(Context, alloc), StateMgr(stateMgr),
-                 ArrayIndexTy(Context.IntTy),
-                 ArrayIndexWidth(Context.getTypeSize(ArrayIndexTy))  
+               : Context(context), BasicVals(context, alloc),
+                 SymMgr(context, BasicVals, alloc),
+                 MemMgr(context, alloc), StateMgr(stateMgr),
+                 ArrayIndexTy(context.IntTy),
+                 ArrayIndexWidth(context.getTypeSize(ArrayIndexTy))  
   {
     // FIXME: Generalize later.
     SVator.reset(clang::CreateSimpleSValuator(*this));
diff --git a/lib/Analysis/MemRegion.cpp b/lib/Analysis/MemRegion.cpp
index 3c174df282..ac633060fd 100644
--- a/lib/Analysis/MemRegion.cpp
+++ b/lib/Analysis/MemRegion.cpp
@@ -15,6 +15,7 @@
 
 #include "llvm/Support/raw_ostream.h"
 #include "clang/Analysis/PathSensitive/MemRegion.h"
+#include "clang/Analysis/PathSensitive/ValueManager.h"
 
 using namespace clang;
 
@@ -171,7 +172,8 @@ void CompoundLiteralRegion::dumpToStream(llvm::raw_ostream& os) const {
 }
 
 void ElementRegion::dumpToStream(llvm::raw_ostream& os) const {
-  os << superRegion << '[' << Index << ']';
+  os << "element{" << superRegion << ','
+     << Index << ',' << getElementType().getAsString() << '}';
 }
 
 void FieldRegion::dumpToStream(llvm::raw_ostream& os) const {
@@ -194,10 +196,18 @@ void VarRegion::dumpToStream(llvm::raw_ostream& os) const {
   os << cast<VarDecl>(D)->getNameAsString();
 }
 
+void RegionRawOffset::dump() const {
+  dumpToStream(llvm::errs());
+}
+
+void RegionRawOffset::dumpToStream(llvm::raw_ostream& os) const {
+  os << "raw_offset{" << getRegion() << ',' << getByteOffset() << '}';
+}
+
 //===----------------------------------------------------------------------===//
 // MemRegionManager methods.
 //===----------------------------------------------------------------------===//
-  
+
 MemSpaceRegion* MemRegionManager::LazyAllocate(MemSpaceRegion*& region) {  
   if (!region) {  
     region = (MemSpaceRegion*) A.Allocate<MemSpaceRegion>();
@@ -306,7 +316,6 @@ AllocaRegion* MemRegionManager::getAllocaRegion(const Expr* E, unsigned cnt) {
   return getRegion<AllocaRegion>(E, cnt);
 }
 
-
 const MemSpaceRegion *MemRegion::getMemorySpace() const {
   const MemRegion *R = this;
   const SubRegion* SR = dyn_cast<SubRegion>(this);
@@ -381,7 +390,7 @@ const MemRegion *MemRegion::getBaseRegion() const {
       // want to strip away ElementRegions, however, where the index is 0.
       SVal index = ER->getIndex();
       if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
-        if (CI->getValue().getZExtValue() == 0) {
+        if (CI->getValue().getSExtValue() == 0) {
           R = ER->getSuperRegion();
           continue;
         }
@@ -391,3 +400,57 @@ const MemRegion *MemRegion::getBaseRegion() const {
   }
   return R;
 }
+
+// FIXME: Merge with the implementation of the same method in Store.cpp
+static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
+  if (const RecordType *RT = Ty->getAs<RecordType>()) {
+    const RecordDecl *D = RT->getDecl();
+    if (!D->getDefinition(Ctx))
+      return false;
+  }
+
+  return true;
+}
+
+RegionRawOffset ElementRegion::getAsRawOffset() const {
+  int64_t offset = 0;
+  const ElementRegion *ER = this;
+  const MemRegion *superR = NULL;
+  ASTContext &C = getContext();
+  
+  // FIXME: Handle multi-dimensional arrays.
+
+  while (ER) {
+    superR = ER->getSuperRegion();
+    
+    // FIXME: generalize to symbolic offsets.
+    SVal index = ER->getIndex();
+    if (nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&index)) {
+      // Update the offset.
+      int64_t i = CI->getValue().getSExtValue();
+      
+      if (i != 0) {
+        QualType elemType = ER->getElementType();
+        
+        // If we are pointing to an incomplete type, go no further.
+        if (!IsCompleteType(C, elemType)) {
+          superR = ER;
+          break;
+        }
+        
+        int64_t size = (int64_t) (C.getTypeSize(elemType) / 8);
+        offset += (i * size);
+      }
+
+      // Go to the next ElementRegion (if any).
+      ER = dyn_cast<ElementRegion>(superR);
+      continue;
+    }
+    
+    return NULL;
+  }
+  
+  assert(superR && "super region cannot be NULL");
+  return RegionRawOffset(superR, offset);
+}
+
diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp
index d79c4c5fcf..6ca881d73b 100644
--- a/lib/Analysis/RegionStore.cpp
+++ b/lib/Analysis/RegionStore.cpp
@@ -112,28 +112,43 @@ namespace clang {
 // This GDM entry tracks what regions have a default value if they have no bound
 // value and have not been killed.
 //
-namespace { class VISIBILITY_HIDDEN RegionDefaultValue {}; }
+namespace {
+class VISIBILITY_HIDDEN RegionDefaultValue {
+public:
+  typedef llvm::ImmutableMap<const MemRegion*, SVal> MapTy;
+};
+}
 static int RegionDefaultValueIndex = 0;
 namespace clang {
  template<> struct GRStateTrait<RegionDefaultValue>
-   : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
+    : public GRStatePartialTrait<RegionDefaultValue::MapTy> {
    static void* GDMIndex() { return &RegionDefaultValueIndex; }
  };
 }
 
 //===----------------------------------------------------------------------===//
+// Utility functions.
+//===----------------------------------------------------------------------===//
+
+static bool IsAnyPointerOrIntptr(QualType ty, ASTContext &Ctx) {
+  if (ty->isAnyPointerType())
+    return true;
+  
+  return ty->isIntegerType() && ty->isScalarType() &&
+         Ctx.getTypeSize(ty) == Ctx.getTypeSize(Ctx.VoidPtrTy);
+}
+
+//===----------------------------------------------------------------------===//
 // Main RegionStore logic.
 //===----------------------------------------------------------------------===//
 
 namespace {
-
-class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
-  typedef llvm::DenseMap<const MemRegion*,
-                         llvm::ImmutableSet<const MemRegion*> > Map;
   
-  llvm::ImmutableSet<const MemRegion*>::Factory F;
+class VISIBILITY_HIDDEN RegionStoreSubRegionMap : public SubRegionMap {
+  typedef llvm::ImmutableSet<const MemRegion*> SetTy;
+  typedef llvm::DenseMap<const MemRegion*, SetTy> Map;  
+  SetTy::Factory F;
   Map M;
-
 public:
   void add(const MemRegion* Parent, const MemRegion* SubRegion) {
     Map::iterator I = M.find(Parent);
@@ -158,6 +173,14 @@ public:
     
     return true;
   }
+  
+  typedef SetTy::iterator iterator;
+
+  std::pair<iterator, iterator> begin_end(const MemRegion *R) {
+    Map::iterator I = M.find(R);
+    SetTy S = I == M.end() ? F.GetEmptySet() : I->second;
+    return std::make_pair(S.begin(), S.end());
+  }
 };  
 
 class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
@@ -182,7 +205,9 @@ public:
 
   virtual ~RegionStoreManager() {}
 
-  SubRegionMap* getSubRegionMap(const GRState *state);
+  SubRegionMap *getSubRegionMap(const GRState *state);
+    
+  RegionStoreSubRegionMap *getRegionStoreSubRegionMap(const GRState *state);
   
   /// getLValueString - Returns an SVal representing the lvalue of a
   ///  StringLiteral.  Within RegionStore a StringLiteral has an
@@ -247,6 +272,12 @@ public:
   const GRState *InvalidateRegion(const GRState *state, const MemRegion *R,
                                   const Expr *E, unsigned Count);
   
+private:
+  RegionBindingsTy RemoveSubRegionBindings(RegionBindingsTy B,
+                                           const MemRegion *R,
+                                           RegionStoreSubRegionMap &M);
+  
+public:  
   const GRState *Bind(const GRState *state, Loc LV, SVal V);
 
   const GRState *BindCompoundLiteral(const GRState *state,
@@ -405,41 +436,91 @@ StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
   return new RegionStoreManager(StMgr, F);
 }
 
-SubRegionMap* RegionStoreManager::getSubRegionMap(const GRState *state) {
+RegionStoreSubRegionMap*
+RegionStoreManager::getRegionStoreSubRegionMap(const GRState *state) {
   RegionBindingsTy B = GetRegionBindings(state->getStore());
   RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
   
-  for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I) {
+  llvm::SmallPtrSet<const MemRegion*, 10> Marked;
+  llvm::SmallVector<const SubRegion*, 10> WL;
+
+  for (RegionBindingsTy::iterator I=B.begin(), E=B.end(); I!=E; ++I)
     if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
-      M->add(R->getSuperRegion(), R);
-  }
+      WL.push_back(R);
   
+  RegionDefaultValue::MapTy DVM = state->get<RegionDefaultValue>();
+  for (RegionDefaultValue::MapTy::iterator I = DVM.begin(), E = DVM.end();
+       I != E; ++I)    
+    if (const SubRegion* R = dyn_cast<SubRegion>(I.getKey()))
+      WL.push_back(R);
+
+  // We also need to record in the subregion map "intermediate" regions that  
+  // don't have direct bindings but are super regions of those that do.
+  while (!WL.empty()) {
+    const SubRegion *R = WL.back();
+    WL.pop_back();
+
+    if (Marked.count(R))
+      continue;
+
+    const MemRegion *superR = R->getSuperRegion();
+    M->add(superR, R);
+    if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
+      WL.push_back(sr);
+  }
+
   return M;
 }
 
+SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) {
+  return getRegionStoreSubRegionMap(state);
+}
+
 //===----------------------------------------------------------------------===//
 // Binding invalidation.
 //===----------------------------------------------------------------------===//
 
+RegionBindingsTy
+RegionStoreManager::RemoveSubRegionBindings(RegionBindingsTy B,
+                                            const MemRegion *R,
+                                            RegionStoreSubRegionMap &M) {
+  
+  RegionStoreSubRegionMap::iterator I, E;
+
+  for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I)
+    B = RemoveSubRegionBindings(B, *I, M);
+    
+  return RBFactory.Remove(B, R);
+}
+
+
 const GRState *RegionStoreManager::InvalidateRegion(const GRState *state,
                                                     const MemRegion *R,
                                                     const Expr *E,
                                                     unsigned Count) {
   ASTContext& Ctx = StateMgr.getContext();
   
+  // Strip away casts.
+  R = R->getBaseRegion();
+
+  // Get the mapping of regions -> subregions.
+  llvm::OwningPtr<RegionStoreSubRegionMap>
+  SubRegions(getRegionStoreSubRegionMap(state));
+  
+  // Remove the bindings to subregions.
+  RegionBindingsTy B = GetRegionBindings(state->getStore());
+  B = RemoveSubRegionBindings(B, R, *SubRegions.get());
+  state = state->makeWithStore(B.getRoot());
+  
   if (!R->isBoundable())
     return state;
   
-  if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R) 
-      || isa<ObjCObjectRegion>(R)) {
-    // Invalidate the alloca region by setting its default value to 
+  if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R) ||
+      isa<ObjCObjectRegion>(R)) {
+    // Invalidate the region by setting its default value to 
     // conjured symbol. The type of the symbol is irrelavant.
     SVal V = ValMgr.getConjuredSymbolVal(E, Ctx.IntTy, Count);
-    state = setDefaultValue(state, R, V);
-    
-    // FIXME: This form of invalidation is a little bogus; we actually need
-    // to invalidate all subregions as well.
-    return state;
+    return setDefaultValue(state, R, V);
   }
   
   const TypedRegion *TR = cast<TypedRegion>(R);
@@ -465,12 +546,8 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state,
       T = NewT;
   }
 #endif
-  
-  if (Loc::IsLocType(T) || (T->isIntegerType() && T->isScalarType())) {
-    SVal V = ValMgr.getConjuredSymbolVal(E, T, Count);
-    return Bind(state, ValMgr.makeLoc(TR), V);
-  }
-  else if (const RecordType *RT = T->getAsStructureType()) {
+
+  if (const RecordType *RT = T->getAsStructureType()) {
     // FIXME: handle structs with default region value.
     const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
     
@@ -478,40 +555,22 @@ const GRState *RegionStoreManager::InvalidateRegion(const GRState *state,
     if (!RD)
       return state;
     
-    // Iterate through the fields and construct new symbols.
-    for (RecordDecl::field_iterator FI=RD->field_begin(),
-         FE=RD->field_end(); FI!=FE; ++FI) {
-      
-      // For now just handle scalar fields.
-      FieldDecl *FD = *FI;
-      QualType FT = FD->getType();
-      const FieldRegion* FR = MRMgr.getFieldRegion(FD, TR);
-      
-      if (Loc::IsLocType(FT) || 
-          (FT->isIntegerType() && FT->isScalarType())) {
-        SVal V = ValMgr.getConjuredSymbolVal(E, FT, Count);
-        state = state->bindLoc(ValMgr.makeLoc(FR), V);
-      }
-      else if (FT->isStructureType()) {
-        // set the default value of the struct field to conjured
-        // symbol. Note that the type of the symbol is irrelavant.
-        // We cannot use the type of the struct otherwise ValMgr won't
-        // give us the conjured symbol.
-        SVal V = ValMgr.getConjuredSymbolVal(E, Ctx.IntTy, Count);
-        state = setDefaultValue(state, FR, V);
-      }
-    }
-  } else if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
+    // Invalidate the region by setting its default value to 
+    // conjured symbol. The type of the symbol is irrelavant.
+    SVal V = ValMgr.getConjuredSymbolVal(E, Ctx.IntTy, Count);
+    return setDefaultValue(state, R, V);
+  }
+
+  if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
     // Set the default value of the array to conjured symbol.
     SVal V = ValMgr.getConjuredSymbolVal(E, AT->getElementType(),
                                          Count);
-    state = setDefaultValue(state, TR, V);
-  } else {
-    // Just blast away other values.
-    state = Bind(state, ValMgr.makeLoc(TR), UnknownVal());
+    return setDefaultValue(state, TR, V);
   }
   
-  return state;
+  SVal V = ValMgr.getConjuredSymbolVal(E, T, Count);
+  assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
+  return Bind(state, ValMgr.makeLoc(TR), V);
 }
 
 //===----------------------------------------------------------------------===//
@@ -923,6 +982,7 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
   //
   // Such funny addressing will occur due to layering of regions.
 
+#if 0
   ASTContext &Ctx = getContext();
   if (!T.isNull() && IsReinterpreted(RTy, T, Ctx)) {
     SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
@@ -931,6 +991,7 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
     assert(Ctx.getCanonicalType(RTy) ==
            Ctx.getCanonicalType(R->getValueType(Ctx)));
   }  
+#endif
 
   if (RTy->isStructureType())
     return SValuator::CastResult(state, RetrieveStruct(state, R));
@@ -990,6 +1051,8 @@ RegionStoreManager::Retrieve(const GRState *state, Loc L, QualType T) {
   return SValuator::CastResult(state,
                                ValMgr.getRegionValueSymbolValOrUnknown(R, RTy));
 }
+  
+
 
 SVal RegionStoreManager::RetrieveElement(const GRState* state,
                                          const ElementRegion* R) {
@@ -1014,6 +1077,29 @@ SVal RegionStoreManager::RetrieveElement(const GRState* state,
       return ValMgr.makeIntVal(c, getContext().CharTy);
     }
   }
+  
+  // Special case: the current region represents a cast and it and the super
+  // region both have pointer types or intptr_t types.  If so, perform the
+  // retrieve from the super region and appropriately "cast" the value.
+  // This is needed to support OSAtomicCompareAndSwap and friends or other
+  // loads that treat integers as pointers and vis versa.  
+  if (R->getIndex().isZeroConstant()) {
+    if (const TypedRegion *superTR = dyn_cast<TypedRegion>(superR)) {
+      ASTContext &Ctx = getContext();
+
+      if (IsAnyPointerOrIntptr(superTR->getValueType(Ctx), Ctx)) {
+        QualType valTy = R->getValueType(Ctx);
+        if (IsAnyPointerOrIntptr(valTy, Ctx)) {
+          // Retrieve the value from the super region.  This will be casted to
+          // valTy when we return to 'Retrieve'.
+          const SValuator::CastResult &cr = Retrieve(state,
+                                                     loc::MemRegionVal(superR),
+                                                     valTy);
+          return cr.getSVal();
+        }
+      }
+    }
+  }
 
   // Check if the super region has a default value.
   if (const SVal *D = state->get<RegionDefaultValue>(superR)) {
@@ -1078,18 +1164,29 @@ SVal RegionStoreManager::RetrieveField(const GRState* state,
     return *V;
 
   const MemRegion* superR = R->getSuperRegion();
-  if (const SVal* D = state->get<RegionDefaultValue>(superR)) {
-    if (D->hasConjuredSymbol())
-      return ValMgr.getRegionValueSymbolVal(R);
+  while (superR) {
+    if (const SVal* D = state->get<RegionDefaultValue>(superR)) {
+      if (SymbolRef parentSym = D->getAsSymbol())
+        return ValMgr.getDerivedRegionValueSymbolVal(parentSym, R);
 
-    if (D->isZeroConstant())
-      return ValMgr.makeZeroVal(Ty);
+      if (D->isZeroConstant())
+        return ValMgr.makeZeroVal(Ty);
 
-    if (D->isUnknown())
-      return *D;
+      if (D->isUnknown())
+        return *D;
 
-    assert(0 && "Unknown default value");
-  }
+      assert(0 && "Unknown default value");
+    }
+   
+    // If our super region is a field or element itself, walk up the region
+    // hierarchy to see if there is a default value installed in an ancestor.
+    if (isa<FieldRegion>(superR) || isa<ElementRegion>(superR)) {
+      superR = cast<SubRegion>(superR)->getSuperRegion();
+      continue;
+    }
+    
+    break;
+  }    
 
 #if HEAP_UNDEFINED
   // FIXME: Is this correct?  Should it be UnknownVal?
@@ -1260,17 +1357,39 @@ const GRState *RegionStoreManager::Bind(const GRState *state, Loc L, SVal V) {
     return state;
 
   // If we get here, the location should be a region.
-  const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion();
+  const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
   
   // Check if the region is a struct region.
   if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
     if (TR->getValueType(getContext())->isStructureType())
       return BindStruct(state, TR, V);
   
-  RegionBindingsTy B = GetRegionBindings(state->getStore());
-  
-  B = RBFactory.Add(B, R, V);
+  // Special case: the current region represents a cast and it and the super
+  // region both have pointer types or intptr_t types.  If so, perform the
+  // bind to the super region.
+  // This is needed to support OSAtomicCompareAndSwap and friends or other
+  // loads that treat integers as pointers and vis versa.  
+  if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
+    if (ER->getIndex().isZeroConstant()) {
+      if (const TypedRegion *superR =
+            dyn_cast<TypedRegion>(ER->getSuperRegion())) {
+        ASTContext &Ctx = getContext();
+        QualType superTy = superR->getValueType(Ctx);
+        QualType erTy = ER->getValueType(Ctx);
+        
+        if (IsAnyPointerOrIntptr(superTy, Ctx) && 
+            IsAnyPointerOrIntptr(erTy, Ctx)) {
+          SValuator::CastResult cr = 
+            ValMgr.getSValuator().EvalCast(V, state, superTy, erTy);  
+          return Bind(cr.getState(), loc::MemRegionVal(superR), cr.getSVal());
+        }
+      }
+    }
+  }
   
+  // Perform the binding.
+  RegionBindingsTy B = GetRegionBindings(state->getStore());
+  B = RBFactory.Add(B, R, V);  
   return state->makeWithStore(B.getRoot());
 }
 
@@ -1522,28 +1641,31 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
   typedef llvm::ImmutableSet<const MemRegion*> SubRegionsTy;
   typedef llvm::ImmutableMap<const MemRegion*, SubRegionsTy> SubRegionsMapTy;
   
-  // FIXME: As a future optimization we can modifiy BumpPtrAllocator to have
-  // the ability to reuse memory.  This way we can keep TmpAlloc around as
-  // an instance variable of RegionStoreManager (avoiding repeated malloc
-  // overhead).
-  llvm::BumpPtrAllocator TmpAlloc;
-  
-  // Factory objects.
-  SubRegionsMapTy::Factory SubRegMapF(TmpAlloc);
-  SubRegionsTy::Factory SubRegF(TmpAlloc);
-  
   // The backmap from regions to subregions.
-  SubRegionsMapTy SubRegMap = SubRegMapF.GetEmptyMap();
+  llvm::OwningPtr<RegionStoreSubRegionMap>
+  SubRegions(getRegionStoreSubRegionMap(state));
   
   // Do a pass over the regions in the store.  For VarRegions we check if
   // the variable is still live and if so add it to the list of live roots.
   // For other regions we populate our region backmap.  
   llvm::SmallVector<const MemRegion*, 10> IntermediateRoots;
   
+  // Scan the direct bindings for "intermediate" roots.
   for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I) {
-    IntermediateRoots.push_back(I.getKey());
+    const MemRegion *R = I.getKey();
+    IntermediateRoots.push_back(R);
   }
   
+  // Scan the default bindings for "intermediate" roots.
+  RegionDefaultValue::MapTy DVM = state->get<RegionDefaultValue>();
+  for (RegionDefaultValue::MapTy::iterator I = DVM.begin(), E = DVM.end();
+       I != E; ++I) {
+    const MemRegion *R = I.getKey();
+    IntermediateRoots.push_back(R);
+  }
+
+  // Process the "intermediate" roots to find if they are referenced by
+  // real roots.  
   while (!IntermediateRoots.empty()) {
     const MemRegion* R = IntermediateRoots.back();
     IntermediateRoots.pop_back();
@@ -1552,40 +1674,32 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
       if (SymReaper.isLive(Loc, VR->getDecl())) {
         RegionRoots.push_back(VR); // This is a live "root".
       }
-    } 
-    else if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
+      continue;
+    }
+    
+    if (const SymbolicRegion* SR = dyn_cast<SymbolicRegion>(R)) {
       if (SymReaper.isLive(SR->getSymbol()))
         RegionRoots.push_back(SR);
+      continue;
     }
-    else {
-      // Get the super region for R.
-      const MemRegion* superR = cast<SubRegion>(R)->getSuperRegion();
-      
-      // Get the current set of subregions for SuperR.
-      const SubRegionsTy* SRptr = SubRegMap.lookup(superR);
-      SubRegionsTy SRs = SRptr ? *SRptr : SubRegF.GetEmptySet();
-      
-      // Add R to the subregions of SuperR.
-      SubRegMap = SubRegMapF.Add(SubRegMap, superR, SubRegF.Add(SRs, R));
-      
-      // Super region may be VarRegion or subregion of another VarRegion. Add it
-      // to the work list.
-      if (isa<SubRegion>(superR))
-        IntermediateRoots.push_back(superR);
-    }
+
+    // Add the super region for R to the worklist if it is a subregion.
+    if (const SubRegion* superR =
+          dyn_cast<SubRegion>(cast<SubRegion>(R)->getSuperRegion()))
+      IntermediateRoots.push_back(superR);
   }
   
   // Process the worklist of RegionRoots.  This performs a "mark-and-sweep"
   // of the store.  We want to find all live symbols and dead regions.  
-  llvm::SmallPtrSet<const MemRegion*, 10> Marked;
-  
+  llvm::SmallPtrSet<const MemRegion*, 10> Marked;  
   while (!RegionRoots.empty()) {
     // Dequeue the next region on the worklist.
     const MemRegion* R = RegionRoots.back();
     RegionRoots.pop_back();
     
     // Check if we have already processed this region.
-    if (Marked.count(R)) continue;
+    if (Marked.count(R))
+      continue;
     
     // Mark this region as processed.  This is needed for termination in case
     // a region is referenced more than once.
@@ -1597,7 +1711,13 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
       SymReaper.markLive(SymR->getSymbol());
     
     // Get the data binding for R (if any).
-    RegionBindingsTy::data_type* Xptr = B.lookup(R);
+    const SVal* Xptr = B.lookup(R);    
+    if (!Xptr) {
+      // No direct binding? Get the default binding for R (if any).
+      Xptr = DVM.lookup(R);
+    }
+
+    // Direct or default binding?
     if (Xptr) {
       SVal X = *Xptr;
       UpdateLiveSymbols(X, SymReaper); // Update the set of live symbols.
@@ -1605,12 +1725,9 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
       // If X is a region, then add it to the RegionRoots.
       if (const MemRegion *RX = X.getAsRegion()) {
         RegionRoots.push_back(RX);
-
         // Mark the super region of the RX as live.
         // e.g.: int x; char *y = (char*) &x; if (*y) ... 
         // 'y' => element region. 'x' is its super region.
-        // We only add one level super region for now.
-        // FIXME: maybe multiple level of super regions should be added.
         if (const SubRegion *SR = dyn_cast<SubRegion>(RX)) {
           RegionRoots.push_back(SR->getSuperRegion());
         }
@@ -1619,13 +1736,9 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
     
     // Get the subregions of R.  These are RegionRoots as well since they
     // represent values that are also bound to R.
-    const SubRegionsTy* SRptr = SubRegMap.lookup(R);      
-    if (!SRptr) continue;
-    SubRegionsTy SR = *SRptr;
-    
-    for (SubRegionsTy::iterator I=SR.begin(), E=SR.end(); I!=E; ++I)
+    RegionStoreSubRegionMap::iterator I, E;    
+    for (llvm::tie(I, E) = SubRegions->begin_end(R); I != E; ++I)
       RegionRoots.push_back(*I);
-
   }
   
   // We have now scanned the store, marking reachable regions and symbols
@@ -1646,9 +1759,12 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
     
     SVal X = I.getData();
     SVal::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
-    for (; SI != SE; ++SI) SymReaper.maybeDead(*SI);
+    for (; SI != SE; ++SI)
+      SymReaper.maybeDead(*SI);
   }
   
+  // FIXME: remove default bindings as well.
+
   return store;
 }
 
@@ -1659,8 +1775,8 @@ Store RegionStoreManager::RemoveDeadBindings(const GRState *state, Stmt* Loc,
 void RegionStoreManager::print(Store store, llvm::raw_ostream& OS,
                                const char* nl, const char *sep) {
   RegionBindingsTy B = GetRegionBindings(store);
-  OS << "Store:" << nl;
+  OS << "Store (direct bindings):" << nl;
   
   for (RegionBindingsTy::iterator I = B.begin(), E = B.end(); I != E; ++I)
-    OS << ' ' << I.getKey() << " : " << I.getData() << nl;
+    OS << ' ' << I.getKey() << " : " << I.getData() << nl;  
 }
diff --git a/lib/Analysis/Store.cpp b/lib/Analysis/Store.cpp
index 68bb49cbe3..bfcb0f41ca 100644
--- a/lib/Analysis/Store.cpp
+++ b/lib/Analysis/Store.cpp
@@ -22,17 +22,15 @@ StoreManager::StoreManager(GRStateManager &stateMgr)
 
 StoreManager::CastResult
 StoreManager::MakeElementRegion(const GRState *state, const MemRegion *region,
-                                QualType pointeeTy, QualType castToTy) {
-  
-  // Record the cast type of the region.
-  state = setCastType(state, region, castToTy);
-  
-  // Create a new ElementRegion at offset 0.
-  SVal idx = ValMgr.makeZeroArrayIndex();
+                                QualType pointeeTy, QualType castToTy,
+                                uint64_t index) {
+  // Create a new ElementRegion.
+  SVal idx = ValMgr.makeArrayIndex(index);
   return CastResult(state, MRMgr.getElementRegion(pointeeTy, idx, region,
                                                   ValMgr.getContext()));  
 }
 
+// FIXME: Merge with the implementation of the same method in MemRegion.cpp
 static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
   if (const RecordType *RT = Ty->getAs<RecordType>()) {
     const RecordDecl *D = RT->getDecl();
@@ -49,15 +47,10 @@ StoreManager::CastRegion(const GRState *state, const MemRegion* R,
   
   ASTContext& Ctx