Refactored most of the "Store" piece of ValueState into a Store type. The

current store implementation is now encapsulated by BasicStore.

These changes prompted some long due constification of ValueState. Much of the
diffs in this patch include adding "const" qualifiers.


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

16 files changed, 519 insertions, 365 deletions

diff --git a/include/clang/Analysis/PathSensitive/BasicStore.h b/include/clang/Analysis/PathSensitive/BasicStore.h
new file mode 100644
index 0000000000..88ac9ce381
--- /dev/null
+++ b/include/clang/Analysis/PathSensitive/BasicStore.h
@@ -0,0 +1,27 @@
+//== BasicStore.h - Basic map from Locations to Values ----------*- C++ -*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defined the BasicStore and BasicStoreManager classes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_BASICSTORE_H
+#define LLVM_CLANG_ANALYSIS_BASICSTORE_H
+
+#include "clang/Analysis/PathSensitive/Store.h"
+
+namespace llvm {
+  class llvm::BumpPtrAllocator; 
+}
+  
+namespace clang {
+  StoreManager* CreateBasicStoreManager(llvm::BumpPtrAllocator& Alloc);
+}
+
+#endif
diff --git a/include/clang/Analysis/PathSensitive/ExplodedGraph.h b/include/clang/Analysis/PathSensitive/ExplodedGraph.h
index 39a064d4c6..71043f0ef6 100644
--- a/include/clang/Analysis/PathSensitive/ExplodedGraph.h
+++ b/include/clang/Analysis/PathSensitive/ExplodedGraph.h
@@ -95,10 +95,8 @@ protected:
   ///  with this node.
   const ProgramPoint Location;
   
-  /// State - The state associated with this node. Normally this value
-  ///  is immutable, but we anticipate there will be times when algorithms
-  ///  that directly manipulate the analysis graph will need to change it.
-  void* State;
+  /// State - The state associated with this node.
+  const void* State;
   
   /// Preds - The predecessors of this node.
   NodeGroup Preds;
@@ -107,7 +105,7 @@ protected:
   NodeGroup Succs;
   
   /// Construct a ExplodedNodeImpl with the provided location and state.
-  explicit ExplodedNodeImpl(const ProgramPoint& loc, void* state)
+  explicit ExplodedNodeImpl(const ProgramPoint& loc, const void* state)
   : Location(loc), State(state) {}
   
   /// addPredeccessor - Adds a predecessor to the current node, and 
@@ -146,19 +144,19 @@ class ExplodedNode : public ExplodedNodeImpl {
 public:
   /// Construct a ExplodedNodeImpl with the given node ID, program edge,
   ///  and state.
-  explicit ExplodedNode(const ProgramPoint& loc, StateTy* St)
+  explicit ExplodedNode(const ProgramPoint& loc, const StateTy* St)
     : ExplodedNodeImpl(loc, St) {}
   
   /// getState - Returns the state associated with the node.  
-  inline StateTy* getState() const {
-    return static_cast<StateTy*>(State);
+  inline const StateTy* getState() const {
+    return static_cast<const StateTy*>(State);
   }
   
   // Profiling (for FoldingSet).
   
   static inline void Profile(llvm::FoldingSetNodeID& ID,
                              const ProgramPoint& Loc,
-                             StateTy* state) {
+                             const StateTy* state) {
     ID.Add(Loc);
     GRTrait<StateTy>::Profile(ID, state);
   }
@@ -241,7 +239,8 @@ protected:
   /// getNodeImpl - Retrieve the node associated with a (Location,State)
   ///  pair, where 'State' is represented as an opaque void*.  This method
   ///  is intended to be used only by GRCoreEngineImpl.
-  virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L, void* State,
+  virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L,
+                                        const void* State,
                                         bool* IsNew) = 0;
   
   virtual ExplodedGraphImpl* MakeEmptyGraph() const = 0;
@@ -300,9 +299,10 @@ protected:
   
 protected:
   virtual ExplodedNodeImpl* getNodeImpl(const ProgramPoint& L,
-                                        void* State, bool* IsNew) {
+                                        const void* State,
+                                        bool* IsNew) {
     
-    return getNode(L, static_cast<StateTy*>(State), IsNew);
+    return getNode(L, static_cast<const StateTy*>(State), IsNew);
   }
   
   virtual ExplodedGraphImpl* MakeEmptyGraph() const {
@@ -317,7 +317,8 @@ public:
   ///  where the 'Location' is a ProgramPoint in the CFG.  If no node for
   ///  this pair exists, it is created.  IsNew is set to true if
   ///  the node was freshly created.
-  NodeTy* getNode(const ProgramPoint& L, StateTy* State, bool* IsNew = NULL) {
+  NodeTy* getNode(const ProgramPoint& L, const StateTy* State,
+                  bool* IsNew = NULL) {
     
     // Profile 'State' to determine if we already have an existing node.
     llvm::FoldingSetNodeID profile;    
diff --git a/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/include/clang/Analysis/PathSensitive/GRCoreEngine.h
index 19028ee875..32fe9d3342 100644
--- a/include/clang/Analysis/PathSensitive/GRCoreEngine.h
+++ b/include/clang/Analysis/PathSensitive/GRCoreEngine.h
@@ -61,14 +61,14 @@ protected:
   ///   number of times different CFGBlocks have been visited along a path.
   GRBlockCounter::Factory BCounterFactory;
   
-  void GenerateNode(const ProgramPoint& Loc, void* State,
+  void GenerateNode(const ProgramPoint& Loc, const void* State,
                     ExplodedNodeImpl* Pred = NULL);
   
   /// getInitialState - Gets the void* representing the initial 'state'
   ///  of the analysis.  This is simply a wrapper (implemented
   ///  in GRCoreEngine) that performs type erasure on the initial
   ///  state returned by the checker object.
-  virtual void* getInitialState() = 0;
+  virtual const void* getInitialState() = 0;
   
   void HandleBlockEdge(const BlockEdge& E, ExplodedNodeImpl* Pred);
   void HandleBlockEntrance(const BlockEntrance& E, ExplodedNodeImpl* Pred);
@@ -81,7 +81,7 @@ protected:
   
   virtual void ProcessEndPath(GREndPathNodeBuilderImpl& Builder) = 0;  
   
-  virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State,
+  virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State,
                                     GRBlockCounter BC) = 0;
 
   virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilderImpl& Builder) = 0;
@@ -142,11 +142,11 @@ public:
   }  
     
   ExplodedNodeImpl*
-  generateNodeImpl(Stmt* S, void* State, ExplodedNodeImpl* Pred,
+  generateNodeImpl(Stmt* S, const void* State, ExplodedNodeImpl* Pred,
                    ProgramPoint::Kind K = ProgramPoint::PostStmtKind);
 
   ExplodedNodeImpl*
-  generateNodeImpl(Stmt* S, void* State,
+  generateNodeImpl(Stmt* S, const void* State,
                    ProgramPoint::Kind K = ProgramPoint::PostStmtKind) {    
     ExplodedNodeImpl* N = getLastNode();
     assert (N && "Predecessor of new node is infeasible.");
@@ -169,7 +169,7 @@ class GRStmtNodeBuilder  {
   typedef ExplodedNode<StateTy>   NodeTy;
   
   GRStmtNodeBuilderImpl& NB;
-  StateTy* CleanedState;
+  const StateTy* CleanedState;
   
   GRAuditor<StateTy> **CallExprAuditBeg, **CallExprAuditEnd;
   GRAuditor<StateTy> **ObjCMsgExprAuditBeg, **ObjCMsgExprAuditEnd;
@@ -201,7 +201,7 @@ public:
   }
   
   NodeTy*
-  generateNode(Stmt* S, StateTy* St, NodeTy* Pred,
+  generateNode(Stmt* S, const StateTy* St, NodeTy* Pred,
                ProgramPoint::Kind K = ProgramPoint::PostStmtKind) {
 
     HasGeneratedNode = true;
@@ -210,7 +210,7 @@ public:
   }
   
   NodeTy*
-  generateNode(Stmt* S, StateTy* St,
+  generateNode(Stmt* S, const StateTy* St,
                ProgramPoint::Kind K = ProgramPoint::PostStmtKind) {
       
     HasGeneratedNode = true;
@@ -226,21 +226,21 @@ public:
     return NB.getCurrentBlockCount();
   }
   
-  StateTy* GetState(NodeTy* Pred) const {
+  const StateTy* GetState(NodeTy* Pred) const {
     if ((ExplodedNodeImpl*) Pred == NB.getBasePredecessor())
       return CleanedState;
     else
       return Pred->getState();
   }
   
-  void SetCleanedState(StateTy* St) {
+  void SetCleanedState(const StateTy* St) {
     CleanedState = St;
   }
   
   NodeTy* MakeNode(ExplodedNodeSet<StateTy>& Dst, Stmt* S,
-                 NodeTy* Pred, StateTy* St) {    
+                   NodeTy* Pred, const StateTy* St) {    
     
-    StateTy* PredState = GetState(Pred);
+    const StateTy* PredState = GetState(Pred);
     
     GRAuditor<StateTy> **AB = NULL, **AE = NULL;
     
@@ -309,7 +309,7 @@ public:
   const ExplodedGraphImpl& getGraph() const { return *Eng.G; }
   GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
     
-  ExplodedNodeImpl* generateNodeImpl(void* State, bool branch);
+  ExplodedNodeImpl* generateNodeImpl(const void* State, bool branch);
   
   CFGBlock* getTargetBlock(bool branch) const {
     return branch ? DstT : DstF;
@@ -340,11 +340,11 @@ public:
     return static_cast<NodeTy*>(NB.getPredecessor());
   }
   
-  StateTy* getState() const {
+  const StateTy* getState() const {
     return getPredecessor()->getState();
   }
 
-  NodeTy* generateNode(StateTy* St, bool branch) {
+  NodeTy* generateNode(const StateTy* St, bool branch) {
     return static_cast<NodeTy*>(NB.generateNodeImpl(St, branch));
   }
   
@@ -396,11 +396,11 @@ public:
   Iterator begin() { return Iterator(DispatchBlock.succ_begin()); }
   Iterator end() { return Iterator(DispatchBlock.succ_end()); }
   
-  ExplodedNodeImpl* generateNodeImpl(const Iterator& I, void* State,
+  ExplodedNodeImpl* generateNodeImpl(const Iterator& I, const void* State,
                                      bool isSink);
   
   Expr* getTarget() const { return E; }
-  void* getState() const { return Pred->State; }
+  const void* getState() const { return Pred->State; }
 };
   
 template<typename STATE>
@@ -421,12 +421,12 @@ public:
   
   Expr* getTarget() const { return NB.getTarget(); }
   
-  NodeTy* generateNode(const iterator& I, StateTy* St, bool isSink=false){    
+  NodeTy* generateNode(const iterator& I, const StateTy* St, bool isSink=false){    
     return static_cast<NodeTy*>(NB.generateNodeImpl(I, St, isSink));
   }
   
-  StateTy* getState() const {
-    return static_cast<StateTy*>(NB.getState());
+  const StateTy* getState() const {
+    return static_cast<const StateTy*>(NB.getState());
   }    
 };
   
@@ -462,11 +462,14 @@ public:
   Iterator begin() { return Iterator(Src->succ_rbegin()+1); }
   Iterator end() { return Iterator(Src->succ_rend()); }
   
-  ExplodedNodeImpl* generateCaseStmtNodeImpl(const Iterator& I, void* State);
-  ExplodedNodeImpl* generateDefaultCaseNodeImpl(void* State, bool isSink);
+  ExplodedNodeImpl* generateCaseStmtNodeImpl(const Iterator& I,
+                                             const void* State);
+  
+  ExplodedNodeImpl* generateDefaultCaseNodeImpl(const void* State,
+                                                bool isSink);
   
   Expr* getCondition() const { return Condition; }
-  void* getState() const { return Pred->State; }
+  const void* getState() const { return Pred->State; }
 };
 
 template<typename STATE>
@@ -487,16 +490,16 @@ public:
   
   Expr* getCondition() const { return NB.getCondition(); }
   
-  NodeTy* generateCaseStmtNode(const iterator& I, StateTy* St) {
+  NodeTy* generateCaseStmtNode(const iterator& I, const StateTy* St) {
     return static_cast<NodeTy*>(NB.generateCaseStmtNodeImpl(I, St));
   }
   
-  NodeTy* generateDefaultCaseNode(StateTy* St, bool isSink = false) {    
+  NodeTy* generateDefaultCaseNode(const StateTy* St, bool isSink = false) {    
     return static_cast<NodeTy*>(NB.generateDefaultCaseNodeImpl(St, isSink));
   }
   
-  StateTy* getState() const {
-    return static_cast<StateTy*>(NB.getState());
+  const StateTy* getState() const {
+    return static_cast<const StateTy*>(NB.getState());
   }    
 };
   
@@ -522,7 +525,7 @@ public:
     return getBlockCounter().getNumVisited(B.getBlockID());
   }  
   
-  ExplodedNodeImpl* generateNodeImpl(void* State);
+  ExplodedNodeImpl* generateNodeImpl(const void* State);
     
   CFGBlock* getBlock() const { return &B; }
 };
@@ -550,11 +553,11 @@ public:
     return NB.getCurrentBlockCount();
   }
   
-  StateTy* getState() const {
+  const StateTy* getState() const {
     return getPredecessor()->getState();
   }
   
-  NodeTy* MakeNode(StateTy* St) {  
+  NodeTy* MakeNode(const StateTy* St) {  
     return static_cast<NodeTy*>(NB.generateNodeImpl(St));
   }
 };
@@ -571,7 +574,7 @@ public:
 protected:
   SubEngineTy& SubEngine;
   
-  virtual void* getInitialState() {
+  virtual const void* getInitialState() {
     return SubEngine.getInitialState();
   }
   
@@ -585,9 +588,11 @@ protected:
     SubEngine.ProcessStmt(S, Builder);
   }
   
-  virtual bool ProcessBlockEntrance(CFGBlock* Blk, void* State,
+  virtual bool ProcessBlockEntrance(CFGBlock* Blk, const void* State,
                                     GRBlockCounter BC) {    
-    return SubEngine.ProcessBlockEntrance(Blk, static_cast<StateTy*>(State),BC);
+    return SubEngine.ProcessBlockEntrance(Blk,
+                                          static_cast<const StateTy*>(State),
+                                          BC);
   }
 
   virtual void ProcessBranch(Expr* Condition, Stmt* Terminator,
diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h
index 6dfd428bf4..97699ca902 100644
--- a/include/clang/Analysis/PathSensitive/GRExprEngine.h
+++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h
@@ -86,7 +86,7 @@ protected:
 
   /// CleanedState - The state for EntryNode "cleaned" of all dead
   ///  variables and symbols (as determined by a liveness analysis).
-  ValueState* CleanedState;  
+  const ValueState* CleanedState;  
   
   /// CurrentStmt - The current block-level statement.
   Stmt* CurrentStmt;
@@ -210,7 +210,7 @@ public:
   
   /// getInitialState - Return the initial state used for the root vertex
   ///  in the ExplodedGraph.
-  ValueState* getInitialState();
+  const ValueState* getInitialState();
   
   GraphTy& getGraph() { return G; }
   const GraphTy& getGraph() const { return G; }
@@ -370,7 +370,8 @@ public:
   /// ProcessBlockEntrance - Called by GRCoreEngine when start processing
   ///  a CFGBlock.  This method returns true if the analysis should continue
   ///  exploring the given path, and false otherwise.
-  bool ProcessBlockEntrance(CFGBlock* B, ValueState* St, GRBlockCounter BC);
+  bool ProcessBlockEntrance(CFGBlock* B, const ValueState* St,
+                            GRBlockCounter BC);
   
   /// ProcessBranch - Called by GRCoreEngine.  Used to generate successor
   ///  nodes by processing the 'effects' of a branch condition.
@@ -401,7 +402,7 @@ public:
   
 protected:
   
-  ValueState* GetState(NodeTy* N) {
+  const ValueState* GetState(NodeTy* N) {
     return N == EntryNode ? CleanedState : N->getState();
   }
   
@@ -409,35 +410,35 @@ public:
   
   // FIXME: Maybe make these accesible only within the StmtBuilder?
   
-  ValueState* SetRVal(ValueState* St, Expr* Ex, RVal V);
+  const ValueState* SetRVal(const ValueState* St, Expr* Ex, RVal V);
   
-  ValueState* SetRVal(ValueState* St, const Expr* Ex, RVal V) {
+  const ValueState* SetRVal(const ValueState* St, const Expr* Ex, RVal V) {
     return SetRVal(St, const_cast<Expr*>(Ex), V);
   }
   
 protected:
  
-  ValueState* SetBlkExprRVal(ValueState* St, Expr* Ex, RVal V) {
+  const ValueState* SetBlkExprRVal(const ValueState* St, Expr* Ex, RVal V) {
     return StateMgr.SetRVal(St, Ex, V, true, false);
   }
   
-  ValueState* SetRVal(ValueState* St, LVal LV, RVal V) {
+  const ValueState* SetRVal(const ValueState* St, LVal LV, RVal V) {
     return StateMgr.SetRVal(St, LV, V);
   }
   
-  RVal GetRVal(ValueState* St, Expr* Ex) {
+  RVal GetRVal(const ValueState* St, Expr* Ex) {
     return StateMgr.GetRVal(St, Ex);
   }
     
-  RVal GetRVal(ValueState* St, const Expr* Ex) {
+  RVal GetRVal(const ValueState* St, const Expr* Ex) {
     return GetRVal(St, const_cast<Expr*>(Ex));
   }
   
-  RVal GetBlkExprRVal(ValueState* St, Expr* Ex) {
+  RVal GetBlkExprRVal(const ValueState* St, Expr* Ex) {
     return StateMgr.GetBlkExprRVal(St, Ex);
   }  
     
-  RVal GetRVal(ValueState* St, LVal LV, QualType T = QualType()) {    
+  RVal GetRVal(const ValueState* St, LVal LV, QualType T = QualType()) {    
     return StateMgr.GetRVal(St, LV, T);
   }
   
@@ -447,8 +448,8 @@ protected:
   
   /// Assume - Create new state by assuming that a given expression
   ///  is true or false.
-  ValueState* Assume(ValueState* St, RVal Cond, bool Assumption,
-                     bool& isFeasible) {
+  const ValueState* Assume(const ValueState* St, RVal Cond, bool Assumption,
+                           bool& isFeasible) {
     
     if (Cond.isUnknown()) {
       isFeasible = true;
@@ -461,28 +462,28 @@ protected:
       return Assume(St, cast<NonLVal>(Cond), Assumption, isFeasible);
   }
   
-  ValueState* Assume(ValueState* St, LVal Cond, bool Assumption,
-                     bool& isFeasible);
+  const ValueState* Assume(const ValueState* St, LVal Cond, bool Assumption,
+                           bool& isFeasible);
                      
-  ValueState* AssumeAux(ValueState* St, LVal Cond, bool Assumption,
-                        bool& isFeasible);
+  const ValueState* AssumeAux(const ValueState* St, LVal Cond, bool Assumption,
+                              bool& isFeasible);
 
-  ValueState* Assume(ValueState* St, NonLVal Cond, bool Assumption,
-                     bool& isFeasible);
+  const ValueState* Assume(const ValueState* St, NonLVal Cond, bool Assumption,
+                           bool& isFeasible);
   
-  ValueState* AssumeAux(ValueState* St, NonLVal Cond, bool Assumption,
-                        bool& isFeasible);
+  const ValueState* AssumeAux(const ValueState* St, NonLVal Cond,
+                              bool Assumption, bool& isFeasible);
   
-  ValueState* AssumeSymNE(ValueState* St, SymbolID sym, const llvm::APSInt& V,
-                          bool& isFeasible);
+  const ValueState* AssumeSymNE(const ValueState* St, SymbolID sym,
+                                const llvm::APSInt& V, bool& isFeasible);
   
-  ValueState* AssumeSymEQ(ValueState* St, SymbolID sym, const llvm::APSInt& V,
-                          bool& isFeasible);
+  const ValueState* AssumeSymEQ(const ValueState* St, SymbolID sym,
+                                const llvm::APSInt& V, bool& isFeasible);
   
-  ValueState* AssumeSymInt(ValueState* St, bool Assumption,
-                           const SymIntConstraint& C, bool& isFeasible);
+  const ValueState* AssumeSymInt(const ValueState* St, bool Assumption,
+                                 const SymIntConstraint& C, bool& isFeasible);
   
-  NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, ValueState* St) {
+  NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const ValueState* St) {
     assert (Builder && "GRStmtNodeBuilder not present.");
     return Builder->MakeNode(Dst, S, Pred, St);
   }
@@ -568,7 +569,8 @@ protected:
   void VisitUnaryOperator(UnaryOperator* B, NodeTy* Pred, NodeSet& Dst,
                           bool asLVal);
  
-  bool CheckDivideZero(Expr* Ex, ValueState* St, NodeTy* Pred, RVal Denom);  
+  bool CheckDivideZero(Expr* Ex, const ValueState* St, NodeTy* Pred,
+                       RVal Denom);  
   
   RVal EvalCast(RVal X, QualType CastT) {
     if (X.isUnknownOrUndef())
@@ -634,21 +636,22 @@ protected:
     TF->EvalObjCMessageExpr(Dst, *this, *Builder, ME, Pred);
   }
   
-  void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, ValueState* St,
+  void EvalStore(NodeSet& Dst, Expr* E, NodeTy* Pred, const ValueState* St,
                  RVal TargetLV, RVal Val);
   
   // FIXME: The "CheckOnly" option exists only because Array and Field
   //  loads aren't fully implemented.  Eventually this option will go away.
   
   void EvalLoad(NodeSet& Dst, Expr* Ex, NodeTy* Pred,
-                ValueState* St, RVal location, bool CheckOnly = false);
+                const ValueState* St, RVal location, bool CheckOnly = false);
   
-  ValueState* EvalLocation(Expr* Ex, NodeTy* Pred,
-                           ValueState* St, RVal location, bool isLoad = false);
+  const ValueState* EvalLocation(Expr* Ex, NodeTy* Pred,
+                                 const ValueState* St, RVal location,
+                                 bool isLoad = false);
   
   void EvalReturn(NodeSet& Dst, ReturnStmt* s, NodeTy* Pred);
   
-  ValueState* MarkBranch(ValueState* St, Stmt* Terminator, bool branchTaken);
+  const ValueState* MarkBranch(const ValueState* St, Stmt* Terminator, bool branchTaken);
 };
   
 } // end clang namespace
diff --git a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h
index 323358e0c3..4e267f8859 100644
--- a/include/clang/Analysis/PathSensitive/GRTransferFuncs.h
+++ b/include/clang/Analysis/PathSensitive/GRTransferFuncs.h
@@ -82,7 +82,7 @@ public:
                          GRExprEngine& Engine,
                          GRStmtNodeBuilder<ValueState>& Builder,
                          Expr* E, ExplodedNode<ValueState>* Pred,
-                         ValueState* St, RVal TargetLV, RVal Val);
+                         const ValueState* St, RVal TargetLV, RVal Val);
                          
   
   // End-of-path and dead symbol notification.
@@ -96,7 +96,7 @@ public:
                                GRStmtNodeBuilder<ValueState>& Builder,
                                ExplodedNode<ValueState>* Pred,
                                Stmt* S,
-                               ValueState* St,
+                               const ValueState* St,
                                const ValueStateManager::DeadSymbolsTy& Dead) {}
   
   // Return statements.
@@ -109,8 +109,10 @@ public:
 
   // Assumptions.
   
-  virtual ValueState* EvalAssume(GRExprEngine& Engine, ValueState* St,
-                                 RVal Cond, bool Assumption, bool& isFeasible) {
+  virtual const ValueState* EvalAssume(GRExprEngine& Engine,
+                                       const ValueState* St,
+                                       RVal Cond, bool Assumption,
+                                       bool& isFeasible) {
     return St;
   }
 };
diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h
new file mode 100644
index 0000000000..adf9cf8eae
--- /dev/null
+++ b/include/clang/Analysis/PathSensitive/Store.h
@@ -0,0 +1,34 @@
+//== Store.h - Interface for maps from Locations to Values ------*- C++ -*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defined the types Store and StoreManager.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_STORE_H
+#define LLVM_CLANG_ANALYSIS_STORE_H
+
+#include "clang/Analysis/PathSensitive/RValues.h"
+
+namespace clang {
+  
+typedef const void* Store;
+  
+class StoreManager {
+public:
+  virtual ~StoreManager() {}
+  virtual RVal GetRVal(Store St, LVal LV, QualType T) = 0;
+  virtual Store SetRVal(Store St, LVal LV, RVal V) = 0;
+  virtual Store Remove(Store St, LVal LV) = 0;
+  virtual Store getInitialStore() = 0;
+};
+  
+} // end clang namespace
+
+#endif
diff --git a/include/clang/Analysis/PathSensitive/ValueState.h b/include/clang/Analysis/PathSensitive/ValueState.h
index ab9b4a8b32..36bfdff5b9 100644
--- a/include/clang/Analysis/PathSensitive/ValueState.h
+++ b/include/clang/Analysis/PathSensitive/ValueState.h
@@ -17,6 +17,7 @@
 // FIXME: Reduce the number of includes.
 
 #include "clang/Analysis/PathSensitive/Environment.h"
+#include "clang/Analysis/PathSensitive/Store.h"
 #include "clang/Analysis/PathSensitive/RValues.h"
 #include "clang/Analysis/PathSensitive/GRCoreEngine.h"
 #include "clang/AST/Expr.h"
@@ -54,7 +55,6 @@ class ValueState : public llvm::FoldingSetNode {
 public:  
   // Typedefs.  
   typedef llvm::ImmutableSet<llvm::APSInt*>                IntSetTy;
-  typedef llvm::ImmutableMap<VarDecl*,RVal>                VarBindingsTy;  
   typedef llvm::ImmutableMap<SymbolID,IntSetTy>            ConstNotEqTy;
   typedef llvm::ImmutableMap<SymbolID,const llvm::APSInt*> ConstEqTy;
 
@@ -64,10 +64,10 @@ private:
   friend class ValueStateManager;
   
   Environment Env;
+  Store St;
 
   // FIXME: Make these private.
 public:
-  VarBindingsTy    VarBindings;
   ConstNotEqTy     ConstNotEq;
   ConstEqTy        ConstEq;
   void*            CheckerState;
@@ -75,10 +75,10 @@ public:
 public:
   
   /// This ctor is used when creating the first ValueState object.
-  ValueState(const Environment& env,  VarBindingsTy VB,
+  ValueState(const Environment& env,  Store st,
              ConstNotEqTy CNE, ConstEqTy  CE)
     : Env(env),
-      VarBindings(VB),
+      St(st),
       ConstNotEq(CNE),
       ConstEq(CE),
       CheckerState(NULL) {}
@@ -88,7 +88,7 @@ public:
   ValueState(const ValueState& RHS)
     : llvm::FoldingSetNode(),
       Env(RHS.Env),
-      VarBindings(RHS.VarBindings),
+      St(RHS.St),
       ConstNotEq(RHS.ConstNotEq),
       ConstEq(RHS.ConstEq),
       CheckerState(RHS.CheckerState) {} 
@@ -97,11 +97,15 @@ public:
   ///  The environment is the mapping from expressions to values.
   const Environment& getEnvironment() const { return Env; }
   
+  /// getStore - Return the store associated with this state.  The store
+  ///  is a mapping from locations to values.
+  Store getStore() const { return St; }
+  
   /// Profile - Profile the contents of a ValueState object for use
   ///  in a FoldingSet.
   static void Profile(llvm::FoldingSetNodeID& ID, const ValueState* V) {
     V->Env.Profile(ID);
-    V->VarBindings.Profile(ID);
+    ID.AddPointer(V->St);
     V->ConstNotEq.Profile(ID);
     V->ConstEq.Profile(ID);
     ID.AddPointer(V->CheckerState);
@@ -124,9 +128,18 @@ 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 { return VarBindings.begin(); }
-  vb_iterator vb_end() const { return VarBindings.end(); }
+  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(); }
@@ -173,8 +186,8 @@ template<> struct GRTrait<ValueState*> {
 class ValueStateManager {
 private:
   EnvironmentManager                   EnvMgr;
+  llvm::OwningPtr<StoreManager>        StMgr;
   ValueState::IntSetTy::Factory        ISetFactory;
-  ValueState::VarBindingsTy::Factory   VBFactory;
   ValueState::ConstNotEqTy::Factory    CNEFactory;
   ValueState::ConstEqTy::Factory       CEFactory;
   
@@ -196,58 +209,53 @@ private:
   Environment RemoveBlkExpr(const Environment& Env, Expr* E) {
     return EnvMgr.RemoveBlkExpr(Env, E);
   }
-  
-  ValueState::VarBindingsTy Remove(ValueState::VarBindingsTy B, VarDecl* V) {
-    return VBFactory.Remove(B, V);
-  }
-  
-  ValueState::VarBindingsTy Remove(const ValueState& V, VarDecl* D) {
-    return Remove(V.VarBindings, D);
+   
+  // FIXME: Remove when we do lazy initializaton of variable bindings.
+  const ValueState* BindVar(const ValueState* St, VarDecl* D, RVal V) {
+    return SetRVal(St, lval::DeclVal(D), V);
   }
-                  
-  ValueState* BindVar(ValueState* St, VarDecl* D, RVal V);
-  ValueState* UnbindVar(ValueState* St, VarDecl* D);  
-  
+    
 public:  
-  ValueStateManager(ASTContext& Ctx, llvm::BumpPtrAllocator& alloc) 
-    : EnvMgr(alloc),
-      ISetFactory(alloc), 
-      VBFactory(alloc),
-      CNEFactory(alloc),
-      CEFactory(alloc),
-      BasicVals(Ctx, alloc),
-      SymMgr(alloc),
-      Alloc(alloc) {}
-  
-  ValueState* getInitialState();
+  ValueStateManager(ASTContext& Ctx, StoreManager* stmgr,
+                    llvm::BumpPtrAllocator& alloc) 
+  : EnvMgr(alloc),
+    StMgr(stmgr),
+    ISetFactory(alloc), 
+    CNEFactory(alloc),
+    CEFactory(alloc),
+    BasicVals(Ctx, alloc),
+    SymMgr(alloc),
+    Alloc(alloc) {}
+
+  const ValueState* getInitialState();
         
   BasicValueFactory& getBasicValueFactory() { return BasicVals; }
   SymbolManager& getSymbolManager() { return SymMgr; }
   
   typedef llvm::DenseSet<SymbolID> DeadSymbolsTy;
   
-  ValueState* RemoveDeadBindings(ValueState* St, Stmt* Loc, 
-                                 const LiveVariables& Liveness,
-                                 DeadSymbolsTy& DeadSymbols);
+  const ValueState* RemoveDeadBindings(const ValueState* St, Stmt* Loc, 
+                                       const LiveVariables& Liveness,
+                                       DeadSymbolsTy& DeadSymbols);
 
-  ValueState* RemoveSubExprBindings(ValueState* St) {
+  const ValueState* RemoveSubExprBindings(const ValueState* St) {
     ValueState NewSt = *St;
     NewSt.Env = EnvMgr.RemoveSubExprBindings(NewSt.Env);
-    return getPersistentState(NewSt);    
+    return getPersistentState(NewSt);
   }
 
   // Methods that query & manipulate the Environment.
   
-  RVal GetRVal(ValueState* St, Expr* Ex) {
+  RVal GetRVal(const ValueState* St, Expr* Ex) {
     return St->getEnvironment().GetRVal(Ex, BasicVals);
   }
   
-  RVal GetBlkExprRVal(ValueState* St, Expr* Ex) {
+  RVal GetBlkExprRVal(const ValueState* St, Expr* Ex) {
     return St->getEnvironment().GetBlkExprRVal(Ex, BasicVals);
   }
   
-  ValueState* SetRVal(ValueState* St, Expr* Ex, RVal V, bool isBlkExpr,
-                      bool Invalidate) {
+  const ValueState* SetRVal(const ValueState* St, Expr* Ex, RVal V,
+                            bool isBlkExpr, bool Invalidate) {
     
     const Environment& OldEnv = St->getEnvironment();
     Environment NewEnv = EnvMgr.SetRVal(OldEnv, Ex, V, isBlkExpr, Invalidate);
@@ -262,18 +270,29 @@ public:
 
   // Methods that query & manipulate the Store.
 
-  RVal GetRVal(ValueState* St, LVal LV, QualType T = QualType());    
+  RVal GetRVal(const ValueState* St, LVal LV, QualType T = QualType()) {
+    return StMgr->GetRVal(St->getStore(), LV, T);
+  }
   
-  ValueState* SetRVal(ValueState* St, LVal LV, RVal V);
+  void SetRVal(ValueState& St, LVal LV, RVal V) {
+    St.St = StMgr->SetRVal(St.St, LV, V);
+  }
+  
+  const ValueState* SetRVal(const ValueState* St, LVal LV, RVal V);  
 
-  void BindVar(ValueState& StImpl, VarDecl* D, RVal V);
+  void Unbind(ValueState& St, LVal LV) {
+    St.St = StMgr->Remove(St.St, LV);
+  }
   
-  void Unbind(ValueState& StImpl, LVal LV);
+  const ValueState* Unbind(const ValueState* St, LVal LV);
   
-  ValueState* getPersistentState(ValueState& Impl);
+  const ValueState* getPersistentState(ValueState& Impl);
   
-  ValueState* AddEQ(ValueState* St, SymbolID sym, const llvm::APSInt& V);
-  ValueState* AddNE(ValueState* St, SymbolID sym, const llvm::APSInt& V);
+  const ValueState* AddEQ(const ValueState* St, SymbolID sym,
+                          const llvm::APSInt& V);
+
+  const ValueState* AddNE(const ValueState* St, SymbolID sym,
+                          const llvm::APSInt& V);
 };
   
 } // end clang namespace
diff --git a/lib/Analysis/BasicObjCFoundationChecks.cpp b/lib/Analysis/BasicObjCFoundationChecks.cpp