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