Author: Donát Nagy Date: 2026-02-24T17:41:04+01:00 New Revision: 1a81673922a3f5b75f342e416e925a69822c4613
URL: https://github.com/llvm/llvm-project/commit/1a81673922a3f5b75f342e416e925a69822c4613 DIFF: https://github.com/llvm/llvm-project/commit/1a81673922a3f5b75f342e416e925a69822c4613.diff LOG: [NFCI][analyzer] Add a clean way to generate nodes (#182377) 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()`. Eventually I intend to replace most use of `NodeBuilder`s with direct calls to this method. To ensure that this new `makeNode()` doesn't generate non-sink nodes with `PosteriorlyOverconstrained` state, I moved the `isPosteriorlyOverconstrained()` check from `CoreEngine::generateNode()` to `makeNode()`. This is technically speaking not an NFC change, because it prevents `BranchNodeBuilder::generateNode()` from generating non-sink nodes with `PosteriorlyOverconstrained` state (previously it was able to do so because it calls `NodeBuilder::generateNodeImpl()` instead of `NodeBuilder::generateNode()`). However I labelled this as an NFCI change, as I'm fairly confident that this won't lead to any observable changes because: - `PosteriorlyOverconstrained` states are very rare. - A state derived from a `PosteriorlyOverconstrained` state is also posteriorly overconstrained, so if `BranchNodeBuilder` fails to sink the execution path, it will be sunk anyway at the next transition which is done by a plain `NodeBuilder`. Note that 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. For more explanation see the doc-comment above the data member `bool PosteriorlyOverconstrained` within `ProgramState`. Added: Modified: clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h clang/include/clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h clang/lib/StaticAnalyzer/Core/CoreEngine.cpp Removed: ################################################################################ diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index d4669fd2d1720..a8b33f22fcc33 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); @@ -235,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; @@ -245,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) {} @@ -267,13 +276,8 @@ class NodeBuilder { } /// Generates a node in the ExplodedGraph. - ExplodedNode *generateNode(const ProgramPoint &PP, - ProgramStateRef State, - ExplodedNode *Pred) { - return generateNodeImpl( - PP, State, Pred, - /*MarkAsSink=*/State->isPosteriorlyOverconstrained()); - } + ExplodedNode *generateNode(const ProgramPoint &PP, ProgramStateRef State, + ExplodedNode *Pred, bool MarkAsSink = false); /// Generates a sink in the ExplodedGraph. /// @@ -283,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/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 354739c537802..29bd103e57d2c 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -565,8 +565,23 @@ void CoreEngine::HandleVirtualBaseBranch(const CFGBlock *B, HandleBlockEdge(Loc, Pred); } +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); + + return IsNew ? N : nullptr; +} + /// 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) { @@ -694,21 +709,14 @@ 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; - 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) - Frontier.Add(N); + Frontier.Add(N); return N; } @@ -723,7 +731,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
