LLVM  13.0.0git
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:
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.
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.
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:
174  LoopBlocksDFS DFS;
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.
197 };
198 
199 /// Traverse the blocks in a loop using a depth-first search.
201 public:
202  /// Graph traversal iterator.
204 
205 private:
206  LoopBlocksDFS &DFS;
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.
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  }
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
llvm::SuccIterator
Definition: CFG.h:139
llvm::NextPowerOf2
uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:683
llvm::LoopBodyTraits::WrappedSuccIterator
Definition: LoopIterator.h:45
llvm::LoopBlocksTraversal
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
llvm
Definition: AllocatorList.h:23
llvm::LoopBodyTraits::WrappedSuccIterator::WrappedSuccIterator
WrappedSuccIterator(succ_iterator Begin, const Loop *L)
Definition: LoopIterator.h:58
llvm::succ_end
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.h:102
llvm::LoopBodyTraits::LoopBodyFilter
Definition: LoopIterator.h:64
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
llvm::LoopBlocksRPO::end
LoopBlocksDFS::RPOIterator end() const
Definition: LoopIterator.h:186
llvm::iterator_adaptor_base< WrappedSuccIterator, succ_iterator, std::iterator_traits< succ_iterator >::iterator_category, NodeRef, std::ptrdiff_t, NodeRef *, NodeRef >::I
succ_iterator I
Definition: iterator.h:217
llvm::LoopBlocksTraversal::visitPreorder
bool visitPreorder(BasicBlock *BB)
Called by po_iterator upon reaching a block via a CFG edge.
Definition: LoopIterator.h:231
llvm::po_iterator_storage::finishPostorder
void finishPostorder(NodeRef BB)
Definition: PostOrderIterator.h:69
llvm::LoopBlocksTraversal::POTIterator
po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator
Graph traversal iterator.
Definition: LoopIterator.h:203
llvm::po_ext_end
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
Definition: PostOrderIterator.h:205
llvm::LoopBlocksDFS::getRPO
unsigned getRPO(BasicBlock *BB) const
Get a block's reverse postorder number.
Definition: LoopIterator.h:160
llvm::filter_iterator_impl
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:412
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::iterator_adaptor_base
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:211
llvm::Optional
Definition: APInt.h:33
llvm::DenseMapBase::count
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:145
llvm::LoopBlocksTraversal::end
POTIterator end()
Definition: LoopIterator.h:221
llvm::po_iterator_storage
Default po_iterator_storage implementation with an internal set object.
Definition: PostOrderIterator.h:58
llvm::LoopBase::getNumBlocks
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
Definition: LoopInfo.h:185
llvm::LoopBlocksDFS::beginRPO
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::LoopBlocksDFS::isComplete
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
llvm::LoopBlocksRPO
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
llvm::LoopBlocksTraversal::finishPostorder
void finishPostorder(BasicBlock *BB)
Called by po_iterator each time it advances, indicating a block's postorder.
Definition: LoopIterator.h:240
llvm::LoopBlocksDFS::getLoop
Loop * getLoop() const
Definition: LoopIterator.h:120
llvm::LoopBlocksDFS::getPostorder
unsigned getPostorder(BasicBlock *BB) const
Get a block's postorder number.
Definition: LoopIterator.h:152
llvm::LoopBodyTraits::NodeRef
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41
llvm::LoopBodyTraits::WrappedSuccIterator::operator*
NodeRef operator*() const
Definition: LoopIterator.h:61
llvm::LoopBlocksTraversal::begin
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
llvm::po_ext_begin
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
Definition: PostOrderIterator.h:200
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
llvm::LoopBlocksRPO::begin
LoopBlocksDFS::RPOIterator begin() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:185
LoopInfo.h
llvm::LoopBlocksDFS::RPOIterator
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
llvm::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::DenseMapBase::clear
void clear()
Definition: DenseMap.h:111
llvm::LoopBodyTraits
Definition: LoopIterator.h:40
llvm::DenseMap< BasicBlock *, unsigned >
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:964
llvm::LoopBodyTraits::child_end
static ChildIteratorType child_end(NodeRef Node)
Definition: LoopIterator.h:84
I
#define I(x, y, z)
Definition: MD5.cpp:59
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
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1149
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::po_iterator
Definition: PostOrderIterator.h:95
llvm::LoopBlocksRPO::LoopBlocksRPO
LoopBlocksRPO(Loop *Container)
Definition: LoopIterator.h:177
llvm::LoopBlocksDFS::POIterator
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
llvm::LoopBlocksTraversal::LoopBlocksTraversal
LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo)
Definition: LoopIterator.h:210
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::LoopBodyTraits::ChildIteratorType
filter_iterator< WrappedSuccIterator, LoopBodyFilter > ChildIteratorType
Definition: LoopIterator.h:72
Node
Definition: ItaniumDemangle.h:114
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::make_filter_range
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:486
llvm::LoopBlocksDFS::clear
void clear()
Definition: LoopIterator.h:164
llvm::LoopBlocksDFS::hasPreorder
bool hasPreorder(BasicBlock *BB) const
Return true if this block has been preorder visited.
Definition: LoopIterator.h:143
llvm::LoopBodyTraits::getEntryNode
static NodeRef getEntryNode(const Loop &G)
Definition: LoopIterator.h:74
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::LoopBlocksDFS::LoopBlocksDFS
LoopBlocksDFS(Loop *Container)
Definition: LoopIterator.h:115
llvm::LoopBodyTraits::child_begin
static ChildIteratorType child_begin(NodeRef Node)
Definition: LoopIterator.h:76
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::LoopBlocksDFS::beginPostorder
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
llvm::LoopBlocksDFS::hasPostorder
bool hasPostorder(BasicBlock *BB) const
Return true if this block has a postorder number.
Definition: LoopIterator.h:146
PostOrderIterator.h
N
#define N
llvm::DenseMapBase::reserve
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:104
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::succ_iterator
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:243
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::LoopBodyTraits::LoopBodyFilter::operator()
bool operator()(NodeRef N) const
Definition: LoopIterator.h:65
llvm::LoopBlocksRPO::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
llvm::po_iterator_storage< LoopBlocksTraversal, true >::po_iterator_storage
po_iterator_storage(LoopBlocksTraversal &lbs)
Definition: LoopIterator.h:193
llvm::LoopBlocksDFS::endPostorder
POIterator endPostorder() const
Definition: LoopIterator.h:133
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1797
llvm::po_iterator_storage::insertEdge
bool insertEdge(Optional< NodeRef > From, NodeRef To)
Definition: PostOrderIterator.h:64