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 31namespace llvm { 32 33class 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. 39class LoopBlocksDFS { 40public: 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 47private: 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 56public: 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/// Specialize po_iterator_storage to record postorder numbers. 113template<> class po_iterator_storage<LoopBlocksTraversal, true> { 114 LoopBlocksTraversal &LBT; 115public: 116 po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} 117 // These functions are defined below. 118 bool insertEdge(BasicBlock *From, BasicBlock *To); 119 void finishPostorder(BasicBlock *BB); 120}; 121 122/// Traverse the blocks in a loop using a depth-first search. 123class LoopBlocksTraversal { 124public: 125 /// Graph traversal iterator. 126 typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 127 128private: 129 LoopBlocksDFS &DFS; 130 LoopInfo *LI; 131 132public: 133 LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 134 DFS(Storage), LI(LInfo) {} 135 136 /// Postorder traversal over the graph. This only needs to be done once. 137 /// po_iterator "automatically" calls back to visitPreorder and 138 /// finishPostorder to record the DFS result. 139 POTIterator begin() { 140 assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); 141 assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); 142 return po_ext_begin(DFS.L->getHeader(), *this); 143 } 144 POTIterator end() { 145 // po_ext_end interface requires a basic block, but ignores its value. 146 return po_ext_end(DFS.L->getHeader(), *this); 147 } 148 149 /// Called by po_iterator upon reaching a block via a CFG edge. If this block 150 /// is contained in the loop and has not been visited, then mark it preorder 151 /// visited and return true. 152 /// 153 /// TODO: If anyone is interested, we could record preorder numbers here. 154 bool visitPreorder(BasicBlock *BB) { 155 if (!DFS.L->contains(LI->getLoopFor(BB))) 156 return false; 157 158 return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 159 } 160 161 /// Called by po_iterator each time it advances, indicating a block's 162 /// postorder. 163 void finishPostorder(BasicBlock *BB) { 164 assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 165 DFS.PostBlocks.push_back(BB); 166 DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 167 } 168}; 169 170inline bool po_iterator_storage<LoopBlocksTraversal, true>:: 171insertEdge(BasicBlock *From, BasicBlock *To) { 172 return LBT.visitPreorder(To); 173} 174 175inline void po_iterator_storage<LoopBlocksTraversal, true>:: 176finishPostorder(BasicBlock *BB) { 177 LBT.finishPostorder(BB); 178} 179 180} // End namespace llvm 181 182#endif 183