[CodeGen] Implement RV64GC frame lowering

29 files changed, 4264 insertions, 9 deletions

diff --git a/backend/include/rcc/CodeGen/FrameIndexElimination.h b/backend/include/rcc/CodeGen/FrameIndexElimination.h
new file mode 100644
index 0000000..df67479
--- /dev/null
+++ b/backend/include/rcc/CodeGen/FrameIndexElimination.h
@@ -0,0 +1,22 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_FRAMEINDEXELIMINATION_H
+#define RCC_CODEGEN_FRAMEINDEXELIMINATION_H
+
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+class MachineFunction;
+class RegisterScavenger;
+class TargetDescription;
+class TargetFrameLowering;
+
+[[nodiscard]] Expected<bool> eliminateFrameIndices(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   const TargetFrameLowering &FrameLowering,
+                                                   RegisterScavenger &Scavenger);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_FRAMEINDEXELIMINATION_H
diff --git a/backend/include/rcc/CodeGen/MachineInstr.h b/backend/include/rcc/CodeGen/MachineInstr.h
index e7294b4..84d2f0e 100644
--- a/backend/include/rcc/CodeGen/MachineInstr.h
+++ b/backend/include/rcc/CodeGen/MachineInstr.h
@@ -98,6 +98,8 @@ public:
   [[nodiscard]] Expected<void> untieOperand(std::size_t Index);
 
   [[nodiscard]] Expected<void> addMemOperand(const MachineMemOperand &MemOperand);
+  [[nodiscard]] Expected<void> replaceMemOperand(std::size_t Index,
+                                                 const MachineMemOperand &MemOperand);
   [[nodiscard]] Expected<void> eraseMemOperand(std::size_t Index);
   [[nodiscard]] std::span<const MachineMemOperand *const> memOperands() const noexcept {
     return MemOperands;
diff --git a/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h
new file mode 100644
index 0000000..b94715a
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PrologueEpilogueInsertion.h
@@ -0,0 +1,30 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
+#define RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
+
+#include "rcc/CodeGen/MachinePass.h"
+
+namespace rcc {
+
+class TargetFrameLowering;
+
+class PrologueEpilogueInsertionPass final : public MachineFunctionPass {
+public:
+  explicit PrologueEpilogueInsertionPass(const TargetFrameLowering &Info) noexcept : Info(&Info) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  [[nodiscard]] Expected<MachinePassResult>
+  runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+
+  const TargetFrameLowering *Info;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_PROLOGUEEPILOGUEINSERTION_H
diff --git a/backend/include/rcc/CodeGen/RegisterScavenger.h b/backend/include/rcc/CodeGen/RegisterScavenger.h
new file mode 100644
index 0000000..6351b98
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegisterScavenger.h
@@ -0,0 +1,42 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGISTERSCAVENGER_H
+#define RCC_CODEGEN_REGISTERSCAVENGER_H
+
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <span>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+struct ScavengedRegister final {
+  PhysicalRegister Reg;
+  bool RequiresSpill = false;
+};
+
+class RegisterScavenger final {
+public:
+  RegisterScavenger(const MachineFunction &Function, const TargetDescription &Target) noexcept
+      : Function(&Function), Target(&Target) {}
+
+  [[nodiscard]] Expected<ScavengedRegister>
+  scavenge(const MachineInstr &Instruction, std::span<const PhysicalRegister> Candidates) const;
+
+private:
+  [[nodiscard]] Expected<bool> isLiveBefore(const MachineInstr &Instruction,
+                                            PhysicalRegister Reg) const;
+  [[nodiscard]] bool instructionUses(const MachineInstr &Instruction,
+                                     PhysicalRegister Reg) const noexcept;
+
+  const MachineFunction *Function;
+  const TargetDescription *Target;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGISTERSCAVENGER_H
diff --git a/backend/include/rcc/CodeGen/TargetFrameLowering.h b/backend/include/rcc/CodeGen/TargetFrameLowering.h
new file mode 100644
index 0000000..1712616
--- /dev/null
+++ b/backend/include/rcc/CodeGen/TargetFrameLowering.h
@@ -0,0 +1,73 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_TARGETFRAMELOWERING_H
+#define RCC_CODEGEN_TARGETFRAMELOWERING_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineInstr;
+class RegisterScavenger;
+class TargetDescription;
+
+struct FrameIndexReference final {
+  PhysicalRegister BaseRegister;
+  std::int64_t Offset = 0;
+};
+
+class TargetFrameLowering {
+public:
+  virtual ~TargetFrameLowering() = default;
+
+  [[nodiscard]] virtual Expected<void> prepareFrame(MachineFunction &Function,
+                                                    const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  insertCalleeSavedSpillsAndRestores(MachineFunction &Function,
+                                     const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  processFunctionBeforeFrameFinalized(MachineFunction &, const TargetDescription &) const {
+    return {};
+  }
+  [[nodiscard]] virtual Expected<void> finalizeFrame(MachineFunction &Function,
+                                                     const TargetDescription &Target) const = 0;
+
+  [[nodiscard]] virtual bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept = 0;
+  [[nodiscard]] virtual Expected<void>
+  eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function,
+                           const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0;
+
+  [[nodiscard]] virtual Expected<void> emitPrologue(MachineFunction &Function,
+                                                    const TargetDescription &Target,
+                                                    RegisterScavenger &Scavenger) const = 0;
+  [[nodiscard]] virtual bool
+  isEpilogueTerminator(const MachineInstr &Instruction,
+                       const TargetDescription &Target) const noexcept = 0;
+  [[nodiscard]] virtual Expected<void>
+  emitEpilogue(MachineBasicBlock &Block, MachineInstr &Terminator, MachineFunction &Function,
+               const TargetDescription &Target, RegisterScavenger &Scavenger) const = 0;
+  [[nodiscard]] virtual Expected<void>
+  processFunctionBeforeFrameIndexElimination(MachineFunction &, const TargetDescription &) const {
+    return {};
+  }
+
+  [[nodiscard]] virtual Expected<FrameIndexReference>
+  getFrameIndexReference(const MachineFunction &Function, const MachineInstr &Instruction,
+                         FrameIndex Index, std::int64_t OperandOffset) const = 0;
+  [[nodiscard]] virtual Expected<void> eliminateFrameIndex(MachineInstr &Instruction,
+                                                           std::size_t OperandIndex,
+                                                           MachineFunction &Function,
+                                                           const TargetDescription &Target,
+                                                           RegisterScavenger &Scavenger) const = 0;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_TARGETFRAMELOWERING_H
diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
index 6e25465..4448933 100644
--- a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
+++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
@@ -51,6 +51,11 @@ public:
                                                 RegisterClassID) const noexcept {
     return 1;
   }
+
+  [[nodiscard]] virtual bool isReservedForFunction(const MachineFunction &, PhysicalRegister,
+                                                   const TargetDescription &) const noexcept {
+    return false;
+  }
 };
 
 } // namespace rcc
diff --git a/backend/include/rcc/Support/Error.h b/backend/include/rcc/Support/Error.h
index 81568de..44ff967 100644
--- a/backend/include/rcc/Support/Error.h
+++ b/backend/include/rcc/Support/Error.h
@@ -19,6 +19,7 @@ enum class ErrorCode : std::uint8_t {
   RegisterAllocationFailed,
   IoError,
   InternalError,
+  FrameLayoutFailed,
 };
 
 [[nodiscard]] std::string_view getErrorCodeName(ErrorCode Code) noexcept;
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index 403bb2d..0cec77d 100644
--- a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
+++ b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
@@ -4,6 +4,7 @@
 #define RCC_TARGET_RISCV_RISCVCODEGEN_H
 
 #include "rcc/CodeGen/TargetCodeGen.h"
+#include "rcc/CodeGen/TargetFrameLowering.h"
 #include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
 
 namespace rcc::riscv {
@@ -13,6 +14,7 @@ namespace rcc::riscv {
 [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
 [[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept;
 [[nodiscard]] const TargetRegisterAllocationInfo &registerAllocationInfo() noexcept;
+[[nodiscard]] const TargetFrameLowering &frameLowering() noexcept;
 
 } // namespace rcc::riscv
 
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
diff --git a/backend/lib/Support/Error.cpp b/backend/lib/Support/Error.cpp
index 817a2bb..f18cc45 100644
--- a/backend/lib/Support/Error.cpp
+++ b/backend/lib/Support/Error.cpp
@@ -16,6 +16,8 @@ std::string_view getErrorCodeName(ErrorCode Code) noexcept {
     return "unsupported";
   case ErrorCode::RegisterAllocationFailed:
     return "register allocation failed";
+  case ErrorCode::FrameLayoutFailed:
+    return "frame layout failed";
   case ErrorCode::IoError:
     return "I/O error";
   case ErrorCode::InternalError:
diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt
index 1d9a27a..442e75e 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
+  RISCVFrameLowering.cpp
   RISCVRegisterAllocation.cpp
   RISCVTarget.cpp
   "${RCCBackendRISCVGeneratedRegisterHeader}"
@@ -94,6 +95,7 @@ install(
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLowering.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCodeGen.h"
@@ -103,6 +105,7 @@ 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}/RISCVFrameLowering.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp"
 )
diff --git a/backend/lib/Target/RISCV/RISCVFrameLowering.cpp b/backend/lib/Target/RISCV/RISCVFrameLowering.cpp
new file mode 100644
index 0000000..0e6fec9
--- /dev/null
+++ b/backend/lib/Target/RISCV/RISCVFrameLowering.cpp
@@ -0,0 +1,2019 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFIInfo.h"
+#include "rcc/CodeGen/MachineFrameInfo.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/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/RegisterScavenger.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/Target/RISCV/RISCVCallLowering.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 <bit>
+#include <cstddef>
+#include <cstdint>
+#include <iterator>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc::riscv {
+namespace {
+
+constexpr std::uint64_t StackAlignmentBytes = 16;
+constexpr std::int64_t MinSigned12 = -2048;
+constexpr std::int64_t MaxSigned12 = 2047;
+constexpr std::uint8_t DwarfCFAExpression = 0x10U;
+constexpr std::uint8_t DwarfOpBaseRegister0 = 0x70U;
+constexpr std::uint8_t DwarfOpBaseRegisterExtended = 0x92U;
+
+[[nodiscard]] constexpr Opcode targetOpcode(InstructionOpcode Value) noexcept {
+  return Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] Expected<PhysicalRegister> physical(PhysicalRegisterID ID) {
+  return physicalRegister(ID);
+}
+
+[[nodiscard]] constexpr bool fitsSigned12(std::int64_t Value) noexcept {
+  return Value >= MinSigned12 && Value <= MaxSigned12;
+}
+
+[[nodiscard]] constexpr bool hasStackObjectFlag(const StackObjectDesc &Object,
+                                                CallStackObjectFlag Flag) noexcept {
+  return (Object.TargetFlags & static_cast<std::uint64_t>(Flag)) != 0;
+}
+
+[[nodiscard]] constexpr bool isOutgoingCallObject(const StackObjectDesc &Object) noexcept {
+  return Object.Kind == StackObjectKind::Target &&
+         (hasStackObjectFlag(Object, CallStackObjectFlag::OutgoingArgument) ||
+          hasStackObjectFlag(Object, CallStackObjectFlag::ByValCopy));
+}
+
+[[nodiscard]] Expected<std::int64_t> checkedAdd(std::int64_t Left, std::int64_t Right) {
+  std::int64_t Result = 0;
+  if (__builtin_add_overflow(Left, Right, &Result))
+    return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame offset overflows int64");
+  return Result;
+}
+
+[[nodiscard]] Expected<std::uint64_t> alignTo(std::uint64_t Value, std::uint64_t Align) {
+  if (Align == 0 || !std::has_single_bit(Align))
+    return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V frame alignment is invalid");
+  const std::uint64_t Mask = Align - 1U;
+  if (Value > std::numeric_limits<std::uint64_t>::max() - Mask)
+    return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame size overflows uint64");
+  return (Value + Mask) & ~Mask;
+}
+
+[[nodiscard]] Expected<std::int64_t> immediateValue(const MachineOperand &Operand) {
+  if (const auto *Immediate = Operand.getIf<std::int64_t>())
+    return *Immediate;
+  const auto *Integer = Operand.getIf<IntegerImmediateOperand>();
+  if (Integer == nullptr || Integer->Value.bitWidth() == 0) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V frame operand requires an integer immediate");
+  }
+  if (Integer->Value.bitWidth() > 64) {
+    return makeUnexpected(ErrorCode::Unsupported, "RISC-V frame immediate must fit in 64 bits");
+  }
+  std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front();
+  const std::uint32_t Width = Integer->Value.bitWidth();
+  if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0)
+    Raw |= ~std::uint64_t{0} << Width;
+  return std::bit_cast<std::int64_t>(Raw);
+}
+
+struct CallFrameRequirement final {
+  std::int64_t Amount = 0;
+  std::int64_t Alignment = 0;
+  std::int64_t AlignedAmount = 0;
+};
+
+[[nodiscard]] Expected<CallFrameRequirement> callFrameRequirement(const MachineInstr &Instruction) {
+  if (Instruction.operandCount() != 2) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V call-frame pseudo requires exactly amount and alignment");
+  }
+  auto Amount = immediateValue(*Instruction.operandAt(0));
+  auto RequestedAlignment = immediateValue(*Instruction.operandAt(1));
+  if (!Amount || !RequestedAlignment || *Amount < 0 || *RequestedAlignment <= 0 ||
+      !std::has_single_bit(static_cast<std::uint64_t>(*RequestedAlignment))) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V call-frame amount or alignment is invalid");
+  }
+  const std::uint64_t Alignment =
+      std::max(StackAlignmentBytes, static_cast<std::uint64_t>(*RequestedAlignment));
+  auto Aligned = alignTo(static_cast<std::uint64_t>(*Amount), Alignment);
+  if (!Aligned || *Aligned > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+    return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V call-frame amount is too large");
+  }
+  return CallFrameRequirement{*Amount, *RequestedAlignment, static_cast<std::int64_t>(*Aligned)};
+}
+
+[[nodiscard]] Expected<std::int64_t> callFrameAmount(const MachineInstr &Instruction) {
+  auto Requirement = callFrameRequirement(Instruction);
+  if (!Requirement)
+    return std::unexpected(Requirement.error());
+  return Requirement->AlignedAmount;
+}
+
+[[nodiscard]] bool hasVariableObject(const MachineFunction &Function) noexcept {
+  return std::ranges::any_of(Function.frameInfo().objects(), [](const StackObject &Object) {
+    return !Object.isTombstone() && !Object.description()->IsDead && Object.isVariableSized();
+  });
+}
+
+[[nodiscard]] std::uint64_t requiredStackAlignment(const MachineFunction &Function) noexcept {
+  std::uint64_t Result = StackAlignmentBytes;
+  Result =
+      std::max(Result, Function.frameInfo().state().MaxAlignment.value_or(Alignment{}).bytes());
+  for (const StackObject &Object : Function.frameInfo().objects()) {
+    if (!Object.isTombstone() && !Object.description()->IsDead)
+      Result = std::max(Result, Object.description()->Align.bytes());
+  }
+  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() != targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) &&
+          Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKUP)) {
+        continue;
+      }
+      if (Instruction->operandCount() < 2)
+        continue;
+      auto Requested = immediateValue(*Instruction->operandAt(1));
+      if (Requested && *Requested > 0 &&
+          std::has_single_bit(static_cast<std::uint64_t>(*Requested))) {
+        Result = std::max(Result, static_cast<std::uint64_t>(*Requested));
+      }
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] bool requiresStackRealignment(const MachineFunction &Function) noexcept {
+  return requiredStackAlignment(Function) > StackAlignmentBytes;
+}
+
+[[nodiscard]] bool requiresFramePointer(const MachineFunction &Function) noexcept {
+  const MachineFrameState &State = Function.frameInfo().state();
+  if (State.IsFrameAddressTaken || State.HasOpaqueSPAdjustment || hasVariableObject(Function) ||
+      requiresStackRealignment(Function))
+    return true;
+  switch (State.FramePointerPolicy) {
+  case MachineFramePointerPolicy::All:
+    return true;
+  case MachineFramePointerPolicy::NonLeaf:
+  case MachineFramePointerPolicy::NonLeafNoReserve:
+    return State.HasCalls;
+  case MachineFramePointerPolicy::None:
+  case MachineFramePointerPolicy::Reserved:
+  case MachineFramePointerPolicy::Count:
+    return false;
+  }
+  return false;
+}
+
+[[nodiscard]] bool requiresBasePointer(const MachineFunction &Function) noexcept {
+  return requiresStackRealignment(Function);
+}
+
+[[nodiscard]] Expected<void> validateFrameRegisterUses(const MachineFunction &Function,
+                                                       const TargetDescription &Target) {
+  std::vector<PhysicalRegister> FrameRegisters;
+  if (requiresFramePointer(Function)) {
+    auto FP = physical(PhysicalRegisterID::X8);
+    if (!FP)
+      return std::unexpected(FP.error());
+    FrameRegisters.push_back(*FP);
+  }
+  if (requiresBasePointer(Function)) {
+    auto BP = physical(PhysicalRegisterID::X9);
+    if (!BP)
+      return std::unexpected(BP.error());
+    FrameRegisters.push_back(*BP);
+  }
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    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())
+          continue;
+        const auto Physical = Reg->physicalRegister();
+        if (Physical && std::ranges::any_of(FrameRegisters, [&](PhysicalRegister FrameReg) {
+              return Target.registers().regsOverlap(*Physical, FrameReg);
+            })) {
+          return makeUnexpected(
+              ErrorCode::VerificationError,
+              "RISC-V post-allocation code uses a register reserved for frame lowering");
+        }
+      }
+    }
+  }
+  if (!requiresStackRealignment(Function))
+    return {};
+  auto OldFPScratch = physical(PhysicalRegisterID::X5);
+  if (!OldFPScratch)
+    return std::unexpected(OldFPScratch.error());
+  const auto OverlapsScratch = [&](PhysicalRegister Reg) {
+    return Target.registers().regsOverlap(Reg, *OldFPScratch);
+  };
+  if (std::ranges::any_of(Function.registerInfo().liveIns(), [&](const PhysicalRegisterLiveIn &In) {
+        return OverlapsScratch(In.PhysReg);
+      })) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V realignment scratch register is a function live-in");
+  }
+  const MachineBasicBlock *Entry = Function.firstBlock();
+  if (Entry == nullptr)
+    return {};
+  if (std::ranges::any_of(Entry->liveIns(), [&](const MachineBasicBlockLiveIn &In) {
+        return OverlapsScratch(In.PhysReg);
+      })) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V realignment scratch register is an entry live-in");
+  }
+  bool Defined = false;
+  for (const MachineInstr *Instruction = Entry->firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      const Register *Reg = Operand.getIf<Register>();
+      const auto Physical =
+          Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt;
+      if (Physical && OverlapsScratch(*Physical) && Operand.isUse() && !Operand.isDebugUse() &&
+          !Operand.registerFlags().has(RegisterOperandFlag::Undef) && !Defined) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "RISC-V realignment scratch register is used before its first def");
+      }
+    }
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      const Register *Reg = Operand.getIf<Register>();
+      const auto Physical =
+          Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt;
+      Defined |= Physical && OverlapsScratch(*Physical) && Operand.isDef();
+      if (const auto *Mask = Operand.getIf<RegisterMaskOperand>();
+          Mask != nullptr && Mask->Mask && Mask->Mask->clobbers(*OldFPScratch)) {
+        Defined = true;
+      }
+    }
+  }
+  return {};
+}
+
+[[nodiscard]] bool hasReservedCallFrame(const MachineFunction &Function) noexcept {
+  const MachineFrameState &State = Function.frameInfo().state();
+  return !hasVariableObject(Function) && !State.HasOpaqueSPAdjustment;
+}
+
+[[nodiscard]] Expected<void> computeMaxCallFrameSize(MachineFunction &Function) {
+  std::uint64_t Maximum = Function.frameInfo().maxCallFrameSize().value_or(0);
+  bool SawPseudo = false;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    std::optional<CallFrameRequirement> Active;
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const bool IsDown =
+          Instruction->opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN);
+      const bool IsUp = Instruction->opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKUP);
+      if (!IsDown && !IsUp)
+        continue;
+      SawPseudo = true;
+      auto Requirement = callFrameRequirement(*Instruction);
+      if (!Requirement)
+        return std::unexpected(Requirement.error());
+      if (IsDown) {
+        if (Active) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "RISC-V call-frame sequences must not be nested");
+        }
+        Active = *Requirement;
+        Maximum = std::max(Maximum, static_cast<std::uint64_t>(Requirement->AlignedAmount));
+        continue;
+      }
+      if (!Active) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "RISC-V call-frame destroy has no matching setup");
+      }
+      if (Active->Amount != Requirement->Amount || Active->Alignment != Requirement->Alignment) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "RISC-V call-frame setup and destroy requirements differ");
+      }
+      Active.reset();
+    }
+    if (Active) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V call-frame setup has no matching destroy");
+    }
+  }
+  if (!SawPseudo && !Function.frameInfo().maxCallFrameSize())
+    return {};
+  return Function.frameInfo().setMaxCallFrameSize(Maximum);
+}
+
+[[nodiscard]] std::array<PhysicalRegisterID, 25> saveOrder() noexcept {
+  return {
+      PhysicalRegisterID::X1,  PhysicalRegisterID::X8,  PhysicalRegisterID::X9,
+      PhysicalRegisterID::X18, PhysicalRegisterID::X19, PhysicalRegisterID::X20,
+      PhysicalRegisterID::X21, PhysicalRegisterID::X22, PhysicalRegisterID::X23,
+      PhysicalRegisterID::X24, PhysicalRegisterID::X25, PhysicalRegisterID::X26,
+      PhysicalRegisterID::X27, PhysicalRegisterID::F8,  PhysicalRegisterID::F9,
+      PhysicalRegisterID::F18, PhysicalRegisterID::F19, PhysicalRegisterID::F20,
+      PhysicalRegisterID::F21, PhysicalRegisterID::F22, PhysicalRegisterID::F23,
+      PhysicalRegisterID::F24, PhysicalRegisterID::F25, PhysicalRegisterID::F26,
+      PhysicalRegisterID::F27,
+  };
+}
+
+[[nodiscard]] Expected<std::vector<PhysicalRegister>>
+modifiedCalleeSavedRegisters(const MachineFunction &Function, const TargetDescription &Target) {
+  std::unordered_set<PhysicalRegister> Modified;
+  for (const StackObject &Object : Function.frameInfo().objects()) {
+    if (!Object.isTombstone() && !Object.description()->IsDead &&
+        Object.description()->CalleeSavedRegister) {
+      Modified.insert(*Object.description()->CalleeSavedRegister);
+    }
+  }
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); Mask != nullptr) {
+          if (!Mask->Mask) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "RISC-V callee-save analysis found a null register mask");
+          }
+          for (const PhysicalRegisterID ID : saveOrder()) {
+            auto Reg = physical(ID);
+            if (!Reg)
+              return std::unexpected(Reg.error());
+            if (Mask->Mask->clobbers(*Reg))
+              Modified.insert(*Reg);
+          }
+        }
+        const Register *Reg = Operand.getIf<Register>();
+        if (Reg == nullptr || !Reg->isPhysical() || !Operand.isDef())
+          continue;
+        const auto Physical = Reg->physicalRegister();
+        if (Physical)
+          Modified.insert(*Physical);
+      }
+    }
+  }
+
+  std::vector<PhysicalRegister> Result;
+  for (const PhysicalRegisterID ID : saveOrder()) {
+    auto Reg = physical(ID);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    if (Modified.contains(*Reg))
+      Result.push_back(*Reg);
+  }
+  if (requiresFramePointer(Function)) {
+    auto FP = physical(PhysicalRegisterID::X8);
+    if (!FP)
+      return std::unexpected(FP.error());
+    if (std::ranges::find(Result, *FP) == Result.end()) {
+      const auto Position = static_cast<std::vector<PhysicalRegister>::difference_type>(
+          std::min<std::size_t>(1, Result.size()));
+      Result.insert(Result.begin() + Position, *FP);
+    }
+  }
+  if (requiresBasePointer(Function)) {
+    auto BP = physical(PhysicalRegisterID::X9);
+    if (!BP)
+      return std::unexpected(BP.error());
+    if (std::ranges::find(Result, *BP) == Result.end()) {
+      const auto Position = static_cast<std::vector<PhysicalRegister>::difference_type>(
+          std::min<std::size_t>(2, Result.size()));
+      Result.insert(Result.begin() + Position, *BP);
+    }
+  }
+  for (const PhysicalRegister Reg : Result) {
+    if (Target.registers().physicalRegister(Reg) == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V callee-save register is absent from target facts");
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<const MachineMemOperand *>
+createStackMemory(MachineFunction &Function, FrameIndex Index, MemoryAccessFlag Access) {
+  auto Size = MemorySize::fixed(8);
+  auto Align = Alignment::create(8);
+  if (!Size || !Align)
+    return makeUnexpected(ErrorCode::InternalError, "RISC-V spill facts are invalid");
+  MachineMemOperandDesc Description;
+  Description.Accesses = {Access};
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = MemoryBase::frameIndex(Index);
+  return Function.createMemOperand(std::move(Description));
+}
+
+[[nodiscard]] Expected<const MachineMemOperand *>
+createResolvedStackMemory(MachineFunction &Function, MemoryAccessFlag Access, std::int64_t Offset) {
+  auto Size = MemorySize::fixed(8);
+  auto Align = Alignment::create(8);
+  if (!Size || !Align)
+    return makeUnexpected(ErrorCode::InternalError, "RISC-V spill facts are invalid");
+  MachineMemOperandDesc Description;
+  Description.Accesses = {Access};
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = MemoryBase::stack();
+  Description.Offset = Offset;
+  return Function.createMemOperand(std::move(Description));
+}
+
+[[nodiscard]] Expected<void> replaceImmediate(MachineInstr &Instruction, std::size_t Index,
+                                              std::int64_t Value) {
+  const MachineOperand *Old = Instruction.operandAt(Index);
+  if (Old == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V frame instruction lacks its offset operand");
+  const std::uint32_t TargetFlags = Old->targetFlags();
+  auto Erased = Instruction.eraseOperand(Index);
+  if (!Erased)
+    return std::unexpected(Erased.error());
+  return Instruction.insertOperand(Index, MachineOperand::immediate(Value, TargetFlags));
+}
+
+[[nodiscard]] Expected<void> replaceWithRegister(MachineInstr &Instruction, std::size_t Index,
+                                                 PhysicalRegister Reg) {
+  const MachineOperand *Old = Instruction.operandAt(Index);
+  if (Old == nullptr)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V frame instruction lacks its frame operand");
+  const std::uint32_t TargetFlags = Old->targetFlags();
+  auto Replacement = MachineOperand::registerOperand(Register::fromPhysical(Reg),
+                                                     {RegisterOperandFlag::Use}, {}, TargetFlags);
+  if (!Replacement)
+    return std::unexpected(Replacement.error());
+  auto Erased = Instruction.eraseOperand(Index);
+  if (!Erased)
+    return std::unexpected(Erased.error());
+  return Instruction.insertOperand(Index, std::move(*Replacement));
+}
+
+[[nodiscard]] Expected<void> setFrameFlag(MachineInstrBuilder &Builder,
+                                          std::optional<MachineInstrFlag> Flag) {
+  if (!Flag)
+    return {};
+  return Builder.setFlags({*Flag});
+}
+
+[[nodiscard]] Expected<DwarfRegisterNumber> dwarfRegister(const TargetDescription &Target,
+                                                          PhysicalRegister Reg) {
+  const auto Number = Target.mirText().dwarfRegister(Reg);
+  if (!Number) {
+    return makeUnexpected(ErrorCode::InternalError, "RISC-V frame register has no DWARF mapping");
+  }
+  return DwarfRegisterNumber::fromValue(*Number);
+}
+
+[[nodiscard]] Expected<void> emitCFI(MachineIRBuilder &Builder, MachineCFIInstruction Instruction) {
+  auto Index = Builder.function().cfiInfo().addInstruction(std::move(Instruction));
+  if (!Index)
+    return std::unexpected(Index.error());
+  auto Pending = Builder.buildInstr(rcc::opcode(GenericOpcode::CFI_INSTRUCTION));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addCFIInstruction(*Index); !Result)
+    return std::unexpected(Result.error());
+  auto Built = Pending->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return {};
+}
+
+void appendULEB128(std::vector<std::uint8_t> &Bytes, std::uint64_t Value) {
+  do {
+    std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7FU);
+    Value >>= 7U;
+    if (Value != 0)
+      Byte |= 0x80U;
+    Bytes.push_back(Byte);
+  } while (Value != 0);
+}
+
+void appendSLEB128(std::vector<std::uint8_t> &Bytes, std::int64_t Value) {
+  bool More = true;
+  while (More) {
+    std::uint8_t Byte = static_cast<std::uint8_t>(Value & 0x7F);
+    const bool Sign = (Byte & 0x40U) != 0;
+    Value >>= 7;
+    More = (Value != 0 || Sign) && (Value != -1 || !Sign);
+    if (More)
+      Byte |= 0x80U;
+    Bytes.push_back(Byte);
+  }
+}
+
+[[nodiscard]] Expected<void>
+emitSavedRegisterCFI(MachineIRBuilder &Builder, const TargetDescription &Target,
+                     PhysicalRegister Reg, std::int64_t Offset,
+                     std::optional<PhysicalRegister> ExpressionBase = std::nullopt) {
+  auto DwarfReg = dwarfRegister(Target, Reg);
+  if (!DwarfReg)
+    return std::unexpected(DwarfReg.error());
+  if (!ExpressionBase)
+    return emitCFI(Builder, MachineCFIInstruction::offset(*DwarfReg, Offset));
+
+  auto DwarfBase = dwarfRegister(Target, *ExpressionBase);
+  if (!DwarfBase)
+    return std::unexpected(DwarfBase.error());
+  std::vector<std::uint8_t> Expression;
+  if (DwarfBase->value() <= 31U) {
+    Expression.push_back(static_cast<std::uint8_t>(DwarfOpBaseRegister0 + DwarfBase->value()));
+  } else {
+    Expression.push_back(DwarfOpBaseRegisterExtended);
+    appendULEB128(Expression, DwarfBase->value());
+  }
+  appendSLEB128(Expression, Offset);
+
+  std::vector<std::uint8_t> Escape{DwarfCFAExpression};
+  appendULEB128(Escape, DwarfReg->value());
+  appendULEB128(Escape, Expression.size());
+  Escape.insert(Escape.end(), Expression.begin(), Expression.end());
+  auto Rule = MachineCFIInstruction::escape(std::move(Escape));
+  if (!Rule)
+    return std::unexpected(Rule.error());
+  return emitCFI(Builder, std::move(*Rule));
+}
+
+[[nodiscard]] Expected<void> emitRestoreRegisterCFI(MachineIRBuilder &Builder,
+                                                    const TargetDescription &Target,
+                                                    PhysicalRegister Reg) {
+  auto DwarfReg = dwarfRegister(Target, Reg);
+  if (!DwarfReg)
+    return std::unexpected(DwarfReg.error());
+  return emitCFI(Builder, MachineCFIInstruction::restore(*DwarfReg));
+}
+
+[[nodiscard]] Expected<void> emitDefCFI(MachineIRBuilder &Builder, const TargetDescription &Target,
+                                        PhysicalRegister Reg, std::int64_t Offset) {
+  auto DwarfReg = dwarfRegister(Target, Reg);
+  if (!DwarfReg)
+    return std::unexpected(DwarfReg.error());
+  return emitCFI(Builder, MachineCFIInstruction::defCFA(*DwarfReg, Offset));
+}
+
+[[nodiscard]] Expected<void> emitConstant(MachineIRBuilder &Builder, PhysicalRegister Destination,
+                                          PhysicalRegister Zero, std::int64_t Value,
+                                          std::optional<MachineInstrFlag> Flag) {
+  std::uint64_t Remaining = static_cast<std::uint64_t>(Value);
+  std::vector<std::int64_t> Digits;
+  while (!fitsSigned12(std::bit_cast<std::int64_t>(Remaining))) {
+    std::int64_t Digit = static_cast<std::int64_t>(Remaining & 0xFFFU);
+    if (Digit >= 0x800)
+      Digit -= 0x1000;
+    Digits.push_back(Digit);
+    const std::uint64_t Adjusted = Remaining - static_cast<std::uint64_t>(Digit);
+    Remaining = Adjusted >> 12U;
+    if ((Adjusted & (std::uint64_t{1} << 63U)) != 0)
+      Remaining |= ~std::uint64_t{0} << 52U;
+  }
+
+  auto Base = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI));
+  if (!Base)
+    return std::unexpected(Base.error());
+  if (auto Result = Base->addDef(Register::fromPhysical(Destination)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Base->addUse(Register::fromPhysical(Zero)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Base->addImmediate(std::bit_cast<std::int64_t>(Remaining)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = setFrameFlag(*Base, Flag); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Base->build(); !Result)
+    return std::unexpected(Result.error());
+
+  for (std::size_t Reverse = Digits.size(); Reverse != 0; --Reverse) {
+    auto Shift = Builder.buildInstr(targetOpcode(InstructionOpcode::SLLI));
+    if (!Shift)
+      return std::unexpected(Shift.error());
+    if (auto Result = Shift->addDef(Register::fromPhysical(Destination)); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Shift->addUse(Register::fromPhysical(Destination)); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Shift->addImmediate(12); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = setFrameFlag(*Shift, Flag); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Shift->build(); !Result)
+      return std::unexpected(Result.error());
+
+    auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI));
+    if (!Add)
+      return std::unexpected(Add.error());
+    if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Add->addUse(Register::fromPhysical(Destination)); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Add->addImmediate(Digits[Reverse - 1U]); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = setFrameFlag(*Add, Flag); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Add->build(); !Result)
+      return std::unexpected(Result.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> emitRegisterAdd(MachineIRBuilder &Builder,
+                                             PhysicalRegister Destination, PhysicalRegister Left,
+                                             PhysicalRegister Right,
+                                             std::optional<MachineInstrFlag> Flag) {
+  auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADD));
+  if (!Add)
+    return std::unexpected(Add.error());
+  if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Add->addUse(Register::fromPhysical(Left)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Add->addUse(Register::fromPhysical(Right)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = setFrameFlag(*Add, Flag); !Result)
+    return std::unexpected(Result.error());
+  auto Built = Add->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return {};
+}
+
+[[nodiscard]] Expected<void> emitAddImmediate(MachineIRBuilder &Builder,
+                                              PhysicalRegister Destination, PhysicalRegister Source,
+                                              std::int64_t Amount,
+                                              std::optional<MachineInstrFlag> Flag) {
+  auto Add = Builder.buildInstr(targetOpcode(InstructionOpcode::ADDI));
+  if (!Add)
+    return std::unexpected(Add.error());
+  if (auto Result = Add->addDef(Register::fromPhysical(Destination)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Add->addUse(Register::fromPhysical(Source)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Add->addImmediate(Amount); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = setFrameFlag(*Add, Flag); !Result)
+    return std::unexpected(Result.error());
+  auto Built = Add->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return {};
+}
+
+[[nodiscard]] Expected<void> emitAndImmediate(MachineIRBuilder &Builder,
+                                              PhysicalRegister Destination, PhysicalRegister Source,
+                                              std::int64_t Amount,
+                                              std::optional<MachineInstrFlag> Flag) {
+  auto And = Builder.buildInstr(targetOpcode(InstructionOpcode::ANDI));
+  if (!And)
+    return std::unexpected(And.error());
+  if (auto Result = And->addDef(Register::fromPhysical(Destination)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = And->addUse(Register::fromPhysical(Source)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = And->addImmediate(Amount); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = setFrameFlag(*And, Flag); !Result)
+    return std::unexpected(Result.error());
+  auto Built = And->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return {};
+}
+
+[[nodiscard]] Expected<void> emitRegisterAnd(MachineIRBuilder &Builder,
+                                             PhysicalRegister Destination, PhysicalRegister Left,
+                                             PhysicalRegister Right,
+                                             std::optional<MachineInstrFlag> Flag) {
+  auto And = Builder.buildInstr(targetOpcode(InstructionOpcode::AND));
+  if (!And)
+    return std::unexpected(And.error());
+  if (auto Result = And->addDef(Register::fromPhysical(Destination)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = And->addUse(Register::fromPhysical(Left)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = And->addUse(Register::fromPhysical(Right)); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = setFrameFlag(*And, Flag); !Result)
+    return std::unexpected(Result.error());
+  auto Built = And->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return {};
+}
+
+[[nodiscard]] std::array<PhysicalRegisterID, 7> scratchOrder() noexcept {
+  return {PhysicalRegisterID::X5,  PhysicalRegisterID::X6,  PhysicalRegisterID::X7,
+          PhysicalRegisterID::X28, PhysicalRegisterID::X29, PhysicalRegisterID::X30,
+          PhysicalRegisterID::X31};
+}
+
+[[nodiscard]] Expected<std::vector<PhysicalRegister>> scratchRegisters() {
+  std::vector<PhysicalRegister> Result;
+  for (const PhysicalRegisterID ID : scratchOrder()) {
+    auto Reg = physical(ID);
+    if (!Reg)
+      return std::unexpected(Reg.error());
+    Result.push_back(*Reg);
+  }
+  return Result;
+}
+
+[[nodiscard]] const StackObject *emergencyObject(const MachineFunction &Function) noexcept {
+  for (const StackObject &Object : Function.frameInfo().objects()) {
+    if (!Object.isTombstone() && !Object.description()->IsDead &&
+        Object.description()->Kind == StackObjectKind::EmergencySpill)
+      return &Object;
+  }
+  return nullptr;
+}
+
+[[nodiscard]] Expected<FrameIndex> createEmergencyObject(MachineFunction &Function) {
+  auto Align = Alignment::create(8);
+  if (!Align)
+    return std::unexpected(Align.error());
+  StackObjectDesc Description;
+  Description.Kind = StackObjectKind::EmergencySpill;
+  Description.Size = 8;
+  Description.Align = *Align;
+  return Function.frameInfo().createObject(std::move(Description));
+}
+
+[[nodiscard]] Expected<std::uint64_t> layoutFrame(MachineFunction &Function, bool HasFP,
+                                                  bool ReserveCallFrame) {
+  MachineFrameInfo &Frame = Function.frameInfo();
+  const std::uint64_t CallFrame = ReserveCallFrame ? Frame.maxCallFrameSize().value_or(0) : 0;
+  auto Initial = alignTo(CallFrame, StackAlignmentBytes);
+  if (!Initial)
+    return std::unexpected(Initial.error());
+  std::uint64_t Cursor = *Initial;
+
+  std::vector<const StackObject *> Specials;
+  std::vector<const StackObject *> Locals;
+  std::vector<const StackObject *> PreallocatedLocals;
+  std::uint64_t LocalBlobSize = Frame.state().LocalFrameSize;
+  std::uint64_t LocalBlobAlignment = 1;
+  std::uint64_t MaximumAlignment = requiredStackAlignment(Function);
+  for (const StackObject &Object : Frame.objects()) {
+    if (Object.isTombstone() || Object.description()->IsDead)
+      continue;
+    const StackObjectDesc &Description = *Object.description();
+    if (Description.Stack != StackID::defaultStack()) {
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "RV64GC does not support non-default stack IDs");
+    }
+    MaximumAlignment = std::max(MaximumAlignment, Description.Align.bytes());
+    if (Object.isVariableSized())
+      continue;
+    if (Description.LocalOffset) {
+      if (*Description.LocalOffset < 0 ||
+          static_cast<std::uint64_t>(*Description.LocalOffset) % Description.Align.bytes() != 0) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V local stack object has an invalid offset");
+      }
+      const std::uint64_t Offset = static_cast<std::uint64_t>(*Description.LocalOffset);
+      if (Description.Size.value_or(0) > std::numeric_limits<std::uint64_t>::max() - Offset) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V local stack object range overflows");
+      }
+      const std::uint64_t End = Offset + Description.Size.value_or(0);
+      if (isOutgoingCallObject(Description)) {
+        if (!Frame.maxCallFrameSize() || End > *Frame.maxCallFrameSize()) {
+          return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                                "RISC-V outgoing stack object exceeds the call frame");
+        }
+      } else {
+        LocalBlobSize = std::max(LocalBlobSize, End);
+        LocalBlobAlignment = std::max(LocalBlobAlignment, Description.Align.bytes());
+        PreallocatedLocals.push_back(&Object);
+      }
+      continue;
+    }
+    if (Object.isFixed())
+      continue;
+    if (Description.Kind == StackObjectKind::CalleeSaved ||
+        Description.Kind == StackObjectKind::EmergencySpill) {
+      Specials.push_back(&Object);
+    } else {
+      Locals.push_back(&Object);
+    }
+  }
+  const auto Order = [](const StackObject *Left, const StackObject *Right) {
+    const StackObjectDesc &L = *Left->description();
+    const StackObjectDesc &R = *Right->description();
+    if (L.Align.bytes() != R.Align.bytes())
+      return L.Align.bytes() > R.Align.bytes();
+    if (L.Size != R.Size)
+      return L.Size.value_or(0) > R.Size.value_or(0);
+    return Left->index().value() < Right->index().value();
+  };
+  std::ranges::sort(Locals, Order);
+  std::ranges::sort(Specials, Order);
+  std::ranges::sort(PreallocatedLocals, [](const StackObject *Left, const StackObject *Right) {
+    return Left->index().value() < Right->index().value();
+  });
+
+  const auto Place = [&](std::span<const StackObject *const> Objects) -> Expected<void> {
+    for (const StackObject *Object : Objects) {
+      const StackObjectDesc &Description = *Object->description();
+      auto Aligned = alignTo(Cursor, Description.Align.bytes());
+      if (!Aligned)
+        return std::unexpected(Aligned.error());
+      Cursor = *Aligned;
+      if (Cursor > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V frame offset exceeds signed 64-bit range");
+      }
+      auto Set = Frame.setObjectOffset(Object->index(), static_cast<std::int64_t>(Cursor));
+      if (!Set)
+        return std::unexpected(Set.error());
+      if (Description.Size.value_or(0) > std::numeric_limits<std::uint64_t>::max() - Cursor) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V frame size overflows uint64");
+      }
+      Cursor += Description.Size.value_or(0);
+    }
+    return {};
+  };
+
+  const auto PlacePreallocated = [&]() -> Expected<void> {
+    if (LocalBlobSize == 0)
+      return {};
+    auto Aligned = alignTo(Cursor, LocalBlobAlignment);
+    if (!Aligned)
+      return std::unexpected(Aligned.error());
+    const std::uint64_t BlobStart = *Aligned;
+    for (const StackObject *Object : PreallocatedLocals) {
+      const std::uint64_t LocalOffset =
+          static_cast<std::uint64_t>(*Object->description()->LocalOffset);
+      if (BlobStart > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()) ||
+          LocalOffset >
+              static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()) - BlobStart) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V local frame offset exceeds int64");
+      }
+      auto Set = Frame.setObjectOffset(Object->index(),
+                                       static_cast<std::int64_t>(BlobStart + LocalOffset));
+      if (!Set)
+        return std::unexpected(Set.error());
+    }
+    if (LocalBlobSize > std::numeric_limits<std::uint64_t>::max() - BlobStart)
+      return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                            "RISC-V local frame size overflows uint64");
+    Cursor = BlobStart + LocalBlobSize;
+    return {};
+  };
+
+  if (!HasFP || requiresStackRealignment(Function)) {
+    auto Placed = Place(Specials);
+    if (!Placed)
+      return std::unexpected(Placed.error());
+  }
+  auto PlacedLocals = Place(Locals);
+  if (!PlacedLocals)
+    return std::unexpected(PlacedLocals.error());
+  auto PlacedPreallocated = PlacePreallocated();
+  if (!PlacedPreallocated)
+    return std::unexpected(PlacedPreallocated.error());
+  if (HasFP && !requiresStackRealignment(Function)) {
+    auto Placed = Place(Specials);
+    if (!Placed)
+      return std::unexpected(Placed.error());
+  }
+
+  for (const StackObject &Object : Frame.objects()) {
+    if (Object.isTombstone() || Object.description()->IsDead || Object.isVariableSized())
+      continue;
+    const StackObjectDesc &Description = *Object.description();
+    if (Description.LocalOffset && isOutgoingCallObject(Description)) {
+      auto Set = Frame.setObjectOffset(Object.index(), *Description.LocalOffset);
+      if (!Set)
+        return std::unexpected(Set.error());
+    }
+  }
+  if (LocalBlobSize > std::numeric_limits<std::uint32_t>::max()) {
+    return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                          "RISC-V local frame blob exceeds MIR limits");
+  }
+  MachineFrameState State = Frame.state();
+  State.LocalFrameSize = static_cast<std::uint32_t>(LocalBlobSize);
+  auto UpdatedState = Frame.setState(std::move(State));
+  if (!UpdatedState)
+    return std::unexpected(UpdatedState.error());
+  auto FinalSize = alignTo(Cursor, MaximumAlignment);
+  if (!FinalSize)
+    return std::unexpected(FinalSize.error());
+  if (*FinalSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+    return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                          "RISC-V frame size exceeds signed 64-bit range");
+  }
+  return *FinalSize;
+}
+
+[[nodiscard]] Expected<std::int64_t> objectReferenceOffset(const MachineFunction &Function,
+                                                           const MachineInstr &Instruction,
+                                                           const StackObjectDesc &Object,
+                                                           std::int64_t OperandOffset) {
+  if (!Object.Offset)
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V FrameIndex references an object without a final offset");
+  const bool HasFP = requiresFramePointer(Function);
+  std::int64_t BaseOffset = *Object.Offset;
+  if (Object.LocalOffset && isOutgoingCallObject(Object))
+    BaseOffset = *Object.LocalOffset;
+  else if (Object.Kind == StackObjectKind::FixedABI ||
+           Object.Kind == StackObjectKind::FixedSpillSlot) {
+    if (!HasFP) {
+      if (Function.frameInfo().state().StackSize >
+          static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V stack size exceeds signed 64-bit range");
+      }
+      auto Added =
+          checkedAdd(BaseOffset, static_cast<std::int64_t>(Function.frameInfo().state().StackSize));
+      if (!Added)
+        return std::unexpected(Added.error());
+      BaseOffset = *Added;
+    }
+  } else if (!requiresStackRealignment(Function) && HasFP &&
+             !Instruction.flags().has(MachineInstrFlag::FrameSetup)) {
+    if (Function.frameInfo().state().StackSize >
+        static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+      return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                            "RISC-V stack size exceeds signed 64-bit range");
+    }
+    auto Added =
+        checkedAdd(BaseOffset, -static_cast<std::int64_t>(Function.frameInfo().state().StackSize));
+    if (!Added)
+      return std::unexpected(Added.error());
+    BaseOffset = *Added;
+  }
+  return checkedAdd(BaseOffset, OperandOffset);
+}
+
+[[nodiscard]] Expected<FrameIndexReference> emergencyFrameReference(const MachineFunction &Function,
+                                                                    const StackObjectDesc &Object) {
+  if (!Object.Offset) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RISC-V emergency spill object has no final offset");
+  }
+  PhysicalRegisterID BaseID = PhysicalRegisterID::X2;
+  std::int64_t Offset = *Object.Offset;
+  if (requiresBasePointer(Function)) {
+    BaseID = PhysicalRegisterID::X9;
+  } else if (requiresFramePointer(Function)) {
+    BaseID = PhysicalRegisterID::X8;
+    if (Function.frameInfo().state().StackSize >
+        static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+      return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                            "RISC-V stack size exceeds signed 64-bit range");
+    }
+    auto Adjusted =
+        checkedAdd(Offset, -static_cast<std::int64_t>(Function.frameInfo().state().StackSize));
+    if (!Adjusted)
+      return std::unexpected(Adjusted.error());
+    Offset = *Adjusted;
+  }
+  auto Base = physical(BaseID);
+  if (!Base)
+    return std::unexpected(Base.error());
+  return FrameIndexReference{*Base, Offset};
+}
+
+[[nodiscard]] Expected<MachineInstr *>
+emitCalleeSave(MachineIRBuilder &Builder, PhysicalRegister Reg, FrameIndex Index, bool Restore) {
+  const bool IsFPR = Reg.number() >= static_cast<std::uint32_t>(PhysicalRegisterID::F0);
+  const InstructionOpcode OpcodeValue =
+      Restore ? (IsFPR ? InstructionOpcode::FLD : InstructionOpcode::LD)
+              : (IsFPR ? InstructionOpcode::FSD : InstructionOpcode::SD);
+  auto Memory = createStackMemory(Builder.function(), Index,
+                                  Restore ? MemoryAccessFlag::Load : MemoryAccessFlag::Store);
+  if (!Memory)
+    return std::unexpected(Memory.error());
+  auto Pending = Builder.buildInstr(targetOpcode(OpcodeValue));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  const Register Value = Register::fromPhysical(Reg);
+  auto RegisterResult = Restore ? Pending->addDef(Value) : Pending->addUse(Value);
+  if (!RegisterResult)
+    return std::unexpected(RegisterResult.error());
+  if (auto Result = Pending->addFrameIndex(Index); !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());
+  if (auto Result = setFrameFlag(*Pending, Restore ? MachineInstrFlag::FrameDestroy
+                                                   : MachineInstrFlag::FrameSetup);
+      !Result) {
+    return std::unexpected(Result.error());
+  }
+  auto Built = Pending->build();
+  if (!Built)
+    return std::unexpected(Built.error());
+  return *Built;
+}
+
+[[nodiscard]] std::optional<FrameIndex> calleeSaveSlot(const MachineFunction &Function,
+                                                       PhysicalRegister Reg) noexcept {
+  for (const StackObject &Object : Function.frameInfo().objects()) {
+    if (Object.isTombstone() || Object.description()->IsDead)
+      continue;
+    if (Object.description()->CalleeSavedRegister == Reg)
+      return Object.index();
+  }
+  return std::nullopt;
+}
+
+[[nodiscard]] bool isABIStackSaveRegister(PhysicalRegister Reg) {
+  return std::ranges::any_of(saveOrder(), [Reg](PhysicalRegisterID ID) {
+    auto Candidate = physical(ID);
+    return Candidate && *Candidate == Reg;
+  });
+}
+
+[[nodiscard]] Expected<void>
+validateCalleeSaveObjects(const MachineFunction &Function,
+                          std::span<const PhysicalRegister> SavedRegisters) {
+  std::unordered_set<PhysicalRegister> Slots;
+  for (const StackObject &Object : Function.frameInfo().objects()) {
+    if (Object.isTombstone() || Object.description()->IsDead ||
+        !Object.description()->CalleeSavedRegister) {
+      continue;
+    }
+    const StackObjectDesc &Description = *Object.description();
+    const PhysicalRegister Reg = *Description.CalleeSavedRegister;
+    if (!isABIStackSaveRegister(Reg)) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V callee-save object names a caller-saved register");
+    }
+    if (Description.Kind != StackObjectKind::CalleeSaved ||
+        Description.Size != std::optional<std::uint64_t>{8} || Description.Align.bytes() < 8 ||
+        Description.Stack != StackID::defaultStack()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V callee-save object has an invalid kind, size, or alignment");
+    }
+    if (!Slots.insert(Reg).second) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V callee-save register has duplicate stack objects");
+    }
+    if (std::ranges::find(SavedRegisters, Reg) == SavedRegisters.end()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V callee-save object was omitted from save analysis");
+    }
+  }
+  return {};
+}
+
+[[nodiscard]] bool calleeSaveIsRestored(const MachineFunction &Function,
+                                        PhysicalRegister Reg) noexcept {
+  const auto Slot = calleeSaveSlot(Function, Reg);
+  const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr;
+  return Object != nullptr && Object->description()->CalleeSavedRestored;
+}
+
+struct CalleeSaveOperation final {
+  MachineInstr *Instruction = nullptr;
+  PhysicalRegister Reg;
+};
+
+[[nodiscard]] std::vector<CalleeSaveOperation>
+calleeSaveOperations(MachineBasicBlock &Block, const MachineFunction &Function, bool Restore) {
+  std::vector<CalleeSaveOperation> Result;
+  for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (!Instruction->flags().has(Restore ? MachineInstrFlag::FrameDestroy
+                                          : MachineInstrFlag::FrameSetup)) {
+      continue;
+    }
+    for (const MachineOperand &Operand : Instruction->operands()) {
+      const auto *Frame = Operand.getIf<FrameIndexOperand>();
+      if (Frame == nullptr)
+        continue;
+      const StackObject *Object = Function.frameInfo().object(Frame->Index);
+      if (Object != nullptr && Object->description()->CalleeSavedRegister) {
+        Result.push_back(
+            CalleeSaveOperation{Instruction, *Object->description()->CalleeSavedRegister});
+        break;
+      }
+    }
+  }
+  return Result;
+}
+
+class RISCVFrameLowering final : public TargetFrameLowering {
+public:
+  [[nodiscard]] Expected<void> prepareFrame(MachineFunction &Function,
+                                            const TargetDescription &Target) const override {
+    MachineFrameInfo &Frame = Function.frameInfo();
+    if (Frame.isFrozen())
+      return makeUnexpected(ErrorCode::InvalidArgument, "RISC-V frame layout is already frozen");
+
+    MachineFrameState State = Frame.state();
+    for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        const InstructionDescriptor *Descriptor =
+            Target.instructionDescriptor(Instruction->opcode());
+        if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Call))
+          State.HasCalls = true;
+      }
+    }
+    auto UpdatedState = Frame.setState(State);
+    if (!UpdatedState)
+      return std::unexpected(UpdatedState.error());
+
+    auto CallFrame = computeMaxCallFrameSize(Function);
+    if (!CallFrame)
+      return std::unexpected(CallFrame.error());
+    auto FrameRegisters = validateFrameRegisterUses(Function, Target);
+    if (!FrameRegisters)
+      return std::unexpected(FrameRegisters.error());
+
+    auto SavedRegisters = modifiedCalleeSavedRegisters(Function, Target);
+    if (!SavedRegisters)
+      return std::unexpected(SavedRegisters.error());
+    auto ExistingSlots = validateCalleeSaveObjects(Function, *SavedRegisters);
+    if (!ExistingSlots)
+      return std::unexpected(ExistingSlots.error());
+    auto Align8 = Alignment::create(8);
+    if (!Align8)
+      return std::unexpected(Align8.error());
+    for (const PhysicalRegister Reg : *SavedRegisters) {
+      if (calleeSaveSlot(Function, Reg))
+        continue;
+      StackObjectDesc Description;
+      Description.Kind = StackObjectKind::CalleeSaved;
+      Description.Size = 8;
+      Description.Align = *Align8;
+      Description.CalleeSavedRegister = Reg;
+      auto Created = Frame.createObject(std::move(Description));
+      if (!Created)
+        return std::unexpected(Created.error());
+    }
+    auto CompleteSlots = validateCalleeSaveObjects(Function, *SavedRegisters);
+    if (!CompleteSlots)
+      return std::unexpected(CompleteSlots.error());
+
+    const bool HasFP = requiresFramePointer(Function);
+    const bool ReserveCallFrame = hasReservedCallFrame(Function);
+    auto StackSize = layoutFrame(Function, HasFP, ReserveCallFrame);
+    if (!StackSize)
+      return std::unexpected(StackSize.error());
+
+    State = Frame.state();
+    State.StackSize = *StackSize;
+    auto RequiredAlignment = Alignment::create(requiredStackAlignment(Function));
+    if (!RequiredAlignment)
+      return std::unexpected(RequiredAlignment.error());
+    State.MaxAlignment = *RequiredAlignment;
+    auto StateForReferences = Frame.setState(State);
+    if (!StateForReferences)
+      return std::unexpected(StateForReferences.error());
+
+    bool NeedsEmergency = false;
+    for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        if (isCallFramePseudo(*Instruction)) {
+          auto Amount = callFrameAmount(*Instruction);
+          if (!Amount)
+            return std::unexpected(Amount.error());
+          NeedsEmergency |= !ReserveCallFrame && !fitsSigned12(*Amount);
+        }
+        for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+          const auto *FrameOperand = Instruction->operandAt(Index)->getIf<FrameIndexOperand>();
+          if (FrameOperand == nullptr)
+            continue;
+          std::int64_t Extra = FrameOperand->Offset;
+          if (Index + 1U >= Instruction->operandCount()) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "RISC-V frame operand lacks an adjacent immediate");
+          }
+          auto Immediate = immediateValue(*Instruction->operandAt(Index + 1U));
+          if (!Immediate)
+            return std::unexpected(Immediate.error());
+          auto Added = checkedAdd(Extra, *Immediate);
+          if (!Added)
+            return std::unexpected(Added.error());
+          Extra = *Added;
+          const StackObject *Object = Frame.object(FrameOperand->Index);
+          if (Object == nullptr || Object->description()->IsDead)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "RISC-V frame instruction references an invalid object");
+          auto Offset =
+              objectReferenceOffset(Function, *Instruction, *Object->description(), Extra);
+          if (!Offset)
+            return std::unexpected(Offset.error());
+          NeedsEmergency |= !fitsSigned12(*Offset);
+        }
+      }
+    }
+    if (NeedsEmergency && emergencyObject(Function) == nullptr) {
+      auto Emergency = createEmergencyObject(Function);
+      if (!Emergency)
+        return std::unexpected(Emergency.error());
+      StackSize = layoutFrame(Function, HasFP, ReserveCallFrame);
+      if (!StackSize)
+        return std::unexpected(StackSize.error());
+    }
+
+    State = Frame.state();
+    State.StackSize = *StackSize;
+    State.AdjustsStack = State.AdjustsStack || *StackSize != 0;
+    State.IsCalleeSavedInfoValid = true;
+    State.SavePoints.clear();
+    State.RestorePoints.clear();
+    if (!SavedRegisters->empty() && Function.firstBlock() != nullptr) {
+      State.SavePoints.push_back(
+          MachineFrameSaveRestorePoint{Function.firstBlock()->stableID(), *SavedRegisters});
+    }
+    for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      bool HasEpilogue = false;
+      for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        HasEpilogue |= isEpilogueTerminator(*Instruction, Target);
+      }
+      if (HasEpilogue && !SavedRegisters->empty()) {
+        std::vector<PhysicalRegister> Restored;
+        std::ranges::copy_if(
+            *SavedRegisters, std::back_inserter(Restored),
+            [&Function](PhysicalRegister Reg) { return calleeSaveIsRestored(Function, Reg); });
+        if (!Restored.empty()) {
+          State.RestorePoints.push_back(
+              MachineFrameSaveRestorePoint{Block->stableID(), std::move(Restored)});
+        }
+      }
+    }
+    auto SetState = Frame.setState(std::move(State));
+    if (!SetState)
+      return std::unexpected(SetState.error());
+    auto Records = Function.records().setCalleeSavedRegisters(*SavedRegisters);
+    if (!Records)
+      return std::unexpected(Records.error());
+    return {};
+  }
+
+  [[nodiscard]] Expected<void>
+  insertCalleeSavedSpillsAndRestores(MachineFunction &Function,
+                                     const TargetDescription &Target) const override {
+    if (Function.frameInfo().isFrozen()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V callee saves must be inserted before frame freeze");
+    }
+    const std::span<const PhysicalRegister> Saved = Function.records().calleeSavedRegisters();
+    if (Saved.empty())
+      return {};
+    MachineBasicBlock *Entry = Function.firstBlock();
+    if (Entry == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V callee-save frame has no entry block");
+    }
+    auto FP = physical(PhysicalRegisterID::X8);
+    auto BP = physical(PhysicalRegisterID::X9);
+    auto OldFP = physical(PhysicalRegisterID::X5);
+    if (!FP || !BP || !OldFP)
+      return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable");
+    const bool Realign = requiresStackRealignment(Function);
+
+    MachineIRBuilder SaveBuilder(Function, Target);
+    auto SavePoint = Entry->firstInstruction() != nullptr
+                         ? SaveBuilder.setInsertPointBefore(*Entry->firstInstruction())
+                         : SaveBuilder.setInsertPoint(*Entry);
+    if (!SavePoint)
+      return std::unexpected(SavePoint.error());
+    for (const PhysicalRegister Reg : Saved) {
+      const auto Slot = calleeSaveSlot(Function, Reg);
+      if (!Slot) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RISC-V callee-save register has no stack slot");
+      }
+      const PhysicalRegister Value = Realign && Reg == *FP ? *OldFP : Reg;
+      auto Stored = emitCalleeSave(SaveBuilder, Value, *Slot, false);
+      if (!Stored)
+        return std::unexpected(Stored.error());
+    }
+
+    for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+         Block = Block->next()) {
+      std::vector<MachineInstr *> Terminators;
+      for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        if (isEpilogueTerminator(*Instruction, Target))
+          Terminators.push_back(Instruction);
+      }
+      for (MachineInstr *Terminator : Terminators) {
+        MachineIRBuilder RestoreBuilder(Function, Target);
+        auto Point = RestoreBuilder.setInsertPointBefore(*Terminator);
+        if (!Point)
+          return std::unexpected(Point.error());
+        const auto EmitRestore = [&](PhysicalRegister Reg) -> Expected<void> {
+          if (!calleeSaveIsRestored(Function, Reg))
+            return {};
+          const auto Slot = calleeSaveSlot(Function, Reg);
+          if (!Slot) {
+            return makeUnexpected(ErrorCode::InternalError,
+                                  "RISC-V callee-save register has no restore slot");
+          }
+          auto Loaded = emitCalleeSave(RestoreBuilder, Reg, *Slot, true);
+          if (!Loaded)
+            return std::unexpected(Loaded.error());
+          return {};
+        };
+        for (const PhysicalRegister Reg : Saved) {
+          if ((requiresFramePointer(Function) && Reg == *FP) || (Realign && Reg == *BP))
+            continue;
+          auto Loaded = EmitRestore(Reg);
+          if (!Loaded)
+            return std::unexpected(Loaded.error());
+        }
+        if (requiresFramePointer(Function)) {
+          auto Loaded = EmitRestore(*FP);
+          if (!Loaded)
+            return std::unexpected(Loaded.error());
+        }
+        if (Realign) {
+          auto Loaded = EmitRestore(*BP);
+          if (!Loaded)
+            return std::unexpected(Loaded.error());
+        }
+      }
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<void> finalizeFrame(MachineFunction &Function,
+                                             const TargetDescription &) const override {
+    MachineFrameInfo &Frame = Function.frameInfo();
+    if (Frame.isFrozen())
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V frame was frozen before final layout");
+    std::vector<std::optional<std::int64_t>> PreliminaryOffsets;
+    PreliminaryOffsets.reserve(Frame.objects().size());
+    for (const StackObject &Object : Frame.objects()) {
+      PreliminaryOffsets.push_back(Object.isTombstone() ? std::nullopt
+                                                        : Object.description()->Offset);
+    }
+    const std::uint64_t PreliminarySize = Frame.state().StackSize;
+    auto StackSize =
+        layoutFrame(Function, requiresFramePointer(Function), hasReservedCallFrame(Function));
+    if (!StackSize)
+      return std::unexpected(StackSize.error());
+    if (*StackSize != PreliminarySize || Frame.objects().size() != PreliminaryOffsets.size()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V frame resources changed after preliminary layout");
+    }
+    for (const StackObject &Object : Frame.objects()) {
+      if (!Object.isTombstone() &&
+          Object.description()->Offset != PreliminaryOffsets[Object.index().value()]) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RISC-V frame offsets changed after callee-save insertion");
+      }
+    }
+    auto StackAlignment = Alignment::create(requiredStackAlignment(Function));
+    if (!StackAlignment)
+      return std::unexpected(StackAlignment.error());
+    return Frame.freeze(*StackSize, *StackAlignment);
+  }
+
+  [[nodiscard]] bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept override {
+    return Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) ||
+           Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKUP);
+  }
+
+  [[nodiscard]] Expected<void>
+  eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function,
+                           const TargetDescription &Target,
+                           RegisterScavenger &Scavenger) const override {
+    MachineBasicBlock *Block = Instruction.parent();
+    if (Block == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError, "RISC-V call-frame pseudo is detached");
+    if (!hasReservedCallFrame(Function)) {
+      auto Amount = callFrameAmount(Instruction);
+      if (!Amount)
+        return std::unexpected(Amount.error());
+      std::int64_t Adjustment = *Amount;
+      if (Instruction.opcode() == targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN))
+        Adjustment = -Adjustment;
+      auto Adjusted = emitStackAdjustment(Instruction, Function, Target, Scavenger, Adjustment,
+                                          Adjustment < 0 ? MachineInstrFlag::FrameSetup
+                                                         : MachineInstrFlag::FrameDestroy);
+      if (!Adjusted)
+        return std::unexpected(Adjusted.error());
+    }
+    return Block->removeInstruction(Instruction);
+  }
+
+  [[nodiscard]] Expected<void> emitPrologue(MachineFunction &Function,
+                                            const TargetDescription &Target,
+                                            RegisterScavenger &Scavenger) const override {
+    MachineBasicBlock *Entry = Function.firstBlock();
+    if (Entry == nullptr)
+      return Function.frameInfo().state().StackSize == 0
+                 ? Expected<void>{}
+                 : makeUnexpected(ErrorCode::VerificationError,
+                                  "RISC-V nonempty frame has no entry block");
+    const std::vector<CalleeSaveOperation> Saves = calleeSaveOperations(*Entry, Function, false);
+    if (Saves.size() != Function.records().calleeSavedRegisters().size()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V prologue has an incomplete callee-save sequence");
+    }
+    MachineInstr *Anchor = Entry->firstInstruction();
+    MachineIRBuilder Builder(Function, Target);
+    auto Point =
+        Anchor != nullptr ? Builder.setInsertPointBefore(*Anchor) : Builder.setInsertPoint(*Entry);
+    if (!Point)
+      return std::unexpected(Point.error());
+
+    const std::uint64_t StackSize = Function.frameInfo().state().StackSize;
+    const std::uint64_t StackAlignment = requiredStackAlignment(Function);
+    const bool Realign = requiresStackRealignment(Function);
+    auto SP = physical(PhysicalRegisterID::X2);
+    auto FP = physical(PhysicalRegisterID::X8);
+    auto BP = physical(PhysicalRegisterID::X9);
+    auto Zero = physical(PhysicalRegisterID::X0);
+    auto OldFP = physical(PhysicalRegisterID::X5);
+    auto DefaultTemporary = physical(PhysicalRegisterID::X6);
+    if (!SP || !FP || !BP || !Zero || !OldFP || !DefaultTemporary) {
+      return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable");
+    }
+    PhysicalRegister Temporary = *DefaultTemporary;
+    const std::int64_t AlignmentMask = std::bit_cast<std::int64_t>(~(StackAlignment - 1U));
+    const bool NeedsTemporary = StackSize > 2048U ||
+                                (!Realign && requiresFramePointer(Function) &&
+                                 StackSize > static_cast<std::uint64_t>(MaxSigned12)) ||
+                                (Realign && !fitsSigned12(AlignmentMask));
+    if (NeedsTemporary) {
+      auto Candidates = scratchRegisters();
+      if (!Candidates)
+        return std::unexpected(Candidates.error());
+      if (Anchor != nullptr) {
+        auto Scratch = Scavenger.scavenge(*Anchor, *Candidates);
+        if (!Scratch)
+          return std::unexpected(Scratch.error());
+        if (Scratch->RequiresSpill) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "RISC-V prologue has no dead scratch register");
+        }
+        Temporary = Scratch->Reg;
+      } else {
+        Temporary = Candidates->front();
+      }
+    }
+
+    if (Realign) {
+      auto PreserveFP = emitAddImmediate(Builder, *OldFP, *FP, 0, MachineInstrFlag::FrameSetup);
+      if (!PreserveFP)
+        return std::unexpected(PreserveFP.error());
+      auto CaptureIncomingSP = emitAddImmediate(Builder, *FP, *SP, 0, MachineInstrFlag::FrameSetup);
+      if (!CaptureIncomingSP)
+        return std::unexpected(CaptureIncomingSP.error());
+      auto CFA = emitDefCFI(Builder, Target, *FP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+    }
+
+    const std::uint64_t AllocationSize = StackSize;
+    if (AllocationSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max())) {
+      return makeUnexpected(ErrorCode::FrameLayoutFailed, "RISC-V stack adjustment exceeds int64");
+    }
+    if (AllocationSize != 0) {
+      const std::int64_t Amount = -static_cast<std::int64_t>(AllocationSize);
+      if (fitsSigned12(Amount)) {
+        auto Adjust = emitAddImmediate(Builder, *SP, *SP, Amount, MachineInstrFlag::FrameSetup);
+        if (!Adjust)
+          return std::unexpected(Adjust.error());
+      } else {
+        auto Constant =
+            emitConstant(Builder, Temporary, *Zero, Amount, MachineInstrFlag::FrameSetup);
+        if (!Constant)
+          return std::unexpected(Constant.error());
+        auto Adjust = emitRegisterAdd(Builder, *SP, *SP, Temporary, MachineInstrFlag::FrameSetup);
+        if (!Adjust)
+          return std::unexpected(Adjust.error());
+      }
+      if (!Realign) {
+        auto CFA = emitDefCFI(Builder, Target, *SP, static_cast<std::int64_t>(StackSize));
+        if (!CFA)
+          return std::unexpected(CFA.error());
+      }
+    }
+    if (Realign) {
+      const std::int64_t Mask = AlignmentMask;
+      Expected<void> Aligned =
+          fitsSigned12(Mask)
+              ? emitAndImmediate(Builder, *SP, *SP, Mask, MachineInstrFlag::FrameSetup)
+              : emitConstant(Builder, Temporary, *Zero, Mask, MachineInstrFlag::FrameSetup);
+      if (!Aligned)
+        return std::unexpected(Aligned.error());
+      if (!fitsSigned12(Mask)) {
+        Aligned = emitRegisterAnd(Builder, *SP, *SP, Temporary, MachineInstrFlag::FrameSetup);
+        if (!Aligned)
+          return std::unexpected(Aligned.error());
+      }
+    }
+
+    if (Realign) {
+      if (Saves.empty()) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RISC-V realigned frame has no callee-save sequence");
+      }
+      MachineIRBuilder AfterSaves(Function, Target);
+      auto PointAfterSaves = AfterSaves.setInsertPointAfter(*Saves.back().Instruction);
+      if (!PointAfterSaves)
+        return std::unexpected(PointAfterSaves.error());
+      auto Set = emitAddImmediate(AfterSaves, *BP, *SP, 0, MachineInstrFlag::FrameSetup);
+      if (!Set)
+        return std::unexpected(Set.error());
+      for (const PhysicalRegister Reg : Function.records().calleeSavedRegisters()) {
+        const auto Slot = calleeSaveSlot(Function, Reg);
+        const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr;
+        if (Object == nullptr || !Object->description()->Offset) {
+          return makeUnexpected(ErrorCode::InternalError,
+                                "RISC-V realigned CFI slot is incomplete");
+        }
+        auto CFI =
+            emitSavedRegisterCFI(AfterSaves, Target, Reg, *Object->description()->Offset, *BP);
+        if (!CFI)
+          return std::unexpected(CFI.error());
+      }
+      return {};
+    }
+
+    for (std::size_t Index = 0; Index < Saves.size(); ++Index) {
+      const CalleeSaveOperation &Save = Saves[Index];
+      const auto Slot = calleeSaveSlot(Function, Save.Reg);
+      const StackObject *Object = Slot ? Function.frameInfo().object(*Slot) : nullptr;
+      if (Object == nullptr || !Object->description()->Offset) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "RISC-V callee-save CFI slot is incomplete");
+      }
+      auto Offset =
+          checkedAdd(*Object->description()->Offset, -static_cast<std::int64_t>(StackSize));
+      if (!Offset)
+        return std::unexpected(Offset.error());
+      MachineIRBuilder AfterSave(Function, Target);
+      auto PointAfterSave = AfterSave.setInsertPointAfter(*Save.Instruction);
+      if (!PointAfterSave)
+        return std::unexpected(PointAfterSave.error());
+      auto CFI = emitSavedRegisterCFI(AfterSave, Target, Save.Reg, *Offset);
+      if (!CFI)
+        return std::unexpected(CFI.error());
+      if (Index + 1U != Saves.size() || !requiresFramePointer(Function))
+        continue;
+      Expected<void> Set =
+          StackSize <= static_cast<std::uint64_t>(MaxSigned12)
+              ? emitAddImmediate(AfterSave, *FP, *SP, static_cast<std::int64_t>(StackSize),
+                                 MachineInstrFlag::FrameSetup)
+              : emitConstant(AfterSave, Temporary, *Zero, static_cast<std::int64_t>(StackSize),
+                             MachineInstrFlag::FrameSetup);
+      if (!Set)
+        return std::unexpected(Set.error());
+      if (StackSize > static_cast<std::uint64_t>(MaxSigned12)) {
+        Set = emitRegisterAdd(AfterSave, *FP, *SP, Temporary, MachineInstrFlag::FrameSetup);
+        if (!Set)
+          return std::unexpected(Set.error());
+      }
+      auto CFA = emitDefCFI(AfterSave, Target, *FP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+    }
+    if (Saves.empty() && requiresFramePointer(Function)) {
+      Expected<void> Set =
+          StackSize <= static_cast<std::uint64_t>(MaxSigned12)
+              ? emitAddImmediate(Builder, *FP, *SP, static_cast<std::int64_t>(StackSize),
+                                 MachineInstrFlag::FrameSetup)
+              : emitConstant(Builder, Temporary, *Zero, static_cast<std::int64_t>(StackSize),
+                             MachineInstrFlag::FrameSetup);
+      if (!Set)
+        return std::unexpected(Set.error());
+      if (StackSize > static_cast<std::uint64_t>(MaxSigned12)) {
+        Set = emitRegisterAdd(Builder, *FP, *SP, Temporary, MachineInstrFlag::FrameSetup);
+        if (!Set)
+          return std::unexpected(Set.error());
+      }
+      auto CFA = emitDefCFI(Builder, Target, *FP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+    }
+    return {};
+  }
+
+  [[nodiscard]] bool isEpilogueTerminator(const MachineInstr &Instruction,
+                                          const TargetDescription &Target) const noexcept override {
+    if (Instruction.opcode() == targetOpcode(InstructionOpcode::PseudoTAIL))
+      return true;
+    const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode());
+    return Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Return);
+  }
+
+  [[nodiscard]] Expected<void> emitEpilogue(MachineBasicBlock &Block, MachineInstr &Terminator,
+                                            MachineFunction &Function,
+                                            const TargetDescription &Target,
+                                            RegisterScavenger &Scavenger) const override {
+    auto FP = physical(PhysicalRegisterID::X8);
+    auto SP = physical(PhysicalRegisterID::X2);
+    auto BP = physical(PhysicalRegisterID::X9);
+    if (!FP || !SP || !BP) {
+      return makeUnexpected(ErrorCode::InternalError, "RISC-V frame registers are unavailable");
+    }
+    const bool HasFP = requiresFramePointer(Function);
+    const bool Realign = requiresStackRealignment(Function);
+    const std::uint64_t StackSize = Function.frameInfo().state().StackSize;
+    const bool HasFrameCFI = StackSize != 0 || !Function.records().calleeSavedRegisters().empty();
+
+    const std::vector<CalleeSaveOperation> BlockRestores =
+        calleeSaveOperations(Block, Function, true);
+    std::vector<CalleeSaveOperation> Restores;
+    for (MachineInstr *Cursor = Terminator.previous(); Cursor != nullptr;
+         Cursor = Cursor->previous()) {
+      const auto Position =
+          std::ranges::find(BlockRestores, Cursor, &CalleeSaveOperation::Instruction);
+      if (Position == BlockRestores.end())
+        break;
+      Restores.push_back(*Position);
+    }
+    std::ranges::reverse(Restores);
+    const std::size_t ExpectedRestores = static_cast<std::size_t>(std::ranges::count_if(
+        Function.records().calleeSavedRegisters(),
+        [&Function](PhysicalRegister Reg) { return calleeSaveIsRestored(Function, Reg); }));
+    if (Restores.size() != ExpectedRestores) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "RISC-V epilogue has an incomplete callee-restore sequence");
+    }
+
+    if (HasFrameCFI) {
+      MachineIRBuilder RememberBuilder(Function, Target);
+      auto Point = Restores.empty()
+                       ? RememberBuilder.setInsertPointBefore(Terminator)
+                       : RememberBuilder.setInsertPointBefore(*Restores.front().Instruction);
+      if (!Point)
+        return std::unexpected(Point.error());
+      auto Remember = emitCFI(RememberBuilder, MachineCFIInstruction::rememberState());
+      if (!Remember)
+        return std::unexpected(Remember.error());
+    }
+
+    for (const CalleeSaveOperation &Restore : Restores) {
+      if ((HasFP && Restore.Reg == *FP) || (Realign && Restore.Reg == *BP))
+        continue;
+      MachineIRBuilder AfterRestore(Function, Target);
+      auto Point = AfterRestore.setInsertPointAfter(*Restore.Instruction);
+      if (!Point)
+        return std::unexpected(Point.error());
+      auto CFI = emitRestoreRegisterCFI(AfterRestore, Target, Restore.Reg);
+      if (!CFI)
+        return std::unexpected(CFI.error());
+    }
+
+    if (Realign) {
+      const auto FPRestore = std::ranges::find(Restores, *FP, &CalleeSaveOperation::Reg);
+      const auto BPRestore = std::ranges::find(Restores, *BP, &CalleeSaveOperation::Reg);
+      MachineIRBuilder Teardown(Function, Target);
+      MachineInstr *SpecialRestore =
+          FPRestore != Restores.end()
+              ? FPRestore->Instruction
+              : (BPRestore != Restores.end() ? BPRestore->Instruction : &Terminator);
+      auto Point = Teardown.setInsertPointBefore(*SpecialRestore);
+      if (!Point)
+        return std::unexpected(Point.error());
+      auto RestoreSP = emitAddImmediate(Teardown, *SP, *FP, 0, MachineInstrFlag::FrameDestroy);
+      if (!RestoreSP)
+        return std::unexpected(RestoreSP.error());
+      auto CFA = emitDefCFI(Teardown, Target, *SP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+      if (FPRestore != Restores.end()) {
+        MachineIRBuilder AfterFP(Function, Target);
+        auto After = AfterFP.setInsertPointAfter(*FPRestore->Instruction);
+        if (!After)
+          return std::unexpected(After.error());
+        auto FPCFI = emitRestoreRegisterCFI(AfterFP, Target, *FP);
+        if (!FPCFI)
+          return std::unexpected(FPCFI.error());
+      }
+      if (BPRestore != Restores.end()) {
+        MachineIRBuilder AfterBP(Function, Target);
+        auto After = AfterBP.setInsertPointAfter(*BPRestore->Instruction);
+        if (!After)
+          return std::unexpected(After.error());
+        auto BPCFI = emitRestoreRegisterCFI(AfterBP, Target, *BP);
+        if (!BPCFI)
+          return std::unexpected(BPCFI.error());
+      }
+    } else if (HasFP) {
+      const auto FPRestore = std::ranges::find(Restores, *FP, &CalleeSaveOperation::Reg);
+      MachineIRBuilder Teardown(Function, Target);
+      auto Point = FPRestore == Restores.end()
+                       ? Teardown.setInsertPointBefore(Terminator)
+                       : Teardown.setInsertPointBefore(*FPRestore->Instruction);
+      if (!Point)
+        return std::unexpected(Point.error());
+      auto RestoreSP = emitAddImmediate(Teardown, *SP, *FP, 0, MachineInstrFlag::FrameDestroy);
+      if (!RestoreSP)
+        return std::unexpected(RestoreSP.error());
+      auto CFA = emitDefCFI(Teardown, Target, *SP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+      if (FPRestore != Restores.end()) {
+        MachineIRBuilder AfterFP(Function, Target);
+        auto After = AfterFP.setInsertPointAfter(*FPRestore->Instruction);
+        if (!After)
+          return std::unexpected(After.error());
+        auto FPCFI = emitRestoreRegisterCFI(AfterFP, Target, *FP);
+        if (!FPCFI)
+          return std::unexpected(FPCFI.error());
+      }
+    } else if (StackSize != 0) {
+      if (StackSize > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
+        return makeUnexpected(ErrorCode::FrameLayoutFailed,
+                              "RISC-V stack adjustment exceeds int64");
+      MachineIRBuilder Teardown(Function, Target);
+      auto Point = Teardown.setInsertPointBefore(Terminator);
+      if (!Point)
+        return std::unexpected(Point.error());
+      const std::int64_t Amount = static_cast<std::int64_t>(StackSize);
+      if (fitsSigned12(Amount)) {
+        auto Adjust = emitAddImmediate(Teardown, *SP, *SP, Amount, MachineInstrFlag::FrameDestroy);
+        if (!Adjust)
+          return std::unexpected(Adjust.error());
+      } else {
+        auto Candidates = scratchRegisters();
+        auto Zero = physical(PhysicalRegisterID::X0);
+        if (!Candidates || !Zero)
+          return std::unexpected(!Candidates ? Candidates.error() : Zero.error());
+        auto Scratch = Scavenger.scavenge(Terminator, *Candidates);
+        if (!Scratch)
+          return std::unexpected(Scratch.error());
+        if (Scratch->RequiresSpill) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "RISC-V epilogue has no dead scratch register");
+        }
+        auto Constant =
+            emitConstant(Teardown, Scratch->Reg, *Zero, Amount, MachineInstrFlag::FrameDestroy);
+        if (!Constant)
+          return std::unexpected(Constant.error());
+        auto Adjust =
+            emitRegisterAdd(Teardown, *SP, *SP, Scratch->Reg, MachineInstrFlag::FrameDestroy);
+        if (!Adjust)
+          return std::unexpected(Adjust.error());
+      }
+      auto CFA = emitDefCFI(Teardown, Target, *SP, 0);
+      if (!CFA)
+        return std::unexpected(CFA.error());
+    }
+    if (HasFrameCFI) {
+      MachineIRBuilder RestoreBuilder(Function, Target);
+      auto After = RestoreBuilder.setInsertPointAfter(Terminator);
+      if (!After)
+        return std::unexpected(After.error());
+      auto Restore = emitCFI(RestoreBuilder, MachineCFIInstruction::restoreState());
+      if (!Restore)
+        return std::unexpected(Restore.error());
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<FrameIndexReference>
+  getFrameIndexReference(const MachineFunction &Function, const MachineInstr &Instruction,
+                         FrameIndex Index, std::int64_t OperandOffset) const override {
+    const StackObject *Object = Function.frameInfo().object(Index);
+    if (Object == nullptr || Object->description()->IsDead)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V FrameIndex references an invalid stack object");
+    if (Object->isVariableSized())
+      return makeUnexpected(ErrorCode::Unsupported,
+                            "RISC-V variable-sized object cannot be addressed by FrameIndex");
+    auto Offset =
+        objectReferenceOffset(Function, Instruction, *Object->description(), OperandOffset);
+    if (!Offset)
+      return std::unexpected(Offset.error());
+    const StackObjectDesc &Description = *Object->description();
+    PhysicalRegisterID BaseID = PhysicalRegisterID::X2;
+    if (!isOutgoingCallObject(Description) &&
+        !Instruction.flags().has(MachineInstrFlag::FrameSetup)) {
+      const bool FixedObject = Description.Kind == StackObjectKind::FixedABI ||
+                               Description.Kind == StackObjectKind::FixedSpillSlot;
+      const bool HasFP = requiresFramePointer(Function);
+      const bool HasBP = requiresBasePointer(Function);
+      if (HasFP && (FixedObject || !HasBP)) {
+        BaseID = PhysicalRegisterID::X8;
+      } else if (HasBP) {
+        BaseID = PhysicalRegisterID::X9;
+      }
+    }
+    auto Base = physical(BaseID);
+    if (!Base)
+      return std::unexpected(Base.error());
+    return FrameIndexReference{*Base, *Offset};
+  }
+
+  [[nodiscard]] Expected<void> eliminateFrameIndex(MachineInstr &Instruction,
+                                                   std::size_t OperandIndex,
+                                                   MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   RegisterScavenger &Scavenger) const override {
+    const auto *Frame = Instruction.operandAt(OperandIndex)->getIf<FrameIndexOperand>();
+    if (Frame == nullptr)
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "RISC-V frame elimination requires a FrameIndex operand");
+    if (OperandIndex + 1U >= Instruction.operandCount())
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "RISC-V frame operand lacks an adjacent immediate");
+    auto Immediate = immediateValue(*Instruction.operandAt(OperandIndex + 1U));
+    if (!Immediate)
+      return std::unexpected(Immediate.error());
+    auto Extra = checkedAdd(Frame->Offset, *Immediate);
+    if (!Extra)
+      return std::unexpected(Extra.error());
+    auto Reference = getFrameIndexReference(Function, Instruction, Frame->Index, *Extra);
+    if (!Reference)
+      return std::unexpected(Reference.error());
+    if (fitsSigned12(Reference->Offset)) {
+      auto Base = replaceWithRegister(Instruction, OperandIndex, Reference->BaseRegister);
+      if (!Base)
+        return std::unexpected(Base.error());
+      return replaceImmediate(Instruction, OperandIndex + 1U, Reference->Offset);
+    }
+
+    auto Candidates = scratchRegisters();
+    if (!Candidates)
+      return std::unexpected(Candidates.error());
+    auto Scratch = Scavenger.scavenge(Instruction, *Candidates);
+    if (!Scratch)
+      return std::unexpected(Scratch.error());
+    std::optional<FrameIndexReference> Emergency;
+    if (Scratch->RequiresSpill) {
+      const StackObject *Object = emergencyObject(Function);
+      if (Object == nullptr)
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "RISC-V scavenging requires an emergency spill slot");
+      auto Ref = emergencyFrameReference(Function, *Object->description());
+      if (!Ref)
+        return std::unexpected(Ref.error());
+      if (!fitsSigned12(Ref->Offset)) {
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "RISC-V emergency spill slot is out of range");
+      }
+      Emergency = *Ref;
+      auto Saved =
+          emitResolvedScratchAccess(Instruction, Function, Target, Scratch->Reg, *Emergency, false);
+      if (!Saved)
+        return std::unexpected(Saved.error());
+    }
+
+    MachineIRBuilder Builder(Function, Target);
+    auto Point = Builder.setInsertPointBefore(Instruction);
+    if (!Point)
+      return std::unexpected(Point.error());
+    auto Zero = physical(PhysicalRegisterID::X0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    auto Constant = emitConstant(Builder, Scratch->Reg, *Zero, Reference->Offset, std::nullopt);
+    if (!Constant)
+      return std::unexpected(Constant.error());
+    auto Address =
+        emitRegisterAdd(Builder, Scratch->Reg, Reference->BaseRegister, Scratch->Reg, std::nullopt);
+    if (!Address)
+      return std::unexpected(Address.error());
+    auto Base = replaceWithRegister(Instruction, OperandIndex, Scratch->Reg);
+    if (!Base)
+      return std::unexpected(Base.error());
+    auto Offset = replaceImmediate(Instruction, OperandIndex + 1U, 0);
+    if (!Offset)
+      return std::unexpected(Offset.error());
+    if (Emergency) {
+      auto Restored =
+          emitResolvedScratchAccess(Instruction, Function, Target, Scratch->Reg, *Emergency, true);
+      if (!Restored)
+        return std::unexpected(Restored.error());
+    }
+    return {};
+  }
+
+private:
+  [[nodiscard]] Expected<void> emitStackAdjustment(MachineInstr &Anchor, MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   RegisterScavenger &Scavenger,
+                                                   std::int64_t Amount,
+                                                   MachineInstrFlag Flag) const {
+    if (Amount == 0)
+      return {};
+    auto SP = physical(PhysicalRegisterID::X2);
+    if (!SP)
+      return std::unexpected(SP.error());
+    MachineIRBuilder Builder(Function, Target);
+    auto Point = Builder.setInsertPointBefore(Anchor);
+    if (!Point)
+      return std::unexpected(Point.error());
+    if (fitsSigned12(Amount))
+      return emitAddImmediate(Builder, *SP, *SP, Amount, Flag);
+
+    auto Candidates = scratchRegisters();
+    if (!Candidates)
+      return std::unexpected(Candidates.error());
+    auto Scratch = Scavenger.scavenge(Anchor, *Candidates);
+    if (!Scratch)
+      return std::unexpected(Scratch.error());
+    std::optional<FrameIndexReference> Emergency;
+    if (Scratch->RequiresSpill) {
+      const StackObject *Object = emergencyObject(Function);
+      if (Object == nullptr)
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "RISC-V stack adjustment requires an emergency spill slot");
+      auto Ref = emergencyFrameReference(Function, *Object->description());
+      if (!Ref || !fitsSigned12(Ref->Offset))
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "RISC-V emergency spill slot is unavailable");
+      Emergency = *Ref;
+      auto Saved =
+          emitResolvedScratchAccess(Anchor, Function, Target, Scratch->Reg, *Emergency, false);
+      if (!Saved)
+        return std::unexpected(Saved.error());
+    }
+    auto Zero = physical(PhysicalRegisterID::X0);
+    if (!Zero)
+      return std::unexpected(Zero.error());
+    auto Constant = emitConstant(Builder, Scratch->Reg, *Zero, Amount, Flag);
+    if (!Constant)
+      return std::unexpected(Constant.error());
+    auto Adjust = emitRegisterAdd(Builder, *SP, *SP, Scratch->Reg, Flag);
+    if (!Adjust)
+      return std::unexpected(Adjust.error());
+    if (Emergency) {
+      auto Restored =
+          emitResolvedScratchAccess(Anchor, Function, Target, Scratch->Reg, *Emergency, true);
+      if (!Restored)
+        return std::unexpected(Restored.error());
+    }
+    return {};
+  }
+
+  [[nodiscard]] Expected<void>
+  emitResolvedScratchAccess(MachineInstr &Anchor, MachineFunction &Function,
+                            const TargetDescription &Target, PhysicalRegister Scratch,
+                            FrameIndexReference Reference, bool Restore) const {
+    MachineIRBuilder Builder(Function, Target);
+    auto Point =
+        Restore ? Builder.setInsertPointAfter(Anchor) : Builder.setInsertPointBefore(Anchor);
+    if (!Point)
+      return std::unexpected(Point.error());
+    auto Memory = createResolvedStackMemory(
+        Function, Restore ? MemoryAccessFlag::Load : MemoryAccessFlag::Store, Reference.Offset);
+    if (!Memory)
+      return std::unexpected(Memory.error());
+    auto Pending =
+        Builder.buildInstr(targetOpcode(Restore ? InstructionOpcode::LD : InstructionOpcode::SD));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    auto Value = Restore ? Pending->addDef(Register::fromPhysical(Scratch))
+                         : Pending->addUse(Register::fromPhysical(Scratch));
+    if (!Value)
+      return std::unexpected(Value.error());
+    if (auto Result = Pending->addUse(Register::fromPhysical(Reference.BaseRegister)); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addImmediate(Reference.Offset); !Result)
+      return std::unexpected(Result.error());
+    if (auto Result = Pending->addMemOperand(**Memory); !Result)
+      return std::unexpected(Result.error());
+    auto Built = Pending->build();
+    if (!Built)
+      return std::unexpected(Built.error());
+    return {};
+  }
+};
+
+} // namespace
+
+const TargetFrameLowering &frameLowering() noexcept {
+  static const RISCVFrameLowering Info;
+  return Info;
+}
+
+} // namespace rcc::riscv
diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
index e437e18..81fc6dc 100644
--- a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
+++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
 #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"
@@ -13,6 +14,7 @@
 
 #include <algorithm>
 #include <array>
+#include <bit>
 #include <cstddef>
 #include <cstdint>
 #include <optional>
@@ -35,6 +37,20 @@ struct SpillForm final {
   return RegisterClassID::fromValue(static_cast<std::uint32_t>(Value));
 }
 
+[[nodiscard]] std::optional<std::int64_t> immediateValue(const MachineOperand &Operand) noexcept {
+  if (const auto *Immediate = Operand.getIf<std::int64_t>())
+    return *Immediate;
+  const auto *Integer = Operand.getIf<IntegerImmediateOperand>();
+  if (Integer == nullptr || Integer->Value.bitWidth() == 0 || Integer->Value.bitWidth() > 64) {
+    return std::nullopt;
+  }
+  std::uint64_t Raw = Integer->Value.words().empty() ? 0 : Integer->Value.words().front();
+  const std::uint32_t Width = Integer->Value.bitWidth();
+  if (Width < 64 && (Raw & (std::uint64_t{1} << (Width - 1U))) != 0)
+    Raw |= ~std::uint64_t{0} << Width;
+  return std::bit_cast<std::int64_t>(Raw);
+}
+
 [[nodiscard]] constexpr std::optional<SpillForm> spillForm(RegisterClassID Class) noexcept {
   if (Class == registerClassID(RegisterClass::GPR) ||
       Class == registerClassID(RegisterClass::GPRC) ||
@@ -102,6 +118,74 @@ createStackMemoryOperand(MachineIRBuilder &Builder, FrameIndex StackSlot, Memory
 
 class RISCVRegisterAllocationInfo final : public TargetRegisterAllocationInfo {
 public:
+  [[nodiscard]] bool
+  isReservedForFunction(const MachineFunction &Function, PhysicalRegister Reg,
+                        const TargetDescription &Target) const noexcept override {
+    std::uint64_t RequiredAlignment = 16;
+    RequiredAlignment = std::max(
+        RequiredAlignment, Function.frameInfo().state().MaxAlignment.value_or(Alignment{}).bytes());
+    for (const StackObject &Object : Function.frameInfo().objects()) {
+      if (!Object.isTombstone() && !Object.description()->IsDead) {
+        RequiredAlignment = std::max(RequiredAlignment, Object.description()->Align.bytes());
+      }
+    }
+    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() != targetOpcode(InstructionOpcode::ADJCALLSTACKDOWN) &&
+            Instruction->opcode() != targetOpcode(InstructionOpcode::ADJCALLSTACKUP)) {
+          continue;
+        }
+        if (Instruction->operandCount() < 2)
+          continue;
+        const auto Requested = immediateValue(*Instruction->operandAt(1));
+        if (Requested && *Requested > 0 &&
+            std::has_single_bit(static_cast<std::uint64_t>(*Requested))) {
+          RequiredAlignment = std::max(RequiredAlignment, static_cast<std::uint64_t>(*Requested));
+        }
+      }
+    }
+    const bool RequiresRealignment = RequiredAlignment > 16;
+    if (Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X9))
+      return RequiresRealignment;
+    if (Reg.number() != static_cast<std::uint32_t>(PhysicalRegisterID::X8))
+      return false;
+    const MachineFrameState &State = Function.frameInfo().state();
+    bool HasCalls = State.HasCalls;
+    for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr && !HasCalls;
+         Block = Block->next()) {
+      for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+           Instruction = Instruction->next()) {
+        const InstructionDescriptor *Descriptor =
+            Target.instructionDescriptor(Instruction->opcode());
+        if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Call)) {
+          HasCalls = true;
+          break;
+        }
+      }
+    }
+    const bool HasVariableObject =
+        std::ranges::any_of(Function.frameInfo().objects(), [](const StackObject &Object) {
+          return !Object.isTombstone() && !Object.description()->IsDead && Object.isVariableSized();
+        });
+    if (State.IsFrameAddressTaken || State.HasOpaqueSPAdjustment || HasVariableObject ||
+        RequiresRealignment)
+      return true;
+    switch (State.FramePointerPolicy) {
+    case MachineFramePointerPolicy::All:
+    case MachineFramePointerPolicy::Reserved:
+      return true;
+    case MachineFramePointerPolicy::NonLeaf:
+    case MachineFramePointerPolicy::NonLeafNoReserve:
+      return HasCalls;
+    case MachineFramePointerPolicy::None:
+    case MachineFramePointerPolicy::Count:
+      return false;
+    }
+    return false;
+  }
+
   [[nodiscard]] Expected<void> validateSpillReload(RegisterClassID Class,
                                                    const TargetDescription &Target) const override {
     const RegisterClassDesc *Description = Target.registers().registerClass(Class);
diff --git a/backend/unittests/CodeGen/MachineIRCoreTest.cpp b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
index 028afc5..7982b04 100644
--- a/backend/unittests/CodeGen/MachineIRCoreTest.cpp
+++ b/backend/unittests/CodeGen/MachineIRCoreTest.cpp
@@ -438,12 +438,20 @@ void testOwnershipCFGAndMemory(TestContext &Context) {
                  "instruction must reject a block operand from another function");
 
   auto MemOperand = Function->createMemOperand(makeLoadDescription());
+  auto ReplacementMemOperand = Function->createMemOperand(makeLoadDescription());
   auto ForeignMemOperand = OtherFunction->createMemOperand(makeLoadDescription());
-  Context.expect(MemOperand && ForeignMemOperand,
+  Context.expect(MemOperand && ReplacementMemOperand && ForeignMemOperand,
                  "function arena must allocate immutable memory operands");
-  if (MemOperand && ForeignMemOperand) {
+  if (MemOperand && ReplacementMemOperand && ForeignMemOperand) {
     Context.expect((*Instr)->addMemOperand(**MemOperand).has_value(),
                    "instruction must accept a memory operand owned by its function");
+    Context.expect((*Instr)->replaceMemOperand(0, **ReplacementMemOperand).has_value() &&
+                       (*Instr)->memOperands().front() == *ReplacementMemOperand,
+                   "instruction must replace an owned memory operand in place");
+    Context.expect(!(*Instr)->replaceMemOperand(1, **MemOperand) &&
+                       !(*Instr)->replaceMemOperand(0, **ForeignMemOperand) &&
+                       (*Instr)->memOperands().front() == *ReplacementMemOperand,
+                   "invalid memory replacement must fail without mutation");
     Context.expect(!(*Instr)->addMemOperand(**ForeignMemOperand),
                    "instruction must reject a memory operand from another function");
   }
diff --git a/backend/unittests/Support/ErrorTest.cpp b/backend/unittests/Support/ErrorTest.cpp
index 23140e3..af2ece9 100644
--- a/backend/unittests/Support/ErrorTest.cpp
+++ b/backend/unittests/Support/ErrorTest.cpp
@@ -28,6 +28,8 @@ int main() {
     return fail("Error must preserve its message");
   if (rcc::getErrorCodeName(Failure.error().code()) != "parse error")
     return fail("Error code must have a stable name");
+  if (rcc::getErrorCodeName(rcc::ErrorCode::FrameLayoutFailed) != "frame layout failed")
+    return fail("frame-layout errors must have a stable name");
 
   return 0;
 }
diff --git a/backend/unittests/Target/CMakeLists.txt b/backend/unittests/Target/CMakeLists.txt
index ca376da..a114c7f 100644
--- a/backend/unittests/Target/CMakeLists.txt
+++ b/backend/unittests/Target/CMakeLists.txt
@@ -49,6 +49,17 @@ add_test(
   COMMAND RCCBackendRISCVRegisterAllocationTests
 )
 
+add_executable(RCCBackendRISCVFrameLoweringTests RISCVFrameLoweringTest.cpp)
+rcc_backend_configure_target(RCCBackendRISCVFrameLoweringTests)
+target_link_libraries(
+  RCCBackendRISCVFrameLoweringTests
+  PRIVATE RCCBackend::RISCV RCCBackend::CodeGen
+)
+add_test(
+  NAME RCCBackendRISCVFrameLoweringTests
+  COMMAND RCCBackendRISCVFrameLoweringTests
+)
+
 rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/DescriptionGeneratorTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLoweringTest.cpp"
@@ -56,6 +67,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocationTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLoweringTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.h"
 )
@@ -66,5 +78,6 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGenTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVSSAExitTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocationTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RISCVFrameLoweringTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/TestTarget.cpp"
 )
diff --git a/backend/unittests/Target/RISCVFrameLoweringTest.cpp b/backend/unittests/Target/RISCVFrameLoweringTest.cpp
new file mode 100644
index 0000000..7096840
--- /dev/null
+++ b/backend/unittests/Target/RISCVFrameLoweringTest.cpp
@@ -0,0 +1,1361 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineCFIInfo.h"
+#include "rcc/CodeGen/MachineFrameInfo.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/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/PrologueEpilogueInsertion.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetFrameLowering.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+#include "rcc/Target/RISCV/RISCVCallLowering.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 <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++Failures;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return Failures == 0 ? 0 : 1;
+  }
+
+private:
+  int Failures = 0;
+};
+
+struct FunctionFixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  rcc::MachineBasicBlock *Block = nullptr;
+};
+
+class ObservingFrameLowering final : public rcc::TargetFrameLowering {
+public:
+  explicit ObservingFrameLowering(const rcc::TargetFrameLowering &Delegate,
+                                  bool SkipFrameIndexElimination = false) noexcept
+      : Delegate(&Delegate), SkipFrameIndexElimination(SkipFrameIndexElimination) {}
+
+  [[nodiscard]] rcc::Expected<void>
+  prepareFrame(rcc::MachineFunction &Function,
+               const rcc::TargetDescription &Target) const override {
+    PrepareSawUnfrozen = !Function.frameInfo().isFrozen();
+    return Delegate->prepareFrame(Function, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  insertCalleeSavedSpillsAndRestores(rcc::MachineFunction &Function,
+                                     const rcc::TargetDescription &Target) const override {
+    InsertSawUnfrozen = !Function.frameInfo().isFrozen();
+    return Delegate->insertCalleeSavedSpillsAndRestores(Function, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  processFunctionBeforeFrameFinalized(rcc::MachineFunction &Function,
+                                      const rcc::TargetDescription &Target) const override {
+    return Delegate->processFunctionBeforeFrameFinalized(Function, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  finalizeFrame(rcc::MachineFunction &Function,
+                const rcc::TargetDescription &Target) const override {
+    FinalizeSawUnfrozen = !Function.frameInfo().isFrozen();
+    bool HasCalleeSave = false;
+    for (const rcc::MachineInstr *Instruction : Function.allInstructions()) {
+      if (Instruction == nullptr || Instruction->parent() == nullptr)
+        continue;
+      for (const rcc::MachineOperand &Operand : Instruction->operands()) {
+        const auto *Frame = Operand.getIf<rcc::FrameIndexOperand>();
+        const rcc::StackObject *Object =
+            Frame == nullptr ? nullptr : Function.frameInfo().object(Frame->Index);
+        HasCalleeSave |=
+            Object != nullptr && Object->description()->Kind == rcc::StackObjectKind::CalleeSaved;
+      }
+    }
+    FinalizeSawCalleeSave = HasCalleeSave;
+    auto Result = Delegate->finalizeFrame(Function, Target);
+    FinalizeProducedFrozen = Result && Function.frameInfo().isFrozen();
+    return Result;
+  }
+
+  [[nodiscard]] bool
+  isCallFramePseudo(const rcc::MachineInstr &Instruction) const noexcept override {
+    return Delegate->isCallFramePseudo(Instruction);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  eliminateCallFramePseudo(rcc::MachineInstr &Instruction, rcc::MachineFunction &Function,
+                           const rcc::TargetDescription &Target,
+                           rcc::RegisterScavenger &Scavenger) const override {
+    return Delegate->eliminateCallFramePseudo(Instruction, Function, Target, Scavenger);
+  }
+
+  [[nodiscard]] rcc::Expected<void> emitPrologue(rcc::MachineFunction &Function,
+                                                 const rcc::TargetDescription &Target,
+                                                 rcc::RegisterScavenger &Scavenger) const override {
+    PrologueSawFrozen = Function.frameInfo().isFrozen();
+    return Delegate->emitPrologue(Function, Target, Scavenger);
+  }
+
+  [[nodiscard]] bool
+  isEpilogueTerminator(const rcc::MachineInstr &Instruction,
+                       const rcc::TargetDescription &Target) const noexcept override {
+    return Delegate->isEpilogueTerminator(Instruction, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<void> emitEpilogue(rcc::MachineBasicBlock &Block,
+                                                 rcc::MachineInstr &Terminator,
+                                                 rcc::MachineFunction &Function,
+                                                 const rcc::TargetDescription &Target,
+                                                 rcc::RegisterScavenger &Scavenger) const override {
+    EpilogueSawFrozen = Function.frameInfo().isFrozen();
+    return Delegate->emitEpilogue(Block, Terminator, Function, Target, Scavenger);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  processFunctionBeforeFrameIndexElimination(rcc::MachineFunction &Function,
+                                             const rcc::TargetDescription &Target) const override {
+    return Delegate->processFunctionBeforeFrameIndexElimination(Function, Target);
+  }
+
+  [[nodiscard]] rcc::Expected<rcc::FrameIndexReference>
+  getFrameIndexReference(const rcc::MachineFunction &Function, const rcc::MachineInstr &Instruction,
+                         rcc::FrameIndex Index, std::int64_t OperandOffset) const override {
+    return Delegate->getFrameIndexReference(Function, Instruction, Index, OperandOffset);
+  }
+
+  [[nodiscard]] rcc::Expected<void>
+  eliminateFrameIndex(rcc::MachineInstr &Instruction, std::size_t OperandIndex,
+                      rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                      rcc::RegisterScavenger &Scavenger) const override {
+    if (SkipFrameIndexElimination)
+      return {};
+    return Delegate->eliminateFrameIndex(Instruction, OperandIndex, Function, Target, Scavenger);
+  }
+
+  mutable bool PrepareSawUnfrozen = false;
+  mutable bool InsertSawUnfrozen = false;
+  mutable bool FinalizeSawUnfrozen = false;
+  mutable bool FinalizeSawCalleeSave = false;
+  mutable bool FinalizeProducedFrozen = false;
+  mutable bool PrologueSawFrozen = false;
+  mutable bool EpilogueSawFrozen = false;
+
+private:
+  const rcc::TargetFrameLowering *Delegate;
+  bool SkipFrameIndexElimination = false;
+};
+
+[[nodiscard]] constexpr rcc::Opcode opcode(rcc::riscv::InstructionOpcode Value) noexcept {
+  return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] rcc::PhysicalRegister physReg(rcc::riscv::PhysicalRegisterID ID) {
+  return *rcc::riscv::physicalRegister(ID);
+}
+
+[[nodiscard]] rcc::Register physical(rcc::riscv::PhysicalRegisterID ID) {
+  return rcc::Register::fromPhysical(physReg(ID));
+}
+
+[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name,
+                                                            std::uint64_t StableID) {
+  auto Function = rcc::MachineFunction::create(std::move(Name),
+                                               rcc::MachineFunctionStableID::fromValue(StableID));
+  if (!Function)
+    return std::unexpected(Function.error());
+  auto Block = (*Function)->createBasicBlock();
+  if (!Block)
+    return std::unexpected(Block.error());
+  if (auto Result = (*Function)->appendBlock(**Block); !Result)
+    return std::unexpected(Result.error());
+  return FunctionFixture{std::move(*Function), *Block};
+}
+
+void setFramePassProperties(rcc::MachineFunction &Function) {
+  for (const rcc::MachineFunctionProperty Property : {
+           rcc::MachineFunctionProperty::Legalized,
+           rcc::MachineFunctionProperty::RegBankSelected,
+           rcc::MachineFunctionProperty::Selected,
+           rcc::MachineFunctionProperty::NoPHIs,
+           rcc::MachineFunctionProperty::TiedOpsRewritten,
+           rcc::MachineFunctionProperty::NoVRegs,
+       }) {
+    Function.properties().set(Property);
+  }
+}
+
+[[nodiscard]] rcc::Expected<void>
+runFrameLoweringWith(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                     const rcc::TargetFrameLowering &FrameLowering) {
+  setFramePassProperties(Function);
+  rcc::MachinePassManager Pipeline;
+  auto Added =
+      Pipeline.addPass(std::make_unique<rcc::PrologueEpilogueInsertionPass>(FrameLowering));
+  if (!Added)
+    return std::unexpected(Added.error());
+  rcc::MachineAnalysisManager Analyses;
+  return Pipeline.run(Function, Target, Analyses);
+}
+
+[[nodiscard]] rcc::Expected<void> runFrameLowering(rcc::MachineFunction &Function,
+                                                   const rcc::TargetDescription &Target) {
+  return runFrameLoweringWith(Function, Target, rcc::riscv::frameLowering());
+}
+
+[[nodiscard]] rcc::Expected<rcc::FrameIndex>
+createStackObject(rcc::MachineFunction &Function, rcc::StackObjectKind Kind,
+                  std::optional<std::uint64_t> Size, std::uint64_t Alignment,
+                  std::optional<std::int64_t> Offset = std::nullopt) {
+  auto Align = rcc::Alignment::create(Alignment);
+  if (!Align)
+    return std::unexpected(Align.error());
+  rcc::StackObjectDesc Description;
+  Description.Kind = Kind;
+  Description.Size = Size;
+  Description.Align = *Align;
+  Description.Offset = Offset;
+  return Function.frameInfo().createObject(std::move(Description));
+}
+
+[[nodiscard]] rcc::Expected<const rcc::MachineMemOperand *>
+createStackMemory(rcc::MachineFunction &Function, rcc::FrameIndex Index,
+                  rcc::MemoryAccessFlag Access, std::int64_t Offset) {
+  auto Size = rcc::MemorySize::fixed(8);
+  auto Align = rcc::Alignment::create(8);
+  if (!Size || !Align)
+    return rcc::makeUnexpected(rcc::ErrorCode::InternalError, "invalid test memory facts");
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = {Access};
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = rcc::MemoryBase::frameIndex(Index);
+  Description.Offset = Offset;
+  return Function.createMemOperand(std::move(Description));
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildStackAccess(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                 rcc::MachineBasicBlock &Block, rcc::riscv::InstructionOpcode OpcodeValue,
+                 rcc::Register Value, rcc::FrameIndex Index, std::int64_t Offset) {
+  const bool IsLoad = OpcodeValue == rcc::riscv::InstructionOpcode::LD ||
+                      OpcodeValue == rcc::riscv::InstructionOpcode::FLD;
+  auto Memory = createStackMemory(
+      Function, Index, IsLoad ? rcc::MemoryAccessFlag::Load : rcc::MemoryAccessFlag::Store, Offset);
+  if (!Memory)
+    return std::unexpected(Memory.error());
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(OpcodeValue));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto RegisterResult = IsLoad ? Pending->addDef(Value) : Pending->addUse(Value);
+  if (!RegisterResult)
+    return std::unexpected(RegisterResult.error());
+  if (auto Result = Pending->addFrameIndex(Index); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addImmediate(Offset); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addMemOperand(**Memory); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildAddImmediate(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                  rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source,
+                  std::int64_t Immediate) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADDI));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addDef(Destination); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addUse(Source); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addImmediate(Immediate); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildAdd(rcc::MachineFunction &Function,
+                                                          const rcc::TargetDescription &Target,
+                                                          rcc::MachineBasicBlock &Block,
+                                                          rcc::Register Destination,
+                                                          rcc::Register Left, rcc::Register Right) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADD));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addDef(Destination); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addUse(Left); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addUse(Right); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildMoveToDouble(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                  rcc::MachineBasicBlock &Block, rcc::Register Destination, rcc::Register Source) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::FMV_D_X));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addDef(Destination); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addUse(Source); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildCallFramePseudo(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                     rcc::MachineBasicBlock &Block, rcc::riscv::InstructionOpcode OpcodeValue,
+                     std::int64_t Amount, std::int64_t Alignment = 16) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(OpcodeValue));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addImmediate(Amount); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addImmediate(Alignment); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildRegisterMaskClobber(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                         rcc::MachineBasicBlock &Block, rcc::PhysicalRegister Clobbered) {
+  std::uint64_t Preserved = ~std::uint64_t{1};
+  Preserved &= ~(std::uint64_t{1} << Clobbered.number());
+  auto Mask = std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{Preserved});
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::INLINEASM));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addRegisterMask(std::move(Mask)); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildIndirectTail(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+                  rcc::MachineBasicBlock &Block, rcc::Register Callee) {
+  auto Mask =
+      std::make_shared<const rcc::RegisterMask>(std::vector<std::uint64_t>{~std::uint64_t{1}});
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::PseudoTAIL));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  if (auto Result = Pending->addUse(Callee); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addImmediate(1); !Result)
+    return std::unexpected(Result.error());
+  if (auto Result = Pending->addRegisterMask(std::move(Mask)); !Result)
+    return std::unexpected(Result.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *> buildReturn(rcc::MachineFunction &Function,
+                                                             const rcc::TargetDescription &Target,
+                                                             rcc::MachineBasicBlock &Block) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  if (auto Result = Builder.setInsertPoint(Block); !Result)
+    return std::unexpected(Result.error());
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::PseudoRET));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  return Pending->build();
+}
+
+[[nodiscard]] std::vector<rcc::MachineInstr *> instructions(rcc::MachineBasicBlock &Block) {
+  std::vector<rcc::MachineInstr *> Result;
+  for (rcc::MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    Result.push_back(Instruction);
+  }
+  return Result;
+}
+
+[[nodiscard]] std::size_t countOpcode(const rcc::MachineFunction &Function,
+                                      rcc::Opcode OpcodeValue) {
+  std::size_t Result = 0;
+  for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      Result += Instruction->opcode() == OpcodeValue ? 1U : 0U;
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] std::size_t countOpcode(const rcc::MachineFunction &Function,
+                                      rcc::riscv::InstructionOpcode OpcodeValue) {
+  return countOpcode(Function, opcode(OpcodeValue));
+}
+
+[[nodiscard]] std::optional<rcc::PhysicalRegister> registerAt(const rcc::MachineInstr &Instruction,
+                                                              std::size_t Index) {
+  const rcc::MachineOperand *Operand = Instruction.operandAt(Index);
+  if (Operand == nullptr)
+    return std::nullopt;
+  const rcc::Register *Reg = Operand->getIf<rcc::Register>();
+  if (Reg == nullptr || !Reg->isPhysical())
+    return std::nullopt;
+  return Reg->physicalRegister();
+}
+
+[[nodiscard]] std::optional<std::int64_t> immediateAt(const rcc::MachineInstr &Instruction,
+                                                      std::size_t Index) {
+  const rcc::MachineOperand *Operand = Instruction.operandAt(Index);
+  if (Operand == nullptr)
+    return std::nullopt;
+  const auto *Immediate = Operand->getIf<std::int64_t>();
+  return Immediate == nullptr ? std::nullopt : std::optional<std::int64_t>(*Immediate);
+}
+
+[[nodiscard]] bool hasFrameIndex(const rcc::MachineFunction &Function) {
+  for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      for (const rcc::MachineOperand &Operand : Instruction->operands()) {
+        if (Operand.kind() == rcc::MachineOperand::Kind::FrameIndex)
+          return true;
+      }
+      for (const rcc::MachineMemOperand *Memory : Instruction->memOperands()) {
+        if (Memory->description().Base.frameIndex())
+          return true;
+      }
+    }
+  }
+  return false;
+}
+
+[[nodiscard]] const rcc::StackObject *findStackObject(const rcc::MachineFunction &Function,
+                                                      rcc::StackObjectKind Kind) {
+  const auto Position =
+      std::ranges::find_if(Function.frameInfo().objects(), [Kind](const rcc::StackObject &Object) {
+        return !Object.isTombstone() && !Object.description()->IsDead &&
+               Object.description()->Kind == Kind;
+      });
+  return Position == Function.frameInfo().objects().end() ? nullptr : &*Position;
+}
+
+[[nodiscard]] const rcc::StackObject *findCalleeSave(const rcc::MachineFunction &Function,
+                                                     rcc::PhysicalRegister Reg) {
+  const auto Position =
+      std::ranges::find_if(Function.frameInfo().objects(), [Reg](const rcc::StackObject &Object) {
+        return !Object.isTombstone() && !Object.description()->IsDead &&
+               Object.description()->CalleeSavedRegister == Reg;
+      });
+  return Position == Function.frameInfo().objects().end() ? nullptr : &*Position;
+}
+
+void testLeafAndSmallFrame(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Leaf = createFunction("leaf", 1);
+  if (!Leaf || !buildReturn(*Leaf->Function, Target, *Leaf->Block))
+    return;
+  auto LoweredLeaf = runFrameLowering(*Leaf->Function, Target);
+  Context.expect(
+      LoweredLeaf && Leaf->Function->frameInfo().isFrozen() &&
+          Leaf->Function->frameInfo().state().StackSize == 0 &&
+          instructions(*Leaf->Block).size() == 1 &&
+          Leaf->Function->properties().has(rcc::MachineFunctionProperty::FrameFinalized) &&
+          Leaf->Function->properties().has(rcc::MachineFunctionProperty::NoFrameIndices),
+      "leaf frame lowering must freeze an empty frame without extra code");
+
+  auto DeadObject = createFunction("dead-stack-object", 24);
+  if (!DeadObject)
+    return;
+  auto DeadSlot = createStackObject(*DeadObject->Function, rcc::StackObjectKind::Default, 32, 16);
+  if (!DeadSlot || !DeadObject->Function->frameInfo().markObjectDead(*DeadSlot) ||
+      !buildReturn(*DeadObject->Function, Target, *DeadObject->Block)) {
+    return;
+  }
+  auto DeadResult = runFrameLowering(*DeadObject->Function, Target);
+  Context.expect(DeadResult && DeadObject->Function->frameInfo().isFrozen() &&
+                     DeadObject->Function->frameInfo().state().StackSize == 0,
+                 "dead stack objects must not require layout offsets or stack space");
+
+  auto Small = createFunction("small-frame", 2);
+  if (!Small)
+    return;
+  auto Slot = createStackObject(*Small->Function, rcc::StackObjectKind::SpillSlot, 8, 8);
+  if (!Slot)
+    return;
+  auto Store =
+      buildStackAccess(*Small->Function, Target, *Small->Block, rcc::riscv::InstructionOpcode::SD,
+                       physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0);
+  if (!Store || !buildReturn(*Small->Function, Target, *Small->Block))
+    return;
+  auto Lowered = runFrameLowering(*Small->Function, Target);
+  Context.expect(Lowered && Small->Function->frameInfo().state().StackSize == 16 &&
+                     !hasFrameIndex(*Small->Function) &&
+                     countOpcode(*Small->Function, rcc::riscv::InstructionOpcode::ADDI) == 2,
+                 "a small frame must use one aligned allocation and eliminate every FrameIndex");
+  const auto SmallCFI = Small->Function->cfiInfo().instructions();
+  Context.expect(
+      Lowered && SmallCFI.size() == 4 &&
+          SmallCFI.front().operation() == rcc::MachineCFIOperation::DefCFA &&
+          SmallCFI.front().getIf<rcc::MachineCFIRegisterOffsetRule>()->Offset == 16 &&
+          SmallCFI[1].operation() == rcc::MachineCFIOperation::RememberState &&
+          SmallCFI[2].operation() == rcc::MachineCFIOperation::DefCFA &&
+          SmallCFI[2].getIf<rcc::MachineCFIRegisterOffsetRule>()->Offset == 0 &&
+          SmallCFI.back().operation() == rcc::MachineCFIOperation::RestoreState &&
+          countOpcode(*Small->Function, rcc::opcode(rcc::GenericOpcode::CFI_INSTRUCTION)) == 4,
+      "small-frame CFI must track the allocated and restored CFA exactly");
+  Context.expect(Lowered && registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) &&
+                     immediateAt(**Store, 2) == 0 && (*Store)->memOperands().size() == 1 &&
+                     (*Store)->memOperands().front()->description().Base.kind() ==
+                         rcc::MemoryBase::Kind::Stack &&
+                     (*Store)->memOperands().front()->description().Offset == 0,
+                 "small-frame instruction and MMO addresses must agree after elimination");
+
+  auto MultiExit = createFunction("multi-exit-frame", 14);
+  if (!MultiExit)
+    return;
+  auto SecondBlock = MultiExit->Function->createBasicBlock();
+  if (!SecondBlock || !MultiExit->Function->appendBlock(**SecondBlock))
+    return;
+  auto MultiSlot = createStackObject(*MultiExit->Function, rcc::StackObjectKind::Default, 8, 8);
+  if (!MultiSlot ||
+      !buildStackAccess(*MultiExit->Function, Target, *MultiExit->Block,
+                        rcc::riscv::InstructionOpcode::SD,
+                        physical(rcc::riscv::PhysicalRegisterID::X10), *MultiSlot, 0) ||
+      !buildReturn(*MultiExit->Function, Target, *MultiExit->Block) ||
+      !buildReturn(*MultiExit->Function, Target, **SecondBlock)) {
+    return;
+  }
+  auto MultiResult = runFrameLowering(*MultiExit->Function, Target);
+  const auto MultiCFI = MultiExit->Function->cfiInfo().instructions();
+  const auto CountCFIOperation = [MultiCFI](rcc::MachineCFIOperation Operation) {
+    return std::ranges::count_if(MultiCFI,
+                                 [Operation](const rcc::MachineCFIInstruction &Instruction) {
+                                   return Instruction.operation() == Operation;
+                                 });
+  };
+  Context.expect(MultiResult && MultiCFI.size() == 7 &&
+                     CountCFIOperation(rcc::MachineCFIOperation::RememberState) == 2 &&
+                     CountCFIOperation(rcc::MachineCFIOperation::RestoreState) == 2,
+                 "multiple epilogues must isolate their linear CFI state");
+}
+
+void testCalleeSavedRegisters(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("callee-saves", 3);
+  if (!Fixture)
+    return;
+  const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0);
+  if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::X1), Zero, 1) ||
+      !buildAddImmediate(*Fixture->Function, Target, *Fixture->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::X9), Zero, 2) ||
+      !buildMoveToDouble(*Fixture->Function, Target, *Fixture->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::F8), Zero) ||
+      !buildReturn(*Fixture->Function, Target, *Fixture->Block)) {
+    return;
+  }
+  auto Lowered = runFrameLowering(*Fixture->Function, Target);
+  const auto Saved = Fixture->Function->records().calleeSavedRegisters();
+  Context.expect(
+      Lowered && Saved.size() == 3 && Saved[0] == physReg(rcc::riscv::PhysicalRegisterID::X1) &&
+          Saved[1] == physReg(rcc::riscv::PhysicalRegisterID::X9) &&
+          Saved[2] == physReg(rcc::riscv::PhysicalRegisterID::F8) &&
+          countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::SD) == 2 &&
+          countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::FSD) == 1 &&
+          countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::LD) == 2 &&
+          countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::FLD) == 1,
+      "used GPR, FPR, and return-address callee saves must have symmetric save/restore code");
+  Context.expect(
+      Lowered && Fixture->Function->cfiInfo().instructions().size() == 10 &&
+          countOpcode(*Fixture->Function, rcc::opcode(rcc::GenericOpcode::CFI_INSTRUCTION)) == 10,
+      "callee-save CFI must describe every save, restore, and CFA transition");
+  Context.expect(
+      findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::X1)) != nullptr &&
+          findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::X9)) !=
+              nullptr &&
+          findCalleeSave(*Fixture->Function, physReg(rcc::riscv::PhysicalRegisterID::F8)) !=
+              nullptr &&
+          !hasFrameIndex(*Fixture->Function),
+      "callee-save records, stack objects, and eliminated operands must remain consistent");
+
+  auto MaskFixture = createFunction("regmask-callee-save", 15);
+  const rcc::PhysicalRegister X18 = physReg(rcc::riscv::PhysicalRegisterID::X18);
+  if (!MaskFixture ||
+      !buildRegisterMaskClobber(*MaskFixture->Function, Target, *MaskFixture->Block, X18) ||
+      !buildReturn(*MaskFixture->Function, Target, *MaskFixture->Block)) {
+    return;
+  }
+  auto MaskLowered = runFrameLowering(*MaskFixture->Function, Target);
+  Context.expect(MaskLowered &&
+                     MaskFixture->Function->records().calleeSavedRegisters().size() == 1 &&
+                     MaskFixture->Function->records().calleeSavedRegisters().front() == X18 &&
+                     countOpcode(*MaskFixture->Function, rcc::riscv::InstructionOpcode::SD) == 1 &&
+                     countOpcode(*MaskFixture->Function, rcc::riscv::InstructionOpcode::LD) == 1,
+                 "RegMask clobbers must participate in callee-save discovery");
+
+  auto NoRestore = createFunction("callee-save-no-restore", 16);
+  auto Align8 = rcc::Alignment::create(8);
+  if (!NoRestore || !Align8)
+    return;
+  rcc::StackObjectDesc NoRestoreDescription;
+  NoRestoreDescription.Kind = rcc::StackObjectKind::CalleeSaved;
+  NoRestoreDescription.Size = 8;
+  NoRestoreDescription.Align = *Align8;
+  NoRestoreDescription.CalleeSavedRegister = X18;
+  NoRestoreDescription.CalleeSavedRestored = false;
+  if (!NoRestore->Function->frameInfo().createObject(std::move(NoRestoreDescription)) ||
+      !buildReturn(*NoRestore->Function, Target, *NoRestore->Block)) {
+    return;
+  }
+  auto NoRestoreResult = runFrameLowering(*NoRestore->Function, Target);
+  Context.expect(
+      NoRestoreResult &&
+          countOpcode(*NoRestore->Function, rcc::riscv::InstructionOpcode::SD) == 1 &&
+          countOpcode(*NoRestore->Function, rcc::riscv::InstructionOpcode::LD) == 0 &&
+          NoRestore->Function->frameInfo().state().RestorePoints.empty(),
+      "CalleeSavedRestored=false must suppress the restore without suppressing the save");
+}
+
+void testFramePointerAndFixedObjects(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("frame-pointer", 4);
+  if (!Fixture)
+    return;
+  rcc::MachineFrameState State = Fixture->Function->frameInfo().state();
+  State.FramePointerPolicy = rcc::MachineFramePointerPolicy::All;
+  if (!Fixture->Function->frameInfo().setState(State))
+    return;
+  auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8, 8);
+  auto Fixed = createStackObject(*Fixture->Function, rcc::StackObjectKind::FixedABI, 8, 8, 16);
+  auto Variable =
+      createStackObject(*Fixture->Function, rcc::StackObjectKind::VariableSized, std::nullopt, 16);
+  if (!Local || !Fixed || !Variable)
+    return;
+  auto LocalLoad = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                    rcc::riscv::InstructionOpcode::LD,
+                                    physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 0);
+  auto FixedLoad = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                    rcc::riscv::InstructionOpcode::LD,
+                                    physical(rcc::riscv::PhysicalRegisterID::X11), *Fixed, 0);
+  if (!LocalLoad || !FixedLoad || !buildReturn(*Fixture->Function, Target, *Fixture->Block)) {
+    return;
+  }
+  auto Lowered = runFrameLowering(*Fixture->Function, Target);
+  const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8);
+  Context.expect(Lowered && registerAt(**LocalLoad, 1) == FP &&
+                     immediateAt(**LocalLoad, 2) == -16 && registerAt(**FixedLoad, 1) == FP &&
+                     immediateAt(**FixedLoad, 2) == 16 &&
+                     findCalleeSave(*Fixture->Function, FP) != nullptr,
+                 "FP frames must address locals below and fixed ABI objects above incoming SP");
+
+  auto Preallocated = createFunction("preallocated-local-frame", 13);
+  if (!Preallocated)
+    return;
+  rcc::MachineFrameState PreallocatedState = Preallocated->Function->frameInfo().state();
+  PreallocatedState.LocalFrameSize = 32;
+  if (!Preallocated->Function->frameInfo().setState(PreallocatedState))
+    return;
+  auto Align8 = rcc::Alignment::create(8);
+  if (!Align8)
+    return;
+  rcc::StackObjectDesc PreallocatedDescription;
+  PreallocatedDescription.Size = 8;
+  PreallocatedDescription.Align = *Align8;
+  PreallocatedDescription.LocalOffset = 16;
+  auto PreallocatedObject =
+      Preallocated->Function->frameInfo().createObject(std::move(PreallocatedDescription));
+  if (!PreallocatedObject)
+    return;
+  auto PreallocatedStore = buildStackAccess(
+      *Preallocated->Function, Target, *Preallocated->Block, rcc::riscv::InstructionOpcode::SD,
+      physical(rcc::riscv::PhysicalRegisterID::X10), *PreallocatedObject, 0);
+  if (!PreallocatedStore || !buildReturn(*Preallocated->Function, Target, *Preallocated->Block)) {
+    return;
+  }
+  auto PreallocatedResult = runFrameLowering(*Preallocated->Function, Target);
+  Context.expect(
+      PreallocatedResult && Preallocated->Function->frameInfo().state().StackSize == 32 &&
+          Preallocated->Function->frameInfo().state().LocalFrameSize == 32 &&
+          registerAt(**PreallocatedStore, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) &&
+          immediateAt(**PreallocatedStore, 2) == 16,
+      "preallocated local blobs must preserve localFrameSize and local-offset semantics");
+}
+
+void testStackRealignment(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("realigned-frame", 5);
+  if (!Fixture)
+    return;
+  auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 32, 32);
+  if (!Local)
+    return;
+  auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 0);
+  if (!Store || !buildReturn(*Fixture->Function, Target, *Fixture->Block))
+    return;
+
+  const auto &RA = rcc::riscv::registerAllocationInfo();
+  const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8);
+  const rcc::PhysicalRegister BP = physReg(rcc::riscv::PhysicalRegisterID::X9);
+  Context.expect(RA.isReservedForFunction(*Fixture->Function, FP, Target) &&
+                     RA.isReservedForFunction(*Fixture->Function, BP, Target),
+                 "stack realignment must reserve both FP and BP before allocation");
+
+  auto Lowered = runFrameLowering(*Fixture->Function, Target);
+  const bool Valid = Lowered && Fixture->Function->frameInfo().stackAlignment().bytes() == 32 &&
+                     Fixture->Function->frameInfo().state().StackSize == 64 &&
+                     registerAt(**Store, 1) == BP && immediateAt(**Store, 2) == 32 &&
+                     countOpcode(*Fixture->Function, rcc::riscv::InstructionOpcode::ANDI) == 1 &&
+                     findCalleeSave(*Fixture->Function, FP) != nullptr &&
+                     findCalleeSave(*Fixture->Function, BP) != nullptr;
+  Context.expect(Valid,
+                 "over-aligned frames must align SP and use a preserved aligned base pointer");
+  const auto CFI = Fixture->Function->cfiInfo().instructions();
+  const std::size_t Expressions = static_cast<std::size_t>(
+      std::ranges::count_if(CFI, [](const rcc::MachineCFIInstruction &Instruction) {
+        const auto *Escape = Instruction.getIf<rcc::MachineCFIEscapeRule>();
+        return Escape != nullptr && !Escape->Bytes.empty() && Escape->Bytes.front() == 0x10U;
+      }));
+  Context.expect(Lowered && Expressions == 2,
+                 "realigned callee saves must use BP-relative DWARF expressions");
+}
+
+void testCallFrames(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Reserved = createFunction("reserved-call-frame", 6);
+  if (!Reserved || !Reserved->Function->frameInfo().setMaxCallFrameSize(48))
+    return;
+  auto Align16 = rcc::Alignment::create(16);
+  if (!Align16)
+    return;
+  rcc::StackObjectDesc OutgoingDescription;
+  OutgoingDescription.Kind = rcc::StackObjectKind::Target;
+  OutgoingDescription.Size = 8;
+  OutgoingDescription.Align = *Align16;
+  OutgoingDescription.LocalOffset = 32;
+  OutgoingDescription.TargetFlags =
+      static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument);
+  auto Outgoing = Reserved->Function->frameInfo().createObject(std::move(OutgoingDescription));
+  if (!Outgoing)
+    return;
+  auto OutgoingStore = buildStackAccess(
+      *Reserved->Function, Target, *Reserved->Block, rcc::riscv::InstructionOpcode::SD,
+      physical(rcc::riscv::PhysicalRegisterID::X10), *Outgoing, 0);
+  if (!OutgoingStore ||
+      !buildCallFramePseudo(*Reserved->Function, Target, *Reserved->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48) ||
+      !buildCallFramePseudo(*Reserved->Function, Target, *Reserved->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48) ||
+      !buildReturn(*Reserved->Function, Target, *Reserved->Block)) {
+    return;
+  }
+  auto ReservedResult = runFrameLowering(*Reserved->Function, Target);
+  Context.expect(
+      ReservedResult && Reserved->Function->frameInfo().state().StackSize == 48 &&
+          countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) == 0 &&
+          countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 0 &&
+          countOpcode(*Reserved->Function, rcc::riscv::InstructionOpcode::ADDI) == 2 &&
+          registerAt(**OutgoingStore, 1) == physReg(rcc::riscv::PhysicalRegisterID::X2) &&
+          immediateAt(**OutgoingStore, 2) == 32,
+      "reserved call frames must fold call pseudos into the fixed frame");
+
+  auto Computed = createFunction("computed-call-frame", 17);
+  if (!Computed)
+    return;
+  auto ComputedOutgoingAlign = rcc::Alignment::create(16);
+  if (!ComputedOutgoingAlign)
+    return;
+  rcc::StackObjectDesc ComputedOutgoingDescription;
+  ComputedOutgoingDescription.Kind = rcc::StackObjectKind::Target;
+  ComputedOutgoingDescription.Size = 8;
+  ComputedOutgoingDescription.Align = *ComputedOutgoingAlign;
+  ComputedOutgoingDescription.LocalOffset = 48;
+  ComputedOutgoingDescription.TargetFlags =
+      static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument);
+  auto ComputedOutgoing =
+      Computed->Function->frameInfo().createObject(std::move(ComputedOutgoingDescription));
+  auto ComputedLocal = createStackObject(*Computed->Function, rcc::StackObjectKind::Default, 8, 8);
+  if (!ComputedOutgoing || !ComputedLocal ||
+      !buildStackAccess(*Computed->Function, Target, *Computed->Block,
+                        rcc::riscv::InstructionOpcode::SD,
+                        physical(rcc::riscv::PhysicalRegisterID::X10), *ComputedOutgoing, 0) ||
+      !buildStackAccess(*Computed->Function, Target, *Computed->Block,
+                        rcc::riscv::InstructionOpcode::SD,
+                        physical(rcc::riscv::PhysicalRegisterID::X11), *ComputedLocal, 0) ||
+      !buildCallFramePseudo(*Computed->Function, Target, *Computed->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48, 64) ||
+      !buildCallFramePseudo(*Computed->Function, Target, *Computed->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48, 64) ||
+      !buildReturn(*Computed->Function, Target, *Computed->Block)) {
+    return;
+  }
+  auto ComputedResult = runFrameLowering(*Computed->Function, Target);
+  const rcc::StackObject *ComputedLocalObject =
+      Computed->Function->frameInfo().object(*ComputedLocal);
+  Context.expect(ComputedResult && Computed->Function->frameInfo().maxCallFrameSize() == 64 &&
+                     Computed->Function->frameInfo().stackAlignment().bytes() == 64 &&
+                     Computed->Function->frameInfo().state().StackSize == 128 &&
+                     ComputedLocalObject != nullptr &&
+                     ComputedLocalObject->description()->Offset >= 64,
+                 "PEI must compute and align the reserved call frame from call-frame pseudos");
+
+  auto Mismatched = createFunction("mismatched-call-frame", 18);
+  if (!Mismatched ||
+      !buildCallFramePseudo(*Mismatched->Function, Target, *Mismatched->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 48, 16) ||
+      !buildCallFramePseudo(*Mismatched->Function, Target, *Mismatched->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 48, 32) ||
+      !buildReturn(*Mismatched->Function, Target, *Mismatched->Block)) {
+    return;
+  }
+  auto MismatchResult = runFrameLowering(*Mismatched->Function, Target);
+  Context.expect(
+      !MismatchResult && MismatchResult.error().code() == rcc::ErrorCode::VerificationError &&
+          !Mismatched->Function->frameInfo().isFrozen() &&
+          countOpcode(*Mismatched->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) ==
+              1 &&
+          countOpcode(*Mismatched->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 1,
+      "mismatched call-frame pairs must fail transactionally");
+
+  auto Unmatched = createFunction("unmatched-call-frame", 19);
+  if (!Unmatched ||
+      !buildCallFramePseudo(*Unmatched->Function, Target, *Unmatched->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 32) ||
+      !buildReturn(*Unmatched->Function, Target, *Unmatched->Block)) {
+    return;
+  }
+  auto UnmatchedResult = runFrameLowering(*Unmatched->Function, Target);
+  Context.expect(!UnmatchedResult &&
+                     UnmatchedResult.error().code() == rcc::ErrorCode::VerificationError &&
+                     !Unmatched->Function->frameInfo().isFrozen(),
+                 "unmatched call-frame setup must fail transactionally");
+
+  auto Dynamic = createFunction("dynamic-call-frame", 7);
+  if (!Dynamic)
+    return;
+  auto Variable =
+      createStackObject(*Dynamic->Function, rcc::StackObjectKind::DynamicAlloca, std::nullopt, 16);
+  if (!Variable ||
+      !buildCallFramePseudo(*Dynamic->Function, Target, *Dynamic->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 4096, 32) ||
+      !buildCallFramePseudo(*Dynamic->Function, Target, *Dynamic->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 4096, 32) ||
+      !buildReturn(*Dynamic->Function, Target, *Dynamic->Block)) {
+    return;
+  }
+  Context.expect(rcc::riscv::registerAllocationInfo().isReservedForFunction(
+                     *Dynamic->Function, physReg(rcc::riscv::PhysicalRegisterID::X9), Target),
+                 "over-aligned call frames must reserve BP before register allocation");
+  auto DynamicResult = runFrameLowering(*Dynamic->Function, Target);
+  Context.expect(
+      DynamicResult &&
+          countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN) == 0 &&
+          countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADJCALLSTACKUP) == 0 &&
+          countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ADD) >= 2 &&
+          countOpcode(*Dynamic->Function, rcc::riscv::InstructionOpcode::ANDI) == 1 &&
+          findStackObject(*Dynamic->Function, rcc::StackObjectKind::EmergencySpill) != nullptr,
+      "dynamic large call frames must materialize SP adjustments and reserve emergency space");
+
+  auto DynamicSpill = createFunction("dynamic-call-frame-spill", 25);
+  if (!DynamicSpill)
+    return;
+  auto DynamicVariable = createStackObject(*DynamicSpill->Function,
+                                           rcc::StackObjectKind::DynamicAlloca, std::nullopt, 16);
+  const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = {
+      rcc::riscv::PhysicalRegisterID::X5,  rcc::riscv::PhysicalRegisterID::X6,
+      rcc::riscv::PhysicalRegisterID::X7,  rcc::riscv::PhysicalRegisterID::X28,
+      rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30,
+      rcc::riscv::PhysicalRegisterID::X31,
+  };
+  const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0);
+  if (!DynamicVariable)
+    return;
+  for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) {
+    if (!buildAddImmediate(*DynamicSpill->Function, Target, *DynamicSpill->Block,
+                           physical(ScratchIDs[Index]), Zero,
+                           static_cast<std::int64_t>(Index + 1U))) {
+      return;
+    }
+  }
+  if (!buildCallFramePseudo(*DynamicSpill->Function, Target, *DynamicSpill->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKDOWN, 4096) ||
+      !buildCallFramePseudo(*DynamicSpill->Function, Target, *DynamicSpill->Block,
+                            rcc::riscv::InstructionOpcode::ADJCALLSTACKUP, 4096)) {
+    return;
+  }
+  for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) {
+    if (!buildAdd(*DynamicSpill->Function, Target, *DynamicSpill->Block,
+                  physical(rcc::riscv::PhysicalRegisterID::X10), physical(ID), Zero)) {
+      return;
+    }
+  }
+  if (!buildReturn(*DynamicSpill->Function, Target, *DynamicSpill->Block))
+    return;
+  auto DynamicSpillResult = runFrameLowering(*DynamicSpill->Function, Target);
+  const rcc::PhysicalRegister FP = physReg(rcc::riscv::PhysicalRegisterID::X8);
+  std::size_t StableEmergencyStores = 0;
+  std::size_t StableEmergencyLoads = 0;
+  for (const rcc::MachineInstr *Instruction : DynamicSpill->Function->allInstructions()) {
+    if (Instruction == nullptr || Instruction->parent() == nullptr ||
+        Instruction->memOperands().empty() ||
+        Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) ||
+        Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy)) {
+      continue;
+    }
+    const auto &Memory = Instruction->memOperands().front()->description();
+    if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || registerAt(*Instruction, 1) != FP)
+      continue;
+    StableEmergencyStores +=
+        Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD) ? 1U : 0U;
+    StableEmergencyLoads +=
+        Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD) ? 1U : 0U;
+  }
+  Context.expect(DynamicSpillResult && StableEmergencyStores == 2 && StableEmergencyLoads == 2,
+                 "dynamic call-frame scavenging must preserve scratch values through stable "
+                 "FP-relative emergency slots");
+}
+
+void testLargeOffsetAndScavenging(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("large-frame-offset", 8);
+  if (!Fixture)
+    return;
+  auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8192, 8);
+  if (!Local)
+    return;
+
+  const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = {
+      rcc::riscv::PhysicalRegisterID::X5,  rcc::riscv::PhysicalRegisterID::X6,
+      rcc::riscv::PhysicalRegisterID::X7,  rcc::riscv::PhysicalRegisterID::X28,
+      rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30,
+      rcc::riscv::PhysicalRegisterID::X31,
+  };
+  const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0);
+  for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) {
+    if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, physical(ScratchIDs[Index]),
+                           Zero, static_cast<std::int64_t>(Index + 1U))) {
+      return;
+    }
+  }
+  auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 5000);
+  if (!Store)
+    return;
+  for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) {
+    if (!buildAdd(*Fixture->Function, Target, *Fixture->Block,
+                  physical(rcc::riscv::PhysicalRegisterID::X10), physical(ID), Zero)) {
+      return;
+    }
+  }
+  if (!buildReturn(*Fixture->Function, Target, *Fixture->Block))
+    return;
+
+  auto Lowered = runFrameLowering(*Fixture->Function, Target);
+  Context.expect(Lowered &&
+                     findStackObject(*Fixture->Function, rcc::StackObjectKind::EmergencySpill) !=
+                         nullptr &&
+                     registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X5) &&
+                     immediateAt(**Store, 2) == 0 && !hasFrameIndex(*Fixture->Function),
+                 "large FrameIndex offsets must use a scavenged physical address register");
+
+  bool HasUnflaggedEmergencyStore = false;
+  bool HasUnflaggedEmergencyLoad = false;
+  for (rcc::MachineInstr *Instruction : instructions(*Fixture->Block)) {
+    if (Instruction == *Store || Instruction->memOperands().empty())
+      continue;
+    const auto &Memory = Instruction->memOperands().front()->description();
+    if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || Memory.Offset != 0)
+      continue;
+    const bool HasFrameFlag = Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) ||
+                              Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy);
+    HasUnflaggedEmergencyStore |=
+        Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD) && !HasFrameFlag;
+    HasUnflaggedEmergencyLoad |=
+        Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD) && !HasFrameFlag;
+  }
+  Context.expect(HasUnflaggedEmergencyStore && HasUnflaggedEmergencyLoad,
+                 "live scratch registers must be preserved without false frame flags");
+
+  auto Huge = createFunction("huge-rv64-frame", 26);
+  constexpr std::uint64_t HugeFrameSize = (std::uint64_t{1} << 32U) + 16U;
+  if (!Huge ||
+      !createStackObject(*Huge->Function, rcc::StackObjectKind::Default, HugeFrameSize, 16) ||
+      !buildReturn(*Huge->Function, Target, *Huge->Block)) {
+    return;
+  }
+  auto HugeResult = runFrameLowering(*Huge->Function, Target);
+  Context.expect(HugeResult && Huge->Function->frameInfo().state().StackSize == HugeFrameSize &&
+                     countOpcode(*Huge->Function, rcc::riscv::InstructionOpcode::ADD) >= 2,
+                 "RV64 frames larger than uint32 must use 64-bit stack adjustments");
+
+  auto TailScratch = createFunction("large-frame-tail-scratch", 27);
+  if (!TailScratch ||
+      !createStackObject(*TailScratch->Function, rcc::StackObjectKind::Default, 8192, 16) ||
+      !buildIndirectTail(*TailScratch->Function, Target, *TailScratch->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::X5))) {
+    return;
+  }
+  auto TailResult = runFrameLowering(*TailScratch->Function, Target);
+  bool FrameCodeClobbersTailCallee = false;
+  for (const rcc::MachineInstr *Instruction : TailScratch->Function->allInstructions()) {
+    if (Instruction == nullptr || Instruction->parent() == nullptr ||
+        (!Instruction->flags().has(rcc::MachineInstrFlag::FrameSetup) &&
+         !Instruction->flags().has(rcc::MachineInstrFlag::FrameDestroy))) {
+      continue;
+    }
+    FrameCodeClobbersTailCallee |=
+        registerAt(*Instruction, 0) == physReg(rcc::riscv::PhysicalRegisterID::X5);
+  }
+  Context.expect(TailResult && !FrameCodeClobbersTailCallee,
+                 "large prologue/epilogue adjustments must not clobber a tail-call operand");
+}
+
+void testCFGScavenging(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("cfg-scavenging", 13);
+  if (!Fixture)
+    return;
+  auto Loop = Fixture->Function->createBasicBlock();
+  if (!Loop || !Fixture->Function->appendBlock(**Loop) ||
+      !Fixture->Function->cfgUpdater().addSuccessor(*Fixture->Block, **Loop,
+                                                    rcc::BranchProbability::one()) ||
+      !Fixture->Function->cfgUpdater().addSuccessor(**Loop, **Loop,
+                                                    rcc::BranchProbability::one())) {
+    return;
+  }
+  auto Local = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8192, 8);
+  if (!Local)
+    return;
+
+  const std::vector<rcc::riscv::PhysicalRegisterID> ScratchIDs = {
+      rcc::riscv::PhysicalRegisterID::X5,  rcc::riscv::PhysicalRegisterID::X6,
+      rcc::riscv::PhysicalRegisterID::X7,  rcc::riscv::PhysicalRegisterID::X28,
+      rcc::riscv::PhysicalRegisterID::X29, rcc::riscv::PhysicalRegisterID::X30,
+      rcc::riscv::PhysicalRegisterID::X31,
+  };
+  const rcc::Register Zero = physical(rcc::riscv::PhysicalRegisterID::X0);
+  for (std::size_t Index = 0; Index < ScratchIDs.size(); ++Index) {
+    if (!buildAddImmediate(*Fixture->Function, Target, *Fixture->Block, physical(ScratchIDs[Index]),
+                           Zero, static_cast<std::int64_t>(Index + 1U))) {
+      return;
+    }
+  }
+  auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Local, 5000);
+  if (!Store)
+    return;
+  for (const rcc::riscv::PhysicalRegisterID ID : ScratchIDs) {
+    if (!buildAdd(*Fixture->Function, Target, **Loop, physical(rcc::riscv::PhysicalRegisterID::X10),
+                  physical(ID), Zero)) {
+      return;
+    }
+  }
+  if (!buildReturn(*Fixture->Function, Target, **Loop))
+    return;
+
+  Context.expect((*Loop)->liveIns().empty(),
+                 "CFG scavenging fixture must not depend on prebuilt live-ins");
+  auto Lowered = runFrameLowering(*Fixture->Function, Target);
+  bool HasEmergencyStore = false;
+  bool HasEmergencyLoad = false;
+  for (rcc::MachineInstr *Instruction : instructions(*Fixture->Block)) {
+    if (Instruction == *Store || Instruction->memOperands().empty())
+      continue;
+    const auto &Memory = Instruction->memOperands().front()->description();
+    if (Memory.Base.kind() != rcc::MemoryBase::Kind::Stack || Memory.Offset != 0) {
+      continue;
+    }
+    HasEmergencyStore |= Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::SD);
+    HasEmergencyLoad |= Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD);
+  }
+  Context.expect(
+      Lowered && HasEmergencyStore && HasEmergencyLoad &&
+          registerAt(**Store, 1) == physReg(rcc::riscv::PhysicalRegisterID::X5) &&
+          !hasFrameIndex(*Fixture->Function),
+      "successor and loop uses must keep scratch registers live across FrameIndex elimination");
+}
+
+[[nodiscard]] std::vector<std::int64_t> frameSignature(const rcc::MachineFunction &Function) {
+  std::vector<std::int64_t> Result;
+  Result.push_back(static_cast<std::int64_t>(Function.frameInfo().state().StackSize));
+  Result.push_back(static_cast<std::int64_t>(Function.frameInfo().stackAlignment().bytes()));
+  for (const rcc::StackObject &Object : Function.frameInfo().objects()) {
+    if (Object.isTombstone() || Object.description()->IsDead)
+      continue;
+    Result.push_back(static_cast<std::int64_t>(Object.description()->Kind));
+    Result.push_back(Object.description()->Offset.value_or(-1));
+  }
+  for (const rcc::MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    for (const rcc::MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      Result.push_back(static_cast<std::int64_t>(Instruction->opcode().value()));
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        Result.push_back(immediateAt(*Instruction, Index).value_or(0));
+        Result.push_back(registerAt(*Instruction, Index)
+                             .transform([](rcc::PhysicalRegister Reg) {
+                               return static_cast<std::int64_t>(Reg.number());
+                             })
+                             .value_or(0));
+      }
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] rcc::Expected<FunctionFixture>
+createDeterminismFixture(const rcc::TargetDescription &Target, std::uint64_t StableID) {
+  auto Fixture = createFunction("deterministic-frame", StableID);
+  if (!Fixture)
+    return std::unexpected(Fixture.error());
+  auto Small = createStackObject(*Fixture->Function, rcc::StackObjectKind::Default, 8, 8);
+  auto Large = createStackObject(*Fixture->Function, rcc::StackObjectKind::SpillSlot, 24, 16);
+  if (!Small || !Large)
+    return std::unexpected(!Small ? Small.error() : Large.error());
+  auto Store = buildStackAccess(*Fixture->Function, Target, *Fixture->Block,
+                                rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Small, 0);
+  if (!Store)
+    return std::unexpected(Store.error());
+  auto Return = buildReturn(*Fixture->Function, Target, *Fixture->Block);
+  if (!Return)
+    return std::unexpected(Return.error());
+  return Fixture;
+}
+
+void testPEIOrderingAndPostconditions(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Ordered = createFunction("pei-ordering", 22);
+  if (!Ordered ||
+      !buildAddImmediate(*Ordered->Function, Target, *Ordered->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::X18),
+                         physical(rcc::riscv::PhysicalRegisterID::X0), 1) ||
+      !buildReturn(*Ordered->Function, Target, *Ordered->Block)) {
+    return;
+  }
+  ObservingFrameLowering Observer(rcc::riscv::frameLowering());
+  auto OrderedResult = runFrameLoweringWith(*Ordered->Function, Target, Observer);
+  Context.expect(
+      OrderedResult && Observer.PrepareSawUnfrozen && Observer.InsertSawUnfrozen &&
+          Observer.FinalizeSawUnfrozen && Observer.FinalizeSawCalleeSave &&
+          Observer.FinalizeProducedFrozen && Observer.PrologueSawFrozen &&
+          Observer.EpilogueSawFrozen,
+      "PEI must insert callee saves before freeze and emit prologue/epilogue after freeze");
+
+  auto InvalidPostcondition = createFunction("pei-invalid-postcondition", 23);
+  if (!InvalidPostcondition)
+    return;
+  auto Slot =
+      createStackObject(*InvalidPostcondition->Function, rcc::StackObjectKind::Default, 8, 8);
+  if (!Slot)
+    return;
+  auto Store = buildStackAccess(*InvalidPostcondition->Function, Target,
+                                *InvalidPostcondition->Block, rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0);
+  if (!Store ||
+      !buildReturn(*InvalidPostcondition->Function, Target, *InvalidPostcondition->Block)) {
+    return;
+  }
+  const std::size_t OriginalInstructionCount = InvalidPostcondition->Block->instructionCount();
+  ObservingFrameLowering Broken(rcc::riscv::frameLowering(), true);
+  auto Rejected = runFrameLoweringWith(*InvalidPostcondition->Function, Target, Broken);
+  Context.expect(
+      !Rejected && !InvalidPostcondition->Function->frameInfo().isFrozen() &&
+          InvalidPostcondition->Block->instructionCount() == OriginalInstructionCount &&
+          (*Store)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex &&
+          InvalidPostcondition->Function->cfiInfo().instructions().empty(),
+      "PEI transaction preflight must verify final properties before mutating the original");
+}
+
+void testAtomicityAndDeterminism(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Invalid = createFunction("invalid-frame", 9);
+  if (!Invalid)
+    return;
+  auto Slot = createStackObject(*Invalid->Function, rcc::StackObjectKind::Default, 8, 8);
+  if (!Slot)
+    return;
+  auto Store = buildStackAccess(*Invalid->Function, Target, *Invalid->Block,
+                                rcc::riscv::InstructionOpcode::SD,
+                                physical(rcc::riscv::PhysicalRegisterID::X10), *Slot, 0);
+  if (!Store || !(*Store)->eraseOperand(2) ||
+      !buildReturn(*Invalid->Function, Target, *Invalid->Block)) {
+    return;
+  }
+  auto Rejected = runFrameLowering(*Invalid->Function, Target);
+  Context.expect(!Rejected && !Invalid->Function->frameInfo().isFrozen() &&
+                     Invalid->Function->frameInfo().liveObjectCount() == 1 &&
+                     (*Store)->operandCount() == 2 &&
+                     (*Store)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex,
+                 "failed frame lowering must leave the original MachineFunction unchanged");
+
+  auto OverflowingCallFrame = createFunction("overflowing-call-frame", 12);
+  if (!OverflowingCallFrame ||
+      !OverflowingCallFrame->Function->frameInfo().setMaxCallFrameSize(16)) {
+    return;
+  }
+  auto Align8 = rcc::Alignment::create(8);
+  if (!Align8)
+    return;
+  rcc::StackObjectDesc OutgoingDescription;
+  OutgoingDescription.Kind = rcc::StackObjectKind::Target;
+  OutgoingDescription.Size = 8;
+  OutgoingDescription.Align = *Align8;
+  OutgoingDescription.LocalOffset = 16;
+  OutgoingDescription.TargetFlags =
+      static_cast<std::uint64_t>(rcc::riscv::CallStackObjectFlag::OutgoingArgument);
+  auto Outgoing =
+      OverflowingCallFrame->Function->frameInfo().createObject(std::move(OutgoingDescription));
+  if (!Outgoing)
+    return;
+  auto OutgoingStore =
+      buildStackAccess(*OverflowingCallFrame->Function, Target, *OverflowingCallFrame->Block,
+                       rcc::riscv::InstructionOpcode::SD,
+                       physical(rcc::riscv::PhysicalRegisterID::X10), *Outgoing, 0);
+  if (!OutgoingStore ||
+      !buildReturn(*OverflowingCallFrame->Function, Target, *OverflowingCallFrame->Block)) {
+    return;
+  }
+  auto FrameRejected = runFrameLowering(*OverflowingCallFrame->Function, Target);
+  Context.expect(
+      !FrameRejected && FrameRejected.error().code() == rcc::ErrorCode::FrameLayoutFailed &&
+          !OverflowingCallFrame->Function->frameInfo().isFrozen() &&
+          OverflowingCallFrame->Function->cfiInfo().instructions().empty() &&
+          (*OutgoingStore)->operandAt(1)->kind() == rcc::MachineOperand::Kind::FrameIndex &&
+          (*OutgoingStore)->memOperands().front()->description().Base.frameIndex() == *Outgoing,
+      "transaction preflight must reject invalid call-frame layout without mutation");
+
+  auto MalformedSave = createFunction("malformed-callee-save", 20);
+  auto Align4 = rcc::Alignment::create(4);
+  if (!MalformedSave || !Align4)
+    return;
+  rcc::StackObjectDesc MalformedDescription;
+  MalformedDescription.Kind = rcc::StackObjectKind::CalleeSaved;
+  MalformedDescription.Size = 4;
+  MalformedDescription.Align = *Align4;
+  MalformedDescription.CalleeSavedRegister = physReg(rcc::riscv::PhysicalRegisterID::X18);
+  if (!MalformedSave->Function->frameInfo().createObject(std::move(MalformedDescription)) ||
+      !buildReturn(*MalformedSave->Function, Target, *MalformedSave->Block)) {
+    return;
+  }
+  auto MalformedResult = runFrameLowering(*MalformedSave->Function, Target);
+  Context.expect(
+      !MalformedResult && MalformedResult.error().code() == rcc::ErrorCode::VerificationError &&
+          !MalformedSave->Function->frameInfo().isFrozen() &&
+          MalformedSave->Function->frameInfo().liveObjectCount() == 1 &&
+          MalformedSave->Function->cfiInfo().instructions().empty(),
+      "malformed callee-save slots must be rejected before mutating the original function");
+
+  auto DuplicateSave = createFunction("duplicate-callee-save", 28);
+  auto Align8ForDuplicates = rcc::Alignment::create(8);
+  if (!DuplicateSave || !Align8ForDuplicates)
+    return;
+  for (std::size_t Index = 0; Index < 2; ++Index) {
+    rcc::StackObjectDesc DuplicateDescription;
+    DuplicateDescription.Kind = rcc::StackObjectKind::CalleeSaved;
+    DuplicateDescription.Size = 8;
+    DuplicateDescription.Align = *Align8ForDuplicates;
+    DuplicateDescription.CalleeSavedRegister = physReg(rcc::riscv::PhysicalRegisterID::X18);
+    if (!DuplicateSave->Function->frameInfo().createObject(std::move(DuplicateDescription))) {
+      return;
+    }
+  }
+  if (!buildReturn(*DuplicateSave->Function, Target, *DuplicateSave->Block))
+    return;
+  auto DuplicateResult = runFrameLowering(*DuplicateSave->Function, Target);
+  Context.expect(!DuplicateResult &&
+                     DuplicateResult.error().code() == rcc::ErrorCode::VerificationError &&
+                     !DuplicateSave->Function->frameInfo().isFrozen(),
+                 "duplicate callee-save slots must be rejected transactionally");
+
+  auto ReservedFrameRegister = createFunction("used-reserved-frame-register", 21);
+  if (!ReservedFrameRegister)
+    return;
+  auto OverAligned =
+      createStackObject(*ReservedFrameRegister->Function, rcc::StackObjectKind::Default, 32, 32);
+  if (!OverAligned ||
+      !buildAddImmediate(*ReservedFrameRegister->Function, Target, *ReservedFrameRegister->Block,
+                         physical(rcc::riscv::PhysicalRegisterID::X8),
+                         physical(rcc::riscv::PhysicalRegisterID::X0), 1) ||
+      !buildReturn(*ReservedFrameRegister->Function, Target, *ReservedFrameRegister->Block)) {
+    return;
+  }
+  auto ReservedFrameResult = runFrameLowering(*ReservedFrameRegister->Function, Target);
+  Context.expect(
+      !ReservedFrameResult &&
+          ReservedFrameResult.error().code() == rcc::ErrorCode::VerificationError &&
+          !ReservedFrameRegister->Function->frameInfo().isFrozen() &&
+          ReservedFrameRegister->Function->frameInfo().liveObjectCount() == 1,
+      "post-RA uses of required FP/BP registers must fail without partial frame mutation");
+
+  auto First = createDeterminismFixture(Target, 10);
+  auto Second = createDeterminismFixture(Target, 11);
+  if (!First || !Second)
+    return;
+  auto FirstResult = runFrameLowering(*First->Function, Target);
+  auto SecondResult = runFrameLowering(*Second->Function, Target);
+  Context.expect(FirstResult && SecondResult &&
+                     frameSignature(*First->Function) == frameSignature(*Second->Function),
+                 "identical frame inputs must produce deterministic layouts and code");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = rcc::riscv::createTargetDescription();
+  Context.expect(Target.has_value(), "RV64GC frame-lowering target must be constructible");
+  if (!Target)
+    return Context.result();
+
+  testLeafAndSmallFrame(Context, *Target);
+  testCalleeSavedRegisters(Context, *Target);
+  testFramePointerAndFixedObjects(Context, *Target);
+  testStackRealignment(Context, *Target);
+  testCallFrames(Context, *Target);
+  testLargeOffsetAndScavenging(Context, *Target);
+  testCFGScavenging(Context, *Target);
+  testPEIOrderingAndPostconditions(Context, *Target);
+  testAtomicityAndDeterminism(Context, *Target);
+  return Context.result();
+}
diff --git a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp
index f9031da..72cce51 100644
--- a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp
+++ b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp
@@ -26,6 +26,7 @@
 #include <cstdint>
 #include <iostream>
 #include <memory>
+#include <optional>
 #include <string>
 #include <string_view>
 #include <utility>
@@ -399,6 +400,46 @@ void testRealAllocators(TestContext &Context, const rcc::TargetDescription &Targ
   }
 }
 
+void testFunctionReservedRegisters(TestContext &Context, const rcc::TargetDescription &Target) {
+  for (const auto [Kind, ID, Name] : {
+           std::tuple{AllocatorKind::Basic, std::uint64_t{13}, std::string_view{"Basic"}},
+           std::tuple{AllocatorKind::Fast, std::uint64_t{14}, std::string_view{"Fast"}},
+           std::tuple{AllocatorKind::PBQP, std::uint64_t{15}, std::string_view{"PBQP"}},
+       }) {
+    auto Fixture = createSimpleAllocationFunction(Target, ID);
+    auto Align64 = rcc::Alignment::create(64);
+    if (!Fixture || !Align64)
+      continue;
+    rcc::StackObjectDesc Description;
+    Description.Size = 8;
+    Description.Align = *Align64;
+    if (!Fixture->Function->frameInfo().createObject(std::move(Description)))
+      continue;
+    auto Allocated = runAllocator(*Fixture->Function, Target, Kind);
+    const rcc::PhysicalRegister FP =
+        *rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X8);
+    const rcc::PhysicalRegister BP =
+        *rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X9);
+    bool AllocatedFrameRegister = false;
+    for (const rcc::MachineInstr *Instruction : Fixture->Function->allInstructions()) {
+      if (Instruction == nullptr || Instruction->parent() == nullptr)
+        continue;
+      for (const rcc::MachineOperand &Operand : Instruction->operands()) {
+        const rcc::Register *Reg = Operand.getIf<rcc::Register>();
+        const auto Physical =
+            Reg != nullptr && Reg->isPhysical() ? Reg->physicalRegister() : std::nullopt;
+        AllocatedFrameRegister |= Physical && (*Physical == FP || *Physical == BP);
+      }
+    }
+    if (!Allocated)
+      std::cerr << "RV64GC " << Name << " reservation error: " << Allocated.error().message()
+                << '\n';
+    Context.expect(Allocated && Fixture->Function->registerInfo().isReserved(FP) &&
+                       Fixture->Function->registerInfo().isReserved(BP) && !AllocatedFrameRegister,
+                   "every allocator must persist and honor function-level FP/BP reservations");
+  }
+}
+
 [[nodiscard]] rcc::Expected<FunctionFixture>
 createPressureFunction(const rcc::TargetDescription &Target, std::uint64_t ID) {
   auto Fixture = createFunction("riscv-pressure-" + std::to_string(ID), ID);
@@ -486,6 +527,7 @@ int main() {
   testTargetHooks(Context, *Target);
   testRematerialization(Context, *Target);
   testRealAllocators(Context, *Target);
+  testFunctionReservedRegisters(Context, *Target);
   testRealPressureAndDeterminism(Context, *Target);
   return Context.result();
 }