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/predecessors of a VPBlockBase node,
29/// including its hierarchical successors/predecessors:
30///
31/// A
32/// |
33/// +-----+ <- Region R
34/// | b |
35/// | |
36/// | ... |
37/// | |
38/// | e |
39/// +-----+
40/// |
41/// B
42///
43/// Forward == true:
44/// Region blocks themselves traverse only their entries directly.
45/// Region's successor is implictly traversed when processing its exiting
46/// block.
47/// children(A) == {R}
48/// children(R) == {b}
49/// children(e) == {B}
50///
51/// Forward == false:
52/// Region blocks themselves traverse only their exiting blocks directly.
53/// Region's predecessor is implicitly traversed when processing its entry
54/// block.
55/// children(B) == {R}
56/// children(R) == {e}
57/// children(b) == {A}
58///
59/// The scheme described above ensures that all blocks of the region are visited
60/// before continuing traversal outside the region when doing a reverse
61/// post-order traversal of the VPlan.
62template <typename BlockPtrTy, bool Forward = true>
63class VPHierarchicalChildrenIterator
64 : public iterator_facade_base<
65 VPHierarchicalChildrenIterator<BlockPtrTy, Forward>,
66 std::bidirectional_iterator_tag, VPBlockBase> {
67 BlockPtrTy Block;
68 /// Index of the current successor/predecessor. For VPBasicBlock nodes, this
69 /// simply is the index for the successors/predecessors array. For
70 /// VPRegionBlock, EdgeIdx == 0 is used for the region's entry/exiting block,
71 /// and EdgeIdx - 1 are the indices for the successors/predecessors array.
72 size_t EdgeIdx;
73
74 static size_t getNumOutgoingEdges(BlockPtrTy Current) {
75 if constexpr (Forward)
76 return Current->getNumSuccessors();
77 else
78 return Current->getNumPredecessors();
79 }
80
81 static ArrayRef<BlockPtrTy> getOutgoingEdges(BlockPtrTy Current) {
82 if constexpr (Forward)
83 return Current->getSuccessors();
84 else
85 return Current->getPredecessors();
86 }
87
88 static BlockPtrTy getBlockWithOutgoingEdges(BlockPtrTy Current) {
89 while (Current && getNumOutgoingEdges(Current) == 0)
90 Current = Current->getParent();
91 return Current;
92 }
93
94 /// Templated helper to dereference successor/predecessor \p EdgeIdx of \p
95 /// Block. Used by both the const and non-const operator* implementations.
96 template <typename T1> static T1 deref(T1 Block, unsigned EdgeIdx) {
97 if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
98 assert(EdgeIdx == 0);
99 if constexpr (Forward)
100 return R->getEntry();
101 else
102 return R->getExiting();
103 }
104
105 // For exit blocks, use the next parent region with successors.
106 return getOutgoingEdges(Current: getBlockWithOutgoingEdges(Current: Block))[EdgeIdx];
107 }
108
109public:
110 /// Used by iterator_facade_base with bidirectional_iterator_tag.
111 using reference = BlockPtrTy;
112
113 VPHierarchicalChildrenIterator(BlockPtrTy Block, size_t Idx = 0)
114 : Block(Block), EdgeIdx(Idx) {}
115 VPHierarchicalChildrenIterator(const VPHierarchicalChildrenIterator &Other)
116 : Block(Other.Block), EdgeIdx(Other.EdgeIdx) {}
117
118 VPHierarchicalChildrenIterator &
119 operator=(const VPHierarchicalChildrenIterator &R) {
120 Block = R.Block;
121 EdgeIdx = R.EdgeIdx;
122 return *this;
123 }
124
125 static VPHierarchicalChildrenIterator end(BlockPtrTy Block) {
126 if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
127 // Traverse through the region's entry/exiting (based on Forward) node.
128 return {R, 1};
129 }
130 BlockPtrTy ParentWithOutgoingEdges = getBlockWithOutgoingEdges(Current: Block);
131 unsigned NumOutgoingEdges =
132 ParentWithOutgoingEdges ? getNumOutgoingEdges(Current: ParentWithOutgoingEdges)
133 : 0;
134 return {Block, NumOutgoingEdges};
135 }
136
137 bool operator==(const VPHierarchicalChildrenIterator &R) const {
138 return Block == R.Block && EdgeIdx == R.EdgeIdx;
139 }
140
141 const VPBlockBase *operator*() const { return deref(Block, EdgeIdx); }
142
143 BlockPtrTy operator*() { return deref(Block, EdgeIdx); }
144
145 VPHierarchicalChildrenIterator &operator++() {
146 EdgeIdx++;
147 return *this;
148 }
149
150 VPHierarchicalChildrenIterator &operator--() {
151 EdgeIdx--;
152 return *this;
153 }
154
155 VPHierarchicalChildrenIterator operator++(int X) {
156 VPHierarchicalChildrenIterator Orig = *this;
157 EdgeIdx++;
158 return Orig;
159 }
160};
161
162/// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
163template <typename BlockTy> class VPBlockDeepTraversalWrapper {
164 BlockTy Entry;
165
166public:
167 VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
168 BlockTy getEntry() { return Entry; }
169};
170
171/// GraphTraits specialization to recursively traverse VPBlockBase nodes,
172/// including traversing through VPRegionBlocks. Exit blocks of a region
173/// implicitly have their parent region's successors. This ensures all blocks in
174/// a region are visited before any blocks in a successor region when doing a
175/// reverse post-order traversal of the graph.
176template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> {
177 using NodeRef = VPBlockBase *;
178 using ChildIteratorType = VPHierarchicalChildrenIterator<VPBlockBase *>;
179
180 static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) {
181 return N.getEntry();
182 }
183
184 static inline ChildIteratorType child_begin(NodeRef N) {
185 return ChildIteratorType(N);
186 }
187
188 static inline ChildIteratorType child_end(NodeRef N) {
189 return ChildIteratorType::end(Block: N);
190 }
191};
192
193template <>
194struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
195 using NodeRef = const VPBlockBase *;
196 using ChildIteratorType = VPHierarchicalChildrenIterator<const VPBlockBase *>;
197
198 static NodeRef
199 getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) {
200 return N.getEntry();
201 }
202
203 static inline ChildIteratorType child_begin(NodeRef N) {
204 return ChildIteratorType(N);
205 }
206
207 static inline ChildIteratorType child_end(NodeRef N) {
208 return ChildIteratorType::end(Block: N);
209 }
210};
211
212/// Helper for GraphTraits specialization that does not traverses through
213/// VPRegionBlocks.
214template <typename BlockTy> class VPBlockShallowTraversalWrapper {
215 BlockTy Entry;
216
217public:
218 VPBlockShallowTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
219 BlockTy getEntry() { return Entry; }
220};
221
222template <> struct GraphTraits<VPBlockShallowTraversalWrapper<VPBlockBase *>> {
223 using NodeRef = VPBlockBase *;
224 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
225
226 static NodeRef getEntryNode(VPBlockShallowTraversalWrapper<VPBlockBase *> N) {
227 return N.getEntry();
228 }
229
230 static inline ChildIteratorType child_begin(NodeRef N) {
231 return N->getSuccessors().begin();
232 }
233
234 static inline ChildIteratorType child_end(NodeRef N) {
235 return N->getSuccessors().end();
236 }
237};
238
239template <>
240struct GraphTraits<VPBlockShallowTraversalWrapper<const VPBlockBase *>> {
241 using NodeRef = const VPBlockBase *;
242 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
243
244 static NodeRef
245 getEntryNode(VPBlockShallowTraversalWrapper<const VPBlockBase *> N) {
246 return N.getEntry();
247 }
248
249 static inline ChildIteratorType child_begin(NodeRef N) {
250 return N->getSuccessors().begin();
251 }
252
253 static inline ChildIteratorType child_end(NodeRef N) {
254 return N->getSuccessors().end();
255 }
256};
257
258/// Returns an iterator range to traverse the graph starting at \p G in
259/// depth-first order. The iterator won't traverse through region blocks.
260inline iterator_range<
261 df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
262vp_depth_first_shallow(VPBlockBase *G) {
263 return depth_first(G: VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
264}
265inline iterator_range<
266 df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
267vp_depth_first_shallow(const VPBlockBase *G) {
268 return depth_first(G: VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
269}
270
271/// Returns an iterator range to traverse the graph starting at \p G in
272/// post order. The iterator won't traverse through region blocks.
273inline iterator_range<
274 po_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
275vp_post_order_shallow(VPBlockBase *G) {
276 return post_order(G: VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
277}
278
279/// Returns an iterator range to traverse the graph starting at \p G in
280/// post order while traversing through region blocks.
281inline iterator_range<po_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
282vp_post_order_deep(VPBlockBase *G) {
283 return post_order(G: VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
284}
285
286/// Returns an iterator range to traverse the graph starting at \p G in
287/// depth-first order while traversing through region blocks.
288inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
289vp_depth_first_deep(VPBlockBase *G) {
290 return depth_first(G: VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
291}
292inline iterator_range<
293 df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
294vp_depth_first_deep(const VPBlockBase *G) {
295 return depth_first(G: VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
296}
297
298// The following set of template specializations implement GraphTraits to treat
299// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
300// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
301// VPBlockBase is a VPRegionBlock, this specialization provides access to its
302// successors/predecessors but not to the blocks inside the region.
303
304template <> struct GraphTraits<VPBlockBase *> {
305 using NodeRef = VPBlockBase *;
306 using ChildIteratorType = VPHierarchicalChildrenIterator<VPBlockBase *>;
307
308 static NodeRef getEntryNode(NodeRef N) { return N; }
309
310 static inline ChildIteratorType child_begin(NodeRef N) {
311 return ChildIteratorType(N);
312 }
313
314 static inline ChildIteratorType child_end(NodeRef N) {
315 return ChildIteratorType::end(Block: N);
316 }
317};
318
319template <> struct GraphTraits<const VPBlockBase *> {
320 using NodeRef = const VPBlockBase *;
321 using ChildIteratorType = VPHierarchicalChildrenIterator<const VPBlockBase *>;
322
323 static NodeRef getEntryNode(NodeRef N) { return N; }
324
325 static inline ChildIteratorType child_begin(NodeRef N) {
326 return ChildIteratorType(N);
327 }
328
329 static inline ChildIteratorType child_end(NodeRef N) {
330 return ChildIteratorType::end(Block: N);
331 }
332};
333
334template <> struct GraphTraits<Inverse<VPBlockBase *>> {
335 using NodeRef = VPBlockBase *;
336 using ChildIteratorType =
337 VPHierarchicalChildrenIterator<VPBlockBase *, /*Forward=*/false>;
338
339 static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
340
341 static inline ChildIteratorType child_begin(NodeRef N) {
342 return ChildIteratorType(N);
343 }
344
345 static inline ChildIteratorType child_end(NodeRef N) {
346 return ChildIteratorType::end(Block: N);
347 }
348};
349
350template <> struct GraphTraits<VPlan *> {
351 using GraphRef = VPlan *;
352 using NodeRef = VPBlockBase *;
353 using nodes_iterator = df_iterator<NodeRef>;
354
355 static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
356
357 static nodes_iterator nodes_begin(GraphRef N) {
358 return nodes_iterator::begin(G: N->getEntry());
359 }
360
361 static nodes_iterator nodes_end(GraphRef N) {
362 // df_iterator::end() returns an empty iterator so the node used doesn't
363 // matter.
364 return nodes_iterator::end(G: N->getEntry());
365 }
366};
367
368} // namespace llvm
369
370#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
371