1 //===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
9 // This file defines iterators to visit the basic blocks within a loop.
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.
15 // If you want to visit all blocks in a loop and don't need an ordered traveral,
16 // use Loop::block_begin() instead.
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 //===----------------------------------------------------------------------===//
24 #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
25 #define LLVM_ANALYSIS_LOOPITERATOR_H
27 #include "llvm/ADT/PostOrderIterator.h"
28 #include "llvm/Analysis/LoopInfo.h"
32 class LoopBlocksTraversal;
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.
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 *>;
44 // This wraps a const Loop * into the iterator, so we know which edges to
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>;
59 WrappedSuccIterator(succ_iterator Begin, const Loop *L)
60 : BaseT(Begin), L(L) {}
62 NodeRef operator*() const { return {L, *I}; }
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);
72 using ChildIteratorType =
73 filter_iterator<WrappedSuccIterator, LoopBodyFilter>;
75 static NodeRef getEntryNode(const Loop &G) { return {&G, G.getHeader()}; }
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}),
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}),
94 /// Store the result of a depth first search within basic blocks contained by a
97 /// TODO: This could be generalized for any CFG region, or the entire CFG.
100 /// Postorder list iterators.
101 typedef std::vector<BasicBlock*>::const_iterator POIterator;
102 typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
104 friend class LoopBlocksTraversal;
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;
116 LoopBlocksDFS(Loop *Container) :
117 L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
118 PostBlocks.reserve(Container->getNumBlocks());
121 Loop *getLoop() const { return L; }
123 /// Traverse the loop blocks and store the DFS result.
124 void perform(LoopInfo *LI);
126 /// Return true if postorder numbers are assigned to all loop blocks.
127 bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
129 /// Iterate over the cached postorder blocks.
130 POIterator beginPostorder() const {
131 assert(isComplete() && "bad loop DFS");
132 return PostBlocks.begin();
134 POIterator endPostorder() const { return PostBlocks.end(); }
136 /// Reverse iterate over the cached postorder blocks.
137 RPOIterator beginRPO() const {
138 assert(isComplete() && "bad loop DFS");
139 return PostBlocks.rbegin();
141 RPOIterator endRPO() const { return PostBlocks.rend(); }
143 /// Return true if this block has been preorder visited.
144 bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
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;
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");
160 /// Get a block's reverse postorder number.
161 unsigned getRPO(BasicBlock *BB) const {
162 return 1 + PostBlocks.size() - getPostorder(BB);
171 /// Specialize po_iterator_storage to record postorder numbers.
172 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
173 LoopBlocksTraversal &LBT;
175 po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
176 // These functions are defined below.
177 bool insertEdge(Optional<BasicBlock *> From, BasicBlock *To);
178 void finishPostorder(BasicBlock *BB);
181 /// Traverse the blocks in a loop using a depth-first search.
182 class LoopBlocksTraversal {
184 /// Graph traversal iterator.
185 typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
192 LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
193 DFS(Storage), LI(LInfo) {}
195 /// Postorder traversal over the graph. This only needs to be done once.
196 /// po_iterator "automatically" calls back to visitPreorder and
197 /// finishPostorder to record the DFS result.
198 POTIterator begin() {
199 assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
200 assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
201 return po_ext_begin(DFS.L->getHeader(), *this);
204 // po_ext_end interface requires a basic block, but ignores its value.
205 return po_ext_end(DFS.L->getHeader(), *this);
208 /// Called by po_iterator upon reaching a block via a CFG edge. If this block
209 /// is contained in the loop and has not been visited, then mark it preorder
210 /// visited and return true.
212 /// TODO: If anyone is interested, we could record preorder numbers here.
213 bool visitPreorder(BasicBlock *BB) {
214 if (!DFS.L->contains(LI->getLoopFor(BB)))
217 return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
220 /// Called by po_iterator each time it advances, indicating a block's
222 void finishPostorder(BasicBlock *BB) {
223 assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
224 DFS.PostBlocks.push_back(BB);
225 DFS.PostNumbers[BB] = DFS.PostBlocks.size();
229 inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge(
230 Optional<BasicBlock *> From, BasicBlock *To) {
231 return LBT.visitPreorder(To);
234 inline void po_iterator_storage<LoopBlocksTraversal, true>::
235 finishPostorder(BasicBlock *BB) {
236 LBT.finishPostorder(BB);
239 } // End namespace llvm