https://github.com/MaskRay updated https://github.com/llvm/llvm-project/pull/207552
>From 975a96465e3ebe05db294b484bd4dbd45e1b73dd Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Sat, 4 Jul 2026 18:10:41 -0700 Subject: [PATCH 1/2] [Analysis] Modernize CFGBlock GraphTraits; drop generic dominator tree special case Make clang analyzer's CFG behave like other graphs in the generic dominator tree builder by teaching the CFGBlock GraphTraits two things. * Node numbers: getNumber/getMaxNumber/getNumberEpoch backed by the dense, never-renumbered BlockIDs. GraphHasNodeNumbers<CFGBlock *> becomes true (#101706) so Semi-NCA indexes a SmallVector instead of a DenseMap and DominatorTreeBase drops its CFGBlock-to-index map. * Plain `CFGBlock *` children: map through the reachable target and skip `AB_Unreachable` (null) edges. This drops the is_same_v/make_filter_range fallback in getChildren() and the CFGBlock ChildrenGetterTy specialization. (Post)dominator and IDF results are unchanged. Aided by Claude Opus 4.8 --- .../clang/Analysis/Analyses/Dominators.h | 27 --- clang/include/clang/Analysis/CFG.h | 183 ++++++++++++++---- .../llvm/Support/GenericDomTreeConstruction.h | 12 +- 3 files changed, 150 insertions(+), 72 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h index 7dd54c5ce262c..3dd5319e36468 100644 --- a/clang/include/clang/Analysis/Analyses/Dominators.h +++ b/clang/include/clang/Analysis/Analyses/Dominators.h @@ -185,33 +185,6 @@ using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>; template<> void CFGDominatorTreeImpl<true>::anchor(); template<> void CFGDominatorTreeImpl<false>::anchor(); -} // end of namespace clang - -namespace llvm { -namespace IDFCalculatorDetail { - -/// Specialize ChildrenGetterTy to skip nullpointer successors. -template <bool IsPostDom> -struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> { - using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef; - using ChildrenTy = SmallVector<NodeRef, 8>; - - ChildrenTy get(const NodeRef &N) { - using OrderedNodeTy = - typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy; - - auto Children = children<OrderedNodeTy>(N); - ChildrenTy Ret{Children.begin(), Children.end()}; - llvm::erase(Ret, nullptr); - return Ret; - } -}; - -} // end of namespace IDFCalculatorDetail -} // end of namespace llvm - -namespace clang { - class ControlDependencyCalculator : public ManagedAnalysis { using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>; using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>; diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h index 2079f99046021..749ed3fc76452 100644 --- a/clang/include/clang/Analysis/CFG.h +++ b/clang/include/clang/Analysis/CFG.h @@ -1520,12 +1520,43 @@ class CFG { Expr *extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE); -} // namespace clang - //===----------------------------------------------------------------------===// // GraphTraits specializations for CFG basic block graphs (source-level CFGs) //===----------------------------------------------------------------------===// +namespace detail { +// The GraphTraits below present a CFGBlock's successors and predecessors as +// plain CFGBlock *, so generic graph algorithms need not know about +// AdjacentBlock. AB_Unreachable edges, whose reachable target is null, are kept +// in the CFG to preserve terminator successor positions but are not real +// control-flow edges and are skipped here. +struct CFGBlockReachableEdge { + bool operator()(const CFGBlock::AdjacentBlock &AB) const { + return AB.getReachableBlock() != nullptr; + } +}; +template <typename BlockT> struct CFGBlockEdgeTarget { + BlockT *operator()(const CFGBlock::AdjacentBlock &AB) const { + return AB.getReachableBlock(); + } +}; + +// A GraphTraits child iterator over BlockT: each AdjacentBlock edge projected +// to its reachable target, with unreachable (null) edges skipped. +template <typename IterT, typename BlockT> +using CFGReachableChildIterator = + llvm::mapped_iterator<llvm::filter_iterator<IterT, CFGBlockReachableEdge>, + CFGBlockEdgeTarget<BlockT>>; + +template <typename BlockT, typename RangeT> +auto cfgReachableChildren(RangeT Edges) { + return llvm::map_range( + llvm::make_filter_range(Edges, CFGBlockReachableEdge()), + CFGBlockEdgeTarget<BlockT>()); +} +} // namespace detail +} // namespace clang + namespace llvm { /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from @@ -1540,62 +1571,129 @@ template <> struct simplify_type< ::clang::CFGTerminator> { // Traits for: CFGBlock -template <> struct GraphTraits< ::clang::CFGBlock *> { - using NodeRef = ::clang::CFGBlock *; - using ChildIteratorType = ::clang::CFGBlock::succ_iterator; +// CFGBlocks are numbered densely from 0 by their BlockID, so dominator tree +// construction can index by number instead of using a DenseMap. +template <> struct GraphTraits<clang::CFGBlock *> { + using NodeRef = clang::CFGBlock *; + using ChildIteratorType = + clang::detail::CFGReachableChildIterator<clang::CFGBlock::succ_iterator, + clang::CFGBlock>; - static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } - static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } + static NodeRef getEntryNode(clang::CFGBlock *BB) { return BB; } + static ChildIteratorType child_begin(NodeRef N) { + return clang::detail::cfgReachableChildren<clang::CFGBlock>(N->succs()) + .begin(); + } + static ChildIteratorType child_end(NodeRef N) { + return clang::detail::cfgReachableChildren<clang::CFGBlock>(N->succs()) + .end(); + } + + static unsigned getNumber(const clang::CFGBlock *BB) { + return BB->getBlockID(); + } }; -template <> struct GraphTraits< const ::clang::CFGBlock *> { - using NodeRef = const ::clang::CFGBlock *; - using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; +static_assert(GraphHasNodeNumbers<clang::CFGBlock *>, + "GraphTraits getNumber() not detected"); + +template <> struct GraphTraits<const clang::CFGBlock *> { + using NodeRef = const clang::CFGBlock *; + using ChildIteratorType = clang::detail::CFGReachableChildIterator< + clang::CFGBlock::const_succ_iterator, const clang::CFGBlock>; static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } - static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } + static ChildIteratorType child_begin(NodeRef N) { + return clang::detail::cfgReachableChildren<const clang::CFGBlock>( + N->succs()) + .begin(); + } + static ChildIteratorType child_end(NodeRef N) { + return clang::detail::cfgReachableChildren<const clang::CFGBlock>( + N->succs()) + .end(); + } + + static unsigned getNumber(const clang::CFGBlock *BB) { + return BB->getBlockID(); + } }; -template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { - using NodeRef = ::clang::CFGBlock *; - using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; +static_assert(GraphHasNodeNumbers<const clang::CFGBlock *>, + "GraphTraits getNumber() not detected"); - static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { - return G.Graph; +template <> struct GraphTraits<Inverse<clang::CFGBlock *>> { + using NodeRef = clang::CFGBlock *; + using ChildIteratorType = + clang::detail::CFGReachableChildIterator<clang::CFGBlock::pred_iterator, + clang::CFGBlock>; + + static NodeRef getEntryNode(Inverse<clang::CFGBlock *> G) { return G.Graph; } + static ChildIteratorType child_begin(NodeRef N) { + return clang::detail::cfgReachableChildren<clang::CFGBlock>(N->preds()) + .begin(); + } + static ChildIteratorType child_end(NodeRef N) { + return clang::detail::cfgReachableChildren<clang::CFGBlock>(N->preds()) + .end(); } - static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } + static unsigned getNumber(const clang::CFGBlock *BB) { + return BB->getBlockID(); + } }; -template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { - using NodeRef = const ::clang::CFGBlock *; - using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; +static_assert(GraphHasNodeNumbers<Inverse<clang::CFGBlock *>>, + "GraphTraits getNumber() not detected"); + +template <> struct GraphTraits<Inverse<const clang::CFGBlock *>> { + using NodeRef = const clang::CFGBlock *; + using ChildIteratorType = clang::detail::CFGReachableChildIterator< + clang::CFGBlock::const_pred_iterator, const clang::CFGBlock>; - static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { + static NodeRef getEntryNode(Inverse<const clang::CFGBlock *> G) { return G.Graph; } + static ChildIteratorType child_begin(NodeRef N) { + return clang::detail::cfgReachableChildren<const clang::CFGBlock>( + N->preds()) + .begin(); + } + static ChildIteratorType child_end(NodeRef N) { + return clang::detail::cfgReachableChildren<const clang::CFGBlock>( + N->preds()) + .end(); + } - static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } - static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } + static unsigned getNumber(const clang::CFGBlock *BB) { + return BB->getBlockID(); + } }; +static_assert(GraphHasNodeNumbers<Inverse<const clang::CFGBlock *>>, + "GraphTraits getNumber() not detected"); + // Traits for: CFG -template <> struct GraphTraits< ::clang::CFG* > - : public GraphTraits< ::clang::CFGBlock *> { +template <> +struct GraphTraits<::clang::CFG *> : public GraphTraits<clang::CFGBlock *> { using nodes_iterator = ::clang::CFG::iterator; static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } static unsigned size(::clang::CFG* F) { return F->size(); } + + static unsigned getMaxNumber(const ::clang::CFG *F) { + return F->getNumBlockIDs(); + } + // Block numbers are fixed when the CFG is built and never change afterwards. + static unsigned getNumberEpoch(const ::clang::CFG *F) { return 0; } }; -template <> struct GraphTraits<const ::clang::CFG* > - : public GraphTraits<const ::clang::CFGBlock *> { +template <> +struct GraphTraits<const ::clang::CFG *> + : public GraphTraits<const clang::CFGBlock *> { using nodes_iterator = ::clang::CFG::const_iterator; static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } @@ -1611,19 +1709,31 @@ template <> struct GraphTraits<const ::clang::CFG* > static unsigned size(const ::clang::CFG* F) { return F->size(); } + + static unsigned getMaxNumber(const ::clang::CFG *F) { + return F->getNumBlockIDs(); + } + static unsigned getNumberEpoch(const ::clang::CFG *F) { return 0; } }; -template <> struct GraphTraits<Inverse< ::clang::CFG *>> - : public GraphTraits<Inverse< ::clang::CFGBlock *>> { +template <> +struct GraphTraits<Inverse<::clang::CFG *>> + : public GraphTraits<Inverse<clang::CFGBlock *>> { using nodes_iterator = ::clang::CFG::iterator; static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } + + static unsigned getMaxNumber(const ::clang::CFG *F) { + return F->getNumBlockIDs(); + } + static unsigned getNumberEpoch(const ::clang::CFG *F) { return 0; } }; -template <> struct GraphTraits<Inverse<const ::clang::CFG *>> - : public GraphTraits<Inverse<const ::clang::CFGBlock *>> { +template <> +struct GraphTraits<Inverse<const ::clang::CFG *>> + : public GraphTraits<Inverse<const clang::CFGBlock *>> { using nodes_iterator = ::clang::CFG::const_iterator; static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } @@ -1635,6 +1745,11 @@ template <> struct GraphTraits<Inverse<const ::clang::CFG *>> static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->nodes_end(); } + + static unsigned getMaxNumber(const ::clang::CFG *F) { + return F->getNumBlockIDs(); + } + static unsigned getNumberEpoch(const ::clang::CFG *F) { return 0; } }; } // namespace llvm diff --git a/llvm/include/llvm/Support/GenericDomTreeConstruction.h b/llvm/include/llvm/Support/GenericDomTreeConstruction.h index 869087cda219a..f9596576b3abd 100644 --- a/llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ b/llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -111,9 +111,6 @@ template <typename DomTreeT> struct SemiNCAInfo { static SmallVector<NodePtr, 8> getChildren(NodePtr N, BatchUpdatePtr BUI) { if (BUI) return BUI->PreViewCFG.template getChildren<Inversed>(N); - // Force the element type to NodePtr. some graphs (clang's - // CFGBlock::AdjacentBlock) yield a proxy convertible to NodePtr rather than - // NodePtr itself. auto Children = getChildren<Inversed>(N); return SmallVector<NodePtr, 8>(Children.begin(), Children.end()); } @@ -123,14 +120,7 @@ template <typename DomTreeT> struct SemiNCAInfo { template <bool Inversed> static auto getChildren(NodePtr N) { using DirectedNodeT = std::conditional_t<Inversed, Inverse<NodePtr>, NodePtr>; - auto R = detail::reverse_if<!Inversed>(children<DirectedNodeT>(N)); - // Most graphs' iterators yield NodePtr directly; return the range as is. - // clang's CFGBlock instead yields a CFGBlock::AdjacentBlock proxy that is - // convertible to NodePtr but can be null for AB_Unreachable. - if constexpr (std::is_same_v<std::decay_t<decltype(*R.begin())>, NodePtr>) - return R; - else - return llvm::make_filter_range(R, [](NodePtr C) { return C != nullptr; }); + return detail::reverse_if<!Inversed>(children<DirectedNodeT>(N)); } InfoRec &getNodeInfo(NodePtr BB) { >From f1aa550b6114da3294d6914499e39feb37c26e9d Mon Sep 17 00:00:00 2001 From: Fangrui Song <[email protected]> Date: Sat, 4 Jul 2026 19:03:43 -0700 Subject: [PATCH 2/2] simplify llvm/include/llvm/Support/CFGDiff.h --- llvm/include/llvm/Support/CFGDiff.h | 3 --- 1 file changed, 3 deletions(-) diff --git a/llvm/include/llvm/Support/CFGDiff.h b/llvm/include/llvm/Support/CFGDiff.h index 88f4fe52d2019..f81215ed71bd4 100644 --- a/llvm/include/llvm/Support/CFGDiff.h +++ b/llvm/include/llvm/Support/CFGDiff.h @@ -136,9 +136,6 @@ template <typename NodePtr, bool InverseGraph = false> class GraphDiff { auto R = children<DirectedNodeT>(N); VectRet Res = VectRet(detail::reverse_if<!InverseEdge>(R)); - // Remove nullptr children for clang. - llvm::erase(Res, nullptr); - auto &Children = (InverseEdge != InverseGraph) ? Pred : Succ; auto It = Children.find(N); if (It == Children.end()) _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
