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