/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/LoopIterator.h
Line | Count | Source (jump to first uncovered line) |
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 | 0 | : BaseT(Begin), L(L) {} |
60 | | |
61 | 0 | NodeRef operator*() const { return {L, *I}; } |
62 | | }; |
63 | | |
64 | | struct LoopBodyFilter { |
65 | 0 | bool operator()(NodeRef N) const { |
66 | 0 | const Loop *L = N.first; |
67 | 0 | return N.second != L->getHeader() && L->contains(N.second); |
68 | 0 | } |
69 | | }; |
70 | | |
71 | | using ChildIteratorType = |
72 | | filter_iterator<WrappedSuccIterator, LoopBodyFilter>; |
73 | | |
74 | 0 | static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; } |
75 | | |
76 | 0 | static ChildIteratorType child_begin(NodeRef Node) { |
77 | 0 | return make_filter_range(make_range<WrappedSuccIterator>( |
78 | 0 | {succ_begin(Node.second), Node.first}, |
79 | 0 | {succ_end(Node.second), Node.first}), |
80 | 0 | LoopBodyFilter{}) |
81 | 0 | .begin(); |
82 | 0 | } |
83 | | |
84 | 0 | static ChildIteratorType child_end(NodeRef Node) { |
85 | 0 | return make_filter_range(make_range<WrappedSuccIterator>( |
86 | 0 | {succ_begin(Node.second), Node.first}, |
87 | 0 | {succ_end(Node.second), Node.first}), |
88 | 0 | LoopBodyFilter{}) |
89 | 0 | .end(); |
90 | 0 | } |
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 | 858k | L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { |
117 | 858k | PostBlocks.reserve(Container->getNumBlocks()); |
118 | 858k | } |
119 | | |
120 | 0 | 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 | 0 | bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } |
127 | | |
128 | | /// Iterate over the cached postorder blocks. |
129 | 143 | POIterator beginPostorder() const { |
130 | 143 | assert(isComplete() && "bad loop DFS"); |
131 | 143 | return PostBlocks.begin(); |
132 | 143 | } |
133 | 143 | POIterator endPostorder() const { return PostBlocks.end(); } |
134 | | |
135 | | /// Reverse iterate over the cached postorder blocks. |
136 | 852k | RPOIterator beginRPO() const { |
137 | 852k | assert(isComplete() && "bad loop DFS"); |
138 | 852k | return PostBlocks.rbegin(); |
139 | 852k | } |
140 | 853k | RPOIterator endRPO() const { return PostBlocks.rend(); } |
141 | | |
142 | | /// Return true if this block has been preorder visited. |
143 | 0 | bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } |
144 | | |
145 | | /// Return true if this block has a postorder number. |
146 | 0 | bool hasPostorder(BasicBlock *BB) const { |
147 | 0 | DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); |
148 | 0 | return I != PostNumbers.end() && I->second; |
149 | 0 | } |
150 | | |
151 | | /// Get a block's postorder number. |
152 | 0 | unsigned getPostorder(BasicBlock *BB) const { |
153 | 0 | DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); |
154 | 0 | assert(I != PostNumbers.end() && "block not visited by DFS"); |
155 | 0 | assert(I->second && "block not finished by DFS"); |
156 | 0 | return I->second; |
157 | 0 | } |
158 | | |
159 | | /// Get a block's reverse postorder number. |
160 | 0 | unsigned getRPO(BasicBlock *BB) const { |
161 | 0 | return 1 + PostBlocks.size() - getPostorder(BB); |
162 | 0 | } |
163 | | |
164 | 0 | void clear() { |
165 | 0 | PostNumbers.clear(); |
166 | 0 | PostBlocks.clear(); |
167 | 0 | } |
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 | 763k | LoopBlocksRPO(Loop *Container) : DFS(Container) {} |
178 | | |
179 | | /// Traverse the loop blocks and store the DFS result. |
180 | 762k | void perform(LoopInfo *LI) { |
181 | 762k | DFS.perform(LI); |
182 | 762k | } |
183 | | |
184 | | /// Reverse iterate over the cached postorder blocks. |
185 | 762k | LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); } |
186 | 762k | 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 | 1.71M | po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} |
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. |
200 | | class LoopBlocksTraversal { |
201 | | public: |
202 | | /// Graph traversal iterator. |
203 | | typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; |
204 | | |
205 | | private: |
206 | | LoopBlocksDFS &DFS; |
207 | | LoopInfo *LI; |
208 | | |
209 | | public: |
210 | | LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : |
211 | 856k | 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 | 856k | POTIterator begin() { |
217 | 856k | assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); |
218 | 856k | assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); |
219 | 856k | return po_ext_begin(DFS.L->getHeader(), *this); |
220 | 856k | } |
221 | 856k | POTIterator end() { |
222 | 856k | // po_ext_end interface requires a basic block, but ignores its value. |
223 | 856k | return po_ext_end(DFS.L->getHeader(), *this); |
224 | 856k | } |
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 | 6.51M | bool visitPreorder(BasicBlock *BB) { |
232 | 6.51M | if (!DFS.L->contains(LI->getLoopFor(BB))) |
233 | 1.14M | return false; |
234 | 5.36M | |
235 | 5.36M | return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; |
236 | 5.36M | } |
237 | | |
238 | | /// Called by po_iterator each time it advances, indicating a block's |
239 | | /// postorder. |
240 | 3.29M | void finishPostorder(BasicBlock *BB) { |
241 | 3.29M | assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); |
242 | 3.29M | DFS.PostBlocks.push_back(BB); |
243 | 3.29M | DFS.PostNumbers[BB] = DFS.PostBlocks.size(); |
244 | 3.29M | } |
245 | | }; |
246 | | |
247 | | inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( |
248 | 6.51M | Optional<BasicBlock *> From, BasicBlock *To) { |
249 | 6.51M | return LBT.visitPreorder(To); |
250 | 6.51M | } |
251 | | |
252 | | inline void po_iterator_storage<LoopBlocksTraversal, true>:: |
253 | 3.29M | finishPostorder(BasicBlock *BB) { |
254 | 3.29M | LBT.finishPostorder(BB); |
255 | 3.29M | } |
256 | | |
257 | | } // End namespace llvm |
258 | | |
259 | | #endif |