From 0849ade4bb3e90c2fc0ce01ccd330f76f91da732 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Thu, 12 Jan 2012 19:25:46 +0000 Subject: [PATCH] [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 --- .../Core/PathSensitive/ProgramState.h | 3 +- .../StaticAnalyzer/Core/PathSensitive/Store.h | 3 +- .../Core/ExprEngineCallAndReturn.cpp | 25 +++++++++++++--- lib/StaticAnalyzer/Core/ProgramState.cpp | 6 ++-- lib/StaticAnalyzer/Core/RegionStore.cpp | 25 +++++++++------- lib/StaticAnalyzer/Core/Store.cpp | 3 +- test/Analysis/inline.c | 30 +++++++++++++++++++ 7 files changed, 76 insertions(+), 19 deletions(-) diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index af7845af6c..2987116e4f 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/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/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h index 20b9346137..52ea37c431 100644 --- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h +++ b/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/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(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(frame->getDecl()); + const LocationContext *callerCtx, + const StackFrameContext *calleeCtx) +{ + FunctionDecl const *FD = cast(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(frame->getCallSite())) { + if (CallExpr const *CE = dyn_cast(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(frame->getCallSite())) { + dyn_cast(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(frame->getDecl())); + assert(isa(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); } diff --git a/test/Analysis/inline.c b/test/Analysis/inline.c index e3c7e83893..de807fb3aa 100644 --- a/test/Analysis/inline.c +++ b/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 + } +} -- 2.40.0