LoopInfoImpl.h revision 4fa57932c7b13ec42c563e33a2e40fd04194b64e
1cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===// 2cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 3cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// The LLVM Compiler Infrastructure 4cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 5cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// This file is distributed under the University of Illinois Open Source 6cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// License. See LICENSE.TXT for details. 7cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 8cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 9cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 10cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// This is the generic implementation of LoopInfo used for both Loops and 11cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// MachineLoops. 12cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 13cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 14cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 15674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H 16674be02d525d4e24bc6943ed9274958c580bcfbcJakub Staszak#define LLVM_ANALYSIS_LOOPINFOIMPL_H 17cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 1837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick#include "llvm/ADT/PostOrderIterator.h" 194fa57932c7b13ec42c563e33a2e40fd04194b64eJakub Staszak#include "llvm/ADT/STLExtras.h" 20255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Analysis/LoopInfo.h" 21cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 22cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricknamespace llvm { 23cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 24cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 25cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// APIs for simple analysis of the loop. See header notes. 26cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 27cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitingBlocks - Return all blocks inside the loop that have successors 28cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// outside of the loop. These are the blocks _inside of the current loop_ 29cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// which branch out. The returned list is always unique. 30cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 31cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 32cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 33cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { 34cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 35cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 36cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 37cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::sort(LoopBBs.begin(), LoopBBs.end()); 38cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 39cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 40cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 41cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 42cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 43cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 44cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) { 45cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 46cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitingBlocks.push_back(*BI); 47cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick break; 48cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 49cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 50cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 51cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitingBlock - If getExitingBlocks would return exactly one block, 52cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// return that block. Otherwise return null. 53cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 54cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { 55cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 8> ExitingBlocks; 56cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick getExitingBlocks(ExitingBlocks); 57cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (ExitingBlocks.size() == 1) 58cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return ExitingBlocks[0]; 59cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; 60cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 61cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 62cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitBlocks - Return all of the successor blocks of this loop. These 63cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// are the blocks _outside of the current loop_ which are branched to. 64cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 65cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 66cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 67cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { 68cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 69cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 70cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 71cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::sort(LoopBBs.begin(), LoopBBs.end()); 72cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 73cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 74cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 75cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 76cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 77cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 78cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 79cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 80cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitBlocks.push_back(*I); 81cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 82cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 83cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitBlock - If getExitBlocks would return exactly one block, 84cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// return that block. Otherwise return null. 85cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 86cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { 87cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 8> ExitBlocks; 88cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick getExitBlocks(ExitBlocks); 89cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (ExitBlocks.size() == 1) 90cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return ExitBlocks[0]; 91cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; 92cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 93cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 94cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). 95cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 96cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 97cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { 98cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 99cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 100cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 101cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick array_pod_sort(LoopBBs.begin(), LoopBBs.end()); 102cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 103cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 104cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 105cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 106cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 107cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 108cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 109cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 110cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitEdges.push_back(Edge(*BI, *I)); 111cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 112cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 113cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getLoopPreheader - If there is a preheader for this loop, return it. A 114cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// loop has a preheader if there is only one edge to the header of the loop 115cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// from outside of the loop. If this is the case, the block branching to the 116cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// header of the loop is the preheader node. 117cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 118cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// This method returns null if there is no preheader for the loop. 119cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 120cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 121cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { 122cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Keep track of nodes outside the loop branching to the header... 123cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Out = getLoopPredecessor(); 124cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!Out) return 0; 125cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 126cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Make sure there is only one exit out of the preheader. 127cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 128cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 129cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ++SI; 130cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (SI != BlockTraits::child_end(Out)) 131cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; // Multiple exits from the block, must not be a preheader. 132cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 133cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // The predecessor has exactly one successor, so it is a preheader. 134cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return Out; 135cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 136cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 137cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getLoopPredecessor - If the given loop's header has exactly one unique 138cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// predecessor outside the loop, return it. Otherwise return null. 139cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// This is less strict that the loop "preheader" concept, which requires 140cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// the predecessor to have exactly one successor. 141cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 142cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 143cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { 144cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Keep track of nodes outside the loop branching to the header... 145cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Out = 0; 146cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 147cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Loop over the predecessors of the header node... 148cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Header = getHeader(); 149cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 150cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 151cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_begin(Header), 152cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { 153cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename InvBlockTraits::NodeType *N = *PI; 154cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!contains(N)) { // If the block is not in the loop... 155cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (Out && Out != N) 156cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; // Multiple predecessors outside the loop 157cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick Out = N; 158cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 159cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 160cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 161cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Make sure there is only one exit out of the preheader. 162cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(Out && "Header of loop has no predecessors from outside loop?"); 163cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return Out; 164cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 165cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 166cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getLoopLatch - If there is a single latch block for this loop, return it. 167cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// A latch block is a block that contains a branch back to the header. 168cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 169cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { 170cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Header = getHeader(); 171cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 172cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename InvBlockTraits::ChildIteratorType PI = 173cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_begin(Header); 174cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename InvBlockTraits::ChildIteratorType PE = 175cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_end(Header); 176cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Latch = 0; 177cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (; PI != PE; ++PI) { 178cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename InvBlockTraits::NodeType *N = *PI; 179cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (contains(N)) { 180cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (Latch) return 0; 181cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick Latch = N; 182cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 183cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 184cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 185cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return Latch; 186cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 187cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 188cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 189cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// APIs for updating loop information after changing the CFG 190cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// 191cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 192cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// addBasicBlockToLoop - This method is used by other analyses to update loop 193cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// information. NewBB is set to be a new member of the current loop. 194cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// Because of this, it is added as a member of all parent loops, and is added 195cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// to the specified LoopInfo object as being in the current basic block. It 196cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// is not valid to replace the loop header with this method. 197cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 198cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 199cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 200cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickaddBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { 201cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert((Blocks.empty() || LIB[getHeader()] == this) && 202cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "Incorrect LI specified for this loop!"); 203cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(NewBB && "Cannot add a null basic block to the loop!"); 204cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!"); 205cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 206cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *L = static_cast<LoopT *>(this); 207cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 208cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Add the loop mapping to the LoopInfo object... 209cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LIB.BBMap[NewBB] = L; 210cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 211cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Add the basic block to this loop and all parent loops... 212cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick while (L) { 213cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L->Blocks.push_back(NewBB); 214cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L = L->getParentLoop(); 215cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 216cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 217cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 218cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// replaceChildLoopWith - This is used when splitting loops up. It replaces 219cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// the OldChild entry in our children list with NewChild, and updates the 220cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// parent pointer of OldChild to be null and the NewChild to be this loop. 221cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// This updates the loop depth of the new child. 222cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 223cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 224cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickreplaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) { 225cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(OldChild->ParentLoop == this && "This loop is already broken!"); 226cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!"); 227cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename std::vector<LoopT *>::iterator I = 228cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::find(SubLoops.begin(), SubLoops.end(), OldChild); 229cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(I != SubLoops.end() && "OldChild not in loop!"); 230cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick *I = NewChild; 231cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OldChild->ParentLoop = 0; 232cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NewChild->ParentLoop = static_cast<LoopT *>(this); 233cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 234cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 235cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// verifyLoop - Verify loop structure 236cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 237cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>::verifyLoop() const { 238cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#ifndef NDEBUG 239cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(!Blocks.empty() && "Loop header is missing"); 240cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 241cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Setup for using a depth-first iterator to visit every block in the loop. 242cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 8> ExitBBs; 243cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick getExitBlocks(ExitBBs); 244cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick llvm::SmallPtrSet<BlockT*, 8> VisitSet; 245cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); 246cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> > 247cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BI = df_ext_begin(getHeader(), VisitSet), 248cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BE = df_ext_end(getHeader(), VisitSet); 249cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 250cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Keep track of the number of BBs visited. 251cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick unsigned NumVisited = 0; 252cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 253cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 254cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 255cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 256cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::sort(LoopBBs.begin(), LoopBBs.end()); 257cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 258cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Check the individual blocks. 259cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for ( ; BI != BE; ++BI) { 260cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *BB = *BI; 261cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick bool HasInsideLoopSuccs = false; 262cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick bool HasInsideLoopPreds = false; 263cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT *, 2> OutsideLoopPreds; 264cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 265cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 266cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType SI = 267cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB); 268cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SI != SE; ++SI) 269cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) { 270cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick HasInsideLoopSuccs = true; 271cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick break; 272cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 273cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 274cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 275cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); 276cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick PI != PE; ++PI) { 277cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *N = *PI; 278cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N)) 279cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick HasInsideLoopPreds = true; 280cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick else 281cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OutsideLoopPreds.push_back(N); 282cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 283cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 284cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (BB == getHeader()) { 285cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); 286cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } else if (!OutsideLoopPreds.empty()) { 287cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // A non-header loop shouldn't be reachable from outside the loop, 288cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // though it is permitted if the predecessor is not itself actually 289cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // reachable. 290cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *EntryBB = BB->getParent()->begin(); 291cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (df_iterator<BlockT *> NI = df_begin(EntryBB), 292cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NE = df_end(EntryBB); NI != NE; ++NI) 293cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) 294cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(*NI != OutsideLoopPreds[i] && 295cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "Loop has multiple entry points!"); 296cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 297cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!"); 298cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!"); 299cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(BB != getHeader()->getParent()->begin() && 300cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "Loop contains function entry block!"); 301cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 302cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NumVisited++; 303cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 304cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 305cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(NumVisited == getNumBlocks() && "Unreachable block in loop"); 306cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 307cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Check the subloops. 308cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (iterator I = begin(), E = end(); I != E; ++I) 309cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Each block in each subloop should be contained within this loop. 310cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); 311cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BI != BE; ++BI) { 312cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) && 313cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "Loop does not contain all the blocks of a subloop!"); 314cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 315cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 316cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Check the parent loop pointer. 317cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (ParentLoop) { 318cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) != 319cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ParentLoop->end() && 320cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "Loop is not a subloop of its parent!"); 321cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 322cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#endif 323cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 324cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 325cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// verifyLoop - Verify loop structure of this loop and all nested loops. 326cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 327cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>::verifyLoopNest( 328cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick DenseSet<const LoopT*> *Loops) const { 329cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick Loops->insert(static_cast<const LoopT *>(this)); 330cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Verify this loop. 331cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick verifyLoop(); 332cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Verify the subloops. 333cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (iterator I = begin(), E = end(); I != E; ++I) 334cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick (*I)->verifyLoopNest(Loops); 335cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 336cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 337cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 338cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const { 339cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OS.indent(Depth*2) << "Loop at depth " << getLoopDepth() 340cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick << " containing: "; 341cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 342cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0; i < getBlocks().size(); ++i) { 343cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (i) OS << ","; 344cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *BB = getBlocks()[i]; 345cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick WriteAsOperand(OS, BB, false); 346cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (BB == getHeader()) OS << "<header>"; 347cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (BB == getLoopLatch()) OS << "<latch>"; 348cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (isLoopExiting(BB)) OS << "<exiting>"; 349cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 350cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OS << "\n"; 351cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 352cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (iterator I = begin(), E = end(); I != E; ++I) 353cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick (*I)->print(OS, Depth+2); 354cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 355cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 356cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 35737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the 35837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// result does / not depend on use list (block predecessor) order. 35937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 36037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 36137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Discover a subloop with the specified backedges such that: All blocks within 36237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// this loop are mapped to this loop or a subloop. And all subloops within this 36337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// loop have their parent loop set to this loop or a subloop. 36437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 36537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickstatic void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges, 36637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopInfoBase<BlockT, LoopT> *LI, 36737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DominatorTreeBase<BlockT> &DomTree) { 36837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 36937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 37037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick unsigned NumBlocks = 0; 37137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick unsigned NumSubloops = 0; 37237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 37337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a backward CFG traversal using a worklist. 37437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); 37537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (!ReverseCFGWorklist.empty()) { 37637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *PredBB = ReverseCFGWorklist.back(); 37737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.pop_back(); 37837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 37937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopT *Subloop = LI->getLoopFor(PredBB); 38037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!Subloop) { 38137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!DomTree.isReachableFromEntry(PredBB)) 38237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 38337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 38437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // This is an undiscovered block. Map it to the current loop. 38537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI->changeLoopFor(PredBB, L); 38637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++NumBlocks; 38737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (PredBB == L->getHeader()) 38837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 38937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Push all block predecessors on the worklist. 39037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), 39137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(PredBB), 39237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_end(PredBB)); 39337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 39437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick else { 39537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // This is a discovered block. Find its outermost discovered loop. 39637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (LoopT *Parent = Subloop->getParentLoop()) 39737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop = Parent; 39837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 39937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // If it is already discovered to be a subloop of this loop, continue. 40037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (Subloop == L) 40137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 40237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 40337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Discover a subloop of this loop. 40437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->setParentLoop(L); 40537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++NumSubloops; 40637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick NumBlocks += Subloop->getBlocks().capacity(); 40737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PredBB = Subloop->getHeader(); 40837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Continue traversal along predecessors that are not loop-back edges from 40937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // within this subloop tree itself. Note that a predecessor may directly 41037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // reach another subloop that is not yet discovered to be a subloop of 41137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // this loop, which we must traverse. 41237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 41337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(PredBB), 41437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) { 41537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (LI->getLoopFor(*PI) != Subloop) 41637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.push_back(*PI); 41737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 41837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 41937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 42037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick L->getSubLoopsVector().reserve(NumSubloops); 42137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick L->getBlocksVector().reserve(NumBlocks); 42237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 42337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 42437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricknamespace { 42537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Populate all loop data in a stable order during a single forward DFS. 42637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 42737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickclass PopulateLoopsDFS { 42837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 42937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef typename BlockTraits::ChildIteratorType SuccIterTy; 43037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 43137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopInfoBase<BlockT, LoopT> *LI; 43237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DenseSet<const BlockT *> VisitedBlocks; 43337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack; 43437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 43537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickpublic: 43637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li): 43737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI(li) {} 43837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 43937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick void traverse(BlockT *EntryBlock); 44037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 44137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickprotected: 442b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick void insertIntoLoop(BlockT *Block); 44337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 44437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *dfsSource() { return DFSStack.back().first; } 44537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SuccIterTy &dfsSucc() { return DFSStack.back().second; } 44637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); } 44737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 44837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick void pushBlock(BlockT *Block) { 44937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block))); 45037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 45137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick}; 45237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} // anonymous 45337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 45437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Top-level driver for the forward DFS within the loop. 45537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 45637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickvoid PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { 45737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick pushBlock(EntryBlock); 45837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick VisitedBlocks.insert(EntryBlock); 45937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (!DFSStack.empty()) { 46037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Traverse the leftmost path as far as possible. 46137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (dfsSucc() != dfsSuccEnd()) { 46237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *BB = *dfsSucc(); 46337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++dfsSucc(); 46437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!VisitedBlocks.insert(BB).second) 46537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 46637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 46737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Push the next DFS successor onto the stack. 46837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick pushBlock(BB); 46937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 47037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Visit the top of the stack in postorder and backtrack. 471b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick insertIntoLoop(dfsSource()); 47237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFSStack.pop_back(); 47337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 47437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 47537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 47637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Add a single Block to its ancestor loops in PostOrder. If the block is a 47737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// subloop header, add the subloop to its parent in PostOrder, then reverse the 47837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Block and Subloop vectors of the now complete subloop to achieve RPO. 47937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 480b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trickvoid PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { 481b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick LoopT *Subloop = LI->getLoopFor(Block); 482b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick if (Subloop && Block == Subloop->getHeader()) { 483b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick // We reach this point once per subloop after processing all the blocks in 484b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick // the subloop. 48537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (Subloop->getParentLoop()) 48637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); 48737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick else 48837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI->addTopLevelLoop(Subloop); 48937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 49037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // For convenience, Blocks and Subloops are inserted in postorder. Reverse 49137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // the lists, except for the loop header, which is always at the beginning. 49237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::reverse(Subloop->getBlocksVector().begin()+1, 49337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getBlocksVector().end()); 49437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::reverse(Subloop->getSubLoopsVector().begin(), 49537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getSubLoopsVector().end()); 496b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick 497b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick Subloop = Subloop->getParentLoop(); 49837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 499b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick for (; Subloop; Subloop = Subloop->getParentLoop()) 500b9598e41bc5187cfe8fb6345a90be27e6967958fAndrew Trick Subloop->getBlocksVector().push_back(Block); 50137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 50237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 50337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal 50437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// interleaved with backward CFG traversals within each subloop 50537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so 50637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// this part of the algorithm is linear in the number of CFG edges. Subloop and 50737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Block vectors are then populated during a single forward CFG traversal 50837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// (PopulateLoopDFS). 50937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 51037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// During the two CFG traversals each block is seen three times: 51137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 1) Discovered and mapped by a reverse CFG traversal. 51237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 2) Visited during a forward DFS CFG traversal. 51337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 3) Reverse-inserted in the loop in postorder following forward DFS. 51437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 51537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// The Block vectors are inclusive, so step 3 requires loop-depth number of 51637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// insertions per block. 51737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 51837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickvoid LoopInfoBase<BlockT, LoopT>:: 51937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew TrickAnalyze(DominatorTreeBase<BlockT> &DomTree) { 52037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 52137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Postorder traversal of the dominator tree. 52237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode(); 52337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot), 52437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { 52537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 52637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *Header = DomIter->getBlock(); 52737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SmallVector<BlockT *, 4> Backedges; 52837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 52937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Check each predecessor of the potential loop header. 53037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 53137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 53237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(Header), 53337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { 53437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 53537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *Backedge = *PI; 53637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 53737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // If Header dominates predBB, this is a new loop. Collect the backedges. 53837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (DomTree.dominates(Header, Backedge) 53937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick && DomTree.isReachableFromEntry(Backedge)) { 54037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Backedges.push_back(Backedge); 54137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 54237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 54337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a backward CFG traversal to discover and map blocks in this loop. 54437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!Backedges.empty()) { 54537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopT *L = new LoopT(Header); 54637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree); 54737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 54837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 54937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a single forward CFG traversal to populate block and subloop 55037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // vectors for all loops. 55137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PopulateLoopsDFS<BlockT, LoopT> DFS(this); 55237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFS.traverse(DomRoot->getBlock()); 55337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 55437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 555cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// Debugging 556cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 557cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { 558cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 559cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TopLevelLoops[i]->print(OS); 560cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#if 0 561cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), 562cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick E = BBMap.end(); I != E; ++I) 563cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OS << "BB '" << I->first->getName() << "' level = " 564cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick << I->second->getLoopDepth() << "\n"; 565cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#endif 566cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 567cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 568cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} // End llvm namespace 569cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 570cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#endif 571