LLVM  9.0.0svn
LoopIterator.h
Go to the documentation of this file.
1 //===--------- LoopIterator.h - Iterate over loop blocks --------*- 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 iterators to visit the basic blocks within a loop.
9 //
10 // These iterators currently visit blocks within subloops as well.
11 // Unfortunately we have no efficient way of summarizing loop exits which would
12 // allow skipping subloops during traversal.
13 //
14 // If you want to visit all blocks in a loop and don't need an ordered traveral,
15 // use Loop::block_begin() instead.
16 //
17 // This is intentionally designed to work with ill-formed loops in which the
18 // backedge has been deleted. The only prerequisite is that all blocks
19 // contained within the loop according to the most recent LoopInfo analysis are
20 // reachable from the loop header.
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
24 #define LLVM_ANALYSIS_LOOPITERATOR_H
25 
27 #include "llvm/Analysis/LoopInfo.h"
28 
29 namespace llvm {
30 
31 class LoopBlocksTraversal;
32 
33 // A traits type that is intended to be used in graph algorithms. The graph
34 // traits starts at the loop header, and traverses the BasicBlocks that are in
35 // the loop body, but not the loop header. Since the loop header is skipped,
36 // the back edges are excluded.
37 //
38 // TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
39 // LoopBodyTraits, so that insertEdge doesn't have to be specialized.
41  using NodeRef = std::pair<const Loop *, BasicBlock *>;
42 
43  // This wraps a const Loop * into the iterator, so we know which edges to
44  // filter out.
46  : public iterator_adaptor_base<
47  WrappedSuccIterator, succ_iterator,
48  typename std::iterator_traits<succ_iterator>::iterator_category,
49  NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
52  typename std::iterator_traits<succ_iterator>::iterator_category,
53  NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
54 
55  const Loop *L;
56 
57  public:
58  WrappedSuccIterator(succ_iterator Begin, const Loop *L)
59  : BaseT(Begin), L(L) {}
60 
61  NodeRef operator*() const { return {L, *I}; }
62  };
63 
64  struct LoopBodyFilter {
65  bool operator()(NodeRef N) const {
66  const Loop *L = N.first;
67  return N.second != L->getHeader() && L->contains(N.second);
68  }
69  };
70 
71  using ChildIteratorType =
73 
74  static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
75 
77  return make_filter_range(make_range<WrappedSuccIterator>(
78  {succ_begin(Node.second), Node.first},
79  {succ_end(Node.second), Node.first}),
81  .begin();
82  }
83 
85  return make_filter_range(make_range<WrappedSuccIterator>(
86  {succ_begin(Node.second), Node.first},
87  {succ_end(Node.second), Node.first}),
89  .end();
90  }
91 };
92 
93 /// Store the result of a depth first search within basic blocks contained by a
94 /// single loop.
95 ///
96 /// TODO: This could be generalized for any CFG region, or the entire CFG.
98 public:
99  /// Postorder list iterators.
100  typedef std::vector<BasicBlock*>::const_iterator POIterator;
101  typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
102 
103  friend class LoopBlocksTraversal;
104 
105 private:
106  Loop *L;
107 
108  /// Map each block to its postorder number. A block is only mapped after it is
109  /// preorder visited by DFS. It's postorder number is initially zero and set
110  /// to nonzero after it is finished by postorder traversal.
112  std::vector<BasicBlock*> PostBlocks;
113 
114 public:
115  LoopBlocksDFS(Loop *Container) :
116  L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
117  PostBlocks.reserve(Container->getNumBlocks());
118  }
119 
120  Loop *getLoop() const { return L; }
121 
122  /// Traverse the loop blocks and store the DFS result.
123  void perform(LoopInfo *LI);
124 
125  /// Return true if postorder numbers are assigned to all loop blocks.
126  bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
127 
128  /// Iterate over the cached postorder blocks.
129  POIterator beginPostorder() const {
130  assert(isComplete() && "bad loop DFS");
131  return PostBlocks.begin();
132  }
133  POIterator endPostorder() const { return PostBlocks.end(); }
134 
135  /// Reverse iterate over the cached postorder blocks.
136  RPOIterator beginRPO() const {
137  assert(isComplete() && "bad loop DFS");
138  return PostBlocks.rbegin();
139  }
140  RPOIterator endRPO() const { return PostBlocks.rend(); }
141 
142  /// Return true if this block has been preorder visited.
143  bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
144 
145  /// Return true if this block has a postorder number.
146  bool hasPostorder(BasicBlock *BB) const {
148  return I != PostNumbers.end() && I->second;
149  }
150 
151  /// Get a block's postorder number.
152  unsigned getPostorder(BasicBlock *BB) const {
154  assert(I != PostNumbers.end() && "block not visited by DFS");
155  assert(I->second && "block not finished by DFS");
156  return I->second;
157  }
158 
159  /// Get a block's reverse postorder number.
160  unsigned getRPO(BasicBlock *BB) const {
161  return 1 + PostBlocks.size() - getPostorder(BB);
162  }
163 
164  void clear() {
165  PostNumbers.clear();
166  PostBlocks.clear();
167  }
168 };
169 
170 /// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
171 /// interface for the DFS reverse post-order traversal of blocks in a loop body.
173 private:
175 
176 public:
177  LoopBlocksRPO(Loop *Container) : DFS(Container) {}
178 
179  /// Traverse the loop blocks and store the DFS result.
180  void perform(LoopInfo *LI) {
181  DFS.perform(LI);
182  }
183 
184  /// Reverse iterate over the cached postorder blocks.
185  LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
186  LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
187 };
188 
189 /// Specialize po_iterator_storage to record postorder numbers.
191  LoopBlocksTraversal &LBT;
192 public:
194  // These functions are defined below.
195  bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
196  void finishPostorder(BasicBlock *BB);
197 };
198 
199 /// Traverse the blocks in a loop using a depth-first search.
201 public:
202  /// Graph traversal iterator.
204 
205 private:
207  LoopInfo *LI;
208 
209 public:
211  DFS(Storage), LI(LInfo) {}
212 
213  /// Postorder traversal over the graph. This only needs to be done once.
214  /// po_iterator "automatically" calls back to visitPreorder and
215  /// finishPostorder to record the DFS result.
216  POTIterator begin() {
217  assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
218  assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
219  return po_ext_begin(DFS.L->getHeader(), *this);
220  }
221  POTIterator end() {
222  // po_ext_end interface requires a basic block, but ignores its value.
223  return po_ext_end(DFS.L->getHeader(), *this);
224  }
225 
226  /// Called by po_iterator upon reaching a block via a CFG edge. If this block
227  /// is contained in the loop and has not been visited, then mark it preorder
228  /// visited and return true.
229  ///
230  /// TODO: If anyone is interested, we could record preorder numbers here.
232  if (!DFS.L->contains(LI->getLoopFor(BB)))
233  return false;
234 
235  return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
236  }
237 
238  /// Called by po_iterator each time it advances, indicating a block's
239  /// postorder.
241  assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
242  DFS.PostBlocks.push_back(BB);
243  DFS.PostNumbers[BB] = DFS.PostBlocks.size();
244  }
245 };
246 
249  return LBT.visitPreorder(To);
250 }
251 
254  LBT.finishPostorder(BB);
255 }
256 
257 } // End namespace llvm
258 
259 #endif
bool hasPostorder(BasicBlock *BB) const
Return true if this block has a postorder number.
Definition: LoopIterator.h:146
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
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
Loop * getLoop() const
Definition: LoopIterator.h:120
LoopBlocksDFS(Loop *Container)
Definition: LoopIterator.h:115
block Block Frequency true
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:221
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:901
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
bool hasPreorder(BasicBlock *BB) const
Return true if this block has been preorder visited.
Definition: LoopIterator.h:143
void finishPostorder(NodeRef BB)
RPOIterator endRPO() const
Definition: LoopIterator.h:140
BlockT * getHeader() const
Definition: LoopInfo.h:102
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
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1064
static ChildIteratorType child_end(NodeRef Node)
Definition: LoopIterator.h:84
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:105
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:176
po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator
Graph traversal iterator.
Definition: LoopIterator.h:203
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
LoopBlocksDFS::RPOIterator begin() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:185
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:205
WrappedSuccIterator(succ_iterator Begin, const Loop *L)
Definition: LoopIterator.h:58
Default po_iterator_storage implementation with an internal set object.
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again...
Definition: DenseMap.h:129
bool insertEdge(Optional< NodeRef > From, NodeRef To)
static NodeRef getEntryNode(const Loop &G)
Definition: LoopIterator.h:74
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:639
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:112
unsigned getRPO(BasicBlock *BB) const
Get a block&#39;s reverse postorder number.
Definition: LoopIterator.h:160
BlockVerifier::State From
static ChildIteratorType child_begin(NodeRef Node)
Definition: LoopIterator.h:76
bool visitPreorder(BasicBlock *BB)
Called by po_iterator upon reaching a block via a CFG edge.
Definition: LoopIterator.h:231
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
Store the result of a depth first search within basic blocks contained by a single loop...
Definition: LoopIterator.h:97
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
POIterator endPostorder() const
Definition: LoopIterator.h:133
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:165
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:240
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:510
#define N
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
iterator end()
Definition: DenseMap.h:108
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
LoopBlocksRPO(Loop *Container)
Definition: LoopIterator.h:177
LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo)
Definition: LoopIterator.h:210
iterator_range< filter_iterator< detail::IterOfRange< RangeT >, PredicateT > > make_filter_range(RangeT &&Range, PredicateT Pred)
Convenience function that takes a range of elements and a predicate, and return a new filter_iterator...
Definition: STLExtras.h:434
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:171
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
void finishPostorder(BasicBlock *BB)
Called by po_iterator each time it advances, indicating a block&#39;s postorder.
Definition: LoopIterator.h:240
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:360
unsigned getPostorder(BasicBlock *BB) const
Get a block&#39;s postorder number.
Definition: LoopIterator.h:152
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
LoopBlocksDFS::RPOIterator end() const
Definition: LoopIterator.h:186
bool operator()(NodeRef N) const
Definition: LoopIterator.h:65