1226584Sdim//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===// 2226584Sdim// 3226584Sdim// The LLVM Compiler Infrastructure 4226584Sdim// 5226584Sdim// This file is distributed under the University of Illinois Open Source 6226584Sdim// License. See LICENSE.TXT for details. 7226584Sdim// 8226584Sdim//===----------------------------------------------------------------------===// 9226584Sdim// This file defines iterators to visit the basic blocks within a loop. 10226584Sdim// 11226584Sdim// These iterators currently visit blocks within subloops as well. 12226584Sdim// Unfortunately we have no efficient way of summarizing loop exits which would 13226584Sdim// allow skipping subloops during traversal. 14226584Sdim// 15226584Sdim// If you want to visit all blocks in a loop and don't need an ordered traveral, 16226584Sdim// use Loop::block_begin() instead. 17226584Sdim// 18226584Sdim// This is intentionally designed to work with ill-formed loops in which the 19226584Sdim// backedge has been deleted. The only prerequisite is that all blocks 20226584Sdim// contained within the loop according to the most recent LoopInfo analysis are 21226584Sdim// reachable from the loop header. 22226584Sdim//===----------------------------------------------------------------------===// 23226584Sdim 24249423Sdim#ifndef LLVM_ANALYSIS_LOOPITERATOR_H 25249423Sdim#define LLVM_ANALYSIS_LOOPITERATOR_H 26226584Sdim 27226584Sdim#include "llvm/ADT/PostOrderIterator.h" 28226584Sdim#include "llvm/Analysis/LoopInfo.h" 29226584Sdim 30226584Sdimnamespace llvm { 31226584Sdim 32226584Sdimclass LoopBlocksTraversal; 33226584Sdim 34226584Sdim/// Store the result of a depth first search within basic blocks contained by a 35226584Sdim/// single loop. 36226584Sdim/// 37226584Sdim/// TODO: This could be generalized for any CFG region, or the entire CFG. 38226584Sdimclass LoopBlocksDFS { 39226584Sdimpublic: 40226584Sdim /// Postorder list iterators. 41226584Sdim typedef std::vector<BasicBlock*>::const_iterator POIterator; 42226584Sdim typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator; 43226584Sdim 44226584Sdim friend class LoopBlocksTraversal; 45226584Sdim 46226584Sdimprivate: 47226584Sdim Loop *L; 48226584Sdim 49226584Sdim /// Map each block to its postorder number. A block is only mapped after it is 50226584Sdim /// preorder visited by DFS. It's postorder number is initially zero and set 51226584Sdim /// to nonzero after it is finished by postorder traversal. 52226584Sdim DenseMap<BasicBlock*, unsigned> PostNumbers; 53226584Sdim std::vector<BasicBlock*> PostBlocks; 54226584Sdim 55226584Sdimpublic: 56226584Sdim LoopBlocksDFS(Loop *Container) : 57226584Sdim L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { 58226584Sdim PostBlocks.reserve(Container->getNumBlocks()); 59226584Sdim } 60226584Sdim 61226584Sdim Loop *getLoop() const { return L; } 62226584Sdim 63226584Sdim /// Traverse the loop blocks and store the DFS result. 64226584Sdim void perform(LoopInfo *LI); 65226584Sdim 66226584Sdim /// Return true if postorder numbers are assigned to all loop blocks. 67226584Sdim bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } 68226584Sdim 69226584Sdim /// Iterate over the cached postorder blocks. 70226584Sdim POIterator beginPostorder() const { 71226584Sdim assert(isComplete() && "bad loop DFS"); 72226584Sdim return PostBlocks.begin(); 73226584Sdim } 74226584Sdim POIterator endPostorder() const { return PostBlocks.end(); } 75226584Sdim 76226584Sdim /// Reverse iterate over the cached postorder blocks. 77226584Sdim RPOIterator beginRPO() const { 78226584Sdim assert(isComplete() && "bad loop DFS"); 79226584Sdim return PostBlocks.rbegin(); 80226584Sdim } 81226584Sdim RPOIterator endRPO() const { return PostBlocks.rend(); } 82226584Sdim 83226584Sdim /// Return true if this block has been preorder visited. 84226584Sdim bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } 85226584Sdim 86226584Sdim /// Return true if this block has a postorder number. 87226584Sdim bool hasPostorder(BasicBlock *BB) const { 88226584Sdim DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 89226584Sdim return I != PostNumbers.end() && I->second; 90226584Sdim } 91226584Sdim 92226584Sdim /// Get a block's postorder number. 93226584Sdim unsigned getPostorder(BasicBlock *BB) const { 94226584Sdim DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 95226584Sdim assert(I != PostNumbers.end() && "block not visited by DFS"); 96226584Sdim assert(I->second && "block not finished by DFS"); 97226584Sdim return I->second; 98226584Sdim } 99226584Sdim 100226584Sdim /// Get a block's reverse postorder number. 101226584Sdim unsigned getRPO(BasicBlock *BB) const { 102226584Sdim return 1 + PostBlocks.size() - getPostorder(BB); 103226584Sdim } 104226584Sdim 105226584Sdim void clear() { 106226584Sdim PostNumbers.clear(); 107226584Sdim PostBlocks.clear(); 108226584Sdim } 109226584Sdim}; 110226584Sdim 111239462Sdim/// Specialize po_iterator_storage to record postorder numbers. 112239462Sdimtemplate<> class po_iterator_storage<LoopBlocksTraversal, true> { 113239462Sdim LoopBlocksTraversal &LBT; 114239462Sdimpublic: 115239462Sdim po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} 116239462Sdim // These functions are defined below. 117239462Sdim bool insertEdge(BasicBlock *From, BasicBlock *To); 118239462Sdim void finishPostorder(BasicBlock *BB); 119239462Sdim}; 120239462Sdim 121226584Sdim/// Traverse the blocks in a loop using a depth-first search. 122226584Sdimclass LoopBlocksTraversal { 123226584Sdimpublic: 124226584Sdim /// Graph traversal iterator. 125226584Sdim typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 126226584Sdim 127226584Sdimprivate: 128226584Sdim LoopBlocksDFS &DFS; 129226584Sdim LoopInfo *LI; 130226584Sdim 131226584Sdimpublic: 132226584Sdim LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 133226584Sdim DFS(Storage), LI(LInfo) {} 134226584Sdim 135226584Sdim /// Postorder traversal over the graph. This only needs to be done once. 136226584Sdim /// po_iterator "automatically" calls back to visitPreorder and 137226584Sdim /// finishPostorder to record the DFS result. 138226584Sdim POTIterator begin() { 139226584Sdim assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); 140226584Sdim assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); 141226584Sdim return po_ext_begin(DFS.L->getHeader(), *this); 142226584Sdim } 143226584Sdim POTIterator end() { 144226584Sdim // po_ext_end interface requires a basic block, but ignores its value. 145226584Sdim return po_ext_end(DFS.L->getHeader(), *this); 146226584Sdim } 147226584Sdim 148226584Sdim /// Called by po_iterator upon reaching a block via a CFG edge. If this block 149226584Sdim /// is contained in the loop and has not been visited, then mark it preorder 150226584Sdim /// visited and return true. 151226584Sdim /// 152226584Sdim /// TODO: If anyone is interested, we could record preorder numbers here. 153226584Sdim bool visitPreorder(BasicBlock *BB) { 154226584Sdim if (!DFS.L->contains(LI->getLoopFor(BB))) 155226584Sdim return false; 156226584Sdim 157226584Sdim return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 158226584Sdim } 159226584Sdim 160226584Sdim /// Called by po_iterator each time it advances, indicating a block's 161226584Sdim /// postorder. 162226584Sdim void finishPostorder(BasicBlock *BB) { 163226584Sdim assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 164226584Sdim DFS.PostBlocks.push_back(BB); 165226584Sdim DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 166226584Sdim } 167239462Sdim}; 168226584Sdim 169239462Sdiminline bool po_iterator_storage<LoopBlocksTraversal, true>:: 170239462SdiminsertEdge(BasicBlock *From, BasicBlock *To) { 171239462Sdim return LBT.visitPreorder(To); 172239462Sdim} 173226584Sdim 174239462Sdiminline void po_iterator_storage<LoopBlocksTraversal, true>:: 175239462SdimfinishPostorder(BasicBlock *BB) { 176239462Sdim LBT.finishPostorder(BB); 177239462Sdim} 178226584Sdim 179226584Sdim} // End namespace llvm 180226584Sdim 181226584Sdim#endif 182