From 7740c6d643765f390254706284824b090f985461 Mon Sep 17 00:00:00 2001 From: Csaba Dabis Date: Thu, 1 Aug 2019 20:41:13 +0000 Subject: [PATCH] [analyzer] StackFrameContext: Add NodeBuilderContext::blockCount() to its profile Summary: It allows discriminating between stack frames of the same call that is called multiple times in a loop. Thanks to Artem Dergachev for the great idea! Reviewed By: NoQ Tags: #clang Differential Revision: https://reviews.llvm.org/D65587 llvm-svn: 367608 --- clang/include/clang/Analysis/AnalysisDeclContext.h | 49 ++++++++++++---------- .../StaticAnalyzer/Core/PathSensitive/CallEvent.h | 5 ++- clang/lib/Analysis/AnalysisDeclContext.cpp | 21 +++++----- clang/lib/StaticAnalyzer/Core/CallEvent.cpp | 12 +++--- clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp | 5 ++- .../Core/ExprEngineCallAndReturn.cpp | 5 +-- clang/test/Analysis/loop-block-counts.c | 2 +- clang/test/Analysis/loop-unrolling.cpp | 10 ++--- .../test/Analysis/stack-frame-context-revision.cpp | 37 ++++++++++++++++ 9 files changed, 95 insertions(+), 51 deletions(-) create mode 100644 clang/test/Analysis/stack-frame-context-revision.cpp diff --git a/clang/include/clang/Analysis/AnalysisDeclContext.h b/clang/include/clang/Analysis/AnalysisDeclContext.h index 1961d57..d5445d3 100644 --- a/clang/include/clang/Analysis/AnalysisDeclContext.h +++ b/clang/include/clang/Analysis/AnalysisDeclContext.h @@ -183,9 +183,8 @@ public: const ImplicitParamDecl *getSelfDecl() const; const StackFrameContext *getStackFrame(LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx); + const Stmt *S, const CFGBlock *Blk, + unsigned BlockCount, unsigned Idx); const BlockInvocationContext * getBlockInvocationContext(const LocationContext *parent, @@ -303,15 +302,19 @@ class StackFrameContext : public LocationContext { // The parent block of the callsite. const CFGBlock *Block; + // The number of times the 'Block' has been visited. + // It allows discriminating between stack frames of the same call that is + // called multiple times in a loop. + const unsigned BlockCount; + // The index of the callsite in the CFGBlock. - unsigned Index; + const unsigned Index; StackFrameContext(AnalysisDeclContext *ctx, const LocationContext *parent, - const Stmt *s, const CFGBlock *blk, - unsigned idx, - int64_t ID) - : LocationContext(StackFrame, ctx, parent, ID), CallSite(s), - Block(blk), Index(idx) {} + const Stmt *s, const CFGBlock *blk, unsigned blockCount, + unsigned idx, int64_t ID) + : LocationContext(StackFrame, ctx, parent, ID), CallSite(s), Block(blk), + BlockCount(blockCount), Index(idx) {} public: ~StackFrameContext() override = default; @@ -329,9 +332,10 @@ public: static void Profile(llvm::FoldingSetNodeID &ID, AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s, - const CFGBlock *blk, unsigned idx) { + const CFGBlock *blk, unsigned blockCount, unsigned idx) { ProfileCommon(ID, StackFrame, ctx, parent, s); ID.AddPointer(blk); + ID.AddInteger(blockCount); ID.AddInteger(idx); } @@ -410,8 +414,8 @@ public: const StackFrameContext *getStackFrame(AnalysisDeclContext *ctx, const LocationContext *parent, - const Stmt *s, - const CFGBlock *blk, unsigned idx); + const Stmt *s, const CFGBlock *blk, + unsigned blockCount, unsigned idx); const ScopeContext *getScope(AnalysisDeclContext *ctx, const LocationContext *parent, @@ -483,26 +487,25 @@ public: bool synthesizeBodies() const { return SynthesizeBodies; } const StackFrameContext *getStackFrame(AnalysisDeclContext *Ctx, - LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx) { - return LocContexts.getStackFrame(Ctx, Parent, S, Blk, Idx); + const LocationContext *Parent, + const Stmt *S, const CFGBlock *Blk, + unsigned BlockCount, unsigned Idx) { + return LocContexts.getStackFrame(Ctx, Parent, S, Blk, BlockCount, Idx); } // Get the top level stack frame. const StackFrameContext *getStackFrame(const Decl *D) { return LocContexts.getStackFrame(getContext(D), nullptr, nullptr, nullptr, - 0); + 0, 0); } // Get a stack frame with parent. StackFrameContext const *getStackFrame(const Decl *D, - LocationContext const *Parent, - const Stmt *S, - const CFGBlock *Blk, - unsigned Idx) { - return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, Idx); + const LocationContext *Parent, + const Stmt *S, const CFGBlock *Blk, + unsigned BlockCount, unsigned Idx) { + return LocContexts.getStackFrame(getContext(D), Parent, S, Blk, BlockCount, + Idx); } /// Get a reference to {@code BodyFarm} instance. diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h index db84102..b2826a8 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h @@ -386,11 +386,12 @@ public: /// during analysis if the call is inlined, but it may still be useful /// in intermediate calculations even if the call isn't inlined. /// May fail; returns null on failure. - const StackFrameContext *getCalleeStackFrame() const; + const StackFrameContext *getCalleeStackFrame(unsigned BlockCount) const; /// Returns memory location for a parameter variable within the callee stack /// frame. May fail; returns null on failure. - const VarRegion *getParameterLocation(unsigned Index) const; + const VarRegion *getParameterLocation(unsigned Index, + unsigned BlockCount) const; /// Returns true if on the current path, the argument was constructed by /// calling a C++ constructor over it. This is an internal detail of the diff --git a/clang/lib/Analysis/AnalysisDeclContext.cpp b/clang/lib/Analysis/AnalysisDeclContext.cpp index b6a429f..5ecb3ff 100644 --- a/clang/lib/Analysis/AnalysisDeclContext.cpp +++ b/clang/lib/Analysis/AnalysisDeclContext.cpp @@ -310,8 +310,10 @@ BodyFarm &AnalysisDeclContextManager::getBodyFarm() { return FunctionBodyFarm; } const StackFrameContext * AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, - const CFGBlock *Blk, unsigned Idx) { - return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); + const CFGBlock *Blk, unsigned BlockCount, + unsigned Idx) { + return getLocationContextManager().getStackFrame(this, Parent, S, Blk, + BlockCount, Idx); } const BlockInvocationContext * @@ -359,7 +361,8 @@ void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, } void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { - Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); + Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, + BlockCount, Index); } void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { @@ -392,18 +395,16 @@ LocationContextManager::getLocationContext(AnalysisDeclContext *ctx, return L; } -const StackFrameContext* -LocationContextManager::getStackFrame(AnalysisDeclContext *ctx, - const LocationContext *parent, - const Stmt *s, - const CFGBlock *blk, unsigned idx) { +const StackFrameContext *LocationContextManager::getStackFrame( + AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s, + const CFGBlock *blk, unsigned blockCount, unsigned idx) { llvm::FoldingSetNodeID ID; - StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); + StackFrameContext::Profile(ID, ctx, parent, s, blk, blockCount, idx); void *InsertPos; auto *L = cast_or_null(Contexts.FindNodeOrInsertPos(ID, InsertPos)); if (!L) { - L = new StackFrameContext(ctx, parent, s, blk, idx, ++NewID); + L = new StackFrameContext(ctx, parent, s, blk, blockCount, idx, ++NewID); Contexts.InsertNode(L, InsertPos); } return L; diff --git a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp index a5f7500..b6f551d 100644 --- a/clang/lib/StaticAnalyzer/Core/CallEvent.cpp +++ b/clang/lib/StaticAnalyzer/Core/CallEvent.cpp @@ -191,7 +191,8 @@ AnalysisDeclContext *CallEvent::getCalleeAnalysisDeclContext() const { return ADC; } -const StackFrameContext *CallEvent::getCalleeStackFrame() const { +const StackFrameContext * +CallEvent::getCalleeStackFrame(unsigned BlockCount) const { AnalysisDeclContext *ADC = getCalleeAnalysisDeclContext(); if (!ADC) return nullptr; @@ -217,11 +218,12 @@ const StackFrameContext *CallEvent::getCalleeStackFrame() const { break; assert(Idx < Sz); - return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, Idx); + return ADC->getManager()->getStackFrame(ADC, LCtx, E, B, BlockCount, Idx); } -const VarRegion *CallEvent::getParameterLocation(unsigned Index) const { - const StackFrameContext *SFC = getCalleeStackFrame(); +const VarRegion *CallEvent::getParameterLocation(unsigned Index, + unsigned BlockCount) const { + const StackFrameContext *SFC = getCalleeStackFrame(BlockCount); // We cannot construct a VarRegion without a stack frame. if (!SFC) return nullptr; @@ -322,7 +324,7 @@ ProgramStateRef CallEvent::invalidateRegions(unsigned BlockCount, if (getKind() != CE_CXXAllocator) if (isArgumentConstructedDirectly(Idx)) if (auto AdjIdx = getAdjustedParameterIndex(Idx)) - if (const VarRegion *VR = getParameterLocation(*AdjIdx)) + if (const VarRegion *VR = getParameterLocation(*AdjIdx, BlockCount)) ValuesToInvalidate.push_back(loc::MemRegionVal(VR)); } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp index 1cbd09e..10c8cb1 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCXX.cpp @@ -323,7 +323,8 @@ std::pair ExprEngine::prepareForObjectConstruction( CallEventManager &CEMgr = getStateManager().getCallEventManager(); SVal V = UnknownVal(); auto getArgLoc = [&](CallEventRef<> Caller) -> Optional { - const LocationContext *FutureSFC = Caller->getCalleeStackFrame(); + const LocationContext *FutureSFC = + Caller->getCalleeStackFrame(currBldrCtx->blockCount()); // Return early if we are unable to reliably foresee // the future stack frame. if (!FutureSFC) @@ -342,7 +343,7 @@ std::pair ExprEngine::prepareForObjectConstruction( // because this-argument is implemented as a normal argument in // operator call expressions but not in operator declarations. const VarRegion *VR = Caller->getParameterLocation( - *Caller->getAdjustedParameterIndex(Idx)); + *Caller->getAdjustedParameterIndex(Idx), currBldrCtx->blockCount()); if (!VR) return None; diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index b935e3a..345d4d8 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -451,9 +451,8 @@ bool ExprEngine::inlineCall(const CallEvent &Call, const Decl *D, // Construct a new stack frame for the callee. AnalysisDeclContext *CalleeADC = AMgr.getAnalysisDeclContext(D); const StackFrameContext *CalleeSFC = - CalleeADC->getStackFrame(ParentOfCallee, CallE, - currBldrCtx->getBlock(), - currStmtIdx); + CalleeADC->getStackFrame(ParentOfCallee, CallE, currBldrCtx->getBlock(), + currBldrCtx->blockCount(), currStmtIdx); CallEnter Loc(CallE, CalleeSFC, CurLC); diff --git a/clang/test/Analysis/loop-block-counts.c b/clang/test/Analysis/loop-block-counts.c index 04a3f74..66bb850 100644 --- a/clang/test/Analysis/loop-block-counts.c +++ b/clang/test/Analysis/loop-block-counts.c @@ -12,7 +12,7 @@ void loop() { for (int i = 0; i < 2; ++i) callee(&arr[i]); // FIXME: Should be UNKNOWN. - clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{TRUE}} + clang_analyzer_eval(arr[0] == arr[1]); // expected-warning{{FALSE}} } void loopWithCall() { diff --git a/clang/test/Analysis/loop-unrolling.cpp b/clang/test/Analysis/loop-unrolling.cpp index b7375df..761bf5a 100644 --- a/clang/test/Analysis/loop-unrolling.cpp +++ b/clang/test/Analysis/loop-unrolling.cpp @@ -347,9 +347,9 @@ int simple_known_bound_loop() { int simple_unknown_bound_loop() { for (int i = 2; i < getNum(); i++) { #ifdef DFS - clang_analyzer_numTimesReached(); // expected-warning {{10}} + clang_analyzer_numTimesReached(); // expected-warning {{16}} #else - clang_analyzer_numTimesReached(); // expected-warning {{13}} + clang_analyzer_numTimesReached(); // expected-warning {{8}} #endif } return 0; @@ -368,10 +368,10 @@ int nested_inlined_unroll1() { int nested_inlined_no_unroll1() { int k; for (int i = 0; i < 9; i++) { -#ifdef ANALYZER_CM_Z3 - clang_analyzer_numTimesReached(); // expected-warning {{13}} +#ifdef DFS + clang_analyzer_numTimesReached(); // expected-warning {{18}} #else - clang_analyzer_numTimesReached(); // expected-warning {{15}} + clang_analyzer_numTimesReached(); // expected-warning {{14}} #endif k = simple_unknown_bound_loop(); // reevaluation without inlining, splits the state as well } diff --git a/clang/test/Analysis/stack-frame-context-revision.cpp b/clang/test/Analysis/stack-frame-context-revision.cpp new file mode 100644 index 0000000..8c119f5 --- /dev/null +++ b/clang/test/Analysis/stack-frame-context-revision.cpp @@ -0,0 +1,37 @@ +// RUN: %clang_analyze_cc1 -analyzer-checker=core,cplusplus.NewDelete -verify %s + +// expected-no-diagnostics: +// From now the profile of the 'StackFrameContext' also contains the +// 'NodeBuilderContext::blockCount()'. With this addition we can distinguish +// between the 'StackArgumentsSpaceRegion' of the 'P' arguments being different +// on every iteration. + +typedef __INTPTR_TYPE__ intptr_t; + +template +struct SmarterPointer { + PointerTy getFromVoidPointer(void *P) const { + return static_cast(P); + } + + PointerTy getPointer() const { + return getFromVoidPointer(reinterpret_cast(Value)); + } + + intptr_t Value = 13; +}; + +struct Node { + SmarterPointer Pred; +}; + +void test(Node *N) { + while (N) { + SmarterPointer Next = N->Pred; + delete N; + + N = Next.getPointer(); + // no-warning: 'Use of memory after it is freed' was here as the same + // 'StackArgumentsSpaceRegion' purged out twice as 'P'. + } +} -- 2.7.4