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