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