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 : children<Inverse<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 typedef GraphTraits<BlockT *> BlockTraits; 212 typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out); 213 ++SI; 214 if (SI != BlockTraits::child_end(Out)) 215 return nullptr; // Multiple exits from the block, must not be a preheader. 216 217 // The predecessor has exactly one successor, so it is a preheader. 218 return Out; 219 } 220 221 /// getLoopPredecessor - If the given loop's header has exactly one unique 222 /// predecessor outside the loop, return it. Otherwise return null. 223 /// This is less strict that the loop "preheader" concept, which requires 224 /// the predecessor to have exactly one successor. 225 /// 226 template <class BlockT, class LoopT> 227 BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const { 228 assert(!isInvalid() && "Loop not in a valid state!"); 229 // Keep track of nodes outside the loop branching to the header... 230 BlockT *Out = nullptr; 231 232 // Loop over the predecessors of the header node... 233 BlockT *Header = getHeader(); 234 for (const auto Pred : children<Inverse<BlockT *>>(Header)) { 235 if (!contains(Pred)) { // If the block is not in the loop... 236 if (Out && Out != Pred) 237 return nullptr; // Multiple predecessors outside the loop 238 Out = Pred; 239 } 240 } 241 242 return Out; 243 } 244 245 /// getLoopLatch - If there is a single latch block for this loop, return it. 246 /// A latch block is a block that contains a branch back to the header. 247 template <class BlockT, class LoopT> 248 BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const { 249 assert(!isInvalid() && "Loop not in a valid state!"); 250 BlockT *Header = getHeader(); 251 BlockT *Latch = nullptr; 252 for (const auto Pred : children<Inverse<BlockT *>>(Header)) { 253 if (contains(Pred)) { 254 if (Latch) 255 return nullptr; 256 Latch = Pred; 257 } 258 } 259 260 return Latch; 261 } 262 263 //===----------------------------------------------------------------------===// 264 // APIs for updating loop information after changing the CFG 265 // 266 267 /// addBasicBlockToLoop - This method is used by other analyses to update loop 268 /// information. NewBB is set to be a new member of the current loop. 269 /// Because of this, it is added as a member of all parent loops, and is added 270 /// to the specified LoopInfo object as being in the current basic block. It 271 /// is not valid to replace the loop header with this method. 272 /// 273 template <class BlockT, class LoopT> 274 void LoopBase<BlockT, LoopT>::addBasicBlockToLoop( 275 BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { 276 assert(!isInvalid() && "Loop not in a valid state!"); 277 #ifndef NDEBUG 278 if (!Blocks.empty()) { 279 auto SameHeader = LIB[getHeader()]; 280 assert(contains(SameHeader) && getHeader() == SameHeader->getHeader() && 281 "Incorrect LI specified for this loop!"); 282 } 283 #endif 284 assert(NewBB && "Cannot add a null basic block to the loop!"); 285 assert(!LIB[NewBB] && "BasicBlock already in the loop!"); 286 287 LoopT *L = static_cast<LoopT *>(this); 288 289 // Add the loop mapping to the LoopInfo object... 290 LIB.BBMap[NewBB] = L; 291 292 // Add the basic block to this loop and all parent loops... 293 while (L) { 294 L->addBlockEntry(NewBB); 295 L = L->getParentLoop(); 296 } 297 } 298 299 /// replaceChildLoopWith - This is used when splitting loops up. It replaces 300 /// the OldChild entry in our children list with NewChild, and updates the 301 /// parent pointer of OldChild to be null and the NewChild to be this loop. 302 /// This updates the loop depth of the new child. 303 template <class BlockT, class LoopT> 304 void LoopBase<BlockT, LoopT>::replaceChildLoopWith(LoopT *OldChild, 305 LoopT *NewChild) { 306 assert(!isInvalid() && "Loop not in a valid state!"); 307 assert(OldChild->ParentLoop == this && "This loop is already broken!"); 308 assert(!NewChild->ParentLoop && "NewChild already has a parent!"); 309 typename std::vector<LoopT *>::iterator I = find(SubLoops, OldChild); 310 assert(I != SubLoops.end() && "OldChild not in loop!"); 311 *I = NewChild; 312 OldChild->ParentLoop = nullptr; 313 NewChild->ParentLoop = static_cast<LoopT *>(this); 314 } 315 316 /// verifyLoop - Verify loop structure 317 template <class BlockT, class LoopT> 318 void LoopBase<BlockT, LoopT>::verifyLoop() const { 319 assert(!isInvalid() && "Loop not in a valid state!"); 320 #ifndef NDEBUG 321 assert(!Blocks.empty() && "Loop header is missing"); 322 323 // Setup for using a depth-first iterator to visit every block in the loop. 324 SmallVector<BlockT *, 8> ExitBBs; 325 getExitBlocks(ExitBBs); 326 df_iterator_default_set<BlockT *> VisitSet; 327 VisitSet.insert(ExitBBs.begin(), ExitBBs.end()); 328 329 // Keep track of the BBs visited. 330 SmallPtrSet<BlockT *, 8> VisitedBBs; 331 332 // Check the individual blocks. 333 for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) { 334 assert(std::any_of(GraphTraits<BlockT *>::child_begin(BB), 335 GraphTraits<BlockT *>::child_end(BB), 336 [&](BlockT *B) { return contains(B); }) && 337 "Loop block has no in-loop successors!"); 338 339 assert(std::any_of(GraphTraits<Inverse<BlockT *>>::child_begin(BB), 340 GraphTraits<Inverse<BlockT *>>::child_end(BB), 341 [&](BlockT *B) { return contains(B); }) && 342 "Loop block has no in-loop predecessors!"); 343 344 SmallVector<BlockT *, 2> OutsideLoopPreds; 345 for (BlockT *B : 346 llvm::make_range(GraphTraits<Inverse<BlockT *>>::child_begin(BB), 347 GraphTraits<Inverse<BlockT *>>::child_end(BB))) 348 if (!contains(B)) 349 OutsideLoopPreds.push_back(B); 350 351 if (BB == getHeader()) { 352 assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); 353 } else if (!OutsideLoopPreds.empty()) { 354 // A non-header loop shouldn't be reachable from outside the loop, 355 // though it is permitted if the predecessor is not itself actually 356 // reachable. 357 BlockT *EntryBB = &BB->getParent()->front(); 358 for (BlockT *CB : depth_first(EntryBB)) 359 for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) 360 assert(CB != OutsideLoopPreds[i] && 361 "Loop has multiple entry points!"); 362 } 363 assert(BB != &getHeader()->getParent()->front() && 364 "Loop contains function entry block!"); 365 366 VisitedBBs.insert(BB); 367 } 368 369 if (VisitedBBs.size() != getNumBlocks()) { 370 dbgs() << "The following blocks are unreachable in the loop: "; 371 for (auto *BB : Blocks) { 372 if (!VisitedBBs.count(BB)) { 373 dbgs() << *BB << "\n"; 374 } 375 } 376 assert(false && "Unreachable block in loop"); 377 } 378 379 // Check the subloops. 380 for (iterator I = begin(), E = end(); I != E; ++I) 381 // Each block in each subloop should be contained within this loop. 382 for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); 383 BI != BE; ++BI) { 384 assert(contains(*BI) && 385 "Loop does not contain all the blocks of a subloop!"); 386 } 387 388 // Check the parent loop pointer. 389 if (ParentLoop) { 390 assert(is_contained(ParentLoop->getSubLoops(), this) && 391 "Loop is not a subloop of its parent!"); 392 } 393 #endif 394 } 395 396 /// verifyLoop - Verify loop structure of this loop and all nested loops. 397 template <class BlockT, class LoopT> 398 void LoopBase<BlockT, LoopT>::verifyLoopNest( 399 DenseSet<const LoopT *> *Loops) const { 400 assert(!isInvalid() && "Loop not in a valid state!"); 401 Loops->insert(static_cast<const LoopT *>(this)); 402 // Verify this loop. 403 verifyLoop(); 404 // Verify the subloops. 405 for (iterator I = begin(), E = end(); I != E; ++I) 406 (*I)->verifyLoopNest(Loops); 407 } 408 409 template <class BlockT, class LoopT> 410 void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, bool Verbose, 411 bool PrintNested, unsigned Depth) const { 412 OS.indent(Depth * 2); 413 if (static_cast<const LoopT *>(this)->isAnnotatedParallel()) 414 OS << "Parallel "; 415 OS << "Loop at depth " << getLoopDepth() << " containing: "; 416 417 BlockT *H = getHeader(); 418 for (unsigned i = 0; i < getBlocks().size(); ++i) { 419 BlockT *BB = getBlocks()[i]; 420 if (!Verbose) { 421 if (i) 422 OS << ","; 423 BB->printAsOperand(OS, false); 424 } else 425 OS << "\n"; 426 427 if (BB == H) 428 OS << "<header>"; 429 if (isLoopLatch(BB)) 430 OS << "<latch>"; 431 if (isLoopExiting(BB)) 432 OS << "<exiting>"; 433 if (Verbose) 434 BB->print(OS); 435 } 436 437 if (PrintNested) { 438 OS << "\n"; 439 440 for (iterator I = begin(), E = end(); I != E; ++I) 441 (*I)->print(OS, /*Verbose*/ false, PrintNested, Depth + 2); 442 } 443 } 444 445 //===----------------------------------------------------------------------===// 446 /// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the 447 /// result does / not depend on use list (block predecessor) order. 448 /// 449 450 /// Discover a subloop with the specified backedges such that: All blocks within 451 /// this loop are mapped to this loop or a subloop. And all subloops within this 452 /// loop have their parent loop set to this loop or a subloop. 453 template <class BlockT, class LoopT> 454 static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT *> Backedges, 455 LoopInfoBase<BlockT, LoopT> *LI, 456 const DomTreeBase<BlockT> &DomTree) { 457 typedef GraphTraits<Inverse<BlockT *>> InvBlockTraits; 458 459 unsigned NumBlocks = 0; 460 unsigned NumSubloops = 0; 461 462 // Perform a backward CFG traversal using a worklist. 463 std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end()); 464 while (!ReverseCFGWorklist.empty()) { 465 BlockT *PredBB = ReverseCFGWorklist.back(); 466 ReverseCFGWorklist.pop_back(); 467 468 LoopT *Subloop = LI->getLoopFor(PredBB); 469 if (!Subloop) { 470 if (!DomTree.isReachableFromEntry(PredBB)) 471 continue; 472 473 // This is an undiscovered block. Map it to the current loop. 474 LI->changeLoopFor(PredBB, L); 475 ++NumBlocks; 476 if (PredBB == L->getHeader()) 477 continue; 478 // Push all block predecessors on the worklist. 479 ReverseCFGWorklist.insert(ReverseCFGWorklist.end(), 480 InvBlockTraits::child_begin(PredBB), 481 InvBlockTraits::child_end(PredBB)); 482 } else { 483 // This is a discovered block. Find its outermost discovered loop. 484 Subloop = Subloop->getOutermostLoop(); 485 486 // If it is already discovered to be a subloop of this loop, continue. 487 if (Subloop == L) 488 continue; 489 490 // Discover a subloop of this loop. 491 Subloop->setParentLoop(L); 492 ++NumSubloops; 493 NumBlocks += Subloop->getBlocksVector().capacity(); 494 PredBB = Subloop->getHeader(); 495 // Continue traversal along predecessors that are not loop-back edges from 496 // within this subloop tree itself. Note that a predecessor may directly 497 // reach another subloop that is not yet discovered to be a subloop of 498 // this loop, which we must traverse. 499 for (const auto Pred : children<Inverse<BlockT *>>(PredBB)) { 500 if (LI->getLoopFor(Pred) != Subloop) 501 ReverseCFGWorklist.push_back(Pred); 502 } 503 } 504 } 505 L->getSubLoopsVector().reserve(NumSubloops); 506 L->reserveBlocks(NumBlocks); 507 } 508 509 /// Populate all loop data in a stable order during a single forward DFS. 510 template <class BlockT, class LoopT> class PopulateLoopsDFS { 511 typedef GraphTraits<BlockT *> BlockTraits; 512 typedef typename BlockTraits::ChildIteratorType SuccIterTy; 513 514 LoopInfoBase<BlockT, LoopT> *LI; 515 516 public: 517 PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li) : LI(li) {} 518 519 void traverse(BlockT *EntryBlock); 520 521 protected: 522 void insertIntoLoop(BlockT *Block); 523 }; 524 525 /// Top-level driver for the forward DFS within the loop. 526 template <class BlockT, class LoopT> 527 void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) { 528 for (BlockT *BB : post_order(EntryBlock)) 529 insertIntoLoop(BB); 530 } 531 532 /// Add a single Block to its ancestor loops in PostOrder. If the block is a 533 /// subloop header, add the subloop to its parent in PostOrder, then reverse the 534 /// Block and Subloop vectors of the now complete subloop to achieve RPO. 535 template <class BlockT, class LoopT> 536 void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { 537 LoopT *Subloop = LI->getLoopFor(Block); 538 if (Subloop && Block == Subloop->getHeader()) { 539 // We reach this point once per subloop after processing all the blocks in 540 // the subloop. 541 if (!Subloop->isOutermost()) 542 Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop); 543 else 544 LI->addTopLevelLoop(Subloop); 545 546 // For convenience, Blocks and Subloops are inserted in postorder. Reverse 547 // the lists, except for the loop header, which is always at the beginning. 548 Subloop->reverseBlock(1); 549 std::reverse(Subloop->getSubLoopsVector().begin(), 550 Subloop->getSubLoopsVector().end()); 551 552 Subloop = Subloop->getParentLoop(); 553 } 554 for (; Subloop; Subloop = Subloop->getParentLoop()) 555 Subloop->addBlockEntry(Block); 556 } 557 558 /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal 559 /// interleaved with backward CFG traversals within each subloop 560 /// (discoverAndMapSubloop). The backward traversal skips inner subloops, so 561 /// this part of the algorithm is linear in the number of CFG edges. Subloop and 562 /// Block vectors are then populated during a single forward CFG traversal 563 /// (PopulateLoopDFS). 564 /// 565 /// During the two CFG traversals each block is seen three times: 566 /// 1) Discovered and mapped by a reverse CFG traversal. 567 /// 2) Visited during a forward DFS CFG traversal. 568 /// 3) Reverse-inserted in the loop in postorder following forward DFS. 569 /// 570 /// The Block vectors are inclusive, so step 3 requires loop-depth number of 571 /// insertions per block. 572 template <class BlockT, class LoopT> 573 void LoopInfoBase<BlockT, LoopT>::analyze(const DomTreeBase<BlockT> &DomTree) { 574 // Postorder traversal of the dominator tree. 575 const DomTreeNodeBase<BlockT> *DomRoot = DomTree.getRootNode(); 576 for (auto DomNode : post_order(DomRoot)) { 577 578 BlockT *Header = DomNode->getBlock(); 579 SmallVector<BlockT *, 4> Backedges; 580 581 // Check each predecessor of the potential loop header. 582 for (const auto Backedge : children<Inverse<BlockT *>>(Header)) { 583 // If Header dominates predBB, this is a new loop. Collect the backedges. 584 if (DomTree.dominates(Header, Backedge) && 585 DomTree.isReachableFromEntry(Backedge)) { 586 Backedges.push_back(Backedge); 587 } 588 } 589 // Perform a backward CFG traversal to discover and map blocks in this loop. 590 if (!Backedges.empty()) { 591 LoopT *L = AllocateLoop(Header); 592 discoverAndMapSubloop(L, ArrayRef<BlockT *>(Backedges), this, DomTree); 593 } 594 } 595 // Perform a single forward CFG traversal to populate block and subloop 596 // vectors for all loops. 597 PopulateLoopsDFS<BlockT, LoopT> DFS(this); 598 DFS.traverse(DomRoot->getBlock()); 599 } 600 601 template <class BlockT, class LoopT> 602 SmallVector<LoopT *, 4> 603 LoopInfoBase<BlockT, LoopT>::getLoopsInPreorder() const { 604 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; 605 // The outer-most loop actually goes into the result in the same relative 606 // order as we walk it. But LoopInfo stores the top level loops in reverse 607 // program order so for here we reverse it to get forward program order. 608 // FIXME: If we change the order of LoopInfo we will want to remove the 609 // reverse here. 610 for (LoopT *RootL : reverse(*this)) { 611 auto PreOrderLoopsInRootL = RootL->getLoopsInPreorder(); 612 PreOrderLoops.append(PreOrderLoopsInRootL.begin(), 613 PreOrderLoopsInRootL.end()); 614 } 615 616 return PreOrderLoops; 617 } 618 619 template <class BlockT, class LoopT> 620 SmallVector<LoopT *, 4> 621 LoopInfoBase<BlockT, LoopT>::getLoopsInReverseSiblingPreorder() const { 622 SmallVector<LoopT *, 4> PreOrderLoops, PreOrderWorklist; 623 // The outer-most loop actually goes into the result in the same relative 624 // order as we walk it. LoopInfo stores the top level loops in reverse 625 // program order so we walk in order here. 626 // FIXME: If we change the order of LoopInfo we will want to add a reverse 627 // here. 628 for (LoopT *RootL : *this) { 629 assert(PreOrderWorklist.empty() && 630 "Must start with an empty preorder walk worklist."); 631 PreOrderWorklist.push_back(RootL); 632 do { 633 LoopT *L = PreOrderWorklist.pop_back_val(); 634 // Sub-loops are stored in forward program order, but will process the 635 // worklist backwards so we can just append them in order. 636 PreOrderWorklist.append(L->begin(), L->end()); 637 PreOrderLoops.push_back(L); 638 } while (!PreOrderWorklist.empty()); 639 } 640 641 return PreOrderLoops; 642 } 643 644 // Debugging 645 template <class BlockT, class LoopT> 646 void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { 647 for (unsigned i = 0; i < TopLevelLoops.size(); ++i) 648 TopLevelLoops[i]->print(OS); 649 #if 0 650 for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), 651 E = BBMap.end(); I != E; ++I) 652 OS << "BB '" << I->first->getName() << "' level = " 653 << I->second->getLoopDepth() << "\n"; 654 #endif 655 } 656 657 template <typename T> 658 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { 659 llvm::sort(BB1); 660 llvm::sort(BB2); 661 return BB1 == BB2; 662 } 663 664 template <class BlockT, class LoopT> 665 void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders, 666 const LoopInfoBase<BlockT, LoopT> &LI, 667 const LoopT &L) { 668 LoopHeaders[L.getHeader()] = &L; 669 for (LoopT *SL : L) 670 addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL); 671 } 672 673 #ifndef NDEBUG 674 template <class BlockT, class LoopT> 675 static void compareLoops(const LoopT *L, const LoopT *OtherL, 676 DenseMap<BlockT *, const LoopT *> &OtherLoopHeaders) { 677 BlockT *H = L->getHeader(); 678 BlockT *OtherH = OtherL->getHeader(); 679 assert(H == OtherH && 680 "Mismatched headers even though found in the same map entry!"); 681 682 assert(L->getLoopDepth() == OtherL->getLoopDepth() && 683 "Mismatched loop depth!"); 684 const LoopT *ParentL = L, *OtherParentL = OtherL; 685 do { 686 assert(ParentL->getHeader() == OtherParentL->getHeader() && 687 "Mismatched parent loop headers!"); 688 ParentL = ParentL->getParentLoop(); 689 OtherParentL = OtherParentL->getParentLoop(); 690 } while (ParentL); 691 692 for (const LoopT *SubL : *L) { 693 BlockT *SubH = SubL->getHeader(); 694 const LoopT *OtherSubL = OtherLoopHeaders.lookup(SubH); 695 assert(OtherSubL && "Inner loop is missing in computed loop info!"); 696 OtherLoopHeaders.erase(SubH); 697 compareLoops(SubL, OtherSubL, OtherLoopHeaders); 698 } 699 700 std::vector<BlockT *> BBs = L->getBlocks(); 701 std::vector<BlockT *> OtherBBs = OtherL->getBlocks(); 702 assert(compareVectors(BBs, OtherBBs) && 703 "Mismatched basic blocks in the loops!"); 704 705 const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet(); 706 const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = 707 OtherL->getBlocksSet(); 708 assert(BlocksSet.size() == OtherBlocksSet.size() && 709 llvm::set_is_subset(BlocksSet, OtherBlocksSet) && 710 "Mismatched basic blocks in BlocksSets!"); 711 } 712 #endif 713 714 template <class BlockT, class LoopT> 715 void LoopInfoBase<BlockT, LoopT>::verify( 716 const DomTreeBase<BlockT> &DomTree) const { 717 DenseSet<const LoopT *> Loops; 718 for (iterator I = begin(), E = end(); I != E; ++I) { 719 assert((*I)->isOutermost() && "Top-level loop has a parent!"); 720 (*I)->verifyLoopNest(&Loops); 721 } 722 723 // Verify that blocks are mapped to valid loops. 724 #ifndef NDEBUG 725 for (auto &Entry : BBMap) { 726 const BlockT *BB = Entry.first; 727 LoopT *L = Entry.second; 728 assert(Loops.count(L) && "orphaned loop"); 729 assert(L->contains(BB) && "orphaned block"); 730 for (LoopT *ChildLoop : *L) 731 assert(!ChildLoop->contains(BB) && 732 "BBMap should point to the innermost loop containing BB"); 733 } 734 735 // Recompute LoopInfo to verify loops structure. 736 LoopInfoBase<BlockT, LoopT> OtherLI; 737 OtherLI.analyze(DomTree); 738 739 // Build a map we can use to move from our LI to the computed one. This 740 // allows us to ignore the particular order in any layer of the loop forest 741 // while still comparing the structure. 742 DenseMap<BlockT *, const LoopT *> OtherLoopHeaders; 743 for (LoopT *L : OtherLI) 744 addInnerLoopsToHeadersMap(OtherLoopHeaders, OtherLI, *L); 745 746 // Walk the top level loops and ensure there is a corresponding top-level 747 // loop in the computed version and then recursively compare those loop 748 // nests. 749 for (LoopT *L : *this) { 750 BlockT *Header = L->getHeader(); 751 const LoopT *OtherL = OtherLoopHeaders.lookup(Header); 752 assert(OtherL && "Top level loop is missing in computed loop info!"); 753 // Now that we've matched this loop, erase its header from the map. 754 OtherLoopHeaders.erase(Header); 755 // And recursively compare these loops. 756 compareLoops(L, OtherL, OtherLoopHeaders); 757 } 758 759 // Any remaining entries in the map are loops which were found when computing 760 // a fresh LoopInfo but not present in the current one. 761 if (!OtherLoopHeaders.empty()) { 762 for (const auto &HeaderAndLoop : OtherLoopHeaders) 763 dbgs() << "Found new loop: " << *HeaderAndLoop.second << "\n"; 764 llvm_unreachable("Found new loops when recomputing LoopInfo!"); 765 } 766 #endif 767 } 768 769 } // namespace llvm 770 771 #endif // LLVM_SUPPORT_GENERICLOOPINFOIMPL_H 772