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 25 namespace 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 /// 34 template <class BlockT, class LoopT> 35 void 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. 49 template <class BlockT, class LoopT> 50 BlockT *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 /// 62 template <class BlockT, class LoopT> 63 void 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. 75 template <class BlockT, class LoopT> 76 BlockT *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_). 86 template <class BlockT, class LoopT> 87 void 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 /// 105 template <class BlockT, class LoopT> 106 BlockT *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 /// 133 template <class BlockT, class LoopT> 134 BlockT *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. 156 template <class BlockT, class LoopT> 157 BlockT *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 /// 182 template <class BlockT, class LoopT> 183 void 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. 212 template <class BlockT, class LoopT> 213 void 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 226 template <class BlockT, class LoopT> 227 void 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. 312 template <class BlockT, class LoopT> 313 void 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 324 template <class BlockT, class LoopT> 325 void 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. 362 template <class BlockT, class LoopT> 363 static 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. 420 template <class BlockT, class LoopT> class PopulateLoopsDFS { 421 typedef GraphTraits<BlockT *> BlockTraits; 422 typedef typename BlockTraits::ChildIteratorType SuccIterTy; 423 424 LoopInfoBase<BlockT, LoopT> *LI; 425 426 public: 427 PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} 428 429 void traverse(BlockT *EntryBlock); 430 431 protected: 432 void insertIntoLoop(BlockT *Block); 433 }; 434 435 /// Top-level driver for the forward DFS within the loop. 436 template <class BlockT, class LoopT> 437 void 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. 445 template <class BlockT, class LoopT> 446 void 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. 482 template <class BlockT, class LoopT> 483 void 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 511 template <class BlockT, class LoopT> 512 SmallVector<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 535 template <class BlockT, class LoopT> 536 SmallVector<LoopT *, 4> 537 LoopInfoBase<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 561 template <class BlockT, class LoopT> 562 void 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 573 template <typename T> 574 bool 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 580 template <class BlockT, class LoopT> 581 void 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 590 template <class BlockT, class LoopT> 591 static 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 623 template <class BlockT, class LoopT> 624 void 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