LLVM  14.0.0git
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> class RNSuccIterator {
39 public:
40  using iterator_category = std::forward_iterator_tag;
42  using difference_type = std::ptrdiff_t;
43  using pointer = value_type *;
44  using reference = value_type &;
45 
46 private:
48  using SuccIterTy = typename BlockTraits::ChildIteratorType;
49 
50  // The iterator works in two modes, bb mode or region mode.
51  enum ItMode {
52  // In BB mode it returns all successors of this BasicBlock as its
53  // successors.
54  ItBB,
55  // In region mode there is only one successor, thats the regionnode mapping
56  // to the exit block of the regionnode
57  ItRgBegin, // At the beginning of the regionnode successor.
58  ItRgEnd // At the end of the regionnode successor.
59  };
60 
61  static_assert(std::is_pointer<NodeRef>::value,
62  "FIXME: Currently RNSuccIterator only supports NodeRef as "
63  "pointers due to the use of pointer-specific data structures "
64  "(e.g. PointerIntPair and SmallPtrSet) internally. Generalize "
65  "it to support non-pointer types");
66 
67  // Use two bit to represent the mode iterator.
69 
70  // The block successor iterator.
71  SuccIterTy BItor;
72 
73  // advanceRegionSucc - A region node has only one successor. It reaches end
74  // once we advance it.
75  void advanceRegionSucc() {
76  assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
77  Node.setInt(ItRgEnd);
78  }
79 
80  NodeRef getNode() const { return Node.getPointer(); }
81 
82  // isRegionMode - Is the current iterator in region mode?
83  bool isRegionMode() const { return Node.getInt() != ItBB; }
84 
85  // Get the immediate successor. This function may return a Basic Block
86  // RegionNode or a subregion RegionNode.
87  NodeRef getISucc(BlockT *BB) const {
88  NodeRef succ;
89  succ = getNode()->getParent()->getNode(BB);
90  assert(succ && "BB not in Region or entered subregion!");
91  return succ;
92  }
93 
94  // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
95  inline BlockT* getRegionSucc() const {
96  assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
97  return getNode()->template getNodeAs<RegionT>()->getExit();
98  }
99 
100  // isExit - Is this the exit BB of the Region?
101  inline bool isExit(BlockT* BB) const {
102  return getNode()->getParent()->getExit() == BB;
103  }
104 
105 public:
107 
108  /// Create begin iterator of a RegionNode.
110  : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
111  BItor(BlockTraits::child_begin(node->getEntry())) {
112  // Skip the exit block
113  if (!isRegionMode())
114  while (BlockTraits::child_end(node->getEntry()) != BItor && isExit(*BItor))
115  ++BItor;
116 
117  if (isRegionMode() && isExit(getRegionSucc()))
118  advanceRegionSucc();
119  }
120 
121  /// Create an end iterator.
123  : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
124  BItor(BlockTraits::child_end(node->getEntry())) {}
125 
126  inline bool operator==(const Self& x) const {
127  assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
128  if (isRegionMode())
129  return Node.getInt() == x.Node.getInt();
130  else
131  return BItor == x.BItor;
132  }
133 
134  inline bool operator!=(const Self& x) const { return !operator==(x); }
135 
136  inline value_type operator*() const {
137  BlockT *BB = isRegionMode() ? getRegionSucc() : *BItor;
138  assert(!isExit(BB) && "Iterator out of range!");
139  return getISucc(BB);
140  }
141 
142  inline Self& operator++() {
143  if(isRegionMode()) {
144  // The Region only has 1 successor.
145  advanceRegionSucc();
146  } else {
147  // Skip the exit.
148  do
149  ++BItor;
150  while (BItor != BlockTraits::child_end(getNode()->getEntry())
151  && isExit(*BItor));
152  }
153  return *this;
154  }
155 
156  inline Self operator++(int) {
157  Self tmp = *this;
158  ++*this;
159  return tmp;
160  }
161 };
162 
163 //===----------------------------------------------------------------------===//
164 /// Flat RegionNode iterator.
165 ///
166 /// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
167 /// are contained in the Region and its subregions. This is close to a virtual
168 /// control flow graph of the Region.
169 template <class NodeRef, class BlockT, class RegionT>
170 class RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT> {
172  using SuccIterTy = typename BlockTraits::ChildIteratorType;
173 
174  NodeRef Node;
175  SuccIterTy Itor;
176 
177 public:
178  using iterator_category = std::forward_iterator_tag;
180  using difference_type = std::ptrdiff_t;
181  using pointer = value_type *;
183 
184  using Self = RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>;
185 
186  /// Create the iterator from a RegionNode.
187  ///
188  /// Note that the incoming node must be a bb node, otherwise it will trigger
189  /// an assertion when we try to get a BasicBlock.
191  : Node(node), Itor(BlockTraits::child_begin(node->getEntry())) {
192  assert(!Node->isSubRegion() &&
193  "Subregion node not allowed in flat iterating mode!");
194  assert(Node->getParent() && "A BB node must have a parent!");
195 
196  // Skip the exit block of the iterating region.
197  while (BlockTraits::child_end(Node->getEntry()) != Itor &&
198  Node->getParent()->getExit() == *Itor)
199  ++Itor;
200  }
201 
202  /// Create an end iterator
204  : Node(node), Itor(BlockTraits::child_end(node->getEntry())) {
205  assert(!Node->isSubRegion() &&
206  "Subregion node not allowed in flat iterating mode!");
207  }
208 
209  inline bool operator==(const Self& x) const {
210  assert(Node->getParent() == x.Node->getParent()
211  && "Cannot compare iterators of different regions!");
212 
213  return Itor == x.Itor && Node == x.Node;
214  }
215 
216  inline bool operator!=(const Self& x) const { return !operator==(x); }
217 
218  inline value_type operator*() const {
219  BlockT *BB = *Itor;
220 
221  // Get the iterating region.
222  RegionT *Parent = Node->getParent();
223 
224  // The only case that the successor reaches out of the region is it reaches
225  // the exit of the region.
226  assert(Parent->getExit() != BB && "iterator out of range!");
227 
228  return Parent->getBBNode(BB);
229  }
230 
231  inline Self& operator++() {
232  // Skip the exit block of the iterating region.
233  do
234  ++Itor;
235  while (Itor != succ_end(Node->getEntry())
236  && Node->getParent()->getExit() == *Itor);
237 
238  return *this;
239  }
240 
241  inline Self operator++(int) {
242  Self tmp = *this;
243  ++*this;
244  return tmp;
245  }
246 };
247 
248 template <class NodeRef, class BlockT, class RegionT>
251 }
252 
253 template <class NodeRef, class BlockT, class RegionT>
256 }
257 
258 //===--------------------------------------------------------------------===//
259 // RegionNode GraphTraits specialization so the bbs in the region can be
260 // iterate by generic graph iterators.
261 //
262 // NodeT can either be region node or const region node, otherwise child_begin
263 // and child_end fail.
264 
265 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \
266  template <> struct GraphTraits<NodeT *> { \
267  using NodeRef = NodeT *; \
268  using ChildIteratorType = RNSuccIterator<NodeRef, BlockT, RegionT>; \
269  static NodeRef getEntryNode(NodeRef N) { return N; } \
270  static inline ChildIteratorType child_begin(NodeRef N) { \
271  return RNSuccIterator<NodeRef, BlockT, RegionT>(N); \
272  } \
273  static inline ChildIteratorType child_end(NodeRef N) { \
274  return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true); \
275  } \
276  }; \
277  template <> struct GraphTraits<FlatIt<NodeT *>> { \
278  using NodeRef = NodeT *; \
279  using ChildIteratorType = \
280  RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>; \
281  static NodeRef getEntryNode(NodeRef N) { return N; } \
282  static inline ChildIteratorType child_begin(NodeRef N) { \
283  return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N); \
284  } \
285  static inline ChildIteratorType child_end(NodeRef N) { \
286  return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N, true); \
287  } \
288  }
289 
290 #define RegionGraphTraits(RegionT, NodeT) \
291  template <> struct GraphTraits<RegionT *> : public GraphTraits<NodeT *> { \
292  using nodes_iterator = df_iterator<NodeRef>; \
293  static NodeRef getEntryNode(RegionT *R) { \
294  return R->getNode(R->getEntry()); \
295  } \
296  static nodes_iterator nodes_begin(RegionT *R) { \
297  return nodes_iterator::begin(getEntryNode(R)); \
298  } \
299  static nodes_iterator nodes_end(RegionT *R) { \
300  return nodes_iterator::end(getEntryNode(R)); \
301  } \
302  }; \
303  template <> \
304  struct GraphTraits<FlatIt<RegionT *>> \
305  : public GraphTraits<FlatIt<NodeT *>> { \
306  using nodes_iterator = \
307  df_iterator<NodeRef, df_iterator_default_set<NodeRef>, false, \
308  GraphTraits<FlatIt<NodeRef>>>; \
309  static NodeRef getEntryNode(RegionT *R) { \
310  return R->getBBNode(R->getEntry()); \
311  } \
312  static nodes_iterator nodes_begin(RegionT *R) { \
313  return nodes_iterator::begin(getEntryNode(R)); \
314  } \
315  static nodes_iterator nodes_end(RegionT *R) { \
316  return nodes_iterator::end(getEntryNode(R)); \
317  } \
318  }
319 
320 RegionNodeGraphTraits(RegionNode, BasicBlock, Region);
321 RegionNodeGraphTraits(const RegionNode, BasicBlock, Region);
322 
323 RegionGraphTraits(Region, RegionNode);
324 RegionGraphTraits(const Region, const RegionNode);
325 
326 template <> struct GraphTraits<RegionInfo*>
328  using nodes_iterator =
331 
333  return GraphTraits<FlatIt<Region*>>::getEntryNode(RI->getTopLevelRegion());
334  }
335 
337  return nodes_iterator::begin(getEntryNode(RI));
338  }
339 
341  return nodes_iterator::end(getEntryNode(RI));
342  }
343 };
344 
345 template <> struct GraphTraits<RegionInfoPass*>
346  : public GraphTraits<RegionInfo *> {
347  using nodes_iterator =
350 
353  }
354 
357  }
358 
361  }
362 };
363 
364 } // end namespace llvm
365 
366 #endif // LLVM_ANALYSIS_REGIONITERATOR_H
RegionInfo.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::RegionInfoBase::getTopLevelRegion
RegionT * getTopLevelRegion() const
Definition: RegionInfo.h:866
llvm::RNSuccIterator::operator!=
bool operator!=(const Self &x) const
Definition: RegionIterator.h:134
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::RNSuccIterator
RNSuccIterator(NodeRef node)
Create the iterator from a RegionNode.
Definition: RegionIterator.h:190
llvm::RNSuccIterator::RNSuccIterator
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
Definition: RegionIterator.h:122
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::operator==
bool operator==(const Self &x) const
Definition: RegionIterator.h:209
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::value_type
NodeRef value_type
Definition: RegionIterator.h:179
llvm::FlatIt
Marker class to iterate over the elements of a Region in flat mode.
Definition: RegionInfo.h:112
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >
Flat RegionNode iterator.
Definition: RegionIterator.h:170
llvm::RNSuccIterator::operator==
bool operator==(const Self &x) const
Definition: RegionIterator.h:126
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::RNSuccIterator
RNSuccIterator(NodeRef node, bool)
Create an end iterator.
Definition: RegionIterator.h:203
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::GraphTraits< RegionInfoPass * >::nodes_end
static nodes_iterator nodes_end(RegionInfoPass *RI)
Definition: RegionIterator.h:359
llvm::RegionGraphTraits
RegionGraphTraits(Region, RegionNode)
llvm::RegionInfoPass::getRegionInfo
RegionInfo & getRegionInfo()
Definition: RegionInfo.h:951
DepthFirstIterator.h
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::pointer
value_type * pointer
Definition: RegionIterator.h:181
llvm::GraphTraits< RegionInfo * >::getEntryNode
static NodeRef getEntryNode(RegionInfo *RI)
Definition: RegionIterator.h:332
PointerIntPair.h
GraphTraits.h
llvm::GraphTraits< RegionInfoPass * >::getEntryNode
static NodeRef getEntryNode(RegionInfoPass *RI)
Definition: RegionIterator.h:351
llvm::RNSuccIterator::operator*
value_type operator*() const
Definition: RegionIterator.h:136
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::iterator_category
std::forward_iterator_tag iterator_category
Definition: RegionIterator.h:178
llvm::RNSuccIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: RegionIterator.h:40
llvm::GraphTraits< RegionInfo * >
Definition: RegionIterator.h:326
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::operator!=
bool operator!=(const Self &x) const
Definition: RegionIterator.h:216
CFG.h
llvm::GraphTraits< RegionInfo * >::nodes_end
static nodes_iterator nodes_end(RegionInfo *RI)
Definition: RegionIterator.h:340
llvm::RNSuccIterator::value_type
NodeRef value_type
Definition: RegionIterator.h:41
llvm::RNSuccIterator::difference_type
std::ptrdiff_t difference_type
Definition: RegionIterator.h:42
llvm::succ_begin
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:99
node
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
Definition: README-SSE.txt:406
llvm::RNSuccIterator::reference
value_type & reference
Definition: RegionIterator.h:44
llvm::RNSuccIterator::operator++
Self & operator++()
Definition: RegionIterator.h:142
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::operator++
Self & operator++()
Definition: RegionIterator.h:231
llvm::RNSuccIterator::RNSuccIterator
RNSuccIterator(NodeRef node)
Create begin iterator of a RegionNode.
Definition: RegionIterator.h:109
llvm::RegionNodeGraphTraits
RegionNodeGraphTraits(RegionNode, BasicBlock, Region)
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::RegionInfoPass
Definition: RegionInfo.h:942
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::operator++
Self operator++(int)
Definition: RegionIterator.h:241
llvm::RegionInfo
Definition: RegionInfo.h:900
llvm::RNSuccIterator
Hierarchical RegionNode successor iterator.
Definition: RegionIterator.h:38
Node
Definition: ItaniumDemangle.h:234
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::reference
value_type & reference
Definition: RegionIterator.h:182
x
TODO unsigned x
Definition: README.txt:10
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::difference_type
std::ptrdiff_t difference_type
Definition: RegionIterator.h:180
llvm::RNSuccIterator< FlatIt< NodeRef >, BlockT, RegionT >::operator*
value_type operator*() const
Definition: RegionIterator.h:218
llvm::GraphTraits< RegionInfo * >::nodes_begin
static nodes_iterator nodes_begin(RegionInfo *RI)
Definition: RegionIterator.h:336
llvm::PointerIntPair< NodeRef, 2, ItMode >
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::GraphTraits< RegionInfoPass * >::nodes_begin
static nodes_iterator nodes_begin(RegionInfoPass *RI)
Definition: RegionIterator.h:355
llvm::GraphTraits< FlatIt< RegionNode * > >::NodeRef
typename FlatIt< RegionNode * > ::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:78
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::RNSuccIterator::operator++
Self operator++(int)
Definition: RegionIterator.h:156
llvm::RNSuccIterator::pointer
value_type * pointer
Definition: RegionIterator.h:43