LLVM 19.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
28
29namespace llvm {
30
31class 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
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
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.
98public:
99 /// Postorder list iterators.
100 typedef std::vector<BasicBlock*>::const_iterator POIterator;
101 typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
102
104
105private:
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
114public:
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(const 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.
173private:
174 LoopBlocksDFS DFS;
175
176public:
177 LoopBlocksRPO(Loop *Container) : DFS(Container) {}
178
179 /// Traverse the loop blocks and store the DFS result.
180 void perform(const 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.
192public:
194 // These functions are defined below.
195 bool insertEdge(std::optional<BasicBlock *> From, BasicBlock *To);
196 void finishPostorder(BasicBlock *BB);
197};
198
199/// Traverse the blocks in a loop using a depth-first search.
201public:
202 /// Graph traversal iterator.
204
205private:
206 LoopBlocksDFS &DFS;
207 const LoopInfo *LI;
208
209public:
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
248 std::optional<BasicBlock *> From, BasicBlock *To) {
249 return LBT.visitPreorder(To);
250}
251
254 LBT.finishPostorder(BB);
255}
256
257} // End namespace llvm
258
259#endif
basic Basic Alias true
BlockVerifier::State From
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:155
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:151
iterator end()
Definition: DenseMap.h:84
void reserve(size_type NumEntries)
Grow the densemap so that it can contain at least NumEntries items before resizing again.
Definition: DenseMap.h:103
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
unsigned getNumBlocks() const
Get the number of blocks in this loop in constant time.
BlockT * getHeader() const
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
bool hasPreorder(BasicBlock *BB) const
Return true if this block has been preorder visited.
Definition: LoopIterator.h:143
unsigned getPostorder(BasicBlock *BB) const
Get a block's postorder number.
Definition: LoopIterator.h:152
std::vector< BasicBlock * >::const_reverse_iterator RPOIterator
Definition: LoopIterator.h:101
bool hasPostorder(BasicBlock *BB) const
Return true if this block has a postorder number.
Definition: LoopIterator.h:146
unsigned getRPO(BasicBlock *BB) const
Get a block's reverse postorder number.
Definition: LoopIterator.h:160
Loop * getLoop() const
Definition: LoopIterator.h:120
LoopBlocksDFS(Loop *Container)
Definition: LoopIterator.h:115
bool isComplete() const
Return true if postorder numbers are assigned to all loop blocks.
Definition: LoopIterator.h:126
POIterator beginPostorder() const
Iterate over the cached postorder blocks.
Definition: LoopIterator.h:129
POIterator endPostorder() const
Definition: LoopIterator.h:133
std::vector< BasicBlock * >::const_iterator POIterator
Postorder list iterators.
Definition: LoopIterator.h:100
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1222
RPOIterator endRPO() const
Definition: LoopIterator.h:140
Wrapper class to LoopBlocksDFS that provides a standard begin()/end() interface for the DFS reverse p...
Definition: LoopIterator.h:172
LoopBlocksDFS::RPOIterator end() const
Definition: LoopIterator.h:186
LoopBlocksDFS::RPOIterator begin() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:185
LoopBlocksRPO(Loop *Container)
Definition: LoopIterator.h:177
void perform(const LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopIterator.h:180
Traverse the blocks in a loop using a depth-first search.
Definition: LoopIterator.h:200
bool visitPreorder(BasicBlock *BB)
Called by po_iterator upon reaching a block via a CFG edge.
Definition: LoopIterator.h:231
void finishPostorder(BasicBlock *BB)
Called by po_iterator each time it advances, indicating a block's postorder.
Definition: LoopIterator.h:240
LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo)
Definition: LoopIterator.h:210
po_iterator< BasicBlock *, LoopBlocksTraversal, true > POTIterator
Graph traversal iterator.
Definition: LoopIterator.h:203
POTIterator begin()
Postorder traversal over the graph.
Definition: LoopIterator.h:216
WrappedSuccIterator(succ_iterator Begin, const Loop *L)
Definition: LoopIterator.h:58
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Specialization of filter_iterator_base for forward iteration only.
Definition: STLExtras.h:506
CRTP base class for adapting an iterator to a different type.
Definition: iterator.h:237
Default po_iterator_storage implementation with an internal set object.
bool insertEdge(std::optional< NodeRef > From, NodeRef To)
void finishPostorder(NodeRef BB)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Interval::succ_iterator succ_end(Interval *I)
Definition: Interval.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:99
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
SuccIterator< Instruction, BasicBlock > succ_iterator
Definition: CFG.h:242
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:581
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
constexpr uint64_t NextPowerOf2(uint64_t A)
Returns the next power of two (in 64-bits) that is strictly greater than A.
Definition: MathExtras.h:349
#define N
bool operator()(NodeRef N) const
Definition: LoopIterator.h:65
static ChildIteratorType child_end(NodeRef Node)
Definition: LoopIterator.h:84
std::pair< const Loop *, BasicBlock * > NodeRef
Definition: LoopIterator.h:41
static ChildIteratorType child_begin(NodeRef Node)
Definition: LoopIterator.h:76
static NodeRef getEntryNode(const Loop &G)
Definition: LoopIterator.h:74