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