Author: Donát Nagy Date: 2026-08-12T10:40:33+02:00 New Revision: c76a617524fa62f85c1ff825b5d47885599c6482
URL: https://github.com/llvm/llvm-project/commit/c76a617524fa62f85c1ff825b5d47885599c6482 DIFF: https://github.com/llvm/llvm-project/commit/c76a617524fa62f85c1ff825b5d47885599c6482.diff LOG: [NFC][analyzer] Refactor processCFGBlockEntrance (#215284) This commit tries to untangle the logic of `ExprEngine::processCFGBlockExampe` (which handles the loop unrolling, the loop widening and the `MaxBlockVisitOnPath` limit). This was the only place that used the method `NodeBuilder::hasGeneratedNodes()`, and with that, it was able to set up remarkably convoluted logic despite the fact that the `Frontier` of this `NodeBuilder` always contained at most one node. This is part of my commit series that gradually removes `NodeBuilder`s from the analyzer engine. As this is an NFC change, I kept that this method can create two `ExplodedNode`s in two rare corner cases (when the loop unrolling state update is followed by either a loop widening step or a "block count exceeded" sink creation). The removal of these extra nodes could theoretically perturb the behavior of the analyzer (because it changes the number of nodes in the graph), but I'm pretty sure that there is no logic that concretely looks for these (fortunately non-tagged) nodes, so I intend to remove them in a follow-up commit. In addition to the removal of the NodeBuilder I also performed some minor code quality improvements in this method. Added: Modified: clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h clang/lib/StaticAnalyzer/Core/CoreEngine.cpp clang/lib/StaticAnalyzer/Core/ExprEngine.cpp Removed: ################################################################################ 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 7fe6e59a3679d..68d4362aca941 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -388,8 +388,9 @@ class ExprEngine { ExplodedNode *Pred, ExplodedNodeSet &Dst); /// Called by CoreEngine when processing the entrance of a CFGBlock. - void 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 121a40cc58237..6ae711af33bed 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -325,19 +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(Pred, DstNodes, ExprEng.getBuilderContext()); - ExprEng.processCFGBlockEntrance(BE, Builder, Pred); - - // Auto-generate a node. - if (!Builder.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) + ExprEng.runCheckersForBlockEntrance(BE, Processed, CheckerNodes); // Enqueue nodes onto the worklist. enqueue(CheckerNodes); @@ -681,7 +674,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 fe4dc8a49cb99..328ed5b23dd83 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2391,40 +2391,37 @@ bool ExprEngine::replayWithoutInlining(ExplodedNode *N, } /// Block entrance. (Update counters). -void ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, - NodeBuilder &Builder, - ExplodedNode *Pred) { - // 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; - const Stmt *Term = getCurrBlock()->getTerminatorStmt(); - if (Term) { - ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(), - Pred, maxBlockVisitOnPath); - if (NewState != Pred->getState()) { - ExplodedNode *UpdatedNode = Builder.generateNode(BE, NewState, Pred); - if (!UpdatedNode) - return; - Pred = UpdatedNode; - } - } +ExplodedNode *ExprEngine::processCFGBlockEntrance(const BlockEntrance &BE, + ExplodedNode *Pred) { + 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) { + 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(Pred->getState())) - return; + if (isUnrolledState(State)) + return Engine.makeNode(BE, State, Pred); } // 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) { - const Stmt *Term = getCurrBlock()->getTerminatorStmt(); + if (BlockCount == MaxBlockVisit - 1 && AMgr.options.ShouldWidenLoops) { if (!isa_and_nonnull<ForStmt, WhileStmt, DoStmt, CXXForRangeStmt>(Term)) - return; + return Engine.makeNode(BE, State, Pred); - // Widen. - const StackFrame *SF = Pred->getStackFrame(); + 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,44 +2430,54 @@ void 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()); - Builder.generateNode(BE, WidenedState, Pred); - return; + State, SF, BlockCount, *getCurrBlock()->ref_begin()); + 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); - const ExplodedNode *Sink = - Builder.generateSink(TaggedLoc, Pred->getState(), Pred); + // If we did not reach MaxBlockVisitOnPath, continue the analysis normally. + if (BlockCount < MaxBlockVisit) + return Engine.makeNode(BE, State, Pred); - 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 - // diff erent (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; - NumMaxBlockCountReachedInInlined++; - } else - NumMaxBlockCountReached++; + // ... otherwise, discard this execution path. - // Make sink nodes as exhausted(for stats) only if retry failed. - Engine.blocksExhausted.push_back(std::make_pair(BE, Sink)); - } + 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), State, Pred, /*MarkAsSink=*/true); + + 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 + // diff erent (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++; + + // 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, _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
