LLVM 20.0.0git
VPlanCFG.h
Go to the documentation of this file.
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"
19
20namespace 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
33template <typename BlockPtrTy>
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
63public:
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) {}
70 : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
71
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
98 SuccessorIdx++;
99 return *this;
100 }
101
103 SuccessorIdx--;
104 return *this;
105 }
106
108 VPAllSuccessorsIterator Orig = *this;
109 SuccessorIdx++;
110 return Orig;
111 }
112};
113
114/// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
115template <typename BlockTy> class VPBlockDeepTraversalWrapper {
116 BlockTy Entry;
117
118public:
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.
131
133 return N.getEntry();
134 }
135
137 return ChildIteratorType(N);
138 }
139
141 return ChildIteratorType::end(N);
142 }
143};
144
145template <>
147 using NodeRef = const VPBlockBase *;
149
150 static NodeRef
152 return N.getEntry();
153 }
154
156 return ChildIteratorType(N);
157 }
158
160 return ChildIteratorType::end(N);
161 }
162};
163
164/// Helper for GraphTraits specialization that does not traverses through
165/// VPRegionBlocks.
166template <typename BlockTy> class VPBlockShallowTraversalWrapper {
167 BlockTy Entry;
168
169public:
171 BlockTy getEntry() { return Entry; }
172};
173
177
179 return N.getEntry();
180 }
181
183 return N->getSuccessors().begin();
184 }
185
187 return N->getSuccessors().end();
188 }
189};
190
191template <>
193 using NodeRef = const VPBlockBase *;
195
196 static NodeRef
198 return N.getEntry();
199 }
200
202 return N->getSuccessors().begin();
203 }
204
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.
212inline iterator_range<
213 df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
216}
217inline iterator_range<
218 df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
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.
225inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
228}
229inline iterator_range<
230 df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
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
241template <> struct GraphTraits<VPBlockBase *> {
244
245 static NodeRef getEntryNode(NodeRef N) { return N; }
246
248 return ChildIteratorType(N);
249 }
250
252 return ChildIteratorType::end(N);
253 }
254};
255
256template <> struct GraphTraits<const VPBlockBase *> {
257 using NodeRef = const VPBlockBase *;
259
260 static NodeRef getEntryNode(NodeRef N) { return N; }
261
263 return ChildIteratorType(N);
264 }
265
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.
274template <> struct GraphTraits<Inverse<VPBlockBase *>> {
277
279 llvm_unreachable("not implemented");
280 }
281
283 llvm_unreachable("not implemented");
284 }
285
287 llvm_unreachable("not implemented");
288 }
289};
290
291template <> struct GraphTraits<VPlan *> {
292 using GraphRef = VPlan *;
295
296 static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
297
299 return nodes_iterator::begin(N->getEntry());
300 }
301
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
aarch64 promote const
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
std::pair< BasicBlock *, unsigned > BlockTy
A pair of (basic block, score).
#define G(x, y, z)
Definition: MD5.cpp:56
#define T1
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file contains the declarations of the Vectorization Plan base classes:
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:591
typename SuperClass::iterator iterator
Definition: SmallVector.h:590
Iterator to traverse all successors of a VPBlockBase node.
Definition: VPlanCFG.h:37
const VPBlockBase * operator*() const
Definition: VPlanCFG.h:93
VPAllSuccessorsIterator & operator++()
Definition: VPlanCFG.h:97
bool operator==(const VPAllSuccessorsIterator &R) const
Definition: VPlanCFG.h:89
VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx=0)
Definition: VPlanCFG.h:67
VPAllSuccessorsIterator operator++(int X)
Definition: VPlanCFG.h:107
VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
Definition: VPlanCFG.h:69
VPAllSuccessorsIterator & operator--()
Definition: VPlanCFG.h:102
BlockPtrTy reference
Used by iterator_facade_base with bidirectional_iterator_tag.
Definition: VPlanCFG.h:65
VPAllSuccessorsIterator & operator=(const VPAllSuccessorsIterator &R)
Definition: VPlanCFG.h:72
static VPAllSuccessorsIterator end(BlockPtrTy Block)
Definition: VPlanCFG.h:78
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:437
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlanCFG.h:115
VPBlockDeepTraversalWrapper(BlockTy Entry)
Definition: VPlanCFG.h:119
Helper for GraphTraits specialization that does not traverses through VPRegionBlocks.
Definition: VPlanCFG.h:166
VPBlockShallowTraversalWrapper(BlockTy Entry)
Definition: VPlanCFG.h:170
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:3268
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:80
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< df_iterator< VPBlockShallowTraversalWrapper< VPBlockBase * > > > vp_depth_first_shallow(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order.
Definition: VPlanCFG.h:214
iterator_range< df_iterator< VPBlockDeepTraversalWrapper< VPBlockBase * > > > vp_depth_first_deep(VPBlockBase *G)
Returns an iterator range to traverse the graph starting at G in depth-first order while traversing t...
Definition: VPlanCFG.h:226
@ Other
Any other memory.
iterator_range< df_iterator< T > > depth_first(const T &G)
#define N
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlanCFG.h:276
static NodeRef getEntryNode(Inverse< NodeRef > B)
Definition: VPlanCFG.h:278
static ChildIteratorType child_end(NodeRef N)
Definition: VPlanCFG.h:286
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlanCFG.h:282
static NodeRef getEntryNode(NodeRef N)
Definition: VPlanCFG.h:245
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlanCFG.h:247
static ChildIteratorType child_end(NodeRef N)
Definition: VPlanCFG.h:251
static NodeRef getEntryNode(VPBlockDeepTraversalWrapper< VPBlockBase * > N)
Definition: VPlanCFG.h:132
static NodeRef getEntryNode(VPBlockDeepTraversalWrapper< const VPBlockBase * > N)
Definition: VPlanCFG.h:151
static NodeRef getEntryNode(VPBlockShallowTraversalWrapper< VPBlockBase * > N)
Definition: VPlanCFG.h:178
SmallVectorImpl< VPBlockBase * >::iterator ChildIteratorType
Definition: VPlanCFG.h:176
SmallVectorImpl< VPBlockBase * >::const_iterator ChildIteratorType
Definition: VPlanCFG.h:194
static NodeRef getEntryNode(VPBlockShallowTraversalWrapper< const VPBlockBase * > N)
Definition: VPlanCFG.h:197
static nodes_iterator nodes_end(GraphRef N)
Definition: VPlanCFG.h:302
static NodeRef getEntryNode(GraphRef N)
Definition: VPlanCFG.h:296
static nodes_iterator nodes_begin(GraphRef N)
Definition: VPlanCFG.h:298
static ChildIteratorType child_end(NodeRef N)
Definition: VPlanCFG.h:266
static ChildIteratorType child_begin(NodeRef N)
Definition: VPlanCFG.h:262
static NodeRef getEntryNode(NodeRef N)
Definition: VPlanCFG.h:260
Binary functor that adapts to any other binary functor after dereferencing operands.
Definition: STLExtras.h:2219