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
312