Enhances SCA to process untyped region to typed region conversion.

 - RegionView and RegionViewMap is introduced to assist back-mapping from
   super region to subregions.
 - GDM is used to carry RegionView information.
 - AnonTypedRegion is added to represent a typed region introduced by pointer
   casting. Later AnonTypedRegion can be used in other similar cases, e.g.,
   malloc()'ed region.
 - The specific conversion is delegated to store manager.

llvm-svn: 59382

4 files changed, 113 insertions, 2 deletions

diff --git a/clang/lib/Analysis/BasicStore.cpp b/clang/lib/Analysis/BasicStore.cpp
index 4197c08a9cf..8b5ef6ee865 100644
--- a/clang/lib/Analysis/BasicStore.cpp
+++ b/clang/lib/Analysis/BasicStore.cpp
@@ -65,6 +65,12 @@ public:
   /// ArrayToPointer - Used by GRExprEngine::VistCast to handle implicit
   ///  conversions between arrays and pointers.
   SVal ArrayToPointer(SVal Array) { return Array; }
+
+  const GRState* CastRegion(const GRState* St, SVal VoidPtr, QualType CastToTy,
+                            Stmt* CastE) {
+    return St;
+  }
+
   
   /// getSelfRegion - Returns the region for the 'self' (Objective-C) or
   ///  'this' object (C++).  When used when analyzing a normal function this
diff --git a/clang/lib/Analysis/GRExprEngine.cpp b/clang/lib/Analysis/GRExprEngine.cpp
index 55fbf1874a5..e002c136372 100644
--- a/clang/lib/Analysis/GRExprEngine.cpp
+++ b/clang/lib/Analysis/GRExprEngine.cpp
@@ -1692,6 +1692,21 @@ void GRExprEngine::VisitCast(Expr* CastE, Expr* Ex, NodeTy* Pred, NodeSet& Dst){
       continue;
     }
 
+    // Check for casts from AllocaRegion pointer to typed pointer.
+    if (isa<loc::MemRegionVal>(V)) {
+      assert(Loc::IsLocType(T));
+      assert(Loc::IsLocType(ExTy));
+
+      // Delegate to store manager.
+      const GRState* NewSt = getStoreManager().CastRegion(St, V, T, CastE);
+
+      // If no new region is created, fall through to the default case.
+      if (NewSt != St) {
+        MakeNode(Dst, CastE, N, NewSt);
+        continue;
+      }
+    }
+
     // All other cases.
     MakeNode(Dst, CastE, N, BindExpr(St, CastE, EvalCast(V, CastE->getType())));
   }
diff --git a/clang/lib/Analysis/MemRegion.cpp b/clang/lib/Analysis/MemRegion.cpp
index a292d98e605..4636eaef11f 100644
--- a/clang/lib/Analysis/MemRegion.cpp
+++ b/clang/lib/Analysis/MemRegion.cpp
@@ -44,6 +44,13 @@ void AllocaRegion::Profile(llvm::FoldingSetNodeID& ID) const {
   ProfileRegion(ID, Ex, Cnt);
 }
 
+void AnonTypedRegion::ProfileRegion(llvm::FoldingSetNodeID& ID, QualType T, 
+                                    const MemRegion* superRegion) {
+  ID.AddInteger((unsigned) AnonTypedRegionKind);
+  ID.Add(T);
+  ID.AddPointer(superRegion);
+}
+
 QualType AnonPointeeRegion::getType(ASTContext& C) const {
   QualType T = C.getCanonicalType(Pointer->getType());
   PointerType* PTy = cast<PointerType>(T.getTypePtr());
@@ -110,7 +117,7 @@ QualType ElementRegion::getType(ASTContext& C) const {
     ArrayType* AT = cast<ArrayType>(T.getTypePtr());
     return AT->getElementType();
   }
-  else if (isa<AllocaRegion>(superRegion)) {
+  else if (isa<AnonTypedRegion>(superRegion)) {
     PointerType* PtrT = cast<PointerType>(T.getTypePtr());
     QualType PTy = PtrT->getPointeeType();
     return C.getCanonicalType(PTy);
@@ -369,6 +376,23 @@ MemRegionManager::getObjCObjectRegion(const ObjCInterfaceDecl* d,
   return R;
 }
 
+AnonTypedRegion* 
+MemRegionManager::getAnonTypedRegion(QualType t, const MemRegion* superRegion) {
+  llvm::FoldingSetNodeID ID;
+  AnonTypedRegion::ProfileRegion(ID, t, superRegion);
+
+  void* InsertPos;
+  MemRegion* data = Regions.FindNodeOrInsertPos(ID, InsertPos);
+  AnonTypedRegion* R = cast_or_null<AnonTypedRegion>(data);
+
+  if (!R) {
+    R = (AnonTypedRegion*) A.Allocate<AnonTypedRegion>();
+    new (R) AnonTypedRegion(t, superRegion);
+    Regions.InsertNode(R, InsertPos);
+  }
+
+  return R;
+}
 
 AnonPointeeRegion* MemRegionManager::getAnonPointeeRegion(const VarDecl* d) {
   llvm::FoldingSetNodeID ID;
diff --git a/clang/lib/Analysis/RegionStore.cpp b/clang/lib/Analysis/RegionStore.cpp
index f1c57b33bdf..732785c0f72 100644
--- a/clang/lib/Analysis/RegionStore.cpp
+++ b/clang/lib/Analysis/RegionStore.cpp
@@ -16,26 +16,46 @@
 //===----------------------------------------------------------------------===//
 #include "clang/Analysis/PathSensitive/MemRegion.h"
 #include "clang/Analysis/PathSensitive/GRState.h"
+#include "clang/Analysis/PathSensitive/GRStateTrait.h"
 #include "clang/Analysis/Analyses/LiveVariables.h"
 
 #include "llvm/ADT/ImmutableMap.h"
+#include "llvm/ADT/ImmutableList.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/Compiler.h"
 
 using namespace clang;
 
 typedef llvm::ImmutableMap<const MemRegion*, SVal> RegionBindingsTy;
+typedef llvm::ImmutableList<const MemRegion*> RegionViewTy;
+typedef llvm::ImmutableMap<const MemRegion*, RegionViewTy> RegionViewMapTy;
+
+static int RegionViewMapTyIndex = 0;
+
+namespace clang {
+template<> struct GRStateTrait<RegionViewMapTy> 
+  : public GRStatePartialTrait<RegionViewMapTy> {
+  static void* GDMIndex() { return &RegionViewMapTyIndex; }
+};
+}
 
 namespace {
 
 class VISIBILITY_HIDDEN RegionStoreManager : public StoreManager {
   RegionBindingsTy::Factory RBFactory;
+  RegionViewTy::Factory RVFactory;
+  RegionViewMapTy::Factory RVMFactory;
+
   GRStateManager& StateMgr;
   MemRegionManager MRMgr;
 
 public:
   RegionStoreManager(GRStateManager& mgr) 
-    : StateMgr(mgr), MRMgr(StateMgr.getAllocator()) {}
+    : RBFactory(mgr.getAllocator()),
+      RVFactory(mgr.getAllocator()),
+      RVMFactory(mgr.getAllocator()),
+      StateMgr(mgr), 
+      MRMgr(StateMgr.getAllocator()) {}
 
   virtual ~RegionStoreManager() {}
 
@@ -62,6 +82,9 @@ public:
 
   SVal ArrayToPointer(SVal Array);
 
+  const GRState* CastRegion(const GRState* St, SVal VoidPtr, 
+                            QualType CastToTy, Stmt* CastE);
+
   SVal Retrieve(Store S, Loc L, QualType T = QualType());
 
   Store Bind(Store St, Loc LV, SVal V);
@@ -112,6 +135,9 @@ private:
   // Utility methods.
   BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
   ASTContext& getContext() { return StateMgr.getContext(); }
+
+  const GRState* AddRegionView(const GRState* St,
+                               const MemRegion* View, const MemRegion* Base);
 };
 
 } // end anonymous namespace
@@ -238,6 +264,30 @@ SVal RegionStoreManager::ArrayToPointer(SVal Array) {
   return loc::MemRegionVal(ER);                    
 }
 
+const GRState* RegionStoreManager::CastRegion(const GRState* St,
+                                              SVal VoidPtr, 
+                                              QualType CastToTy,
+                                              Stmt* CastE) {
+  if (const AllocaRegion* AR =
+      dyn_cast<AllocaRegion>(cast<loc::MemRegionVal>(VoidPtr).getRegion())) {
+
+    // Create a new region to attach type information to it.
+    const AnonTypedRegion* TR = MRMgr.getAnonTypedRegion(CastToTy, AR);
+
+    // Get the pointer to the first element.
+    nonloc::ConcreteInt Idx(getBasicVals().getZeroWithPtrWidth(false));
+    const ElementRegion* ER = MRMgr.getElementRegion(Idx, TR);
+
+    St = StateMgr.BindExpr(St, CastE, loc::MemRegionVal(ER));
+
+    // Add a RegionView to base region.
+    return AddRegionView(St, TR, AR);
+  }
+
+  // Default case.
+  return St;
+}
+
 SVal RegionStoreManager::Retrieve(Store S, Loc L, QualType T) {
   assert(!isa<UnknownVal>(L) && "location unknown");
   assert(!isa<UndefinedVal>(L) && "location undefined");
@@ -600,3 +650,19 @@ Store RegionStoreManager::BindStructToVal(Store store, const TypedRegion* BaseR,
 
   return store;
 }
+
+const GRState* RegionStoreManager::AddRegionView(const GRState* St,
+                                                 const MemRegion* View,
+                                                 const MemRegion* Base) {
+  GRStateRef state(St, StateMgr);
+
+  // First, retrieve the region view of the base region.
+  RegionViewMapTy::data_type* d = state.get<RegionViewMapTy>(Base);
+  RegionViewTy L = d ? *d : RVFactory.GetEmptyList();
+
+  // Now add View to the region view.
+  L = RVFactory.Add(View, L);
+
+  // Create a new state with the new region view.
+  return state.set<RegionViewMapTy>(Base, L);
+}