Line data Source code
1 : //===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : // This file defines iterators to visit the basic blocks within a loop.
10 : //
11 : // These iterators currently visit blocks within subloops as well.
12 : // Unfortunately we have no efficient way of summarizing loop exits which would
13 : // allow skipping subloops during traversal.
14 : //
15 : // If you want to visit all blocks in a loop and don't need an ordered traveral,
16 : // use Loop::block_begin() instead.
17 : //
18 : // This is intentionally designed to work with ill-formed loops in which the
19 : // backedge has been deleted. The only prerequisite is that all blocks
20 : // contained within the loop according to the most recent LoopInfo analysis are
21 : // reachable from the loop header.
22 : //===----------------------------------------------------------------------===//
23 :
24 : #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
25 : #define LLVM_ANALYSIS_LOOPITERATOR_H
26 :
27 : #include "llvm/ADT/PostOrderIterator.h"
28 : #include "llvm/Analysis/LoopInfo.h"
29 :
30 : namespace llvm {
31 :
32 : class LoopBlocksTraversal;
33 :
34 : // A traits type that is intended to be used in graph algorithms. The graph
35 : // traits starts at the loop header, and traverses the BasicBlocks that are in
36 : // the loop body, but not the loop header. Since the loop header is skipped,
37 : // the back edges are excluded.
38 : //
39 : // TODO: Explore the possibility to implement LoopBlocksTraversal in terms of
40 : // LoopBodyTraits, so that insertEdge doesn't have to be specialized.
41 : struct LoopBodyTraits {
42 : using NodeRef = std::pair<const Loop *, BasicBlock *>;
43 :
44 : // This wraps a const Loop * into the iterator, so we know which edges to
45 : // filter out.
46 : class WrappedSuccIterator
47 : : public iterator_adaptor_base<
48 : WrappedSuccIterator, succ_iterator,
49 : typename std::iterator_traits<succ_iterator>::iterator_category,
50 : NodeRef, std::ptrdiff_t, NodeRef *, NodeRef> {
51 : using BaseT = iterator_adaptor_base<
52 : WrappedSuccIterator, succ_iterator,
53 : typename std::iterator_traits<succ_iterator>::iterator_category,
54 : NodeRef, std::ptrdiff_t, NodeRef *, NodeRef>;
55 :
56 : const Loop *L;
57 :
58 : public:
59 : WrappedSuccIterator(succ_iterator Begin, const Loop *L)
60 : : BaseT(Begin), L(L) {}
61 :
62 : NodeRef operator*() const { return {L, *I}; }
63 : };
64 :
65 : struct LoopBodyFilter {
66 : bool operator()(NodeRef N) const {
67 : const Loop *L = N.first;
68 : return N.second != L->getHeader() && L->contains(N.second);
69 : }
70 : };
71 :
72 : using ChildIteratorType =
73 : filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
74 :
75 : static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
76 :
77 : static ChildIteratorType child_begin(NodeRef Node) {
78 : return make_filter_range(make_range<WrappedSuccIterator>(
79 : {succ_begin(Node.second), Node.first},
80 : {succ_end(Node.second), Node.first}),
81 : LoopBodyFilter{})
82 : .begin();
83 : }
84 :
85 : static ChildIteratorType child_end(NodeRef Node) {
86 : return make_filter_range(make_range<WrappedSuccIterator>(
87 : {succ_begin(Node.second), Node.first},
88 : {succ_end(Node.second), Node.first}),
89 : LoopBodyFilter{})
90 : .end();
91 : }
92 : };
93 :
94 : /// Store the result of a depth first search within basic blocks contained by a
95 : /// single loop.
96 : ///
97 : /// TODO: This could be generalized for any CFG region, or the entire CFG.
98 : class LoopBlocksDFS {
99 : public:
100 : /// Postorder list iterators.
101 : typedef std::vector<BasicBlock*>::const_iterator POIterator;
102 : typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
103 :
104 : friend class LoopBlocksTraversal;
105 :
106 : private:
107 : Loop *L;
108 :
109 : /// Map each block to its postorder number. A block is only mapped after it is
110 : /// preorder visited by DFS. It's postorder number is initially zero and set
111 : /// to nonzero after it is finished by postorder traversal.
112 : DenseMap<BasicBlock*, unsigned> PostNumbers;
113 : std::vector<BasicBlock*> PostBlocks;
114 :
115 : public:
116 8482 : LoopBlocksDFS(Loop *Container) :
117 25446 : L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
118 8482 : PostBlocks.reserve(Container->getNumBlocks());
119 8482 : }
120 :
121 : Loop *getLoop() const { return L; }
122 :
123 : /// Traverse the loop blocks and store the DFS result.
124 : void perform(LoopInfo *LI);
125 :
126 : /// Return true if postorder numbers are assigned to all loop blocks.
127 : bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
128 :
129 : /// Iterate over the cached postorder blocks.
130 : POIterator beginPostorder() const {
131 : assert(isComplete() && "bad loop DFS");
132 4 : return PostBlocks.begin();
133 : }
134 4 : POIterator endPostorder() const { return PostBlocks.end(); }
135 :
136 : /// Reverse iterate over the cached postorder blocks.
137 : RPOIterator beginRPO() const {
138 : assert(isComplete() && "bad loop DFS");
139 : return PostBlocks.rbegin();
140 : }
141 : RPOIterator endRPO() const { return PostBlocks.rend(); }
142 :
143 : /// Return true if this block has been preorder visited.
144 : bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
145 :
146 : /// Return true if this block has a postorder number.
147 : bool hasPostorder(BasicBlock *BB) const {
148 : DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
149 : return I != PostNumbers.end() && I->second;
150 : }
151 :
152 : /// Get a block's postorder number.
153 : unsigned getPostorder(BasicBlock *BB) const {
154 : DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
155 : assert(I != PostNumbers.end() && "block not visited by DFS");
156 : assert(I->second && "block not finished by DFS");
157 : return I->second;
158 : }
159 :
160 : /// Get a block's reverse postorder number.
161 : unsigned getRPO(BasicBlock *BB) const {
162 : return 1 + PostBlocks.size() - getPostorder(BB);
163 : }
164 :
165 : void clear() {
166 : PostNumbers.clear();
167 : PostBlocks.clear();
168 : }
169 : };
170 :
171 : /// Wrapper class to LoopBlocksDFS that provides a standard begin()/end()
172 : /// interface for the DFS reverse post-order traversal of blocks in a loop body.
173 4481 : class LoopBlocksRPO {
174 : private:
175 : LoopBlocksDFS DFS;
176 :
177 : public:
178 4481 : LoopBlocksRPO(Loop *Container) : DFS(Container) {}
179 :
180 : /// Traverse the loop blocks and store the DFS result.
181 : void perform(LoopInfo *LI) {
182 4481 : DFS.perform(LI);
183 : }
184 :
185 : /// Reverse iterate over the cached postorder blocks.
186 : LoopBlocksDFS::RPOIterator begin() const { return DFS.beginRPO(); }
187 : LoopBlocksDFS::RPOIterator end() const { return DFS.endRPO(); }
188 : };
189 :
190 : /// Specialize po_iterator_storage to record postorder numbers.
191 : template<> class po_iterator_storage<LoopBlocksTraversal, true> {
192 : LoopBlocksTraversal &LBT;
193 : public:
194 8458 : po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
195 : // These functions are defined below.
196 : bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
197 : void finishPostorder(BasicBlock *BB);
198 : };
199 :
200 : /// Traverse the blocks in a loop using a depth-first search.
201 : class LoopBlocksTraversal {
202 : public:
203 : /// Graph traversal iterator.
204 : typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
205 :
206 : private:
207 : LoopBlocksDFS &DFS;
208 : LoopInfo *LI;
209 :
210 : public:
211 8458 : LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
212 8458 : DFS(Storage), LI(LInfo) {}
213 :
214 : /// Postorder traversal over the graph. This only needs to be done once.
215 : /// po_iterator "automatically" calls back to visitPreorder and
216 : /// finishPostorder to record the DFS result.
217 8458 : POTIterator begin() {
218 : assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
219 : assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
220 16916 : return po_ext_begin(DFS.L->getHeader(), *this);
221 : }
222 : POTIterator end() {
223 : // po_ext_end interface requires a basic block, but ignores its value.
224 8458 : return po_ext_end(DFS.L->getHeader(), *this);
225 : }
226 :
227 : /// Called by po_iterator upon reaching a block via a CFG edge. If this block
228 : /// is contained in the loop and has not been visited, then mark it preorder
229 : /// visited and return true.
230 : ///
231 : /// TODO: If anyone is interested, we could record preorder numbers here.
232 61299 : bool visitPreorder(BasicBlock *BB) {
233 122598 : if (!DFS.L->contains(LI->getLoopFor(BB)))
234 : return false;
235 :
236 45203 : return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
237 : }
238 :
239 : /// Called by po_iterator each time it advances, indicating a block's
240 : /// postorder.
241 0 : void finishPostorder(BasicBlock *BB) {
242 : assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
243 0 : DFS.PostBlocks.push_back(BB);
244 0 : DFS.PostNumbers[BB] = DFS.PostBlocks.size();
245 0 : }
246 : };
247 :
248 0 : inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
249 : Optional<BasicBlock *> From, BasicBlock *To) {
250 61299 : return LBT.visitPreorder(To);
251 : }
252 :
253 0 : inline void po_iterator_storage<LoopBlocksTraversal, true>::
254 : finishPostorder(BasicBlock *BB) {
255 29909 : LBT.finishPostorder(BB);
256 0 : }
257 :
258 : } // End namespace llvm
259 :
260 : #endif
|
