Add (initial?) static analyzer support for handling C++ references.

This change was a lot bigger than I originally anticipated; among
other things it requires us storing more information in the CFG to
record what block-level expressions need to be evaluated as lvalues.

The big change is that CFGBlocks no longer contain Stmt*'s by
CFGElements.  Currently CFGElements just wrap Stmt*, but they also
store a bit indicating whether the block-level expression should be
evalauted as an lvalue.  DeclStmts involving the initialization of a
reference require us treating the initialization expression as an
lvalue, even though that information isn't recorded in the AST.
Conceptually this change isn't that complicated, but it required
bubbling up the data through the CFGBuilder, to GRCoreEngine, and
eventually to GRExprEngine.

The addition of CFGElement is also useful for when we want to handle
more control-flow constructs or other data we want to keep in the CFG
that isn't represented well with just a block of statements.

In GRExprEngine, this patch introduces logic for evaluating the
lvalues of references, which currently retrieves the internal "pointer
value" that the reference represents.  EvalLoad does a two stage load
to catch null dereferences involving an invalid reference (although
this could possibly be caught earlier during the initialization of a
reference).

Symbols are currently symbolicated using the reference type, instead
of a pointer type, and special handling is required creating
ElementRegions that layer on SymbolicRegions (see the changes to
RegionStoreManager).

Along the way, the DeadStoresChecker also silences warnings involving
dead stores to references.  This was the original change I introduced
(which I wrote test cases for) that I realized caused GRExprEngine to
crash.

llvm-svn: 91501

6 files changed, 92 insertions, 56 deletions

diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h
index e6f4cf961be..cf9b0a0e043 100644
--- a/clang/include/clang/Analysis/CFG.h
+++ b/clang/include/clang/Analysis/CFG.h
@@ -15,8 +15,10 @@
 #ifndef LLVM_CLANG_CFG_H
 #define LLVM_CLANG_CFG_H
 
+#include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/Support/Allocator.h"
+#include "llvm/Support/Casting.h"
 #include "clang/Analysis/Support/BumpVector.h"
 #include <cassert>
 
@@ -31,6 +33,17 @@ namespace clang {
   class LangOptions;
   class ASTContext;
 
+/// CFGElement - Represents a top-level expression in a basic block.
+class CFGElement {
+  llvm::PointerIntPair<Stmt *, 1> Data;
+public:
+  explicit CFGElement() {}
+  CFGElement(Stmt *S, bool lvalue) : Data(S, lvalue ? 1 : 0) {}
+  Stmt *getStmt() const { return Data.getPointer(); }
+  bool asLValue() const { return Data.getInt() == 1; }
+  operator Stmt*() const { return getStmt(); }
+};
+
 /// CFGBlock - Represents a single basic block in a source-level CFG.
 ///  It consists of:
 ///
@@ -57,7 +70,7 @@ namespace clang {
 ///
 class CFGBlock {
   class StatementList {
-    typedef BumpVector<Stmt*> ImplTy;
+    typedef BumpVector<CFGElement> ImplTy;
     ImplTy Impl;
   public:
     StatementList(BumpVectorContext &C) : Impl(C, 4) {}
@@ -67,9 +80,9 @@ class CFGBlock {
     typedef ImplTy::iterator                              reverse_iterator;
     typedef ImplTy::const_iterator                        const_reverse_iterator;
   
-    void push_back(Stmt *s, BumpVectorContext &C) { Impl.push_back(s, C); }
-    Stmt *front() const { return Impl.back(); }
-    Stmt *back() const { return Impl.front(); }
+    void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
+    CFGElement front() const { return Impl.back(); }
+    CFGElement back() const { return Impl.front(); }
     
     iterator begin() { return Impl.rbegin(); }
     iterator end() { return Impl.rend(); }
@@ -80,7 +93,7 @@ class CFGBlock {
     const_reverse_iterator rbegin() const { return Impl.begin(); }
     const_reverse_iterator rend() const { return Impl.end(); }
 
-   Stmt*  operator[](size_t i) const  {
+   CFGElement operator[](size_t i) const  {
      assert(i < Impl.size());
      return Impl[Impl.size() - 1 - i];
    }
@@ -129,8 +142,8 @@ public:
   typedef StatementList::reverse_iterator              reverse_iterator;
   typedef StatementList::const_reverse_iterator        const_reverse_iterator;
 
-  Stmt*                        front()       const { return Stmts.front();   }
-  Stmt*                        back()        const { return Stmts.back();    }
+  CFGElement                   front()       const { return Stmts.front();   }
+  CFGElement                   back()        const { return Stmts.back();    }
 
   iterator                     begin()             { return Stmts.begin();   }
   iterator                     end()               { return Stmts.end();     }
@@ -145,8 +158,7 @@ public:
   unsigned                     size()        const { return Stmts.size();    }
   bool                         empty()       const { return Stmts.empty();   }
 
-  Stmt*  operator[](size_t i) const  { return Stmts[i]; }
-
+  CFGElement operator[](size_t i) const  { return Stmts[i]; }
 
   // CFG iterators
   typedef AdjacentBlocks::iterator                              pred_iterator;
@@ -221,8 +233,8 @@ public:
     Succs.push_back(Block, C);
   }
   
-  void appendStmt(Stmt* Statement, BumpVectorContext &C) {
-      Stmts.push_back(Statement, C);
+  void appendStmt(Stmt* Statement, BumpVectorContext &C, bool asLValue) {
+      Stmts.push_back(CFGElement(Statement, asLValue), C);
   }  
 };
 
@@ -370,13 +382,25 @@ private:
 
 namespace llvm {
 
+/// Implement simplify_type for CFGElement, so that we can dyn_cast from
+/// CFGElement to a specific Stmt class.
+template <> struct simplify_type<const ::clang::CFGElement> {
+  typedef ::clang::Stmt* SimpleType;
+  static SimpleType getSimplifiedValue(const ::clang::CFGElement &Val) {
+    return Val.getStmt();
+  }
+};
+  
+template <> struct simplify_type< ::clang::CFGElement> 
+  : public simplify_type<const ::clang::CFGElement> {};
+  
 // Traits for: CFGBlock
 
-template <> struct GraphTraits<clang::CFGBlock* > {
-  typedef clang::CFGBlock NodeType;
-  typedef clang::CFGBlock::succ_iterator ChildIteratorType;
+template <> struct GraphTraits< ::clang::CFGBlock* > {
+  typedef ::clang::CFGBlock NodeType;
+  typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
 
-  static NodeType* getEntryNode(clang::CFGBlock* BB)
+  static NodeType* getEntryNode(::clang::CFGBlock* BB)
   { return BB; }
 
   static inline ChildIteratorType child_begin(NodeType* N)
@@ -386,9 +410,9 @@ template <> struct GraphTraits<clang::CFGBlock* > {
   { return N->succ_end(); }
 };
 
-template <> struct GraphTraits<const clang::CFGBlock* > {
-  typedef const clang::CFGBlock NodeType;
-  typedef clang::CFGBlock::const_succ_iterator ChildIteratorType;
+template <> struct GraphTraits< const ::clang::CFGBlock* > {
+  typedef const ::clang::CFGBlock NodeType;
+  typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
 
   static NodeType* getEntryNode(const clang::CFGBlock* BB)
   { return BB; }
@@ -400,11 +424,11 @@ template <> struct GraphTraits<const clang::CFGBlock* > {
   { return N->succ_end(); }
 };
 
-template <> struct GraphTraits<Inverse<const clang::CFGBlock*> > {
-  typedef const clang::CFGBlock NodeType;
-  typedef clang::CFGBlock::const_pred_iterator ChildIteratorType;
+template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
+  typedef const ::clang::CFGBlock NodeType;
+  typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(Inverse<const clang::CFGBlock*> G)
+  static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
   { return G.Graph; }
 
   static inline ChildIteratorType child_begin(NodeType* N)
@@ -416,36 +440,40 @@ template <> struct GraphTraits<Inverse<const clang::CFGBlock*> > {
 
 // Traits for: CFG
 
-template <> struct GraphTraits<clang::CFG* >
-            : public GraphTraits<clang::CFGBlock* >  {
+template <> struct GraphTraits< ::clang::CFG* >
+    : public GraphTraits< ::clang::CFGBlock* >  {
 
-  typedef clang::CFG::iterator nodes_iterator;
+  typedef ::clang::CFG::iterator nodes_iterator;
 
-  static NodeType *getEntryNode(clang::CFG* F) { return &F->getEntry(); }
-  static nodes_iterator nodes_begin(clang::CFG* F) { return F->begin(); }
-  static nodes_iterator nodes_end(clang::CFG* F) { return F->end(); }
+  static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
+  static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
+  static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
 };
 
-template <> struct GraphTraits< const clang::CFG* >
-            : public GraphTraits< const clang::CFGBlock* >  {
+template <> struct GraphTraits<const ::clang::CFG* >
+    : public GraphTraits<const ::clang::CFGBlock* >  {
 
-  typedef clang::CFG::const_iterator nodes_iterator;
+  typedef ::clang::CFG::const_iterator nodes_iterator;
 
-  static NodeType *getEntryNode( const clang::CFG* F) { return &F->getEntry(); }
-  static nodes_iterator nodes_begin( const clang::CFG* F) { return F->begin(); }
-  static nodes_iterator nodes_end( const clang::CFG* F) { return F->end(); }
+  static NodeType *getEntryNode( const ::clang::CFG* F) {
+    return &F->getEntry();
+  }
+  static nodes_iterator nodes_begin( const ::clang::CFG* F) {
+    return F->begin();
+  }
+  static nodes_iterator nodes_end( const ::clang::CFG* F) {
+    return F->end();
+  }
 };
 
-template <> struct GraphTraits<Inverse<const clang::CFG*> >
-            : public GraphTraits<Inverse<const clang::CFGBlock*> > {
+template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
+  : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 
-  typedef clang::CFG::const_iterator nodes_iterator;
+  typedef ::clang::CFG::const_iterator nodes_iterator;
 
-  static NodeType *getEntryNode(const clang::CFG* F) { return &F->getExit(); }
-  static nodes_iterator nodes_begin(const clang::CFG* F) { return F->begin();}
-  static nodes_iterator nodes_end(const clang::CFG* F) { return F->end(); }
+  static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
+  static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
+  static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
 };
-
 } // end llvm namespace
-
 #endif
diff --git a/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h b/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
index b78cc6adfc4..e2a03a21ebf 100644
--- a/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
+++ b/clang/include/clang/Analysis/PathSensitive/GRCoreEngine.h
@@ -75,8 +75,7 @@ class GRCoreEngine {
 
   void ProcessEndPath(GREndPathNodeBuilder& Builder);
 
-  void ProcessStmt(Stmt* S, GRStmtNodeBuilder& Builder);
-
+  void ProcessStmt(CFGElement E, GRStmtNodeBuilder& Builder);
 
   bool ProcessBlockEntrance(CFGBlock* Blk, const GRState* State,
                             GRBlockCounter BC);
diff --git a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
index 8b20a823c6a..d4e8f79eb58 100644
--- a/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
+++ b/clang/include/clang/Analysis/PathSensitive/GRExprEngine.h
@@ -149,7 +149,7 @@ public:
 
   /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor
   ///  nodes by processing the 'effects' of a block-level statement.
-  void ProcessStmt(Stmt* S, GRStmtNodeBuilder& builder);
+  void ProcessStmt(CFGElement E, GRStmtNodeBuilder& builder);
 
   /// ProcessBlockEntrance - Called by GRCoreEngine when start processing
   ///  a CFGBlock.  This method returns true if the analysis should continue
@@ -399,15 +399,19 @@ public:
 
   // FIXME: 'tag' should be removed, and a LocationContext should be used
   // instead.
-  void EvalLocation(ExplodedNodeSet &Dst, Stmt *S, ExplodedNode* Pred,
-                       const GRState* St, SVal location,
-                       const void *tag, bool isLoad);
-
-  // FIXME: 'tag' should be removed, and a LocationContext should be used
-  // instead.
   void EvalStore(ExplodedNodeSet& Dst, Expr* AssignE, Expr* StoreE,
                  ExplodedNode* Pred, const GRState* St, SVal TargetLV, SVal Val,
                  const void *tag = 0);
+private:  
+  void EvalLoadCommon(ExplodedNodeSet& Dst, Expr* Ex, ExplodedNode* Pred,
+                      const GRState* St, SVal location, const void *tag,
+                      QualType LoadTy);
+
+  // FIXME: 'tag' should be removed, and a LocationContext should be used
+  // instead.
+  void EvalLocation(ExplodedNodeSet &Dst, Stmt *S, ExplodedNode* Pred,
+                    const GRState* St, SVal location,
+                    const void *tag, bool isLoad);
 };
 
 } // end clang namespace
diff --git a/clang/include/clang/Analysis/PathSensitive/GRSubEngine.h b/clang/include/clang/Analysis/PathSensitive/GRSubEngine.h
index 62e36f9e641..99cdf15e693 100644
--- a/clang/include/clang/Analysis/PathSensitive/GRSubEngine.h
+++ b/clang/include/clang/Analysis/PathSensitive/GRSubEngine.h
@@ -37,7 +37,7 @@ public:
 
   /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor
   ///  nodes by processing the 'effects' of a block-level statement.
-  virtual void ProcessStmt(Stmt* S, GRStmtNodeBuilder& builder) = 0;
+  virtual void ProcessStmt(CFGElement E, GRStmtNodeBuilder& builder) = 0;
 
   /// ProcessBlockEntrance - Called by GRCoreEngine when start processing
   ///  a CFGBlock.  This method returns true if the analysis should continue
diff --git a/clang/include/clang/Analysis/PathSensitive/SVals.h b/clang/include/clang/Analysis/PathSensitive/SVals.h
index 8b5cf40e29c..3cd4f1c5506 100644
--- a/clang/include/clang/Analysis/PathSensitive/SVals.h
+++ b/clang/include/clang/Analysis/PathSensitive/SVals.h
@@ -244,7 +244,8 @@ public:
   }
 
   static inline bool IsLocType(QualType T) {
-    return T->isAnyPointerType() || T->isBlockPointerType();
+    return T->isAnyPointerType() || T->isBlockPointerType() || 
+           T->isReferenceType();
   }
 };
 
diff --git a/clang/include/clang/Analysis/ProgramPoint.h b/clang/include/clang/Analysis/ProgramPoint.h
index 5abe1abd5d3..332f9d384f0 100644
--- a/clang/include/clang/Analysis/ProgramPoint.h
+++ b/clang/include/clang/Analysis/ProgramPoint.h
@@ -108,9 +108,13 @@ public:
     return const_cast<CFGBlock*>(reinterpret_cast<const CFGBlock*>(getData1()));
   }
 
-  Stmt* getFirstStmt() const {
+  CFGElement getFirstElement() const {
     const CFGBlock* B = getBlock();
-    return B->empty() ? NULL : B->front();
+    return B->empty() ? CFGElement() : B->front();
+  }
+  
+  Stmt *getFirstStmt() const {
+    return getFirstElement().getStmt();
   }
 
   static bool classof(const ProgramPoint* Location) {
@@ -129,7 +133,7 @@ public:
 
   Stmt* getLastStmt() const {
     const CFGBlock* B = getBlock();
-    return B->empty() ? NULL : B->back();
+    return B->empty() ? CFGElement() : B->back();
   }
 
   Stmt* getTerminator() const {