[LoopUnroll] adjust for new `convergent` semantics

[sameerds]

Summary

Adjust the unrolling check for the new semantics:

• There is no restriction on loops with convergent operations that are controlled inside the loop -- their behavior with respect to cross-thread communication is (partially) implementation-defined, and the loop unrolling is part of the implementation, so...

• Fix unrolling with loop heart intrinsics: in a typical loop with a loop heart in the header that uses a token from outside the loop, duplicating the intrinsic would introduce multiple static uses of a convergence control token in a cycle that does not contain its definition.

Spell out the setup of UnrollLoopOptions to reduce the potential for
confusion caused by very long struct initializers.

Original implementation [D85605] by Nicolai Haehnle <[e-mail]>.

[JonChesterfield]

This looks quite high risk. How is it tested beyond this lit test, specifically with code that runs on the GPU? It's really easy to get broken transforms to pass a lit test where the checks were generated from the implementation.

Also could you point reviewer's to the documentation on the heart intrinsic system and how it relates to the current modeling? I know there's a slide deque or two somewhere, hoping for something more formal.

[sameerds]

In D153744#4448078, @JonChesterfield wrote:

This looks quite high risk. How is it tested beyond this lit test, specifically with code that runs on the GPU? It's really easy to get broken transforms to pass a lit test where the checks were generated from the implementation.

Also could you point reviewer's to the documentation on the heart intrinsic system and how it relates to the current modeling? I know there's a slide deque or two somewhere, hoping for something more formal.

Thanks for taking an interest, Jon. There's a reason why the intrinsics have the word "experimental" in their name. Risk is limited to any flow that actually decides to use them, and no one is being exhorted to actually run this stuff on their GPU at this point. As for documentation, there's definitely been a LOT more activity than just a "slide deck or two", both inside AMD as well as outside. Please do refer to the "stack" of reviews that this Phab review belongs to.

Also, there's this, for links to all historical stuff:
https://discourse.llvm.org/t/rfc-introduce-convergence-control-intrinsics/69613

[arsenm]

In D153744#4448078, @JonChesterfield wrote:

This looks quite high risk. How is it tested beyond this lit test, specifically with code that runs on the GPU? It's really easy to get broken transforms to pass a lit test where the checks were generated from the implementation.

The fun part is things are

llvm/lib/Transforms/Utils/LoopUnroll.cpp

472–497

This is a lot for one LLVM_DEBUG, move this all to a function?

[JonChesterfield]

! In D153744#4448146, @sameerds wrote:
As for documentation, there's definitely been a LOT more activity than just a "slide deck or two", both inside AMD as well as outside. Please do refer to the "stack" of reviews that this Phab review belongs to.

Also, there's this, for links to all historical stuff:
https://discourse.llvm.org/t/rfc-introduce-convergence-control-intrinsics/69613

It's been a multi-year thing with multiple authors, I doubt trawling the history will provide anyone with an accurate idea of what we're currently trying to build.

This stack is revising how control flow is modelled in llvm for GPUs. The failure modes are substantial. Could part of the implementation effort be directed to writing down what the overall algorithm is intended to be, somewhere that is visible outside of AMD? Hopefully that's a direct adaption of whatever design document you are working from internally.

[sameerds]

In D153744#4448501, @JonChesterfield wrote:

It's been a multi-year thing with multiple authors, I doubt trawling the history will provide anyone with an accurate idea of what we're currently trying to build.

This stack is revising how control flow is modelled in llvm for GPUs. The failure modes are substantial. Could part of the implementation effort be directed to writing down what the overall algorithm is intended to be, somewhere that is visible outside of AMD? Hopefully that's a direct adaption of whatever design document you are working from internally.

This review points to earlier "parent" reviews. In particular:

D147116: [RFC] Introduce convergence control intrinsics

That's the very first review in this stack.

[arsenm]

llvm/lib/Analysis/CodeMetrics.cpp

114–138

It might be worth introducing a ConvergenceControlInst subclass of IntrinsicInst

[sameerds]

• rebase

[sameerds]

For what it's worth, the formal semantics of convergence tokens and intrinsics landed in LLVM. This patch relaxes the constraints on loop unrolling in the presence of convergence tokens as defined in that spec:

https://llvm.org/docs/ConvergentOperations.html

[sameerds]

• rebased
• addressed the comment about having too much code inside LLVM_DEBUG

[sameerds]

llvm/lib/Analysis/CodeMetrics.cpp

114–138

I suppose so, but it seems too early to attempt for an experimental feature!

llvm/lib/Transforms/Utils/LoopUnroll.cpp

472–497

Fixed by moving it out into a function.

[arsenm]

llvm/lib/Analysis/CodeMetrics.cpp

114–138

Part of the experiment is how inconvenient it is, and also there's no better time to have the convenient code than when implementing it. We have ConstrainedFPIntrinsic for "experimental" features too. It's not a lot of work to add (not that it should be part of this patch)

[sameerds]

llvm/lib/Analysis/CodeMetrics.cpp

114–138

Does that mean this change is good to go?

llvm/include/llvm/Analysis/CodeMetrics.h

 #define LLVM_ANALYSIS_CODEMETRICS_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/InstructionCost.h"
 
 namespace llvm {
 class AssumptionCache;
 class BasicBlock;
+class Instruction;
 class Loop;
 class Function;
 template <class T> class SmallPtrSetImpl;
 class TargetTransformInfo;
 class Value;
 
 /// Utility to calculate the size and a few similar metrics for a set
 /// of basic blocks.
struct CodeMetrics {
   ///
   /// True if this function contains one or more indirect branches, or it contains
   /// one or more 'noduplicate' instructions.
   bool notDuplicatable = false;
 
   /// True if this function contains a call to a convergent function.
   bool convergent = false;
 
+  /// True if the code contains an uncontrolled convergent operation.
+  bool convergentUncontrolled = false;
+
   /// True if this function calls alloca (in the C sense).
   bool usesDynamicAlloca = false;
 
   /// Code size cost of the analyzed blocks.
   InstructionCost NumInsts = 0;
 
   /// Number of analyzed blocks.
   unsigned NumBlocks = false;
 
+  /// Keeps track of loop heart intrinsics and their convergencectrl token use.
+  std::vector<std::pair<const Instruction *, Value *>> convergenceHearts;
+
   /// Keeps track of basic block code size estimates.
   DenseMap<const BasicBlock *, InstructionCost> NumBBInsts;
 
   /// Keep track of the number of calls to 'big' functions.
   unsigned NumCalls = false;
 
   /// The number of calls to internal functions with a single caller.
   ///
   /// These are likely targets for future inlining, likely exposed by
   /// interleaved devirtualization.
   unsigned NumInlineCandidates = 0;
 
   /// How many instructions produce vector values.
   ///
   /// The inliner is more aggressive with inlining vector kernels.
   unsigned NumVectorInsts = 0;
 
   /// How many 'ret' instructions the blocks contain.
   unsigned NumRets = 0;
 
   /// Add information about a block to the current state.
   void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI,
                          const SmallPtrSetImpl<const Value *> &EphValues,
-                         bool PrepareForLTO = false);
+                         bool PrepareForLTO = false, const Loop *L = nullptr);
 
   /// Collect a loop's ephemeral values (those used only by an assume
   /// or similar intrinsics in the loop).
   static void collectEphemeralValues(const Loop *L, AssumptionCache *AC,
                                      SmallPtrSetImpl<const Value *> &EphValues);
 
   /// Collect a functions's ephemeral values (those used only by an
   /// assume or similar intrinsics in the function).
   static void collectEphemeralValues(const Function *L, AssumptionCache *AC,
                                      SmallPtrSetImpl<const Value *> &EphValues);
 };
 
 }
 
 #endif

llvm/include/llvm/Transforms/Utils/UnrollLoop.h

 
 struct UnrollLoopOptions {
   unsigned Count;
   bool Force;
   bool Runtime;
   bool AllowExpensiveTripCount;
   bool UnrollRemainder;
   bool ForgetAllSCEV;
+  const Instruction *Heart = nullptr;
 };
 
 LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
                             ScalarEvolution *SE, DominatorTree *DT,
                             AssumptionCache *AC,
                             const llvm::TargetTransformInfo *TTI,
                             OptimizationRemarkEmitter *ORE, bool PreserveLCSSA,
                             Loop **RemainderLoop = nullptr);
TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
     Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI,
     BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
     llvm::OptimizationRemarkEmitter &ORE, int OptLevel,
     std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
     std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
     std::optional<bool> UserUpperBound,
     std::optional<unsigned> UserFullUnrollMaxCount);
 
-InstructionCost ApproximateLoopSize(const Loop *L, unsigned &NumCalls,
-    bool &NotDuplicatable, bool &Convergent, const TargetTransformInfo &TTI,
-    const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns);
+enum class LoopConvergenceKind {
+  // No convergent operations at all.
+  None,
+
+  // All convergent operations are controlled and anchored inside the loop.
+  AnchoredInLoop,
+
+  // Some convergent operations, unrolling is possible subject to constraints
+  // (no remainder loop).
+  Some,
+};
+
+InstructionCost
+ApproximateLoopSize(const Loop *L, unsigned &NumCalls, bool &NotDuplicatable,
+                    LoopConvergenceKind &Convergent, const Instruction *&Heart,
+                    const TargetTransformInfo &TTI,
+                    const SmallPtrSetImpl<const Value *> &EphValues,
+                    unsigned BEInsns);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H

llvm/lib/Analysis/CodeMetrics.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/InstructionCost.h"
 
 #define DEBUG_TYPE "code-metrics"
 
 using namespace llvm;
 
 static void
assert(I->getParent()->getParent() == F &&
            "Found assumption for the wrong function!");
 
     if (EphValues.insert(I).second)
       appendSpeculatableOperands(I, Visited, Worklist);
   }
 
   completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
+static bool isConvergenceCtrlIntr(const Instruction &I) {
+  auto *Intrinsic = dyn_cast<IntrinsicInst>(&I);
+  if (!Intrinsic)
+    return false;
+  switch (Intrinsic->getIntrinsicID()) {
+  case Intrinsic::experimental_convergence_entry:
+  case Intrinsic::experimental_convergence_anchor:
+  case Intrinsic::experimental_convergence_loop:
+    return true;
+  }
+  return false;
+}
+
+static bool isUsedOutsideOfLoop(const Instruction &I, const Loop &L) {
+  for (const auto *U : I.users()) {
+    if (auto *I = dyn_cast<Instruction>(U)) {
+      if (!L.contains(I->getParent()))
+        return true;
+    }
+  }
+  return false;
+}
+
 /// Fill in the current structure with information gleaned from the specified
 /// block.
 void CodeMetrics::analyzeBasicBlock(
     const BasicBlock *BB, const TargetTransformInfo &TTI,
-    const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) {
+    const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO,
+    const Loop *L) {
   ++NumBlocks;
   InstructionCost NumInstsBeforeThisBB = NumInsts;
   for (const Instruction &I : *BB) {
     // Skip ephemeral values.
     if (EphValues.count(&I))
       continue;
 
     // Special handling for calls.
for (const Instruction &I : *BB) {
     if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
       if (!AI->isStaticAlloca())
         this->usesDynamicAlloca = true;
     }
 
     if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
       ++NumVectorInsts;
 
-    if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
-      notDuplicatable = true;
+    if (I.getType()->isTokenTy()) {
+      if (L && isConvergenceCtrlIntr(I)) {
+        notDuplicatable = isUsedOutsideOfLoop(I, *L);
+      } else {
+        notDuplicatable = I.isUsedOutsideOfBlock(BB);
+      }
+    }
 
-    if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
-      if (CI->cannotDuplicate())
+    if (const CallBase *CB = dyn_cast<CallBase>(&I)) {
+      if (CB->cannotDuplicate())
         notDuplicatable = true;
-      if (CI->isConvergent())
+      if (CB->isConvergent()) {
         convergent = true;
-    }
 
-    if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
-      if (InvI->cannotDuplicate())
-        notDuplicatable = true;
+        auto *intrinsicInst = dyn_cast<IntrinsicInst>(CB);
+        auto control = CB->getOperandBundle(LLVMContext::OB_convergencectrl);
+        if (intrinsicInst && intrinsicInst->getIntrinsicID() ==
+                                 Intrinsic::experimental_convergence_loop) {
+          assert(control &&
+                 "invalid IR: loop heart without convergencectrl bundle");
+          Value *token = control->Inputs[0].get();
+          convergenceHearts.emplace_back(intrinsicInst, token);
+        } else if (!control &&
+                   (!intrinsicInst ||
+                    intrinsicInst->getIntrinsicID() !=
+                        Intrinsic::experimental_convergence_anchor)) {
+          convergentUncontrolled = true;
+        }
+      }
+    }
 
     NumInsts += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);
   }
 
   if (isa<ReturnInst>(BB->getTerminator()))
     ++NumRets;
 
   // We never want to inline functions that contain an indirectbr.  This is

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

for (Instruction &I : *BB) {
         if (Alloca->getParent() == &F->getEntryBlock())
           EphValues.insert(&I);
       }
     }
   }
 
   unsigned NumInlineCandidates;
   bool NotDuplicatable;
-  bool Convergent;
+  LoopConvergenceKind Convergent;
+  const Instruction *Heart;
   InstructionCost LoopSizeIC =
       ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
-                          TTI, EphValues, UP.BEInsns);
+                          Heart, TTI, EphValues, UP.BEInsns);
   LLVM_DEBUG(dbgs() << "Estimated loop size is " << LoopSizeIC << "\n");
 
   // Loop is not unrollable if the loop contains certain instructions.
-  if (NotDuplicatable || Convergent || !LoopSizeIC.isValid()) {
+  if (NotDuplicatable || !LoopSizeIC.isValid() ||
+      Convergent != LoopConvergenceKind::None) {
     LLVM_DEBUG(dbgs() << "Loop not considered unrollable\n");
     return 1;
   }
   unsigned LoopSize = *LoopSizeIC.getValue();
 
   // TODO: Determine trip count of \p CLI if constant, computeUnrollCount might
   // be able to use it.
   int TripCount = 0;

llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp

tryToUnrollAndJamLoop(Loop *L, DominatorTree &DT, LoopInfo *LI,
   if (!isSafeToUnrollAndJam(L, SE, DT, DI, *LI)) {
     LLVM_DEBUG(dbgs() << "  Disabled due to not being safe.\n");
     return LoopUnrollResult::Unmodified;
   }
 
   // Approximate the loop size and collect useful info
   unsigned NumInlineCandidates;
   bool NotDuplicatable;
-  bool Convergent;
   SmallPtrSet<const Value *, 32> EphValues;
   CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
   Loop *SubLoop = L->getSubLoops()[0];
+  LoopConvergenceKind Convergent;
+  const Instruction *Heart;
   InstructionCost InnerLoopSizeIC =
       ApproximateLoopSize(SubLoop, NumInlineCandidates, NotDuplicatable,
-                          Convergent, TTI, EphValues, UP.BEInsns);
+                          Convergent, Heart, TTI, EphValues, UP.BEInsns);
   InstructionCost OuterLoopSizeIC =
       ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
-                          TTI, EphValues, UP.BEInsns);
+                          Heart, TTI, EphValues, UP.BEInsns);
   LLVM_DEBUG(dbgs() << "  Outer Loop Size: " << OuterLoopSizeIC << "\n");
   LLVM_DEBUG(dbgs() << "  Inner Loop Size: " << InnerLoopSizeIC << "\n");
 
   if (!InnerLoopSizeIC.isValid() || !OuterLoopSizeIC.isValid()) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop which contains instructions"
                       << " with invalid cost.\n");
     return LoopUnrollResult::Unmodified;
   }
   unsigned InnerLoopSize = *InnerLoopSizeIC.getValue();
   unsigned OuterLoopSize = *OuterLoopSizeIC.getValue();
 
   if (NotDuplicatable) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop which contains non-duplicatable "
                          "instructions.\n");
     return LoopUnrollResult::Unmodified;
   }
   if (NumInlineCandidates != 0) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop with inlinable calls.\n");
     return LoopUnrollResult::Unmodified;
   }
-  if (Convergent) {
+  if (Convergent != LoopConvergenceKind::None) {
     LLVM_DEBUG(
         dbgs() << "  Not unrolling loop with convergent instructions.\n");
     return LoopUnrollResult::Unmodified;
   }
 
   // Save original loop IDs for after the transformation.
   MDNode *OrigOuterLoopID = L->getLoopID();
   MDNode *OrigSubLoopID = SubLoop->getLoopID();

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

LLVM_DEBUG(dbgs() << "Analysis finished:\n"
                     << "UnrolledCost: " << UnrolledCost << ", "
                     << "RolledDynamicCost: " << RolledDynamicCost << "\n");
   return {{unsigned(*UnrolledCost.getValue()),
            unsigned(*RolledDynamicCost.getValue())}};
 }
 
 /// ApproximateLoopSize - Approximate the size of the loop.
 InstructionCost llvm::ApproximateLoopSize(
-    const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent,
+    const Loop *L, unsigned &NumCalls, bool &NotDuplicatable,
+    LoopConvergenceKind &Convergent, const Instruction *&Heart,
     const TargetTransformInfo &TTI,
     const SmallPtrSetImpl<const Value *> &EphValues, unsigned BEInsns) {
   CodeMetrics Metrics;
-  for (BasicBlock *BB : L->blocks())
-    Metrics.analyzeBasicBlock(BB, TTI, EphValues);
+  bool convergenceControlledByOutside = false;
+
+  Heart = nullptr;
+
+  for (BasicBlock *BB : L->blocks()) {
+    Metrics.analyzeBasicBlock(BB, TTI, EphValues, /* PrepareForLTO= */ false,
+                              L);
+
+    for (const auto &heart : Metrics.convergenceHearts) {
+      BasicBlock *defBlock = cast<Instruction>(heart.second)->getParent();
+      if (!L->contains(defBlock)) {
+        convergenceControlledByOutside = true;
+        assert(!Heart && "invalid IR: loop has multiple relevant hearts");
+        Heart = heart.first;
+      }
+    }
+    Metrics.convergenceHearts.clear();
+  }
   NumCalls = Metrics.NumInlineCandidates;
   NotDuplicatable = Metrics.notDuplicatable;
-  Convergent = Metrics.convergent;
+
+  if (Metrics.convergentUncontrolled || convergenceControlledByOutside)
+    Convergent = LoopConvergenceKind::Some;
+  else if (Metrics.convergent)
+    Convergent = LoopConvergenceKind::AnchoredInLoop;
+  else
+    Convergent = LoopConvergenceKind::None;
 
   InstructionCost LoopSize = Metrics.NumInsts;
 
   // Don't allow an estimate of size zero.  This would allows unrolling of loops
   // with huge iteration counts, which is a compile time problem even if it's
   // not a problem for code quality. Also, the code using this size may assume
   // that each loop has at least three instructions (likely a conditional
   // branch, a comparison feeding that branch, and some kind of loop increment
tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
   // When automatic unrolling is disabled, do not unroll unless overridden for
   // this loop.
   if (OnlyWhenForced && !(TM & TM_Enable))
     return LoopUnrollResult::Unmodified;
 
   bool OptForSize = L->getHeader()->getParent()->hasOptSize();
   unsigned NumInlineCandidates;
   bool NotDuplicatable;
-  bool Convergent;
   TargetTransformInfo::UnrollingPreferences UP = gatherUnrollingPreferences(
       L, SE, TTI, BFI, PSI, ORE, OptLevel, ProvidedThreshold, ProvidedCount,
       ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
       ProvidedFullUnrollMaxCount);
   TargetTransformInfo::PeelingPreferences PP = gatherPeelingPreferences(
       L, SE, TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling, true);
 
   // Exit early if unrolling is disabled. For OptForSize, we pick the loop size
   // as threshold later on.
   if (UP.Threshold == 0 && (!UP.Partial || UP.PartialThreshold == 0) &&
       !OptForSize)
     return LoopUnrollResult::Unmodified;
 
   SmallPtrSet<const Value *, 32> EphValues;
   CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
 
+  LoopConvergenceKind Convergent;
+  const Instruction *Heart;
   InstructionCost LoopSizeIC =
       ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
-                          TTI, EphValues, UP.BEInsns);
+                          Heart, TTI, EphValues, UP.BEInsns);
   LLVM_DEBUG(dbgs() << "  Loop Size = " << LoopSizeIC << "\n");
 
   if (!LoopSizeIC.isValid()) {
     LLVM_DEBUG(dbgs() << "  Not unrolling loop which contains instructions"
                       << " with invalid cost.\n");
     return LoopUnrollResult::Unmodified;
   }
   unsigned LoopSize = *LoopSizeIC.getValue();
if (ExitingBlock)
       TripMultiple = SE.getSmallConstantTripMultiple(L, ExitingBlock);
   }
 
   // If the loop contains a convergent operation, the prelude we'd add
   // to do the first few instructions before we hit the unrolled loop
   // is unsafe -- it adds a control-flow dependency to the convergent
   // operation.  Therefore restrict remainder loop (try unrolling without).
   //
-  // TODO: This is quite conservative.  In practice, convergent_op()
-  // is likely to be called unconditionally in the loop.  In this
-  // case, the program would be ill-formed (on most architectures)
-  // unless n were the same on all threads in a thread group.
-  // Assuming n is the same on all threads, any kind of unrolling is
-  // safe.  But currently llvm's notion of convergence isn't powerful
-  // enough to express this.
-  if (Convergent)
+  // TODO: This is still somewhat conservative, as we could allow the remainder
+  // if the trip count is uniform (and we don't have an unnatural heart).
+  bool ConvergentAllowsRuntime = true;
+  switch (Convergent) {
+  case LoopConvergenceKind::None:
+  case LoopConvergenceKind::AnchoredInLoop:
+    break; // no convergence-related restrictions
+  case LoopConvergenceKind::Some:
     UP.AllowRemainder = false;
+    ConvergentAllowsRuntime = false;
+    break;
+  }
 
   // Try to find the trip count upper bound if we cannot find the exact trip
   // count.
   unsigned MaxTripCount = 0;
   bool MaxOrZero = false;
   if (!TripCount) {
     MaxTripCount = SE.getSmallConstantMaxTripCount(L);
     MaxOrZero = SE.isBackedgeTakenCountMaxOrZero(L);
   }
 
   // computeUnrollCount() decides whether it is beneficial to use upper bound to
   // fully unroll the loop.
   bool UseUpperBound = false;
   bool IsCountSetExplicitly = computeUnrollCount(
     L, TTI, DT, LI, &AC, SE, EphValues, &ORE, TripCount, MaxTripCount, MaxOrZero,
       TripMultiple, LoopSize, UP, PP, UseUpperBound);
   if (!UP.Count)
     return LoopUnrollResult::Unmodified;
 
+  UP.Runtime &= ConvergentAllowsRuntime;
+
   if (PP.PeelCount) {
     assert(UP.Count == 1 && "Cannot perform peel and unroll in the same step");
     LLVM_DEBUG(dbgs() << "PEELING loop %" << L->getHeader()->getName()
                       << " with iteration count " << PP.PeelCount << "!\n");
     ORE.emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Peeled", L->getStartLoc(),
                                 L->getHeader())
              << " peeled loop by " << ore::NV("PeelCount", PP.PeelCount)
tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE,
   // computeUnrollCount().
   UP.Runtime &= TripCount == 0 && TripMultiple % UP.Count != 0;
 
   // Save loop properties before it is transformed.
   MDNode *OrigLoopID = L->getLoopID();
 
   // Unroll the loop.
   Loop *RemainderLoop = nullptr;
+  UnrollLoopOptions ULO;
+  ULO.Count = UP.Count;
+  ULO.Force = UP.Force;
+  ULO.AllowExpensiveTripCount = UP.AllowExpensiveTripCount;
+  ULO.UnrollRemainder = UP.UnrollRemainder;
+  ULO.Runtime = UP.Runtime;
+  ULO.ForgetAllSCEV = ForgetAllSCEV;
+  ULO.Heart = Heart;
   LoopUnrollResult UnrollResult = UnrollLoop(
-      L,
-      {UP.Count, UP.Force, UP.Runtime, UP.AllowExpensiveTripCount,
-       UP.UnrollRemainder, ForgetAllSCEV},
-      LI, &SE, &DT, &AC, &TTI, &ORE, PreserveLCSSA, &RemainderLoop);
+      L, ULO, LI, &SE, &DT, &AC, &TTI, &ORE, PreserveLCSSA, &RemainderLoop);
   if (UnrollResult == LoopUnrollResult::Unmodified)
     return LoopUnrollResult::Unmodified;
 
   if (RemainderLoop) {
     std::optional<MDNode *> RemainderLoopID =
         makeFollowupLoopID(OrigLoopID, {LLVMLoopUnrollFollowupAll,
                                         LLVMLoopUnrollFollowupRemainder});
     if (RemainderLoopID)

llvm/lib/Transforms/Utils/LoopUnroll.cpp

for (BasicBlock *BB : L->getBlocks()) {
     }
     // We can't do recursive deletion until we're done iterating, as we might
     // have a phi which (potentially indirectly) uses instructions later in
     // the block we're iterating through.
     RecursivelyDeleteTriviallyDeadInstructions(DeadInsts);
   }
 }
 
+// Loops containing convergent instructions that are uncontrolled or controlled
+// from outside the loop must have a count that divides their TripMultiple.
+LLVM_ATTRIBUTE_USED
+static bool canHaveUnrollRemainder(const Loop *L) {
+  // If the first call in the loop header the loop intrinsic, then the loop is
+  // controlled from outside.
+  auto *H = L->getHeader();
+  for (auto &I : *H) {
+    if (isa<CallBase>(I)) {
+      if (auto *intrinsicInst = dyn_cast<IntrinsicInst>(&I)) {
+        if (intrinsicInst->getIntrinsicID() ==
+            Intrinsic::experimental_convergence_loop)
+          return false;
+      }
+      break;
+    }
+  }
+
+  // Check for uncontrolled convergent operations.
+  for (auto &BB : L->blocks()) {
+    for (auto &I : *BB) {
+      if (auto *CB = dyn_cast<CallBase>(&I)) {
+        if (auto *intrinsicInst = dyn_cast<IntrinsicInst>(CB)) {
+          if (intrinsicInst->getIntrinsicID() ==
+              Intrinsic::experimental_convergence_anchor) {
+            // A call to anchor does not count as uncontrolled. We don't need to
+            // check further because there can be no uncontrolled operations in
+            // this function.
+            return true;
+          }
+          if (CB->isConvergent() && CB->countOperandBundlesOfType(
+                                        LLVMContext::OB_convergencectrl) == 0) {
+            return false;
+          }
+        }
+      }
+    }
+  }
+  return true;
+}
+
 /// Unroll the given loop by Count. The loop must be in LCSSA form.  Unrolling
 /// can only fail when the loop's latch block is not terminated by a conditional
 /// branch instruction. However, if the trip count (and multiple) are not known,
 /// loop unrolling will mostly produce more code that is no faster.
 ///
 /// If Runtime is true then UnrollLoop will try to insert a prologue or
 /// epilogue that ensures the latch has a trip multiple of Count. UnrollLoop
 /// will not runtime-unroll the loop if computing the run-time trip count will
LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
   // unconditional branch in the unrolled loop in some cases.
   bool LatchIsExiting = L->isLoopExiting(LatchBlock);
   if (!LatchBI || (LatchBI->isConditional() && !LatchIsExiting)) {
     LLVM_DEBUG(
         dbgs() << "Can't unroll; a conditional latch must exit the loop");
     return LoopUnrollResult::Unmodified;
   }
 
-  // Loops containing convergent instructions cannot use runtime unrolling,
-  // as the prologue/epilogue may add additional control-dependencies to
-  // convergent operations.
-  LLVM_DEBUG(
-      {
-        bool HasConvergent = false;
-        for (auto &BB : L->blocks())
-          for (auto &I : *BB)
-            if (auto *CB = dyn_cast<CallBase>(&I))
-              HasConvergent |= CB->isConvergent();
-        assert((!HasConvergent || !ULO.Runtime) &&
-               "Can't runtime unroll if loop contains a convergent operation.");
-      });
+  assert((!ULO.Runtime || canHaveUnrollRemainder(L)) &&
 
   bool EpilogProfitability =
       UnrollRuntimeEpilog.getNumOccurrences() ? UnrollRuntimeEpilog
                                               : isEpilogProfitable(L);
 
   if (ULO.Runtime &&
       !UnrollRuntimeLoopRemainder(L, ULO.Count, ULO.AllowExpensiveTripCount,
                                   EpilogProfitability, ULO.UnrollRemainder,
                                   ULO.ForgetAllSCEV, LI, SE, DT, AC, TTI,
                                   PreserveLCSSA, RemainderLoop)) {
     if (ULO.Force)
       ULO.Runtime = false;
     else {
       LLVM_DEBUG(dbgs() << "Won't unroll; remainder loop could not be "
                            "generated when assuming runtime trip count\n");
       return LoopUnrollResult::Unmodified;
     }
   }
 
   using namespace ore;
   // Report the unrolling decision.
   if (CompletelyUnroll) {
     LLVM_DEBUG(dbgs() << "COMPLETELY UNROLLING loop %" << Header->getName()
                       << " with trip count " << ULO.Count << "!\n");
     if (ORE)
       ORE->emit([&]() {
         return OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
                                   L->getHeader())
                << "completely unrolled loop with "
                << NV("UnrollCount", ULO.Count) << " iterations";
       });
   } else {
     LLVM_DEBUG(dbgs() << "UNROLLING loop %" << Header->getName() << " by "
                       << ULO.Count);
     if (ULO.Runtime)
       LLVM_DEBUG(dbgs() << " with run-time trip count");
     LLVM_DEBUG(dbgs() << "!\n");
 
LoopUnrollResult llvm::UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI,
   // loop, the associated metadata must be cloned for each iteration.
   SmallVector<MDNode *, 6> LoopLocalNoAliasDeclScopes;
   identifyNoAliasScopesToClone(L->getBlocks(), LoopLocalNoAliasDeclScopes);
 
   // We place the unrolled iterations immediately after the original loop
   // latch.  This is a reasonable default placement if we don't have block
   // frequencies, and if we do, well the layout will be adjusted later.
   auto BlockInsertPt = std::next(LatchBlock->getIterator());
+
+  assert(ULO.Heart == nullptr || ULO.Heart->getParent() == Header);
+
   for (unsigned It = 1; It != ULO.Count; ++It) {
     SmallVector<BasicBlock *, 8> NewBlocks;
     SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
     NewLoops[L] = L;
 
     for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
       ValueToValueMapTy VMap;
       BasicBlock *New = CloneBasicBlock(*BB, VMap, "." + Twine(It));
       Header->getParent()->insert(BlockInsertPt, New);
 
       assert((*BB != Header || LI->getLoopFor(*BB) == L) &&
              "Header should not be in a sub-loop");
       // Tell LI about New.
       const Loop *OldLoop = addClonedBlockToLoopInfo(*BB, New, LI, NewLoops);
       if (OldLoop)
         LoopsToSimplify.insert(NewLoops[OldLoop]);
 
-      if (*BB == Header)
+      if (*BB == Header) {
         // Loop over all of the PHI nodes in the block, changing them to use
         // the incoming values from the previous block.
         for (PHINode *OrigPHI : OrigPHINode) {
           PHINode *NewPHI = cast<PHINode>(VMap[OrigPHI]);
           Value *InVal = NewPHI->getIncomingValueForBlock(LatchBlock);
           if (Instruction *InValI = dyn_cast<Instruction>(InVal))
             if (It > 1 && L->contains(InValI))
               InVal = LastValueMap[InValI];
           VMap[OrigPHI] = InVal;
           NewPHI->eraseFromParent();
         }
 
+        // Eliminate copies of the loop heart intrinsic, if any.
+        if (ULO.Heart) {
+          auto it = VMap.find(ULO.Heart);
+          assert(it != VMap.end());
+          Instruction *heartCopy = cast<Instruction>(it->second);
+          heartCopy->eraseFromParent();
+          VMap.erase(it);
+        }
+      }
+
       // Update our running map of newest clones
       LastValueMap[*BB] = New;
       for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
            VI != VE; ++VI)
         LastValueMap[VI->first] = VI->second;
 
       // Add phi entries for newly created values to all exit blocks.
       for (BasicBlock *Succ : successors(*BB)) {

llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp

if (OtherExits.size() > 0) {
     // preserve LoopSimplifyForm.
     if (remainderLoop)
       formDedicatedExitBlocks(remainderLoop, DT, LI, nullptr, PreserveLCSSA);
   }
 
   auto UnrollResult = LoopUnrollResult::Unmodified;
   if (remainderLoop && UnrollRemainder) {
     LLVM_DEBUG(dbgs() << "Unrolling remainder loop\n");
-    UnrollResult =
-        UnrollLoop(remainderLoop,
-                   {/*Count*/ Count - 1, /*Force*/ false, /*Runtime*/ false,
-                    /*AllowExpensiveTripCount*/ false,
-                    /*UnrollRemainder*/ false, ForgetAllSCEV},
-                   LI, SE, DT, AC, TTI, /*ORE*/ nullptr, PreserveLCSSA);
+    UnrollLoopOptions ULO;
+    ULO.Count = Count - 1;
+    ULO.Force = false;
+    ULO.Runtime = false;
+    ULO.AllowExpensiveTripCount = false;
+    ULO.UnrollRemainder = false;
+    ULO.ForgetAllSCEV = ForgetAllSCEV;
+    UnrollResult = UnrollLoop(remainderLoop, ULO, LI, SE, DT, AC, TTI,
+                              /*ORE*/ nullptr, PreserveLCSSA);
   }
 
   if (ResultLoop && UnrollResult != LoopUnrollResult::FullyUnrolled)
     *ResultLoop = remainderLoop;
   NumRuntimeUnrolled++;
   return true;
 }

llvm/test/Transforms/LoopUnroll/convergent.controlled.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=loop-unroll -unroll-runtime -unroll-allow-partial -S | FileCheck %s
+
+declare void @f() convergent
+declare void @g()
+
+; Although this loop contains a convergent instruction, it should be
+; fully unrolled.
+define i32 @full_unroll() {
+; CHECK-LABEL: @full_unroll(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       a:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_1:%.*]]
+; CHECK:       a.1:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_2:%.*]]
+; CHECK:       a.2:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %l3
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %a ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 3
+  br label %a
+
+a:
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  br i1 %exitcond, label %exit, label %l3
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction, but it should be partially
+; unrolled.  The unroll count is the largest power of 2 that divides the
+; multiple -- 4, in this case.
+define i32 @runtime_unroll(i32 %n) {
+; CHECK-LABEL: @runtime_unroll(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    [[LOOP_CTL:%.*]] = mul nsw i32 [[N:%.*]], 12
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_3:%.*]], [[A_3:%.*]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       a:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_1:%.*]]
+; CHECK:       a.1:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_2:%.*]]
+; CHECK:       a.2:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_3]]
+; CHECK:       a.3:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[INC_3]] = add nsw i32 [[X_0]], 4
+; CHECK-NEXT:    [[EXITCOND_3:%.*]] = icmp eq i32 [[INC_3]], [[LOOP_CTL]]
+; CHECK-NEXT:    br i1 [[EXITCOND_3]], label [[EXIT:%.*]], label [[L3]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  %loop_ctl = mul nsw i32 %n, 12
+  br label %l3
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %a ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br label %a
+
+a:
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %loop_ctl
+  br i1 %exitcond, label %exit, label %l3
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction, so its partial unroll
+; count must divide its trip multiple.  This overrides its unroll
+; pragma -- we unroll exactly 8 times, even though 16 is requested.
+define i32 @pragma_unroll(i32 %n) {
+; CHECK-LABEL: @pragma_unroll(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    [[LOOP_CTL:%.*]] = mul nsw i32 [[N:%.*]], 24
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_7:%.*]], [[A_7:%.*]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       a:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_1:%.*]]
+; CHECK:       a.1:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_2:%.*]]
+; CHECK:       a.2:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_3:%.*]]
+; CHECK:       a.3:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_4:%.*]]
+; CHECK:       a.4:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_5:%.*]]
+; CHECK:       a.5:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_6:%.*]]
+; CHECK:       a.6:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    br label [[A_7]]
+; CHECK:       a.7:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[INC_7]] = add nsw i32 [[X_0]], 8
+; CHECK-NEXT:    [[EXITCOND_7:%.*]] = icmp eq i32 [[INC_7]], [[LOOP_CTL]]
+; CHECK-NEXT:    br i1 [[EXITCOND_7]], label [[EXIT:%.*]], label [[L3]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  %loop_ctl = mul nsw i32 %n, 24
+  br label %l3, !llvm.loop !0
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %a ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  br label %a
+
+a:
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %loop_ctl
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !0
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction. Since the pragma loop unroll
+; count 2 divides trip count 4. The loop unroll should respect the pragma.
+define void @pragma_unroll_divisible_trip_count() {
+; CHECK-LABEL: @pragma_unroll_divisible_trip_count(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4:![0-9]+]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_1:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[INC_1]] = add nuw nsw i32 [[X_0]], 2
+; CHECK-NEXT:    [[EXITCOND_1:%.*]] = icmp eq i32 [[INC_1]], 4
+; CHECK-NEXT:    br i1 [[EXITCOND_1]], label [[EXIT:%.*]], label [[L3]], !llvm.loop [[LOOP6:![0-9]+]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  ret void
+}
+
+; This loop contains a convergent instruction. Since the pragma loop unroll
+; count 2 divides trip multiple 2. The loop unroll should respect the pragma.
+define i32 @pragma_unroll_divisible_trip_multiple(i32 %n) {
+; CHECK-LABEL: @pragma_unroll_divisible_trip_multiple(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    [[LOOP_CTL:%.*]] = mul nsw i32 [[N:%.*]], 2
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_1:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[INC_1]] = add nsw i32 [[X_0]], 2
+; CHECK-NEXT:    [[EXITCOND_1:%.*]] = icmp eq i32 [[INC_1]], [[LOOP_CTL]]
+; CHECK-NEXT:    br i1 [[EXITCOND_1]], label [[EXIT:%.*]], label [[L3]], !llvm.loop [[LOOP7:![0-9]+]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  %loop_ctl = mul nsw i32 %n, 2
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %loop_ctl
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction. Since the pragma loop unroll
+; count 2 is unknown to divide runtime trip count, the loop is not unrolled
+; since remainder is forbidden for unrolling convergent loop.
+define i32 @pragma_unroll_indivisible_runtime_trip_count(i32 %n) {
+; CHECK-LABEL: @pragma_unroll_indivisible_runtime_trip_count(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[X_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[L3]], !llvm.loop [[LOOP4]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %n
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction. Since the pragma loop unroll
+; count 2 does not divide trip count 5, the loop is not unrolled by 2
+; since remainder is forbidden for unrolling convergent loop. Instead, the
+; loop gets fully unrolled.
+define i32 @pragma_unroll_indivisible_trip_count() {
+; CHECK-LABEL: @pragma_unroll_indivisible_trip_count(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[ANCHOR:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token [[ANCHOR]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %anchor = call token @llvm.experimental.convergence.anchor()
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.loop() [ "convergencectrl"(token %anchor) ]
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 5
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  ret i32 0
+}
+
+; This loop contains a convergent instruction that is anchored inside the loop
+; itself. It is unrolled by 2 with remainder, as requested by the loop metadata.
+define i32 @pragma_unroll_with_remainder(i32 %n) {
+; CHECK-LABEL: @pragma_unroll_with_remainder(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = freeze i32 [[N:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[TMP0]], -1
+; CHECK-NEXT:    [[XTRAITER:%.*]] = and i32 [[TMP0]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i32 [[TMP1]], 1
+; CHECK-NEXT:    br i1 [[TMP2]], label [[EXIT_UNR_LCSSA:%.*]], label [[ENTRY_NEW:%.*]]
+; CHECK:       entry.new:
+; CHECK-NEXT:    [[UNROLL_ITER:%.*]] = sub i32 [[TMP0]], [[XTRAITER]]
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY_NEW]] ], [ [[INC_1:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[NITER:%.*]] = phi i32 [ 0, [[ENTRY_NEW]] ], [ [[NITER_NEXT_1:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    [[TOK_LOOP_1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP_1]]) ]
+; CHECK-NEXT:    [[INC_1]] = add nsw i32 [[X_0]], 2
+; CHECK-NEXT:    [[NITER_NEXT_1]] = add i32 [[NITER]], 2
+; CHECK-NEXT:    [[NITER_NCMP_1:%.*]] = icmp eq i32 [[NITER_NEXT_1]], [[UNROLL_ITER]]
+; CHECK-NEXT:    br i1 [[NITER_NCMP_1]], label [[EXIT_UNR_LCSSA_LOOPEXIT:%.*]], label [[L3]], !llvm.loop [[LOOP8:![0-9]+]]
+; CHECK:       exit.unr-lcssa.loopexit:
+; CHECK-NEXT:    br label [[EXIT_UNR_LCSSA]]
+; CHECK:       exit.unr-lcssa:
+; CHECK-NEXT:    [[LCMP_MOD:%.*]] = icmp ne i32 [[XTRAITER]], 0
+; CHECK-NEXT:    br i1 [[LCMP_MOD]], label [[L3_EPIL_PREHEADER:%.*]], label [[EXIT:%.*]]
+; CHECK:       l3.epil.preheader:
+; CHECK-NEXT:    br label [[L3_EPIL:%.*]]
+; CHECK:       l3.epil:
+; CHECK-NEXT:    [[TOK_LOOP_EPIL:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP_EPIL]]) ]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.anchor()
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %n
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  ret i32 0
+}
+
+; Don't unroll a loop that is extended by convergence controls.
+;
+; We could theoretically duplicate the extension part, but this is not
+; implemented.
+define i32 @extended_loop(i32 %n) {
+; CHECK-LABEL: @extended_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[L3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[L3]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[X_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], [[N:%.*]]
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[L3]], !llvm.loop [[LOOP4]]
+; CHECK:       exit:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_LOOP]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %l3, !llvm.loop !1
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %l3 ]
+  %tok.loop = call token @llvm.experimental.convergence.anchor()
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, %n
+  br i1 %exitcond, label %exit, label %l3, !llvm.loop !1
+
+exit:
+  call void @f() [ "convergencectrl"(token %tok.loop) ]
+  ret i32 0
+}
+
+; Inner loop is extended beyond the outer loop. No unrolling possible.
+
+define i32 @extended_inner_loop_1(i32 %n, i1 %cond) {
+; CHECK-LABEL: @extended_inner_loop_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       l3:
+; CHECK-NEXT:    [[X_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    [[TOK_LOOP:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    [[INC]] = add nsw i32 [[X_0]], 1
+; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp eq i32 [[INC]], 4
+; CHECK-NEXT:    br label [[L2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2:
+; CHECK-NEXT:    [[TOK_L2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2]]) ]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[L2]], label [[LATCH]], !llvm.loop [[LOOP4]]
+; CHECK:       latch:
+; CHECK-NEXT:    br i1 [[EXITCOND]], label [[EXIT:%.*]], label [[L3]]
+; CHECK:       exit:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %l3
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %latch ]
+  %tok.loop = call token @llvm.experimental.convergence.anchor()
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br label %l2, !llvm.loop !1
+
+l2:
+  %tok.l2 = call token @llvm.experimental.convergence.anchor()
+  call void @f() [ "convergencectrl"(token %tok.l2) ]
+  br i1 %cond, label %l2, label %latch, !llvm.loop !1
+
+latch:
+  br i1 %exitcond, label %exit, label %l3
+
+exit:
+  call void @f() [ "convergencectrl"(token %tok.l2) ]
+  ret i32 0
+}
+
+; Inner loop is extended inside the outer loop. Outer loop is unrolled.
+
+define i32 @extended_inner_loop_2(i32 %n, i1 %cond) {
+; CHECK-LABEL: @extended_inner_loop_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       l3:
+; CHECK-NEXT:    br label [[L2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2:
+; CHECK-NEXT:    [[TOK_L2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2]]) ]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[L2]], label [[LATCH:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       latch:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2]]) ]
+; CHECK-NEXT:    br label [[L2_1:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.1:
+; CHECK-NEXT:    [[TOK_L2_1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_1]], label [[LATCH_1:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       latch.1:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1]]) ]
+; CHECK-NEXT:    br label [[L2_2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.2:
+; CHECK-NEXT:    [[TOK_L2_2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_2]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_2]], label [[LATCH_2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       latch.2:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_2]]) ]
+; CHECK-NEXT:    br label [[L2_3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.3:
+; CHECK-NEXT:    [[TOK_L2_3:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_3]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_3]], label [[LATCH_3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       latch.3:
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_3]]) ]
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %l3
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %latch ]
+  %tok.loop = call token @llvm.experimental.convergence.anchor()
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br label %l2, !llvm.loop !1
+
+l2:
+  %tok.l2 = call token @llvm.experimental.convergence.anchor()
+  call void @f() [ "convergencectrl"(token %tok.l2) ]
+  br i1 %cond, label %l2, label %latch, !llvm.loop !1
+
+latch:
+  call void @f() [ "convergencectrl"(token %tok.l2) ]
+  br i1 %exitcond, label %exit, label %l3
+
+exit:
+  ret i32 0
+}
+
+; No extension. Both loops unrolled.
+
+define i32 @unroll_nest(i32 %n, i1 %cond) {
+; CHECK-LABEL: @unroll_nest(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       l3:
+; CHECK-NEXT:    br label [[L2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2:
+; CHECK-NEXT:    [[TOK_L2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2]]) ]
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[L2_1:%.*]], label [[LATCH:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.1:
+; CHECK-NEXT:    [[TOK_L2_1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2]], label [[LATCH]], !llvm.loop [[LOOP9:![0-9]+]]
+; CHECK:       latch:
+; CHECK-NEXT:    br label [[L2_12:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.12:
+; CHECK-NEXT:    [[TOK_L2_11:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_11]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_1_1:%.*]], label [[LATCH_1:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.1.1:
+; CHECK-NEXT:    [[TOK_L2_1_1:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1_1]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_12]], label [[LATCH_1]], !llvm.loop [[LOOP9]]
+; CHECK:       latch.1:
+; CHECK-NEXT:    br label [[L2_2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.2:
+; CHECK-NEXT:    [[TOK_L2_2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_2]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_1_2:%.*]], label [[LATCH_2:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.1.2:
+; CHECK-NEXT:    [[TOK_L2_1_2:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1_2]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_2]], label [[LATCH_2]], !llvm.loop [[LOOP9]]
+; CHECK:       latch.2:
+; CHECK-NEXT:    br label [[L2_3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.3:
+; CHECK-NEXT:    [[TOK_L2_3:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_3]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_1_3:%.*]], label [[LATCH_3:%.*]], !llvm.loop [[LOOP4]]
+; CHECK:       l2.1.3:
+; CHECK-NEXT:    [[TOK_L2_1_3:%.*]] = call token @llvm.experimental.convergence.anchor()
+; CHECK-NEXT:    call void @f() [ "convergencectrl"(token [[TOK_L2_1_3]]) ]
+; CHECK-NEXT:    br i1 [[COND]], label [[L2_3]], label [[LATCH_3]], !llvm.loop [[LOOP9]]
+; CHECK:       latch.3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %l3
+
+l3:
+  %x.0 = phi i32 [ 0, %entry ], [ %inc, %latch ]
+  %tok.loop = call token @llvm.experimental.convergence.anchor()
+  %inc = add nsw i32 %x.0, 1
+  %exitcond = icmp eq i32 %inc, 4
+  br label %l2, !llvm.loop !1
+
+l2:
+  %tok.l2 = call token @llvm.experimental.convergence.anchor()
+  call void @f() [ "convergencectrl"(token %tok.l2) ]
+  br i1 %cond, label %l2, label %latch, !llvm.loop !1
+
+latch:
+  br i1 %exitcond, label %exit, label %l3
+
+exit:
+  ret i32 0
+}
+
+declare token @llvm.experimental.convergence.anchor()
+declare token @llvm.experimental.convergence.loop()
+
+!0 = !{!0, !{!"llvm.loop.unroll.count", i32 16}}
+!1 = !{!1, !{!"llvm.loop.unroll.count", i32 2}}