[analyzer] fix inlining's handling of mapping actual to formal arguments and limit the call stack depth. The analyzer can now accurately simulate factorial for limited depths.

llvm-svn: 148036

7 files changed, 76 insertions, 19 deletions

diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
index af7845af6c1..2987116e4f1 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h
@@ -227,7 +227,8 @@ public:
 
   /// enterStackFrame - Returns the state for entry to the given stack frame,
   ///  preserving the current state.
-  const ProgramState *enterStackFrame(const StackFrameContext *frame) const;
+  const ProgramState *enterStackFrame(const LocationContext *callerCtx,
+                                      const StackFrameContext *calleeCtx) const;
 
   /// Get the lvalue for a variable reference.
   Loc getLValue(const VarDecl *D, const LocationContext *LC) const;
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
index 20b93461376..52ea37c4314 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
@@ -197,7 +197,8 @@ public:
   /// enterStackFrame - Let the StoreManager to do something when execution
   /// engine is about to execute into a callee.
   virtual StoreRef enterStackFrame(const ProgramState *state,
-                                   const StackFrameContext *frame);
+                                   const LocationContext *callerCtx,
+                                   const StackFrameContext *calleeCtx);
 
   virtual void print(Store store, raw_ostream &Out,
                      const char* nl, const char *sep) = 0;
diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index 81472fae6c3..ed58cd4a412 100644
--- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
@@ -22,8 +22,8 @@ using namespace ento;
 
 void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
   // Get the entry block in the CFG of the callee.
-  const StackFrameContext *SFC = CE.getCalleeContext();
-  const CFG *CalleeCFG = SFC->getCFG();
+  const StackFrameContext *calleeCtx = CE.getCalleeContext();
+  const CFG *CalleeCFG = calleeCtx->getCFG();
   const CFGBlock *Entry = &(CalleeCFG->getEntry());
   
   // Validate the CFG.
@@ -34,11 +34,13 @@ void ExprEngine::processCallEnter(CallEnter CE, ExplodedNode *Pred) {
   const CFGBlock *Succ = *(Entry->succ_begin());
   
   // Construct an edge representing the starting location in the callee.
-  BlockEdge Loc(Entry, Succ, SFC);
+  BlockEdge Loc(Entry, Succ, calleeCtx);
 
   // Construct a new state which contains the mapping from actual to
   // formal arguments.
-  const ProgramState *state = Pred->getState()->enterStackFrame(SFC);
+  const LocationContext *callerCtx = Pred->getLocationContext();
+  const ProgramState *state = Pred->getState()->enterStackFrame(callerCtx,
+                                                                calleeCtx);
   
   // Construct a new node and add it to the worklist.
   bool isNew;
@@ -115,6 +117,16 @@ void ExprEngine::processCallExit(ExplodedNode *Pred) {
   }
 }
 
+static unsigned getNumberStackFrames(const LocationContext *LCtx) {
+  unsigned count = 0;
+  while (LCtx) {
+    if (isa<StackFrameContext>(LCtx))
+      ++count;
+    LCtx = LCtx->getParent();
+  }
+  return count;  
+}
+
 bool ExprEngine::InlineCall(ExplodedNodeSet &Dst,
                             const CallExpr *CE, 
                             ExplodedNode *Pred) {
@@ -130,6 +142,11 @@ bool ExprEngine::InlineCall(ExplodedNodeSet &Dst,
       // FIXME: Handle C++.
       break;
     case Stmt::CallExprClass: {
+      // Cap the stack depth at 4 calls (5 stack frames, base + 4 calls).
+      // These heuristics are a WIP.
+      if (getNumberStackFrames(Pred->getLocationContext()) == 5)
+        return false;
+      
       // Construct a new stack frame for the callee.
       AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(FD);
       const StackFrameContext *CallerSFC =
diff --git a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
index 86a9ac03578..5eb0e06bca5 100644
--- a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -180,9 +180,11 @@ const ProgramState *ProgramState::unbindLoc(Loc LV) const {
   return makeWithStore(newStore);
 }
 
-const ProgramState *ProgramState::enterStackFrame(const StackFrameContext *frame) const {
+const ProgramState *
+ProgramState::enterStackFrame(const LocationContext *callerCtx,
+                              const StackFrameContext *calleeCtx) const {
   const StoreRef &new_store =
-    getStateManager().StoreMgr->enterStackFrame(this, frame);
+    getStateManager().StoreMgr->enterStackFrame(this, callerCtx, calleeCtx);
   return makeWithStore(new_store);
 }
 
diff --git a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp
index d2234150ddd..5bd7d726750 100644
--- a/clang/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/clang/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -380,7 +380,8 @@ public: // Part of public interface to class.
                               SymbolReaper& SymReaper);
 
   StoreRef enterStackFrame(const ProgramState *state,
-                           const StackFrameContext *frame);
+                           const LocationContext *callerCtx,
+                           const StackFrameContext *calleeCtx);
 
   //===------------------------------------------------------------------===//
   // Region "extents".
@@ -1855,36 +1856,40 @@ StoreRef RegionStoreManager::removeDeadBindings(Store store,
 
 
 StoreRef RegionStoreManager::enterStackFrame(const ProgramState *state,
-                                             const StackFrameContext *frame) {
-  FunctionDecl const *FD = cast<FunctionDecl>(frame->getDecl());
+                                             const LocationContext *callerCtx,
+                                             const StackFrameContext *calleeCtx)
+{
+  FunctionDecl const *FD = cast<FunctionDecl>(calleeCtx->getDecl());
   FunctionDecl::param_const_iterator PI = FD->param_begin(), 
                                      PE = FD->param_end();
   StoreRef store = StoreRef(state->getStore(), *this);
 
-  if (CallExpr const *CE = dyn_cast<CallExpr>(frame->getCallSite())) {
+  if (CallExpr const *CE = dyn_cast<CallExpr>(calleeCtx->getCallSite())) {
     CallExpr::const_arg_iterator AI = CE->arg_begin(), AE = CE->arg_end();
 
     // Copy the arg expression value to the arg variables.  We check that
     // PI != PE because the actual number of arguments may be different than
     // the function declaration.
     for (; AI != AE && PI != PE; ++AI, ++PI) {
-      SVal ArgVal = state->getSVal(*AI, frame);
+      SVal ArgVal = state->getSVal(*AI, callerCtx);
       store = Bind(store.getStore(),
-                   svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, frame)), ArgVal);
+                   svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)),
+                   ArgVal);
     }
   } else if (const CXXConstructExpr *CE =
-               dyn_cast<CXXConstructExpr>(frame->getCallSite())) {
+               dyn_cast<CXXConstructExpr>(calleeCtx->getCallSite())) {
     CXXConstructExpr::const_arg_iterator AI = CE->arg_begin(),
       AE = CE->arg_end();
 
     // Copy the arg expression value to the arg variables.
     for (; AI != AE; ++AI, ++PI) {
-      SVal ArgVal = state->getSVal(*AI, frame);
+      SVal ArgVal = state->getSVal(*AI, callerCtx);
       store = Bind(store.getStore(),
-                   svalBuilder.makeLoc(MRMgr.getVarRegion(*PI,frame)), ArgVal);
+                   svalBuilder.makeLoc(MRMgr.getVarRegion(*PI, calleeCtx)),
+                   ArgVal);
     }
   } else
-    assert(isa<CXXDestructorDecl>(frame->getDecl()));
+    assert(isa<CXXDestructorDecl>(calleeCtx->getDecl()));
 
   return store;
 }
diff --git a/clang/lib/StaticAnalyzer/Core/Store.cpp b/clang/lib/StaticAnalyzer/Core/Store.cpp
index 543f87879d4..bbe0a1cfe30 100644
--- a/clang/lib/StaticAnalyzer/Core/Store.cpp
+++ b/clang/lib/StaticAnalyzer/Core/Store.cpp
@@ -23,7 +23,8 @@ StoreManager::StoreManager(ProgramStateManager &stateMgr)
     MRMgr(svalBuilder.getRegionManager()), Ctx(stateMgr.getContext()) {}
 
 StoreRef StoreManager::enterStackFrame(const ProgramState *state,
-                                       const StackFrameContext *frame) {
+                                       const LocationContext *callerCtx,
+                                       const StackFrameContext *calleeCtx) {
   return StoreRef(state->getStore(), *this);
 }
 
diff --git a/clang/test/Analysis/inline.c b/clang/test/Analysis/inline.c
index e3c7e838934..de807fb3aad 100644
--- a/clang/test/Analysis/inline.c
+++ b/clang/test/Analysis/inline.c
@@ -28,3 +28,33 @@ void test2_f3() {
   test2_f1(test2_f2()); // expected-warning{{too many arguments in call to 'test2_f1'}}
 }
 
+// Test that inlining works with recursive functions.
+
+unsigned factorial(unsigned x) {
+  if (x <= 1)
+    return 1;
+  return x * factorial(x - 1);
+}
+
+void test_factorial() {
+  if (factorial(3) == 6) {
+    int *p = 0;
+    *p = 0xDEADBEEF;  // expected-warning {{null}}
+  }
+  else {
+    int *p = 0;
+    *p = 0xDEADBEEF; // no-warning
+  }
+}
+
+void test_factorial_2() {
+  unsigned x = factorial(3);
+  if (x == factorial(3)) {
+    int *p = 0;
+    *p = 0xDEADBEEF;  // expected-warning {{null}}
+  }
+  else {
+    int *p = 0;
+    *p = 0xDEADBEEF; // no-warning
+  }
+}