LLVM  6.0.0svn
RegionIterator.h
Go to the documentation of this file.
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 
16 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/IR/CFG.h"
20 #include <cassert>
21 #include <iterator>
22 #include <type_traits>
23 
24 namespace llvm {
25 
26 class 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.
39 template <class NodeRef, class BlockT, class RegionT>
41  : public std::iterator<std::forward_iterator_tag, NodeRef> {
42  using super = std::iterator<std::forward_iterator_tag, NodeRef>;
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.
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 
101 public:
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.
166 template <class NodeRef, class BlockT, class RegionT>
167 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>
168  : public std::iterator<std::forward_iterator_tag, NodeRef> {
169  using super = std::iterator<std::forward_iterator_tag, NodeRef>;
171  using SuccIterTy = typename BlockTraits::ChildIteratorType;
172 
173  NodeRef Node;
174  SuccIterTy Itor;
175 
176 public:
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 
242 template <class NodeRef, class BlockT, class RegionT>
245 }
246 
247 template <class NodeRef, class BlockT, class RegionT>
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 
314 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
315 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
316 
317 RegionGraphTraits(Region, RegionNode);
318 RegionGraphTraits(const Region, const RegionNode);
319 
320 template <> struct GraphTraits<RegionInfo*>
322  using nodes_iterator =
325 
327  return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
328  }
329 
331  return nodes_iterator::begin(getEntryNode(RI));
332  }
333 
335  return nodes_iterator::end(getEntryNode(RI));
336  }
337 };
338 
339 template <> struct GraphTraits<RegionInfoPass*>
340  : public GraphTraits<RegionInfo *> {
341  using nodes_iterator =
344 
347  }
348 
351  }
352 
355  }
356 };
357 
358 } // end namespace llvm
359 
360 #endif // LLVM_ANALYSIS_REGIONITERATOR_H
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:244
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:235
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
PointerTy getPointer() const
Various leaf nodes.
Definition: ISDOpcodes.h:60
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:103
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:106
typename FlatIt< RegionNode * > ::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:59
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
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())