1*06c3fb27SDimitry Andric //===- GenericLoopInfoImp.h - Generic Loop Info Implementation --*- C++ -*-===// 2*06c3fb27SDimitry Andric // 3*06c3fb27SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*06c3fb27SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 5*06c3fb27SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*06c3fb27SDimitry Andric // 7*06c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 8*06c3fb27SDimitry Andric // 9*06c3fb27SDimitry Andric // This fle contains the implementation of GenericLoopInfo. It should only be 10*06c3fb27SDimitry Andric // included in files that explicitly instantiate a GenericLoopInfo. 11*06c3fb27SDimitry Andric // 12*06c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 13*06c3fb27SDimitry Andric 14*06c3fb27SDimitry Andric #ifndef LLVM_SUPPORT_GENERICLOOPINFOIMPL_H 15*06c3fb27SDimitry Andric #define LLVM_SUPPORT_GENERICLOOPINFOIMPL_H 16*06c3fb27SDimitry Andric 17*06c3fb27SDimitry Andric #include "llvm/ADT/DepthFirstIterator.h" 18*06c3fb27SDimitry Andric #include "llvm/ADT/PostOrderIterator.h" 19*06c3fb27SDimitry Andric #include "llvm/ADT/STLExtras.h" 20*06c3fb27SDimitry Andric #include "llvm/ADT/SetOperations.h" 21*06c3fb27SDimitry Andric #include "llvm/Support/GenericLoopInfo.h" 22*06c3fb27SDimitry Andric 23*06c3fb27SDimitry Andric namespace llvm { 24*06c3fb27SDimitry Andric 25*06c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 26*06c3fb27SDimitry Andric // APIs for simple analysis of the loop. See header notes. 27*06c3fb27SDimitry Andric 28*06c3fb27SDimitry Andric /// getExitingBlocks - Return all blocks inside the loop that have successors 29*06c3fb27SDimitry Andric /// outside of the loop. These are the blocks _inside of the current loop_ 30*06c3fb27SDimitry Andric /// which branch out. The returned list is always unique. 31*06c3fb27SDimitry Andric /// 32*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 33*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitingBlocks( 34*06c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitingBlocks) const { 35*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 36*06c3fb27SDimitry Andric for (const auto BB : blocks()) 37*06c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB)) 38*06c3fb27SDimitry Andric if (!contains(Succ)) { 39*06c3fb27SDimitry Andric // Not in current loop? It must be an exit block. 40*06c3fb27SDimitry Andric ExitingBlocks.push_back(BB); 41*06c3fb27SDimitry Andric break; 42*06c3fb27SDimitry Andric } 43*06c3fb27SDimitry Andric } 44*06c3fb27SDimitry Andric 45*06c3fb27SDimitry Andric /// getExitingBlock - If getExitingBlocks would return exactly one block, 46*06c3fb27SDimitry Andric /// return that block. Otherwise return null. 47*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 48*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { 49*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 50*06c3fb27SDimitry Andric auto notInLoop = [&](BlockT *BB) { return !contains(BB); }; 51*06c3fb27SDimitry Andric auto isExitBlock = [&](BlockT *BB, bool AllowRepeats) -> BlockT * { 52*06c3fb27SDimitry Andric assert(!AllowRepeats && "Unexpected parameter value."); 53*06c3fb27SDimitry Andric // Child not in current loop? It must be an exit block. 54*06c3fb27SDimitry Andric return any_of(children<BlockT *>(BB), notInLoop) ? BB : nullptr; 55*06c3fb27SDimitry Andric }; 56*06c3fb27SDimitry Andric 57*06c3fb27SDimitry Andric return find_singleton<BlockT>(blocks(), isExitBlock); 58*06c3fb27SDimitry Andric } 59*06c3fb27SDimitry Andric 60*06c3fb27SDimitry Andric /// getExitBlocks - Return all of the successor blocks of this loop. These 61*06c3fb27SDimitry Andric /// are the blocks _outside of the current loop_ which are branched to. 62*06c3fb27SDimitry Andric /// 63*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 64*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitBlocks( 65*06c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const { 66*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 67*06c3fb27SDimitry Andric for (const auto BB : blocks()) 68*06c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB)) 69*06c3fb27SDimitry Andric if (!contains(Succ)) 70*06c3fb27SDimitry Andric // Not in current loop? It must be an exit block. 71*06c3fb27SDimitry Andric ExitBlocks.push_back(Succ); 72*06c3fb27SDimitry Andric } 73*06c3fb27SDimitry Andric 74*06c3fb27SDimitry Andric /// getExitBlock - If getExitBlocks would return exactly one block, 75*06c3fb27SDimitry Andric /// return that block. Otherwise return null. 76*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 77*06c3fb27SDimitry Andric std::pair<BlockT *, bool> getExitBlockHelper(const LoopBase<BlockT, LoopT> *L, 78*06c3fb27SDimitry Andric bool Unique) { 79*06c3fb27SDimitry Andric assert(!L->isInvalid() && "Loop not in a valid state!"); 80*06c3fb27SDimitry Andric auto notInLoop = [&](BlockT *BB, 81*06c3fb27SDimitry Andric bool AllowRepeats) -> std::pair<BlockT *, bool> { 82*06c3fb27SDimitry Andric assert(AllowRepeats == Unique && "Unexpected parameter value."); 83*06c3fb27SDimitry Andric return {!L->contains(BB) ? BB : nullptr, false}; 84*06c3fb27SDimitry Andric }; 85*06c3fb27SDimitry Andric auto singleExitBlock = [&](BlockT *BB, 86*06c3fb27SDimitry Andric bool AllowRepeats) -> std::pair<BlockT *, bool> { 87*06c3fb27SDimitry Andric assert(AllowRepeats == Unique && "Unexpected parameter value."); 88*06c3fb27SDimitry Andric return find_singleton_nested<BlockT>(children<BlockT *>(BB), notInLoop, 89*06c3fb27SDimitry Andric AllowRepeats); 90*06c3fb27SDimitry Andric }; 91*06c3fb27SDimitry Andric return find_singleton_nested<BlockT>(L->blocks(), singleExitBlock, Unique); 92*06c3fb27SDimitry Andric } 93*06c3fb27SDimitry Andric 94*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 95*06c3fb27SDimitry Andric bool LoopBase<BlockT, LoopT>::hasNoExitBlocks() const { 96*06c3fb27SDimitry Andric auto RC = getExitBlockHelper(this, false); 97*06c3fb27SDimitry Andric if (RC.second) 98*06c3fb27SDimitry Andric // found multiple exit blocks 99*06c3fb27SDimitry Andric return false; 100*06c3fb27SDimitry Andric // return true if there is no exit block 101*06c3fb27SDimitry Andric return !RC.first; 102*06c3fb27SDimitry Andric } 103*06c3fb27SDimitry Andric 104*06c3fb27SDimitry Andric /// getExitBlock - If getExitBlocks would return exactly one block, 105*06c3fb27SDimitry Andric /// return that block. Otherwise return null. 106*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 107*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { 108*06c3fb27SDimitry Andric return getExitBlockHelper(this, false).first; 109*06c3fb27SDimitry Andric } 110*06c3fb27SDimitry Andric 111*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 112*06c3fb27SDimitry Andric bool LoopBase<BlockT, LoopT>::hasDedicatedExits() const { 113*06c3fb27SDimitry Andric // Each predecessor of each exit block of a normal loop is contained 114*06c3fb27SDimitry Andric // within the loop. 115*06c3fb27SDimitry Andric SmallVector<BlockT *, 4> UniqueExitBlocks; 116*06c3fb27SDimitry Andric getUniqueExitBlocks(UniqueExitBlocks); 117*06c3fb27SDimitry Andric for (BlockT *EB : UniqueExitBlocks) 118*06c3fb27SDimitry Andric for (BlockT *Predecessor : children<Inverse<BlockT *>>(EB)) 119*06c3fb27SDimitry Andric if (!contains(Predecessor)) 120*06c3fb27SDimitry Andric return false; 121*06c3fb27SDimitry Andric // All the requirements are met. 122*06c3fb27SDimitry Andric return true; 123*06c3fb27SDimitry Andric } 124*06c3fb27SDimitry Andric 125*06c3fb27SDimitry Andric // Helper function to get unique loop exits. Pred is a predicate pointing to 126*06c3fb27SDimitry Andric // BasicBlocks in a loop which should be considered to find loop exits. 127*06c3fb27SDimitry Andric template <class BlockT, class LoopT, typename PredicateT> 128*06c3fb27SDimitry Andric void getUniqueExitBlocksHelper(const LoopT *L, 129*06c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks, 130*06c3fb27SDimitry Andric PredicateT Pred) { 131*06c3fb27SDimitry Andric assert(!L->isInvalid() && "Loop not in a valid state!"); 132*06c3fb27SDimitry Andric SmallPtrSet<BlockT *, 32> Visited; 133*06c3fb27SDimitry Andric auto Filtered = make_filter_range(L->blocks(), Pred); 134*06c3fb27SDimitry Andric for (BlockT *BB : Filtered) 135*06c3fb27SDimitry Andric for (BlockT *Successor : children<BlockT *>(BB)) 136*06c3fb27SDimitry Andric if (!L->contains(Successor)) 137*06c3fb27SDimitry Andric if (Visited.insert(Successor).second) 138*06c3fb27SDimitry Andric ExitBlocks.push_back(Successor); 139*06c3fb27SDimitry Andric } 140*06c3fb27SDimitry Andric 141*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 142*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getUniqueExitBlocks( 143*06c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const { 144*06c3fb27SDimitry Andric getUniqueExitBlocksHelper(this, ExitBlocks, 145*06c3fb27SDimitry Andric [](const BlockT *BB) { return true; }); 146*06c3fb27SDimitry Andric } 147*06c3fb27SDimitry Andric 148*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 149*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getUniqueNonLatchExitBlocks( 150*06c3fb27SDimitry Andric SmallVectorImpl<BlockT *> &ExitBlocks) const { 151*06c3fb27SDimitry Andric const BlockT *Latch = getLoopLatch(); 152*06c3fb27SDimitry Andric assert(Latch && "Latch block must exists"); 153*06c3fb27SDimitry Andric getUniqueExitBlocksHelper(this, ExitBlocks, 154*06c3fb27SDimitry Andric [Latch](const BlockT *BB) { return BB != Latch; }); 155*06c3fb27SDimitry Andric } 156*06c3fb27SDimitry Andric 157*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 158*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getUniqueExitBlock() const { 159*06c3fb27SDimitry Andric return getExitBlockHelper(this, true).first; 160*06c3fb27SDimitry Andric } 161*06c3fb27SDimitry Andric 162*06c3fb27SDimitry Andric /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). 163*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 164*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::getExitEdges( 165*06c3fb27SDimitry Andric SmallVectorImpl<Edge> &ExitEdges) const { 166*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 167*06c3fb27SDimitry Andric for (const auto BB : blocks()) 168*06c3fb27SDimitry Andric for (auto *Succ : children<BlockT *>(BB)) 169*06c3fb27SDimitry Andric if (!contains(Succ)) 170*06c3fb27SDimitry Andric // Not in current loop? It must be an exit block. 171*06c3fb27SDimitry Andric ExitEdges.emplace_back(BB, Succ); 172*06c3fb27SDimitry Andric } 173*06c3fb27SDimitry Andric 174*06c3fb27SDimitry Andric namespace detail { 175*06c3fb27SDimitry Andric template <class BlockT> 176*06c3fb27SDimitry Andric using has_hoist_check = decltype(&BlockT::isLegalToHoistInto); 177*06c3fb27SDimitry Andric 178*06c3fb27SDimitry Andric template <class BlockT> 179*06c3fb27SDimitry Andric using detect_has_hoist_check = llvm::is_detected<has_hoist_check, BlockT>; 180*06c3fb27SDimitry Andric 181*06c3fb27SDimitry Andric /// SFINAE functions that dispatch to the isLegalToHoistInto member function or 182*06c3fb27SDimitry Andric /// return false, if it doesn't exist. 183*06c3fb27SDimitry Andric template <class BlockT> bool isLegalToHoistInto(BlockT *Block) { 184*06c3fb27SDimitry Andric if constexpr (detect_has_hoist_check<BlockT>::value) 185*06c3fb27SDimitry Andric return Block->isLegalToHoistInto(); 186*06c3fb27SDimitry Andric return false; 187*06c3fb27SDimitry Andric } 188*06c3fb27SDimitry Andric } // namespace detail 189*06c3fb27SDimitry Andric 190*06c3fb27SDimitry Andric /// getLoopPreheader - If there is a preheader for this loop, return it. A 191*06c3fb27SDimitry Andric /// loop has a preheader if there is only one edge to the header of the loop 192*06c3fb27SDimitry Andric /// from outside of the loop and it is legal to hoist instructions into the 193*06c3fb27SDimitry Andric /// predecessor. If this is the case, the block branching to the header of the 194*06c3fb27SDimitry Andric /// loop is the preheader node. 195*06c3fb27SDimitry Andric /// 196*06c3fb27SDimitry Andric /// This method returns null if there is no preheader for the loop. 197*06c3fb27SDimitry Andric /// 198*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 199*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const { 200*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 201*06c3fb27SDimitry Andric // Keep track of nodes outside the loop branching to the header... 202*06c3fb27SDimitry Andric BlockT *Out = getLoopPredecessor(); 203*06c3fb27SDimitry Andric if (!Out) 204*06c3fb27SDimitry Andric return nullptr; 205*06c3fb27SDimitry Andric 206*06c3fb27SDimitry Andric // Make sure we are allowed to hoist instructions into the predecessor. 207*06c3fb27SDimitry Andric if (!detail::isLegalToHoistInto(Out)) 208*06c3fb27SDimitry Andric return nullptr; 209*06c3fb27SDimitry Andric 210*06c3fb27SDimitry Andric // Make sure there is only one exit out of the preheader. 211*06c3fb27SDimitry Andric typedef GraphTraits<BlockT *> BlockTraits; 212*06c3fb27SDimitry Andric typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 213*06c3fb27SDimitry Andric ++SI; 214*06c3fb27SDimitry Andric if (SI != BlockTraits::child_end(Out)) 215*06c3fb27SDimitry Andric return nullptr; // Multiple exits from the block, must not be a preheader. 216*06c3fb27SDimitry Andric 217*06c3fb27SDimitry Andric // The predecessor has exactly one successor, so it is a preheader. 218*06c3fb27SDimitry Andric return Out; 219*06c3fb27SDimitry Andric } 220*06c3fb27SDimitry Andric 221*06c3fb27SDimitry Andric /// getLoopPredecessor - If the given loop's header has exactly one unique 222*06c3fb27SDimitry Andric /// predecessor outside the loop, return it. Otherwise return null. 223*06c3fb27SDimitry Andric /// This is less strict that the loop "preheader" concept, which requires 224*06c3fb27SDimitry Andric /// the predecessor to have exactly one successor. 225*06c3fb27SDimitry Andric /// 226*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 227*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { 228*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 229*06c3fb27SDimitry Andric // Keep track of nodes outside the loop branching to the header... 230*06c3fb27SDimitry Andric BlockT *Out = nullptr; 231*06c3fb27SDimitry Andric 232*06c3fb27SDimitry Andric // Loop over the predecessors of the header node... 233*06c3fb27SDimitry Andric BlockT *Header = getHeader(); 234*06c3fb27SDimitry Andric for (const auto Pred : children<Inverse<BlockT *>>(Header)) { 235*06c3fb27SDimitry Andric if (!contains(Pred)) { // If the block is not in the loop... 236*06c3fb27SDimitry Andric if (Out && Out != Pred) 237*06c3fb27SDimitry Andric return nullptr; // Multiple predecessors outside the loop 238*06c3fb27SDimitry Andric Out = Pred; 239*06c3fb27SDimitry Andric } 240*06c3fb27SDimitry Andric } 241*06c3fb27SDimitry Andric 242*06c3fb27SDimitry Andric return Out; 243*06c3fb27SDimitry Andric } 244*06c3fb27SDimitry Andric 245*06c3fb27SDimitry Andric /// getLoopLatch - If there is a single latch block for this loop, return it. 246*06c3fb27SDimitry Andric /// A latch block is a block that contains a branch back to the header. 247*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 248*06c3fb27SDimitry Andric BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { 249*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 250*06c3fb27SDimitry Andric BlockT *Header = getHeader(); 251*06c3fb27SDimitry Andric BlockT *Latch = nullptr; 252*06c3fb27SDimitry Andric for (const auto Pred : children<Inverse<BlockT *>>(Header)) { 253*06c3fb27SDimitry Andric if (contains(Pred)) { 254*06c3fb27SDimitry Andric if (Latch) 255*06c3fb27SDimitry Andric return nullptr; 256*06c3fb27SDimitry Andric Latch = Pred; 257*06c3fb27SDimitry Andric } 258*06c3fb27SDimitry Andric } 259*06c3fb27SDimitry Andric 260*06c3fb27SDimitry Andric return Latch; 261*06c3fb27SDimitry Andric } 262*06c3fb27SDimitry Andric 263*06c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 264*06c3fb27SDimitry Andric // APIs for updating loop information after changing the CFG 265*06c3fb27SDimitry Andric // 266*06c3fb27SDimitry Andric 267*06c3fb27SDimitry Andric /// addBasicBlockToLoop - This method is used by other analyses to update loop 268*06c3fb27SDimitry Andric /// information. NewBB is set to be a new member of the current loop. 269*06c3fb27SDimitry Andric /// Because of this, it is added as a member of all parent loops, and is added 270*06c3fb27SDimitry Andric /// to the specified LoopInfo object as being in the current basic block. It 271*06c3fb27SDimitry Andric /// is not valid to replace the loop header with this method. 272*06c3fb27SDimitry Andric /// 273*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 274*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::addBasicBlockToLoop( 275*06c3fb27SDimitry Andric BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { 276*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 277*06c3fb27SDimitry Andric #ifndef NDEBUG 278*06c3fb27SDimitry Andric if (!Blocks.empty()) { 279*06c3fb27SDimitry Andric auto SameHeader = LIB[getHeader()]; 280*06c3fb27SDimitry Andric assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() && 281*06c3fb27SDimitry Andric "Incorrect LI specified for this loop!"); 282*06c3fb27SDimitry Andric } 283*06c3fb27SDimitry Andric #endif 284*06c3fb27SDimitry Andric assert(NewBB && "Cannot add a null basic block to the loop!"); 285*06c3fb27SDimitry Andric assert(!LIB[NewBB] && "BasicBlock already in the loop!"); 286*06c3fb27SDimitry Andric 287*06c3fb27SDimitry Andric LoopT *L = static_cast<LoopT *>(this); 288*06c3fb27SDimitry Andric 289*06c3fb27SDimitry Andric // Add the loop mapping to the LoopInfo object... 290*06c3fb27SDimitry Andric LIB.BBMap[NewBB] = L; 291*06c3fb27SDimitry Andric 292*06c3fb27SDimitry Andric // Add the basic block to this loop and all parent loops... 293*06c3fb27SDimitry Andric while (L) { 294*06c3fb27SDimitry Andric L->addBlockEntry(NewBB); 295*06c3fb27SDimitry Andric L = L->getParentLoop(); 296*06c3fb27SDimitry Andric } 297*06c3fb27SDimitry Andric } 298*06c3fb27SDimitry Andric 299*06c3fb27SDimitry Andric /// replaceChildLoopWith - This is used when splitting loops up. It replaces 300*06c3fb27SDimitry Andric /// the OldChild entry in our children list with NewChild, and updates the 301*06c3fb27SDimitry Andric /// parent pointer of OldChild to be null and the NewChild to be this loop. 302*06c3fb27SDimitry Andric /// This updates the loop depth of the new child. 303*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 304*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild, 305*06c3fb27SDimitry Andric LoopT *NewChild) { 306*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 307*06c3fb27SDimitry Andric assert(OldChild->ParentLoop == this && "This loop is already broken!"); 308*06c3fb27SDimitry Andric assert(!NewChild->ParentLoop && "NewChild already has a parent!"); 309*06c3fb27SDimitry Andric typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild); 310*06c3fb27SDimitry Andric assert(I != SubLoops.end() && "OldChild not in loop!"); 311*06c3fb27SDimitry Andric *I = NewChild; 312*06c3fb27SDimitry Andric OldChild->ParentLoop = nullptr; 313*06c3fb27SDimitry Andric NewChild->ParentLoop = static_cast<LoopT *>(this); 314*06c3fb27SDimitry Andric } 315*06c3fb27SDimitry Andric 316*06c3fb27SDimitry Andric /// verifyLoop - Verify loop structure 317*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 318*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::verifyLoop() const { 319*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 320*06c3fb27SDimitry Andric #ifndef NDEBUG 321*06c3fb27SDimitry Andric assert(!Blocks.empty() && "Loop header is missing"); 322*06c3fb27SDimitry Andric 323*06c3fb27SDimitry Andric // Setup for using a depth-first iterator to visit every block in the loop. 324*06c3fb27SDimitry Andric SmallVector<BlockT *, 8> ExitBBs; 325*06c3fb27SDimitry Andric getExitBlocks(ExitBBs); 326*06c3fb27SDimitry Andric df_iterator_default_set<BlockT *> VisitSet; 327*06c3fb27SDimitry Andric VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); 328*06c3fb27SDimitry Andric 329*06c3fb27SDimitry Andric // Keep track of the BBs visited. 330*06c3fb27SDimitry Andric SmallPtrSet<BlockT *, 8> VisitedBBs; 331*06c3fb27SDimitry Andric 332*06c3fb27SDimitry Andric // Check the individual blocks. 333*06c3fb27SDimitry Andric for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) { 334*06c3fb27SDimitry Andric assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB), 335*06c3fb27SDimitry Andric GraphTraits<BlockT *>::child_end(BB), 336*06c3fb27SDimitry Andric [&](BlockT *B) { return contains(B); }) && 337*06c3fb27SDimitry Andric "Loop block has no in-loop successors!"); 338*06c3fb27SDimitry Andric 339*06c3fb27SDimitry Andric assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB), 340*06c3fb27SDimitry Andric GraphTraits<Inverse<BlockT *>>::child_end(BB), 341*06c3fb27SDimitry Andric [&](BlockT *B) { return contains(B); }) && 342*06c3fb27SDimitry Andric "Loop block has no in-loop predecessors!"); 343*06c3fb27SDimitry Andric 344*06c3fb27SDimitry Andric SmallVector<BlockT *, 2> OutsideLoopPreds; 345*06c3fb27SDimitry Andric for (BlockT *B : 346*06c3fb27SDimitry Andric llvm::make_range(GraphTraits<Inverse<BlockT *>>::child_begin(BB), 347*06c3fb27SDimitry Andric GraphTraits<Inverse<BlockT *>>::child_end(BB))) 348*06c3fb27SDimitry Andric if (!contains(B)) 349*06c3fb27SDimitry Andric OutsideLoopPreds.push_back(B); 350*06c3fb27SDimitry Andric 351*06c3fb27SDimitry Andric if (BB == getHeader()) { 352*06c3fb27SDimitry Andric assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); 353*06c3fb27SDimitry Andric } else if (!OutsideLoopPreds.empty()) { 354*06c3fb27SDimitry Andric // A non-header loop shouldn't be reachable from outside the loop, 355*06c3fb27SDimitry Andric // though it is permitted if the predecessor is not itself actually 356*06c3fb27SDimitry Andric // reachable. 357*06c3fb27SDimitry Andric BlockT *EntryBB = &BB->getParent()->front(); 358*06c3fb27SDimitry Andric for (BlockT *CB : depth_first(EntryBB)) 359*06c3fb27SDimitry Andric for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) 360*06c3fb27SDimitry Andric assert(CB != OutsideLoopPreds[i] && 361*06c3fb27SDimitry Andric "Loop has multiple entry points!"); 362*06c3fb27SDimitry Andric } 363*06c3fb27SDimitry Andric assert(BB != &getHeader()->getParent()->front() && 364*06c3fb27SDimitry Andric "Loop contains function entry block!"); 365*06c3fb27SDimitry Andric 366*06c3fb27SDimitry Andric VisitedBBs.insert(BB); 367*06c3fb27SDimitry Andric } 368*06c3fb27SDimitry Andric 369*06c3fb27SDimitry Andric if (VisitedBBs.size() != getNumBlocks()) { 370*06c3fb27SDimitry Andric dbgs() << "The following blocks are unreachable in the loop: "; 371*06c3fb27SDimitry Andric for (auto *BB : Blocks) { 372*06c3fb27SDimitry Andric if (!VisitedBBs.count(BB)) { 373*06c3fb27SDimitry Andric dbgs() << *BB << "\n"; 374*06c3fb27SDimitry Andric } 375*06c3fb27SDimitry Andric } 376*06c3fb27SDimitry Andric assert(false && "Unreachable block in loop"); 377*06c3fb27SDimitry Andric } 378*06c3fb27SDimitry Andric 379*06c3fb27SDimitry Andric // Check the subloops. 380*06c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I) 381*06c3fb27SDimitry Andric // Each block in each subloop should be contained within this loop. 382*06c3fb27SDimitry Andric for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); 383*06c3fb27SDimitry Andric BI != BE; ++BI) { 384*06c3fb27SDimitry Andric assert(contains(*BI) && 385*06c3fb27SDimitry Andric "Loop does not contain all the blocks of a subloop!"); 386*06c3fb27SDimitry Andric } 387*06c3fb27SDimitry Andric 388*06c3fb27SDimitry Andric // Check the parent loop pointer. 389*06c3fb27SDimitry Andric if (ParentLoop) { 390*06c3fb27SDimitry Andric assert(is_contained(ParentLoop->getSubLoops(), this) && 391*06c3fb27SDimitry Andric "Loop is not a subloop of its parent!"); 392*06c3fb27SDimitry Andric } 393*06c3fb27SDimitry Andric #endif 394*06c3fb27SDimitry Andric } 395*06c3fb27SDimitry Andric 396*06c3fb27SDimitry Andric /// verifyLoop - Verify loop structure of this loop and all nested loops. 397*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 398*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::verifyLoopNest( 399*06c3fb27SDimitry Andric DenseSet<const LoopT *> *Loops) const { 400*06c3fb27SDimitry Andric assert(!isInvalid() && "Loop not in a valid state!"); 401*06c3fb27SDimitry Andric Loops->insert(static_cast<const LoopT *>(this)); 402*06c3fb27SDimitry Andric // Verify this loop. 403*06c3fb27SDimitry Andric verifyLoop(); 404*06c3fb27SDimitry Andric // Verify the subloops. 405*06c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I) 406*06c3fb27SDimitry Andric (*I)->verifyLoopNest(Loops); 407*06c3fb27SDimitry Andric } 408*06c3fb27SDimitry Andric 409*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 410*06c3fb27SDimitry Andric void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, bool Verbose, 411*06c3fb27SDimitry Andric bool PrintNested, unsigned Depth) const { 412*06c3fb27SDimitry Andric OS.indent(Depth * 2); 413*06c3fb27SDimitry Andric if (static_cast<const LoopT *>(this)->isAnnotatedParallel()) 414*06c3fb27SDimitry Andric OS << "Parallel "; 415*06c3fb27SDimitry Andric OS << "Loop at depth " << getLoopDepth() << " containing: "; 416*06c3fb27SDimitry Andric 417*06c3fb27SDimitry Andric BlockT *H = getHeader(); 418*06c3fb27SDimitry Andric for (unsigned i = 0; i < getBlocks().size(); ++i) { 419*06c3fb27SDimitry Andric BlockT *BB = getBlocks()[i]; 420*06c3fb27SDimitry Andric if (!Verbose) { 421*06c3fb27SDimitry Andric if (i) 422*06c3fb27SDimitry Andric OS << ","; 423*06c3fb27SDimitry Andric BB->printAsOperand(OS, false); 424*06c3fb27SDimitry Andric } else 425*06c3fb27SDimitry Andric OS << "\n"; 426*06c3fb27SDimitry Andric 427*06c3fb27SDimitry Andric if (BB == H) 428*06c3fb27SDimitry Andric OS << "<header>"; 429*06c3fb27SDimitry Andric if (isLoopLatch(BB)) 430*06c3fb27SDimitry Andric OS << "<latch>"; 431*06c3fb27SDimitry Andric if (isLoopExiting(BB)) 432*06c3fb27SDimitry Andric OS << "<exiting>"; 433*06c3fb27SDimitry Andric if (Verbose) 434*06c3fb27SDimitry Andric BB->print(OS); 435*06c3fb27SDimitry Andric } 436*06c3fb27SDimitry Andric 437*06c3fb27SDimitry Andric if (PrintNested) { 438*06c3fb27SDimitry Andric OS << "\n"; 439*06c3fb27SDimitry Andric 440*06c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I) 441*06c3fb27SDimitry Andric (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2); 442*06c3fb27SDimitry Andric } 443*06c3fb27SDimitry Andric } 444*06c3fb27SDimitry Andric 445*06c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 446*06c3fb27SDimitry Andric /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the 447*06c3fb27SDimitry Andric /// result does / not depend on use list (block predecessor) order. 448*06c3fb27SDimitry Andric /// 449*06c3fb27SDimitry Andric 450*06c3fb27SDimitry Andric /// Discover a subloop with the specified backedges such that: All blocks within 451*06c3fb27SDimitry Andric /// this loop are mapped to this loop or a subloop. And all subloops within this 452*06c3fb27SDimitry Andric /// loop have their parent loop set to this loop or a subloop. 453*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 454*06c3fb27SDimitry Andric static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges, 455*06c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> *LI, 456*06c3fb27SDimitry Andric const DomTreeBase<BlockT> &DomTree) { 457*06c3fb27SDimitry Andric typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; 458*06c3fb27SDimitry Andric 459*06c3fb27SDimitry Andric unsigned NumBlocks = 0; 460*06c3fb27SDimitry Andric unsigned NumSubloops = 0; 461*06c3fb27SDimitry Andric 462*06c3fb27SDimitry Andric // Perform a backward CFG traversal using a worklist. 463*06c3fb27SDimitry Andric std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); 464*06c3fb27SDimitry Andric while (!ReverseCFGWorklist.empty()) { 465*06c3fb27SDimitry Andric BlockT *PredBB = ReverseCFGWorklist.back(); 466*06c3fb27SDimitry Andric ReverseCFGWorklist.pop_back(); 467*06c3fb27SDimitry Andric 468*06c3fb27SDimitry Andric LoopT *Subloop = LI->getLoopFor(PredBB); 469*06c3fb27SDimitry Andric if (!Subloop) { 470*06c3fb27SDimitry Andric if (!DomTree.isReachableFromEntry(PredBB)) 471*06c3fb27SDimitry Andric continue; 472*06c3fb27SDimitry Andric 473*06c3fb27SDimitry Andric // This is an undiscovered block. Map it to the current loop. 474*06c3fb27SDimitry Andric LI->changeLoopFor(PredBB, L); 475*06c3fb27SDimitry Andric ++NumBlocks; 476*06c3fb27SDimitry Andric if (PredBB == L->getHeader()) 477*06c3fb27SDimitry Andric continue; 478*06c3fb27SDimitry Andric // Push all block predecessors on the worklist. 479*06c3fb27SDimitry Andric ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), 480*06c3fb27SDimitry Andric InvBlockTraits::child_begin(PredBB), 481*06c3fb27SDimitry Andric InvBlockTraits::child_end(PredBB)); 482*06c3fb27SDimitry Andric } else { 483*06c3fb27SDimitry Andric // This is a discovered block. Find its outermost discovered loop. 484*06c3fb27SDimitry Andric Subloop = Subloop->getOutermostLoop(); 485*06c3fb27SDimitry Andric 486*06c3fb27SDimitry Andric // If it is already discovered to be a subloop of this loop, continue. 487*06c3fb27SDimitry Andric if (Subloop == L) 488*06c3fb27SDimitry Andric continue; 489*06c3fb27SDimitry Andric 490*06c3fb27SDimitry Andric // Discover a subloop of this loop. 491*06c3fb27SDimitry Andric Subloop->setParentLoop(L); 492*06c3fb27SDimitry Andric ++NumSubloops; 493*06c3fb27SDimitry Andric NumBlocks += Subloop->getBlocksVector().capacity(); 494*06c3fb27SDimitry Andric PredBB = Subloop->getHeader(); 495*06c3fb27SDimitry Andric // Continue traversal along predecessors that are not loop-back edges from 496*06c3fb27SDimitry Andric // within this subloop tree itself. Note that a predecessor may directly 497*06c3fb27SDimitry Andric // reach another subloop that is not yet discovered to be a subloop of 498*06c3fb27SDimitry Andric // this loop, which we must traverse. 499*06c3fb27SDimitry Andric for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) { 500*06c3fb27SDimitry Andric if (LI->getLoopFor(Pred) != Subloop) 501*06c3fb27SDimitry Andric ReverseCFGWorklist.push_back(Pred); 502*06c3fb27SDimitry Andric } 503*06c3fb27SDimitry Andric } 504*06c3fb27SDimitry Andric } 505*06c3fb27SDimitry Andric L->getSubLoopsVector().reserve(NumSubloops); 506*06c3fb27SDimitry Andric L->reserveBlocks(NumBlocks); 507*06c3fb27SDimitry Andric } 508*06c3fb27SDimitry Andric 509*06c3fb27SDimitry Andric /// Populate all loop data in a stable order during a single forward DFS. 510*06c3fb27SDimitry Andric template <class BlockT, class LoopT> class PopulateLoopsDFS { 511*06c3fb27SDimitry Andric typedef GraphTraits<BlockT *> BlockTraits; 512*06c3fb27SDimitry Andric typedef typename BlockTraits::ChildIteratorType SuccIterTy; 513*06c3fb27SDimitry Andric 514*06c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> *LI; 515*06c3fb27SDimitry Andric 516*06c3fb27SDimitry Andric public: 517*06c3fb27SDimitry Andric PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} 518*06c3fb27SDimitry Andric 519*06c3fb27SDimitry Andric void traverse(BlockT *EntryBlock); 520*06c3fb27SDimitry Andric 521*06c3fb27SDimitry Andric protected: 522*06c3fb27SDimitry Andric void insertIntoLoop(BlockT *Block); 523*06c3fb27SDimitry Andric }; 524*06c3fb27SDimitry Andric 525*06c3fb27SDimitry Andric /// Top-level driver for the forward DFS within the loop. 526*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 527*06c3fb27SDimitry Andric void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { 528*06c3fb27SDimitry Andric for (BlockT *BB : post_order(EntryBlock)) 529*06c3fb27SDimitry Andric insertIntoLoop(BB); 530*06c3fb27SDimitry Andric } 531*06c3fb27SDimitry Andric 532*06c3fb27SDimitry Andric /// Add a single Block to its ancestor loops in PostOrder. If the block is a 533*06c3fb27SDimitry Andric /// subloop header, add the subloop to its parent in PostOrder, then reverse the 534*06c3fb27SDimitry Andric /// Block and Subloop vectors of the now complete subloop to achieve RPO. 535*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 536*06c3fb27SDimitry Andric void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { 537*06c3fb27SDimitry Andric LoopT *Subloop = LI->getLoopFor(Block); 538*06c3fb27SDimitry Andric if (Subloop && Block == Subloop->getHeader()) { 539*06c3fb27SDimitry Andric // We reach this point once per subloop after processing all the blocks in 540*06c3fb27SDimitry Andric // the subloop. 541*06c3fb27SDimitry Andric if (!Subloop->isOutermost()) 542*06c3fb27SDimitry Andric Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); 543*06c3fb27SDimitry Andric else 544*06c3fb27SDimitry Andric LI->addTopLevelLoop(Subloop); 545*06c3fb27SDimitry Andric 546*06c3fb27SDimitry Andric // For convenience, Blocks and Subloops are inserted in postorder. Reverse 547*06c3fb27SDimitry Andric // the lists, except for the loop header, which is always at the beginning. 548*06c3fb27SDimitry Andric Subloop->reverseBlock(1); 549*06c3fb27SDimitry Andric std::reverse(Subloop->getSubLoopsVector().begin(), 550*06c3fb27SDimitry Andric Subloop->getSubLoopsVector().end()); 551*06c3fb27SDimitry Andric 552*06c3fb27SDimitry Andric Subloop = Subloop->getParentLoop(); 553*06c3fb27SDimitry Andric } 554*06c3fb27SDimitry Andric for (; Subloop; Subloop = Subloop->getParentLoop()) 555*06c3fb27SDimitry Andric Subloop->addBlockEntry(Block); 556*06c3fb27SDimitry Andric } 557*06c3fb27SDimitry Andric 558*06c3fb27SDimitry Andric /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal 559*06c3fb27SDimitry Andric /// interleaved with backward CFG traversals within each subloop 560*06c3fb27SDimitry Andric /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so 561*06c3fb27SDimitry Andric /// this part of the algorithm is linear in the number of CFG edges. Subloop and 562*06c3fb27SDimitry Andric /// Block vectors are then populated during a single forward CFG traversal 563*06c3fb27SDimitry Andric /// (PopulateLoopDFS). 564*06c3fb27SDimitry Andric /// 565*06c3fb27SDimitry Andric /// During the two CFG traversals each block is seen three times: 566*06c3fb27SDimitry Andric /// 1) Discovered and mapped by a reverse CFG traversal. 567*06c3fb27SDimitry Andric /// 2) Visited during a forward DFS CFG traversal. 568*06c3fb27SDimitry Andric /// 3) Reverse-inserted in the loop in postorder following forward DFS. 569*06c3fb27SDimitry Andric /// 570*06c3fb27SDimitry Andric /// The Block vectors are inclusive, so step 3 requires loop-depth number of 571*06c3fb27SDimitry Andric /// insertions per block. 572*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 573*06c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { 574*06c3fb27SDimitry Andric // Postorder traversal of the dominator tree. 575*06c3fb27SDimitry Andric const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode(); 576*06c3fb27SDimitry Andric for (auto DomNode : post_order(DomRoot)) { 577*06c3fb27SDimitry Andric 578*06c3fb27SDimitry Andric BlockT *Header = DomNode->getBlock(); 579*06c3fb27SDimitry Andric SmallVector<BlockT *, 4> Backedges; 580*06c3fb27SDimitry Andric 581*06c3fb27SDimitry Andric // Check each predecessor of the potential loop header. 582*06c3fb27SDimitry Andric for (const auto Backedge : children<Inverse<BlockT *>>(Header)) { 583*06c3fb27SDimitry Andric // If Header dominates predBB, this is a new loop. Collect the backedges. 584*06c3fb27SDimitry Andric if (DomTree.dominates(Header, Backedge) && 585*06c3fb27SDimitry Andric DomTree.isReachableFromEntry(Backedge)) { 586*06c3fb27SDimitry Andric Backedges.push_back(Backedge); 587*06c3fb27SDimitry Andric } 588*06c3fb27SDimitry Andric } 589*06c3fb27SDimitry Andric // Perform a backward CFG traversal to discover and map blocks in this loop. 590*06c3fb27SDimitry Andric if (!Backedges.empty()) { 591*06c3fb27SDimitry Andric LoopT *L = AllocateLoop(Header); 592*06c3fb27SDimitry Andric discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree); 593*06c3fb27SDimitry Andric } 594*06c3fb27SDimitry Andric } 595*06c3fb27SDimitry Andric // Perform a single forward CFG traversal to populate block and subloop 596*06c3fb27SDimitry Andric // vectors for all loops. 597*06c3fb27SDimitry Andric PopulateLoopsDFS<BlockT, LoopT> DFS(this); 598*06c3fb27SDimitry Andric DFS.traverse(DomRoot->getBlock()); 599*06c3fb27SDimitry Andric } 600*06c3fb27SDimitry Andric 601*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 602*06c3fb27SDimitry Andric SmallVector<LoopT *, 4> 603*06c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() const { 604*06c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; 605*06c3fb27SDimitry Andric // The outer-most loop actually goes into the result in the same relative 606*06c3fb27SDimitry Andric // order as we walk it. But LoopInfo stores the top level loops in reverse 607*06c3fb27SDimitry Andric // program order so for here we reverse it to get forward program order. 608*06c3fb27SDimitry Andric // FIXME: If we change the order of LoopInfo we will want to remove the 609*06c3fb27SDimitry Andric // reverse here. 610*06c3fb27SDimitry Andric for (LoopT *RootL : reverse(*this)) { 611*06c3fb27SDimitry Andric auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder(); 612*06c3fb27SDimitry Andric PreOrderLoops.append(PreOrderLoopsInRootL.begin(), 613*06c3fb27SDimitry Andric PreOrderLoopsInRootL.end()); 614*06c3fb27SDimitry Andric } 615*06c3fb27SDimitry Andric 616*06c3fb27SDimitry Andric return PreOrderLoops; 617*06c3fb27SDimitry Andric } 618*06c3fb27SDimitry Andric 619*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 620*06c3fb27SDimitry Andric SmallVector<LoopT *, 4> 621*06c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() const { 622*06c3fb27SDimitry Andric SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; 623*06c3fb27SDimitry Andric // The outer-most loop actually goes into the result in the same relative 624*06c3fb27SDimitry Andric // order as we walk it. LoopInfo stores the top level loops in reverse 625*06c3fb27SDimitry Andric // program order so we walk in order here. 626*06c3fb27SDimitry Andric // FIXME: If we change the order of LoopInfo we will want to add a reverse 627*06c3fb27SDimitry Andric // here. 628*06c3fb27SDimitry Andric for (LoopT *RootL : *this) { 629*06c3fb27SDimitry Andric assert(PreOrderWorklist.empty() && 630*06c3fb27SDimitry Andric "Must start with an empty preorder walk worklist."); 631*06c3fb27SDimitry Andric PreOrderWorklist.push_back(RootL); 632*06c3fb27SDimitry Andric do { 633*06c3fb27SDimitry Andric LoopT *L = PreOrderWorklist.pop_back_val(); 634*06c3fb27SDimitry Andric // Sub-loops are stored in forward program order, but will process the 635*06c3fb27SDimitry Andric // worklist backwards so we can just append them in order. 636*06c3fb27SDimitry Andric PreOrderWorklist.append(L->begin(), L->end()); 637*06c3fb27SDimitry Andric PreOrderLoops.push_back(L); 638*06c3fb27SDimitry Andric } while (!PreOrderWorklist.empty()); 639*06c3fb27SDimitry Andric } 640*06c3fb27SDimitry Andric 641*06c3fb27SDimitry Andric return PreOrderLoops; 642*06c3fb27SDimitry Andric } 643*06c3fb27SDimitry Andric 644*06c3fb27SDimitry Andric // Debugging 645*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 646*06c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { 647*06c3fb27SDimitry Andric for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 648*06c3fb27SDimitry Andric TopLevelLoops[i]->print(OS); 649*06c3fb27SDimitry Andric #if 0 650*06c3fb27SDimitry Andric for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), 651*06c3fb27SDimitry Andric E = BBMap.end(); I != E; ++I) 652*06c3fb27SDimitry Andric OS << "BB '" << I->first->getName() << "' level = " 653*06c3fb27SDimitry Andric << I->second->getLoopDepth() << "\n"; 654*06c3fb27SDimitry Andric #endif 655*06c3fb27SDimitry Andric } 656*06c3fb27SDimitry Andric 657*06c3fb27SDimitry Andric template <typename T> 658*06c3fb27SDimitry Andric bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { 659*06c3fb27SDimitry Andric llvm::sort(BB1); 660*06c3fb27SDimitry Andric llvm::sort(BB2); 661*06c3fb27SDimitry Andric return BB1 == BB2; 662*06c3fb27SDimitry Andric } 663*06c3fb27SDimitry Andric 664*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 665*06c3fb27SDimitry Andric void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders, 666*06c3fb27SDimitry Andric const LoopInfoBase<BlockT, LoopT> &LI, 667*06c3fb27SDimitry Andric const LoopT &L) { 668*06c3fb27SDimitry Andric LoopHeaders[L.getHeader()] = &L; 669*06c3fb27SDimitry Andric for (LoopT *SL : L) 670*06c3fb27SDimitry Andric addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL); 671*06c3fb27SDimitry Andric } 672*06c3fb27SDimitry Andric 673*06c3fb27SDimitry Andric #ifndef NDEBUG 674*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 675*06c3fb27SDimitry Andric static void compareLoops(const LoopT *L, const LoopT *OtherL, 676*06c3fb27SDimitry Andric DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) { 677*06c3fb27SDimitry Andric BlockT *H = L->getHeader(); 678*06c3fb27SDimitry Andric BlockT *OtherH = OtherL->getHeader(); 679*06c3fb27SDimitry Andric assert(H == OtherH && 680*06c3fb27SDimitry Andric "Mismatched headers even though found in the same map entry!"); 681*06c3fb27SDimitry Andric 682*06c3fb27SDimitry Andric assert(L->getLoopDepth() == OtherL->getLoopDepth() && 683*06c3fb27SDimitry Andric "Mismatched loop depth!"); 684*06c3fb27SDimitry Andric const LoopT *ParentL = L, *OtherParentL = OtherL; 685*06c3fb27SDimitry Andric do { 686*06c3fb27SDimitry Andric assert(ParentL->getHeader() == OtherParentL->getHeader() && 687*06c3fb27SDimitry Andric "Mismatched parent loop headers!"); 688*06c3fb27SDimitry Andric ParentL = ParentL->getParentLoop(); 689*06c3fb27SDimitry Andric OtherParentL = OtherParentL->getParentLoop(); 690*06c3fb27SDimitry Andric } while (ParentL); 691*06c3fb27SDimitry Andric 692*06c3fb27SDimitry Andric for (const LoopT *SubL : *L) { 693*06c3fb27SDimitry Andric BlockT *SubH = SubL->getHeader(); 694*06c3fb27SDimitry Andric const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH); 695*06c3fb27SDimitry Andric assert(OtherSubL && "Inner loop is missing in computed loop info!"); 696*06c3fb27SDimitry Andric OtherLoopHeaders.erase(SubH); 697*06c3fb27SDimitry Andric compareLoops(SubL, OtherSubL, OtherLoopHeaders); 698*06c3fb27SDimitry Andric } 699*06c3fb27SDimitry Andric 700*06c3fb27SDimitry Andric std::vector<BlockT *> BBs = L->getBlocks(); 701*06c3fb27SDimitry Andric std::vector<BlockT *> OtherBBs = OtherL->getBlocks(); 702*06c3fb27SDimitry Andric assert(compareVectors(BBs, OtherBBs) && 703*06c3fb27SDimitry Andric "Mismatched basic blocks in the loops!"); 704*06c3fb27SDimitry Andric 705*06c3fb27SDimitry Andric const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet(); 706*06c3fb27SDimitry Andric const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = 707*06c3fb27SDimitry Andric OtherL->getBlocksSet(); 708*06c3fb27SDimitry Andric assert(BlocksSet.size() == OtherBlocksSet.size() && 709*06c3fb27SDimitry Andric llvm::set_is_subset(BlocksSet, OtherBlocksSet) && 710*06c3fb27SDimitry Andric "Mismatched basic blocks in BlocksSets!"); 711*06c3fb27SDimitry Andric } 712*06c3fb27SDimitry Andric #endif 713*06c3fb27SDimitry Andric 714*06c3fb27SDimitry Andric template <class BlockT, class LoopT> 715*06c3fb27SDimitry Andric void LoopInfoBase<BlockT, LoopT>::verify( 716*06c3fb27SDimitry Andric const DomTreeBase<BlockT> &DomTree) const { 717*06c3fb27SDimitry Andric DenseSet<const LoopT *> Loops; 718*06c3fb27SDimitry Andric for (iterator I = begin(), E = end(); I != E; ++I) { 719*06c3fb27SDimitry Andric assert((*I)->isOutermost() && "Top-level loop has a parent!"); 720*06c3fb27SDimitry Andric (*I)->verifyLoopNest(&Loops); 721*06c3fb27SDimitry Andric } 722*06c3fb27SDimitry Andric 723*06c3fb27SDimitry Andric // Verify that blocks are mapped to valid loops. 724*06c3fb27SDimitry Andric #ifndef NDEBUG 725*06c3fb27SDimitry Andric for (auto &Entry : BBMap) { 726*06c3fb27SDimitry Andric const BlockT *BB = Entry.first; 727*06c3fb27SDimitry Andric LoopT *L = Entry.second; 728*06c3fb27SDimitry Andric assert(Loops.count(L) && "orphaned loop"); 729*06c3fb27SDimitry Andric assert(L->contains(BB) && "orphaned block"); 730*06c3fb27SDimitry Andric for (LoopT *ChildLoop : *L) 731*06c3fb27SDimitry Andric assert(!ChildLoop->contains(BB) && 732*06c3fb27SDimitry Andric "BBMap should point to the innermost loop containing BB"); 733*06c3fb27SDimitry Andric } 734*06c3fb27SDimitry Andric 735*06c3fb27SDimitry Andric // Recompute LoopInfo to verify loops structure. 736*06c3fb27SDimitry Andric LoopInfoBase<BlockT, LoopT> OtherLI; 737*06c3fb27SDimitry Andric OtherLI.analyze(DomTree); 738*06c3fb27SDimitry Andric 739*06c3fb27SDimitry Andric // Build a map we can use to move from our LI to the computed one. This 740*06c3fb27SDimitry Andric // allows us to ignore the particular order in any layer of the loop forest 741*06c3fb27SDimitry Andric // while still comparing the structure. 742*06c3fb27SDimitry Andric DenseMap<BlockT *, const LoopT *> OtherLoopHeaders; 743*06c3fb27SDimitry Andric for (LoopT *L : OtherLI) 744*06c3fb27SDimitry Andric addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L); 745*06c3fb27SDimitry Andric 746*06c3fb27SDimitry Andric // Walk the top level loops and ensure there is a corresponding top-level 747*06c3fb27SDimitry Andric // loop in the computed version and then recursively compare those loop 748*06c3fb27SDimitry Andric // nests. 749*06c3fb27SDimitry Andric for (LoopT *L : *this) { 750*06c3fb27SDimitry Andric BlockT *Header = L->getHeader(); 751*06c3fb27SDimitry Andric const LoopT *OtherL = OtherLoopHeaders.lookup(Header); 752*06c3fb27SDimitry Andric assert(OtherL && "Top level loop is missing in computed loop info!"); 753*06c3fb27SDimitry Andric // Now that we've matched this loop, erase its header from the map. 754*06c3fb27SDimitry Andric OtherLoopHeaders.erase(Header); 755*06c3fb27SDimitry Andric // And recursively compare these loops. 756*06c3fb27SDimitry Andric compareLoops(L, OtherL, OtherLoopHeaders); 757*06c3fb27SDimitry Andric } 758*06c3fb27SDimitry Andric 759*06c3fb27SDimitry Andric // Any remaining entries in the map are loops which were found when computing 760*06c3fb27SDimitry Andric // a fresh LoopInfo but not present in the current one. 761*06c3fb27SDimitry Andric if (!OtherLoopHeaders.empty()) { 762*06c3fb27SDimitry Andric for (const auto &HeaderAndLoop : OtherLoopHeaders) 763*06c3fb27SDimitry Andric dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n"; 764*06c3fb27SDimitry Andric llvm_unreachable("Found new loops when recomputing LoopInfo!"); 765*06c3fb27SDimitry Andric } 766*06c3fb27SDimitry Andric #endif 767*06c3fb27SDimitry Andric } 768*06c3fb27SDimitry Andric 769*06c3fb27SDimitry Andric } // namespace llvm 770*06c3fb27SDimitry Andric 771*06c3fb27SDimitry Andric #endif // LLVM_SUPPORT_GENERICLOOPINFOIMPL_H 772