https://github.com/jvoung created https://github.com/llvm/llvm-project/pull/186808
Bail out early if the visiting each reachable basic block once would have exceeded the MaxBlockVisits limit. If that is the case, then actually visiting and doing the dataflow analysis would hit the limit, but we would have wasted a lot of time and possibly OOMed. We've seen example of CFGs with # of blocks that are 2-8x the visit limit. Those examples also tend to have lots of `Locs`, which we track in maps for each BB. Since the maps do not share memory across BBs, this leads to non-linear memory usage and OOMing before hitting the max visit limit. >From b6f1adc7038af27414786b4220d6aedb5c66169a Mon Sep 17 00:00:00 2001 From: Jan Voung <[email protected]> Date: Mon, 16 Mar 2026 14:16:30 +0000 Subject: [PATCH] [clang][FlowSensitive] Do a quick check and bail early for massive CFGs Bail out early if the visiting each reachable basic block once would have exceeded the MaxBlockVisits limit. If that is the case, then actually visiting and doing the dataflow analysis would hit the limit, but we would have wasted a lot of time and possibly OOMed. We've seen example of CFGs with # of blocks that are 2-8x the visit limit. Those examples also tend to have lots of `Locs`, which we track in maps for each BB. Since the maps do not share memory across BBs, this leads to non-linear memory usage and OOMing before hitting the max visit limit. --- .../TypeErasedDataflowAnalysis.cpp | 31 +++++++++++++++++++ 1 file changed, 31 insertions(+) diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 02982274093cb..0b2a45c963141 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -11,6 +11,7 @@ // //===----------------------------------------------------------------------===// +#include <cstddef> #include <optional> #include <system_error> #include <utility> @@ -34,6 +35,7 @@ #include "clang/Basic/LLVM.h" #include "clang/Support/Compiler.h" #include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" @@ -479,6 +481,27 @@ transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, return State; } +// Returns the number of blocks that would be visited if we only visit each +// reachable block once. This provides a lower bound on the number of block +// visits. This is a light version of the main analysis loop (keep in sync). +size_t NumBlockVisitsIfVisitEachReachableOnce(const CFG &CFG) { + PostOrderCFGView POV(&CFG); + ForwardDataflowWorklist Worklist(CFG, &POV); + llvm::BitVector VisitedBlocks(CFG.size()); + const CFGBlock &Entry = CFG.getEntry(); + Worklist.enqueueSuccessors(&Entry); + while (const CFGBlock *Block = Worklist.dequeue()) { + if (VisitedBlocks[Block->getBlockID()]) + continue; + // Do not add unreachable successor blocks to `Worklist`. + if (Block->hasNoReturnElement()) + continue; + VisitedBlocks[Block->getBlockID()] = true; + Worklist.enqueueSuccessors(Block); + } + return VisitedBlocks.count(); +} + llvm::Expected<std::vector<std::optional<TypeErasedDataflowAnalysisState>>> runTypeErasedDataflowAnalysis( const AdornedCFG &ACFG, TypeErasedDataflowAnalysis &Analysis, @@ -496,6 +519,14 @@ runTypeErasedDataflowAnalysis( MaybeStartingEnv ? *MaybeStartingEnv : InitEnv; const clang::CFG &CFG = ACFG.getCFG(); + if (CFG.size() > MaxBlockVisits) { + if (CFG.size() > NumBlockVisitsIfVisitEachReachableOnce(CFG)) { + return llvm::createStringError( + std::errc::timed_out, "number of blocks in cfg will lead to " + "exceeding maximum number of block visits"); + } + } + PostOrderCFGView POV(&CFG); ForwardDataflowWorklist Worklist(CFG, &POV); llvm::SmallDenseSet<const CFGBlock *> NonStructLoopBackedgeNodes = _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
