[RFC][GlobalISel] convergence control tokens and intrinsics

[sameerds]

Summary

This is an early attempt and a call for feedback on adding support in GlobalISel
for convergence control tokens:

• IRTranslator converts LLVM token type to LLT::token(), which is an alias for the s0 type. These show up as implicit uses on convergent operations.
• Legalizer removes all implicit uses of convergence control tokens, since they are not meant to be translated to actual target instructions.
• Machine verifier enforces the static rules of convergence control.

[arsenm]

llvm/lib/CodeGen/GlobalISel/CallLowering.cpp

91

isEntryConvergenceToken

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

212–213

I think you should just bypass this assert, you're creating one special case that doesn't benefit from any of the type logic here

2463

Just directly create the token vreg

[arsenm]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

133

Verifier should reject debug uses of tokens

[arsenm]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

122–140

Wait, why is this here? Generic intrinsics shouldn't reach the legalizer, they should go through G_* instruction wrappers. If your intention was to default legalize to erase, those should be just in the default lower action

[sameerds]

• rebased
• addressed some review comments
• added machine verifier

[sameerds]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

2463

I didn't understand. In the LLVM IR, this is a token use, and the token definition was elsewhere. We still need to find that existing register, right?

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

122–140

I don't understand, mostly because I am quite unfamiliar with the backend. But in GlobalISel.cpp, the legalizer comes before selection. So this definitely hits the legalizer? By "default lower action", you mean somewhere in InstructionSelect::runOnMachineFunction() before it calls the target-specific virtual function InstructionSelector::select()?

133

The verifier (see the new patch) rejects any uses other than a call or an intrinsic.

[sameerds]

Bump! Waiting for more info on comments from @arsenm

[arsenm]

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

2463

Yes, you still need to update the map entry. But you don't need to go through the full getOrCreateVregs with all of the type handling

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

122–140

The legalizer shouldn't need to specially intercept intrinsics. A generic intrinsic should not pass the IRTranslator. These should be swapped to new G_* instructions which the ordinary legalizer can express rules. The default lower action for them can be to just erase (or we can let these pass to selection)

[sameerds]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

122–140

The legalizer shouldn't need to specially intercept intrinsics. A generic intrinsic should not pass the IRTranslator.

That is confusing still. Isn't MachineIRBuilder::buildIntrinsic() how LLVM IR intrinsics get translated to G_INTRINSIC instances in GMIR?

These should be swapped to new G_* instructions which the ordinary legalizer can express rules. The default lower action for them can be to just erase (or we can let these pass to selection)

What I am looking for is a place that is common to all targets, where the convergence control intrinsics can be erased just before or during selection. Until that point, the G_INTRINSIC instances of the convergence control intrinsics is how tokens are produced in GMIR. The legalizer is very close to such a point. Why is it that the legalizer can express rules for G_* opcodes but not generic intrinsics?

Separately, I don't think there is value in creating new G_* opcodes for these intrinsics (yet).

[sameerds]

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

122–140

That is confusing still.

What I am looking for is a place that is common to all targets, where the convergence control intrinsics can be erased just before or during selection. Until that point, the G_INTRINSIC instances of the convergence control intrinsics is how tokens are produced in GMIR. The legalizer is very close to such a point. Why is it that the legalizer can express rules for G_* opcodes but not generic intrinsics?

Never mind! I spent some time looking at how GlobalISel works with help from @cdevadas , and I think I have some idea of what to do with tokens.

llvm/include/llvm/CodeGen/GlobalISel/CallLowering.h

struct CallLoweringInfo {
 
     /// List of descriptors of the arguments passed to the function.
     SmallVector<ArgInfo, 32> OrigArgs;
 
     /// Valid if the call has a swifterror inout parameter, and contains the
     /// vreg that the swifterror should be copied into after the call.
     Register SwiftErrorVReg;
 
+    Register ConvergenceCtrlToken;
+
     /// Original IR callsite corresponding to this call, if available.
     const CallBase *CB = nullptr;
 
     MDNode *KnownCallees = nullptr;
 
     /// True if the call must be tail call optimized.
     bool IsMustTailCall = false;
 
public:
   /// the target determines it cannot jump to the destination based purely on \p
   /// CI. This might be because \p CI is indirect, or because of the limited
   /// range of an immediate jump.
   ///
   /// \return true if the lowering succeeded, false otherwise.
   bool lowerCall(MachineIRBuilder &MIRBuilder, const CallBase &Call,
                  ArrayRef<Register> ResRegs,
                  ArrayRef<ArrayRef<Register>> ArgRegs, Register SwiftErrorVReg,
+                 Register ConvergenceCtrlToken,
                  std::function<unsigned()> GetCalleeReg) const;
 
   /// For targets which want to use big-endian can enable it with
   /// enableBigEndian() hook
   virtual bool enableBigEndian() const { return false; }
 
   /// For targets which support the "returned" parameter attribute, returns
   /// true if the given type is a valid one to use with "returned".
   virtual bool isTypeIsValidForThisReturn(EVT Ty) const { return false; }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_GLOBALISEL_CALLLOWERING_H

llvm/include/llvm/CodeGen/LowLevelType.h

 //== llvm/CodeGen/LowLevelType.h ------------------------------- -*- 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
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// Implement a low-level type suitable for MachineInstr level instruction

 public:
   /// Get a low-level scalar or aggregate "bag of bits".
   static constexpr LLT scalar(unsigned SizeInBits) {
     return LLT{/*isPointer=*/false, /*isVector=*/false, /*isScalar=*/true,
                ElementCount::getFixed(0), SizeInBits,
                /*AddressSpace=*/0};
   }
 
+  /// Get a low-level token; just a scalar with zero bits (or no size).
+  static constexpr LLT token() {
+    return LLT{/*isPointer=*/false,
+               /*isVector=*/false,
+               /*isScalar=*/true,
+               ElementCount::getFixed(0),
+               0,
+               /*AddressSpace=*/0};
+  }
+
   /// Get a low-level pointer in the given address space.
   static constexpr LLT pointer(unsigned AddressSpace, unsigned SizeInBits) {
     assert(SizeInBits > 0 && "invalid pointer size");
     return LLT{/*isPointer=*/true, /*isVector=*/false, /*isScalar=*/false,
                ElementCount::getFixed(0), SizeInBits, AddressSpace};
   }
 
   /// Get a low-level vector of some number of elements and element width.
private:
   /// isPointer : 1
   /// isVector  : 1
   /// with 61 bits remaining for Kind-specific data, packed in bitfields
   /// as described below. As there isn't a simple portable way to pack bits
   /// into bitfields, here the different fields in the packed structure is
   /// described in static const *Field variables. Each of these variables
   /// is a 2-element array, with the first element describing the bitfield size
   /// and the second element describing the bitfield offset.
+  ///
+  /// +--------+---------+--------+----------+----------------------+
+  /// |isScalar|isPointer|isVector| RawData  |Notes                 |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    0    |   0    |    0     |Invalid               |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    0    |   1    |    0     |Tombstone Key         |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    1    |   0    |    0     |Empty Key             |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   1    |    0    |   0    |    0     |Token                 |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   1    |    0    |   0    | non-zero |Scalar                |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    1    |   0    | non-zero |Pointer               |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    0    |   1    | non-zero |Vector of non-pointer |
+  /// +--------+---------+--------+----------+----------------------+
+  /// |   0    |    1    |   1    | non-zero |Vector of pointer     |
+  /// +--------+---------+--------+----------+----------------------+
+  ///
+  /// Everything else is reserved.
   typedef int BitFieldInfo[2];
   ///
   /// This is how the bitfields are packed per Kind:
   /// * Invalid:
   ///   gets encoded as RawData == 0, as that is an invalid encoding, since for
   ///   valid encodings, SizeInBits/SizeOfElement must be larger than 0.
   /// * Non-pointer scalar (isPointer == 0 && isVector == 0):
   ///   SizeInBits: 32;

llvm/include/llvm/CodeGen/MachineConvergenceVerifier.h

+//===- MachineConvergenceVerifier.h - Verify convergenctrl ------*- 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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This file declares the GMIR IR specialization of the
+/// GenericConvergenceVerifier template.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_MACHINECONVERGENCEVERIFIER_H
+#define LLVM_CODEGEN_MACHINECONVERGENCEVERIFIER_H
+
+#include "llvm/ADT/GenericConvergenceVerifier.h"
+#include "llvm/CodeGen/MachineSSAContext.h"
+
+namespace llvm {
+
+using MachineConvergenceVerifier =
+    GenericConvergenceVerifier<MachineSSAContext>;
+
+} // namespace llvm
+
+#endif // LLVM_CODEGEN_MACHINECONVERGENCEVERIFIER_H

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   LowLevelTypeUtils.cpp
   LowerEmuTLS.cpp
   MachineBasicBlock.cpp
   MachineBlockFrequencyInfo.cpp
   MachineBlockPlacement.cpp
   MachineBranchProbabilityInfo.cpp
   MachineCFGPrinter.cpp
   MachineCombiner.cpp
+  MachineConvergenceVerifier.cpp
   MachineCopyPropagation.cpp
   MachineCSE.cpp
   MachineCheckDebugify.cpp
   MachineCycleAnalysis.cpp
   MachineDebugify.cpp
   MachineDominanceFrontier.cpp
   MachineDominators.cpp
   MachineFrameInfo.cpp

llvm/lib/CodeGen/GlobalISel/CallLowering.cpp

 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Target/TargetMachine.h"
 
 #define DEBUG_TYPE "call-lowering"
 
 using namespace llvm;
 

 void CallLowering::addArgFlagsFromAttributes(ISD::ArgFlagsTy &Flags,
                                              const AttributeList &Attrs,
                                              unsigned OpIdx) const {
   addFlagsUsingAttrFn(Flags, [&Attrs, &OpIdx](Attribute::AttrKind Attr) {
     return Attrs.hasAttributeAtIndex(OpIdx, Attr);
   });
 }
 
+static bool hasConvergenceEntryToken(const CallBase &CB) {
+  auto Bundle = CB.getOperandBundle(LLVMContext::OB_convergencectrl);
+  if (!Bundle)
+    return true;
+  auto *Token = Bundle->Inputs[0].get();
+  auto *Def = cast<IntrinsicInst>(Token);
+  return Def->getIntrinsicID() == Intrinsic::experimental_convergence_entry;
+}
+
 bool CallLowering::lowerCall(MachineIRBuilder &MIRBuilder, const CallBase &CB,
                              ArrayRef<Register> ResRegs,
                              ArrayRef<ArrayRef<Register>> ArgRegs,
                              Register SwiftErrorVReg,
+                             Register ConvergenceCtrlToken,
                              std::function<unsigned()> GetCalleeReg) const {
   CallLoweringInfo Info;
   const DataLayout &DL = MIRBuilder.getDataLayout();
   MachineFunction &MF = MIRBuilder.getMF();
   MachineRegisterInfo &MRI = MF.getRegInfo();
   bool CanBeTailCalled = CB.isTailCall() &&
                          isInTailCallPosition(CB, MF.getTarget()) &&
                          (MF.getFunction()
if (!Info.CanLowerReturn) {
     // Callee requires sret demotion.
     insertSRetOutgoingArgument(MIRBuilder, CB, Info);
 
     // The sret demotion isn't compatible with tail-calls, since the sret
     // argument points into the caller's stack frame.
     CanBeTailCalled = false;
   }
 
+  if (!hasConvergenceEntryToken(CB))
+    CanBeTailCalled = false;
 
   // First step is to marshall all the function's parameters into the correct
   // physregs and memory locations. Gather the sequence of argument types that
   // we'll pass to the assigner function.
   unsigned i = 0;
   unsigned NumFixedArgs = CB.getFunctionType()->getNumParams();
   for (const auto &Arg : CB.args()) {
     ArgInfo OrigArg{ArgRegs[i], *Arg.get(), i, getAttributesForArgIdx(CB, i),
if (Bundle && CB.isIndirectCall()) {
     Info.CFIType = cast<ConstantInt>(Bundle->Inputs[0]);
     assert(Info.CFIType->getType()->isIntegerTy(32) && "Invalid CFI type");
   }
 
   Info.CB = &CB;
   Info.KnownCallees = CB.getMetadata(LLVMContext::MD_callees);
   Info.CallConv = CallConv;
   Info.SwiftErrorVReg = SwiftErrorVReg;
+  Info.ConvergenceCtrlToken = ConvergenceCtrlToken;
   Info.IsMustTailCall = CB.isMustTailCall();
   Info.IsTailCall = CanBeTailCalled;
   Info.IsVarArg = IsVarArg;
   if (!lowerCall(MIRBuilder, Info))
     return false;
 
   if (ReturnHintAlignReg && !Info.IsTailCall) {
     MIRBuilder.buildAssertAlign(ResRegs[0], ReturnHintAlignReg,

llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp

if (VRegsIt != VMap.vregs_end())
     return *VRegsIt->second;
 
   if (Val.getType()->isVoidTy())
     return *VMap.getVRegs(Val);
 
   // Create entry for this type.
   auto *VRegs = VMap.getVRegs(Val);
   auto *Offsets = VMap.getOffsets(Val);
 
+  if (!Val.getType()->isTokenTy())
     assert(Val.getType()->isSized() &&
            "Don't know how to create an empty vreg");
 
   SmallVector<LLT, 4> SplitTys;
   computeValueLLTs(*DL, *Val.getType(), SplitTys,
                    Offsets->empty() ? Offsets : nullptr);
 
   if (!isa<Constant>(Val)) {
     for (auto Ty : SplitTys)
       VRegs->push_back(MRI->createGenericVirtualRegister(Ty));
if (auto *CI = dyn_cast<CallInst>(&CB)) {
     if (ORE->enabled()) {
       if (MemoryOpRemark::canHandle(CI, *LibInfo)) {
         MemoryOpRemark R(*ORE, "gisel-irtranslator-memsize", *DL, *LibInfo);
         R.visit(CI);
       }
     }
   }
 
+  Register ConvergenceCtrlToken = 0;
+  if (auto Bundle = CB.getOperandBundle(LLVMContext::OB_convergencectrl)) {
+    auto *Token = Bundle->Inputs[0].get();
+    ConvergenceCtrlToken = getOrCreateVReg(*Token);
+  }
+
   // We don't set HasCalls on MFI here yet because call lowering may decide to
   // optimize into tail calls. Instead, we defer that to selection where a final
   // scan is done to check if any instructions are calls.
-  bool Success =
-      CLI->lowerCall(MIRBuilder, CB, Res, Args, SwiftErrorVReg,
-                     [&]() { return getOrCreateVReg(*CB.getCalledOperand()); });
+  bool Success = CLI->lowerCall(
+      MIRBuilder, CB, Res, Args, SwiftErrorVReg, ConvergenceCtrlToken,
 
   // Check if we just inserted a tail call.
   if (Success) {
     assert(!HasTailCall && "Can't tail call return twice from block?");
     const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
     HasTailCall = TII->isTailCall(*std::prev(MIRBuilder.getInsertPt()));
   }
 
if (TII && ID == Intrinsic::not_intrinsic)
       ID = static_cast<Intrinsic::ID>(TII->getIntrinsicID(F));
   }
 
   if (!F || !F->isIntrinsic() || ID == Intrinsic::not_intrinsic)
     return translateCallBase(CI, MIRBuilder);
 
   assert(ID != Intrinsic::not_intrinsic && "unknown intrinsic");
 
-  if (translateKnownIntrinsic(CI, ID, MIRBuilder))
+  // Note: Known intrinsics are target-independent, and not expected to be
+  // convergent. Hence we don't look for a convergencectrl operand bundle if we
+  // are calling a known intrinsic.
+  if (translateKnownIntrinsic(CI, ID, MIRBuilder)) {
+    assert(!CI.countOperandBundlesOfType(LLVMContext::OB_convergencectrl));
     return true;
+  }
 
   ArrayRef<Register> ResultRegs;
   if (!CI.getType()->isVoidTy())
     ResultRegs = getOrCreateVRegs(CI);
 
   // Ignore the callsite attributes. Backend code is most likely not expecting
   // an intrinsic to sometimes have side effects and sometimes not.
   MachineInstrBuilder MIB = MIRBuilder.buildIntrinsic(ID, ResultRegs);
if (TLI.getTgtMemIntrinsic(Info, CI, *MF, ID)) {
     if (Info.ptrVal)
       MPI = MachinePointerInfo(Info.ptrVal, Info.offset);
     else if (Info.fallbackAddressSpace)
       MPI = MachinePointerInfo(*Info.fallbackAddressSpace);
     MIB.addMemOperand(
         MF->getMachineMemOperand(MPI, Info.flags, MemTy, Alignment, CI.getAAMetadata()));
   }
 
+  if (CI.isConvergent()) {
+    if (auto Bundle = CI.getOperandBundle(LLVMContext::OB_convergencectrl)) {
+      auto *Token = Bundle->Inputs[0].get();
+      Register TokenReg = getOrCreateVReg(*Token);
+      MIB.addUse(TokenReg, RegState::Implicit);
+    }
+  }
+
   return true;
 }
 
 bool IRTranslator::findUnwindDestinations(
     const BasicBlock *EHPadBB,
     BranchProbability Prob,
     SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
         &UnwindDests) {

llvm/lib/CodeGen/GlobalISel/InlineAsmLowering.cpp

case InlineAsm::isClobber: {
                                getImplRegState(Reg.isPhysical()));
         }
       }
       break;
     }
     }
   }
 
+  if (auto Bundle = Call.getOperandBundle(LLVMContext::OB_convergencectrl)) {
+    auto *Token = Bundle->Inputs[0].get();
+    ArrayRef<Register> SourceRegs = GetOrCreateVRegs(*Token);
+    assert(SourceRegs.size() == 1 &&
+           "Expected the control token to fit into a single virtual register");
+    Inst.addUse(SourceRegs[0], RegState::Implicit);
+  }
+
   if (const MDNode *SrcLoc = Call.getMetadata("srcloc"))
     Inst.addMetadata(SrcLoc);
 
   // All inputs are handled, insert the instruction now
   MIRBuilder.insertInstr(Inst);
 
   // Finally, copy the output operands into the output registers
   ArrayRef<Register> ResRegs = GetOrCreateVRegs(Call);

llvm/lib/CodeGen/GlobalISel/LegalizerHelper.cpp

 
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI,
                                    LostDebugLocObserver &LocObserver) {
   LLVM_DEBUG(dbgs() << "Legalizing: " << MI);
 
   MIRBuilder.setInstrAndDebugLoc(MI);
 
-  if (isa<GIntrinsic>(MI))
+  if (auto *GI = dyn_cast<GIntrinsic>(&MI)) {
+    auto ID = GI->getIntrinsicID();
+    assert(ID != Intrinsic::not_intrinsic);
+    switch (ID) {
+    default:
+      break;
+    case Intrinsic::experimental_convergence_anchor:
+    case Intrinsic::experimental_convergence_entry:
+    case Intrinsic::experimental_convergence_loop:
+      assert(MI.getNumDefs() == 1);
+      Register Token = MI.defs().begin()->getReg();
+      for (auto &Use : MRI.use_operands(Token)) {
+        auto *UserInstr = Use.getParent();
+        UserInstr->removeOperand(Use.getOperandNo());
+      }
+      MI.eraseFromParent();
+      return Legalized;
+    }
+
     return LI.legalizeIntrinsic(*this, MI) ? Legalized : UnableToLegalize;
+  }
   auto Step = LI.getAction(MI, MRI);
   switch (Step.Action) {
   case Legal:
     LLVM_DEBUG(dbgs() << ".. Already legal\n");
     return AlreadyLegal;
   case Libcall:
     LLVM_DEBUG(dbgs() << ".. Convert to libcall\n");
     return libcall(MI, LocObserver);

llvm/lib/CodeGen/LowLevelTypeUtils.cpp

LLT llvm::getLLTForType(Type &Ty, const DataLayout &DL) {
   if (Ty.isSized() && !Ty.isScalableTargetExtTy()) {
     // Aggregates are no different from real scalars as far as GlobalISel is
     // concerned.
     auto SizeInBits = DL.getTypeSizeInBits(&Ty);
     assert(SizeInBits != 0 && "invalid zero-sized type");
     return LLT::scalar(SizeInBits);
   }
 
+  if (Ty.isTokenTy()) {
+    return LLT::token();
+  }
+
   return LLT();
 }
 
 MVT llvm::getMVTForLLT(LLT Ty) {
   if (!Ty.isVector())
     return MVT::getIntegerVT(Ty.getSizeInBits());
 
   return MVT::getVectorVT(

llvm/lib/CodeGen/MIRParser/MIParser.cpp

bool MIParser::parseLowLevelType(StringRef::iterator Loc, LLT &Ty) {
   if (Token.range().front() == 's' || Token.range().front() == 'p') {
     StringRef SizeStr = Token.range().drop_front();
     if (SizeStr.size() == 0 || !llvm::all_of(SizeStr, isdigit))
       return error("expected integers after 's'/'p' type character");
   }
 
   if (Token.range().front() == 's') {
     auto ScalarSize = APSInt(Token.range().drop_front()).getZExtValue();
+    if (ScalarSize) {
       if (!verifyScalarSize(ScalarSize))
         return error("invalid size for scalar type");
-
       Ty = LLT::scalar(ScalarSize);
+    } else {
+      Ty = LLT::token();
+    }
     lex();
     return false;
   } else if (Token.range().front() == 'p') {
     const DataLayout &DL = MF.getDataLayout();
     uint64_t AS = APSInt(Token.range().drop_front()).getZExtValue();
     if (!verifyAddrSpace(AS))
       return error("invalid address space number");
 
if (Token.range().front() != 's' && Token.range().front() != 'p')
     return error(Loc, "expected <M x sN> or <M x pA> for vector type");
   StringRef SizeStr = Token.range().drop_front();
   if (SizeStr.size() == 0 || !llvm::all_of(SizeStr, isdigit))
     return error("expected integers after 's'/'p' type character");
 
   if (Token.range().front() == 's') {
     auto ScalarSize = APSInt(Token.range().drop_front()).getZExtValue();
     if (!verifyScalarSize(ScalarSize))
-      return error("invalid size for scalar type");
+      return error("invalid size for scalar element in vector");
     Ty = LLT::scalar(ScalarSize);
   } else if (Token.range().front() == 'p') {
     const DataLayout &DL = MF.getDataLayout();
     uint64_t AS = APSInt(Token.range().drop_front()).getZExtValue();
     if (!verifyAddrSpace(AS))
       return error("invalid address space number");
 
     Ty = LLT::pointer(AS, DL.getPointerSizeInBits(AS));

llvm/lib/CodeGen/MachineConvergenceVerifier.cpp

+//===- ConvergenceVerifier.cpp - Verify convergence control -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/MachineConvergenceVerifier.h"
+#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineSSAContext.h"
+#include "llvm/IR/GenericConvergenceVerifierImpl.h"
+
+using namespace llvm;
+
+template <>
+const MachineInstr *
+GenericConvergenceVerifier<MachineSSAContext>::findAndCheckConvergenceTokenUsed(
+    const MachineInstr &MI) {
+  auto &MRI = Context.getFunction()->getRegInfo();
+  const MachineInstr *TokenDef = nullptr;
+
+  for (auto &MO : MI.uses()) {
+    if (!MO.isReg())
+      continue;
+
+    const auto RegTy = MRI.getType(MO.getReg());
+    if (RegTy != LLT::token())
+      continue;
+
+    // A token type operand is a convergence control token iff its unique
+    // definition is a convergence control intrinsic. We can't really verify
+    // that since the token type may have other implicit uses. Instead we use it
+    // as a way to identify convergence control token operands.
+    const auto *Def = MRI.getUniqueVRegDef(MO.getReg());
+    if (!Def)
+      continue;
+    if (!isConvergenceControlIntrinsic(MachineSSAContext::getIntrinsicID(*Def)))
+      continue;
+
+    CheckOrNull(MI.isCall() || isa<GIntrinsic>(MI),
+                "Convergence control tokens can only be used by call "
+                "instructions or intrinsics.",
+                {Context.print(MO.getReg()), Context.print(&MI)});
+
+    CheckOrNull(MO.isImplicit(),
+                "Convergence control tokens can only be used implicitly.",
+                {Context.print(MO.getReg()), Context.print(&MI)});
+
+    CheckOrNull(!TokenDef,
+                "A call can use at most one convergence control token.",
+                {Context.print(MO.getReg()), Context.print(&MI)});
+
+    TokenDef = Def;
+  }
+
+  if (TokenDef)
+    Tokens[&MI] = TokenDef;
+
+  return TokenDef;
+}
+
+template <>
+bool GenericConvergenceVerifier<MachineSSAContext>::isInsideConvergentFunction(
+    const MachineInstr &MI) {
+  // The class MachineFunction does not have any property to indicate whether it
+  // is convergent. Trivially return true so that the check always passes.
+  return true;
+}
+template <>
+bool GenericConvergenceVerifier<MachineSSAContext>::isConvergent(
+    const MachineInstr &MI) {
+  return MI.isConvergent();
+}
+
+template class llvm::GenericConvergenceVerifier<MachineSSAContext>;

llvm/lib/CodeGen/MachineVerifier.cpp

 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/LiveIntervals.h"
 #include "llvm/CodeGen/LiveRangeCalc.h"
 #include "llvm/CodeGen/LiveStacks.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/LowLevelType.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineConvergenceVerifier.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineInstrBundle.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
struct MachineVerifier {
     }
 
     // Analysis information if available
     LiveVariables *LiveVars = nullptr;
     LiveIntervals *LiveInts = nullptr;
     LiveStacks *LiveStks = nullptr;
     SlotIndexes *Indexes = nullptr;
 
+    // This is calculated only when trying to verify convergence control tokens.
+    // Similar to the LLVM IR verifier, we calculate this locally instead of
+    // relying on the pass manager.
+    MachineDomTree DT;
+
     void visitMachineFunctionBefore();
     void visitMachineBasicBlockBefore(const MachineBasicBlock *MBB);
     void visitMachineBundleBefore(const MachineInstr *MI);
 
     /// Verify that all of \p MI's virtual register operands are scalars.
     /// \returns True if all virtual register operands are scalar. False
     /// otherwise.
     bool verifyAllRegOpsScalar(const MachineInstr &MI,
if (MInfo.reachable) {
           errs() << printMBBReference(*Pred)
                  << " is a predecessor according to the CFG.\n";
         }
       }
     }
   }
 }
 
+static void
+verifyConvergenceControl(const MachineFunction &MF, MachineDomTree &DT,
+                         std::function<void(const Twine &Message)> FailureCB) {
+  MachineConvergenceVerifier CV;
+  CV.initialize(&errs(), FailureCB, MF);
+
+  if (MF.getProperties().hasProperty(
+          MachineFunctionProperties::Property::Selected))
+    return;
+
+  for (const auto &MBB : MF) {
+    for (const auto &MI : MBB.instrs())
+      CV.visit(MI);
+  }
+
+  if (CV.sawTokens()) {
+    DT.recalculate(const_cast<MachineFunction &>(MF));
+    CV.verify(DT);
+  }
+}
+
 void MachineVerifier::visitMachineFunctionAfter() {
+  auto FailureCB = [this](const Twine &Message) {
+    report(Message.str().c_str(), MF);
+  };
+  verifyConvergenceControl(*MF, DT, FailureCB);
+
   calcRegsPassed();
 
   for (const MachineBasicBlock &MBB : *MF)
     checkPHIOps(MBB);
 
   // Now check liveness info if available
   calcRegsRequired();
 

llvm/lib/Target/AMDGPU/AMDGPUCallLowering.cpp

bool AMDGPUCallLowering::lowerTailCall(
   if (!determineAssignments(Assigner, OutArgs, CCInfo))
     return false;
 
   // Do the actual argument marshalling.
   AMDGPUOutgoingArgHandler Handler(MIRBuilder, MRI, MIB, true, FPDiff);
   if (!handleAssignments(Handler, OutArgs, CCInfo, ArgLocs, MIRBuilder))
     return false;
 
+  if (Info.ConvergenceCtrlToken) {
+    MIB.addUse(Info.ConvergenceCtrlToken, RegState::Implicit);
+  }
   handleImplicitCallArguments(MIRBuilder, MIB, ST, *FuncInfo, ImplicitArgRegs);
 
   // If we have -tailcallopt, we need to adjust the stack. We'll do the call
   // sequence start and end here.
   if (!IsSibCall) {
     MIB->getOperand(1).setImm(FPDiff);
     CallSeqStart.addImm(NumBytes).addImm(0);
     // End the call sequence *before* emitting the call. Normally, we would
if (!determineAssignments(Assigner, OutArgs, CCInfo))
     return false;
 
   AMDGPUOutgoingArgHandler Handler(MIRBuilder, MRI, MIB, false);
   if (!handleAssignments(Handler, OutArgs, CCInfo, ArgLocs, MIRBuilder))
     return false;
 
   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 
+  if (Info.ConvergenceCtrlToken) {
+    MIB.addUse(Info.ConvergenceCtrlToken, RegState::Implicit);
+  }
   handleImplicitCallArguments(MIRBuilder, MIB, ST, *MFI, ImplicitArgRegs);
 
   // Get a count of how many bytes are to be pushed on the stack.
   unsigned NumBytes = CCInfo.getStackSize();
 
   // If Callee is a reg, since it is used by a target specific
   // instruction, it must have a register class matching the
   // constraint of that instruction.

llvm/lib/Target/AMDGPU/AMDGPUInstructionSelector.cpp

bool AMDGPUInstructionSelector::selectDivScale(MachineInstr &MI) const {
 
   MI.eraseFromParent();
   return constrainSelectedInstRegOperands(*MIB, TII, TRI, RBI);
 }
 
 bool AMDGPUInstructionSelector::selectG_INTRINSIC(MachineInstr &I) const {
   unsigned IntrinsicID = cast<GIntrinsic>(I).getIntrinsicID();
   switch (IntrinsicID) {
+  case Intrinsic::experimental_convergence_anchor:
+  case Intrinsic::experimental_convergence_entry:
+  case Intrinsic::experimental_convergence_loop:
+    return true;
   case Intrinsic::amdgcn_if_break: {
     MachineBasicBlock *BB = I.getParent();
 
     // FIXME: Manually selecting to avoid dealing with the SReg_1 trick
     // SelectionDAG uses for wave32 vs wave64.
     BuildMI(*BB, &I, I.getDebugLoc(), TII.get(AMDGPU::SI_IF_BREAK))
       .add(I.getOperand(0))
       .add(I.getOperand(2))

llvm/test/CodeGen/AMDGPU/GlobalISel/convergence-tokens.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -global-isel -mtriple=amdgcn-amd-mesa3d -mcpu=gfx900 -verify-machineinstrs -o - %s | FileCheck -enable-var-scope %s
+
+define void @test_readfirstlane(ptr addrspace(1) %out, i32 %src) #1 {
+; CHECK-LABEL: test_readfirstlane:
+; CHECK:       ; %bb.0:
+; CHECK-NEXT:    s_waitcnt vmcnt(0) expcnt(0) lgkmcnt(0)
+; CHECK-NEXT:    v_readfirstlane_b32 s4, v2
+; CHECK-NEXT:    v_mov_b32_e32 v2, s4
+; CHECK-NEXT:    global_store_dword v[0:1], v2, off
+; CHECK-NEXT:    s_waitcnt vmcnt(0)
+; CHECK-NEXT:    s_setpc_b64 s[30:31]
+  %t = call token @llvm.experimental.convergence.anchor()
+  %readfirstlane = call i32 @llvm.amdgcn.readfirstlane(i32 %src) [ "convergencectrl"(token %t) ]
+  store i32 %readfirstlane, ptr addrspace(1) %out, align 4
+  ret void
+}
+
+declare i32 @llvm.amdgcn.readfirstlane(i32) #0
+
+declare token @llvm.experimental.convergence.entry()
+declare token @llvm.experimental.convergence.anchor()
+declare token @llvm.experimental.convergence.loop()
+
+attributes #0 = { nounwind readnone convergent }
+attributes #1 = { nounwind }

llvm/test/CodeGen/AMDGPU/GlobalISel/irtranslator-convergence-tokens.ll

+; NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+; RUN: llc -global-isel -stop-after=irtranslator -mtriple=amdgcn-amd-mesa3d -mcpu=gfx900 -verify-machineinstrs -o - %s | FileCheck -enable-var-scope %s
+
+define void @test_readfirstlane(ptr addrspace(1) %out, i32 %src) #1 {
+  ; CHECK-LABEL: name: test_readfirstlane
+  ; CHECK: bb.1 (%ir-block.0):
+  ; CHECK-NEXT:   liveins: $vgpr0, $vgpr1, $vgpr2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:_(s32) = COPY $vgpr0
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:_(s32) = COPY $vgpr1
+  ; CHECK-NEXT:   [[MV:%[0-9]+]]:_(p1) = G_MERGE_VALUES [[COPY]](s32), [[COPY1]](s32)
+  ; CHECK-NEXT:   [[COPY2:%[0-9]+]]:_(s32) = COPY $vgpr2
+  ; CHECK-NEXT:   [[INTRINSIC_CONVERGENT:%[0-9]+]]:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+  ; CHECK-NEXT:   [[INTRINSIC_CONVERGENT1:%[0-9]+]]:_(s32) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.amdgcn.readfirstlane), [[COPY2]](s32), implicit [[INTRINSIC_CONVERGENT]](s0)
+  ; CHECK-NEXT:   G_STORE [[INTRINSIC_CONVERGENT1]](s32), [[MV]](p1) :: (store (s32) into %ir.out, addrspace 1)
+  ; CHECK-NEXT:   SI_RETURN
+  %t = call token @llvm.experimental.convergence.anchor()
+  %readfirstlane = call i32 @llvm.amdgcn.readfirstlane(i32 %src) [ "convergencectrl"(token %t) ]
+  store i32 %readfirstlane, ptr addrspace(1) %out, align 4
+  ret void
+}
+
+declare i32 @llvm.amdgcn.readfirstlane(i32) #0
+
+declare token @llvm.experimental.convergence.entry()
+declare token @llvm.experimental.convergence.anchor()
+declare token @llvm.experimental.convergence.loop()
+
+attributes #0 = { nounwind readnone convergent }
+attributes #1 = { nounwind }

llvm/test/CodeGen/AMDGPU/verify-convergencectrl/basic.mir

+# RUN: not --crash llc -mtriple=amdgcn--1 -run-pass=machineverifier -o /dev/null %s 2>&1 | FileCheck %s
+---
+name:            basic
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    %0:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    ; It's impossible to check that no token is passed to entry, since the
+    ; verifier will return when it sees that the entry is not the first instruction
+    ; in the function.
+    ; CHECK: Entry intrinsic can occur only at the start of the basic block.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.entry)
+    %1:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.entry), implicit %0:_(s0)
+    ; CHECK: Loop intrinsic must have a convergencectrl token operand.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop)
+    %2:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop)
+    ; CHECK: Loop intrinsic can occur only at the start of the basic block.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop)
+    %3:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), implicit %0:_(s0)
+    ; CHECK: Convergence control tokens can only be used implicitly.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop)
+    %4:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), %0:_(s0)
+    %5:_(s1) = IMPLICIT_DEF
+    G_BRCOND %6:sgpr_64(s1), %bb.1
+    G_BR %bb.2
+
+  bb.1:
+    ; CHECK: Entry intrinsic can occur only in the entry block.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.entry)
+    %7:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.entry)
+
+  bb.2:
+    ; CHECK: Convergence control tokens can only be used by call instructions or intrinsics.
+    ; CHECK: G_PHI
+    %8:_(s0) = G_PHI %0:_(s0), %bb.0, %0:_(s0), %bb.1
+    %9:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    %10:sgpr_64 = IMPLICIT_DEF
+    %6:sgpr_64(s1) = G_SI_CALL %10:sgpr_64, 1, implicit %9:_(s0)
+    %11:sgpr_64 = G_SI_CALL %10:sgpr_64, 2, implicit %9:_(s0), implicit %9:_(s0)
+    %12:sgpr_64 = G_SI_CALL %10:sgpr_64, 3
+    %13:sgpr_64 = G_SI_CALL %10:sgpr_64, 4, implicit %9:_(s0)
+...

llvm/test/CodeGen/AMDGPU/verify-convergencectrl/cycles.mir

+# RUN: not --crash llc -mtriple=amdgcn-- -run-pass=machineverifier -o /dev/null %s 2>&1 | FileCheck %s
+---
+name:            cycles
+body:             |
+  bb.0:
+    %0:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    %1:_(s1) = IMPLICIT_DEF
+    %2:_(s1) = IMPLICIT_DEF
+    G_BRCOND %2:_(s1), %bb.9
+    G_BR %bb.1
+
+  bb.1:
+    G_BRCOND %2:_(s1), %bb.8
+    G_BR %bb.5
+
+  bb.2:
+    G_BRCOND %2:_(s1), %bb.3
+    G_BR %bb.4
+
+  bb.3:
+    ; CHECK: Cycle heart must dominate all blocks in the cycle.
+    ; Irreducible cycle: entries(bb.4 bb.3)
+    %3:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), implicit %0:_(s0)
+    G_BR %bb.4
+
+  bb.4:
+    G_BR %bb.3
+
+  bb.5:
+    G_BRCOND %2:_(s1), %bb.6
+    G_BR %bb.2
+
+  bb.6:
+    G_BR %bb.7
+
+  bb.7:
+    ; CHECK: Cycle heart must dominate all blocks in the cycle.
+    ; Reducible cycle: entries(bb.6) bb.7
+    %4:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), implicit %0:_(s0)
+    G_BR %bb.6
+
+  bb.8:
+    ; CHECK: Two static convergence token uses in a cycle that does not contain either token's definition.
+    %5:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), implicit %0:_(s0)
+    %6:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.loop), implicit %0:_(s0)
+    G_BR %bb.8
+
+  bb.9:
+    ; CHECK: Convergence token used by an instruction other than llvm.experimental.convergence.loop in a cycle that does not contain the token's definition.
+    %7:sgpr_64 = G_SI_CALL %1:_(s1), 3, implicit %0:_(s0)
+    G_BR %bb.9
+
+...

llvm/test/CodeGen/AMDGPU/verify-convergencectrl/mixed2.mir

+# RUN: not --crash llc -mtriple=amdgcn-- -run-pass=machineverifier -o /dev/null %s 2>&1 | FileCheck %s
+---
+name:            mixed2
+body:             |
+  bb.0:
+    %0:sgpr_64 = IMPLICIT_DEF
+    %1:sgpr_64 = G_SI_CALL %0, 1
+    ; CHECK: Cannot mix controlled and uncontrolled convergence in the same function.
+    ; CHECK: G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    %2:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    ; CHECK: Cannot mix controlled and uncontrolled convergence in the same function.
+    ; CHECK: G_SI_CALL %{{[0-9]}}:sgpr_64, 2
+    %3:sgpr_64 = G_SI_CALL %0, 2, implicit %2(s0)
+
+...

llvm/test/CodeGen/AMDGPU/verify-convergencectrl/region-nesting.mir

+# RUN: not --crash llc -mtriple=amdgcn-- -run-pass=machineverifier -o /dev/null %s 2>&1 | FileCheck %s
+---
+name:            region_nesting
+body:             |
+  bb.0:
+    %0:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    %1:_(s0) = G_INTRINSIC_CONVERGENT intrinsic(@llvm.experimental.convergence.anchor)
+    %2:sgpr_64 = IMPLICIT_DEF
+    %3:sgpr_64 = G_SI_CALL %2, 1, implicit %0(s0)
+    ; CHECK: Convergence region is not well-nested.
+    ; CHECK: G_SI_CALL %{{[0-9]}}:sgpr_64, 2
+    %3:sgpr_64 = G_SI_CALL %2, 2, implicit %1(s0)
+    %4:_(s1) = IMPLICIT_DEF
+    G_BRCOND %4(s1), %bb.1
+    G_BR %bb.2
+
+  bb.1:
+    %5:sgpr_64 = G_SI_CALL %2, 3, implicit %0(s0)
+
+  bb.2:
+    ; CHECK: Convergence region is not well-nested.
+    ; CHECK: G_SI_CALL %{{[0-9]}}:sgpr_64, 4
+    %6:sgpr_64 = G_SI_CALL %2, 4, implicit %1(s0)
+
+...

llvm/test/CodeGen/MIR/AArch64/parse-low-level-type-invalid4.mir

-# RUN: not llc -mtriple=aarch64-- -run-pass none -o /dev/null %s 2>&1 | FileCheck %s
-# When a low-level type is 0 bits
----
-name: test_scalar_size_0
-body: |
-  bb.0:
-    liveins: $x0
-    ; CHECK: [[@LINE+1]]:10: invalid size for scalar type
-    %0:_(s0) = G_IMPLICIT_DEF
-...

llvm/test/CodeGen/MIR/AArch64/parse-low-level-type-invalid6.mir

 # RUN: not llc -mtriple=aarch64-- -run-pass none -o /dev/null %s 2>&1 | FileCheck %s
 # When a low-level type vector has a 0-bit element
 ---
 name: test_vector_element_size_0
 body: |
   bb.0:
     liveins: $x0
-    ; CHECK: [[@LINE+1]]:15: invalid size for scalar type
+    ; CHECK: [[@LINE+1]]:15: invalid size for scalar element in vector
     %0:_(<2 x s0>) = G_IMPLICIT_DEF
 ...