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
24namespace llvm {
25
26class BasicBlock;
27
28//===----------------------------------------------------------------------===//
29/// @brief 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.
39template <class NodeRef, class BlockT, class RegionT>
40class 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  NodeRef getNode() const { return Node.getPointer(); }
77
78  // isRegionMode - Is the current iterator in region mode?
79  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    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    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    return getNode()->getParent()->getExit() == BB;
99  }
100
101public:
102  using Self = RNSuccIterator<NodeRef, BlockT, RegionT>;
103  using value_type = typename super::value_type;
104
105  /// @brief Create begin iterator of a RegionNode.
106  inline RNSuccIterator(NodeRef node)
107      : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
108        BItor(BlockTraits::child_begin(node->getEntry())) {
109    // Skip the exit block
110    if (!isRegionMode())
111      while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
112        ++BItor;
113
114    if (isRegionMode() && isExit(getRegionSucc()))
115      advanceRegionSucc();
116  }
117
118  /// @brief Create an end iterator.
119  inline RNSuccIterator(NodeRef node, bool)
120      : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
121        BItor(BlockTraits::child_end(node->getEntry())) {}
122
123  inline bool operator==(const Self& x) const {
124    assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
125    if (isRegionMode())
126      return Node.getInt() == x.Node.getInt();
127    else
128      return BItor == x.BItor;
129  }
130
131  inline bool operator!=(const Self& x) const { return !operator==(x); }
132
133  inline value_type operator*() const {
134    BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
135    assert(!isExit(BB) && "Iterator out of range!");
136    return getISucc(BB);
137  }
138
139  inline Self& operator++() {
140    if(isRegionMode()) {
141      // The Region only has 1 successor.
142      advanceRegionSucc();
143    } else {
144      // Skip the exit.
145      do
146        ++BItor;
147      while (BItor != BlockTraits::child_end(getNode()->getEntry())
148          && isExit(*BItor));
149    }
150    return *this;
151  }
152
153  inline Self operator++(int) {
154    Self tmp = *this;
155    ++*this;
156    return tmp;
157  }
158};
159
160//===----------------------------------------------------------------------===//
161/// @brief Flat RegionNode iterator.
162///
163/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
164/// are contained in the Region and its subregions. This is close to a virtual
165/// control flow graph of the Region.
166template <class NodeRef, class BlockT, class RegionT>
167class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
168    : public std::iterator<std::forward_iterator_tag, NodeRef> {
169  using super = std::iterator<std::forward_iterator_tag, NodeRef>;
170  using BlockTraits = GraphTraits<BlockT *>;
171  using SuccIterTy = typename BlockTraits::ChildIteratorType;
172
173  NodeRef Node;
174  SuccIterTy Itor;
175
176public:
177  using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
178  using value_type = typename super::value_type;
179
180  /// @brief Create the iterator from a RegionNode.
181  ///
182  /// 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  inline RNSuccIterator(NodeRef node)
185      : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
186    assert(!Node->isSubRegion() &&
187           "Subregion node not allowed in flat iterating mode!");
188    assert(Node->getParent() && "A BB node must have a parent!");
189
190    // Skip the exit block of the iterating region.
191    while (BlockTraits::child_end(Node->getEntry()) != Itor &&
192           Node->getParent()->getExit() == *Itor)
193      ++Itor;
194  }
195
196  /// @brief Create an end iterator
197  inline RNSuccIterator(NodeRef node, bool)
198      : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
199    assert(!Node->isSubRegion() &&
200           "Subregion node not allowed in flat iterating mode!");
201  }
202
203  inline bool operator==(const Self& x) const {
204    assert(Node->getParent() == x.Node->getParent()
205           && "Cannot compare iterators of different regions!");
206
207    return Itor == x.Itor && Node == x.Node;
208  }
209
210  inline bool operator!=(const Self& x) const { return !operator==(x); }
211
212  inline value_type operator*() const {
213    BlockT *BB = *Itor;
214
215    // Get the iterating region.
216    RegionT *Parent = Node->getParent();
217
218    // The only case that the successor reaches out of the region is it reaches
219    // the exit of the region.
220    assert(Parent->getExit() != BB && "iterator out of range!");
221
222    return Parent->getBBNode(BB);
223  }
224
225  inline Self& operator++() {
226    // Skip the exit block of the iterating region.
227    do
228      ++Itor;
229    while (Itor != succ_end(Node->getEntry())
230        && Node->getParent()->getExit() == *Itor);
231
232    return *this;
233  }
234
235  inline Self operator++(int) {
236    Self tmp = *this;
237    ++*this;
238    return tmp;
239  }
240};
241
242template <class NodeRef, class BlockT, class RegionT>
243inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_begin(NodeRef Node) {
244  return RNSuccIterator<NodeRef, BlockT, RegionT>(Node);
245}
246
247template <class NodeRef, class BlockT, class RegionT>
248inline 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
314RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
315RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
316
317RegionGraphTraits(Region, RegionNode);
318RegionGraphTraits(const Region, const RegionNode);
319
320template <> 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    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  static nodes_iterator nodes_end(RegionInfo *RI) {
335    return nodes_iterator::end(getEntryNode(RI));
336  }
337};
338
339template <> 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
361