[LLVM] move verification of convergence control to a class template

[sameerds]

Summary

The refactored template can now be used with MachineVerifier.

[arsenm]

llvm/include/llvm/ADT/GenericConvergenceVerifier.h

35

can this be function_ref? I'd expect this to have the failure context as an explicit argument

71

Lowercase?

llvm/lib/IR/Verifier.cpp

395

Don't think you need the everything capture

[sameerds]

• rebase
• replaced std::function with function_ref
• removed the everything capture
• renamed CheckFailed() to reportFailure() ... more aligned with the coding standard

[sameerds]

llvm/include/llvm/ADT/GenericConvergenceVerifier.h

35

See the function reportFailure() where the failure context is passed as an ArrayRef<Printable>. Both verifiers use different variadic function templates that do the same thing: print the message, change the verifier state and then print a variable number of context arguments. This lambda is a call-back to do the first two things. reportFailure() calls this lambda and then prints the context objects passed to it.

[sameerds]

llvm/test/Verifier/convergencectrl-invalid.ll

3

These extra tests were separately committed to the main branch in

https://reviews.llvm.org/rGf7b09516e466

[c-rhodes]

this broke my build with:

ld.lld-12: error: undefined symbol: llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> >::contains(llvm::BasicBlock const*) const
>>> referenced by UniformityAnalysis.cpp:72 (/home/culrho01/llvm-project/llvm/lib/Analysis/UniformityAnalysis.cpp:72)
>>>               lib/Analysis/CMakeFiles/LLVMAnalysis.dir/UniformityAnalysis.cpp.o:(llvm::GenericUniformityAnalysisImpl<llvm::GenericSSAContext<llvm::Function> >::usesValueFromCycle(llvm::Instruction const&, llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> > const&) const)

please could you look into it?

[sameerds]

In D156522#4549644, @c-rhodes wrote:

this broke my build with:

ld.lld-12: error: undefined symbol: llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> >::contains(llvm::BasicBlock const*) const
>>> referenced by UniformityAnalysis.cpp:72 (/home/culrho01/llvm-project/llvm/lib/Analysis/UniformityAnalysis.cpp:72)
>>>               lib/Analysis/CMakeFiles/LLVMAnalysis.dir/UniformityAnalysis.cpp.o:(llvm::GenericUniformityAnalysisImpl<llvm::GenericSSAContext<llvm::Function> >::usesValueFromCycle(llvm::Instruction const&, llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> > const&) const)

please could you look into it?

It's not obvious to me how this change could affect affect functions defined in GenericCycle. Can you please provide the commit hash that you are building, and the build parameters? I will need to reproduced this locally to make any progress.

[c-rhodes]

In D156522#4549769, @sameerds wrote:

In D156522#4549644, @c-rhodes wrote:

this broke my build with:

ld.lld-12: error: undefined symbol: llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> >::contains(llvm::BasicBlock const*) const
>>> referenced by UniformityAnalysis.cpp:72 (/home/culrho01/llvm-project/llvm/lib/Analysis/UniformityAnalysis.cpp:72)
>>>               lib/Analysis/CMakeFiles/LLVMAnalysis.dir/UniformityAnalysis.cpp.o:(llvm::GenericUniformityAnalysisImpl<llvm::GenericSSAContext<llvm::Function> >::usesValueFromCycle(llvm::Instruction const&, llvm::GenericCycle<llvm::GenericSSAContext<llvm::Function> > const&) const)

please could you look into it?

It's not obvious to me how this change could affect affect functions defined in GenericCycle. Can you please provide the commit hash that you are building, and the build parameters? I will need to reproduced this locally to make any progress.

I build with -DBUILD_SHARED_LIBS=ON -DCMAKE_BUILD_TYPE=Debug, I tried static libs (-DBUILD_SHARED_LIBS=OFF) and that works so I think you'll be able to reproduce with shared libs.

[c-rhodes]

failing top of tree (991855ea8a7ff070ca0e22ccba0ff2e96dcdf65b)

[sameerds]

Reopened this because of build errors with shared libraries enabled.

The "extern template" declaration of CycleInfo caused problems in a shared build when CycleInfo was removed from Verifier.cpp. There needs to be an explicit instantiation corresponding to an extern template in every SO.

[steven_wu]

llvm/include/llvm/ADT/GenericConvergenceVerifierImpl.h

34 ↗

(On Diff #545918)

This commit also breaks clang module. You cannot add a dependency from ADT -> IR. This will cause a cyclic dependency in modules between LLVM_Utils <-> LLVM_IR.

[sameerds]

• rebase
• fix build failures:
  • Shared libraries build failed with undefined references due to "extern template" declarations.
  • Modules build failed due to a cycle dependence between llvm/ADT and llvm/IR. The Generic*Impl.h files should be in llvm/IR to prevent this.

[sameerds]

llvm/include/llvm/ADT/GenericConvergenceVerifierImpl.h

34 ↗

(On Diff #545918)

Fixed this by moving the file into llvm/IR. But I still see a failure in the modules build, in a different place:

In file included from /home/ssahasra/projects/llvm-gmir-verifier/llvm/lib/Support/MemAlloc.cpp:10:
...
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/type_traits:2993:41: error: template parameter redefines default argument
template <typename _Tp, unsigned _Idx = 0>
                                        ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/type_traits:2993:41: note: previous default template argument defined here
template <typename _Tp, unsigned _Idx = 0>
                                        ^
1 error generated.

Is that expected? I am using "Ubuntu clang version 14.0.6"

[steven_wu]

llvm/include/llvm/ADT/GenericConvergenceVerifierImpl.h

34 ↗

(On Diff #545918)

I am not too familiar with stdc++ implementation (it should work) but libcxx should just work. We have some macOS bots covering the module builds (it didn't report last time because your commit and revert happen to landed in the same build).

llvm/include/llvm/ADT/GenericConvergenceVerifier.h

+//===- GenericConvergenceVerifier.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
+///
+/// A verifier for the static rules of convergence control tokens that works
+/// with both LLVM IR and MIR.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ADT_GENERICCONVERGENCEVERIFIER_H
+#define LLVM_ADT_GENERICCONVERGENCEVERIFIER_H
+
+#include "llvm/ADT/GenericCycleInfo.h"
+
+namespace llvm {
+
+template <typename ContextT> class GenericConvergenceVerifier {
+public:
+  using BlockT = typename ContextT::BlockT;
+  using FunctionT = typename ContextT::FunctionT;
+  using ValueRefT = typename ContextT::ValueRefT;
+  using InstructionT = typename ContextT::InstructionT;
+  using DominatorTreeT = typename ContextT::DominatorTreeT;
+  using CycleInfoT = GenericCycleInfo<ContextT>;
+  using CycleT = typename CycleInfoT::CycleT;
+
+  void initialize(raw_ostream *OS,
+                  function_ref<void(const Twine &Message)> FailureCB,
+                  const FunctionT &F) {
+    clear();
+    this->OS = OS;
+    this->FailureCB = FailureCB;
+    Context = ContextT(&F);
+  }
+
+  void clear();
+  void visit(const InstructionT &I);
+  void verify(const DominatorTreeT &DT);
+
+  bool sawTokens() const { return ConvergenceKind == ControlledConvergence; }
+
+private:
+  raw_ostream *OS;
+  std::function<void(const Twine &Message)> FailureCB;
+  DominatorTreeT *DT;
+  CycleInfoT CI;
+  ContextT Context;
+
+  /// Whether the current function has convergencectrl operand bundles.
+  enum {
+    ControlledConvergence,
+    UncontrolledConvergence,
+    NoConvergence
+  } ConvergenceKind = NoConvergence;
+
+  // Cache token uses found so far. Note that we track the unique definitions
+  // and not the token values.
+  DenseMap<const InstructionT *, const InstructionT *> Tokens;
+
+  const InstructionT *findAndCheckConvergenceTokenUsed(const InstructionT &I);
+  bool isControlledConvergent(const InstructionT &I);
+  bool isConvergent(const InstructionT &I) const;
+
+  void reportFailure(const Twine &Message, ArrayRef<Printable> Values);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_ADT_GENERICCONVERGENCEVERIFIER_H

llvm/include/llvm/ADT/GenericSSAContext.h

 
 #include "llvm/Support/Printable.h"
 
 namespace llvm {
 
 template <typename, bool> class DominatorTreeBase;
 template <typename> class SmallVectorImpl;
 
+namespace Intrinsic {
+typedef unsigned ID;
+}
+
 // Specializations of this template should provide the types used by the
 // template GenericSSAContext below.
 template <typename _FunctionT> struct GenericSSATraits;
 
 // Ideally this should have been a stateless traits class. But the print methods
 // for Machine IR need access to the owning function. So we track that state in
 // the template itself.
 //
public:
   // a given funciton.
   using DominatorTreeT = DominatorTreeBase<BlockT, false>;
 
   GenericSSAContext() = default;
   GenericSSAContext(const FunctionT *F) : F(F) {}
 
   const FunctionT *getFunction() const { return F; }
 
+  static Intrinsic::ID getIntrinsicID(const InstructionT &I);
+
   static void appendBlockDefs(SmallVectorImpl<ValueRefT> &defs, BlockT &block);
   static void appendBlockDefs(SmallVectorImpl<ConstValueRefT> &defs,
                               const BlockT &block);
 
   static void appendBlockTerms(SmallVectorImpl<InstructionT *> &terms,
                                BlockT &block);
   static void appendBlockTerms(SmallVectorImpl<const InstructionT *> &terms,
                                const BlockT &block);
 
   static bool isConstantOrUndefValuePhi(const InstructionT &Instr);
   const BlockT *getDefBlock(ConstValueRefT value) const;
 
   Printable print(const BlockT *block) const;
+  Printable printAsOperand(const BlockT *BB) const;
   Printable print(const InstructionT *inst) const;
   Printable print(ConstValueRefT value) const;
 };
 } // namespace llvm
 
 #endif // LLVM_ADT_GENERICSSACONTEXT_H

llvm/include/llvm/IR/ConvergenceVerifier.h

+//===- ConvergenceVerifier.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 LLVM IR specialization of the
+/// GenericConvergenceVerifier template.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_CONVERGENCEVERIFIER_H
+#define LLVM_IR_CONVERGENCEVERIFIER_H
+
+#include "llvm/ADT/GenericConvergenceVerifier.h"
+#include "llvm/IR/SSAContext.h"
+
+namespace llvm {
+
+using ConvergenceVerifier = GenericConvergenceVerifier<SSAContext>;
+
+} // namespace llvm
+
+#endif // LLVM_IR_CONVERGENCEVERIFIER_H

llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h

+//===- GenericConvergenceVerifierImpl.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
+///
+/// A verifier for the static rules of convergence control tokens that works
+/// with both LLVM IR and MIR.
+///
+/// This template implementation resides in a separate file so that it does not
+/// get injected into every .cpp file that includes the generic header.
+///
+/// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
+///
+/// This file should only be included by files that implement a
+/// specialization of the relevant templates. Currently these are:
+/// - llvm/lib/IR/Verifier.cpp
+/// - llvm/lib/CodeGen/MachineVerifier.cpp
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
+#define LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H
+
+#include "llvm/ADT/GenericConvergenceVerifier.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/IR/Intrinsics.h"
+
+using namespace llvm;
+
+#define Check(C, ...)                                                          \
+  do {                                                                         \
+    if (!(C)) {                                                                \
+      reportFailure(__VA_ARGS__);                                              \
+      return;                                                                  \
+    }                                                                          \
+  } while (false)
+
+#define CheckOrNull(C, ...)                                                    \
+  do {                                                                         \
+    if (!(C)) {                                                                \
+      reportFailure(__VA_ARGS__);                                              \
+      return {};                                                               \
+    }                                                                          \
+  } while (false)
+
+static bool isConvergenceControlIntrinsic(unsigned IntrinsicID) {
+  switch (IntrinsicID) {
+  default:
+    return false;
+  case Intrinsic::experimental_convergence_anchor:
+  case Intrinsic::experimental_convergence_entry:
+  case Intrinsic::experimental_convergence_loop:
+    return true;
+  }
+}
+
+namespace llvm {
+template <class ContextT> void GenericConvergenceVerifier<ContextT>::clear() {
+  Tokens.clear();
+  CI.clear();
+  ConvergenceKind = NoConvergence;
+}
+
+template <class ContextT>
+void GenericConvergenceVerifier<ContextT>::visit(const InstructionT &I) {
+  if (isControlledConvergent(I)) {
+    Check(isConvergent(I),
+          "Expected convergent attribute on a controlled convergent call.",
+          {Context.print(&I)});
+    Check(ConvergenceKind != UncontrolledConvergence,
+          "Cannot mix controlled and uncontrolled convergence in the same "
+          "function.",
+          {Context.print(&I)});
+    ConvergenceKind = ControlledConvergence;
+  } else if (isConvergent(I)) {
+    Check(ConvergenceKind != ControlledConvergence,
+          "Cannot mix controlled and uncontrolled convergence in the same "
+          "function.",
+          {Context.print(&I)});
+    ConvergenceKind = UncontrolledConvergence;
+  }
+}
+
+template <class ContextT>
+void GenericConvergenceVerifier<ContextT>::reportFailure(
+    const Twine &Message, ArrayRef<Printable> DumpedValues) {
+  FailureCB(Message);
+  if (OS) {
+    for (auto V : DumpedValues)
+      *OS << V << '\n';
+  }
+}
+
+template <class ContextT>
+void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) {
+  assert(Context.getFunction());
+  const auto &F = *Context.getFunction();
+
+  DenseMap<const BlockT *, SmallVector<const InstructionT *, 8>> LiveTokenMap;
+  DenseMap<const CycleT *, const InstructionT *> CycleHearts;
+
+  // Just like the DominatorTree, compute the CycleInfo locally so that we
+  // can run the verifier outside of a pass manager and we don't rely on
+  // potentially out-dated analysis results.
+  CI.compute(const_cast<FunctionT &>(F));
+
+  auto checkToken = [&](const InstructionT *Token, const InstructionT *User,
+                        SmallVectorImpl<const InstructionT *> &LiveTokens) {
+    Check(llvm::is_contained(LiveTokens, Token),
+          "Convergence region is not well-nested.",
+          {Context.print(Token), Context.print(User)});
+    while (LiveTokens.back() != Token)
+      LiveTokens.pop_back();
+
+    // Check static rules about cycles.
+    auto *BB = User->getParent();
+    auto *BBCycle = CI.getCycle(BB);
+    if (!BBCycle)
+      return;
+
+    auto *DefBB = Token->getParent();
+    if (DefBB == BB || BBCycle->contains(DefBB)) {
+      // degenerate occurrence of a loop intrinsic
+      return;
+    }
+
+    Check(ContextT::getIntrinsicID(*User) ==
+              Intrinsic::experimental_convergence_loop,
+          "Convergence token used by an instruction other than "
+          "llvm.experimental.convergence.loop in a cycle that does "
+          "not contain the token's definition.",
+          {Context.print(User), CI.print(BBCycle)});
+
+    while (true) {
+      auto *Parent = BBCycle->getParentCycle();
+      if (!Parent || Parent->contains(DefBB))
+        break;
+      BBCycle = Parent;
+    };
+
+    Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),
+          "Cycle heart must dominate all blocks in the cycle.",
+          {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)});
+    Check(!CycleHearts.count(BBCycle),
+          "Two static convergence token uses in a cycle that does "
+          "not contain either token's definition.",
+          {Context.print(User), Context.print(CycleHearts[BBCycle]),
+           CI.print(BBCycle)});
+    CycleHearts[BBCycle] = User;
+  };
+
+  ReversePostOrderTraversal<const FunctionT *> RPOT(&F);
+  SmallVector<const InstructionT *, 8> LiveTokens;
+  for (auto *BB : RPOT) {
+    LiveTokens.clear();
+    auto LTIt = LiveTokenMap.find(BB);
+    if (LTIt != LiveTokenMap.end()) {
+      LiveTokens = std::move(LTIt->second);
+      LiveTokenMap.erase(LTIt);
+    }
+
+    for (auto &I : *BB) {
+      if (auto *Token = Tokens.lookup(&I))
+        checkToken(Token, &I, LiveTokens);
+      if (isConvergenceControlIntrinsic(ContextT::getIntrinsicID(I)))
+        LiveTokens.push_back(&I);
+    }
+
+    // Propagate token liveness
+    for (auto *Succ : successors(BB)) {
+      auto *SuccNode = DT.getNode(Succ);
+      auto LTIt = LiveTokenMap.find(Succ);
+      if (LTIt == LiveTokenMap.end()) {
+        // We're the first predecessor: all tokens which dominate the
+        // successor are live for now.
+        LTIt = LiveTokenMap.try_emplace(Succ).first;
+        for (auto LiveToken : LiveTokens) {
+          if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))
+            break;
+          LTIt->second.push_back(LiveToken);
+        }
+      } else {
+        // Compute the intersection of live tokens.
+        auto It = llvm::partition(
+            LTIt->second, [&LiveTokens](const InstructionT *Token) {
+              return llvm::is_contained(LiveTokens, Token);
+            });
+        LTIt->second.erase(It, LTIt->second.end());
+      }
+    }
+  }
+}
+
+} // end namespace llvm
+
+#endif // LLVM_IR_GENERICCONVERGENCEVERIFIERIMPL_H

llvm/lib/CodeGen/MachineSSAContext.cpp

 //===- MachineSSAContext.cpp ------------------------------------*- 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 defines a specialization of the GenericSSAContext<X>
 /// template class for Machine IR.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/MachineSSAContext.h"
+#include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 

 }
 
 template <>
 bool MachineSSAContext::isConstantOrUndefValuePhi(const MachineInstr &Phi) {
   return Phi.isConstantValuePHI();
 }
 
 template <>
+Intrinsic::ID MachineSSAContext::getIntrinsicID(const MachineInstr &MI) {
+  if (auto *GI = dyn_cast<GIntrinsic>(&MI))
+    return GI->getIntrinsicID();
+  return Intrinsic::not_intrinsic;
+}
+
+template <>
 Printable MachineSSAContext::print(const MachineBasicBlock *Block) const {
   if (!Block)
     return Printable([](raw_ostream &Out) { Out << "<nullptr>"; });
   return Printable([Block](raw_ostream &Out) { Block->printName(Out); });
 }
 
 template <> Printable MachineSSAContext::print(const MachineInstr *I) const {
   return Printable([I](raw_ostream &Out) { I->print(Out); });
 }
 
 template <> Printable MachineSSAContext::print(Register Value) const {
   auto *MRI = &F->getRegInfo();
   return Printable([MRI, Value](raw_ostream &Out) {
     Out << printReg(Value, MRI->getTargetRegisterInfo(), 0, MRI);
 
     if (Value) {
       // Try to print the definition.
       if (auto *Instr = MRI->getUniqueVRegDef(Value)) {
         Out << ": ";
         Instr->print(Out);
       }
     }
   });
 }
+
+template <>
+Printable MachineSSAContext::printAsOperand(const MachineBasicBlock *BB) const {
+  return Printable([BB](raw_ostream &Out) { BB->printAsOperand(Out); });
+}

llvm/lib/IR/CMakeLists.txt

 add_llvm_component_library(LLVMCore
   AbstractCallSite.cpp
   AsmWriter.cpp
   Assumptions.cpp
   Attributes.cpp
   AutoUpgrade.cpp
   BasicBlock.cpp
   BuiltinGCs.cpp
   Comdat.cpp
   ConstantFold.cpp
   ConstantRange.cpp
   Constants.cpp
+  ConvergenceVerifier.cpp
   Core.cpp
   CycleInfo.cpp
   DIBuilder.cpp
   DataLayout.cpp
   DebugInfo.cpp
   DebugInfoMetadata.cpp
   DebugLoc.cpp
   DiagnosticHandler.cpp

llvm/lib/IR/ConvergenceVerifier.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/IR/ConvergenceVerifier.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/GenericConvergenceVerifierImpl.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/SSAContext.h"
+
+using namespace llvm;
+
+template <>
+const Instruction *
+GenericConvergenceVerifier<SSAContext>::findAndCheckConvergenceTokenUsed(
+    const Instruction &I) {
+  auto *CB = dyn_cast<CallBase>(&I);
+  if (!CB)
+    return nullptr;
+
+  unsigned Count =
+      CB->countOperandBundlesOfType(LLVMContext::OB_convergencectrl);
+  CheckOrNull(Count <= 1,
+              "The 'convergencectrl' bundle can occur at most once on a call",
+              {Context.print(CB)});
+  if (!Count)
+    return nullptr;
+
+  auto Bundle = CB->getOperandBundle(LLVMContext::OB_convergencectrl);
+  CheckOrNull(Bundle->Inputs.size() == 1 &&
+                  Bundle->Inputs[0]->getType()->isTokenTy(),
+              "The 'convergencectrl' bundle requires exactly one token use.",
+              {Context.print(CB)});
+  auto *Token = Bundle->Inputs[0].get();
+  auto *Def = dyn_cast<Instruction>(Token);
+
+  CheckOrNull(
+      Def && isConvergenceControlIntrinsic(SSAContext::getIntrinsicID(*Def)),
+      "Convergence control tokens can only be produced by calls to the "
+      "convergence control intrinsics.",
+      {Context.print(Token), Context.print(&I)});
+
+  if (Def)
+    Tokens[&I] = Def;
+
+  return Def;
+}
+
+template <>
+bool GenericConvergenceVerifier<SSAContext>::isConvergent(
+    const InstructionT &I) const {
+  if (auto *CB = dyn_cast<CallBase>(&I)) {
+    return CB->isConvergent();
+  }
+  return false;
+}
+
+template <>
+bool GenericConvergenceVerifier<SSAContext>::isControlledConvergent(
+    const InstructionT &I) {
+  // First find a token and place it in the map.
+  if (findAndCheckConvergenceTokenUsed(I))
+    return true;
+
+  // The entry and anchor intrinsics do not use a token, so we do a broad check
+  // here. The loop intrinsic will be checked separately for a missing token.
+  if (isConvergenceControlIntrinsic(SSAContext::getIntrinsicID(I)))
+    return true;
+
+  return false;
+}
+
+template class llvm::GenericConvergenceVerifier<SSAContext>;

llvm/lib/IR/SSAContext.cpp

 /// template class for LLVM IR.
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/SSAContext.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Function.h"
-#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
-#include "llvm/Support/raw_ostream.h"
+#include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/ModuleSlotTracker.h"
+#include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 template <>
 void SSAContext::appendBlockDefs(SmallVectorImpl<Value *> &defs,
                                  BasicBlock &block) {
   for (auto &instr : block) {
     if (instr.isTerminator())

 
 template <>
 bool SSAContext::isConstantOrUndefValuePhi(const Instruction &Instr) {
   if (auto *Phi = dyn_cast<PHINode>(&Instr))
     return Phi->hasConstantOrUndefValue();
   return false;
 }
 
+template <> Intrinsic::ID SSAContext::getIntrinsicID(const Instruction &I) {
+  if (auto *CB = dyn_cast<CallBase>(&I))
+    return CB->getIntrinsicID();
+  return Intrinsic::not_intrinsic;
+}
+
 template <> Printable SSAContext::print(const Value *V) const {
   return Printable([V](raw_ostream &Out) { V->print(Out); });
 }
 
 template <> Printable SSAContext::print(const Instruction *Inst) const {
   return print(cast<Value>(Inst));
 }
 
 template <> Printable SSAContext::print(const BasicBlock *BB) const {
   if (!BB)
     return Printable([](raw_ostream &Out) { Out << "<nullptr>"; });
   if (BB->hasName())
     return Printable([BB](raw_ostream &Out) { Out << BB->getName(); });
 
   return Printable([BB](raw_ostream &Out) {
     ModuleSlotTracker MST{BB->getParent()->getParent(), false};
     MST.incorporateFunction(*BB->getParent());
     Out << MST.getLocalSlot(BB);
   });
 }
+
+template <> Printable SSAContext::printAsOperand(const BasicBlock *BB) const {
+  return Printable([BB](raw_ostream &Out) { BB->printAsOperand(Out); });
+}

llvm/lib/IR/Verifier.cpp

 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/CallingConv.h"
 #include "llvm/IR/Comdat.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
-#include "llvm/IR/CycleInfo.h"
+#include "llvm/IR/ConvergenceVerifier.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/EHPersonalities.h"
 #include "llvm/IR/Function.h"
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   bool SawFrameEscape;
 
   /// Whether the current function has a DISubprogram attached to it.
   bool HasDebugInfo = false;
 
   /// The current source language.
   dwarf::SourceLanguage CurrentSourceLang = dwarf::DW_LANG_lo_user;
 
-  /// Whether the current function has convergencectrl operand bundles.
-  enum {
-    ControlledConvergence,
-    UncontrolledConvergence,
-    NoConvergence
-  } ConvergenceKind = NoConvergence;
-
   /// Whether source was present on the first DIFile encountered in each CU.
   DenseMap<const DICompileUnit *, bool> HasSourceDebugInfo;
 
   /// Stores the count of how many objects were passed to llvm.localescape for a
   /// given function and the largest index passed to llvm.localrecover.
   DenseMap<Function *, std::pair<unsigned, unsigned>> FrameEscapeInfo;
 
   // Maps catchswitches and cleanuppads that unwind to siblings to the
class Verifier : public InstVisitor<Verifier>, VerifierSupport {
   // twice, if they have multiple operands. In particular for very large
   // constant expressions, we can arrive at a particular user many times.
   SmallPtrSet<const Value *, 32> GlobalValueVisited;
 
   // Keeps track of duplicate function argument debug info.
   SmallVector<const DILocalVariable *, 16> DebugFnArgs;
 
   TBAAVerifier TBAAVerifyHelper;
+  ConvergenceVerifier CV;
 
   SmallVector<IntrinsicInst *, 4> NoAliasScopeDecls;
 
   void checkAtomicMemAccessSize(Type *Ty, const Instruction *I);
 
 public:
   explicit Verifier(raw_ostream *OS, bool ShouldTreatBrokenDebugInfoAsError,
                     const Module &M)
bool verify(const Function &F) {
     // information, and directly compute a dominance tree. We don't rely on the
     // pass manager to provide this as it isolates us from a potentially
     // out-of-date dominator tree and makes it significantly more complex to run
     // this code outside of a pass manager.
     // FIXME: It's really gross that we have to cast away constness here.
     if (!F.empty())
       DT.recalculate(const_cast<Function &>(F));
 
     for (const BasicBlock &BB : F) {
       if (!BB.empty() && BB.back().isTerminator())
         continue;
 
       if (OS) {
         *OS << "Basic Block in function '" << F.getName()
             << "' does not have terminator!\n";
         BB.printAsOperand(*OS, true, MST);
         *OS << "\n";
       }
       return false;
     }
 
+    auto FailureCB = [this](const Twine &Message) {
+      this->CheckFailed(Message);
+    };
+    CV.initialize(OS, FailureCB, F);
+
     Broken = false;
     // FIXME: We strip const here because the inst visitor strips const.
     visit(const_cast<Function &>(F));
     verifySiblingFuncletUnwinds();
-    if (ConvergenceKind == ControlledConvergence)
-      verifyConvergenceControl(const_cast<Function &>(F));
+
+    if (CV.sawTokens())
+      CV.verify(DT);
+
     InstsInThisBlock.clear();
     DebugFnArgs.clear();
     LandingPadResultTy = nullptr;
     SawFrameEscape = false;
     SiblingFuncletInfo.clear();
     verifyNoAliasScopeDecl();
     NoAliasScopeDecls.clear();
-    ConvergenceKind = NoConvergence;
 
     return !Broken;
   }
 
   /// Verify the module that this instance of \c Verifier was initialized with.
   bool verify() {
     Broken = false;
 
#include "llvm/IR/Metadata.def"
   void verifyFunctionMetadata(ArrayRef<std::pair<unsigned, MDNode *>> MDs);
 
   void visitConstantExprsRecursively(const Constant *EntryC);
   void visitConstantExpr(const ConstantExpr *CE);
   void verifyInlineAsmCall(const CallBase &Call);
   void verifyStatepoint(const CallBase &Call);
   void verifyFrameRecoverIndices();
   void verifySiblingFuncletUnwinds();
-  void verifyConvergenceControl(Function &F);
 
   void verifyFragmentExpression(const DbgVariableIntrinsic &I);
   template <typename ValueOrMetadata>
   void verifyFragmentExpression(const DIVariable &V,
                                 DIExpression::FragmentInfo Fragment,
                                 ValueOrMetadata *Desc);
   void verifyFnArgs(const DbgVariableIntrinsic &I);
   void verifyNotEntryValue(const DbgVariableIntrinsic &I);
do {
       Active.insert(PredPad);
     } while (true);
     // Each node only has one successor, so we've walked all the active
     // nodes' successors.
     Active.clear();
   }
 }
 
-static bool isConvergenceControlIntrinsic(const CallBase &Call) {
-  switch (Call.getIntrinsicID()) {
-  case Intrinsic::experimental_convergence_anchor:
-  case Intrinsic::experimental_convergence_entry:
-  case Intrinsic::experimental_convergence_loop:
-    return true;
-  default:
-    return false;
-  }
-}
-
-static bool isControlledConvergent(const CallBase &Call) {
-  if (Call.countOperandBundlesOfType(LLVMContext::OB_convergencectrl))
-    return true;
-  return isConvergenceControlIntrinsic(Call);
-}
-
-void Verifier::verifyConvergenceControl(Function &F) {
-  DenseMap<BasicBlock *, SmallVector<CallBase *, 8>> LiveTokenMap;
-  DenseMap<const Cycle *, const CallBase *> CycleHearts;
-
-  // Just like the DominatorTree, compute the CycleInfo locally so that we
-  // can run the verifier outside of a pass manager and we don't rely on
-  // potentially out-dated analysis results.
-  CycleInfo CI;
-  CI.compute(F);
-
-  auto checkBundle = [&](OperandBundleUse &Bundle, CallBase *CB,
-                         SmallVectorImpl<CallBase *> &LiveTokens) {
-    Check(Bundle.Inputs.size() == 1 && Bundle.Inputs[0]->getType()->isTokenTy(),
-          "The 'convergencectrl' bundle requires exactly one token use.", CB);
-
-    Value *Token = Bundle.Inputs[0].get();
-    auto *Def = dyn_cast<CallBase>(Token);
-    Check(Def && isConvergenceControlIntrinsic(*Def),
-          "Convergence control tokens can only be produced by calls to the "
-          "convergence control intrinsics.",
-          Token, CB);
-
-    Check(llvm::is_contained(LiveTokens, Token),
-          "Convergence region is not well-nested.", Token, CB);
-
-    while (LiveTokens.back() != Token)
-      LiveTokens.pop_back();
-
-    // Check static rules about cycles.
-    auto *BB = CB->getParent();
-    auto *BBCycle = CI.getCycle(BB);
-    if (!BBCycle)
-      return;
-
-    BasicBlock *DefBB = Def->getParent();
-    if (DefBB == BB || BBCycle->contains(DefBB)) {
-      // degenerate occurrence of a loop intrinsic
-      return;
-    }
-
-    auto *II = dyn_cast<IntrinsicInst>(CB);
-    Check(II &&
-              II->getIntrinsicID() == Intrinsic::experimental_convergence_loop,
-          "Convergence token used by an instruction other than "
-          "llvm.experimental.convergence.loop in a cycle that does "
-          "not contain the token's definition.",
-          CB, CI.print(BBCycle));
-
-    while (true) {
-      auto *Parent = BBCycle->getParentCycle();
-      if (!Parent || Parent->contains(DefBB))
-        break;
-      BBCycle = Parent;
-    };
-
-    Check(BBCycle->isReducible() && BB == BBCycle->getHeader(),
-          "Cycle heart must dominate all blocks in the cycle.", CB, BB,
-          CI.print(BBCycle));
-    Check(!CycleHearts.count(BBCycle),
-          "Two static convergence token uses in a cycle that does "
-          "not contain either token's definition.",
-          CB, CycleHearts[BBCycle], CI.print(BBCycle));
-    CycleHearts[BBCycle] = CB;
-  };
-
-  ReversePostOrderTraversal<Function *> RPOT(&F);
-  SmallVector<CallBase *, 8> LiveTokens;
-  for (BasicBlock *BB : RPOT) {
-    LiveTokens.clear();
-    auto LTIt = LiveTokenMap.find(BB);
-    if (LTIt != LiveTokenMap.end()) {
-      LiveTokens = std::move(LTIt->second);
-      LiveTokenMap.erase(LTIt);
-    }
-
-    for (Instruction &I : *BB) {
-      CallBase *CB = dyn_cast<CallBase>(&I);
-      if (!CB)
-        continue;
-
-      Check(CB->countOperandBundlesOfType(LLVMContext::OB_convergencectrl) <= 1,
-            "The 'convergencetrl' bundle can occur at most once on a call", CB);
-
-      auto Bundle = CB->getOperandBundle(LLVMContext::OB_convergencectrl);
-      if (Bundle)
-        checkBundle(*Bundle, CB, LiveTokens);
-
-      if (CB->getType()->isTokenTy())
-        LiveTokens.push_back(CB);
-    }
-
-    // Propagate token liveness
-    for (BasicBlock *Succ : successors(BB)) {
-      DomTreeNode *SuccNode = DT.getNode(Succ);
-      LTIt = LiveTokenMap.find(Succ);
-      if (LTIt == LiveTokenMap.end()) {
-        // We're the first predecessor: all tokens which dominate the
-        // successor are live for now.
-        LTIt = LiveTokenMap.try_emplace(Succ).first;
-        for (CallBase *LiveToken : LiveTokens) {
-          if (!DT.dominates(DT.getNode(LiveToken->getParent()), SuccNode))
-            break;
-          LTIt->second.push_back(LiveToken);
-        }
-      } else {
-        // Compute the intersection of live tokens.
-        auto It = llvm::partition(LTIt->second, [&LiveTokens](CallBase *Token) {
-          return llvm::is_contained(LiveTokens, Token);
-        });
-        LTIt->second.erase(It, LTIt->second.end());
-      }
-    }
-  }
-}
-
 // visitFunction - Verify that a function is ok.
 //
 void Verifier::visitFunction(const Function &F) {
   visitGlobalValue(F);
 
   // Check function arguments.
   FunctionType *FT = F.getFunctionType();
   unsigned NumArgs = F.arg_size();
if (Call.getFunction()->getSubprogram() && Call.getCalledFunction() &&
     CheckDI(Call.getDebugLoc(),
             "inlinable function call in a function with "
             "debug info must have a !dbg location",
             Call);
 
   if (Call.isInlineAsm())
     verifyInlineAsmCall(Call);
 
-  if (isControlledConvergent(Call)) {
-    Check(Call.isConvergent(),
-          "Expected convergent attribute on a controlled convergent call.",
-          Call);
-    Check(ConvergenceKind != UncontrolledConvergence,
-          "Cannot mix controlled and uncontrolled convergence in the same "
-          "function.",
-          Call);
-    ConvergenceKind = ControlledConvergence;
-  } else if (Call.isConvergent()) {
-    Check(ConvergenceKind != ControlledConvergence,
-          "Cannot mix controlled and uncontrolled convergence in the same "
-          "function.",
-          Call);
-    ConvergenceKind = UncontrolledConvergence;
-  }
+  CV.visit(Call);
 
   visitInstruction(Call);
 }
 
 void Verifier::verifyTailCCMustTailAttrs(const AttrBuilder &Attrs,
                                          StringRef Context) {
   Check(!Attrs.contains(Attribute::InAlloca),
         Twine("inalloca attribute not allowed in ") + Context);

llvm/test/Verifier/convergencectrl-invalid.ll

 ; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s
 
 ; CHECK: Convergence control tokens can only be produced by calls to the convergence control intrinsics.
 ; CHECK-NEXT:  %t04_tok1 = call token @produce_token()
 ; CHECK-NEXT:  call void @f() [ "convergencectrl"(token %t04_tok1) ]
 define void @wrong_token() {
   %t04_tok1 = call token @produce_token()
   call void @f() [ "convergencectrl"(token %t04_tok1) ]
   ret void
 }
 

 ; CHECK-NEXT:  call void @g()
 define void @multiple_tokens() {
   %t06_tok1 = call token @llvm.experimental.convergence.anchor()
   %t06_tok2 = call token @llvm.experimental.convergence.anchor()
   call void @g() [ "convergencectrl"(token %t06_tok2, token %t06_tok1) ]
   ret void
 }
 
-; CHECK: The 'convergencetrl' bundle can occur at most once on a call
+; CHECK: The 'convergencectrl' bundle can occur at most once on a call
 ; CHECK-NEXT:  call void @g()
 define void @multiple_bundles() {
   %t07_tok1 = call token @llvm.experimental.convergence.anchor()
   %t07_tok2 = call token @llvm.experimental.convergence.anchor()
   call void @g() [ "convergencectrl"(token %t07_tok2), "convergencectrl"(token %t07_tok1) ]
   ret void
 }