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