[CodeGen] Complete register allocation infrastructure

35 files changed, 2955 insertions, 154 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 4c2887c..d6233c2 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -30,6 +30,14 @@ set(
   MachinePass.cpp
   MachinePipelinePasses.cpp
   MachineRegisterInfo.cpp
+  InlineSpiller.cpp
+  LiveRangeEdit.cpp
+  LiveRegMatrix.cpp
+  RegAllocBase.cpp
+  RegAllocBasic.cpp
+  RegAllocFast.cpp
+  RegAllocPBQP.cpp
+  VirtRegMap.cpp
   MachineSSAExit.cpp
   MachineVerifier.cpp
   MachineFunctionProperties.cpp
@@ -74,6 +82,19 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Graph.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Math.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/ReductionRules.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Solution.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Solver.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRangeEdit.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRegMatrix.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocCommon.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocFast.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocPBQP.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Spiller.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterAllocationInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/VirtRegMap.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h"
@@ -146,6 +167,17 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/InlineSpiller.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LiveRangeEdit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrix.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocInternal.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
@@ -189,6 +221,14 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/InlineSpiller.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LiveRangeEdit.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrix.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp"
diff --git a/backend/lib/CodeGen/GenericConstant.cpp b/backend/lib/CodeGen/GenericConstant.cpp
index 2ef24bf..d9d9233 100644
--- a/backend/lib/CodeGen/GenericConstant.cpp
+++ b/backend/lib/CodeGen/GenericConstant.cpp
@@ -66,8 +66,7 @@ struct VectorShape final {
   friend constexpr bool operator==(VectorShape Left, VectorShape Right) noexcept = default;
 };
 
-[[nodiscard]] std::optional<VectorShape>
-vectorShape(const GenericConstantType &Type) noexcept {
+[[nodiscard]] std::optional<VectorShape> vectorShape(const GenericConstantType &Type) noexcept {
   const GenericConstantType &Resolved = resolvedType(Type);
   if (Resolved.Kind != GenericConstantTypeKind::Vector)
     return std::nullopt;
@@ -121,8 +120,7 @@ pointerAddressSpace(const GenericConstantType &Type) noexcept {
   if (isIntegerScalarType(Type) || isFloatingScalarType(Type))
     return true;
   const GenericConstantType *Element = vectorElementType(Type);
-  return Element != nullptr &&
-         (isIntegerScalarType(*Element) || isFloatingScalarType(*Element));
+  return Element != nullptr && (isIntegerScalarType(*Element) || isFloatingScalarType(*Element));
 }
 
 [[nodiscard]] std::optional<std::uint64_t>
@@ -175,8 +173,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
          isPointerScalarType(*PointerElement) && isIntegerScalarType(*IntegerElement);
 }
 
-[[nodiscard]] bool isSizedType(const GenericConstantType &Type,
-                                std::size_t Depth = 0) noexcept {
+[[nodiscard]] bool isSizedType(const GenericConstantType &Type, std::size_t Depth = 0) noexcept {
   if (Depth > MaximumVerificationDepth)
     return false;
   const GenericConstantType &Resolved = resolvedType(Type);
@@ -224,8 +221,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
 [[nodiscard]] bool hasOnlyValuePayload(const GenericConstantData &Value) noexcept {
   return Value.Symbol.empty() && Value.Block.empty() &&
          Value.ExpressionOpcode == GenericConstantExpressionOpcode::Invalid &&
-         Value.ExpressionFlags.rawValue() == 0 && !Value.SourceElementType &&
-         !Value.InRangeStart && !Value.InRangeEnd;
+         Value.ExpressionFlags.rawValue() == 0 && !Value.SourceElementType && !Value.InRangeStart &&
+         !Value.InRangeEnd;
 }
 
 [[nodiscard]] Expected<void> verifyType(const GenericConstantType &Type, std::size_t Depth,
@@ -335,8 +332,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
         (EffectiveType.Kind != GenericConstantTypeKind::Integer &&
          EffectiveType.Kind != GenericConstantTypeKind::Byte) ||
         Value.IntegerValue->bitWidth() !=
-            (EffectiveType.Kind == GenericConstantTypeKind::Byte ? 8U
-                                                                 : EffectiveType.BitWidth)) {
+            (EffectiveType.Kind == GenericConstantTypeKind::Byte ? 8U : EffectiveType.BitWidth)) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "generic integer constant has an inconsistent payload");
     }
@@ -384,9 +380,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
     }
     for (std::size_t Index = 0; Index < Value.Elements.size(); ++Index) {
       const GenericConstantType &ExpectedType =
-          EffectiveType.Kind == GenericConstantTypeKind::Struct
-              ? EffectiveType.Elements[Index]
-              : EffectiveType.Elements.front();
+          EffectiveType.Kind == GenericConstantTypeKind::Struct ? EffectiveType.Elements[Index]
+                                                                : EffectiveType.Elements.front();
       if (Value.Elements[Index].Type != ExpectedType) {
         return makeUnexpected(ErrorCode::VerificationError,
                               "generic aggregate element type does not match its container");
@@ -417,8 +412,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
         Value.IntegerValue || Value.FloatingValue || !Value.ByteValue.empty() ||
         !Value.Elements.empty() || !Value.Block.empty() ||
         Value.ExpressionOpcode != GenericConstantExpressionOpcode::Invalid ||
-        Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType ||
-        Value.InRangeStart || Value.InRangeEnd) {
+        Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || Value.InRangeStart ||
+        Value.InRangeEnd) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "generic global-address constant has an inconsistent payload");
     }
@@ -428,13 +423,13 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
         Value.Block.empty() || Value.IntegerValue || Value.FloatingValue ||
         !Value.ByteValue.empty() || !Value.Elements.empty() ||
         Value.ExpressionOpcode != GenericConstantExpressionOpcode::Invalid ||
-        Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType ||
-        Value.InRangeStart || Value.InRangeEnd) {
+        Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || Value.InRangeStart ||
+        Value.InRangeEnd) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "generic block-address constant has an inconsistent payload");
     }
     return {};
-  case GenericConstantKind::PointerAuth:
+  case GenericConstantKind::PointerAuth: {
     if (EffectiveType.Kind != GenericConstantTypeKind::Pointer || Value.Elements.size() < 2 ||
         Value.Elements.size() > 5 || Value.IntegerValue || Value.FloatingValue ||
         !Value.ByteValue.empty() || !hasOnlyValuePayload(Value)) {
@@ -446,19 +441,20 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
       if (!Result)
         return Result;
     }
+    const auto KeyBitWidth = integerScalarBitWidth(Value.Elements[1].Type);
     if (!isPointerScalarType(Value.Elements[0].Type) ||
-        !sameResolvedType(Value.Type, Value.Elements[0].Type) ||
-        !integerScalarBitWidth(Value.Elements[1].Type) ||
-        *integerScalarBitWidth(Value.Elements[1].Type) != 32) {
+        !sameResolvedType(Value.Type, Value.Elements[0].Type) || !KeyBitWidth ||
+        KeyBitWidth.value() != 32) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "generic pointer-auth constant has invalid pointer or key operands");
     }
-    if (Value.Elements.size() >= 3 &&
-        (!integerScalarBitWidth(Value.Elements[2].Type) ||
-         *integerScalarBitWidth(Value.Elements[2].Type) != 64)) {
-      return makeUnexpected(
-          ErrorCode::VerificationError,
-          "generic pointer-auth constant integer discriminator must be a scalar i64");
+    if (Value.Elements.size() >= 3) {
+      const auto DiscriminatorBitWidth = integerScalarBitWidth(Value.Elements[2].Type);
+      if (!DiscriminatorBitWidth || DiscriminatorBitWidth.value() != 64) {
+        return makeUnexpected(
+            ErrorCode::VerificationError,
+            "generic pointer-auth constant integer discriminator must be a scalar i64");
+      }
     }
     for (std::size_t Index = 3; Index < Value.Elements.size(); ++Index) {
       if (!isPointerScalarType(Value.Elements[Index].Type)) {
@@ -468,6 +464,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
       }
     }
     return {};
+  }
   case GenericConstantKind::Expression:
     if (Value.ExpressionOpcode == GenericConstantExpressionOpcode::Invalid ||
         Value.Elements.empty() || Value.IntegerValue || Value.FloatingValue ||
@@ -495,18 +492,18 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
     const bool IsBinary = Value.ExpressionOpcode == GenericConstantExpressionOpcode::Add ||
                           Value.ExpressionOpcode == GenericConstantExpressionOpcode::Sub ||
                           Value.ExpressionOpcode == GenericConstantExpressionOpcode::Xor;
-    const bool IsGEP = Value.ExpressionOpcode ==
-                       GenericConstantExpressionOpcode::GetElementPtr;
+    const bool IsGEP = Value.ExpressionOpcode == GenericConstantExpressionOpcode::GetElementPtr;
     const std::uint8_t Flags = Value.ExpressionFlags.rawValue();
     const std::uint8_t BinaryFlags =
-        (std::uint8_t{1} << static_cast<std::uint8_t>(GenericConstantExpressionFlag::NoUnsignedWrap)) |
+        (std::uint8_t{1} << static_cast<std::uint8_t>(
+             GenericConstantExpressionFlag::NoUnsignedWrap)) |
         (std::uint8_t{1} << static_cast<std::uint8_t>(GenericConstantExpressionFlag::NoSignedWrap));
     const std::uint8_t GEPFlags =
         (std::uint8_t{1} << static_cast<std::uint8_t>(GenericConstantExpressionFlag::InBounds)) |
-        (std::uint8_t{1} <<
-         static_cast<std::uint8_t>(GenericConstantExpressionFlag::NoUnsignedSignedWrap)) |
-        (std::uint8_t{1} <<
-         static_cast<std::uint8_t>(GenericConstantExpressionFlag::GEPNoUnsignedWrap));
+        (std::uint8_t{1} << static_cast<std::uint8_t>(
+             GenericConstantExpressionFlag::NoUnsignedSignedWrap)) |
+        (std::uint8_t{1} << static_cast<std::uint8_t>(
+             GenericConstantExpressionFlag::GEPNoUnsignedWrap));
     if ((!IsBinary && !IsGEP && Flags != 0) || (IsBinary && (Flags & ~BinaryFlags) != 0) ||
         (IsGEP && (Flags & ~GEPFlags) != 0)) {
       return makeUnexpected(ErrorCode::VerificationError,
@@ -594,14 +591,14 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
       if (!isIntegerOrIntegerVectorType(Value.Type) ||
           !sameResolvedType(Value.Elements[0].Type, Value.Type) ||
           !sameResolvedType(Value.Elements[1].Type, Value.Type)) {
-        return makeUnexpected(ErrorCode::VerificationError,
-                              "generic binary constant requires equal integer operand and result types");
+        return makeUnexpected(
+            ErrorCode::VerificationError,
+            "generic binary constant requires equal integer operand and result types");
       }
       return {};
     case GenericConstantExpressionOpcode::GetElementPtr: {
       if (!Value.SourceElementType || !isSizedType(*Value.SourceElementType) ||
-          !isPointerOrPointerVectorType(FirstType) ||
-          !isPointerOrPointerVectorType(Value.Type)) {
+          !isPointerOrPointerVectorType(FirstType) || !isPointerOrPointerVectorType(Value.Type)) {
         return makeUnexpected(ErrorCode::VerificationError,
                               "generic getelementptr constant has invalid source or pointer types");
       }
@@ -631,9 +628,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept {
         return makeUnexpected(ErrorCode::VerificationError,
                               "generic getelementptr result has an incompatible vector shape");
       }
-      if (Value.InRangeStart &&
-          (Value.InRangeStart->bitWidth() != Value.InRangeEnd->bitWidth() ||
-           !signedIntegerLess(*Value.InRangeStart, *Value.InRangeEnd))) {
+      if (Value.InRangeStart && (Value.InRangeStart->bitWidth() != Value.InRangeEnd->bitWidth() ||
+                                 !signedIntegerLess(*Value.InRangeStart, *Value.InRangeEnd))) {
         return makeUnexpected(ErrorCode::VerificationError,
                               "generic getelementptr inrange interval is invalid");
       }
@@ -756,9 +752,8 @@ Expected<GenericConstantType> GenericConstantType::array(std::uint64_t Count,
   return Type;
 }
 
-Expected<GenericConstantType> GenericConstantType::vector(std::uint64_t Count,
-                                                          GenericConstantType Element,
-                                                          bool IsScalable) {
+Expected<GenericConstantType>
+GenericConstantType::vector(std::uint64_t Count, GenericConstantType Element, bool IsScalable) {
   if (Count == 0)
     return makeUnexpected(ErrorCode::InvalidArgument, "generic vector type cannot be empty");
   auto Verification = Element.verify();
@@ -800,8 +795,7 @@ GenericConstantType::function(GenericConstantType Return,
   return Type;
 }
 
-Expected<GenericConstantType> GenericConstantType::named(std::string TypeName,
-                                                         bool IsNumericName) {
+Expected<GenericConstantType> GenericConstantType::named(std::string TypeName, bool IsNumericName) {
   if (TypeName.empty())
     return makeUnexpected(ErrorCode::InvalidArgument, "generic named type cannot be empty");
   GenericConstantType Type;
diff --git a/backend/lib/CodeGen/InlineSpiller.cpp b/backend/lib/CodeGen/InlineSpiller.cpp
new file mode 100644
index 0000000..589b7b8
--- /dev/null
+++ b/backend/lib/CodeGen/InlineSpiller.cpp
@@ -0,0 +1,270 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/Spiller.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <cstddef>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] Expected<void> clearDebugRegisterOperand(MachineOperand &Operand) {
+  RegisterOperandFlags Flags = Operand.registerFlags();
+  Flags.set(RegisterOperandFlag::Undef);
+  auto SetReg = Operand.setRegister(Register{});
+  if (!SetReg)
+    return std::unexpected(SetReg.error());
+  auto SetSubReg = Operand.setSubReg(SubRegIndex{});
+  if (!SetSubReg)
+    return std::unexpected(SetSubReg.error());
+  return Operand.setRegisterFlags(Flags);
+}
+
+} // namespace
+
+Expected<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Register VirtualReg) {
+  if (!EnableRematerialization)
+    return std::optional<std::vector<Register>>{};
+  const MachineOperand *Definition = Function->registerInfo().getUniqueVRegDef(VirtualReg);
+  const MachineInstr *DefiningInstruction = Definition == nullptr ? nullptr : Definition->parent();
+  if (DefiningInstruction == nullptr || DefiningInstruction->parent() == nullptr)
+    return std::optional<std::vector<Register>>{};
+  auto Accepted =
+      TargetInfo->isRematerializable(*DefiningInstruction, VirtualReg, *Function, *Target);
+  if (!Accepted)
+    return std::unexpected(Accepted.error());
+  if (!*Accepted)
+    return std::optional<std::vector<Register>>{};
+
+  struct UseSite final {
+    MachineInstr *Instruction = nullptr;
+    std::vector<std::size_t> OperandIndices;
+  };
+  std::vector<UseSite> Sites;
+  for (MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      UseSite Site{Instruction, {}};
+      bool HasDefinition = false;
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+        if (Reg == nullptr || *Reg != VirtualReg)
+          continue;
+        HasDefinition |= Operand->isDef();
+        if (Operand->isUse() && !Operand->isDebugUse())
+          Site.OperandIndices.push_back(Index);
+      }
+      if (HasDefinition && !Site.OperandIndices.empty())
+        return std::optional<std::vector<Register>>{};
+      if (!Site.OperandIndices.empty())
+        Sites.push_back(std::move(Site));
+    }
+  }
+  if (Sites.empty())
+    return std::optional<std::vector<Register>>{};
+
+  std::vector<Register> NewRegisters;
+  NewRegisters.reserve(Sites.size());
+  for (UseSite &Site : Sites) {
+    auto Child = Edit.createFrom(VirtualReg, false);
+    if (!Child)
+      return std::unexpected(Child.error());
+    MachineIRBuilder Builder(*Function, *Target);
+    auto Positioned = Builder.setInsertPointBefore(*Site.Instruction);
+    if (!Positioned)
+      return std::unexpected(Positioned.error());
+    auto Materialized =
+        TargetInfo->rematerialize(Builder, *DefiningInstruction, *Child, VirtualReg, *Target);
+    if (!Materialized)
+      return std::unexpected(Materialized.error());
+    for (const std::size_t Index : Site.OperandIndices) {
+      MachineOperand *Operand = Site.Instruction->operandAt(Index);
+      auto Replaced = Operand->setRegister(*Child);
+      if (!Replaced)
+        return std::unexpected(Replaced.error());
+    }
+    VirtRegMapEntry *Entry = Mapping->entry(VirtualReg);
+    if (Entry != nullptr)
+      ++Entry->Spill.RematerializationCount;
+    NewRegisters.push_back(*Child);
+  }
+
+  bool HasNonDebugUse = false;
+  for (const MachineOperand &Operand : Function->registerInfo().useOperands(VirtualReg, false)) {
+    if (Operand.parent() != nullptr) {
+      HasNonDebugUse = true;
+      break;
+    }
+  }
+  if (!HasNonDebugUse) {
+    MachineBasicBlock *Block = const_cast<MachineBasicBlock *>(DefiningInstruction->parent());
+    auto Removed = Block->removeInstruction(*const_cast<MachineInstr *>(DefiningInstruction));
+    if (!Removed)
+      return std::unexpected(Removed.error());
+  }
+  return std::optional<std::vector<Register>>(std::move(NewRegisters));
+}
+
+Expected<std::vector<Register>> Spiller::spillAtInstructions(Register VirtualReg) {
+  auto ClassID = regalloc_detail::registerClassFor(*Function, VirtualReg);
+  if (!ClassID)
+    return std::unexpected(ClassID.error());
+  auto Validated = TargetInfo->validateSpillReload(*ClassID, *Target);
+  if (!Validated) {
+    std::string Message =
+        "target declares an allocatable spillable class without spill/reload support: ";
+    Message.append(Validated.error().message());
+    return makeUnexpected(ErrorCode::InternalError, std::move(Message));
+  }
+  auto StackSlot = Edit.getOrCreateSpillSlot(VirtualReg);
+  if (!StackSlot)
+    return std::unexpected(StackSlot.error());
+  auto LiveInSpill = spillLiveIn(VirtualReg, *ClassID, *StackSlot);
+  if (!LiveInSpill)
+    return std::unexpected(LiveInSpill.error());
+
+  struct SpillSite final {
+    MachineInstr *Instruction = nullptr;
+    std::vector<std::size_t> OperandIndices;
+    std::vector<std::size_t> DebugIndices;
+    bool HasUse = false;
+    bool HasDef = false;
+  };
+  std::vector<SpillSite> Sites;
+  for (MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      SpillSite Site;
+      Site.Instruction = Instruction;
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+        if (Reg == nullptr || *Reg != VirtualReg)
+          continue;
+        if (Operand->isDebugUse()) {
+          Site.DebugIndices.push_back(Index);
+          continue;
+        }
+        Site.OperandIndices.push_back(Index);
+        Site.HasUse |= Operand->isUse();
+        Site.HasDef |= Operand->isDef();
+      }
+      if (!Site.OperandIndices.empty() || !Site.DebugIndices.empty())
+        Sites.push_back(std::move(Site));
+    }
+  }
+
+  std::vector<Register> NewRegisters;
+  for (SpillSite &Site : Sites) {
+    for (const std::size_t Index : Site.DebugIndices) {
+      MachineOperand *Operand = Site.Instruction->operandAt(Index);
+      auto Cleared = clearDebugRegisterOperand(*Operand);
+      if (!Cleared)
+        return std::unexpected(Cleared.error());
+    }
+    if (Site.OperandIndices.empty())
+      continue;
+
+    auto Child = Edit.createFrom(VirtualReg, false);
+    if (!Child)
+      return std::unexpected(Child.error());
+    if (Site.HasUse) {
+      MachineIRBuilder Builder(*Function, *Target);
+      auto Positioned = Builder.setInsertPointBefore(*Site.Instruction);
+      if (!Positioned)
+        return std::unexpected(Positioned.error());
+      auto Reload = TargetInfo->emitReload(Builder, *Child, *ClassID, *StackSlot, LaneMask::all());
+      if (!Reload)
+        return std::unexpected(Reload.error());
+      VirtRegMapEntry *Entry = Mapping->entry(VirtualReg);
+      if (Entry != nullptr)
+        ++Entry->Spill.ReloadCount;
+    }
+    for (const std::size_t Index : Site.OperandIndices) {
+      MachineOperand *Operand = Site.Instruction->operandAt(Index);
+      auto Replaced = Operand->setRegister(*Child);
+      if (!Replaced)
+        return std::unexpected(Replaced.error());
+    }
+    if (Site.HasDef) {
+      const InstructionDescriptor *Descriptor =
+          Target->instructionDescriptor(Site.Instruction->opcode());
+      if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) {
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "a terminator-defined value cannot be spilled on its outgoing edge");
+      }
+      MachineIRBuilder Builder(*Function, *Target);
+      auto Positioned = Builder.setInsertPointAfter(*Site.Instruction);
+      if (!Positioned)
+        return std::unexpected(Positioned.error());
+      auto Spill = TargetInfo->emitSpill(Builder, *Child, *ClassID, *StackSlot, LaneMask::all());
+      if (!Spill)
+        return std::unexpected(Spill.error());
+      VirtRegMapEntry *Entry = Mapping->entry(VirtualReg);
+      if (Entry != nullptr)
+        ++Entry->Spill.SpillCount;
+    }
+    NewRegisters.push_back(*Child);
+  }
+  return NewRegisters;
+}
+
+Expected<void> Spiller::spillLiveIn(Register VirtualReg, RegisterClassID Class,
+                                    FrameIndex StackSlot) {
+  const auto LiveIn = std::ranges::find_if(Function->registerInfo().liveIns(),
+                                           [VirtualReg](const PhysicalRegisterLiveIn &Value) {
+                                             return Value.InitialVirtualRegister == VirtualReg;
+                                           });
+  if (LiveIn == Function->registerInfo().liveIns().end())
+    return {};
+  MachineBasicBlock *EntryBlock = Function->firstBlock();
+  if (EntryBlock == nullptr) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "function live-in spill requires an entry block");
+  }
+  MachineIRBuilder Builder(*Function, *Target);
+  Expected<void> Positioned = EntryBlock->firstInstruction() != nullptr
+                                  ? Builder.setInsertPointBefore(*EntryBlock->firstInstruction())
+                                  : Builder.setInsertPoint(*EntryBlock);
+  if (!Positioned)
+    return std::unexpected(Positioned.error());
+  auto Spill = TargetInfo->emitSpill(Builder, Register::fromPhysical(LiveIn->PhysReg), Class,
+                                     StackSlot, LaneMask::all());
+  if (!Spill)
+    return std::unexpected(Spill.error());
+  VirtRegMapEntry *Entry = Mapping->entry(VirtualReg);
+  if (Entry != nullptr)
+    ++Entry->Spill.SpillCount;
+  return {};
+}
+
+Expected<std::vector<Register>> Spiller::spill(Register VirtualReg) {
+  if (!VirtualReg.isVirtual() || !Function->registerInfo().isKnownVirtualRegister(VirtualReg))
+    return makeUnexpected(ErrorCode::InvalidArgument, "Spiller requires a known virtual register");
+  if (!Mapping->isSpillable(VirtualReg)) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "register pressure requires spilling a non-spillable value");
+  }
+  auto Rematerialized = tryRematerialize(VirtualReg);
+  if (!Rematerialized)
+    return std::unexpected(Rematerialized.error());
+  if (*Rematerialized)
+    return std::move(**Rematerialized);
+  return spillAtInstructions(VirtualReg);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/LiveRangeEdit.cpp b/backend/lib/CodeGen/LiveRangeEdit.cpp
new file mode 100644
index 0000000..23a7b3d
--- /dev/null
+++ b/backend/lib/CodeGen/LiveRangeEdit.cpp
@@ -0,0 +1,126 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LiveRangeEdit.h"
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+namespace rcc {
+
+Expected<Register> LiveRangeEdit::createFrom(Register Parent, bool Spillable,
+                                             std::optional<Register> Origin) {
+  auto ParentInfo = Function->registerInfo().virtualRegisterInfo(Parent);
+  if (!ParentInfo)
+    return std::unexpected(ParentInfo.error());
+  const VirtualRegisterInfo &Source = ParentInfo->get();
+  Expected<Register> Created = Source.Type
+                                   ? Function->registerInfo().createVirtualRegister(*Source.Type)
+                                   : Function->registerInfo().createVirtualRegister();
+  if (!Created)
+    return std::unexpected(Created.error());
+  const Register Child = *Created;
+  auto Fail = [&](const Error &Failure) -> Expected<Register> {
+    auto Erased = Function->registerInfo().eraseVirtualRegister(Child);
+    if (!Erased)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "split virtual-register setup and rollback both failed");
+    return std::unexpected(Failure);
+  };
+  if (Source.Bank) {
+    auto Set = Function->registerInfo().setRegisterBank(Child, *Source.Bank);
+    if (!Set)
+      return Fail(Set.error());
+  }
+  if (Source.RegClass) {
+    auto Set = Function->registerInfo().setRegisterClass(Child, *Source.RegClass);
+    if (!Set)
+      return Fail(Set.error());
+  }
+  for (const PhysicalRegister Hint : Source.AllocationHints) {
+    auto Added = Function->registerInfo().addAllocationHint(Child, Hint);
+    if (!Added)
+      return Fail(Added.error());
+  }
+  if (Source.TargetFlags != 0) {
+    auto Set = Function->registerInfo().setTargetRegisterFlags(Child, Source.TargetFlags);
+    if (!Set)
+      return Fail(Set.error());
+  }
+  const VirtRegMapEntry *ParentEntry = Mapping->entry(Parent);
+  const Register Root = Origin.value_or(
+      ParentEntry != nullptr && ParentEntry->Origin ? *ParentEntry->Origin : Parent);
+  const std::optional<FrameIndex> ParentStackSlot =
+      ParentEntry == nullptr ? std::nullopt : ParentEntry->Spill.StackSlot;
+  const LaneMask ParentSpillLanes =
+      ParentEntry == nullptr ? LaneMask::all() : ParentEntry->Spill.Lanes;
+  auto Added = Mapping->add(Child, Spillable, Parent, Root);
+  if (!Added)
+    return Fail(Added.error());
+  auto Split = Mapping->markSplit(Child, Parent, Root);
+  if (!Split)
+    return Fail(Split.error());
+  if (ParentStackSlot) {
+    auto SharedSlot = Mapping->assignStackSlot(Child, *ParentStackSlot, ParentSpillLanes);
+    if (!SharedSlot)
+      return Fail(SharedSlot.error());
+  }
+  return Child;
+}
+
+Expected<FrameIndex> LiveRangeEdit::getOrCreateSpillSlot(Register VirtualReg) {
+  if (const auto Existing = Mapping->stackSlot(VirtualReg))
+    return *Existing;
+  const VirtRegMapEntry *Entry = Mapping->entry(VirtualReg);
+  const Register Original = Entry != nullptr && Entry->Origin ? *Entry->Origin : VirtualReg;
+  if (Original != VirtualReg) {
+    if (const auto Existing = Mapping->stackSlot(Original)) {
+      auto Shared = Mapping->assignStackSlot(VirtualReg, *Existing);
+      if (!Shared)
+        return std::unexpected(Shared.error());
+      return *Existing;
+    }
+  }
+  auto ClassID = regalloc_detail::registerClassFor(*Function, Original);
+  if (!ClassID)
+    return std::unexpected(ClassID.error());
+  const RegisterClassDesc *Class = Target->registers().registerClass(*ClassID);
+  if (Class == nullptr || Class->SpillSizeInBits == 0 || Class->SpillAlignmentInBits == 0 ||
+      Class->SpillSizeInBits % 8U != 0 || Class->SpillAlignmentInBits % 8U != 0) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "allocatable register class has no valid spill size and alignment");
+  }
+  auto Align = Alignment::create(Class->SpillAlignmentInBits / 8U);
+  if (!Align)
+    return std::unexpected(Align.error());
+  StackObjectDesc Description;
+  Description.Kind = StackObjectKind::SpillSlot;
+  Description.Size = Class->SpillSizeInBits / 8U;
+  Description.Align = *Align;
+  auto Slot = Function->frameInfo().createObject(std::move(Description));
+  if (!Slot)
+    return std::unexpected(Slot.error());
+  auto AssignedOriginal = Mapping->assignStackSlot(Original, *Slot);
+  if (!AssignedOriginal)
+    return std::unexpected(AssignedOriginal.error());
+  if (Original != VirtualReg) {
+    auto AssignedChild = Mapping->assignStackSlot(VirtualReg, *Slot);
+    if (!AssignedChild)
+      return std::unexpected(AssignedChild.error());
+  }
+  return *Slot;
+}
+
+Expected<void> LiveRangeEdit::eraseVirtualRegister(Register VirtualReg) {
+  if (!Function->registerInfo().useEmpty(VirtualReg))
+    return makeUnexpected(ErrorCode::InternalError,
+                          "cannot erase a split virtual register with remaining uses");
+  for (const MachineOperand &Operand : Function->registerInfo().defOperands(VirtualReg)) {
+    if (Operand.parent() != nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "cannot erase a split virtual register with remaining definitions");
+  }
+  return Function->registerInfo().eraseVirtualRegister(VirtualReg);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/LiveRegMatrix.cpp b/backend/lib/CodeGen/LiveRegMatrix.cpp
new file mode 100644
index 0000000..64c7046
--- /dev/null
+++ b/backend/lib/CodeGen/LiveRegMatrix.cpp
@@ -0,0 +1,330 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LiveRegMatrix.h"
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <tuple>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<LaneMask> relevantLanes(const LiveInterval &Interval,
+                                                    RegisterUnitLane Unit) noexcept {
+  if (Interval.SubRanges.empty())
+    return Unit.Lanes;
+  LaneMask Result;
+  for (const LiveSubRange &SubRange : Interval.SubRanges) {
+    if (SubRange.Lanes.intersects(Unit.Lanes))
+      Result = Result | (SubRange.Lanes & Unit.Lanes);
+  }
+  if (Result.empty())
+    return std::nullopt;
+  return Result;
+}
+
+[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept {
+  std::uint64_t View = UnitViewLanes.rawValue();
+  const std::uint64_t Selected = View & RegisterLanes.rawValue();
+  std::uint64_t Normalized = 0;
+  std::uint32_t UnitLane = 0;
+  while (View != 0) {
+    const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View);
+    if ((Selected & RegisterLane) != 0)
+      Normalized |= std::uint64_t{1} << UnitLane;
+    View &= View - 1U;
+    ++UnitLane;
+  }
+  return LaneMask::fromRaw(Normalized);
+}
+
+[[nodiscard]] LaneMask intervalUnitLanes(const LiveInterval &Interval,
+                                         RegisterUnitLane Unit) noexcept {
+  if (Interval.SubRanges.empty())
+    return normalizeUnitLanes(Unit.Lanes, Unit.Lanes);
+  LaneMask Result;
+  for (const LiveSubRange &SubRange : Interval.SubRanges)
+    Result = Result | normalizeUnitLanes(Unit.Lanes, SubRange.Lanes);
+  return Result;
+}
+
+[[nodiscard]] bool intervalLiveAtFixedRegister(const LiveInterval &Interval,
+                                               const PhysicalRegisterDesc &Candidate,
+                                               const PhysicalRegisterDesc &Fixed,
+                                               SlotIndex Position) noexcept {
+  for (const RegisterUnitLane CandidateUnit : Candidate.Units) {
+    const auto FixedUnit =
+        std::ranges::find(Fixed.Units, CandidateUnit.Unit, &RegisterUnitLane::Unit);
+    if (FixedUnit == Fixed.Units.end())
+      continue;
+    const LaneMask FixedLanes = normalizeUnitLanes(FixedUnit->Lanes, FixedUnit->Lanes);
+    if (Interval.SubRanges.empty()) {
+      if (normalizeUnitLanes(CandidateUnit.Lanes, CandidateUnit.Lanes).intersects(FixedLanes) &&
+          Interval.MainRange.liveAt(Position)) {
+        return true;
+      }
+      continue;
+    }
+    for (const LiveSubRange &SubRange : Interval.SubRanges) {
+      if (normalizeUnitLanes(CandidateUnit.Lanes, SubRange.Lanes).intersects(FixedLanes) &&
+          SubRange.Range.liveAt(Position)) {
+        return true;
+      }
+    }
+  }
+  return false;
+}
+
+[[nodiscard]] bool rangeForUnitOverlaps(const LiveInterval &Interval, RegisterUnitLane Unit,
+                                        const LiveRange &Other) noexcept {
+  if (!relevantLanes(Interval, Unit))
+    return false;
+  if (Interval.SubRanges.empty())
+    return Interval.MainRange.overlaps(Other);
+  for (const LiveSubRange &SubRange : Interval.SubRanges) {
+    if (SubRange.Lanes.intersects(Unit.Lanes) && SubRange.Range.overlaps(Other))
+      return true;
+  }
+  return false;
+}
+
+} // namespace
+
+bool regalloc_detail::intervalsOverlapOnPhysicalRegisters(
+    const LiveInterval &Left, PhysicalRegister LeftReg, const LiveInterval &Right,
+    PhysicalRegister RightReg, const TargetRegisterInfo &Registers) noexcept {
+  const PhysicalRegisterDesc *LeftDescription = Registers.physicalRegister(LeftReg);
+  const PhysicalRegisterDesc *RightDescription = Registers.physicalRegister(RightReg);
+  if (LeftDescription == nullptr || RightDescription == nullptr)
+    return true;
+  for (const RegisterUnitLane LeftUnit : LeftDescription->Units) {
+    for (const RegisterUnitLane RightUnit : RightDescription->Units) {
+      if (LeftUnit.Unit != RightUnit.Unit)
+        continue;
+      const LaneMask LeftUnitLanes = intervalUnitLanes(Left, LeftUnit);
+      const LaneMask RightUnitLanes = intervalUnitLanes(Right, RightUnit);
+      if (!LeftUnitLanes.intersects(RightUnitLanes))
+        continue;
+      if (Left.SubRanges.empty() && Right.SubRanges.empty())
+        return Left.MainRange.overlaps(Right.MainRange);
+      const auto LeftRanges = Left.SubRanges.empty()
+                                  ? std::span<const LiveSubRange>{}
+                                  : std::span<const LiveSubRange>(Left.SubRanges);
+      const auto RightRanges = Right.SubRanges.empty()
+                                   ? std::span<const LiveSubRange>{}
+                                   : std::span<const LiveSubRange>(Right.SubRanges);
+      if (LeftRanges.empty()) {
+        for (const LiveSubRange &RightRange : RightRanges) {
+          const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes);
+          if (LeftUnitLanes.intersects(RightRangeLanes) &&
+              Left.MainRange.overlaps(RightRange.Range))
+            return true;
+        }
+        continue;
+      }
+      if (RightRanges.empty()) {
+        for (const LiveSubRange &LeftRange : LeftRanges) {
+          const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes);
+          if (LeftRangeLanes.intersects(RightUnitLanes) &&
+              LeftRange.Range.overlaps(Right.MainRange))
+            return true;
+        }
+        continue;
+      }
+      for (const LiveSubRange &LeftRange : LeftRanges) {
+        const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes);
+        if (LeftRangeLanes.empty())
+          continue;
+        for (const LiveSubRange &RightRange : RightRanges) {
+          const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes);
+          if (LeftRangeLanes.intersects(RightRangeLanes) &&
+              LeftRange.Range.overlaps(RightRange.Range))
+            return true;
+        }
+      }
+    }
+  }
+  return false;
+}
+
+bool LiveRegMatrix::intervalOverlapsUnit(const LiveInterval &Interval, RegisterUnitLane Unit,
+                                         const LiveRange &UnitRange) const noexcept {
+  return rangeForUnitOverlaps(Interval, Unit, UnitRange);
+}
+
+bool LiveRegMatrix::intervalsOverlapOnCandidates(const LiveInterval &Left, PhysicalRegister LeftReg,
+                                                 const LiveInterval &Right,
+                                                 PhysicalRegister RightReg) const noexcept {
+  return regalloc_detail::intervalsOverlapOnPhysicalRegisters(Left, LeftReg, Right, RightReg,
+                                                              Target->registers());
+}
+
+std::vector<RegisterInterference>
+LiveRegMatrix::collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const {
+  std::vector<RegisterInterference> Result;
+  const LiveInterval *Interval = Intervals->interval(VirtualReg);
+  const PhysicalRegisterDesc *Candidate = Target->registers().physicalRegister(PhysicalReg);
+  if (Interval == nullptr || Candidate == nullptr)
+    return Result;
+
+  for (const MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const SlotIndex Position = Intervals->slot(*Instruction);
+      if (!Position.isValid())
+        continue;
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg == nullptr || !Reg->isPhysical())
+          continue;
+        const auto Fixed = Reg->physicalRegister();
+        if (!Fixed)
+          continue;
+        const PhysicalRegister FixedReg = Fixed.value();
+        if (!Target->registers().regsOverlap(FixedReg, PhysicalReg))
+          continue;
+        const PhysicalRegisterDesc *FixedDescription =
+            Target->registers().physicalRegister(FixedReg);
+        if (FixedDescription == nullptr)
+          continue;
+        const SlotIndex OperandPosition =
+            Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)
+                ? Position.earlyClobberSlot()
+                : Position.registerSlot();
+        if (intervalLiveAtFixedRegister(*Interval, *Candidate, *FixedDescription,
+                                        OperandPosition)) {
+          Result.push_back(RegisterInterference{RegisterInterferenceKind::FixedRegister,
+                                                std::nullopt, FixedReg, std::nullopt,
+                                                Instruction->stableID()});
+        }
+      }
+    }
+  }
+
+  for (const RegMaskPosition &Mask : Intervals->regMaskPositions()) {
+    if (Mask.Mask && Mask.Mask->clobbers(PhysicalReg) &&
+        Interval->MainRange.liveAt(Mask.Position)) {
+      Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterMask, std::nullopt,
+                                            std::nullopt, std::nullopt, Mask.Instruction});
+    }
+  }
+
+  for (const RegisterUnitLane Unit : Candidate->Units) {
+    const LiveRange *FixedRange = Intervals->regUnitRange(Unit.Unit);
+    if (FixedRange != nullptr && intervalOverlapsUnit(*Interval, Unit, *FixedRange)) {
+      Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterUnit, std::nullopt,
+                                            std::nullopt, Unit.Unit, std::nullopt});
+    }
+  }
+
+  for (const auto &[OtherReg, OtherPhysical] : OrderedAssignments) {
+    if (OtherReg == VirtualReg)
+      continue;
+    const LiveInterval *OtherInterval = Intervals->interval(OtherReg);
+    if (OtherInterval != nullptr &&
+        intervalsOverlapOnCandidates(*Interval, PhysicalReg, *OtherInterval, OtherPhysical)) {
+      Result.push_back(RegisterInterference{RegisterInterferenceKind::VirtualRegister, OtherReg,
+                                            std::nullopt, std::nullopt, std::nullopt});
+    }
+  }
+
+  std::ranges::sort(
+      Result, [](const RegisterInterference &Left, const RegisterInterference &Right) {
+        return std::tuple{Left.Kind, Left.VirtualReg.value_or(Register{}).opaqueValue(),
+                          Left.FixedReg.value_or(PhysicalRegister{}).number(),
+                          Left.Unit ? Left.Unit->value() : 0U,
+                          Left.Instruction ? Left.Instruction->value() : 0ULL} <
+               std::tuple{Right.Kind, Right.VirtualReg.value_or(Register{}).opaqueValue(),
+                          Right.FixedReg.value_or(PhysicalRegister{}).number(),
+                          Right.Unit ? Right.Unit->value() : 0U,
+                          Right.Instruction ? Right.Instruction->value() : 0ULL};
+      });
+  Result.erase(std::unique(Result.begin(), Result.end(),
+                           [](const RegisterInterference &Left, const RegisterInterference &Right) {
+                             return Left.Kind == Right.Kind &&
+                                    Left.VirtualReg == Right.VirtualReg &&
+                                    Left.FixedReg == Right.FixedReg && Left.Unit == Right.Unit &&
+                                    Left.Instruction == Right.Instruction;
+                           }),
+               Result.end());
+  return Result;
+}
+
+RegisterInterference LiveRegMatrix::checkInterference(Register VirtualReg,
+                                                      PhysicalRegister PhysicalReg) const noexcept {
+  const std::vector<RegisterInterference> Values = collectInterferences(VirtualReg, PhysicalReg);
+  if (Values.empty())
+    return {};
+  return Values.front();
+}
+
+Expected<void> LiveRegMatrix::assign(Register VirtualReg, PhysicalRegister PhysicalReg) {
+  if (!VirtualReg.isVirtual() || Intervals->interval(VirtualReg) == nullptr ||
+      Target->registers().physicalRegister(PhysicalReg) == nullptr) {
+    return makeUnexpected(
+        ErrorCode::InvalidArgument,
+        "LiveRegMatrix assignment requires a known interval and physical register");
+  }
+  if (regalloc_detail::isUnavailablePhysicalRegister(*Function, Target->registers(), PhysicalReg)) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "LiveRegMatrix cannot assign an unavailable physical register");
+  }
+  auto Info = Function->registerInfo().virtualRegisterInfo(VirtualReg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  const auto ClassID = Info->get().RegClass;
+  if (ClassID) {
+    if (!Target->registers().registerClassContains(ClassID.value(), PhysicalReg)) {
+      return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                            "LiveRegMatrix assignment is outside the virtual register class");
+    }
+  }
+  if (!regalloc_detail::candidateSupportsSubRegisters(*Function, Target->registers(), VirtualReg,
+                                                      PhysicalReg)) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "LiveRegMatrix assignment lacks a required subregister view");
+  }
+  if (Assignments.contains(VirtualReg))
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is already assigned");
+  const RegisterInterference Interference = checkInterference(VirtualReg, PhysicalReg);
+  if (Interference.Kind != RegisterInterferenceKind::Free) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "physical register assignment has live interference");
+  }
+  Assignments.emplace(VirtualReg, PhysicalReg);
+  OrderedAssignments.emplace_back(VirtualReg, PhysicalReg);
+  std::ranges::sort(OrderedAssignments, [](const auto &Left, const auto &Right) {
+    return Left.first.opaqueValue() < Right.first.opaqueValue();
+  });
+  return {};
+}
+
+Expected<void> LiveRegMatrix::unassign(Register VirtualReg) {
+  if (!Assignments.erase(VirtualReg))
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is not assigned");
+  std::erase_if(OrderedAssignments,
+                [VirtualReg](const auto &Entry) { return Entry.first == VirtualReg; });
+  return {};
+}
+
+std::optional<PhysicalRegister> LiveRegMatrix::assignment(Register VirtualReg) const noexcept {
+  const auto Position = Assignments.find(VirtualReg);
+  if (Position == Assignments.end())
+    return std::nullopt;
+  return Position->second;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineAnalyses.cpp b/backend/lib/CodeGen/MachineAnalyses.cpp
index cbc46fd..33dc14f 100644
--- a/backend/lib/CodeGen/MachineAnalyses.cpp
+++ b/backend/lib/CodeGen/MachineAnalyses.cpp
@@ -12,6 +12,7 @@
 #include <cstddef>
 #include <cstdint>
 #include <limits>
+#include <map>
 #include <optional>
 #include <ranges>
 #include <span>
@@ -296,7 +297,7 @@ Expected<MachineLoopAnalysis::Result> MachineLoopAnalysis::run(MachineFunction &
   Result ResultValue;
   std::vector<MachineBasicBlock *> Blocks = linkedBlocks(Function);
   const auto Order = blockOrder(Blocks);
-  std::unordered_map<MachineBasicBlock *, std::unordered_set<MachineBasicBlock *>> LoopBlocks;
+  std::map<MachineBasicBlock *, std::unordered_set<MachineBasicBlock *>> LoopBlocks;
   std::unordered_map<MachineBasicBlock *, std::vector<MachineBasicBlock *>> LoopLatches;
 
   for (MachineBasicBlock *Latch : Blocks) {
diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp
index 600deac..1091b52 100644
--- a/backend/lib/CodeGen/MachineCompilationStatus.cpp
+++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp
@@ -42,6 +42,7 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep
   case ErrorCode::ParseError:
   case ErrorCode::VerificationError:
   case ErrorCode::Unsupported:
+  case ErrorCode::RegisterAllocationFailed:
   case ErrorCode::IoError:
   case ErrorCode::InternalError:
     return true;
diff --git a/backend/lib/CodeGen/MachineFrameInfo.cpp b/backend/lib/CodeGen/MachineFrameInfo.cpp
index 21a4b78..a6f7a77 100644
--- a/backend/lib/CodeGen/MachineFrameInfo.cpp
+++ b/backend/lib/CodeGen/MachineFrameInfo.cpp
@@ -66,8 +66,7 @@ parseMachineFramePointerPolicy(std::string_view Name) noexcept {
   return std::nullopt;
 }
 
-std::string_view
-getMachineFramePointerPolicyName(MachineFramePointerPolicy Policy) noexcept {
+std::string_view getMachineFramePointerPolicyName(MachineFramePointerPolicy Policy) noexcept {
   switch (Policy) {
   case MachineFramePointerPolicy::None:
     return "none";
@@ -96,8 +95,8 @@ bool StackObject::isSpill() const noexcept {
 
 bool StackObject::isFixed() const noexcept {
   const StackObjectDesc *Desc = description();
-  return Desc != nullptr && (Desc->Kind == StackObjectKind::FixedABI ||
-                             Desc->Kind == StackObjectKind::FixedSpillSlot);
+  return Desc != nullptr &&
+         (Desc->Kind == StackObjectKind::FixedABI || Desc->Kind == StackObjectKind::FixedSpillSlot);
 }
 
 bool StackObject::isVariableSized() const noexcept {
@@ -142,9 +141,8 @@ Expected<void> MachineFrameInfo::verifyDescription(const StackObjectDesc &Descri
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "callee-saved stack objects require a nonzero physical register");
   }
-  if (Description.LocalOffset &&
-      (Description.Kind == StackObjectKind::FixedABI ||
-       Description.Kind == StackObjectKind::FixedSpillSlot)) {
+  if (Description.LocalOffset && (Description.Kind == StackObjectKind::FixedABI ||
+                                  Description.Kind == StackObjectKind::FixedSpillSlot)) {
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "fixed ABI stack objects cannot have a local frame offset");
   }
@@ -196,8 +194,7 @@ Expected<void> MachineFrameInfo::verifyStateStructure(const MachineFrameState &S
       for (const PhysicalRegister Reg : Point.Registers) {
         if (Reg.number() == 0 || !Registers.insert(Reg).second) {
           return makeUnexpected(ErrorCode::InvalidArgument,
-                                std::string(Kind) +
-                                    " point registers must be nonzero and unique");
+                                std::string(Kind) + " point registers must be nonzero and unique");
         }
       }
     }
diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp
index ced3b1a..0048194 100644
--- a/backend/lib/CodeGen/MachineFunctionCloner.cpp
+++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp
@@ -526,8 +526,7 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) {
     }
     return {};
   };
-  auto SaveResult =
-      ClonePoints(State.Source.frameInfo().state().SavePoints, FrameState.SavePoints);
+  auto SaveResult = ClonePoints(State.Source.frameInfo().state().SavePoints, FrameState.SavePoints);
   if (!SaveResult)
     return SaveResult;
   auto RestoreResult =
diff --git a/backend/lib/CodeGen/MachineJumpTableInfo.cpp b/backend/lib/CodeGen/MachineJumpTableInfo.cpp
index 5ba0853..c832e7c 100644
--- a/backend/lib/CodeGen/MachineJumpTableInfo.cpp
+++ b/backend/lib/CodeGen/MachineJumpTableInfo.cpp
@@ -84,9 +84,8 @@ Expected<JumpTableIndex> MachineJumpTableInfo::reserveTable() {
   return Index;
 }
 
-Expected<void>
-MachineJumpTableInfo::defineReservedTable(JumpTableIndex Index,
-                                          MachineJumpTableDesc Description) {
+Expected<void> MachineJumpTableInfo::defineReservedTable(JumpTableIndex Index,
+                                                         MachineJumpTableDesc Description) {
   if (Frozen) {
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "frozen jump table info cannot define reserved tables");
diff --git a/backend/lib/CodeGen/MachineLiveness.cpp b/backend/lib/CodeGen/MachineLiveness.cpp
index b3d88cd..327ae7d 100644
--- a/backend/lib/CodeGen/MachineLiveness.cpp
+++ b/backend/lib/CodeGen/MachineLiveness.cpp
@@ -1662,10 +1662,9 @@ LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &T
     auto Info = Function.registerInfo().virtualRegisterInfo(Reg);
     if (!Info)
       return std::unexpected(Info.error());
+    // Preserve the target-provided hint order.  MachineRegisterInfo already de-duplicates
+    // hints, and their order is the deterministic preference order consumed by allocators.
     Interval.AllocationHints = Info->get().AllocationHints;
-    std::ranges::sort(Interval.AllocationHints, [](PhysicalRegister Left, PhysicalRegister Right) {
-      return Left.number() < Right.number();
-    });
 
     std::uint64_t Weight = 1;
     for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) {
diff --git a/backend/lib/CodeGen/MachinePass.cpp b/backend/lib/CodeGen/MachinePass.cpp
index e6dccd0..ae69b1c 100644
--- a/backend/lib/CodeGen/MachinePass.cpp
+++ b/backend/lib/CodeGen/MachinePass.cpp
@@ -20,6 +20,7 @@
 #include <memory>
 #include <optional>
 #include <ranges>
+#include <set>
 #include <string>
 #include <string_view>
 #include <thread>
@@ -164,8 +165,9 @@ MachineAnalysisManager::registerAnalysisImpl(MachineAnalysisRegistration Registr
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine analysis name is already registered");
   }
-  Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner),
-                                                       std::move(Invalidator)});
+  const AnalysisID RegistrationID = Registration.ID;
+  Registry.emplace(RegistrationID, RegisteredAnalysis{std::move(Registration), std::move(Runner),
+                                                      std::move(Invalidator)});
   return {};
 }
 
@@ -287,7 +289,7 @@ void MachineAnalysisManager::invalidate(MachineFunction &Function,
   if (FunctionPosition == Cache.end() || Preserved.preservesAll() || Changes.empty())
     return;
 
-  std::unordered_set<AnalysisID> Invalid;
+  std::set<AnalysisID> Invalid;
   for (auto &[ID, Entry] : FunctionPosition->second) {
     if (Preserved.preserves(ID))
       continue;
@@ -406,8 +408,9 @@ Expected<void> CompilationUnitAnalysisManager::registerAnalysisImpl(
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "compilation-unit analysis name is already registered");
   }
-  Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner),
-                                                       std::move(Invalidator)});
+  const AnalysisID RegistrationID = Registration.ID;
+  Registry.emplace(RegistrationID, RegisteredAnalysis{std::move(Registration), std::move(Runner),
+                                                      std::move(Invalidator)});
   return {};
 }
 
@@ -524,7 +527,7 @@ void CompilationUnitAnalysisManager::invalidate(CompilationUnit &Unit,
   if (UnitPosition == Cache.end() || Preserved.preservesAll() || Changes.empty())
     return;
 
-  std::unordered_set<AnalysisID> Invalid;
+  std::set<AnalysisID> Invalid;
   for (auto &[ID, Entry] : UnitPosition->second) {
     if (Preserved.preserves(ID))
       continue;
@@ -1238,10 +1241,10 @@ Expected<void> MachinePassManager::runFunctions(CompilationUnit &Unit,
   for (std::size_t Index = 0; Index < FunctionCount; ++Index) {
     if (Instrumentation != nullptr)
       Instrumentation->replayBufferedEvents(EventBuffers[Index]);
-    if (Failures[Index]) {
-      return std::unexpected(
-          prefixedError(*Failures[Index],
-                        "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: "));
+    const auto &Failure = Failures[Index];
+    if (Failure) {
+      return std::unexpected(prefixedError(
+          *Failure, "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: "));
     }
   }
   return {};
diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp
index 3784b22..7bd0ef3 100644
--- a/backend/lib/CodeGen/MachineRegisterInfo.cpp
+++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp
@@ -229,6 +229,11 @@ Expected<void> MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg,
   return {};
 }
 
+void MachineRegisterInfo::clearLiveInVirtualRegisters() noexcept {
+  for (PhysicalRegisterLiveIn &LiveIn : LiveIns)
+    LiveIn.InitialVirtualRegister.reset();
+}
+
 Expected<void> MachineRegisterInfo::reservePhysicalRegister(PhysicalRegister PhysReg) {
   if (!PhysReg.isValid()) {
     return makeUnexpected(ErrorCode::InvalidArgument,
diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp
new file mode 100644
index 0000000..1aae22d
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocBase.cpp
@@ -0,0 +1,91 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "RegAllocBase.h"
+
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/Spiller.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc {
+
+std::vector<const LiveInterval *>
+orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals,
+                           const MachineFunction &Function) {
+  std::vector<const LiveInterval *> Result;
+  for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) {
+    auto Reg = Register::makeVirtual(Index);
+    if (!Reg)
+      continue;
+    const LiveInterval *Interval = Intervals.interval(*Reg);
+    if (Interval != nullptr && !Interval->MainRange.empty())
+      Result.push_back(Interval);
+  }
+  std::ranges::sort(Result, [](const LiveInterval *Left, const LiveInterval *Right) {
+    const LiveSegment &LeftSegment = Left->MainRange.segments().front();
+    const LiveSegment &RightSegment = Right->MainRange.segments().front();
+    if (LeftSegment.Start != RightSegment.Start)
+      return LeftSegment.Start < RightSegment.Start;
+    if (LeftSegment.End != RightSegment.End)
+      return LeftSegment.End < RightSegment.End;
+    return Left->Reg.opaqueValue() < Right->Reg.opaqueValue();
+  });
+  return Result;
+}
+
+Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run() {
+  const std::uint64_t InitialFingerprint = regalloc_detail::allocationFingerprint(Function);
+  const std::size_t InitialFrameObjects = Function.frameInfo().liveObjectCount();
+  VirtRegMap Mapping(Function);
+  auto Initialized = regalloc_detail::initializeMapping(Function, Mapping);
+  if (!Initialized)
+    return std::unexpected(Initialized.error());
+
+  std::unordered_set<std::uint64_t> SeenFingerprints;
+  while (true) {
+    const std::uint64_t Fingerprint = regalloc_detail::allocationFingerprint(Function);
+    if (!SeenFingerprints.insert(Fingerprint).second) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "register allocation spill/rebuild cycle made no progress");
+    }
+    auto Intervals = Analyses.getResult<LiveIntervalsAnalysis>(Function, Target);
+    if (!Intervals)
+      return std::unexpected(Intervals.error());
+    auto Round = allocateRound(**Intervals, Mapping);
+    if (!Round)
+      return std::unexpected(Round.error());
+    if (Round->Spilled.empty())
+      break;
+
+    std::ranges::sort(Round->Spilled, [](Register Left, Register Right) {
+      return Left.opaqueValue() < Right.opaqueValue();
+    });
+    Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization);
+    for (const Register VirtualReg : Round->Spilled) {
+      VirtRegMapEntry *Entry = Mapping.entry(VirtualReg);
+      if (Entry != nullptr) {
+        Entry->PhysicalReg.reset();
+        Entry->State = VirtRegAllocationState::Unassigned;
+      }
+      auto NewRegisters = ValueSpiller.spill(VirtualReg);
+      if (!NewRegisters)
+        return std::unexpected(NewRegisters.error());
+    }
+    Analyses.clear(Function);
+  }
+
+  auto Rewritten = rewriteVirtualRegisters(Function, Target, Mapping);
+  if (!Rewritten)
+    return std::unexpected(Rewritten.error());
+  const std::uint64_t FinalFingerprint = regalloc_detail::allocationFingerprint(Function);
+  regalloc_detail::AllocationRunResult Result;
+  Result.Changed = InitialFingerprint != FinalFingerprint || *Rewritten;
+  Result.ChangedInstructions = InitialFingerprint != FinalFingerprint;
+  Result.ChangedFrame = InitialFrameObjects != Function.frameInfo().liveObjectCount();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h
new file mode 100644
index 0000000..5af5ed0
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocBase.h
@@ -0,0 +1,51 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_LIB_CODEGEN_REGALLOCBASE_H
+#define RCC_LIB_CODEGEN_REGALLOCBASE_H
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+#include "rcc/CodeGen/VirtRegMap.h"
+
+#include <vector>
+
+namespace rcc {
+
+struct AllocationRoundResult final {
+  std::vector<Register> Spilled;
+};
+
+class RegAllocBase {
+public:
+  virtual ~RegAllocBase() = default;
+
+  [[nodiscard]] Expected<regalloc_detail::AllocationRunResult> run();
+
+protected:
+  RegAllocBase(MachineFunction &Function, const TargetDescription &Target,
+               const TargetRegisterAllocationInfo &TargetInfo, MachineAnalysisManager &Analyses,
+               RegisterAllocationOptions Options) noexcept
+      : Function(Function), Target(Target), TargetInfo(TargetInfo), Analyses(Analyses),
+        Options(Options) {}
+
+  [[nodiscard]] virtual Expected<AllocationRoundResult>
+  allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) = 0;
+
+  MachineFunction &Function;
+  const TargetDescription &Target;
+  const TargetRegisterAllocationInfo &TargetInfo;
+  MachineAnalysisManager &Analyses;
+  RegisterAllocationOptions Options;
+};
+
+[[nodiscard]] std::vector<const LiveInterval *>
+orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals,
+                           const MachineFunction &Function);
+
+} // namespace rcc
+
+#endif // RCC_LIB_CODEGEN_REGALLOCBASE_H
diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp
new file mode 100644
index 0000000..4bb7b23
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocBasic.cpp
@@ -0,0 +1,136 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "RegAllocBasic.h"
+
+#include "RegAllocBase.h"
+#include "rcc/CodeGen/LiveRegMatrix.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+
+#include <algorithm>
+#include <memory>
+#include <ranges>
+
+namespace rcc {
+namespace {
+
+class BasicAllocatorEngine final : public RegAllocBase {
+public:
+  BasicAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
+                       const TargetRegisterAllocationInfo &TargetInfo,
+                       MachineAnalysisManager &Analyses, RegisterAllocationOptions Options)
+      : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {}
+
+private:
+  [[nodiscard]] Expected<AllocationRoundResult>
+  allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override {
+    LiveRegMatrix Matrix(Function, Target, Intervals);
+    AllocationRoundResult Result;
+    std::vector<const LiveInterval *> Worklist = orderedAllocationIntervals(Intervals, Function);
+    std::ranges::stable_sort(Worklist, [&](const LiveInterval *Left, const LiveInterval *Right) {
+      const bool LeftSpillable = Mapping.isSpillable(Left->Reg);
+      const bool RightSpillable = Mapping.isSpillable(Right->Reg);
+      if (LeftSpillable != RightSpillable)
+        return !LeftSpillable;
+      if (Left->SpillWeight != Right->SpillWeight)
+        return Left->SpillWeight > Right->SpillWeight;
+      return false;
+    });
+    for (const LiveInterval *Interval : Worklist) {
+      const Register VirtualReg = Interval->Reg;
+      if (regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg)) {
+        auto Marked = Mapping.setSpillable(VirtualReg, false);
+        if (!Marked)
+          return std::unexpected(Marked.error());
+      }
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg);
+      if (!Candidates)
+        return std::unexpected(Candidates.error());
+      bool Assigned = false;
+      for (const PhysicalRegister Candidate : *Candidates) {
+        if (Matrix.checkInterference(VirtualReg, Candidate).Kind != RegisterInterferenceKind::Free)
+          continue;
+        auto MatrixAssignment = Matrix.assign(VirtualReg, Candidate);
+        if (!MatrixAssignment)
+          continue;
+        auto MapAssignment = Mapping.assign(VirtualReg, Candidate);
+        if (!MapAssignment)
+          return std::unexpected(MapAssignment.error());
+        Assigned = true;
+        break;
+      }
+      if (!Assigned) {
+        if (!Mapping.isSpillable(VirtualReg)) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "BasicAllocator cannot assign a non-spillable virtual register");
+        }
+        Result.Spilled.push_back(VirtualReg);
+      }
+    }
+    return Result;
+  }
+};
+
+[[nodiscard]] const MachinePassContract &basicContract() {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "BasicAllocator",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten,
+                     MachineFunctionProperty::TracksLiveness},
+        .Sets = {MachineFunctionProperty::NoVRegs},
+        .Clears = {},
+        .RequiredAnalyses = {MachineAnalysisManager::id<LiveIntervalsAnalysis>()},
+        .VerificationStage = PipelineStage::RegisterAllocated,
+    };
+    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+    return Value;
+  }();
+  return Contract;
+}
+
+} // namespace
+
+const MachinePassContract &BasicAllocatorPass::contract() const noexcept {
+  return basicContract();
+}
+
+Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
+                                                    const TargetDescription &Target,
+                                                    MachineAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "BasicAllocator requires target behavior");
+  auto Required = regalloc_detail::requireAllocationProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+  auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
+  if (!Trial)
+    return std::unexpected(Trial.error());
+  MachineAnalysisManager TrialAnalyses;
+  auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
+  if (!Registered)
+    return std::unexpected(Registered.error());
+  BasicAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses,
+                                      Options);
+  auto TrialRun = TrialAllocator.run();
+  if (!TrialRun)
+    return std::unexpected(TrialRun.error());
+  auto TrialVerification =
+      regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
+  if (!TrialVerification)
+    return std::unexpected(TrialVerification.error());
+  BasicAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
+  auto Allocated = Allocator.run();
+  if (!Allocated) {
+    return std::unexpected(regalloc_detail::withPrefix(
+        Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: "));
+  }
+  return regalloc_detail::passResult(*Allocated);
+}
+
+std::unique_ptr<MachineFunctionPass>
+createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                         RegisterAllocationOptions Options) {
+  return std::make_unique<BasicAllocatorPass>(Info, Options);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegAllocBasic.h b/backend/lib/CodeGen/RegAllocBasic.h
new file mode 100644
index 0000000..8a68f5f
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocBasic.h
@@ -0,0 +1,31 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_LIB_CODEGEN_REGALLOCBASIC_H
+#define RCC_LIB_CODEGEN_REGALLOCBASIC_H
+
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+
+namespace rcc {
+
+class BasicAllocatorPass final : public MachineFunctionPass {
+public:
+  explicit BasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                              RegisterAllocationOptions Options = {}) noexcept
+      : Info(&Info), Options(Options) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  const TargetRegisterAllocationInfo *Info;
+  RegisterAllocationOptions Options;
+};
+
+} // namespace rcc
+
+#endif // RCC_LIB_CODEGEN_REGALLOCBASIC_H
diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp
new file mode 100644
index 0000000..9b087cc
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocFast.cpp
@@ -0,0 +1,608 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/RegAllocFast.h"
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/LiveRangeEdit.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/Spiller.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <map>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <unordered_map>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+class FastAllocatorEngine final {
+public:
+  FastAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
+                      const TargetRegisterAllocationInfo &TargetInfo,
+                      const LiveVariablesAnalysis::Result &Liveness)
+      : Function(Function), Target(Target), TargetInfo(TargetInfo), Liveness(Liveness),
+        Mapping(Function), Edit(Function, Target, Mapping) {}
+
+  [[nodiscard]] Expected<regalloc_detail::AllocationRunResult> run() {
+    const std::uint64_t InitialFingerprint = regalloc_detail::allocationFingerprint(Function);
+    const std::size_t InitialFrameObjects = Function.frameInfo().liveObjectCount();
+    auto Initialized = regalloc_detail::initializeMapping(Function, Mapping);
+    if (!Initialized)
+      return std::unexpected(Initialized.error());
+
+    bool IsEntry = true;
+    for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      auto Allocated = allocateBlock(*Block, IsEntry);
+      if (!Allocated)
+        return std::unexpected(Allocated.error());
+      IsEntry = false;
+    }
+
+    Function.registerInfo().clearLiveInVirtualRegisters();
+    for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size();
+         ++Index) {
+      auto Reg = regalloc_detail::virtualRegisterAt(Index);
+      if (!Reg)
+        return std::unexpected(Reg.error());
+      if (!Function.registerInfo().isKnownVirtualRegister(*Reg))
+        continue;
+      auto Erased = Function.registerInfo().eraseVirtualRegister(*Reg);
+      if (!Erased)
+        return std::unexpected(Erased.error());
+    }
+    auto Rebuilt = rebuildMachineLiveness(Function, Target);
+    if (!Rebuilt)
+      return std::unexpected(Rebuilt.error());
+
+    regalloc_detail::AllocationRunResult Result;
+    const std::uint64_t FinalFingerprint = regalloc_detail::allocationFingerprint(Function);
+    Result.Changed = InitialFingerprint != FinalFingerprint;
+    Result.ChangedInstructions = Result.Changed;
+    Result.ChangedFrame = InitialFrameObjects != Function.frameInfo().liveObjectCount();
+    return Result;
+  }
+
+private:
+  struct Location final {
+    PhysicalRegister PhysicalReg;
+    bool Dirty = false;
+  };
+
+  struct InstructionRegister final {
+    Register VirtualReg;
+    std::vector<std::size_t> Operands;
+    bool HasUse = false;
+    bool HasDef = false;
+    std::size_t FirstOperand = 0;
+  };
+
+  struct BlockLiveInState final {
+    PhysicalRegister Reg;
+    std::size_t RemainingUses = 0;
+  };
+
+  [[nodiscard]] bool liveOut(const MachineBasicBlock &Block, Register Reg) const noexcept {
+    return Liveness.isLiveOut(Block, Reg);
+  }
+
+  [[nodiscard]] bool neededLater(const MachineBasicBlock &Block, Register Reg) const noexcept {
+    const auto Position = RemainingUses.find(Reg);
+    return (Position != RemainingUses.end() && Position->second != 0) || liveOut(Block, Reg);
+  }
+
+  [[nodiscard]] std::optional<Register> ownerOf(PhysicalRegister Reg) const noexcept {
+    for (const auto &[VirtualReg, Value] : Locations) {
+      if (Target.registers().regsOverlap(Value.PhysicalReg, Reg))
+        return VirtualReg;
+    }
+    return std::nullopt;
+  }
+
+  [[nodiscard]] bool physicalLiveOut(const MachineBasicBlock &Block,
+                                     PhysicalRegister Reg) const noexcept {
+    const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg);
+    if (Description == nullptr)
+      return true;
+    return std::ranges::any_of(Description->Units, [&](const RegisterUnitLane &Unit) {
+      return Liveness.isUnitLiveOut(Block, Unit.Unit, Unit.Lanes);
+    });
+  }
+
+  [[nodiscard]] bool blockedByBlockLiveIn(PhysicalRegister Reg) const noexcept {
+    return std::ranges::any_of(BlockLiveIns, [&](const BlockLiveInState &LiveIn) {
+      return Target.registers().regsOverlap(LiveIn.Reg, Reg);
+    });
+  }
+
+  void initializeBlockLiveIns(const MachineBasicBlock &Block) {
+    BlockLiveIns.clear();
+    for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) {
+      if (LiveIn.Lanes.empty() ||
+          std::ranges::any_of(BlockLiveIns, [&](const BlockLiveInState &Existing) {
+            return Existing.Reg == LiveIn.PhysReg;
+          }))
+        continue;
+      BlockLiveIns.push_back({LiveIn.PhysReg, 0});
+    }
+
+    for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg == nullptr || !Reg->isPhysical() || !Operand.isUse())
+          continue;
+        const auto PhysicalValue = Reg->physicalRegister();
+        if (!PhysicalValue)
+          continue;
+        const PhysicalRegister Physical = PhysicalValue.value();
+        for (BlockLiveInState &LiveIn : BlockLiveIns) {
+          if (Target.registers().regsOverlap(LiveIn.Reg, Physical))
+            ++LiveIn.RemainingUses;
+        }
+      }
+    }
+  }
+
+  void updateBlockLiveIns(const MachineBasicBlock &Block, const MachineInstr &Instruction) {
+    std::vector<PhysicalRegister> Defined;
+    std::vector<const RegisterMask *> Masks;
+    for (const MachineOperand &Operand : Instruction.operands()) {
+      if (const Register *Reg = Operand.getIf<Register>(); Reg != nullptr && Reg->isPhysical()) {
+        const auto PhysicalValue = Reg->physicalRegister();
+        if (Operand.isDef() && PhysicalValue)
+          Defined.push_back(PhysicalValue.value());
+      }
+      if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); Mask != nullptr && Mask->Mask)
+        Masks.push_back(Mask->Mask.get());
+    }
+
+    for (auto Position = BlockLiveIns.begin(); Position != BlockLiveIns.end();) {
+      BlockLiveInState &LiveIn = *Position;
+      for (const MachineOperand &Operand : Instruction.operands()) {
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg == nullptr || !Reg->isPhysical() || !Operand.isUse())
+          continue;
+        const auto PhysicalValue = Reg->physicalRegister();
+        if (!PhysicalValue || !Target.registers().regsOverlap(LiveIn.Reg, PhysicalValue.value()))
+          continue;
+        if (LiveIn.RemainingUses != 0)
+          --LiveIn.RemainingUses;
+      }
+
+      const bool DefinedHere = std::ranges::any_of(Defined, [&](PhysicalRegister Reg) {
+        return Target.registers().regsOverlap(LiveIn.Reg, Reg);
+      });
+      const bool MaskClobbered = std::ranges::any_of(
+          Masks, [&](const RegisterMask *Mask) { return Mask->clobbers(LiveIn.Reg); });
+      const bool KeepForOutput = physicalLiveOut(Block, LiveIn.Reg);
+      if (!KeepForOutput && (DefinedHere || MaskClobbered || LiveIn.RemainingUses == 0))
+        Position = BlockLiveIns.erase(Position);
+      else
+        ++Position;
+    }
+  }
+
+  [[nodiscard]] bool overlapsAny(PhysicalRegister Candidate,
+                                 std::span<const PhysicalRegister> Values) const noexcept {
+    return std::ranges::any_of(Values, [&](PhysicalRegister Value) {
+      return Target.registers().regsOverlap(Candidate, Value);
+    });
+  }
+
+  [[nodiscard]] Expected<FrameIndex> spillSlot(Register Reg) {
+    auto ClassID = regalloc_detail::registerClassFor(Function, Reg);
+    if (!ClassID)
+      return std::unexpected(ClassID.error());
+    auto Validated = TargetInfo.validateSpillReload(*ClassID, Target);
+    if (!Validated) {
+      return makeUnexpected(
+          ErrorCode::InternalError,
+          "target declares an allocatable class without FastAllocator spill hooks");
+    }
+    return Edit.getOrCreateSpillSlot(Reg);
+  }
+
+  [[nodiscard]] Expected<void> emitSpillBefore(Register Reg, PhysicalRegister PhysicalReg,
+                                               MachineInstr *Before, MachineBasicBlock &Block) {
+    auto ClassID = regalloc_detail::registerClassFor(Function, Reg);
+    if (!ClassID)
+      return std::unexpected(ClassID.error());
+    auto Slot = spillSlot(Reg);
+    if (!Slot)
+      return std::unexpected(Slot.error());
+    MachineIRBuilder Builder(Function, Target);
+    Expected<void> Positioned =
+        Before != nullptr ? Builder.setInsertPointBefore(*Before) : Builder.setInsertPoint(Block);
+    if (!Positioned)
+      return std::unexpected(Positioned.error());
+    auto Spill = TargetInfo.emitSpill(Builder, Register::fromPhysical(PhysicalReg), *ClassID, *Slot,
+                                      LaneMask::all());
+    if (!Spill)
+      return std::unexpected(Spill.error());
+    VirtRegMapEntry *Entry = Mapping.entry(Reg);
+    if (Entry != nullptr)
+      ++Entry->Spill.SpillCount;
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> evict(Register Reg, MachineInstr &Before, MachineBasicBlock &Block,
+                                     bool Preserve) {
+    const auto Position = Locations.find(Reg);
+    if (Position == Locations.end())
+      return {};
+    if (Position->second.Dirty && Preserve) {
+      auto Stored = emitSpillBefore(Reg, Position->second.PhysicalReg, &Before, Block);
+      if (!Stored)
+        return std::unexpected(Stored.error());
+    }
+    Locations.erase(Position);
+    return {};
+  }
+
+  [[nodiscard]] Expected<PhysicalRegister>
+  ensureLocation(Register Reg, bool NeedsValue, MachineInstr &Instruction, MachineBasicBlock &Block,
+                 std::span<const PhysicalRegister> Fixed, std::span<const PhysicalRegister> Locked,
+                 const std::unordered_set<Register> &CurrentRegisters) {
+    const auto Existing = Locations.find(Reg);
+    if (Existing != Locations.end() && !overlapsAny(Existing->second.PhysicalReg, Fixed) &&
+        !overlapsAny(Existing->second.PhysicalReg, Locked))
+      return Existing->second.PhysicalReg;
+    if (Existing != Locations.end()) {
+      auto Evicted = evict(Reg, Instruction, Block, NeedsValue || neededLater(Block, Reg));
+      if (!Evicted)
+        return std::unexpected(Evicted.error());
+    }
+
+    auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg);
+    if (!Candidates)
+      return std::unexpected(Candidates.error());
+    for (const PhysicalRegister Candidate : *Candidates) {
+      if (overlapsAny(Candidate, Fixed) || overlapsAny(Candidate, Locked))
+        continue;
+      if (blockedByBlockLiveIn(Candidate))
+        continue;
+      if (const auto Owner = ownerOf(Candidate)) {
+        if (CurrentRegisters.contains(*Owner))
+          continue;
+        auto Evicted = evict(*Owner, Instruction, Block, neededLater(Block, *Owner));
+        if (!Evicted)
+          return std::unexpected(Evicted.error());
+      }
+      if (ownerOf(Candidate))
+        continue;
+
+      if (NeedsValue) {
+        auto ClassID = regalloc_detail::registerClassFor(Function, Reg);
+        if (!ClassID)
+          return std::unexpected(ClassID.error());
+        auto Slot = spillSlot(Reg);
+        if (!Slot)
+          return std::unexpected(Slot.error());
+        MachineIRBuilder Builder(Function, Target);
+        auto Positioned = Builder.setInsertPointBefore(Instruction);
+        if (!Positioned)
+          return std::unexpected(Positioned.error());
+        auto Reload = TargetInfo.emitReload(Builder, Register::fromPhysical(Candidate), *ClassID,
+                                            *Slot, LaneMask::all());
+        if (!Reload)
+          return std::unexpected(Reload.error());
+        VirtRegMapEntry *Entry = Mapping.entry(Reg);
+        if (Entry != nullptr)
+          ++Entry->Spill.ReloadCount;
+      }
+      Locations.emplace(Reg, Location{Candidate, false});
+      return Candidate;
+    }
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "FastAllocator cannot satisfy simultaneous register constraints");
+  }
+
+  [[nodiscard]] Expected<void> installEntryLiveIns(MachineBasicBlock &Block) {
+    if (&Block != Function.firstBlock())
+      return {};
+    for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) {
+      if (!LiveIn.InitialVirtualRegister)
+        continue;
+      const Register Reg = *LiveIn.InitialVirtualRegister;
+      if (!Function.registerInfo().isKnownVirtualRegister(Reg))
+        continue;
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg);
+      if (!Candidates)
+        return std::unexpected(Candidates.error());
+      if (std::ranges::find(*Candidates, LiveIn.PhysReg) == Candidates->end()) {
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "function live-in is outside its allocation order");
+      }
+      if (ownerOf(LiveIn.PhysReg)) {
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "overlapping function live-ins require the same physical register");
+      }
+      Locations.emplace(Reg, Location{LiveIn.PhysReg, true});
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> allocateInstruction(MachineInstr &Instruction,
+                                                   MachineBasicBlock &Block) {
+    std::vector<PhysicalRegister> Fixed;
+    std::vector<const RegisterMask *> Masks;
+    std::map<std::uint32_t, InstructionRegister> Registers;
+    std::vector<std::size_t> DebugOperands;
+    for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) {
+      MachineOperand *Operand = Instruction.operandAt(Index);
+      if (const auto *Mask = Operand->getIf<RegisterMaskOperand>(); Mask != nullptr && Mask->Mask)
+        Masks.push_back(Mask->Mask.get());
+      const Register *Reg = Operand->getIf<Register>();
+      if (Reg == nullptr || Reg->isNoRegister())
+        continue;
+      if (Reg->isPhysical()) {
+        const auto PhysicalValue = Reg->physicalRegister();
+        if (!PhysicalValue) {
+          return makeUnexpected(ErrorCode::InternalError,
+                                "physical register operand lacks a physical register value");
+        }
+        Fixed.push_back(PhysicalValue.value());
+        continue;
+      }
+      if (Operand->isDebugUse()) {
+        DebugOperands.push_back(Index);
+        continue;
+      }
+      auto [Position, Inserted] = Registers.try_emplace(
+          Reg->opaqueValue(), InstructionRegister{*Reg, {}, false, false, Index});
+      if (!Inserted)
+        Position->second.FirstOperand = std::min(Position->second.FirstOperand, Index);
+      Position->second.Operands.push_back(Index);
+      Position->second.HasUse |= Operand->isUse();
+      Position->second.HasDef |= Operand->isDef();
+    }
+    std::ranges::sort(Fixed, {}, &PhysicalRegister::number);
+    Fixed.erase(std::unique(Fixed.begin(), Fixed.end()), Fixed.end());
+
+    std::unordered_set<Register> CurrentRegisters;
+    std::unordered_set<Register> DefinedRegisters;
+    for (const auto &[Key, Value] : Registers) {
+      (void)Key;
+      CurrentRegisters.insert(Value.VirtualReg);
+      if (Value.HasDef)
+        DefinedRegisters.insert(Value.VirtualReg);
+    }
+    for (const auto &[Reg, Value] :
+         std::vector<std::pair<Register, Location>>(Locations.begin(), Locations.end())) {
+      bool Clobbered = false;
+      for (const RegisterMask *Mask : Masks)
+        Clobbered |= Mask->clobbers(Value.PhysicalReg);
+      if (Clobbered) {
+        auto Evicted = evict(Reg, Instruction, Block, neededLater(Block, Reg));
+        if (!Evicted)
+          return std::unexpected(Evicted.error());
+      }
+    }
+
+    std::vector<InstructionRegister *> Ordered;
+    Ordered.reserve(Registers.size());
+    for (auto &[Key, Value] : Registers) {
+      (void)Key;
+      Ordered.push_back(&Value);
+    }
+    std::ranges::sort(Ordered,
+                      [](const InstructionRegister *Left, const InstructionRegister *Right) {
+                        if (Left->HasUse != Right->HasUse)
+                          return Left->HasUse > Right->HasUse;
+                        return Left->FirstOperand < Right->FirstOperand;
+                      });
+
+    std::vector<PhysicalRegister> Locked;
+    for (InstructionRegister *Value : Ordered) {
+      auto Physical = ensureLocation(Value->VirtualReg, Value->HasUse, Instruction, Block, Fixed,
+                                     Locked, CurrentRegisters);
+      if (!Physical)
+        return std::unexpected(Physical.error());
+      Locked.push_back(*Physical);
+      for (const std::size_t Index : Value->Operands) {
+        MachineOperand *Operand = Instruction.operandAt(Index);
+        PhysicalRegister Effective = *Physical;
+        if (Operand->subReg().value() != 0) {
+          const auto Sub = Target.registers().subRegister(*Physical, Operand->subReg());
+          if (!Sub)
+            return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                  "FastAllocator assignment lacks a required subregister");
+          Effective = *Sub;
+        }
+        auto Set = Operand->setRegister(Register::fromPhysical(Effective));
+        if (!Set)
+          return std::unexpected(Set.error());
+        if (Operand->subReg().value() != 0) {
+          auto Cleared = Operand->setSubReg(SubRegIndex{});
+          if (!Cleared)
+            return std::unexpected(Cleared.error());
+        }
+      }
+      if (Value->HasDef)
+        Locations[Value->VirtualReg].Dirty = true;
+    }
+
+    for (const std::size_t Index : DebugOperands) {
+      MachineOperand *Operand = Instruction.operandAt(Index);
+      const Register *Reg = Operand->getIf<Register>();
+      const auto Position = Reg == nullptr ? Locations.end() : Locations.find(*Reg);
+      Register Replacement;
+      if (Position != Locations.end())
+        Replacement = Register::fromPhysical(Position->second.PhysicalReg);
+      auto Set = Operand->setRegister(Replacement);
+      if (!Set)
+        return std::unexpected(Set.error());
+      if (Operand->subReg().value() != 0) {
+        auto Cleared = Operand->setSubReg(SubRegIndex{});
+        if (!Cleared)
+          return std::unexpected(Cleared.error());
+      }
+      if (Replacement.isNoRegister()) {
+        RegisterOperandFlags Flags = Operand->registerFlags();
+        Flags.set(RegisterOperandFlag::Undef);
+        auto Updated = Operand->setRegisterFlags(Flags);
+        if (!Updated)
+          return std::unexpected(Updated.error());
+      }
+    }
+
+    for (InstructionRegister *Value : Ordered) {
+      if (Value->HasUse) {
+        auto Position = RemainingUses.find(Value->VirtualReg);
+        if (Position != RemainingUses.end() && Position->second != 0)
+          --Position->second;
+      }
+      if (!neededLater(Block, Value->VirtualReg))
+        Locations.erase(Value->VirtualReg);
+    }
+    for (const RegisterMask *Mask : Masks) {
+      for (auto Position = Locations.begin(); Position != Locations.end();) {
+        if (Mask->clobbers(Position->second.PhysicalReg) &&
+            !DefinedRegisters.contains(Position->first))
+          Position = Locations.erase(Position);
+        else
+          ++Position;
+      }
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> flushLiveOuts(MachineBasicBlock &Block) {
+    MachineInstr *Terminator = regalloc_detail::firstTerminator(Block, Target);
+    for (const auto &[Reg, Value] :
+         std::vector<std::pair<Register, Location>>(Locations.begin(), Locations.end())) {
+      if (!Value.Dirty || !liveOut(Block, Reg))
+        continue;
+      if (Terminator != nullptr) {
+        for (const MachineOperand &Operand : Terminator->operands()) {
+          const Register *OperandReg = Operand.getIf<Register>();
+          if (OperandReg != nullptr && *OperandReg == Reg && Operand.isDef()) {
+            return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                  "FastAllocator cannot spill a terminator-defined live-out");
+          }
+        }
+      }
+      auto Stored = emitSpillBefore(Reg, Value.PhysicalReg, Terminator, Block);
+      if (!Stored)
+        return std::unexpected(Stored.error());
+    }
+    Locations.clear();
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> allocateBlock(MachineBasicBlock &Block, bool IsEntry) {
+    (void)IsEntry;
+    Locations.clear();
+    RemainingUses.clear();
+    initializeBlockLiveIns(Block);
+    std::vector<MachineInstr *> Instructions;
+    for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      Instructions.push_back(Instruction);
+      std::unordered_set<Register> UsesInInstruction;
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg != nullptr && Reg->isVirtual() && Operand.isUse() && !Operand.isDebugUse())
+          UsesInInstruction.insert(*Reg);
+      }
+      for (const Register Reg : UsesInInstruction)
+        ++RemainingUses[Reg];
+    }
+    auto EntryValues = installEntryLiveIns(Block);
+    if (!EntryValues)
+      return std::unexpected(EntryValues.error());
+    for (MachineInstr *Instruction : Instructions) {
+      auto Allocated = allocateInstruction(*Instruction, Block);
+      if (!Allocated)
+        return std::unexpected(Allocated.error());
+      updateBlockLiveIns(Block, *Instruction);
+    }
+    auto Flushed = flushLiveOuts(Block);
+    BlockLiveIns.clear();
+    return Flushed;
+  }
+
+  MachineFunction &Function;
+  const TargetDescription &Target;
+  const TargetRegisterAllocationInfo &TargetInfo;
+  const LiveVariablesAnalysis::Result &Liveness;
+  VirtRegMap Mapping;
+  LiveRangeEdit Edit;
+  std::unordered_map<Register, Location> Locations;
+  std::unordered_map<Register, std::size_t> RemainingUses;
+  std::vector<BlockLiveInState> BlockLiveIns;
+};
+
+} // namespace
+
+const MachinePassContract &FastAllocatorPass::contract() const noexcept {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "FastAllocator",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten,
+                     MachineFunctionProperty::TracksLiveness},
+        .Sets = {MachineFunctionProperty::NoVRegs},
+        .Clears = {},
+        .RequiredAnalyses = {MachineAnalysisManager::id<LiveVariablesAnalysis>()},
+        .VerificationStage = PipelineStage::RegisterAllocated,
+    };
+    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+    return Value;
+  }();
+  return Contract;
+}
+
+Expected<MachinePassResult> FastAllocatorPass::run(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachineAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "FastAllocator requires target behavior");
+  auto Required = regalloc_detail::requireAllocationProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+  auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
+  if (!Trial)
+    return std::unexpected(Trial.error());
+  MachineAnalysisManager TrialAnalyses;
+  auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
+  if (!Registered)
+    return std::unexpected(Registered.error());
+  auto TrialLiveness =
+      TrialAnalyses.getResult<LiveVariablesAnalysis>(*Trial->ClonedFunction, Target);
+  if (!TrialLiveness)
+    return std::unexpected(TrialLiveness.error());
+  FastAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, **TrialLiveness);
+  auto TrialRun = TrialAllocator.run();
+  if (!TrialRun)
+    return std::unexpected(TrialRun.error());
+  auto TrialVerification =
+      regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
+  if (!TrialVerification)
+    return std::unexpected(TrialVerification.error());
+  auto Liveness = Analyses.getResult<LiveVariablesAnalysis>(Function, Target);
+  if (!Liveness)
+    return std::unexpected(Liveness.error());
+  FastAllocatorEngine Allocator(Function, Target, *Info, **Liveness);
+  auto Allocated = Allocator.run();
+  if (!Allocated) {
+    return std::unexpected(regalloc_detail::withPrefix(
+        Allocated.error(), "FastAllocator diverged after a successful transaction preflight: "));
+  }
+  return regalloc_detail::passResult(*Allocated);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h
new file mode 100644
index 0000000..5d0f434
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocInternal.h
@@ -0,0 +1,236 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_LIB_CODEGEN_REGALLOCINTERNAL_H
+#define RCC_LIB_CODEGEN_REGALLOCINTERNAL_H
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+#include "rcc/CodeGen/VirtRegMap.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::regalloc_detail {
+
+struct AllocationRunResult final {
+  bool Changed = false;
+  bool ChangedInstructions = false;
+  bool ChangedFrame = false;
+};
+
+[[nodiscard]] inline Error withPrefix(const Error &Failure, std::string_view Prefix) {
+  std::string Message(Prefix);
+  Message.append(Failure.message());
+  return Error(Failure.code(), std::move(Message));
+}
+
+[[nodiscard]] inline Expected<Register> virtualRegisterAt(std::size_t Index) {
+  auto Reg = Register::makeVirtual(Index);
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  return *Reg;
+}
+
+[[nodiscard]] inline Expected<RegisterClassID> registerClassFor(const MachineFunction &Function,
+                                                                Register VirtualReg) {
+  auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  const auto ClassID = Info->get().RegClass;
+  if (!ClassID) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "virtual register has no register class after instruction selection");
+  }
+  return ClassID.value();
+}
+
+[[nodiscard]] inline bool isUnavailablePhysicalRegister(const MachineFunction &Function,
+                                                        const TargetRegisterInfo &Registers,
+                                                        PhysicalRegister Reg) noexcept {
+  const PhysicalRegisterDesc *Description = Registers.physicalRegister(Reg);
+  return Description == nullptr || Description->IsConstant || Description->IsArtificial ||
+         Description->IsReserved || Registers.isReservedRegister(Reg) ||
+         Function.registerInfo().isReserved(Reg);
+}
+
+[[nodiscard]] inline bool candidateSupportsSubRegisters(const MachineFunction &Function,
+                                                        const TargetRegisterInfo &Registers,
+                                                        Register VirtualReg,
+                                                        PhysicalRegister Candidate) noexcept {
+  for (const MachineOperand &Operand :
+       const_cast<MachineRegisterInfo &>(Function.registerInfo()).regOperands(VirtualReg)) {
+    if (Operand.subReg().value() != 0 && !Registers.subRegister(Candidate, Operand.subReg()))
+      return false;
+  }
+  return true;
+}
+
+[[nodiscard]] inline Expected<std::vector<PhysicalRegister>>
+allocationOrder(const MachineFunction &Function, const TargetDescription &Target,
+                Register VirtualReg) {
+  auto ClassID = registerClassFor(Function, VirtualReg);
+  if (!ClassID)
+    return std::unexpected(ClassID.error());
+  const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID);
+  if (Class == nullptr || !Class->Allocatable || Class->AllocationOrder.empty()) {
+    return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                          "virtual register class has no allocatable physical registers");
+  }
+
+  auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  std::vector<PhysicalRegister> Result;
+  Result.reserve(Class->AllocationOrder.size());
+  for (const PhysicalRegister Hint : Info->get().AllocationHints) {
+    if (std::ranges::find(Class->AllocationOrder, Hint) != Class->AllocationOrder.end() &&
+        std::ranges::find(Result, Hint) == Result.end())
+      Result.push_back(Hint);
+  }
+  for (const PhysicalRegister Candidate : Class->AllocationOrder) {
+    if (std::ranges::find(Result, Candidate) == Result.end())
+      Result.push_back(Candidate);
+  }
+  std::erase_if(Result, [&](PhysicalRegister Candidate) {
+    return isUnavailablePhysicalRegister(Function, Target.registers(), Candidate) ||
+           !candidateSupportsSubRegisters(Function, Target.registers(), VirtualReg, Candidate);
+  });
+  return Result;
+}
+
+[[nodiscard]] inline MachineInstr *firstTerminator(MachineBasicBlock &Block,
+                                                   const TargetDescription &Target) noexcept {
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+      return Instruction;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] inline bool hasTerminatorDefinition(const MachineFunction &Function,
+                                                  const TargetDescription &Target,
+                                                  Register VirtualReg) noexcept {
+  for (const MachineOperand &Operand :
+       const_cast<MachineRegisterInfo &>(Function.registerInfo()).defOperands(VirtualReg)) {
+    const MachineInstr *Instruction = Operand.parent();
+    const InstructionDescriptor *Descriptor =
+        Instruction == nullptr ? nullptr : Target.instructionDescriptor(Instruction->opcode());
+    if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator))
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] inline std::uint64_t allocationFingerprint(const MachineFunction &Function) noexcept {
+  std::uint64_t Hash = 1469598103934665603ULL;
+  auto Mix = [&Hash](std::uint64_t Value) {
+    Hash ^= Value;
+    Hash *= 1099511628211ULL;
+  };
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    Mix(Block->stableID().value());
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      Mix(Instruction->opcode().value());
+      Mix(Instruction->stableID().value());
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        Mix(static_cast<std::uint64_t>(Operand.kind()));
+        if (const Register *Reg = Operand.getIf<Register>())
+          Mix(Reg->opaqueValue());
+      }
+    }
+  }
+  return Hash;
+}
+
+[[nodiscard]] inline Expected<void> initializeMapping(MachineFunction &Function,
+                                                      VirtRegMap &Mapping) {
+  for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) {
+    auto Reg = virtualRegisterAt(Index);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    if (!Function.registerInfo().isKnownVirtualRegister(*Reg))
+      continue;
+    auto Added = Mapping.add(*Reg);
+    if (!Added)
+      return std::unexpected(Added.error());
+  }
+  return {};
+}
+
+[[nodiscard]] inline MachinePassResult passResult(const AllocationRunResult &Run) {
+  MachinePassResult Result;
+  Result.Changed = Run.Changed;
+  if (Run.Changed) {
+    Result.Changes.add(MachinePassChange::Registers);
+    Result.Changes.add(MachinePassChange::Operands);
+  }
+  if (Run.ChangedInstructions)
+    Result.Changes.add(MachinePassChange::Instructions);
+  if (Run.ChangedFrame)
+    Result.Changes.add(MachinePassChange::Frame);
+  Result.Preserved = PreservedAnalyses::none();
+  return Result;
+}
+
+[[nodiscard]] inline Expected<void>
+requireAllocationProperties(const MachineFunction &Function, const MachinePassContract &Contract) {
+  const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          Contract.Name + " requires properties: " + Missing.toString());
+  }
+  return {};
+}
+
+[[nodiscard]] inline Expected<void> verifyAllocationTrial(MachineFunction &Function,
+                                                          const TargetDescription &Target,
+                                                          const MachinePassContract &Contract) {
+  auto Transition =
+      Function.properties().applyTransition(Contract.Requires, Contract.Sets, Contract.Clears);
+  if (!Transition)
+    return std::unexpected(Transition.error());
+  return MachineVerifier::verify(Function, Target,
+                                 MachineVerifierOptions{.Mode = MachineVerifierMode::Generic,
+                                                        .Stage = Contract.VerificationStage,
+                                                        .VerifyProperties = true});
+}
+
+[[nodiscard]] inline Expected<MachineFunctionCloneResult>
+cloneForAllocation(const MachineFunction &Function, const TargetDescription &Target) {
+  return cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+}
+
+[[nodiscard]] bool
+intervalsOverlapOnPhysicalRegisters(const LiveInterval &Left, PhysicalRegister LeftReg,
+                                    const LiveInterval &Right, PhysicalRegister RightReg,
+                                    const TargetRegisterInfo &Registers) noexcept;
+
+} // namespace rcc::regalloc_detail
+
+#endif // RCC_LIB_CODEGEN_REGALLOCINTERNAL_H
diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp
new file mode 100644
index 0000000..5e56728
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocPBQP.cpp
@@ -0,0 +1,281 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/RegAllocPBQP.h"
+
+#include "RegAllocBase.h"
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/LiveRegMatrix.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/PBQP/Solver.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+struct PBQPAllocationNode final {
+  Register VirtualReg;
+  pbqp::NodeID Node;
+  std::vector<std::optional<PhysicalRegister>> Options;
+};
+
+[[nodiscard]] std::set<std::pair<std::uint32_t, std::uint32_t>>
+copyRelatedRegisters(const MachineFunction &Function) {
+  std::set<std::pair<std::uint32_t, std::uint32_t>> Result;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (Instruction->opcode() != opcode(GenericOpcode::COPY) || Instruction->operandCount() < 2)
+        continue;
+      const Register *Destination = Instruction->operands()[0].getIf<Register>();
+      const Register *Source = Instruction->operands()[1].getIf<Register>();
+      if (Destination == nullptr || Source == nullptr || !Destination->isVirtual() ||
+          !Source->isVirtual() || *Destination == *Source)
+        continue;
+      std::uint32_t Left = Destination->opaqueValue();
+      std::uint32_t Right = Source->opaqueValue();
+      if (Right < Left)
+        std::swap(Left, Right);
+      Result.emplace(Left, Right);
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] pbqp::Cost boundedCost(std::uint64_t Value) noexcept {
+  const std::uint64_t Limit = static_cast<std::uint64_t>(pbqp::InfiniteCost - 1);
+  return static_cast<pbqp::Cost>(std::min(Value, Limit));
+}
+
+class PBQPAllocatorEngine final : public RegAllocBase {
+public:
+  PBQPAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
+                      const TargetRegisterAllocationInfo &TargetInfo,
+                      MachineAnalysisManager &Analyses, RegisterAllocationOptions Options)
+      : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {}
+
+private:
+  [[nodiscard]] Expected<AllocationRoundResult>
+  allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override {
+    LiveRegMatrix FixedMatrix(Function, Target, Intervals);
+    pbqp::Graph Problem;
+    std::vector<PBQPAllocationNode> Nodes;
+    for (const LiveInterval *Interval : orderedAllocationIntervals(Intervals, Function)) {
+      const Register VirtualReg = Interval->Reg;
+      const bool TerminatorDefined =
+          regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg);
+      if (TerminatorDefined) {
+        auto Marked = Mapping.setSpillable(VirtualReg, false);
+        if (!Marked)
+          return std::unexpected(Marked.error());
+      }
+      auto ClassID = regalloc_detail::registerClassFor(Function, VirtualReg);
+      if (!ClassID)
+        return std::unexpected(ClassID.error());
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg);
+      if (!Candidates)
+        return std::unexpected(Candidates.error());
+      std::erase_if(*Candidates, [&](PhysicalRegister Candidate) {
+        return FixedMatrix.checkInterference(VirtualReg, Candidate).Kind !=
+               RegisterInterferenceKind::Free;
+      });
+
+      std::vector<std::optional<PhysicalRegister>> NodeOptions;
+      NodeOptions.reserve(Candidates->size() + 1U);
+      NodeOptions.push_back(std::nullopt);
+      for (const PhysicalRegister Candidate : *Candidates)
+        NodeOptions.push_back(Candidate);
+      pbqp::CostVector Costs(NodeOptions.size(), 0);
+      if (!Mapping.isSpillable(VirtualReg)) {
+        Costs[0] = pbqp::InfiniteCost;
+      } else {
+        const std::uint64_t TargetSpillCost = TargetInfo.spillCost(Function, *Interval, *ClassID);
+        const std::uint64_t Weight = std::max<std::uint64_t>(1, Interval->SpillWeight);
+        const std::uint64_t Scaled =
+            TargetSpillCost > std::numeric_limits<std::uint64_t>::max() / Weight
+                ? std::numeric_limits<std::uint64_t>::max()
+                : TargetSpillCost * Weight;
+        const std::uint64_t Adjusted =
+            Scaled == std::numeric_limits<std::uint64_t>::max() ? Scaled : Scaled + 1U;
+        Costs[0] = boundedCost(Adjusted);
+      }
+      auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg);
+      if (!Info)
+        return std::unexpected(Info.error());
+      for (std::size_t Index = 1; Index < NodeOptions.size(); ++Index) {
+        const auto CandidateOption = NodeOptions[Index];
+        if (!CandidateOption) {
+          return makeUnexpected(ErrorCode::InternalError,
+                                "PBQP allocation node has an unexpected spill option");
+        }
+        const PhysicalRegister Candidate = CandidateOption.value();
+        std::uint64_t Cost =
+            TargetInfo.physicalRegisterCost(Function, VirtualReg, Candidate, *ClassID, true);
+        const auto Hint = std::ranges::find(Info->get().AllocationHints, Candidate);
+        const std::uint64_t HintCost =
+            Hint == Info->get().AllocationHints.end()
+                ? 2U
+                : static_cast<std::uint64_t>(Hint - Info->get().AllocationHints.begin());
+        Cost = Cost > std::numeric_limits<std::uint64_t>::max() - HintCost
+                   ? std::numeric_limits<std::uint64_t>::max()
+                   : Cost + HintCost;
+        Costs[Index] = boundedCost(Cost);
+      }
+      auto NodeID = Problem.addNode(std::move(Costs), VirtualReg.opaqueValue());
+      if (!NodeID)
+        return std::unexpected(NodeID.error());
+      Nodes.push_back(PBQPAllocationNode{VirtualReg, *NodeID, std::move(NodeOptions)});
+    }
+
+    const auto CopyPairs = copyRelatedRegisters(Function);
+    for (std::size_t LeftIndex = 0; LeftIndex < Nodes.size(); ++LeftIndex) {
+      const PBQPAllocationNode &Left = Nodes[LeftIndex];
+      const LiveInterval *LeftInterval = Intervals.interval(Left.VirtualReg);
+      for (std::size_t RightIndex = LeftIndex + 1U; RightIndex < Nodes.size(); ++RightIndex) {
+        const PBQPAllocationNode &Right = Nodes[RightIndex];
+        const LiveInterval *RightInterval = Intervals.interval(Right.VirtualReg);
+        if (LeftInterval == nullptr || RightInterval == nullptr)
+          continue;
+        std::uint32_t LeftKey = Left.VirtualReg.opaqueValue();
+        std::uint32_t RightKey = Right.VirtualReg.opaqueValue();
+        if (RightKey < LeftKey)
+          std::swap(LeftKey, RightKey);
+        const bool CopyRelated =
+            Options.EnableCopyCoalescing && CopyPairs.contains({LeftKey, RightKey});
+        pbqp::CostMatrix Costs(Left.Options.size(), Right.Options.size(), 0);
+        bool HasCost = false;
+        for (std::size_t LeftOption = 1; LeftOption < Left.Options.size(); ++LeftOption) {
+          for (std::size_t RightOption = 1; RightOption < Right.Options.size(); ++RightOption) {
+            const auto LeftRegister = Left.Options[LeftOption];
+            const auto RightRegister = Right.Options[RightOption];
+            if (!LeftRegister || !RightRegister) {
+              return makeUnexpected(ErrorCode::InternalError,
+                                    "PBQP edge has an unexpected spill option");
+            }
+            const PhysicalRegister LeftReg = LeftRegister.value();
+            const PhysicalRegister RightReg = RightRegister.value();
+            if (regalloc_detail::intervalsOverlapOnPhysicalRegisters(
+                    *LeftInterval, LeftReg, *RightInterval, RightReg, Target.registers())) {
+              Costs.at(LeftOption, RightOption) = pbqp::InfiniteCost;
+              HasCost = true;
+            } else if (CopyRelated && LeftReg == RightReg) {
+              Costs.at(LeftOption, RightOption) = -1;
+              HasCost = true;
+            }
+          }
+        }
+        if (!HasCost)
+          continue;
+        const std::uint64_t StableKey =
+            (static_cast<std::uint64_t>(Left.VirtualReg.opaqueValue()) << 32U) |
+            Right.VirtualReg.opaqueValue();
+        auto Edge = Problem.addEdge(Left.Node, Right.Node, std::move(Costs), StableKey);
+        if (!Edge)
+          return std::unexpected(Edge.error());
+      }
+    }
+
+    pbqp::DeterministicSolver Solver;
+    auto Solution = Solver.solve(Problem);
+    if (!Solution)
+      return std::unexpected(Solution.error());
+
+    LiveRegMatrix AssignedMatrix(Function, Target, Intervals);
+    AllocationRoundResult Result;
+    for (const PBQPAllocationNode &Node : Nodes) {
+      const auto Selection = Solution->selection(Node.Node);
+      if (!Selection)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP solver returned an invalid selection");
+      const std::size_t SelectedOption = Selection.value();
+      if (SelectedOption >= Node.Options.size()) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP solver selected an out-of-range option");
+      }
+      const auto AssignedOption = Node.Options[SelectedOption];
+      if (!AssignedOption) {
+        Result.Spilled.push_back(Node.VirtualReg);
+        continue;
+      }
+      const PhysicalRegister Assigned = AssignedOption.value();
+      auto MatrixAssignment = AssignedMatrix.assign(Node.VirtualReg, Assigned);
+      if (!MatrixAssignment)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP solution violates its encoded interference constraints");
+      auto MapAssignment = Mapping.assign(Node.VirtualReg, Assigned);
+      if (!MapAssignment)
+        return std::unexpected(MapAssignment.error());
+    }
+    return Result;
+  }
+};
+
+[[nodiscard]] const MachinePassContract &pbqpContract() {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "PBQPAllocator",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten,
+                     MachineFunctionProperty::TracksLiveness},
+        .Sets = {MachineFunctionProperty::NoVRegs},
+        .Clears = {},
+        .RequiredAnalyses = {MachineAnalysisManager::id<LiveIntervalsAnalysis>()},
+        .VerificationStage = PipelineStage::RegisterAllocated,
+    };
+    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+    return Value;
+  }();
+  return Contract;
+}
+
+} // namespace
+
+const MachinePassContract &PBQPAllocatorPass::contract() const noexcept {
+  return pbqpContract();
+}
+
+Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachineAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "PBQPAllocator requires target behavior");
+  auto Required = regalloc_detail::requireAllocationProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+  auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
+  if (!Trial)
+    return std::unexpected(Trial.error());
+  MachineAnalysisManager TrialAnalyses;
+  auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
+  if (!Registered)
+    return std::unexpected(Registered.error());
+  PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options);
+  auto TrialRun = TrialAllocator.run();
+  if (!TrialRun)
+    return std::unexpected(TrialRun.error());
+  auto TrialVerification =
+      regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
+  if (!TrialVerification)
+    return std::unexpected(TrialVerification.error());
+  PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
+  auto Allocated = Allocator.run();
+  if (!Allocated) {
+    return std::unexpected(regalloc_detail::withPrefix(
+        Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: "));
+  }
+  return regalloc_detail::passResult(*Allocated);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/TargetMIRTextInfo.cpp b/backend/lib/CodeGen/TargetMIRTextInfo.cpp
index 65e3c65..5d54ea6 100644
--- a/backend/lib/CodeGen/TargetMIRTextInfo.cpp
+++ b/backend/lib/CodeGen/TargetMIRTextInfo.cpp
@@ -509,8 +509,7 @@ TargetMIRTextInfo::printFunctionState(const TargetFunctionState &State) const {
   return Node;
 }
 
-Expected<TargetConstant>
-TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const {
+Expected<TargetConstant> TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const {
   if (Description.ParseTargetConstant == nullptr) {
     return makeUnexpected(ErrorCode::Unsupported,
                           "target does not define a target constant MIR schema");
@@ -524,8 +523,7 @@ TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const {
   return Constant;
 }
 
-Expected<std::string>
-TargetMIRTextInfo::printTargetConstant(const TargetConstant &Constant) const {
+Expected<std::string> TargetMIRTextInfo::printTargetConstant(const TargetConstant &Constant) const {
   if (Description.PrintTargetConstant == nullptr) {
     return makeUnexpected(ErrorCode::Unsupported,
                           "target does not define a target constant MIR schema");
diff --git a/backend/lib/CodeGen/VirtRegMap.cpp b/backend/lib/CodeGen/VirtRegMap.cpp
new file mode 100644
index 0000000..624a931
--- /dev/null
+++ b/backend/lib/CodeGen/VirtRegMap.cpp
@@ -0,0 +1,301 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/VirtRegMap.h"
+
+#include "RegAllocInternal.h"
+#include "rcc/CodeGen/LiveRegMatrix.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <optional>
+#include <ranges>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+Expected<void> VirtRegMap::add(Register VirtualReg, bool Spillable,
+                               std::optional<Register> SplitParent,
+                               std::optional<Register> Origin) {
+  if (!VirtualReg.isVirtual() || !Function->registerInfo().isKnownVirtualRegister(VirtualReg))
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "VirtRegMap requires a known virtual register");
+  if (SplitParent && !SplitParent->isVirtual())
+    return makeUnexpected(ErrorCode::InvalidArgument, "split parent must be a virtual register");
+  if (Origin && !Origin->isVirtual())
+    return makeUnexpected(ErrorCode::InvalidArgument, "split origin must be a virtual register");
+  auto [Position, Inserted] =
+      Entries.try_emplace(VirtualReg, VirtRegMapEntry{VirtualReg,
+                                                      VirtRegAllocationState::Unassigned,
+                                                      std::nullopt,
+                                                      SplitParent,
+                                                      Origin,
+                                                      Spillable,
+                                                      {}});
+  if (!Inserted) {
+    Position->second.Spillable = Spillable;
+    if (SplitParent)
+      Position->second.SplitParent = SplitParent;
+    if (Origin)
+      Position->second.Origin = Origin;
+  }
+  return {};
+}
+
+Expected<void> VirtRegMap::assign(Register VirtualReg, PhysicalRegister PhysicalReg) {
+  VirtRegMapEntry *Value = entry(VirtualReg);
+  if (Value == nullptr || !PhysicalReg.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap assignment is invalid");
+  Value->PhysicalReg = PhysicalReg;
+  Value->State = VirtRegAllocationState::Assigned;
+  return {};
+}
+
+Expected<void> VirtRegMap::assignStackSlot(Register VirtualReg, FrameIndex StackSlot,
+                                           LaneMask Lanes) {
+  VirtRegMapEntry *Value = entry(VirtualReg);
+  if (Value == nullptr || Function->frameInfo().object(StackSlot) == nullptr || Lanes.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap spill assignment is invalid");
+  Value->PhysicalReg.reset();
+  Value->State = VirtRegAllocationState::Spilled;
+  Value->Spill.StackSlot = StackSlot;
+  Value->Spill.Lanes = Lanes;
+  return {};
+}
+
+Expected<void> VirtRegMap::markSplit(Register VirtualReg, Register Parent, Register Origin) {
+  VirtRegMapEntry *Value = entry(VirtualReg);
+  if (Value == nullptr || !Parent.isVirtual() || !Origin.isVirtual() || Parent == VirtualReg ||
+      Origin == VirtualReg || !Function->registerInfo().isKnownVirtualRegister(Parent) ||
+      !Function->registerInfo().isKnownVirtualRegister(Origin))
+    return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap split relationship is invalid");
+  Value->State = VirtRegAllocationState::Split;
+  Value->SplitParent = Parent;
+  Value->Origin = Origin;
+  return {};
+}
+
+Expected<void> VirtRegMap::setSpillable(Register VirtualReg, bool Spillable) {
+  VirtRegMapEntry *Value = entry(VirtualReg);
+  if (Value == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "unknown virtual register in VirtRegMap");
+  Value->Spillable = Spillable;
+  return {};
+}
+
+VirtRegMapEntry *VirtRegMap::entry(Register VirtualReg) noexcept {
+  const auto Position = Entries.find(VirtualReg);
+  return Position == Entries.end() ? nullptr : &Position->second;
+}
+
+const VirtRegMapEntry *VirtRegMap::entry(Register VirtualReg) const noexcept {
+  const auto Position = Entries.find(VirtualReg);
+  return Position == Entries.end() ? nullptr : &Position->second;
+}
+
+std::optional<PhysicalRegister> VirtRegMap::physicalRegister(Register VirtualReg) const noexcept {
+  const VirtRegMapEntry *Value = entry(VirtualReg);
+  return Value == nullptr ? std::nullopt : Value->PhysicalReg;
+}
+
+std::optional<FrameIndex> VirtRegMap::stackSlot(Register VirtualReg) const noexcept {
+  const VirtRegMapEntry *Value = entry(VirtualReg);
+  return Value == nullptr ? std::nullopt : Value->Spill.StackSlot;
+}
+
+bool VirtRegMap::isSpillable(Register VirtualReg) const noexcept {
+  const VirtRegMapEntry *Value = entry(VirtualReg);
+  return Value != nullptr && Value->Spillable;
+}
+
+std::vector<const VirtRegMapEntry *> VirtRegMap::orderedEntries() const {
+  std::vector<const VirtRegMapEntry *> Result;
+  Result.reserve(Entries.size());
+  for (const auto &[Reg, Value] : Entries) {
+    (void)Reg;
+    Result.push_back(&Value);
+  }
+  std::ranges::sort(Result, [](const VirtRegMapEntry *Left, const VirtRegMapEntry *Right) {
+    return Left->VirtualReg.opaqueValue() < Right->VirtualReg.opaqueValue();
+  });
+  return Result;
+}
+
+Expected<void> VirtRegMap::verify() const {
+  if (Function == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has no MachineFunction");
+  for (const VirtRegMapEntry *Value : orderedEntries()) {
+    if (Value == nullptr || !Value->VirtualReg.isVirtual() ||
+        !Function->registerInfo().isKnownVirtualRegister(Value->VirtualReg))
+      return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap contains an invalid entry");
+    if (Value->State == VirtRegAllocationState::Assigned &&
+        (!Value->PhysicalReg || !Value->PhysicalReg->isValid()))
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "assigned VirtRegMap entry has no register");
+    if (Value->State == VirtRegAllocationState::Spilled && !Value->Spill.StackSlot)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "spilled VirtRegMap entry has no stack slot");
+    if (Value->Spill.StackSlot && Value->Spill.Lanes.empty())
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "VirtRegMap spill metadata has an empty lane mask");
+    if (Value->SplitParent &&
+        (!Value->SplitParent->isVirtual() || *Value->SplitParent == Value->VirtualReg ||
+         !Function->registerInfo().isKnownVirtualRegister(*Value->SplitParent)))
+      return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has an invalid split parent");
+    if (Value->Origin && (!Value->Origin->isVirtual() || *Value->Origin == Value->VirtualReg ||
+                          !Function->registerInfo().isKnownVirtualRegister(*Value->Origin)))
+      return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has an invalid split origin");
+    if (Value->State == VirtRegAllocationState::Split && (!Value->SplitParent || !Value->Origin))
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "split VirtRegMap entry lacks parent or origin metadata");
+  }
+  return {};
+}
+
+Expected<bool> rewriteVirtualRegisters(MachineFunction &Function, const TargetDescription &Target,
+                                       const VirtRegMap &Mapping) {
+  if (&Mapping.function() != &Function)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "VirtRegMap belongs to a different MachineFunction");
+  auto MappingVerification = Mapping.verify();
+  if (!MappingVerification)
+    return std::unexpected(MappingVerification.error());
+
+  MachineAnalysisManager ValidationAnalyses;
+  auto Registered = registerStage11MachineAnalyses(ValidationAnalyses);
+  if (!Registered)
+    return std::unexpected(Registered.error());
+  auto Intervals = ValidationAnalyses.getResult<LiveIntervalsAnalysis>(Function, Target);
+  if (!Intervals)
+    return std::unexpected(Intervals.error());
+  LiveRegMatrix ValidationMatrix(Function, Target, **Intervals);
+  for (const VirtRegMapEntry *Entry : Mapping.orderedEntries()) {
+    if (Entry == nullptr || !Entry->PhysicalReg)
+      continue;
+    auto ClassID = regalloc_detail::registerClassFor(Function, Entry->VirtualReg);
+    if (!ClassID)
+      return std::unexpected(ClassID.error());
+    if (!Target.registers().registerClassContains(*ClassID, *Entry->PhysicalReg)) {
+      return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                            "VirtRegMap physical register is outside the virtual register class");
+    }
+    const LiveInterval *Interval = (*Intervals)->interval(Entry->VirtualReg);
+    if (Interval == nullptr || Interval->MainRange.empty())
+      continue;
+    auto Assigned = ValidationMatrix.assign(Entry->VirtualReg, *Entry->PhysicalReg);
+    if (!Assigned)
+      return std::unexpected(Assigned.error());
+  }
+
+  struct Rewrite final {
+    MachineOperand *Operand = nullptr;
+    Register NewRegister;
+  };
+  std::vector<Rewrite> Rewrites;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        MachineOperand *Operand = Instruction->operandAt(Index);
+        const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+        if (Reg == nullptr || !Reg->isVirtual())
+          continue;
+        const auto Assigned = Mapping.physicalRegister(*Reg);
+        if (!Assigned) {
+          if (Operand->isDebugUse()) {
+            Rewrites.push_back({Operand, Register{}});
+            continue;
+          }
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "physical rewrite found an unassigned virtual register " +
+                                    Reg->toString());
+        }
+        PhysicalRegister Effective = *Assigned;
+        if (Operand->subReg().value() != 0) {
+          const auto Sub = Target.registers().subRegister(*Assigned, Operand->subReg());
+          if (!Sub) {
+            return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                  "physical assignment does not support a required subregister");
+          }
+          Effective = *Sub;
+        }
+        Rewrites.push_back({Operand, Register::fromPhysical(Effective)});
+      }
+    }
+  }
+
+  for (const Rewrite &Plan : Rewrites) {
+    auto SetRegister = Plan.Operand->setRegister(Plan.NewRegister);
+    if (!SetRegister)
+      return std::unexpected(SetRegister.error());
+    if (Plan.Operand->subReg().value() != 0) {
+      auto Cleared = Plan.Operand->setSubReg(SubRegIndex{});
+      if (!Cleared)
+        return std::unexpected(Cleared.error());
+    }
+    if (Plan.NewRegister.isNoRegister()) {
+      RegisterOperandFlags Flags = Plan.Operand->registerFlags();
+      Flags.set(RegisterOperandFlag::Undef);
+      auto Updated = Plan.Operand->setRegisterFlags(Flags);
+      if (!Updated)
+        return std::unexpected(Updated.error());
+    }
+  }
+
+  Function.registerInfo().clearLiveInVirtualRegisters();
+  for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) {
+    auto Reg = regalloc_detail::virtualRegisterAt(Index);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    if (!Function.registerInfo().isKnownVirtualRegister(*Reg))
+      continue;
+    auto Erased = Function.registerInfo().eraseVirtualRegister(*Reg);
+    if (!Erased)
+      return std::unexpected(Erased.error());
+  }
+  auto Liveness = rebuildMachineLiveness(Function, Target);
+  if (!Liveness)
+    return std::unexpected(Liveness.error());
+  return !Rewrites.empty();
+}
+
+const MachinePassContract &VirtualRegisterRewritePass::contract() const noexcept {
+  static const MachinePassContract Contract{
+      .Name = "VirtualRegisterRewrite",
+      .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                   MachineFunctionProperty::TiedOpsRewritten},
+      .Sets = {MachineFunctionProperty::NoVRegs},
+      .Clears = {},
+      .RequiredAnalyses = {},
+      .VerificationStage = PipelineStage::RegisterAllocated,
+  };
+  return Contract;
+}
+
+Expected<MachinePassResult> VirtualRegisterRewritePass::run(MachineFunction &Function,
+                                                            const TargetDescription &Target,
+                                                            MachineAnalysisManager &) {
+  if (Mapping == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "VirtualRegisterRewrite requires a VirtRegMap");
+  auto Rewritten = rewriteVirtualRegisters(Function, Target, *Mapping);
+  if (!Rewritten)
+    return std::unexpected(Rewritten.error());
+  MachinePassResult Result;
+  Result.Changed = *Rewritten;
+  if (Result.Changed) {
+    Result.Changes.add(MachinePassChange::Registers);
+    Result.Changes.add(MachinePassChange::Operands);
+  }
+  Result.Preserved = PreservedAnalyses::none();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/MIR/EmbeddedIR.cpp b/backend/lib/MIR/EmbeddedIR.cpp
index b19748e..662faac 100644
--- a/backend/lib/MIR/EmbeddedIR.cpp
+++ b/backend/lib/MIR/EmbeddedIR.cpp
@@ -322,8 +322,8 @@ private:
       parseMetadataDefinition(Line, LineOffset, Position, End);
   }
 
-  void parseTypeDefinition(std::string_view Line, std::size_t LineOffset,
-                           std::size_t Position, std::size_t End) {
+  void parseTypeDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Position,
+                           std::size_t End) {
     auto Name = parseIdentifier(Line, LineOffset, Position, End, '%');
     if (!Name || Failed)
       return;
@@ -350,15 +350,14 @@ private:
       return;
     }
     const std::size_t TypeIndex = Index.TypeDefinitions.size();
-    const bool NumericName = !Name->Name.empty() && Name->Name.front() >= '0' &&
-                             Name->Name.front() <= '9';
+    const bool NumericName =
+        !Name->Name.empty() && Name->Name.front() >= '0' && Name->Name.front() <= '9';
     Index.TypeNameToIndex.emplace(Name->Name, TypeIndex);
     Index.TypeDefinitions.push_back(EmbeddedIRTypeDefinition{
         .Name = std::move(Name->Name),
         .Range = Name->Range,
         .Definition = std::string(Line.substr(Position, DefinitionEnd - Position)),
-        .DefinitionRange =
-            Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd),
+        .DefinitionRange = Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd),
         .NumericName = NumericName,
     });
   }
@@ -495,10 +494,10 @@ private:
         std::size_t Previous = IdentifierBegin;
         while (Previous > 0 && isHorizontalSpace(Line[Previous - 1]))
           --Previous;
-        const bool HasTypeBefore = Previous != 0 && Line[Previous - 1] != '(' &&
-                                   Line[Previous - 1] != ',';
-        const bool EndsParameter = Following == End || Line[Following] == ',' ||
-                                   Line[Following] == ')';
+        const bool HasTypeBefore =
+            Previous != 0 && Line[Previous - 1] != '(' && Line[Previous - 1] != ',';
+        const bool EndsParameter =
+            Following == End || Line[Following] == ',' || Line[Following] == ')';
         if (HasTypeBefore && EndsParameter)
           addLocalValue(*Name, Index.Functions[ActiveFunction.value()]);
         Position = Name->End - 1;
@@ -630,9 +629,8 @@ private:
     });
   }
 
-  void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset,
-                                 std::size_t Begin, std::size_t End,
-                                 EmbeddedIRFunction &Function) {
+  void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Begin,
+                                 std::size_t End, EmbeddedIRFunction &Function) {
     std::size_t Position = skipHorizontalSpace(Line, Begin, End);
     if (Position >= End || Line[Position] != '%')
       return;
diff --git a/backend/lib/MIR/LLVMConstantSyntax.cpp b/backend/lib/MIR/LLVMConstantSyntax.cpp
index 543cc1a..8bc2c18 100644
--- a/backend/lib/MIR/LLVMConstantSyntax.cpp
+++ b/backend/lib/MIR/LLVMConstantSyntax.cpp
@@ -248,9 +248,7 @@ private:
     Words[Nibble / 16U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator))
                            << ((Nibble % 16U) * 4U);
   }
-  if ((BitWidth % 64U) != 0 && (Words.back() >> (BitWidth % 64U)) != 0)
-    return false;
-  return true;
+  return (BitWidth % 64U) == 0 || (Words.back() >> (BitWidth % 64U)) == 0;
 }
 
 [[nodiscard]] bool parseLegacyWideFloatHexWords(std::string_view Digits,
@@ -1172,7 +1170,7 @@ convertRawDoubleNaN(FloatSemantics Semantics, bool Negative, std::uint64_t Fract
                           "integer hexadecimal spelling contains a non-hexadecimal digit");
   }
 
-  const auto FirstNonZero =
+  const auto *const FirstNonZero =
       std::ranges::find_if(Digits, [](char Character) { return hexDigitValue(Character) != 0; });
   std::size_t ActiveBits = 0;
   if (FirstNonZero != Digits.end()) {
@@ -1998,9 +1996,8 @@ Expected<GenericConstantData> ConstantParser::parseExpression(GenericConstantTyp
     case GenericConstantExpressionOpcode::Xor:
     case GenericConstantExpressionOpcode::ExtractElement:
       return 2;
-    case GenericConstantExpressionOpcode::InsertElement:
-      return 3;
     case GenericConstantExpressionOpcode::ShuffleVector:
+    case GenericConstantExpressionOpcode::InsertElement:
       return 3;
     case GenericConstantExpressionOpcode::GetElementPtr:
       return 1;
@@ -2454,15 +2451,22 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT
   case GenericConstantKind::Invalid:
     break;
   case GenericConstantKind::Integer:
+    if (!Value.IntegerValue)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "integer constant is missing its integer payload");
     if (resolvedType(Value.Type).Kind == GenericConstantTypeKind::Integer &&
         resolvedType(Value.Type).BitWidth == 1)
-      Result.append(Value.IntegerValue->isZero() ? "false" : "true");
+      Result.append(Value.IntegerValue.value().isZero() ? "false" : "true");
     else
-      Result.append(Value.IntegerValue->toUnsignedDecimal());
+      Result.append(Value.IntegerValue.value().toUnsignedDecimal());
     return Result;
   case GenericConstantKind::Floating:
+    if (!Value.FloatingValue)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "floating constant is missing its floating payload");
     Result.append("f0x");
-    Result.append(hexadecimalWords(Value.FloatingValue->words(), Value.FloatingValue->bitWidth()));
+    Result.append(hexadecimalWords(Value.FloatingValue.value().words(),
+                                   Value.FloatingValue.value().bitWidth()));
     return Result;
   case GenericConstantKind::NullPointer:
     Result.append("null");
@@ -2549,15 +2553,25 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT
     if (Value.ExpressionFlags.has(GenericConstantExpressionFlag::NoSignedWrap))
       Result.append(" nsw");
     if (Value.InRangeStart) {
+      if (!Value.InRangeEnd) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "constant expression is missing its inrange end");
+      }
+      const auto &InRangeStart = Value.InRangeStart.value();
+      const auto &InRangeEnd = Value.InRangeEnd.value();
       Result.append(" inrange(");
-      Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeStart->words()[0])));
+      Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeStart.words()[0])));
       Result.append(", ");
-      Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeEnd->words()[0])));
+      Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeEnd.words()[0])));
       Result.push_back(')');
     }
     Result.append(" (");
     if (Value.ExpressionOpcode == GenericConstantExpressionOpcode::GetElementPtr) {
-      auto SourceType = printType(*Value.SourceElementType);
+      if (!Value.SourceElementType) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "getelementptr constant is missing its source element type");
+      }
+      auto SourceType = printType(Value.SourceElementType.value());
       if (!SourceType)
         return std::unexpected(SourceType.error());
       Result.append(*SourceType);
@@ -3004,14 +3018,12 @@ LayoutAlignment DataLayoutInfo::scalarAlignment(char Kind, std::uint32_t BitWidt
     if (Entry.Kind != Kind)
       continue;
     if (Kind == 'i') {
-      if (Entry.BitWidth >= BitWidth &&
-          (Selected == nullptr || Entry.BitWidth < Selected->BitWidth)) {
+      const bool BetterMatch =
+          Selected == nullptr ||
+          (Entry.BitWidth >= BitWidth && Entry.BitWidth < Selected->BitWidth) ||
+          (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth);
+      if (BetterMatch)
         Selected = &Entry;
-      } else if (Selected == nullptr) {
-        Selected = &Entry;
-      } else if (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth) {
-        Selected = &Entry;
-      }
     } else if (Entry.BitWidth == BitWidth) {
       Selected = &Entry;
       break;
diff --git a/backend/lib/MIR/MIDebugSyntax.cpp b/backend/lib/MIR/MIDebugSyntax.cpp
index bee82c4..fc08df6 100644
--- a/backend/lib/MIR/MIDebugSyntax.cpp
+++ b/backend/lib/MIR/MIDebugSyntax.cpp
@@ -16,15 +16,13 @@ namespace {
 [[nodiscard]] bool parseIndex(std::string_view Text, std::uint64_t &Value) noexcept {
   if (Text.empty())
     return false;
-  const auto [End, Error] =
-      std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10);
+  const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10);
   return Error == std::errc{} && End == Text.data() + Text.size();
 }
 
 } // namespace
 
-std::optional<std::uint64_t>
-parseDIExpressionOpcodeName(std::string_view Name) noexcept {
+std::optional<std::uint64_t> parseDIExpressionOpcodeName(std::string_view Name) noexcept {
   const auto NumberedOpcode = [Name](std::string_view Prefix,
                                      std::uint64_t Base) -> std::optional<std::uint64_t> {
     if (!Name.starts_with(Prefix))
@@ -117,7 +115,7 @@ parseDIExpressionOpcodeName(std::string_view Name) noexcept {
       {"DW_OP_LLVM_implicit_pointer", 0x1004},
       {"DW_OP_LLVM_arg", 0x1005},
   });
-  const auto Found =
+  const auto *const Found =
       std::ranges::find_if(NamedOpcodes, [Name](const auto &Entry) { return Entry.first == Name; });
   if (Found == NamedOpcodes.end())
     return std::nullopt;
diff --git a/backend/lib/MIR/MIPrinter.cpp b/backend/lib/MIR/MIPrinter.cpp
index 83fce40..8ad6d6c 100644
--- a/backend/lib/MIR/MIPrinter.cpp
+++ b/backend/lib/MIR/MIPrinter.cpp
@@ -1285,20 +1285,24 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "machine instruction has no target descriptor");
   }
-  if (Descriptor->NumExplicitDefs > Instruction.operandCount()) {
-    return makeUnexpected(ErrorCode::VerificationError,
-                          "machine instruction has fewer operands than explicit definitions");
+  std::size_t ExplicitDefs = 0;
+  while (ExplicitDefs < Instruction.operandCount()) {
+    const MachineOperand *Operand = Instruction.operandAt(ExplicitDefs);
+    if (Operand == nullptr || !Operand->isRegister() || Operand->isImplicit() ||
+        !Operand->isDef() || Operand->isUse())
+      break;
+    ++ExplicitDefs;
   }
 
   Output.append("  ");
-  for (std::size_t Index = 0; Index < Descriptor->NumExplicitDefs; ++Index) {
+  for (std::size_t Index = 0; Index < ExplicitDefs; ++Index) {
     if (Index != 0)
       Output.append(", ");
     if (auto Printed = printOperand(*Instruction.operandAt(Index), true); !Printed) {
       return Printed;
     }
   }
-  if (Descriptor->NumExplicitDefs != 0)
+  if (ExplicitDefs != 0)
     Output.append(" = ");
 
   const MachineInstrFlags Flags = Instruction.flags();
@@ -1333,8 +1337,7 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) {
   Output.append(Descriptor->Name);
 
   bool HasPrintedTail = false;
-  for (std::size_t Index = Descriptor->NumExplicitDefs; Index < Instruction.operandCount();
-       ++Index) {
+  for (std::size_t Index = ExplicitDefs; Index < Instruction.operandCount(); ++Index) {
     Output.append(HasPrintedTail ? ", " : " ");
     HasPrintedTail = true;
     if (auto Printed = printOperand(*Instruction.operandAt(Index), false); !Printed) {
diff --git a/backend/lib/MIR/MIRDocument.cpp b/backend/lib/MIR/MIRDocument.cpp
index 4808df7..67e6ffb 100644
--- a/backend/lib/MIR/MIRDocument.cpp
+++ b/backend/lib/MIR/MIRDocument.cpp
@@ -406,7 +406,8 @@ class MIRDocumentParser final {
 public:
   MIRDocumentParser(const TargetDescription &Target, std::string SourceName, std::string SourceText,
                     MIRDocumentParserOptions Options)
-      : Target(Target), Options(Options), Result(std::move(SourceName), std::move(SourceText)) {}
+      : Target(Target), Options(std::move(Options)),
+        Result(std::move(SourceName), std::move(SourceText)) {}
 
   [[nodiscard]] MIRDocumentParseResult run();
 
@@ -2144,8 +2145,7 @@ bool MIRDocumentParser::parseFunctionRecords(const yaml::Node &Root, MachineFunc
           WideFlags > std::numeric_limits<std::uint32_t>::max()) {
         return true;
       }
-      if (ActiveDocument->EmbeddedIR &&
-          ActiveDocument->EmbeddedIR->hasGlobalValue(Callee) == false) {
+      if (ActiveDocument->EmbeddedIR && !ActiveDocument->EmbeddedIR->hasGlobalValue(Callee)) {
         return fail(CalleeNode->range(), "called global references an undefined embedded global");
       }
       auto AddResult =
@@ -2765,7 +2765,8 @@ MIRDocumentParseResult::~MIRDocumentParseResult() = default;
 
 MIRDocumentParseResult parseMIRDocument(const TargetDescription &Target, std::string SourceName,
                                         std::string SourceText, MIRDocumentParserOptions Options) {
-  return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), Options).run();
+  return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), std::move(Options))
+      .run();
 }
 
 } // namespace rcc::mir
diff --git a/backend/lib/MIR/MIRDocumentPrinter.cpp b/backend/lib/MIR/MIRDocumentPrinter.cpp
index e9f9e1c..dba1ec7 100644
--- a/backend/lib/MIR/MIRDocumentPrinter.cpp
+++ b/backend/lib/MIR/MIRDocumentPrinter.cpp
@@ -85,7 +85,7 @@ class MIRDocumentPrinter final {
 public:
   MIRDocumentPrinter(const MIRDocument &Document, const TargetDescription &Target,
                      MIRDocumentPrinterOptions Options)
-      : Document(Document), Target(Target), Options(Options) {}
+      : Document(Document), Target(Target), Options(std::move(Options)) {}
 
   [[nodiscard]] Expected<std::string> run();
 
@@ -1187,9 +1187,10 @@ Expected<void> MIRDocumentPrinter::printFunction(const MachineFunction &Function
   Output.append("---\nname: ");
   Output.append(yamlScalar(Function.name()));
   Output.push_back('\n');
-  if (Function.attributes().alignment()) {
+  const auto Alignment = Function.attributes().alignment();
+  if (Alignment) {
     Output.append("alignment: ");
-    Output.append(std::to_string(Function.attributes().alignment()->bytes()));
+    Output.append(std::to_string(Alignment->bytes()));
     Output.push_back('\n');
   }
 
@@ -1296,7 +1297,7 @@ Expected<std::string> MIRDocumentPrinter::run() {
 
 Expected<std::string> printMIRDocument(const MIRDocument &Document, const TargetDescription &Target,
                                        MIRDocumentPrinterOptions Options) {
-  return MIRDocumentPrinter(Document, Target, Options).run();
+  return MIRDocumentPrinter(Document, Target, std::move(Options)).run();
 }
 
 } // namespace rcc::mir
diff --git a/backend/lib/MIR/MIRDocumentReferenceValidation.h b/backend/lib/MIR/MIRDocumentReferenceValidation.h
index 0992d84..2ab6291 100644
--- a/backend/lib/MIR/MIRDocumentReferenceValidation.h
+++ b/backend/lib/MIR/MIRDocumentReferenceValidation.h
@@ -1,5 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
 #ifndef RCC_LIB_MIR_MIRDOCUMENTREFERENCEVALIDATION_H
 #define RCC_LIB_MIR_MIRDOCUMENTREFERENCEVALIDATION_H
 
diff --git a/backend/lib/Support/Error.cpp b/backend/lib/Support/Error.cpp
index dc7d590..817a2bb 100644
--- a/backend/lib/Support/Error.cpp
+++ b/backend/lib/Support/Error.cpp
@@ -14,6 +14,8 @@ std::string_view getErrorCodeName(ErrorCode Code) noexcept {
     return "verification error";
   case ErrorCode::Unsupported:
     return "unsupported";
+  case ErrorCode::RegisterAllocationFailed:
+    return "register allocation failed";
   case ErrorCode::IoError:
     return "I/O error";
   case ErrorCode::InternalError:
diff --git a/backend/lib/Target/Description/TargetDescriptionGenerator.cpp b/backend/lib/Target/Description/TargetDescriptionGenerator.cpp
index 3c5e817..9d6b8e1 100644
--- a/backend/lib/Target/Description/TargetDescriptionGenerator.cpp
+++ b/backend/lib/Target/Description/TargetDescriptionGenerator.cpp
@@ -1364,7 +1364,7 @@ private:
       const auto Value = unsignedInteger32(*Tie, "instruction operand default_tied_operand");
       if (!Value)
         return std::nullopt;
-      Result.DefaultTiedOperand = *Value;
+      Result.DefaultTiedOperand = Value;
     }
     if (const yaml::Node *EarlyClobber = optionalNode(Node, "early_clobber")) {
       const auto Value = boolean(*EarlyClobber, "instruction operand early_clobber");
@@ -1614,7 +1614,7 @@ operandKindEnumerator(std::string_view Value) noexcept {
       {"debug_instr_ref", "DebugInstrRef"},
       {"lane_mask", "LaneMask"},
   }};
-  const auto Position = std::ranges::find(Kinds, Value, &decltype(Kinds)::value_type::first);
+  const auto *const Position = std::ranges::find(Kinds, Value, &decltype(Kinds)::value_type::first);
   if (Position == Kinds.end())
     return std::nullopt;
   return Position->second;
@@ -1675,7 +1675,7 @@ instructionFlagEnumerator(std::string_view Value) noexcept {
       {"generic", "Generic"},
       {"terminal_emission", "TerminalEmission"},
   }};
-  const auto Position = std::ranges::find(Flags, Value, &decltype(Flags)::value_type::first);
+  const auto *const Position = std::ranges::find(Flags, Value, &decltype(Flags)::value_type::first);
   if (Position == Flags.end())
     return std::nullopt;
   return Position->second;
@@ -1698,7 +1698,8 @@ pseudoOwnerEnumerator(std::string_view Value) noexcept {
   }};
   if (Value == "asm_printer")
     return "AsmPrinter";
-  const auto Position = std::ranges::find(Owners, Value, &decltype(Owners)::value_type::first);
+  const auto *const Position =
+      std::ranges::find(Owners, Value, &decltype(Owners)::value_type::first);
   if (Position == Owners.end())
     return std::nullopt;
   return Position->second;
@@ -1718,7 +1719,8 @@ pipelineStageEnumerator(std::string_view Value) noexcept {
       {"post_ra_finalized", "PostRAFinalized"},
       {"emission", "Emission"},
   }};
-  const auto Position = std::ranges::find(Stages, Value, &decltype(Stages)::value_type::first);
+  const auto *const Position =
+      std::ranges::find(Stages, Value, &decltype(Stages)::value_type::first);
   if (Position == Stages.end())
     return std::nullopt;
   return Position->second;
@@ -2066,7 +2068,7 @@ private:
         fail(Convention.Range, "calling convention register classes must resolve");
         return false;
       }
-      const auto normalizeRegisterList = [this,
+      const auto NormalizeRegisterList = [this,
                                           &Convention](const std::vector<std::string> &Symbols,
                                                        const NormalizedRegisterClass &RegisterClass,
                                                        std::vector<std::uint32_t> &Output) {
@@ -2101,13 +2103,13 @@ private:
           .SupportsVarArgs = Convention.SupportsVarArgs,
           .SupportsTailCalls = Convention.SupportsTailCalls,
       };
-      if (!normalizeRegisterList(Convention.IntegerArgumentRegisterSymbols,
+      if (!NormalizeRegisterList(Convention.IntegerArgumentRegisterSymbols,
                                  *IntegerClassDescription, Normalized.IntegerArgumentRegisters) ||
-          !normalizeRegisterList(Convention.FloatingArgumentRegisterSymbols,
+          !NormalizeRegisterList(Convention.FloatingArgumentRegisterSymbols,
                                  *FloatingClassDescription, Normalized.FloatingArgumentRegisters) ||
-          !normalizeRegisterList(Convention.IntegerReturnRegisterSymbols, *IntegerClassDescription,
+          !NormalizeRegisterList(Convention.IntegerReturnRegisterSymbols, *IntegerClassDescription,
                                  Normalized.IntegerReturnRegisters) ||
-          !normalizeRegisterList(Convention.FloatingReturnRegisterSymbols,
+          !NormalizeRegisterList(Convention.FloatingReturnRegisterSymbols,
                                  *FloatingClassDescription, Normalized.FloatingReturnRegisters)) {
         return false;
       }
@@ -3004,8 +3006,9 @@ void emitImmediatePredicate(std::ostream &Output, const NormalizedImmediatePredi
 
 } // namespace
 
-DescriptionGenerationResult generateDescription(std::string SourceName, std::string SourceText) {
-  yaml::ParseResult YAMLResult = yaml::parse(SourceName, SourceText);
+DescriptionGenerationResult generateDescription(const std::string &SourceName,
+                                                std::string SourceText) {
+  yaml::ParseResult YAMLResult = yaml::parse(SourceName, std::move(SourceText));
   if (!YAMLResult.succeeded()) {
     DescriptionGenerationResult Result;
     for (const TextDiagnostic &Diagnostic : YAMLResult.diagnostics())
diff --git a/backend/lib/Target/Description/TargetDescriptionGenerator.h b/backend/lib/Target/Description/TargetDescriptionGenerator.h
index c0d8ed5..9a03aa0 100644
--- a/backend/lib/Target/Description/TargetDescriptionGenerator.h
+++ b/backend/lib/Target/Description/TargetDescriptionGenerator.h
@@ -1,5 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
 #ifndef RCC_TARGET_DESCRIPTION_TARGETDESCRIPTIONGENERATOR_H
 #define RCC_TARGET_DESCRIPTION_TARGETDESCRIPTIONGENERATOR_H
 
@@ -27,7 +29,7 @@ struct DescriptionGenerationResult final {
   }
 };
 
-[[nodiscard]] DescriptionGenerationResult generateDescription(std::string SourceName,
+[[nodiscard]] DescriptionGenerationResult generateDescription(const std::string &SourceName,
                                                               std::string SourceText);
 
 } // namespace rcc::targetgen
diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt
index 4728117..1d9a27a 100644
--- a/backend/lib/Target/RISCV/CMakeLists.txt
+++ b/backend/lib/Target/RISCV/CMakeLists.txt
@@ -49,6 +49,7 @@ add_library(
   RCCBackendRISCV
   RISCVCodeGen.cpp
   RISCVCallLowering.cpp
+  RISCVRegisterAllocation.cpp
   RISCVTarget.cpp
   "${RCCBackendRISCVGeneratedRegisterHeader}"
   "${RCCBackendRISCVGeneratedInstructionHeader}"
@@ -93,6 +94,7 @@ install(
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCodeGen.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCallLowering.h"
@@ -101,5 +103,6 @@ rcc_backend_register_format_files(
 rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp"
 )
diff --git a/backend/lib/Target/RISCV/RISCV.rccdesc b/backend/lib/Target/RISCV/RISCV.rccdesc
index a8dfdde..e248bc7 100644
--- a/backend/lib/Target/RISCV/RISCV.rccdesc
+++ b/backend/lib/Target/RISCV/RISCV.rccdesc
@@ -375,7 +375,7 @@ instructions:
       - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD }
       - { kinds: [immediate], immediate_predicate: SIMM20, name: IMM }
     num_explicit_defs: 1
-    flags: [produces_code]
+    flags: [produces_code, rematerializable]
     scheduling_class: ALU
     encoding_category: U
     assembly_format: RD_IMM
@@ -402,7 +402,7 @@ instructions:
       - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
-    flags: [produces_code]
+    flags: [produces_code, rematerializable]
     scheduling_class: ALU
     encoding_category: I
     assembly_format: RD_RS1_IMM
@@ -444,7 +444,7 @@ instructions:
       - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
-    flags: [produces_code]
+    flags: [produces_code, rematerializable]
     scheduling_class: ALU
     encoding_category: I
     assembly_format: RD_RS1_IMM
@@ -709,7 +709,7 @@ instructions:
     assembly_mnemonic: lw
     operands:
       - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, memory_role: value, name: RD }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
     flags: [may_load, produces_code]
@@ -799,7 +799,7 @@ instructions:
     assembly_mnemonic: sw
     operands:
       - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: value, name: RS2 }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 0
     flags: [may_store, produces_code]
@@ -1202,7 +1202,7 @@ instructions:
     assembly_mnemonic: ld
     operands:
       - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, memory_role: value, name: RD }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
     flags: [may_load, produces_code]
@@ -1217,7 +1217,7 @@ instructions:
     assembly_mnemonic: sd
     operands:
       - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: value, name: RS2 }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 0
     flags: [may_store, produces_code]
@@ -1423,7 +1423,7 @@ instructions:
     assembly_mnemonic: flw
     operands:
       - { kinds: [register], role: def, register_class: FPR32, register_bank: FPR, memory_role: value, name: FRD }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
     flags: [may_load, produces_code]
@@ -1438,7 +1438,7 @@ instructions:
     assembly_mnemonic: fsw
     operands:
       - { kinds: [register], role: use, register_class: FPR32, register_bank: FPR, memory_role: value, name: FRS2 }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 0
     flags: [may_store, produces_code]
@@ -1854,7 +1854,7 @@ instructions:
     assembly_mnemonic: fld
     operands:
       - { kinds: [register], role: def, register_class: FPR64, register_bank: FPR, memory_role: value, name: FRD }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 1
     flags: [may_load, produces_code]
@@ -1869,7 +1869,7 @@ instructions:
     assembly_mnemonic: fsd
     operands:
       - { kinds: [register], role: use, register_class: FPR64, register_bank: FPR, memory_role: value, name: FRS2 }
-      - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
+      - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 }
       - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM }
     num_explicit_defs: 0
     flags: [may_store, produces_code]
diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
new file mode 100644
index 0000000..e437e18
--- /dev/null
+++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
@@ -0,0 +1,279 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVRegisters.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <utility>
+
+namespace rcc::riscv {
+namespace {
+
+struct SpillForm final {
+  InstructionOpcode Load;
+  InstructionOpcode Store;
+  std::uint64_t SizeInBytes;
+};
+
+[[nodiscard]] constexpr Opcode targetOpcode(InstructionOpcode Value) noexcept {
+  return Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] constexpr RegisterClassID registerClassID(RegisterClass Value) noexcept {
+  return RegisterClassID::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] constexpr std::optional<SpillForm> spillForm(RegisterClassID Class) noexcept {
+  if (Class == registerClassID(RegisterClass::GPR) ||
+      Class == registerClassID(RegisterClass::GPRC) ||
+      Class == registerClassID(RegisterClass::GPR_NX0) ||
+      Class == registerClassID(RegisterClass::GPR_NX0_NX2)) {
+    return SpillForm{InstructionOpcode::LD, InstructionOpcode::SD, 8};
+  }
+  if (Class == registerClassID(RegisterClass::FPR64) ||
+      Class == registerClassID(RegisterClass::FPR64C)) {
+    return SpillForm{InstructionOpcode::FLD, InstructionOpcode::FSD, 8};
+  }
+  if (Class == registerClassID(RegisterClass::FPR32) ||
+      Class == registerClassID(RegisterClass::FPR32C)) {
+    return SpillForm{InstructionOpcode::FLW, InstructionOpcode::FSW, 4};
+  }
+  return std::nullopt;
+}
+
+[[nodiscard]] Expected<const MachineMemOperand *>
+createStackMemoryOperand(MachineIRBuilder &Builder, FrameIndex StackSlot, MemoryAccessFlag Access,
+                         std::uint64_t SizeInBytes, std::uint64_t AlignmentInBytes) {
+  auto Size = MemorySize::fixed(SizeInBytes);
+  if (!Size)
+    return std::unexpected(Size.error());
+  auto Align = Alignment::create(AlignmentInBytes);
+  if (!Align)
+    return std::unexpected(Align.error());
+
+  MachineMemOperandDesc Description;
+  Description.Accesses = {Access};
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = MemoryBase::frameIndex(StackSlot);
+  return Builder.function().createMemOperand(std::move(Description));
+}
+
+[[nodiscard]] bool isCalleeSaved(PhysicalRegister Reg) noexcept {
+  const std::uint32_t Number = Reg.number();
+  const std::array GPRs{
+      PhysicalRegisterID::X8,  PhysicalRegisterID::X9,  PhysicalRegisterID::X18,
+      PhysicalRegisterID::X19, PhysicalRegisterID::X20, PhysicalRegisterID::X21,
+      PhysicalRegisterID::X22, PhysicalRegisterID::X23, PhysicalRegisterID::X24,
+      PhysicalRegisterID::X25, PhysicalRegisterID::X26, PhysicalRegisterID::X27,
+  };
+  const std::array FPRs{
+      PhysicalRegisterID::F8,  PhysicalRegisterID::F9,  PhysicalRegisterID::F18,
+      PhysicalRegisterID::F19, PhysicalRegisterID::F20, PhysicalRegisterID::F21,
+      PhysicalRegisterID::F22, PhysicalRegisterID::F23, PhysicalRegisterID::F24,
+      PhysicalRegisterID::F25, PhysicalRegisterID::F26, PhysicalRegisterID::F27,
+  };
+  const auto Matches = [Number](PhysicalRegisterID ID) {
+    return Number == static_cast<std::uint32_t>(ID);
+  };
+  return std::ranges::any_of(GPRs, Matches) || std::ranges::any_of(FPRs, Matches);
+}
+
+[[nodiscard]] bool isCompressedRegister(PhysicalRegister Reg) noexcept {
+  const std::uint32_t Number = Reg.number();
+  const std::uint32_t X8 = static_cast<std::uint32_t>(PhysicalRegisterID::X8);
+  const std::uint32_t X15 = static_cast<std::uint32_t>(PhysicalRegisterID::X15);
+  const std::uint32_t F8 = static_cast<std::uint32_t>(PhysicalRegisterID::F8);
+  const std::uint32_t F15 = static_cast<std::uint32_t>(PhysicalRegisterID::F15);
+  return (Number >= X8 && Number <= X15) || (Number >= F8 && Number <= F15);
+}
+
+class RISCVRegisterAllocationInfo final : public TargetRegisterAllocationInfo {
+public:
+  [[nodiscard]] Expected<void> validateSpillReload(RegisterClassID Class,
+                                                   const TargetDescription &Target) const override {
+    const RegisterClassDesc *Description = Target.registers().registerClass(Class);
+    const auto Form = spillForm(Class);
+    if (!Form) {
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "RV64GC register class has no scalar spill/reload form");
+    }
+    if (Description == nullptr || !Description->Allocatable ||
+        Description->SpillSizeInBits != Form->SizeInBytes * 8U ||
+        Description->SpillAlignmentInBits == 0 || Description->SpillAlignmentInBits % 8U != 0) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RV64GC register class has inconsistent spill properties");
+    }
+    for (const InstructionOpcode OpcodeValue : {Form->Load, Form->Store}) {
+      const InstructionDescriptor *Instruction =
+          Target.instructionDescriptor(targetOpcode(OpcodeValue));
+      if (Instruction == nullptr || Instruction->Operands.size() != 3 ||
+          !Instruction->Operands[1].Kinds.contains(MachineOperand::Kind::FrameIndex) ||
+          !Instruction->RequiresMemoryOperands) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RV64GC spill instruction descriptor is incomplete");
+      }
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<MachineInstr *> emitReload(MachineIRBuilder &Builder, Register Destination,
+                                                    RegisterClassID Class, FrameIndex StackSlot,
+                                                    LaneMask Lanes) const override {
+    auto Validated = validateSpillReload(Class, Builder.target());
+    if (!Validated)
+      return std::unexpected(Validated.error());
+    const RegisterClassDesc *Description = Builder.target().registers().registerClass(Class);
+    if (Lanes.empty() || !Lanes.intersects(Description->Lanes)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RV64GC reload requires a nonempty class lane mask");
+    }
+    const auto FormValue = spillForm(Class);
+    if (!FormValue) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RV64GC reload lost its validated spill form");
+    }
+    const SpillForm Form = FormValue.value();
+    auto Memory =
+        createStackMemoryOperand(Builder, StackSlot, MemoryAccessFlag::Load, Form.SizeInBytes,
+                                 Description->SpillAlignmentInBits / 8U);
+    if (!Memory)
+      return std::unexpected(Memory.error());
+    auto Pending = Builder.buildInstr(targetOpcode(Form.Load));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    if (auto Result = Pending->addDef(Destination); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addFrameIndex(StackSlot); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addImmediate(0); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addMemOperand(**Memory); !Result)
+      return std::unexpected(Result.error());
+    return Pending->build();
+  }
+
+  [[nodiscard]] Expected<MachineInstr *> emitSpill(MachineIRBuilder &Builder, Register Source,
+                                                   RegisterClassID Class, FrameIndex StackSlot,
+                                                   LaneMask Lanes) const override {
+    auto Validated = validateSpillReload(Class, Builder.target());
+    if (!Validated)
+      return std::unexpected(Validated.error());
+    const RegisterClassDesc *Description = Builder.target().registers().registerClass(Class);
+    if (Lanes.empty() || !Lanes.intersects(Description->Lanes)) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RV64GC spill requires a nonempty class lane mask");
+    }
+    const auto FormValue = spillForm(Class);
+    if (!FormValue) {
+      return makeUnexpected(ErrorCode::InternalError, "RV64GC spill lost its validated spill form");
+    }
+    const SpillForm Form = FormValue.value();
+    auto Memory =
+        createStackMemoryOperand(Builder, StackSlot, MemoryAccessFlag::Store, Form.SizeInBytes,
+                                 Description->SpillAlignmentInBits / 8U);
+    if (!Memory)
+      return std::unexpected(Memory.error());
+    auto Pending = Builder.buildInstr(targetOpcode(Form.Store));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    if (auto Result = Pending->addUse(Source); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addFrameIndex(StackSlot); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addImmediate(0); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addMemOperand(**Memory); !Result)
+      return std::unexpected(Result.error());
+    return Pending->build();
+  }
+
+  [[nodiscard]] Expected<bool> isRematerializable(const MachineInstr &Instruction,
+                                                  Register VirtualReg, const MachineFunction &,
+                                                  const TargetDescription &) const override {
+    const MachineOperand *Definition = Instruction.operandAt(0);
+    const Register *DefinedReg = Definition == nullptr ? nullptr : Definition->getIf<Register>();
+    if (DefinedReg == nullptr || *DefinedReg != VirtualReg || !Definition->isDef())
+      return false;
+
+    if (Instruction.opcode() == targetOpcode(InstructionOpcode::LUI))
+      return Instruction.operandCount() == 2 && Instruction.operandAt(1) != nullptr;
+    if (Instruction.opcode() != targetOpcode(InstructionOpcode::ADDI) &&
+        Instruction.opcode() != targetOpcode(InstructionOpcode::ADDIW)) {
+      return false;
+    }
+    if (Instruction.operandCount() != 3)
+      return false;
+    const MachineOperand *Source = Instruction.operandAt(1);
+    const Register *SourceReg = Source == nullptr ? nullptr : Source->getIf<Register>();
+    const auto Zero = physicalRegister(PhysicalRegisterID::X0);
+    return Zero && SourceReg != nullptr && *SourceReg == Register::fromPhysical(*Zero) &&
+           Source->isUse();
+  }
+
+  [[nodiscard]] Expected<MachineInstr *>
+  rematerialize(MachineIRBuilder &Builder, const MachineInstr &Original, Register Destination,
+                Register OriginalRegister, const TargetDescription &Target) const override {
+    auto Accepted = isRematerializable(Original, OriginalRegister, Builder.function(), Target);
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RV64GC instruction is not rematerializable");
+    }
+
+    auto Pending = Builder.buildInstr(Original.opcode());
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    const MachineOperand *OriginalDef = Original.operandAt(0);
+    if (auto Result = Pending->addDef(Destination, {}, {}, OriginalDef->targetFlags()); !Result)
+      return std::unexpected(Result.error());
+    for (std::size_t Index = 1; Index < Original.operandCount(); ++Index) {
+      const MachineOperand *Operand = Original.operandAt(Index);
+      if (Operand == nullptr) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RV64GC rematerialization found a missing operand");
+      }
+      if (auto Result = Pending->addOperand(Operand->cloneDetached()); !Result)
+        return std::unexpected(Result.error());
+    }
+    return Pending->build();
+  }
+
+  [[nodiscard]] std::uint64_t physicalRegisterCost(const MachineFunction &, Register,
+                                                   PhysicalRegister Reg, RegisterClassID,
+                                                   bool) const noexcept override {
+    if (Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X1))
+      return 16;
+    if (isCalleeSaved(Reg))
+      return 4;
+    return isCompressedRegister(Reg) ? 0 : 1;
+  }
+
+  [[nodiscard]] std::uint64_t spillCost(const MachineFunction &, const LiveInterval &,
+                                        RegisterClassID Class) const noexcept override {
+    const auto Form = spillForm(Class);
+    return Form ? std::max<std::uint64_t>(1, Form->SizeInBytes / 4U) : 1;
+  }
+};
+
+} // namespace
+
+const TargetRegisterAllocationInfo &registerAllocationInfo() noexcept {
+  static const RISCVRegisterAllocationInfo Info;
+  return Info;
+}
+
+} // namespace rcc::riscv