1bdd1243dSDimitry Andric //===- VPlanCFG.h - GraphTraits for VP blocks -------------------*- C++ -*-===// 2bdd1243dSDimitry Andric // 3bdd1243dSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4bdd1243dSDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5bdd1243dSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6bdd1243dSDimitry Andric // 7bdd1243dSDimitry Andric //===----------------------------------------------------------------------===// 8bdd1243dSDimitry Andric /// Specializations of GraphTraits that allow VPBlockBase graphs to be 9bdd1243dSDimitry Andric /// treated as proper graphs for generic algorithms; 10bdd1243dSDimitry Andric //===----------------------------------------------------------------------===// 11bdd1243dSDimitry Andric 12bdd1243dSDimitry Andric #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H 13bdd1243dSDimitry Andric #define LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H 14bdd1243dSDimitry Andric 15bdd1243dSDimitry Andric #include "VPlan.h" 16*06c3fb27SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h" 17bdd1243dSDimitry Andric #include "llvm/ADT/GraphTraits.h" 18bdd1243dSDimitry Andric #include "llvm/ADT/SmallVector.h" 19bdd1243dSDimitry Andric 20bdd1243dSDimitry Andric namespace llvm { 21bdd1243dSDimitry Andric 22bdd1243dSDimitry Andric //===----------------------------------------------------------------------===// 23bdd1243dSDimitry Andric // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs // 24bdd1243dSDimitry Andric //===----------------------------------------------------------------------===// 25bdd1243dSDimitry Andric 26bdd1243dSDimitry Andric /// Iterator to traverse all successors of a VPBlockBase node. This includes the 27bdd1243dSDimitry Andric /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their 28bdd1243dSDimitry Andric /// parent region's successors. This ensures all blocks in a region are visited 29bdd1243dSDimitry Andric /// before any blocks in a successor region when doing a reverse post-order 30bdd1243dSDimitry Andric // traversal of the graph. Region blocks themselves traverse only their entries 31bdd1243dSDimitry Andric // directly and not their successors. Those will be traversed when a region's 32bdd1243dSDimitry Andric // exiting block is traversed 33bdd1243dSDimitry Andric template <typename BlockPtrTy> 34bdd1243dSDimitry Andric class VPAllSuccessorsIterator 35bdd1243dSDimitry Andric : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>, 36bdd1243dSDimitry Andric std::bidirectional_iterator_tag, 37bdd1243dSDimitry Andric VPBlockBase> { 38bdd1243dSDimitry Andric BlockPtrTy Block; 39bdd1243dSDimitry Andric /// Index of the current successor. For VPBasicBlock nodes, this simply is the 40bdd1243dSDimitry Andric /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is 41bdd1243dSDimitry Andric /// used for the region's entry block, and SuccessorIdx - 1 are the indices 42bdd1243dSDimitry Andric /// for the successor array. 43bdd1243dSDimitry Andric size_t SuccessorIdx; 44bdd1243dSDimitry Andric getBlockWithSuccs(BlockPtrTy Current)45bdd1243dSDimitry Andric static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) { 46bdd1243dSDimitry Andric while (Current && Current->getNumSuccessors() == 0) 47bdd1243dSDimitry Andric Current = Current->getParent(); 48bdd1243dSDimitry Andric return Current; 49bdd1243dSDimitry Andric } 50bdd1243dSDimitry Andric 51bdd1243dSDimitry Andric /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by 52bdd1243dSDimitry Andric /// both the const and non-const operator* implementations. deref(T1 Block,unsigned SuccIdx)53bdd1243dSDimitry Andric template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) { 54bdd1243dSDimitry Andric if (auto *R = dyn_cast<VPRegionBlock>(Block)) { 55bdd1243dSDimitry Andric assert(SuccIdx == 0); 56bdd1243dSDimitry Andric return R->getEntry(); 57bdd1243dSDimitry Andric } 58bdd1243dSDimitry Andric 59bdd1243dSDimitry Andric // For exit blocks, use the next parent region with successors. 60bdd1243dSDimitry Andric return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx]; 61bdd1243dSDimitry Andric } 62bdd1243dSDimitry Andric 63bdd1243dSDimitry Andric public: 64bdd1243dSDimitry Andric /// Used by iterator_facade_base with bidirectional_iterator_tag. 65bdd1243dSDimitry Andric using reference = BlockPtrTy; 66bdd1243dSDimitry Andric 67bdd1243dSDimitry Andric VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0) Block(Block)68bdd1243dSDimitry Andric : Block(Block), SuccessorIdx(Idx) {} VPAllSuccessorsIterator(const VPAllSuccessorsIterator & Other)69bdd1243dSDimitry Andric VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other) 70bdd1243dSDimitry Andric : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {} 71bdd1243dSDimitry Andric 72bdd1243dSDimitry Andric VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) { 73bdd1243dSDimitry Andric Block = R.Block; 74bdd1243dSDimitry Andric SuccessorIdx = R.SuccessorIdx; 75bdd1243dSDimitry Andric return *this; 76bdd1243dSDimitry Andric } 77bdd1243dSDimitry Andric end(BlockPtrTy Block)78bdd1243dSDimitry Andric static VPAllSuccessorsIterator end(BlockPtrTy Block) { 79bdd1243dSDimitry Andric if (auto *R = dyn_cast<VPRegionBlock>(Block)) { 80bdd1243dSDimitry Andric // Traverse through the region's entry node. 81bdd1243dSDimitry Andric return {R, 1}; 82bdd1243dSDimitry Andric } 83bdd1243dSDimitry Andric BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block); 84bdd1243dSDimitry Andric unsigned NumSuccessors = 85bdd1243dSDimitry Andric ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0; 86bdd1243dSDimitry Andric return {Block, NumSuccessors}; 87bdd1243dSDimitry Andric } 88bdd1243dSDimitry Andric 89bdd1243dSDimitry Andric bool operator==(const VPAllSuccessorsIterator &R) const { 90bdd1243dSDimitry Andric return Block == R.Block && SuccessorIdx == R.SuccessorIdx; 91bdd1243dSDimitry Andric } 92bdd1243dSDimitry Andric 93bdd1243dSDimitry Andric const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); } 94bdd1243dSDimitry Andric 95bdd1243dSDimitry Andric BlockPtrTy operator*() { return deref(Block, SuccessorIdx); } 96bdd1243dSDimitry Andric 97bdd1243dSDimitry Andric VPAllSuccessorsIterator &operator++() { 98bdd1243dSDimitry Andric SuccessorIdx++; 99bdd1243dSDimitry Andric return *this; 100bdd1243dSDimitry Andric } 101bdd1243dSDimitry Andric 102bdd1243dSDimitry Andric VPAllSuccessorsIterator &operator--() { 103bdd1243dSDimitry Andric SuccessorIdx--; 104bdd1243dSDimitry Andric return *this; 105bdd1243dSDimitry Andric } 106bdd1243dSDimitry Andric 107bdd1243dSDimitry Andric VPAllSuccessorsIterator operator++(int X) { 108bdd1243dSDimitry Andric VPAllSuccessorsIterator Orig = *this; 109bdd1243dSDimitry Andric SuccessorIdx++; 110bdd1243dSDimitry Andric return Orig; 111bdd1243dSDimitry Andric } 112bdd1243dSDimitry Andric }; 113bdd1243dSDimitry Andric 114bdd1243dSDimitry Andric /// Helper for GraphTraits specialization that traverses through VPRegionBlocks. 115bdd1243dSDimitry Andric template <typename BlockTy> class VPBlockDeepTraversalWrapper { 116bdd1243dSDimitry Andric BlockTy Entry; 117bdd1243dSDimitry Andric 118bdd1243dSDimitry Andric public: VPBlockDeepTraversalWrapper(BlockTy Entry)119bdd1243dSDimitry Andric VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {} getEntry()120bdd1243dSDimitry Andric BlockTy getEntry() { return Entry; } 121bdd1243dSDimitry Andric }; 122bdd1243dSDimitry Andric 123bdd1243dSDimitry Andric /// GraphTraits specialization to recursively traverse VPBlockBase nodes, 124bdd1243dSDimitry Andric /// including traversing through VPRegionBlocks. Exit blocks of a region 125bdd1243dSDimitry Andric /// implicitly have their parent region's successors. This ensures all blocks in 126bdd1243dSDimitry Andric /// a region are visited before any blocks in a successor region when doing a 127bdd1243dSDimitry Andric /// reverse post-order traversal of the graph. 128bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> { 129bdd1243dSDimitry Andric using NodeRef = VPBlockBase *; 130bdd1243dSDimitry Andric using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>; 131bdd1243dSDimitry Andric 132bdd1243dSDimitry Andric static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) { 133bdd1243dSDimitry Andric return N.getEntry(); 134bdd1243dSDimitry Andric } 135bdd1243dSDimitry Andric 136bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 137bdd1243dSDimitry Andric return ChildIteratorType(N); 138bdd1243dSDimitry Andric } 139bdd1243dSDimitry Andric 140bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 141bdd1243dSDimitry Andric return ChildIteratorType::end(N); 142bdd1243dSDimitry Andric } 143bdd1243dSDimitry Andric }; 144bdd1243dSDimitry Andric 145bdd1243dSDimitry Andric template <> 146bdd1243dSDimitry Andric struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> { 147bdd1243dSDimitry Andric using NodeRef = const VPBlockBase *; 148bdd1243dSDimitry Andric using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>; 149bdd1243dSDimitry Andric 150bdd1243dSDimitry Andric static NodeRef 151bdd1243dSDimitry Andric getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) { 152bdd1243dSDimitry Andric return N.getEntry(); 153bdd1243dSDimitry Andric } 154bdd1243dSDimitry Andric 155bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 156bdd1243dSDimitry Andric return ChildIteratorType(N); 157bdd1243dSDimitry Andric } 158bdd1243dSDimitry Andric 159bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 160bdd1243dSDimitry Andric return ChildIteratorType::end(N); 161bdd1243dSDimitry Andric } 162bdd1243dSDimitry Andric }; 163bdd1243dSDimitry Andric 164bdd1243dSDimitry Andric /// Helper for GraphTraits specialization that does not traverses through 165bdd1243dSDimitry Andric /// VPRegionBlocks. 166bdd1243dSDimitry Andric template <typename BlockTy> class VPBlockShallowTraversalWrapper { 167bdd1243dSDimitry Andric BlockTy Entry; 168bdd1243dSDimitry Andric 169bdd1243dSDimitry Andric public: 170bdd1243dSDimitry Andric VPBlockShallowTraversalWrapper(BlockTy Entry) : Entry(Entry) {} 171bdd1243dSDimitry Andric BlockTy getEntry() { return Entry; } 172bdd1243dSDimitry Andric }; 173bdd1243dSDimitry Andric 174bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockShallowTraversalWrapper<VPBlockBase *>> { 175bdd1243dSDimitry Andric using NodeRef = VPBlockBase *; 176bdd1243dSDimitry Andric using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; 177bdd1243dSDimitry Andric 178bdd1243dSDimitry Andric static NodeRef getEntryNode(VPBlockShallowTraversalWrapper<VPBlockBase *> N) { 179bdd1243dSDimitry Andric return N.getEntry(); 180bdd1243dSDimitry Andric } 181bdd1243dSDimitry Andric 182bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 183bdd1243dSDimitry Andric return N->getSuccessors().begin(); 184bdd1243dSDimitry Andric } 185bdd1243dSDimitry Andric 186bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 187bdd1243dSDimitry Andric return N->getSuccessors().end(); 188bdd1243dSDimitry Andric } 189bdd1243dSDimitry Andric }; 190bdd1243dSDimitry Andric 191bdd1243dSDimitry Andric template <> 192bdd1243dSDimitry Andric struct GraphTraits<VPBlockShallowTraversalWrapper<const VPBlockBase *>> { 193bdd1243dSDimitry Andric using NodeRef = const VPBlockBase *; 194bdd1243dSDimitry Andric using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator; 195bdd1243dSDimitry Andric 196bdd1243dSDimitry Andric static NodeRef 197bdd1243dSDimitry Andric getEntryNode(VPBlockShallowTraversalWrapper<const VPBlockBase *> N) { 198bdd1243dSDimitry Andric return N.getEntry(); 199bdd1243dSDimitry Andric } 200bdd1243dSDimitry Andric 201bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 202bdd1243dSDimitry Andric return N->getSuccessors().begin(); 203bdd1243dSDimitry Andric } 204bdd1243dSDimitry Andric 205bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 206bdd1243dSDimitry Andric return N->getSuccessors().end(); 207bdd1243dSDimitry Andric } 208bdd1243dSDimitry Andric }; 209bdd1243dSDimitry Andric 210bdd1243dSDimitry Andric /// Returns an iterator range to traverse the graph starting at \p G in 211bdd1243dSDimitry Andric /// depth-first order. The iterator won't traverse through region blocks. 212bdd1243dSDimitry Andric inline iterator_range< 213bdd1243dSDimitry Andric df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>> 214bdd1243dSDimitry Andric vp_depth_first_shallow(VPBlockBase *G) { 215bdd1243dSDimitry Andric return depth_first(VPBlockShallowTraversalWrapper<VPBlockBase *>(G)); 216bdd1243dSDimitry Andric } 217bdd1243dSDimitry Andric inline iterator_range< 218bdd1243dSDimitry Andric df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>> 219bdd1243dSDimitry Andric vp_depth_first_shallow(const VPBlockBase *G) { 220bdd1243dSDimitry Andric return depth_first(VPBlockShallowTraversalWrapper<const VPBlockBase *>(G)); 221bdd1243dSDimitry Andric } 222bdd1243dSDimitry Andric 223bdd1243dSDimitry Andric /// Returns an iterator range to traverse the graph starting at \p G in 224bdd1243dSDimitry Andric /// depth-first order while traversing through region blocks. 225bdd1243dSDimitry Andric inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>> 226bdd1243dSDimitry Andric vp_depth_first_deep(VPBlockBase *G) { 227bdd1243dSDimitry Andric return depth_first(VPBlockDeepTraversalWrapper<VPBlockBase *>(G)); 228bdd1243dSDimitry Andric } 229bdd1243dSDimitry Andric inline iterator_range< 230bdd1243dSDimitry Andric df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>> 231bdd1243dSDimitry Andric vp_depth_first_deep(const VPBlockBase *G) { 232bdd1243dSDimitry Andric return depth_first(VPBlockDeepTraversalWrapper<const VPBlockBase *>(G)); 233bdd1243dSDimitry Andric } 234bdd1243dSDimitry Andric 235bdd1243dSDimitry Andric // The following set of template specializations implement GraphTraits to treat 236bdd1243dSDimitry Andric // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note 237bdd1243dSDimitry Andric // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the 238bdd1243dSDimitry Andric // VPBlockBase is a VPRegionBlock, this specialization provides access to its 239bdd1243dSDimitry Andric // successors/predecessors but not to the blocks inside the region. 240bdd1243dSDimitry Andric 241bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockBase *> { 242bdd1243dSDimitry Andric using NodeRef = VPBlockBase *; 243bdd1243dSDimitry Andric using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>; 244bdd1243dSDimitry Andric 245bdd1243dSDimitry Andric static NodeRef getEntryNode(NodeRef N) { return N; } 246bdd1243dSDimitry Andric 247bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 248bdd1243dSDimitry Andric return ChildIteratorType(N); 249bdd1243dSDimitry Andric } 250bdd1243dSDimitry Andric 251bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 252bdd1243dSDimitry Andric return ChildIteratorType::end(N); 253bdd1243dSDimitry Andric } 254bdd1243dSDimitry Andric }; 255bdd1243dSDimitry Andric 256bdd1243dSDimitry Andric template <> struct GraphTraits<const VPBlockBase *> { 257bdd1243dSDimitry Andric using NodeRef = const VPBlockBase *; 258bdd1243dSDimitry Andric using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>; 259bdd1243dSDimitry Andric 260bdd1243dSDimitry Andric static NodeRef getEntryNode(NodeRef N) { return N; } 261bdd1243dSDimitry Andric 262bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 263bdd1243dSDimitry Andric return ChildIteratorType(N); 264bdd1243dSDimitry Andric } 265bdd1243dSDimitry Andric 266bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 267bdd1243dSDimitry Andric return ChildIteratorType::end(N); 268bdd1243dSDimitry Andric } 269bdd1243dSDimitry Andric }; 270bdd1243dSDimitry Andric 271bdd1243dSDimitry Andric /// Inverse graph traits are not implemented yet. 272bdd1243dSDimitry Andric /// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse 273bdd1243dSDimitry Andric /// predecessors recursively through regions. 274bdd1243dSDimitry Andric template <> struct GraphTraits<Inverse<VPBlockBase *>> { 275bdd1243dSDimitry Andric using NodeRef = VPBlockBase *; 276bdd1243dSDimitry Andric using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator; 277bdd1243dSDimitry Andric 278bdd1243dSDimitry Andric static NodeRef getEntryNode(Inverse<NodeRef> B) { 279bdd1243dSDimitry Andric llvm_unreachable("not implemented"); 280bdd1243dSDimitry Andric } 281bdd1243dSDimitry Andric 282bdd1243dSDimitry Andric static inline ChildIteratorType child_begin(NodeRef N) { 283bdd1243dSDimitry Andric llvm_unreachable("not implemented"); 284bdd1243dSDimitry Andric } 285bdd1243dSDimitry Andric 286bdd1243dSDimitry Andric static inline ChildIteratorType child_end(NodeRef N) { 287bdd1243dSDimitry Andric llvm_unreachable("not implemented"); 288bdd1243dSDimitry Andric } 289bdd1243dSDimitry Andric }; 290bdd1243dSDimitry Andric 291bdd1243dSDimitry Andric template <> struct GraphTraits<VPlan *> { 292bdd1243dSDimitry Andric using GraphRef = VPlan *; 293bdd1243dSDimitry Andric using NodeRef = VPBlockBase *; 294bdd1243dSDimitry Andric using nodes_iterator = df_iterator<NodeRef>; 295bdd1243dSDimitry Andric 296bdd1243dSDimitry Andric static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); } 297bdd1243dSDimitry Andric 298bdd1243dSDimitry Andric static nodes_iterator nodes_begin(GraphRef N) { 299bdd1243dSDimitry Andric return nodes_iterator::begin(N->getEntry()); 300bdd1243dSDimitry Andric } 301bdd1243dSDimitry Andric 302bdd1243dSDimitry Andric static nodes_iterator nodes_end(GraphRef N) { 303bdd1243dSDimitry Andric // df_iterator::end() returns an empty iterator so the node used doesn't 304bdd1243dSDimitry Andric // matter. 305bdd1243dSDimitry Andric return nodes_iterator::end(N->getEntry()); 306bdd1243dSDimitry Andric } 307bdd1243dSDimitry Andric }; 308bdd1243dSDimitry Andric 309bdd1243dSDimitry Andric } // namespace llvm 310bdd1243dSDimitry Andric 311bdd1243dSDimitry Andric #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H 312