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