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
14 #include "llvm/ADT/DepthFirstIterator.h"
15 #include "llvm/ADT/GraphTraits.h"
16 #include "llvm/ADT/PointerIntPair.h"
17 #include "llvm/Analysis/RegionInfo.h"
18 #include <cassert>
19 #include <iterator>
20 #include <type_traits>
21
22 namespace llvm {
23
24 class BasicBlock;
25 class 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.
38 template <class NodeRef, class BlockT, class RegionT> class RNSuccIterator {
39 public:
40 using iterator_category = std::forward_iterator_tag;
41 using value_type = NodeRef;
42 using difference_type = std::ptrdiff_t;
43 using pointer = value_type *;
44 using reference = value_type &;
45
46 private:
47 using BlockTraits = GraphTraits<BlockT *>;
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.
68 PointerIntPair<NodeRef, 2, ItMode> Node;
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.
advanceRegionSucc()75 void advanceRegionSucc() {
76 assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
77 Node.setInt(ItRgEnd);
78 }
79
getNode()80 NodeRef getNode() const { return Node.getPointer(); }
81
82 // isRegionMode - Is the current iterator in region mode?
isRegionMode()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.
getISucc(BlockT * BB)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.
getRegionSucc()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?
isExit(BlockT * BB)101 inline bool isExit(BlockT* BB) const {
102 return getNode()->getParent()->getExit() == BB;
103 }
104
105 public:
106 using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;
107
108 /// Create begin iterator of a RegionNode.
RNSuccIterator(NodeRef node)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.
RNSuccIterator(NodeRef node,bool)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.
169 template <class NodeRef, class BlockT, class RegionT>
170 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
171 using BlockTraits = GraphTraits<BlockT *>;
172 using SuccIterTy = typename BlockTraits::ChildIteratorType;
173
174 NodeRef Node;
175 SuccIterTy Itor;
176
177 public:
178 using iterator_category = std::forward_iterator_tag;
179 using value_type = NodeRef;
180 using difference_type = std::ptrdiff_t;
181 using pointer = value_type *;
182 using reference = value_type &;
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.
RNSuccIterator(NodeRef node)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
RNSuccIterator(NodeRef node,bool)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
248 template <class NodeRef, class BlockT, class RegionT>
succ_begin(NodeRef Node)249 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
250 return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
251 }
252
253 template <class NodeRef, class BlockT, class RegionT>
succ_end(NodeRef Node)254 inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
255 return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
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
320 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
321 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
322
323 RegionGraphTraits(Region, RegionNode);
324 RegionGraphTraits(const Region, const RegionNode);
325
326 template <> struct GraphTraits<RegionInfo*>
327 : public GraphTraits<FlatIt<RegionNode*>> {
328 using nodes_iterator =
329 df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
330 GraphTraits<FlatIt<NodeRef>>>;
331
332 static NodeRef getEntryNode(RegionInfo *RI) {
333 return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
334 }
335
336 static nodes_iterator nodes_begin(RegionInfo* RI) {
337 return nodes_iterator::begin(getEntryNode(RI));
338 }
339
340 static nodes_iterator nodes_end(RegionInfo *RI) {
341 return nodes_iterator::end(getEntryNode(RI));
342 }
343 };
344
345 template <> struct GraphTraits<RegionInfoPass*>
346 : public GraphTraits<RegionInfo *> {
347 using nodes_iterator =
348 df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
349 GraphTraits<FlatIt<NodeRef>>>;
350
351 static NodeRef getEntryNode(RegionInfoPass *RI) {
352 return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
353 }
354
355 static nodes_iterator nodes_begin(RegionInfoPass* RI) {
356 return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
357 }
358
359 static nodes_iterator nodes_end(RegionInfoPass *RI) {
360 return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
361 }
362 };
363
364 } // end namespace llvm
365
366 #endif // LLVM_ANALYSIS_REGIONITERATOR_H
367