[CodeGen] Complete register allocation infrastructure

20 files changed, 1160 insertions, 19 deletions

diff --git a/backend/include/rcc/CodeGen/GenericConstant.h b/backend/include/rcc/CodeGen/GenericConstant.h
index 11c5068..92a8f13 100644
--- a/backend/include/rcc/CodeGen/GenericConstant.h
+++ b/backend/include/rcc/CodeGen/GenericConstant.h
@@ -50,8 +50,8 @@ struct GenericConstantType final {
   [[nodiscard]] static GenericConstantType byte() noexcept;
   [[nodiscard]] static Expected<GenericConstantType> floating(FloatSemantics Semantics);
   [[nodiscard]] static GenericConstantType pointer(std::uint32_t AddressSpace = 0) noexcept;
-  [[nodiscard]] static Expected<GenericConstantType>
-  array(std::uint64_t ElementCount, GenericConstantType Element);
+  [[nodiscard]] static Expected<GenericConstantType> array(std::uint64_t ElementCount,
+                                                           GenericConstantType Element);
   [[nodiscard]] static Expected<GenericConstantType>
   vector(std::uint64_t ElementCount, GenericConstantType Element, bool Scalable = false);
   [[nodiscard]] static Expected<GenericConstantType>
@@ -152,8 +152,7 @@ struct GenericConstantData final {
   std::string Block;
   bool NumericSymbol = false;
   bool NumericBlock = false;
-  GenericConstantExpressionOpcode ExpressionOpcode =
-      GenericConstantExpressionOpcode::Invalid;
+  GenericConstantExpressionOpcode ExpressionOpcode = GenericConstantExpressionOpcode::Invalid;
   GenericConstantExpressionFlags ExpressionFlags;
   std::optional<GenericConstantType> SourceElementType;
   std::optional<IntegerImmediate> InRangeStart;
diff --git a/backend/include/rcc/CodeGen/LiveRangeEdit.h b/backend/include/rcc/CodeGen/LiveRangeEdit.h
new file mode 100644
index 0000000..66696df
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveRangeEdit.h
@@ -0,0 +1,32 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVERANGEEDIT_H
+#define RCC_CODEGEN_LIVERANGEEDIT_H
+
+#include "rcc/CodeGen/VirtRegMap.h"
+
+#include <optional>
+
+namespace rcc {
+
+class TargetDescription;
+
+class LiveRangeEdit final {
+public:
+  LiveRangeEdit(MachineFunction &Function, const TargetDescription &Target, VirtRegMap &Mapping)
+      : Function(&Function), Target(&Target), Mapping(&Mapping) {}
+
+  [[nodiscard]] Expected<Register> createFrom(Register Parent, bool Spillable,
+                                              std::optional<Register> Origin = std::nullopt);
+  [[nodiscard]] Expected<FrameIndex> getOrCreateSpillSlot(Register VirtualReg);
+  [[nodiscard]] Expected<void> eraseVirtualRegister(Register VirtualReg);
+
+private:
+  MachineFunction *Function;
+  const TargetDescription *Target;
+  VirtRegMap *Mapping;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_LIVERANGEEDIT_H
diff --git a/backend/include/rcc/CodeGen/LiveRegMatrix.h b/backend/include/rcc/CodeGen/LiveRegMatrix.h
new file mode 100644
index 0000000..953828c
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveRegMatrix.h
@@ -0,0 +1,73 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVEREGMATRIX_H
+#define RCC_CODEGEN_LIVEREGMATRIX_H
+
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunction;
+class TargetDescription;
+
+enum class RegisterInterferenceKind : std::uint8_t {
+  Free,
+  VirtualRegister,
+  FixedRegister,
+  RegisterMask,
+  RegisterUnit,
+};
+
+struct RegisterInterference final {
+  RegisterInterferenceKind Kind = RegisterInterferenceKind::Free;
+  std::optional<Register> VirtualReg;
+  std::optional<PhysicalRegister> FixedReg;
+  std::optional<RegisterUnitID> Unit;
+  std::optional<MachineInstrStableID> Instruction;
+};
+
+class LiveRegMatrix final {
+public:
+  LiveRegMatrix(const MachineFunction &Function, const TargetDescription &Target,
+                const LiveIntervalsAnalysis::Result &Intervals) noexcept
+      : Function(&Function), Target(&Target), Intervals(&Intervals) {}
+
+  [[nodiscard]] Expected<void> assign(Register VirtualReg, PhysicalRegister PhysicalReg);
+  [[nodiscard]] Expected<void> unassign(Register VirtualReg);
+  [[nodiscard]] std::optional<PhysicalRegister> assignment(Register VirtualReg) const noexcept;
+  [[nodiscard]] RegisterInterference checkInterference(Register VirtualReg,
+                                                       PhysicalRegister PhysicalReg) const noexcept;
+  [[nodiscard]] std::vector<RegisterInterference>
+  collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const;
+
+  [[nodiscard]] std::span<const std::pair<Register, PhysicalRegister>>
+  assignments() const noexcept {
+    return OrderedAssignments;
+  }
+
+private:
+  [[nodiscard]] bool intervalsOverlapOnCandidates(const LiveInterval &Left,
+                                                  PhysicalRegister LeftReg,
+                                                  const LiveInterval &Right,
+                                                  PhysicalRegister RightReg) const noexcept;
+  [[nodiscard]] bool intervalOverlapsUnit(const LiveInterval &Interval, RegisterUnitLane Unit,
+                                          const LiveRange &UnitRange) const noexcept;
+
+  const MachineFunction *Function;
+  const TargetDescription *Target;
+  const LiveIntervalsAnalysis::Result *Intervals;
+  std::unordered_map<Register, PhysicalRegister> Assignments;
+  std::vector<std::pair<Register, PhysicalRegister>> OrderedAssignments;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_LIVEREGMATRIX_H
diff --git a/backend/include/rcc/CodeGen/MachineFrameInfo.h b/backend/include/rcc/CodeGen/MachineFrameInfo.h
index 48e3d7a..c884afb 100644
--- a/backend/include/rcc/CodeGen/MachineFrameInfo.h
+++ b/backend/include/rcc/CodeGen/MachineFrameInfo.h
@@ -197,8 +197,7 @@ struct MachineFrameState final {
   std::vector<MachineFrameSaveRestorePoint> SavePoints;
   std::vector<MachineFrameSaveRestorePoint> RestorePoints;
 
-  friend bool operator==(const MachineFrameState &Left,
-                         const MachineFrameState &Right) = default;
+  friend bool operator==(const MachineFrameState &Left, const MachineFrameState &Right) = default;
 };
 
 class MachineFrameInfo final {
diff --git a/backend/include/rcc/CodeGen/MachineRegisterInfo.h b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
index b6485e3..14e50a3 100644
--- a/backend/include/rcc/CodeGen/MachineRegisterInfo.h
+++ b/backend/include/rcc/CodeGen/MachineRegisterInfo.h
@@ -134,6 +134,7 @@ public:
   [[nodiscard]] std::span<const PhysicalRegisterLiveIn> liveIns() const noexcept {
     return LiveIns;
   }
+  void clearLiveInVirtualRegisters() noexcept;
 
   [[nodiscard]] Expected<void> reservePhysicalRegister(PhysicalRegister PhysReg);
   [[nodiscard]] bool isReserved(PhysicalRegister PhysReg) const noexcept;
diff --git a/backend/include/rcc/CodeGen/PBQP/Graph.h b/backend/include/rcc/CodeGen/PBQP/Graph.h
new file mode 100644
index 0000000..9173bfd
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PBQP/Graph.h
@@ -0,0 +1,194 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PBQP_GRAPH_H
+#define RCC_CODEGEN_PBQP_GRAPH_H
+
+#include "rcc/CodeGen/PBQP/Math.h"
+#include "rcc/Support/Error.h"
+
+#include <compare>
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <limits>
+#include <optional>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc::pbqp {
+
+class NodeID final {
+public:
+  constexpr NodeID() noexcept = default;
+  [[nodiscard]] static constexpr NodeID fromValue(std::uint32_t Value) noexcept {
+    return NodeID(Value);
+  }
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != InvalidValue;
+  }
+  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
+    return Value;
+  }
+  friend constexpr bool operator==(NodeID, NodeID) noexcept = default;
+  friend constexpr auto operator<=>(NodeID, NodeID) noexcept = default;
+
+private:
+  static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max();
+  explicit constexpr NodeID(std::uint32_t Value) noexcept : Value(Value) {}
+  std::uint32_t Value = InvalidValue;
+};
+
+class EdgeID final {
+public:
+  constexpr EdgeID() noexcept = default;
+  [[nodiscard]] static constexpr EdgeID fromValue(std::uint32_t Value) noexcept {
+    return EdgeID(Value);
+  }
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != InvalidValue;
+  }
+  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
+    return Value;
+  }
+  friend constexpr bool operator==(EdgeID, EdgeID) noexcept = default;
+  friend constexpr auto operator<=>(EdgeID, EdgeID) noexcept = default;
+
+private:
+  static constexpr std::uint32_t InvalidValue = std::numeric_limits<std::uint32_t>::max();
+  explicit constexpr EdgeID(std::uint32_t Value) noexcept : Value(Value) {}
+  std::uint32_t Value = InvalidValue;
+};
+
+struct Node final {
+  NodeID ID;
+  std::uint64_t StableKey = 0;
+  CostVector Costs;
+  std::vector<EdgeID> AdjacentEdges;
+};
+
+struct Edge final {
+  EdgeID ID;
+  NodeID First;
+  NodeID Second;
+  std::uint64_t StableKey = 0;
+  CostMatrix Costs;
+};
+
+class Graph final {
+public:
+  [[nodiscard]] Expected<NodeID> addNode(CostVector Costs, std::uint64_t StableKey = 0) {
+    if (Costs.empty())
+      return makeUnexpected(ErrorCode::InvalidArgument, "PBQP node requires at least one option");
+    if (Nodes.size() >= std::numeric_limits<std::uint32_t>::max())
+      return makeUnexpected(ErrorCode::Unsupported, "PBQP node ID space is exhausted");
+    const NodeID ID = NodeID::fromValue(static_cast<std::uint32_t>(Nodes.size()));
+    Nodes.push_back(Node{ID, StableKey, std::move(Costs), {}});
+    return ID;
+  }
+
+  [[nodiscard]] Expected<EdgeID> addEdge(NodeID First, NodeID Second, CostMatrix Costs,
+                                         std::uint64_t StableKey = 0) {
+    const Node *FirstNode = node(First);
+    const Node *SecondNode = node(Second);
+    if (FirstNode == nullptr || SecondNode == nullptr || First == Second) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "PBQP edge requires two distinct known nodes");
+    }
+    if (edgeBetween(First, Second))
+      return makeUnexpected(ErrorCode::InvalidArgument, "PBQP graph already contains this edge");
+
+    if (Second < First) {
+      std::swap(First, Second);
+      Costs = Costs.transpose();
+      std::swap(FirstNode, SecondNode);
+    }
+    if (Costs.rows() != FirstNode->Costs.size() || Costs.columns() != SecondNode->Costs.size()) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "PBQP edge matrix dimensions do not match its nodes");
+    }
+    if (Edges.size() >= std::numeric_limits<std::uint32_t>::max())
+      return makeUnexpected(ErrorCode::Unsupported, "PBQP edge ID space is exhausted");
+    const EdgeID ID = EdgeID::fromValue(static_cast<std::uint32_t>(Edges.size()));
+    Edges.push_back(Edge{ID, First, Second, StableKey, std::move(Costs)});
+    Nodes[First.value()].AdjacentEdges.push_back(ID);
+    Nodes[Second.value()].AdjacentEdges.push_back(ID);
+    return ID;
+  }
+
+  [[nodiscard]] const Node *node(NodeID ID) const noexcept {
+    return ID.isValid() && ID.value() < Nodes.size() ? &Nodes[ID.value()] : nullptr;
+  }
+  [[nodiscard]] const Edge *edge(EdgeID ID) const noexcept {
+    return ID.isValid() && ID.value() < Edges.size() ? &Edges[ID.value()] : nullptr;
+  }
+
+  [[nodiscard]] const Edge *edgeBetween(NodeID Left, NodeID Right) const noexcept {
+    const Node *LeftNode = node(Left);
+    if (LeftNode == nullptr || node(Right) == nullptr)
+      return nullptr;
+    for (const EdgeID ID : LeftNode->AdjacentEdges) {
+      const Edge &Candidate = Edges[ID.value()];
+      if ((Candidate.First == Left && Candidate.Second == Right) ||
+          (Candidate.First == Right && Candidate.Second == Left))
+        return &Candidate;
+    }
+    return nullptr;
+  }
+
+  [[nodiscard]] std::span<const Node> nodes() const noexcept {
+    return Nodes;
+  }
+  [[nodiscard]] std::span<const Edge> edges() const noexcept {
+    return Edges;
+  }
+  [[nodiscard]] std::size_t nodeCount() const noexcept {
+    return Nodes.size();
+  }
+
+  [[nodiscard]] Expected<void> verify() const {
+    for (std::size_t Index = 0; Index < Nodes.size(); ++Index) {
+      const Node &Value = Nodes[Index];
+      if (Value.ID.value() != Index || Value.Costs.empty())
+        return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid node");
+      for (const EdgeID ID : Value.AdjacentEdges) {
+        const Edge *Adjacent = edge(ID);
+        if (Adjacent == nullptr || (Adjacent->First != Value.ID && Adjacent->Second != Value.ID)) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "PBQP node has an invalid adjacency entry");
+        }
+      }
+    }
+    for (std::size_t Index = 0; Index < Edges.size(); ++Index) {
+      const Edge &Value = Edges[Index];
+      const Node *First = node(Value.First);
+      const Node *Second = node(Value.Second);
+      if (Value.ID.value() != Index || First == nullptr || Second == nullptr ||
+          !(Value.First < Value.Second) || Value.Costs.rows() != First->Costs.size() ||
+          Value.Costs.columns() != Second->Costs.size()) {
+        return makeUnexpected(ErrorCode::VerificationError, "PBQP graph contains an invalid edge");
+      }
+    }
+    return {};
+  }
+
+private:
+  std::vector<Node> Nodes;
+  std::vector<Edge> Edges;
+};
+
+} // namespace rcc::pbqp
+
+template <> struct std::hash<rcc::pbqp::NodeID> {
+  [[nodiscard]] std::size_t operator()(rcc::pbqp::NodeID ID) const noexcept {
+    return std::hash<std::uint32_t>{}(ID.value());
+  }
+};
+
+template <> struct std::hash<rcc::pbqp::EdgeID> {
+  [[nodiscard]] std::size_t operator()(rcc::pbqp::EdgeID ID) const noexcept {
+    return std::hash<std::uint32_t>{}(ID.value());
+  }
+};
+
+#endif // RCC_CODEGEN_PBQP_GRAPH_H
diff --git a/backend/include/rcc/CodeGen/PBQP/Math.h b/backend/include/rcc/CodeGen/PBQP/Math.h
new file mode 100644
index 0000000..90fc751
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PBQP/Math.h
@@ -0,0 +1,114 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PBQP_MATH_H
+#define RCC_CODEGEN_PBQP_MATH_H
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <span>
+#include <utility>
+#include <vector>
+
+namespace rcc::pbqp {
+
+using Cost = std::int64_t;
+
+inline constexpr Cost InfiniteCost = std::numeric_limits<Cost>::max() / 4;
+inline constexpr Cost NegativeInfiniteCost = -InfiniteCost;
+
+[[nodiscard]] constexpr bool isInfinite(Cost Value) noexcept {
+  return Value >= InfiniteCost;
+}
+
+[[nodiscard]] constexpr Cost addCosts(Cost Left, Cost Right) noexcept {
+  if (isInfinite(Left) || isInfinite(Right))
+    return InfiniteCost;
+  if (Left <= NegativeInfiniteCost || Right <= NegativeInfiniteCost)
+    return NegativeInfiniteCost;
+  if (Right > 0 && Left > InfiniteCost - Right)
+    return InfiniteCost;
+  if (Right < 0 && Left < NegativeInfiniteCost - Right)
+    return NegativeInfiniteCost;
+  return Left + Right;
+}
+
+class CostVector final {
+public:
+  explicit CostVector(std::size_t Size, Cost Initial = 0) : Values(Size, Initial) {}
+  explicit CostVector(std::vector<Cost> Values) : Values(std::move(Values)) {}
+
+  [[nodiscard]] std::size_t size() const noexcept {
+    return Values.size();
+  }
+  [[nodiscard]] bool empty() const noexcept {
+    return Values.empty();
+  }
+  [[nodiscard]] Cost &operator[](std::size_t Index) noexcept {
+    return Values[Index];
+  }
+  [[nodiscard]] Cost operator[](std::size_t Index) const noexcept {
+    return Values[Index];
+  }
+  [[nodiscard]] std::span<const Cost> values() const noexcept {
+    return Values;
+  }
+
+  [[nodiscard]] std::size_t minimumIndex() const noexcept {
+    return static_cast<std::size_t>(std::ranges::min_element(Values) - Values.begin());
+  }
+
+  void add(const CostVector &Other) noexcept {
+    for (std::size_t Index = 0; Index < Values.size(); ++Index)
+      Values[Index] = addCosts(Values[Index], Other.Values[Index]);
+  }
+
+private:
+  std::vector<Cost> Values;
+};
+
+class CostMatrix final {
+public:
+  CostMatrix(std::size_t Rows, std::size_t Columns, Cost Initial = 0)
+      : RowCount(Rows), ColumnCount(Columns), Values(Rows * Columns, Initial) {}
+
+  [[nodiscard]] std::size_t rows() const noexcept {
+    return RowCount;
+  }
+  [[nodiscard]] std::size_t columns() const noexcept {
+    return ColumnCount;
+  }
+  [[nodiscard]] bool empty() const noexcept {
+    return RowCount == 0 || ColumnCount == 0;
+  }
+
+  [[nodiscard]] Cost &at(std::size_t Row, std::size_t Column) noexcept {
+    return Values[Row * ColumnCount + Column];
+  }
+  [[nodiscard]] Cost at(std::size_t Row, std::size_t Column) const noexcept {
+    return Values[Row * ColumnCount + Column];
+  }
+
+  [[nodiscard]] CostMatrix transpose() const {
+    CostMatrix Result(ColumnCount, RowCount);
+    for (std::size_t Row = 0; Row < RowCount; ++Row)
+      for (std::size_t Column = 0; Column < ColumnCount; ++Column)
+        Result.at(Column, Row) = at(Row, Column);
+    return Result;
+  }
+
+  void add(const CostMatrix &Other) noexcept {
+    for (std::size_t Index = 0; Index < Values.size(); ++Index)
+      Values[Index] = addCosts(Values[Index], Other.Values[Index]);
+  }
+
+private:
+  std::size_t RowCount;
+  std::size_t ColumnCount;
+  std::vector<Cost> Values;
+};
+
+} // namespace rcc::pbqp
+
+#endif // RCC_CODEGEN_PBQP_MATH_H
diff --git a/backend/include/rcc/CodeGen/PBQP/ReductionRules.h b/backend/include/rcc/CodeGen/PBQP/ReductionRules.h
new file mode 100644
index 0000000..1b28e33
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PBQP/ReductionRules.h
@@ -0,0 +1,32 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PBQP_REDUCTIONRULES_H
+#define RCC_CODEGEN_PBQP_REDUCTIONRULES_H
+
+#include "rcc/CodeGen/PBQP/Graph.h"
+
+#include <cstdint>
+
+namespace rcc::pbqp {
+
+enum class ReductionKind : std::uint8_t {
+  DegreeZero,
+  DegreeOne,
+  DegreeTwo,
+  Heuristic,
+};
+
+struct ReductionRecord final {
+  ReductionKind Kind = ReductionKind::DegreeZero;
+  NodeID Node;
+  NodeID FirstNeighbor;
+  NodeID SecondNeighbor;
+  std::size_t FixedSelection = 0;
+  CostVector NodeCosts{1};
+  CostMatrix FirstCosts{1, 1};
+  CostMatrix SecondCosts{1, 1};
+};
+
+} // namespace rcc::pbqp
+
+#endif // RCC_CODEGEN_PBQP_REDUCTIONRULES_H
diff --git a/backend/include/rcc/CodeGen/PBQP/Solution.h b/backend/include/rcc/CodeGen/PBQP/Solution.h
new file mode 100644
index 0000000..512eb57
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PBQP/Solution.h
@@ -0,0 +1,85 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PBQP_SOLUTION_H
+#define RCC_CODEGEN_PBQP_SOLUTION_H
+
+#include "rcc/CodeGen/PBQP/Graph.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <limits>
+#include <optional>
+#include <span>
+#include <vector>
+
+namespace rcc::pbqp {
+
+class Solution final {
+public:
+  explicit Solution(std::size_t NodeCount)
+      : Selections(NodeCount, std::numeric_limits<std::size_t>::max()) {}
+
+  [[nodiscard]] Expected<void> setSelection(NodeID ID, std::size_t Selection) {
+    if (!ID.isValid() || ID.value() >= Selections.size())
+      return makeUnexpected(ErrorCode::InvalidArgument, "PBQP solution received an unknown node");
+    Selections[ID.value()] = Selection;
+    return {};
+  }
+
+  [[nodiscard]] std::optional<std::size_t> selection(NodeID ID) const noexcept {
+    if (!ID.isValid() || ID.value() >= Selections.size() ||
+        Selections[ID.value()] == std::numeric_limits<std::size_t>::max())
+      return std::nullopt;
+    return Selections[ID.value()];
+  }
+
+  [[nodiscard]] std::span<const std::size_t> selections() const noexcept {
+    return Selections;
+  }
+  [[nodiscard]] Cost totalCost() const noexcept {
+    return TotalCost;
+  }
+  void setTotalCost(Cost Value) noexcept {
+    TotalCost = Value;
+  }
+
+  [[nodiscard]] Expected<void> verify(const Graph &Problem) const {
+    if (Selections.size() != Problem.nodeCount())
+      return makeUnexpected(ErrorCode::VerificationError, "PBQP solution has the wrong node count");
+    Cost Total = 0;
+    for (const Node &NodeValue : Problem.nodes()) {
+      const auto Selection = selection(NodeValue.ID);
+      if (!Selection)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PBQP solution omits a valid node selection");
+      const std::size_t SelectedOption = Selection.value();
+      if (SelectedOption >= NodeValue.Costs.size())
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PBQP solution selects an invalid node option");
+      Total = addCosts(Total, NodeValue.Costs[SelectedOption]);
+    }
+    for (const Edge &EdgeValue : Problem.edges()) {
+      const auto FirstSelection = selection(EdgeValue.First);
+      const auto SecondSelection = selection(EdgeValue.Second);
+      if (!FirstSelection || !SecondSelection) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "PBQP solution omits an edge endpoint selection");
+      }
+      Total = addCosts(Total, EdgeValue.Costs.at(FirstSelection.value(), SecondSelection.value()));
+    }
+    if (isInfinite(Total))
+      return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                            "PBQP problem has no finite solution");
+    if (Total != TotalCost)
+      return makeUnexpected(ErrorCode::VerificationError, "PBQP solution cost is inconsistent");
+    return {};
+  }
+
+private:
+  std::vector<std::size_t> Selections;
+  Cost TotalCost = 0;
+};
+
+} // namespace rcc::pbqp
+
+#endif // RCC_CODEGEN_PBQP_SOLUTION_H
diff --git a/backend/include/rcc/CodeGen/PBQP/Solver.h b/backend/include/rcc/CodeGen/PBQP/Solver.h
new file mode 100644
index 0000000..ff14857
--- /dev/null
+++ b/backend/include/rcc/CodeGen/PBQP/Solver.h
@@ -0,0 +1,342 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_PBQP_SOLVER_H
+#define RCC_CODEGEN_PBQP_SOLVER_H
+
+#include "rcc/CodeGen/PBQP/ReductionRules.h"
+#include "rcc/CodeGen/PBQP/Solution.h"
+
+#include <algorithm>
+#include <cstddef>
+#include <cstdint>
+#include <map>
+#include <optional>
+#include <set>
+#include <tuple>
+#include <utility>
+#include <vector>
+
+namespace rcc::pbqp {
+
+class DeterministicSolver final {
+public:
+  [[nodiscard]] Expected<Solution> solve(const Graph &Problem) const {
+    auto Verified = Problem.verify();
+    if (!Verified)
+      return std::unexpected(Verified.error());
+
+    WorkingProblem Work(Problem);
+    std::vector<ReductionRecord> Reductions;
+    Reductions.reserve(Problem.nodeCount());
+    while (Work.activeNodeCount() != 0) {
+      const NodeID Selected = Work.selectReductionNode();
+      const std::size_t Degree = Work.degree(Selected);
+      Expected<ReductionRecord> Reduced = Degree == 0   ? Work.reduceDegreeZero(Selected)
+                                          : Degree == 1 ? Work.reduceDegreeOne(Selected)
+                                          : Degree == 2 ? Work.reduceDegreeTwo(Selected)
+                                                        : Work.reduceHeuristically(Selected);
+      if (!Reduced)
+        return std::unexpected(Reduced.error());
+      Reductions.push_back(std::move(*Reduced));
+    }
+
+    Solution Result(Problem.nodeCount());
+    for (auto Position = Reductions.rbegin(); Position != Reductions.rend(); ++Position) {
+      const ReductionRecord &Record = *Position;
+      std::size_t Choice = Record.FixedSelection;
+      if (Record.Kind != ReductionKind::Heuristic) {
+        Cost Best = InfiniteCost;
+        for (std::size_t Option = 0; Option < Record.NodeCosts.size(); ++Option) {
+          Cost Candidate = Record.NodeCosts[Option];
+          if (Record.Kind == ReductionKind::DegreeOne || Record.Kind == ReductionKind::DegreeTwo) {
+            const auto Neighbor = Result.selection(Record.FirstNeighbor);
+            if (!Neighbor)
+              return makeUnexpected(ErrorCode::InternalError,
+                                    "PBQP back-propagation encountered an unsolved neighbor");
+            Candidate = addCosts(Candidate, Record.FirstCosts.at(Option, *Neighbor));
+          }
+          if (Record.Kind == ReductionKind::DegreeTwo) {
+            const auto Neighbor = Result.selection(Record.SecondNeighbor);
+            if (!Neighbor)
+              return makeUnexpected(ErrorCode::InternalError,
+                                    "PBQP back-propagation encountered an unsolved neighbor");
+            Candidate = addCosts(Candidate, Record.SecondCosts.at(Option, *Neighbor));
+          }
+          if (Candidate < Best) {
+            Best = Candidate;
+            Choice = Option;
+          }
+        }
+        if (isInfinite(Best))
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "PBQP reductions produced no finite option");
+      }
+      auto Set = Result.setSelection(Record.Node, Choice);
+      if (!Set)
+        return std::unexpected(Set.error());
+    }
+
+    Cost Total = 0;
+    for (const Node &NodeValue : Problem.nodes()) {
+      const auto Selection = Result.selection(NodeValue.ID);
+      if (!Selection) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP solver did not select a reduced node option");
+      }
+      Total = addCosts(Total, NodeValue.Costs[Selection.value()]);
+    }
+    for (const Edge &EdgeValue : Problem.edges()) {
+      const auto FirstSelection = Result.selection(EdgeValue.First);
+      const auto SecondSelection = Result.selection(EdgeValue.Second);
+      if (!FirstSelection || !SecondSelection) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP solver did not select an edge endpoint option");
+      }
+      Total = addCosts(Total, EdgeValue.Costs.at(FirstSelection.value(), SecondSelection.value()));
+    }
+    if (isInfinite(Total))
+      return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                            "PBQP problem has no finite solution");
+    Result.setTotalCost(Total);
+    auto ResultVerification = Result.verify(Problem);
+    if (!ResultVerification)
+      return std::unexpected(ResultVerification.error());
+    return Result;
+  }
+
+private:
+  struct WorkingEdge final {
+    NodeID First;
+    NodeID Second;
+    CostMatrix Costs;
+  };
+
+  class WorkingProblem final {
+  public:
+    explicit WorkingProblem(const Graph &Problem) {
+      Costs.reserve(Problem.nodeCount());
+      StableKeys.reserve(Problem.nodeCount());
+      Active.assign(Problem.nodeCount(), true);
+      for (const Node &NodeValue : Problem.nodes()) {
+        Costs.push_back(NodeValue.Costs);
+        StableKeys.push_back(NodeValue.StableKey);
+      }
+      for (const Edge &EdgeValue : Problem.edges())
+        Edges.emplace(key(EdgeValue.First, EdgeValue.Second),
+                      WorkingEdge{EdgeValue.First, EdgeValue.Second, EdgeValue.Costs});
+      ActiveCount = Problem.nodeCount();
+    }
+
+    [[nodiscard]] std::size_t activeNodeCount() const noexcept {
+      return ActiveCount;
+    }
+
+    [[nodiscard]] std::size_t degree(NodeID ID) const noexcept {
+      std::size_t Result = 0;
+      for (const auto &[EdgeKey, EdgeValue] : Edges) {
+        (void)EdgeKey;
+        if (Active[EdgeValue.First.value()] && Active[EdgeValue.Second.value()] &&
+            (EdgeValue.First == ID || EdgeValue.Second == ID))
+          ++Result;
+      }
+      return Result;
+    }
+
+    [[nodiscard]] NodeID selectReductionNode() const noexcept {
+      std::optional<std::tuple<bool, std::size_t, std::uint64_t, std::uint32_t>> Best;
+      NodeID Result;
+      for (std::size_t Index = 0; Index < Active.size(); ++Index) {
+        if (!Active[Index])
+          continue;
+        const NodeID ID = NodeID::fromValue(static_cast<std::uint32_t>(Index));
+        const std::size_t Degree = degree(ID);
+        const auto Rank = std::tuple{Degree > 2, Degree, StableKeys[Index], ID.value()};
+        if (!Best || Rank < *Best) {
+          Best = Rank;
+          Result = ID;
+        }
+      }
+      return Result;
+    }
+
+    [[nodiscard]] Expected<ReductionRecord> reduceDegreeZero(NodeID ID) {
+      ReductionRecord Record;
+      Record.Kind = ReductionKind::DegreeZero;
+      Record.Node = ID;
+      Record.NodeCosts = Costs[ID.value()];
+      deactivate(ID);
+      return Record;
+    }
+
+    [[nodiscard]] Expected<ReductionRecord> reduceDegreeOne(NodeID ID) {
+      const std::vector<WorkingEdge> Incident = incidentEdges(ID);
+      if (Incident.size() != 1)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP degree-one reduction is inconsistent");
+      const WorkingEdge &EdgeValue = Incident.front();
+      const NodeID Neighbor = other(EdgeValue, ID);
+      const CostMatrix Oriented = orientFrom(EdgeValue, ID);
+
+      ReductionRecord Record;
+      Record.Kind = ReductionKind::DegreeOne;
+      Record.Node = ID;
+      Record.FirstNeighbor = Neighbor;
+      Record.NodeCosts = Costs[ID.value()];
+      Record.FirstCosts = Oriented;
+
+      for (std::size_t NeighborOption = 0; NeighborOption < Costs[Neighbor.value()].size();
+           ++NeighborOption) {
+        Cost Minimum = InfiniteCost;
+        for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) {
+          Minimum = std::min(
+              Minimum, addCosts(Costs[ID.value()][Option], Oriented.at(Option, NeighborOption)));
+        }
+        Costs[Neighbor.value()][NeighborOption] =
+            addCosts(Costs[Neighbor.value()][NeighborOption], Minimum);
+      }
+      removeIncidentEdges(ID);
+      deactivate(ID);
+      return Record;
+    }
+
+    [[nodiscard]] Expected<ReductionRecord> reduceDegreeTwo(NodeID ID) {
+      const std::vector<WorkingEdge> Incident = incidentEdges(ID);
+      if (Incident.size() != 2)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP degree-two reduction is inconsistent");
+      NodeID First = other(Incident[0], ID);
+      NodeID Second = other(Incident[1], ID);
+      CostMatrix FirstCosts = orientFrom(Incident[0], ID);
+      CostMatrix SecondCosts = orientFrom(Incident[1], ID);
+      if (Second < First) {
+        std::swap(First, Second);
+        std::swap(FirstCosts, SecondCosts);
+      }
+
+      ReductionRecord Record;
+      Record.Kind = ReductionKind::DegreeTwo;
+      Record.Node = ID;
+      Record.FirstNeighbor = First;
+      Record.SecondNeighbor = Second;
+      Record.NodeCosts = Costs[ID.value()];
+      Record.FirstCosts = FirstCosts;
+      Record.SecondCosts = SecondCosts;
+
+      CostMatrix Delta(Costs[First.value()].size(), Costs[Second.value()].size(), InfiniteCost);
+      for (std::size_t FirstOption = 0; FirstOption < Delta.rows(); ++FirstOption) {
+        for (std::size_t SecondOption = 0; SecondOption < Delta.columns(); ++SecondOption) {
+          for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) {
+            const Cost Candidate =
+                addCosts(Costs[ID.value()][Option], addCosts(FirstCosts.at(Option, FirstOption),
+                                                             SecondCosts.at(Option, SecondOption)));
+            Delta.at(FirstOption, SecondOption) =
+                std::min(Delta.at(FirstOption, SecondOption), Candidate);
+          }
+        }
+      }
+      removeIncidentEdges(ID);
+      const auto Position = Edges.find(key(First, Second));
+      if (Position == Edges.end())
+        Edges.emplace(key(First, Second), WorkingEdge{First, Second, std::move(Delta)});
+      else
+        Position->second.Costs.add(Delta);
+      deactivate(ID);
+      return Record;
+    }
+
+    [[nodiscard]] Expected<ReductionRecord> reduceHeuristically(NodeID ID) {
+      const std::vector<WorkingEdge> Incident = incidentEdges(ID);
+      Cost Best = InfiniteCost;
+      std::size_t Choice = 0;
+      for (std::size_t Option = 0; Option < Costs[ID.value()].size(); ++Option) {
+        Cost Candidate = Costs[ID.value()][Option];
+        for (const WorkingEdge &EdgeValue : Incident) {
+          const NodeID Neighbor = other(EdgeValue, ID);
+          const CostMatrix Oriented = orientFrom(EdgeValue, ID);
+          Cost NeighborMinimum = InfiniteCost;
+          for (std::size_t NeighborOption = 0; NeighborOption < Costs[Neighbor.value()].size();
+               ++NeighborOption) {
+            NeighborMinimum = std::min(NeighborMinimum, Oriented.at(Option, NeighborOption));
+          }
+          Candidate = addCosts(Candidate, NeighborMinimum);
+        }
+        if (Candidate < Best) {
+          Best = Candidate;
+          Choice = Option;
+        }
+      }
+      if (isInfinite(Best))
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "PBQP heuristic reduction has no finite option");
+
+      ReductionRecord Record;
+      Record.Kind = ReductionKind::Heuristic;
+      Record.Node = ID;
+      Record.FixedSelection = Choice;
+      Record.NodeCosts = Costs[ID.value()];
+      for (const WorkingEdge &EdgeValue : Incident) {
+        const NodeID Neighbor = other(EdgeValue, ID);
+        const CostMatrix Oriented = orientFrom(EdgeValue, ID);
+        for (std::size_t Option = 0; Option < Costs[Neighbor.value()].size(); ++Option) {
+          Costs[Neighbor.value()][Option] =
+              addCosts(Costs[Neighbor.value()][Option], Oriented.at(Choice, Option));
+        }
+      }
+      removeIncidentEdges(ID);
+      deactivate(ID);
+      return Record;
+    }
+
+  private:
+    using EdgeKey = std::pair<std::uint32_t, std::uint32_t>;
+
+    [[nodiscard]] static EdgeKey key(NodeID First, NodeID Second) noexcept {
+      if (Second < First)
+        std::swap(First, Second);
+      return {First.value(), Second.value()};
+    }
+
+    [[nodiscard]] static NodeID other(const WorkingEdge &EdgeValue, NodeID ID) noexcept {
+      return EdgeValue.First == ID ? EdgeValue.Second : EdgeValue.First;
+    }
+
+    [[nodiscard]] static CostMatrix orientFrom(const WorkingEdge &EdgeValue, NodeID ID) {
+      return EdgeValue.First == ID ? EdgeValue.Costs : EdgeValue.Costs.transpose();
+    }
+
+    [[nodiscard]] std::vector<WorkingEdge> incidentEdges(NodeID ID) const {
+      std::vector<WorkingEdge> Result;
+      for (const auto &[EdgeKeyValue, EdgeValue] : Edges) {
+        (void)EdgeKeyValue;
+        if (Active[EdgeValue.First.value()] && Active[EdgeValue.Second.value()] &&
+            (EdgeValue.First == ID || EdgeValue.Second == ID))
+          Result.push_back(EdgeValue);
+      }
+      return Result;
+    }
+
+    void removeIncidentEdges(NodeID ID) {
+      for (auto Position = Edges.begin(); Position != Edges.end();) {
+        if (Position->second.First == ID || Position->second.Second == ID)
+          Position = Edges.erase(Position);
+        else
+          ++Position;
+      }
+    }
+
+    void deactivate(NodeID ID) noexcept {
+      Active[ID.value()] = false;
+      --ActiveCount;
+    }
+
+    std::vector<CostVector> Costs;
+    std::vector<std::uint64_t> StableKeys;
+    std::vector<bool> Active;
+    std::size_t ActiveCount = 0;
+    std::map<EdgeKey, WorkingEdge> Edges;
+  };
+};
+
+} // namespace rcc::pbqp
+
+#endif // RCC_CODEGEN_PBQP_SOLVER_H
diff --git a/backend/include/rcc/CodeGen/RegAllocCommon.h b/backend/include/rcc/CodeGen/RegAllocCommon.h
new file mode 100644
index 0000000..0df9799
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegAllocCommon.h
@@ -0,0 +1,25 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGALLOCCOMMON_H
+#define RCC_CODEGEN_REGALLOCCOMMON_H
+
+#include "rcc/CodeGen/MachinePass.h"
+
+#include <memory>
+
+namespace rcc {
+
+class TargetRegisterAllocationInfo;
+
+struct RegisterAllocationOptions final {
+  bool EnableRematerialization = true;
+  bool EnableCopyCoalescing = true;
+};
+
+[[nodiscard]] std::unique_ptr<MachineFunctionPass>
+createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                         RegisterAllocationOptions Options = {});
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGALLOCCOMMON_H
diff --git a/backend/include/rcc/CodeGen/RegAllocFast.h b/backend/include/rcc/CodeGen/RegAllocFast.h
new file mode 100644
index 0000000..84cf30c
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegAllocFast.h
@@ -0,0 +1,26 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGALLOCFAST_H
+#define RCC_CODEGEN_REGALLOCFAST_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+
+namespace rcc {
+
+class FastAllocatorPass final : public MachineFunctionPass {
+public:
+  explicit FastAllocatorPass(const TargetRegisterAllocationInfo &Info) noexcept : Info(&Info) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  const TargetRegisterAllocationInfo *Info;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGALLOCFAST_H
diff --git a/backend/include/rcc/CodeGen/RegAllocPBQP.h b/backend/include/rcc/CodeGen/RegAllocPBQP.h
new file mode 100644
index 0000000..368cbee
--- /dev/null
+++ b/backend/include/rcc/CodeGen/RegAllocPBQP.h
@@ -0,0 +1,29 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_REGALLOCPBQP_H
+#define RCC_CODEGEN_REGALLOCPBQP_H
+
+#include "rcc/CodeGen/RegAllocCommon.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+
+namespace rcc {
+
+class PBQPAllocatorPass final : public MachineFunctionPass {
+public:
+  explicit PBQPAllocatorPass(const TargetRegisterAllocationInfo &Info,
+                             RegisterAllocationOptions Options = {}) noexcept
+      : Info(&Info), Options(Options) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  const TargetRegisterAllocationInfo *Info;
+  RegisterAllocationOptions Options;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_REGALLOCPBQP_H
diff --git a/backend/include/rcc/CodeGen/Spiller.h b/backend/include/rcc/CodeGen/Spiller.h
new file mode 100644
index 0000000..3d1fc66
--- /dev/null
+++ b/backend/include/rcc/CodeGen/Spiller.h
@@ -0,0 +1,41 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_SPILLER_H
+#define RCC_CODEGEN_SPILLER_H
+
+#include "rcc/CodeGen/LiveRangeEdit.h"
+#include "rcc/CodeGen/TargetRegisterAllocationInfo.h"
+
+#include <optional>
+#include <vector>
+
+namespace rcc {
+
+class Spiller final {
+public:
+  Spiller(MachineFunction &Function, const TargetDescription &Target,
+          const TargetRegisterAllocationInfo &TargetInfo, VirtRegMap &Mapping,
+          bool EnableRematerialization = true)
+      : Function(&Function), Target(&Target), TargetInfo(&TargetInfo), Mapping(&Mapping),
+        Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization) {}
+
+  [[nodiscard]] Expected<std::vector<Register>> spill(Register VirtualReg);
+
+private:
+  [[nodiscard]] Expected<std::vector<Register>> spillAtInstructions(Register VirtualReg);
+  [[nodiscard]] Expected<void> spillLiveIn(Register VirtualReg, RegisterClassID Class,
+                                           FrameIndex StackSlot);
+  [[nodiscard]] Expected<std::optional<std::vector<Register>>>
+  tryRematerialize(Register VirtualReg);
+
+  MachineFunction *Function;
+  const TargetDescription *Target;
+  const TargetRegisterAllocationInfo *TargetInfo;
+  VirtRegMap *Mapping;
+  LiveRangeEdit Edit;
+  bool EnableRematerialization;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_SPILLER_H
diff --git a/backend/include/rcc/CodeGen/TargetMIRTextInfo.h b/backend/include/rcc/CodeGen/TargetMIRTextInfo.h
index b8eb4ee..3ed6022 100644
--- a/backend/include/rcc/CodeGen/TargetMIRTextInfo.h
+++ b/backend/include/rcc/CodeGen/TargetMIRTextInfo.h
@@ -68,10 +68,8 @@ struct MIRTargetMappingEntry final {
                          const MIRTargetMappingEntry &Right) = default;
 };
 
-using MIRTargetFunctionStateParser =
-    Expected<TargetFunctionState> (*)(const MIRTargetNode &Node);
-using MIRTargetFunctionStatePrinter =
-    Expected<MIRTargetNode> (*)(const TargetFunctionState &State);
+using MIRTargetFunctionStateParser = Expected<TargetFunctionState> (*)(const MIRTargetNode &Node);
+using MIRTargetFunctionStatePrinter = Expected<MIRTargetNode> (*)(const TargetFunctionState &State);
 using MIRTargetConstantParser = Expected<TargetConstant> (*)(std::string_view Text);
 using MIRTargetConstantPrinter = Expected<std::string> (*)(const TargetConstant &Constant);
 
@@ -235,13 +233,10 @@ public:
     return Description.FunctionStateType;
   }
 
-  [[nodiscard]] Expected<TargetFunctionState>
-  parseFunctionState(const MIRTargetNode &Node) const;
-  [[nodiscard]] Expected<MIRTargetNode>
-  printFunctionState(const TargetFunctionState &State) const;
+  [[nodiscard]] Expected<TargetFunctionState> parseFunctionState(const MIRTargetNode &Node) const;
+  [[nodiscard]] Expected<MIRTargetNode> printFunctionState(const TargetFunctionState &State) const;
   [[nodiscard]] Expected<TargetConstant> parseTargetConstant(std::string_view Text) const;
-  [[nodiscard]] Expected<std::string>
-  printTargetConstant(const TargetConstant &Constant) const;
+  [[nodiscard]] Expected<std::string> printTargetConstant(const TargetConstant &Constant) const;
 
 private:
   explicit TargetMIRTextInfo(TargetMIRTextInfoDesc Description)
diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
new file mode 100644
index 0000000..6e25465
--- /dev/null
+++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
@@ -0,0 +1,58 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H
+#define RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H
+
+#include "rcc/CodeGen/MachineFrameInfo.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <cstdint>
+
+namespace rcc {
+
+class MachineIRBuilder;
+class MachineInstr;
+class TargetDescription;
+
+class TargetRegisterAllocationInfo {
+public:
+  virtual ~TargetRegisterAllocationInfo() = default;
+
+  [[nodiscard]] virtual Expected<void>
+  validateSpillReload(RegisterClassID Class, const TargetDescription &Target) const = 0;
+  [[nodiscard]] virtual Expected<MachineInstr *>
+  emitReload(MachineIRBuilder &Builder, Register Destination, RegisterClassID Class,
+             FrameIndex StackSlot, LaneMask Lanes) const = 0;
+  [[nodiscard]] virtual Expected<MachineInstr *> emitSpill(MachineIRBuilder &Builder,
+                                                           Register Source, RegisterClassID Class,
+                                                           FrameIndex StackSlot,
+                                                           LaneMask Lanes) const = 0;
+
+  [[nodiscard]] virtual Expected<bool> isRematerializable(const MachineInstr &, Register,
+                                                          const MachineFunction &,
+                                                          const TargetDescription &) const {
+    return false;
+  }
+  [[nodiscard]] virtual Expected<MachineInstr *> rematerialize(MachineIRBuilder &,
+                                                               const MachineInstr &, Register,
+                                                               Register,
+                                                               const TargetDescription &) const {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "target accepted rematerialization without implementing it");
+  }
+
+  [[nodiscard]] virtual std::uint64_t physicalRegisterCost(const MachineFunction &, Register,
+                                                           PhysicalRegister, RegisterClassID,
+                                                           bool) const noexcept {
+    return 0;
+  }
+  [[nodiscard]] virtual std::uint64_t spillCost(const MachineFunction &, const LiveInterval &,
+                                                RegisterClassID) const noexcept {
+    return 1;
+  }
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H
diff --git a/backend/include/rcc/CodeGen/VirtRegMap.h b/backend/include/rcc/CodeGen/VirtRegMap.h
new file mode 100644
index 0000000..f37af84
--- /dev/null
+++ b/backend/include/rcc/CodeGen/VirtRegMap.h
@@ -0,0 +1,93 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_VIRTREGMAP_H
+#define RCC_CODEGEN_VIRTREGMAP_H
+
+#include "rcc/CodeGen/MachineFrameInfo.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <cstdint>
+#include <optional>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunction;
+class TargetDescription;
+
+enum class VirtRegAllocationState : std::uint8_t {
+  Unassigned,
+  Assigned,
+  Spilled,
+  Split,
+};
+
+struct VirtRegSpillMetadata final {
+  std::optional<FrameIndex> StackSlot;
+  LaneMask Lanes = LaneMask::all();
+  std::uint64_t SpillCount = 0;
+  std::uint64_t ReloadCount = 0;
+  std::uint64_t RematerializationCount = 0;
+};
+
+struct VirtRegMapEntry final {
+  Register VirtualReg;
+  VirtRegAllocationState State = VirtRegAllocationState::Unassigned;
+  std::optional<PhysicalRegister> PhysicalReg;
+  std::optional<Register> SplitParent;
+  std::optional<Register> Origin;
+  bool Spillable = true;
+  VirtRegSpillMetadata Spill;
+};
+
+class VirtRegMap final {
+public:
+  explicit VirtRegMap(MachineFunction &Function) noexcept : Function(&Function) {}
+
+  [[nodiscard]] MachineFunction &function() const noexcept {
+    return *Function;
+  }
+  [[nodiscard]] Expected<void> add(Register VirtualReg, bool Spillable = true,
+                                   std::optional<Register> SplitParent = std::nullopt,
+                                   std::optional<Register> Origin = std::nullopt);
+  [[nodiscard]] Expected<void> assign(Register VirtualReg, PhysicalRegister PhysicalReg);
+  [[nodiscard]] Expected<void> assignStackSlot(Register VirtualReg, FrameIndex StackSlot,
+                                               LaneMask Lanes = LaneMask::all());
+  [[nodiscard]] Expected<void> markSplit(Register VirtualReg, Register Parent, Register Origin);
+  [[nodiscard]] Expected<void> setSpillable(Register VirtualReg, bool Spillable);
+  [[nodiscard]] VirtRegMapEntry *entry(Register VirtualReg) noexcept;
+  [[nodiscard]] const VirtRegMapEntry *entry(Register VirtualReg) const noexcept;
+  [[nodiscard]] std::optional<PhysicalRegister>
+  physicalRegister(Register VirtualReg) const noexcept;
+  [[nodiscard]] std::optional<FrameIndex> stackSlot(Register VirtualReg) const noexcept;
+  [[nodiscard]] bool isSpillable(Register VirtualReg) const noexcept;
+  [[nodiscard]] std::vector<const VirtRegMapEntry *> orderedEntries() const;
+  [[nodiscard]] Expected<void> verify() const;
+
+private:
+  MachineFunction *Function;
+  std::unordered_map<Register, VirtRegMapEntry> Entries;
+};
+
+[[nodiscard]] Expected<bool> rewriteVirtualRegisters(MachineFunction &Function,
+                                                     const TargetDescription &Target,
+                                                     const VirtRegMap &Mapping);
+
+class VirtualRegisterRewritePass final : public MachineFunctionPass {
+public:
+  explicit VirtualRegisterRewritePass(const VirtRegMap &Mapping) noexcept : Mapping(&Mapping) {}
+
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+
+private:
+  const VirtRegMap *Mapping;
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_VIRTREGMAP_H
diff --git a/backend/include/rcc/MIR/EmbeddedIR.h b/backend/include/rcc/MIR/EmbeddedIR.h
index 50567de..522a217 100644
--- a/backend/include/rcc/MIR/EmbeddedIR.h
+++ b/backend/include/rcc/MIR/EmbeddedIR.h
@@ -122,8 +122,7 @@ public:
     return GlobalObjects;
   }
 
-  [[nodiscard]] std::span<const EmbeddedIRMetadataDefinition>
-  metadataDefinitions() const noexcept {
+  [[nodiscard]] std::span<const EmbeddedIRMetadataDefinition> metadataDefinitions() const noexcept {
     return MetadataDefinitions;
   }
 
@@ -134,7 +133,8 @@ public:
   [[nodiscard]] const EmbeddedIRFunction *function(std::string_view Name) const noexcept;
   [[nodiscard]] const EmbeddedIRReference *globalObject(std::string_view Name) const noexcept;
   [[nodiscard]] const EmbeddedIRMetadataDefinition *metadata(std::string_view Name) const noexcept;
-  [[nodiscard]] const EmbeddedIRTypeDefinition *typeDefinition(std::string_view Name) const noexcept;
+  [[nodiscard]] const EmbeddedIRTypeDefinition *
+  typeDefinition(std::string_view Name) const noexcept;
   [[nodiscard]] bool hasGlobalValue(std::string_view Name) const noexcept {
     return function(Name) != nullptr || globalObject(Name) != nullptr;
   }
diff --git a/backend/include/rcc/Support/Error.h b/backend/include/rcc/Support/Error.h
index 3d50b46..81568de 100644
--- a/backend/include/rcc/Support/Error.h
+++ b/backend/include/rcc/Support/Error.h
@@ -16,6 +16,7 @@ enum class ErrorCode : std::uint8_t {
   ParseError,
   VerificationError,
   Unsupported,
+  RegisterAllocationFailed,
   IoError,
   InternalError,
 };
diff --git a/backend/include/rcc/Target/RISCV/RISCVCodeGen.h b/backend/include/rcc/Target/RISCV/RISCVCodeGen.h
index 4db60f7..403bb2d 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/TargetRegisterAllocationInfo.h"
 
 namespace rcc::riscv {
 
@@ -11,6 +12,7 @@ namespace rcc::riscv {
 [[nodiscard]] const TargetRegisterBankInfo &registerBankInfo() noexcept;
 [[nodiscard]] const TargetInstructionSelector &instructionSelector() noexcept;
 [[nodiscard]] const TargetSSAInfo &ssaInfo() noexcept;
+[[nodiscard]] const TargetRegisterAllocationInfo &registerAllocationInfo() noexcept;
 
 } // namespace rcc::riscv