include/llvm/Analysis/LoopInfoImpl.h

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