Analysis: Add a GenericCycleInfo analysis

[nhaehnle]

Summary

This analysis allows algorithms to capture all loops, including irreducible
loops, in a structured way. Based on Havlak (1997), Nesting of Reducible and
Irreducible Loops. See the definition of a "cycle" in the header file and
the IR test cases for more detail.

This patch also immediately adds (new and old-style) IR function passes.

Change-Id: I91f0d001d18906126961dc4aa2f8727ad4aff87c

[RKSimon]

I'll have to leave the implementation review to analysis specialists, but I noticed a few minors.

llvm/include/llvm/Analysis/CycleInfo.h

20

Do you need to include BasicBlock + Dominators? Can you use forward declarations instead?

llvm/include/llvm/Analysis/GenericCycleInfo.h

130

Do you need to include all these? Can you use forward declarations got any instead?

[arsenm]

llvm/include/llvm/Analysis/GenericCycleInfo.h

150

SmallVector?

154

SmallVector?

161

Not sure where this uint typedef is coming from

480

Is this in a future patch?

llvm/lib/Analysis/GenericCycleInfo.cpp

81

I think auto hurts here, and this should explicitly be std::unique_ptr

100

I think there is an is_contained for this pattern

137

!is_contained

179

Unused variable warning in release build

193–201

Might as well put these in the header?

345

I expect documentation comments on the declarations in the header, not in the implementation

428

I think it would be more helpful to have this return a bool for fail/pass, and not directly assert. The assert conditions could print more about why it's not valid (although there so many asserts, this might be annoying)

440–441

is_contained

445

Unused variable in release

454

is_contained

473

is_contained

[nhaehnle]

Thank you for the feedback. I've addressed things locally, will update the patch once I've gone through the whole series (probably on Monday)

llvm/include/llvm/Analysis/CycleInfo.h

20

Cleaned up locally.

llvm/include/llvm/Analysis/GenericCycleInfo.h

130

GenericDomTree was a left-over, removed locally.

150

This is following LoopBase, which uses a std::vector for child loops. I think it makes sense, given that most loops probably don't have any child loops.

m_entries is different: LoopBase doesn't have an equivalent, and we'd expect almost all loops to be natural loops, i.e. with exactly one entry.

154

Also following LoopBase.

161

Locally changed to unsigned.

480

No. I found it hard to implement these kind of templates correctly without code that actually uses them, and since LoopInfo doesn't implement those parts of GraphTraits either, well...

llvm/lib/Analysis/GenericCycleInfo.cpp

81

You mean in terms of readability? I thought it'd be clear because the type is on the RHS, but in any case I've changed it locally.

100

TIL. Locally replaced this throughout my changes.

345

Hmm, I've found different precedents for this in LLVM, e.g. IRBuilder.cpp has a bunch of documentation comments on methods.

Personally, I find it more convenient in the source file: IDEs generally pick the comments up either way, and this keeps the header files leaner which allows the reader to get a quicker overview of what the class offers.

428

It's not clear to me why the fail/pass return would be more helpful?

[nhaehnle]

• cleanup #includes
• use is_contained instead of llvm::find(range, ...) != range.end() pattern
• mark some variables as unused in release builds
• address additional review comments

[arsenm]

llvm/lib/Analysis/GenericCycleInfo.cpp

421

If this is going to be assert-based, might as well disable the whole function ifndef NDEBUG?

428

I sometimes have called these type of verifiers in the middle of passes in gdb but it's not that important

[nhaehnle]

llvm/lib/Analysis/GenericCycleInfo.cpp

428

I'm going down the error message path. It is slightly more convenient -- the error messages probably aren't the most helpful, but at least they are distinct so you can always put a breakpoint there if you want to explore further.

[nhaehnle]

v6:
- rename {to,from}Generic -> {wrap,unwrap}Ref
- validateTree prints errors and returns bool now instead of
  using assertions

[arsenm]

LGTM

[tschuett]

llvm/include/llvm/Analysis/GenericCycleInfo.h

146

m_XX looks like LLDB coding style and not LLVM.

[nhaehnle]

v7:
- add llvm::Cycle alias
- add GenericCycleBase::isRoot and fix ::isNaturalLoop
- fix a number of bugs in GenericCycleInfoBase::extendCycle
  and add a `transferredBlocks` argument
- use a "check" macro in validateTree so that a single breakpoint can
  catch all validation errors

[nhaehnle]

v9:

• rebase on factored-out Handle infrastructure

[sameerds]

Moved to: https://reviews.llvm.org/D112696

Restarted this discussion with a refactored implementation that uses static polymorphism. The result is an analysis implemented as a class template instantiated separately for LLVM IR and Machine IR.

llvm/include/llvm/Analysis/CycleInfo.h

+//===- CycleInfo.h - IR Cycle Info ------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the CycleInfo class, which specializes the GenericCycleInfo
+// for LLVM IR.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_CYCLEINFO_H
+#define LLVM_IR_CYCLEINFO_H
+
+#include "llvm/Analysis/GenericCycleInfo.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+using CycleInfo = GenericCycleInfo<IrCfgTraits>;
+
+/// Analysis pass which computes a \ref CycleInfo.
+class CycleInfoAnalysis : public AnalysisInfoMixin<CycleInfoAnalysis> {
+  friend AnalysisInfoMixin<CycleInfoAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  /// Provide the result typedef for this analysis pass.
+  using Result = CycleInfo;
+
+  /// Run the analysis pass over a function and produce a dominator tree.
+  CycleInfo run(Function &F, FunctionAnalysisManager &);
+
+  // TODO: verify analysis?
+};
+
+/// Printer pass for the \c DominatorTree.
+class CycleInfoPrinterPass : public PassInfoMixin<CycleInfoPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit CycleInfoPrinterPass(raw_ostream &OS);
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Legacy analysis pass which computes a \ref CycleInfo.
+class CycleInfoWrapperPass : public FunctionPass {
+  Function *m_function = nullptr;
+  CycleInfo m_cycleInfo;
+
+public:
+  static char ID;
+
+  CycleInfoWrapperPass();
+
+  CycleInfo &getCycleInfo() { return m_cycleInfo; }
+  const CycleInfo &getCycleInfo() const { return m_cycleInfo; }
+
+  bool runOnFunction(Function &F) override;
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  void releaseMemory() override;
+  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+
+  // TODO: verify analysis?
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ANALYSIS_CYCLEINFO_H

llvm/include/llvm/Analysis/GenericCycleInfo.h

+//===- GenericCycleInfo.h - Control Flow Cycle Calculator -----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// \brief Find all cycles in a control-flow graph, including irreducible loops.
+///
+/// Based on Havlak (1997), Nesting of Reducible and Irreducible Loops.
+///
+/// The term "cycle" is chosen to avoid a clash with the existing notion of
+/// (natural) "loop".
+///
+/// Cycles are defined recursively:
+///  1. The root "cycle" consists of all basic blocks of a function. Its header
+///     is the entry block of the function.
+///  2. The cycles nested inside a cycle C with header H are the maximal
+///     non-trivial strongly connected components of the (induced) subgraph on
+///     (C - H). (Non-trivial means that there must be an actual cycle, i.e.
+///     a single basic blocks is only considered a cycle if it has a self-loop.)
+///
+/// Note: the C++ representation of the root "cycle" does _not_ contain an
+/// explicit list of blocks, to avoid unnecessary memory use.
+///
+/// Every cycle has a \em header block, which is the target of a back edge in
+/// the DFS tree chosen by the analysis.
+///
+/// Every cycle has one or more \em entry blocks, i.e. blocks with incoming
+/// arcs from outside the cycle. The header block is the first entry block;
+/// there is no order among the non-header entry blocks.
+///
+/// Warnings:
+///  - Non-header entry blocks of a cycle can be contained in child cycles.
+///  - Since the set of back edges depends on choices during a DFS (for
+///    irreducible CFGs), there may be edges that "look like" back edges, but
+///    whose destination block is not the header block of any cycle.
+///
+/// Some interesting properties:
+///  - If the CFG is reducible, the cycles are exactly the natural loops and
+///    every cycle has exactly one entry block.
+///  - Cycles are well-nested (by definition).
+///  - The entry blocks of a cycle are siblings in the dominator tree.
+///  - The header of every natural loop is the header of some cycle (natural
+///    loop back edges are back edges in _every_ choice of DFS tree). This
+///    cycle is a superset of the natural loop.
+///
+/// Example (irreducible loop that contains natural loops; arcs are pointing
+/// down unless indicated otherwise, brackets indicate self-loops):
+///
+///     |   |
+///   />A] [B<\
+///   |  \ /  |
+///   ^---C---^
+///       |
+///
+///   The self-loops of A and B give rise to two single-block natural loops.
+///   A possible hierarchy of cycles is:
+///   - cycle of blocks A, B, C, with A as header and B as additional entry
+///     block; containing:
+///   -- cycle of blocks B and C, with C as header and B as additional entry
+///      block; containing
+///   --- singleton cycle of block B
+///   This hierarchy arises when DFS visits the blocks in the order A, C, B (in
+///   preorder).
+///
+/// Example (irreducible loop as union of two natural loops):
+///
+///     |   |
+///     A<->B
+///     ^   ^
+///     |   |
+///     v   v
+///     C   D
+///     |   |
+///
+///   There are two natural loops: A, C and B, D.
+///   A possible hierarchy of cycles is:
+///   - cycle of blocks A, B, C, D, entry blocks A & B, with header A
+///   -- cycle of blocks B, D, entry and header block B
+///
+/// Example (irreducible loop with "back edge" not necessarily pointing to a
+/// header):
+///
+///     |   |
+///    [A<--B<\
+///     |     |
+///     C-----^
+///     |
+///
+///   The self-loop of A gives rise to a natural loop.
+///   One possible cycle analysis is the following hierarchy:
+///   - cycle of blocks A, B, C, with A and B as entry blocks and B as header
+///   -- singleton cycle of block A
+///   Another possible cycle analysis is result is that there is a single cycle
+///   of blocks A, B, C, with A and B as entry blocks and A as header. The
+///   presumed back edge C->B does not target a cycle header. This analysis
+///   result occurs when the DFS visits the blocks in the order A, C, B (in
+///   preorder).
+///
+/// Example (irreducible loop without any natural loops):
+///
+///     |   |
+///   />A   B<\
+///   | |\ /| |
+///   | | x | |
+///   | |/ \| |
+///   ^-C   D-^
+///     |   |
+///
+///   No natural loops, since A, B, C, D are siblings in the dominator tree.
+///   A possible hierarchy of cycles is:
+///   - cycle of blocks A, B, C, D, entry blocks A & B, with header A
+///   -- cycle of blocks B, D, both as entry blocks, and D as header
+///
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_GENERICCYCLEINFO_H
+#define LLVM_GENERICCYCLEINFO_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/CfgTraits.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Printable.h"
+
+#include <functional>
+#include <vector>
+
+namespace llvm {
+
+/// \brief Type-erased base class for a cycle of basic blocks.
+class GenericCycleBase {
+  friend class GenericCycleInfoBase;
+
+protected:
+  /// The parent cycle. Is null for the root "cycle". Top-level cycles point
+  /// at the root.
+  GenericCycleBase *m_parent = nullptr;
+
+  /// The entry block(s) of the cycle. The first entry is the header.
+  SmallVector<CfgBlockRef, 1> m_entries;
+
+  /// Child cycles, if any.
+  std::vector<std::unique_ptr<GenericCycleBase>> m_children;
+
+  /// Basic blocks that are contained in the cycle, including entry blocks,
+  /// and including blocks that are part of a child cycle.
+  std::vector<CfgBlockRef> m_blocks;
+
+  /// Depth of the cycle in the tree. The root "cycle" is at depth 0.
+  ///
+  /// \note Depths are not necessarily contiguous. However, child loops always
+  ///       have strictly greater depth than their parents, and sibling loops
+  ///       always have the same depth.
+  unsigned m_depth = 0;
+
+  GenericCycleBase(const GenericCycleBase &) = delete;
+  GenericCycleBase &operator=(const GenericCycleBase &) = delete;
+  GenericCycleBase(GenericCycleBase &&rhs) = delete;
+  GenericCycleBase &operator=(GenericCycleBase &&rhs) = delete;
+
+public:
+  GenericCycleBase() = default;
+
+  /// \brief Whether the cycle is a natural loop.
+  bool isNaturalLoop() const { return m_entries.size() == 1; }
+
+  CfgBlockRef getHeader() const { return m_entries[0]; }
+
+  /// \brief Return whether \p block is an entry block of the cycle.
+  bool isEntry(CfgBlockRef block) const {
+    return is_contained(m_entries, block);
+  }
+
+  /// \brief Return whether \p block is contained in the cycle.
+  bool containsBlock(CfgBlockRef block) const {
+    return is_contained(m_blocks, block);
+  }
+
+  const GenericCycleBase *getParent() const { return m_parent; }
+  GenericCycleBase *getParent() { return m_parent; }
+  uint getDepth() const { return m_depth; }
+
+  Printable printEntries(const CfgPrinter &printer) const;
+  Printable print(const CfgPrinter &printer) const;
+
+  /// Iteration over child cycles.
+  //@{
+  using const_child_iterator_base =
+      std::vector<std::unique_ptr<GenericCycleBase>>::const_iterator;
+  struct const_child_iterator
+      : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
+    using Base =
+        iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;
+
+    const_child_iterator() = default;
+    explicit const_child_iterator(const_child_iterator_base I) : Base(I) {}
+
+    GenericCycleBase *operator*() const { return I->get(); }
+  };
+
+  const_child_iterator children_begin() const {
+    return const_child_iterator{m_children.begin()};
+  }
+  const_child_iterator children_end() const {
+    return const_child_iterator{m_children.end()};
+  }
+  size_t children_size() const { return m_children.size(); }
+  iterator_range<const_child_iterator> children() const {
+    return llvm::make_range(const_child_iterator{m_children.begin()},
+                            const_child_iterator{m_children.end()});
+  }
+  //@}
+
+  /// Iteration over blocks in the cycle (including entry blocks).
+  //@{
+  using const_blockref_iterator = std::vector<CfgBlockRef>::const_iterator;
+
+  size_t blocks_size() const { return m_blocks.size(); }
+  iterator_range<const_blockref_iterator> blocks() const {
+    return llvm::make_range(m_blocks.begin(), m_blocks.end());
+  }
+  //@}
+
+  /// Iteration over entry blocks.
+  //@{
+  using const_entry_iterator = SmallVectorImpl<CfgBlockRef>::const_iterator;
+
+  size_t entries_size() const { return m_entries.size(); }
+  iterator_range<const_entry_iterator> entries() const {
+    return llvm::make_range(m_entries.begin(), m_entries.end());
+  }
+  //@}
+};
+
+/// \brief A cycle of basic blocks and child cycles.
+template <typename CfgTraitsT> class GenericCycle : public GenericCycleBase {
+public:
+  using CfgTraits = CfgTraitsT;
+  using Self = GenericCycle<CfgTraitsT>;
+  using BlockRef = typename CfgTraitsT::BlockRef;
+
+  bool isEntry(BlockRef block) const {
+    return GenericCycleBase::isEntry(CfgTraits::wrapRef(block));
+  }
+  BlockRef getHeader() const {
+    return CfgTraits::unwrapRef(GenericCycleBase::getHeader());
+  }
+  bool containsBlock(BlockRef block) const {
+    return GenericCycleBase::containsBlock(CfgTraits::wrapRef(block));
+  }
+
+  const GenericCycle *getParent() const {
+    return static_cast<const GenericCycle *>(m_parent);
+  }
+  GenericCycle *getParent() { return static_cast<GenericCycle *>(m_parent); }
+
+  Printable printEntries() const {
+    return Printable([&](raw_ostream &out) {
+      out << GenericCycleBase::printEntries(CfgPrinterImpl<CfgTraits>(
+          CfgInterfaceImpl<CfgTraits>(CfgTraits::getBlockParent(getHeader()))));
+    });
+  }
+  Printable print() const {
+    return Printable([&](raw_ostream &out) {
+      out << GenericCycleBase::print(CfgPrinterImpl<CfgTraits>(
+          CfgInterfaceImpl<CfgTraits>(CfgTraits::getBlockParent(getHeader()))));
+    });
+  }
+  void dump() const { dbgs() << print(); }
+
+  using const_child_iterator_base = GenericCycleBase::const_child_iterator_base;
+  struct const_child_iterator
+      : iterator_adaptor_base<const_child_iterator, const_child_iterator_base> {
+    using Base =
+        iterator_adaptor_base<const_child_iterator, const_child_iterator_base>;
+
+    const_child_iterator() = default;
+    explicit const_child_iterator(const_child_iterator_base I) : Base(I) {}
+
+    Self *operator*() const { return static_cast<Self *>(this->I->get()); }
+  };
+
+  const_child_iterator children_begin() const {
+    return const_child_iterator{m_children.begin()};
+  }
+  const_child_iterator children_end() const {
+    return const_child_iterator{m_children.end()};
+  }
+  iterator_range<const_child_iterator> children() const {
+    return llvm::make_range(children_begin(), children_end());
+  }
+
+  auto entries() const { return CfgTraits::unwrapRange(m_entries); }
+  auto blocks() const { return CfgTraits::unwrapRange(m_blocks); }
+};
+
+/// \brief Type-erased cycle information for a function.
+class GenericCycleInfoBase {
+protected:
+  /// Root "cycle".
+  ///
+  /// A cycle structure is used here primarily to simplify the \ref GraphTraits
+  /// implementation and related iteration. Only the cycle children and entrance
+  /// member is filled in, the blocks member remains empty.
+  ///
+  /// Top-level cycles link back to the root as their parent.
+  ///
+  /// A dynamic allocation is used here to allow GenericCycleInfo to be moved
+  /// without invalidating any cycle pointers.
+  std::unique_ptr<GenericCycleBase> m_root;
+
+  /// Map basic blocks to their inner-most containing loop.
+  DenseMap<CfgBlockRef, GenericCycleBase *> m_blockMap;
+
+public:
+  GenericCycleInfoBase();
+  ~GenericCycleInfoBase();
+  GenericCycleInfoBase(GenericCycleInfoBase &&) = default;
+  GenericCycleInfoBase &operator=(GenericCycleInfoBase &&) = default;
+
+  void reset();
+
+  void compute(const CfgInterface &iface, CfgBlockRef entryBlock);
+
+  /// Methods for updating the cycle info.
+  //@{
+  void splitBlock(CfgBlockRef oldBlock, CfgBlockRef newBlock);
+  void extendCycle(const CfgInterface &iface, GenericCycleBase *cycleToExtend,
+                   CfgBlockRef toBlock);
+  //@}
+
+  /// \brief Return the root "cycle", which contains all the top-level cycles
+  ///        as children.
+  GenericCycleBase *getRoot() { return m_root.get(); }
+  const GenericCycleBase *getRoot() const { return m_root.get(); }
+
+  GenericCycleBase *getCycle(CfgBlockRef block);
+  const GenericCycleBase *getCycle(CfgBlockRef block) const {
+    return const_cast<GenericCycleInfoBase *>(this)->getCycle(block);
+  }
+  bool contains(const GenericCycleBase *a, const GenericCycleBase *b) const;
+  GenericCycleBase *findSmallestCommonCycle(const GenericCycleBase *a,
+                                            const GenericCycleBase *b);
+  const GenericCycleBase *
+  findSmallestCommonCycle(const GenericCycleBase *a,
+                          const GenericCycleBase *b) const {
+    return const_cast<GenericCycleInfoBase *>(this)->findSmallestCommonCycle(a,
+                                                                             b);
+  };
+  GenericCycleBase *findLargestDisjointAncestor(const GenericCycleBase *a,
+                                                const GenericCycleBase *b);
+  const GenericCycleBase *
+  findLargestDisjointAncestor(const GenericCycleBase *a,
+                              const GenericCycleBase *b) const {
+    return const_cast<GenericCycleInfoBase *>(this)
+        ->findLargestDisjointAncestor(a, b);
+  }
+
+  ArrayRef<CfgBlockRef>
+  findExitBlocks(const CfgInterface &iface, const GenericCycleBase *cycle,
+                 SmallVectorImpl<CfgBlockRef> &tmpStorage) const;
+
+  /// Methods for debug and self-test.
+  //@{
+  bool validateTree() const;
+  void print(const CfgPrinter &printer, raw_ostream &out) const;
+  void dump(const CfgPrinter &printer) const { print(printer, dbgs()); }
+  //@}
+
+private:
+  // Helper classes used by the cycle info computation.
+  class ContractedDomSubTree;
+  class Compute;
+
+  friend struct GraphTraits<GenericCycleInfoBase::ContractedDomSubTree>;
+  friend struct DenseMapInfo<ContractedDomSubTree>;
+};
+
+/// \brief Cycle information for a function.
+template <typename CfgTraitsT>
+class GenericCycleInfo : public GenericCycleInfoBase {
+public:
+  using CfgTraits = CfgTraitsT;
+  using ParentType = typename CfgTraits::ParentType;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using Cycle = GenericCycle<CfgTraits>;
+
+  void compute(BlockRef entryBlock) {
+    GenericCycleInfoBase::compute(
+        CfgInterfaceImpl<CfgTraits>(CfgTraits::getBlockParent(entryBlock)),
+        CfgTraits::wrapRef(entryBlock));
+  }
+
+  void splitBlock(BlockRef oldBlock, BlockRef newBlock) {
+    GenericCycleInfoBase::splitBlock(CfgTraits::wrapRef(oldBlock),
+                                     CfgTraits::wrapRef(newBlock));
+  }
+
+  void extendCycle(Cycle *cycleToExtend, BlockRef toBlock) {
+    GenericCycleInfoBase::extendCycle(
+        CfgInterfaceImpl<CfgTraits>(CfgTraits::getBlockParent(toBlock)),
+        cycleToExtend, CfgTraits::wrapRef(toBlock));
+  }
+
+  Cycle *getRoot() { return static_cast<Cycle *>(m_root.get()); }
+  const Cycle *getRoot() const {
+    return static_cast<const Cycle *>(m_root.get());
+  }
+
+  Cycle *getCycle(BlockRef block) {
+    return static_cast<Cycle *>(
+        GenericCycleInfoBase::getCycle(CfgTraits::wrapRef(block)));
+  }
+  const Cycle *getCycle(BlockRef block) const {
+    return static_cast<const Cycle *>(
+        GenericCycleInfoBase::getCycle(CfgTraits::wrapRef(block)));
+  }
+
+  bool contains(const Cycle *a, const Cycle *b) const {
+    return GenericCycleInfoBase::contains(a, b);
+  }
+
+  Cycle *findSmallestCommonCycle(const Cycle *a, const Cycle *b) {
+    return static_cast<Cycle *>(
+        GenericCycleInfoBase::findSmallestCommonCycle(a, b));
+  }
+  const Cycle *findSmallestCommonCycle(const Cycle *a, const Cycle *b) const {
+    return static_cast<const Cycle *>(
+        GenericCycleInfoBase::findSmallestCommonCycle(a, b));
+  }
+
+  Cycle *findLargestDisjointAncestor(const Cycle *a, const Cycle *b) {
+    return static_cast<Cycle *>(
+        GenericCycleInfoBase::findLargestDisjointAncestor(a, b));
+  }
+  const Cycle *findLargestDisjointAncestor(const Cycle *a,
+                                           const Cycle *b) const {
+    return static_cast<const Cycle *>(
+        GenericCycleInfoBase::findLargestDisjointAncestor(a, b));
+  }
+
+  auto findExitBlocks(const Cycle *cycle,
+                      SmallVectorImpl<CfgBlockRef> &tmpStorage) const {
+    return CfgTraits::unwrapRange(GenericCycleInfoBase::findExitBlocks(
+        CfgInterfaceImpl<CfgTraits>(
+            CfgTraits::getBlockParent(cycle->getHeader())),
+        cycle, tmpStorage));
+  }
+
+  void print(raw_ostream &out) const {
+    GenericCycleInfoBase::print(
+        CfgPrinterImpl<CfgTraits>(CfgInterfaceImpl<CfgTraits>(
+            CfgTraits::getBlockParent(getRoot()->getHeader()))),
+        out);
+  }
+  void dump() const { print(dbgs()); }
+};
+
+/// \brief GraphTraits for iterating over a sub-tree of the Cycle tree.
+template <typename CycleRefT, typename ChildIteratorT>
+struct GenericCycleGraphTraits {
+  using NodeRef = CycleRefT;
+
+  using nodes_iterator = ChildIteratorT;
+  using ChildIteratorType = nodes_iterator;
+
+  static NodeRef getEntryNode(NodeRef graph) { return graph; }
+
+  static ChildIteratorType child_begin(NodeRef ref) {
+    return ref->children_begin();
+  }
+  static ChildIteratorType child_end(NodeRef ref) {
+    return ref->children_end();
+  }
+
+  // Not implemented:
+  // static nodes_iterator nodes_begin(GraphType *G)
+  // static nodes_iterator nodes_end  (GraphType *G)
+  //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+
+  // typedef EdgeRef           - Type of Edge token in the graph, which should
+  //                             be cheap to copy.
+  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
+  //                             graph, dereference to a EdgeRef.
+
+  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
+  // static ChildEdgeIteratorType child_edge_end(NodeRef)
+  //     Return iterators that point to the beginning and ending of the
+  //     edge list for the given callgraph node.
+  //
+  // static NodeRef edge_dest(EdgeRef)
+  //     Return the destination node of an edge.
+  // static unsigned       size       (GraphType *G)
+  //    Return total number of nodes in the graph
+};
+
+template <>
+struct GraphTraits<const GenericCycleBase *>
+    : GenericCycleGraphTraits<const GenericCycleBase *,
+                              GenericCycleBase::const_child_iterator> {};
+template <>
+struct GraphTraits<GenericCycleBase *>
+    : GenericCycleGraphTraits<GenericCycleBase *,
+                              GenericCycleBase::const_child_iterator> {};
+template <typename CfgTraitsT>
+struct GraphTraits<const GenericCycle<CfgTraitsT> *>
+    : GenericCycleGraphTraits<
+          const GenericCycle<CfgTraitsT> *,
+          typename GenericCycle<CfgTraitsT>::const_child_iterator> {};
+template <typename CfgTraitsT>
+struct GraphTraits<GenericCycle<CfgTraitsT> *>
+    : GenericCycleGraphTraits<
+          GenericCycle<CfgTraitsT> *,
+          typename GenericCycle<CfgTraitsT>::const_child_iterator> {};
+
+} // namespace llvm
+
+#endif // LLVM_GENERICCYCLEINFO_H

llvm/include/llvm/InitializePasses.h

 //===- llvm/InitializePasses.h - Initialize All Passes ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the declarations for the pass initialization routines

 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstantPropagationPass(PassRegistry&);
 void initializeControlHeightReductionLegacyPassPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
+void initializeCycleInfoWrapperPassPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCELegacyPassPass(PassRegistry&);
 void initializeDSELegacyPassPass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDebugifyMachineModulePass(PassRegistry &);

llvm/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerLegacyPassPass(Registry);
   initializeCFGPrinterLegacyPassPass(Registry);
   initializeCFGOnlyViewerLegacyPassPass(Registry);
   initializeCFGOnlyPrinterLegacyPassPass(Registry);
   initializeCFLAndersAAWrapperPassPass(Registry);
   initializeCFLSteensAAWrapperPassPass(Registry);
+  initializeCycleInfoWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   CallGraph.cpp
   CallGraphSCCPass.cpp
   CallPrinter.cpp
   CaptureTracking.cpp
   CmpInstAnalysis.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  CycleInfo.cpp
   DDG.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DependenceGraphBuilder.cpp
   DevelopmentModeInlineAdvisor.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DomTreeUpdater.cpp
   DominanceFrontier.cpp
   EHPersonalities.cpp
   FunctionPropertiesAnalysis.cpp
+  GenericCycleInfo.cpp
   GlobalsModRef.cpp
   GuardUtils.cpp
   HeatUtils.cpp
   IVDescriptors.cpp
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InlineAdvisor.cpp

llvm/lib/Analysis/CycleInfo.cpp

+//===- CycleInfo.cpp - IR Cycle Info ----------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CycleInfo.h"
+#include "llvm/IR/ModuleSlotTracker.h"
+
+#include "llvm/InitializePasses.h"
+
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+//  CycleInfoAnalysis and related pass implementations
+//===----------------------------------------------------------------------===//
+
+CycleInfo CycleInfoAnalysis::run(Function &F, FunctionAnalysisManager &) {
+  CycleInfo cycleInfo;
+  cycleInfo.compute(&F.getEntryBlock());
+  return cycleInfo;
+}
+
+AnalysisKey CycleInfoAnalysis::Key;
+
+CycleInfoPrinterPass::CycleInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
+
+PreservedAnalyses CycleInfoPrinterPass::run(Function &F,
+                                            FunctionAnalysisManager &AM) {
+  OS << "CycleInfo for function: " << F.getName() << "\n";
+  AM.getResult<CycleInfoAnalysis>(F).print(OS);
+
+  return PreservedAnalyses::all();
+}
+
+//===----------------------------------------------------------------------===//
+//  CycleInfoWrapperPass Implementation
+//===----------------------------------------------------------------------===//
+//
+// The implementation details of the wrapper pass that holds a CycleInfo
+// suitable for use with the legacy pass manager.
+//
+//===----------------------------------------------------------------------===//
+
+char CycleInfoWrapperPass::ID = 0;
+
+CycleInfoWrapperPass::CycleInfoWrapperPass() : FunctionPass(ID) {
+  initializeCycleInfoWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+INITIALIZE_PASS_BEGIN(CycleInfoWrapperPass, "cycleinfo", "Cycle Info Analysis",
+                      true, true)
+INITIALIZE_PASS_END(CycleInfoWrapperPass, "cycleinfo", "Cycle Info Analysis",
+                    true, true)
+
+void CycleInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+bool CycleInfoWrapperPass::runOnFunction(Function &F) {
+  m_cycleInfo.reset();
+
+  m_function = &F;
+  m_cycleInfo.compute(&F.getEntryBlock());
+  return false;
+}
+
+void CycleInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  OS << "CycleInfo for function: " << m_function->getName() << "\n";
+  m_cycleInfo.print(OS);
+}
+
+void CycleInfoWrapperPass::releaseMemory() {
+  m_cycleInfo.reset();
+  m_function = nullptr;
+}

llvm/lib/Analysis/GenericCycleInfo.cpp

+//===- GenericCycleInfo.cpp - Control Flow Cycle Calculator ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/GenericCycleInfo.h"
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+/// \brief Helper class for computing the machine cycle information.
+class GenericCycleInfoBase::Compute {
+  GenericCycleInfoBase &m_info;
+  const CfgInterface &m_iface;
+
+  struct DfsInfo {
+    unsigned start = 0; // DFS start; positive if block is found
+    unsigned end = 0; // DFS end
+
+    DfsInfo() {}
+    explicit DfsInfo(unsigned start) : start(start) {}
+
+    /// Whether this node is an ancestor (or equal to) the node \p other
+    /// in the DFS tree.
+    bool isAncestorOf(const DfsInfo &other) const {
+      return start <= other.start && other.end <= end;
+    }
+  };
+
+  DenseMap<CfgBlockRef, DfsInfo> m_blockDfsInfo;
+  SmallVector<CfgBlockRef, 8> m_blockPreorder;
+
+  friend struct GraphTraits<ContractedDomSubTree>;
+
+  Compute(const Compute &) = delete;
+  Compute &operator=(const Compute &) = delete;
+
+public:
+  Compute(GenericCycleInfoBase &info, const CfgInterface &iface)
+      : m_info(info), m_iface(iface) {}
+
+  void run(CfgBlockRef entryBlock);
+
+  static void updateDepth(GenericCycleBase *subTree);
+
+private:
+  void dfs(CfgBlockRef entryBlock);
+};
+
+/// \brief Main function of the cycle info computations.
+void GenericCycleInfoBase::Compute::run(CfgBlockRef entryBlock) {
+  assert(m_info.m_root->m_entries.empty());
+  m_info.m_root->m_entries.push_back(entryBlock);
+
+  dfs(entryBlock);
+
+  SmallVector<CfgBlockRef, 4> tmpPredecessors;
+  SmallVector<CfgBlockRef, 8> worklist;
+
+  for (CfgBlockRef headerCandidate : llvm::reverse(m_blockPreorder)) {
+    const DfsInfo blockDfsInfo = m_blockDfsInfo.lookup(headerCandidate);
+
+    for (CfgBlockRef pred :
+         m_iface.getPredecessors(headerCandidate, tmpPredecessors)) {
+      const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred);
+      if (blockDfsInfo.isAncestorOf(predDfsInfo))
+        worklist.push_back(pred);
+    }
+    if (worklist.empty())
+      continue;
+
+    // Found a cycle with the candidate as its header.
+    std::unique_ptr<GenericCycleBase> cycle =
+        std::make_unique<GenericCycleBase>();
+    cycle->m_entries.push_back(headerCandidate);
+    cycle->m_blocks.push_back(headerCandidate);
+    m_info.m_blockMap.try_emplace(headerCandidate, cycle.get());
+
+    // Helper function to process (non-back-edge) predecessors of a discovered
+    // block and either add them to the worklist or recognize that the given
+    // block is an additional cycle entry.
+    auto processPredecessors = [&](CfgBlockRef block) {
+      bool isEntry = false;
+      for (CfgBlockRef pred : m_iface.getPredecessors(block, tmpPredecessors)) {
+        const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred);
+        if (blockDfsInfo.isAncestorOf(predDfsInfo)) {
+          worklist.push_back(pred);
+        } else {
+          isEntry = true;
+        }
+      }
+      if (isEntry) {
+        assert(!is_contained(cycle->m_entries, block));
+        cycle->m_entries.push_back(block);
+      }
+    };
+
+    do {
+      CfgBlockRef block = worklist.pop_back_val();
+      if (block == headerCandidate)
+        continue;
+
+      auto mapIt = m_info.m_blockMap.find(block);
+      if (mapIt != m_info.m_blockMap.end()) {
+        // The block has already been discovered by some cycle (possibly by
+        // ourself). Its outer-most discovered ancestor becomes our child if
+        // that hasn't happened yet.
+        GenericCycleBase *child = mapIt->second;
+        while (child->m_parent)
+          child = child->m_parent;
+        if (child != cycle.get()) {
+          auto rootIt = llvm::find_if(
+              m_info.m_root->m_children,
+              [=](const auto &ptr) -> bool { return child == ptr.get(); });
+          assert(rootIt != m_info.m_root->m_children.end());
+          cycle->m_children.push_back(std::move(*rootIt));
+          *rootIt = std::move(m_info.m_root->m_children.back());
+          m_info.m_root->m_children.pop_back();
+
+          child->m_parent = cycle.get();
+
+          cycle->m_blocks.insert(cycle->m_blocks.end(), child->m_blocks.begin(),
+                                 child->m_blocks.end());
+
+          for (CfgBlockRef childEntry : child->entries())
+            processPredecessors(childEntry);
+        }
+      } else {
+        m_info.m_blockMap.try_emplace(block, cycle.get());
+        assert(!is_contained(cycle->m_blocks, block));
+        cycle->m_blocks.push_back(block);
+        processPredecessors(block);
+      }
+    } while (!worklist.empty());
+
+    m_info.m_root->m_children.push_back(std::move(cycle));
+  }
+
+  // Fix top-level cycle links and compute cycle depths.
+  for (GenericCycleBase *topLevelCycle : m_info.m_root->children()) {
+    topLevelCycle->m_parent = m_info.m_root.get();
+    updateDepth(topLevelCycle);
+  }
+}
+
+/// \brief Recompute depth values of \p subTree and all descendants.
+void GenericCycleInfoBase::Compute::updateDepth(GenericCycleBase *subTree) {
+  for (GenericCycleBase *cycle : depth_first(subTree))
+    cycle->m_depth = cycle->m_parent->m_depth + 1;
+}
+
+/// \brief Compute a DFS of basic blocks starting at the function entry.
+///
+/// Fills m_blockDfsInfo with start/end counters and m_blockPreorder.
+void GenericCycleInfoBase::Compute::dfs(CfgBlockRef entryBlock) {
+  SmallVector<unsigned, 8> dfsTreeStack;
+  SmallVector<CfgBlockRef, 8> traverseStack;
+  unsigned counter = 0;
+  traverseStack.emplace_back(entryBlock);
+
+  do {
+    CfgBlockRef block = traverseStack.back();
+    if (!m_blockDfsInfo.count(block)) {
+      // We're visiting the block for the first time. Open its DfsInfo, add
+      // successors to the traversal stack, and remember the traversal stack
+      // depth at which the block was opened, so that we can correctly record
+      // its end time.
+      dfsTreeStack.emplace_back(traverseStack.size());
+      m_iface.appendSuccessors(block, traverseStack);
+
+      LLVM_ATTRIBUTE_UNUSED
+      bool added = m_blockDfsInfo.try_emplace(block, ++counter).second;
+      assert(added);
+      m_blockPreorder.push_back(block);
+    } else {
+      assert(!dfsTreeStack.empty());
+      if (dfsTreeStack.back() == traverseStack.size()) {
+        m_blockDfsInfo.find(block)->second.end = ++counter;
+        dfsTreeStack.pop_back();
+      }
+      traverseStack.pop_back();
+    }
+  } while (!traverseStack.empty());
+  assert(dfsTreeStack.empty());
+}
+
+/// \brief Return printable with space-separated cycle entry blocks.
+Printable GenericCycleBase::printEntries(const CfgPrinter &printer) const {
+  return Printable([this, &printer](raw_ostream &out) {
+    bool first = true;
+    for (CfgBlockRef entry : m_entries) {
+      if (!first)
+        out << ' ';
+      first = false;
+      printer.printBlockName(out, entry);
+    }
+  });
+}
+
+/// \brief Return printable representation of the cycle.
+Printable GenericCycleBase::print(const CfgPrinter &printer) const {
+  return Printable([&](raw_ostream &out) {
+    out << "depth=" << m_depth << ": entries(" << printEntries(printer) << ')';
+
+    for (CfgBlockRef block : m_blocks) {
+      if (isEntry(block))
+        continue;
+
+      out << ' ';
+      printer.printBlockName(out, block);
+    }
+  });
+}
+
+GenericCycleInfoBase::GenericCycleInfoBase()
+    : m_root(std::make_unique<GenericCycleBase>()) {}
+GenericCycleInfoBase::~GenericCycleInfoBase() {}
+
+/// \brief Reset the object to its initial state.
+void GenericCycleInfoBase::reset() {
+  m_root->m_entries.clear(); // remove entry block
+  m_root->m_children.clear();
+  m_blockMap.clear();
+}
+
+/// \brief Compute the cycle info for a function.
+void GenericCycleInfoBase::compute(const CfgInterface &iface,
+                                   CfgBlockRef entryBlock) {
+  Compute compute(*this, iface);
+  compute.run(entryBlock);
+
+  assert(validateTree());
+}
+
+/// \brief Update the cycle info after splitting a basic block.
+///
+/// Notify the cycle info that \p oldBlock was split, with \p newBlock as its
+/// new unique successor. All original successors of \p oldBlock are now
+/// successors of \p newBlock.
+void GenericCycleInfoBase::splitBlock(CfgBlockRef oldBlock,
+                                      CfgBlockRef newBlock) {
+  GenericCycleBase *cycle = getCycle(oldBlock);
+  if (cycle != getRoot()) {
+    cycle->m_blocks.push_back(newBlock);
+    m_blockMap[newBlock] = cycle;
+  }
+}
+
+/// \brief Extend a cycle minimally such that it contains all predecessors of a
+///        given block.
+///
+/// The cycle structure is updated such that all predecessors of \p toBlock will
+/// be contained (possibly indirectly) in \p cycleToExtend, without removing any
+/// cycles: if \p toBlock is not contained in an ancestor of \p cycle, it and
+/// its ancestors will be moved into \p cycleToExtend, as will cousin cycles
+/// that are encountered while following control flow backwards from \p toBlock.
+void GenericCycleInfoBase::extendCycle(const CfgInterface &iface,
+                                       GenericCycleBase *cycleToExtend,
+                                       CfgBlockRef toBlock) {
+  SmallVector<CfgBlockRef, 32> workList;
+  iface.appendPredecessors(toBlock, workList);
+
+  while (!workList.empty()) {
+    CfgBlockRef block = workList.pop_back_val();
+    GenericCycleBase *cycle = getCycle(block);
+    if (contains(cycleToExtend, cycle))
+      continue;
+
+    GenericCycleBase *ancestor =
+        findLargestDisjointAncestor(cycle, cycleToExtend);
+    if (ancestor) {
+      // Move ancestor into cycleToExtend, continue from its entries.
+      auto childIt = llvm::find_if(
+          ancestor->m_parent->m_children,
+          [=](const auto &ptr) -> bool { return ancestor == ptr.get(); });
+      assert(childIt != ancestor->m_parent->m_children.end());
+      cycleToExtend->m_children.push_back(std::move(*childIt));
+      *childIt = std::move(ancestor->m_parent->m_children.back());
+      ancestor->m_parent->m_children.pop_back();
+      ancestor->m_parent = cycleToExtend;
+
+      assert(ancestor->m_depth <= cycleToExtend->m_depth);
+      Compute::updateDepth(ancestor);
+
+      for (CfgBlockRef entry : ancestor->m_entries)
+        iface.appendPredecessors(entry, workList);
+    } else {
+      // Block is contained in an ancestor of cycleToExtend, just add it
+      // to the cycle and proceed.
+      auto blockIt = llvm::find(cycle->m_blocks, block);
+      if (blockIt != cycle->m_blocks.end()) {
+        *blockIt = cycle->m_blocks.back();
+        cycle->m_blocks.pop_back();
+      } else {
+        assert(cycle == getRoot());
+      }
+
+      cycleToExtend->m_blocks.push_back(block);
+      m_blockMap[block] = cycleToExtend;
+
+      iface.appendPredecessors(block, workList);
+    }
+  }
+}
+
+/// \brief Returns true iff \p a contains \p b.
+///
+/// Note: Non-strict containment check, i.e. return true if a == b.
+bool GenericCycleInfoBase::contains(const GenericCycleBase *a,
+                                    const GenericCycleBase *b) const {
+  if (a->m_depth > b->m_depth)
+    return false;
+  while (a->m_depth < b->m_depth)
+    b = b->m_parent;
+  return a == b;
+}
+
+/// \brief Find the innermost cycle containing a given block.
+///
+/// \returns the innermost cycle containing \p block or the root "cycle" if
+///          is not contained in any cycle.
+GenericCycleBase *GenericCycleInfoBase::getCycle(CfgBlockRef block) {
+  auto mapIt = m_blockMap.find(block);
+  if (mapIt != m_blockMap.end())
+    return mapIt->second;
+  return m_root.get();
+}
+
+/// \brief Find the smallest cycle containing both \p a and \p b.
+GenericCycleBase *
+GenericCycleInfoBase::findSmallestCommonCycle(const GenericCycleBase *a,
+                                              const GenericCycleBase *b) {
+  if (a != b) {
+    for (;;) {
+      while (a->m_depth > b->m_depth)
+        a = a->m_parent;
+      while (a->m_depth < b->m_depth)
+        b = b->m_parent;
+      if (a == b)
+        break;
+      b = b->m_parent;
+      a = a->m_parent;
+    }
+  }
+  // const_cast is justified since cycles are owned by this object, which is
+  // non-const.
+  return const_cast<GenericCycleBase *>(a);
+}
+
+/// \brief Finds the largest ancestor of \p a that is disjoint from \b.
+///
+/// The caller must ensure that \p b does not contain \p a. If \p a
+/// contains \p b, null is returned.
+GenericCycleBase *
+GenericCycleInfoBase::findLargestDisjointAncestor(const GenericCycleBase *a,
+                                                  const GenericCycleBase *b) {
+  while (a->m_depth < b->m_depth)
+    b = b->m_parent;
+  if (a == b)
+    return nullptr;
+
+  for (;;) {
+    while (a->m_depth > b->m_depth)
+      a = a->m_parent;
+    while (a->m_depth < b->m_depth)
+      b = b->m_parent;
+    if (a->m_parent == b->m_parent)
+      break;
+    a = a->m_parent;
+    b = b->m_parent;
+  }
+  // const_cast is justified since cycles are owned by this object, which is
+  // non-const.
+  return const_cast<GenericCycleBase *>(a);
+}
+
+/// \brief Find (compute) the exit blocks of a given cycle
+///
+/// Find the blocks outside the cycle with incoming edges from the cycle.
+///
+/// The returned array reference remains valid as long as \p tmpStorage
+/// remains unmodified.
+ArrayRef<CfgBlockRef> GenericCycleInfoBase::findExitBlocks(
+    const CfgInterface &iface, const GenericCycleBase *cycle,
+    SmallVectorImpl<CfgBlockRef> &tmpStorage) const {
+  tmpStorage.clear();
+
+  size_t numExitBlocks = 0;
+  for (CfgBlockRef block : cycle->blocks()) {
+    iface.appendSuccessors(block, tmpStorage);
+
+    for (size_t idx = numExitBlocks, end = tmpStorage.size(); idx < end;
+         ++idx) {
+      CfgBlockRef succ = tmpStorage[idx];
+      if (!contains(cycle, getCycle(succ))) {
+        auto exitEndIt = tmpStorage.begin() + numExitBlocks;
+        if (std::find(tmpStorage.begin(), exitEndIt, succ) == exitEndIt)
+          tmpStorage[numExitBlocks++] = succ;
+      }
+    }
+
+    tmpStorage.resize(numExitBlocks);
+  }
+
+  return tmpStorage;
+}
+
+/// \brief Validate the internal consistency of the cycle tree.
+///
+/// Note that this does \em not check that cycles are really cycles in the CFG,
+/// or that the right set of cycles in the CFG were found.
+bool GenericCycleInfoBase::validateTree() const {
+  DenseSet<CfgBlockRef> blocks;
+  DenseSet<CfgBlockRef> entries;
+
+  for (const GenericCycleBase *cycle : depth_first(getRoot())) {
+    if (!cycle->m_parent) {
+      if (cycle != getRoot()) {
+        errs() << "CycleInfo: non-root cycle with !parent\n";
+        return false;
+      }
+      if (cycle->m_entries.size() != 1) {
+        errs() << "CycleInfo: root cycle with != 1 entry\n";
+        return false;
+      }
+      if (!cycle->m_blocks.empty()) {
+        errs() << "CycleInfo: by convention, the root cycle should store no "
+                  "blocks\n";
+        return false;
+      }
+      if (cycle->m_depth != 0) {
+        errs() << "CycleInfo: root cycle depth != 0\n";
+        return false;
+      }
+    } else {
+      if (cycle == getRoot()) {
+        errs() << "CycleInfo: root cycle has a parent\n";
+        return false;
+      }
+      if (!is_contained(cycle->m_parent->children(), cycle)) {
+        errs() << "CycleInfo: cycle not a child of its parent\n";
+        return false;
+      }
+
+      for (CfgBlockRef block : cycle->m_blocks) {
+        auto mapIt = m_blockMap.find(block);
+        if (mapIt == m_blockMap.end()) {
+          errs() << "CycleInfo: block not in m_blockMap\n";
+          return false;
+        }
+        if (!contains(cycle, mapIt->second)) {
+          errs() << "CycleInfo: cycle block list contains block that is not "
+                    "transitively part of the cycle\n";
+          return false;
+        }
+        if (!blocks.insert(block).second) {
+          errs() << "CycleInfo: block list contains duplicates\n";
+          return false;
+        }
+      }
+      blocks.clear();
+
+      if (cycle->m_entries.empty()) {
+        errs() << "CycleInfo: cycle has no entry\n";
+        return false;
+      }
+      for (CfgBlockRef entry : cycle->m_entries) {
+        if (!entries.insert(entry).second) {
+          errs() << "CycleInfo: entry list contains duplicates\n";
+          return false;
+        }
+        if (!is_contained(cycle->m_blocks, entry)) {
+          errs() << "CycleInfo: cycle entry not contained in block list\n";
+          return false;
+        }
+      }
+      entries.clear();
+    }
+
+    uint childDepth = 0;
+    for (const GenericCycleBase *child : cycle->children()) {
+      if (child->m_depth <= cycle->m_depth) {
+        errs() << "CycleInfo: child not at higher depth than parent\n";
+        return false;
+      }
+      if (!childDepth) {
+        childDepth = child->m_depth;
+      } else {
+        if (childDepth != child->m_depth) {
+          errs() << "CycleInfo: children at different depths\n";
+          return false;
+        }
+      }
+    }
+  }
+
+  for (const auto &entry : m_blockMap) {
+    CfgBlockRef block = entry.first;
+    for (const GenericCycleBase *cycle = entry.second; cycle != getRoot();
+         cycle = cycle->m_parent) {
+      if (!is_contained(cycle->m_blocks, block)) {
+        errs() << "CycleInfo: block not contained in cycle(s) indicated by "
+                  "m_blockMap[block]\n";
+        return false;
+      }
+    }
+  }
+
+  return true;
+}
+
+/// \brief Print the cycle info.
+void GenericCycleInfoBase::print(const CfgPrinter &printer,
+                                 raw_ostream &out) const {
+  for (const GenericCycleBase *cycle : depth_first(getRoot())) {
+    if (!cycle->m_depth)
+      continue;
+
+    for (uint i = 0; i < cycle->m_depth; ++i)
+      out << "    ";
+
+    out << cycle->print(printer) << '\n';
+  }
+}

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/CFGPrinter.h"
 #include "llvm/Analysis/CFLAndersAliasAnalysis.h"
 #include "llvm/Analysis/CFLSteensAliasAnalysis.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CycleInfo.h"
 #include "llvm/Analysis/DDG.h"
 #include "llvm/Analysis/DemandedBits.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/FunctionPropertiesAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IVUsers.h"
 #include "llvm/Analysis/InlineAdvisor.h"

llvm/lib/Passes/PassRegistry.def

 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())
 FUNCTION_ANALYSIS("block-freq", BlockFrequencyAnalysis())
 FUNCTION_ANALYSIS("branch-prob", BranchProbabilityAnalysis())
+FUNCTION_ANALYSIS("cycleinfo", CycleInfoAnalysis())
 FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis())
 FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis())
 FUNCTION_ANALYSIS("demanded-bits", DemandedBitsAnalysis())
 FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())
 FUNCTION_ANALYSIS("func-properties", FunctionPropertiesAnalysis())

 FUNCTION_PASS("loop-fusion", LoopFusePass())
 FUNCTION_PASS("loop-distribute", LoopDistributePass())
 FUNCTION_PASS("pgo-memop-opt", PGOMemOPSizeOpt())
 FUNCTION_PASS("print", PrintFunctionPass(dbgs()))
 FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs()))
 FUNCTION_PASS("print<block-freq>", BlockFrequencyPrinterPass(dbgs()))
 FUNCTION_PASS("print<branch-prob>", BranchProbabilityPrinterPass(dbgs()))
 FUNCTION_PASS("print<da>", DependenceAnalysisPrinterPass(dbgs()))
+FUNCTION_PASS("print<cycleinfo>", CycleInfoPrinterPass(dbgs()))
 FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<inline-cost>", InlineCostAnnotationPrinterPass(dbgs()))
 FUNCTION_PASS("print<inliner-size-estimator>", 
   InlineSizeEstimatorAnalysisPrinterPass(dbgs()))
 FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs()))

llvm/test/Analysis/CycleInfo/basic.ll

+; RUN: opt < %s -cycleinfo -analyze | FileCheck %s -check-prefix=CHECK
+; RUN: opt < %s -disable-output -passes='print<cycleinfo>' 2>&1 | FileCheck %s -check-prefix=CHECK
+
+define void @empty() {
+; CHECK-LABEL: CycleInfo for function: empty
+; CHECK-NOT:       depth
+
+  ret void
+}
+
+define void @simple() {
+; CHECK-LABEL: CycleInfo for function: simple
+; CHECK:           depth=1: entries(loop)
+entry:
+  br label %loop
+
+loop:
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @two_latches() {
+; CHECK-LABEL: CycleInfo for function: two_latches
+; CHECK:           depth=1: entries(loop) loop_next
+entry:
+  br label %loop
+
+loop:
+  br i1 undef, label %loop, label %loop_next
+
+loop_next:
+  br i1 undef, label %exit, label %loop
+
+exit:
+  ret void
+}
+
+define void @nested_simple() {
+; CHECK-LABEL: CycleInfo for function: nested_simple
+; CHECK:           depth=1: entries(outer_header) outer_latch inner
+; CHECK:               depth=2: entries(inner)
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %inner
+
+inner:
+  br i1 undef, label %inner, label %outer_latch
+
+outer_latch:
+  br i1 undef, label %outer_header, label %exit
+
+exit:
+  ret void
+}
+
+define void @nested_outer_latch_in_inner_loop() {
+; CHECK-LABEL: CycleInfo for function: nested_outer_latch_in_inner_loop
+; CHECK:           depth=1: entries(outer_header) inner_header inner_latch
+; CHECK:               depth=2: entries(inner_header) inner_latch
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %inner_header
+
+inner_header:
+  br i1 undef, label %inner_latch, label %outer_header
+
+inner_latch:
+  br i1 undef, label %exit, label %inner_header
+
+exit:
+  ret void
+}
+
+define void @sibling_loops() {
+; CHECK-LABEL: CycleInfo for function: sibling_loops
+; CHECK-DAG:       depth=1: entries(left)
+; CHECK-DAG:       depth=1: entries(right)
+entry:
+  br i1 undef, label %left, label %right
+
+left:
+  br i1 undef, label %left, label %exit
+
+right:
+  br i1 undef, label %right, label %exit
+
+exit:
+  ret void
+}
+
+define void @serial_loops() {
+; CHECK-LABEL: CycleInfo for function: serial_loops
+; CHECK-DAG:       depth=1: entries(second)
+; CHECK-DAG:       depth=1: entries(first)
+entry:
+  br label %first
+
+first:
+  br i1 undef, label %first, label %second
+
+second:
+  br i1 undef, label %second, label %exit
+
+exit:
+  ret void
+}
+
+define void @nested_sibling_loops() {
+; CHECK-LABEL: CycleInfo for function: nested_sibling_loops
+; CHECK:           depth=1: entries(outer_header) left right
+; CHECK-DAG:           depth=2: entries(right)
+; CHECK-DAG:           depth=2: entries(left)
+entry:
+  br label %outer_header
+
+outer_header:
+  br i1 undef, label %left, label %right
+
+left:
+  switch i32 undef, label %exit [ i32 0, label %left
+                                  i32 1, label %outer_header ]
+
+right:
+  switch i32 undef, label %outer_header [ i32 0, label %exit
+                                          i32 1, label %right ]
+
+exit:
+  ret void
+}
+
+define void @deeper_nest() {
+; CHECK-LABEL: CycleInfo for function: deeper_nest
+; CHECK:           depth=1: entries(outer_header) outer_latch middle_header inner_header inner_latch
+; CHECK:               depth=2: entries(middle_header) inner_header inner_latch
+; CHECK:                   depth=3: entries(inner_header) inner_latch
+entry:
+  br label %outer_header
+
+outer_header:
+  br label %middle_header
+
+middle_header:
+  br label %inner_header
+
+inner_header:
+  br i1 undef, label %middle_header, label %inner_latch
+
+inner_latch:
+  br i1 undef, label %inner_header, label %outer_latch
+
+outer_latch:
+  br i1 undef, label %outer_header, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_basic() {
+; CHECK-LABEL: CycleInfo for function: irreducible_basic
+; CHECK:           depth=1: entries(right left)
+entry:
+  br i1 undef, label %left, label %right
+
+left:
+  br i1 undef, label %right, label %exit
+
+right:
+  br i1 undef, label %left, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_mess() {
+; CHECK-LABEL: CycleInfo for function: irreducible_mess
+; CHECK:           depth=1: entries(B A) D C
+; CHECK:               depth=2: entries(D C A)
+; CHECK:                   depth=3: entries(C A)
+entry:
+  br i1 undef, label %A, label %B
+
+A:
+  br i1 undef, label %C, label %D
+
+B:
+  br i1 undef, label %C, label %D
+
+C:
+  switch i32 undef, label %A [ i32 0, label %D
+                               i32 1, label %exit ]
+
+D:
+  switch i32 undef, label %B [ i32 0, label %C
+                               i32 1, label %exit ]
+
+exit:
+  ret void
+}
+
+define void @irreducible_into_simple_cycle() {
+; CHECK-LABEL: CycleInfo for function: irreducible_into_simple_cycle
+; CHECK:           depth=1: entries(F C A) E D B
+entry:
+  switch i32 undef, label %A [ i32 0, label %C
+                               i32 1, label %F ]
+
+A:
+  br label %B
+
+B:
+  br label %C
+
+C:
+  br label %D
+
+D:
+  br i1 undef, label %E, label %exit
+
+E:
+  br label %F
+
+F:
+  br i1 undef, label %A, label %exit
+
+exit:
+  ret void
+}
+
+define void @irreducible_mountain_bug() {
+; CHECK-LABEL: CycleInfo for function: irreducible_mountain_bug
+; CHECK:           depth=1: entries(while.cond)
+; CHECK:               depth=2: entries(cond.end61 cond.true49) while.body63 while.cond47
+; CHECK:                   depth=3: entries(while.body63 cond.true49) while.cond47
+entry:
+  br i1 undef, label %if.end, label %if.then
+
+if.end:
+  br i1 undef, label %if.then7, label %if.else
+
+if.then7:
+  br label %if.end16
+
+if.else:
+  br label %if.end16
+
+if.end16:
+  br i1 undef, label %while.cond.preheader, label %if.then39
+
+while.cond.preheader:
+  br label %while.cond
+
+while.cond:
+  br i1 undef, label %cond.true49, label %lor.rhs
+
+cond.true49:
+  br i1 undef, label %if.then69, label %while.body63
+
+while.body63:
+  br i1 undef, label %exit, label %while.cond47
+
+while.cond47:
+  br i1 undef, label %cond.true49, label %cond.end61
+
+cond.end61:
+  br i1 undef, label %while.body63, label %while.cond
+
+if.then69:
+  br i1 undef, label %exit, label %while.cond
+
+lor.rhs:
+  br i1 undef, label %cond.end61, label %while.end76
+
+while.end76:
+  br label %exit
+
+if.then39:
+  br i1 undef, label %exit, label %if.end.i145
+
+if.end.i145:
+  br i1 undef, label %exit, label %if.end8.i149
+
+if.end8.i149:
+  br label %exit
+
+if.then:
+  br i1 undef, label %exit, label %if.end.i
+
+if.end.i:
+  br i1 undef, label %exit, label %if.end8.i
+
+if.end8.i:
+  br label %exit
+
+exit:
+  ret void
+}