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 LoopBlocksDFS(Loop *Container) : 117 L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { 118 PostBlocks.reserve(Container->getNumBlocks()); 119 } 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 return PostBlocks.begin(); 133 } 134 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 class LoopBlocksRPO { 174 private: 175 LoopBlocksDFS DFS; 176 177 public: 178 LoopBlocksRPO(Loop *Container) : DFS(Container) {} 179 180 /// Traverse the loop blocks and store the DFS result. 181 void perform(LoopInfo *LI) { 182 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 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 LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 212 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 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 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 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 bool visitPreorder(BasicBlock *BB) { 233 if (!DFS.L->contains(LI->getLoopFor(BB))) 234 return false; 235 236 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 void finishPostorder(BasicBlock *BB) { 242 assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 243 DFS.PostBlocks.push_back(BB); 244 DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 245 } 246 }; 247 248 inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( 249 Optional<BasicBlock *> From, BasicBlock *To) { 250 return LBT.visitPreorder(To); 251 } 252 253 inline void po_iterator_storage<LoopBlocksTraversal, true>:: 254 finishPostorder(BasicBlock *BB) { 255 LBT.finishPostorder(BB); 256 } 257 258 } // End namespace llvm 259 260 #endif 261