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 | |
26 | #include "llvm/ADT/PostOrderIterator.h" |
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. |
40 | struct LoopBodyTraits { |
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. |
45 | class WrappedSuccIterator |
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> { |
50 | using BaseT = iterator_adaptor_base< |
51 | WrappedSuccIterator, succ_iterator, |
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(BB: N.second); |
68 | } |
69 | }; |
70 | |
71 | using ChildIteratorType = |
72 | filter_iterator<WrappedSuccIterator, LoopBodyFilter>; |
73 | |
74 | static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; } |
75 | |
76 | static ChildIteratorType child_begin(NodeRef Node) { |
77 | return make_filter_range(Range: make_range<WrappedSuccIterator>( |
78 | x: {succ_begin(BB: Node.second), Node.first}, |
79 | y: {succ_end(BB: Node.second), Node.first}), |
80 | Pred: LoopBodyFilter{}) |
81 | .begin(); |
82 | } |
83 | |
84 | static ChildIteratorType child_end(NodeRef Node) { |
85 | return make_filter_range(Range: make_range<WrappedSuccIterator>( |
86 | x: {succ_begin(BB: Node.second), Node.first}, |
87 | y: {succ_end(BB: Node.second), Node.first}), |
88 | Pred: LoopBodyFilter{}) |
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. |
97 | class LoopBlocksDFS { |
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. |
111 | DenseMap<BasicBlock*, unsigned> PostNumbers; |
112 | std::vector<BasicBlock*> PostBlocks; |
113 | |
114 | public: |
115 | LoopBlocksDFS(Loop *Container) : |
116 | L(Container), PostNumbers(NextPowerOf2(A: Container->getNumBlocks())) { |
117 | PostBlocks.reserve(n: 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. |
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(Val: BB); } |
144 | |
145 | /// Return true if this block has a postorder number. |
146 | bool hasPostorder(BasicBlock *BB) const { |
147 | DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(Val: BB); |
148 | return I != PostNumbers.end() && I->second; |
149 | } |
150 | |
151 | /// Get a block's postorder number. |
152 | unsigned getPostorder(BasicBlock *BB) const { |
153 | DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(Val: BB); |
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. |
172 | class LoopBlocksRPO { |
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(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. |
190 | template<> class po_iterator_storage<LoopBlocksTraversal, true> { |
191 | LoopBlocksTraversal &LBT; |
192 | public: |
193 | po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} |
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. |
200 | class LoopBlocksTraversal { |
201 | public: |
202 | /// Graph traversal iterator. |
203 | typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; |
204 | |
205 | private: |
206 | LoopBlocksDFS &DFS; |
207 | const LoopInfo *LI; |
208 | |
209 | public: |
210 | LoopBlocksTraversal(LoopBlocksDFS &Storage, const LoopInfo *LInfo) : |
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(G: DFS.L->getHeader(), S&: *this); |
220 | } |
221 | POTIterator end() { |
222 | // po_ext_end interface requires a basic block, but ignores its value. |
223 | return po_ext_end(G: DFS.L->getHeader(), S&: *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. |
231 | bool visitPreorder(BasicBlock *BB) { |
232 | if (!DFS.L->contains(L: LI->getLoopFor(BB))) |
233 | return false; |
234 | |
235 | return DFS.PostNumbers.insert(KV: std::make_pair(x&: BB, y: 0)).second; |
236 | } |
237 | |
238 | /// Called by po_iterator each time it advances, indicating a block's |
239 | /// postorder. |
240 | void finishPostorder(BasicBlock *BB) { |
241 | assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder" ); |
242 | DFS.PostBlocks.push_back(x: BB); |
243 | DFS.PostNumbers[BB] = DFS.PostBlocks.size(); |
244 | } |
245 | }; |
246 | |
247 | inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( |
248 | std::optional<BasicBlock *> From, BasicBlock *To) { |
249 | return LBT.visitPreorder(BB: To); |
250 | } |
251 | |
252 | inline void po_iterator_storage<LoopBlocksTraversal, true>:: |
253 | finishPostorder(BasicBlock *BB) { |
254 | LBT.finishPostorder(BB); |
255 | } |
256 | |
257 | } // End namespace llvm |
258 | |
259 | #endif |
260 | |