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