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