[CodeGen] Implement the greedy register allocator pipeline

16 files changed, 454 insertions, 46 deletions

diff --git a/backend/include/rcc/CodeGen/RegAllocCommon.h b/backend/include/rcc/CodeGen/RegAllocCommon.h
index ac3aa56..5994d64 100644
--- a/backend/include/rcc/CodeGen/RegAllocCommon.h
+++ b/backend/include/rcc/CodeGen/RegAllocCommon.h
@@ -19,6 +19,9 @@ struct RegisterAllocationOptions final {
 [[nodiscard]] std::unique_ptr<MachineFunctionPass>
 createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
                          RegisterAllocationOptions Options = {});
+[[nodiscard]] std::unique_ptr<MachineFunctionPass>
+createGreedyAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                          RegisterAllocationOptions Options = {});
 
 } // namespace rcc
 
diff --git a/backend/include/rcc/CodeGen/VirtRegMap.h b/backend/include/rcc/CodeGen/VirtRegMap.h
index 30ef450..eda71c2 100644
--- a/backend/include/rcc/CodeGen/VirtRegMap.h
+++ b/backend/include/rcc/CodeGen/VirtRegMap.h
@@ -9,6 +9,7 @@
 
 #include <cstdint>
 #include <optional>
+#include <string_view>
 #include <unordered_map>
 #include <vector>
 
@@ -75,17 +76,24 @@ private:
                                                      const TargetDescription &Target,
                                                      const VirtRegMap &Mapping);
 
-class VirtualRegisterRewritePass final : public MachineFunctionPass {
+class VirtRegMapAnalysis final {
 public:
-  explicit VirtualRegisterRewritePass(const VirtRegMap &Mapping) noexcept : Mapping(&Mapping) {}
+  using Result = VirtRegMap;
+
+  [[nodiscard]] static constexpr std::string_view name() noexcept {
+    return "VirtRegMap";
+  }
+  [[nodiscard]] static Expected<Result> run(MachineFunction &Function,
+                                            const TargetDescription &Target,
+                                            MachineFunctionAnalysisManager &Analyses);
+};
 
+class VirtualRegisterRewritePass final : public MachineFunctionPass {
+public:
   [[nodiscard]] const MachinePassContract &contract() const noexcept override;
   [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
                                                 const TargetDescription &Target,
                                                 MachineFunctionAnalysisManager &Analyses) override;
-
-private:
-  const VirtRegMap *Mapping;
 };
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 03fec17..b30479e 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -71,6 +71,7 @@ set(
   RegAllocBase.cpp
   RegAllocBasic.cpp
   RegAllocFast.cpp
+  RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   VirtRegMap.cpp
   PHIElimination.cpp
@@ -234,6 +235,7 @@ set(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulerInternal.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.h"
+  "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocGreedy.h"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocInternal.h"
 )
 rcc_backend_register_format_files(
diff --git a/backend/lib/CodeGen/LiveVariables.cpp b/backend/lib/CodeGen/LiveVariables.cpp
index 8bdd23e..601fd05 100644
--- a/backend/lib/CodeGen/LiveVariables.cpp
+++ b/backend/lib/CodeGen/LiveVariables.cpp
@@ -13,6 +13,7 @@
 #include "rcc/CodeGen/SlotIndexes.h"
 #include "rcc/CodeGen/TargetDescription.h"
 #include "rcc/CodeGen/TargetRegisterInfo.h"
+#include "rcc/CodeGen/VirtRegMap.h"
 
 #include <algorithm>
 #include <array>
@@ -655,9 +656,14 @@ buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescriptio
           }
           continue;
         }
-        const bool IsSemanticUse = !Operand->isDebugUse() &&
-                                   !Operand->registerFlags().has(RegisterOperandFlag::Undef) &&
-                                   !Operand->registerValue()->isNoRegister();
+        const Register OperandRegister = *Operand->registerValue();
+        const auto PhysicalRegister = OperandRegister.physicalRegister();
+        const PhysicalRegisterDesc *PhysicalDescription =
+            PhysicalRegister ? Target.registers().physicalRegister(*PhysicalRegister) : nullptr;
+        const bool IsSemanticUse =
+            !Operand->isDebugUse() && !Operand->registerFlags().has(RegisterOperandFlag::Undef) &&
+            !OperandRegister.isNoRegister() &&
+            (PhysicalDescription == nullptr || !PhysicalDescription->IsConstant);
         bool IsKill = false;
         if (IsSemanticUse) {
           auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target);
@@ -985,6 +991,7 @@ Expected<void> registerStage11MachineAnalyses(MachineFunctionAnalysisManager &An
       MachineFunctionAnalysisManager::id<SlotIndexesAnalysis>(),
       MachineFunctionAnalysisManager::id<LiveVariablesAnalysis>(),
       MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(),
+      MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>(),
   };
   const std::size_t Registered = static_cast<std::size_t>(
       std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); }));
@@ -1028,6 +1035,14 @@ Expected<void> registerStage11MachineAnalyses(MachineFunctionAnalysisManager &An
   });
   if (!Intervals)
     return std::unexpected(Intervals.error());
+  auto Mapping = Staging.registerAnalysis<VirtRegMapAnalysis>({
+      .Name = "VirtRegMap",
+      .Dependencies = {},
+      .InvalidatedBy = MachinePassChanges::all(),
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Mapping)
+    return std::unexpected(Mapping.error());
   return Analyses.replaceRegistrations(std::move(Staging));
 }
 
diff --git a/backend/lib/CodeGen/MIRPrinter.cpp b/backend/lib/CodeGen/MIRPrinter.cpp
index 3708053..2a6ddb4 100644
--- a/backend/lib/CodeGen/MIRPrinter.cpp
+++ b/backend/lib/CodeGen/MIRPrinter.cpp
@@ -493,7 +493,7 @@ MIRDocumentPrinter::createBodyContext(const MachineFunction &Function) const {
   std::uint32_t FixedID = 0;
   for (const StackObject &Object : Function.frameInfo().objects()) {
     const StackObjectDesc *Description = Object.description();
-    if (Description == nullptr)
+    if (Description == nullptr || Description->IsDead)
       continue;
     MIFrameObjectSlot Slot{
         .TextID = Object.isFixed() ? FixedID++ : StackID++,
diff --git a/backend/lib/CodeGen/MachineCopyPropagation.cpp b/backend/lib/CodeGen/MachineCopyPropagation.cpp
index aafed4b..b4fce2b 100644
--- a/backend/lib/CodeGen/MachineCopyPropagation.cpp
+++ b/backend/lib/CodeGen/MachineCopyPropagation.cpp
@@ -180,6 +180,34 @@ struct CopyOperands final {
   });
 }
 
+[[nodiscard]] Expected<void> clearRegisterKills(MachineInstr &First, MachineInstr &Last,
+                                                PhysicalRegister Reg,
+                                                const TargetRegisterInfo &Registers) {
+  for (MachineInstr *Instruction = &First; Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (Instruction == &Last)
+      return {};
+    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+      MachineOperand *Operand = Instruction->operandAt(Index);
+      const Register *OperandReg = Operand == nullptr ? nullptr : Operand->getIf<Register>();
+      const std::optional<PhysicalRegister> Physical =
+          OperandReg == nullptr ? std::nullopt : OperandReg->physicalRegister();
+      if (!Physical || !Operand->isUse() ||
+          !Operand->registerFlags().has(RegisterOperandFlag::Kill) ||
+          !Registers.regsOverlap(*Physical, Reg)) {
+        continue;
+      }
+      RegisterOperandFlags Flags = Operand->registerFlags();
+      Flags.clear(RegisterOperandFlag::Kill);
+      auto Updated = Operand->setRegisterFlags(Flags);
+      if (!Updated)
+        return std::unexpected(Updated.error());
+    }
+  }
+  return makeUnexpected(ErrorCode::InternalError,
+                        "COPY propagation replacement is outside the COPY block");
+}
+
 [[nodiscard]] Expected<bool> propagatePhysicalCopy(MachineInstr &Copy, const CopyOperands &Operands,
                                                    MachineFunction &Function,
                                                    const TargetDescription &Target,
@@ -202,7 +230,9 @@ struct CopyOperands final {
     return makeUnexpected(ErrorCode::InternalError,
                           "physical COPY propagation candidate is detached");
   const bool IsGenericCopy = Copy.opcode() == opcode(GenericOpcode::COPY);
-  if (*Destination == *Source && IsGenericCopy) {
+  if (*Destination == *Source) {
+    if (!IsGenericCopy)
+      return false;
     auto Removed = Block->removeInstruction(Copy);
     if (!Removed)
       return std::unexpected(Removed.error());
@@ -228,11 +258,16 @@ struct CopyOperands final {
           !canReplacePhysicalUse(*Instruction, Index, *Source, Function, Target, Info)) {
         continue;
       }
+      const bool DestinationWasKilled = Operand->registerFlags().has(RegisterOperandFlag::Kill);
       auto Replaced = Operand->setRegister(Operands.Source);
       if (!Replaced)
         return std::unexpected(Replaced.error());
       RegisterOperandFlags Flags = Operand->registerFlags();
       Flags.clear(RegisterOperandFlag::Kill);
+      if (DestinationWasKilled && (clobbersRegister(*Instruction, *Source, Target.registers()) ||
+                                   !valueUsedAfter(*Instruction, *Source, Target))) {
+        Flags.set(RegisterOperandFlag::Kill);
+      }
       if (!Operands.SourceOperand->registerFlags().has(RegisterOperandFlag::Renamable))
         Flags.clear(RegisterOperandFlag::Renamable);
       if (Operands.SourceOperand->registerFlags().has(RegisterOperandFlag::Undef))
@@ -242,6 +277,9 @@ struct CopyOperands final {
       auto SetFlags = Operand->setRegisterFlags(Flags);
       if (!SetFlags)
         return std::unexpected(SetFlags.error());
+      auto ClearedKills = clearRegisterKills(Copy, *Instruction, *Source, Target.registers());
+      if (!ClearedKills)
+        return std::unexpected(ClearedKills.error());
       Changed = true;
     }
   }
diff --git a/backend/lib/CodeGen/MachineStackSlotColoring.cpp b/backend/lib/CodeGen/MachineStackSlotColoring.cpp
index eec2747..eef913f 100644
--- a/backend/lib/CodeGen/MachineStackSlotColoring.cpp
+++ b/backend/lib/CodeGen/MachineStackSlotColoring.cpp
@@ -26,7 +26,7 @@ namespace {
 [[nodiscard]] const MachinePassContract &stackSlotColoringContract() {
   static const MachinePassContract Contract = [] {
     MachinePassContract Value{
-        .Name = "machine-stack-slot-coloring",
+        .Name = "stack-slot-coloring",
         .Requires = {},
         .Sets = {},
         .Clears = {},
diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp
index 0fac6aa..da526dd 100644
--- a/backend/lib/CodeGen/RegAllocBase.cpp
+++ b/backend/lib/CodeGen/RegAllocBase.cpp
@@ -36,10 +36,10 @@ orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals,
   return Result;
 }
 
-Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run() {
+Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run(VirtRegMap &Mapping) {
   const std::uint64_t InitialFingerprint = regalloc_detail::allocationFingerprint(Function);
   const std::size_t InitialFrameObjects = Function.frameInfo().liveObjectCount();
-  VirtRegMap Mapping(Function);
+  Mapping = VirtRegMap(Function);
   auto Initialized = regalloc_detail::initializeMapping(Function, Mapping);
   if (!Initialized)
     return std::unexpected(Initialized.error());
@@ -75,15 +75,13 @@ Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run() {
       if (!NewRegisters)
         return std::unexpected(NewRegisters.error());
     }
-    Analyses.clear(Function);
+    PreservedAnalyses Preserved;
+    Preserved.preserve<VirtRegMapAnalysis>();
+    Analyses.invalidate(Function, Preserved, MachinePassChanges::all());
   }
-
-  auto Rewritten = rewriteVirtualRegisters(Function, Target, Mapping);
-  if (!Rewritten)
-    return std::unexpected(Rewritten.error());
   const std::uint64_t FinalFingerprint = regalloc_detail::allocationFingerprint(Function);
   regalloc_detail::AllocationRunResult Result;
-  Result.Changed = InitialFingerprint != FinalFingerprint || *Rewritten;
+  Result.Changed = InitialFingerprint != FinalFingerprint;
   Result.ChangedInstructions = InitialFingerprint != FinalFingerprint;
   Result.ChangedFrame = InitialFrameObjects != Function.frameInfo().liveObjectCount();
   return Result;
diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h
index 4ef0bb7..8b09081 100644
--- a/backend/lib/CodeGen/RegAllocBase.h
+++ b/backend/lib/CodeGen/RegAllocBase.h
@@ -23,7 +23,7 @@ class RegAllocBase {
 public:
   virtual ~RegAllocBase() = default;
 
-  [[nodiscard]] Expected<regalloc_detail::AllocationRunResult> run();
+  [[nodiscard]] Expected<regalloc_detail::AllocationRunResult> run(VirtRegMap &Mapping);
 
 protected:
   RegAllocBase(MachineFunction &Function, const TargetDescription &Target,
diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp
index c3ed98b..2e2222f 100644
--- a/backend/lib/CodeGen/RegAllocBasic.cpp
+++ b/backend/lib/CodeGen/RegAllocBasic.cpp
@@ -78,10 +78,11 @@ private:
         .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
                      MachineFunctionProperty::TiedOpsRewritten,
                      MachineFunctionProperty::TracksLiveness},
-        .Sets = {MachineFunctionProperty::NoVRegs},
-        .Clears = {},
-        .RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>()},
-        .VerificationStage = PipelineStage::RegisterAllocated,
+        .Sets = {},
+        .Clears = {MachineFunctionProperty::IsSSA},
+        .RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(),
+                             MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>()},
+        .VerificationStage = std::nullopt,
     };
     Value.ThreadSafety = PassThreadSafety::ThreadSafe;
     return Value;
@@ -118,7 +119,8 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
     return std::unexpected(Registered.error());
   BasicAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses,
                                       Options);
-  auto TrialRun = TrialAllocator.run();
+  VirtRegMap TrialMapping(*Trial->ClonedFunction);
+  auto TrialRun = TrialAllocator.run(TrialMapping);
   if (!TrialRun)
     return std::unexpected(TrialRun.error());
   auto TrialVerification =
@@ -126,7 +128,10 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
   if (!TrialVerification)
     return std::unexpected(TrialVerification.error());
   BasicAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
-  auto Allocated = Allocator.run();
+  auto Mapping = Analyses.getResult<VirtRegMapAnalysis>(Function, Target);
+  if (!Mapping)
+    return std::unexpected(Mapping.error());
+  auto Allocated = Allocator.run(**Mapping);
   if (!Allocated) {
     return std::unexpected(withErrorContext(
         Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: "));
@@ -135,7 +140,9 @@ Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
   if (!Reserved)
     return std::unexpected(Reserved.error());
   Allocated->Changed |= *Reserved;
-  return regalloc_detail::passResult(*Allocated);
+  MachinePassResult Result = regalloc_detail::passResult(*Allocated);
+  Result.Preserved.preserve<VirtRegMapAnalysis>();
+  return Result;
 }
 
 std::unique_ptr<MachineFunctionPass>
diff --git a/backend/lib/CodeGen/RegAllocGreedy.cpp b/backend/lib/CodeGen/RegAllocGreedy.cpp
new file mode 100644
index 0000000..c00e753
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocGreedy.cpp
@@ -0,0 +1,270 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "RegAllocGreedy.h"
+
+#include "RegAllocBase.h"
+#include "rcc/CodeGen/LiveIntervals.h"
+#include "rcc/CodeGen/LiveRegMatrix.h"
+#include "rcc/CodeGen/LiveVariables.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <limits>
+#include <memory>
+#include <optional>
+#include <ranges>
+#include <unordered_set>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+struct EvictionCandidate final {
+  PhysicalRegister PhysicalReg;
+  std::vector<Register> Victims;
+  std::uint64_t Cost = 0;
+};
+
+[[nodiscard]] std::uint64_t saturatedAdd(std::uint64_t Left, std::uint64_t Right) noexcept {
+  if (Right > std::numeric_limits<std::uint64_t>::max() - Left)
+    return std::numeric_limits<std::uint64_t>::max();
+  return Left + Right;
+}
+
+[[nodiscard]] std::uint64_t normalizedSpillCost(const LiveInterval &Interval) noexcept {
+  std::uint64_t Length = 0;
+  for (const LiveSegment &Segment : Interval.MainRange.segments())
+    Length = saturatedAdd(Length, Segment.End.value() - Segment.Start.value());
+  Length = std::max<std::uint64_t>(1, Length);
+  constexpr std::uint64_t Scale = std::uint64_t{1} << 20U;
+  const std::uint64_t Weight = std::max<std::uint64_t>(1, Interval.SpillWeight);
+  const std::uint64_t ScaledWeight = Weight > std::numeric_limits<std::uint64_t>::max() / Scale
+                                         ? std::numeric_limits<std::uint64_t>::max()
+                                         : Weight * Scale;
+  return std::max<std::uint64_t>(1, ScaledWeight / Length);
+}
+
+[[nodiscard]] bool isBetterEviction(const EvictionCandidate &Left,
+                                    const EvictionCandidate &Right) noexcept {
+  if (Left.Cost != Right.Cost)
+    return Left.Cost < Right.Cost;
+  if (Left.Victims.size() != Right.Victims.size())
+    return Left.Victims.size() < Right.Victims.size();
+  return Left.PhysicalReg.number() < Right.PhysicalReg.number();
+}
+
+class GreedyAllocatorEngine final : public RegAllocBase {
+public:
+  GreedyAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
+                        const TargetRegisterAllocationInfo &TargetInfo,
+                        MachineFunctionAnalysisManager &Analyses, RegisterAllocationOptions Options)
+      : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {}
+
+private:
+  [[nodiscard]] Expected<std::optional<EvictionCandidate>>
+  evictionCandidate(Register VirtualReg, PhysicalRegister Candidate,
+                    const LiveIntervalsAnalysis::Result &Intervals, const LiveRegMatrix &Matrix,
+                    const VirtRegMap &Mapping) const {
+    const LiveInterval *Current = Intervals.interval(VirtualReg);
+    if (Current == nullptr)
+      return std::optional<EvictionCandidate>{};
+
+    EvictionCandidate Result{.PhysicalReg = Candidate, .Victims = {}, .Cost = 0};
+    for (const RegisterInterference &Interference :
+         Matrix.collectInterferences(VirtualReg, Candidate)) {
+      if (Interference.Kind != RegisterInterferenceKind::VirtualRegister ||
+          !Interference.VirtualReg) {
+        return std::optional<EvictionCandidate>{};
+      }
+      const Register Victim = *Interference.VirtualReg;
+      if (std::ranges::find(Result.Victims, Victim) != Result.Victims.end())
+        continue;
+      if (!Mapping.isSpillable(Victim))
+        return std::optional<EvictionCandidate>{};
+      const LiveInterval *VictimInterval = Intervals.interval(Victim);
+      if (VictimInterval == nullptr)
+        return std::optional<EvictionCandidate>{};
+      Result.Victims.push_back(Victim);
+      Result.Cost = std::max(Result.Cost, normalizedSpillCost(*VictimInterval));
+    }
+    if (Result.Victims.empty())
+      return std::optional<EvictionCandidate>{};
+
+    const std::uint64_t CurrentCost = normalizedSpillCost(*Current);
+    if (Mapping.isSpillable(VirtualReg) && Result.Cost >= CurrentCost)
+      return std::optional<EvictionCandidate>{};
+    std::ranges::sort(Result.Victims, [](Register Left, Register Right) {
+      return Left.opaqueValue() < Right.opaqueValue();
+    });
+    return std::optional<EvictionCandidate>{std::move(Result)};
+  }
+
+  [[nodiscard]] Expected<AllocationRoundResult>
+  allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override {
+    LiveRegMatrix Matrix(Function, Target, Intervals);
+    AllocationRoundResult Result;
+    std::unordered_set<Register> Spilled;
+    std::vector<const LiveInterval *> Worklist = orderedAllocationIntervals(Intervals, Function);
+    std::ranges::stable_sort(Worklist, [&](const LiveInterval *Left, const LiveInterval *Right) {
+      const bool LeftSpillable = Mapping.isSpillable(Left->Reg);
+      const bool RightSpillable = Mapping.isSpillable(Right->Reg);
+      if (LeftSpillable != RightSpillable)
+        return !LeftSpillable;
+      if (Left->SpillWeight != Right->SpillWeight)
+        return Left->SpillWeight > Right->SpillWeight;
+      return false;
+    });
+
+    for (const LiveInterval *Interval : Worklist) {
+      const Register VirtualReg = Interval->Reg;
+      if (regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg)) {
+        auto Marked = Mapping.setSpillable(VirtualReg, false);
+        if (!Marked)
+          return std::unexpected(Marked.error());
+      }
+      auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg);
+      if (!Candidates)
+        return std::unexpected(Candidates.error());
+
+      std::optional<PhysicalRegister> Assignment;
+      for (const PhysicalRegister Candidate : *Candidates) {
+        if (Matrix.checkInterference(VirtualReg, Candidate).Kind ==
+            RegisterInterferenceKind::Free) {
+          Assignment = Candidate;
+          break;
+        }
+      }
+
+      std::optional<EvictionCandidate> BestEviction;
+      if (!Assignment) {
+        for (const PhysicalRegister Candidate : *Candidates) {
+          auto CandidateEviction =
+              evictionCandidate(VirtualReg, Candidate, Intervals, Matrix, Mapping);
+          if (!CandidateEviction)
+            return std::unexpected(CandidateEviction.error());
+          if (!*CandidateEviction)
+            continue;
+          if (!BestEviction || isBetterEviction(**CandidateEviction, *BestEviction))
+            BestEviction = std::move(**CandidateEviction);
+        }
+      }
+
+      if (BestEviction) {
+        for (const Register Victim : BestEviction->Victims) {
+          auto Unassigned = Matrix.unassign(Victim);
+          if (!Unassigned)
+            return std::unexpected(Unassigned.error());
+          VirtRegMapEntry *Entry = Mapping.entry(Victim);
+          if (Entry == nullptr)
+            return makeUnexpected(ErrorCode::InternalError,
+                                  "greedy eviction found an unknown virtual register");
+          Entry->PhysicalReg.reset();
+          Entry->State = VirtRegAllocationState::Unassigned;
+          if (Spilled.insert(Victim).second)
+            Result.Spilled.push_back(Victim);
+        }
+        Assignment = BestEviction->PhysicalReg;
+      }
+
+      if (!Assignment) {
+        if (!Mapping.isSpillable(VirtualReg)) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "greedy allocator cannot assign a non-spillable virtual register");
+        }
+        if (Spilled.insert(VirtualReg).second)
+          Result.Spilled.push_back(VirtualReg);
+        continue;
+      }
+
+      auto MatrixAssignment = Matrix.assign(VirtualReg, *Assignment);
+      if (!MatrixAssignment)
+        return std::unexpected(MatrixAssignment.error());
+      auto MapAssignment = Mapping.assign(VirtualReg, *Assignment);
+      if (!MapAssignment)
+        return std::unexpected(MapAssignment.error());
+    }
+    return Result;
+  }
+};
+
+[[nodiscard]] const MachinePassContract &greedyContract() {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "greedy",
+        .Requires = {MachineFunctionProperty::NoPHIs, MachineFunctionProperty::TracksLiveness},
+        .Sets = {},
+        .Clears = {MachineFunctionProperty::IsSSA},
+        .RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(),
+                             MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>()},
+        .VerificationStage = std::nullopt,
+    };
+    Value.ThreadSafety = PassThreadSafety::ThreadSafe;
+    return Value;
+  }();
+  return Contract;
+}
+
+} // namespace
+
+const MachinePassContract &GreedyAllocatorPass::contract() const noexcept {
+  return greedyContract();
+}
+
+Expected<MachinePassResult> GreedyAllocatorPass::run(MachineFunction &Function,
+                                                     const TargetDescription &Target,
+                                                     MachineFunctionAnalysisManager &Analyses) {
+  if (Info == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "greedy allocator requires target behavior");
+  auto Required = regalloc_detail::requireAllocationProperties(Function, contract());
+  if (!Required)
+    return std::unexpected(Required.error());
+
+  auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
+  if (!Trial)
+    return std::unexpected(Trial.error());
+  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());
+  MachineFunctionAnalysisManager TrialAnalyses;
+  auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
+  if (!Registered)
+    return std::unexpected(Registered.error());
+  GreedyAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses,
+                                       Options);
+  VirtRegMap TrialMapping(*Trial->ClonedFunction);
+  auto TrialRun = TrialAllocator.run(TrialMapping);
+  if (!TrialRun)
+    return std::unexpected(TrialRun.error());
+  auto TrialVerification =
+      regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
+  if (!TrialVerification)
+    return std::unexpected(TrialVerification.error());
+
+  auto Mapping = Analyses.getResult<VirtRegMapAnalysis>(Function, Target);
+  if (!Mapping)
+    return std::unexpected(Mapping.error());
+  GreedyAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
+  auto Allocated = Allocator.run(**Mapping);
+  if (!Allocated) {
+    return std::unexpected(withErrorContext(
+        Allocated.error(), "greedy allocator diverged after a successful transaction preflight: "));
+  }
+  auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
+  if (!Reserved)
+    return std::unexpected(Reserved.error());
+  Allocated->Changed |= *Reserved;
+  MachinePassResult Result = regalloc_detail::passResult(*Allocated);
+  Result.Preserved.preserve<VirtRegMapAnalysis>();
+  return Result;
+}
+
+std::unique_ptr<MachineFunctionPass>
+createGreedyAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                          RegisterAllocationOptions Options) {
+  return std::make_unique<GreedyAllocatorPass>(Info, Options);
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/RegAllocGreedy.h b/backend/lib/CodeGen/RegAllocGreedy.h
new file mode 100644
index 0000000..1f25a5c
--- /dev/null
+++ b/backend/lib/CodeGen/RegAllocGreedy.h
@@ -0,0 +1,31 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
+#ifndef RCC_LIB_CODEGEN_REGALLOCGREEDY_H
+#define RCC_LIB_CODEGEN_REGALLOCGREEDY_H
+
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+
+namespace rcc {
+
+class GreedyAllocatorPass final : public MachineFunctionPass {
+public:
+  explicit GreedyAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                               RegisterAllocationOptions Options = {}) noexcept
+      : Info(&Info), Options(Options) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineFunctionAnalysisManager &Analyses) override;
+
+private:
+  const TargetRegisterAllocationInfo *Info;
+  RegisterAllocationOptions Options;
+};
+
+} // namespace rcc
+
+#endif // RCC_LIB_CODEGEN_REGALLOCGREEDY_H
diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp
index 25fc596..5b187d8 100644
--- a/backend/lib/CodeGen/RegAllocPBQP.cpp
+++ b/backend/lib/CodeGen/RegAllocPBQP.cpp
@@ -273,10 +273,11 @@ private:
     MachinePassContract Value{
         .Name = "PBQPAllocator",
         .Requires = {MachineFunctionProperty::NoPHIs},
-        .Sets = {MachineFunctionProperty::NoVRegs},
+        .Sets = {},
         .Clears = {MachineFunctionProperty::IsSSA},
-        .RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>()},
-        .VerificationStage = PipelineStage::RegisterAllocated,
+        .RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(),
+                             MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>()},
+        .VerificationStage = std::nullopt,
     };
     Value.ThreadSafety = PassThreadSafety::ThreadSafe;
     return Value;
@@ -314,7 +315,8 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
   MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
   PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options,
                                      &Actions);
-  auto TrialRun = TrialAllocator.run();
+  VirtRegMap TrialMapping(*Trial->ClonedFunction);
+  auto TrialRun = TrialAllocator.run(TrialMapping);
   if (!TrialRun)
     return std::unexpected(TrialRun.error());
   auto TrialVerification =
@@ -323,7 +325,10 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
     return std::unexpected(TrialVerification.error());
   Actions.beginReplay();
   PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options, &Actions);
-  auto Allocated = Allocator.run();
+  auto Mapping = Analyses.getResult<VirtRegMapAnalysis>(Function, Target);
+  if (!Mapping)
+    return std::unexpected(Mapping.error());
+  auto Allocated = Allocator.run(**Mapping);
   if (!Allocated) {
     return std::unexpected(withErrorContext(
         Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: "));
@@ -335,7 +340,9 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
   if (!Reserved)
     return std::unexpected(Reserved.error());
   Allocated->Changed |= *Reserved;
-  return regalloc_detail::passResult(*Allocated);
+  MachinePassResult Result = regalloc_detail::passResult(*Allocated);
+  Result.Preserved.preserve<VirtRegMapAnalysis>();
+  return Result;
 }
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/VirtRegMap.cpp b/backend/lib/CodeGen/VirtRegMap.cpp
index 4f3ae45..b764667 100644
--- a/backend/lib/CodeGen/VirtRegMap.cpp
+++ b/backend/lib/CodeGen/VirtRegMap.cpp
@@ -236,6 +236,18 @@ Expected<bool> rewriteVirtualRegisters(MachineFunction &Function, const TargetDe
     auto SetRegister = Plan.Operand->setRegister(Plan.NewRegister);
     if (!SetRegister)
       return std::unexpected(SetRegister.error());
+    if (const auto Physical = Plan.NewRegister.physicalRegister()) {
+      const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(*Physical);
+      if (Description != nullptr && !Description->IsConstant && !Description->IsArtificial &&
+          !Description->IsReserved && !Target.registers().isReservedRegister(*Physical) &&
+          !Function.registerInfo().isReserved(*Physical)) {
+        RegisterOperandFlags Flags = Plan.Operand->registerFlags();
+        Flags.set(RegisterOperandFlag::Renamable);
+        auto Updated = Plan.Operand->setRegisterFlags(Flags);
+        if (!Updated)
+          return std::unexpected(Updated.error());
+      }
+    }
     if (Plan.Operand->subReg().value() != 0) {
       auto Cleared = Plan.Operand->setSubReg(SubRegIndex{});
       if (!Cleared)
@@ -269,24 +281,29 @@ Expected<bool> rewriteVirtualRegisters(MachineFunction &Function, const TargetDe
 
 const MachinePassContract &VirtualRegisterRewritePass::contract() const noexcept {
   static const MachinePassContract Contract{
-      .Name = "VirtualRegisterRewrite",
-      .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
-                   MachineFunctionProperty::TiedOpsRewritten},
+      .Name = "virtregrewriter",
+      .Requires = {MachineFunctionProperty::NoPHIs},
       .Sets = {MachineFunctionProperty::NoVRegs},
-      .Clears = {},
-      .RequiredAnalyses = {},
+      .Clears = {MachineFunctionProperty::IsSSA},
+      .RequiredAnalyses = {MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>()},
       .VerificationStage = PipelineStage::RegisterAllocated,
   };
   return Contract;
 }
 
-Expected<MachinePassResult> VirtualRegisterRewritePass::run(MachineFunction &Function,
-                                                            const TargetDescription &Target,
-                                                            MachineFunctionAnalysisManager &) {
-  if (Mapping == nullptr)
-    return makeUnexpected(ErrorCode::InvalidArgument,
-                          "VirtualRegisterRewrite requires a VirtRegMap");
-  auto Rewritten = rewriteVirtualRegisters(Function, Target, *Mapping);
+Expected<VirtRegMapAnalysis::Result> VirtRegMapAnalysis::run(MachineFunction &Function,
+                                                             const TargetDescription &,
+                                                             MachineFunctionAnalysisManager &) {
+  return VirtRegMap(Function);
+}
+
+Expected<MachinePassResult>
+VirtualRegisterRewritePass::run(MachineFunction &Function, const TargetDescription &Target,
+                                MachineFunctionAnalysisManager &Analyses) {
+  auto Mapping = Analyses.getResult<VirtRegMapAnalysis>(Function, Target);
+  if (!Mapping)
+    return std::unexpected(Mapping.error());
+  auto Rewritten = rewriteVirtualRegisters(Function, Target, **Mapping);
   if (!Rewritten)
     return std::unexpected(Rewritten.error());
   MachinePassResult Result;
diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp
index 854417a..1e18661 100644
--- a/backend/lib/Target/RISCV/RISCVPipeline.cpp
+++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp
@@ -15,9 +15,11 @@
 #include "rcc/CodeGen/MachineOptimizationPipeline.h"
 #include "rcc/CodeGen/MachinePseudoExpansion.h"
 #include "rcc/CodeGen/PHIElimination.h"
+#include "rcc/CodeGen/RegAllocCommon.h"
 #include "rcc/CodeGen/RegAllocPBQP.h"
 #include "rcc/CodeGen/TargetDescription.h"
 #include "rcc/CodeGen/TwoAddressInstructionPass.h"
+#include "rcc/CodeGen/VirtRegMap.h"
 
 #include <memory>
 #include <ranges>
@@ -86,7 +88,10 @@ template <typename PassT, typename... ArgumentT>
                                          Options.DebugPrologueEpilogue));
   if (!Added)
     return std::unexpected(Added.error());
-  return addPass<PBQPAllocatorPass>(Pipeline, registerAllocationInfo());
+  Added = addPass<PBQPAllocatorPass>(Pipeline, registerAllocationInfo());
+  if (!Added)
+    return std::unexpected(Added.error());
+  return addPass<VirtualRegisterRewritePass>(Pipeline);
 }
 
 [[nodiscard]] Expected<void> addCompleteRegistry(MachineFunctionPassManager &Pipeline,
@@ -98,6 +103,9 @@ template <typename PassT, typename... ArgumentT>
   Added = addSSAExitPipeline(Pipeline, Subtarget, Options);
   if (!Added)
     return std::unexpected(Added.error());
+  Added = Pipeline.addPass(createGreedyAllocatorPass(registerAllocationInfo()));
+  if (!Added)
+    return std::unexpected(Added.error());
   Added = addRegisterAllocationPipeline(Pipeline, Subtarget, Options);
   if (!Added)
     return std::unexpected(Added.error());
diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
index 99c261c..2b34f53 100644
--- a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
+++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp
@@ -60,10 +60,14 @@ createStackMemoryOperand(MachineIRBuilder &Builder, FrameIndex StackSlot, Memory
   auto Align = Alignment::create(AlignmentInBytes);
   if (!Align)
     return std::unexpected(Align.error());
+  auto Type = LowLevelType::makeCategoryNeutralScalar(SizeInBytes * 8U);
+  if (!Type)
+    return std::unexpected(Type.error());
 
   MachineMemOperandDesc Description;
   Description.Accesses = {Access};
   Description.Size = *Size;
+  Description.MemoryType = *Type;
   Description.Align = *Align;
   Description.Base = MemoryBase::frameIndex(StackSlot);
   return Builder.function().createMemOperand(std::move(Description));