Correct word hyphenations
[oota-llvm.git] / include / llvm / Analysis / LoopIterator.h
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 /// Store the result of a depth first search within basic blocks contained by a
35 /// single loop.
36 ///
37 /// TODO: This could be generalized for any CFG region, or the entire CFG.
38 class LoopBlocksDFS {
39 public:
40   /// Postorder list iterators.
41   typedef std::vector<BasicBlock*>::const_iterator POIterator;
42   typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator;
43
44   friend class LoopBlocksTraversal;
45
46 private:
47   Loop *L;
48
49   /// Map each block to its postorder number. A block is only mapped after it is
50   /// preorder visited by DFS. It's postorder number is initially zero and set
51   /// to nonzero after it is finished by postorder traversal.
52   DenseMap<BasicBlock*, unsigned> PostNumbers;
53   std::vector<BasicBlock*> PostBlocks;
54
55 public:
56   LoopBlocksDFS(Loop *Container) :
57     L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) {
58     PostBlocks.reserve(Container->getNumBlocks());
59   }
60
61   Loop *getLoop() const { return L; }
62
63   /// Traverse the loop blocks and store the DFS result.
64   void perform(LoopInfo *LI);
65
66   /// Return true if postorder numbers are assigned to all loop blocks.
67   bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); }
68
69   /// Iterate over the cached postorder blocks.
70   POIterator beginPostorder() const {
71     assert(isComplete() && "bad loop DFS");
72     return PostBlocks.begin();
73   }
74   POIterator endPostorder() const { return PostBlocks.end(); }
75
76   /// Reverse iterate over the cached postorder blocks.
77   RPOIterator beginRPO() const {
78     assert(isComplete() && "bad loop DFS");
79     return PostBlocks.rbegin();
80   }
81   RPOIterator endRPO() const { return PostBlocks.rend(); }
82
83   /// Return true if this block has been preorder visited.
84   bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); }
85
86   /// Return true if this block has a postorder number.
87   bool hasPostorder(BasicBlock *BB) const {
88     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
89     return I != PostNumbers.end() && I->second;
90   }
91
92   /// Get a block's postorder number.
93   unsigned getPostorder(BasicBlock *BB) const {
94     DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB);
95     assert(I != PostNumbers.end() && "block not visited by DFS");
96     assert(I->second && "block not finished by DFS");
97     return I->second;
98   }
99
100   /// Get a block's reverse postorder number.
101   unsigned getRPO(BasicBlock *BB) const {
102     return 1 + PostBlocks.size() - getPostorder(BB);
103   }
104
105   void clear() {
106     PostNumbers.clear();
107     PostBlocks.clear();
108   }
109 };
110
111 /// Specialize po_iterator_storage to record postorder numbers.
112 template<> class po_iterator_storage<LoopBlocksTraversal, true> {
113   LoopBlocksTraversal &LBT;
114 public:
115   po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
116   // These functions are defined below.
117   bool insertEdge(BasicBlock *From, BasicBlock *To);
118   void finishPostorder(BasicBlock *BB);
119 };
120
121 /// Traverse the blocks in a loop using a depth-first search.
122 class LoopBlocksTraversal {
123 public:
124   /// Graph traversal iterator.
125   typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator;
126
127 private:
128   LoopBlocksDFS &DFS;
129   LoopInfo *LI;
130
131 public:
132   LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) :
133     DFS(Storage), LI(LInfo) {}
134
135   /// Postorder traversal over the graph. This only needs to be done once.
136   /// po_iterator "automatically" calls back to visitPreorder and
137   /// finishPostorder to record the DFS result.
138   POTIterator begin() {
139     assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing");
140     assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph");
141     return po_ext_begin(DFS.L->getHeader(), *this);
142   }
143   POTIterator end() {
144     // po_ext_end interface requires a basic block, but ignores its value.
145     return po_ext_end(DFS.L->getHeader(), *this);
146   }
147
148   /// Called by po_iterator upon reaching a block via a CFG edge. If this block
149   /// is contained in the loop and has not been visited, then mark it preorder
150   /// visited and return true.
151   ///
152   /// TODO: If anyone is interested, we could record preorder numbers here.
153   bool visitPreorder(BasicBlock *BB) {
154     if (!DFS.L->contains(LI->getLoopFor(BB)))
155       return false;
156
157     return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second;
158   }
159
160   /// Called by po_iterator each time it advances, indicating a block's
161   /// postorder.
162   void finishPostorder(BasicBlock *BB) {
163     assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder");
164     DFS.PostBlocks.push_back(BB);
165     DFS.PostNumbers[BB] = DFS.PostBlocks.size();
166   }
167 };
168
169 inline bool po_iterator_storage<LoopBlocksTraversal, true>::
170 insertEdge(BasicBlock *From, BasicBlock *To) {
171   return LBT.visitPreorder(To);
172 }
173
174 inline void po_iterator_storage<LoopBlocksTraversal, true>::
175 finishPostorder(BasicBlock *BB) {
176   LBT.finishPostorder(BB);
177 }
178
179 } // End namespace llvm
180
181 #endif