[CodeGen] Add machine instruction descriptors

Introduce an immutable instruction registry with exact operand, implicit register, tie, pseudo lifecycle, and memory constraints. Validate descriptor tables before publication and use the same rules to verify MachineInstr instances.

7 files changed, 1186 insertions, 0 deletions

diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h
new file mode 100644
index 0000000..c6049b9
--- /dev/null
+++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h
@@ -0,0 +1,264 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_INSTRUCTIONDESCRIPTOR_H
+#define RCC_CODEGEN_INSTRUCTIONDESCRIPTOR_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <initializer_list>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineInstr;
+class MachineRegisterInfo;
+
+class OperandKindSet final {
+public:
+  static_assert(static_cast<std::uint32_t>(MachineOperand::Kind::Count) <= 32);
+
+  constexpr OperandKindSet() noexcept = default;
+
+  OperandKindSet(std::initializer_list<MachineOperand::Kind> Kinds) noexcept;
+
+  [[nodiscard]] constexpr bool empty() const noexcept {
+    return Mask == 0;
+  }
+
+  [[nodiscard]] constexpr bool contains(MachineOperand::Kind Kind) const noexcept {
+    const auto Index = static_cast<std::uint32_t>(Kind);
+    if (Index >= static_cast<std::uint32_t>(MachineOperand::Kind::Count))
+      return false;
+    return (Mask & (std::uint32_t{1} << Index)) != 0;
+  }
+
+  constexpr void add(MachineOperand::Kind Kind) noexcept {
+    const auto Index = static_cast<std::uint32_t>(Kind);
+    if (Index < static_cast<std::uint32_t>(MachineOperand::Kind::Count))
+      Mask |= std::uint32_t{1} << Index;
+  }
+
+  [[nodiscard]] constexpr std::uint32_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  friend constexpr bool operator==(OperandKindSet Left, OperandKindSet Right) noexcept = default;
+
+private:
+  std::uint32_t Mask = 0;
+};
+
+enum class RegisterOperandRole : std::uint8_t {
+  None,
+  Def,
+  Use,
+  DefUse,
+};
+
+enum class MemoryOperandRole : std::uint8_t {
+  None,
+  Address,
+  Value,
+  Size,
+  Ordering,
+};
+
+enum class InstructionFlag : std::uint8_t {
+  Terminator,
+  Branch,
+  IndirectBranch,
+  Call,
+  Return,
+  Barrier,
+  MayLoad,
+  MayStore,
+  HasSideEffects,
+  Pseudo,
+  Meta,
+  AllowedPreLegalizer,
+  ProducesCode,
+  Commutable,
+  Rematerializable,
+  Predicable,
+  NotDuplicable,
+  Convergent,
+  UnmodeledSideEffects,
+  Phi,
+  Generic,
+  TerminalEmission,
+  Count,
+};
+
+class InstructionFlags final {
+public:
+  static_assert(static_cast<std::uint32_t>(InstructionFlag::Count) <= 32);
+
+  constexpr InstructionFlags() noexcept = default;
+
+  InstructionFlags(std::initializer_list<InstructionFlag> Flags) noexcept;
+
+  [[nodiscard]] constexpr bool has(InstructionFlag Flag) const noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index >= static_cast<std::uint32_t>(InstructionFlag::Count))
+      return false;
+    return (Mask & (std::uint32_t{1} << Index)) != 0;
+  }
+
+  constexpr void set(InstructionFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index < static_cast<std::uint32_t>(InstructionFlag::Count))
+      Mask |= std::uint32_t{1} << Index;
+  }
+
+  constexpr void clear(InstructionFlag Flag) noexcept {
+    const auto Index = static_cast<std::uint32_t>(Flag);
+    if (Index < static_cast<std::uint32_t>(InstructionFlag::Count))
+      Mask &= ~(std::uint32_t{1} << Index);
+  }
+
+  [[nodiscard]] constexpr std::uint32_t rawValue() const noexcept {
+    return Mask;
+  }
+
+  friend constexpr bool operator==(InstructionFlags Left,
+                                   InstructionFlags Right) noexcept = default;
+
+private:
+  std::uint32_t Mask = 0;
+};
+
+enum class PseudoOwner : std::uint8_t {
+  None,
+  Legalizer,
+  RegisterBankSelect,
+  InstructionSelect,
+  PhiElimination,
+  TwoAddressRewrite,
+  RegisterAllocator,
+  PrePEIExpansion,
+  PrologueEpilogueInsertion,
+  PostRAExpansion,
+  Finalization,
+  AsmPrinter,
+};
+
+enum class PipelineStage : std::uint8_t {
+  MachineIRInput,
+  Legalized,
+  RegBankSelected,
+  Selected,
+  SSAEliminated,
+  TiedOpsRewritten,
+  RegisterAllocated,
+  FrameFinalized,
+  PostRAFinalized,
+  Emission,
+};
+
+struct OperandDescriptor final {
+  OperandKindSet Kinds;
+  RegisterOperandRole RegisterRole = RegisterOperandRole::None;
+  std::optional<RegisterClassID> RegClass;
+  std::optional<RegisterBankID> RegBank;
+  std::optional<ImmediatePredicateID> ImmediatePredicate;
+  MemoryOperandRole MemoryRole = MemoryOperandRole::None;
+  std::optional<std::size_t> DefaultTiedOperand;
+  bool EarlyClobber = false;
+  bool Optional = false;
+  bool VariadicGroup = false;
+  bool AllowSubReg = false;
+  std::optional<NamedOperandID> Name;
+  std::optional<TargetOperandTypeID> TargetOperandType;
+  std::uint32_t AllowedTargetFlags = 0;
+};
+
+struct ImplicitRegisterDescriptor final {
+  PhysicalRegister Reg;
+  bool EarlyClobber = false;
+  bool Renamable = false;
+
+  friend bool operator==(const ImplicitRegisterDescriptor &Left,
+                         const ImplicitRegisterDescriptor &Right) = default;
+};
+
+struct InstructionDescriptor final {
+  Opcode InstructionOpcode;
+  std::string Name;
+  std::vector<OperandDescriptor> Operands;
+  std::size_t NumExplicitDefs = 0;
+  bool Variadic = false;
+  std::vector<ImplicitRegisterDescriptor> ImplicitDefs;
+  std::vector<ImplicitRegisterDescriptor> ImplicitUses;
+  bool AllowExtraImplicitOperands = false;
+  InstructionFlags Flags;
+  SchedulingClassID SchedulingClass;
+  EncodingCategoryID EncodingCategory;
+  AssemblyFormatID AssemblyFormat;
+  bool RequiresMemoryOperands = false;
+  PseudoOwner Owner = PseudoOwner::None;
+  PipelineStage Deadline = PipelineStage::Emission;
+};
+
+struct ImmediatePredicate final {
+  ImmediatePredicateID ID;
+  std::string Name;
+  std::function<bool(const MachineOperand &)> Predicate;
+};
+
+class InstructionSet final {
+public:
+  [[nodiscard]] static Expected<InstructionSet>
+  create(std::vector<InstructionDescriptor> Descriptors,
+         std::vector<ImmediatePredicate> ImmediatePredicates = {});
+
+  [[nodiscard]] const InstructionDescriptor *descriptor(Opcode InstructionOpcode) const noexcept;
+  [[nodiscard]] const InstructionDescriptor *descriptor(std::string_view Name) const noexcept;
+  [[nodiscard]] std::span<const InstructionDescriptor> descriptors() const noexcept {
+    return Descriptors;
+  }
+
+  [[nodiscard]] Expected<void> validateExplicitOperands(Opcode InstructionOpcode,
+                                                        std::span<const MachineOperand> Operands,
+                                                        const MachineRegisterInfo &RegInfo) const;
+  [[nodiscard]] Expected<void> validateInstruction(const MachineInstr &Instruction,
+                                                   const MachineRegisterInfo &RegInfo) const;
+
+  [[nodiscard]] Expected<std::vector<MachineOperand>>
+  createDefaultImplicitOperands(const InstructionDescriptor &Descriptor) const;
+
+private:
+  InstructionSet(std::vector<InstructionDescriptor> Descriptors,
+                 std::vector<ImmediatePredicate> ImmediatePredicates)
+      : Descriptors(std::move(Descriptors)), ImmediatePredicates(std::move(ImmediatePredicates)) {}
+
+  [[nodiscard]] const ImmediatePredicate *
+  immediatePredicate(ImmediatePredicateID ID) const noexcept;
+  [[nodiscard]] Expected<void> validateExplicitOperands(const InstructionDescriptor &Descriptor,
+                                                        std::span<const MachineOperand> Operands,
+                                                        const MachineRegisterInfo &RegInfo) const;
+  [[nodiscard]] Expected<void> validateOperand(const OperandDescriptor &Descriptor,
+                                               const MachineOperand &Operand,
+                                               const MachineRegisterInfo &RegInfo) const;
+
+  std::vector<InstructionDescriptor> Descriptors;
+  std::vector<ImmediatePredicate> ImmediatePredicates;
+  std::unordered_map<Opcode, std::size_t> OpcodeToIndex;
+  std::unordered_map<std::string, std::size_t> NameToIndex;
+  std::unordered_map<ImmediatePredicateID, std::size_t> PredicateToIndex;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_INSTRUCTIONDESCRIPTOR_H
diff --git a/backend/include/rcc/CodeGen/MachineIRTypes.h b/backend/include/rcc/CodeGen/MachineIRTypes.h
index 6d2a710..de6be5a 100644
--- a/backend/include/rcc/CodeGen/MachineIRTypes.h
+++ b/backend/include/rcc/CodeGen/MachineIRTypes.h
@@ -47,6 +47,11 @@ struct SubRegIndexTag;
 struct RegisterBankIDTag;
 struct RegisterClassIDTag;
 struct SchedulingClassIDTag;
+struct ImmediatePredicateIDTag;
+struct NamedOperandIDTag;
+struct TargetOperandTypeIDTag;
+struct EncodingCategoryIDTag;
+struct AssemblyFormatIDTag;
 struct SyncScopeIDTag;
 struct MemoryAliasSourceIDTag;
 struct OriginIDTag;
@@ -61,6 +66,11 @@ using SubRegIndex = MachineIndex<detail::SubRegIndexTag>;
 using RegisterBankID = MachineIndex<detail::RegisterBankIDTag>;
 using RegisterClassID = MachineIndex<detail::RegisterClassIDTag>;
 using SchedulingClassID = MachineIndex<detail::SchedulingClassIDTag>;
+using ImmediatePredicateID = MachineIndex<detail::ImmediatePredicateIDTag>;
+using NamedOperandID = MachineIndex<detail::NamedOperandIDTag>;
+using TargetOperandTypeID = MachineIndex<detail::TargetOperandTypeIDTag>;
+using EncodingCategoryID = MachineIndex<detail::EncodingCategoryIDTag>;
+using AssemblyFormatID = MachineIndex<detail::AssemblyFormatIDTag>;
 using SyncScopeID = MachineIndex<detail::SyncScopeIDTag>;
 using MemoryAliasSourceID = MachineIndex<detail::MemoryAliasSourceIDTag, std::uint64_t>;
 using OriginID = MachineIndex<detail::OriginIDTag, std::uint64_t>;
diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h
index 0da9f25..35cf45b 100644
--- a/backend/include/rcc/CodeGen/MachineOperand.h
+++ b/backend/include/rcc/CodeGen/MachineOperand.h
@@ -213,6 +213,7 @@ public:
     Metadata,
     TargetIndex,
     MCSymbol,
+    Count,
   };
 
   MachineOperand(const MachineOperand &) = delete;
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index ffa5e82..d700d54 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -2,6 +2,7 @@
 
 set(
   RCCBackendCodeGenSources
+  InstructionDescriptor.cpp
   LowLevelType.cpp
   MachineBasicBlock.cpp
   MachineCFGUpdater.cpp
@@ -17,6 +18,7 @@ set(
 )
 set(
   RCCBackendCodeGenHeaders
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlock.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFGUpdater.h"
@@ -61,6 +63,7 @@ install(
 )
 
 rcc_backend_register_format_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
@@ -76,6 +79,7 @@ rcc_backend_register_format_files(
   ${RCCBackendCodeGenHeaders}
 )
 rcc_backend_register_tidy_files(
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptor.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/LowLevelType.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineBasicBlock.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineCFGUpdater.cpp"
diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp
new file mode 100644
index 0000000..e5efad7
--- /dev/null
+++ b/backend/lib/CodeGen/InstructionDescriptor.cpp
@@ -0,0 +1,531 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] bool isRegisterOnly(const OperandKindSet &Kinds) noexcept {
+  OperandKindSet RegisterKind{MachineOperand::Kind::Register};
+  return Kinds == RegisterKind;
+}
+
+[[nodiscard]] bool isDefRole(RegisterOperandRole Role) noexcept {
+  return Role == RegisterOperandRole::Def || Role == RegisterOperandRole::DefUse;
+}
+
+[[nodiscard]] bool isUseRole(RegisterOperandRole Role) noexcept {
+  return Role == RegisterOperandRole::Use || Role == RegisterOperandRole::DefUse;
+}
+
+[[nodiscard]] bool formsDefUsePair(RegisterOperandRole Left, RegisterOperandRole Right) noexcept {
+  return (Left == RegisterOperandRole::Def && Right == RegisterOperandRole::Use) ||
+         (Left == RegisterOperandRole::Use && Right == RegisterOperandRole::Def);
+}
+
+[[nodiscard]] Expected<void> validateDescriptorStructure(const InstructionDescriptor &Descriptor) {
+  if (!Descriptor.InstructionOpcode.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "instruction descriptor opcode is invalid");
+  if (Descriptor.Name.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "instruction descriptor name is empty");
+  if (Descriptor.NumExplicitDefs > Descriptor.Operands.size()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction descriptor explicit def count is out of range");
+  }
+
+  bool SawOptional = false;
+  for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) {
+    const OperandDescriptor &Operand = Descriptor.Operands[Index];
+    if (Operand.Kinds.empty()) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "operand descriptor must accept at least one operand kind");
+    }
+
+    const bool IsRegister = Operand.Kinds.contains(MachineOperand::Kind::Register);
+    if (IsRegister != (Operand.RegisterRole != RegisterOperandRole::None)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "register-capable operand descriptor must declare a register role");
+    }
+    if (isDefRole(Operand.RegisterRole) && !isRegisterOnly(Operand.Kinds)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "register definition descriptor must accept only registers");
+    }
+    if (!IsRegister &&
+        (Operand.RegClass || Operand.RegBank || Operand.EarlyClobber || Operand.AllowSubReg)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "non-register operand descriptor has register constraints");
+    }
+    if (Operand.EarlyClobber && !isDefRole(Operand.RegisterRole)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "early-clobber operand descriptor must define a register");
+    }
+    if (Index < Descriptor.NumExplicitDefs && !isDefRole(Operand.RegisterRole)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "canonical explicit defs must precede instruction uses");
+    }
+    if (Index >= Descriptor.NumExplicitDefs && isDefRole(Operand.RegisterRole)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "register definition appears after the explicit def prefix");
+    }
+
+    if (Descriptor.Variadic && Operand.Optional) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "variadic instruction descriptor cannot contain optional operands");
+    }
+    if (Operand.Optional)
+      SawOptional = true;
+    else if (SawOptional && !Operand.VariadicGroup) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "optional operand descriptors must form a trailing suffix");
+    }
+
+    if (Operand.VariadicGroup &&
+        (!Descriptor.Variadic || Index + 1 != Descriptor.Operands.size())) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "variadic operand group must be the final descriptor");
+    }
+    if (Operand.VariadicGroup && (Operand.Optional || Operand.DefaultTiedOperand)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "variadic operand descriptor cannot be optional or have a default tie");
+    }
+  }
+
+  if (Descriptor.Variadic &&
+      (Descriptor.Operands.empty() || !Descriptor.Operands.back().VariadicGroup)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "variadic instruction descriptor requires a final variadic group");
+  }
+  if (!Descriptor.Variadic &&
+      std::ranges::any_of(Descriptor.Operands,
+                          [](const OperandDescriptor &Operand) { return Operand.VariadicGroup; })) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "non-variadic instruction descriptor has a variadic group");
+  }
+
+  for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) {
+    const OperandDescriptor &Operand = Descriptor.Operands[Index];
+    if (!Operand.DefaultTiedOperand)
+      continue;
+    const std::size_t OtherIndex = *Operand.DefaultTiedOperand;
+    if (OtherIndex >= Descriptor.Operands.size() || OtherIndex == Index ||
+        Descriptor.Operands[OtherIndex].DefaultTiedOperand != Index) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "default operand tie must be reciprocal and in range");
+    }
+    if (Operand.Optional || Descriptor.Operands[OtherIndex].Optional ||
+        !isRegisterOnly(Operand.Kinds) || !isRegisterOnly(Descriptor.Operands[OtherIndex].Kinds) ||
+        !formsDefUsePair(Operand.RegisterRole, Descriptor.Operands[OtherIndex].RegisterRole)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "default operand tie must connect required register def and use");
+    }
+  }
+
+  std::unordered_set<NamedOperandID> OperandNames;
+  for (const OperandDescriptor &Operand : Descriptor.Operands) {
+    if (Operand.Name && !OperandNames.insert(*Operand.Name).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "instruction descriptor has duplicate named operands");
+    }
+  }
+
+  std::unordered_set<PhysicalRegister> ImplicitDefs;
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) {
+    if (!Implicit.Reg.isValid() || !ImplicitDefs.insert(Implicit.Reg).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "implicit definitions must name unique physical registers");
+    }
+  }
+  std::unordered_set<PhysicalRegister> ImplicitUses;
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) {
+    if (!Implicit.Reg.isValid() || Implicit.EarlyClobber ||
+        !ImplicitUses.insert(Implicit.Reg).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "implicit uses must name unique physical registers and cannot "
+                            "early-clobber");
+    }
+  }
+
+  const bool IsBranch = Descriptor.Flags.has(InstructionFlag::Branch);
+  const bool IsTerminator = Descriptor.Flags.has(InstructionFlag::Terminator);
+  if ((IsBranch || Descriptor.Flags.has(InstructionFlag::Return) ||
+       Descriptor.Flags.has(InstructionFlag::Barrier) ||
+       Descriptor.Flags.has(InstructionFlag::IndirectBranch)) &&
+      !IsTerminator) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "branch, return, and barrier descriptors must be terminators");
+  }
+  if (Descriptor.Flags.has(InstructionFlag::IndirectBranch) && !IsBranch) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "indirect branch descriptor must also be a branch");
+  }
+
+  const bool IsPseudo = Descriptor.Flags.has(InstructionFlag::Pseudo);
+  const bool IsMeta = Descriptor.Flags.has(InstructionFlag::Meta);
+  if (IsMeta && (!IsPseudo || Descriptor.Flags.has(InstructionFlag::ProducesCode))) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "meta instruction must be a non-emitting pseudo");
+  }
+  if (!IsPseudo && Descriptor.Owner != PseudoOwner::None) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "non-pseudo instruction cannot have a pseudo owner");
+  }
+  if (IsPseudo && !IsMeta && Descriptor.Owner == PseudoOwner::None) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "executable pseudo must declare its expansion owner");
+  }
+  if (Descriptor.Flags.has(InstructionFlag::TerminalEmission) &&
+      (!IsPseudo || Descriptor.Owner != PseudoOwner::AsmPrinter ||
+       !Descriptor.Flags.has(InstructionFlag::ProducesCode))) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "terminal emission pseudo must produce code and be owned by AsmPrinter");
+  }
+  if (Descriptor.RequiresMemoryOperands && !Descriptor.Flags.has(InstructionFlag::MayLoad) &&
+      !Descriptor.Flags.has(InstructionFlag::MayStore)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "MMO requirement needs mayLoad or mayStore");
+  }
+
+  return {};
+}
+
+[[nodiscard]] const OperandDescriptor &descriptorForOperand(const InstructionDescriptor &Descriptor,
+                                                            std::size_t Index) {
+  if (Index < Descriptor.Operands.size())
+    return Descriptor.Operands[Index];
+  return Descriptor.Operands.back();
+}
+
+} // namespace
+
+OperandKindSet::OperandKindSet(std::initializer_list<MachineOperand::Kind> Kinds) noexcept {
+  for (const MachineOperand::Kind Kind : Kinds)
+    add(Kind);
+}
+
+InstructionFlags::InstructionFlags(std::initializer_list<InstructionFlag> Flags) noexcept {
+  for (const InstructionFlag Flag : Flags)
+    set(Flag);
+}
+
+Expected<InstructionSet>
+InstructionSet::create(std::vector<InstructionDescriptor> Descriptors,
+                       std::vector<ImmediatePredicate> ImmediatePredicates) {
+  if (Descriptors.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "instruction set requires at least one descriptor");
+  }
+
+  InstructionSet Result(std::move(Descriptors), std::move(ImmediatePredicates));
+
+  std::unordered_set<std::string> PredicateNames;
+  for (std::size_t Index = 0; Index < Result.ImmediatePredicates.size(); ++Index) {
+    const ImmediatePredicate &Predicate = Result.ImmediatePredicates[Index];
+    if (Predicate.Name.empty() || !Predicate.Predicate) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "immediate predicate requires a name and callable");
+    }
+    if (!Result.PredicateToIndex.emplace(Predicate.ID, Index).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument, "duplicate immediate predicate ID");
+    }
+    if (!PredicateNames.insert(Predicate.Name).second) {
+      return makeUnexpected(ErrorCode::InvalidArgument, "duplicate immediate predicate name");
+    }
+  }
+
+  for (std::size_t Index = 0; Index < Result.Descriptors.size(); ++Index) {
+    const InstructionDescriptor &Descriptor = Result.Descriptors[Index];
+    const auto Validation = validateDescriptorStructure(Descriptor);
+    if (!Validation)
+      return std::unexpected(Validation.error());
+    if (!Result.OpcodeToIndex.emplace(Descriptor.InstructionOpcode, Index).second)
+      return makeUnexpected(ErrorCode::InvalidArgument, "duplicate instruction opcode");
+    if (!Result.NameToIndex.emplace(Descriptor.Name, Index).second)
+      return makeUnexpected(ErrorCode::InvalidArgument, "duplicate instruction name");
+
+    for (const OperandDescriptor &Operand : Descriptor.Operands) {
+      if (Operand.ImmediatePredicate &&
+          Result.immediatePredicate(*Operand.ImmediatePredicate) == nullptr) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "operand descriptor references an unknown immediate predicate");
+      }
+    }
+  }
+
+  return Result;
+}
+
+const InstructionDescriptor *InstructionSet::descriptor(Opcode InstructionOpcode) const noexcept {
+  const auto Position = OpcodeToIndex.find(InstructionOpcode);
+  if (Position == OpcodeToIndex.end())
+    return nullptr;
+  return &Descriptors[Position->second];
+}
+
+const InstructionDescriptor *InstructionSet::descriptor(std::string_view Name) const noexcept {
+  const auto Position = NameToIndex.find(std::string(Name));
+  if (Position == NameToIndex.end())
+    return nullptr;
+  return &Descriptors[Position->second];
+}
+
+Expected<void> InstructionSet::validateExplicitOperands(const InstructionDescriptor &Descriptor,
+                                                        std::span<const MachineOperand> Operands,
+                                                        const MachineRegisterInfo &RegInfo) const {
+  std::size_t RequiredCount = Descriptor.Operands.size();
+  if (Descriptor.Variadic)
+    --RequiredCount;
+  else {
+    while (RequiredCount != 0 && Descriptor.Operands[RequiredCount - 1].Optional)
+      --RequiredCount;
+  }
+
+  if (Operands.size() < RequiredCount ||
+      (!Descriptor.Variadic && Operands.size() > Descriptor.Operands.size())) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "instruction has an invalid explicit operand count");
+  }
+
+  for (std::size_t Index = 0; Index < Operands.size(); ++Index) {
+    const MachineOperand &Operand = Operands[Index];
+    if (Operand.isImplicit()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "explicit operand sequence contains an implicit register");
+    }
+    const auto Validation =
+        validateOperand(descriptorForOperand(Descriptor, Index), Operand, RegInfo);
+    if (!Validation)
+      return std::unexpected(Validation.error());
+  }
+  return {};
+}
+
+Expected<void> InstructionSet::validateExplicitOperands(Opcode InstructionOpcode,
+                                                        std::span<const MachineOperand> Operands,
+                                                        const MachineRegisterInfo &RegInfo) const {
+  const InstructionDescriptor *Descriptor = descriptor(InstructionOpcode);
+  if (Descriptor == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered");
+  }
+  return validateExplicitOperands(*Descriptor, Operands, RegInfo);
+}
+
+Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descriptor,
+                                               const MachineOperand &Operand,
+                                               const MachineRegisterInfo &RegInfo) const {
+  if (!Descriptor.Kinds.contains(Operand.kind())) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "instruction operand kind does not match its descriptor");
+  }
+  if ((Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "instruction operand uses unregistered target flags");
+  }
+
+  if (Operand.isRegister()) {
+    const bool IsDef = Operand.isDef();
+    const bool IsUse = Operand.isUse();
+    const bool ExpectedDef = isDefRole(Descriptor.RegisterRole);
+    const bool ExpectedUse = isUseRole(Descriptor.RegisterRole);
+    if (IsDef != ExpectedDef || IsUse != ExpectedUse) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "register operand def/use role does not match its descriptor");
+    }
+    if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber) != Descriptor.EarlyClobber) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "register operand early-clobber does not match its descriptor");
+    }
+    if (!Descriptor.AllowSubReg && Operand.subReg().value() != 0) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "register operand has a disallowed subregister index");
+    }
+
+    const Register *Reg = Operand.getIf<Register>();
+    if (Reg == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError, "register operand has inconsistent storage");
+    }
+    if (Reg->isVirtual()) {
+      auto Info = RegInfo.virtualRegisterInfo(*Reg);
+      if (!Info)
+        return std::unexpected(Info.error());
+      if (Descriptor.RegBank && Info->get().Bank != Descriptor.RegBank) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "virtual register bank does not match operand descriptor");
+      }
+      if (Descriptor.RegClass && Info->get().RegClass != Descriptor.RegClass) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "virtual register class does not match operand descriptor");
+      }
+    }
+  }
+
+  if (Descriptor.ImmediatePredicate) {
+    const ImmediatePredicate *Predicate = immediatePredicate(*Descriptor.ImmediatePredicate);
+    if (Predicate == nullptr || !Predicate->Predicate(Operand)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "instruction operand fails its immediate predicate");
+    }
+  }
+
+  return {};
+}
+
+Expected<void> InstructionSet::validateInstruction(const MachineInstr &Instruction,
+                                                   const MachineRegisterInfo &RegInfo) const {
+  const InstructionDescriptor *Descriptor = descriptor(Instruction.opcode());
+  if (Descriptor == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered");
+
+  const auto AllOperands = Instruction.operands();
+  std::size_t ExplicitCount = 0;
+  while (ExplicitCount < AllOperands.size() && !AllOperands[ExplicitCount].isImplicit())
+    ++ExplicitCount;
+  for (std::size_t Index = ExplicitCount; Index < AllOperands.size(); ++Index) {
+    if (!AllOperands[Index].isImplicit()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "explicit operand appears after implicit operands");
+    }
+  }
+
+  const auto ExplicitValidation =
+      validateExplicitOperands(*Descriptor, AllOperands.first(ExplicitCount), RegInfo);
+  if (!ExplicitValidation)
+    return std::unexpected(ExplicitValidation.error());
+
+  for (std::size_t Index = 0; Index < ExplicitCount; ++Index) {
+    const MachineOperand &Operand = AllOperands[Index];
+    const OperandDescriptor &OperandDesc = descriptorForOperand(*Descriptor, Index);
+    if (OperandDesc.DefaultTiedOperand &&
+        Operand.tiedOperandIndex() != OperandDesc.DefaultTiedOperand) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "required descriptor tie is not materialized");
+    }
+    if (!Operand.tiedOperandIndex())
+      continue;
+    const std::size_t OtherIndex = *Operand.tiedOperandIndex();
+    if (OtherIndex >= ExplicitCount || AllOperands[OtherIndex].tiedOperandIndex() != Index ||
+        !Operand.isRegister() || !AllOperands[OtherIndex].isRegister() ||
+        Operand.isDef() == AllOperands[OtherIndex].isDef() ||
+        Operand.isUse() == AllOperands[OtherIndex].isUse()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "instruction operand tie is invalid or not reciprocal");
+    }
+  }
+
+  const std::size_t DefaultImplicitCount =
+      Descriptor->ImplicitDefs.size() + Descriptor->ImplicitUses.size();
+  const std::size_t ActualImplicitCount = AllOperands.size() - ExplicitCount;
+  if (ActualImplicitCount < DefaultImplicitCount ||
+      (!Descriptor->AllowExtraImplicitOperands && ActualImplicitCount != DefaultImplicitCount)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "instruction implicit operand count does not match its descriptor");
+  }
+
+  std::size_t ImplicitIndex = ExplicitCount;
+  auto ValidateImplicit = [&](const ImplicitRegisterDescriptor &Implicit,
+                              bool IsDef) -> Expected<void> {
+    const MachineOperand &Operand = AllOperands[ImplicitIndex++];
+    const auto Reg = Operand.registerValue();
+    if (!Reg || Reg->physicalRegister() != Implicit.Reg || Operand.isDef() != IsDef ||
+        Operand.isUse() == IsDef || !Operand.isImplicit() ||
+        Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber) != Implicit.EarlyClobber ||
+        Operand.registerFlags().has(RegisterOperandFlag::Renamable) != Implicit.Renamable) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "default implicit register operand does not match its descriptor");
+    }
+    return {};
+  };
+
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor->ImplicitDefs) {
+    auto Validation = ValidateImplicit(Implicit, true);
+    if (!Validation)
+      return std::unexpected(Validation.error());
+  }
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor->ImplicitUses) {
+    auto Validation = ValidateImplicit(Implicit, false);
+    if (!Validation)
+      return std::unexpected(Validation.error());
+  }
+  for (; ImplicitIndex < AllOperands.size(); ++ImplicitIndex) {
+    if (!AllOperands[ImplicitIndex].isRegister() || !AllOperands[ImplicitIndex].isImplicit()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "dynamic implicit operand must be an implicit register");
+    }
+  }
+
+  const bool MayLoad = Descriptor->Flags.has(InstructionFlag::MayLoad);
+  const bool MayStore = Descriptor->Flags.has(InstructionFlag::MayStore);
+  if (Descriptor->RequiresMemoryOperands && Instruction.memOperands().empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "memory instruction is missing MachineMemOperand");
+  }
+  for (const MachineMemOperand *MemOperand : Instruction.memOperands()) {
+    if (MemOperand == nullptr || (MemOperand->isLoad() && !MayLoad) ||
+        (MemOperand->isStore() && !MayStore)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "MachineMemOperand access conflicts with instruction descriptor");
+    }
+  }
+  if (!MayLoad && !MayStore && !Instruction.memOperands().empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "non-memory instruction carries MachineMemOperand");
+  }
+
+  return {};
+}
+
+Expected<std::vector<MachineOperand>>
+InstructionSet::createDefaultImplicitOperands(const InstructionDescriptor &Descriptor) const {
+  std::vector<MachineOperand> Result;
+  Result.reserve(Descriptor.ImplicitDefs.size() + Descriptor.ImplicitUses.size());
+
+  auto AppendImplicit = [&Result](const ImplicitRegisterDescriptor &Implicit,
+                                  bool IsDef) -> Expected<void> {
+    RegisterOperandFlags Flags{
+        IsDef ? RegisterOperandFlag::Define : RegisterOperandFlag::Use,
+        RegisterOperandFlag::Implicit,
+    };
+    if (Implicit.EarlyClobber)
+      Flags.set(RegisterOperandFlag::EarlyClobber);
+    if (Implicit.Renamable)
+      Flags.set(RegisterOperandFlag::Renamable);
+
+    auto Operand = MachineOperand::registerOperand(Register::fromPhysical(Implicit.Reg), Flags);
+    if (!Operand)
+      return std::unexpected(Operand.error());
+    Result.push_back(std::move(*Operand));
+    return {};
+  };
+
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) {
+    auto AppendResult = AppendImplicit(Implicit, true);
+    if (!AppendResult)
+      return std::unexpected(AppendResult.error());
+  }
+  for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) {
+    auto AppendResult = AppendImplicit(Implicit, false);
+    if (!AppendResult)
+      return std::unexpected(AppendResult.error());
+  }
+  return Result;
+}
+
+const ImmediatePredicate *
+InstructionSet::immediatePredicate(ImmediatePredicateID ID) const noexcept {
+  const auto Position = PredicateToIndex.find(ID);
+  if (Position == PredicateToIndex.end())
+    return nullptr;
+  return &ImmediatePredicates[Position->second];
+}
+
+} // namespace rcc
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index cad2a44..a3aefde 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -3,6 +3,7 @@
 set(
   RCCBackendCodeGenTestSources
   CoreTypesTest.cpp
+  InstructionDescriptorTest.cpp
   MachineIRCoreTest.cpp
   MachineValueTypesTest.cpp
 )
@@ -13,6 +14,21 @@ target_link_libraries(RCCBackendCodeGenCoreTypesTests PRIVATE RCCBackend::CodeGe
 
 add_test(NAME RCCBackend.CodeGen.CoreTypes COMMAND RCCBackendCodeGenCoreTypesTests)
 
+add_executable(
+  RCCBackendCodeGenInstructionDescriptorTests
+  InstructionDescriptorTest.cpp
+)
+rcc_backend_configure_target(RCCBackendCodeGenInstructionDescriptorTests)
+target_link_libraries(
+  RCCBackendCodeGenInstructionDescriptorTests
+  PRIVATE RCCBackend::CodeGen
+)
+
+add_test(
+  NAME RCCBackend.CodeGen.InstructionDescriptor
+  COMMAND RCCBackendCodeGenInstructionDescriptorTests
+)
+
 add_executable(RCCBackendCodeGenMachineValueTypesTests MachineValueTypesTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenMachineValueTypesTests)
 target_link_libraries(RCCBackendCodeGenMachineValueTypesTests PRIVATE RCCBackend::CodeGen)
@@ -33,11 +49,13 @@ add_test(
 
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/CoreTypesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/InstructionDescriptorTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineValueTypesTest.cpp"
 )
diff --git a/backend/unittests/CodeGen/InstructionDescriptorTest.cpp b/backend/unittests/CodeGen/InstructionDescriptorTest.cpp
new file mode 100644
index 0000000..424d2e4
--- /dev/null
+++ b/backend/unittests/CodeGen/InstructionDescriptorTest.cpp
@@ -0,0 +1,358 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++FailureCount;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return FailureCount == 0 ? 0 : 1;
+  }
+
+private:
+  int FailureCount = 0;
+};
+
+[[nodiscard]] rcc::OperandDescriptor registerDescriptor(rcc::RegisterOperandRole Role) {
+  rcc::OperandDescriptor Descriptor;
+  Descriptor.Kinds = {rcc::MachineOperand::Kind::Register};
+  Descriptor.RegisterRole = Role;
+  return Descriptor;
+}
+
+[[nodiscard]] rcc::InstructionDescriptor minimalDescriptor(std::uint32_t OpcodeValue,
+                                                           std::string Name) {
+  rcc::InstructionDescriptor Descriptor;
+  Descriptor.InstructionOpcode = rcc::Opcode::fromValue(OpcodeValue);
+  Descriptor.Name = std::move(Name);
+  Descriptor.Flags = {rcc::InstructionFlag::ProducesCode};
+  return Descriptor;
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineOperand> registerOperand(rcc::Register Reg,
+                                                                 rcc::RegisterOperandFlags Flags,
+                                                                 rcc::SubRegIndex SubReg = {},
+                                                                 std::uint32_t TargetFlags = 0) {
+  return rcc::MachineOperand::registerOperand(Reg, Flags, SubReg, TargetFlags);
+}
+
+[[nodiscard]] rcc::MachineMemOperandDesc loadDescription() {
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = {rcc::MemoryAccessFlag::Load};
+  Description.Size = *rcc::MemorySize::fixed(8);
+  Description.Align = *rcc::Alignment::create(8);
+  Description.Base = rcc::MemoryBase::frameIndex(rcc::FrameIndex::fromValue(0));
+  return Description;
+}
+
+[[nodiscard]] rcc::Expected<rcc::InstructionSet> createValidInstructionSet() {
+  constexpr std::uint32_t AddOpcode = 1;
+  constexpr std::uint32_t TwoAddressOpcode = 2;
+  constexpr std::uint32_t LoadOpcode = 3;
+
+  rcc::InstructionDescriptor Add = minimalDescriptor(AddOpcode, "TEST_ADDri");
+  auto Def = registerDescriptor(rcc::RegisterOperandRole::Def);
+  Def.RegBank = rcc::RegisterBankID::fromValue(7);
+  Def.RegClass = rcc::RegisterClassID::fromValue(8);
+  Def.Name = rcc::NamedOperandID::fromValue(1);
+
+  auto Source = registerDescriptor(rcc::RegisterOperandRole::Use);
+  Source.Name = rcc::NamedOperandID::fromValue(2);
+
+  rcc::OperandDescriptor RegisterOrImmediate;
+  RegisterOrImmediate.Kinds = {
+      rcc::MachineOperand::Kind::Register,
+      rcc::MachineOperand::Kind::Immediate,
+  };
+  RegisterOrImmediate.RegisterRole = rcc::RegisterOperandRole::Use;
+  RegisterOrImmediate.ImmediatePredicate = rcc::ImmediatePredicateID::fromValue(1);
+  RegisterOrImmediate.Name = rcc::NamedOperandID::fromValue(3);
+  RegisterOrImmediate.AllowedTargetFlags = 0x3;
+
+  Add.Operands.push_back(Def);
+  Add.Operands.push_back(Source);
+  Add.Operands.push_back(RegisterOrImmediate);
+  Add.NumExplicitDefs = 1;
+  Add.ImplicitDefs.push_back(
+      rcc::ImplicitRegisterDescriptor{*rcc::PhysicalRegister::create(1), false, true});
+  Add.ImplicitUses.push_back(rcc::ImplicitRegisterDescriptor{*rcc::PhysicalRegister::create(2)});
+
+  rcc::InstructionDescriptor TwoAddress = minimalDescriptor(TwoAddressOpcode, "TEST_TWOADDR");
+  auto TiedDef = registerDescriptor(rcc::RegisterOperandRole::Def);
+  auto TiedUse = registerDescriptor(rcc::RegisterOperandRole::Use);
+  TiedDef.DefaultTiedOperand = 1;
+  TiedUse.DefaultTiedOperand = 0;
+  TwoAddress.Operands.push_back(TiedDef);
+  TwoAddress.Operands.push_back(TiedUse);
+  TwoAddress.NumExplicitDefs = 1;
+
+  rcc::InstructionDescriptor Load = minimalDescriptor(LoadOpcode, "TEST_LOAD");
+  Load.Flags.set(rcc::InstructionFlag::MayLoad);
+  Load.RequiresMemoryOperands = true;
+
+  rcc::ImmediatePredicate Signed12;
+  Signed12.ID = rcc::ImmediatePredicateID::fromValue(1);
+  Signed12.Name = "register-or-simm12";
+  Signed12.Predicate = [](const rcc::MachineOperand &Operand) {
+    if (Operand.isRegister())
+      return true;
+    const auto *Value = Operand.getIf<std::int64_t>();
+    return Value != nullptr && *Value >= -2048 && *Value <= 2047;
+  };
+
+  std::vector<rcc::InstructionDescriptor> Descriptors;
+  Descriptors.push_back(std::move(Add));
+  Descriptors.push_back(std::move(TwoAddress));
+  Descriptors.push_back(std::move(Load));
+  std::vector<rcc::ImmediatePredicate> Predicates;
+  Predicates.push_back(std::move(Signed12));
+  return rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates));
+}
+
+void testDescriptorStructure(TestContext &Context) {
+  Context.expect(!rcc::InstructionSet::create({}), "an empty instruction set must be rejected");
+
+  auto DefAfterUses = minimalDescriptor(10, "BAD_DEF_ORDER");
+  DefAfterUses.Operands.push_back(registerDescriptor(rcc::RegisterOperandRole::Def));
+  Context.expect(!rcc::InstructionSet::create({DefAfterUses}),
+                 "a definition outside the explicit def prefix must be rejected");
+
+  auto AmbiguousVariadic = minimalDescriptor(11, "BAD_VARIADIC");
+  auto Optional = registerDescriptor(rcc::RegisterOperandRole::Use);
+  Optional.Optional = true;
+  auto Variadic = registerDescriptor(rcc::RegisterOperandRole::Use);
+  Variadic.VariadicGroup = true;
+  AmbiguousVariadic.Operands.push_back(Optional);
+  AmbiguousVariadic.Operands.push_back(Variadic);
+  AmbiguousVariadic.Variadic = true;
+  Context.expect(!rcc::InstructionSet::create({AmbiguousVariadic}),
+                 "optional and variadic operand tails must not be combined");
+
+  auto BadTie = minimalDescriptor(12, "BAD_TIE");
+  auto Def = registerDescriptor(rcc::RegisterOperandRole::Def);
+  auto Use = registerDescriptor(rcc::RegisterOperandRole::Use);
+  Def.DefaultTiedOperand = 1;
+  BadTie.Operands.push_back(Def);
+  BadTie.Operands.push_back(Use);
+  BadTie.NumExplicitDefs = 1;
+  Context.expect(!rcc::InstructionSet::create({BadTie}), "default operand ties must be reciprocal");
+
+  auto DuplicateNames = minimalDescriptor(13, "BAD_NAMES");
+  auto FirstUse = registerDescriptor(rcc::RegisterOperandRole::Use);
+  auto SecondUse = registerDescriptor(rcc::RegisterOperandRole::Use);
+  FirstUse.Name = rcc::NamedOperandID::fromValue(9);
+  SecondUse.Name = rcc::NamedOperandID::fromValue(9);
+  DuplicateNames.Operands.push_back(FirstUse);
+  DuplicateNames.Operands.push_back(SecondUse);
+  Context.expect(!rcc::InstructionSet::create({DuplicateNames}),
+                 "named operand IDs must be unique within an instruction");
+
+  auto BadBranch = minimalDescriptor(14, "BAD_BRANCH");
+  BadBranch.Flags.set(rcc::InstructionFlag::Branch);
+  Context.expect(!rcc::InstructionSet::create({BadBranch}),
+                 "branch descriptors must also be terminators");
+
+  auto UnknownPredicate = minimalDescriptor(15, "BAD_PREDICATE");
+  rcc::OperandDescriptor Immediate;
+  Immediate.Kinds = {rcc::MachineOperand::Kind::Immediate};
+  Immediate.ImmediatePredicate = rcc::ImmediatePredicateID::fromValue(99);
+  UnknownPredicate.Operands.push_back(Immediate);
+  Context.expect(!rcc::InstructionSet::create({UnknownPredicate}),
+                 "operand descriptors must not reference unknown predicates");
+}
+
+void testOperandValidation(TestContext &Context) {
+  auto InstructionSet = createValidInstructionSet();
+  Context.expect(InstructionSet.has_value(), "the complete test instruction set must be valid");
+  if (!InstructionSet)
+    return;
+
+  auto Function = rcc::MachineFunction::create("descriptor_operands",
+                                               rcc::MachineFunctionStableID::fromValue(1));
+  Context.expect(Function.has_value(), "descriptor test function must be valid");
+  if (!Function)
+    return;
+
+  auto I64 = rcc::LLT::makeInteger(64);
+  auto Destination = (*Function)->registerInfo().createVirtualRegister(*I64);
+  auto Source = (*Function)->registerInfo().createVirtualRegister(*I64);
+  Context.expect(Destination && Source, "descriptor test virtual registers must be allocated");
+  if (!Destination || !Source)
+    return;
+
+  auto &RegInfo = (*Function)->registerInfo();
+  Context.expect(
+      RegInfo.setRegisterBank(*Destination, rcc::RegisterBankID::fromValue(7)).has_value() &&
+          RegInfo.setRegisterClass(*Destination, rcc::RegisterClassID::fromValue(8)).has_value(),
+      "descriptor test destination constraints must be recorded");
+
+  std::vector<rcc::MachineOperand> ValidOperands;
+  ValidOperands.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Define}));
+  ValidOperands.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
+  ValidOperands.push_back(rcc::MachineOperand::immediate(42, 0x1));
+  Context.expect(
+      InstructionSet->validateExplicitOperands(rcc::Opcode::fromValue(1), ValidOperands, RegInfo)
+          .has_value(),
+      "matching roles, constraints, flags, and predicate must validate");
+
+  std::vector<rcc::MachineOperand> WrongRole;
+  WrongRole.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Use}));
+  WrongRole.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
+  WrongRole.push_back(rcc::MachineOperand::immediate(1));
+  Context.expect(
+      !InstructionSet->validateExplicitOperands(rcc::Opcode::fromValue(1), WrongRole, RegInfo),
+      "a register role mismatch must be rejected");
+
+  std::vector<rcc::MachineOperand> BadImmediate;
+  BadImmediate.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Define}));
+  BadImmediate.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
+  BadImmediate.push_back(rcc::MachineOperand::immediate(4096));
+  Context.expect(
+      !InstructionSet->validateExplicitOperands(rcc::Opcode::fromValue(1), BadImmediate, RegInfo),
+      "an operand outside its immediate predicate must be rejected");
+
+  std::vector<rcc::MachineOperand> BadTargetFlags;
+  BadTargetFlags.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Define}));
+  BadTargetFlags.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
+  BadTargetFlags.push_back(rcc::MachineOperand::immediate(1, 0x4));
+  Context.expect(
+      !InstructionSet->validateExplicitOperands(rcc::Opcode::fromValue(1), BadTargetFlags, RegInfo),
+      "unregistered target operand flags must be rejected");
+}
+
+void testInstructionValidation(TestContext &Context) {
+  auto InstructionSet = createValidInstructionSet();
+  auto Function = rcc::MachineFunction::create("descriptor_instructions",
+                                               rcc::MachineFunctionStableID::fromValue(2));
+  Context.expect(InstructionSet && Function, "instruction validation setup must succeed");
+  if (!InstructionSet || !Function)
+    return;
+
+  auto I64 = rcc::LLT::makeInteger(64);
+  auto Reg = (*Function)->registerInfo().createVirtualRegister(*I64);
+  Context.expect(Reg.has_value(), "instruction validation register must be allocated");
+  if (!Reg)
+    return;
+
+  auto Tied = (*Function)->createInstruction(rcc::Opcode::fromValue(2));
+  Context.expect(Tied.has_value(), "tied instruction must be allocated");
+  if (!Tied)
+    return;
+  Context.expect(
+      (*Tied)->addOperand(*registerOperand(*Reg, {rcc::RegisterOperandFlag::Define})).has_value() &&
+          (*Tied)
+              ->addOperand(*registerOperand(*Reg, {rcc::RegisterOperandFlag::Use}))
+              .has_value() &&
+          (*Tied)->tieOperands(0, 1).has_value(),
+      "tied instruction operands must be materialized");
+  Context.expect(
+      InstructionSet->validateInstruction(**Tied, (*Function)->registerInfo()).has_value(),
+      "a reciprocal descriptor-required tie must validate");
+
+  auto Untied = (*Function)->createInstruction(rcc::Opcode::fromValue(2));
+  Context.expect(Untied.has_value(), "untied instruction must be allocated");
+  if (Untied) {
+    Context.expect((*Untied)
+                           ->addOperand(*registerOperand(*Reg, {rcc::RegisterOperandFlag::Define}))
+                           .has_value() &&
+                       (*Untied)
+                           ->addOperand(*registerOperand(*Reg, {rcc::RegisterOperandFlag::Use}))
+                           .has_value(),
+                   "untied instruction operands must be added");
+    Context.expect(!InstructionSet->validateInstruction(**Untied, (*Function)->registerInfo()),
+                   "a missing descriptor-required tie must be rejected");
+  }
+
+  auto Destination = (*Function)->registerInfo().createVirtualRegister(*I64);
+  auto Source = (*Function)->registerInfo().createVirtualRegister(*I64);
+  Context.expect(Destination && Source, "implicit operand validation registers must be allocated");
+  if (!Destination || !Source)
+    return;
+  auto &RegInfo = (*Function)->registerInfo();
+  Context.expect(
+      RegInfo.setRegisterBank(*Destination, rcc::RegisterBankID::fromValue(7)).has_value() &&
+          RegInfo.setRegisterClass(*Destination, rcc::RegisterClassID::fromValue(8)).has_value(),
+      "implicit validation destination constraints must be recorded");
+
+  auto WithImplicit = (*Function)->createInstruction(rcc::Opcode::fromValue(1));
+  const rcc::InstructionDescriptor *AddDescriptor =
+      InstructionSet->descriptor(rcc::Opcode::fromValue(1));
+  Context.expect(WithImplicit && AddDescriptor != nullptr,
+                 "implicit instruction setup must find its descriptor");
+  if (!WithImplicit || AddDescriptor == nullptr)
+    return;
+  Context.expect(
+      (*WithImplicit)
+              ->addOperand(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Define}))
+              .has_value() &&
+          (*WithImplicit)
+              ->addOperand(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}))
+              .has_value() &&
+          (*WithImplicit)->addOperand(rcc::MachineOperand::immediate(7)).has_value(),
+      "explicit operands for implicit validation must be added");
+  auto DefaultImplicit = InstructionSet->createDefaultImplicitOperands(*AddDescriptor);
+  Context.expect(DefaultImplicit.has_value(), "default implicit operands must be constructible");
+  if (!DefaultImplicit)
+    return;
+  for (rcc::MachineOperand &Operand : *DefaultImplicit) {
+    Context.expect((*WithImplicit)->addOperand(std::move(Operand)).has_value(),
+                   "default implicit operand insertion must succeed");
+  }
+  Context.expect(InstructionSet->validateInstruction(**WithImplicit, RegInfo).has_value(),
+                 "exact default implicit operands must validate");
+
+  rcc::MachineOperand *ImplicitDef = (*WithImplicit)->operandAt(3);
+  Context.expect(ImplicitDef != nullptr &&
+                     ImplicitDef
+                         ->setRegisterFlags(
+                             {rcc::RegisterOperandFlag::Define, rcc::RegisterOperandFlag::Implicit})
+                         .has_value(),
+                 "implicit definition flags must be mutable for a negative test");
+  Context.expect(!InstructionSet->validateInstruction(**WithImplicit, RegInfo),
+                 "implicit renamable state must match the descriptor exactly");
+
+  auto Load = (*Function)->createInstruction(rcc::Opcode::fromValue(3));
+  Context.expect(Load.has_value(), "load instruction must be allocated");
+  if (!Load)
+    return;
+  Context.expect(!InstructionSet->validateInstruction(**Load, RegInfo),
+                 "an MMO-required load without an MMO must be rejected");
+  auto MemOperand = (*Function)->createMemOperand(loadDescription());
+  Context.expect(MemOperand.has_value() && (*Load)->addMemOperand(**MemOperand).has_value(),
+                 "a function-owned load MMO must attach");
+  Context.expect(InstructionSet->validateInstruction(**Load, RegInfo).has_value(),
+                 "an MMO matching mayLoad must validate");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  testDescriptorStructure(Context);
+  testOperandValidation(Context);
+  testInstructionValidation(Context);
+  return Context.result();
+}