7 files changed, 1259 insertions, 36 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 68ebf04..3a45cec 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -23,7 +23,9 @@ set(
   Register.cpp
   RegisterMask.cpp
   TargetConstant.cpp
+  TargetDescription.cpp
   TargetFunctionState.cpp
+  TargetRegisterInfo.cpp
 )
 set(
   RCCBackendCodeGenHeaders
@@ -49,7 +51,9 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetConstant.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetDescription.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFunctionState.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterInfo.h"
 )
 
 add_library(RCCBackendCodeGen ${RCCBackendCodeGenSources})
@@ -102,7 +106,9 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp"
   ${RCCBackendCodeGenHeaders}
 )
 rcc_backend_register_tidy_files(
@@ -127,5 +133,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp"
 )
diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp
index 9f4a178..3d97440 100644
--- a/backend/lib/CodeGen/InstructionDescriptor.cpp
+++ b/backend/lib/CodeGen/InstructionDescriptor.cpp
@@ -493,14 +493,6 @@ Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descript
       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");
-      }
     }
   }
 
diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp
index a8fe15e..d365fd0 100644
--- a/backend/lib/CodeGen/MachineFunctionCloner.cpp
+++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp
@@ -15,6 +15,7 @@
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
 #include "rcc/CodeGen/TargetFunctionState.h"
 
 #include <cstddef>
@@ -553,9 +554,9 @@ MachineFunctionCloneResult::operator=(MachineFunctionCloneResult &&) noexcept =
 MachineFunctionCloneResult::~MachineFunctionCloneResult() = default;
 
 Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction &Source,
-                                                          const InstructionSet &Instructions,
+                                                          const TargetDescription &Target,
                                                           MachineFunctionCloneOptions Options) {
-  auto SourceVerification = MachineVerifier::verify(Source, Instructions);
+  auto SourceVerification = MachineVerifier::verify(Source, Target);
   if (!SourceVerification)
     return std::unexpected(SourceVerification.error());
   if (!Options.NewStableID.isValid()) {
@@ -615,7 +616,7 @@ Expected<MachineFunctionCloneResult> cloneMachineFunction(const MachineFunction
     return std::unexpected(CompilationStatus.error());
   Result.ClonedFunction->compilationStatus() = std::move(*CompilationStatus);
   Result.ClonedFunction->properties() = Source.properties();
-  auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Instructions);
+  auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Target);
   if (!DestinationVerification)
     return std::unexpected(DestinationVerification.error());
   return Result;
diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp
index 74ca55b..7f6421b 100644
--- a/backend/lib/CodeGen/MachineIRBuilder.cpp
+++ b/backend/lib/CodeGen/MachineIRBuilder.cpp
@@ -20,16 +20,15 @@
 
 namespace rcc {
 
-MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function,
-                                         const InstructionSet &Instructions,
+MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, const TargetDescription &Target,
                                          const InstructionDescriptor &Descriptor,
                                          MachineBasicBlock &InsertBlock,
                                          MachineInstr *InsertBefore) noexcept
-    : Function(&Function), Instructions(&Instructions), Descriptor(&Descriptor),
-      InsertBlock(&InsertBlock), InsertBefore(InsertBefore) {}
+    : Function(&Function), Target(&Target), Descriptor(&Descriptor), InsertBlock(&InsertBlock),
+      InsertBefore(InsertBefore) {}
 
 MachineInstrBuilder::MachineInstrBuilder(MachineInstrBuilder &&Other) noexcept
-    : Function(Other.Function), Instructions(Other.Instructions), Descriptor(Other.Descriptor),
+    : Function(Other.Function), Target(Other.Target), Descriptor(Other.Descriptor),
       InsertBlock(Other.InsertBlock), InsertBefore(Other.InsertBefore),
       ExplicitOperands(std::move(Other.ExplicitOperands)),
       ExtraImplicitOperands(std::move(Other.ExtraImplicitOperands)),
@@ -37,7 +36,7 @@ MachineInstrBuilder::MachineInstrBuilder(MachineInstrBuilder &&Other) noexcept
       Flags(Other.Flags), Location(std::move(Other.Location)), Origin(Other.Origin),
       IsBuilt(Other.IsBuilt) {
   Other.Function = nullptr;
-  Other.Instructions = nullptr;
+  Other.Target = nullptr;
   Other.Descriptor = nullptr;
   Other.InsertBlock = nullptr;
   Other.InsertBefore = nullptr;
@@ -49,7 +48,7 @@ MachineInstrBuilder &MachineInstrBuilder::operator=(MachineInstrBuilder &&Other)
     return *this;
 
   Function = Other.Function;
-  Instructions = Other.Instructions;
+  Target = Other.Target;
   Descriptor = Other.Descriptor;
   InsertBlock = Other.InsertBlock;
   InsertBefore = Other.InsertBefore;
@@ -63,7 +62,7 @@ MachineInstrBuilder &MachineInstrBuilder::operator=(MachineInstrBuilder &&Other)
   IsBuilt = Other.IsBuilt;
 
   Other.Function = nullptr;
-  Other.Instructions = nullptr;
+  Other.Target = nullptr;
   Other.Descriptor = nullptr;
   Other.InsertBlock = nullptr;
   Other.InsertBefore = nullptr;
@@ -448,12 +447,12 @@ Expected<MachineInstr *> MachineInstrBuilder::build() {
     }
   }
 
-  auto ExplicitValidation = Instructions->validateExplicitOperands(
+  auto ExplicitValidation = Target->validateExplicitOperands(
       Descriptor->InstructionOpcode, ExplicitOperands, Function->registerInfo());
   if (!ExplicitValidation)
     return std::unexpected(ExplicitValidation.error());
 
-  auto DefaultImplicit = Instructions->createDefaultImplicitOperands(*Descriptor);
+  auto DefaultImplicit = Target->createDefaultImplicitOperands(*Descriptor);
   if (!DefaultImplicit)
     return std::unexpected(DefaultImplicit.error());
 
@@ -463,19 +462,23 @@ Expected<MachineInstr *> MachineInstrBuilder::build() {
     ImplicitOperands.push_back(&Operand);
   for (const MachineOperand &Operand : ExtraImplicitOperands)
     ImplicitOperands.push_back(&Operand);
-  auto ImplicitValidation =
-      Instructions->validateImplicitOperands(Descriptor->InstructionOpcode, ImplicitOperands);
+  auto ImplicitValidation = Target->validateImplicitOperands(
+      Descriptor->InstructionOpcode, ImplicitOperands, Function->registerInfo());
   if (!ImplicitValidation)
     return std::unexpected(ImplicitValidation.error());
 
   const std::vector<MachineOperandTie> Ties = collectOperandTies();
-  auto TieValidation =
-      Instructions->validateOperandTies(Descriptor->InstructionOpcode, ExplicitOperands, Ties);
+  auto TieValidation = Target->validateOperandTies(Descriptor->InstructionOpcode, ExplicitOperands,
+                                                   Ties, Function->registerInfo());
   if (!TieValidation)
     return std::unexpected(TieValidation.error());
 
-  auto MemoryValidation =
-      Instructions->validateMemOperands(Descriptor->InstructionOpcode, MemOperands);
+  auto EarlyClobberValidation =
+      Target->validateEarlyClobber(ExplicitOperands, ImplicitOperands, Ties);
+  if (!EarlyClobberValidation)
+    return std::unexpected(EarlyClobberValidation.error());
+
+  auto MemoryValidation = Target->validateMemOperands(Descriptor->InstructionOpcode, MemOperands);
   if (!MemoryValidation)
     return std::unexpected(MemoryValidation.error());
 
@@ -577,7 +580,7 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc
   if (InsertBlock == nullptr) {
     return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point");
   }
-  const InstructionDescriptor *Descriptor = Instructions->descriptor(InstructionOpcode);
+  const InstructionDescriptor *Descriptor = Target->instructionDescriptor(InstructionOpcode);
   if (Descriptor == nullptr) {
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine IR builder opcode is not registered");
@@ -589,7 +592,7 @@ Expected<MachineInstrBuilder> MachineIRBuilder::buildInstr(Opcode InstructionOpc
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine IR builder insertion cursor is stale");
   }
-  return MachineInstrBuilder(*Function, *Instructions, *Descriptor, *InsertBlock, InsertBefore);
+  return MachineInstrBuilder(*Function, *Target, *Descriptor, *InsertBlock, InsertBefore);
 }
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index 0c05a07..b507079 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -26,9 +26,9 @@ namespace {
 
 class FunctionVerifier final {
 public:
-  FunctionVerifier(const MachineFunction &Function, const InstructionSet &Instructions,
+  FunctionVerifier(const MachineFunction &Function, const TargetDescription &Target,
                    MachineVerifierOptions Options) noexcept
-      : Function(Function), Instructions(Instructions), Options(Options) {}
+      : Function(Function), Target(Target), Options(Options) {}
 
   [[nodiscard]] Expected<void> run() {
     if (Function.name().empty() || !Function.stableID().isValid())
@@ -346,10 +346,10 @@ private:
     if (!LocalResult)
       return LocalResult;
 
-    const InstructionDescriptor *Descriptor = Instructions.descriptor(Instruction.opcode());
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
     if (Descriptor == nullptr)
       return fail("live instruction uses an unregistered opcode");
-    auto DescriptorResult = Instructions.validateInstruction(Instruction, Function.registerInfo());
+    auto DescriptorResult = Target.validateInstruction(Instruction, Function.registerInfo());
     if (!DescriptorResult)
       return failWith("instruction descriptor", DescriptorResult.error());
 
@@ -466,6 +466,9 @@ private:
           return fail("block live-in list contains invalid or duplicate entries");
         }
       }
+      auto TargetLiveInResult = Target.validateBlockLiveIns(*Block);
+      if (!TargetLiveInResult)
+        return failWith("block live-ins", TargetLiveInResult.error());
     }
     return {};
   }
@@ -509,6 +512,9 @@ private:
           return fail("virtual register has an invalid or duplicate allocation hint");
       }
     }
+    auto TargetResult = Target.validateRegisterInfo(RegInfo);
+    if (!TargetResult)
+      return failWith("target register info", TargetResult.error());
     return {};
   }
 
@@ -577,7 +583,7 @@ private:
   }
 
   const MachineFunction &Function;
-  const InstructionSet &Instructions;
+  const TargetDescription &Target;
   MachineVerifierOptions Options;
   std::unordered_set<const MachineBasicBlock *> RegisteredBlocks;
   std::unordered_set<const MachineBasicBlock *> LinkedBlocks;
@@ -600,9 +606,9 @@ private:
 } // namespace
 
 Expected<void> MachineVerifier::verify(const MachineFunction &Function,
-                                       const InstructionSet &Instructions,
+                                       const TargetDescription &Target,
                                        MachineVerifierOptions Options) {
-  return FunctionVerifier(Function, Instructions, Options).run();
+  return FunctionVerifier(Function, Target, Options).run();
 }
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp
new file mode 100644
index 0000000..3a6ea31
--- /dev/null
+++ b/backend/lib/CodeGen/TargetDescription.cpp
@@ -0,0 +1,610 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] const OperandDescriptor &descriptorForOperand(const InstructionDescriptor &Descriptor,
+                                                            std::size_t Index) {
+  if (Index < Descriptor.Operands.size())
+    return Descriptor.Operands[Index];
+  return Descriptor.Operands.back();
+}
+
+[[nodiscard]] std::uint64_t minimumTypeSizeInBits(LLT Type) noexcept {
+  if (Type.isToken())
+    return 0;
+  const std::uint64_t ScalarSize = Type.scalarBitWidth();
+  if (!Type.isVector())
+    return ScalarSize;
+  return ScalarSize * Type.minimumElementCount();
+}
+
+[[nodiscard]] bool isPureDef(const MachineOperand &Operand) noexcept {
+  return Operand.isRegister() && Operand.isDef() && !Operand.isUse();
+}
+
+[[nodiscard]] bool isPureUse(const MachineOperand &Operand) noexcept {
+  return Operand.isRegister() && Operand.isUse() && !Operand.isDef();
+}
+
+} // namespace
+
+Expected<TargetDescription> TargetDescription::create(InstructionSet Instructions,
+                                                      TargetRegisterInfo Registers) {
+  for (const InstructionDescriptor &Instruction : Instructions.descriptors()) {
+    for (const OperandDescriptor &Operand : Instruction.Operands) {
+      if (Operand.RegClass && Registers.registerClass(*Operand.RegClass) == nullptr) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "instruction operand references an unknown target register class");
+      }
+      if (Operand.RegBank && Registers.registerBank(*Operand.RegBank) == nullptr) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "instruction operand references an unknown target register bank");
+      }
+      if (Operand.RegClass && Operand.RegBank &&
+          !Registers.bankCoversClass(*Operand.RegBank, *Operand.RegClass)) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "instruction operand register class is not covered by its bank");
+      }
+    }
+
+    auto ValidateImplicit =
+        [&Registers](const ImplicitRegisterDescriptor &Implicit) -> Expected<void> {
+      const PhysicalRegisterDesc *Register = Registers.physicalRegister(Implicit.Reg);
+      if (Register == nullptr) {
+        return makeUnexpected(
+            ErrorCode::InvalidArgument,
+            "instruction implicit operand references an unknown physical register");
+      }
+      if (Implicit.Renamable && (Register->IsConstant || Register->IsArtificial)) {
+        return makeUnexpected(
+            ErrorCode::InvalidArgument,
+            "renamable implicit operand references a constant or artificial register");
+      }
+      return {};
+    };
+    for (const ImplicitRegisterDescriptor &Implicit : Instruction.ImplicitDefs) {
+      auto Validation = ValidateImplicit(Implicit);
+      if (!Validation)
+        return std::unexpected(Validation.error());
+    }
+    for (const ImplicitRegisterDescriptor &Implicit : Instruction.ImplicitUses) {
+      auto Validation = ValidateImplicit(Implicit);
+      if (!Validation)
+        return std::unexpected(Validation.error());
+    }
+    for (const ImplicitRegisterDescriptor &Def : Instruction.ImplicitDefs) {
+      if (!Def.EarlyClobber)
+        continue;
+      if (std::ranges::any_of(Instruction.ImplicitUses,
+                              [&Registers, Def](const ImplicitRegisterDescriptor &Use) {
+                                return Registers.regsOverlap(Def.Reg, Use.Reg);
+                              })) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "early-clobber implicit definition overlaps an implicit use");
+      }
+    }
+  }
+
+  return TargetDescription(std::move(Instructions), std::move(Registers));
+}
+
+Expected<void> TargetDescription::validateVirtualRegister(Register Reg,
+                                                          const VirtualRegisterInfo &Info) const {
+  if (!Reg.isVirtual()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "target virtual-register validation received a non-virtual register");
+  }
+
+  const RegisterBankDesc *Bank = nullptr;
+  if (Info.Bank) {
+    Bank = Registers.registerBank(*Info.Bank);
+    if (Bank == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register references an unknown target register bank");
+    }
+  }
+
+  const RegisterClassDesc *Class = nullptr;
+  if (Info.RegClass) {
+    Class = Registers.registerClass(*Info.RegClass);
+    if (Class == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register references an unknown target register class");
+    }
+  }
+
+  if (Info.Bank && Info.RegClass && !Registers.bankCoversClass(*Info.Bank, *Info.RegClass)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "virtual register class is not covered by its selected register bank");
+  }
+
+  if (Info.Type) {
+    const std::uint64_t MinimumSize = minimumTypeSizeInBits(*Info.Type);
+    if (MinimumSize == 0 && (Bank != nullptr || Class != nullptr)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "token virtual register cannot have a bank or register class");
+    }
+    if (Bank != nullptr && MinimumSize > Bank->MaximumSizeInBits) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register type exceeds its register bank maximum size");
+    }
+    if (Class != nullptr && MinimumSize > Class->SizeInBits) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register type exceeds its register class size");
+    }
+  }
+
+  for (const PhysicalRegister Hint : Info.AllocationHints) {
+    const PhysicalRegisterDesc *HintDesc = Registers.physicalRegister(Hint);
+    if (HintDesc == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register allocation hint names an unknown physical register");
+    }
+    if (HintDesc->IsConstant || HintDesc->IsArtificial) {
+      return makeUnexpected(
+          ErrorCode::VerificationError,
+          "virtual register allocation hint names a constant or artificial register");
+    }
+    if (Info.RegClass && !Registers.registerClassContains(*Info.RegClass, Hint)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register allocation hint is outside its register class");
+    }
+    if (!Info.RegClass && Info.Bank && !Registers.bankContainsRegister(*Info.Bank, Hint)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register allocation hint is outside its register bank");
+    }
+  }
+  return {};
+}
+
+std::optional<RegisterClassID>
+TargetDescription::effectiveRegisterClass(const MachineOperand &Operand,
+                                          const MachineRegisterInfo &RegInfo) const {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || !Reg->isVirtual())
+    return std::nullopt;
+
+  auto Info = RegInfo.virtualRegisterInfo(*Reg);
+  if (!Info)
+    return std::nullopt;
+  const std::optional<RegisterClassID> RegClass = Info->get().RegClass;
+  if (!RegClass)
+    return std::nullopt;
+  if (Operand.subReg().value() == 0)
+    return RegClass;
+  return Registers.subRegClass(*RegClass, Operand.subReg());
+}
+
+Expected<void> TargetDescription::validateTargetOperand(const OperandDescriptor *Descriptor,
+                                                        const MachineOperand &Operand,
+                                                        const MachineRegisterInfo &RegInfo) const {
+  if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); Mask != nullptr) {
+    if (!Mask->Mask) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "register-mask operand contains a null mask");
+    }
+    return Registers.validateRegisterMask(*Mask->Mask);
+  }
+
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr)
+    return {};
+  if (Reg->isNoRegister()) {
+    if (Operand.subReg().value() != 0) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "noreg operand cannot carry a subregister index");
+    }
+    if (Operand.registerFlags().has(RegisterOperandFlag::Renamable)) {
+      return makeUnexpected(ErrorCode::VerificationError, "noreg operand cannot be renamable");
+    }
+    return {};
+  }
+
+  if (const auto PhysReg = Reg->physicalRegister()) {
+    const PhysicalRegister PhysRegValue = *PhysReg;
+    const PhysicalRegisterDesc *PhysRegDesc = Registers.physicalRegister(PhysRegValue);
+    if (PhysRegDesc == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "operand references an unknown physical register");
+    }
+    if (Operand.subReg().value() != 0) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical register operand cannot carry a subregister index");
+    }
+    if (Descriptor != nullptr && Descriptor->RegClass &&
+        !Registers.registerClassContains(*Descriptor->RegClass, PhysRegValue)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical register operand is outside its required register class");
+    }
+    if (Descriptor != nullptr && Descriptor->RegBank &&
+        !Registers.bankContainsRegister(*Descriptor->RegBank, PhysRegValue)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical register operand is outside its required register bank");
+    }
+    const bool IsReservedOrAlias = std::ranges::any_of(
+        RegInfo.reservedRegisters(), [this, PhysRegValue](PhysicalRegister Reserved) {
+          return Registers.regsOverlap(Reserved, PhysRegValue);
+        });
+    if (Operand.registerFlags().has(RegisterOperandFlag::Renamable) &&
+        (IsReservedOrAlias || PhysRegDesc->IsConstant || PhysRegDesc->IsArtificial)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "fixed physical register operand cannot be renamable");
+    }
+    return {};
+  }
+
+  if (Operand.registerFlags().has(RegisterOperandFlag::Renamable)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "virtual register operand cannot be renamable");
+  }
+
+  auto Info = RegInfo.virtualRegisterInfo(*Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  auto RegisterValidation = validateVirtualRegister(*Reg, Info->get());
+  if (!RegisterValidation)
+    return std::unexpected(RegisterValidation.error());
+
+  if (Operand.subReg().value() != 0) {
+    if (Registers.subRegIndex(Operand.subReg()) == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "operand references an unknown subregister index");
+    }
+    const std::optional<RegisterClassID> RegClass = Info->get().RegClass;
+    if (!RegClass) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "generic virtual register cannot carry a subregister index");
+    }
+    if (!Registers.subRegClass(*RegClass, Operand.subReg())) {
+      return makeUnexpected(
+          ErrorCode::VerificationError,
+          "virtual register class does not support the operand subregister index");
+    }
+  }
+
+  if (Descriptor != nullptr && Descriptor->RegBank && Info->get().Bank != Descriptor->RegBank) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "virtual register bank does not match the operand descriptor");
+  }
+  if (Descriptor != nullptr && Descriptor->RegClass) {
+    const auto EffectiveClass = effectiveRegisterClass(Operand, RegInfo);
+    if (!EffectiveClass || !Registers.isSubclass(*EffectiveClass, *Descriptor->RegClass)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "virtual register class does not satisfy the operand descriptor");
+    }
+  }
+  return {};
+}
+
+Expected<void>
+TargetDescription::validateExplicitOperands(Opcode InstructionOpcode,
+                                            std::span<const MachineOperand> Operands,
+                                            const MachineRegisterInfo &RegInfo) const {
+  auto StructuralValidation =
+      Instructions.validateExplicitOperands(InstructionOpcode, Operands, RegInfo);
+  if (!StructuralValidation)
+    return std::unexpected(StructuralValidation.error());
+
+  const InstructionDescriptor *Descriptor = Instructions.descriptor(InstructionOpcode);
+  if (Descriptor == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered");
+  }
+  for (std::size_t Index = 0; Index < Operands.size(); ++Index) {
+    auto TargetValidation =
+        validateTargetOperand(&descriptorForOperand(*Descriptor, Index), Operands[Index], RegInfo);
+    if (!TargetValidation)
+      return std::unexpected(TargetValidation.error());
+  }
+  return {};
+}
+
+Expected<void>
+TargetDescription::validateTieCompatibility(const MachineOperand &Def, const MachineOperand &Use,
+                                            const MachineRegisterInfo &RegInfo) const {
+  const Register *DefReg = Def.getIf<Register>();
+  const Register *UseReg = Use.getIf<Register>();
+  if (DefReg == nullptr || UseReg == nullptr) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "target tie validation received a non-register operand");
+  }
+  if (DefReg->isNoRegister() || UseReg->isNoRegister())
+    return {};
+
+  const auto DefPhys = DefReg->physicalRegister();
+  const auto UsePhys = UseReg->physicalRegister();
+  if (DefPhys && UsePhys) {
+    if (*DefPhys != *UsePhys) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "tied physical register operands must name the same register");
+    }
+    return {};
+  }
+
+  const auto DefClass = effectiveRegisterClass(Def, RegInfo);
+  const auto UseClass = effectiveRegisterClass(Use, RegInfo);
+  if (DefClass && UseClass && !Registers.registerClassesOverlap(*DefClass, *UseClass)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied virtual register classes have no compatible physical register");
+  }
+
+  auto BankFor = [&RegInfo](Register Reg) -> std::optional<RegisterBankID> {
+    if (!Reg.isVirtual())
+      return std::nullopt;
+    auto Info = RegInfo.virtualRegisterInfo(Reg);
+    return Info ? Info->get().Bank : std::nullopt;
+  };
+  const auto DefBank = BankFor(*DefReg);
+  const auto UseBank = BankFor(*UseReg);
+
+  auto ClassIntersectsBank = [this](RegisterClassID ClassID, RegisterBankID BankID) {
+    const RegisterClassDesc *Class = Registers.registerClass(ClassID);
+    return Class != nullptr &&
+           std::ranges::any_of(Class->Registers, [this, BankID](PhysicalRegister Reg) {
+             return Registers.bankContainsRegister(BankID, Reg);
+           });
+  };
+
+  if (DefPhys && UseClass && !Registers.registerClassContains(*UseClass, *DefPhys)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied physical register is outside the virtual use register class");
+  }
+  if (UsePhys && DefClass && !Registers.registerClassContains(*DefClass, *UsePhys)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied physical register is outside the virtual def register class");
+  }
+  if (DefPhys && UseBank && !Registers.bankContainsRegister(*UseBank, *DefPhys)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied physical register is outside the virtual use register bank");
+  }
+  if (UsePhys && DefBank && !Registers.bankContainsRegister(*DefBank, *UsePhys)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied physical register is outside the virtual def register bank");
+  }
+  if (DefClass && UseBank && !ClassIntersectsBank(*DefClass, *UseBank)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied def register class and use register bank do not intersect");
+  }
+  if (UseClass && DefBank && !ClassIntersectsBank(*UseClass, *DefBank)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied use register class and def register bank do not intersect");
+  }
+  if (!DefClass && !UseClass && DefBank && UseBank &&
+      !Registers.registerBanksOverlap(*DefBank, *UseBank)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "tied virtual register banks have no compatible physical register");
+  }
+  return {};
+}
+
+Expected<void> TargetDescription::validateOperandTies(
+    Opcode InstructionOpcode, std::span<const MachineOperand> ExplicitOperands,
+    std::span<const MachineOperandTie> Ties, const MachineRegisterInfo &RegInfo) const {
+  auto StructuralValidation =
+      Instructions.validateOperandTies(InstructionOpcode, ExplicitOperands, Ties);
+  if (!StructuralValidation)
+    return std::unexpected(StructuralValidation.error());
+
+  for (const MachineOperandTie Tie : Ties) {
+    auto Compatibility = validateTieCompatibility(ExplicitOperands[Tie.DefOperand],
+                                                  ExplicitOperands[Tie.UseOperand], RegInfo);
+    if (!Compatibility)
+      return std::unexpected(Compatibility.error());
+  }
+  return {};
+}
+
+Expected<void>
+TargetDescription::validateImplicitOperands(Opcode InstructionOpcode,
+                                            std::span<const MachineOperand *const> ImplicitOperands,
+                                            const MachineRegisterInfo &RegInfo) const {
+  auto StructuralValidation =
+      Instructions.validateImplicitOperands(InstructionOpcode, ImplicitOperands);
+  if (!StructuralValidation)
+    return std::unexpected(StructuralValidation.error());
+
+  for (const MachineOperand *Operand : ImplicitOperands) {
+    if (Operand == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "implicit operand sequence contains a null operand");
+    }
+    auto TargetValidation = validateTargetOperand(nullptr, *Operand, RegInfo);
+    if (!TargetValidation)
+      return std::unexpected(TargetValidation.error());
+  }
+  return {};
+}
+
+Expected<void>
+TargetDescription::validateEarlyClobber(std::span<const MachineOperand> ExplicitOperands,
+                                        std::span<const MachineOperand *const> ImplicitOperands,
+                                        std::span<const MachineOperandTie> Ties) const {
+  struct IndexedOperand final {
+    const MachineOperand *Operand = nullptr;
+    std::optional<std::size_t> ExplicitIndex;
+  };
+
+  std::vector<IndexedOperand> Operands;
+  Operands.reserve(ExplicitOperands.size() + ImplicitOperands.size());
+  for (std::size_t Index = 0; Index < ExplicitOperands.size(); ++Index)
+    Operands.push_back(IndexedOperand{&ExplicitOperands[Index], Index});
+  for (const MachineOperand *Operand : ImplicitOperands)
+    Operands.push_back(IndexedOperand{Operand, std::nullopt});
+
+  auto AreTied = [Ties](const IndexedOperand &Def, const IndexedOperand &Use) {
+    if (!Def.ExplicitIndex || !Use.ExplicitIndex)
+      return false;
+    return std::ranges::any_of(Ties, [&Def, &Use](MachineOperandTie Tie) {
+      return Tie.DefOperand == *Def.ExplicitIndex && Tie.UseOperand == *Use.ExplicitIndex;
+    });
+  };
+
+  for (const IndexedOperand &DefEntry : Operands) {
+    if (DefEntry.Operand == nullptr)
+      continue;
+    const MachineOperand &Def = *DefEntry.Operand;
+    if (!Def.isDef() || !Def.registerFlags().has(RegisterOperandFlag::EarlyClobber))
+      continue;
+
+    const Register *DefReg = Def.getIf<Register>();
+    if (DefReg == nullptr || DefReg->isNoRegister())
+      continue;
+    for (const IndexedOperand &UseEntry : Operands) {
+      if (UseEntry.Operand == nullptr || UseEntry.Operand == DefEntry.Operand)
+        continue;
+      const MachineOperand &Use = *UseEntry.Operand;
+      if (!Use.isUse() || AreTied(DefEntry, UseEntry))
+        continue;
+
+      const Register *UseReg = Use.getIf<Register>();
+      if (UseReg == nullptr || UseReg->isNoRegister())
+        continue;
+      if (DefReg->isVirtual() && UseReg->isVirtual() && *DefReg == *UseReg) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "early-clobber virtual definition overlaps an untied use");
+      }
+
+      const auto DefPhys = DefReg->physicalRegister();
+      const auto UsePhys = UseReg->physicalRegister();
+      if (DefPhys && UsePhys && Registers.regsOverlap(*DefPhys, *UsePhys)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "early-clobber physical definition overlaps an untied use");
+      }
+    }
+  }
+  return {};
+}
+
+Expected<void> TargetDescription::validateInstruction(const MachineInstr &Instruction,
+                                                      const MachineRegisterInfo &RegInfo) const {
+  auto StructuralValidation = Instructions.validateInstruction(Instruction, RegInfo);
+  if (!StructuralValidation)
+    return std::unexpected(StructuralValidation.error());
+
+  const auto Operands = Instruction.operands();
+  std::size_t ExplicitCount = 0;
+  while (ExplicitCount < Operands.size() && !Operands[ExplicitCount].isImplicit()) {
+    ++ExplicitCount;
+  }
+
+  auto ExplicitValidation =
+      validateExplicitOperands(Instruction.opcode(), Operands.first(ExplicitCount), RegInfo);
+  if (!ExplicitValidation)
+    return std::unexpected(ExplicitValidation.error());
+
+  std::vector<const MachineOperand *> ImplicitOperands;
+  for (std::size_t Index = ExplicitCount; Index < Operands.size(); ++Index)
+    ImplicitOperands.push_back(&Operands[Index]);
+  auto ImplicitValidation =
+      validateImplicitOperands(Instruction.opcode(), ImplicitOperands, RegInfo);
+  if (!ImplicitValidation)
+    return std::unexpected(ImplicitValidation.error());
+
+  std::vector<MachineOperandTie> Ties;
+  for (std::size_t Index = 0; Index < ExplicitCount; ++Index) {
+    const MachineOperand &Operand = Operands[Index];
+    if (!Operand.tiedOperandIndex() || Index > *Operand.tiedOperandIndex()) {
+      continue;
+    }
+    const std::size_t OtherIndex = *Operand.tiedOperandIndex();
+    if (isPureDef(Operand) && isPureUse(Operands[OtherIndex])) {
+      Ties.push_back(MachineOperandTie{Index, OtherIndex});
+    } else {
+      Ties.push_back(MachineOperandTie{OtherIndex, Index});
+    }
+  }
+  auto TieValidation =
+      validateOperandTies(Instruction.opcode(), Operands.first(ExplicitCount), Ties, RegInfo);
+  if (!TieValidation)
+    return std::unexpected(TieValidation.error());
+
+  return validateEarlyClobber(Operands.first(ExplicitCount), ImplicitOperands, Ties);
+}
+
+Expected<void> TargetDescription::validateRegisterInfo(const MachineRegisterInfo &RegInfo) const {
+  for (const PhysicalRegisterLiveIn &LiveIn : RegInfo.liveIns()) {
+    if (!Registers.isKnownPhysicalRegister(LiveIn.PhysReg)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "function live-in names an unknown physical register");
+    }
+    if (!LiveIn.InitialVirtualRegister)
+      continue;
+    auto Info = RegInfo.virtualRegisterInfo(*LiveIn.InitialVirtualRegister);
+    if (!Info)
+      return std::unexpected(Info.error());
+    const std::optional<RegisterClassID> RegClass = Info->get().RegClass;
+    if (RegClass && !Registers.registerClassContains(*RegClass, LiveIn.PhysReg)) {
+      return makeUnexpected(
+          ErrorCode::VerificationError,
+          "function live-in physical register is outside its initial virtual register class");
+    }
+    const std::optional<RegisterBankID> Bank = Info->get().Bank;
+    if (Bank && !Registers.bankContainsRegister(*Bank, LiveIn.PhysReg)) {
+      return makeUnexpected(
+          ErrorCode::VerificationError,
+          "function live-in physical register is outside its initial virtual register bank");
+    }
+  }
+  for (const PhysicalRegister Reg : RegInfo.reservedRegisters()) {
+    if (!Registers.isKnownPhysicalRegister(Reg)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "reserved-register list names an unknown physical register");
+    }
+  }
+
+  const auto VirtualRegisters = RegInfo.virtualRegisters();
+  for (std::size_t Index = 0; Index < VirtualRegisters.size(); ++Index) {
+    const VirtualRegisterInfo &Info = VirtualRegisters[Index];
+    if (Info.IsTombstone)
+      continue;
+    auto Reg = Register::makeVirtual(Index);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    auto Validation = validateVirtualRegister(*Reg, Info);
+    if (!Validation)
+      return std::unexpected(Validation.error());
+    for (const PhysicalRegister Hint : Info.AllocationHints) {
+      if (std::ranges::any_of(RegInfo.reservedRegisters(), [this, Hint](PhysicalRegister Reserved) {
+            return Registers.regsOverlap(Reserved, Hint);
+          })) {
+        return makeUnexpected(
+            ErrorCode::VerificationError,
+            "virtual register allocation hint overlaps a reserved physical register");
+      }
+    }
+  }
+  return {};
+}
+
+Expected<void> TargetDescription::validateBlockLiveIns(const MachineBasicBlock &Block) const {
+  for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) {
+    if (!Registers.isKnownPhysicalRegister(LiveIn.PhysReg)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "block live-in names an unknown physical register");
+    }
+    if (!Registers.isValidLaneMask(LiveIn.PhysReg, LiveIn.Lanes)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "block live-in lane mask is not valid for its physical register");
+    }
+  }
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/TargetRegisterInfo.cpp b/backend/lib/CodeGen/TargetRegisterInfo.cpp
new file mode 100644
index 0000000..7bd4834
--- /dev/null
+++ b/backend/lib/CodeGen/TargetRegisterInfo.cpp
@@ -0,0 +1,603 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::unexpected<Error> invalidDescription(std::string Message) {
+  return makeUnexpected(ErrorCode::InvalidArgument,
+                        "target register description: " + std::move(Message));
+}
+
+[[nodiscard]] bool isPowerOfTwo(std::uint32_t Value) noexcept {
+  return Value != 0 && std::has_single_bit(Value);
+}
+
+template <typename RangeT, typename ValueT>
+[[nodiscard]] bool contains(const RangeT &Range, const ValueT &Value) {
+  return std::ranges::find(Range, Value) != std::ranges::end(Range);
+}
+
+[[nodiscard]] const RegisterUnitLane *findUnit(const PhysicalRegisterDesc &Register,
+                                               RegisterUnitID Unit) noexcept {
+  const auto Position = std::ranges::find(Register.Units, Unit, &RegisterUnitLane::Unit);
+  return Position == Register.Units.end() ? nullptr : &*Position;
+}
+
+} // namespace
+
+Expected<TargetRegisterInfo> TargetRegisterInfo::create(TargetRegisterInfoDesc Description) {
+  if (Description.RegisterUnits.empty() || Description.PhysicalRegisters.empty() ||
+      Description.RegisterClasses.empty() || Description.RegisterBanks.empty()) {
+    return invalidDescription(
+        "register units, physical registers, classes, and banks must be nonempty");
+  }
+
+  TargetRegisterInfo Result(std::move(Description));
+
+  std::unordered_set<std::string> UnitNames;
+  for (std::size_t Index = 0; Index < Result.Description.RegisterUnits.size(); ++Index) {
+    const RegisterUnitDesc &Unit = Result.Description.RegisterUnits[Index];
+    if (Unit.ID.value() == 0 || Unit.Name.empty()) {
+      return invalidDescription("register unit requires a nonzero ID and name");
+    }
+    if (!Result.UnitToIndex.emplace(Unit.ID, Index).second || !UnitNames.insert(Unit.Name).second) {
+      return invalidDescription("register unit IDs and names must be unique");
+    }
+  }
+
+  for (std::size_t Index = 0; Index < Result.Description.PhysicalRegisters.size(); ++Index) {
+    const PhysicalRegisterDesc &Register = Result.Description.PhysicalRegisters[Index];
+    if (!Register.Reg.isValid() || Register.Name.empty()) {
+      return invalidDescription("physical register requires a valid number and name");
+    }
+    if (!Result.RegisterToIndex.emplace(Register.Reg, Index).second ||
+        !Result.RegisterNameToIndex.emplace(Register.Name, Index).second) {
+      return invalidDescription("physical register numbers and names must be unique");
+    }
+  }
+
+  std::unordered_set<std::string> SubRegNames;
+  for (std::size_t Index = 0; Index < Result.Description.SubRegIndices.size(); ++Index) {
+    const SubRegIndexDesc &SubReg = Result.Description.SubRegIndices[Index];
+    if (SubReg.ID.value() == 0 || SubReg.Name.empty() || SubReg.Lanes.empty() ||
+        SubReg.SizeInBits == 0 ||
+        static_cast<std::uint64_t>(SubReg.OffsetInBits) + SubReg.SizeInBits >
+            std::numeric_limits<std::uint32_t>::max()) {
+      return invalidDescription(
+          "subregister index requires a nonzero ID, name, lanes, and valid bit range");
+    }
+    if (!Result.SubRegIndexToIndex.emplace(SubReg.ID, Index).second ||
+        !SubRegNames.insert(SubReg.Name).second) {
+      return invalidDescription("subregister index IDs and names must be unique");
+    }
+  }
+
+  std::unordered_set<std::string> ClassNames;
+  for (std::size_t Index = 0; Index < Result.Description.RegisterClasses.size(); ++Index) {
+    const RegisterClassDesc &Class = Result.Description.RegisterClasses[Index];
+    if (Class.ID.value() == 0 || Class.Name.empty()) {
+      return invalidDescription("register class requires a nonzero ID and name");
+    }
+    if (!Result.ClassToIndex.emplace(Class.ID, Index).second ||
+        !ClassNames.insert(Class.Name).second) {
+      return invalidDescription("register class IDs and names must be unique");
+    }
+  }
+
+  std::unordered_set<std::string> BankNames;
+  for (std::size_t Index = 0; Index < Result.Description.RegisterBanks.size(); ++Index) {
+    const RegisterBankDesc &Bank = Result.Description.RegisterBanks[Index];
+    if (Bank.ID.value() == 0 || Bank.Name.empty() || Bank.MaximumSizeInBits == 0) {
+      return invalidDescription("register bank requires a nonzero ID, name, and maximum size");
+    }
+    if (!Result.BankToIndex.emplace(Bank.ID, Index).second || !BankNames.insert(Bank.Name).second) {
+      return invalidDescription("register bank IDs and names must be unique");
+    }
+  }
+
+  std::unordered_set<RegisterUnitID> ReferencedUnits;
+  for (const PhysicalRegisterDesc &Register : Result.Description.PhysicalRegisters) {
+    if (Register.Units.empty())
+      return invalidDescription("physical register must reference at least one register unit");
+
+    std::unordered_set<RegisterUnitID> SeenUnits;
+    LaneMask RegisterLanes;
+    for (const RegisterUnitLane &Unit : Register.Units) {
+      if (Result.registerUnit(Unit.Unit) == nullptr || Unit.Lanes.empty() ||
+          !SeenUnits.insert(Unit.Unit).second) {
+        return invalidDescription(
+            "physical register has an unknown, empty-lane, or duplicate register unit");
+      }
+      ReferencedUnits.insert(Unit.Unit);
+      RegisterLanes = RegisterLanes | Unit.Lanes;
+    }
+    if (RegisterLanes.empty())
+      return invalidDescription("physical register has no addressable lanes");
+  }
+  if (ReferencedUnits.size() != Result.Description.RegisterUnits.size())
+    return invalidDescription("every declared register unit must be used by a physical register");
+
+  const std::size_t RegisterCount = Result.Description.PhysicalRegisters.size();
+  std::vector<std::vector<bool>> IsSubRegister(RegisterCount,
+                                               std::vector<bool>(RegisterCount, false));
+  for (const PhysicalSubRegisterDesc &Mapping : Result.Description.PhysicalSubRegisters) {
+    const PhysicalRegisterDesc *Super = Result.physicalRegister(Mapping.SuperReg);
+    const PhysicalRegisterDesc *Sub = Result.physicalRegister(Mapping.SubReg);
+    const SubRegIndexDesc *Index = Result.subRegIndex(Mapping.Index);
+    if (Super == nullptr || Sub == nullptr || Index == nullptr ||
+        Mapping.SuperReg == Mapping.SubReg) {
+      return invalidDescription(
+          "physical subregister mapping references an unknown or identical register");
+    }
+
+    const std::uint64_t Key = pairKey(Mapping.SuperReg.number(), Mapping.Index.value());
+    if (!Result.SubRegisterMap.emplace(Key, Mapping.SubReg).second)
+      return invalidDescription("physical subregister mapping key must be unique");
+
+    LaneMask ProjectedLanes;
+    for (const RegisterUnitLane &SubUnit : Sub->Units) {
+      const RegisterUnitLane *SuperUnit = findUnit(*Super, SubUnit.Unit);
+      if (SuperUnit == nullptr) {
+        return invalidDescription(
+            "physical subregister units must be a subset of its superregister units");
+      }
+      ProjectedLanes = ProjectedLanes | SuperUnit->Lanes;
+    }
+    if (ProjectedLanes != Index->Lanes) {
+      return invalidDescription(
+          "physical subregister units do not match the subregister index lane mask");
+    }
+
+    const std::size_t SuperIndex = Result.RegisterToIndex.at(Mapping.SuperReg);
+    const std::size_t SubIndex = Result.RegisterToIndex.at(Mapping.SubReg);
+    IsSubRegister[SuperIndex][SubIndex] = true;
+  }
+
+  for (std::size_t Through = 0; Through < RegisterCount; ++Through) {
+    for (std::size_t Super = 0; Super < RegisterCount; ++Super) {
+      if (!IsSubRegister[Super][Through])
+        continue;
+      for (std::size_t Sub = 0; Sub < RegisterCount; ++Sub)
+        IsSubRegister[Super][Sub] = IsSubRegister[Super][Sub] || IsSubRegister[Through][Sub];
+    }
+  }
+  for (std::size_t Index = 0; Index < RegisterCount; ++Index) {
+    if (IsSubRegister[Index][Index])
+      return invalidDescription("physical subregister graph must be acyclic");
+  }
+
+  Result.SuperRegisters.resize(RegisterCount);
+  for (std::size_t Sub = 0; Sub < RegisterCount; ++Sub) {
+    for (std::size_t Super = 0; Super < RegisterCount; ++Super) {
+      if (IsSubRegister[Super][Sub]) {
+        Result.SuperRegisters[Sub].push_back(Result.Description.PhysicalRegisters[Super].Reg);
+      }
+    }
+  }
+
+  for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) {
+    const SubRegIndexDesc *First = Result.subRegIndex(Composition.First);
+    const SubRegIndexDesc *Second = Result.subRegIndex(Composition.Second);
+    const SubRegIndexDesc *Composed = Result.subRegIndex(Composition.Result);
+    if (First == nullptr || Second == nullptr || Composed == nullptr) {
+      return invalidDescription("subregister composition references an unknown index");
+    }
+    const std::uint64_t ComposedOffset =
+        static_cast<std::uint64_t>(First->OffsetInBits) + Second->OffsetInBits;
+    if (static_cast<std::uint64_t>(Second->OffsetInBits) + Second->SizeInBits > First->SizeInBits ||
+        Composed->SizeInBits != Second->SizeInBits || Composed->OffsetInBits != ComposedOffset) {
+      return invalidDescription("subregister composition has inconsistent bit ranges");
+    }
+    const std::uint64_t Key = pairKey(Composition.First.value(), Composition.Second.value());
+    if (!Result.CompositionMap.emplace(Key, Composition.Result).second)
+      return invalidDescription("subregister composition key must be unique");
+  }
+
+  for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) {
+    for (const PhysicalRegisterDesc &Super : Result.Description.PhysicalRegisters) {
+      const auto Intermediate = Result.subRegister(Super.Reg, Composition.First);
+      if (!Intermediate)
+        continue;
+      const auto Final = Result.subRegister(*Intermediate, Composition.Second);
+      if (!Final)
+        continue;
+      const auto Composed = Result.subRegister(Super.Reg, Composition.Result);
+      if (!Composed || *Composed != *Final) {
+        return invalidDescription(
+            "subregister composition conflicts with physical subregister mappings");
+      }
+    }
+  }
+
+  for (const RegisterBankDesc &Bank : Result.Description.RegisterBanks) {
+    if (Bank.RegisterClasses.empty())
+      return invalidDescription("register bank must cover at least one register class");
+
+    std::unordered_set<RegisterClassID> SeenClasses;
+    for (const RegisterClassID ClassID : Bank.RegisterClasses) {
+      const RegisterClassDesc *Class = Result.registerClass(ClassID);
+      if (Class == nullptr || !SeenClasses.insert(ClassID).second) {
+        return invalidDescription("register bank has an unknown or duplicate register class");
+      }
+      if (Class->SizeInBits > Bank.MaximumSizeInBits) {
+        return invalidDescription(
+            "register bank maximum size is smaller than a covered register class");
+      }
+    }
+  }
+
+  for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) {
+    if (Class.Registers.empty() || Class.SizeInBits == 0 ||
+        Class.SpillSizeInBits < Class.SizeInBits || !isPowerOfTwo(Class.SpillAlignmentInBits) ||
+        Class.Lanes.empty()) {
+      return invalidDescription(
+          "register class requires members, sizes, power-of-two spill alignment, and lanes");
+    }
+
+    std::unordered_set<PhysicalRegister> Members;
+    for (const PhysicalRegister Reg : Class.Registers) {
+      if (!Result.isKnownPhysicalRegister(Reg) || !Members.insert(Reg).second ||
+          !Result.isValidLaneMask(Reg, Class.Lanes)) {
+        return invalidDescription(
+            "register class has an unknown, duplicate, or lane-incompatible member");
+      }
+    }
+
+    std::unordered_set<PhysicalRegister> AllocationRegisters;
+    for (const PhysicalRegister Reg : Class.AllocationOrder) {
+      if (!Members.contains(Reg) || !AllocationRegisters.insert(Reg).second) {
+        return invalidDescription(
+            "register class allocation order must contain unique class members");
+      }
+    }
+    if ((Class.Allocatable && Class.AllocationOrder.empty()) ||
+        (!Class.Allocatable && !Class.AllocationOrder.empty())) {
+      return invalidDescription(
+          "allocatable classes require an allocation order and nonallocatable classes forbid one");
+    }
+
+    std::unordered_set<SubRegIndex> SupportedSubRegs;
+    LaneMask CoveredSubRegLanes;
+    for (const SubRegIndex SubReg : Class.SupportedSubRegs) {
+      const SubRegIndexDesc *SubRegDesc = Result.subRegIndex(SubReg);
+      if (SubRegDesc == nullptr || !SupportedSubRegs.insert(SubReg).second ||
+          !Class.Lanes.contains(SubRegDesc->Lanes)) {
+        return invalidDescription(
+            "register class has an unknown, duplicate, or lane-incompatible subregister index");
+      }
+      CoveredSubRegLanes = CoveredSubRegLanes | SubRegDesc->Lanes;
+    }
+    if (Class.CoveredBySubRegs &&
+        (Class.SupportedSubRegs.empty() || !CoveredSubRegLanes.contains(Class.Lanes))) {
+      return invalidDescription(
+          "subregister-covered class must cover every class lane with supported indices");
+    }
+
+    std::unordered_set<RegisterClassID> SuperClasses;
+    for (const RegisterClassID SuperClass : Class.SuperClasses) {
+      if (Result.registerClass(SuperClass) == nullptr || SuperClass == Class.ID ||
+          !SuperClasses.insert(SuperClass).second) {
+        return invalidDescription("register class has an unknown, self, or duplicate superclass");
+      }
+      Result.SubclassRelations.insert(pairKey(Class.ID.value(), SuperClass.value()));
+    }
+    Result.SubclassRelations.insert(pairKey(Class.ID.value(), Class.ID.value()));
+
+    if (Result.registerBank(Class.DefaultBank) == nullptr ||
+        !Result.bankCoversClass(Class.DefaultBank, Class.ID)) {
+      return invalidDescription(
+          "register class default bank must exist and explicitly cover the class");
+    }
+  }
+
+  bool RelationsChanged = true;
+  while (RelationsChanged) {
+    RelationsChanged = false;
+    for (const RegisterClassDesc &Candidate : Result.Description.RegisterClasses) {
+      for (const RegisterClassDesc &Intermediate : Result.Description.RegisterClasses) {
+        if (!Result.isSubclass(Candidate.ID, Intermediate.ID))
+          continue;
+        for (const RegisterClassDesc &Required : Result.Description.RegisterClasses) {
+          if (!Result.isSubclass(Intermediate.ID, Required.ID))
+            continue;
+          RelationsChanged |=
+              Result.SubclassRelations.insert(pairKey(Candidate.ID.value(), Required.ID.value()))
+                  .second;
+        }
+      }
+    }
+  }
+
+  for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) {
+    for (const RegisterClassDesc &Other : Result.Description.RegisterClasses) {
+      if (Class.ID != Other.ID && Result.isSubclass(Class.ID, Other.ID) &&
+          Result.isSubclass(Other.ID, Class.ID)) {
+        return invalidDescription("register class hierarchy must be acyclic");
+      }
+    }
+    for (const RegisterClassID SuperID : Class.SuperClasses) {
+      const RegisterClassDesc *Super = Result.registerClass(SuperID);
+      if (Super == nullptr || Class.SizeInBits != Super->SizeInBits ||
+          Class.SpillSizeInBits != Super->SpillSizeInBits ||
+          Class.SpillAlignmentInBits != Super->SpillAlignmentInBits ||
+          !std::ranges::all_of(Class.Registers, [Super](PhysicalRegister Reg) {
+            return contains(Super->Registers, Reg);
+          })) {
+        return invalidDescription(
+            "register class must be storage-compatible with each declared superclass");
+      }
+    }
+  }
+
+  for (const SubRegClassMapping &Mapping : Result.Description.SubRegClassMappings) {
+    const RegisterClassDesc *Source = Result.registerClass(Mapping.SourceClass);
+    const SubRegIndexDesc *Index = Result.subRegIndex(Mapping.Index);
+    const RegisterClassDesc *Mapped = Result.registerClass(Mapping.ResultClass);
+    if (Source == nullptr || Index == nullptr || Mapped == nullptr ||
+        !contains(Source->SupportedSubRegs, Mapping.Index)) {
+      return invalidDescription(
+          "subregister class mapping references an unknown or unsupported entity");
+    }
+    if (Mapped->SizeInBits != Index->SizeInBits) {
+      return invalidDescription("subregister class mapping result size must match its index size");
+    }
+    if (static_cast<std::uint64_t>(Index->OffsetInBits) + Index->SizeInBits > Source->SizeInBits) {
+      return invalidDescription("subregister class mapping index exceeds its source class size");
+    }
+
+    const std::uint64_t Key = pairKey(Mapping.SourceClass.value(), Mapping.Index.value());
+    if (!Result.SubRegClassMap.emplace(Key, Mapping.ResultClass).second) {
+      return invalidDescription("subregister class mapping key must be unique");
+    }
+    for (const PhysicalRegister SuperReg : Source->Registers) {
+      const auto SubReg = Result.subRegister(SuperReg, Mapping.Index);
+      if (!SubReg || !Result.registerClassContains(Mapping.ResultClass, *SubReg)) {
+        return invalidDescription("subregister class mapping does not cover every source register");
+      }
+    }
+  }
+
+  for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) {
+    for (const SubRegIndex SubReg : Class.SupportedSubRegs) {
+      if (!Result.subRegClass(Class.ID, SubReg)) {
+        return invalidDescription(
+            "every supported class subregister index requires a class mapping");
+      }
+    }
+  }
+
+  for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) {
+    for (const RegisterClassDesc &Source : Result.Description.RegisterClasses) {
+      const auto Intermediate = Result.subRegClass(Source.ID, Composition.First);
+      if (!Intermediate)
+        continue;
+      const auto Final = Result.subRegClass(*Intermediate, Composition.Second);
+      if (!Final)
+        continue;
+      const auto Composed = Result.subRegClass(Source.ID, Composition.Result);
+      if (!Composed || !Result.isSubclass(*Final, *Composed)) {
+        return invalidDescription("subregister composition conflicts with register class mappings");
+      }
+    }
+  }
+
+  for (const PhysicalRegisterDesc &Register : Result.Description.PhysicalRegisters) {
+    if (std::ranges::none_of(Result.Description.RegisterClasses,
+                             [&Register](const RegisterClassDesc &Class) {
+                               return contains(Class.Registers, Register.Reg);
+                             })) {
+      return invalidDescription(
+          "every physical register must belong to at least one register class");
+    }
+  }
+
+  Result.Aliases.resize(RegisterCount);
+  for (std::size_t Left = 0; Left < RegisterCount; ++Left) {
+    for (std::size_t Right = 0; Right < RegisterCount; ++Right) {
+      if (Left != Right && Result.regsOverlap(Result.Description.PhysicalRegisters[Left].Reg,
+                                              Result.Description.PhysicalRegisters[Right].Reg)) {
+        Result.Aliases[Left].push_back(Result.Description.PhysicalRegisters[Right].Reg);
+      }
+    }
+  }
+
+  return Result;
+}
+
+const RegisterUnitDesc *TargetRegisterInfo::registerUnit(RegisterUnitID ID) const noexcept {
+  const auto Position = UnitToIndex.find(ID);
+  return Position == UnitToIndex.end() ? nullptr : &Description.RegisterUnits[Position->second];
+}
+
+const PhysicalRegisterDesc *
+TargetRegisterInfo::physicalRegister(PhysicalRegister Reg) const noexcept {
+  const auto Position = RegisterToIndex.find(Reg);
+  return Position == RegisterToIndex.end() ? nullptr
+                                           : &Description.PhysicalRegisters[Position->second];
+}
+
+const PhysicalRegisterDesc *
+TargetRegisterInfo::physicalRegister(std::string_view Name) const noexcept {
+  const auto Position = RegisterNameToIndex.find(std::string(Name));
+  return Position == RegisterNameToIndex.end() ? nullptr
+                                               : &Description.PhysicalRegisters[Position->second];
+}
+
+const SubRegIndexDesc *TargetRegisterInfo::subRegIndex(SubRegIndex Index) const noexcept {
+  const auto Position = SubRegIndexToIndex.find(Index);
+  return Position == SubRegIndexToIndex.end() ? nullptr
+                                              : &Description.SubRegIndices[Position->second];
+}
+
+const RegisterClassDesc *TargetRegisterInfo::registerClass(RegisterClassID ID) const noexcept {
+  const auto Position = ClassToIndex.find(ID);
+  return Position == ClassToIndex.end() ? nullptr : &Description.RegisterClasses[Position->second];
+}
+
+const RegisterBankDesc *TargetRegisterInfo::registerBank(RegisterBankID ID) const noexcept {
+  const auto Position = BankToIndex.find(ID);
+  return Position == BankToIndex.end() ? nullptr : &Description.RegisterBanks[Position->second];
+}
+
+LaneMask TargetRegisterInfo::registerLaneMask(PhysicalRegister Reg) const noexcept {
+  const PhysicalRegisterDesc *Register = physicalRegister(Reg);
+  if (Register == nullptr)
+    return {};
+
+  LaneMask Result;
+  for (const RegisterUnitLane &Unit : Register->Units)
+    Result = Result | Unit.Lanes;
+  return Result;
+}
+
+bool TargetRegisterInfo::isValidLaneMask(PhysicalRegister Reg, LaneMask Lanes) const noexcept {
+  if (physicalRegister(Reg) == nullptr || Lanes.empty())
+    return false;
+  if (Lanes == LaneMask::all())
+    return true;
+  return registerLaneMask(Reg).contains(Lanes);
+}
+
+bool TargetRegisterInfo::regsOverlap(PhysicalRegister Left, PhysicalRegister Right) const noexcept {
+  const PhysicalRegisterDesc *LeftDesc = physicalRegister(Left);
+  const PhysicalRegisterDesc *RightDesc = physicalRegister(Right);
+  if (LeftDesc == nullptr || RightDesc == nullptr)
+    return false;
+
+  return std::ranges::any_of(LeftDesc->Units, [RightDesc](const RegisterUnitLane &Unit) {
+    return findUnit(*RightDesc, Unit.Unit) != nullptr;
+  });
+}
+
+std::span<const PhysicalRegister> TargetRegisterInfo::aliases(PhysicalRegister Reg) const noexcept {
+  const auto Position = RegisterToIndex.find(Reg);
+  if (Position == RegisterToIndex.end())
+    return {};
+  return Aliases[Position->second];
+}
+
+std::optional<PhysicalRegister> TargetRegisterInfo::subRegister(PhysicalRegister SuperReg,
+                                                                SubRegIndex Index) const noexcept {
+  const auto Position = SubRegisterMap.find(pairKey(SuperReg.number(), Index.value()));
+  if (Position == SubRegisterMap.end())
+    return std::nullopt;
+  return Position->second;
+}
+
+bool TargetRegisterInfo::isSubRegister(PhysicalRegister SuperReg,
+                                       PhysicalRegister SubReg) const noexcept {
+  const auto Position = RegisterToIndex.find(SubReg);
+  if (Position == RegisterToIndex.end())
+    return false;
+  return contains(SuperRegisters[Position->second], SuperReg);
+}
+
+std::span<const PhysicalRegister>
+TargetRegisterInfo::superRegisters(PhysicalRegister Reg) const noexcept {
+  const auto Position = RegisterToIndex.find(Reg);
+  if (Position == RegisterToIndex.end())
+    return {};
+  return SuperRegisters[Position->second];
+}
+
+std::optional<SubRegIndex>
+TargetRegisterInfo::composeSubRegIndices(SubRegIndex First, SubRegIndex Second) const noexcept {
+  const auto Position = CompositionMap.find(pairKey(First.value(), Second.value()));
+  if (Position == CompositionMap.end())
+    return std::nullopt;
+  return Position->second;
+}
+
+bool TargetRegisterInfo::registerClassContains(RegisterClassID Class,
+                                               PhysicalRegister Reg) const noexcept {
+  const RegisterClassDesc *ClassDesc = registerClass(Class);
+  return ClassDesc != nullptr && contains(ClassDesc->Registers, Reg);
+}
+
+bool TargetRegisterInfo::isSubclass(RegisterClassID Candidate,
+                                    RegisterClassID Required) const noexcept {
+  return SubclassRelations.contains(pairKey(Candidate.value(), Required.value()));
+}
+
+bool TargetRegisterInfo::registerClassesOverlap(RegisterClassID Left,
+                                                RegisterClassID Right) const noexcept {
+  const RegisterClassDesc *LeftClass = registerClass(Left);
+  const RegisterClassDesc *RightClass = registerClass(Right);
+  if (LeftClass == nullptr || RightClass == nullptr)
+    return false;
+  return std::ranges::any_of(LeftClass->Registers, [RightClass](PhysicalRegister Reg) {
+    return contains(RightClass->Registers, Reg);
+  });
+}
+
+std::optional<RegisterClassID> TargetRegisterInfo::subRegClass(RegisterClassID Source,
+                                                               SubRegIndex Index) const noexcept {
+  const auto Position = SubRegClassMap.find(pairKey(Source.value(), Index.value()));
+  if (Position == SubRegClassMap.end())
+    return std::nullopt;
+  return Position->second;
+}
+
+bool TargetRegisterInfo::bankCoversClass(RegisterBankID Bank,
+                                         RegisterClassID Class) const noexcept {
+  const RegisterBankDesc *BankDesc = registerBank(Bank);
+  return BankDesc != nullptr && contains(BankDesc->RegisterClasses, Class);
+}
+
+bool TargetRegisterInfo::bankContainsRegister(RegisterBankID Bank,
+                                              PhysicalRegister Reg) const noexcept {
+  const RegisterBankDesc *BankDesc = registerBank(Bank);
+  if (BankDesc == nullptr)
+    return false;
+  return std::ranges::any_of(BankDesc->RegisterClasses, [this, Reg](RegisterClassID Class) {
+    return registerClassContains(Class, Reg);
+  });
+}
+
+bool TargetRegisterInfo::registerBanksOverlap(RegisterBankID Left,
+                                              RegisterBankID Right) const noexcept {
+  const RegisterBankDesc *LeftBank = registerBank(Left);
+  const RegisterBankDesc *RightBank = registerBank(Right);
+  if (LeftBank == nullptr || RightBank == nullptr)
+    return false;
+  return std::ranges::any_of(Description.PhysicalRegisters,
+                             [this, Left, Right](const PhysicalRegisterDesc &Register) {
+                               return bankContainsRegister(Left, Register.Reg) &&
+                                      bankContainsRegister(Right, Register.Reg);
+                             });
+}
+
+Expected<void> TargetRegisterInfo::validateRegisterMask(const RegisterMask &Mask) const {
+  constexpr std::uint64_t BitsPerWord = 64;
+  for (std::size_t WordIndex = 0; WordIndex < Mask.words().size(); ++WordIndex) {
+    std::uint64_t Word = Mask.words()[WordIndex];
+    while (Word != 0) {
+      const std::uint64_t BitIndex = static_cast<std::uint64_t>(std::countr_zero(Word));
+      const std::uint64_t RegisterNumber =
+          static_cast<std::uint64_t>(WordIndex) * BitsPerWord + BitIndex;
+      const auto Reg = PhysicalRegister::create(RegisterNumber);
+      if (!Reg || !isKnownPhysicalRegister(*Reg)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "register mask preserves an unknown physical register");
+      }
+      Word &= Word - 1;
+    }
+  }
+  return {};
+}
+
+} // namespace rcc