https://github.com/NagyDonat updated https://github.com/llvm/llvm-project/pull/215284
From 9f76f5d4fe0c17e6b48438ef01a10177e1c0119f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 30 Jul 2026 16:56:10 +0200 Subject: [PATCH 01/12] Hoist HasGeneratedNodes to its only usecase Instances of class `NodeBuilder` had a boolean member called `HasGeneratedNodes` which was initialized to false and then updated to true when `generateNode` was called (directly or indirectly through `generateSink` etc., even if the node creation cached out). This feature was only relevant in the method `processCFGBlockEntrance` where it heavily contributed to the code complexity. To prepare for the untangling of this Gordian knot, this commit removes `HasGeneratedNodes` from `NodeBuilder` and reintroduces it as a local variable in `processCFGBlockEntrance` (the only place where it's relevant). This change inserts `HasGeneratedNodes = true` before the three `generateNode()` calls reachable from `processCFGBlockEntrance` and returns this boolean from `processCFGBlockEntrance` to the only location where `hasGeneratedNodes()` is called. --- .../Core/PathSensitive/CoreEngine.h | 4 ---- .../Core/PathSensitive/ExprEngine.h | 3 ++- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 5 ++--- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 17 +++++++++++------ 4 files changed, 15 insertions(+), 14 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index d56d8df8efd31..2a7264009b076 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -266,8 +266,6 @@ class NodeBuilder { protected: const NodeBuilderContext &C; - bool HasGeneratedNodes = false; - /// The frontier set - a set of nodes which need to be propagated after /// the builder dies. ExplodedNodeSet &Frontier; @@ -325,8 +323,6 @@ class NodeBuilder { const ExplodedNodeSet &getResults() const { return Frontier; } - bool hasGeneratedNodes() const { return HasGeneratedNodes; } - void takeNodes(const ExplodedNodeSet &S) { for (const auto I : S) Frontier.erase(I); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index bd50674fa428b..98dc54393be02 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -388,7 +388,8 @@ class ExprEngine { ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Called by CoreEngine when processing the entrance of a CFGBlock. - void processCFGBlockEntrance(const BlockEntrance &BE, NodeBuilder &Builder, + /// Returns true if it has generated a new node. + bool processCFGBlockEntrance(const BlockEntrance &BE, NodeBuilder &Builder, ExplodedNode *Pred); void runCheckersForBlockEntrance(const BlockEntrance &Entrance, diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 121a40cc58237..774ef81709d18 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -327,10 +327,10 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getStackFrame()); ExplodedNodeSet DstNodes; NodeBuilder Builder(Pred, DstNodes, ExprEng.getBuilderContext()); - ExprEng.processCFGBlockEntrance(BE, Builder, Pred); + bool HasGeneratedNodes = ExprEng.processCFGBlockEntrance(BE, Builder, Pred); // Auto-generate a node. - if (!Builder.hasGeneratedNodes()) { + if (!HasGeneratedNodes) { Builder.generateNode(BE, Pred->State, Pred); } @@ -681,7 +681,6 @@ void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS ExplodedNode *NodeBuilder::generateNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *FromN, bool MarkAsSink) { - HasGeneratedNodes = true; Frontier.erase(FromN); ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 07597769009ba..d47c1ff74cf9f 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2390,9 +2390,10 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, } /// Block entrance. (Update counters). -void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, +bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, NodeBuilder &Builder, ExplodedNode *Pred) { + bool HasGeneratedNodes = false; // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. if(AMgr.options.ShouldUnrollLoops) { @@ -2402,15 +2403,16 @@ void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), Pred, maxBlockVisitOnPath); if (NewState != Pred->getState()) { + HasGeneratedNodes = true; ExplodedNode *UpdatedNode = Builder.generateNode(BE, NewState, Pred); if (!UpdatedNode) - return; + return HasGeneratedNodes; Pred = UpdatedNode; } } // Is we are inside an unrolled loop then no need the check the counters. if(isUnrolledState(Pred->getState())) - return; + return HasGeneratedNodes; } // If this block is terminated by a loop and it has already been visited the @@ -2420,7 +2422,7 @@ void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, AMgr.options.ShouldWidenLoops) { const Stmt *Term = getCurrBlock()->getTerminatorStmt(); if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) - return; + return HasGeneratedNodes; // Widen. const StackFrame *SF = Pred->getStackFrame(); @@ -2433,14 +2435,16 @@ void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // Here we just pass the the first CFG element in the block. ProgramStateRef WidenedState = getWidenedLoopState( Pred->getState(), SF, BlockCount, *getCurrBlock()->ref_begin()); + HasGeneratedNodes = true; Builder.generateNode(BE, WidenedState, Pred); - return; + return HasGeneratedNodes; } // FIXME: Refactor this into a checker. if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded"); const ProgramPoint TaggedLoc = BE.withTag(&Tag); + HasGeneratedNodes = true; const ExplodedNode *Sink = Builder.generateSink(TaggedLoc, Pred->getState(), Pred); @@ -2462,7 +2466,7 @@ void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // the list. Replay should almost never fail. Use the stats to catch it // if it does. if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF))) - return; + return HasGeneratedNodes; NumMaxBlockCountReachedInInlined++; } else NumMaxBlockCountReached++; @@ -2470,6 +2474,7 @@ void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // Make sink nodes as exhausted(for stats) only if retry failed. Engine.blocksExhausted.push_back(std::make_pair(BE, Sink)); } + return HasGeneratedNodes; } void ExprEngine::runCheckersForBlockEntrance(const BlockEntrance &Entrance, From 55c84f85861fa4e50d0240042df95c07ca666cd8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 30 Jul 2026 18:08:05 +0200 Subject: [PATCH 02/12] Remove source argument from the construction of Builder The constructor of the `NodeBuilder` instance `Builder` was inserting `Pred` into the node set `DstNodes`, but this was always irrelevant, because either `processCFGBlockEntrance` called `generateNode` with `Pred` as its argument (which removed `Pred` from the frontier) or otherwise `HasGeneratedNodes` was false and then a `generateNode` call happened on the "Auto-generate" branch. --- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 774ef81709d18..b6eab63e00e2b 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -326,7 +326,7 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { // Call into the ExprEngine to process entering the CFGBlock. BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getStackFrame()); ExplodedNodeSet DstNodes; - NodeBuilder Builder(Pred, DstNodes, ExprEng.getBuilderContext()); + NodeBuilder Builder(DstNodes, ExprEng.getBuilderContext()); bool HasGeneratedNodes = ExprEng.processCFGBlockEntrance(BE, Builder, Pred); // Auto-generate a node. From ad46eac5c5dc72bb99ba332bc0a328393350a843 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 30 Jul 2026 18:35:18 +0200 Subject: [PATCH 03/12] Remove NodeBuilder from processCFGBlockEntrance This commit replaces `generateNode()` and `generateSink()` calls with the underlying `CoreEngine::makeNode()` call and replaces the `Frontier`-based logic with explicit handling of the `ExplodedNode`s. This function never generated more than one child from the same exploded node, so the `Frontier` (i.e. the set `DstNodes` at the call site) always contained at most one node. This commit eliminates the set `DstNodes` and ensures that `processCFGBlockEntrance` returns the one node that ends up in `DstNodes` after all the mutating steps: - When `processCFGBlockEntrance` generates a node in the loop unrolling step, that node is saved in `Pred` and then returned if later steps don't generate another node. - When `processCFGBlockEntrance` generates a node in the loop widening step, that node is immediately returned. (In this case the "block count exceeded" step was and is skipped.) - When `processCFGBlockEntrance` generates a sink node in the "block count exceeded" step, `nullptr` is returned to mirror the fact that trying to insert a sink node into a `NodeBuilderSet` has no effect. - If neither of these generated a node, `processCFGBlockEntrance` calls `MakeDefaultNode()` to perform the "Auto-transition" which was done by the block after the callsite of `processCFGBlockEntrance` in the old implementation. As `DstNodes` is eliminated, the `for` loop over it is replaced by an `if (Processed && !Processed->isSink())` check. (Here `isSink()` ensures equivalence with the old code in the rare corner case when a node becomes a sink because it has a `PosteriorlyOverconstrained` state.) Follow-up commits will make the code more idiomatic. --- .../Core/PathSensitive/ExprEngine.h | 6 ++-- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 14 +++------ clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 29 ++++++++++--------- 3 files changed, 23 insertions(+), 26 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 98dc54393be02..102595ee9bc1a 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -388,9 +388,9 @@ class ExprEngine { ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Called by CoreEngine when processing the entrance of a CFGBlock. - /// Returns true if it has generated a new node. - bool processCFGBlockEntrance(const BlockEntrance &BE, NodeBuilder &Builder, - ExplodedNode *Pred); + /// Returns nullptr or a node descending from Pred. + ExplodedNode *processCFGBlockEntrance(const BlockEntrance &BE, + ExplodedNode *Pred); void runCheckersForBlockEntrance(const BlockEntrance &Entrance, ExplodedNode *Pred, ExplodedNodeSet &Dst); diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index b6eab63e00e2b..d0096346b0990 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -325,18 +325,12 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { // Call into the ExprEngine to process entering the CFGBlock. BlockEntrance BE(L.getSrc(), L.getDst(), Pred->getStackFrame()); - ExplodedNodeSet DstNodes; - NodeBuilder Builder(DstNodes, ExprEng.getBuilderContext()); - bool HasGeneratedNodes = ExprEng.processCFGBlockEntrance(BE, Builder, Pred); - - // Auto-generate a node. - if (!HasGeneratedNodes) { - Builder.generateNode(BE, Pred->State, Pred); - } + ExplodedNode *Processed = ExprEng.processCFGBlockEntrance(BE, Pred); ExplodedNodeSet CheckerNodes; - for (auto *N : DstNodes) { - ExprEng.runCheckersForBlockEntrance(BE, N, CheckerNodes); + + if (Processed && !Processed->isSink()) { + ExprEng.runCheckersForBlockEntrance(BE, Processed, CheckerNodes); } // Enqueue nodes onto the worklist. diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index d47c1ff74cf9f..003ef03ab0c49 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2390,10 +2390,13 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, } /// Block entrance. (Update counters). -bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, - NodeBuilder &Builder, - ExplodedNode *Pred) { +ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, + ExplodedNode *Pred) { bool HasGeneratedNodes = false; + auto MakeDefaultNode = [BE, &Engine = Engine, OriginalPred = Pred]() { + return Engine.makeNode(BE, OriginalPred->getState(), OriginalPred); + }; + // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. if(AMgr.options.ShouldUnrollLoops) { @@ -2404,15 +2407,15 @@ bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, Pred, maxBlockVisitOnPath); if (NewState != Pred->getState()) { HasGeneratedNodes = true; - ExplodedNode *UpdatedNode = Builder.generateNode(BE, NewState, Pred); + ExplodedNode *UpdatedNode = Engine.makeNode(BE, NewState, Pred); if (!UpdatedNode) - return HasGeneratedNodes; + return nullptr; Pred = UpdatedNode; } } // Is we are inside an unrolled loop then no need the check the counters. if(isUnrolledState(Pred->getState())) - return HasGeneratedNodes; + return HasGeneratedNodes ? Pred : MakeDefaultNode(); } // If this block is terminated by a loop and it has already been visited the @@ -2422,7 +2425,7 @@ bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, AMgr.options.ShouldWidenLoops) { const Stmt *Term = getCurrBlock()->getTerminatorStmt(); if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) - return HasGeneratedNodes; + return HasGeneratedNodes ? Pred : MakeDefaultNode(); // Widen. const StackFrame *SF = Pred->getStackFrame(); @@ -2435,9 +2438,7 @@ bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // Here we just pass the the first CFG element in the block. ProgramStateRef WidenedState = getWidenedLoopState( Pred->getState(), SF, BlockCount, *getCurrBlock()->ref_begin()); - HasGeneratedNodes = true; - Builder.generateNode(BE, WidenedState, Pred); - return HasGeneratedNodes; + return Engine.makeNode(BE, WidenedState, Pred); } // FIXME: Refactor this into a checker. @@ -2446,7 +2447,7 @@ bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, const ProgramPoint TaggedLoc = BE.withTag(&Tag); HasGeneratedNodes = true; const ExplodedNode *Sink = - Builder.generateSink(TaggedLoc, Pred->getState(), Pred); + Engine.makeNode(TaggedLoc, Pred->getState(), Pred, /*MarkAsSink=*/true); const StackFrame *SF = Pred->getStackFrame(); if (!SF->inTopFrame()) { @@ -2466,15 +2467,17 @@ bool ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // the list. Replay should almost never fail. Use the stats to catch it // if it does. if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF))) - return HasGeneratedNodes; + return nullptr; NumMaxBlockCountReachedInInlined++; } else NumMaxBlockCountReached++; // Make sink nodes as exhausted(for stats) only if retry failed. Engine.blocksExhausted.push_back(std::make_pair(BE, Sink)); + + return nullptr; } - return HasGeneratedNodes; + return HasGeneratedNodes ? Pred : MakeDefaultNode(); } void ExprEngine::runCheckersForBlockEntrance(const BlockEntrance &Entrance, From 62c8a0069b5af42d5846e8e1c1e78fc77edcb2ee Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 14:47:13 +0200 Subject: [PATCH 04/12] Dedent the "Block count exceeded" block Flip the condition of the `if` to turn the short branch into an early return and reduce the indentation level of the more complex "Block count exceeded" block. Also remove an old "Turn this into a checker" FIXME because it does not fit the current architecture and trends in the analyzer. --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 67 ++++++++++---------- 1 file changed, 33 insertions(+), 34 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 003ef03ab0c49..327c9713d64c4 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2441,43 +2441,42 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, return Engine.makeNode(BE, WidenedState, Pred); } - // FIXME: Refactor this into a checker. - if (BlockCount >= AMgr.options.maxBlockVisitOnPath) { - static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded"); - const ProgramPoint TaggedLoc = BE.withTag(&Tag); - HasGeneratedNodes = true; - const ExplodedNode *Sink = - Engine.makeNode(TaggedLoc, Pred->getState(), Pred, /*MarkAsSink=*/true); + if (BlockCount < AMgr.options.maxBlockVisitOnPath) + return HasGeneratedNodes ? Pred : MakeDefaultNode(); - const StackFrame *SF = Pred->getStackFrame(); - if (!SF->inTopFrame()) { - // FIXME: This will unconditionally prevent inlining this function (even - // from other entry points), which is not a reasonable heuristic: even if - // we reached max block count on this particular execution path, there - // may be other execution paths (especially with other parametrizations) - // where the analyzer can reach the end of the function (so there is no - // natural reason to avoid inlining it). However, disabling this would - // significantly increase the analysis time (because more entry points - // would exhaust their allocated budget), so it must be compensated by a - // different (more reasonable) reduction of analysis scope. - Engine.FunctionSummaries->markShouldNotInline(SF->getDecl()); - - // Re-run the call evaluation without inlining it, by storing the - // no-inlining policy in the state and enqueuing the new work item on - // the list. Replay should almost never fail. Use the stats to catch it - // if it does. - if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF))) - return nullptr; - NumMaxBlockCountReachedInInlined++; - } else - NumMaxBlockCountReached++; + static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded"); + const ProgramPoint TaggedLoc = BE.withTag(&Tag); + HasGeneratedNodes = true; + const ExplodedNode *Sink = + Engine.makeNode(TaggedLoc, Pred->getState(), Pred, /*MarkAsSink=*/true); - // Make sink nodes as exhausted(for stats) only if retry failed. - Engine.blocksExhausted.push_back(std::make_pair(BE, Sink)); + const StackFrame *SF = Pred->getStackFrame(); + if (!SF->inTopFrame()) { + // FIXME: This will unconditionally prevent inlining this function (even + // from other entry points), which is not a reasonable heuristic: even if + // we reached max block count on this particular execution path, there + // may be other execution paths (especially with other parametrizations) + // where the analyzer can reach the end of the function (so there is no + // natural reason to avoid inlining it). However, disabling this would + // significantly increase the analysis time (because more entry points + // would exhaust their allocated budget), so it must be compensated by a + // different (more reasonable) reduction of analysis scope. + Engine.FunctionSummaries->markShouldNotInline(SF->getDecl()); + + // Re-run the call evaluation without inlining it, by storing the + // no-inlining policy in the state and enqueuing the new work item on + // the list. Replay should almost never fail. Use the stats to catch it + // if it does. + if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF))) + return nullptr; + NumMaxBlockCountReachedInInlined++; + } else + NumMaxBlockCountReached++; - return nullptr; - } - return HasGeneratedNodes ? Pred : MakeDefaultNode(); + // Make sink nodes as exhausted(for stats) only if retry failed. + Engine.blocksExhausted.push_back(std::make_pair(BE, Sink)); + + return nullptr; } void ExprEngine::runCheckersForBlockEntrance(const BlockEntrance &Entrance, From 1194faf418ef89054be510c1bad6b49a7835e1f6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 14:58:02 +0200 Subject: [PATCH 05/12] Eliminate variable UpdatedNode which is now useless --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 327c9713d64c4..1f4c5842a76f8 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2407,10 +2407,9 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, Pred, maxBlockVisitOnPath); if (NewState != Pred->getState()) { HasGeneratedNodes = true; - ExplodedNode *UpdatedNode = Engine.makeNode(BE, NewState, Pred); - if (!UpdatedNode) + Pred = Engine.makeNode(BE, NewState, Pred); + if (!Pred) return nullptr; - Pred = UpdatedNode; } } // Is we are inside an unrolled loop then no need the check the counters. From bdd8c2c18907831fb41f3d69e79b6fddd90ffbb6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 15:16:11 +0200 Subject: [PATCH 06/12] Unify definition of 'StackFrame *SF' The transitions within this method cannot change the stack frame, so let's introduce the short name 'SF' at the beginning of the method. Also remove a very obvious comment. --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 1f4c5842a76f8..a78cede917f48 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2392,6 +2392,7 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, /// Block entrance. (Update counters). ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, ExplodedNode *Pred) { + const StackFrame *SF = Pred->getStackFrame(); bool HasGeneratedNodes = false; auto MakeDefaultNode = [BE, &Engine = Engine, OriginalPred = Pred]() { return Engine.makeNode(BE, OriginalPred->getState(), OriginalPred); @@ -2426,9 +2427,6 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) return HasGeneratedNodes ? Pred : MakeDefaultNode(); - // Widen. - const StackFrame *SF = Pred->getStackFrame(); - // FIXME: // We cannot use the CFG element from the via `ExprEngine::getCFGElementRef` // since we are currently at the block entrance and the current reference @@ -2449,7 +2447,6 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, const ExplodedNode *Sink = Engine.makeNode(TaggedLoc, Pred->getState(), Pred, /*MarkAsSink=*/true); - const StackFrame *SF = Pred->getStackFrame(); if (!SF->inTopFrame()) { // FIXME: This will unconditionally prevent inlining this function (even // from other entry points), which is not a reasonable heuristic: even if From cb4233a4c2b13929ae4a41d46f5844ad418cedad Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 15:18:24 +0200 Subject: [PATCH 07/12] Simplify the creation of the 'Sink' node The value of `HasGeneratedNodes` is never accessed after this point, so there is no reason to set it. Also inline the definition of `TaggedLoc` to save a source line. --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index a78cede917f48..6bfe8da64cc67 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2442,10 +2442,8 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, return HasGeneratedNodes ? Pred : MakeDefaultNode(); static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded"); - const ProgramPoint TaggedLoc = BE.withTag(&Tag); - HasGeneratedNodes = true; - const ExplodedNode *Sink = - Engine.makeNode(TaggedLoc, Pred->getState(), Pred, /*MarkAsSink=*/true); + const ExplodedNode *Sink = Engine.makeNode(BE.withTag(&Tag), Pred->getState(), + Pred, /*MarkAsSink=*/true); if (!SF->inTopFrame()) { // FIXME: This will unconditionally prevent inlining this function (even From 3fab27527bc74bf35f16e530c4d3e7b1e75719de Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 15:44:36 +0200 Subject: [PATCH 08/12] Also unify the definition of 'Term' --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 6bfe8da64cc67..618818e555957 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2393,6 +2393,7 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, ExplodedNode *Pred) { const StackFrame *SF = Pred->getStackFrame(); + const Stmt *Term = getCurrBlock()->getTerminatorStmt(); bool HasGeneratedNodes = false; auto MakeDefaultNode = [BE, &Engine = Engine, OriginalPred = Pred]() { return Engine.makeNode(BE, OriginalPred->getState(), OriginalPred); @@ -2402,7 +2403,6 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // other constraints) then consider completely unrolling it. if(AMgr.options.ShouldUnrollLoops) { unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; - const Stmt *Term = getCurrBlock()->getTerminatorStmt(); if (Term) { ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), Pred, maxBlockVisitOnPath); @@ -2423,7 +2423,6 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, unsigned int BlockCount = getNumVisitedCurrent(); if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && AMgr.options.ShouldWidenLoops) { - const Stmt *Term = getCurrBlock()->getTerminatorStmt(); if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) return HasGeneratedNodes ? Pred : MakeDefaultNode(); From 4c88985b29ef77c227a7f1bb498076630669c5b1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 15:54:58 +0200 Subject: [PATCH 09/12] Postpone the creation of the loop unrolling node In `processCFGBlockEntrance` the primary source of pointless complexity is that it eagerly creates a new node when the loop unrolling calculations updated the state. This commit postpones the creation of this node to the point where we're sure that we will need it. This way we can remove the ugly `HasGeneratedNode` logic: instead of `HasGeneratedNode ? Pred : MakeDefaultNode()` we can use a simple unconditional `Engine.makeNode(BE, State, Pred)` call that creates a node with the most recent state (which may be either the original state or the state that was updated by the loop unrolling logic). This commit still creates a separate node for the loop unrolling state update in the cases when it will serve as the parent of another node created within this function. These blocks are ugly and almost certainly completely pointless, but removing them will change the shape of the `ExplodedGraph` so I will only do it in a separate commit. --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 45 +++++++++++--------- 1 file changed, 26 insertions(+), 19 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 618818e555957..068b140301e7d 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2394,28 +2394,19 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, ExplodedNode *Pred) { const StackFrame *SF = Pred->getStackFrame(); const Stmt *Term = getCurrBlock()->getTerminatorStmt(); - bool HasGeneratedNodes = false; - auto MakeDefaultNode = [BE, &Engine = Engine, OriginalPred = Pred]() { - return Engine.makeNode(BE, OriginalPred->getState(), OriginalPred); - }; + ProgramStateRef State = Pred->getState(); // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. if(AMgr.options.ShouldUnrollLoops) { unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; if (Term) { - ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), - Pred, maxBlockVisitOnPath); - if (NewState != Pred->getState()) { - HasGeneratedNodes = true; - Pred = Engine.makeNode(BE, NewState, Pred); - if (!Pred) - return nullptr; - } + State = updateLoopStack(Term, AMgr.getASTContext(), Pred, + maxBlockVisitOnPath); } // Is we are inside an unrolled loop then no need the check the counters. - if(isUnrolledState(Pred->getState())) - return HasGeneratedNodes ? Pred : MakeDefaultNode(); + if (isUnrolledState(State)) + return Engine.makeNode(BE, State, Pred); } // If this block is terminated by a loop and it has already been visited the @@ -2424,7 +2415,15 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && AMgr.options.ShouldWidenLoops) { if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) - return HasGeneratedNodes ? Pred : MakeDefaultNode(); + return Engine.makeNode(BE, State, Pred); + + if (State != Pred->getState()) { + // TODO: This intermediate transition is very likely to be irrelevant, + // remove it in a follow-up change. + Pred = Engine.makeNode(BE, State, Pred); + if (!Pred) + return nullptr; + } // FIXME: // We cannot use the CFG element from the via `ExprEngine::getCFGElementRef` @@ -2433,16 +2432,24 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // block, but the terminator cannot be referred as a CFG element. // Here we just pass the the first CFG element in the block. ProgramStateRef WidenedState = getWidenedLoopState( - Pred->getState(), SF, BlockCount, *getCurrBlock()->ref_begin()); + State, SF, BlockCount, *getCurrBlock()->ref_begin()); return Engine.makeNode(BE, WidenedState, Pred); } if (BlockCount < AMgr.options.maxBlockVisitOnPath) - return HasGeneratedNodes ? Pred : MakeDefaultNode(); + return Engine.makeNode(BE, State, Pred); + + if (State != Pred->getState()) { + // TODO: This intermediate transition is very likely to be irrelevant, + // remove it in a follow-up change. + Pred = Engine.makeNode(BE, State, Pred); + if (!Pred) + return nullptr; + } static SimpleProgramPointTag Tag(TagProviderName, "Block count exceeded"); - const ExplodedNode *Sink = Engine.makeNode(BE.withTag(&Tag), Pred->getState(), - Pred, /*MarkAsSink=*/true); + const ExplodedNode *Sink = + Engine.makeNode(BE.withTag(&Tag), State, Pred, /*MarkAsSink=*/true); if (!SF->inTopFrame()) { // FIXME: This will unconditionally prevent inlining this function (even From e1aaa8d2e259edc71d789b58ac53f2ba31c504f8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Wed, 5 Aug 2026 16:14:03 +0200 Subject: [PATCH 10/12] Introduce short name for AMgr.options.maxBlockVisitOnPath --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 13 +++++-------- 1 file changed, 5 insertions(+), 8 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 068b140301e7d..45f91e84b7cfe 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2395,15 +2395,13 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, const StackFrame *SF = Pred->getStackFrame(); const Stmt *Term = getCurrBlock()->getTerminatorStmt(); ProgramStateRef State = Pred->getState(); + unsigned MaxBlockVisit = AMgr.options.maxBlockVisitOnPath; // If we reach a loop which has a known bound (and meets // other constraints) then consider completely unrolling it. if(AMgr.options.ShouldUnrollLoops) { - unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath; - if (Term) { - State = updateLoopStack(Term, AMgr.getASTContext(), Pred, - maxBlockVisitOnPath); - } + if (Term) + State = updateLoopStack(Term, AMgr.getASTContext(), Pred, MaxBlockVisit); // Is we are inside an unrolled loop then no need the check the counters. if (isUnrolledState(State)) return Engine.makeNode(BE, State, Pred); @@ -2412,8 +2410,7 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // If this block is terminated by a loop and it has already been visited the // maximum number of times, widen the loop. unsigned int BlockCount = getNumVisitedCurrent(); - if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 && - AMgr.options.ShouldWidenLoops) { + if (BlockCount == MaxBlockVisit - 1 && AMgr.options.ShouldWidenLoops) { if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) return Engine.makeNode(BE, State, Pred); @@ -2436,7 +2433,7 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, return Engine.makeNode(BE, WidenedState, Pred); } - if (BlockCount < AMgr.options.maxBlockVisitOnPath) + if (BlockCount < MaxBlockVisit) return Engine.makeNode(BE, State, Pred); if (State != Pred->getState()) { From a2a2820cce146a95453aa9745acf41c4d5c8d8fc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Mon, 10 Aug 2026 15:43:54 +0200 Subject: [PATCH 11/12] Tweak code formatting, add a few comment lines --- clang/lib/StaticAnalyzer/Core/ExprEngine.cpp | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 45f91e84b7cfe..a6a36fabba965 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2397,9 +2397,9 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, ProgramStateRef State = Pred->getState(); unsigned MaxBlockVisit = AMgr.options.maxBlockVisitOnPath; - // If we reach a loop which has a known bound (and meets - // other constraints) then consider completely unrolling it. - if(AMgr.options.ShouldUnrollLoops) { + // If we reach a loop which has a known bound (and meets other constraints) + // then consider completely unrolling it. + if (AMgr.options.ShouldUnrollLoops) { if (Term) State = updateLoopStack(Term, AMgr.getASTContext(), Pred, MaxBlockVisit); // Is we are inside an unrolled loop then no need the check the counters. @@ -2433,9 +2433,12 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, return Engine.makeNode(BE, WidenedState, Pred); } + // If we did not reach MaxBlockVisitOnPath, continue the analysis normally. if (BlockCount < MaxBlockVisit) return Engine.makeNode(BE, State, Pred); + // ... otherwise, discard this execution path. + if (State != Pred->getState()) { // TODO: This intermediate transition is very likely to be irrelevant, // remove it in a follow-up change. @@ -2464,7 +2467,7 @@ ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, // no-inlining policy in the state and enqueuing the new work item on // the list. Replay should almost never fail. Use the stats to catch it // if it does. - if ((!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF))) + if (!AMgr.options.NoRetryExhausted && replayWithoutInlining(Pred, SF)) return nullptr; NumMaxBlockCountReachedInInlined++; } else From 5d287d92d423def755cee3ed8f261c8fe72c74fd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Tue, 11 Aug 2026 12:57:01 +0200 Subject: [PATCH 12/12] Remove redundant isSink() check This `!Processed->isSink()` call was redundant, because `ExprEngine::runCheckersForBlockEntrance()` directly passes the node `Processed` to `CheckerManager::runCheckersForBlockEntrance`, which uses it to implicitly construct an `ExplodedNodeSet` -- and sinks are ignored by the constructor of `ExplodedNodeSet`. --- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index d0096346b0990..6ae711af33bed 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -329,9 +329,8 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { ExplodedNodeSet CheckerNodes; - if (Processed && !Processed->isSink()) { + if (Processed) ExprEng.runCheckersForBlockEntrance(BE, Processed, CheckerNodes); - } // Enqueue nodes onto the worklist. enqueue(CheckerNodes); _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
