LoopInfoImpl.h revision 37aa33bc11c01a7142bfa2428a5a4d219b07b6c3
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 15cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H 16cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#define LLVM_ANALYSIS_LOOP_INFO_IMPL_H 17cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 18cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#include "llvm/Analysis/LoopInfo.h" 1937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick#include "llvm/ADT/PostOrderIterator.h" 20cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 21cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricknamespace llvm { 22cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 23cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick//===----------------------------------------------------------------------===// 24cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// APIs for simple analysis of the loop. See header notes. 25cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 26cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitingBlocks - Return all blocks inside the loop that have successors 27cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// outside of the loop. These are the blocks _inside of the current loop_ 28cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// which branch out. The returned list is always unique. 29cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 30cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 31cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 32cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { 33cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 34cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 35cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 36cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::sort(LoopBBs.begin(), LoopBBs.end()); 37cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 38cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 39cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 40cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 41cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 42cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 43cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) { 44cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 45cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitingBlocks.push_back(*BI); 46cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick break; 47cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 48cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 49cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 50cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitingBlock - If getExitingBlocks would return exactly one block, 51cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// return that block. Otherwise return null. 52cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 53cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { 54cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 8> ExitingBlocks; 55cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick getExitingBlocks(ExitingBlocks); 56cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (ExitingBlocks.size() == 1) 57cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return ExitingBlocks[0]; 58cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; 59cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 60cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 61cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitBlocks - Return all of the successor blocks of this loop. These 62cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// are the blocks _outside of the current loop_ which are branched to. 63cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 64cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 65cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 66cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { 67cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 68cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 69cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 70cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::sort(LoopBBs.begin(), LoopBBs.end()); 71cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 72cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 73cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 74cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 75cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 76cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 77cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 78cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 79cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitBlocks.push_back(*I); 80cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 81cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 82cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitBlock - If getExitBlocks would return exactly one block, 83cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// return that block. Otherwise return null. 84cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 85cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { 86cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 8> ExitBlocks; 87cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick getExitBlocks(ExitBlocks); 88cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (ExitBlocks.size() == 1) 89cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return ExitBlocks[0]; 90cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; 91cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 92cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 93cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). 94cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 95cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopBase<BlockT, LoopT>:: 96cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickgetExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { 97cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Sort the blocks vector so that we can use binary search to do quick 98cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // lookups. 99cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); 100cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick array_pod_sort(LoopBBs.begin(), LoopBBs.end()); 101cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 102cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 103cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) 104cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename BlockTraits::ChildIteratorType I = 105cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); 106cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) 107cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) 108cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Not in current loop? It must be an exit block. 109cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ExitEdges.push_back(Edge(*BI, *I)); 110cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 111cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 112cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getLoopPreheader - If there is a preheader for this loop, return it. A 113cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// loop has a preheader if there is only one edge to the header of the loop 114cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// from outside of the loop. If this is the case, the block branching to the 115cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// header of the loop is the preheader node. 116cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 117cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// This method returns null if there is no preheader for the loop. 118cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 119cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 120cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { 121cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Keep track of nodes outside the loop branching to the header... 122cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Out = getLoopPredecessor(); 123cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!Out) return 0; 124cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 125cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Make sure there is only one exit out of the preheader. 126cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 127cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 128cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ++SI; 129cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (SI != BlockTraits::child_end(Out)) 130cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return 0; // Multiple exits from the block, must not be a preheader. 131cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 132cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // The predecessor has exactly one successor, so it is a preheader. 133cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return Out; 134cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 135cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 136cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// getLoopPredecessor - If the given loop's header has exactly one unique 137cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// predecessor outside the loop, return it. Otherwise return null. 138cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// This is less strict that the loop "preheader" concept, which requires 139cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// the predecessor to have exactly one successor. 140cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 141cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 142cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickBlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { 143cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Keep track of nodes outside the loop branching to the header... 144cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Out = 0; 145cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 146cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Loop over the predecessors of the header node... 147cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *Header = getHeader(); 148cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 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//===----------------------------------------------------------------------===// 357cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// LoopInfo - This class builds and contains all of the top level loop 358cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// structures in the specified function. 359cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// 360cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 361cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 362cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopInfoBase<BlockT, LoopT>::Calculate(DominatorTreeBase<BlockT> &DT) { 363cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *RootNode = DT.getRootNode()->getBlock(); 364cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 365cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (df_iterator<BlockT*> NI = df_begin(RootNode), 366cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NE = df_end(RootNode); NI != NE; ++NI) 367cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (LoopT *L = ConsiderForLoop(*NI, DT)) 368cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TopLevelLoops.push_back(L); 369cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 370cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 371cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 372cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickLoopT *LoopInfoBase<BlockT, LoopT>:: 373cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) { 374cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (BBMap.count(BB)) return 0; // Haven't processed this node? 375cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 376cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::vector<BlockT *> TodoStack; 377cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 378cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Scan the predecessors of BB, checking to see if BB dominates any of 379cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // them. This identifies backedges which target this node... 380cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 381cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename InvBlockTraits::ChildIteratorType I = 382cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB); 383cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick I != E; ++I) { 384cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename InvBlockTraits::NodeType *N = *I; 385cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // If BB dominates its predecessor... 386cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (DT.dominates(BB, N) && DT.isReachableFromEntry(N)) 387cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TodoStack.push_back(N); 388cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 389cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 390cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (TodoStack.empty()) return 0; // No backedges to this block... 391cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 392cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Create a new loop to represent this basic block... 393cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *L = new LoopT(BB); 394cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BBMap[BB] = L; 395cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 396cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick while (!TodoStack.empty()) { // Process all the nodes in the loop 397cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *X = TodoStack.back(); 398cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TodoStack.pop_back(); 399cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 400cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (!L->contains(X) && // As of yet unprocessed?? 401cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick DT.isReachableFromEntry(X)) { 402cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Check to see if this block already belongs to a loop. If this occurs 403cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // then we have a case where a loop that is supposed to be a child of 404cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // the current loop was processed before the current loop. When this 405cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // occurs, this child loop gets added to a part of the current loop, 406cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // making it a sibling to the current loop. We have to reparent this 407cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // loop. 408cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (LoopT *SubLoop = 409cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick const_cast<LoopT *>(getLoopFor(X))) 410cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){ 411cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Remove the subloop from its current parent... 412cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L); 413cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent 414cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename std::vector<LoopT *>::iterator I = 415cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop); 416cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?"); 417cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SLP->SubLoops.erase(I); // Remove from parent... 418cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 419cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Add the subloop to THIS loop... 420cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick SubLoop->ParentLoop = L; 421cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L->SubLoops.push_back(SubLoop); 422cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 423cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 424cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Normal case, add the block to our loop... 425cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L->Blocks.push_back(X); 426cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 427cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 428cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 429cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Add all of the predecessors of X to the end of the work stack... 430cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X), 431cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InvBlockTraits::child_end(X)); 432cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 433cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 434cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 435cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // If there are any loops nested within this loop, create them now! 436cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), 437cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick E = L->Blocks.end(); I != E; ++I) 438cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) { 439cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L->SubLoops.push_back(NewLoop); 440cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NewLoop->ParentLoop = L; 441cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 442cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 443cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Add the basic blocks that comprise this loop to the BBMap so that this 444cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // loop can be found for them. 445cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // 446cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), 447cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick E = L->Blocks.end(); I != E; ++I) 448cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BBMap.insert(std::make_pair(*I, L)); 449cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 450cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Now that we have a list of all of the child loops of this loop, check to 451cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // see if any of them should actually be nested inside of each other. We 452cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // can accidentally pull loops our of their parents, so we must make sure to 453cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // organize the loop nests correctly now. 454cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick { 455cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::map<BlockT *, LoopT *> ContainingLoops; 456cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0; i != L->SubLoops.size(); ++i) { 457cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *Child = L->SubLoops[i]; 458cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(Child->getParentLoop() == L && "Not proper child loop?"); 459cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 460cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) { 461cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // If there is already a loop which contains this loop, move this loop 462cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // into the containing loop. 463cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick MoveSiblingLoopInto(Child, ContainingLoop); 464cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick --i; // The loop got removed from the SubLoops list. 465cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } else { 466cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // This is currently considered to be a top-level loop. Check to see 467cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // if any of the contained blocks are loop headers for subloops we 468cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // have already processed. 469cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) { 470cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]]; 471cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (BlockLoop == 0) { // Child block not processed yet... 472cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockLoop = Child; 473cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } else if (BlockLoop != Child) { 474cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *SubLoop = BlockLoop; 475cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Reparent all of the blocks which used to belong to BlockLoops 476cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j) 477cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick ContainingLoops[SubLoop->Blocks[j]] = Child; 478cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 479cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // There is already a loop which contains this block, that means 480cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // that we should reparent the loop which the block is currently 481cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // considered to belong to to be a child of this loop. 482cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick MoveSiblingLoopInto(SubLoop, Child); 483cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick --i; // We just shrunk the SubLoops list. 484cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 485cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 486cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 487cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 488cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 489cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 490cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return L; 491cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 492cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 493cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// MoveSiblingLoopInto - This method moves the NewChild loop to live inside 494cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// of the NewParent Loop, instead of being a sibling of it. 495cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 496cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopInfoBase<BlockT, LoopT>:: 497cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew TrickMoveSiblingLoopInto(LoopT *NewChild, LoopT *NewParent) { 498cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick LoopT *OldParent = NewChild->getParentLoop(); 499cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(OldParent && OldParent == NewParent->getParentLoop() && 500cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NewChild != NewParent && "Not sibling loops!"); 501cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 502cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Remove NewChild from being a child of OldParent 503cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick typename std::vector<LoopT *>::iterator I = 504cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), 505cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NewChild); 506cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??"); 507cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OldParent->SubLoops.erase(I); // Remove from parent's subloops list 508cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick NewChild->ParentLoop = 0; 509cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 510cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InsertLoopInto(NewChild, NewParent); 511cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 512cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 513cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// InsertLoopInto - This inserts loop L into the specified parent loop. If 514cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// the parent loop contains a loop which should contain L, the loop gets 515cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick/// inserted into L instead. 516cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 517cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopInfoBase<BlockT, LoopT>::InsertLoopInto(LoopT *L, LoopT *Parent) { 518cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick BlockT *LHeader = L->getHeader(); 519cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick assert(Parent->contains(LHeader) && 520cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick "This loop should not be inserted here!"); 521cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 522cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // Check to see if it belongs in a child loop... 523cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size()); 524cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick i != e; ++i) 525cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick if (Parent->SubLoops[i]->contains(LHeader)) { 526cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick InsertLoopInto(L, Parent->SubLoops[i]); 527cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick return; 528cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick } 529cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 530cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick // If not, insert it here! 531cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick Parent->SubLoops.push_back(L); 532cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick L->ParentLoop = Parent; 533cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 534cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 53537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick//===----------------------------------------------------------------------===// 53637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the 53737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// result does / not depend on use list (block predecessor) order. 53837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 53937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 54037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Discover a subloop with the specified backedges such that: All blocks within 54137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// this loop are mapped to this loop or a subloop. And all subloops within this 54237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// loop have their parent loop set to this loop or a subloop. 54337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 54437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickstatic void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges, 54537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopInfoBase<BlockT, LoopT> *LI, 54637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DominatorTreeBase<BlockT> &DomTree) { 54737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 54837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 54937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick unsigned NumBlocks = 0; 55037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick unsigned NumSubloops = 0; 55137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 55237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a backward CFG traversal using a worklist. 55337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); 55437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (!ReverseCFGWorklist.empty()) { 55537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *PredBB = ReverseCFGWorklist.back(); 55637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.pop_back(); 55737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 55837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopT *Subloop = LI->getLoopFor(PredBB); 55937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!Subloop) { 56037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!DomTree.isReachableFromEntry(PredBB)) 56137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 56237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 56337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // This is an undiscovered block. Map it to the current loop. 56437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI->changeLoopFor(PredBB, L); 56537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++NumBlocks; 56637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (PredBB == L->getHeader()) 56737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 56837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Push all block predecessors on the worklist. 56937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), 57037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(PredBB), 57137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_end(PredBB)); 57237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 57337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick else { 57437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // This is a discovered block. Find its outermost discovered loop. 57537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (LoopT *Parent = Subloop->getParentLoop()) 57637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop = Parent; 57737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 57837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // If it is already discovered to be a subloop of this loop, continue. 57937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (Subloop == L) 58037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 58137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 58237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Discover a subloop of this loop. 58337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->setParentLoop(L); 58437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++NumSubloops; 58537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick NumBlocks += Subloop->getBlocks().capacity(); 58637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PredBB = Subloop->getHeader(); 58737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Continue traversal along predecessors that are not loop-back edges from 58837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // within this subloop tree itself. Note that a predecessor may directly 58937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // reach another subloop that is not yet discovered to be a subloop of 59037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // this loop, which we must traverse. 59137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 59237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(PredBB), 59337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) { 59437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (LI->getLoopFor(*PI) != Subloop) 59537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ReverseCFGWorklist.push_back(*PI); 59637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 59737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 59837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 59937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick L->getSubLoopsVector().reserve(NumSubloops); 60037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick L->getBlocksVector().reserve(NumBlocks); 60137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 60237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 60337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricknamespace { 60437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Populate all loop data in a stable order during a single forward DFS. 60537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 60637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickclass PopulateLoopsDFS { 60737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<BlockT*> BlockTraits; 60837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef typename BlockTraits::ChildIteratorType SuccIterTy; 60937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 61037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopInfoBase<BlockT, LoopT> *LI; 61137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DenseSet<const BlockT *> VisitedBlocks; 61237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack; 61337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 61437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickpublic: 61537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li): 61637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI(li) {} 61737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 61837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick void traverse(BlockT *EntryBlock); 61937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 62037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickprotected: 62137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick void reverseInsertIntoLoop(BlockT *Block); 62237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 62337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *dfsSource() { return DFSStack.back().first; } 62437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SuccIterTy &dfsSucc() { return DFSStack.back().second; } 62537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); } 62637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 62737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick void pushBlock(BlockT *Block) { 62837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block))); 62937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 63037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick}; 63137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} // anonymous 63237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 63337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Top-level driver for the forward DFS within the loop. 63437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 63537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickvoid PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { 63637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick pushBlock(EntryBlock); 63737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick VisitedBlocks.insert(EntryBlock); 63837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (!DFSStack.empty()) { 63937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Traverse the leftmost path as far as possible. 64037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick while (dfsSucc() != dfsSuccEnd()) { 64137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *BB = *dfsSucc(); 64237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick ++dfsSucc(); 64337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!VisitedBlocks.insert(BB).second) 64437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 64537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 64637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Push the next DFS successor onto the stack. 64737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick pushBlock(BB); 64837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 64937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Visit the top of the stack in postorder and backtrack. 65037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick reverseInsertIntoLoop(dfsSource()); 65137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFSStack.pop_back(); 65237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 65337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 65437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 65537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Add a single Block to its ancestor loops in PostOrder. If the block is a 65637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// subloop header, add the subloop to its parent in PostOrder, then reverse the 65737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Block and Subloop vectors of the now complete subloop to achieve RPO. 65837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 65937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickvoid PopulateLoopsDFS<BlockT, LoopT>::reverseInsertIntoLoop(BlockT *Block) { 66037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (LoopT *Subloop = LI->getLoopFor(Block); 66137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop; Subloop = Subloop->getParentLoop()) { 66237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 66337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (Block != Subloop->getHeader()) { 66437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getBlocksVector().push_back(Block); 66537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick continue; 66637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 66737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (Subloop->getParentLoop()) 66837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); 66937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick else 67037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LI->addTopLevelLoop(Subloop); 67137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 67237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // For convenience, Blocks and Subloops are inserted in postorder. Reverse 67337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // the lists, except for the loop header, which is always at the beginning. 67437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::reverse(Subloop->getBlocksVector().begin()+1, 67537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getBlocksVector().end()); 67637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick std::reverse(Subloop->getSubLoopsVector().begin(), 67737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Subloop->getSubLoopsVector().end()); 67837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 67937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 68037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 68137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal 68237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// interleaved with backward CFG traversals within each subloop 68337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so 68437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// this part of the algorithm is linear in the number of CFG edges. Subloop and 68537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// Block vectors are then populated during a single forward CFG traversal 68637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// (PopulateLoopDFS). 68737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 68837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// During the two CFG traversals each block is seen three times: 68937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 1) Discovered and mapped by a reverse CFG traversal. 69037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 2) Visited during a forward DFS CFG traversal. 69137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 3) Reverse-inserted in the loop in postorder following forward DFS. 69237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// 69337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// The Block vectors are inclusive, so step 3 requires loop-depth number of 69437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick/// insertions per block. 69537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Tricktemplate<class BlockT, class LoopT> 69637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trickvoid LoopInfoBase<BlockT, LoopT>:: 69737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew TrickAnalyze(DominatorTreeBase<BlockT> &DomTree) { 69837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 69937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Postorder traversal of the dominator tree. 70037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode(); 70137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot), 70237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) { 70337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 70437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *Header = DomIter->getBlock(); 70537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick SmallVector<BlockT *, 4> Backedges; 70637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 70737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Check each predecessor of the potential loop header. 70837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; 70937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick for (typename InvBlockTraits::ChildIteratorType PI = 71037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick InvBlockTraits::child_begin(Header), 71137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) { 71237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 71337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick BlockT *Backedge = *PI; 71437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 71537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // If Header dominates predBB, this is a new loop. Collect the backedges. 71637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (DomTree.dominates(Header, Backedge) 71737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick && DomTree.isReachableFromEntry(Backedge)) { 71837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick Backedges.push_back(Backedge); 71937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 72037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 72137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a backward CFG traversal to discover and map blocks in this loop. 72237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick if (!Backedges.empty()) { 72337aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick LoopT *L = new LoopT(Header); 72437aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree); 72537aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 72637aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick } 72737aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // Perform a single forward CFG traversal to populate block and subloop 72837aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick // vectors for all loops. 72937aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick PopulateLoopsDFS<BlockT, LoopT> DFS(this); 73037aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick DFS.traverse(DomRoot->getBlock()); 73137aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick} 73237aa33bc11c01a7142bfa2428a5a4d219b07b6c3Andrew Trick 733cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// Debugging 734cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate<class BlockT, class LoopT> 735cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trickvoid LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { 736cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 737cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick TopLevelLoops[i]->print(OS); 738cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#if 0 739cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), 740cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick E = BBMap.end(); I != E; ++I) 741cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick OS << "BB '" << I->first->getName() << "' level = " 742cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick << I->second->getLoopDepth() << "\n"; 743cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#endif 744cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} 745cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 746cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick} // End llvm namespace 747cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick 748cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick#endif 749