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 30namespace llvm { 31 32class 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. 41struct 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. 98class LoopBlocksDFS { 99public: 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 106private: 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 115public: 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/// Specialize po_iterator_storage to record postorder numbers. 172template<> class po_iterator_storage<LoopBlocksTraversal, true> { 173 LoopBlocksTraversal &LBT; 174public: 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); 179}; 180 181/// Traverse the blocks in a loop using a depth-first search. 182class LoopBlocksTraversal { 183public: 184 /// Graph traversal iterator. 185 typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 186 187private: 188 LoopBlocksDFS &DFS; 189 LoopInfo *LI; 190 191public: 192 LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 193 DFS(Storage), LI(LInfo) {} 194 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); 202 } 203 POTIterator end() { 204 // po_ext_end interface requires a basic block, but ignores its value. 205 return po_ext_end(DFS.L->getHeader(), *this); 206 } 207 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. 211 /// 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))) 215 return false; 216 217 return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 218 } 219 220 /// Called by po_iterator each time it advances, indicating a block's 221 /// postorder. 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(); 226 } 227}; 228 229inline bool po_iterator_storage<LoopBlocksTraversal, true>::insertEdge( 230 Optional<BasicBlock *> From, BasicBlock *To) { 231 return LBT.visitPreorder(To); 232} 233 234inline void po_iterator_storage<LoopBlocksTraversal, true>:: 235finishPostorder(BasicBlock *BB) { 236 LBT.finishPostorder(BB); 237} 238 239} // End namespace llvm 240 241#endif 242