This is a big patch, but the functionality change is small and the rest of the patch consists of deltas due to API changes.

This patch overhauls the "memory region" abstraction that was prototyped (but never really used) as part of the Store.h.  This patch adds MemRegion.h and MemRegion.cpp, which defines the class MemRegion and its subclasses.  This classes serve to define an abstract representation of memory, with regions being layered on other regions to to capture the relationships between fields and variables, variables and the address space they are allocated in, and so on.  

The main motivation of this patch is that key parts of the analyzer assumed that all value bindings were to VarDecls.  In the future this won't be the case, and this patch removes lval::DeclVal and replaces it with lval::MemRegionVal.  Now all pieces of the analyzer must reason about abstract memory blocks instead of just variables.

There should be no functionality change from this patch, but it opens the door for significant improvements to the analyzer such as field-sensitivity and object-sensitivity, both which were on hold until the memory abstraction got generalized.

The memory region abstraction also allows type-information to literally be affixed to a memory region.  This will allow the some now redundant logic to be removed from the retain/release checker.

llvm-svn: 57042

1 files changed, 68 insertions, 26 deletions

diff --git a/clang/lib/Analysis/CFRefCount.cpp b/clang/lib/Analysis/CFRefCount.cpp
index 733cad18acf..c63529aa055 100644
--- a/clang/lib/Analysis/CFRefCount.cpp
+++ b/clang/lib/Analysis/CFRefCount.cpp
@@ -1489,7 +1489,7 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<GRState>& Dst,
       // Nuke all arguments passed by reference.
       StateMgr.Unbind(StVals, cast<LVal>(V));
 #else
-      if (lval::DeclVal* DV = dyn_cast<lval::DeclVal>(&V)) {
+      if (lval::MemRegionVal* MR = dyn_cast<lval::MemRegionVal>(&V)) {
 
         if (GetArgE(Summ, idx) == DoNothingByRef)
           continue;
@@ -1506,23 +1506,28 @@ void CFRefCount::EvalSummary(ExplodedNodeSet<GRState>& Dst,
         //  disambiguate conjured symbols. 
 
         // Is the invalidated variable something that we were tracking?
-        RVal X = state.GetRVal(*DV);
+        RVal X = state.GetRVal(*MR);
         
         if (isa<lval::SymbolVal>(X)) {
           SymbolID Sym = cast<lval::SymbolVal>(X).getSymbol();
           state = state.remove<RefBindings>(Sym);
         }
-
-        // Set the value of the variable to be a conjured symbol.
-        unsigned Count = Builder.getCurrentBlockCount();
-        SymbolID NewSym =
-          Eng.getSymbolManager().getConjuredSymbol(*I, DV->getDecl()->getType(),
-                                                   Count);
-
-        state = state.SetRVal(*DV,
-                              LVal::IsLValType(DV->getDecl()->getType())
-                              ? cast<RVal>(lval::SymbolVal(NewSym))
-                              : cast<RVal>(nonlval::SymbolVal(NewSym)));
+        
+        TypedRegion* R = dyn_cast<TypedRegion>(MR->getRegion());
+        if (R) {
+          // Set the value of the variable to be a conjured symbol.
+          unsigned Count = Builder.getCurrentBlockCount();
+          QualType T = R->getType();
+          SymbolID NewSym =
+            Eng.getSymbolManager().getConjuredSymbol(*I, T, Count);
+          
+          state = state.SetRVal(*MR,
+                                LVal::IsLValType(T)
+                                ? cast<RVal>(lval::SymbolVal(NewSym))
+                                : cast<RVal>(nonlval::SymbolVal(NewSym)));
+        }
+        else
+          state = state.SetRVal(*MR, UnknownVal());
       }
       else {
         // Nuke all other arguments passed by reference.
@@ -1709,10 +1714,12 @@ void CFRefCount::EvalStore(ExplodedNodeSet<GRState>& Dst,
   
   bool escapes = false;
   
-  if (!isa<lval::DeclVal>(TargetLV))
+  if (!isa<lval::MemRegionVal>(TargetLV))
     escapes = true;
-  else
-    escapes = cast<lval::DeclVal>(TargetLV).getDecl()->hasGlobalStorage();
+  else {
+    MemRegion* R = cast<lval::MemRegionVal>(TargetLV).getRegion();
+    escapes = !Eng.getStateManager().hasStackStorage(R);
+  }
   
   if (!escapes)
     return;
@@ -2307,14 +2314,51 @@ PathDiagnosticPiece* CFRefReport::VisitNode(ExplodedNode<GRState>* N,
   return P;
 }
 
-static std::pair<ExplodedNode<GRState>*,store::Binding>
+namespace {
+class VISIBILITY_HIDDEN FindUniqueBinding :
+  public StoreManager::BindingsHandler {
+    SymbolID Sym;
+    MemRegion* Binding;
+    bool First;
+    
+  public:
+    FindUniqueBinding(SymbolID sym) : Sym(sym), Binding(0), First(true) {}
+    
+  bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal val) {
+    if (const lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&val)) {
+      if (SV->getSymbol() != Sym) 
+        return true;
+    }
+    else if (const nonlval::SymbolVal* SV=dyn_cast<nonlval::SymbolVal>(&val)) {
+      if (SV->getSymbol() != Sym)
+        return true;
+    }
+    else
+      return true;
+
+    if (Binding) {
+      First = false;
+      return false;
+    }
+    else
+      Binding = R;
+    
+    return true;    
+  }
+    
+  operator bool() { return First && Binding; }
+  MemRegion* getRegion() { return Binding; }
+};  
+}
+
+static std::pair<ExplodedNode<GRState>*,MemRegion*>
 GetAllocationSite(GRStateManager* StateMgr, ExplodedNode<GRState>* N,
                   SymbolID Sym) {
 
   // Find both first node that referred to the tracked symbol and the
   // memory location that value was store to.
   ExplodedNode<GRState>* Last = N;
-  store::Binding FirstBinding;  
+  MemRegion* FirstBinding = 0;  
   
   while (N) {
     const GRState* St = N->getState();
@@ -2324,11 +2368,9 @@ GetAllocationSite(GRStateManager* StateMgr, ExplodedNode<GRState>* N,
       break;
 
     if (StateMgr) {
-      llvm::SmallVector<store::Binding, 5> Bindings;
-      StateMgr->getBindings(Bindings, St, Sym);
-
-      if (Bindings.size() == 1)
-        FirstBinding = Bindings[0];
+      FindUniqueBinding FB(Sym);
+      StateMgr->iterBindings(St, FB);      
+      if (FB) FirstBinding = FB.getRegion();      
     }
     
     Last = N;
@@ -2357,7 +2399,7 @@ PathDiagnosticPiece* CFRefReport::getEndPath(BugReporter& br,
   // symbol appeared, and also get the first VarDecl that tracked object
   // is stored to.
   ExplodedNode<GRState>* AllocNode = 0;
-  store::Binding FirstBinding;
+  MemRegion* FirstBinding = 0;
 
   llvm::tie(AllocNode, FirstBinding) =
     GetAllocationSite(&BR.getStateManager(), EndN, Sym);
@@ -2413,8 +2455,8 @@ PathDiagnosticPiece* CFRefReport::getEndPath(BugReporter& br,
   os << "Object allocated on line " << AllocLine;
   
   if (FirstBinding)
-    os << " and stored into '" 
-       << BR.getStateManager().BindingAsString(FirstBinding) << '\'';    
+    os << " and stored into '" << FirstBinding->getString() << '\'';  
+  
   os << " is no longer referenced after this point and has a retain count of +"
      << RetCount << " (object leaked).";