LLVM 17.0.0git
RegionIterator.h
Go to the documentation of this file.
1//===- RegionIterator.h - Iterators to iteratate over Regions ---*- 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// This file defines the iterators to iterate over the elements of a Region.
9//===----------------------------------------------------------------------===//
10
11#ifndef LLVM_ANALYSIS_REGIONITERATOR_H
12#define LLVM_ANALYSIS_REGIONITERATOR_H
13
18#include <cassert>
19#include <iterator>
20#include <type_traits>
21
22namespace llvm {
23
24class BasicBlock;
25class RegionInfo;
26
27//===----------------------------------------------------------------------===//
28/// Hierarchical RegionNode successor iterator.
29///
30/// This iterator iterates over all successors of a RegionNode.
31///
32/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
33/// the parent Region. Furthermore for BasicBlocks that start a subregion, a
34/// RegionNode representing the subregion is returned.
35///
36/// For a subregion RegionNode there is just one successor. The RegionNode
37/// representing the exit of the subregion.
38template <class NodeRef, class BlockT, class RegionT> class RNSuccIterator {
39public:
40 using iterator_category = std::forward_iterator_tag;
41 using value_type = NodeRef;
42 using difference_type = std::ptrdiff_t;
45
46private:
48 using SuccIterTy = typename BlockTraits::ChildIteratorType;
49
50 // The iterator works in two modes, bb mode or region mode.
51 enum ItMode {
52 // In BB mode it returns all successors of this BasicBlock as its
53 // successors.
54 ItBB,
55 // In region mode there is only one successor, thats the regionnode mapping
56 // to the exit block of the regionnode
57 ItRgBegin, // At the beginning of the regionnode successor.
58 ItRgEnd // At the end of the regionnode successor.
59 };
60
61 static_assert(std::is_pointer<NodeRef>::value,
62 "FIXME: Currently RNSuccIterator only supports NodeRef as "
63 "pointers due to the use of pointer-specific data structures "
64 "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
65 "it to support non-pointer types");
66
67 // Use two bit to represent the mode iterator.
69
70 // The block successor iterator.
71 SuccIterTy BItor;
72
73 // advanceRegionSucc - A region node has only one successor. It reaches end
74 // once we advance it.
75 void advanceRegionSucc() {
76 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
77 Node.setInt(ItRgEnd);
78 }
79
80 NodeRef getNode() const { return Node.getPointer(); }
81
82 // isRegionMode - Is the current iterator in region mode?
83 bool isRegionMode() const { return Node.getInt() != ItBB; }
84
85 // Get the immediate successor. This function may return a Basic Block
86 // RegionNode or a subregion RegionNode.
87 NodeRef getISucc(BlockT *BB) const {
88 NodeRef succ;
89 succ = getNode()->getParent()->getNode(BB);
90 assert(succ && "BB not in Region or entered subregion!");
91 return succ;
92 }
93
94 // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
95 inline BlockT* getRegionSucc() const {
96 assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
97 return getNode()->template getNodeAs<RegionT>()->getExit();
98 }
99
100 // isExit - Is this the exit BB of the Region?
101 inline bool isExit(BlockT* BB) const {
102 return getNode()->getParent()->getExit() == BB;
103 }
104
105public:
107
108 /// Create begin iterator of a RegionNode.
109 inline RNSuccIterator(NodeRef node)
110 : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
111 BItor(BlockTraits::child_begin(node->getEntry())) {
112 // Skip the exit block
113 if (!isRegionMode())
114 while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
115 ++BItor;
116
117 if (isRegionMode() && isExit(getRegionSucc()))
118 advanceRegionSucc();
119 }
120
121 /// Create an end iterator.
122 inline RNSuccIterator(NodeRef node, bool)
123 : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
124 BItor(BlockTraits::child_end(node->getEntry())) {}
125
126 inline bool operator==(const Self& x) const {
127 assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
128 if (isRegionMode())
129 return Node.getInt() == x.Node.getInt();
130 else
131 return BItor == x.BItor;
132 }
133
134 inline bool operator!=(const Self& x) const { return !operator==(x); }
135
136 inline value_type operator*() const {
137 BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
138 assert(!isExit(BB) && "Iterator out of range!");
139 return getISucc(BB);
140 }
141
142 inline Self& operator++() {
143 if(isRegionMode()) {
144 // The Region only has 1 successor.
145 advanceRegionSucc();
146 } else {
147 // Skip the exit.
148 do
149 ++BItor;
150 while (BItor != BlockTraits::child_end(getNode()->getEntry())
151 && isExit(*BItor));
152 }
153 return *this;
154 }
155
156 inline Self operator++(int) {
157 Self tmp = *this;
158 ++*this;
159 return tmp;
160 }
161};
162
163//===----------------------------------------------------------------------===//
164/// Flat RegionNode iterator.
165///
166/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
167/// are contained in the Region and its subregions. This is close to a virtual
168/// control flow graph of the Region.
169template <class NodeRef, class BlockT, class RegionT>
170class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
172 using SuccIterTy = typename BlockTraits::ChildIteratorType;
173
174 NodeRef Node;
175 SuccIterTy Itor;
176
177public:
178 using iterator_category = std::forward_iterator_tag;
179 using value_type = NodeRef;
180 using difference_type = std::ptrdiff_t;
183
184 using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
185
186 /// Create the iterator from a RegionNode.
187 ///
188 /// Note that the incoming node must be a bb node, otherwise it will trigger
189 /// an assertion when we try to get a BasicBlock.
190 inline RNSuccIterator(NodeRef node)
191 : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
192 assert(!Node->isSubRegion() &&
193 "Subregion node not allowed in flat iterating mode!");
194 assert(Node->getParent() && "A BB node must have a parent!");
195
196 // Skip the exit block of the iterating region.
197 while (BlockTraits::child_end(Node->getEntry()) != Itor &&
198 Node->getParent()->getExit() == *Itor)
199 ++Itor;
200 }
201
202 /// Create an end iterator
203 inline RNSuccIterator(NodeRef node, bool)
204 : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
205 assert(!Node->isSubRegion() &&
206 "Subregion node not allowed in flat iterating mode!");
207 }
208
209 inline bool operator==(const Self& x) const {
210 assert(Node->getParent() == x.Node->getParent()
211 && "Cannot compare iterators of different regions!");
212
213 return Itor == x.Itor && Node == x.Node;
214 }
215
216 inline bool operator!=(const Self& x) const { return !operator==(x); }
217
218 inline value_type operator*() const {
219 BlockT *BB = *Itor;
220
221 // Get the iterating region.
222 RegionT *Parent = Node->getParent();
223
224 // The only case that the successor reaches out of the region is it reaches
225 // the exit of the region.
226 assert(Parent->getExit() != BB && "iterator out of range!");
227
228 return Parent->getBBNode(BB);
229 }
230
231 inline Self& operator++() {
232 // Skip the exit block of the iterating region.
233 do
234 ++Itor;
235 while (Itor != succ_end(Node->getEntry())
236 && Node->getParent()->getExit() == *Itor);
237
238 return *this;
239 }
240
241 inline Self operator++(int) {
242 Self tmp = *this;
243 ++*this;
244 return tmp;
245 }
246};
247
248template <class NodeRef, class BlockT, class RegionT>
251}
252
253template <class NodeRef, class BlockT, class RegionT>
256}
257
258//===--------------------------------------------------------------------===//
259// RegionNode GraphTraits specialization so the bbs in the region can be
260// iterate by generic graph iterators.
261//
262// NodeT can either be region node or const region node, otherwise child_begin
263// and child_end fail.
264
265#define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
266 template <> struct GraphTraits<NodeT *> { \
267 using NodeRef = NodeT *; \
268 using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>; \
269 static NodeRef getEntryNode(NodeRef N) { return N; } \
270 static inline ChildIteratorType child_begin(NodeRef N) { \
271 return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \
272 } \
273 static inline ChildIteratorType child_end(NodeRef N) { \
274 return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \
275 } \
276 }; \
277 template <> struct GraphTraits<FlatIt<NodeT *>> { \
278 using NodeRef = NodeT *; \
279 using ChildIteratorType = \
280 RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>; \
281 static NodeRef getEntryNode(NodeRef N) { return N; } \
282 static inline ChildIteratorType child_begin(NodeRef N) { \
283 return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \
284 } \
285 static inline ChildIteratorType child_end(NodeRef N) { \
286 return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \
287 } \
288 }
289
290#define RegionGraphTraits(RegionT, NodeT) \
291 template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> { \
292 using nodes_iterator = df_iterator<NodeRef>; \
293 static NodeRef getEntryNode(RegionT *R) { \
294 return R->getNode(R->getEntry()); \
295 } \
296 static nodes_iterator nodes_begin(RegionT *R) { \
297 return nodes_iterator::begin(getEntryNode(R)); \
298 } \
299 static nodes_iterator nodes_end(RegionT *R) { \
300 return nodes_iterator::end(getEntryNode(R)); \
301 } \
302 }; \
303 template <> \
304 struct GraphTraits<FlatIt<RegionT *>> \
305 : public GraphTraits<FlatIt<NodeT *>> { \
306 using nodes_iterator = \
307 df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, \
308 GraphTraits<FlatIt<NodeRef>>>; \
309 static NodeRef getEntryNode(RegionT *R) { \
310 return R->getBBNode(R->getEntry()); \
311 } \
312 static nodes_iterator nodes_begin(RegionT *R) { \
313 return nodes_iterator::begin(getEntryNode(R)); \
314 } \
315 static nodes_iterator nodes_end(RegionT *R) { \
316 return nodes_iterator::end(getEntryNode(R)); \
317 } \
318 }
319
322
325
326template <> struct GraphTraits<RegionInfo*>
331
333 return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
334 }
335
337 return nodes_iterator::begin(getEntryNode(RI));
338 }
339
341 return nodes_iterator::end(getEntryNode(RI));
342 }
343};
344
345template <> struct GraphTraits<RegionInfoPass*>
350
353 }
354
357 }
358
361 }
362};
363
364} // end namespace llvm
365
366#endif // LLVM_ANALYSIS_REGIONITERATOR_H
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
This file defines the PointerIntPair class.
#define RegionNodeGraphTraits(NodeT, BlockT, RegionT)
#define RegionGraphTraits(RegionT, NodeT)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
Marker class to iterate over the elements of a Region in flat mode.
Definition: RegionInfo.h:112
PointerIntPair - This class implements a pair of a pointer and small integer.
IntType getInt() const
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
RNSuccIterator(NodeRef node)
Create the iterator from a RegionNode.
Hierarchical RegionNode successor iterator.
value_type operator*() const
value_type * pointer
value_type & reference
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
std::forward_iterator_tag iterator_category
std::ptrdiff_t difference_type
bool operator!=(const Self &x) const
bool operator==(const Self &x) const
RNSuccIterator(NodeRef node)
Create begin iterator of a RegionNode.
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:866
RegionInfo & getRegionInfo()
Definition: RegionInfo.h:951
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:99
static nodes_iterator nodes_begin(RegionInfoPass *RI)
static nodes_iterator nodes_end(RegionInfoPass *RI)
static NodeRef getEntryNode(RegionInfoPass *RI)
static nodes_iterator nodes_begin(RegionInfo *RI)
static nodes_iterator nodes_end(RegionInfo *RI)
static NodeRef getEntryNode(RegionInfo *RI)
typename GraphType::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80