Split libAnalysis into two libraries: libAnalysis and libChecker.

(1) libAnalysis is a generic analysis library that can be used by
    Sema.  It defines the CFG, basic dataflow analysis primitives, and
    inexpensive flow-sensitive analyses (e.g. LiveVariables).

(2) libChecker contains the guts of the static analyzer, incuding the
    path-sensitive analysis engine and domain-specific checks.

Now any clients that want to use the frontend to build their own tools
don't need to link in the entire static analyzer.

This change exposes various obvious cleanups that can be made to the
layout of files and headers in libChecker.  More changes pending.  :)

This change also exposed a layering violation between AnalysisContext
and MemRegion.  BlockInvocationContext shouldn't explicitly know about
BlockDataRegions.  For now I've removed the BlockDataRegion* from
BlockInvocationContext (removing context-sensitivity; although this
wasn't used yet).  We need to have a better way to extend
BlockInvocationContext (and any LocationContext) to add
context-sensitivty.


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

1 files changed, 2015 insertions, 0 deletions

diff --git a/lib/Checker/RegionStore.cpp b/lib/Checker/RegionStore.cpp
new file mode 100644
index 0000000000..39686c22df
--- /dev/null
+++ b/lib/Checker/RegionStore.cpp
@@ -0,0 +1,2015 @@
+//== RegionStore.cpp - Field-sensitive store model --------------*- C++ -*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a basic region store model. In this model, we do have field
+// sensitivity. But we assume nothing about the heap shape. So recursive data
+// structures are largely ignored. Basically we do 1-limiting analysis.
+// Parameter pointers are assumed with no aliasing. Pointee objects of
+// parameters are created lazily.
+//
+//===----------------------------------------------------------------------===//
+#include "clang/Checker/PathSensitive/MemRegion.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Checker/PathSensitive/GRState.h"
+#include "clang/Checker/PathSensitive/GRStateTrait.h"
+#include "clang/Analysis/Analyses/LiveVariables.h"
+#include "clang/Analysis/Support/Optional.h"
+#include "clang/Basic/TargetInfo.h"
+#include "clang/AST/CharUnits.h"
+
+#include "llvm/ADT/ImmutableMap.h"
+#include "llvm/ADT/ImmutableList.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace clang;
+
+#define USE_EXPLICIT_COMPOUND 0
+
+//===----------------------------------------------------------------------===//
+// Representation of value bindings.
+//===----------------------------------------------------------------------===//
+
+namespace {
+class BindingVal {
+public:
+  enum BindingKind { Direct, Default };
+private:
+  SVal Value;
+  BindingKind Kind;
+
+public:
+  BindingVal(SVal V, BindingKind K) : Value(V), Kind(K) {}
+
+  bool isDefault() const { return Kind == Default; }
+
+  const SVal *getValue() const { return &Value; }
+
+  const SVal *getDirectValue() const { return isDefault() ? 0 : &Value; }
+
+  const SVal *getDefaultValue() const { return isDefault() ? &Value : 0; }
+
+  void Profile(llvm::FoldingSetNodeID& ID) const {
+    Value.Profile(ID);
+    ID.AddInteger(Kind);
+  }
+
+  inline bool operator==(const BindingVal& R) const {
+    return Value == R.Value && Kind == R.Kind;
+  }
+
+  inline bool operator!=(const BindingVal& R) const {
+    return !(*this == R);
+  }
+};
+}
+
+namespace llvm {
+static inline 
+llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingVal V) {
+  if (V.isDefault())
+    os << "(default) ";
+  else
+    os << "(direct) ";
+  os << *V.getValue();
+  return os;
+}
+} // end llvm namespace
+
+//===----------------------------------------------------------------------===//
+// Representation of binding keys.
+//===----------------------------------------------------------------------===//
+
+namespace {
+  class BindingKey : public std::pair<const MemRegion*, uint64_t> {
+public:
+  explicit BindingKey(const MemRegion *r, uint64_t offset)
+    : std::pair<const MemRegion*,uint64_t>(r, offset) { assert(r); }
+  
+  const MemRegion *getRegion() const { return first; }
+  uint64_t getOffset() const { return second; }
+  
+  void Profile(llvm::FoldingSetNodeID& ID) const {
+    ID.AddPointer(getRegion());
+    ID.AddInteger(getOffset());
+  }
+    
+  static BindingKey Make(const MemRegion *R);
+};    
+} // end anonymous namespace
+
+namespace llvm {
+  static inline 
+  llvm::raw_ostream& operator<<(llvm::raw_ostream& os, BindingKey K) {
+    os << '(' << K.getRegion() << ',' << K.getOffset() << ')';
+    return os;
+  }
+} // end llvm namespace
+
+//===----------------------------------------------------------------------===//
+// Actual Store type.
+//===----------------------------------------------------------------------===//
+
+typedef llvm::ImmutableMap<BindingKey, BindingVal> RegionBindings;
+
+//===----------------------------------------------------------------------===//
+// Fine-grained control of RegionStoreManager.
+//===----------------------------------------------------------------------===//
+
+namespace {
+struct minimal_features_tag {};
+struct maximal_features_tag {};
+
+class RegionStoreFeatures {
+  bool SupportsFields;
+  bool SupportsRemaining;
+
+public:
+  RegionStoreFeatures(minimal_features_tag) :
+    SupportsFields(false), SupportsRemaining(false) {}
+
+  RegionStoreFeatures(maximal_features_tag) :
+    SupportsFields(true), SupportsRemaining(false) {}
+
+  void enableFields(bool t) { SupportsFields = t; }
+
+  bool supportsFields() const { return SupportsFields; }
+  bool supportsRemaining() const { return SupportsRemaining; }
+};
+}
+
+//===----------------------------------------------------------------------===//
+// Region "Extents"
+//===----------------------------------------------------------------------===//
+//
+//  MemRegions represent chunks of memory with a size (their "extent").  This
+//  GDM entry tracks the extents for regions.  Extents are in bytes.
+//
+namespace { class RegionExtents {}; }
+static int RegionExtentsIndex = 0;
+namespace clang {
+  template<> struct GRStateTrait<RegionExtents>
+    : public GRStatePartialTrait<llvm::ImmutableMap<const MemRegion*, SVal> > {
+    static void* GDMIndex() { return &RegionExtentsIndex; }
+  };
+}
+
+//===----------------------------------------------------------------------===//
+// 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 RegionStoreSubRegionMap : public SubRegionMap {
+  typedef llvm::ImmutableSet<const MemRegion*> SetTy;
+  typedef llvm::DenseMap<const MemRegion*, SetTy> Map;
+  SetTy::Factory F;
+  Map M;
+public:
+  bool add(const MemRegion* Parent, const MemRegion* SubRegion) {
+    Map::iterator I = M.find(Parent);
+
+    if (I == M.end()) {
+      M.insert(std::make_pair(Parent, F.Add(F.GetEmptySet(), SubRegion)));
+      return true;
+    }
+
+    I->second = F.Add(I->second, SubRegion);
+    return false;
+  }
+
+  void process(llvm::SmallVectorImpl<const SubRegion*> &WL, const SubRegion *R);
+
+  ~RegionStoreSubRegionMap() {}
+
+  bool iterSubRegions(const MemRegion* Parent, Visitor& V) const {
+    Map::const_iterator I = M.find(Parent);
+
+    if (I == M.end())
+      return true;
+
+    llvm::ImmutableSet<const MemRegion*> S = I->second;
+    for (llvm::ImmutableSet<const MemRegion*>::iterator SI=S.begin(),SE=S.end();
+         SI != SE; ++SI) {
+      if (!V.Visit(Parent, *SI))
+        return false;
+    }
+
+    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 RegionStoreManager : public StoreManager {
+  const RegionStoreFeatures Features;
+  RegionBindings::Factory RBFactory;
+  
+  typedef llvm::DenseMap<const GRState *, RegionStoreSubRegionMap*> SMCache;
+  SMCache SC;
+
+public:
+  RegionStoreManager(GRStateManager& mgr, const RegionStoreFeatures &f)
+    : StoreManager(mgr),
+      Features(f),
+      RBFactory(mgr.getAllocator()) {}
+
+  virtual ~RegionStoreManager() {
+    for (SMCache::iterator I = SC.begin(), E = SC.end(); I != E; ++I)
+      delete (*I).second;
+  }
+
+  SubRegionMap *getSubRegionMap(const GRState *state);
+
+  RegionStoreSubRegionMap *getRegionStoreSubRegionMap(Store store);
+
+  Optional<SVal> getBinding(RegionBindings B, const MemRegion *R);
+  Optional<SVal> getDirectBinding(RegionBindings B, const MemRegion *R);
+  /// getDefaultBinding - Returns an SVal* representing an optional default
+  ///  binding associated with a region and its subregions.
+  Optional<SVal> getDefaultBinding(RegionBindings B, const MemRegion *R);
+  
+  /// setImplicitDefaultValue - Set the default binding for the provided
+  ///  MemRegion to the value implicitly defined for compound literals when
+  ///  the value is not specified.  
+  const GRState *setImplicitDefaultValue(const GRState *state,
+                                         const MemRegion *R,
+                                         QualType T);
+
+  /// getLValueString - Returns an SVal representing the lvalue of a
+  ///  StringLiteral.  Within RegionStore a StringLiteral has an
+  ///  associated StringRegion, and the lvalue of a StringLiteral is
+  ///  the lvalue of that region.
+  SVal getLValueString(const StringLiteral* S);
+
+  /// getLValueCompoundLiteral - Returns an SVal representing the
+  ///   lvalue of a compound literal.  Within RegionStore a compound
+  ///   literal has an associated region, and the lvalue of the
+  ///   compound literal is the lvalue of that region.
+  SVal getLValueCompoundLiteral(const CompoundLiteralExpr*);
+
+  /// getLValueVar - Returns an SVal that represents the lvalue of a
+  ///  variable.  Within RegionStore a variable has an associated
+  ///  VarRegion, and the lvalue of the variable is the lvalue of that region.
+  SVal getLValueVar(const VarDecl *VD, const LocationContext *LC);
+
+  SVal getLValueIvar(const ObjCIvarDecl* D, SVal Base);
+
+  SVal getLValueField(const FieldDecl* D, SVal Base);
+
+  SVal getLValueFieldOrIvar(const Decl* D, SVal Base);
+
+  SVal getLValueElement(QualType elementType, SVal Offset, SVal Base);
+
+
+  /// ArrayToPointer - Emulates the "decay" of an array to a pointer
+  ///  type.  'Array' represents the lvalue of the array being decayed
+  ///  to a pointer, and the returned SVal represents the decayed
+  ///  version of that lvalue (i.e., a pointer to the first element of
+  ///  the array).  This is called by GRExprEngine when evaluating
+  ///  casts from arrays to pointers.
+  SVal ArrayToPointer(Loc Array);
+
+  SVal EvalBinOp(const GRState *state, BinaryOperator::Opcode Op,Loc L,
+                 NonLoc R, QualType resultTy);
+
+  Store getInitialStore(const LocationContext *InitLoc) {
+    return RBFactory.GetEmptyMap().getRoot();
+  }
+
+  //===-------------------------------------------------------------------===//
+  // Binding values to regions.
+  //===-------------------------------------------------------------------===//
+
+  const GRState *InvalidateRegion(const GRState *state, const MemRegion *R,
+                                  const Expr *E, unsigned Count,
+                                  InvalidatedSymbols *IS) {
+    return RegionStoreManager::InvalidateRegions(state, &R, &R+1, E, Count, IS);
+  }
+  
+  const GRState *InvalidateRegions(const GRState *state,
+                                   const MemRegion * const *Begin,
+                                   const MemRegion * const *End,
+                                   const Expr *E, unsigned Count,
+                                   InvalidatedSymbols *IS);
+
+private:
+  void RemoveSubRegionBindings(RegionBindings &B, const MemRegion *R,
+                               RegionStoreSubRegionMap &M);
+
+  RegionBindings Add(RegionBindings B, BindingKey K, BindingVal V);
+  RegionBindings Add(RegionBindings B, const MemRegion *R, BindingVal V);
+  
+  const BindingVal *Lookup(RegionBindings B, BindingKey K);
+  const BindingVal *Lookup(RegionBindings B, const MemRegion *R);
+
+  RegionBindings Remove(RegionBindings B, BindingKey K);
+  RegionBindings Remove(RegionBindings B, const MemRegion *R);
+  Store Remove(Store store, BindingKey K);
+
+public:
+  const GRState *Bind(const GRState *state, Loc LV, SVal V);
+
+  const GRState *BindCompoundLiteral(const GRState *state,
+                                     const CompoundLiteralExpr* CL,
+                                     const LocationContext *LC,
+                                     SVal V);
+
+  const GRState *BindDecl(const GRState *ST, const VarRegion *VR,
+                          SVal InitVal);
+
+  const GRState *BindDeclWithNoInit(const GRState *state, 
+                                    const VarRegion *) {
+    return state;
+  }
+
+  /// BindStruct - Bind a compound value to a structure.
+  const GRState *BindStruct(const GRState *, const TypedRegion* R, SVal V);
+
+  const GRState *BindArray(const GRState *state, const TypedRegion* R, SVal V);
+
+  /// KillStruct - Set the entire struct to unknown.
+  Store KillStruct(Store store, const TypedRegion* R);
+
+  Store Remove(Store store, Loc LV);
+  
+
+  //===------------------------------------------------------------------===//
+  // Loading values from regions.
+  //===------------------------------------------------------------------===//
+
+  /// The high level logic for this method is this:
+  /// Retrieve (L)
+  ///   if L has binding
+  ///     return L's binding
+  ///   else if L is in killset
+  ///     return unknown
+  ///   else
+  ///     if L is on stack or heap
+  ///       return undefined
+  ///     else
+  ///       return symbolic
+  SValuator::CastResult Retrieve(const GRState *state, Loc L,
+                                 QualType T = QualType());
+
+  SVal RetrieveElement(const GRState *state, const ElementRegion *R);
+
+  SVal RetrieveField(const GRState *state, const FieldRegion *R);
+
+  SVal RetrieveObjCIvar(const GRState *state, const ObjCIvarRegion *R);
+
+  SVal RetrieveVar(const GRState *state, const VarRegion *R);
+
+  SVal RetrieveLazySymbol(const GRState *state, const TypedRegion *R);
+
+  SVal RetrieveFieldOrElementCommon(const GRState *state, const TypedRegion *R,
+                                    QualType Ty, const MemRegion *superR);
+
+  /// Retrieve the values in a struct and return a CompoundVal, used when doing
+  /// struct copy:
+  /// struct s x, y;
+  /// x = y;
+  /// y's value is retrieved by this method.
+  SVal RetrieveStruct(const GRState *St, const TypedRegion* R);
+
+  SVal RetrieveArray(const GRState *St, const TypedRegion* R);
+
+  /// Get the state and region whose binding this region R corresponds to.
+  std::pair<const GRState*, const MemRegion*>
+  GetLazyBinding(RegionBindings B, const MemRegion *R);
+
+  const GRState* CopyLazyBindings(nonloc::LazyCompoundVal V,
+                                  const GRState *state,
+                                  const TypedRegion *R);
+
+  const ElementRegion *GetElementZeroRegion(const SymbolicRegion *SR,
+                                            QualType T);
+
+  //===------------------------------------------------------------------===//
+  // State pruning.
+  //===------------------------------------------------------------------===//
+
+  /// RemoveDeadBindings - Scans the RegionStore of 'state' for dead values.
+  ///  It returns a new Store with these values removed.
+  void RemoveDeadBindings(GRState &state, Stmt* Loc, SymbolReaper& SymReaper,
+                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots);
+
+  const GRState *EnterStackFrame(const GRState *state,
+                                 const StackFrameContext *frame);
+
+  //===------------------------------------------------------------------===//
+  // Region "extents".
+  //===------------------------------------------------------------------===//
+
+  const GRState *setExtent(const GRState *state,const MemRegion* R,SVal Extent);
+  DefinedOrUnknownSVal getSizeInElements(const GRState *state, 
+                                         const MemRegion* R, QualType EleTy);
+
+  //===------------------------------------------------------------------===//
+  // Utility methods.
+  //===------------------------------------------------------------------===//
+
+  static inline RegionBindings GetRegionBindings(Store store) {
+    return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
+  }
+
+  void print(Store store, llvm::raw_ostream& Out, const char* nl,
+             const char *sep);
+
+  void iterBindings(Store store, BindingsHandler& f) {
+    // FIXME: Implement.
+  }
+
+  // FIXME: Remove.
+  BasicValueFactory& getBasicVals() {
+      return StateMgr.getBasicVals();
+  }
+
+  // FIXME: Remove.
+  ASTContext& getContext() { return StateMgr.getContext(); }
+};
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+// RegionStore creation.
+//===----------------------------------------------------------------------===//
+
+StoreManager *clang::CreateRegionStoreManager(GRStateManager& StMgr) {
+  RegionStoreFeatures F = maximal_features_tag();
+  return new RegionStoreManager(StMgr, F);
+}
+
+StoreManager *clang::CreateFieldsOnlyRegionStoreManager(GRStateManager &StMgr) {
+  RegionStoreFeatures F = minimal_features_tag();
+  F.enableFields(true);
+  return new RegionStoreManager(StMgr, F);
+}
+
+void
+RegionStoreSubRegionMap::process(llvm::SmallVectorImpl<const SubRegion*> &WL,
+                                 const SubRegion *R) {
+  const MemRegion *superR = R->getSuperRegion();
+  if (add(superR, R))
+    if (const SubRegion *sr = dyn_cast<SubRegion>(superR))
+      WL.push_back(sr);
+}
+
+RegionStoreSubRegionMap*
+RegionStoreManager::getRegionStoreSubRegionMap(Store store) {
+  RegionBindings B = GetRegionBindings(store);
+  RegionStoreSubRegionMap *M = new RegionStoreSubRegionMap();
+
+  llvm::SmallVector<const SubRegion*, 10> WL;
+
+  for (RegionBindings::iterator I=B.begin(), E=B.end(); I!=E; ++I)
+    if (const SubRegion *R = dyn_cast<SubRegion>(I.getKey().getRegion()))
+      M->process(WL, 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();
+    M->process(WL, R);
+  }
+
+  return M;
+}
+
+SubRegionMap *RegionStoreManager::getSubRegionMap(const GRState *state) {
+  return getRegionStoreSubRegionMap(state->getStore());
+}
+
+//===----------------------------------------------------------------------===//
+// Binding invalidation.
+//===----------------------------------------------------------------------===//
+
+void RegionStoreManager::RemoveSubRegionBindings(RegionBindings &B,
+                                                 const MemRegion *R,
+                                                 RegionStoreSubRegionMap &M) {
+  RegionStoreSubRegionMap::iterator I, E;
+
+  for (llvm::tie(I, E) = M.begin_end(R); I != E; ++I)
+    RemoveSubRegionBindings(B, *I, M);
+  
+  B = Remove(B, R);
+}
+
+const GRState *RegionStoreManager::InvalidateRegions(const GRState *state,
+                                                     const MemRegion * const *I,
+                                                     const MemRegion * const *E,
+                                                     const Expr *Ex,
+                                                     unsigned Count,
+                                                     InvalidatedSymbols *IS) {
+  ASTContext& Ctx = StateMgr.getContext();
+
+  // Get the mapping of regions -> subregions.
+  llvm::OwningPtr<RegionStoreSubRegionMap>
+    SubRegions(getRegionStoreSubRegionMap(state->getStore()));
+  
+  RegionBindings B = GetRegionBindings(state->getStore());
+
+  llvm::DenseMap<const MemRegion *, unsigned> Visited;
+  llvm::SmallVector<const MemRegion *, 10> WorkList;
+  
+  for ( ; I != E; ++I) {
+    // Strip away casts.
+    WorkList.push_back((*I)->StripCasts());
+  }
+  
+  while (!WorkList.empty()) {
+    const MemRegion *R = WorkList.back();
+    WorkList.pop_back();
+    
+    // Have we visited this region before?
+    unsigned &visited = Visited[R];
+    if (visited)
+      continue;
+    visited = 1;
+
+    // Add subregions to work list.
+    RegionStoreSubRegionMap::iterator I, E;
+    for (llvm::tie(I, E) = SubRegions->begin_end(R); I!=E; ++I)
+      WorkList.push_back(*I);
+
+    // Get the old binding.  Is it a region?  If so, add it to the worklist.
+    if (Optional<SVal> V = getDirectBinding(B, R)) {
+      if (const MemRegion *RV = V->getAsRegion())
+        WorkList.push_back(RV);
+      
+      // A symbol?  Mark it touched by the invalidation.
+      if (IS) {
+        if (SymbolRef Sym = V->getAsSymbol())
+          IS->insert(Sym);
+      }
+    }
+
+    // Symbolic region?  Mark that symbol touched by the invalidation.
+    if (IS) {
+      if (const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R))
+        IS->insert(SR->getSymbol());
+    }
+    
+    // BlockDataRegion?  If so, invalidate captured variables that are passed
+    // by reference.
+    if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
+      for (BlockDataRegion::referenced_vars_iterator
+            I = BR->referenced_vars_begin(), E = BR->referenced_vars_end() ;
+           I != E; ++I) {
+        const VarRegion *VR = *I;
+        if (VR->getDecl()->getAttr<BlocksAttr>())
+          WorkList.push_back(VR);
+      }
+      continue;
+    }
+
+    // Handle the region itself.
+    if (isa<AllocaRegion>(R) || isa<SymbolicRegion>(R)) {
+      // Invalidate the region by setting its default value to
+      // conjured symbol. The type of the symbol is irrelavant.
+      DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
+                                                           Count);
+      B = Add(B, R, BindingVal(V, BindingVal::Default));
+      continue;
+    }
+
+    if (!R->isBoundable())
+      continue;
+  
+    const TypedRegion *TR = cast<TypedRegion>(R);
+    QualType T = TR->getValueType(Ctx);
+  
+    if (const RecordType *RT = T->getAsStructureType()) {
+      const RecordDecl *RD = RT->getDecl()->getDefinition(Ctx);
+    
+      // No record definition.  There is nothing we can do.
+      if (!RD)
+        continue;
+    
+      // Invalidate the region by setting its default value to
+      // conjured symbol. The type of the symbol is irrelavant.
+      DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, Ctx.IntTy,
+                                                           Count);
+      B = Add(B, R, BindingVal(V, BindingVal::Default));
+      continue;
+    }
+  
+    if (const ArrayType *AT = Ctx.getAsArrayType(T)) {
+      // Set the default value of the array to conjured symbol.
+      DefinedOrUnknownSVal V =
+        ValMgr.getConjuredSymbolVal(R, Ex, AT->getElementType(), Count);
+      B = Add(B, R, BindingVal(V, BindingVal::Default));
+      continue;
+    }
+
+    if ((isa<FieldRegion>(R)||isa<ElementRegion>(R)||isa<ObjCIvarRegion>(R))
+        && Visited[cast<SubRegion>(R)->getSuperRegion()]) {
+      // For fields and elements whose super region has also been invalidated,
+      // only remove the old binding.  The super region will get set with a
+      // default value from which we can lazily derive a new symbolic value.
+      B = Remove(B, R);
+      continue;
+    }
+    
+    // Invalidate the binding.
+    DefinedOrUnknownSVal V = ValMgr.getConjuredSymbolVal(R, Ex, T, Count);
+    assert(SymbolManager::canSymbolicate(T) || V.isUnknown());
+    B = Add(B, R, BindingVal(V, BindingVal::Direct));
+  }
+
+  // Create a new state with the updated bindings.
+  return state->makeWithStore(B.getRoot());
+}
+
+//===----------------------------------------------------------------------===//
+// getLValueXXX methods.
+//===----------------------------------------------------------------------===//
+
+/// getLValueString - Returns an SVal representing the lvalue of a
+///  StringLiteral.  Within RegionStore a StringLiteral has an
+///  associated StringRegion, and the lvalue of a StringLiteral is the
+///  lvalue of that region.
+SVal RegionStoreManager::getLValueString(const StringLiteral* S) {
+  return loc::MemRegionVal(MRMgr.getStringRegion(S));
+}
+
+/// getLValueVar - Returns an SVal that represents the lvalue of a
+///  variable.  Within RegionStore a variable has an associated
+///  VarRegion, and the lvalue of the variable is the lvalue of that region.
+SVal RegionStoreManager::getLValueVar(const VarDecl *VD, 
+                                      const LocationContext *LC) {
+  return loc::MemRegionVal(MRMgr.getVarRegion(VD, LC));
+}
+
+SVal RegionStoreManager::getLValueIvar(const ObjCIvarDecl* D, SVal Base) {
+  return getLValueFieldOrIvar(D, Base);
+}
+
+SVal RegionStoreManager::getLValueField(const FieldDecl* D, SVal Base) {
+  return getLValueFieldOrIvar(D, Base);
+}
+
+SVal RegionStoreManager::getLValueFieldOrIvar(const Decl* D, SVal Base) {
+  if (Base.isUnknownOrUndef())
+    return Base;
+
+  Loc BaseL = cast<Loc>(Base);
+  const MemRegion* BaseR = 0;
+
+  switch (BaseL.getSubKind()) {
+  case loc::MemRegionKind:
+    BaseR = cast<loc::MemRegionVal>(BaseL).getRegion();
+    break;
+
+  case loc::GotoLabelKind:
+    // These are anormal cases. Flag an undefined value.
+    return UndefinedVal();
+
+  case loc::ConcreteIntKind:
+    // While these seem funny, this can happen through casts.
+    // FIXME: What we should return is the field offset.  For example,
+    //  add the field offset to the integer value.  That way funny things
+    //  like this work properly:  &(((struct foo *) 0xa)->f)
+    return Base;
+
+  default:
+    assert(0 && "Unhandled Base.");
+    return Base;
+  }
+
+  // NOTE: We must have this check first because ObjCIvarDecl is a subclass
+  // of FieldDecl.
+  if (const ObjCIvarDecl *ID = dyn_cast<ObjCIvarDecl>(D))
+    return loc::MemRegionVal(MRMgr.getObjCIvarRegion(ID, BaseR));
+
+  return loc::MemRegionVal(MRMgr.getFieldRegion(cast<FieldDecl>(D), BaseR));
+}
+
+SVal RegionStoreManager::getLValueElement(QualType elementType, SVal Offset, 
+                                          SVal Base) {
+
+  // If the base is an unknown or undefined value, just return it back.
+  // FIXME: For absolute pointer addresses, we just return that value back as
+  //  well, although in reality we should return the offset added to that
+  //  value.
+  if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
+    return Base;
+
+  // Only handle integer offsets... for now.
+  if (!isa<nonloc::ConcreteInt>(Offset))
+    return UnknownVal();
+
+  const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
+
+  // Pointer of any type can be cast and used as array base.
+  const ElementRegion *ElemR = dyn_cast<ElementRegion>(BaseRegion);
+
+  // Convert the offset to the appropriate size and signedness.
+  Offset = ValMgr.convertToArrayIndex(Offset);
+
+  if (!ElemR) {
+    //
+    // If the base region is not an ElementRegion, create one.
+    // This can happen in the following example:
+    //
+    //   char *p = __builtin_alloc(10);
+    //   p[1] = 8;
+    //
+    //  Observe that 'p' binds to an AllocaRegion.
+    //
+    return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
+                                                    BaseRegion, getContext()));
+  }
+
+  SVal BaseIdx = ElemR->getIndex();
+
+  if (!isa<nonloc::ConcreteInt>(BaseIdx))
+    return UnknownVal();
+
+  const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
+  const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
+  assert(BaseIdxI.isSigned());
+
+  // Compute the new index.
+  SVal NewIdx = nonloc::ConcreteInt(getBasicVals().getValue(BaseIdxI + OffI));
+
+  // Construct the new ElementRegion.
+  const MemRegion *ArrayR = ElemR->getSuperRegion();
+  return loc::MemRegionVal(MRMgr.getElementRegion(elementType, NewIdx, ArrayR,
+                                                  getContext()));
+}
+
+//===----------------------------------------------------------------------===//
+// Extents for regions.
+//===----------------------------------------------------------------------===//
+
+DefinedOrUnknownSVal RegionStoreManager::getSizeInElements(const GRState *state,
+                                                           const MemRegion *R,
+                                                           QualType EleTy) {
+
+  switch (R->getKind()) {
+    case MemRegion::CXXThisRegionKind:
+      assert(0 && "Cannot get size of 'this' region");      
+    case MemRegion::GenericMemSpaceRegionKind:
+    case MemRegion::StackLocalsSpaceRegionKind:
+    case MemRegion::StackArgumentsSpaceRegionKind:
+    case MemRegion::HeapSpaceRegionKind:
+    case MemRegion::GlobalsSpaceRegionKind:
+    case MemRegion::UnknownSpaceRegionKind:
+      assert(0 && "Cannot index into a MemSpace");
+      return UnknownVal();
+
+    case MemRegion::FunctionTextRegionKind:
+    case MemRegion::BlockTextRegionKind:
+    case MemRegion::BlockDataRegionKind:
+      // Technically this can happen if people do funny things with casts.
+      return UnknownVal();
+
+      // Not yet handled.
+    case MemRegion::AllocaRegionKind:
+    case MemRegion::CompoundLiteralRegionKind:
+    case MemRegion::ElementRegionKind:
+    case MemRegion::FieldRegionKind:
+    case MemRegion::ObjCIvarRegionKind:
+    case MemRegion::CXXObjectRegionKind:
+      return UnknownVal();
+
+    case MemRegion::SymbolicRegionKind: {
+      const SVal *Size = state->get<RegionExtents>(R);
+      if (!Size)
+        return UnknownVal();
+      const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(Size);
+      if (!CI)
+        return UnknownVal();
+
+      CharUnits RegionSize = 
+        CharUnits::fromQuantity(CI->getValue().getSExtValue());
+      CharUnits EleSize = getContext().getTypeSizeInChars(EleTy);
+      assert(RegionSize % EleSize == 0);
+
+      return ValMgr.makeIntVal(RegionSize / EleSize, false);
+    }
+
+    case MemRegion::StringRegionKind: {
+      const StringLiteral* Str = cast<StringRegion>(R)->getStringLiteral();
+      // We intentionally made the size value signed because it participates in
+      // operations with signed indices.
+      return ValMgr.makeIntVal(Str->getByteLength()+1, false);
+    }
+
+    case MemRegion::VarRegionKind: {
+      const VarRegion* VR = cast<VarRegion>(R);
+      // Get the type of the variable.
+      QualType T = VR->getDesugaredValueType(getContext());
+
+      // FIXME: Handle variable-length arrays.
+      if (isa<VariableArrayType>(T))
+        return UnknownVal();
+
+      if (const ConstantArrayType* CAT = dyn_cast<ConstantArrayType>(T)) {
+        // return the size as signed integer.
+        return ValMgr.makeIntVal(CAT->getSize(), false);
+      }
+
+      // Clients can use ordinary variables as if they were arrays.  These
+      // essentially are arrays of size 1.
+      return ValMgr.makeIntVal(1, false);
+    }
+  }
+
+  assert(0 && "Unreachable");
+  return UnknownVal();
+}
+
+const GRState *RegionStoreManager::setExtent(const GRState *state,
+                                             const MemRegion *region,
+                                             SVal extent) {
+  return state->set<RegionExtents>(region, extent);
+}
+
+//===----------------------------------------------------------------------===//
+// Location and region casting.
+//===----------------------------------------------------------------------===//
+
+/// ArrayToPointer - Emulates the "decay" of an array to a pointer
+///  type.  'Array' represents the lvalue of the array being decayed
+///  to a pointer, and the returned SVal represents the decayed
+///  version of that lvalue (i.e., a pointer to the first element of
+///  the array).  This is called by GRExprEngine when evaluating casts
+///  from arrays to pointers.
+SVal RegionStoreManager::ArrayToPointer(Loc Array) {
+  if (!isa<loc::MemRegionVal>(Array))
+    return UnknownVal();
+
+  const MemRegion* R = cast<loc::MemRegionVal>(&Array)->getRegion();
+  const TypedRegion* ArrayR = dyn_cast<TypedRegion>(R);
+
+  if (!ArrayR)
+    return UnknownVal();
+
+  // Strip off typedefs from the ArrayRegion's ValueType.
+  QualType T = ArrayR->getValueType(getContext()).getDesugaredType();
+  ArrayType *AT = cast<ArrayType>(T);
+  T = AT->getElementType();
+
+  SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
+  return loc::MemRegionVal(MRMgr.getElementRegion(T, ZeroIdx, ArrayR,
+                                                  getContext()));
+}
+
+//===----------------------------------------------------------------------===//
+// Pointer arithmetic.
+//===----------------------------------------------------------------------===//
+
+SVal RegionStoreManager::EvalBinOp(const GRState *state,
+                                   BinaryOperator::Opcode Op, Loc L, NonLoc R,
+                                   QualType resultTy) {
+  // Assume the base location is MemRegionVal.
+  if (!isa<loc::MemRegionVal>(L))
+    return UnknownVal();
+
+  const MemRegion* MR = cast<loc::MemRegionVal>(L).getRegion();
+  const ElementRegion *ER = 0;
+
+  switch (MR->getKind()) {
+    case MemRegion::SymbolicRegionKind: {
+      const SymbolicRegion *SR = cast<SymbolicRegion>(MR);
+      SymbolRef Sym = SR->getSymbol();
+      QualType T = Sym->getType(getContext());
+      QualType EleTy;
+
+      if (const PointerType *PT = T->getAs<PointerType>())
+        EleTy = PT->getPointeeType();
+      else
+        EleTy = T->getAs<ObjCObjectPointerType>()->getPointeeType();
+
+      SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
+      ER = MRMgr.getElementRegion(EleTy, ZeroIdx, SR, getContext());
+      break;
+    }
+    case MemRegion::AllocaRegionKind: {
+      const AllocaRegion *AR = cast<AllocaRegion>(MR);
+      QualType T = getContext().CharTy; // Create an ElementRegion of bytes.
+      QualType EleTy = T->getAs<PointerType>()->getPointeeType();
+      SVal ZeroIdx = ValMgr.makeZeroArrayIndex();
+      ER = MRMgr.getElementRegion(EleTy, ZeroIdx, AR, getContext());
+      break;
+    }
+
+    case MemRegion::ElementRegionKind: {
+      ER = cast<ElementRegion>(MR);
+      break;
+    }
+
+    // Not yet handled.
+    case MemRegion::VarRegionKind:
+    case MemRegion::StringRegionKind: {
+      
+    }
+    // Fall-through.
+    case MemRegion::CompoundLiteralRegionKind:
+    case MemRegion::FieldRegionKind:
+    case MemRegion::ObjCIvarRegionKind:
+    case MemRegion::CXXObjectRegionKind:
+      return UnknownVal();
+
+    case MemRegion::FunctionTextRegionKind:
+    case MemRegion::BlockTextRegionKind:
+    case MemRegion::BlockDataRegionKind:
+      // Technically this can happen if people do funny things with casts.
+      return UnknownVal();
+
+    case MemRegion::CXXThisRegionKind:
+      assert(0 &&
+             "Cannot perform pointer arithmetic on implicit argument 'this'");
+    case MemRegion::GenericMemSpaceRegionKind:
+    case MemRegion::StackLocalsSpaceRegionKind:
+    case MemRegion::StackArgumentsSpaceRegionKind:
+    case MemRegion::HeapSpaceRegionKind:
+    case MemRegion::GlobalsSpaceRegionKind:
+    case MemRegion::UnknownSpaceRegionKind:
+      assert(0 && "Cannot perform pointer arithmetic on a MemSpace");
+