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 "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 the
29/// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
30/// parent region's successors. This ensures all blocks in a region are visited
31/// before any blocks in a successor region when doing a reverse post-order
32// traversal of the graph. Region blocks themselves traverse only their entries
33// directly and not their successors. Those will be traversed when a region's
34// exiting block is traversed
35template <typename BlockPtrTy>
36class VPAllSuccessorsIterator
37 : 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 the
42 /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
43 /// used for the region's entry block, and SuccessorIdx - 1 are the indices
44 /// 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 by
54 /// 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(Current: 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(Current: 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 region
127/// implicitly have their parent region's successors. This ensures all blocks in
128/// a region are visited before any blocks in a successor region when doing a
129/// 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(Block: N);
144 }
145};
146
147template <>
148struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
149 using NodeRef = const VPBlockBase *;
150 using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
151
152 static NodeRef
153 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(Block: N);
163 }
164};
165
166/// Helper for GraphTraits specialization that does not traverses through
167/// 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 NodeRef
199 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 in
213/// 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(G: VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
218}
219inline iterator_range<
220 df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
221vp_depth_first_shallow(const VPBlockBase *G) {
222 return depth_first(G: VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
223}
224
225/// Returns an iterator range to traverse the graph starting at \p G in
226/// 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(G: VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
231}
232
233/// Returns an iterator range to traverse the graph starting at \p G in
234/// post order while traversing through region blocks.
235inline iterator_range<po_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
236vp_post_order_deep(VPBlockBase *G) {
237 return post_order(G: VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
238}
239
240/// Returns an iterator range to traverse the graph starting at \p G in
241/// 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(G: VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
245}
246inline iterator_range<
247 df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
248vp_depth_first_deep(const VPBlockBase *G) {
249 return depth_first(G: VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
250}
251
252// The following set of template specializations implement GraphTraits to treat
253// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
254// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
255// VPBlockBase is a VPRegionBlock, this specialization provides access to its
256// 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(Block: 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(Block: N);
285 }
286};
287
288/// Inverse graph traits are not implemented yet.
289/// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse
290/// 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(G: 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't
321 // matter.
322 return nodes_iterator::end(G: N->getEntry());
323 }
324};
325
326} // namespace llvm
327
328#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
329