https://github.com/NagyDonat updated https://github.com/llvm/llvm-project/pull/182377
From 9a21f3ae0b32cf6812b49e2f739613e1d1e8a8c9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 18:42:22 +0100 Subject: [PATCH 1/7] [NFC][analyzer] Add a clean way to generate nodes Currently the most common way for generating nodes is a complicated and confusing boilerplate approach, which appears in many places: - A `NodeBuilderContext` is constructed from a `CoreEngine &` and two other irrelevant arguments. - A short-lived temporary `NodeBuilder` is constructed from the `NodeBuilderContext` and some almost irrelevant node sets. - `NodeBuilder::generateNode()` is invoked once and accesses the graph through the `CoreEngine &` to generate the node. To simplify this, I'm cutting out the wrapper layers and extracting the "main logic" of the method `NodeBuilder::generateNode()` to a new method called `CoreEngine::makeNode()`. It should be easy to verify that the behavior of `NodeBuilder::generateNodeImpl()` is exactly the same as before this change. Note that I picked the name `makeNode()` because: - `CoreEngine::generateNode()` already exists as a barely used method. I intend to eliminate it later (because it will be natural to replace it with `makeNode()` calls), but immediately "taking over" its name could have led to confusion, especially on downstream forks. - Although the lower-level method is named `ExplodedGraph::getNode()`, I didn't want to reuse that name because `getXXX` would imply a getter method (and this is not a getter). - I rejected `addNode` becasue we are not adding an existing node, but making a new node. Eventually I intend to replace most use of `NodeBuilder`s with direct calls to this freshly introduced `CoreEngine::makeNode()`. --- .../Core/PathSensitive/CoreEngine.h | 3 +++ clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 23 +++++++++++++------ 2 files changed, 19 insertions(+), 7 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index d4669fd2d1720..3ec1cbd8d3576 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -176,6 +176,9 @@ class CoreEngine { auto aborted_blocks() const { return llvm::iterator_range(blocksAborted); } + ExplodedNode *makeNode(const ProgramPoint &Loc, ProgramStateRef State, + ExplodedNode *Pred, bool MarkAsSink = false) const; + /// Enqueue the given set of nodes onto the work list. void enqueue(ExplodedNodeSet &Set); diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 9f0fcc4c3e3a5..b04a90bd5a0b4 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -559,6 +559,20 @@ void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, HandleBlockEdge(Loc, Pred); } +ExplodedNode *CoreEngine::makeNode(const ProgramPoint &Loc, + ProgramStateRef State, + ExplodedNode *Pred, + bool MarkAsSink) const { + bool IsNew; + ExplodedNode *N = G.getNode(Loc, State, MarkAsSink, &IsNew); + N->addPredecessor(Pred, G); + + if (!IsNew) + return nullptr; + + return N; +} + /// generateNode - Utility method to generate nodes, hook up successors, /// and add nodes to the worklist. void CoreEngine::generateNode(const ProgramPoint &Loc, @@ -693,15 +707,10 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, ExplodedNode *FromN, bool MarkAsSink) { HasGeneratedNodes = true; - bool IsNew; - ExplodedNode *N = C.getEngine().G.getNode(Loc, State, MarkAsSink, &IsNew); - N->addPredecessor(FromN, C.getEngine().G); Frontier.erase(FromN); + ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); - if (!IsNew) - return nullptr; - - if (!MarkAsSink) + if (N && !MarkAsSink) Frontier.Add(N); return N; From 5a975f6a9bac6fadfa4a69a0b30d1aded70f9c38 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 19:31:56 +0100 Subject: [PATCH 2/7] [NFC][analyzer] Remove a redundant check The method `ExplodedNodeSet::Add()` already does nothing if its argument is a null pointer or a sink node: ```c++ void Add(ExplodedNode *N) { if (N && !N->isSink()) Impl.insert(N); } ``` Note that `CoreEngine::makeNode()` and `ExplodedGraph::getNode()` ensure that they return a sink node if and only if the `IsSink` / `MarkAsSink` argument is true. --- 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 b04a90bd5a0b4..610c4656e6b8a 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -710,8 +710,7 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, Frontier.erase(FromN); ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); - if (N && !MarkAsSink) - Frontier.Add(N); + Frontier.Add(N); return N; } From 766a0cefa77404efd536731f212fad8a1b206b6a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 19:47:53 +0100 Subject: [PATCH 3/7] [analyzer] Respect PosteriorlyOverconstrained in BranchNodeBuilder The analyzer sometimes realizes that the constraints of the current `ProgramState` have became contradictory at some earlier point in its analysis. (For more explanation see the doc-comment above the data member `bool ProgramState::PosteriorlyOverconstrained`.) Simulated paths with a `PosteriorlyOverconstrained` state do not correspond to real paths that can occur during the actual execution of the program, so the analyzer should stop following them as soon as possible. Traditionally, this was done by calling `isPosteriorlyOverconstrained()` within `NodeBuilder::generateNode()` (a method which -- through many intermediaries -- generates most nodes in our graph) and passing `MarkAsSink = true` to `NodeBuilder::generateNodeImpl()` if it returns true. However `NodeBuilder::generateNodeImpl()` is called from _three_ locations: - this location; - `NodeBuilder::generateSink()` which already always asks for a sink; - and `BranchNodeBuilder::generateNode()` which could -- until now -- generate non-sink nodes with PosteriorlyOverconstrained state. This commit moves the call to `isPosteriorlyOverconstrained()` from `NodeBuilder::generateNode()` to `NodeBuilder::generateNodeImpl()` to also cover the nodes built by `BranchNodeBuilder`s. Note that this is a practically negligible change because states derived from a `PosteriorlyOverconstrained` state are themselves also `PosteriorlyOverconstrained`, so any paths that are not sunk by `BranchNodeBuilder` were probably sunk anyway at the next transition. Also, `PosteriorlyOverconstrained` states are very rare, in fact so rare that I don't know how to write a test that artificially introduces one. --- .../clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h | 4 +--- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 2 ++ 2 files changed, 3 insertions(+), 3 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 3ec1cbd8d3576..ddff2393920e1 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -273,9 +273,7 @@ class NodeBuilder { ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred) { - return generateNodeImpl( - PP, State, Pred, - /*MarkAsSink=*/State->isPosteriorlyOverconstrained()); + return generateNodeImpl(PP, State, Pred); } /// Generates a sink in the ExplodedGraph. diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 610c4656e6b8a..f6b101b02847d 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -706,6 +706,8 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *FromN, bool MarkAsSink) { + MarkAsSink = MarkAsSink || State->isPosteriorlyOverconstrained(); + HasGeneratedNodes = true; Frontier.erase(FromN); ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); From 6f80cabf4b06f5484684bdc6b3355b35a6c60e74 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 20:21:57 +0100 Subject: [PATCH 4/7] [NFC][analyzer] Move PosteriorlyOverconstrained check to CoreEngine ... more precisely, move it to `CoreEngine::makeNode()` instead of `NodeBuilder::generateNodeImpl()`. This change is trivially NFC because the (freshly introduced) `CoreEngine::makeNode()` is currently only called from `NodeBuilder::generateNodeImpl()`. However in the future I intend to also call `CoreEngine::makeNode()` from other methods of `CoreEngine` (e.g. `generateNode()`) and then this will let them also respect `PosteriorlyOverconstrained`. (Currently those methods of `CoreEngine` can generate non-sink nodes with `PosteriorlyOverconstrained` state.) Eventually it would be nice to do the `PosteriorlyOverconstrained` check at the deepest level, in the methods of `ExplodedGraph`; but instead of one sudden change I try to approach that gradually. --- .../clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h | 6 +++++- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 4 ++-- 2 files changed, 7 insertions(+), 3 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h index 12487a33a485e..e8a63e6967805 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h @@ -78,7 +78,6 @@ class ProgramState : public llvm::FoldingSetNode { friend class ProgramStateManager; friend class ExplodedGraph; friend class ExplodedNode; - friend class NodeBuilder; ProgramStateManager *stateMgr; Environment Env; // Maps a Stmt to its current SVal. @@ -116,6 +115,11 @@ class ProgramState : public llvm::FoldingSetNode { // overconstrained-related functions. We want to keep this API inaccessible // for Checkers. friend class ConstraintManager; + // The CoreEngine also needs to be a friend to mark nodes as sinks if they + // are generated with a PosteriorlyOverconstrained state. + // FIXME: Perform this check in the relevant methods of `ExplodedGraph` and + // remove this `friend` declaration. + friend class CoreEngine; bool isPosteriorlyOverconstrained() const { return PosteriorlyOverconstrained; } diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index f6b101b02847d..840108e543a90 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -563,6 +563,8 @@ ExplodedNode *CoreEngine::makeNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *Pred, bool MarkAsSink) const { + MarkAsSink = MarkAsSink || State->isPosteriorlyOverconstrained(); + bool IsNew; ExplodedNode *N = G.getNode(Loc, State, MarkAsSink, &IsNew); N->addPredecessor(Pred, G); @@ -706,8 +708,6 @@ ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *FromN, bool MarkAsSink) { - MarkAsSink = MarkAsSink || State->isPosteriorlyOverconstrained(); - HasGeneratedNodes = true; Frontier.erase(FromN); ExplodedNode *N = C.getEngine().makeNode(Loc, State, FromN, MarkAsSink); From fae12ead3f80c00816716d4eab78b8a3ead45cb7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 20:49:43 +0100 Subject: [PATCH 5/7] [NFC][analyzer] Mark plans with TODO comments I intend to implement these changes within the next few weeks; however, I hope that the comments are clear enough even if I cannot do so. --- .../StaticAnalyzer/Core/PathSensitive/CoreEngine.h | 13 +++++++++++++ clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 3 +++ 2 files changed, 16 insertions(+) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index ddff2393920e1..9f45031e61b51 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -238,6 +238,17 @@ class NodeBuilderContext { /// be propagated to the next step / builder. They are the nodes which have been /// added to the builder (either as the input node set or as the newly /// constructed nodes) but did not have any outgoing transitions added. +/// +/// TODO: This "main benefit" is often useless, in fact the only significant +/// use is within `CheckerManager::ExpandGraphWithCheckers`. There this logic +/// ensures that if a checker performs multiple transitions on the same path, +/// then only the last of them is "built upon" by other checkers or the engine. +/// +/// However, there are also many short-lived temporary `NodeBuilder` instances +/// where the `generateNode` is called in a very predictable manner (once, or +/// once for each source node) and the frontier management is overkill. +/// These locations should be gradually simplified by using the method +/// `CoreEngine::makeNode()` instead of the temporary `NodeBuilder`s. class NodeBuilder { protected: const NodeBuilderContext &C; @@ -270,6 +281,8 @@ class NodeBuilder { } /// Generates a node in the ExplodedGraph. + /// TODO: This is a useless wrapper layer, rename `generateNodeImpl` to + /// `generateNode`. ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred) { diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 840108e543a90..07780c57940ca 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -577,6 +577,9 @@ ExplodedNode *CoreEngine::makeNode(const ProgramPoint &Loc, /// generateNode - Utility method to generate nodes, hook up successors, /// and add nodes to the worklist. +/// TODO: This and other similar methods should call CoreEngine::makeNode() +/// instead of duplicating its logic. This would also fix that currently these +/// can generate non-sink nodes with PosteriorlyOverconstrained state. void CoreEngine::generateNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *Pred) { From f8ad7fad8d8f2c5b79d95bd632a280fa695e0654 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Thu, 19 Feb 2026 22:33:51 +0100 Subject: [PATCH 6/7] Satisfy git-clang-format --- .../clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h | 2 +- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 5 ++--- 2 files changed, 3 insertions(+), 4 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 9f45031e61b51..e2a5713f659ae 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -177,7 +177,7 @@ class CoreEngine { auto aborted_blocks() const { return llvm::iterator_range(blocksAborted); } ExplodedNode *makeNode(const ProgramPoint &Loc, ProgramStateRef State, - ExplodedNode *Pred, bool MarkAsSink = false) const; + ExplodedNode *Pred, bool MarkAsSink = false) const; /// Enqueue the given set of nodes onto the work list. void enqueue(ExplodedNodeSet &Set); diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 07780c57940ca..941b4e1fb1697 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -560,9 +560,8 @@ void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, } ExplodedNode *CoreEngine::makeNode(const ProgramPoint &Loc, - ProgramStateRef State, - ExplodedNode *Pred, - bool MarkAsSink) const { + ProgramStateRef State, ExplodedNode *Pred, + bool MarkAsSink) const { MarkAsSink = MarkAsSink || State->isPosteriorlyOverconstrained(); bool IsNew; From 09ca6a600488faf2656f6ea05235f5c5326155ba Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Don=C3=A1t=20Nagy?= <[email protected]> Date: Fri, 20 Feb 2026 15:02:10 +0100 Subject: [PATCH 7/7] [NFC][analyzer] Simplify 3-parameter NodeBuilder::generateNode After previous simplifications the `NodeBuilder::generateNode` overload with three parameters became a trivial wrapper around `NodeBuilder::generateNodeImpl`; this commit places the implementation of `generateNodeImpl` directly under `generateNode`. `NodeBuilder::` was necessary in `BranchNodeBuilder::generateNode` because otherwise C++ would've preferred the method of `BranchNodeBuilder` (and run into an incompatible arguments error). --- .../Core/PathSensitive/CoreEngine.h | 16 +++------------- clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 9 ++++----- 2 files changed, 7 insertions(+), 18 deletions(-) diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index e2a5713f659ae..a8b33f22fcc33 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -259,11 +259,6 @@ class NodeBuilder { /// the builder dies. ExplodedNodeSet &Frontier; - ExplodedNode *generateNodeImpl(const ProgramPoint &PP, - ProgramStateRef State, - ExplodedNode *Pred, - bool MarkAsSink = false); - public: NodeBuilder(ExplodedNodeSet &DstSet, const NodeBuilderContext &Ctx) : C(Ctx), Frontier(DstSet) {} @@ -281,13 +276,8 @@ class NodeBuilder { } /// Generates a node in the ExplodedGraph. - /// TODO: This is a useless wrapper layer, rename `generateNodeImpl` to - /// `generateNode`. - ExplodedNode *generateNode(const ProgramPoint &PP, - ProgramStateRef State, - ExplodedNode *Pred) { - return generateNodeImpl(PP, State, Pred); - } + ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, + ExplodedNode *Pred, bool MarkAsSink = false); /// Generates a sink in the ExplodedGraph. /// @@ -297,7 +287,7 @@ class NodeBuilder { ExplodedNode *generateSink(const ProgramPoint &PP, ProgramStateRef State, ExplodedNode *Pred) { - return generateNodeImpl(PP, State, Pred, true); + return generateNode(PP, State, Pred, true); } ExplodedNode *generateNode(const Stmt *S, diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 941b4e1fb1697..c2c81e9a8ef60 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -706,10 +706,9 @@ void CoreEngine::enqueueEndOfFunction(ExplodedNodeSet &Set, const ReturnStmt *RS } } -ExplodedNode* NodeBuilder::generateNodeImpl(const ProgramPoint &Loc, - ProgramStateRef State, - ExplodedNode *FromN, - bool MarkAsSink) { +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); @@ -729,7 +728,7 @@ ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, ProgramPoint Loc = BlockEdge(C.getBlock(), Dst, NodePred->getLocationContext()); - ExplodedNode *Succ = generateNodeImpl(Loc, State, NodePred); + ExplodedNode *Succ = NodeBuilder::generateNode(Loc, State, NodePred); return Succ; } _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
