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

1 files changed, 231 insertions, 115 deletions

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;  
 }