https://github.com/aengelke updated https://github.com/llvm/llvm-project/pull/191047
>From aa004c0eed82a0651178f73d2c7bbeb7dc359462 Mon Sep 17 00:00:00 2001 From: Alexis Engelke <[email protected]> Date: Wed, 8 Apr 2026 20:08:51 +0000 Subject: [PATCH 1/2] [spr] initial version Created using spr 1.3.8-wip --- llvm/include/llvm/ADT/PostOrderIterator.h | 218 ++++++++++++------ .../llvm/Analysis/BlockFrequencyInfoImpl.h | 3 +- llvm/include/llvm/Analysis/LoopIterator.h | 46 +--- llvm/lib/Analysis/BranchProbabilityInfo.cpp | 2 +- llvm/lib/Analysis/CFGPrinter.cpp | 2 +- llvm/lib/Analysis/LoopInfo.cpp | 4 +- llvm/lib/CodeGen/MachineTraceMetrics.cpp | 19 +- .../Transforms/Vectorize/SLPVectorizer.cpp | 2 +- llvm/lib/Transforms/Vectorize/VPlanCFG.h | 5 +- .../Transforms/Vectorize/VPlanTransforms.cpp | 10 +- llvm/lib/Transforms/Vectorize/VPlanUtils.h | 3 +- llvm/unittests/ADT/PostOrderIteratorTest.cpp | 34 +-- .../Transforms/Vectorize/VPlanTest.cpp | 9 +- mlir/include/mlir/IR/Iterators.h | 4 +- 14 files changed, 190 insertions(+), 171 deletions(-) diff --git a/llvm/include/llvm/ADT/PostOrderIterator.h b/llvm/include/llvm/ADT/PostOrderIterator.h index 1dfd259e58897..cb777d6c3055b 100644 --- a/llvm/include/llvm/ADT/PostOrderIterator.h +++ b/llvm/include/llvm/ADT/PostOrderIterator.h @@ -120,6 +120,142 @@ using DefaultSet = } // namespace po_detail +template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { + using GT = GraphTraits<GraphT>; + using NodeRef = typename GT::NodeRef; + using ChildItTy = typename GT::ChildIteratorType; + + /// Used to maintain the ordering. + /// First element is basic block pointer, second is iterator for the next + /// child to visit, third is the end iterator. + SmallVector<std::tuple<NodeRef, ChildItTy, ChildItTy>, 8> VisitStack; + +public: + class iterator { + friend class PostOrderTraversalBase; + + public: + using iterator_category = std::input_iterator_tag; + using value_type = NodeRef; + using difference_type = std::ptrdiff_t; + using pointer = value_type *; + using reference = NodeRef; + + private: + DerivedT *POT = nullptr; + NodeRef V = nullptr; + + public: + iterator() = default; + + private: + iterator(DerivedT &POT, value_type V) : POT(&POT), V(V) {} + + public: + bool operator==(const iterator &X) const { return V == X.V; } + bool operator!=(const iterator &X) const { return !(*this == X); } + + NodeRef operator*() const { return V; } + + // This is a nonstandard operator-> that dereferences the pointer an extra + // time... so that you can actually call methods ON the BasicBlock, because + // the contained type is a pointer. This allows BBIt->getTerminator() f.e. + // + NodeRef operator->() const { return **this; } + + iterator &operator++() { // Preincrement + V = POT->next(); + return *this; + } + + iterator operator++(int) { // Postincrement + iterator tmp = *this; + ++*this; + return tmp; + } + }; + +protected: + PostOrderTraversalBase() = default; + + DerivedT *derived() { return static_cast<DerivedT *>(this); } + + void init(NodeRef Start) { + if (derived()->insertEdge(std::optional<NodeRef>(), Start)) { + VisitStack.emplace_back(Start, GT::child_begin(Start), + GT::child_end(Start)); + traverseChild(); + } + } + +private: + void traverseChild() { + while (true) { + auto &Entry = VisitStack.back(); + if (std::get<1>(Entry) == std::get<2>(Entry)) + break; + NodeRef BB = *std::get<1>(Entry)++; + if (derived()->insertEdge(std::optional<NodeRef>(std::get<0>(Entry)), + BB)) { + // If the block is not visited... + VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB)); + } + } + } + + NodeRef next() { + derived()->finishPostorder(std::get<0>(VisitStack.back())); + VisitStack.pop_back(); + if (!VisitStack.empty()) + traverseChild(); + return !VisitStack.empty() ? std::get<0>(VisitStack.back()) : nullptr; + } + +public: + iterator begin() { + if (VisitStack.empty()) + return iterator(); // We don't even want to see the start node. + return iterator(*derived(), std::get<0>(VisitStack.back())); + } + iterator end() { return iterator(); } + + // Methods that are intended to be overridden by sub-classes. + + /// Add edge and return whether To should be visited. From is nullopt for the + /// root node. + bool insertEdge(std::optional<NodeRef> From, NodeRef To); + + /// Callback just before the iterator moves to the next block. + void finishPostorder(NodeRef) {} +}; + +/// Post-order traversal of a graph. +template <typename GraphT, typename SetType = po_detail::DefaultSet<GraphT>> +class PostOrderTraversal + : public PostOrderTraversalBase<PostOrderTraversal<GraphT, SetType>, + GraphT> { + using NodeRef = typename GraphTraits<GraphT>::NodeRef; + + SetType Visited; + +public: + PostOrderTraversal(const GraphT &G) { + this->init(GraphTraits<GraphT>::getEntryNode(G)); +#if 0 + if constexpr (GraphHasNodeNumbers<GraphT>) + Visited.reserve(GraphTraits<GraphT>::getMaxNumber(G)); +#endif + } + + PostOrderTraversal(const GraphT &G, SetType &S) : Visited(S) { + this->init(GraphTraits<GraphT>::getEntryNode(G)); + } + + bool insertEdge(std::optional<NodeRef> From, NodeRef To) { + return Visited.insert(To).second; + } +}; + template <class GraphT, class SetType = po_detail::DefaultSet<GraphT>, bool ExtStorage = false, class GT = GraphTraits<GraphT>> class po_iterator : public po_iterator_storage<SetType, ExtStorage> { @@ -217,83 +353,15 @@ class po_iterator : public po_iterator_storage<SetType, ExtStorage> { // Provide global constructors that automatically figure out correct types... // -template <class T> -po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); } -template <class T> -po_iterator<T> po_end (const T &G) { return po_iterator<T>::end(G); } - -template <class T> iterator_range<po_iterator<T>> post_order(const T &G) { - return make_range(po_begin(G), po_end(G)); -} - -// Provide global definitions of external postorder iterators... -template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>> -struct po_ext_iterator : po_iterator<T, SetType, true> { - po_ext_iterator(const po_iterator<T, SetType, true> &V) : - po_iterator<T, SetType, true>(V) {} -}; - -template <class T, class SetType> -po_ext_iterator<T, SetType> po_ext_begin(const T &G, SetType &S) { - return po_ext_iterator<T, SetType>::begin(G, S); -} - -template <class T, class SetType> -po_ext_iterator<T, SetType> po_ext_end(const T &G, SetType &S) { - return po_ext_iterator<T, SetType>::end(G, S); -} - -template <class T, class SetType> -iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) { - return make_range(po_ext_begin(G, S), po_ext_end(G, S)); -} - -// Provide global definitions of inverse post order iterators... -template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>, - bool External = false> -struct ipo_iterator : po_iterator<Inverse<T>, SetType, External> { - ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) : - po_iterator<Inverse<T>, SetType, External> (V) {} -}; - -template <class T> -ipo_iterator<T> ipo_begin(const T &G) { - return ipo_iterator<T>::begin(G); +template <class T> auto post_order(const T &G) { + return PostOrderTraversal<T>(G); } - -template <class T> -ipo_iterator<T> ipo_end(const T &G){ - return ipo_iterator<T>::end(G); +template <class T, class SetType> auto post_order_ext(const T &G, SetType &S) { + return PostOrderTraversal<T, SetType &>(G, S); } - -template <class T> -iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) { - return make_range(ipo_begin(G), ipo_end(G)); -} - -// Provide global definitions of external inverse postorder iterators... -template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>> -struct ipo_ext_iterator : ipo_iterator<T, SetType, true> { - ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) : - ipo_iterator<T, SetType, true>(V) {} - ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) : - ipo_iterator<T, SetType, true>(V) {} -}; - -template <class T, class SetType> -ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) { - return ipo_ext_iterator<T, SetType>::begin(G, S); -} - -template <class T, class SetType> -ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) { - return ipo_ext_iterator<T, SetType>::end(G, S); -} - template <class T, class SetType> -iterator_range<ipo_ext_iterator<T, SetType>> -inverse_post_order_ext(const T &G, SetType &S) { - return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S)); +auto inverse_post_order_ext(const T &G, SetType &S) { + return PostOrderTraversal<Inverse<T>, SetType &>(G, S); } //===--------------------------------------------------------------------===// @@ -331,7 +399,7 @@ class ReversePostOrderTraversal { VecTy Blocks; // Block list in normal PO order void Initialize(const GraphT &G) { - std::copy(po_begin(G), po_end(G), std::back_inserter(Blocks)); + llvm::copy(post_order(G), std::back_inserter(Blocks)); } public: diff --git a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h index cc2404a0249e7..7cc40084b9247 100644 --- a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -1106,9 +1106,8 @@ void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, } template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() { - const BlockT *Entry = &F->front(); RPOT.reserve(F->size()); - for (const BlockT *BB : post_order(Entry)) + for (const BlockT *BB : post_order(F)) RPOT.emplace_back(BB); std::reverse(RPOT.begin(), RPOT.end()); diff --git a/llvm/include/llvm/Analysis/LoopIterator.h b/llvm/include/llvm/Analysis/LoopIterator.h index 1ac8e68bfa2f1..b359812d396cd 100644 --- a/llvm/include/llvm/Analysis/LoopIterator.h +++ b/llvm/include/llvm/Analysis/LoopIterator.h @@ -186,49 +186,33 @@ class LoopBlocksRPO { LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); } }; -/// Specialize po_iterator_storage to record postorder numbers. -template<> class po_iterator_storage<LoopBlocksTraversal, true> { - LoopBlocksTraversal &LBT; -public: - po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} - // These functions are defined below. - bool insertEdge(std::optional<BasicBlock *> From, BasicBlock *To); - void finishPostorder(BasicBlock *BB); -}; - /// Traverse the blocks in a loop using a depth-first search. -class LoopBlocksTraversal { -public: - /// Graph traversal iterator. - typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; - -private: +class LoopBlocksTraversal + : public PostOrderTraversalBase<LoopBlocksTraversal, Function *> { LoopBlocksDFS &DFS; const LoopInfo *LI; public: - LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo) : - DFS(Storage), LI(LInfo) {} + LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo) + : DFS(Storage), LI(LInfo) {} /// Postorder traversal over the graph. This only needs to be done once. /// po_iterator "automatically" calls back to visitPreorder and /// finishPostorder to record the DFS result. - POTIterator begin() { + iterator begin() { assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); - assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); - return po_ext_begin(DFS.L->getHeader(), *this); - } - POTIterator end() { - // po_ext_end interface requires a basic block, but ignores its value. - return po_ext_end(DFS.L->getHeader(), *this); + assert(DFS.L->getNumBlocks() && "cannot handle an empty graph"); + init(DFS.L->getHeader()); + return PostOrderTraversalBase::begin(); } + iterator end() { return PostOrderTraversalBase::end(); } /// Called by po_iterator upon reaching a block via a CFG edge. If this block /// is contained in the loop and has not been visited, then mark it preorder /// visited and return true. /// /// TODO: If anyone is interested, we could record preorder numbers here. - bool visitPreorder(BasicBlock *BB) { + bool insertEdge(std::optional<BasicBlock *> /*From*/, BasicBlock *BB) { if (!DFS.L->contains(LI->getLoopFor(BB))) return false; @@ -244,16 +228,6 @@ class LoopBlocksTraversal { } }; -inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( - std::optional<BasicBlock *> From, BasicBlock *To) { - return LBT.visitPreorder(To); -} - -inline void po_iterator_storage<LoopBlocksTraversal, true>:: -finishPostorder(BasicBlock *BB) { - LBT.finishPostorder(BB); -} - } // End namespace llvm #endif diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index 490bfbc0fb7ca..fdb539d91313c 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -1263,7 +1263,7 @@ void BPIConstruction::calculate(const Function &F, const LoopInfo &LoopI, // Walk the basic blocks in post-order so that we can build up state about // the successors of a block iteratively. - for (const auto *BB : post_order(&F.getEntryBlock())) { + for (const auto *BB : post_order(&F)) { LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); // If there is no at least two successors, no sense to set probability. diff --git a/llvm/lib/Analysis/CFGPrinter.cpp b/llvm/lib/Analysis/CFGPrinter.cpp index 39108a906f081..18776bc539b32 100644 --- a/llvm/lib/Analysis/CFGPrinter.cpp +++ b/llvm/lib/Analysis/CFGPrinter.cpp @@ -206,7 +206,7 @@ void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths( }; /// The post order traversal iteration is done to know the status of /// isOnDeoptOrUnreachablePath for all the successors on the current BB. - llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB); + llvm::for_each(post_order(F), evaluateBB); } bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node, diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp index 8e08a70e69cdd..b459b12d47e8e 100644 --- a/llvm/lib/Analysis/LoopInfo.cpp +++ b/llvm/lib/Analysis/LoopInfo.cpp @@ -1284,8 +1284,6 @@ PreservedAnalyses LoopVerifierPass::run(Function &F, /// visit blocks during the initial traversal. void LoopBlocksDFS::perform(const LoopInfo *LI) { LoopBlocksTraversal Traversal(*this, LI); - for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(), - POE = Traversal.end(); - POI != POE; ++POI) + for ([[maybe_unused]] BasicBlock *BB : Traversal) ; } diff --git a/llvm/lib/CodeGen/MachineTraceMetrics.cpp b/llvm/lib/CodeGen/MachineTraceMetrics.cpp index 81dd68a519e76..9b7bf6ea3cc82 100644 --- a/llvm/lib/CodeGen/MachineTraceMetrics.cpp +++ b/llvm/lib/CodeGen/MachineTraceMetrics.cpp @@ -484,13 +484,17 @@ struct LoopBounds { // Specialize po_iterator_storage in order to prune the post-order traversal so // it is limited to the current loop and doesn't traverse the loop back edges. -template <> class llvm::po_iterator_storage<LoopBounds, true> { +template <typename GraphT> +class LoopBoundsPostOrderTraversal + : public PostOrderTraversalBase<LoopBoundsPostOrderTraversal<GraphT>, + GraphT> { LoopBounds &LB; public: - po_iterator_storage(LoopBounds &lb) : LB(lb) {} - - void finishPostorder(const MachineBasicBlock*) {} + LoopBoundsPostOrderTraversal(const MachineBasicBlock *Start, LoopBounds &LB) + : LB(LB) { + this->init(Start); + } bool insertEdge(std::optional<const MachineBasicBlock *> From, const MachineBasicBlock *To) { @@ -525,7 +529,9 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { // Run an upwards post-order search for the trace start. Bounds.Downward = false; Bounds.Visited.clear(); - for (const auto *I : inverse_post_order_ext(MBB, Bounds)) { + for (const auto *I : + LoopBoundsPostOrderTraversal<Inverse<const MachineBasicBlock *>>( + MBB, Bounds)) { LLVM_DEBUG(dbgs() << " pred for " << printMBBReference(*I) << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the predecessors have been visited, pick the preferred one. @@ -543,7 +549,8 @@ void MachineTraceMetrics::Ensemble::computeTrace(const MachineBasicBlock *MBB) { // Run a downwards post-order search for the trace end. Bounds.Downward = true; Bounds.Visited.clear(); - for (const auto *I : post_order_ext(MBB, Bounds)) { + for (const auto *I : + LoopBoundsPostOrderTraversal<const MachineBasicBlock *>(MBB, Bounds)) { LLVM_DEBUG(dbgs() << " succ for " << printMBBReference(*I) << ": "); TraceBlockInfo &TBI = BlockInfo[I->getNumber()]; // All the successors have been visited, pick the preferred one. diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index f2ccf198c4c81..bc26d74ba3e67 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -25250,7 +25250,7 @@ bool SLPVectorizerPass::runImpl(Function &F, ScalarEvolution *SE_, DT->updateDFSNumbers(); // Scan the blocks in the function in post order. - for (auto *BB : post_order(&F.getEntryBlock())) { + for (auto *BB : post_order(&F)) { if (BB->isEHPad() || isa_and_nonnull<UnreachableInst>(BB->getTerminator())) continue; diff --git a/llvm/lib/Transforms/Vectorize/VPlanCFG.h b/llvm/lib/Transforms/Vectorize/VPlanCFG.h index 963d84675693a..58e43a9d81809 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanCFG.h +++ b/llvm/lib/Transforms/Vectorize/VPlanCFG.h @@ -261,15 +261,14 @@ vp_depth_first_shallow(const VPBlockBase *G) { /// Returns an iterator range to traverse the graph starting at \p G in /// post order. The iterator won't traverse through region blocks. -inline iterator_range< - po_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>> +inline PostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> vp_post_order_shallow(VPBlockBase *G) { return post_order(VPBlockShallowTraversalWrapper<VPBlockBase *>(G)); } /// Returns an iterator range to traverse the graph starting at \p G in /// post order while traversing through region blocks. -inline iterator_range<po_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>> +inline PostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> vp_post_order_deep(VPBlockBase *G) { return post_order(VPBlockDeepTraversalWrapper<VPBlockBase *>(G)); } diff --git a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp index 5fbdb2aa98d9f..8ce2d682a123f 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp @@ -734,8 +734,9 @@ static bool isDeadRecipe(VPRecipeBase &R) { } void VPlanTransforms::removeDeadRecipes(VPlan &Plan) { - for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>( - vp_post_order_deep(Plan.getEntry()))) { + PostOrderTraversal<VPBlockDeepTraversalWrapper<VPBlockBase *>> POT( + Plan.getEntry()); + for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(POT)) { // The recipes in the block are processed in reverse order, to catch chains // of dead recipes. for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) { @@ -2711,8 +2712,9 @@ static void licm(VPlan &Plan) { // Sink recipes with no users inside the vector loop region if all users are // in the same exit block of the region. // TODO: Extend to sink recipes from inner loops. - for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>( - vp_post_order_shallow(LoopRegion->getEntry()))) { + PostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> POT( + LoopRegion->getEntry()); + for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(POT)) { for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) { if (cannotHoistOrSinkRecipe(R)) continue; diff --git a/llvm/lib/Transforms/Vectorize/VPlanUtils.h b/llvm/lib/Transforms/Vectorize/VPlanUtils.h index 5fdd5ea4204e0..2cab5967b42f7 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanUtils.h +++ b/llvm/lib/Transforms/Vectorize/VPlanUtils.h @@ -269,8 +269,7 @@ class VPBlockUtils { /// Return an iterator range over \p Range which only includes \p BlockTy /// blocks. The accesses are casted to \p BlockTy. - template <typename BlockTy, typename T> - static auto blocksOnly(const T &Range) { + template <typename BlockTy, typename T> static auto blocksOnly(T &&Range) { // Create BaseTy with correct const-ness based on BlockTy. using BaseTy = std::conditional_t<std::is_const<BlockTy>::value, const VPBlockBase, VPBlockBase>; diff --git a/llvm/unittests/ADT/PostOrderIteratorTest.cpp b/llvm/unittests/ADT/PostOrderIteratorTest.cpp index 11da6925bb1fb..f66d9b6bc8b83 100644 --- a/llvm/unittests/ADT/PostOrderIteratorTest.cpp +++ b/llvm/unittests/ADT/PostOrderIteratorTest.cpp @@ -38,9 +38,9 @@ TEST(PostOrderIteratorTest, Compiles) { Graph<6> G; using NodeType = Graph<6>::NodeType; NodeType *NullNode = nullptr; - auto PI = po_end(G); + auto PI = post_order(G); PI.insertEdge(std::optional<NodeType *>(), NullNode); - auto PIExt = po_ext_end(G, Ext); + auto PIExt = post_order_ext(G, Ext); PIExt.insertEdge(std::optional<NodeType *>(), NullNode); } @@ -83,34 +83,4 @@ TEST(PostOrderIteratorTest, PostOrderAndReversePostOrderTraverrsal) { EXPECT_EQ(1, FromIterator[4]); EXPECT_EQ(4, FromIterator[5]); } - -// po_iterator should be (at-least) a forward-iterator -static_assert(std::is_base_of_v<std::forward_iterator_tag, - po_iterator<Graph<4>>::iterator_category>); - -// po_ext_iterator cannot provide multi-pass guarantee, therefore its only -// an input-iterator -static_assert(std::is_same_v<po_ext_iterator<Graph<4>>::iterator_category, - std::input_iterator_tag>); - -TEST(PostOrderIteratorTest, MultiPassSafeWithInternalSet) { - Graph<4> G; - G.AddEdge(0, 1); - G.AddEdge(1, 2); - G.AddEdge(1, 3); - - std::array<decltype(G)::NodeType *, 4> NodesFirstPass, NodesSecondPass; - - auto B = po_begin(G), E = po_end(G); - - std::size_t I = 0; - for (auto It = B; It != E; ++It) - NodesFirstPass[I++] = *It; - - I = 0; - for (auto It = B; It != E; ++It) - NodesSecondPass[I++] = *It; - - EXPECT_EQ(NodesFirstPass, NodesSecondPass); -} } diff --git a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp index 017aa6dab705e..b378b74618258 100644 --- a/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/VPlanTest.cpp @@ -546,7 +546,7 @@ TEST_F(VPBasicBlockTest, TraversingIteratorTest) { // Post-order. FromIterator.clear(); - FromIterator.append(po_begin(Start), po_end(Start)); + copy(post_order(Start), std::back_inserter(FromIterator)); EXPECT_EQ(10u, FromIterator.size()); EXPECT_EQ(VPBB2, FromIterator[0]); EXPECT_EQ(R1BB3, FromIterator[1]); @@ -597,7 +597,7 @@ TEST_F(VPBasicBlockTest, TraversingIteratorTest) { // Post-order. FromIterator.clear(); - FromIterator.append(po_begin(Start), po_end(Start)); + copy(post_order(Start), std::back_inserter(FromIterator)); EXPECT_EQ(5u, FromIterator.size()); EXPECT_EQ(R2BB2, FromIterator[0]); EXPECT_EQ(R2BB1, FromIterator[1]); @@ -678,8 +678,9 @@ TEST_F(VPBasicBlockTest, TraversingIteratorTest) { // Post-order, const VPRegionBlocks only. VPBlockDeepTraversalWrapper<const VPBlockBase *> StartConst(VPBB1); - SmallVector<const VPRegionBlock *> FromIteratorVPRegion( - VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst))); + SmallVector<const VPRegionBlock *> FromIteratorVPRegion; + copy(VPBlockUtils::blocksOnly<const VPRegionBlock>(post_order(StartConst)), + std::back_inserter(FromIteratorVPRegion)); EXPECT_EQ(3u, FromIteratorVPRegion.size()); EXPECT_EQ(R3, FromIteratorVPRegion[0]); EXPECT_EQ(R2, FromIteratorVPRegion[1]); diff --git a/mlir/include/mlir/IR/Iterators.h b/mlir/include/mlir/IR/Iterators.h index dcb738c549438..4754d3beb2c6e 100644 --- a/mlir/include/mlir/IR/Iterators.h +++ b/mlir/include/mlir/IR/Iterators.h @@ -100,9 +100,10 @@ struct ReverseDominanceIterator { static constexpr auto makeIterable(Operation &range) { return llvm::reverse(ForwardIterator::makeIterable(range)); } - +#if 0 static auto makeIterable(Region ®ion) { Block *null = nullptr; + llvm::PostOrderTraversal<Block *>::iterator sentinel; if (SkipGraphRegion && !mayHaveSSADominance(region)) { // Skip graph regions. return llvm::make_pointee_range( @@ -118,6 +119,7 @@ struct ReverseDominanceIterator { // Walk API expects Block references instead of pointers. return llvm::make_pointee_range(it); } +#endif }; } // namespace mlir >From d2b122989fc605b6aaba551c2faf6618a6cfa1c8 Mon Sep 17 00:00:00 2001 From: Alexis Engelke <[email protected]> Date: Thu, 9 Apr 2026 07:45:17 +0000 Subject: [PATCH 2/2] Fix Clang+MLIR Created using spr 1.3.8-wip --- .../Analysis/Analyses/PostOrderCFGView.h | 51 ----- clang/lib/Analysis/PostOrderCFGView.cpp | 38 +++- llvm/include/llvm/ADT/PostOrderIterator.h | 191 +----------------- .../llvm/Analysis/BlockFrequencyInfoImpl.h | 3 +- llvm/include/llvm/Analysis/LoopIterator.h | 3 +- llvm/lib/Analysis/BranchProbabilityInfo.cpp | 2 +- llvm/lib/Analysis/CFGPrinter.cpp | 2 +- llvm/lib/CodeGen/MachineTraceMetrics.cpp | 2 +- .../Transforms/Vectorize/SLPVectorizer.cpp | 2 +- mlir/include/mlir/IR/Iterators.h | 41 ++-- 10 files changed, 78 insertions(+), 257 deletions(-) diff --git a/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h index c4998bb2285f7..0a37fdea63fac 100644 --- a/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h +++ b/clang/include/clang/Analysis/Analyses/PostOrderCFGView.h @@ -29,32 +29,16 @@ class PostOrderCFGView : public ManagedAnalysis { public: /// Implements a set of CFGBlocks using a BitVector. - /// - /// This class contains a minimal interface, primarily dictated by the SetType - /// template parameter of the llvm::po_iterator template, as used with - /// external storage. We also use this set to keep track of which CFGBlocks we - /// visit during the analysis. class CFGBlockSet { llvm::BitVector VisitedBlockIDs; public: - // po_iterator requires this iterator, but the only interface needed is the - // value_type type. - struct iterator { using value_type = const CFGBlock *; }; - CFGBlockSet() = default; CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} /// Set the bit associated with a particular CFGBlock. /// This is the important method for the SetType template parameter. std::pair<std::nullopt_t, bool> insert(const CFGBlock *Block) { - // Note that insert() is called by po_iterator, which doesn't check to - // make sure that Block is non-null. Moreover, the CFGBlock iterator will - // occasionally hand out null pointers for pruned edges, so we catch those - // here. - if (!Block) - return std::make_pair(std::nullopt, - false); // if an edge is trivially false. if (VisitedBlockIDs.test(Block->getBlockID())) return std::make_pair(std::nullopt, false); VisitedBlockIDs.set(Block->getBlockID()); @@ -70,41 +54,6 @@ class PostOrderCFGView : public ManagedAnalysis { }; private: - // The CFG orders the blocks of loop bodies before those of loop successors - // (both numerically, and in the successor order of the loop condition - // block). So, RPO necessarily reverses that order, placing the loop successor - // *before* the loop body. For many analyses, particularly those that converge - // to a fixpoint, this results in potentially significant extra work because - // loop successors will necessarily need to be reconsidered once the algorithm - // has reached a fixpoint on the loop body. - // - // This definition of CFG graph traits reverses the order of children, so that - // loop bodies will come first in an RPO. - struct CFGLoopBodyFirstTraits { - using NodeRef = const ::clang::CFGBlock *; - using ChildIteratorType = ::clang::CFGBlock::const_succ_reverse_iterator; - - static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); } - static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); } - - using nodes_iterator = ::clang::CFG::const_iterator; - - static NodeRef getEntryNode(const ::clang::CFG *F) { - return &F->getEntry(); - } - - static nodes_iterator nodes_begin(const ::clang::CFG *F) { - return F->nodes_begin(); - } - - static nodes_iterator nodes_end(const ::clang::CFG *F) { - return F->nodes_end(); - } - - static unsigned size(const ::clang::CFG *F) { return F->size(); } - }; - using po_iterator = - llvm::po_iterator<const CFG *, CFGBlockSet, true, CFGLoopBodyFirstTraits>; std::vector<const CFGBlock *> Blocks; using BlockOrderTy = llvm::DenseMap<const CFGBlock *, unsigned>; diff --git a/clang/lib/Analysis/PostOrderCFGView.cpp b/clang/lib/Analysis/PostOrderCFGView.cpp index 0c09c0f97ff68..324d64c25e090 100644 --- a/clang/lib/Analysis/PostOrderCFGView.cpp +++ b/clang/lib/Analysis/PostOrderCFGView.cpp @@ -20,12 +20,40 @@ void PostOrderCFGView::anchor() {} PostOrderCFGView::PostOrderCFGView(const CFG *cfg) { Blocks.reserve(cfg->getNumBlockIDs()); - CFGBlockSet BSet(cfg); - for (po_iterator I = po_iterator::begin(cfg, BSet), - E = po_iterator::end(cfg, BSet); I != E; ++I) { - BlockOrder[*I] = Blocks.size() + 1; - Blocks.push_back(*I); + // The CFG orders the blocks of loop bodies before those of loop successors + // (both numerically, and in the successor order of the loop condition + // block). So, RPO necessarily reverses that order, placing the loop successor + // *before* the loop body. For many analyses, particularly those that converge + // to a fixpoint, this results in potentially significant extra work because + // loop successors will necessarily need to be reconsidered once the algorithm + // has reached a fixpoint on the loop body. + // + // This definition of CFG graph traits reverses the order of children, so that + // loop bodies will come first in an RPO. + struct CFGLoopBodyFirstTraits { + using NodeRef = const ::clang::CFGBlock *; + using ChildIteratorType = ::clang::CFGBlock::const_succ_reverse_iterator; + + static ChildIteratorType child_begin(NodeRef N) { return N->succ_rbegin(); } + static ChildIteratorType child_end(NodeRef N) { return N->succ_rend(); } + }; + + struct POTraversal + : llvm::PostOrderTraversalBase<POTraversal, CFGLoopBodyFirstTraits> { + CFGBlockSet BSet; + + POTraversal(const CFG *cfg) : BSet(cfg) { this->init(&cfg->getEntry()); } + bool insertEdge(std::optional<const CFGBlock *>, const CFGBlock *To) { + if (!To) + return false; + return BSet.insert(To).second; + } + }; + + for (const CFGBlock *Block : POTraversal(cfg)) { + BlockOrder[Block] = Blocks.size() + 1; + Blocks.push_back(Block); } } diff --git a/llvm/include/llvm/ADT/PostOrderIterator.h b/llvm/include/llvm/ADT/PostOrderIterator.h index cb777d6c3055b..77ce6cc6c6ff2 100644 --- a/llvm/include/llvm/ADT/PostOrderIterator.h +++ b/llvm/include/llvm/ADT/PostOrderIterator.h @@ -19,78 +19,12 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/iterator_range.h" #include <iterator> #include <optional> -#include <set> #include <type_traits> #include <utility> namespace llvm { - -// The po_iterator_storage template provides access to the set of already -// visited nodes during the po_iterator's depth-first traversal. -// -// The default implementation simply contains a set of visited nodes, while -// the External=true version uses a reference to an external set. -// -// It is possible to prune the depth-first traversal in several ways: -// -// - When providing an external set that already contains some graph nodes, -// those nodes won't be visited again. This is useful for restarting a -// post-order traversal on a graph with nodes that aren't dominated by a -// single node. -// -// - By providing a custom SetType class, unwanted graph nodes can be excluded -// by having the insert() function return false. This could for example -// confine a CFG traversal to blocks in a specific loop. -// -// - Finally, by specializing the po_iterator_storage template itself, graph -// edges can be pruned by returning false in the insertEdge() function. This -// could be used to remove loop back-edges from the CFG seen by po_iterator. -// -// A specialized po_iterator_storage class can observe both the pre-order and -// the post-order. The insertEdge() function is called in a pre-order, while -// the finishPostorder() function is called just before the po_iterator moves -// on to the next node. - -/// Default po_iterator_storage implementation with an internal set object. -template<class SetType, bool External> -class po_iterator_storage { - SetType Visited; - -public: - // Return true if edge destination should be visited. - template <typename NodeRef> - bool insertEdge(std::optional<NodeRef> From, NodeRef To) { - return Visited.insert(To).second; - } - - // Called after all children of BB have been visited. - template <typename NodeRef> void finishPostorder(NodeRef BB) {} -}; - -/// Specialization of po_iterator_storage that references an external set. -template<class SetType> -class po_iterator_storage<SetType, true> { - SetType &Visited; - -public: - po_iterator_storage(SetType &VSet) : Visited(VSet) {} - po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {} - - // Return true if edge destination should be visited, called with From = 0 for - // the root node. - // Graph edges can be pruned by specializing this function. - template <class NodeRef> - bool insertEdge(std::optional<NodeRef> From, NodeRef To) { - return Visited.insert(To).second; - } - - // Called after all children of BB have been visited. - template <class NodeRef> void finishPostorder(NodeRef BB) {} -}; - namespace po_detail { template <typename NodeRef> class NumberSet { @@ -120,10 +54,10 @@ using DefaultSet = } // namespace po_detail -template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { - using GT = GraphTraits<GraphT>; - using NodeRef = typename GT::NodeRef; - using ChildItTy = typename GT::ChildIteratorType; +template <typename DerivedT, typename GraphTraits> +class PostOrderTraversalBase { + using NodeRef = typename GraphTraits::NodeRef; + using ChildItTy = typename GraphTraits::ChildIteratorType; /// Used to maintain the ordering. /// First element is basic block pointer, second is iterator for the next @@ -155,13 +89,8 @@ template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { bool operator==(const iterator &X) const { return V == X.V; } bool operator!=(const iterator &X) const { return !(*this == X); } - NodeRef operator*() const { return V; } - - // This is a nonstandard operator-> that dereferences the pointer an extra - // time... so that you can actually call methods ON the BasicBlock, because - // the contained type is a pointer. This allows BBIt->getTerminator() f.e. - // - NodeRef operator->() const { return **this; } + reference operator*() const { return V; } + pointer operator->() const { return &V; } iterator &operator++() { // Preincrement V = POT->next(); @@ -182,8 +111,8 @@ template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { void init(NodeRef Start) { if (derived()->insertEdge(std::optional<NodeRef>(), Start)) { - VisitStack.emplace_back(Start, GT::child_begin(Start), - GT::child_end(Start)); + VisitStack.emplace_back(Start, GraphTraits::child_begin(Start), + GraphTraits::child_end(Start)); traverseChild(); } } @@ -198,7 +127,8 @@ template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { if (derived()->insertEdge(std::optional<NodeRef>(std::get<0>(Entry)), BB)) { // If the block is not visited... - VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB)); + VisitStack.emplace_back(BB, GraphTraits::child_begin(BB), + GraphTraits::child_end(BB)); } } } @@ -233,7 +163,7 @@ template <typename DerivedT, typename GraphT> class PostOrderTraversalBase { template <typename GraphT, typename SetType = po_detail::DefaultSet<GraphT>> class PostOrderTraversal : public PostOrderTraversalBase<PostOrderTraversal<GraphT, SetType>, - GraphT> { + GraphTraits<GraphT>> { using NodeRef = typename GraphTraits<GraphT>::NodeRef; SetType Visited; @@ -241,10 +171,6 @@ class PostOrderTraversal public: PostOrderTraversal(const GraphT &G) { this->init(GraphTraits<GraphT>::getEntryNode(G)); -#if 0 - if constexpr (GraphHasNodeNumbers<GraphT>) - Visited.reserve(GraphTraits<GraphT>::getMaxNumber(G)); -#endif } PostOrderTraversal(const GraphT &G, SetType &S) : Visited(S) { @@ -256,101 +182,6 @@ class PostOrderTraversal } }; -template <class GraphT, class SetType = po_detail::DefaultSet<GraphT>, - bool ExtStorage = false, class GT = GraphTraits<GraphT>> -class po_iterator : public po_iterator_storage<SetType, ExtStorage> { -public: - // When External storage is used we are not multi-pass safe. - using iterator_category = - std::conditional_t<ExtStorage, std::input_iterator_tag, - std::forward_iterator_tag>; - using value_type = typename GT::NodeRef; - using difference_type = std::ptrdiff_t; - using pointer = value_type *; - using reference = const value_type &; - -private: - using NodeRef = typename GT::NodeRef; - using ChildItTy = typename GT::ChildIteratorType; - - /// Used to maintain the ordering. - /// First element is basic block pointer, second is iterator for the next - /// child to visit, third is the end iterator. - SmallVector<std::tuple<NodeRef, ChildItTy, ChildItTy>, 8> VisitStack; - - po_iterator(NodeRef BB) { - this->insertEdge(std::optional<NodeRef>(), BB); - VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB)); - traverseChild(); - } - - po_iterator() = default; // End is when stack is empty. - - po_iterator(NodeRef BB, SetType &S) - : po_iterator_storage<SetType, ExtStorage>(S) { - if (this->insertEdge(std::optional<NodeRef>(), BB)) { - VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB)); - traverseChild(); - } - } - - po_iterator(SetType &S) - : po_iterator_storage<SetType, ExtStorage>(S) { - } // End is when stack is empty. - - void traverseChild() { - while (true) { - auto &Entry = VisitStack.back(); - if (std::get<1>(Entry) == std::get<2>(Entry)) - break; - NodeRef BB = *std::get<1>(Entry)++; - if (this->insertEdge(std::optional<NodeRef>(std::get<0>(Entry)), BB)) { - // If the block is not visited... - VisitStack.emplace_back(BB, GT::child_begin(BB), GT::child_end(BB)); - } - } - } - -public: - // Provide static "constructors"... - static po_iterator begin(const GraphT &G) { - return po_iterator(GT::getEntryNode(G)); - } - static po_iterator end(const GraphT &G) { return po_iterator(); } - - static po_iterator begin(const GraphT &G, SetType &S) { - return po_iterator(GT::getEntryNode(G), S); - } - static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); } - - bool operator==(const po_iterator &x) const { - return VisitStack == x.VisitStack; - } - bool operator!=(const po_iterator &x) const { return !(*this == x); } - - reference operator*() const { return std::get<0>(VisitStack.back()); } - - // This is a nonstandard operator-> that dereferences the pointer an extra - // time... so that you can actually call methods ON the BasicBlock, because - // the contained type is a pointer. This allows BBIt->getTerminator() f.e. - // - NodeRef operator->() const { return **this; } - - po_iterator &operator++() { // Preincrement - this->finishPostorder(std::get<0>(VisitStack.back())); - VisitStack.pop_back(); - if (!VisitStack.empty()) - traverseChild(); - return *this; - } - - po_iterator operator++(int) { // Postincrement - po_iterator tmp = *this; - ++*this; - return tmp; - } -}; - // Provide global constructors that automatically figure out correct types... // template <class T> auto post_order(const T &G) { diff --git a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h index 7cc40084b9247..cc2404a0249e7 100644 --- a/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h +++ b/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h @@ -1106,8 +1106,9 @@ void BlockFrequencyInfoImpl<BT>::setBlockFreq(const BlockT *BB, } template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() { + const BlockT *Entry = &F->front(); RPOT.reserve(F->size()); - for (const BlockT *BB : post_order(F)) + for (const BlockT *BB : post_order(Entry)) RPOT.emplace_back(BB); std::reverse(RPOT.begin(), RPOT.end()); diff --git a/llvm/include/llvm/Analysis/LoopIterator.h b/llvm/include/llvm/Analysis/LoopIterator.h index b359812d396cd..1205545fe863f 100644 --- a/llvm/include/llvm/Analysis/LoopIterator.h +++ b/llvm/include/llvm/Analysis/LoopIterator.h @@ -188,7 +188,8 @@ class LoopBlocksRPO { /// Traverse the blocks in a loop using a depth-first search. class LoopBlocksTraversal - : public PostOrderTraversalBase<LoopBlocksTraversal, Function *> { + : public PostOrderTraversalBase<LoopBlocksTraversal, + GraphTraits<Function *>> { LoopBlocksDFS &DFS; const LoopInfo *LI; diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index fdb539d91313c..490bfbc0fb7ca 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -1263,7 +1263,7 @@ void BPIConstruction::calculate(const Function &F, const LoopInfo &LoopI, // Walk the basic blocks in post-order so that we can build up state about // the successors of a block iteratively. - for (const auto *BB : post_order(&F)) { + for (const auto *BB : post_order(&F.getEntryBlock())) { LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() << "\n"); // If there is no at least two successors, no sense to set probability. diff --git a/llvm/lib/Analysis/CFGPrinter.cpp b/llvm/lib/Analysis/CFGPrinter.cpp index 18776bc539b32..39108a906f081 100644 --- a/llvm/lib/Analysis/CFGPrinter.cpp +++ b/llvm/lib/Analysis/CFGPrinter.cpp @@ -206,7 +206,7 @@ void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths( }; /// The post order traversal iteration is done to know the status of /// isOnDeoptOrUnreachablePath for all the successors on the current BB. - llvm::for_each(post_order(F), evaluateBB); + llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB); } bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node, diff --git a/llvm/lib/CodeGen/MachineTraceMetrics.cpp b/llvm/lib/CodeGen/MachineTraceMetrics.cpp index 9b7bf6ea3cc82..3525ed7e7d657 100644 --- a/llvm/lib/CodeGen/MachineTraceMetrics.cpp +++ b/llvm/lib/CodeGen/MachineTraceMetrics.cpp @@ -487,7 +487,7 @@ struct LoopBounds { template <typename GraphT> class LoopBoundsPostOrderTraversal : public PostOrderTraversalBase<LoopBoundsPostOrderTraversal<GraphT>, - GraphT> { + GraphTraits<GraphT>> { LoopBounds &LB; public: diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index bc26d74ba3e67..f2ccf198c4c81 100644 --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -25250,7 +25250,7 @@ bool SLPVectorizerPass::runImpl(Function &F, ScalarEvolution *SE_, DT->updateDFSNumbers(); // Scan the blocks in the function in post order. - for (auto *BB : post_order(&F)) { + for (auto *BB : post_order(&F.getEntryBlock())) { if (BB->isEHPad() || isa_and_nonnull<UnreachableInst>(BB->getTerminator())) continue; diff --git a/mlir/include/mlir/IR/Iterators.h b/mlir/include/mlir/IR/Iterators.h index 4754d3beb2c6e..311861a4e1fa5 100644 --- a/mlir/include/mlir/IR/Iterators.h +++ b/mlir/include/mlir/IR/Iterators.h @@ -100,26 +100,37 @@ struct ReverseDominanceIterator { static constexpr auto makeIterable(Operation &range) { return llvm::reverse(ForwardIterator::makeIterable(range)); } -#if 0 + static auto makeIterable(Region ®ion) { - Block *null = nullptr; - llvm::PostOrderTraversal<Block *>::iterator sentinel; - if (SkipGraphRegion && !mayHaveSSADominance(region)) { - // Skip graph regions. - return llvm::make_pointee_range( - llvm::make_range(llvm::po_end(null), llvm::po_end(null))); - } + struct Traversal + : llvm::PostOrderTraversalBase<Traversal, llvm::GraphTraits<Block *>> { + SmallPtrSet<Block *, 16> Visited; + + Traversal(Region *region) { + if (region) + this->init(®ion->front()); + } + bool insertEdge(std::optional<Block *>, Block *To) { + return Visited.insert(To).second; + } + + using BaseT = + typename llvm::PostOrderTraversalBase<Traversal, + llvm::GraphTraits<Block *>>; + // Walk API expects Block references instead of pointers. + using iterator = llvm::pointee_iterator<typename BaseT::iterator>; + iterator begin() { return iterator(BaseT::begin()); } + iterator end() { return iterator(BaseT::end()); } + }; + + // Skip graph regions. + if ((SkipGraphRegion && !mayHaveSSADominance(region)) || region.empty()) + return Traversal(nullptr); // Create post-order iterator. Blocks are enumerated according to their // successor relationship. - auto it = region.empty() - ? llvm::make_range(llvm::po_end(null), llvm::po_end(null)) - : llvm::post_order(®ion.front()); - - // Walk API expects Block references instead of pointers. - return llvm::make_pointee_range(it); + return Traversal(®ion); } -#endif }; } // namespace mlir _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
