Transforms: add ConvergenceControlHeuristic pass

[nhaehnle]

Summary

This pass turns uncontrolled convergent operations into controlled ones
by adding appropriate "convergencectrl" bundles and inserting
convergence control intrinsics.

When this pass is used immediately after generating LLVM IR, it will in
many cases establish convergence control that enforces the semantics
that a programmer would likely expect based on the high-level language
source. However, there are exceptions.

This pass is not intended to be used by default. Frontends that care
about semantics of convergent operations should really emit convergence
control information directly, but this pass can serve as a convenient
stop-gap.

Change-Id: I1c72b53567cb4e8b9b82f31f9c8525f2622cd242

[arsenm]

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

76–77

Don't need intermediate changed variable

116

Why do you need to recreate it? Can't you just directly add the bundle / mutate the instructon? That would also make invoke support free?

126

Can you also add a test with an asm call

[nhaehnle]

• add an inline assembly test
• simplification suggest by a review comment

[nhaehnle]

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

116

Is that possible? There isn't really any infrastructure for adding or removing operands on a User, and with the way that they're allocated it would seem to be a rather invasive change to allow that.

126

Can you also add a test with an asm call

Done.

[Anastasia]

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

15

Can I clarify what do you mean by refer here?

I presume if you only have IR with uncontrolled convergent operation there wouldn't be any tokens to find? Although perhaps this could apply if one has been inserted for another uncontrolled operation previously?

17

Right now Clang decorates all function by convergent regardless whether or not they have convergent operations so it seems that if we are to generalize to the new behavior we could just append an entry intrinsic to the entry basic block everywhere?

18

I would quite like to get an example of HL code that needs an anchor. I am not very clear where it fits at the moment.

20

Ok, in the frontend we might have very limited information about the full CF structure while parsing.

Although we could also think of some combined approaches where frontend generates partial information and then the pass completes the rest...

[nhaehnle]

Hi @Anastasia, thank you for your comments. I replied inline, but a high-level point upfront is that in many ways, this patch only exists because HLL don't really have well-defined semantics for convergent operations yet. Most of us have a shared mental model of what they should be for most high-level constructs, but intuition breaks down for the trickier corner cases. I made some proposals in the Khronos Memory Model TSG for how useful semantics could be added to HLL, taking the corner cases into account, but on my end all of this is on hold while I'm on leave.

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

15

Yes, that's correct.

17

Yes.

18

It depends on the relevant definitions of the HL languages, which don't exist yet.

If you were to translate an algorithm from CUDA, you'd basically use an anchor wherever __activemask() is used.

An example of a piece of code that would leverage it is at https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v9-pre/llvm/docs/ConvergentOperations.rst#opportunistic-convergent-operations (the @reserveSpaceInBuffer example) -- it's not in a HLL, but again, that's because HLL don't really offer these controls yet as inherent language features.

20

If this is in response to the irreducible cycles, keep in mind that you can only really get those with goto in modern languages (or possibly after some transforms have already happened).

I don't know much about Clang in particular, but fong-term, for HLL that have well-defined expected semantics of convergent operations, I expect that it would always be preferable to emit the convergence control information as part of the frontend IR generation.

[Anastasia]

In D85609#2685844, @nhaehnle wrote:

Hi @Anastasia, thank you for your comments. I replied inline, but a high-level point upfront is that in many ways, this patch only exists because HLL don't really have well-defined semantics for convergent operations yet. Most of us have a shared mental model of what they should be for most high-level constructs, but intuition breaks down for the trickier corner cases. I made some proposals in the Khronos Memory Model TSG for how useful semantics could be added to HLL, taking the corner cases into account, but on my end all of this is on hold while I'm on leave.

Great! I will try to find more details there.

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

18

I see, potentially some of the new extended subgroup functions in OpenCL could be using that intrinsics for example sub_group_ballot.
https://www.khronos.org/registry/OpenCL/specs/3.0-unified/html/OpenCL_Ext.html#_extended_subgroup_functions

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 initializeConvergenceControlHeuristicLegacyPassPass(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&);

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_component_library(LLVMTransformUtils
   CallPromotionUtils.cpp
   CallGraphUpdater.cpp
   CanonicalizeAliases.cpp
   CanonicalizeFreezeInLoops.cpp
   CloneFunction.cpp
   CloneModule.cpp
   CodeExtractor.cpp
   CodeMoverUtils.cpp
+  ConvergenceControlHeuristic.cpp
   CtorUtils.cpp
   Debugify.cpp
   DemoteRegToStack.cpp
   EntryExitInstrumenter.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp
   FixIrreducible.cpp
   FlattenCFG.cpp

llvm/lib/Transforms/Utils/ConvergenceControlHeuristic.cpp

+//===- ConvergenceControlHeuristic.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
+//
+//===----------------------------------------------------------------------===//
+//
+/// \brief Heuristic insertion of convergence control tokens
+///
+/// This pass converts uncontrolled convergent operations to controlled ones
+/// by inserting entry, anchor and loop intrinsics as well as operand bundles
+/// according to the following heuristics:
+///
+///  1. In acyclic code, refer to the nearest dominating convergence token if
+///     one exists.
+///  2. Otherwise, refer to an `entry` intrinsic if the containing function
+///     is convergent, and to an `anchor` intrinsic otherwise.
+///  3. In natural loops, refer to a `loop` heart intrinsic in the loop header.
+///  4. In irreducible cycles, place a heart intrinsic in one of the maximal
+///     dominating blocks inside the cycle, and anchor intrinsics in any others.
+///
+/// These heuristics will often succeed at inserting convergence control tokens
+/// in a way that reflects the intention of a programmer writing high-level
+/// language code -- but there are exceptions. Frontends should prefer to
+/// insert the tokens directly based on additional information that is
+/// available in the HLL source.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/ConvergenceUtils.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "convergence-control-heuristic"
+
+namespace {
+
+class ConvergenceControlHeuristic {
+  Function &m_function;
+  DominatorTree &m_domTree;
+  ConvergenceInfo &m_convergenceInfo;
+
+public:
+  ConvergenceControlHeuristic(Function &function, DominatorTree &domTree,
+                              ConvergenceInfo &convergenceInfo)
+      : m_function(function), m_domTree(domTree),
+        m_convergenceInfo(convergenceInfo) {}
+
+  bool run();
+
+private:
+  ConvergentOperation *findOrInsertToken(BasicBlock *block,
+                                         ConvergentOperation *op,
+                                         const Cycle *cycle);
+};
+
+struct ConvergenceControlHeuristicLegacyPass : public FunctionPass {
+  static char ID;
+
+  ConvergenceControlHeuristicLegacyPass() : FunctionPass(ID) {
+    initializeConvergenceControlHeuristicLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  bool runOnFunction(Function &fn) override {
+    DominatorTree &domTree =
+        getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    ConvergenceInfo &convergenceInfo =
+        getAnalysis<ConvergenceInfoWrapperPass>().getConvergenceInfo();
+    ConvergenceControlHeuristic cch(fn, domTree, convergenceInfo);
+    return cch.run();
+  }
+
+  void getAnalysisUsage(AnalysisUsage &au) const override {
+    au.addRequired<DominatorTreeWrapperPass>();
+    au.addRequired<ConvergenceInfoWrapperPass>();
+
+    au.addPreserved<ConvergenceInfoWrapperPass>();
+    au.setPreservesCFG();
+  }
+};
+
+} // end anonymous namespace
+
+char ConvergenceControlHeuristicLegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ConvergenceControlHeuristicLegacyPass, DEBUG_TYPE,
+                      "Heuristically insert convergence control bundles", false,
+                      false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ConvergenceInfoWrapperPass)
+INITIALIZE_PASS_END(ConvergenceControlHeuristicLegacyPass, DEBUG_TYPE,
+                    "Heuristically insert convergence control bundles", false,
+                    false)
+
+bool ConvergenceControlHeuristic::run() {
+  // Take a copy of uncontrolled operations -- this is because we may be
+  // changing the set of roots.
+  SmallVector<ConvergentOperation *, 16> uncontrolled;
+  for (ConvergentOperation *op : m_convergenceInfo.roots()) {
+    if (op->getKind() == ConvergentOperation::Uncontrolled)
+      uncontrolled.push_back(op);
+  }
+
+  for (ConvergentOperation *op : uncontrolled) {
+    ConvergentOperation *token =
+        findOrInsertToken(op->getBlock(), op, op->getCycle());
+
+    if (auto *call = dyn_cast<CallInst>(op->getInstruction())) {
+      // Recreate the call, adding a single additional operand bundle.
+      IRBuilder<> builder(call);
+
+      SmallVector<Value *, 16> args(call->args());
+      SmallVector<OperandBundleDef, 8> bundles;
+
+      for (const auto &boi : call->bundle_op_infos())
+        bundles.emplace_back(call->operandBundleFromBundleOpInfo(boi));
+
+      bundles.push_back(m_convergenceInfo.makeOperandBundleDef(token));
+
+      CallInst *newCall =
+          builder.CreateCall(call->getFunctionType(), call->getCalledOperand(),
+                             args, bundles, call->getName());
+      newCall->setAttributes(call->getAttributes());
+      newCall->copyMetadata(*call);
+
+      m_convergenceInfo.insertOperation(token, ConvergentOperation::User,
+                                        newCall->getParent(), newCall);
+      m_convergenceInfo.eraseOperation(op);
+
+      call->replaceAllUsesWith(newCall);
+      call->eraseFromParent();
+    } else {
+      LLVM_DEBUG(dbgs() << "unhandled operation type: " << *op->getInstruction()
+                        << '\n');
+    }
+  }
+
+  return !uncontrolled.empty();
+}
+
+/// Find or insert a convergent operation producing a token suitable for use
+/// inside \p block for a convergent operation that is associated to \p cycle.
+/// If \p op is non-null, the location is the indicated operation inside the
+/// block; otherwise it is at the end of the block.
+ConvergentOperation *ConvergenceControlHeuristic::findOrInsertToken(
+    BasicBlock *block, ConvergentOperation *op, const Cycle *cycle) {
+  auto reverseBlockOps = llvm::reverse(m_convergenceInfo.block(block));
+  auto it = std::begin(reverseBlockOps);
+
+  if (op) {
+    do { /* nothing */
+    } while (*it++ != op);
+  }
+
+  auto findToken = [cycle](auto opRange) -> ConvergentOperation * {
+    for (ConvergentOperation *op : opRange) {
+      if (op->getKind() == ConvergentOperation::Anchor ||
+          op->getKind() == ConvergentOperation::Entry ||
+          op->getKind() == ConvergentOperation::Copy ||
+          op->getKind() == ConvergentOperation::Heart) {
+        if (op->getCycle() == cycle)
+          return op;
+      }
+    }
+    return nullptr;
+  };
+
+  ConvergentOperation *token =
+      findToken(llvm::make_range(it, std::end(reverseBlockOps)));
+  if (token)
+    return token;
+
+  const CycleInfo &cycleInfo = m_convergenceInfo.getCycleInfo();
+  DomTreeNode *blockNode = m_domTree.getNode(block);
+
+  for (DomTreeNode *parentNode; (parentNode = blockNode->getIDom()) != nullptr;
+       blockNode = parentNode) {
+    const Cycle *parentCycle = cycleInfo.getCycle(parentNode->getBlock());
+    if (parentCycle == cycle) {
+      // Block in the same cycle as the operation. Scan backwards for
+      // a token to use.
+      token = findToken(
+          llvm::reverse(m_convergenceInfo.block(parentNode->getBlock())));
+      if (token)
+        return token;
+      continue;
+    }
+
+    // Skip over blocks in inner cycles (relative to the cycle that we're
+    // trying to find the token for).
+    if (cycleInfo.contains(cycle, parentCycle))
+      continue;
+
+    // We're at the "top" of the cycle we're trying to find the token for,
+    // i.e. blockNode is a node of the cycle whose immediate dominator is
+    // outside the cycle. Insert a heart or anchor.
+    assert(cycleInfo.getCycle(blockNode->getBlock()) == cycle);
+
+    block = blockNode->getBlock();
+    bool insertHeart = false;
+
+    // If there's no heart in the cycle yet, we can potentially insert a heart
+    // here. However, a prerequisite for being able to do this reliably without
+    // breaking the validity of the program is that there is a dominator in
+    // the direct parent cycle. This isn't always the case in irreducible
+    // control flow. Example:
+    //
+    //     I
+    //    / \
+    //   A<->B
+    //   ^   ^
+    //   |   |
+    //   v   v
+    //   C   D
+    //   |   |
+    //
+    // There are two cycles here. Without loss of generality, assume that the
+    // DFS during cycle analysis was chosen such that the cycle hierarchy is:
+    //
+    //   Depth 1: Header A, additional entry B, additional blocks C & D
+    //     Depth 2: Header B, additional block D
+    //
+    // If we're at block B, we can just insert a heart, because if we were to
+    // later also insert a heart in A for the outer cycle, we'd then have a
+    // cycle that goes through two heart uses of a token without going through
+    // its definition.
+    if (!m_convergenceInfo.getHeartBlock(cycle)) {
+      if (parentCycle == cycle->getParent()) {
+        insertHeart = true;
+      } else {
+        // We may find a block in the direct parent further up in the dominator
+        // tree, e.g. in cases with successive self-loops:
+        //
+        //    |
+        //    A
+        //    |
+        //    B]
+        //    |
+        //    C]
+        //    |
+        //
+        // Starting at block C, we find a dominator in the direct parent cycle
+        // at A.
+        for (DomTreeNode *parentNode = blockNode->getIDom(); parentNode;
+             parentNode = parentNode->getIDom()) {
+          const Cycle *parentCycle = cycleInfo.getCycle(parentNode->getBlock());
+          if (parentCycle == cycle->getParent()) {
+            insertHeart = true;
+            break;
+          }
+          if (cycleInfo.contains(parentCycle, cycle))
+            break; // no more chance of finding a block in the direct parent
+        }
+      }
+    }
+
+    ConvergentOperation *parent = nullptr;
+    if (insertHeart) {
+      parent = findOrInsertToken(parentNode->getBlock(), nullptr,
+                                 cycle->getParent());
+    }
+
+    return m_convergenceInfo.createIntrinsic(
+        insertHeart ? ConvergentOperation::Heart : ConvergentOperation::Anchor,
+        parent, block, block->getFirstInsertionPt());
+  }
+
+  // We've reached the entry block without finding a suitable intrinsic.
+  // Insert an entry or anchor.
+  block = blockNode->getBlock();
+  assert(block == &m_function.getEntryBlock());
+
+  return m_convergenceInfo.createIntrinsic(
+      m_function.isConvergent() ? ConvergentOperation::Entry
+                                : ConvergentOperation::Anchor,
+      nullptr, block, block->getFirstInsertionPt());
+}

llvm/lib/Transforms/Utils/Utils.cpp

 /// library.
 void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeAddDiscriminatorsLegacyPassPass(Registry);
   initializeAssumeSimplifyPassLegacyPassPass(Registry);
   initializeAssumeBuilderPassLegacyPassPass(Registry);
   initializeBreakCriticalEdgesPass(Registry);
   initializeCanonicalizeAliasesLegacyPassPass(Registry);
   initializeCanonicalizeFreezeInLoopsPass(Registry);
+  initializeConvergenceControlHeuristicLegacyPassPass(Registry);
   initializeInstNamerPass(Registry);
   initializeLCSSAWrapperPassPass(Registry);
   initializeLibCallsShrinkWrapLegacyPassPass(Registry);
   initializeLoopSimplifyPass(Registry);
   initializeLowerInvokeLegacyPassPass(Registry);
   initializeLowerSwitchPass(Registry);
   initializeNameAnonGlobalLegacyPassPass(Registry);
   initializePromoteLegacyPassPass(Registry);

llvm/test/Transforms/ConvergenceControlHeuristic/basic.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK
+
+define void @empty() {
+; CHECK-LABEL: @empty(
+; CHECK-NEXT:    ret void
+;
+  ret void
+}
+
+define void @simple_convergent() convergent {
+; CHECK-LABEL: @simple_convergent(
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    ret void
+;
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+define void @simple_nonconvergent() {
+; CHECK-LABEL: @simple_nonconvergent(
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    ret void
+;
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+define void @preserve_bundles_and_metadata() {
+; CHECK-LABEL: @preserve_bundles_and_metadata(
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor(), !dbg !1
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "unknown-bundle"(i32 0), "convergencectrl"(token [[TMP1]]) ], !dbg !1, !unknown !5
+; CHECK-NEXT:    ret void
+;
+  call void @convergent.op(i32 0) [ "unknown-bundle"(i32 0) ], !dbg !2, !unknown !0
+  ret void
+}
+
+define void @acyclic() convergent {
+; CHECK-LABEL: @acyclic(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    br i1 undef, label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 undef, label %A, label %B
+
+A:
+  call void @convergent.op(i32 0)
+  br label %B
+
+B:
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+;
+;      |
+;      A]
+;      |
+;   /->B
+;   |  |\
+;   |  | C]
+;   |  |/
+;   ^-<D
+;      |
+;      E
+;
+define void @natural_loops() convergent {
+; CHECK-LABEL: @natural_loops(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TMP2:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ]
+; CHECK-NEXT:    br i1 undef, label [[C:%.*]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[TMP3:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TMP2]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP3]]) ]
+; CHECK-NEXT:    br i1 undef, label [[C]], label [[D]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[E:%.*]]
+; CHECK:       E:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %A
+
+A:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %A, label %B
+
+B:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %C, label %D
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %C, label %D
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %E
+
+E:
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+;
+;   |   |
+;   A<->B
+;   ^   ^
+;   |   |
+;   v   v
+;   C   D
+;    \ /
+;     E
+;
+define void @irreducible() convergent {
+; CHECK-LABEL: @irreducible(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    br i1 undef, label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TMP2:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[E:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP2]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[E]]
+; CHECK:       E:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 undef, label %A, label %B
+
+A:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %C
+
+B:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %A, label %D
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %A, label %E
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %E
+
+E:
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+!llvm.module.flags = !{!1}
+
+!0 = !{}
+!1 = !{i32 2, !"Debug Info Version", i32 3}
+!2 = !DILocation(scope: !3)
+!3 = distinct !DISubprogram(name: "main", unit: !4)
+!4 = distinct !DICompileUnit(language: DW_LANG_C99, file: !5)
+!5 = !DIFile(filename: "foo", directory: "bar")
+
+declare void @convergent.op(i32) convergent

llvm/test/Transforms/ConvergenceControlHeuristic/inlineasm.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK
+
+define void @basic() {
+; CHECK-LABEL: @basic(
+; CHECK-NEXT:    [[TMP1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void asm sideeffect "dummy", ""() #1 [ "convergencectrl"(token [[TMP1]]) ]
+; CHECK-NEXT:    ret void
+;
+  call void asm sideeffect "dummy", ""() convergent
+  ret void
+}

llvm/test/Transforms/ConvergenceControlHeuristic/preexisting.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -convergence-control-heuristic | FileCheck %s -check-prefix=CHECK
+
+define void @simple() convergent {
+; CHECK-LABEL: @simple(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[A:%.*]] = call token @llvm.experimental.convergence.entry()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[A]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 1) [ "convergencectrl"(token [[A]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %a = call token @llvm.experimental.convergence.entry()
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %a) ]
+  call void @convergent.op(i32 1)
+  ret void
+}
+
+define void @simple2() {
+; CHECK-LABEL: @simple2(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[A]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 1) [ "convergencectrl"(token [[A]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %a = call token @llvm.experimental.convergence.anchor()
+  call void @convergent.op(i32 0)
+  call void @convergent.op(i32 1) [ "convergencectrl"(token %a) ]
+  ret void
+}
+
+define void @natural_loop() {
+; CHECK-LABEL: @natural_loop(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %C
+
+C:
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+define void @natural_loop2() {
+; CHECK-LABEL: @natural_loop2(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[C]], label [[D:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  br i1 undef, label %B, label %C
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %C, label %D
+
+D:
+  call void @convergent.op(i32 0)
+  ret void
+}
+
+define void @natural_loop_extended1() {
+; CHECK-LABEL: @natural_loop_extended1(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  br i1 undef, label %B, label %C
+
+C:
+  call void @convergent.op(i32 0) [ "convergencectrl"(token %tok.b) ]
+  call void @convergent.op(i32 1)
+  ret void
+}
+
+define void @natural_loop_extended2() {
+; CHECK-LABEL: @natural_loop_extended2(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  br i1 undef, label %B, label %C
+
+C:
+  call void @convergent.op(i32 0)
+  call void @convergent.op(i32 1) [ "convergencectrl"(token %tok.b) ]
+  ret void
+}
+
+;
+;      A
+;      |
+;      B]
+;      |
+;      C]
+;      |
+;      D
+;      |\
+;      | E
+;      |/
+;      F
+;
+define void @natural_loop_extended3() {
+; CHECK-LABEL: @natural_loop_extended3(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[C]], label [[D:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    br i1 undef, label [[E:%.*]], label [[F:%.*]]
+; CHECK:       E:
+; CHECK-NEXT:    call void @convergent.op(i32 1) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    br label [[F]]
+; CHECK:       F:
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  br i1 undef, label %B, label %C
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %C, label %D
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %E, label %F
+
+E:
+  call void @convergent.op(i32 1) [ "convergencectrl"(token %tok.b) ]
+  br label %F
+
+F:
+  ret void
+}
+
+define void @unusual_heart() {
+; CHECK-LABEL: @unusual_heart(
+; CHECK-NEXT:  A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[C:%.*]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[TOK_C:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_C]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[D]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[E:%.*]]
+; CHECK:       E:
+; CHECK-NEXT:    ret void
+;
+A:
+  %tok.a = call token @llvm.experimental.convergence.anchor()
+  br label %B
+
+B:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %C, label %D
+
+C:
+  %tok.c = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %tok.a) ]
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %D
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %E
+
+E:
+  ret void
+}
+
+;
+;   |   |
+;   A<->B
+;   ^   ^
+;   |   |
+;   v   v
+;   C   D
+;    \ /
+;     E
+;
+define void @irreducible1() {
+; CHECK-LABEL: @irreducible1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 undef, label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[TOK_A:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_A]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[E:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[E]]
+; CHECK:       E:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+A:
+  %tok.a = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br i1 undef, label %B, label %C
+
+B:
+  br i1 undef, label %A, label %D
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %A, label %E
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %E
+
+E:
+  ret void
+}
+
+; Same CFG, different initial loop heart
+define void @irreducible2() {
+; CHECK-LABEL: @irreducible2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 undef, label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[TMP0:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[TOK_B:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TMP0]]) ]
+; CHECK-NEXT:    br i1 undef, label [[A]], label [[E:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    call void @convergent.op(i32 0) [ "convergencectrl"(token [[TOK_B]]) ]
+; CHECK-NEXT:    br i1 undef, label [[B]], label [[E]]
+; CHECK:       E:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br i1 undef, label %A, label %B
+
+A:
+  br i1 undef, label %B, label %C
+
+B:
+  %tok.b = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br i1 undef, label %A, label %D
+
+C:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %A, label %E
+
+D:
+  call void @convergent.op(i32 0)
+  br i1 undef, label %B, label %E
+
+E:
+  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()