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. |
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 | |
105 | public: |
106 | using Self = RNSuccIterator<NodeRef, BlockT, RegionT>; |
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(BB: *BItor)) |
115 | ++BItor; |
116 | |
117 | if (isRegionMode() && isExit(BB: 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(BB: *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. |
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 | |
248 | template <class NodeRef, class BlockT, class RegionT> |
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> |
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(R: RI->getTopLevelRegion()); |
334 | } |
335 | |
336 | static nodes_iterator nodes_begin(RegionInfo* RI) { |
337 | return nodes_iterator::begin(G: getEntryNode(RI)); |
338 | } |
339 | |
340 | static nodes_iterator nodes_end(RegionInfo *RI) { |
341 | return nodes_iterator::end(G: 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: &RI->getRegionInfo()); |
353 | } |
354 | |
355 | static nodes_iterator nodes_begin(RegionInfoPass* RI) { |
356 | return GraphTraits<RegionInfo*>::nodes_begin(RI: &RI->getRegionInfo()); |
357 | } |
358 | |
359 | static nodes_iterator nodes_end(RegionInfoPass *RI) { |
360 | return GraphTraits<RegionInfo*>::nodes_end(RI: &RI->getRegionInfo()); |
361 | } |
362 | }; |
363 | |
364 | } // end namespace llvm |
365 | |
366 | #endif // LLVM_ANALYSIS_REGIONITERATOR_H |
367 | |