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 /// Helper to dereference successor/predecessor \p EdgeIdx of \p Block.
95 static BlockPtrTy deref(BlockPtrTy Block, unsigned EdgeIdx) {
96 if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
97 assert(EdgeIdx == 0);
98 if constexpr (Forward)
99 return R->getEntry();
100 else
101 return R->getExiting();
102 }
103
104 // For exit blocks, use the next parent region with successors.
105 return getOutgoingEdges(Current: getBlockWithOutgoingEdges(Current: Block))[EdgeIdx];
106 }
107
108public:
109 /// Used by iterator_facade_base with bidirectional_iterator_tag.
110 using reference = BlockPtrTy;
111
112 VPHierarchicalChildrenIterator(BlockPtrTy Block, size_t Idx = 0)
113 : Block(Block), EdgeIdx(Idx) {}
114
115 static VPHierarchicalChildrenIterator end(BlockPtrTy Block) {
116 if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
117 // Traverse through the region's entry/exiting (based on Forward) node.
118 return {R, 1};
119 }
120 BlockPtrTy ParentWithOutgoingEdges = getBlockWithOutgoingEdges(Current: Block);
121 unsigned NumOutgoingEdges =
122 ParentWithOutgoingEdges ? getNumOutgoingEdges(Current: ParentWithOutgoingEdges)
123 : 0;
124 return {Block, NumOutgoingEdges};
125 }
126
127 bool operator==(const VPHierarchicalChildrenIterator &R) const {
128 return Block == R.Block && EdgeIdx == R.EdgeIdx;
129 }
130
131 BlockPtrTy operator*() const { return deref(Block, EdgeIdx); }
132
133 VPHierarchicalChildrenIterator &operator++() {
134 EdgeIdx++;
135 return *this;
136 }
137
138 VPHierarchicalChildrenIterator &operator--() {
139 EdgeIdx--;
140 return *this;
141 }
142
143 VPHierarchicalChildrenIterator operator++(int X) {
144 VPHierarchicalChildrenIterator Orig = *this;
145 EdgeIdx++;
146 return Orig;
147 }
148};
149
150/// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
151template <typename BlockTy> class VPBlockDeepTraversalWrapper {
152 BlockTy Entry;
153
154public:
155 VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
156 BlockTy getEntry() { return Entry; }
157};
158
159/// GraphTraits specialization to recursively traverse VPBlockBase nodes,
160/// including traversing through VPRegionBlocks. Exit blocks of a region
161/// implicitly have their parent region's successors. This ensures all blocks in
162/// a region are visited before any blocks in a successor region when doing a
163/// reverse post-order traversal of the graph.
164template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> {
165 using NodeRef = VPBlockBase *;
166 using ChildIteratorType = VPHierarchicalChildrenIterator<VPBlockBase *>;
167
168 static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) {
169 return N.getEntry();
170 }
171
172 static inline ChildIteratorType child_begin(NodeRef N) {
173 return ChildIteratorType(N);
174 }
175
176 static inline ChildIteratorType child_end(NodeRef N) {
177 return ChildIteratorType::end(Block: N);
178 }
179};
180
181template <>
182struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
183 using NodeRef = const VPBlockBase *;
184 using ChildIteratorType = VPHierarchicalChildrenIterator<const VPBlockBase *>;
185
186 static NodeRef
187 getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) {
188 return N.getEntry();
189 }
190
191 static inline ChildIteratorType child_begin(NodeRef N) {
192 return ChildIteratorType(N);
193 }
194
195 static inline ChildIteratorType child_end(NodeRef N) {
196 return ChildIteratorType::end(Block: N);
197 }
198};
199
200/// Helper for GraphTraits specialization that does not traverses through
201/// VPRegionBlocks.
202template <typename BlockTy> class VPBlockShallowTraversalWrapper {
203 BlockTy Entry;
204
205public:
206 VPBlockShallowTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
207 BlockTy getEntry() { return Entry; }
208};
209
210template <> struct GraphTraits<VPBlockShallowTraversalWrapper<VPBlockBase *>> {
211 using NodeRef = VPBlockBase *;
212 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
213
214 static NodeRef getEntryNode(VPBlockShallowTraversalWrapper<VPBlockBase *> N) {
215 return N.getEntry();
216 }
217
218 static inline ChildIteratorType child_begin(NodeRef N) {
219 return N->getSuccessors().begin();
220 }
221
222 static inline ChildIteratorType child_end(NodeRef N) {
223 return N->getSuccessors().end();
224 }
225};
226
227template <>
228struct GraphTraits<VPBlockShallowTraversalWrapper<const VPBlockBase *>> {
229 using NodeRef = const VPBlockBase *;
230 using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
231
232 static NodeRef
233 getEntryNode(VPBlockShallowTraversalWrapper<const VPBlockBase *> N) {
234 return N.getEntry();
235 }
236
237 static inline ChildIteratorType child_begin(NodeRef N) {
238 return N->getSuccessors().begin();
239 }
240
241 static inline ChildIteratorType child_end(NodeRef N) {
242 return N->getSuccessors().end();
243 }
244};
245
246/// Returns an iterator range to traverse the graph starting at \p G in
247/// depth-first order. The iterator won't traverse through region blocks.
248inline iterator_range<
249 df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
250vp_depth_first_shallow(VPBlockBase *G) {
251 return depth_first(G: VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
252}
253inline iterator_range<
254 df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
255vp_depth_first_shallow(const VPBlockBase *G) {
256 return depth_first(G: VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
257}
258
259/// Returns the VPBasicBlocks forming the loop body of a plain (pre-region)
260/// VPlan in reverse post-order starting from \p Header.
261inline SmallVector<VPBasicBlock *>
262vp_rpo_plain_cfg_loop_body(VPBasicBlock *Header) {
263 assert(!Header->getParent() && "Header must not be inside a region");
264 VPBlockBase *Middle = Header->getPredecessors()[1]->getSuccessors()[0];
265 SmallVector<VPBasicBlock *> Result;
266 ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT(
267 Header);
268 for (VPBasicBlock *VPBB : VPBlockUtils::blocksAs<VPBasicBlock>(Range&: RPOT)) {
269 if (VPBB == Middle)
270 break;
271 // Skip exit blocks.
272 if (isa<VPIRBasicBlock>(Val: VPBB)) {
273 assert(is_contained(Header->getPlan()->getExitBlocks(), VPBB) &&
274 "skipped VPIRBBs must be exit blocks");
275 continue;
276 }
277 Result.push_back(Elt: VPBB);
278 }
279 return Result;
280}
281
282/// Returns an iterator range to traverse the graph starting at \p G in
283/// depth-first order while traversing through region blocks.
284inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
285vp_depth_first_deep(VPBlockBase *G) {
286 return depth_first(G: VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
287}
288inline iterator_range<
289 df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
290vp_depth_first_deep(const VPBlockBase *G) {
291 return depth_first(G: VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
292}
293
294// The following set of template specializations implement GraphTraits to treat
295// any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
296// that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
297// VPBlockBase is a VPRegionBlock, this specialization provides access to its
298// successors/predecessors but not to the blocks inside the region.
299
300template <> struct GraphTraits<VPBlockBase *> {
301 using NodeRef = VPBlockBase *;
302 using ChildIteratorType = VPHierarchicalChildrenIterator<VPBlockBase *>;
303
304 static NodeRef getEntryNode(NodeRef N) { return N; }
305
306 static inline ChildIteratorType child_begin(NodeRef N) {
307 return ChildIteratorType(N);
308 }
309
310 static inline ChildIteratorType child_end(NodeRef N) {
311 return ChildIteratorType::end(Block: N);
312 }
313};
314
315template <> struct GraphTraits<const VPBlockBase *> {
316 using NodeRef = const VPBlockBase *;
317 using ChildIteratorType = VPHierarchicalChildrenIterator<const VPBlockBase *>;
318
319 static NodeRef getEntryNode(NodeRef N) { return N; }
320
321 static inline ChildIteratorType child_begin(NodeRef N) {
322 return ChildIteratorType(N);
323 }
324
325 static inline ChildIteratorType child_end(NodeRef N) {
326 return ChildIteratorType::end(Block: N);
327 }
328};
329
330template <> struct GraphTraits<Inverse<VPBlockBase *>> {
331 using NodeRef = VPBlockBase *;
332 using ChildIteratorType =
333 VPHierarchicalChildrenIterator<VPBlockBase *, /*Forward=*/false>;
334
335 static NodeRef getEntryNode(Inverse<NodeRef> B) { return B.Graph; }
336
337 static inline ChildIteratorType child_begin(NodeRef N) {
338 return ChildIteratorType(N);
339 }
340
341 static inline ChildIteratorType child_end(NodeRef N) {
342 return ChildIteratorType::end(Block: N);
343 }
344};
345
346template <> struct GraphTraits<VPlan *> {
347 using GraphRef = VPlan *;
348 using NodeRef = VPBlockBase *;
349 using nodes_iterator = df_iterator<NodeRef>;
350
351 static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
352
353 static nodes_iterator nodes_begin(GraphRef N) {
354 return nodes_iterator::begin(G: N->getEntry());
355 }
356
357 static nodes_iterator nodes_end(GraphRef N) {
358 // df_iterator::end() returns an empty iterator so the node used doesn't
359 // matter.
360 return nodes_iterator::end(G: N->getEntry());
361 }
362};
363
364} // namespace llvm
365
366#endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
367