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