[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.

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

4 files changed, 42 insertions, 17 deletions

diff --git a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
index 81472fae6c..ed58cd4a41 100644
--- a/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp
+++ b/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/lib/StaticAnalyzer/Core/ProgramState.cpp b/lib/StaticAnalyzer/Core/ProgramState.cpp
index 86a9ac0357..5eb0e06bca 100644
--- a/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/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/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index d2234150dd..5bd7d72675 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/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/lib/StaticAnalyzer/Core/Store.cpp b/lib/StaticAnalyzer/Core/Store.cpp
index 543f87879d..bbe0a1cfe3 100644
--- a/lib/StaticAnalyzer/Core/Store.cpp
+++ b/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);
 }