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.


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

1 files changed, 102 insertions, 78 deletions

diff --git a/lib/Analysis/BugReporter.cpp b/lib/Analysis/BugReporter.cpp
index 6a1478a9cb..e56da7b872 100644
--- a/lib/Analysis/BugReporter.cpp
+++ b/lib/Analysis/BugReporter.cpp
@@ -322,32 +322,27 @@ static VarDecl* GetMostRecentVarDeclBinding(ExplodedNode<GRState>* N,
   return 0;
 }
 
+namespace {
+class VISIBILITY_HIDDEN NotableSymbolHandler 
+  : public StoreManager::BindingsHandler {
+    
+  SymbolID Sym;
+  const GRState* PrevSt;
+  Stmt* S;
+  GRStateManager& VMgr;
+  ExplodedNode<GRState>* Pred;
+  PathDiagnostic& PD; 
+  BugReporter& BR;
+    
+public:
+  
+  NotableSymbolHandler(SymbolID sym, const GRState* prevst, Stmt* s,
+                       GRStateManager& vmgr, ExplodedNode<GRState>* pred,
+                       PathDiagnostic& pd, BugReporter& br)
+    : Sym(sym), PrevSt(prevst), S(s), VMgr(vmgr), Pred(pred), PD(pd), BR(br) {}
+                        
+  bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal V) {
 
-static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
-                                SymbolID Sym, BugReporter& BR,
-                                PathDiagnostic& PD) {
-  
-  ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin();
-  const GRState* PrevSt = Pred ? Pred->getState() : 0;
-  
-  if (!PrevSt)
-    return;
-  
-  // Look at the variable bindings of the current state that map to the
-  // specified symbol.  Are any of them not in the previous state.
-  
-  const GRState* St = N->getState();
-  GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
-  
-  // FIXME: Later generalize for a broader memory model.
-
-  // FIXME: This is quadratic, since its nested in another loop.  Probably
-  //   doesn't matter, but keep an eye out for performance issues.  It's
-  //   also a bunch of copy-paste.  Bad.  Cleanup later.
-  
-  for (GRState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E; ++I){
-    
-    RVal V = I.getData();
     SymbolID ScanSym;
     
     if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V))
@@ -355,18 +350,17 @@ static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
     else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V))
       ScanSym = SV->getSymbol();
     else
-      continue;
+      return true;
     
     if (ScanSym != Sym)
-      continue;
-    
-    // Check if the previous state has this binding.
+      return true;
     
-    RVal X = VMgr.GetRVal(PrevSt, lval::DeclVal(I.getKey()));
+    // Check if the previous state has this binding.    
+    RVal X = VMgr.GetRVal(PrevSt, lval::MemRegionVal(R));
     
     if (X == V) // Same binding?
-      continue;
-
+      return true;
+    
     // Different binding.  Only handle assignments for now.  We don't pull
     // this check out of the loop because we will eventually handle other 
     // cases.
@@ -375,41 +369,102 @@ static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
     
     if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
       if (!B->isAssignmentOp())
-        continue;
+        return true;
       
       // What variable did we assign to?
       DeclRefExpr* DR = dyn_cast<DeclRefExpr>(B->getLHS()->IgnoreParenCasts());
       
       if (!DR)
-        continue;
+        return true;
       
       VD = dyn_cast<VarDecl>(DR->getDecl());
     }
     else if (DeclStmt* DS = dyn_cast<DeclStmt>(S))
       VD = dyn_cast<VarDecl>(DS->getDecl());
-      
+    
     if (!VD)
-      continue;
-      
+      return true;
+    
     // What is the most recently referenced variable with this binding?
     VarDecl* MostRecent = GetMostRecentVarDeclBinding(Pred, VMgr, V);
-        
+    
     if (!MostRecent)
-      continue;
-
+      return true;
+    
     // Create the diagnostic.
     
     FullSourceLoc L(S->getLocStart(), BR.getSourceManager());
-      
+    
     if (VD->getType()->isPointerLikeType()) {
       std::string msg = "'" + std::string(VD->getName()) +
-                        "' now aliases '" + MostRecent->getName() + "'";
+      "' now aliases '" + MostRecent->getName() + "'";
       
       PD.push_front(new PathDiagnosticPiece(L, msg));
     }
-  }
+    
+    return true;
+  }  
+};
 }
 
+static void HandleNotableSymbol(ExplodedNode<GRState>* N, Stmt* S,
+                                SymbolID Sym, BugReporter& BR,
+                                PathDiagnostic& PD) {
+  
+  ExplodedNode<GRState>* Pred = N->pred_empty() ? 0 : *N->pred_begin();
+  const GRState* PrevSt = Pred ? Pred->getState() : 0;
+  
+  if (!PrevSt)
+    return;
+  
+  // Look at the region bindings of the current state that map to the
+  // specified symbol.  Are any of them not in the previous state?
+  GRStateManager& VMgr = cast<GRBugReporter>(BR).getStateManager();
+  NotableSymbolHandler H(Sym, PrevSt, S, VMgr, Pred, PD, BR);
+  cast<GRBugReporter>(BR).getStateManager().iterBindings(N->getState(), H);
+}
+
+namespace {
+class VISIBILITY_HIDDEN ScanNotableSymbols
+  : public StoreManager::BindingsHandler {
+    
+  llvm::SmallSet<SymbolID, 10> AlreadyProcessed;
+  ExplodedNode<GRState>* N;
+  Stmt* S;
+  GRBugReporter& BR;
+  PathDiagnostic& PD;
+    
+public:
+  ScanNotableSymbols(ExplodedNode<GRState>* n, Stmt* s, GRBugReporter& br,
+                     PathDiagnostic& pd)
+    : N(n), S(s), BR(br), PD(pd) {}
+  
+  bool HandleBinding(StoreManager& SMgr, Store store, MemRegion* R, RVal V) {
+    SymbolID ScanSym;
+  
+    if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V))
+      ScanSym = SV->getSymbol();
+    else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V))
+      ScanSym = SV->getSymbol();
+    else
+      return true;
+  
+    assert (ScanSym.isInitialized());
+  
+    if (!BR.isNotable(ScanSym))
+      return true;
+  
+    if (AlreadyProcessed.count(ScanSym))
+      return true;
+  
+    AlreadyProcessed.insert(ScanSym);
+  
+    HandleNotableSymbol(N, S, ScanSym, BR, PD);
+    return true;
+  }
+};
+} // end anonymous namespace
+
 void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
                                            BugReport& R) {
 
@@ -633,42 +688,11 @@ void GRBugReporter::GeneratePathDiagnostic(PathDiagnostic& PD,
     if (PathDiagnosticPiece* p = R.VisitNode(N, NextNode, *ReportGraph, *this))
       PD.push_front(p);
     
-    if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {
-      
-      const GRState* St = N->getState();
-      
-      // Scan the lval bindings, and see if a "notable" symbol has a new
+    if (const PostStmt* PS = dyn_cast<PostStmt>(&P)) {      
+      // Scan the region bindings, and see if a "notable" symbol has a new
       // lval binding.
-      
-      // FIXME: In the future, when we generalize the memory model, we'll
-      //  need a way to iterate over binded locations.
-      
-      llvm::SmallSet<SymbolID, 10> AlreadyProcessed;
-      
-      for (GRState::vb_iterator I=St->vb_begin(), E=St->vb_end(); I!=E; ++I){
-        
-        RVal V = I.getData();
-        SymbolID ScanSym;
-        
-        if (lval::SymbolVal* SV = dyn_cast<lval::SymbolVal>(&V))
-          ScanSym = SV->getSymbol();
-        else if (nonlval::SymbolVal* SV = dyn_cast<nonlval::SymbolVal>(&V))
-          ScanSym = SV->getSymbol();
-        else
-          continue;
-        
-        assert (ScanSym.isInitialized());
-        
-        if (!isNotable(ScanSym))
-          continue;
-        
-        if (AlreadyProcessed.count(ScanSym))
-          continue;
-        
-        AlreadyProcessed.insert(ScanSym);
-        
-        HandleNotableSymbol(N, PS->getStmt(), ScanSym, *this, PD);        
-      }
+      ScanNotableSymbols SNS(N, PS->getStmt(), *this, PD);
+      getStateManager().iterBindings(N->getState(), SNS);
     }
   }
 }