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
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 NodeRef, class BlockT, class RegionT>
34class RNSuccIterator
35    : public std::iterator<std::forward_iterator_tag, NodeRef> {
36  typedef std::iterator<std::forward_iterator_tag, NodeRef> 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  static_assert(std::is_pointer<NodeRef>::value,
53                "FIXME: Currently RNSuccIterator only supports NodeRef as "
54                "pointers due to the use of pointer-specific data structures "
55                "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
56                "it to support non-pointer types");
57
58  // Use two bit to represent the mode iterator.
59  PointerIntPair<NodeRef, 2, ItMode> Node;
60
61  // The block successor iterator.
62  SuccIterTy BItor;
63
64  // advanceRegionSucc - A region node has only one successor. It reaches end
65  // once we advance it.
66  void advanceRegionSucc() {
67    assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
68    Node.setInt(ItRgEnd);
69  }
70
71  NodeRef getNode() const { return Node.getPointer(); }
72
73  // isRegionMode - Is the current iterator in region mode?
74  bool isRegionMode() const { return Node.getInt() != ItBB; }
75
76  // Get the immediate successor. This function may return a Basic Block
77  // RegionNode or a subregion RegionNode.
78  NodeRef getISucc(BlockT *BB) const {
79    NodeRef succ;
80    succ = getNode()->getParent()->getNode(BB);
81    assert(succ && "BB not in Region or entered subregion!");
82    return succ;
83  }
84
85  // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
86  inline BlockT* getRegionSucc() const {
87    assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
88    return getNode()->template getNodeAs<RegionT>()->getExit();
89  }
90
91  // isExit - Is this the exit BB of the Region?
92  inline bool isExit(BlockT* BB) const {
93    return getNode()->getParent()->getExit() == BB;
94  }
95public:
96  typedef RNSuccIterator<NodeRef, BlockT, RegionT> Self;
97
98  typedef typename super::value_type value_type;
99
100  /// @brief Create begin iterator of a RegionNode.
101  inline RNSuccIterator(NodeRef node)
102      : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
103        BItor(BlockTraits::child_begin(node->getEntry())) {
104
105    // Skip the exit block
106    if (!isRegionMode())
107      while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
108        ++BItor;
109
110    if (isRegionMode() && isExit(getRegionSucc()))
111      advanceRegionSucc();
112  }
113
114  /// @brief Create an end iterator.
115  inline RNSuccIterator(NodeRef node, bool)
116      : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
117        BItor(BlockTraits::child_end(node->getEntry())) {}
118
119  inline bool operator==(const Self& x) const {
120    assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
121    if (isRegionMode())
122      return Node.getInt() == x.Node.getInt();
123    else
124      return BItor == x.BItor;
125  }
126
127  inline bool operator!=(const Self& x) const { return !operator==(x); }
128
129  inline value_type operator*() const {
130    BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
131    assert(!isExit(BB) && "Iterator out of range!");
132    return getISucc(BB);
133  }
134
135  inline Self& operator++() {
136    if(isRegionMode()) {
137      // The Region only has 1 successor.
138      advanceRegionSucc();
139    } else {
140      // Skip the exit.
141      do
142        ++BItor;
143      while (BItor != BlockTraits::child_end(getNode()->getEntry())
144          && isExit(*BItor));
145    }
146    return *this;
147  }
148
149  inline Self operator++(int) {
150    Self tmp = *this;
151    ++*this;
152    return tmp;
153  }
154};
155
156
157//===----------------------------------------------------------------------===//
158/// @brief Flat RegionNode iterator.
159///
160/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
161/// are contained in the Region and its subregions. This is close to a virtual
162/// control flow graph of the Region.
163template <class NodeRef, class BlockT, class RegionT>
164class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
165    : public std::iterator<std::forward_iterator_tag, NodeRef> {
166  typedef std::iterator<std::forward_iterator_tag, NodeRef> super;
167  typedef GraphTraits<BlockT*> BlockTraits;
168  typedef typename BlockTraits::ChildIteratorType SuccIterTy;
169
170  NodeRef Node;
171  SuccIterTy Itor;
172
173public:
174  typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> Self;
175  typedef typename super::value_type value_type;
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(NodeRef node)
182      : Node(node), Itor(BlockTraits::child_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 (BlockTraits::child_end(Node->getEntry()) != Itor &&
189           Node->getParent()->getExit() == *Itor)
190      ++Itor;
191  }
192
193  /// @brief Create an end iterator
194  inline RNSuccIterator(NodeRef node, bool)
195      : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
196    assert(!Node->isSubRegion() &&
197           "Subregion node not allowed in flat iterating mode!");
198  }
199
200  inline bool operator==(const Self& x) const {
201    assert(Node->getParent() == x.Node->getParent()
202           && "Cannot compare iterators of different regions!");
203
204    return Itor == x.Itor && Node == x.Node;
205  }
206
207  inline bool operator!=(const Self& x) const { return !operator==(x); }
208
209  inline value_type operator*() const {
210    BlockT *BB = *Itor;
211
212    // Get the iterating region.
213    RegionT *Parent = Node->getParent();
214
215    // The only case that the successor reaches out of the region is it reaches
216    // the exit of the region.
217    assert(Parent->getExit() != BB && "iterator out of range!");
218
219    return Parent->getBBNode(BB);
220  }
221
222  inline Self& operator++() {
223    // Skip the exit block of the iterating region.
224    do
225      ++Itor;
226    while (Itor != succ_end(Node->getEntry())
227        && Node->getParent()->getExit() == *Itor);
228
229    return *this;
230  }
231
232  inline Self operator++(int) {
233    Self tmp = *this;
234    ++*this;
235    return tmp;
236  }
237};
238
239template <class NodeRef, class BlockT, class RegionT>
240inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
241  return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
242}
243
244template <class NodeRef, class BlockT, class RegionT>
245inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
246  return RNSuccIterator<NodeRef, BlockT, RegionT>(Node, true);
247}
248
249//===--------------------------------------------------------------------===//
250// RegionNode GraphTraits specialization so the bbs in the region can be
251// iterate by generic graph iterators.
252//
253// NodeT can either be region node or const region node, otherwise child_begin
254// and child_end fail.
255
256#define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
257  template <> struct GraphTraits<NodeT *> {                                    \
258    typedef NodeT *NodeRef;                                                    \
259    typedef RNSuccIterator<NodeRef, BlockT, RegionT> ChildIteratorType;        \
260    static NodeRef getEntryNode(NodeRef N) { return N; }                       \
261    static inline ChildIteratorType child_begin(NodeRef N) {                   \
262      return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
263    }                                                                          \
264    static inline ChildIteratorType child_end(NodeRef N) {                     \
265      return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
266    }                                                                          \
267  };                                                                           \
268  template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
269    typedef NodeT *NodeRef;                                                    \
270    typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>                   \
271        ChildIteratorType;                                                     \
272    static NodeRef getEntryNode(NodeRef N) { return N; }                       \
273    static inline ChildIteratorType child_begin(NodeRef N) {                   \
274      return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
275    }                                                                          \
276    static inline ChildIteratorType child_end(NodeRef N) {                     \
277      return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true);        \
278    }                                                                          \
279  }
280
281#define RegionGraphTraits(RegionT, NodeT)                                      \
282  template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> {    \
283    typedef df_iterator<NodeRef> nodes_iterator;                               \
284    static NodeRef getEntryNode(RegionT *R) {                                  \
285      return R->getNode(R->getEntry());                                        \
286    }                                                                          \
287    static nodes_iterator nodes_begin(RegionT *R) {                            \
288      return nodes_iterator::begin(getEntryNode(R));                           \
289    }                                                                          \
290    static nodes_iterator nodes_end(RegionT *R) {                              \
291      return nodes_iterator::end(getEntryNode(R));                             \
292    }                                                                          \
293  };                                                                           \
294  template <>                                                                  \
295  struct GraphTraits<FlatIt<RegionT *>>                                        \
296      : public GraphTraits<FlatIt<NodeT *>> {                                  \
297    typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,      \
298                        GraphTraits<FlatIt<NodeRef>>>                          \
299        nodes_iterator;                                                        \
300    static NodeRef getEntryNode(RegionT *R) {                                  \
301      return R->getBBNode(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
311RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
312RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
313
314RegionGraphTraits(Region, RegionNode);
315RegionGraphTraits(const Region, const RegionNode);
316
317template <> struct GraphTraits<RegionInfo*>
318  : public GraphTraits<FlatIt<RegionNode*> > {
319  typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
320                      GraphTraits<FlatIt<NodeRef>>>
321      nodes_iterator;
322
323  static NodeRef getEntryNode(RegionInfo *RI) {
324    return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
325  }
326  static nodes_iterator nodes_begin(RegionInfo* RI) {
327    return nodes_iterator::begin(getEntryNode(RI));
328  }
329  static nodes_iterator nodes_end(RegionInfo *RI) {
330    return nodes_iterator::end(getEntryNode(RI));
331  }
332};
333
334template <> struct GraphTraits<RegionInfoPass*>
335  : public GraphTraits<RegionInfo *> {
336  typedef df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false,
337                      GraphTraits<FlatIt<NodeRef>>>
338      nodes_iterator;
339
340  static NodeRef getEntryNode(RegionInfoPass *RI) {
341    return GraphTraits<RegionInfo*>::getEntryNode(&RI->getRegionInfo());
342  }
343  static nodes_iterator nodes_begin(RegionInfoPass* RI) {
344    return GraphTraits<RegionInfo*>::nodes_begin(&RI->getRegionInfo());
345  }
346  static nodes_iterator nodes_end(RegionInfoPass *RI) {
347    return GraphTraits<RegionInfo*>::nodes_end(&RI->getRegionInfo());
348  }
349};
350
351} // End namespace llvm
352
353#endif
354