[CodeGen] Implement RV64GC frame lowering

12 files changed, 551 insertions, 7 deletions

diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index d6233c2..a8cb952 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -5,6 +5,7 @@ set(
   CompilationUnit.cpp
   GenericOpcodes.cpp
   GenericConstant.cpp
+  FrameIndexElimination.cpp
   InstructionDescriptor.cpp
   LowLevelType.cpp
   MachineBasicBlockAttributes.cpp
@@ -30,6 +31,8 @@ set(
   MachinePass.cpp
   MachinePipelinePasses.cpp
   MachineRegisterInfo.cpp
+  PrologueEpilogueInsertion.cpp
+  RegisterScavenger.cpp
   InlineSpiller.cpp
   LiveRangeEdit.cpp
   LiveRegMatrix.cpp
@@ -56,6 +59,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/CompilationUnit.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericOpcodes.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GenericConstant.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/FrameIndexElimination.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlockAttributes.h"
@@ -80,7 +84,10 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePass.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PrologueEpilogueInsertion.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterScavenger.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFrameLowering.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"
diff --git a/backend/lib/CodeGen/FrameIndexElimination.cpp b/backend/lib/CodeGen/FrameIndexElimination.cpp
new file mode 100644
index 0000000..53c64e1
--- /dev/null
+++ b/backend/lib/CodeGen/FrameIndexElimination.cpp
@@ -0,0 +1,61 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/FrameIndexElimination.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/RegisterScavenger.h"
+#include "rcc/CodeGen/TargetFrameLowering.h"
+
+#include <cstddef>
+#include <utility>
+
+namespace rcc {
+
+Expected<bool> eliminateFrameIndices(MachineFunction &Function, const TargetDescription &Target,
+                                     const TargetFrameLowering &FrameLowering,
+                                     RegisterScavenger &Scavenger) {
+  bool Changed = false;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;) {
+      MachineInstr *Next = Instruction->next();
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        if (Instruction->operandAt(Index)->kind() != MachineOperand::Kind::FrameIndex)
+          continue;
+        auto Eliminated =
+            FrameLowering.eliminateFrameIndex(*Instruction, Index, Function, Target, Scavenger);
+        if (!Eliminated)
+          return std::unexpected(Eliminated.error());
+        Changed = true;
+      }
+
+      for (std::size_t Index = 0; Index < Instruction->memOperands().size(); ++Index) {
+        const MachineMemOperand *Memory = Instruction->memOperands()[Index];
+        const auto Frame = Memory->description().Base.frameIndex();
+        if (!Frame)
+          continue;
+        auto Reference = FrameLowering.getFrameIndexReference(Function, *Instruction, *Frame,
+                                                              Memory->description().Offset);
+        if (!Reference)
+          return std::unexpected(Reference.error());
+        MachineMemOperandDesc Description = Memory->description();
+        Description.Base = MemoryBase::stack();
+        Description.Offset = Reference->Offset;
+        auto Replacement = Function.createMemOperand(std::move(Description));
+        if (!Replacement)
+          return std::unexpected(Replacement.error());
+        auto Replaced = Instruction->replaceMemOperand(Index, **Replacement);
+        if (!Replaced)
+          return std::unexpected(Replaced.error());
+        Changed = true;
+      }
+      Instruction = Next;
+    }
+  }
+  return Changed;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp
index 1091b52..765e133 100644
--- a/backend/lib/CodeGen/MachineCompilationStatus.cpp
+++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp
@@ -43,6 +43,7 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep
   case ErrorCode::VerificationError:
   case ErrorCode::Unsupported:
   case ErrorCode::RegisterAllocationFailed:
+  case ErrorCode::FrameLayoutFailed:
   case ErrorCode::IoError:
   case ErrorCode::InternalError:
     return true;
diff --git a/backend/lib/CodeGen/MachineFrameInfo.cpp b/backend/lib/CodeGen/MachineFrameInfo.cpp
index a6f7a77..8c3e6e5 100644
--- a/backend/lib/CodeGen/MachineFrameInfo.cpp
+++ b/backend/lib/CodeGen/MachineFrameInfo.cpp
@@ -330,7 +330,7 @@ Expected<void> MachineFrameInfo::freeze(std::uint64_t Size, Alignment Align) {
   if (Frozen)
     return makeUnexpected(ErrorCode::InvalidArgument, "frame layout is already frozen");
   for (const StackObject &Object : Objects) {
-    if (Object.isTombstone() || Object.isVariableSized())
+    if (Object.isTombstone() || Object.description()->IsDead || Object.isVariableSized())
       continue;
     if (!Object.description()->Offset) {
       return makeUnexpected(ErrorCode::VerificationError,
@@ -364,7 +364,8 @@ Expected<void> MachineFrameInfo::verify() const {
     auto DescriptionResult = verifyDescription(*Object.description());
     if (!DescriptionResult)
       return std::unexpected(DescriptionResult.error());
-    if (Frozen && !Object.isVariableSized() && !Object.description()->Offset) {
+    if (Frozen && !Object.description()->IsDead && !Object.isVariableSized() &&
+        !Object.description()->Offset) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "frozen fixed-size stack object has no final offset");
     }
diff --git a/backend/lib/CodeGen/MachineInstr.cpp b/backend/lib/CodeGen/MachineInstr.cpp
index 7597651..f4602e0 100644
--- a/backend/lib/CodeGen/MachineInstr.cpp
+++ b/backend/lib/CodeGen/MachineInstr.cpp
@@ -235,6 +235,20 @@ Expected<void> MachineInstr::addMemOperand(const MachineMemOperand &MemOperand)
   return {};
 }
 
+Expected<void> MachineInstr::replaceMemOperand(std::size_t Index,
+                                               const MachineMemOperand &MemOperand) {
+  if (Index >= MemOperands.size()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine memory operand index is out of range");
+  }
+  if (!OwnerFunction->ownsMemOperand(MemOperand)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "replacement memory operand belongs to another function");
+  }
+  MemOperands[Index] = &MemOperand;
+  return {};
+}
+
 Expected<void> MachineInstr::eraseMemOperand(std::size_t Index) {
   if (Index >= MemOperands.size()) {
     return makeUnexpected(ErrorCode::InvalidArgument,
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index 957213b..be7462b 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -657,6 +657,7 @@ private:
     for (const MachineMemOperand *MemOperand : Instruction.memOperands()) {
       const MemoryBase &Base = MemOperand->description().Base;
       if (const auto Frame = Base.frameIndex()) {
+        HasFrameIndex = true;
         auto FrameResult = verifyFrameIndex(*Frame);
         if (!FrameResult)
           return FrameResult;
@@ -849,6 +850,8 @@ private:
         (!Has(MachineFunctionProperty::NoVRegs) || !Has(MachineFunctionProperty::NoFrameIndices))) {
       return fail("FrameFinalized requires NoVRegs and NoFrameIndices");
     }
+    if (Has(MachineFunctionProperty::FrameFinalized) && !Function.frameInfo().isFrozen())
+      return fail("FrameFinalized requires a frozen frame layout");
 
     if (Has(MachineFunctionProperty::IsSSA)) {
       for (const auto &[Reg, DefinitionCount] : VirtualDefCounts) {
diff --git a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp
new file mode 100644
index 0000000..acbcbcf
--- /dev/null
+++ b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp
@@ -0,0 +1,166 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/PrologueEpilogueInsertion.h"
+
+#include "rcc/CodeGen/FrameIndexElimination.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/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/RegisterScavenger.h"
+#include "rcc/CodeGen/TargetFrameLowering.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+} // namespace
+
+const MachinePassContract &PrologueEpilogueInsertionPass::contract() const noexcept {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "PrologueEpilogueInsertion",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten, MachineFunctionProperty::NoVRegs},
+        .Sets = {MachineFunctionProperty::FrameFinalized, MachineFunctionProperty::NoFrameIndices},
+        .Clears = {},
+        .RequiredAnalyses = {},
+        .VerificationStage = PipelineStage::FrameFinalized,
+    };
+    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+    Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                             MachinePassChange::Registers, MachinePassChange::Frame};
+    return Value;
+  }();
+  return Contract;
+}
+
+Expected<MachinePassResult> PrologueEpilogueInsertionPass::run(MachineFunction &Function,
+                                                               const TargetDescription &Target,
+                                                               MachineAnalysisManager &) {
+  if (Info == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "PrologueEpilogueInsertion requires target frame lowering");
+  const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "PrologueEpilogueInsertion requires properties: " + Missing.toString());
+  }
+
+  auto Trial = cloneMachineFunction(
+      Function, Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (!Trial)
+    return std::unexpected(prefixedError(Trial.error(), "frame transaction setup failed: "));
+  auto TrialRun = runImplementation(*Trial->ClonedFunction, Target);
+  if (!TrialRun)
+    return std::unexpected(prefixedError(TrialRun.error(), "frame transaction rejected input: "));
+  auto Transition = Trial->ClonedFunction->properties().applyTransition(
+      contract().Requires, contract().Sets, contract().Clears);
+  if (!Transition) {
+    return std::unexpected(
+        prefixedError(Transition.error(), "frame transaction property update failed: "));
+  }
+  auto Verified =
+      MachineVerifier::verify(*Trial->ClonedFunction, Target,
+                              MachineVerifierOptions{.Mode = MachineVerifierMode::Generic,
+                                                     .Stage = contract().VerificationStage,
+                                                     .VerifyProperties = true});
+  if (!Verified) {
+    return std::unexpected(
+        prefixedError(Verified.error(), "frame transaction postcondition failed: "));
+  }
+
+  auto Result = runImplementation(Function, Target);
+  if (!Result) {
+    return std::unexpected(prefixedError(
+        Result.error(), "frame lowering diverged after successful transaction preflight: "));
+  }
+  return Result;
+}
+
+Expected<MachinePassResult>
+PrologueEpilogueInsertionPass::runImplementation(MachineFunction &Function,
+                                                 const TargetDescription &Target) const {
+  auto Prepared = Info->prepareFrame(Function, Target);
+  if (!Prepared)
+    return std::unexpected(Prepared.error());
+
+  RegisterScavenger Scavenger(Function, Target);
+  std::vector<MachineInstr *> CallFramePseudos;
+  std::vector<std::pair<MachineBasicBlock *, MachineInstr *>> Epilogues;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      if (Info->isCallFramePseudo(*Instruction))
+        CallFramePseudos.push_back(Instruction);
+      if (Info->isEpilogueTerminator(*Instruction, Target))
+        Epilogues.emplace_back(Block, Instruction);
+    }
+  }
+  for (MachineInstr *Pseudo : CallFramePseudos) {
+    auto Eliminated = Info->eliminateCallFramePseudo(*Pseudo, Function, Target, Scavenger);
+    if (!Eliminated)
+      return std::unexpected(Eliminated.error());
+  }
+
+  auto CalleeSaved = Info->insertCalleeSavedSpillsAndRestores(Function, Target);
+  if (!CalleeSaved)
+    return std::unexpected(CalleeSaved.error());
+
+  auto PreFinalized = Info->processFunctionBeforeFrameFinalized(Function, Target);
+  if (!PreFinalized)
+    return std::unexpected(PreFinalized.error());
+
+  auto Finalized = Info->finalizeFrame(Function, Target);
+  if (!Finalized)
+    return std::unexpected(Finalized.error());
+  if (!Function.frameInfo().isFrozen()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "target frame lowering did not freeze the frame layout");
+  }
+
+  auto Prologue = Info->emitPrologue(Function, Target, Scavenger);
+  if (!Prologue)
+    return std::unexpected(Prologue.error());
+  for (const auto &[Block, Terminator] : Epilogues) {
+    auto Epilogue = Info->emitEpilogue(*Block, *Terminator, Function, Target, Scavenger);
+    if (!Epilogue)
+      return std::unexpected(Epilogue.error());
+  }
+
+  auto PreFrameIndices = Info->processFunctionBeforeFrameIndexElimination(Function, Target);
+  if (!PreFrameIndices)
+    return std::unexpected(PreFrameIndices.error());
+
+  auto FrameIndices = eliminateFrameIndices(Function, Target, *Info, Scavenger);
+  if (!FrameIndices)
+    return std::unexpected(FrameIndices.error());
+
+  if (Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    auto Rebuilt = rebuildMachineLiveness(Function, Target);
+    if (!Rebuilt)
+      return std::unexpected(Rebuilt.error());
+  }
+
+  MachinePassResult Result;
+  Result.Changed = true;
+  Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                    MachinePassChange::Registers, MachinePassChange::Frame};
+  Result.Preserved = PreservedAnalyses::none();
+  return Result;
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp
index 4bb7b23..7f88f25 100644
--- a/backend/lib/CodeGen/RegAllocBasic.cpp
+++ b/backend/lib/CodeGen/RegAllocBasic.cpp
@@ -42,7 +42,7 @@ private:
         if (!Marked)
           return std::unexpected(Marked.error());
       }
-      auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg);
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg);
       if (!Candidates)
         return std::unexpected(Candidates.error());
       bool Assigned = false;
@@ -105,6 +105,12 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
   auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
   if (!Trial)
     return std::unexpected(Trial.error());
+  const std::vector<PhysicalRegister> FunctionReserved =
+      regalloc_detail::functionReservedRegisters(Function, Target, *Info);
+  auto TrialReserved =
+      regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved);
+  if (!TrialReserved)
+    return std::unexpected(TrialReserved.error());
   MachineAnalysisManager TrialAnalyses;
   auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
   if (!Registered)
@@ -124,6 +130,10 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
     return std::unexpected(regalloc_detail::withPrefix(
         Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: "));
   }
+  auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
+  if (!Reserved)
+    return std::unexpected(Reserved.error());
+  Allocated->Changed |= *Reserved;
   return regalloc_detail::passResult(*Allocated);
 }
 
diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp
index 9b087cc..897f217 100644
--- a/backend/lib/CodeGen/RegAllocFast.cpp
+++ b/backend/lib/CodeGen/RegAllocFast.cpp
@@ -266,7 +266,7 @@ private:
         return std::unexpected(Evicted.error());
     }
 
-    auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg);
+    auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, Reg);
     if (!Candidates)
       return std::unexpected(Candidates.error());
     for (const PhysicalRegister Candidate : *Candidates) {
@@ -319,7 +319,7 @@ private:
       const Register Reg = *LiveIn.InitialVirtualRegister;
       if (!Function.registerInfo().isKnownVirtualRegister(Reg))
         continue;
-      auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg);
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, Reg);
       if (!Candidates)
         return std::unexpected(Candidates.error());
       if (std::ranges::find(*Candidates, LiveIn.PhysReg) == Candidates->end()) {
@@ -577,6 +577,12 @@ Expected<MachinePassResult> FastAllocatorPass::run(MachineFunction &Function,
   auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
   if (!Trial)
     return std::unexpected(Trial.error());
+  const std::vector<PhysicalRegister> FunctionReserved =
+      regalloc_detail::functionReservedRegisters(Function, Target, *Info);
+  auto TrialReserved =
+      regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved);
+  if (!TrialReserved)
+    return std::unexpected(TrialReserved.error());
   MachineAnalysisManager TrialAnalyses;
   auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
   if (!Registered)
@@ -602,6 +608,10 @@ Expected<MachinePassResult> FastAllocatorPass::run(MachineFunction &Function,
     return std::unexpected(regalloc_detail::withPrefix(
         Allocated.error(), "FastAllocator diverged after a successful transaction preflight: "));
   }
+  auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
+  if (!Reserved)
+    return std::unexpected(Reserved.error());
+  Allocated->Changed |= *Reserved;
   return regalloc_detail::passResult(*Allocated);
 }
 
diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h
index 5d0f434..5cd98e8 100644
--- a/backend/lib/CodeGen/RegAllocInternal.h
+++ b/backend/lib/CodeGen/RegAllocInternal.h
@@ -16,6 +16,7 @@
 #include "rcc/CodeGen/MachineVerifier.h"
 #include "rcc/CodeGen/RegAllocCommon.h"
 #include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
 #include "rcc/CodeGen/TargetRegisterInfo.h"
 #include "rcc/CodeGen/VirtRegMap.h"
 
@@ -87,7 +88,7 @@ struct AllocationRunResult final {
 
 [[nodiscard]] inline Expected<std::vector<PhysicalRegister>>
 allocationOrder(const MachineFunction &Function, const TargetDescription &Target,
-                Register VirtualReg) {
+                const TargetRegisterAllocationInfo &TargetInfo, Register VirtualReg) {
   auto ClassID = registerClassFor(Function, VirtualReg);
   if (!ClassID)
     return std::unexpected(ClassID.error());
@@ -113,11 +114,45 @@ allocationOrder(const MachineFunction &Function, const TargetDescription &Target
   }
   std::erase_if(Result, [&](PhysicalRegister Candidate) {
     return isUnavailablePhysicalRegister(Function, Target.registers(), Candidate) ||
+           TargetInfo.isReservedForFunction(Function, Candidate, Target) ||
            !candidateSupportsSubRegisters(Function, Target.registers(), VirtualReg, Candidate);
   });
   return Result;
 }
 
+[[nodiscard]] inline std::vector<PhysicalRegister>
+functionReservedRegisters(const MachineFunction &Function, const TargetDescription &Target,
+                          const TargetRegisterAllocationInfo &TargetInfo) {
+  std::vector<PhysicalRegister> Roots;
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    if (TargetInfo.isReservedForFunction(Function, Description.Reg, Target))
+      Roots.push_back(Description.Reg);
+  }
+  std::vector<PhysicalRegister> Result;
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    if (std::ranges::any_of(Roots, [&](PhysicalRegister Root) {
+          return Target.registers().regsOverlap(Description.Reg, Root);
+        })) {
+      Result.push_back(Description.Reg);
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] inline Expected<bool>
+reserveFunctionRegisters(MachineFunction &Function, std::span<const PhysicalRegister> Registers) {
+  bool Changed = false;
+  for (const PhysicalRegister Reg : Registers) {
+    if (Function.registerInfo().isReserved(Reg))
+      continue;
+    auto Reserved = Function.registerInfo().reservePhysicalRegister(Reg);
+    if (!Reserved)
+      return std::unexpected(Reserved.error());
+    Changed = true;
+  }
+  return Changed;
+}
+
 [[nodiscard]] inline MachineInstr *firstTerminator(MachineBasicBlock &Block,
                                                    const TargetDescription &Target) noexcept {
   for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp
index 5e56728..a5a12f7 100644
--- a/backend/lib/CodeGen/RegAllocPBQP.cpp
+++ b/backend/lib/CodeGen/RegAllocPBQP.cpp
@@ -84,7 +84,7 @@ private:
       auto ClassID = regalloc_detail::registerClassFor(Function, VirtualReg);
       if (!ClassID)
         return std::unexpected(ClassID.error());
-      auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg);
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg);
       if (!Candidates)
         return std::unexpected(Candidates.error());
       std::erase_if(*Candidates, [&](PhysicalRegister Candidate) {
@@ -257,6 +257,12 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
   auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
   if (!Trial)
     return std::unexpected(Trial.error());
+  const std::vector<PhysicalRegister> FunctionReserved =
+      regalloc_detail::functionReservedRegisters(Function, Target, *Info);
+  auto TrialReserved =
+      regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved);
+  if (!TrialReserved)
+    return std::unexpected(TrialReserved.error());
   MachineAnalysisManager TrialAnalyses;
   auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
   if (!Registered)
@@ -275,6 +281,10 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
     return std::unexpected(regalloc_detail::withPrefix(
         Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: "));
   }
+  auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
+  if (!Reserved)
+    return std::unexpected(Reserved.error());
+  Allocated->Changed |= *Reserved;
   return regalloc_detail::passResult(*Allocated);
 }
 
diff --git a/backend/lib/CodeGen/RegisterScavenger.cpp b/backend/lib/CodeGen/RegisterScavenger.cpp
new file mode 100644
index 0000000..386c327
--- /dev/null
+++ b/backend/lib/CodeGen/RegisterScavenger.cpp
@@ -0,0 +1,226 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/RegisterScavenger.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <optional>
+#include <ranges>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] std::optional<PhysicalRegister>
+physicalRegister(const MachineOperand &Operand) noexcept {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || !Reg->isPhysical())
+    return std::nullopt;
+  return Reg->physicalRegister();
+}
+
+[[nodiscard]] bool maskClobbersRegisterUnits(const RegisterMask &Mask, PhysicalRegister Reg,
+                                             const TargetDescription &Target) noexcept {
+  return std::ranges::any_of(Target.registers().physicalRegisters(),
+                             [&](const PhysicalRegisterDesc &Description) {
+                               return Target.registers().regsOverlap(Description.Reg, Reg) &&
+                                      Mask.clobbers(Description.Reg);
+                             });
+}
+
+[[nodiscard]] bool maskPreservesRegisterUnits(const RegisterMask &Mask, PhysicalRegister Reg,
+                                              const TargetDescription &Target) noexcept {
+  return std::ranges::any_of(Target.registers().physicalRegisters(),
+                             [&](const PhysicalRegisterDesc &Description) {
+                               return Target.registers().regsOverlap(Description.Reg, Reg) &&
+                                      Mask.preserves(Description.Reg);
+                             });
+}
+
+[[nodiscard]] bool isUnavailable(const MachineFunction &Function, const TargetDescription &Target,
+                                 PhysicalRegister Reg) noexcept {
+  const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg);
+  if (Description == nullptr || Description->IsConstant || Description->IsArtificial ||
+      Description->IsReserved || Target.registers().isReservedRegister(Reg)) {
+    return true;
+  }
+  return std::ranges::any_of(
+      Function.registerInfo().reservedRegisters(),
+      [&](PhysicalRegister Reserved) { return Target.registers().regsOverlap(Reg, Reserved); });
+}
+
+} // namespace
+
+bool RegisterScavenger::instructionUses(const MachineInstr &Instruction,
+                                        PhysicalRegister Reg) const noexcept {
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    const auto Physical = physicalRegister(Operand);
+    if (Physical && Target->registers().regsOverlap(*Physical, Reg))
+      return true;
+  }
+  return false;
+}
+
+Expected<bool> RegisterScavenger::isLiveBefore(const MachineInstr &Instruction,
+                                               PhysicalRegister Reg) const {
+  const MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr || &Instruction.function() != Function || &Block->function() != Function) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "register scavenging anchor is detached or belongs to another function");
+  }
+
+  std::vector<const MachineBasicBlock *> Blocks;
+  std::unordered_map<const MachineBasicBlock *, std::size_t> BlockIndices;
+  for (const MachineBasicBlock *Current = Function->firstBlock(); Current != nullptr;
+       Current = Current->next()) {
+    BlockIndices.emplace(Current, Blocks.size());
+    Blocks.push_back(Current);
+  }
+
+  if (!BlockIndices.contains(Block)) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "register scavenging anchor block is not linked in its function");
+  }
+  for (const MachineBasicBlock *Current : Blocks) {
+    for (const MachineSuccessor &Successor : Current->successors()) {
+      if (Successor.Block == nullptr || !BlockIndices.contains(Successor.Block)) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "register scavenging CFG has an unknown successor");
+      }
+    }
+    for (const MachineInstr *CurrentInstruction = Current->firstInstruction();
+         CurrentInstruction != nullptr; CurrentInstruction = CurrentInstruction->next()) {
+      for (const MachineOperand &Operand : CurrentInstruction->operands()) {
+        if (const auto *Mask = Operand.getIf<RegisterMaskOperand>();
+            Mask != nullptr && !Mask->Mask) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "register scavenging found a null register mask");
+        }
+        if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>();
+            Mask != nullptr && !Mask->Mask) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "register scavenging found a null live-out register mask");
+        }
+      }
+    }
+  }
+
+  const auto Transfer = [&](const MachineBasicBlock &Current, bool LiveOut) noexcept {
+    bool Live = LiveOut;
+    for (const MachineInstr *CurrentInstruction = Current.lastInstruction();
+         CurrentInstruction != nullptr; CurrentInstruction = CurrentInstruction->previous()) {
+      for (const MachineOperand &Operand : CurrentInstruction->operands()) {
+        if (const auto *Mask = Operand.getIf<RegisterMaskOperand>();
+            Mask != nullptr && maskClobbersRegisterUnits(*Mask->Mask, Reg, *Target)) {
+          Live = false;
+        }
+        const auto Physical = physicalRegister(Operand);
+        if (Physical && Operand.isDef() && Target->registers().regsOverlap(*Physical, Reg)) {
+          Live = false;
+        }
+      }
+      for (const MachineOperand &Operand : CurrentInstruction->operands()) {
+        if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>();
+            Mask != nullptr && maskPreservesRegisterUnits(*Mask->Mask, Reg, *Target)) {
+          Live = true;
+        }
+        const auto Physical = physicalRegister(Operand);
+        if (Physical && Operand.isUse() && !Operand.isDebugUse() &&
+            !Operand.registerFlags().has(RegisterOperandFlag::Undef) &&
+            Target->registers().regsOverlap(*Physical, Reg)) {
+          Live = true;
+        }
+      }
+    }
+    return Live;
+  };
+
+  std::vector<bool> LiveIns(Blocks.size(), false);
+  for (std::size_t Index = 0; Index < Blocks.size(); ++Index) {
+    for (const MachineBasicBlockLiveIn &LiveIn : Blocks[Index]->liveIns()) {
+      if (Target->registers().regsOverlap(LiveIn.PhysReg, Reg))
+        LiveIns[Index] = true;
+    }
+  }
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (std::size_t Reverse = Blocks.size(); Reverse != 0; --Reverse) {
+      const std::size_t Index = Reverse - 1U;
+      bool LiveOut = false;
+      for (const MachineSuccessor &Successor : Blocks[Index]->successors()) {
+        LiveOut |= LiveIns[BlockIndices.at(Successor.Block)];
+      }
+      const bool NewLiveIn = LiveIns[Index] || Transfer(*Blocks[Index], LiveOut);
+      if (NewLiveIn != LiveIns[Index]) {
+        LiveIns[Index] = NewLiveIn;
+        Changed = true;
+      }
+    }
+  }
+
+  bool Live = false;
+  for (const MachineSuccessor &Successor : Block->successors()) {
+    Live |= LiveIns[BlockIndices.at(Successor.Block)];
+  }
+
+  for (const MachineInstr *Current = Block->lastInstruction(); Current != nullptr;
+       Current = Current->previous()) {
+    for (const MachineOperand &Operand : Current->operands()) {
+      if (const auto *Mask = Operand.getIf<RegisterMaskOperand>();
+          Mask != nullptr && maskClobbersRegisterUnits(*Mask->Mask, Reg, *Target)) {
+        Live = false;
+      }
+      const auto Physical = physicalRegister(Operand);
+      if (Physical && Operand.isDef() && Target->registers().regsOverlap(*Physical, Reg))
+        Live = false;
+    }
+    for (const MachineOperand &Operand : Current->operands()) {
+      if (const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>();
+          Mask != nullptr && maskPreservesRegisterUnits(*Mask->Mask, Reg, *Target)) {
+        Live = true;
+      }
+      const auto Physical = physicalRegister(Operand);
+      if (Physical && Operand.isUse() && !Operand.isDebugUse() &&
+          !Operand.registerFlags().has(RegisterOperandFlag::Undef) &&
+          Target->registers().regsOverlap(*Physical, Reg))
+        Live = true;
+    }
+    if (Current == &Instruction)
+      return Live;
+  }
+  return true;
+}
+
+Expected<ScavengedRegister>
+RegisterScavenger::scavenge(const MachineInstr &Instruction,
+                            std::span<const PhysicalRegister> Candidates) const {
+  std::optional<PhysicalRegister> SpillCandidate;
+  for (const PhysicalRegister Candidate : Candidates) {
+    if (!Candidate.isValid() || isUnavailable(*Function, *Target, Candidate) ||
+        instructionUses(Instruction, Candidate)) {
+      continue;
+    }
+    if (!SpillCandidate)
+      SpillCandidate = Candidate;
+    auto Live = isLiveBefore(Instruction, Candidate);
+    if (!Live)
+      return std::unexpected(Live.error());
+    if (!*Live)
+      return ScavengedRegister{Candidate, false};
+  }
+  if (SpillCandidate)
+    return ScavengedRegister{*SpillCandidate, true};
+  return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                        "register scavenging found no usable physical register");
+}
+
+} // namespace rcc