llvm/lib/Transforms/Vectorize/VPlanCFG.h

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