Line data Source code
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.
71 : void advanceRegionSucc() {
72 : assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
73 : Node.setInt(ItRgEnd);
74 : }
75 :
76 220986 : NodeRef getNode() const { return Node.getPointer(); }
77 :
78 : // isRegionMode - Is the current iterator in region mode?
79 218083 : 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.
83 : NodeRef getISucc(BlockT *BB) const {
84 : NodeRef succ;
85 66603 : 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.
91 : inline BlockT* getRegionSucc() const {
92 : assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
93 12704 : return getNode()->template getNodeAs<RegionT>()->getExit();
94 : }
95 :
96 : // isExit - Is this the exit BB of the Region?
97 : inline bool isExit(BlockT* BB) const {
98 98425 : 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.
106 75756 : inline RNSuccIterator(NodeRef node)
107 : : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
108 136595 : BItor(BlockTraits::child_begin(node->getEntry())) {
109 : // Skip the exit block
110 75756 : if (!isRegionMode())
111 73488 : while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
112 : ++BItor;
113 :
114 75756 : if (isRegionMode() && isExit(getRegionSucc()))
115 : advanceRegionSucc();
116 75756 : }
117 8 :
118 : /// Create an end iterator.
119 142329 : inline RNSuccIterator(NodeRef node, bool)
120 : : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
121 142323 : BItor(BlockTraits::child_end(node->getEntry())) {}
122 10 :
123 : inline bool operator==(const Self& x) const {
124 : assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
125 142323 : if (isRegionMode())
126 55228 : return Node.getInt() == x.Node.getInt();
127 8 : else
128 114701 : return BItor == x.BItor;
129 : }
130 0 :
131 : inline bool operator!=(const Self& x) const { return !operator==(x); }
132 0 :
133 66599 : inline value_type operator*() const {
134 66599 : BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
135 : assert(!isExit(BB) && "Iterator out of range!");
136 66599 : return getISucc(BB);
137 : }
138 0 :
139 66599 : inline Self& operator++() {
140 66599 : if(isRegionMode()) {
141 12 : // The Region only has 1 successor.
142 : advanceRegionSucc();
143 12 : } else {
144 12 : // Skip the exit.
145 : do
146 12 : ++BItor;
147 0 : while (BItor != BlockTraits::child_end(getNode()->getEntry())
148 70861 : && isExit(*BItor));
149 0 : }
150 66599 : return *this;
151 : }
152 :
153 12 : inline Self operator++(int) {
154 66607 : Self tmp = *this;
155 66599 : ++*this;
156 8 : return tmp;
157 : }
158 0 : };
159 :
160 0 : //===----------------------------------------------------------------------===//
161 4 : /// Flat RegionNode iterator.
162 4 : ///
163 0 : /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
164 4 : /// are contained in the Region and its subregions. This is close to a virtual
165 0 : /// control flow graph of the Region.
166 0 : template <class NodeRef, class BlockT, class RegionT>
167 0 : class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
168 0 : : public std::iterator<std::forward_iterator_tag, NodeRef> {
169 0 : using super = std::iterator<std::forward_iterator_tag, NodeRef>;
170 : using BlockTraits = GraphTraits<BlockT *>;
171 4 : using SuccIterTy = typename BlockTraits::ChildIteratorType;
172 4 :
173 : NodeRef Node;
174 4 : SuccIterTy Itor;
175 :
176 : public:
177 4 : using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
178 4 : using value_type = typename super::value_type;
179 :
180 0 : /// Create the iterator from a RegionNode.
181 : ///
182 0 : /// Note that the incoming node must be a bb node, otherwise it will trigger
183 : /// an assertion when we try to get a BasicBlock.
184 54 : inline RNSuccIterator(NodeRef node)
185 108 : : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
186 4 : assert(!Node->isSubRegion() &&
187 : "Subregion node not allowed in flat iterating mode!");
188 4 : assert(Node->getParent() && "A BB node must have a parent!");
189 :
190 0 : // Skip the exit block of the iterating region.
191 102 : while (BlockTraits::child_end(Node->getEntry()) != Itor &&
192 48 : Node->getParent()->getExit() == *Itor)
193 0 : ++Itor;
194 54 : }
195 0 :
196 : /// Create an end iterator
197 0 : inline RNSuccIterator(NodeRef node, bool)
198 0 : : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
199 0 : assert(!Node->isSubRegion() &&
200 : "Subregion node not allowed in flat iterating mode!");
201 0 : }
202 :
203 4 : inline bool operator==(const Self& x) const {
204 4 : assert(Node->getParent() == x.Node->getParent()
205 : && "Cannot compare iterators of different regions!");
206 0 :
207 132 : return Itor == x.Itor && Node == x.Node;
208 0 : }
209 :
210 : inline bool operator!=(const Self& x) const { return !operator==(x); }
211 0 :
212 84 : inline value_type operator*() const {
213 80 : BlockT *BB = *Itor;
214 4 :
215 : // Get the iterating region.
216 80 : RegionT *Parent = Node->getParent();
217 0 :
218 4 : // The only case that the successor reaches out of the region is it reaches
219 4 : // the exit of the region.
220 0 : assert(Parent->getExit() != BB && "iterator out of range!");
221 :
222 80 : return Parent->getBBNode(BB);
223 0 : }
224 0 :
225 60 : inline Self& operator++() {
226 : // Skip the exit block of the iterating region.
227 0 : do
228 0 : ++Itor;
229 120 : while (Itor != succ_end(Node->getEntry())
230 60 : && Node->getParent()->getExit() == *Itor);
231 :
232 60 : return *this;
233 : }
234 :
235 0 : inline Self operator++(int) {
236 20 : Self tmp = *this;
237 20 : ++*this;
238 0 : return tmp;
239 : }
240 : };
241 :
242 : template <class NodeRef, class BlockT, class RegionT>
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>
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 218117 : RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
315 : RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
316 :
317 39778 : 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 4 : 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 0 : static nodes_iterator nodes_end(RegionInfo *RI) {
335 0 : 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
|
