LoopIterator.h revision 239462
1249997Swkoszek//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===// 2249997Swkoszek// 3249997Swkoszek// The LLVM Compiler Infrastructure 4249997Swkoszek// 5249997Swkoszek// This file is distributed under the University of Illinois Open Source 6249997Swkoszek// License. See LICENSE.TXT for details. 7249997Swkoszek// 8249997Swkoszek//===----------------------------------------------------------------------===// 9249997Swkoszek// This file defines iterators to visit the basic blocks within a loop. 10249997Swkoszek// 11249997Swkoszek// These iterators currently visit blocks within subloops as well. 12249997Swkoszek// Unfortunately we have no efficient way of summarizing loop exits which would 13249997Swkoszek// allow skipping subloops during traversal. 14249997Swkoszek// 15249997Swkoszek// If you want to visit all blocks in a loop and don't need an ordered traveral, 16249997Swkoszek// use Loop::block_begin() instead. 17249997Swkoszek// 18249997Swkoszek// This is intentionally designed to work with ill-formed loops in which the 19249997Swkoszek// backedge has been deleted. The only prerequisite is that all blocks 20249997Swkoszek// contained within the loop according to the most recent LoopInfo analysis are 21249997Swkoszek// reachable from the loop header. 22249997Swkoszek//===----------------------------------------------------------------------===// 23249997Swkoszek 24249997Swkoszek#ifndef LLVM_ANALYSIS_LOOP_ITERATOR_H 25249997Swkoszek#define LLVM_ANALYSIS_LOOP_ITERATOR_H 26249997Swkoszek 27249997Swkoszek#include "llvm/ADT/DepthFirstIterator.h" 28249997Swkoszek#include "llvm/ADT/PostOrderIterator.h" 29249997Swkoszek#include "llvm/Analysis/LoopInfo.h" 30249997Swkoszek 31249997Swkoszeknamespace llvm { 32249997Swkoszek 33249997Swkoszekclass LoopBlocksTraversal; 34249997Swkoszek 35249997Swkoszek/// Store the result of a depth first search within basic blocks contained by a 36249997Swkoszek/// single loop. 37249997Swkoszek/// 38249997Swkoszek/// TODO: This could be generalized for any CFG region, or the entire CFG. 39249997Swkoszekclass LoopBlocksDFS { 40249997Swkoszekpublic: 41249997Swkoszek /// Postorder list iterators. 42249997Swkoszek typedef std::vector<BasicBlock*>::const_iterator POIterator; 43249997Swkoszek typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator; 44249997Swkoszek 45249997Swkoszek friend class LoopBlocksTraversal; 46249997Swkoszek 47249997Swkoszekprivate: 48249997Swkoszek Loop *L; 49249997Swkoszek 50279724Sian /// Map each block to its postorder number. A block is only mapped after it is 51249997Swkoszek /// preorder visited by DFS. It's postorder number is initially zero and set 52249997Swkoszek /// to nonzero after it is finished by postorder traversal. 53249997Swkoszek DenseMap<BasicBlock*, unsigned> PostNumbers; 54249997Swkoszek std::vector<BasicBlock*> PostBlocks; 55249997Swkoszek 56249997Swkoszekpublic: 57249997Swkoszek LoopBlocksDFS(Loop *Container) : 58249997Swkoszek L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { 59249997Swkoszek PostBlocks.reserve(Container->getNumBlocks()); 60249997Swkoszek } 61249997Swkoszek 62249997Swkoszek Loop *getLoop() const { return L; } 63249997Swkoszek 64249997Swkoszek /// Traverse the loop blocks and store the DFS result. 65249997Swkoszek void perform(LoopInfo *LI); 66249997Swkoszek 67249997Swkoszek /// Return true if postorder numbers are assigned to all loop blocks. 68249997Swkoszek bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } 69249997Swkoszek 70249997Swkoszek /// Iterate over the cached postorder blocks. 71249997Swkoszek POIterator beginPostorder() const { 72249997Swkoszek assert(isComplete() && "bad loop DFS"); 73249997Swkoszek return PostBlocks.begin(); 74249997Swkoszek } 75249997Swkoszek POIterator endPostorder() const { return PostBlocks.end(); } 76249997Swkoszek 77249997Swkoszek /// Reverse iterate over the cached postorder blocks. 78249997Swkoszek RPOIterator beginRPO() const { 79249997Swkoszek assert(isComplete() && "bad loop DFS"); 80249997Swkoszek return PostBlocks.rbegin(); 81249997Swkoszek } 82249997Swkoszek RPOIterator endRPO() const { return PostBlocks.rend(); } 83249997Swkoszek 84249997Swkoszek /// Return true if this block has been preorder visited. 85249997Swkoszek bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } 86249997Swkoszek 87249997Swkoszek /// Return true if this block has a postorder number. 88249997Swkoszek bool hasPostorder(BasicBlock *BB) const { 89249997Swkoszek DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 90249997Swkoszek return I != PostNumbers.end() && I->second; 91249997Swkoszek } 92249997Swkoszek 93249997Swkoszek /// Get a block's postorder number. 94249997Swkoszek unsigned getPostorder(BasicBlock *BB) const { 95249997Swkoszek DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); 96249997Swkoszek assert(I != PostNumbers.end() && "block not visited by DFS"); 97249997Swkoszek assert(I->second && "block not finished by DFS"); 98249997Swkoszek return I->second; 99249997Swkoszek } 100249997Swkoszek 101249997Swkoszek /// Get a block's reverse postorder number. 102249997Swkoszek unsigned getRPO(BasicBlock *BB) const { 103249997Swkoszek return 1 + PostBlocks.size() - getPostorder(BB); 104249997Swkoszek } 105249997Swkoszek 106249997Swkoszek void clear() { 107249997Swkoszek PostNumbers.clear(); 108249997Swkoszek PostBlocks.clear(); 109249997Swkoszek } 110249997Swkoszek}; 111249997Swkoszek 112249997Swkoszek/// Specialize po_iterator_storage to record postorder numbers. 113249997Swkoszektemplate<> class po_iterator_storage<LoopBlocksTraversal, true> { 114249997Swkoszek LoopBlocksTraversal &LBT; 115249997Swkoszekpublic: 116249997Swkoszek po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {} 117249997Swkoszek // These functions are defined below. 118249997Swkoszek bool insertEdge(BasicBlock *From, BasicBlock *To); 119249997Swkoszek void finishPostorder(BasicBlock *BB); 120249997Swkoszek}; 121249997Swkoszek 122249997Swkoszek/// Traverse the blocks in a loop using a depth-first search. 123249997Swkoszekclass LoopBlocksTraversal { 124249997Swkoszekpublic: 125249997Swkoszek /// Graph traversal iterator. 126249997Swkoszek typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; 127249997Swkoszek 128249997Swkoszekprivate: 129249997Swkoszek LoopBlocksDFS &DFS; 130249997Swkoszek LoopInfo *LI; 131249997Swkoszek 132249997Swkoszekpublic: 133249997Swkoszek LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : 134249997Swkoszek DFS(Storage), LI(LInfo) {} 135249997Swkoszek 136249997Swkoszek /// Postorder traversal over the graph. This only needs to be done once. 137249997Swkoszek /// po_iterator "automatically" calls back to visitPreorder and 138249997Swkoszek /// finishPostorder to record the DFS result. 139249997Swkoszek POTIterator begin() { 140249997Swkoszek assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); 141249997Swkoszek assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); 142249997Swkoszek return po_ext_begin(DFS.L->getHeader(), *this); 143249997Swkoszek } 144249997Swkoszek POTIterator end() { 145249997Swkoszek // po_ext_end interface requires a basic block, but ignores its value. 146249997Swkoszek return po_ext_end(DFS.L->getHeader(), *this); 147249997Swkoszek } 148249997Swkoszek 149249997Swkoszek /// Called by po_iterator upon reaching a block via a CFG edge. If this block 150249997Swkoszek /// is contained in the loop and has not been visited, then mark it preorder 151249997Swkoszek /// visited and return true. 152249997Swkoszek /// 153249997Swkoszek /// TODO: If anyone is interested, we could record preorder numbers here. 154249997Swkoszek bool visitPreorder(BasicBlock *BB) { 155249997Swkoszek if (!DFS.L->contains(LI->getLoopFor(BB))) 156249997Swkoszek return false; 157249997Swkoszek 158249997Swkoszek return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; 159249997Swkoszek } 160249997Swkoszek 161249997Swkoszek /// Called by po_iterator each time it advances, indicating a block's 162249997Swkoszek /// postorder. 163249997Swkoszek void finishPostorder(BasicBlock *BB) { 164249997Swkoszek assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); 165249997Swkoszek DFS.PostBlocks.push_back(BB); 166249997Swkoszek DFS.PostNumbers[BB] = DFS.PostBlocks.size(); 167249997Swkoszek } 168249997Swkoszek}; 169249997Swkoszek 170249997Swkoszekinline bool po_iterator_storage<LoopBlocksTraversal, true>:: 171249997SwkoszekinsertEdge(BasicBlock *From, BasicBlock *To) { 172249997Swkoszek return LBT.visitPreorder(To); 173249997Swkoszek} 174249997Swkoszek 175249997Swkoszekinline void po_iterator_storage<LoopBlocksTraversal, true>:: 176249997SwkoszekfinishPostorder(BasicBlock *BB) { 177249997Swkoszek LBT.finishPostorder(BB); 178249997Swkoszek} 179249997Swkoszek 180249997Swkoszek} // End namespace llvm 181249997Swkoszek 182249997Swkoszek#endif 183249997Swkoszek