19 files changed, 768 insertions, 468 deletions

diff --git a/include/clang/Analysis/PathSensitive/Environment.h b/include/clang/Analysis/PathSensitive/Environment.h
index 9c9dc54886..8e1b97a3be 100644
--- a/include/clang/Analysis/PathSensitive/Environment.h
+++ b/include/clang/Analysis/PathSensitive/Environment.h
@@ -19,6 +19,7 @@
 #include "clang/Analysis/PathSensitive/Store.h"
 
 #include "llvm/ADT/ImmutableMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "clang/Analysis/PathSensitive/RValues.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/ADT/FoldingSet.h"
@@ -138,11 +139,10 @@ public:
   Environment SetRVal(const Environment& Env, Expr* E, RVal V,
                       bool isBlkExpr, bool Invalidate);
 
-  Environment RemoveDeadBindings(Environment Env, 
-                                 Stmt* Loc,
-                                 const LiveVariables& Liveness,
-                                 StoreManager::DeclRootsTy& DRoots,
-                                 StoreManager::LiveSymbolsTy& LSymbols);
+  Environment RemoveDeadBindings(Environment Env, Stmt* Loc,
+                              const LiveVariables& Liveness,
+                              llvm::SmallVectorImpl<const MemRegion*>& DRoots,
+                              StoreManager::LiveSymbolsTy& LSymbols);
 };
   
 } // end clang namespace
diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h
index 5b713d9c18..0bcc13781f 100644
--- a/include/clang/Analysis/PathSensitive/GRExprEngine.h
+++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h
@@ -410,6 +410,10 @@ public:
     return SetRVal(St, const_cast<Expr*>(Ex), V);
   }
   
+  LVal getLVal(VarDecl* V) {
+    return getStateManager().getLVal(V);
+  }    
+  
 protected:
  
   const GRState* SetBlkExprRVal(const GRState* St, Expr* Ex, RVal V) {
diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h
index fd81a86946..992174c2a3 100644
--- a/include/clang/Analysis/PathSensitive/GRState.h
+++ b/include/clang/Analysis/PathSensitive/GRState.h
@@ -19,6 +19,7 @@
 #include "clang/Analysis/PathSensitive/Environment.h"
 #include "clang/Analysis/PathSensitive/Store.h"
 #include "clang/Analysis/PathSensitive/ConstraintManager.h"
+#include "clang/Analysis/PathSensitive/MemRegion.h"
 #include "clang/Analysis/PathSensitive/RValues.h"
 #include "clang/Analysis/PathSensitive/GRCoreEngine.h"
 #include "clang/AST/Expr.h"
@@ -133,20 +134,6 @@ public:
   }
   
   // Iterators.
-
-  // FIXME: We'll be removing the VarBindings iterator very soon.  Right now
-  //  it assumes that Store is a VarBindingsTy.
-  typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy;
-  typedef VarBindingsTy::iterator vb_iterator;
-  vb_iterator vb_begin() const {
-    VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St));
-    return B.begin();
-  }
-  vb_iterator vb_end() const {
-    VarBindingsTy B(static_cast<const VarBindingsTy::TreeTy*>(St));
-    return B.end();
-  }
-    
   typedef Environment::seb_iterator seb_iterator;
   seb_iterator seb_begin() const { return Env.seb_begin(); }
   seb_iterator seb_end() const { return Env.beb_end(); }
@@ -249,6 +236,7 @@ private:
   EnvironmentManager                   EnvMgr;
   llvm::OwningPtr<StoreManager>        StMgr;
   llvm::OwningPtr<ConstraintManager>   ConstraintMgr;
+  MemRegionManager                     MRMgr;
   GRState::IntSetTy::Factory           ISetFactory;
   
   GRState::GenericDataMap::Factory     GDMFactory;
@@ -273,10 +261,6 @@ private:
   /// Alloc - A BumpPtrAllocator to allocate states.
   llvm::BumpPtrAllocator& Alloc;
   
-  /// DRoots - A vector to hold of worklist used by RemoveDeadSymbols.
-  ///  This vector is persistent because it is reused over and over.
-  StoreManager::DeclRootsTy DRoots;
-  
   /// CurrentStmt - The block-level statement currently being visited.  This
   ///  is set by GRExprEngine.
   Stmt* CurrentStmt;
@@ -297,10 +281,10 @@ private:
   Environment RemoveBlkExpr(const Environment& Env, Expr* E) {
     return EnvMgr.RemoveBlkExpr(Env, E);
   }
-   
+  
   // FIXME: Remove when we do lazy initializaton of variable bindings.
   const GRState* BindVar(const GRState* St, VarDecl* D, RVal V) {
-    return SetRVal(St, lval::DeclVal(D), V);
+    return SetRVal(St, getLVal(D), V);
   }
     
 public:
@@ -313,7 +297,8 @@ public:
                  ConstraintManagerCreator CreateConstraintManager,
                  llvm::BumpPtrAllocator& alloc, CFG& c, LiveVariables& L) 
   : EnvMgr(alloc),
-    ISetFactory(alloc), 
+    MRMgr(alloc),
+    ISetFactory(alloc),
     GDMFactory(alloc),
     BasicVals(Ctx, alloc),
     SymMgr(alloc),
@@ -334,6 +319,7 @@ public:
   SymbolManager& getSymbolManager() { return SymMgr; }
   LiveVariables& getLiveVariables() { return Liveness; }
   llvm::BumpPtrAllocator& getAllocator() { return Alloc; }
+  MemRegionManager& getRegionManager() { return MRMgr; }
 
   typedef StoreManager::DeadSymbolsTy DeadSymbolsTy;
 
@@ -350,6 +336,17 @@ public:
     return getPersistentState(NewSt);
   }
 
+  
+  // Utility methods for getting regions.
+  
+  VarRegion* getRegion(const VarDecl* D) {
+    return MRMgr.getVarRegion(D);
+  }
+  
+  lval::MemRegionVal getLVal(const VarDecl* D) {
+    return lval::MemRegionVal(getRegion(D));
+  }
+  
   // Methods that query & manipulate the Environment.
   
   RVal GetRVal(const GRState* St, Expr* Ex) {
@@ -394,19 +391,17 @@ public:
   // Methods that manipulate the GDM.
   const GRState* addGDM(const GRState* St, void* Key, void* Data);
   
-  // Methods that query & manipulate the Store.
-  
-  /// getBindings - Returns all store bindings in the specified state that bind
-  ///  to the specified symbolic value.
-  void getBindings(llvm::SmallVectorImpl<store::Binding>& bindings,
-                   const GRState* St, SymbolID Sym) {
-    StMgr->getBindings(bindings, St->getStore(), Sym);    
+  // Methods that query or create regions.
+  bool hasStackStorage(const MemRegion* R) {
+    return getRegionManager().hasStackStorage(R);
   }
   
-  /// BindingAsString - Returns a string representing the given store binding.
-  std::string BindingAsString(store::Binding binding) {
-    return StMgr->BindingAsString(binding);
+  // Methods that query & manipulate the Store.
+
+  void iterBindings(const GRState* state, StoreManager::BindingsHandler& F) {
+    StMgr->iterBindings(state->getStore(), F);
   }
+    
   
   RVal GetRVal(const GRState* St, LVal LV, QualType T = QualType()) {
     return StMgr->GetRVal(St->getStore(), LV, T);
diff --git a/include/clang/Analysis/PathSensitive/MemRegion.h b/include/clang/Analysis/PathSensitive/MemRegion.h
new file mode 100644
index 0000000000..79705613ab
--- /dev/null
+++ b/include/clang/Analysis/PathSensitive/MemRegion.h
@@ -0,0 +1,267 @@
+//== MemRegion.h - Abstract memory regions for static analysis --*- 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 MemRegion and its subclasses.  MemRegion defines a
+//  partially-typed abstraction of memory useful for path-sensitive dataflow
+//  analyses.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_MEMREGION_H
+#define LLVM_CLANG_ANALYSIS_MEMREGION_H
+
+#include "llvm/Support/Casting.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/Support/Allocator.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclObjC.h"
+#include <string>
+
+namespace llvm { class raw_ostream; }
+
+namespace clang {
+ 
+class MemRegionManager;
+  
+      
+/// MemRegion - The root abstract class for all memory regions.
+class MemRegion : public llvm::FoldingSetNode {
+public:
+  enum Kind { MemSpaceRegionKind,
+              // Typed regions.
+              BEG_TYPED_REGIONS,
+              VarRegionKind, FieldRegionKind, ObjCIvarRegionKind,
+              AnonTypedRegionKind,
+              END_TYPED_REGIONS };  
+private:
+  const Kind kind;
+  
+protected:
+  MemRegion(Kind k) : kind(k) {}
+  virtual ~MemRegion();
+
+public:
+  // virtual MemExtent getExtent(MemRegionManager& mrm) const = 0;
+  virtual const MemRegion* getSuperRegion() const = 0;
+  virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
+  
+  std::string getString() const;
+  virtual void print(llvm::raw_ostream& os) const;  
+  
+  Kind getKind() const { return kind; }  
+  static bool classof(const MemRegion*) { return true; }
+};
+  
+/// MemSpaceRegion - A memory region that represents and "memory space";
+///  for example, the set of global variables, the stack frame, etc.
+class MemSpaceRegion : public MemRegion {
+  friend class MemRegionManager;
+  MemSpaceRegion() : MemRegion(MemSpaceRegionKind) {}
+  
+public:
+  //RegionExtent getExtent() const { return UndefinedExtent(); }
+
+  const MemRegion* getSuperRegion() const {
+    return 0;
+  }
+    
+  //static void ProfileRegion(llvm::FoldingSetNodeID& ID);
+  void Profile(llvm::FoldingSetNodeID& ID) const;
+
+  static bool classof(const MemRegion* R) {
+    return R->getKind() == MemSpaceRegionKind;
+  }
+};
+
+/// TypedRegion - An abstract class representing regions that are typed.
+class TypedRegion : public MemRegion {
+protected:
+  const MemRegion* superRegion;
+
+  TypedRegion(const MemRegion* sReg, Kind k)
+    : MemRegion(k), superRegion(sReg) {};
+  
+public:
+  virtual QualType getType() const = 0;
+  
+  // MemExtent getExtent(MemRegionManager& mrm) const;
+  const MemRegion* getSuperRegion() const {
+    return superRegion;
+  }
+  
+  static bool classof(const MemRegion* R) {
+    unsigned k = R->getKind();
+    return k > BEG_TYPED_REGIONS && k < END_TYPED_REGIONS;
+  }
+};
+
+/// AnonTypedRegion - An "anonymous" region that simply types a chunk
+///  of memory.
+class AnonTypedRegion : public TypedRegion {
+  QualType T;
+
+  friend class MemRegionManager;
+  
+  AnonTypedRegion(QualType t, MemRegion* sreg)
+    : TypedRegion(sreg, AnonTypedRegionKind), T(t) {}
+
+  static void ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T,
+                      const MemRegion* superRegion);
+  
+public:
+  QualType getType() const { return T; }
+  
+
+  void Profile(llvm::FoldingSetNodeID& ID) const;
+  
+  static bool classof(const MemRegion* R) {
+    return R->getKind() == AnonTypedRegionKind;
+  }
+};
+
+class DeclRegion : public TypedRegion {
+protected:
+  const Decl* D;
+
+  DeclRegion(const Decl* d, MemRegion* sReg, Kind k)
+    : TypedRegion(sReg, k), D(d) {}
+
+  static void ProfileRegion(llvm::FoldingSetNodeID& ID, const Decl* D,
+                      const MemRegion* superRegion, Kind k);
+  
+public:  
+  void Profile(llvm::FoldingSetNodeID& ID) const;
+};
+  
+class VarRegion : public DeclRegion {
+  friend class MemRegionManager;
+  
+  VarRegion(const VarDecl* vd, MemRegion* sReg)
+    : DeclRegion(vd, sReg, VarRegionKind) {}
+
+  static void ProfileRegion(llvm::FoldingSetNodeID& ID, VarDecl* VD,
+                      const MemRegion* superRegion) {
+    DeclRegion::ProfileRegion(ID, VD, superRegion, VarRegionKind);
+  }
+  
+public:  
+  const VarDecl* getDecl() const { return cast<VarDecl>(D); }
+  QualType getType() const { return getDecl()->getType(); }
+  
+  void print(llvm::raw_ostream& os) const;
+  
+  static bool classof(const MemRegion* R) {
+    return R->getKind() == VarRegionKind;
+  }  
+};
+
+class FieldRegion : public DeclRegion {
+  friend class MemRegionManager;
+
+  FieldRegion(const FieldDecl* fd, MemRegion* sReg)
+    : DeclRegion(fd, sReg, FieldRegionKind) {}
+
+  static void ProfileRegion(llvm::FoldingSetNodeID& ID, FieldDecl* FD,
+                      const MemRegion* superRegion) {
+    DeclRegion::ProfileRegion(ID, FD, superRegion, FieldRegionKind);
+  }
+  
+public:
+  const FieldDecl* getDecl() const { return cast<FieldDecl>(D); }
+  QualType getType() const { return getDecl()->getType(); }
+    
+  static bool classof(const MemRegion* R) {
+    return R->getKind() == FieldRegionKind;
+  }
+};
+  
+class ObjCIvarRegion : public DeclRegion {
+  
+  friend class MemRegionManager;
+  
+  ObjCIvarRegion(const ObjCIvarDecl* ivd, MemRegion* sReg)
+    : DeclRegion(ivd, sReg, ObjCIvarRegionKind) {}
+
+  static void ProfileRegion(llvm::FoldingSetNodeID& ID, ObjCIvarDecl* ivd,
+                      const MemRegion* superRegion) {
+    DeclRegion::ProfileRegion(ID, ivd, superRegion, ObjCIvarRegionKind);
+  }
+  
+public:
+  const ObjCIvarDecl* getDecl() const { return cast<ObjCIvarDecl>(D); }
+  QualType getType() const { return getDecl()->getType(); }
+  
+  static bool classof(const MemRegion* R) {
+    return R->getKind() == ObjCIvarRegionKind;
+  }
+};
+  
+//===----------------------------------------------------------------------===//
+// MemRegionManager - Factory object for creating regions.
+//===----------------------------------------------------------------------===//
+
+class MemRegionManager {
+  llvm::BumpPtrAllocator& A;
+  llvm::FoldingSet<MemRegion> Regions;
+  
+  MemSpaceRegion* globals;
+  MemSpaceRegion* stack;
+  MemSpaceRegion* heap;
+  
+public:
+  MemRegionManager(llvm::BumpPtrAllocator& a)
+  : A(a), globals(0), stack(0), heap(0) {}
+  
+  ~MemRegionManager() {}
+  
+  /// getStackRegion - Retrieve the memory region associated with the
+  ///  current stack frame.
+  MemSpaceRegion* getStackRegion();
+  
+  /// getGlobalsRegion - Retrieve the memory region associated with
+  ///  all global variables.
+  MemSpaceRegion* getGlobalsRegion();
+  
+  /// getHeapRegion - Retrieve the memory region associated with the
+  ///  generic "heap".
+  MemSpaceRegion* getHeapRegion();
+  
+  /// getVarRegion - Retrieve or create the memory region associated with
+  ///  a specified VarDecl.  'superRegion' corresponds to the containing
+  ///  memory region, and 'off' is the offset within the containing region.
+  VarRegion* getVarRegion(const VarDecl* vd, MemRegion* superRegion);
+  
+  VarRegion* getVarRegion(const VarDecl* vd) {
+    return getVarRegion(vd, vd->hasLocalStorage() ? getStackRegion() 
+                        : getGlobalsRegion());
+  }
+  
+  /// getFieldRegion - Retrieve or create the memory region associated with
+  ///  a specified FieldDecl.  'superRegion' corresponds to the containing
+  ///  memory region (which typically represents the memory representing
+  ///  a structure or class).
+  FieldRegion* getFieldRegion(const FieldDecl* fd, MemRegion* superRegion);
+  
+  /// getObjCIvarRegion - Retrieve or create the memory region associated with
+  ///   a specified Objective-c instance variable.  'superRegion' corresponds
+  ///   to the containing region (which typically represents the Objective-C
+  ///   object).
+  ObjCIvarRegion* getObjCIvarRegion(const ObjCIvarDecl* ivd,
+                                    MemRegion* superRegion);
+  
+  bool hasStackStorage(const MemRegion* R);
+  
+private:
+  MemSpaceRegion* LazyAllocate(MemSpaceRegion*& region);
+};
+
+
+  
+} // end clang namespace
+#endif
diff --git a/include/clang/Analysis/PathSensitive/RValues.h b/include/clang/Analysis/PathSensitive/RValues.h
index 9034c0d4ae..82e5119373 100644
--- a/include/clang/Analysis/PathSensitive/RValues.h
+++ b/include/clang/Analysis/PathSensitive/RValues.h
@@ -24,6 +24,9 @@
 
 namespace clang {
   
+class MemRegion;
+class GRStateManager;
+  
 class RVal {
 public:
   enum BaseKind { UndefinedKind, UnknownKind, LValKind, NonLValKind };
@@ -92,7 +95,7 @@ public:
   symbol_iterator symbol_begin() const;
   symbol_iterator symbol_end() const;  
   
-  static RVal MakeVal(BasicValueFactory& BasicVals, DeclRefExpr* E);
+  static RVal MakeVal(GRStateManager& SMgr, DeclRefExpr* E);
   
   // Implement isa<T> support.
   static inline bool classof(const RVal*) { return true; }
@@ -285,7 +288,7 @@ public:
 
 namespace lval {
   
-enum Kind { SymbolValKind, GotoLabelKind, DeclValKind, FuncValKind,
+enum Kind { SymbolValKind, GotoLabelKind, MemRegionKind, FuncValKind,
             ConcreteIntKind, StringLiteralValKind, FieldOffsetKind,
             ArrayOffsetKind };
 
@@ -327,30 +330,30 @@ public:
 };
   
 
-class DeclVal : public LVal {
+class MemRegionVal : public LVal {
 public:
-  DeclVal(const VarDecl* vd) : LVal(DeclValKind, vd) {}
-  
-  VarDecl* getDecl() const {
-    return static_cast<VarDecl*>(Data);
+  MemRegionVal(const MemRegion* r) : LVal(MemRegionKind, r) {}
+
+  MemRegion* getRegion() const {
+    return static_cast<MemRegion*>(Data);
   }
   
-  inline bool operator==(const DeclVal& R) const {
-    return getDecl() == R.getDecl();
+  inline bool operator==(const MemRegionVal& R) const {
+    return getRegion() == R.getRegion();
   }
   
-  inline bool operator!=(const DeclVal& R) const {
-    return getDecl() != R.getDecl();
+  inline bool operator!=(const MemRegionVal& R) const {
+    return getRegion() != R.getRegion();
   }
   
   // Implement isa<T> support.
   static inline bool classof(const RVal* V) {
     return V->getBaseKind() == LValKind &&
-           V->getSubKind() == DeclValKind;
+           V->getSubKind() == MemRegionKind;
   }
   
   static inline bool classof(const LVal* V) {
-    return V->getSubKind() == DeclValKind;
+    return V->getSubKind() == MemRegionKind;
   }    
 };
 
diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h
index fc9b7f3d07..4300954eac 100644
--- a/include/clang/Analysis/PathSensitive/Store.h
+++ b/include/clang/Analysis/PathSensitive/Store.h
@@ -19,127 +19,21 @@
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
-#include <vector>
 #include <iosfwd>
 
 namespace clang {
   
 typedef const void* Store;
   
-namespace store {
-  /// Region - A region represents an abstract chunk of memory.  Subclasses
-  ///  of StoreManager are responsible for defining the particular semantics
-  ///  of Region for the store they represent.
-  class Region {
-  protected:
-    const void* Data;
-    Region(const void* data) : Data(data) {}
-  public:
-    Region() : Data(0) {}
-  };
-  
-  /// Binding - A "binding" represents a binding of a value to an abstract
-  ///  chunk of memory (which is represented by a region).  Subclasses of
-  ///  StoreManager are responsible for defining the particular semantics
-  ///  of a Binding.
-  class Binding {
-  protected:
-    const void* first;
-    const void* second;
-    Binding(const void* f, const void* s = 0) : first(f), second(s) {}
-  public:
-    Binding() : first(0), second(0) {}
-    operator bool() const { return first || second; }
-  };
-  
-  /// RegionExtent - Represents the size, or extent, or an abstract memory
-  ///  chunk (a region).  Sizes are in bits.  RegionExtent is essentially a
-  ///  variant with three subclasses: UnknownExtent, FixedExtent,
-  ///  and SymbolicExtent.  
-  class RegionExtent {
-  public:
-    enum Kind { Unknown = 0, Fixed = 0, Sym = 1 };
-    
-  protected:
-    const uintptr_t Raw;
-    RegionExtent(uintptr_t raw, Kind k) : Raw(raw | k) {}
-    uintptr_t getData() const { return Raw & ~0x1; }
-    
-  public:
-    // Folding-set profiling.
-    void Profile(llvm::FoldingSetNodeID& ID) const {
-      ID.AddPointer((void*) Raw);
-    }  
-    // Comparing extents.
-    bool operator==(const RegionExtent& R) const {
-      return Raw == R.Raw;
-    }
-    bool operator!=(const RegionExtent& R) const {
-      return Raw != R.Raw;
-    }  
-    // Implement isa<T> support.
-    Kind getKind() const { return Kind(Raw & 0x1); }
-    uintptr_t getRaw() const { return Raw; }
-    
-    static inline bool classof(const RegionExtent*) {
-      return true;
-    }
-  };
-  
-  /// UnknownExtent - Represents a region extent with no available information
-  ///  about the size of the region.
-  class UnknownExtent : public RegionExtent {
-  public:
-    UnknownExtent() : RegionExtent(0,Unknown) {}
-    
-    // Implement isa<T> support.
-    static inline bool classof(const RegionExtent* E) {
-      return E->getRaw() == 0;
-    }  
-  };
-  
-  /// FixedExtent - Represents a region extent with a known fixed size.
-  ///  Typically FixedExtents are used to represent the size of variables, but
-  ///  they can also be used to represent the size of a constant-sized array.
-  class FixedExtent : public RegionExtent {
-  public:
-    FixedExtent(const llvm::APSInt& X) : RegionExtent((uintptr_t) &X, Fixed) {}
-    
-    const llvm::APSInt& getInt() const {
-      return *((llvm::APSInt*) getData());
-    }
-    
-    // Implement isa<T> support.
-    static inline bool classof(const RegionExtent* E) {
-      return E->getKind() == Fixed && E->getRaw() != 0;
-    }
-  };
-  
-  /// SymbolicExtent - Represents the extent of a region where the extent
-  ///  itself is a symbolic value.  These extents can be used to represent
-  ///  the sizes of dynamically allocated chunks of memory with variable size.
-  class SymbolicExtent : public RegionExtent {
-  public:
-    SymbolicExtent(SymbolID S) : RegionExtent(S.getNumber() << 1, Sym) {}
-    
-    SymbolID getSymbol() const { return SymbolID(getData() >> 1); }
-    
-    // Implement isa<T> support.
-    static inline bool classof(const RegionExtent* E) {
-      return E->getKind() == Sym;
-    }  
-  };
-} // end store namespace
-  
 class GRStateManager;
 class LiveVariables;
 class Stmt;
+class MemRegion;
   
 class StoreManager {
 public:
   typedef llvm::SmallSet<SymbolID, 20>      LiveSymbolsTy;
   typedef llvm::DenseSet<SymbolID>          DeadSymbolsTy;
-  typedef std::vector<ValueDecl*>           DeclRootsTy;
   
   virtual ~StoreManager() {}
   virtual RVal GetRVal(Store St, LVal LV, QualType T = QualType()) = 0;
@@ -147,10 +41,10 @@ public:
   virtual Store Remove(Store St, LVal LV) = 0;
   virtual Store getInitialStore(GRStateManager& StateMgr) = 0;
   
-  virtual Store RemoveDeadBindings(Store store, Stmt* Loc,
-                                   const LiveVariables& Live,
-                                   DeclRootsTy& DRoots, LiveSymbolsTy& LSymbols,                                  
-                                   DeadSymbolsTy& DSymbols) = 0;
+  virtual Store
+  RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live,
+                     llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
+                     LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols) = 0;
 
   virtual Store AddDecl(Store store, GRStateManager& StMgr,
                         const VarDecl* VD, Expr* Ex, 
@@ -163,29 +57,14 @@ public:
   public:    
     virtual ~BindingsHandler();
     virtual bool HandleBinding(StoreManager& SMgr, Store store,
-                               store::Binding binding) = 0;
+                               MemRegion* R, RVal val) = 0;
   };
   
   /// iterBindings - Iterate over the bindings in the Store.
-  virtual void iterBindings(Store store, BindingsHandler& f) = 0;
-  
-  /// getBindings - Returns all bindings in the specified store that bind
-  ///  to the specified symbolic value.
-  void getBindings(llvm::SmallVectorImpl<store::Binding>& bindings,
-                   Store store, SymbolID Sym);
-  
-  /// BindingAsString - Returns a string representing the given binding.
-  virtual std::string BindingAsString(store::Binding binding) = 0;
-  
-  /// getExtent - Returns the size of the region in bits.
-  virtual store::RegionExtent getExtent(store::Region R) = 0;
-
-  /// getRVal - Returns the bound RVal for a given binding.
-  virtual RVal getRVal(Store store, store::Binding binding) = 0;
+  virtual void iterBindings(Store store, BindingsHandler& f) = 0;  
 };
   
 StoreManager* CreateBasicStoreManager(GRStateManager& StMgr);
-
   
 } // end clang namespace
 
diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp
index 0576eaf2a1..66bf082b13 100644
--- a/lib/Analysis/BasicConstraintManager.cpp
+++ b/lib/Analysis/BasicConstraintManager.cpp
@@ -129,7 +129,7 @@ const GRState* BasicConstraintManager::AssumeAux(const GRState* St, LVal Cond,
       return AssumeSymEQ(St, cast<lval::SymbolVal>(Cond).getSymbol(),
                          BasicVals.getZeroWithPtrWidth(), isFeasible);
 
-  case lval::DeclValKind:
+  case lval::MemRegionKind:
   case lval::FuncValKind:
   case lval::GotoLabelKind:
   case lval::StringLiteralValKind:
diff --git a/lib/Analysis/BasicObjCFoundationChecks.cpp b/lib/Analysis/BasicObjCFoundationChecks.cpp
index 521f317d63..b3f534d1af 100644
--- a/lib/Analysis/BasicObjCFoundationChecks.cpp
+++ b/lib/Analysis/BasicObjCFoundationChecks.cpp
@@ -20,6 +20,7 @@
 #include "clang/Analysis/PathSensitive/GRExprEngine.h"
 #include "clang/Analysis/PathSensitive/GRState.h"
 #include "clang/Analysis/PathSensitive/BugReporter.h"
+#include "clang/Analysis/PathSensitive/MemRegion.h"
 #include "clang/Analysis/PathDiagnostic.h"
 #include "clang/Analysis/LocalCheckers.h"
 
@@ -366,7 +367,7 @@ public:
   
 private:
   
-  void AddError(VarDecl* V, Expr* Ex, ExplodedNode<GRState> *N,
+  void AddError(TypedRegion* R, Expr* Ex, ExplodedNode<GRState> *N,
                 uint64_t SourceSize, uint64_t TargetSize, uint64_t NumberKind);  
 };
 } // end anonymous namespace
@@ -497,12 +498,17 @@ bool AuditCFNumberCreate::Audit(ExplodedNode<GRState>* N,GRStateManager&){
   
   // FIXME: Eventually we should handle arbitrary locations.  We can do this
   //  by having an enhanced memory model that does low-level typing.
-  lval::DeclVal* LV = dyn_cast<lval::DeclVal>(&TheValueExpr);
+  lval::MemRegionVal* LV = dyn_cast<lval::MemRegionVal>(&TheValueExpr);
 
   if (!LV)
     return false;
   
-  QualType T = Ctx.getCanonicalType(LV->getDecl()->getType());
+  TypedRegion* R = dyn_cast<TypedRegion>(LV->getRegion());
+  if (!R)
+    return false;
+  
+  
+  QualType T = Ctx.getCanonicalType(R->getType());
   
   // FIXME: If the pointee isn't an integer type, should we flag a warning?
   //  People can do weird stuff with pointers.
@@ -517,14 +523,14 @@ bool AuditCFNumberCreate::Audit(ExplodedNode<GRState>* N,GRStateManager&){
   if (SourceSize == TargetSize)
     return false;
     
-  AddError(LV->getDecl(), CE->getArg(2), N, SourceSize, TargetSize, NumberKind);
+  AddError(R, CE->getArg(2), N, SourceSize, TargetSize, NumberKind);
   
   // FIXME: We can actually create an abstract "CFNumber" object that has
   //  the bits initialized to the provided values.
   return SourceSize < TargetSize;
 }
 
-void AuditCFNumberCreate::AddError(VarDecl* V, Expr* Ex,
+void AuditCFNumberCreate::AddError(TypedRegion* R, Expr* Ex,
                                    ExplodedNode<GRState> *N,
                                    uint64_t SourceSize, uint64_t TargetSize,
                                    uint64_t NumberKind) {
diff --git a/lib/Analysis/BasicStore.cpp b/lib/Analysis/BasicStore.cpp
index 97566798c0..4616143d13 100644
--- a/lib/Analysis/BasicStore.cpp
+++ b/lib/Analysis/BasicStore.cpp
@@ -18,10 +18,8 @@
 #include "llvm/Support/Streams.h"
 
 using namespace clang;
-using store::Region;
-using store::RegionExtent;
 
-typedef llvm::ImmutableMap<VarDecl*,RVal> VarBindingsTy;  
+typedef llvm::ImmutableMap<const VarDecl*,RVal> VarBindingsTy;  
 
 namespace {
   
@@ -40,10 +38,10 @@ public:
 
   virtual Store getInitialStore(GRStateManager& StateMgr);
   
-  virtual Store RemoveDeadBindings(Store store, Stmt* Loc,
-                                   const LiveVariables& Live,
-                                   DeclRootsTy& DRoots, LiveSymbolsTy& LSymbols,
-                                   DeadSymbolsTy& DSymbols);
+  virtual Store
+  RemoveDeadBindings(Store store, Stmt* Loc, const LiveVariables& Live,
+                     llvm::SmallVectorImpl<const MemRegion*>& RegionRoots,
+                     LiveSymbolsTy& LSymbols, DeadSymbolsTy& DSymbols);
 
   virtual void iterBindings(Store store, BindingsHandler& f);
 
@@ -57,42 +55,9 @@ public:
 
   virtual void print(Store store, std::ostream& Out,
                      const char* nl, const char *sep);
-  
-  virtual RegionExtent getExtent(Region R);
-  
-  /// BindingAsString - Returns a string representing the given binding.
-  virtual std::string BindingAsString(store::Binding binding);
-  
-  /// getRVal - Returns the bound RVal for a given binding.
-  virtual RVal getRVal(Store store, store::Binding binding);
-};
-  
-class VISIBILITY_HIDDEN VarRegion : public store::Region {
-public:
-  VarRegion(VarDecl* VD) : Region(VD) {}  
-  VarDecl* getDecl() const { return (VarDecl*) Data; }    
-  static bool classof(const store::Region*) { return true; }
-};
-
-class VISIBILITY_HIDDEN VarBinding : public store::Binding {
-public:
-  VarBinding(VarBindingsTy::value_type* T) : store::Binding(T) {}
-  
-  const VarBindingsTy::value_type_ref getValue() const {
-    return *static_cast<const VarBindingsTy::value_type*>(first);
-  }
     
-  std::string getName() const {
-    return getValue().first->getName();
-  }
-  
-  RVal getRVal() const {
-    return getValue().second;
-  }
-  
-  static inline bool classof(const store::Binding*) { return true; }
 };
-  
+    
 } // end anonymous namespace
 
 
@@ -100,22 +65,6 @@ StoreManager* clang::CreateBasicStoreManager(GRStateManager& StMgr) {
   return new BasicStoreManager(StMgr);
 }
 
-RegionExtent BasicStoreManager::getExtent(Region R) {
-  QualType T = cast<VarRegion>(&R)->getDecl()->getType();
-  
-  // FIXME: Add support for VLAs.  This may require passing in additional
-  //  information, or tracking a different region type.
-  if (!T.getTypePtr()->isConstantSizeType())
-    return store::UnknownExtent();
-  
-  ASTContext& C = StMgr.getContext();
-  assert (!T->isObjCInterfaceType()); // @interface not a possible VarDecl type.
-  assert (T != C.VoidTy); // void not a possible VarDecl type.  
-  return store::FixedExtent(StMgr.getBasicVals().getValue(C.getTypeSize(T),
-                                                          C.VoidPtrTy));
-}
-
-
 RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) {
   
   if (isa<UnknownVal>(LV))
@@ -125,9 +74,15 @@ RVal BasicStoreManager::GetRVal(Store St, LVal LV, QualType T) {
   
   switch (LV.getSubKind()) {
 
-    case lval::DeclValKind: {      
+    case lval::MemRegionKind: {