xref: /freebsd-src/contrib/llvm-project/llvm/lib/Transforms/Vectorize/VPlanCFG.h (revision 06c3fb2749bda94cb5201f81ffdb8fa6c3161b2e)
1bdd1243dSDimitry Andric //===- VPlanCFG.h - GraphTraits for VP blocks -------------------*- C++ -*-===//
2bdd1243dSDimitry Andric //
3bdd1243dSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4bdd1243dSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5bdd1243dSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6bdd1243dSDimitry Andric //
7bdd1243dSDimitry Andric //===----------------------------------------------------------------------===//
8bdd1243dSDimitry Andric /// Specializations of GraphTraits that allow VPBlockBase graphs to be
9bdd1243dSDimitry Andric /// treated as proper graphs for generic algorithms;
10bdd1243dSDimitry Andric //===----------------------------------------------------------------------===//
11bdd1243dSDimitry Andric 
12bdd1243dSDimitry Andric #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
13bdd1243dSDimitry Andric #define LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
14bdd1243dSDimitry Andric 
15bdd1243dSDimitry Andric #include "VPlan.h"
16*06c3fb27SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h"
17bdd1243dSDimitry Andric #include "llvm/ADT/GraphTraits.h"
18bdd1243dSDimitry Andric #include "llvm/ADT/SmallVector.h"
19bdd1243dSDimitry Andric 
20bdd1243dSDimitry Andric namespace llvm {
21bdd1243dSDimitry Andric 
22bdd1243dSDimitry Andric //===----------------------------------------------------------------------===//
23bdd1243dSDimitry Andric // GraphTraits specializations for VPlan Hierarchical Control-Flow Graphs     //
24bdd1243dSDimitry Andric //===----------------------------------------------------------------------===//
25bdd1243dSDimitry Andric 
26bdd1243dSDimitry Andric /// Iterator to traverse all successors of a VPBlockBase node. This includes the
27bdd1243dSDimitry Andric /// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
28bdd1243dSDimitry Andric /// parent region's successors. This ensures all blocks in a region are visited
29bdd1243dSDimitry Andric /// before any blocks in a successor region when doing a reverse post-order
30bdd1243dSDimitry Andric // traversal of the graph. Region blocks themselves traverse only their entries
31bdd1243dSDimitry Andric // directly and not their successors. Those will be traversed when a region's
32bdd1243dSDimitry Andric // exiting block is traversed
33bdd1243dSDimitry Andric template <typename BlockPtrTy>
34bdd1243dSDimitry Andric class VPAllSuccessorsIterator
35bdd1243dSDimitry Andric     : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
36bdd1243dSDimitry Andric                                   std::bidirectional_iterator_tag,
37bdd1243dSDimitry Andric                                   VPBlockBase> {
38bdd1243dSDimitry Andric   BlockPtrTy Block;
39bdd1243dSDimitry Andric   /// Index of the current successor. For VPBasicBlock nodes, this simply is the
40bdd1243dSDimitry Andric   /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
41bdd1243dSDimitry Andric   /// used for the region's entry block, and SuccessorIdx - 1 are the indices
42bdd1243dSDimitry Andric   /// for the successor array.
43bdd1243dSDimitry Andric   size_t SuccessorIdx;
44bdd1243dSDimitry Andric 
getBlockWithSuccs(BlockPtrTy Current)45bdd1243dSDimitry Andric   static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
46bdd1243dSDimitry Andric     while (Current && Current->getNumSuccessors() == 0)
47bdd1243dSDimitry Andric       Current = Current->getParent();
48bdd1243dSDimitry Andric     return Current;
49bdd1243dSDimitry Andric   }
50bdd1243dSDimitry Andric 
51bdd1243dSDimitry Andric   /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
52bdd1243dSDimitry Andric   /// both the const and non-const operator* implementations.
deref(T1 Block,unsigned SuccIdx)53bdd1243dSDimitry Andric   template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
54bdd1243dSDimitry Andric     if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
55bdd1243dSDimitry Andric       assert(SuccIdx == 0);
56bdd1243dSDimitry Andric       return R->getEntry();
57bdd1243dSDimitry Andric     }
58bdd1243dSDimitry Andric 
59bdd1243dSDimitry Andric     // For exit blocks, use the next parent region with successors.
60bdd1243dSDimitry Andric     return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
61bdd1243dSDimitry Andric   }
62bdd1243dSDimitry Andric 
63bdd1243dSDimitry Andric public:
64bdd1243dSDimitry Andric   /// Used by iterator_facade_base with bidirectional_iterator_tag.
65bdd1243dSDimitry Andric   using reference = BlockPtrTy;
66bdd1243dSDimitry Andric 
67bdd1243dSDimitry Andric   VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
Block(Block)68bdd1243dSDimitry Andric       : Block(Block), SuccessorIdx(Idx) {}
VPAllSuccessorsIterator(const VPAllSuccessorsIterator & Other)69bdd1243dSDimitry Andric   VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
70bdd1243dSDimitry Andric       : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
71bdd1243dSDimitry Andric 
72bdd1243dSDimitry Andric   VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) {
73bdd1243dSDimitry Andric     Block = R.Block;
74bdd1243dSDimitry Andric     SuccessorIdx = R.SuccessorIdx;
75bdd1243dSDimitry Andric     return *this;
76bdd1243dSDimitry Andric   }
77bdd1243dSDimitry Andric 
end(BlockPtrTy Block)78bdd1243dSDimitry Andric   static VPAllSuccessorsIterator end(BlockPtrTy Block) {
79bdd1243dSDimitry Andric     if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
80bdd1243dSDimitry Andric       // Traverse through the region's entry node.
81bdd1243dSDimitry Andric       return {R, 1};
82bdd1243dSDimitry Andric     }
83bdd1243dSDimitry Andric     BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
84bdd1243dSDimitry Andric     unsigned NumSuccessors =
85bdd1243dSDimitry Andric         ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0;
86bdd1243dSDimitry Andric     return {Block, NumSuccessors};
87bdd1243dSDimitry Andric   }
88bdd1243dSDimitry Andric 
89bdd1243dSDimitry Andric   bool operator==(const VPAllSuccessorsIterator &R) const {
90bdd1243dSDimitry Andric     return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
91bdd1243dSDimitry Andric   }
92bdd1243dSDimitry Andric 
93bdd1243dSDimitry Andric   const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
94bdd1243dSDimitry Andric 
95bdd1243dSDimitry Andric   BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
96bdd1243dSDimitry Andric 
97bdd1243dSDimitry Andric   VPAllSuccessorsIterator &operator++() {
98bdd1243dSDimitry Andric     SuccessorIdx++;
99bdd1243dSDimitry Andric     return *this;
100bdd1243dSDimitry Andric   }
101bdd1243dSDimitry Andric 
102bdd1243dSDimitry Andric   VPAllSuccessorsIterator &operator--() {
103bdd1243dSDimitry Andric     SuccessorIdx--;
104bdd1243dSDimitry Andric     return *this;
105bdd1243dSDimitry Andric   }
106bdd1243dSDimitry Andric 
107bdd1243dSDimitry Andric   VPAllSuccessorsIterator operator++(int X) {
108bdd1243dSDimitry Andric     VPAllSuccessorsIterator Orig = *this;
109bdd1243dSDimitry Andric     SuccessorIdx++;
110bdd1243dSDimitry Andric     return Orig;
111bdd1243dSDimitry Andric   }
112bdd1243dSDimitry Andric };
113bdd1243dSDimitry Andric 
114bdd1243dSDimitry Andric /// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
115bdd1243dSDimitry Andric template <typename BlockTy> class VPBlockDeepTraversalWrapper {
116bdd1243dSDimitry Andric   BlockTy Entry;
117bdd1243dSDimitry Andric 
118bdd1243dSDimitry Andric public:
VPBlockDeepTraversalWrapper(BlockTy Entry)119bdd1243dSDimitry Andric   VPBlockDeepTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
getEntry()120bdd1243dSDimitry Andric   BlockTy getEntry() { return Entry; }
121bdd1243dSDimitry Andric };
122bdd1243dSDimitry Andric 
123bdd1243dSDimitry Andric /// GraphTraits specialization to recursively traverse VPBlockBase nodes,
124bdd1243dSDimitry Andric /// including traversing through VPRegionBlocks.  Exit blocks of a region
125bdd1243dSDimitry Andric /// implicitly have their parent region's successors. This ensures all blocks in
126bdd1243dSDimitry Andric /// a region are visited before any blocks in a successor region when doing a
127bdd1243dSDimitry Andric /// reverse post-order traversal of the graph.
128bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockDeepTraversalWrapper<VPBlockBase *>> {
129bdd1243dSDimitry Andric   using NodeRef = VPBlockBase *;
130bdd1243dSDimitry Andric   using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
131bdd1243dSDimitry Andric 
132bdd1243dSDimitry Andric   static NodeRef getEntryNode(VPBlockDeepTraversalWrapper<VPBlockBase *> N) {
133bdd1243dSDimitry Andric     return N.getEntry();
134bdd1243dSDimitry Andric   }
135bdd1243dSDimitry Andric 
136bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
137bdd1243dSDimitry Andric     return ChildIteratorType(N);
138bdd1243dSDimitry Andric   }
139bdd1243dSDimitry Andric 
140bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
141bdd1243dSDimitry Andric     return ChildIteratorType::end(N);
142bdd1243dSDimitry Andric   }
143bdd1243dSDimitry Andric };
144bdd1243dSDimitry Andric 
145bdd1243dSDimitry Andric template <>
146bdd1243dSDimitry Andric struct GraphTraits<VPBlockDeepTraversalWrapper<const VPBlockBase *>> {
147bdd1243dSDimitry Andric   using NodeRef = const VPBlockBase *;
148bdd1243dSDimitry Andric   using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
149bdd1243dSDimitry Andric 
150bdd1243dSDimitry Andric   static NodeRef
151bdd1243dSDimitry Andric   getEntryNode(VPBlockDeepTraversalWrapper<const VPBlockBase *> N) {
152bdd1243dSDimitry Andric     return N.getEntry();
153bdd1243dSDimitry Andric   }
154bdd1243dSDimitry Andric 
155bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
156bdd1243dSDimitry Andric     return ChildIteratorType(N);
157bdd1243dSDimitry Andric   }
158bdd1243dSDimitry Andric 
159bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
160bdd1243dSDimitry Andric     return ChildIteratorType::end(N);
161bdd1243dSDimitry Andric   }
162bdd1243dSDimitry Andric };
163bdd1243dSDimitry Andric 
164bdd1243dSDimitry Andric /// Helper for GraphTraits specialization that does not traverses through
165bdd1243dSDimitry Andric /// VPRegionBlocks.
166bdd1243dSDimitry Andric template <typename BlockTy> class VPBlockShallowTraversalWrapper {
167bdd1243dSDimitry Andric   BlockTy Entry;
168bdd1243dSDimitry Andric 
169bdd1243dSDimitry Andric public:
170bdd1243dSDimitry Andric   VPBlockShallowTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
171bdd1243dSDimitry Andric   BlockTy getEntry() { return Entry; }
172bdd1243dSDimitry Andric };
173bdd1243dSDimitry Andric 
174bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockShallowTraversalWrapper<VPBlockBase *>> {
175bdd1243dSDimitry Andric   using NodeRef = VPBlockBase *;
176bdd1243dSDimitry Andric   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
177bdd1243dSDimitry Andric 
178bdd1243dSDimitry Andric   static NodeRef getEntryNode(VPBlockShallowTraversalWrapper<VPBlockBase *> N) {
179bdd1243dSDimitry Andric     return N.getEntry();
180bdd1243dSDimitry Andric   }
181bdd1243dSDimitry Andric 
182bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
183bdd1243dSDimitry Andric     return N->getSuccessors().begin();
184bdd1243dSDimitry Andric   }
185bdd1243dSDimitry Andric 
186bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
187bdd1243dSDimitry Andric     return N->getSuccessors().end();
188bdd1243dSDimitry Andric   }
189bdd1243dSDimitry Andric };
190bdd1243dSDimitry Andric 
191bdd1243dSDimitry Andric template <>
192bdd1243dSDimitry Andric struct GraphTraits<VPBlockShallowTraversalWrapper<const VPBlockBase *>> {
193bdd1243dSDimitry Andric   using NodeRef = const VPBlockBase *;
194bdd1243dSDimitry Andric   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::const_iterator;
195bdd1243dSDimitry Andric 
196bdd1243dSDimitry Andric   static NodeRef
197bdd1243dSDimitry Andric   getEntryNode(VPBlockShallowTraversalWrapper<const VPBlockBase *> N) {
198bdd1243dSDimitry Andric     return N.getEntry();
199bdd1243dSDimitry Andric   }
200bdd1243dSDimitry Andric 
201bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
202bdd1243dSDimitry Andric     return N->getSuccessors().begin();
203bdd1243dSDimitry Andric   }
204bdd1243dSDimitry Andric 
205bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
206bdd1243dSDimitry Andric     return N->getSuccessors().end();
207bdd1243dSDimitry Andric   }
208bdd1243dSDimitry Andric };
209bdd1243dSDimitry Andric 
210bdd1243dSDimitry Andric /// Returns an iterator range to traverse the graph starting at \p G in
211bdd1243dSDimitry Andric /// depth-first order. The iterator won't traverse through region blocks.
212bdd1243dSDimitry Andric inline iterator_range<
213bdd1243dSDimitry Andric     df_iterator<VPBlockShallowTraversalWrapper<VPBlockBase *>>>
214bdd1243dSDimitry Andric vp_depth_first_shallow(VPBlockBase *G) {
215bdd1243dSDimitry Andric   return depth_first(VPBlockShallowTraversalWrapper<VPBlockBase *>(G));
216bdd1243dSDimitry Andric }
217bdd1243dSDimitry Andric inline iterator_range<
218bdd1243dSDimitry Andric     df_iterator<VPBlockShallowTraversalWrapper<const VPBlockBase *>>>
219bdd1243dSDimitry Andric vp_depth_first_shallow(const VPBlockBase *G) {
220bdd1243dSDimitry Andric   return depth_first(VPBlockShallowTraversalWrapper<const VPBlockBase *>(G));
221bdd1243dSDimitry Andric }
222bdd1243dSDimitry Andric 
223bdd1243dSDimitry Andric /// Returns an iterator range to traverse the graph starting at \p G in
224bdd1243dSDimitry Andric /// depth-first order while traversing through region blocks.
225bdd1243dSDimitry Andric inline iterator_range<df_iterator<VPBlockDeepTraversalWrapper<VPBlockBase *>>>
226bdd1243dSDimitry Andric vp_depth_first_deep(VPBlockBase *G) {
227bdd1243dSDimitry Andric   return depth_first(VPBlockDeepTraversalWrapper<VPBlockBase *>(G));
228bdd1243dSDimitry Andric }
229bdd1243dSDimitry Andric inline iterator_range<
230bdd1243dSDimitry Andric     df_iterator<VPBlockDeepTraversalWrapper<const VPBlockBase *>>>
231bdd1243dSDimitry Andric vp_depth_first_deep(const VPBlockBase *G) {
232bdd1243dSDimitry Andric   return depth_first(VPBlockDeepTraversalWrapper<const VPBlockBase *>(G));
233bdd1243dSDimitry Andric }
234bdd1243dSDimitry Andric 
235bdd1243dSDimitry Andric // The following set of template specializations implement GraphTraits to treat
236bdd1243dSDimitry Andric // any VPBlockBase as a node in a graph of VPBlockBases. It's important to note
237bdd1243dSDimitry Andric // that VPBlockBase traits don't recurse into VPRegioBlocks, i.e., if the
238bdd1243dSDimitry Andric // VPBlockBase is a VPRegionBlock, this specialization provides access to its
239bdd1243dSDimitry Andric // successors/predecessors but not to the blocks inside the region.
240bdd1243dSDimitry Andric 
241bdd1243dSDimitry Andric template <> struct GraphTraits<VPBlockBase *> {
242bdd1243dSDimitry Andric   using NodeRef = VPBlockBase *;
243bdd1243dSDimitry Andric   using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
244bdd1243dSDimitry Andric 
245bdd1243dSDimitry Andric   static NodeRef getEntryNode(NodeRef N) { return N; }
246bdd1243dSDimitry Andric 
247bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
248bdd1243dSDimitry Andric     return ChildIteratorType(N);
249bdd1243dSDimitry Andric   }
250bdd1243dSDimitry Andric 
251bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
252bdd1243dSDimitry Andric     return ChildIteratorType::end(N);
253bdd1243dSDimitry Andric   }
254bdd1243dSDimitry Andric };
255bdd1243dSDimitry Andric 
256bdd1243dSDimitry Andric template <> struct GraphTraits<const VPBlockBase *> {
257bdd1243dSDimitry Andric   using NodeRef = const VPBlockBase *;
258bdd1243dSDimitry Andric   using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
259bdd1243dSDimitry Andric 
260bdd1243dSDimitry Andric   static NodeRef getEntryNode(NodeRef N) { return N; }
261bdd1243dSDimitry Andric 
262bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
263bdd1243dSDimitry Andric     return ChildIteratorType(N);
264bdd1243dSDimitry Andric   }
265bdd1243dSDimitry Andric 
266bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
267bdd1243dSDimitry Andric     return ChildIteratorType::end(N);
268bdd1243dSDimitry Andric   }
269bdd1243dSDimitry Andric };
270bdd1243dSDimitry Andric 
271bdd1243dSDimitry Andric /// Inverse graph traits are not implemented yet.
272bdd1243dSDimitry Andric /// TODO: Implement a version of VPBlockNonRecursiveTraversalWrapper to traverse
273bdd1243dSDimitry Andric /// predecessors recursively through regions.
274bdd1243dSDimitry Andric template <> struct GraphTraits<Inverse<VPBlockBase *>> {
275bdd1243dSDimitry Andric   using NodeRef = VPBlockBase *;
276bdd1243dSDimitry Andric   using ChildIteratorType = SmallVectorImpl<VPBlockBase *>::iterator;
277bdd1243dSDimitry Andric 
278bdd1243dSDimitry Andric   static NodeRef getEntryNode(Inverse<NodeRef> B) {
279bdd1243dSDimitry Andric     llvm_unreachable("not implemented");
280bdd1243dSDimitry Andric   }
281bdd1243dSDimitry Andric 
282bdd1243dSDimitry Andric   static inline ChildIteratorType child_begin(NodeRef N) {
283bdd1243dSDimitry Andric     llvm_unreachable("not implemented");
284bdd1243dSDimitry Andric   }
285bdd1243dSDimitry Andric 
286bdd1243dSDimitry Andric   static inline ChildIteratorType child_end(NodeRef N) {
287bdd1243dSDimitry Andric     llvm_unreachable("not implemented");
288bdd1243dSDimitry Andric   }
289bdd1243dSDimitry Andric };
290bdd1243dSDimitry Andric 
291bdd1243dSDimitry Andric template <> struct GraphTraits<VPlan *> {
292bdd1243dSDimitry Andric   using GraphRef = VPlan *;
293bdd1243dSDimitry Andric   using NodeRef = VPBlockBase *;
294bdd1243dSDimitry Andric   using nodes_iterator = df_iterator<NodeRef>;
295bdd1243dSDimitry Andric 
296bdd1243dSDimitry Andric   static NodeRef getEntryNode(GraphRef N) { return N->getEntry(); }
297bdd1243dSDimitry Andric 
298bdd1243dSDimitry Andric   static nodes_iterator nodes_begin(GraphRef N) {
299bdd1243dSDimitry Andric     return nodes_iterator::begin(N->getEntry());
300bdd1243dSDimitry Andric   }
301bdd1243dSDimitry Andric 
302bdd1243dSDimitry Andric   static nodes_iterator nodes_end(GraphRef N) {
303bdd1243dSDimitry Andric     // df_iterator::end() returns an empty iterator so the node used doesn't
304bdd1243dSDimitry Andric     // matter.
305bdd1243dSDimitry Andric     return nodes_iterator::end(N->getEntry());
306bdd1243dSDimitry Andric   }
307bdd1243dSDimitry Andric };
308bdd1243dSDimitry Andric 
309bdd1243dSDimitry Andric } // namespace llvm
310bdd1243dSDimitry Andric 
311bdd1243dSDimitry Andric #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANCFG_H
312