Analysis: Add GenericConvergenceUtils and related passes

[nhaehnle]

Summary

Convergence utils are helper classes that maintain information
related to convergence intrinsics, such as where convergence anchors
and users of the corresponding tokens are, as well as where hearts of
cycles are.

The convergence utils will be used both by the convergence-aware
uniform analysis and by the reconvergence wave transform in the
AMDGPU backend.

This change also introduces convergence info passes for IR and tests.

v5:

• cleanup #include's
• mark some variables as unused in a release build

v6:

• rename {to,from}Generic -> {wrap,unwrap}Ref

v7:

• cleanup and refactor in terms of "convergencectrl" bundles
• add a test case for the convergenceinfo pass
• cleanup heart-adjusted post-order

Change-Id: Ia07f99b3588c78b810ef0cec2a0568c351b2b6c6

[arsenm]

Has this been replaced by one of the newer convergence token reviews and can be closed?

[sameerds]

In D85608#4442075, @arsenm wrote:

Has this been replaced by one of the newer convergence token reviews and can be closed?

That's the plan. I am working through this stack of reviews and mapping them to new reviews.

llvm/include/llvm/Analysis/ConvergenceUtils.h

+//===- ConvergenceUtils.h -------------------------------------------------===//
+//
+// 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 Convergence info and convergence-aware uniform info for LLVM IR
+///
+/// This differs from traditional divergence analysis by taking convergence
+/// intrinsics into account.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CONVERGENCEUTILS_H
+#define CONVERGENCEUTILS_H
+
+#include "CycleInfo.h"
+#include "GenericConvergenceUtils.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstrTypes.h"
+
+namespace llvm {
+
+class TargetTransformInfo;
+
+/// \brief Convergence info for LLVM IR.
+class ConvergenceInfo : public GenericConvergenceInfo<IrCfgTraits> {
+public:
+  static ConvergenceInfo compute(const DominatorTree &domTree);
+
+  static OperandBundleDef makeOperandBundleDef(ConvergentOperation *op);
+
+  ConvergentOperation *createIntrinsic(ConvergentOperation::Kind kind,
+                                       ConvergentOperation *parent,
+                                       BasicBlock *block,
+                                       BasicBlock::iterator before,
+                                       const Twine &name = "");
+};
+
+using ConvergentOperation = GenericConvergentOperation<IrCfgTraits>;
+
+/// Analysis pass which computes \ref ConvergenceInfo.
+class ConvergenceInfoAnalysis
+    : public AnalysisInfoMixin<ConvergenceInfoAnalysis> {
+  friend AnalysisInfoMixin<ConvergenceInfoAnalysis>;
+  static AnalysisKey Key;
+
+public:
+  using Result = ConvergenceInfo;
+
+  /// Run the analysis pass over a function and produce a dominator tree.
+  Result run(Function &F, FunctionAnalysisManager &);
+};
+
+/// Printer pass for the \c ConvergenceInfo.
+class ConvergenceInfoPrinterPass
+    : public PassInfoMixin<ConvergenceInfoPrinterPass> {
+  raw_ostream &OS;
+
+public:
+  explicit ConvergenceInfoPrinterPass(raw_ostream &OS);
+
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
+/// Legacy analysis pass which computes \ref ConvergenceInfo.
+class ConvergenceInfoWrapperPass : public FunctionPass {
+  Function *m_function = nullptr;
+  ConvergenceInfo m_convergenceInfo;
+
+public:
+  static char ID;
+
+  ConvergenceInfoWrapperPass();
+
+  ConvergenceInfo &getConvergenceInfo() { return m_convergenceInfo; }
+  const ConvergenceInfo &getConvergenceInfo() const {
+    return m_convergenceInfo;
+  }
+
+  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;
+};
+
+} // namespace llvm
+
+#endif // CONVERGENCEUTILS_H

llvm/include/llvm/Analysis/GenericConvergenceAnalysis.h

+//===- GenericConvergenceAnalysis.h ---------------------------------------===//
+//
+// 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 Generic convergence analysis
+///
+/// Algorithm for filling a \ref GenericConvergenceInfo.
+///
+/// Note that if you only want to use the _results_ of convergence analysis, you
+/// do not need to include this file. In particular, no other header file should
+/// include this header.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_GENERICCONVERGENCEANALYSIS_H
+#define LLVM_GENERICCONVERGENCEANALYSIS_H
+
+#include "GenericConvergenceUtils.h"
+#include "llvm/Support/GenericDomTree.h"
+
+#define DEBUG_TYPE "generic-convergence-analysis"
+
+namespace llvm {
+
+/// \brief Type-erased base class for convergence analysis.
+class GenericConvergenceAnalysisBase {
+private:
+  using ConvergentOperation = GenericConvergentOperationBase;
+
+protected:
+  using ConvergenceBlockInfo = GenericConvergenceInfoBase::ConvergenceBlockInfo;
+
+private:
+  const CfgInterface &m_iface;
+  GenericConvergenceInfoBase &m_convergenceInfo;
+  GenericCycleInfoBase &m_cycleInfo;
+  const GenericDominatorTreeBase &m_domTree;
+
+  SmallVector<std::pair<CfgBlockRef, GenericCycleBase *>, 16>
+      m_pendingExtensions;
+  DenseMap<CfgBlockRef, GenericCycleBase *> m_innermostExtension;
+
+  SmallVector<ConvergentOperation *, 8> m_hearts;
+
+public:
+  GenericConvergenceAnalysisBase(const CfgInterface &iface,
+                                 GenericConvergenceInfoBase &convergenceInfo,
+                                 GenericCycleInfoBase &cycleInfo,
+                                 const GenericDominatorTreeBase &domTree)
+      : m_iface(iface), m_convergenceInfo(convergenceInfo),
+        m_cycleInfo(cycleInfo), m_domTree(domTree) {}
+
+  GenericConvergenceAnalysisBase(const GenericConvergenceAnalysisBase &) =
+      delete;
+  GenericConvergenceAnalysisBase &
+  operator=(const GenericConvergenceAnalysisBase &) = delete;
+
+  void run();
+
+  GenericConvergenceInfoBase &getConvergenceInfo() { return m_convergenceInfo; }
+  const GenericDominatorTreeBase &getDomTree() const { return m_domTree; }
+
+protected:
+  /// \brief Visit all convergent operations.
+  ///
+  /// The CFG-specific implementation must call \ref visitConvergentOperation
+  /// for all relevant operations. Parents (in terms of convergence control)
+  /// must be visited before children, and operations within the same block
+  /// must be visited in-order.
+  virtual void visitConvergentOperations() = 0;
+
+  void visitConvergentOperation(ConvergentOperation *parent,
+                                ConvergentOperation::Kind kind,
+                                CfgBlockRef block,
+                                CfgInstructionRef instruction);
+};
+
+/// \brief Convergence analysis implementation.
+///
+/// Derive from this class using CRTP to implement the CFG- or target-specific
+/// bits.
+template <typename AnalysisT, typename CfgTraitsT>
+class GenericConvergenceAnalysis : public GenericConvergenceAnalysisBase {
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using InstructionRef = typename CfgTraits::InstructionRef;
+  using Cycle = GenericCycle<CfgTraits>;
+  using ConvergenceInfo = GenericConvergenceInfo<CfgTraits>;
+  using ConvergentOperation = GenericConvergentOperation<CfgTraits>;
+  using DomTree =
+      DominatorTreeBase<typename std::pointer_traits<BlockRef>::element_type,
+                        false>;
+
+  GenericConvergenceAnalysis(GenericConvergenceInfo<CfgTraits> &convergenceInfo,
+                             const DomTree &domTree)
+      : GenericConvergenceAnalysisBase(m_ifaceImpl, convergenceInfo,
+                                       convergenceInfo.getCycleInfo(), domTree),
+        m_ifaceImpl(CfgTraits::getBlockParent(domTree.getRoot())) {}
+
+  ConvergenceInfo &getConvergenceInfo() {
+    return static_cast<ConvergenceInfo &>(
+        GenericConvergenceAnalysisBase::getConvergenceInfo());
+  }
+  const DomTree &getDomTree() const {
+    return static_cast<const DomTree &>(
+        GenericConvergenceAnalysisBase::getDomTree());
+  }
+
+protected:
+  CfgInterfaceImpl<CfgTraits> m_ifaceImpl;
+};
+
+} // namespace llvm
+
+#undef DEBUG_TYPE
+
+#endif // LLVM_GENERICCONVERGENCEANALYSIS_H

llvm/include/llvm/Analysis/GenericConvergenceUtils.h

+//===- GenericConvergenceUtils.h - ----------------------------------------===//
+//
+// 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 Data structures and algorithms for analyses related to convergence.
+///
+/// \section Convergence info
+///
+/// \ref GenericConvergenceInfo provides convenient access to information about
+/// how convergent operations relate to each other via convergence control
+/// tokens.
+///
+/// It contains:
+///  - a summary of convergent operations in a tree structure according to
+///    convergence control tokens
+///  - a cycle info that may be adjusted to ensure that controlled convergent
+///    operations are contained in the cycle in which their convergence control
+///    token was defined
+///  - information about the relevant heart in each cycle
+///
+///
+/// \subsection Adjusted cycle info
+///
+/// Example 1:
+/// Suppose there is a self-loop at A with an anchor or loop heart intrinsic
+/// inside the loop, and a convergent operation using that token in E.
+///
+///     |
+///     A]       %a = anchor
+///     |
+///     B
+///     |\
+///     | C
+///     |/ \
+///     D  |
+///     |  E     %e = user (%a)
+///
+/// The cycle info is adjusted so that A, B, and C are all part of the cycle
+/// (but not D or E). Furthermore, the operation in E is marked as "end of
+/// cycle".
+///
+/// Example 2 (nested cycles):
+///
+///     |
+///     A<-\     %a = heart
+///     |  |
+///     B] |     %b = heart (%a)
+///     |  |
+///     C>-/
+///     |
+///     D        %d1 = user (%b)
+///              %d2 = user (%a)
+///
+/// The inner cycle now contains blocks B and C, the outer cycle contains
+/// A, B, and C. Both "user" convergent operations are marked as being an
+/// "end of (their respective) cycle".
+///
+///
+/// \subsection Hearts of cycles
+///
+/// The effective heart of a cycle can be contained in a descendant cycle, if
+/// the heart refers to a convergence control token that is defined outside.
+///
+/// Example 1 (effective heart in a child cycle):
+///
+///      |
+///      A        %a = anchor
+///      |
+///   /->B
+///   |  |
+///   |  C]       %c = heart (%a)
+///   |  |
+///   ^-<D        %d = user (%c)
+///      |
+///
+/// The _adjusted_ cycle nest is:
+///
+///   depth 1: header(B) C D
+///     depth 2: header(C) D
+///
+/// %c is the effective heart of both cycles, but note that \ref getCycle()
+/// on %c returns the inner cycle.
+///
+///
+/// Example 2 (irrelevant heart in a child cycle):
+///
+///      |
+///      A
+///      |
+///   /->B        %b = anchor
+///   |  |
+///   |  C]       %c = heart (%b)
+///   |  |
+///   ^-<D        %d = user (%c)
+///      |
+///
+/// This example has the same (adjusted) cycle nest as the example above, but
+/// the outer cycle has no effective heart at all. The inner cycle has an
+/// effective heart, but it is not relevant for the outer cycle because it
+/// is anchored in the outer cycle.
+///
+///
+/// \section Heart-adjusted post-order
+///
+/// \ref HeartAdjustedPostOrder is a post-order modified so that cycles are
+/// contiguous, with the heart as the last entry (i.e., the heart is first in
+/// heart-adjusted _reverse_ post-order).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_GENERICCONVERGENCEUTILS_H
+#define LLVM_GENERICCONVERGENCEUTILS_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/Analysis/GenericCycleInfo.h"
+
+namespace llvm {
+
+class GenericConvergenceAnalysisBase;
+class GenericDominatorTreeBase;
+template <typename NodeT, bool IsPostDom> class DominatorTreeBase;
+
+template <typename CfgTraitsT> class GenericConvergenceInfo;
+
+class GenericConvergentOperationBase {
+public:
+  enum Kind {
+    /// Defines an initial convergence token referring to the function
+    /// entry / caller.
+    Entry,
+
+    /// Defines an initial convergence token with implementation-defined
+    /// convergence.
+    Anchor,
+
+    /// Loop heart intrinsic: this is where loop iterations are counted.
+    Heart,
+
+    /// Defines a convergence token that is effectively a copy of its parent
+    /// (typically a pointless loop heart intrinsic).
+    Copy,
+
+    /// Uses a convergence token but does not define one.
+    User,
+
+    /// Uncontrolled intrinsic: neither uses nor defines a token.
+    Uncontrolled,
+  };
+
+protected:
+  friend class GenericConvergenceAnalysisBase;
+  friend class GenericConvergenceInfoBase;
+
+  CfgBlockRef m_block;
+  CfgInstructionRef m_instruction;
+  Kind m_kind;
+
+  GenericCycleBase *m_cycle = nullptr;
+
+  GenericConvergentOperationBase *m_parent = nullptr;
+  std::vector<GenericConvergentOperationBase *> m_children;
+
+public:
+  GenericConvergentOperationBase(GenericConvergentOperationBase *parent,
+                                 Kind kind, CfgBlockRef block,
+                                 CfgInstructionRef instruction)
+      : m_block(block), m_instruction(instruction), m_kind(kind),
+        m_parent(parent) {}
+
+  GenericConvergentOperationBase *getParent() const { return m_parent; }
+  CfgBlockRef getBlock() const { return m_block; }
+  Kind getKind() const { return m_kind; }
+  const GenericCycleBase *getCycle() const { return m_cycle; }
+  CfgInstructionRef getInstruction() const { return m_instruction; }
+
+  using const_child_iterator =
+      std::vector<GenericConvergentOperationBase *>::const_iterator;
+
+  const_child_iterator children_begin() const { return m_children.begin(); }
+  const_child_iterator children_end() const { return m_children.end(); }
+
+  iterator_range<const_child_iterator> children() const {
+    return {children_begin(), children_end()};
+  }
+};
+
+template <typename CfgTraitsT>
+class GenericConvergentOperation : public GenericConvergentOperationBase {
+private:
+  friend class GenericConvergenceInfo<CfgTraitsT>;
+
+  // Adaptor which changes an iterator over GenericConvergentOperationBase *
+  // into an iterator over GenericConvergentOperation<CfgTraits>.
+  template <typename BaseIteratorT> struct cast_iterator_adaptor;
+
+  template <typename BaseIteratorT>
+  using cast_iterator_adaptor_base = iterator_adaptor_base<
+      cast_iterator_adaptor<BaseIteratorT>, BaseIteratorT,
+      typename std::iterator_traits<BaseIteratorT>::iterator_category,
+      GenericConvergentOperation *, // value_type
+      typename std::iterator_traits<BaseIteratorT>::difference_type,
+      // pointer (not really usable, but we need to put something here)
+      GenericConvergentOperation **,
+      // reference (not a true reference, because operator* doesn't return one)
+      GenericConvergentOperation *>;
+
+  template <typename BaseIteratorT>
+  struct cast_iterator_adaptor : cast_iterator_adaptor_base<BaseIteratorT> {
+    using Base = cast_iterator_adaptor_base<BaseIteratorT>;
+
+    cast_iterator_adaptor() = default;
+    explicit cast_iterator_adaptor(BaseIteratorT &&it)
+        : Base(std::forward<BaseIteratorT>(it)) {}
+
+    auto operator*() const {
+      return static_cast<GenericConvergentOperation *>(*this->I);
+    }
+  };
+
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using InstructionRef = typename CfgTraits::InstructionRef;
+  using ValueRef = typename CfgTraits::ValueRef;
+
+  GenericConvergentOperation *getParent() const {
+    return static_cast<GenericConvergentOperation *>(m_parent);
+  }
+  BlockRef getBlock() const { return CfgTraits::unwrapRef(m_block); }
+  const GenericCycle<CfgTraits> *getCycle() const {
+    return static_cast<const GenericCycle<CfgTraits> *>(m_cycle);
+  }
+  InstructionRef getInstruction() const {
+    return CfgTraits::unwrapRef(m_instruction);
+  }
+
+  cast_iterator_adaptor<GenericConvergentOperationBase::const_child_iterator>
+  children_begin() const {
+    return {m_children.begin()};
+  }
+  cast_iterator_adaptor<GenericConvergentOperationBase::const_child_iterator>
+  children_end() const {
+    return {m_children.end()};
+  }
+
+  auto children() const {
+    return llvm::make_range(children_begin(), children_end());
+  }
+};
+
+/// \brief Type-erased information about CFG convergence.
+class GenericConvergenceInfoBase {
+  friend class GenericConvergenceAnalysisBase;
+
+public:
+  using ConvergentOperation = GenericConvergentOperationBase;
+
+protected:
+  struct ConvergenceBlockInfo {
+    /// Convergent operations in the block, in order.
+    std::vector<GenericConvergentOperationBase *> operations;
+  };
+
+  DenseMap<CfgInstructionRef, std::unique_ptr<GenericConvergentOperationBase>>
+      m_operation;
+  DenseMap<CfgBlockRef, ConvergenceBlockInfo> m_block;
+  DenseMap<GenericCycleBase *, GenericConvergentOperationBase *> m_heart;
+  std::vector<GenericConvergentOperationBase *> m_roots;
+
+  const ConvergenceBlockInfo &lookupBlock(CfgBlockRef block) const {
+    auto blockIt = m_block.find(block);
+    if (blockIt != m_block.end())
+      return blockIt->second;
+
+    static ConvergenceBlockInfo empty;
+    return empty;
+  }
+
+  GenericConvergenceInfoBase(const GenericConvergenceInfoBase &other) = delete;
+  GenericConvergenceInfoBase &
+  operator=(const GenericConvergenceInfoBase &other) = delete;
+
+public:
+  GenericConvergenceInfoBase() = default;
+  GenericConvergenceInfoBase(GenericConvergenceInfoBase &&other) = default;
+  GenericConvergenceInfoBase &
+  operator=(GenericConvergenceInfoBase &&other) = default;
+
+  void clear();
+
+  CfgBlockRef getHeartBlock(const GenericCycleBase *cycle) const;
+  GenericConvergentOperationBase *getOperation(CfgInstructionRef instruction);
+
+  using const_root_iterator =
+      std::vector<GenericConvergentOperationBase *>::const_iterator;
+
+  const_root_iterator roots_begin() const { return m_roots.begin(); }
+  const_root_iterator roots_end() const { return m_roots.end(); }
+
+  auto roots() const { return llvm::make_range(roots_begin(), roots_end()); }
+
+  using const_block_iterator =
+      std::vector<GenericConvergentOperationBase *>::const_iterator;
+
+  const_block_iterator block_begin(CfgBlockRef block) const {
+    return lookupBlock(block).operations.begin();
+  }
+  const_block_iterator block_end(CfgBlockRef block) const {
+    return lookupBlock(block).operations.end();
+  }
+
+  auto block(CfgBlockRef block) const {
+    const ConvergenceBlockInfo &blockInfo = lookupBlock(block);
+    return llvm::make_range(blockInfo.operations.begin(),
+                            blockInfo.operations.end());
+  }
+
+  bool validate(const GenericCycleInfoBase &cycleInfo) const;
+  void print(const CfgPrinter &printer, const GenericCycleInfoBase &cycleInfo,
+             raw_ostream &out) const;
+
+  // Updating the convergence info based on changes made to the IR.
+  //
+  // Note: Changes that would extend/shrink cycles are currently _not_
+  //       supported here at all!
+  ConvergentOperation *
+  insertOperation(const CfgInterface &iface, GenericCycleInfoBase &cycleInfo,
+                  ConvergentOperation *parent, ConvergentOperation::Kind kind,
+                  CfgBlockRef block, CfgInstructionRef instruction);
+  void eraseOperation(GenericCycleInfoBase &cycleInfo, ConvergentOperation *op);
+
+private:
+  void registerHeart(ConvergentOperation *heart);
+  void unregisterHeart(ConvergentOperation *heart);
+};
+
+/// \brief Base class for CFG-specific convergence info.
+///
+/// Derive from this class using CRTP and implement the CFG-specific bits of
+/// the analysis.
+template <typename CfgTraitsT>
+class GenericConvergenceInfo : public GenericConvergenceInfoBase {
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using InstructionRef = typename CfgTraits::InstructionRef;
+  using CycleInfo = GenericCycleInfo<CfgTraits>;
+  using ConvergentOperation = GenericConvergentOperation<CfgTraits>;
+
+private:
+  CycleInfo m_cycleInfo;
+
+public:
+  void clear() {
+    GenericConvergenceInfoBase::clear();
+    m_cycleInfo.reset();
+  }
+
+  CycleInfo &getCycleInfo() { return m_cycleInfo; }
+  const CycleInfo &getCycleInfo() const { return m_cycleInfo; }
+
+  BlockRef getHeartBlock(const GenericCycle<CfgTraits> *cycle) const {
+    return CfgTraits::unwrapRef(
+        GenericConvergenceInfoBase::getHeartBlock(cycle));
+  }
+
+  ConvergentOperation *getOperation(InstructionRef instruction) {
+    return static_cast<ConvergentOperation *>(
+        GenericConvergenceInfoBase::getOperation(
+            CfgTraits::wrapRef(instruction)));
+  }
+
+  using const_root_iterator =
+      typename ConvergentOperation::template cast_iterator_adaptor<
+          GenericConvergenceInfoBase::const_root_iterator>;
+
+  auto roots_begin() const { return const_root_iterator{m_roots.begin()}; }
+  auto roots_end() const { return const_root_iterator{m_roots.end()}; }
+
+  auto roots() const { return llvm::make_range(roots_begin(), roots_end()); }
+
+  using const_block_iterator =
+      typename ConvergentOperation::template cast_iterator_adaptor<
+          GenericConvergenceInfoBase::const_block_iterator>;
+
+  auto block_begin(BlockRef block) const {
+    return const_block_iterator{
+        GenericConvergenceInfoBase::block_begin(CfgTraits::wrapRef(block))};
+  }
+  auto block_end(BlockRef block) const {
+    return const_block_iterator{
+        GenericConvergenceInfoBase::block_end(CfgTraits::wrapRef(block))};
+  }
+
+  auto block(BlockRef block) const {
+    auto range = GenericConvergenceInfoBase::block(CfgTraits::wrapRef(block));
+    return llvm::make_range(const_block_iterator(range.begin()),
+                            const_block_iterator(range.end()));
+  }
+
+  bool validate() const {
+    return GenericConvergenceInfoBase::validate(m_cycleInfo);
+  }
+  void print(raw_ostream &out) const {
+    GenericConvergenceInfoBase::print(
+        CfgPrinterImpl<CfgTraits>(CfgInterfaceImpl<CfgTraits>(
+            CfgTraits::getBlockParent(m_cycleInfo.getRoot()->getHeader()))),
+        m_cycleInfo, out);
+  }
+  LLVM_DUMP_METHOD
+  void dump() const { print(dbgs()); }
+
+  // Updating the convergence info based on changes made to the IR.
+  //
+  // Note: Changes that would extend/shrink cycles are currently _not_
+  //       supported here at all!
+  ConvergentOperation *insertOperation(ConvergentOperation *parent,
+                                       typename ConvergentOperation::Kind kind,
+                                       BlockRef block,
+                                       InstructionRef instruction) {
+    return static_cast<ConvergentOperation *>(
+        GenericConvergenceInfoBase::insertOperation(
+            CfgInterfaceImpl<CfgTraits>(CfgTraits::getBlockParent(block)),
+            m_cycleInfo, parent, kind, CfgTraits::wrapRef(block),
+            CfgTraits::wrapRef(instruction)));
+  }
+
+  void eraseOperation(ConvergentOperation *op) {
+    GenericConvergenceInfoBase::eraseOperation(m_cycleInfo, op);
+  }
+};
+
+/// \brief Type-erased heart-adjusted post order.
+///
+/// The heart-adjusted _reverse_ post order is used as traversal order during
+/// uniform analysis and the reconvergence transform.
+///
+/// The heart-adjusted RPO differs from the regular RPO in that cycles are
+/// treated as contracted nodes which are later expanded as an RPO starting at
+/// the heart. For cycles without an effective heart, we start at the header.
+///
+/// These modifications help the reconvergence transform ensure that the
+/// wave-level CFG has the required convergence guarantees when post-dominator
+/// reconvergence is used, and they help the uniform analysis determine
+/// uniformity in essentially a single pass while being consistent with the
+/// same convergence guarantees.
+///
+/// Note that this function computes the _non-reversed_ heart-adjusted
+/// post order, so you'd typically use it as llvm::reverse(hapo).
+class HeartAdjustedPostOrderBase {
+  std::vector<CfgBlockRef> m_order;
+
+public:
+  using const_iterator = std::vector<CfgBlockRef>::const_iterator;
+
+  bool empty() const { return m_order.empty(); }
+  size_t size() const { return m_order.size(); }
+
+  void clear() { m_order.clear(); }
+  void compute(const CfgInterface &iface,
+               const GenericConvergenceInfoBase &convergenceInfo,
+               const GenericCycleInfoBase &cycleInfo,
+               const GenericDominatorTreeBase &domTree);
+
+  const_iterator begin() const { return m_order.begin(); }
+  const_iterator end() const { return m_order.end(); }
+  CfgBlockRef operator[](size_t idx) const { return m_order[idx]; }
+};
+
+/// \brief Convergence-adjusted post order.
+template <typename CfgTraitsT>
+class HeartAdjustedPostOrder : public HeartAdjustedPostOrderBase {
+public:
+  using CfgTraits = CfgTraitsT;
+  using BlockRef = typename CfgTraits::BlockRef;
+  using DomTree =
+      DominatorTreeBase<typename std::pointer_traits<BlockRef>::element_type,
+                        false>;
+
+  void compute(const GenericConvergenceInfo<CfgTraits> &convergenceInfo,
+               const DomTree &domTree) {
+    HeartAdjustedPostOrderBase::compute(
+        CfgInterfaceImpl<CfgTraits>(
+            CfgTraits::getBlockParent(domTree.getRoot())),
+        convergenceInfo, convergenceInfo.getCycleInfo(), domTree);
+  }
+
+  auto begin() const {
+    return CfgTraits::unwrapIterator(HeartAdjustedPostOrderBase::begin());
+  }
+  auto end() const {
+    return CfgTraits::unwrapIterator(HeartAdjustedPostOrderBase::end());
+  }
+
+  BlockRef operator[](size_t idx) const {
+    return CfgTraits::unwrapRef(HeartAdjustedPostOrderBase::operator[](idx));
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_GENERICCONVERGENCEUTILS_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 initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCallSiteSplittingLegacyPassPass(PassRegistry&);
 void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstantPropagationPass(PassRegistry&);
 void initializeControlHeightReductionLegacyPassPass(PassRegistry&);
+void initializeConvergenceInfoWrapperPassPass(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&);

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);
+  initializeConvergenceInfoWrapperPassPass(Registry);
   initializeCycleInfoWrapperPassPass(Registry);
   initializeDependenceAnalysisWrapperPassPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsWrapperPassPass(Registry);
   initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(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
+  ConvergenceUtils.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
+  GenericConvergenceAnalysis.cpp
+  GenericConvergenceUtils.cpp
   GenericCycleInfo.cpp
   GlobalsModRef.cpp
   GuardUtils.cpp
   HeatUtils.cpp
   IVDescriptors.cpp
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp

llvm/lib/Analysis/ConvergenceUtils.cpp

+//===- ConvergenceUtils.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ConvergenceUtils.h"
+
+#include "llvm/Analysis/GenericConvergenceAnalysis.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/AbstractCallSite.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/InitializePasses.h"
+
+using namespace llvm;
+
+namespace {
+
+/// \brief Analysis for computing convergence info on LLVM IR.
+class ConvergenceAnalysis
+    : public GenericConvergenceAnalysis<ConvergenceAnalysis, IrCfgTraits> {
+public:
+  using Base = GenericConvergenceAnalysis<ConvergenceAnalysis, IrCfgTraits>;
+
+  ConvergenceAnalysis(ConvergenceInfo &convergenceInfo,
+                      const DominatorTree &domTree)
+      : Base(convergenceInfo, domTree) {}
+
+  /// Visit all convergence-relevant intrinsics in depth-first order.
+  void visitConvergentOperations() final {
+    for (BlockRef block : depth_first(getDomTree().getRoot())) {
+      for (Instruction &instr : *block) {
+        if (auto call = dyn_cast<CallBase>(&instr)) {
+          if (!call->isConvergent())
+            continue;
+
+          ConvergentOperation *parent = nullptr;
+          auto ctrl = call->getOperandBundle(LLVMContext::OB_convergencectrl);
+          if (ctrl) {
+            assert(ctrl.getValue().Inputs.size() == 1);
+            Instruction *parentInstr =
+                cast<Instruction>(ctrl.getValue().Inputs[0].get());
+            parent = getConvergenceInfo().getOperation(parentInstr);
+            assert(parent != nullptr);
+          }
+
+          ConvergentOperation::Kind kind =
+              parent ? ConvergentOperation::User
+                     : ConvergentOperation::Uncontrolled;
+
+          if (auto *intrinsic = dyn_cast<IntrinsicInst>(&instr)) {
+            switch (intrinsic->getIntrinsicID()) {
+            case Intrinsic::experimental_convergence_entry:
+              kind = ConvergentOperation::Entry;
+              break;
+            case Intrinsic::experimental_convergence_anchor:
+              kind = ConvergentOperation::Anchor;
+              break;
+            case Intrinsic::experimental_convergence_loop:
+              kind = ConvergentOperation::Heart;
+              break;
+            }
+          }
+
+          visitConvergentOperation(parent, kind, CfgTraits::wrapRef(block),
+                                   CfgTraits::wrapRef(&instr));
+        }
+      }
+    }
+  }
+};
+
+} // anonymous namespace
+
+/// \brief Compute the convergence info for an LLVM IR function.
+ConvergenceInfo ConvergenceInfo::compute(const DominatorTree &domTree) {
+  ConvergenceInfo info;
+  ConvergenceAnalysis analysis(info, domTree);
+  analysis.run();
+  return info;
+}
+
+/// Return the operand bundle to be used for referring to the convergence
+/// control token produced by \op.
+OperandBundleDef
+ConvergenceInfo::makeOperandBundleDef(ConvergentOperation *op) {
+  assert(op->getKind() == ConvergentOperation::Entry ||
+         op->getKind() == ConvergentOperation::Anchor ||
+         op->getKind() == ConvergentOperation::Heart ||
+         op->getKind() == ConvergentOperation::Copy);
+
+  Instruction *instr = cast<Instruction>(op->getInstruction());
+  Value *token[1] = {instr};
+  assert(token[0]->getType()->isTokenTy());
+
+  return OperandBundleDef{"convergencectrl", token};
+}
+
+/// Insert an entry/anchor/loop heart intrinsic at the given position.
+///
+/// Updates the convergence info.
+ConvergentOperation *ConvergenceInfo::createIntrinsic(
+    ConvergentOperation::Kind kind, ConvergentOperation *parent,
+    BasicBlock *block, BasicBlock::iterator before, const Twine &name) {
+  IRBuilder<> builder(block, before);
+
+  Intrinsic::ID iid;
+  switch (kind) {
+  case ConvergentOperation::Entry:
+    iid = Intrinsic::experimental_convergence_entry;
+    break;
+  case ConvergentOperation::Anchor:
+    iid = Intrinsic::experimental_convergence_anchor;
+    break;
+  case ConvergentOperation::Heart:
+    iid = Intrinsic::experimental_convergence_loop;
+    break;
+  default:
+    // Can't create User etc. here
+    llvm_unreachable("bad convergent operation kind");
+  }
+
+  Module *module = block->getModule();
+  Function *fn = Intrinsic::getDeclaration(module, iid, {});
+  SmallVector<OperandBundleDef, 1> bundles;
+
+  if (parent)
+    bundles.emplace_back(makeOperandBundleDef(parent));
+
+  CallInst *call =
+      builder.CreateCall(fn->getFunctionType(), fn, {}, bundles, name);
+
+  return insertOperation(parent, kind, block, call);
+}
+
+//===----------------------------------------------------------------------===//
+//  ConvergenceInfoAnalysis and related pass implementations
+//===----------------------------------------------------------------------===//
+
+ConvergenceInfoAnalysis::Result
+ConvergenceInfoAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
+  auto &domTree = FAM.getResult<DominatorTreeAnalysis>(F);
+  return ConvergenceInfo::compute(domTree);
+}
+
+AnalysisKey ConvergenceInfoAnalysis::Key;
+
+ConvergenceInfoPrinterPass::ConvergenceInfoPrinterPass(raw_ostream &OS)
+    : OS(OS) {}
+
+PreservedAnalyses ConvergenceInfoPrinterPass::run(Function &F,
+                                                  FunctionAnalysisManager &AM) {
+  auto &result = AM.getResult<ConvergenceInfoAnalysis>(F);
+  OS << "ConvergenceInfo for function: " << F.getName() << '\n';
+  result.print(OS);
+  return PreservedAnalyses::all();
+}
+
+//===----------------------------------------------------------------------===//
+//  ConvergenceInfoWrapperPass Implementation
+//===----------------------------------------------------------------------===//
+
+char ConvergenceInfoWrapperPass::ID = 0;
+
+ConvergenceInfoWrapperPass::ConvergenceInfoWrapperPass() : FunctionPass(ID) {
+  initializeConvergenceInfoWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+INITIALIZE_PASS_BEGIN(ConvergenceInfoWrapperPass, "convergenceinfo",
+                      "Convergence Info Analysis", true, true)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(ConvergenceInfoWrapperPass, "convergenceinfo",
+                    "Convergence Info Analysis", true, true)
+
+void ConvergenceInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<DominatorTreeWrapperPass>();
+}
+
+bool ConvergenceInfoWrapperPass::runOnFunction(Function &F) {
+  m_convergenceInfo.clear();
+
+  auto &domTree = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  m_function = &F;
+  m_convergenceInfo = ConvergenceInfo::compute(domTree);
+  return false;
+}
+
+void ConvergenceInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
+  OS << "ConvergenceInfo for function: " << m_function->getName() << "\n";
+  m_convergenceInfo.print(OS);
+}
+
+void ConvergenceInfoWrapperPass::releaseMemory() {
+  m_convergenceInfo.clear();
+  m_function = nullptr;
+}

llvm/lib/Analysis/GenericConvergenceAnalysis.cpp

+//===- GenericConvergenceAnalysis.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
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// \brief Implementation of generic convergence analysis.
+///
+/// Convergence analysis collects convergence intrinsics for quick reference and
+/// adjusts the cycle structure of a CycleInfo that is local to the convergence
+/// info to reflect the effects of convergence intrinsics that enforce
+/// non-reconvergence.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/GenericConvergenceAnalysis.h"
+
+#define DEBUG_TYPE "generic-convergence-analysis"
+
+using namespace llvm;
+
+void GenericConvergenceAnalysisBase::run() {
+  // Compute our own cycle info since we will modify it based on convergence
+  // intrinsics.
+  m_cycleInfo.compute(m_iface, m_domTree.getRootNode()->getBlock());
+
+  // Step 1: CFG-specific program traversal to collect all relevant operations
+  // and their linkage.
+  visitConvergentOperations();
+
+  // Step 2: Work through the cycle extensions.
+  SmallVector<CfgBlockRef, 16> extendedBlocks;
+
+  while (!m_pendingExtensions.empty()) {
+    CfgBlockRef const extendBlock = m_pendingExtensions.back().first;
+    GenericCycleBase *const extendCycle = m_pendingExtensions.back().second;
+    m_pendingExtensions.pop_back();
+
+    GenericCycleBase *&innermost = m_innermostExtension[extendBlock];
+    if (innermost && m_cycleInfo.contains(extendCycle, innermost)) {
+      // Already done (possibly implicitly) by a previous extension of the same
+      // block.
+      continue;
+    }
+    innermost = extendCycle;
+
+    if (extendCycle->containsBlock(extendBlock)) {
+      // Already done by a previous extension of a different block.
+      continue;
+    }
+
+    m_cycleInfo.extendCycle(m_iface, extendCycle, extendBlock, &extendedBlocks);
+
+    // Update an operation that should now be considered to be part of the
+    // given extended cycle.
+    auto updateOperation = [this](ConvergentOperation *op,
+                                  GenericCycleBase *extendCycle) {
+      if (extendCycle == op->m_cycle)
+        return;
+
+      if (m_cycleInfo.contains(op->m_cycle, extendCycle)) {
+        // Handle a case such as the following, where the operation was
+        // assigned to an ancestor of extendCycle:
+        //
+        //    |
+        //    A]      <-- extendCycle
+        //    |
+        //    B       <-- op
+        //    |
+        //    C       <-- extendBlock
+        //    |
+        //
+        // Due to the nesting rule for convergence regions, this can
+        // only happen when `op` itself is anchored in B, which means that
+        // it cannot be a true heart.
+        assert(op->getKind() != ConvergentOperation::Heart);
+        op->m_cycle = extendCycle;
+
+        SmallVector<ConvergentOperation *, 16> stack;
+        for (;;) {
+          for (ConvergentOperation *child : op->m_children) {
+            if (child->getKind() == ConvergentOperation::Heart)
+              continue;
+            if (child->m_cycle == extendCycle)
+              continue; // already updated?
+
+            child->m_cycle = extendCycle;
+            if (!child->m_children.empty())
+              stack.push_back(child);
+
+            CfgBlockRef block = child->m_block;
+            if (!extendCycle->containsBlock(block))
+              m_pendingExtensions.emplace_back(block, extendCycle);
+          }
+
+          if (stack.empty())
+            break;
+          op = stack.pop_back_val();
+        }
+      } else {
+        // The cycle with which this operation is associated must now be
+        // a descendant of the extended cycle, due to the nesting rule for
+        // convergence regions.
+        assert(m_cycleInfo.contains(extendCycle, op->m_cycle));
+      }
+    };
+
+    if (!llvm::is_contained(extendedBlocks, extendBlock)) {
+      auto blockIt = m_convergenceInfo.m_block.find(extendBlock);
+      if (blockIt != m_convergenceInfo.m_block.end()) {
+        GenericCycleBase *cycle = nullptr;
+        for (ConvergentOperation *op :
+             llvm::reverse(m_convergenceInfo.m_block[extendBlock].operations)) {
+          if (cycle)
+            updateOperation(op, cycle);
+          cycle = op->m_cycle;
+        }
+      }
+    }
+
+    for (CfgBlockRef block : extendedBlocks) {
+      auto blockIt = m_convergenceInfo.m_block.find(block);
+      if (blockIt == m_convergenceInfo.m_block.end())
+        continue;
+
+      for (ConvergentOperation *op : blockIt->second.operations)
+        updateOperation(op, extendCycle);
+    }
+    extendedBlocks.clear();
+  }
+
+  // Step 3: Register hearts within their final relevant cycles.
+  for (ConvergentOperation *heart : m_hearts)
+    m_convergenceInfo.registerHeart(heart);
+
+  assert(m_convergenceInfo.validate(m_cycleInfo));
+}
+
+/// \brief Callback for \ref visitConvergentOperations
+///
+/// Record the encountered operation in the tree, in the m_operations map,
+/// and in the per-block list.
+///
+/// Also record the
+void GenericConvergenceAnalysisBase::visitConvergentOperation(
+    ConvergentOperation *parent, ConvergentOperation::Kind kind,
+    CfgBlockRef block, CfgInstructionRef instruction) {
+  assert((kind == ConvergentOperation::Anchor ||
+          kind == ConvergentOperation::Entry ||
+          kind == ConvergentOperation::Uncontrolled) == !parent);
+
+  auto op =
+      std::make_unique<ConvergentOperation>(parent, kind, block, instruction);
+
+  if (parent) {
+    parent->m_children.push_back(op.get());
+  } else {
+    m_convergenceInfo.m_roots.push_back(op.get());
+  }
+
+  op->m_cycle = m_cycleInfo.getCycle(block);
+
+  if (parent) {
+    GenericCycleBase *parentCycle = parent->m_cycle;
+    bool isTrueHeart = false;
+
+    if (parentCycle != op->m_cycle) {
+      if (m_cycleInfo.contains(parentCycle, op->m_cycle)) {
+        // Static validation rule: every cycle that contains a non-heart use of
+        // a token must also contain its definition -- so a valid program can
+        // only have a heart here, and it can't have more than one in this
+        // cycle.
+        assert(kind == ConvergentOperation::Heart);
+        isTrueHeart = true;
+      } else {
+        // Cycle extensions may be required for hearts. Example:
+        //
+        //    |
+        //    A]     %outer = loop heart            <-- parent
+        //    |
+        //    B]     %inner = loop heart (%outer)   <-- op
+        //    |
+        //
+        // In this case, parentCycle is the cycle headed by A, and we are going
+        // to extend it to include the entire cycle headed by B, but we don't
+        // update op->m_cycle.
+        if (kind == ConvergentOperation::Heart) {
+          isTrueHeart = !m_cycleInfo.contains(op->m_cycle, parentCycle);
+          if (!isTrueHeart)
+            op->m_kind = kind = ConvergentOperation::Copy;
+        }
+
+        if (kind != ConvergentOperation::Heart)
+          op->m_cycle = parentCycle;
+
+        m_pendingExtensions.emplace_back(block, parentCycle);
+      }
+    }
+
+    if (kind == ConvergentOperation::Heart) {
+      if (isTrueHeart) {
+        m_hearts.push_back(op.get());
+      } else {
+        op->m_kind = ConvergentOperation::Copy;
+      }
+    }
+  }
+
+  m_convergenceInfo.m_block[block].operations.push_back(op.get());
+
+  assert(!m_convergenceInfo.m_operation.count(instruction));
+  m_convergenceInfo.m_operation[instruction] = std::move(op);
+}

llvm/lib/Analysis/GenericConvergenceUtils.cpp

+//===- GenericConvergenceUtils.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/GenericConvergenceUtils.h"
+
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/Support/GenericDomTree.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+/// \brief Clear all information / reset this structure to the original state
+void GenericConvergenceInfoBase::clear() {
+  m_block.clear();
+  m_heart.clear();
+  m_operation.clear();
+}
+
+/// \brief Return the given cycle's heart block, or null if it has none.
+CfgBlockRef
+GenericConvergenceInfoBase::getHeartBlock(const GenericCycleBase *cycle) const {
+  auto heartIt = m_heart.find(cycle);
+  if (heartIt != m_heart.end())
+    return heartIt->second->getBlock();
+  return {};
+}
+
+/// \brief Return the metadata for the given intrinsic.
+GenericConvergentOperationBase *
+GenericConvergenceInfoBase::getOperation(CfgInstructionRef instruction) {
+  auto it = m_operation.find(instruction);
+  if (it == m_operation.end())
+    return nullptr;
+  return it->second.get();
+}
+
+/// \brief Perform some sanity-checks on the convergence info.
+///
+/// This validation is not exhaustive. For example, it does not check that
+/// independently anchored trees of intrinsics are well-nested.
+bool GenericConvergenceInfoBase::validate(
+    const GenericCycleInfoBase &cycleInfo) const {
+  DenseSet<ConvergentOperation *> allOps;
+  DenseSet<ConvergentOperation *> seen;
+
+  auto reportError = [](const char *file, int line, const char *cond) {
+    errs() << file << ':' << line
+           << ": GenericConvergenceInfo::validate: " << cond << '\n';
+  };
+#define check(cond) do { \
+    if (!(cond)) { \
+      reportError(__FILE__, __LINE__, #cond); \
+      return false; \
+    } \
+  } while (false)
+
+  check(cycleInfo.validateTree());
+
+  for (const auto &op : m_operation) {
+    check(op.first == op.second->m_instruction);
+    check(allOps.insert(op.second.get()).second);
+  }
+
+  for (ConvergentOperation *op : allOps) {
+    bool parentExpected = op->getKind() == ConvergentOperation::Heart ||
+                          op->getKind() == ConvergentOperation::Copy ||
+                          op->getKind() == ConvergentOperation::User;
+    check((op->getParent() != nullptr) == parentExpected);
+    check(!op->getParent() || allOps.count(op->getParent()));
+    check(op->getParent() || llvm::is_contained(m_roots, op));
+
+    for (ConvergentOperation *child : op->children()) {
+      check(allOps.count(child));
+      check(child->getParent() == op);
+      check(seen.insert(child).second); // duplicate child listing?
+    }
+    seen.clear();
+
+    if (op->getParent()) {
+      bool isSameCycle = op->getParent()->getCycle() == op->getCycle();
+      bool expectSameCycle = op->getKind() != ConvergentOperation::Heart;
+      check(isSameCycle == expectSameCycle);
+      check(cycleInfo.contains(op->getParent()->getCycle(), op->getCycle()));
+    }
+
+    auto blockIt = m_block.find(op->getBlock());
+    check(blockIt != m_block.end() &&
+          llvm::is_contained(blockIt->second.operations, op));
+
+    if (op->getKind() == ConvergentOperation::Heart) {
+      for (const GenericCycleBase *cycle = op->m_cycle;
+           cycle != op->m_parent->m_cycle; cycle = cycle->getParent()) {
+        auto heartIt = m_heart.find(cycle);
+        check(heartIt != m_heart.end() && heartIt->second == op);
+      }
+    }
+  }
+
+  for (const auto &block : m_block) {
+    check(!block.second.operations.empty()); // unnecessary allocation?
+
+    const GenericCycleBase *cycle = nullptr;
+
+    for (ConvergentOperation *op : block.second.operations) {
+      check(allOps.count(op));
+      check(op->getBlock() == block.first);
+      check(seen.insert(op).second); // duplicate listing in block?
+
+      check(!cycle || cycleInfo.contains(op->m_cycle, cycle));
+      cycle = op->m_cycle;
+    }
+    seen.clear();
+
+    check(cycleInfo.contains(cycleInfo.getCycle(block.first), cycle));
+  }
+
+  for (const auto &heart : m_heart) {
+    check(allOps.count(heart.second));
+    check(heart.second->getKind() == ConvergentOperation::Heart);
+    check(cycleInfo.contains(heart.first, heart.second->m_cycle));
+  }
+
+  for (ConvergentOperation *root : m_roots) {
+    check(allOps.count(root));
+    check(!root->getParent());
+    check(seen.insert(root).second); // duplicate listing of a root?
+  }
+  seen.clear();
+
+#undef check
+
+  return true;
+}
+
+/// \brief Print convergence info to \p out.
+void GenericConvergenceInfoBase::print(const CfgPrinter &printer,
+                                       const GenericCycleInfoBase &cycleInfo,
+                                       raw_ostream &out) const {
+  out << "Convergence-adjusted cycles:\n";
+  cycleInfo.print(printer, out);
+
+  out << "Convergent operations:\n";
+
+  SmallVector<std::pair<const ConvergentOperation *, uint>, 8> stack;
+  for (ConvergentOperation *root : llvm::reverse(m_roots))
+    stack.emplace_back(root, 1);
+
+  while (!stack.empty()) {
+    auto current = stack.pop_back_val();
+
+    for (unsigned i = 0; i < current.second; ++i)
+      out << "  ";
+
+    switch (current.first->getKind()) {
+    case ConvergentOperation::Entry:
+      out << "(entry) ";
+      break;
+    case ConvergentOperation::Anchor:
+      out << "(anchor) ";
+      break;
+    case ConvergentOperation::Heart:
+      out << "(heart) ";
+      break;
+    case ConvergentOperation::Copy:
+      out << "(copy) ";
+      break;
+    case ConvergentOperation::User:
+      out << "(user) ";
+      break;
+    case ConvergentOperation::Uncontrolled:
+      out << "(uncontrolled) ";
+      break;
+    }
+
+    printer.printBlockName(out, current.first->getBlock());
+    const GenericCycleBase *cycle = current.first->getCycle();
+    if (!cycle->isRoot()) {
+      out << " (cycle=" << current.first->getCycle()->print(printer) << ')';
+    }
+    out << ": ";
+    printer.printInstruction(out, current.first->m_instruction);
+    out << '\n';
+
+    for (const ConvergentOperation *child :
+         llvm::reverse(current.first->children()))
+      stack.emplace_back(child, current.second + 1);
+  }
+}
+
+/// Insert a new convergent operation into the convergence info.
+///
+/// Call this after creating a new operation to preserve the analysis result.
+GenericConvergentOperationBase *GenericConvergenceInfoBase::insertOperation(
+    const CfgInterface &iface, GenericCycleInfoBase &cycleInfo,
+    ConvergentOperation *parent, ConvergentOperation::Kind kind,
+    CfgBlockRef block, CfgInstructionRef instruction) {
+  ConvergenceBlockInfo &blockInfo = m_block[block];
+
+  auto insertIt = llvm::lower_bound(
+      blockInfo.operations, instruction,
+      [&iface](ConvergentOperation *lhs, CfgInstructionRef rhs) {
+        return iface.comesBefore(lhs->getInstruction(), rhs);
+      });
+
+  auto op =
+      std::make_unique<ConvergentOperation>(parent, kind, block, instruction);
+  ConvergentOperation *retOp = op.get();
+
+  if (parent) {
+    if (kind != ConvergentOperation::Heart) {
+      op->m_cycle = parent->m_cycle;
+    } else {
+      op->m_cycle = cycleInfo.getCycle(block);
+
+      registerHeart(op.get());
+    }
+
+    // This assertion triggers if the operation is either entirely misplaced
+    // or requires a cycle extension -- preserving the convergence analysis in
+    // the latter case is unlikely to ever be required and hasn't been
+    // implemented.
+    assert(op->m_cycle == cycleInfo.getCycle(block) ||
+           (insertIt != blockInfo.operations.end() &&
+            cycleInfo.contains(op->m_cycle, (*insertIt)->m_cycle)));
+
+    parent->m_children.push_back(op.get());
+  } else {
+    if (insertIt != blockInfo.operations.end())
+      op->m_cycle = (*insertIt)->m_cycle;
+    else
+      op->m_cycle = cycleInfo.getCycle(block);
+
+    m_roots.push_back(op.get());
+  }
+
+  blockInfo.operations.insert(insertIt, op.get());
+
+  assert(!m_operation.count(instruction));
+  m_operation.try_emplace(instruction, std::move(op));
+
+  assert(validate(cycleInfo));
+
+  return retOp;
+}
+
+/// Erase the given operation from the convergence info.
+void GenericConvergenceInfoBase::eraseOperation(GenericCycleInfoBase &cycleInfo,
+                                                ConvergentOperation *op) {
+  assert(op->m_children.empty() &&
+         "children must be erased before their parents");
+
+  auto blockIt = m_block.find(op->getBlock());
+  assert(blockIt != m_block.end());
+
+  auto opIt = llvm::find(blockIt->second.operations, op);
+  assert(opIt != blockIt->second.operations.end());
+
+  // This assertion triggers if erasing this operation causes a cycle extension
+  // to collapse -- handling this case would be required e.g. if we wanted to
+  // preserve convergence analysis during dead-code elimination.
+  //
+  // Note that this assertion doesn't capture all cases of collapsing cycle
+  // extensions. Consider:
+  //
+  //    |
+  //    A]      %a = loop heart
+  //    |
+  //    B]      %b = loop heart (%a)
+  //    |
+  //
+  // The loop heart %b causes an extension of cycle headed by A to fully
+  // include B, and removing %b causes that extension to collapse (unless some
+  // other use of %a keeps it alive). However, this case is difficult to
+  // detect, and does not trigger this assertion.
+  assert(cycleInfo.getCycle(op->getBlock()) == op->m_cycle ||
+         (opIt != blockIt->second.operations.begin() &&
+          cycleInfo.contains(op->m_cycle, (*(opIt - 1))->m_cycle)) ||
+         (opIt + 1 != blockIt->second.operations.end() &&
+          cycleInfo.contains(op->m_cycle, (*(opIt + 1))->m_cycle)));
+
+  blockIt->second.operations.erase(opIt);
+
+  if (blockIt->second.operations.empty())
+    m_block.erase(blockIt);
+
+  if (op->m_parent) {
+    op->m_parent->m_children.erase(llvm::find(op->m_parent->m_children, op));
+  } else {
+    m_roots.erase(llvm::find(m_roots, op));
+  }
+
+  if (op->getKind() == ConvergentOperation::Heart)
+    unregisterHeart(op);
+
+  // Delete the operation.
+  assert(m_operation[op->m_instruction].get() == op);
+  m_operation.erase(op->m_instruction);
+
+  assert(validate(cycleInfo));
+}
+
+/// Helper that adds \p heart to m_heart for all relevant cycles.
+void GenericConvergenceInfoBase::registerHeart(ConvergentOperation *heart) {
+  assert(heart->getKind() == ConvergentOperation::Heart);
+  for (GenericCycleBase *cycle = heart->m_cycle;
+       cycle != heart->m_parent->m_cycle; cycle = cycle->getParent()) {
+    assert(!m_heart.count(cycle));
+    m_heart.try_emplace(cycle, heart);
+  }
+}
+
+/// Helper that removes \p heart from m_heart for all relevant cycles.
+void GenericConvergenceInfoBase::unregisterHeart(ConvergentOperation *heart) {
+  assert(heart->getKind() == ConvergentOperation::Heart);
+  for (GenericCycleBase *cycle = heart->m_cycle;
+       cycle != heart->m_parent->m_cycle; cycle = cycle->getParent()) {
+    assert(m_heart[cycle] == heart);
+    m_heart.erase(cycle);
+  }
+}
+
+/// \brief Generically compute the heart-adjusted post order.
+void HeartAdjustedPostOrderBase::compute(
+    const CfgInterface &iface,
+    const GenericConvergenceInfoBase &convergenceInfo,
+    const GenericCycleInfoBase &cycleInfo,
+    const GenericDominatorTreeBase &domTree) {
+  // In our forward traversal, the modification bullets from the description of
+  // heart-adjusted reverse post order happen in reverse: within each
+  // cycle, we do a depth-first post-order traversal of only the blocks
+  // belonging to the cycle, starting with the heart.
+  //
+  // The depth-first search mainly uses a stack of blocks, with a look-aside
+  // stack of cycles. Cycles remain on the stack until their final post-order
+  // visit, at which time their blocks are added to the parent cycle's order.
+  // We also maintain a linked list of cycles that are active in the sense that
+  // we're currently visiting blocks inside them.
+  struct Cycle {
+    const GenericCycleBase *cycle;
+    CfgBlockRef heart;
+    unsigned parentStackIdx;
+    std::vector<CfgBlockRef> order;
+    SmallVector<CfgBlockRef, 4> postponedBlocks;
+
+    explicit Cycle(const GenericCycleBase *cycle, CfgBlockRef heart,
+                   unsigned parentStackIdx)
+        : cycle(cycle), heart(heart), parentStackIdx(parentStackIdx) {}
+  };
+
+  DenseSet<CfgBlockRef> visitedBlocks;
+  SmallVector<CfgBlockRef, 32> blockStack;
+  // doneIdxStack contains ((size of blockStack before pop) << 1) | isCycleHeart
+  SmallVector<unsigned, 32> doneIdxStack;
+  SmallVector<Cycle, 8> cycleStack;
+  unsigned currentCycleStackIdx = 0;
+
+  CfgBlockRef entryBlock = domTree.getRootNode()->getBlock();
+  cycleStack.emplace_back(cycleInfo.getRoot(), CfgBlockRef{}, 0);
+  blockStack.push_back(entryBlock);
+
+  // The entry block is not marked as a cycle header, so that we don't attempt
+  // to pop the root cycle: it is handled at the very end after the loop.
+  doneIdxStack.push_back(blockStack.size() << 1);
+  iface.appendSuccessors(entryBlock, blockStack);
+
+  do {
+    CfgBlockRef block = blockStack.back();
+    unsigned doneBack = doneIdxStack.back();
+
+    if (blockStack.size() == (doneBack >> 1)) {
+      if (!(doneBack & 1)) {
+        // Post-order visit of a regular block.
+        cycleStack[currentCycleStackIdx].order.push_back(block);
+        blockStack.pop_back();
+        doneIdxStack.pop_back();
+        continue;
+      }
+
+      // This is the post-order visit of an effective cycle heart.
+      Cycle &cycle = cycleStack.back();
+      if (currentCycleStackIdx == cycleStack.size() - 1)
+        currentCycleStackIdx = cycle.parentStackIdx;
+
+      if (!cycle.postponedBlocks.empty()) {
+        // Enqueue the cycle's postponed exit blocks if there are any. In this
+        // case, we aren't actually at the post-order visit of the cycle yet,
+        // if we interpret it as a contracted node contained in its parent.
+        for (CfgBlockRef postponed : cycle.postponedBlocks) {
+          assert(visitedBlocks.count(postponed));
+          visitedBlocks.erase(postponed);
+          blockStack.push_back(postponed);
+        }
+        cycle.postponedBlocks.clear();
+        continue;
+      }
+
+      // True post-order visit: collect all of the cycle.
+      cycle.order.push_back(block);
+      blockStack.pop_back();
+      doneIdxStack.pop_back();
+
+      auto &parentOrder = cycleStack[cycle.parentStackIdx].order;
+      parentOrder.insert(parentOrder.end(), cycle.order.begin(),
+                         cycle.order.end());
+      cycleStack.pop_back();
+      continue;
+    }
+
+    if (!visitedBlocks.insert(block).second) {
+      blockStack.pop_back();
+      continue; // already visited this one
+    }
+
+    // Pre-order visit of the block.
+    const GenericCycleBase *currentCycle =
+        cycleStack[currentCycleStackIdx].cycle;
+    CfgBlockRef currentHeart = cycleStack[currentCycleStackIdx].heart;
+    const GenericCycleBase *blockCycle = cycleInfo.getCycle(block);
+
+    if (blockCycle == currentCycle ||
+        (currentHeart &&
+         currentHeart == convergenceInfo.getHeartBlock(blockCycle))) {
+      doneIdxStack.push_back(blockStack.size() << 1);
+      iface.appendSuccessors(block, blockStack);
+      continue;
+    }
+
+    if (cycleInfo.contains(currentCycle, blockCycle)) {
+      // Entering a child cycle. In the case of irreducible control flow,
+      // blockCycle might not be a direct child -- find it.
+      while ((blockCycle->getParent() != currentCycle) &&
+             (!currentHeart || currentHeart != convergenceInfo.getHeartBlock(
+                                                   blockCycle->getParent())))
+        blockCycle = blockCycle->getParent();
+
+      CfgBlockRef heart = convergenceInfo.getHeartBlock(blockCycle);
+      CfgBlockRef effectiveHeart = heart ? heart : blockCycle->getHeader();
+
+      cycleStack.emplace_back(blockCycle, heart, currentCycleStackIdx);
+      currentCycleStackIdx = cycleStack.size() - 1;
+
+      // Fixup state as-if we're visiting the effective heart.
+      if (block != effectiveHeart) {
+        blockStack.pop_back();
+        blockStack.push_back(effectiveHeart);
+        visitedBlocks.erase(block);
+        visitedBlocks.insert(effectiveHeart);
+      }
+
+      doneIdxStack.push_back((blockStack.size() << 1) | 1);
+      iface.appendSuccessors(block, blockStack);
+      continue;
+    }
+
+    // This block is not contained in the current cycle; we have to postpone it.
+    blockStack.pop_back();
+
+    Cycle *postponeCycle = &cycleStack[currentCycleStackIdx];
+    for (;;) {
+      Cycle *parent = &cycleStack[postponeCycle->parentStackIdx];
+      if (cycleInfo.contains(parent->cycle, blockCycle))
+        break;
+      postponeCycle = parent;
+    }
+    postponeCycle->postponedBlocks.push_back(block);
+  } while (!blockStack.empty());
+
+  assert(cycleStack.size() == 1);
+  m_order = std::move(cycleStack[0].order);
+}

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/ConvergenceUtils.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"

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("convergenceinfo", ConvergenceInfoAnalysis())
 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_PASS("loop-distribute", LoopDistributePass())
 FUNCTION_PASS("loop-versioning", LoopVersioningPass())
 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<convergenceinfo>", ConvergenceInfoPrinterPass(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<func-properties>", FunctionPropertiesPrinterPass(dbgs()))
 FUNCTION_PASS("print<inline-cost>", InlineCostAnnotationPrinterPass(dbgs()))
 FUNCTION_PASS("print<inliner-size-estimator>", 

llvm/test/Analysis/ConvergenceInfo/basic.ll

+; RUN: opt < %s -convergenceinfo -analyze | FileCheck %s -check-prefix=CHECK
+; RUN: opt < %s -disable-output -passes='print<convergenceinfo>' 2>&1 | FileCheck %s -check-prefix=CHECK
+
+define void @empty() {
+; CHECK-LABEL: ConvergenceInfo for function: empty
+; CHECK-NEXT:  Convergence-adjusted cycles:
+; CHECK-NEXT:  Convergent operations:
+
+  ret void
+}
+
+define void @simple() {
+; CHECK-LABEL: ConvergenceInfo for function: simple
+; CHECK: Convergence-adjusted cycles:
+; CHECK: Convergent operations:
+; CHECK:  (entry) entry:   %tok0 = call token @llvm.experimental.convergence.entry()
+; CHECK:    (user) entry:   call void @convergent.op(i32 0) [ "convergencectrl"(token %tok0) ]
+; CHECK:    (user) then:   call void @convergent.op(i32 1) [ "convergencectrl"(token %tok0) ]
+; CHECK:  (anchor) then:   %tok1 = call token @llvm.experimental.convergence.anchor()
+; CHECK:    (user) then:   call void @convergent.op(i32 2) [ "convergencectrl"(token %tok1) ]
+
+entry:
+  %tok0 = call token @llvm.experimental.convergence.entry()
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %tok0) ]
+  br i1 undef, label %then, label %end
+
+then:
+  call void @convergent.op(i32 1) [ "convergencectrl"(token %tok0) ]
+
+  %tok1 = call token @llvm.experimental.convergence.anchor()
+  call void @convergent.op(i32 2) [ "convergencectrl"(token %tok1) ]
+  br label %end
+
+end:
+  ret void
+}
+
+define void @loops() {
+; CHECK-LABEL: ConvergenceInfo for function: loops
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(outer_hdr) inner_hdr inner_next
+; CHECK:         depth=2: entries(inner_hdr) inner_next
+; CHECK: Convergent operations:
+; CHECK:   (anchor) entry:   %anchor = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (heart) outer_hdr (cycle=depth=1: entries(outer_hdr) inner_hdr inner_next):   %outer = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+; CHECK:       (heart) inner_hdr (cycle=depth=2: entries(inner_hdr) inner_next):   %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
+; CHECK:         (user) inner_hdr (cycle=depth=2: entries(inner_hdr) inner_next):   call void @convergent.op(i32 0) [ "convergencectrl"(token %inner) ]
+
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %outer_hdr
+
+outer_hdr:
+  %outer = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br label %inner_hdr
+
+inner_hdr:
+  %inner = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %outer) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %inner) ]
+  br i1 undef, label %outer_hdr, label %inner_next
+
+inner_next:
+  br i1 undef, label %inner_hdr, label %end
+
+end:
+  ret void
+}
+
+;
+;     |
+;     A]       %a = anchor
+;     |
+;     B
+;     |\
+;     | C
+;     |/ \
+;     D  |
+;        E     %e = user (%a)
+;
+define void @extend_loops() {
+; CHECK-LABEL: ConvergenceInfo for function: extend_loops
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A) C B
+; CHECK: Convergent operations:
+; CHECK:   (anchor) A (cycle=depth=1: entries(A) C B):   %a = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) E (cycle=depth=1: entries(A) C B):   call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+
+entry:
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+B:
+  br i1 undef, label %C, label %D
+
+C:
+  br i1 undef, label %D, label %E
+
+D:
+  ret void
+
+E:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+;
+;     |
+;     A]       %a = anchor
+;     |
+;     B        %b = anchor
+;    / \
+;   C   \
+;  / \  |
+; D   | |
+;     E |      %e = user (%b)
+;       |
+;       F      %f = user (%a)
+;
+define void @extend_loops_iterate() {
+; CHECK-LABEL: ConvergenceInfo for function: extend_loops_iterate
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A) B C
+; CHECK: Convergent operations:
+; CHECK:   (anchor) A (cycle=depth=1: entries(A) B C):   %a = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) F (cycle=depth=1: entries(A) B C):   call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+; CHECK:   (anchor) B (cycle=depth=1: entries(A) B C):   %b = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) E (cycle=depth=1: entries(A) B C):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+
+entry:
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+B:
+  %b = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %C, label %F
+
+C:
+  br i1 undef, label %D, label %E
+
+D:
+  ret void
+
+E:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+  ret void
+
+F:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+;
+;     |
+;     A<-\     %a = heart
+;     |  |
+;     B] |     %b = heart (%a)
+;     |  |
+;     C>-/
+;     |
+;     D        %d1 = user (%b)
+;              %d2 = user (%a)
+;
+define void @nested_loop_extension() {
+; CHECK-LABEL: ConvergenceInfo for function: nested_loop_extension
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A) C B
+; CHECK:         depth=2: entries(B) C
+; CHECK: Convergent operations:
+; CHECK:   (anchor) entry:   %anchor = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (heart) A (cycle=depth=1: entries(A) C B):   %a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+; CHECK:       (heart) B (cycle=depth=2: entries(B) C):   %b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+; CHECK:         (user) D (cycle=depth=2: entries(B) C):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+; CHECK:       (user) D (cycle=depth=1: entries(A) C B):   call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br label %B
+
+B:
+  %b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+  br i1 undef, label %B, label %C
+
+C:
+  br i1 undef, label %A,label %D
+
+D:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+;
+;    |
+;    A]      %a = anchor
+;    |
+;    B       %b1 = anchor       <-- should be associated to extended cycle!
+;    |\      %b2 = user (%b1)
+;    | X
+;    C       %c = user (%a)
+;
+define void @multi_block_extension() {
+; CHECK-LABEL: ConvergenceInfo for function: multi_block_extension
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A) B
+; CHECK: Convergent operations:
+; CHECK:   (anchor) A (cycle=depth=1: entries(A) B):   %a = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) C (cycle=depth=1: entries(A) B):   call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+; CHECK:   (anchor) B (cycle=depth=1: entries(A) B):   %b1 = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) B (cycle=depth=1: entries(A) B):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+
+entry:
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+B:
+  %b1 = call token @llvm.experimental.convergence.anchor()
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+  br i1 undef, label %X, label %C
+
+X:
+  ret void
+
+C:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+;
+;    |
+;    A]      %a = anchor
+;    |
+;    B       %b1 = anchor       <-- should be associated to extended cycle!
+;            %b2 = user (%b1)
+;            %b3 = user (%a)
+;
+define void @multi_extension() {
+; CHECK-LABEL: ConvergenceInfo for function: multi_extension
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A)
+; CHECK: Convergent operations:
+; CHECK:   (anchor) A (cycle=depth=1: entries(A)):   %a = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) B (cycle=depth=1: entries(A)):   call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+; CHECK:   (anchor) B (cycle=depth=1: entries(A)):   %b1 = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (user) B (cycle=depth=1: entries(A)):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+
+entry:
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+B:
+  %b1 = call token @llvm.experimental.convergence.anchor()
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+;
+;    |
+;    A]     %a = anchor
+;    |
+;    B]     %b1 = loop heart (%a)
+;    |      %b2 = user (%b1)
+;    |
+;    C
+;
+define void @lift_loop() {
+; CHECK-LABEL: ConvergenceInfo for function: lift_loop
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A) B
+; CHECK:         depth=2: entries(B)
+; CHECK: Convergent operations:
+; CHECK:   (anchor) A (cycle=depth=1: entries(A) B):   %a = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (heart) B (cycle=depth=2: entries(B)):   %b1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+; CHECK:       (user) B (cycle=depth=2: entries(B)):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+
+entry:
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+B:
+  %b1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+  br i1 undef, label %B, label %C
+
+C:
+  ret void
+}
+
+define void @false_heart_trivial() {
+; CHECK-LABEL: ConvergenceInfo for function: false_heart_trivial
+; CHECK: Convergence-adjusted cycles:
+; CHECK: Convergent operations:
+; CHECK:   (entry) entry:   %a = call token @llvm.experimental.convergence.entry()
+; CHECK:     (copy) entry:   %b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+; CHECK:       (user) entry:   call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+entry:
+  %a = call token @llvm.experimental.convergence.entry()
+  %b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b) ]
+  ret void
+}
+
+;
+;    |
+;    A]     %a = loop heart
+;    |
+;    B      %b1 = false heart (%a)
+;           %b2 = user (%b1)
+;
+define void @false_heart_lifted() {
+; CHECK-LABEL: ConvergenceInfo for function: false_heart_lifted
+; CHECK: Convergence-adjusted cycles:
+; CHECK:     depth=1: entries(A)
+; CHECK: Convergent operations:
+; CHECK:   (anchor) entry:   %anchor = call token @llvm.experimental.convergence.anchor()
+; CHECK:     (heart) A (cycle=depth=1: entries(A)):   %a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+; CHECK:       (copy) B (cycle=depth=1: entries(A)):   %b1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+; CHECK:         (user) B (cycle=depth=1: entries(A)):   call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %A
+
+A:
+  %a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br i1 undef, label %A, label %B
+
+B:
+  %b1 = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %a) ]
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %b1) ]
+  ret void
+}
+
+declare void @convergent.op(i32) convergent
+
+declare token @llvm.experimental.convergence.entry()
+declare token @llvm.experimental.convergence.anchor()
+declare token @llvm.experimental.convergence.loop()