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

129 ↗

(On Diff #275236)

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

[arsenm]

llvm/include/llvm/Analysis/GenericCycleInfo.h

149 ↗

(On Diff #275236)

SmallVector?

153 ↗

(On Diff #275236)

SmallVector?

160 ↗

(On Diff #275236)

Not sure where this uint typedef is coming from

479 ↗

(On Diff #275236)

Is this in a future patch?

llvm/lib/Analysis/GenericCycleInfo.cpp

80 ↗

(On Diff #275236)

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

99 ↗

(On Diff #275236)

I think there is an is_contained for this pattern

136 ↗

(On Diff #275236)

!is_contained

178 ↗

(On Diff #275236)

Unused variable warning in release build

192–200 ↗

(On Diff #275236)

Might as well put these in the header?

344 ↗

(On Diff #275236)

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

427 ↗

(On Diff #275236)

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)

439–440 ↗

(On Diff #275236)

is_contained

444 ↗

(On Diff #275236)

Unused variable in release

453 ↗

(On Diff #275236)

is_contained

472 ↗

(On Diff #275236)

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

129 ↗

(On Diff #275236)

GenericDomTree was a left-over, removed locally.

149 ↗

(On Diff #275236)

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.

153 ↗

(On Diff #275236)

Also following LoopBase.

160 ↗

(On Diff #275236)

Locally changed to unsigned.

479 ↗

(On Diff #275236)

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

80 ↗

(On Diff #275236)

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.

99 ↗

(On Diff #275236)

TIL. Locally replaced this throughout my changes.

344 ↗

(On Diff #275236)

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.

427 ↗

(On Diff #275236)

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

420 ↗

(On Diff #275815)

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

427 ↗

(On Diff #275236)

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

427 ↗

(On Diff #275236)

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 ↗

(On Diff #280484)

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/IR/CFG.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Support/GenericCycleInfo.h"
+
+namespace llvm {
+
+using Cycle = GenericCycle<IrSsaContext>;
+using CycleInfo = GenericCycleInfo<IrSsaContext>;
+
+template <> class ICycleInfoSsaContextMixin<IrSsaContext> {
+public:
+  auto predecessors(BasicBlock *block) const {
+    return llvm::predecessors(block);
+  }
+  auto successors(BasicBlock *block) const { return llvm::successors(block); }
+};
+
+/// 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/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
 //
 //===----------------------------------------------------------------------===//
 //

 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstraintEliminationPass(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 initializeDataFlowSanitizerLegacyPassPass(PassRegistry &);
 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDebugifyMachineModulePass(PassRegistry &);
 void initializeDelinearizationPass(PassRegistry&);

llvm/include/llvm/Support/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/Debug.h"
+#include "llvm/Support/Printable.h"
+#include "llvm/Support/SsaContext.h"
+
+#include <functional>
+#include <vector>
+
+namespace llvm {
+
+/// \brief Extended SsaContext interface for use by cycle info
+class ICycleInfoSsaContext : public ISsaContext {
+public:
+  virtual void appendPredecessors(BlockHandle block,
+                                  SmallVectorImpl<BlockHandle> &list) const = 0;
+  virtual void appendSuccessors(BlockHandle block,
+                                SmallVectorImpl<BlockHandle> &list) const = 0;
+};
+
+/// \brief Implementation of \ref ICycleInfoSsaContext methods
+///
+/// Every IR used with the generic cycle info must provide a specialization of
+/// this template.
+template <typename SsaContextT> class ICycleInfoSsaContextMixin {
+  // RangeType predecessors(BlockRef block) const;
+  // RangeType successors(BlockRef block) const;
+};
+
+template <typename BaseT>
+class ICycleInfoSsaContextImplChain
+    : public BaseT,
+      public ICycleInfoSsaContextMixin<typename BaseT::SsaContext> {
+public:
+  using SsaContext = typename BaseT::SsaContext;
+  using Wrapper = typename SsaContext::Wrapper;
+  using BlockRef = typename SsaContext::BlockRef;
+
+private:
+  using Mixin = ICycleInfoSsaContextMixin<SsaContext>;
+
+public:
+  ICycleInfoSsaContextImplChain(BlockRef block) : BaseT(block) {}
+
+  void appendPredecessors(BlockHandle block,
+                          SmallVectorImpl<BlockHandle> &list) const final {
+    auto range = Mixin::predecessors(Wrapper::unwrapRef(block));
+    list.insert(list.end(), Wrapper::wrapIterator(adl_begin(range)),
+                Wrapper::wrapIterator(adl_end(range)));
+  }
+  void appendSuccessors(BlockHandle block,
+                        SmallVectorImpl<BlockHandle> &list) const final {
+    auto range = Mixin::successors(Wrapper::unwrapRef(block));
+    list.insert(list.end(), Wrapper::wrapIterator(adl_begin(range)),
+                Wrapper::wrapIterator(adl_end(range)));
+  }
+};
+
+template <typename SsaContext, typename Base = ICycleInfoSsaContext>
+using ICycleInfoSsaContextImpl =
+    ICycleInfoSsaContextImplChain<ISsaContextImpl<SsaContext, Base>>;
+
+template <typename RefTypeT>
+using ICycleInfoSsaContextFor =
+    ICycleInfoSsaContextImpl<SsaContextFor<RefTypeT>>;
+
+/// \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<BlockHandle, 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<BlockHandle> 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;
+
+  bool isRoot() const { return !m_parent; }
+
+  /// \brief Whether the cycle is a natural loop.
+  bool isNaturalLoop() const { return !isRoot() && m_entries.size() == 1; }
+
+  BlockHandle getHeader() const { return m_entries[0]; }
+
+  /// \brief Return whether \p block is an entry block of the cycle.
+  bool isEntry(BlockHandle block) const {
+    return is_contained(m_entries, block);
+  }
+
+  /// \brief Return whether \p block is contained in the cycle.
+  bool containsBlock(BlockHandle 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 ISsaContext &ctx) const;
+  Printable print(const ISsaContext &ctx) 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<BlockHandle>::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<BlockHandle>::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 SsaContextT> class GenericCycle : public GenericCycleBase {
+public:
+  using SsaContext = SsaContextT;
+  using Wrapper = typename SsaContext::Wrapper;
+  using Self = GenericCycle<SsaContextT>;
+  using BlockRef = typename SsaContextT::BlockRef;
+
+  bool isEntry(BlockRef block) const {
+    return GenericCycleBase::isEntry(Wrapper::wrapRef(block));
+  }
+  BlockRef getHeader() const {
+    return Wrapper::unwrapRef(GenericCycleBase::getHeader());
+  }
+  bool containsBlock(BlockRef block) const {
+    return GenericCycleBase::containsBlock(Wrapper::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([this](raw_ostream &out) {
+      ISsaContextImpl<SsaContext> iface(getHeader());
+      out << GenericCycleBase::printEntries(iface);
+    });
+  }
+  Printable print() const {
+    return Printable([this](raw_ostream &out) {
+      ISsaContextImpl<SsaContext> iface(getHeader());
+      out << GenericCycleBase::print(iface);
+    });
+  }
+  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 SsaContext::unwrapRange(m_entries); }
+  auto blocks() const { return SsaContext::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<BlockHandle, GenericCycleBase *> m_blockMap;
+
+public:
+  GenericCycleInfoBase();
+  ~GenericCycleInfoBase();
+  GenericCycleInfoBase(GenericCycleInfoBase &&) = default;
+  GenericCycleInfoBase &operator=(GenericCycleInfoBase &&) = default;
+
+  void reset();
+
+  void compute(const ICycleInfoSsaContext &iface, BlockHandle entryBlock);
+
+  /// Methods for updating the cycle info.
+  //@{
+  void splitBlock(BlockHandle oldBlock, BlockHandle newBlock);
+  void extendCycle(const ICycleInfoSsaContext &iface,
+                   GenericCycleBase *cycleToExtend, BlockHandle toBlock,
+                   SmallVectorImpl<BlockHandle> *transferredBlocks = nullptr);
+  void flattenCycles(GenericCycleBase *inner, GenericCycleBase *outer);
+  //@}
+
+  /// \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(BlockHandle block);
+  const GenericCycleBase *getCycle(BlockHandle 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<BlockHandle>
+  findExitBlocks(const ICycleInfoSsaContext &iface,
+                 const GenericCycleBase *cycle,
+                 SmallVectorImpl<BlockHandle> &tmpStorage) const;
+
+  /// Methods for debug and self-test.
+  //@{
+  bool validateTree() const;
+  void print(const ISsaContext &ctx, raw_ostream &out) const;
+  void dump(const ISsaContext &ctx) const { print(ctx, 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 SsaContextT>
+class GenericCycleInfo : public GenericCycleInfoBase {
+public:
+  using SsaContext = SsaContextT;
+  using Wrapper = typename SsaContext::Wrapper;
+  using BlockRef = typename SsaContext::BlockRef;
+  using Cycle = GenericCycle<SsaContext>;
+
+  void compute(BlockRef entryBlock) {
+    GenericCycleInfoBase::compute(
+        ICycleInfoSsaContextImpl<SsaContext>(entryBlock),
+        Wrapper::wrapRef(entryBlock));
+  }
+
+  void splitBlock(BlockRef oldBlock, BlockRef newBlock) {
+    GenericCycleInfoBase::splitBlock(Wrapper::wrapRef(oldBlock),
+                                     Wrapper::wrapRef(newBlock));
+  }
+
+  void extendCycle(Cycle *cycleToExtend, BlockRef toBlock) {
+    GenericCycleInfoBase::extendCycle(
+        ICycleInfoSsaContextImpl<SsaContext>(toBlock), cycleToExtend,
+        Wrapper::wrapRef(toBlock));
+  }
+
+  void flattenCycles(Cycle *inner, Cycle *outer) {
+    GenericCycleInfoBase::flattenCycles(inner, outer);
+  }
+
+  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(Wrapper::wrapRef(block)));
+  }
+  const Cycle *getCycle(BlockRef block) const {
+    return static_cast<const Cycle *>(
+        GenericCycleInfoBase::getCycle(Wrapper::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<BlockHandle> &tmpStorage) const {
+    return SsaContext::unwrapRange(GenericCycleInfoBase::findExitBlocks(
+        ICycleInfoSsaContextImpl<SsaContext>(cycle->getHeader()), cycle,
+        tmpStorage));
+  }
+
+  void print(raw_ostream &out) const {
+    ISsaContextFor<BlockRef> iface(getRoot()->getHeader());
+    GenericCycleInfoBase::print(iface, out);
+  }
+  LLVM_DUMP_METHOD
+  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 SsaContextT>
+struct GraphTraits<const GenericCycle<SsaContextT> *>
+    : GenericCycleGraphTraits<
+          const GenericCycle<SsaContextT> *,
+          typename GenericCycle<SsaContextT>::const_child_iterator> {};
+template <typename SsaContextT>
+struct GraphTraits<GenericCycle<SsaContextT> *>
+    : GenericCycleGraphTraits<
+          GenericCycle<SsaContextT> *,
+          typename GenericCycle<SsaContextT>::const_child_iterator> {};
+
+} // namespace llvm
+
+#endif // LLVM_GENERICCYCLEINFO_H

llvm/lib/Analysis/Analysis.cpp

 //===-- Analysis.cpp ------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
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
   ConstraintSystem.cpp
   Delinearization.cpp
   DemandedBits.cpp
   DependenceAnalysis.cpp
   DependenceGraphBuilder.cpp
   DevelopmentModeInlineAdvisor.cpp
   DivergenceAnalysis.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/Passes/PassBuilder.cpp

 //===- Parsing, selection, and construction of pass pipelines -------------===//
 //
 // 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

 #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/Delinearization.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/IRSimilarityIdentifier.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("func-properties", FunctionPropertiesAnalysis())
 FUNCTION_ANALYSIS("loops", LoopAnalysis())
 FUNCTION_ANALYSIS("lazy-value-info", LazyValueAnalysis())
 FUNCTION_ANALYSIS("da", DependenceAnalysis())

 FUNCTION_PASS("loop-versioning", LoopVersioningPass())
 FUNCTION_PASS("objc-arc-expand", ObjCARCExpandPass())
 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<delinearization>", DelinearizationPrinterPass(dbgs()))
 FUNCTION_PASS("print<demanded-bits>", DemandedBitsPrinterPass(dbgs()))
 FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs()))
 FUNCTION_PASS("print<func-properties>", FunctionPropertiesPrinterPass(dbgs()))
 FUNCTION_PASS("print<inline-cost>", InlineCostAnnotationPrinterPass(dbgs()))
 FUNCTION_PASS("print<inliner-size-estimator>", 

llvm/lib/Support/CMakeLists.txt

add_llvm_component_library(LLVMSupport
   ErrorHandling.cpp
   ExtensibleRTTI.cpp
   FileCollector.cpp
   FileUtilities.cpp
   FileOutputBuffer.cpp
   FoldingSet.cpp
   FormattedStream.cpp
   FormatVariadic.cpp
+  GenericCycleInfo.cpp
   GenericDomTree.cpp
   GlobPattern.cpp
   GraphWriter.cpp
   Hashing.cpp
   InitLLVM.cpp
   IntEqClasses.cpp
   IntervalMap.cpp
   ItaniumManglingCanonicalizer.cpp

llvm/lib/Support/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/Support/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 ICycleInfoSsaContext &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<BlockHandle, DfsInfo> m_blockDfsInfo;
+  SmallVector<BlockHandle, 8> m_blockPreorder;
+
+  friend struct GraphTraits<ContractedDomSubTree>;
+
+  Compute(const Compute &) = delete;
+  Compute &operator=(const Compute &) = delete;
+
+public:
+  Compute(GenericCycleInfoBase &info, const ICycleInfoSsaContext &iface)
+      : m_info(info), m_iface(iface) {}
+
+  void run(BlockHandle entryBlock);
+
+  static void updateDepth(GenericCycleBase *subTree);
+
+private:
+  void dfs(BlockHandle entryBlock);
+};
+
+/// \brief Main function of the cycle info computations.
+void GenericCycleInfoBase::Compute::run(BlockHandle entryBlock) {
+  assert(m_info.m_root->m_entries.empty());
+  m_info.m_root->m_entries.push_back(entryBlock);
+
+  dfs(entryBlock);
+
+  SmallVector<BlockHandle, 4> tmpPredecessors;
+  SmallVector<BlockHandle, 8> worklist;
+
+  for (BlockHandle headerCandidate : llvm::reverse(m_blockPreorder)) {
+    const DfsInfo blockDfsInfo = m_blockDfsInfo.lookup(headerCandidate);
+
+    m_iface.appendPredecessors(headerCandidate, tmpPredecessors);
+    for (BlockHandle pred : tmpPredecessors) {
+      const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred);
+      if (blockDfsInfo.isAncestorOf(predDfsInfo))
+        worklist.push_back(pred);
+    }
+    tmpPredecessors.clear();
+    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 = [&](BlockHandle block) {
+      bool isEntry = false;
+      m_iface.appendPredecessors(block, tmpPredecessors);
+      for (BlockHandle pred : tmpPredecessors) {
+        const DfsInfo predDfsInfo = m_blockDfsInfo.lookup(pred);
+        if (blockDfsInfo.isAncestorOf(predDfsInfo)) {
+          worklist.push_back(pred);
+        } else {
+          isEntry = true;
+        }
+      }
+      tmpPredecessors.clear();
+      if (isEntry) {
+        assert(!is_contained(cycle->m_entries, block));
+        cycle->m_entries.push_back(block);
+      }
+    };
+
+    do {
+      BlockHandle 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 (BlockHandle 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(BlockHandle entryBlock) {
+  SmallVector<unsigned, 8> dfsTreeStack;
+  SmallVector<BlockHandle, 8> traverseStack;
+  unsigned counter = 0;
+  traverseStack.emplace_back(entryBlock);
+
+  do {
+    BlockHandle 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 ISsaContext &ctx) const {
+  return Printable([this, &ctx](raw_ostream &out) {
+    bool first = true;
+    for (BlockHandle entry : m_entries) {
+      if (!first)
+        out << ' ';
+      first = false;
+      out << ctx.printableName(entry);
+    }
+  });
+}
+
+/// \brief Return printable representation of the cycle.
+Printable GenericCycleBase::print(const ISsaContext &ctx) const {
+  return Printable([this, &ctx](raw_ostream &out) {
+    out << "depth=" << m_depth << ": entries(" << printEntries(ctx) << ')';
+
+    for (BlockHandle block : m_blocks) {
+      if (isEntry(block))
+        continue;
+
+      out << ' ' << ctx.printableName(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 ICycleInfoSsaContext &iface,
+                                   BlockHandle 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(BlockHandle oldBlock,
+                                      BlockHandle 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.
+///
+/// If \p transferredBlocks is non-null, all blocks whose direct containing
+/// cycle was changed are appended to the vector.
+void GenericCycleInfoBase::extendCycle(
+    const ICycleInfoSsaContext &iface, GenericCycleBase *cycleToExtend,
+    BlockHandle toBlock, SmallVectorImpl<BlockHandle> *transferredBlocks) {
+  SmallVector<BlockHandle, 32> workList;
+  iface.appendPredecessors(toBlock, workList);
+
+  while (!workList.empty()) {
+    BlockHandle block = workList.pop_back_val();
+    GenericCycleBase *cycle = getCycle(block);
+    if (contains(cycleToExtend, cycle))
+      continue;
+
+    GenericCycleBase *cycleToInclude =
+        findLargestDisjointAncestor(cycle, cycleToExtend);
+    if (cycleToInclude) {
+      GenericCycleBase *oldCommonAncestor = cycleToInclude->getParent();
+
+      // Move cycle into cycleToExtend.
+      auto childIt = llvm::find_if(
+          cycleToInclude->m_parent->m_children,
+          [=](const auto &ptr) -> bool { return cycleToInclude == ptr.get(); });
+      assert(childIt != cycleToInclude->m_parent->m_children.end());
+      cycleToExtend->m_children.push_back(std::move(*childIt));
+      *childIt = std::move(cycleToInclude->m_parent->m_children.back());
+      cycleToInclude->m_parent->m_children.pop_back();
+      cycleToInclude->m_parent = cycleToExtend;
+
+      assert(cycleToInclude->m_depth <= cycleToExtend->m_depth);
+      Compute::updateDepth(cycleToInclude);
+
+      GenericCycleBase *newCommonAncestor = cycleToExtend;
+      do {
+        newCommonAncestor->m_blocks.insert(newCommonAncestor->m_blocks.end(),
+                                           cycleToInclude->m_blocks.begin(),
+                                           cycleToInclude->m_blocks.end());
+        newCommonAncestor = newCommonAncestor->getParent();
+      } while (newCommonAncestor != oldCommonAncestor);
+
+      // Continue from the entries of the newly included cycle.
+      for (BlockHandle entry : cycleToInclude->m_entries)
+        iface.appendPredecessors(entry, workList);
+    } else {
+      // Block is contained in an ancestor of cycleToExtend, just add it
+      // to the cycle and proceed.
+      m_blockMap[block] = cycleToExtend;
+      if (transferredBlocks)
+        transferredBlocks->push_back(block);
+
+      GenericCycleBase *ancestor = cycleToExtend;
+      do {
+        ancestor->m_blocks.push_back(block);
+        ancestor = ancestor->getParent();
+      } while (ancestor != cycle);
+
+      iface.appendPredecessors(block, workList);
+    }
+  }
+
+  assert(validateTree());
+}
+
+/// \brief Flatten the cycle hierarchy such that \p inner is folded into
+///        \p outer.
+///
+/// \p outer must be a strict ancestor of \p inner.
+///
+/// Example change to the cycle hierarchy:
+///
+///       outer                        outer
+///      /  |                         /  |  \
+///     C1  *                       C1   C2  C3
+///        / \            =>
+///      C2   \
+///           inner
+///            |
+///            C3
+///
+void GenericCycleInfoBase::flattenCycles(GenericCycleBase *inner,
+                                         GenericCycleBase *outer) {
+  assert(outer != inner && contains(outer, inner));
+
+  // Re-assign blocks.
+  for (BlockHandle block : outer->m_blocks) {
+    auto it = m_blockMap.find(block);
+    GenericCycleBase *cycle = inner;
+    do {
+      if (cycle == it->second) {
+        it->second = outer;
+        break;
+      }
+      cycle = cycle->getParent();
+    } while (cycle != outer);
+  }
+
+  // Flatten the cycle hierarchy.
+  do {
+    // Remove the inner cycle from its direct parent.
+    GenericCycleBase *parent = inner->m_parent;
+
+    auto it = llvm::find_if(parent->m_children, [=](const auto &child) {
+      return child.get() == inner;
+    });
+    assert(it != parent->m_children.end());
+
+    std::unique_ptr<GenericCycleBase> innerPtr = std::move(*it);
+    parent->m_children.erase(it);
+
+    // Move the inner cycle's direct children to the outer cycle.
+    for (auto &childPtr : inner->m_children) {
+      childPtr->m_parent = inner->m_parent;
+      outer->m_children.emplace_back(std::move(childPtr));
+    }
+
+    inner = inner->getParent();
+  } while (inner != outer);
+
+  assert(validateTree());
+}
+
+/// \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(BlockHandle 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<BlockHandle> GenericCycleInfoBase::findExitBlocks(
+    const ICycleInfoSsaContext &iface, const GenericCycleBase *cycle,
+    SmallVectorImpl<BlockHandle> &tmpStorage) const {
+  tmpStorage.clear();
+
+  size_t numExitBlocks = 0;
+  for (BlockHandle block : cycle->blocks()) {
+    iface.appendSuccessors(block, tmpStorage);
+
+    for (size_t idx = numExitBlocks, end = tmpStorage.size(); idx < end;
+         ++idx) {
+      BlockHandle 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<BlockHandle> blocks;
+  DenseSet<BlockHandle> entries;
+
+  auto reportError = [](const char *file, int line, const char *cond) {
+    errs() << file << ':' << line
+           << ": GenericCycleInfoBase::validateTree: " << cond << '\n';
+  };
+#define check(cond)                                                            \
+  do {                                                                         \
+    if (!(cond)) {                                                             \
+      reportError(__FILE__, __LINE__, #cond);                                  \
+      return false;                                                            \
+    }                                                                          \
+  } while (false)
+
+  for (const GenericCycleBase *cycle : depth_first(getRoot())) {
+    if (!cycle->m_parent) {
+      check(cycle == getRoot());
+      check(cycle->m_entries.size() == 1);
+      check(cycle->m_blocks.empty()); // root cycle is "empty" by convention
+      check(cycle->m_depth == 0);
+    } else {
+      check(cycle != getRoot());
+      check(is_contained(cycle->m_parent->children(), cycle));
+
+      for (BlockHandle block : cycle->m_blocks) {
+        auto mapIt = m_blockMap.find(block);
+        check(mapIt != m_blockMap.end());
+        check(contains(cycle, mapIt->second));
+        check(blocks.insert(block).second); // duplicates in block list?
+      }
+      blocks.clear();
+
+      check(!cycle->m_entries.empty());
+      for (BlockHandle entry : cycle->m_entries) {
+        check(entries.insert(entry).second); // duplicate entry?
+        check(is_contained(cycle->m_blocks, entry));
+      }
+      entries.clear();
+    }
+
+    uint childDepth = 0;
+    for (const GenericCycleBase *child : cycle->children()) {
+      check(child->m_depth > cycle->m_depth);
+      if (!childDepth) {
+        childDepth = child->m_depth;
+      } else {
+        check(childDepth == child->m_depth);
+      }
+    }
+  }
+
+  for (const auto &entry : m_blockMap) {
+    BlockHandle block = entry.first;
+    for (const GenericCycleBase *cycle = entry.second; cycle != getRoot();
+         cycle = cycle->m_parent) {
+      check(is_contained(cycle->m_blocks, block));
+    }
+  }
+
+#undef check
+
+  return true;
+}
+
+/// \brief Print the cycle info.
+void GenericCycleInfoBase::print(const ISsaContext &ctx,
+                                 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(ctx) << '\n';
+  }
+}

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
+}