LLVM  10.0.0svn
RegionIterator.h
Go to the documentation of this file.
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 
15 #include "llvm/ADT/GraphTraits.h"
18 #include "llvm/IR/CFG.h"
19 #include <cassert>
20 #include <iterator>
21 #include <type_traits>
22 
23 namespace llvm {
24 
25 class 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.
38 template <class NodeRef, class BlockT, class RegionT>
40  : public std::iterator<std::forward_iterator_tag, NodeRef> {
41  using super = std::iterator<std::forward_iterator_tag, NodeRef>;
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.
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 
100 public:
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.
165 template <class NodeRef, class BlockT, class RegionT>
166 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
167  : public std::iterator<std::forward_iterator_tag, NodeRef> {
168  using super = std::iterator<std::forward_iterator_tag, NodeRef>;
170  using SuccIterTy = typename BlockTraits::ChildIteratorType;
171 
172  NodeRef Node;
173  SuccIterTy Itor;
174 
175 public:
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 
241 template <class NodeRef, class BlockT, class RegionT>
244 }
245 
246 template <class NodeRef, class BlockT, class RegionT>
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 
313 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
314 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
315 
316 RegionGraphTraits(Region, RegionNode);
317 RegionGraphTraits(const Region, const RegionNode);
318 
319 template <> struct GraphTraits<RegionInfo*>
321  using nodes_iterator =
324 
326  return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
327  }
328 
330  return nodes_iterator::begin(getEntryNode(RI));
331  }
332 
334  return nodes_iterator::end(getEntryNode(RI));
335  }
336 };
337 
338 template <> struct GraphTraits<RegionInfoPass*>
339  : public GraphTraits<RegionInfo *> {
340  using nodes_iterator =
343 
346  }
347 
350  }
351 
354  }
355 };
356 
357 } // end namespace llvm
358 
359 #endif // LLVM_ANALYSIS_REGIONITERATOR_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
void setInt(IntType IntVal)
bool operator==(const Self &x) const
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PointerTy getPointer() const
Various leaf nodes.
Definition: ISDOpcodes.h:59
static nodes_iterator nodes_begin(RegionInfo *RI)
value_type operator*() const
Hierarchical RegionNode successor iterator.
RNSuccIterator(NodeRef node)
Create the iterator from a RegionNode.
static nodes_iterator nodes_end(RegionInfo *RI)
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
RegionInfo & getRegionInfo()
Definition: RegionInfo.h:955
static nodes_iterator nodes_begin(RegionInfoPass *RI)
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:102
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:868
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
IntType getInt() const
RegionNodeGraphTraits(RegionNode, BasicBlock, Region)
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
typename FlatIt< RegionNode * > ::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
bool operator!=(const Self &x) const
static NodeRef getEntryNode(RegionInfoPass *RI)
static NodeRef getEntryNode(RegionInfo *RI)
RNSuccIterator(NodeRef node)
Create begin iterator of a RegionNode.
RegionGraphTraits(Region, RegionNode)
typename super::value_type value_type
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Marker class to iterate over the elements of a Region in flat mode.
Definition: RegionInfo.h:113
static nodes_iterator nodes_end(RegionInfoPass *RI)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())