[CodeGen] Complete register allocation infrastructure

5 files changed, 767 insertions, 0 deletions

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