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