llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang @llvm/pr-subscribers-clang-analysis Author: Jan Voung (jvoung) <details> <summary>Changes</summary> 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 have lots of `Locs`, which we track in MapVectors 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. With this, we can avoid OOMing, and at least get some results for the other CFGs in the TU, instead of losing all results from the process crashing. --- Full diff: https://github.com/llvm/llvm-project/pull/186808.diff 1 Files Affected: - (modified) clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp (+31) ``````````diff diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 02982274093cb..004341f205c9d 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; + VisitedBlocks[Block->getBlockID()] = true; + // Do not add unreachable successor blocks to `Worklist`. + if (Block->hasNoReturnElement()) + continue; + 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() > static_cast<size_t>(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 = `````````` </details> https://github.com/llvm/llvm-project/pull/186808 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
