llvm/ADT/GenericCycleImpl.h

0001 //===- GenericCycleImpl.h -------------------------------------*- C++ -*---===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This template implementation resides in a separate file so that it
0011 /// does not get injected into every .cpp file that includes the
0012 /// generic header.
0013 ///
0014 /// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
0015 ///
0016 /// This file should only be included by files that implement a
0017 /// specialization of the relevant templates. Currently these are:
0018 /// - llvm/lib/IR/CycleInfo.cpp
0019 /// - llvm/lib/CodeGen/MachineCycleAnalysis.cpp
0020 ///
0021 //===----------------------------------------------------------------------===//
0022
0023 #ifndef LLVM_ADT_GENERICCYCLEIMPL_H
0024 #define LLVM_ADT_GENERICCYCLEIMPL_H
0025
0026 #include "llvm/ADT/DenseSet.h"
0027 #include "llvm/ADT/DepthFirstIterator.h"
0028 #include "llvm/ADT/GenericCycleInfo.h"
0029 #include "llvm/ADT/StringExtras.h"
0030
0031 #define DEBUG_TYPE "generic-cycle-impl"
0032
0033 namespace llvm {
0034
0035 template <typename ContextT>
0036 bool GenericCycle<ContextT>::contains(const GenericCycle *C) const {
0037   if (!C)
0038     return false;
0039
0040   if (Depth > C->Depth)
0041     return false;
0042   while (Depth < C->Depth)
0043     C = C->ParentCycle;
0044   return this == C;
0045 }
0046
0047 template <typename ContextT>
0048 void GenericCycle<ContextT>::getExitBlocks(
0049     SmallVectorImpl<BlockT *> &TmpStorage) const {
0050   if (!ExitBlocksCache.empty()) {
0051     TmpStorage = ExitBlocksCache;
0052     return;
0053   }
0054
0055   TmpStorage.clear();
0056
0057   size_t NumExitBlocks = 0;
0058   for (BlockT *Block : blocks()) {
0059     llvm::append_range(TmpStorage, successors(Block));
0060
0061     for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
0062          ++Idx) {
0063       BlockT *Succ = TmpStorage[Idx];
0064       if (!contains(Succ)) {
0065         auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
0066         if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
0067           TmpStorage[NumExitBlocks++] = Succ;
0068       }
0069     }
0070
0071     TmpStorage.resize(NumExitBlocks);
0072   }
0073   ExitBlocksCache.append(TmpStorage.begin(), TmpStorage.end());
0074 }
0075
0076 template <typename ContextT>
0077 void GenericCycle<ContextT>::getExitingBlocks(
0078     SmallVectorImpl<BlockT *> &TmpStorage) const {
0079   TmpStorage.clear();
0080
0081   for (BlockT *Block : blocks()) {
0082     for (BlockT *Succ : successors(Block)) {
0083       if (!contains(Succ)) {
0084         TmpStorage.push_back(Block);
0085         break;
0086       }
0087     }
0088   }
0089 }
0090
0091 template <typename ContextT>
0092 auto GenericCycle<ContextT>::getCyclePreheader() const -> BlockT * {
0093   BlockT *Predecessor = getCyclePredecessor();
0094   if (!Predecessor)
0095     return nullptr;
0096
0097   assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
0098
0099   if (succ_size(Predecessor) != 1)
0100     return nullptr;
0101
0102   // Make sure we are allowed to hoist instructions into the predecessor.
0103   if (!Predecessor->isLegalToHoistInto())
0104     return nullptr;
0105
0106   return Predecessor;
0107 }
0108
0109 template <typename ContextT>
0110 auto GenericCycle<ContextT>::getCyclePredecessor() const -> BlockT * {
0111   if (!isReducible())
0112     return nullptr;
0113
0114   BlockT *Out = nullptr;
0115
0116   // Loop over the predecessors of the header node...
0117   BlockT *Header = getHeader();
0118   for (const auto Pred : predecessors(Header)) {
0119     if (!contains(Pred)) {
0120       if (Out && Out != Pred)
0121         return nullptr;
0122       Out = Pred;
0123     }
0124   }
0125
0126   return Out;
0127 }
0128
0129 /// \brief Verify that this is actually a well-formed cycle in the CFG.
0130 template <typename ContextT> void GenericCycle<ContextT>::verifyCycle() const {
0131 #ifndef NDEBUG
0132   assert(!Blocks.empty() && "Cycle cannot be empty.");
0133   DenseSet<BlockT *> Blocks;
0134   for (BlockT *BB : blocks()) {
0135     assert(Blocks.insert(BB).second); // duplicates in block list?
0136   }
0137   assert(!Entries.empty() && "Cycle must have one or more entries.");
0138
0139   DenseSet<BlockT *> Entries;
0140   for (BlockT *Entry : entries()) {
0141     assert(Entries.insert(Entry).second); // duplicate entry?
0142     assert(contains(Entry));
0143   }
0144
0145   // Setup for using a depth-first iterator to visit every block in the cycle.
0146   SmallVector<BlockT *, 8> ExitBBs;
0147   getExitBlocks(ExitBBs);
0148   df_iterator_default_set<BlockT *> VisitSet;
0149   VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
0150
0151   // Keep track of the BBs visited.
0152   SmallPtrSet<BlockT *, 8> VisitedBBs;
0153
0154   // Check the individual blocks.
0155   for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
0156     assert(llvm::any_of(llvm::children<BlockT *>(BB),
0157                         [&](BlockT *B) { return contains(B); }) &&
0158            "Cycle block has no in-cycle successors!");
0159
0160     assert(llvm::any_of(llvm::inverse_children<BlockT *>(BB),
0161                         [&](BlockT *B) { return contains(B); }) &&
0162            "Cycle block has no in-cycle predecessors!");
0163
0164     DenseSet<BlockT *> OutsideCyclePreds;
0165     for (BlockT *B : llvm::inverse_children<BlockT *>(BB))
0166       if (!contains(B))
0167         OutsideCyclePreds.insert(B);
0168
0169     if (Entries.contains(BB)) {
0170       assert(!OutsideCyclePreds.empty() && "Entry is unreachable!");
0171     } else if (!OutsideCyclePreds.empty()) {
0172       // A non-entry block shouldn't be reachable from outside the cycle,
0173       // though it is permitted if the predecessor is not itself actually
0174       // reachable.
0175       BlockT *EntryBB = &BB->getParent()->front();
0176       for (BlockT *CB : depth_first(EntryBB))
0177         assert(!OutsideCyclePreds.contains(CB) &&
0178                "Non-entry block reachable from outside!");
0179     }
0180     assert(BB != &getHeader()->getParent()->front() &&
0181            "Cycle contains function entry block!");
0182
0183     VisitedBBs.insert(BB);
0184   }
0185
0186   if (VisitedBBs.size() != getNumBlocks()) {
0187     dbgs() << "The following blocks are unreachable in the cycle:\n  ";
0188     ListSeparator LS;
0189     for (auto *BB : Blocks) {
0190       if (!VisitedBBs.count(BB)) {
0191         dbgs() << LS;
0192         BB->printAsOperand(dbgs());
0193       }
0194     }
0195     dbgs() << "\n";
0196     llvm_unreachable("Unreachable block in cycle");
0197   }
0198
0199   verifyCycleNest();
0200 #endif
0201 }
0202
0203 /// \brief Verify the parent-child relations of this cycle.
0204 ///
0205 /// Note that this does \em not check that cycle is really a cycle in the CFG.
0206 template <typename ContextT>
0207 void GenericCycle<ContextT>::verifyCycleNest() const {
0208 #ifndef NDEBUG
0209   // Check the subcycles.
0210   for (GenericCycle *Child : children()) {
0211     // Each block in each subcycle should be contained within this cycle.
0212     for (BlockT *BB : Child->blocks()) {
0213       assert(contains(BB) &&
0214              "Cycle does not contain all the blocks of a subcycle!");
0215     }
0216     assert(Child->Depth == Depth + 1);
0217   }
0218
0219   // Check the parent cycle pointer.
0220   if (ParentCycle) {
0221     assert(is_contained(ParentCycle->children(), this) &&
0222            "Cycle is not a subcycle of its parent!");
0223   }
0224 #endif
0225 }
0226
0227 /// \brief Helper class for computing cycle information.
0228 template <typename ContextT> class GenericCycleInfoCompute {
0229   using BlockT = typename ContextT::BlockT;
0230   using CycleInfoT = GenericCycleInfo<ContextT>;
0231   using CycleT = typename CycleInfoT::CycleT;
0232
0233   CycleInfoT &Info;
0234
0235   struct DFSInfo {
0236     unsigned Start = 0; // DFS start; positive if block is found
0237     unsigned End = 0;   // DFS end
0238
0239     DFSInfo() = default;
0240     explicit DFSInfo(unsigned Start) : Start(Start) {}
0241
0242     explicit operator bool() const { return Start; }
0243
0244     /// Whether this node is an ancestor (or equal to) the node \p Other
0245     /// in the DFS tree.
0246     bool isAncestorOf(const DFSInfo &Other) const {
0247       return Start <= Other.Start && Other.End <= End;
0248     }
0249   };
0250
0251   DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
0252   SmallVector<BlockT *, 8> BlockPreorder;
0253
0254   GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete;
0255   GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
0256
0257 public:
0258   GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {}
0259
0260   void run(BlockT *EntryBlock);
0261
0262   static void updateDepth(CycleT *SubTree);
0263
0264 private:
0265   void dfs(BlockT *EntryBlock);
0266 };
0267
0268 template <typename ContextT>
0269 auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(BlockT *Block)
0270     -> CycleT * {
0271   auto Cycle = BlockMapTopLevel.find(Block);
0272   if (Cycle != BlockMapTopLevel.end())
0273     return Cycle->second;
0274
0275   auto MapIt = BlockMap.find(Block);
0276   if (MapIt == BlockMap.end())
0277     return nullptr;
0278
0279   auto *C = MapIt->second;
0280   while (C->ParentCycle)
0281     C = C->ParentCycle;
0282   BlockMapTopLevel.try_emplace(Block, C);
0283   return C;
0284 }
0285
0286 template <typename ContextT>
0287 void GenericCycleInfo<ContextT>::moveTopLevelCycleToNewParent(CycleT *NewParent,
0288                                                               CycleT *Child) {
0289   assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
0290          "NewParent and Child must be both top level cycle!\n");
0291   auto &CurrentContainer =
0292       Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
0293   auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
0294     return Child == Ptr.get();
0295   });
0296   assert(Pos != CurrentContainer.end());
0297   NewParent->Children.push_back(std::move(*Pos));
0298   *Pos = std::move(CurrentContainer.back());
0299   CurrentContainer.pop_back();
0300   Child->ParentCycle = NewParent;
0301
0302   NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
0303
0304   for (auto &It : BlockMapTopLevel)
0305     if (It.second == Child)
0306       It.second = NewParent;
0307   NewParent->clearCache();
0308   Child->clearCache();
0309 }
0310
0311 template <typename ContextT>
0312 void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) {
0313   // FixMe: Appending NewBlock is fine as a set of blocks in a cycle. When
0314   // printing, cycle NewBlock is at the end of list but it should be in the
0315   // middle to represent actual traversal of a cycle.
0316   Cycle->appendBlock(Block);
0317   BlockMap.try_emplace(Block, Cycle);
0318
0319   CycleT *ParentCycle = Cycle->getParentCycle();
0320   while (ParentCycle) {
0321     Cycle = ParentCycle;
0322     Cycle->appendBlock(Block);
0323     ParentCycle = Cycle->getParentCycle();
0324   }
0325
0326   BlockMapTopLevel.try_emplace(Block, Cycle);
0327   Cycle->clearCache();
0328 }
0329
0330 /// \brief Main function of the cycle info computations.
0331 template <typename ContextT>
0332 void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) {
0333   LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
0334                     << "\n");
0335   dfs(EntryBlock);
0336
0337   SmallVector<BlockT *, 8> Worklist;
0338
0339   for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
0340     const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
0341
0342     for (BlockT *Pred : predecessors(HeaderCandidate)) {
0343       const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
0344       // This automatically ignores unreachable predecessors since they have
0345       // zeros in their DFSInfo.
0346       if (CandidateInfo.isAncestorOf(PredDFSInfo))
0347         Worklist.push_back(Pred);
0348     }
0349     if (Worklist.empty()) {
0350       continue;
0351     }
0352
0353     // Found a cycle with the candidate as its header.
0354     LLVM_DEBUG(errs() << "Found cycle for header: "
0355                       << Info.Context.print(HeaderCandidate) << "\n");
0356     std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
0357     NewCycle->appendEntry(HeaderCandidate);
0358     NewCycle->appendBlock(HeaderCandidate);
0359     Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
0360
0361     // Helper function to process (non-back-edge) predecessors of a discovered
0362     // block and either add them to the worklist or recognize that the given
0363     // block is an additional cycle entry.
0364     auto ProcessPredecessors = [&](BlockT *Block) {
0365       LLVM_DEBUG(errs() << "  block " << Info.Context.print(Block) << ": ");
0366
0367       bool IsEntry = false;
0368       for (BlockT *Pred : predecessors(Block)) {
0369         const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
0370         if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
0371           Worklist.push_back(Pred);
0372         } else if (!PredDFSInfo) {
0373           // Ignore an unreachable predecessor. It will will incorrectly cause
0374           // Block to be treated as a cycle entry.
0375           LLVM_DEBUG(errs() << " skipped unreachable predecessor.\n");
0376         } else {
0377           IsEntry = true;
0378         }
0379       }
0380       if (IsEntry) {
0381         assert(!NewCycle->isEntry(Block));
0382         LLVM_DEBUG(errs() << "append as entry\n");
0383         NewCycle->appendEntry(Block);
0384       } else {
0385         LLVM_DEBUG(errs() << "append as child\n");
0386       }
0387     };
0388
0389     do {
0390       BlockT *Block = Worklist.pop_back_val();
0391       if (Block == HeaderCandidate)
0392         continue;
0393
0394       // If the block has already been discovered by some cycle
0395       // (possibly by ourself), then the outermost cycle containing it
0396       // should become our child.
0397       if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
0398         LLVM_DEBUG(errs() << "  block " << Info.Context.print(Block) << ": ");
0399
0400         if (BlockParent != NewCycle.get()) {
0401           LLVM_DEBUG(errs()
0402                      << "discovered child cycle "
0403                      << Info.Context.print(BlockParent->getHeader()) << "\n");
0404           // Make BlockParent the child of NewCycle.
0405           Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
0406
0407           for (auto *ChildEntry : BlockParent->entries())
0408             ProcessPredecessors(ChildEntry);
0409         } else {
0410           LLVM_DEBUG(errs()
0411                      << "known child cycle "
0412                      << Info.Context.print(BlockParent->getHeader()) << "\n");
0413         }
0414       } else {
0415         Info.BlockMap.try_emplace(Block, NewCycle.get());
0416         assert(!is_contained(NewCycle->Blocks, Block));
0417         NewCycle->Blocks.insert(Block);
0418         ProcessPredecessors(Block);
0419         Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
0420       }
0421     } while (!Worklist.empty());
0422
0423     Info.TopLevelCycles.push_back(std::move(NewCycle));
0424   }
0425
0426   // Fix top-level cycle links and compute cycle depths.
0427   for (auto *TLC : Info.toplevel_cycles()) {
0428     LLVM_DEBUG(errs() << "top-level cycle: "
0429                       << Info.Context.print(TLC->getHeader()) << "\n");
0430
0431     TLC->ParentCycle = nullptr;
0432     updateDepth(TLC);
0433   }
0434 }
0435
0436 /// \brief Recompute depth values of \p SubTree and all descendants.
0437 template <typename ContextT>
0438 void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) {
0439   for (CycleT *Cycle : depth_first(SubTree))
0440     Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
0441 }
0442
0443 /// \brief Compute a DFS of basic blocks starting at the function entry.
0444 ///
0445 /// Fills BlockDFSInfo with start/end counters and BlockPreorder.
0446 template <typename ContextT>
0447 void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
0448   SmallVector<unsigned, 8> DFSTreeStack;
0449   SmallVector<BlockT *, 8> TraverseStack;
0450   unsigned Counter = 0;
0451   TraverseStack.emplace_back(EntryBlock);
0452
0453   do {
0454     BlockT *Block = TraverseStack.back();
0455     LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
0456                       << "\n");
0457     if (!BlockDFSInfo.count(Block)) {
0458       // We're visiting the block for the first time. Open its DFSInfo, add
0459       // successors to the traversal stack, and remember the traversal stack
0460       // depth at which the block was opened, so that we can correctly record
0461       // its end time.
0462       LLVM_DEBUG(errs() << "  first encountered at depth "
0463                         << TraverseStack.size() << "\n");
0464
0465       DFSTreeStack.emplace_back(TraverseStack.size());
0466       llvm::append_range(TraverseStack, successors(Block));
0467
0468       bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
0469       (void)Added;
0470       assert(Added);
0471       BlockPreorder.push_back(Block);
0472       LLVM_DEBUG(errs() << "  preorder number: " << Counter << "\n");
0473     } else {
0474       assert(!DFSTreeStack.empty());
0475       if (DFSTreeStack.back() == TraverseStack.size()) {
0476         LLVM_DEBUG(errs() << "  ended at " << Counter << "\n");
0477         BlockDFSInfo.find(Block)->second.End = Counter;
0478         DFSTreeStack.pop_back();
0479       } else {
0480         LLVM_DEBUG(errs() << "  already done\n");
0481       }
0482       TraverseStack.pop_back();
0483     }
0484   } while (!TraverseStack.empty());
0485   assert(DFSTreeStack.empty());
0486
0487   LLVM_DEBUG(
0488     errs() << "Preorder:\n";
0489     for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
0490       errs() << "  " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
0491     }
0492   );
0493 }
0494
0495 /// \brief Reset the object to its initial state.
0496 template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
0497   TopLevelCycles.clear();
0498   BlockMap.clear();
0499   BlockMapTopLevel.clear();
0500 }
0501
0502 /// \brief Compute the cycle info for a function.
0503 template <typename ContextT>
0504 void GenericCycleInfo<ContextT>::compute(FunctionT &F) {
0505   GenericCycleInfoCompute<ContextT> Compute(*this);
0506   Context = ContextT(&F);
0507
0508   LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
0509                     << "\n");
0510   Compute.run(&F.front());
0511 }
0512
0513 template <typename ContextT>
0514 void GenericCycleInfo<ContextT>::splitCriticalEdge(BlockT *Pred, BlockT *Succ,
0515                                                    BlockT *NewBlock) {
0516   // Edge Pred-Succ is replaced by edges Pred-NewBlock and NewBlock-Succ, all
0517   // cycles that had blocks Pred and Succ also get NewBlock.
0518   CycleT *Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
0519   if (!Cycle)
0520     return;
0521
0522   addBlockToCycle(NewBlock, Cycle);
0523   verifyCycleNest();
0524 }
0525
0526 /// \brief Find the innermost cycle containing a given block.
0527 ///
0528 /// \returns the innermost cycle containing \p Block or nullptr if
0529 ///          it is not contained in any cycle.
0530 template <typename ContextT>
0531 auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
0532     -> CycleT * {
0533   return BlockMap.lookup(Block);
0534 }
0535
0536 /// \brief Find the innermost cycle containing both given cycles.
0537 ///
0538 /// \returns the innermost cycle containing both \p A and \p B
0539 ///          or nullptr if there is no such cycle.
0540 template <typename ContextT>
0541 auto GenericCycleInfo<ContextT>::getSmallestCommonCycle(CycleT *A,
0542                                                         CycleT *B) const
0543     -> CycleT * {
0544   if (!A || !B)
0545     return nullptr;
0546
0547   // If cycles A and B have different depth replace them with parent cycle
0548   // until they have the same depth.
0549   while (A->getDepth() > B->getDepth())
0550     A = A->getParentCycle();
0551   while (B->getDepth() > A->getDepth())
0552     B = B->getParentCycle();
0553
0554   // Cycles A and B are at same depth but may be disjoint, replace them with
0555   // parent cycles until we find cycle that contains both or we run out of
0556   // parent cycles.
0557   while (A != B) {
0558     A = A->getParentCycle();
0559     B = B->getParentCycle();
0560   }
0561
0562   return A;
0563 }
0564
0565 /// \brief get the depth for the cycle which containing a given block.
0566 ///
0567 /// \returns the depth for the innermost cycle containing \p Block or 0 if it is
0568 ///          not contained in any cycle.
0569 template <typename ContextT>
0570 unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const {
0571   CycleT *Cycle = getCycle(Block);
0572   if (!Cycle)
0573     return 0;
0574   return Cycle->getDepth();
0575 }
0576
0577 /// \brief Verify the internal consistency of the cycle tree.
0578 ///
0579 /// Note that this does \em not check that cycles are really cycles in the CFG,
0580 /// or that the right set of cycles in the CFG were found.
0581 template <typename ContextT>
0582 void GenericCycleInfo<ContextT>::verifyCycleNest(bool VerifyFull) const {
0583 #ifndef NDEBUG
0584   DenseSet<BlockT *> CycleHeaders;
0585
0586   for (CycleT *TopCycle : toplevel_cycles()) {
0587     for (CycleT *Cycle : depth_first(TopCycle)) {
0588       BlockT *Header = Cycle->getHeader();
0589       assert(CycleHeaders.insert(Header).second);
0590       if (VerifyFull)
0591         Cycle->verifyCycle();
0592       else
0593         Cycle->verifyCycleNest();
0594       // Check the block map entries for blocks contained in this cycle.
0595       for (BlockT *BB : Cycle->blocks()) {
0596         auto MapIt = BlockMap.find(BB);
0597         assert(MapIt != BlockMap.end());
0598         assert(Cycle->contains(MapIt->second));
0599       }
0600     }
0601   }
0602 #endif
0603 }
0604
0605 /// \brief Verify that the entire cycle tree well-formed.
0606 template <typename ContextT> void GenericCycleInfo<ContextT>::verify() const {
0607   verifyCycleNest(/*VerifyFull=*/true);
0608 }
0609
0610 /// \brief Print the cycle info.
0611 template <typename ContextT>
0612 void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const {
0613   for (const auto *TLC : toplevel_cycles()) {
0614     for (const CycleT *Cycle : depth_first(TLC)) {
0615       for (unsigned I = 0; I < Cycle->Depth; ++I)
0616         Out << "    ";
0617
0618       Out << Cycle->print(Context) << '\n';
0619     }
0620   }
0621 }
0622
0623 } // namespace llvm
0624
0625 #undef DEBUG_TYPE
0626
0627 #endif // LLVM_ADT_GENERICCYCLEIMPL_H