9 files changed, 542 insertions, 416 deletions
diff --git a/backend/include/rcc/CodeGen/LiveInterval.h b/backend/include/rcc/CodeGen/LiveInterval.h
new file mode 100644
index 0000000..28791f1
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveInterval.h
@@ -0,0 +1,144 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVEINTERVAL_H
+#define RCC_CODEGEN_LIVEINTERVAL_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/CodeGen/SlotIndexes.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <compare>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <span>
+#include <vector>
+
+namespace rcc {
+
+class LiveValueNumberID final {
+public:
+  constexpr LiveValueNumberID() noexcept = default;
+
+  [[nodiscard]] static constexpr LiveValueNumberID fromValue(std::uint32_t Value) noexcept {
+    return LiveValueNumberID(Value);
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != 0;
+  }
+
+  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
+    return Value;
+  }
+
+  friend constexpr bool operator==(LiveValueNumberID, LiveValueNumberID) noexcept = default;
+  friend constexpr auto operator<=>(LiveValueNumberID, LiveValueNumberID) noexcept = default;
+
+private:
+  explicit constexpr LiveValueNumberID(std::uint32_t Value) noexcept : Value(Value) {}
+
+  std::uint32_t Value = 0;
+};
+
+enum class LiveValueState : std::uint8_t {
+  Normal,
+  Phi,
+  Unused,
+  Redefined,
+};
+
+struct LiveValueNumber final {
+  LiveValueNumberID ID;
+  SlotIndex Definition;
+  LiveValueState State = LiveValueState::Normal;
+  std::optional<MachineInstrStableID> Origin;
+
+  friend bool operator==(const LiveValueNumber &, const LiveValueNumber &) = default;
+};
+
+struct LiveSegment final {
+  SlotIndex Start;
+  SlotIndex End;
+  LiveValueNumberID Value;
+
+  [[nodiscard]] constexpr bool empty() const noexcept {
+    return !(Start < End);
+  }
+
+  [[nodiscard]] constexpr bool contains(SlotIndex Position) const noexcept {
+    return !(Position < Start) && Position < End;
+  }
+
+  [[nodiscard]] constexpr bool overlaps(const LiveSegment &Other) const noexcept {
+    return Start < Other.End && Other.Start < End;
+  }
+
+  friend constexpr bool operator==(const LiveSegment &, const LiveSegment &) noexcept = default;
+};
+
+class LiveRange final {
+public:
+  [[nodiscard]] std::span<const LiveSegment> segments() const noexcept {
+    return Segments;
+  }
+  [[nodiscard]] std::span<const LiveValueNumber> values() const noexcept {
+    return Values;
+  }
+  [[nodiscard]] bool empty() const noexcept {
+    return Segments.empty();
+  }
+
+  [[nodiscard]] const LiveSegment *segmentAt(SlotIndex Position) const noexcept;
+  [[nodiscard]] const LiveValueNumber *value(LiveValueNumberID ID) const noexcept;
+  [[nodiscard]] const LiveValueNumber *valueAt(SlotIndex Position) const noexcept;
+  [[nodiscard]] bool liveAt(SlotIndex Position) const noexcept;
+  [[nodiscard]] bool overlaps(const LiveRange &Other) const noexcept;
+
+  [[nodiscard]] Expected<LiveValueNumberID>
+  createValue(SlotIndex Definition, LiveValueState State = LiveValueState::Normal,
+              std::optional<MachineInstrStableID> Origin = std::nullopt);
+  [[nodiscard]] Expected<void> addSegment(LiveSegment Segment);
+  [[nodiscard]] Expected<void> extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End);
+  [[nodiscard]] Expected<void> remove(SlotIndex Start, SlotIndex End);
+  [[nodiscard]] Expected<void> shrinkToUses(std::span<const SlotIndex> Uses);
+  [[nodiscard]] Expected<void> verify() const;
+
+private:
+  void mergeAdjacent();
+
+  std::vector<LiveSegment> Segments;
+  std::vector<LiveValueNumber> Values;
+};
+
+struct LiveSubRange final {
+  LaneMask Lanes;
+  LiveRange Range;
+};
+
+struct LiveInterval final {
+  Register Reg;
+  LiveRange MainRange;
+  std::vector<LiveSubRange> SubRanges;
+  std::uint64_t SpillWeight = 0;
+  bool Spillable = true;
+  std::vector<PhysicalRegister> AllocationHints;
+  std::optional<Register> SplitParent;
+  std::optional<Register> Origin;
+
+  [[nodiscard]] bool overlaps(const LiveInterval &Other) const noexcept {
+    return MainRange.overlaps(Other.MainRange);
+  }
+};
+
+} // namespace rcc
+
+template <> struct std::hash<rcc::LiveValueNumberID> {
+  [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept {
+    return std::hash<std::uint32_t>{}(ID.value());
+  }
+};
+
+#endif // RCC_CODEGEN_LIVEINTERVAL_H
diff --git a/backend/include/rcc/CodeGen/LiveIntervals.h b/backend/include/rcc/CodeGen/LiveIntervals.h
new file mode 100644
index 0000000..a45c593
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveIntervals.h
@@ -0,0 +1,73 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVEINTERVALS_H
+#define RCC_CODEGEN_LIVEINTERVALS_H
+
+#include "rcc/CodeGen/LiveInterval.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/RegisterMask.h"
+
+#include <cstdint>
+#include <memory>
+#include <optional>
+#include <span>
+#include <string_view>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+struct RegMaskPosition final {
+  SlotIndex Position;
+  MachineInstrStableID Instruction;
+  std::shared_ptr<const RegisterMask> Mask;
+};
+
+class LiveIntervalsAnalysis final {
+public:
+  class Result final {
+  public:
+    [[nodiscard]] const SlotIndexesAnalysis::Result &slotIndexes() const noexcept {
+      return Indexes;
+    }
+    [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept {
+      return Indexes.instructionIndex(Instruction);
+    }
+    [[nodiscard]] const LiveInterval *interval(Register Reg) const noexcept;
+    [[nodiscard]] LiveInterval *interval(Register Reg) noexcept;
+    [[nodiscard]] const LiveRange *regUnitRange(RegisterUnitID Unit) const noexcept;
+    [[nodiscard]] std::span<const RegMaskPosition> regMaskPositions() const noexcept {
+      return RegMasks;
+    }
+    [[nodiscard]] bool interferes(Register Left, Register Right) const noexcept;
+    [[nodiscard]] bool regMaskClobbers(const LiveInterval &Interval,
+                                       PhysicalRegister Candidate) const noexcept;
+    [[nodiscard]] Expected<void> shrinkToUses(Register Reg, std::span<const SlotIndex> Uses);
+
+    [[nodiscard]] bool invalidate(const MachineFunction &,
+                                  const PreservedAnalyses &Preserved) const noexcept;
+
+  private:
+    SlotIndexesAnalysis::Result Indexes;
+    std::unordered_map<Register, LiveInterval> Intervals;
+    std::unordered_map<RegisterUnitID, LiveRange> RegisterUnitRanges;
+    std::vector<RegMaskPosition> RegMasks;
+
+    friend class LiveIntervalsAnalysis;
+  };
+
+  [[nodiscard]] static constexpr std::string_view name() noexcept {
+    return "LiveIntervals";
+  }
+
+  [[nodiscard]] static Expected<Result>
+  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
+};
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_LIVEINTERVALS_H
diff --git a/backend/include/rcc/CodeGen/MachineLivenessRepair.h b/backend/include/rcc/CodeGen/LivePhysRegs.h
index 049e166..3d4b7ef 100644
--- a/backend/include/rcc/CodeGen/MachineLivenessRepair.h
+++ b/backend/include/rcc/CodeGen/LivePhysRegs.h
@@ -1,9 +1,9 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
-#ifndef RCC_CODEGEN_MACHINELIVENESSREPAIR_H
-#define RCC_CODEGEN_MACHINELIVENESSREPAIR_H
+#ifndef RCC_CODEGEN_LIVEPHYSREGS_H
+#define RCC_CODEGEN_LIVEPHYSREGS_H
 
-#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/LiveVariables.h"
 #include "rcc/Support/Error.h"
 
 #include <span>
@@ -20,4 +20,4 @@ repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks,
 
 } // namespace rcc
 
-#endif // RCC_CODEGEN_MACHINELIVENESSREPAIR_H
+#endif // RCC_CODEGEN_LIVEPHYSREGS_H
diff --git a/backend/include/rcc/CodeGen/LiveRegMatrix.h b/backend/include/rcc/CodeGen/LiveRegMatrix.h
index 953828c..fd1bac4 100644
--- a/backend/include/rcc/CodeGen/LiveRegMatrix.h
+++ b/backend/include/rcc/CodeGen/LiveRegMatrix.h
@@ -3,7 +3,7 @@
 #ifndef RCC_CODEGEN_LIVEREGMATRIX_H
 #define RCC_CODEGEN_LIVEREGMATRIX_H
 
-#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/LiveIntervals.h"
 #include "rcc/CodeGen/TargetRegisterInfo.h"
 
 #include <cstdint>
diff --git a/backend/include/rcc/CodeGen/LiveRegUnits.h b/backend/include/rcc/CodeGen/LiveRegUnits.h
new file mode 100644
index 0000000..6eb06a6
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveRegUnits.h
@@ -0,0 +1,84 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVEREGUNITS_H
+#define RCC_CODEGEN_LIVEREGUNITS_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunction;
+class MachineInstr;
+class MachineOperand;
+class RegisterMask;
+class TargetDescription;
+struct PhysicalRegisterDesc;
+
+class LiveRegUnits final {
+public:
+  [[nodiscard]] LaneMask lanes(RegisterUnitID Unit) const noexcept;
+  [[nodiscard]] bool contains(RegisterUnitID Unit, LaneMask Lanes = LaneMask::all()) const noexcept;
+  [[nodiscard]] bool intersects(RegisterUnitID Unit,
+                                LaneMask Lanes = LaneMask::all()) const noexcept;
+  [[nodiscard]] bool empty() const noexcept {
+    return Values.empty();
+  }
+
+  void add(RegisterUnitID Unit, LaneMask Lanes);
+  void remove(RegisterUnitID Unit, LaneMask Lanes);
+  void unite(const LiveRegUnits &Other);
+  void subtract(const LiveRegUnits &Other);
+
+  [[nodiscard]] const std::unordered_map<RegisterUnitID, LaneMask> &entries() const noexcept {
+    return Values;
+  }
+
+  friend bool operator==(const LiveRegUnits &, const LiveRegUnits &) = default;
+
+private:
+  std::unordered_map<RegisterUnitID, LaneMask> Values;
+};
+
+struct PhysicalUnitAccess final {
+  RegisterUnitID Unit;
+  LaneMask Lanes;
+};
+
+[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes,
+                                          LaneMask RegisterLanes = LaneMask::all()) noexcept;
+[[nodiscard]] LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept;
+[[nodiscard]] LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept;
+[[nodiscard]] LiveRegUnits physicalRegisterCoverage(const PhysicalRegisterDesc &Description,
+                                                    LaneMask Requested = LaneMask::all());
+[[nodiscard]] bool isSubset(const LiveRegUnits &Subset, const LiveRegUnits &Superset) noexcept;
+[[nodiscard]] std::size_t laneCount(const LiveRegUnits &Set) noexcept;
+
+[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function,
+                                                      const TargetDescription &Target);
+[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand,
+                                                     const MachineFunction &Function,
+                                                     const TargetDescription &Target);
+[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>>
+physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target);
+
+void addPhysicalRegister(LiveRegUnits &Set, const PhysicalRegisterDesc &Description,
+                         LaneMask Requested = LaneMask::all());
+[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function,
+                                              const TargetDescription &Target) noexcept;
+[[nodiscard]] Expected<void> addRegisterMaskDefs(LiveRegUnits &Set, const RegisterMask &Mask,
+                                                 const TargetDescription &Target);
+[[nodiscard]] Expected<void> addRegisterMaskUses(LiveRegUnits &Set, const RegisterMask &Mask,
+                                                 const TargetDescription &Target);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_LIVEREGUNITS_H
diff --git a/backend/include/rcc/CodeGen/LiveVariables.h b/backend/include/rcc/CodeGen/LiveVariables.h
new file mode 100644
index 0000000..28a66c1
--- /dev/null
+++ b/backend/include/rcc/CodeGen/LiveVariables.h
@@ -0,0 +1,105 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_LIVEVARIABLES_H
+#define RCC_CODEGEN_LIVEVARIABLES_H
+
+#include "rcc/CodeGen/LiveRegUnits.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/Register.h"
+#include "rcc/Support/Error.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <string_view>
+#include <unordered_map>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class TargetDescription;
+
+class RegisterLaneSet final {
+public:
+  [[nodiscard]] LaneMask lanes(Register Reg) const noexcept;
+  [[nodiscard]] bool contains(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept;
+  [[nodiscard]] bool intersects(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept;
+  [[nodiscard]] bool empty() const noexcept {
+    return Values.empty();
+  }
+
+  void add(Register Reg, LaneMask Lanes);
+  void remove(Register Reg, LaneMask Lanes);
+  void unite(const RegisterLaneSet &Other);
+  void subtract(const RegisterLaneSet &Other);
+
+  [[nodiscard]] const std::unordered_map<Register, LaneMask> &entries() const noexcept {
+    return Values;
+  }
+
+  friend bool operator==(const RegisterLaneSet &, const RegisterLaneSet &) = default;
+
+private:
+  std::unordered_map<Register, LaneMask> Values;
+};
+
+struct MachineBlockLiveness final {
+  RegisterLaneSet VirtualUses;
+  RegisterLaneSet VirtualDefs;
+  RegisterLaneSet VirtualLiveIn;
+  RegisterLaneSet VirtualLiveOut;
+  LiveRegUnits PhysicalUses;
+  LiveRegUnits PhysicalDefs;
+  LiveRegUnits PhysicalLiveIn;
+  LiveRegUnits PhysicalLiveOut;
+};
+
+class LiveVariablesAnalysis final {
+public:
+  class Result final {
+  public:
+    [[nodiscard]] MachineBlockLiveness &getOrCreateBlock(const MachineBasicBlock &Block);
+    [[nodiscard]] const MachineBlockLiveness *block(const MachineBasicBlock &Block) const noexcept;
+    [[nodiscard]] bool isLiveIn(const MachineBasicBlock &Block, Register Reg,
+                                LaneMask Lanes = LaneMask::all()) const noexcept;
+    [[nodiscard]] bool isLiveOut(const MachineBasicBlock &Block, Register Reg,
+                                 LaneMask Lanes = LaneMask::all()) const noexcept;
+    [[nodiscard]] bool isUnitLiveIn(const MachineBasicBlock &Block, RegisterUnitID Unit,
+                                    LaneMask Lanes = LaneMask::all()) const noexcept;
+    [[nodiscard]] bool isUnitLiveOut(const MachineBasicBlock &Block, RegisterUnitID Unit,
+                                     LaneMask Lanes = LaneMask::all()) const noexcept;
+
+    [[nodiscard]] bool invalidate(const MachineFunction &,
+                                  const PreservedAnalyses &Preserved) const noexcept;
+
+  private:
+    std::unordered_map<const MachineBasicBlock *, MachineBlockLiveness> Blocks;
+
+    friend class LiveVariablesAnalysis;
+  };
+
+  [[nodiscard]] static constexpr std::string_view name() noexcept {
+    return "LiveVariables";
+  }
+
+  [[nodiscard]] static Expected<Result>
+  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
+};
+
+class RebuildMachineLivenessPass final : public MachineFunctionPass {
+public:
+  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
+  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
+                                                const TargetDescription &Target,
+                                                MachineAnalysisManager &Analyses) override;
+};
+
+[[nodiscard]] Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function,
+                                                          const TargetDescription &Target);
+[[nodiscard]] Expected<bool> rebuildMachineLiveness(MachineFunction &Function,
+                                                    const TargetDescription &Target);
+[[nodiscard]] Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses);
+
+} // namespace rcc
+
+#endif // RCC_CODEGEN_LIVEVARIABLES_H
diff --git a/backend/include/rcc/CodeGen/MachineLiveness.h b/backend/include/rcc/CodeGen/MachineLiveness.h
deleted file mode 100644
index 678f309..0000000
--- a/backend/include/rcc/CodeGen/MachineLiveness.h
+++ /dev/null
@@ -1,410 +0,0 @@
-// SPDX-License-Identifier: GPL-3.0-or-later
-
-#ifndef RCC_CODEGEN_MACHINELIVENESS_H
-#define RCC_CODEGEN_MACHINELIVENESS_H
-
-#include "rcc/CodeGen/MachineIRTypes.h"
-#include "rcc/CodeGen/MachinePass.h"
-#include "rcc/CodeGen/Register.h"
-#include "rcc/CodeGen/StableID.h"
-#include "rcc/Support/Error.h"
-
-#include <compare>
-#include <cstddef>
-#include <cstdint>
-#include <functional>
-#include <memory>
-#include <optional>
-#include <span>
-#include <string_view>
-#include <unordered_map>
-#include <vector>
-
-namespace rcc {
-
-class MachineBasicBlock;
-class MachineFunction;
-class MachineInstr;
-class RegisterMask;
-class TargetDescription;
-
-enum class SlotIndexKind : std::uint8_t {
-  Block,
-  EarlyClobber,
-  Register,
-  Dead,
-};
-
-class SlotIndex final {
-public:
-  constexpr SlotIndex() noexcept = default;
-
-  [[nodiscard]] static constexpr SlotIndex fromValue(std::uint64_t Value) noexcept {
-    return SlotIndex(Value);
-  }
-
-  [[nodiscard]] constexpr bool isValid() const noexcept {
-    return Value != 0;
-  }
-
-  [[nodiscard]] constexpr std::uint64_t value() const noexcept {
-    return Value;
-  }
-
-  [[nodiscard]] constexpr SlotIndexKind kind() const noexcept {
-    return static_cast<SlotIndexKind>(Value & KindMask);
-  }
-
-  [[nodiscard]] constexpr SlotIndex baseIndex() const noexcept {
-    return SlotIndex(Value & ~KindMask);
-  }
-
-  [[nodiscard]] constexpr SlotIndex withKind(SlotIndexKind Kind) const noexcept {
-    return isValid() ? SlotIndex((Value & ~KindMask) | static_cast<std::uint64_t>(Kind))
-                     : SlotIndex{};
-  }
-
-  [[nodiscard]] constexpr SlotIndex earlyClobberSlot() const noexcept {
-    return withKind(SlotIndexKind::EarlyClobber);
-  }
-
-  [[nodiscard]] constexpr SlotIndex registerSlot() const noexcept {
-    return withKind(SlotIndexKind::Register);
-  }
-
-  [[nodiscard]] constexpr SlotIndex deadSlot() const noexcept {
-    return withKind(SlotIndexKind::Dead);
-  }
-
-  friend constexpr bool operator==(SlotIndex, SlotIndex) noexcept = default;
-  friend constexpr auto operator<=>(SlotIndex, SlotIndex) noexcept = default;
-
-private:
-  static constexpr std::uint64_t KindMask = 3;
-
-  explicit constexpr SlotIndex(std::uint64_t Value) noexcept : Value(Value) {}
-
-  std::uint64_t Value = 0;
-};
-
-class SlotIndexesAnalysis final {
-public:
-  class Result final {
-  public:
-    [[nodiscard]] SlotIndex instructionIndex(const MachineInstr &Instruction) const noexcept;
-    [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept {
-      return instructionIndex(Instruction);
-    }
-    [[nodiscard]] SlotIndex blockStart(const MachineBasicBlock &Block) const noexcept;
-    [[nodiscard]] SlotIndex blockEnd(const MachineBasicBlock &Block) const noexcept;
-    [[nodiscard]] const MachineInstr *instructionFromIndex(SlotIndex Index) const noexcept;
-    [[nodiscard]] const MachineBasicBlock *blockFromIndex(SlotIndex Index) const noexcept;
-
-    [[nodiscard]] Expected<void> insertInstruction(const MachineInstr &Instruction);
-    [[nodiscard]] Expected<void> eraseInstruction(const MachineInstr &Instruction);
-    [[nodiscard]] Expected<void> renumber(MachineFunction &Function);
-
-    [[nodiscard]] bool invalidate(const MachineFunction &,
-                                  const PreservedAnalyses &Preserved) const noexcept;
-
-  private:
-    std::unordered_map<MachineInstrStableID, SlotIndex> InstructionSlots;
-    std::unordered_map<std::uint64_t, const MachineInstr *> SlotToInstruction;
-    std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockStarts;
-    std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockEnds;
-    std::vector<const MachineBasicBlock *> BlocksByStart;
-
-    friend class SlotIndexesAnalysis;
-  };
-
-  [[nodiscard]] static constexpr std::string_view name() noexcept {
-    return "SlotIndexes";
-  }
-
-  [[nodiscard]] static Expected<Result>
-  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
-};
-
-class RegisterLaneSet final {
-public:
-  [[nodiscard]] LaneMask lanes(Register Reg) const noexcept;
-  [[nodiscard]] bool contains(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept;
-  [[nodiscard]] bool intersects(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept;
-  [[nodiscard]] bool empty() const noexcept {
-    return Values.empty();
-  }
-
-  void add(Register Reg, LaneMask Lanes);
-  void remove(Register Reg, LaneMask Lanes);
-  void unite(const RegisterLaneSet &Other);
-  void subtract(const RegisterLaneSet &Other);
-
-  [[nodiscard]] const std::unordered_map<Register, LaneMask> &entries() const noexcept {
-    return Values;
-  }
-
-  friend bool operator==(const RegisterLaneSet &, const RegisterLaneSet &) = default;
-
-private:
-  std::unordered_map<Register, LaneMask> Values;
-};
-
-class RegisterUnitLaneSet final {
-public:
-  [[nodiscard]] LaneMask lanes(RegisterUnitID Unit) const noexcept;
-  [[nodiscard]] bool contains(RegisterUnitID Unit, LaneMask Lanes = LaneMask::all()) const noexcept;
-  [[nodiscard]] bool intersects(RegisterUnitID Unit,
-                                LaneMask Lanes = LaneMask::all()) const noexcept;
-  [[nodiscard]] bool empty() const noexcept {
-    return Values.empty();
-  }
-
-  void add(RegisterUnitID Unit, LaneMask Lanes);
-  void remove(RegisterUnitID Unit, LaneMask Lanes);
-  void unite(const RegisterUnitLaneSet &Other);
-  void subtract(const RegisterUnitLaneSet &Other);
-
-  [[nodiscard]] const std::unordered_map<RegisterUnitID, LaneMask> &entries() const noexcept {
-    return Values;
-  }
-
-  friend bool operator==(const RegisterUnitLaneSet &, const RegisterUnitLaneSet &) = default;
-
-private:
-  std::unordered_map<RegisterUnitID, LaneMask> Values;
-};
-
-struct MachineBlockLiveness final {
-  RegisterLaneSet VirtualUses;
-  RegisterLaneSet VirtualDefs;
-  RegisterLaneSet VirtualLiveIn;
-  RegisterLaneSet VirtualLiveOut;
-  RegisterUnitLaneSet PhysicalUses;
-  RegisterUnitLaneSet PhysicalDefs;
-  RegisterUnitLaneSet PhysicalLiveIn;
-  RegisterUnitLaneSet PhysicalLiveOut;
-};
-
-class LiveVariablesAnalysis final {
-public:
-  class Result final {
-  public:
-    [[nodiscard]] MachineBlockLiveness &getOrCreateBlock(const MachineBasicBlock &Block);
-    [[nodiscard]] const MachineBlockLiveness *block(const MachineBasicBlock &Block) const noexcept;
-    [[nodiscard]] bool isLiveIn(const MachineBasicBlock &Block, Register Reg,
-                                LaneMask Lanes = LaneMask::all()) const noexcept;
-    [[nodiscard]] bool isLiveOut(const MachineBasicBlock &Block, Register Reg,
-                                 LaneMask Lanes = LaneMask::all()) const noexcept;
-    [[nodiscard]] bool isUnitLiveIn(const MachineBasicBlock &Block, RegisterUnitID Unit,
-                                    LaneMask Lanes = LaneMask::all()) const noexcept;
-    [[nodiscard]] bool isUnitLiveOut(const MachineBasicBlock &Block, RegisterUnitID Unit,
-                                     LaneMask Lanes = LaneMask::all()) const noexcept;
-
-    [[nodiscard]] bool invalidate(const MachineFunction &,
-                                  const PreservedAnalyses &Preserved) const noexcept;
-
-  private:
-    std::unordered_map<const MachineBasicBlock *, MachineBlockLiveness> Blocks;
-
-    friend class LiveVariablesAnalysis;
-  };
-
-  [[nodiscard]] static constexpr std::string_view name() noexcept {
-    return "LiveVariables";
-  }
-
-  [[nodiscard]] static Expected<Result>
-  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
-};
-
-class LiveValueNumberID final {
-public:
-  constexpr LiveValueNumberID() noexcept = default;
-
-  [[nodiscard]] static constexpr LiveValueNumberID fromValue(std::uint32_t Value) noexcept {
-    return LiveValueNumberID(Value);
-  }
-
-  [[nodiscard]] constexpr bool isValid() const noexcept {
-    return Value != 0;
-  }
-
-  [[nodiscard]] constexpr std::uint32_t value() const noexcept {
-    return Value;
-  }
-
-  friend constexpr bool operator==(LiveValueNumberID, LiveValueNumberID) noexcept = default;
-  friend constexpr auto operator<=>(LiveValueNumberID, LiveValueNumberID) noexcept = default;
-
-private:
-  explicit constexpr LiveValueNumberID(std::uint32_t Value) noexcept : Value(Value) {}
-
-  std::uint32_t Value = 0;
-};
-
-enum class LiveValueState : std::uint8_t {
-  Normal,
-  Phi,
-  Unused,
-  Redefined,
-};
-
-struct LiveValueNumber final {
-  LiveValueNumberID ID;
-  SlotIndex Definition;
-  LiveValueState State = LiveValueState::Normal;
-  std::optional<MachineInstrStableID> Origin;
-
-  friend bool operator==(const LiveValueNumber &, const LiveValueNumber &) = default;
-};
-
-struct LiveSegment final {
-  SlotIndex Start;
-  SlotIndex End;
-  LiveValueNumberID Value;
-
-  [[nodiscard]] constexpr bool empty() const noexcept {
-    return !(Start < End);
-  }
-
-  [[nodiscard]] constexpr bool contains(SlotIndex Position) const noexcept {
-    return !(Position < Start) && Position < End;
-  }
-
-  [[nodiscard]] constexpr bool overlaps(const LiveSegment &Other) const noexcept {
-    return Start < Other.End && Other.Start < End;
-  }
-
-  friend constexpr bool operator==(const LiveSegment &, const LiveSegment &) noexcept = default;
-};
-
-class LiveRange final {
-public:
-  [[nodiscard]] std::span<const LiveSegment> segments() const noexcept {
-    return Segments;
-  }
-  [[nodiscard]] std::span<const LiveValueNumber> values() const noexcept {
-    return Values;
-  }
-  [[nodiscard]] bool empty() const noexcept {
-    return Segments.empty();
-  }
-
-  [[nodiscard]] const LiveSegment *segmentAt(SlotIndex Position) const noexcept;
-  [[nodiscard]] const LiveValueNumber *value(LiveValueNumberID ID) const noexcept;
-  [[nodiscard]] const LiveValueNumber *valueAt(SlotIndex Position) const noexcept;
-  [[nodiscard]] bool liveAt(SlotIndex Position) const noexcept;
-  [[nodiscard]] bool overlaps(const LiveRange &Other) const noexcept;
-
-  [[nodiscard]] Expected<LiveValueNumberID>
-  createValue(SlotIndex Definition, LiveValueState State = LiveValueState::Normal,
-              std::optional<MachineInstrStableID> Origin = std::nullopt);
-  [[nodiscard]] Expected<void> addSegment(LiveSegment Segment);
-  [[nodiscard]] Expected<void> extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End);
-  [[nodiscard]] Expected<void> remove(SlotIndex Start, SlotIndex End);
-  [[nodiscard]] Expected<void> shrinkToUses(std::span<const SlotIndex> Uses);
-  [[nodiscard]] Expected<void> verify() const;
-
-private:
-  void mergeAdjacent();
-
-  std::vector<LiveSegment> Segments;
-  std::vector<LiveValueNumber> Values;
-};
-
-struct LiveSubRange final {
-  LaneMask Lanes;
-  LiveRange Range;
-};
-
-struct LiveInterval final {
-  Register Reg;
-  LiveRange MainRange;
-  std::vector<LiveSubRange> SubRanges;
-  std::uint64_t SpillWeight = 0;
-  bool Spillable = true;
-  std::vector<PhysicalRegister> AllocationHints;
-  std::optional<Register> SplitParent;
-  std::optional<Register> Origin;
-
-  [[nodiscard]] bool overlaps(const LiveInterval &Other) const noexcept {
-    return MainRange.overlaps(Other.MainRange);
-  }
-};
-
-struct RegMaskPosition final {
-  SlotIndex Position;
-  MachineInstrStableID Instruction;
-  std::shared_ptr<const RegisterMask> Mask;
-};
-
-class LiveIntervalsAnalysis final {
-public:
-  class Result final {
-  public:
-    [[nodiscard]] const SlotIndexesAnalysis::Result &slotIndexes() const noexcept {
-      return Indexes;
-    }
-    [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept {
-      return Indexes.instructionIndex(Instruction);
-    }
-    [[nodiscard]] const LiveInterval *interval(Register Reg) const noexcept;
-    [[nodiscard]] LiveInterval *interval(Register Reg) noexcept;
-    [[nodiscard]] const LiveRange *regUnitRange(RegisterUnitID Unit) const noexcept;
-    [[nodiscard]] std::span<const RegMaskPosition> regMaskPositions() const noexcept {
-      return RegMasks;
-    }
-    [[nodiscard]] bool interferes(Register Left, Register Right) const noexcept;
-    [[nodiscard]] bool regMaskClobbers(const LiveInterval &Interval,
-                                       PhysicalRegister Candidate) const noexcept;
-    [[nodiscard]] Expected<void> shrinkToUses(Register Reg, std::span<const SlotIndex> Uses);
-
-    [[nodiscard]] bool invalidate(const MachineFunction &,
-                                  const PreservedAnalyses &Preserved) const noexcept;
-
-  private:
-    SlotIndexesAnalysis::Result Indexes;
-    std::unordered_map<Register, LiveInterval> Intervals;
-    std::unordered_map<RegisterUnitID, LiveRange> RegisterUnitRanges;
-    std::vector<RegMaskPosition> RegMasks;
-
-    friend class LiveIntervalsAnalysis;
-  };
-
-  [[nodiscard]] static constexpr std::string_view name() noexcept {
-    return "LiveIntervals";
-  }
-
-  [[nodiscard]] static Expected<Result>
-  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
-};
-
-class RebuildMachineLivenessPass final : public MachineFunctionPass {
-public:
-  [[nodiscard]] const MachinePassContract &contract() const noexcept override;
-  [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function,
-                                                const TargetDescription &Target,
-                                                MachineAnalysisManager &Analyses) override;
-};
-
-[[nodiscard]] Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function,
-                                                          const TargetDescription &Target);
-[[nodiscard]] Expected<bool> rebuildMachineLiveness(MachineFunction &Function,
-                                                    const TargetDescription &Target);
-[[nodiscard]] Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses);
-
-} // namespace rcc
-
-template <> struct std::hash<rcc::SlotIndex> {
-  [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept {
-    return std::hash<std::uint64_t>{}(Index.value());
-  }
-};
-
-template <> struct std::hash<rcc::LiveValueNumberID> {
-  [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept {
-    return std::hash<std::uint32_t>{}(ID.value());
-  }
-};
-
-#endif // RCC_CODEGEN_MACHINELIVENESS_H
diff --git a/backend/include/rcc/CodeGen/SlotIndexes.h b/backend/include/rcc/CodeGen/SlotIndexes.h
new file mode 100644
index 0000000..1767596
--- /dev/null
+++ b/backend/include/rcc/CodeGen/SlotIndexes.h
@@ -0,0 +1,130 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_CODEGEN_SLOTINDEXES_H
+#define RCC_CODEGEN_SLOTINDEXES_H
+
+#include "rcc/CodeGen/MachineIRTypes.h"
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/CodeGen/StableID.h"
+#include "rcc/Support/Error.h"
+
+#include <compare>
+#include <cstddef>
+#include <cstdint>
+#include <string_view>
+#include <unordered_map>
+#include <vector>
+
+namespace rcc {
+
+class MachineBasicBlock;
+class MachineFunction;
+class MachineInstr;
+class TargetDescription;
+
+enum class SlotIndexKind : std::uint8_t {
+  Block,
+  EarlyClobber,
+  Register,
+  Dead,
+};
+
+class SlotIndex final {
+public:
+  constexpr SlotIndex() noexcept = default;
+
+  [[nodiscard]] static constexpr SlotIndex fromValue(std::uint64_t Value) noexcept {
+    return SlotIndex(Value);
+  }
+
+  [[nodiscard]] constexpr bool isValid() const noexcept {
+    return Value != 0;
+  }
+
+  [[nodiscard]] constexpr std::uint64_t value() const noexcept {
+    return Value;
+  }
+
+  [[nodiscard]] constexpr SlotIndexKind kind() const noexcept {
+    return static_cast<SlotIndexKind>(Value & KindMask);
+  }
+
+  [[nodiscard]] constexpr SlotIndex baseIndex() const noexcept {
+    return SlotIndex(Value & ~KindMask);
+  }
+
+  [[nodiscard]] constexpr SlotIndex withKind(SlotIndexKind Kind) const noexcept {
+    return isValid() ? SlotIndex((Value & ~KindMask) | static_cast<std::uint64_t>(Kind))
+                     : SlotIndex{};
+  }
+
+  [[nodiscard]] constexpr SlotIndex earlyClobberSlot() const noexcept {
+    return withKind(SlotIndexKind::EarlyClobber);
+  }
+
+  [[nodiscard]] constexpr SlotIndex registerSlot() const noexcept {
+    return withKind(SlotIndexKind::Register);
+  }
+
+  [[nodiscard]] constexpr SlotIndex deadSlot() const noexcept {
+    return withKind(SlotIndexKind::Dead);
+  }
+
+  friend constexpr bool operator==(SlotIndex, SlotIndex) noexcept = default;
+  friend constexpr auto operator<=>(SlotIndex, SlotIndex) noexcept = default;
+
+private:
+  static constexpr std::uint64_t KindMask = 3;
+
+  explicit constexpr SlotIndex(std::uint64_t Value) noexcept : Value(Value) {}
+
+  std::uint64_t Value = 0;
+};
+
+class SlotIndexesAnalysis final {
+public:
+  class Result final {
+  public:
+    [[nodiscard]] SlotIndex instructionIndex(const MachineInstr &Instruction) const noexcept;
+    [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept {
+      return instructionIndex(Instruction);
+    }
+    [[nodiscard]] SlotIndex blockStart(const MachineBasicBlock &Block) const noexcept;
+    [[nodiscard]] SlotIndex blockEnd(const MachineBasicBlock &Block) const noexcept;
+    [[nodiscard]] const MachineInstr *instructionFromIndex(SlotIndex Index) const noexcept;
+    [[nodiscard]] const MachineBasicBlock *blockFromIndex(SlotIndex Index) const noexcept;
+
+    [[nodiscard]] Expected<void> insertInstruction(const MachineInstr &Instruction);
+    [[nodiscard]] Expected<void> eraseInstruction(const MachineInstr &Instruction);
+    [[nodiscard]] Expected<void> renumber(MachineFunction &Function);
+
+    [[nodiscard]] bool invalidate(const MachineFunction &,
+                                  const PreservedAnalyses &Preserved) const noexcept;
+
+  private:
+    std::unordered_map<MachineInstrStableID, SlotIndex> InstructionSlots;
+    std::unordered_map<std::uint64_t, const MachineInstr *> SlotToInstruction;
+    std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockStarts;
+    std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockEnds;
+    std::vector<const MachineBasicBlock *> BlocksByStart;
+
+    friend class SlotIndexesAnalysis;
+  };
+
+  [[nodiscard]] static constexpr std::string_view name() noexcept {
+    return "SlotIndexes";
+  }
+
+  [[nodiscard]] static Expected<Result>
+  run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses);
+};
+
+} // namespace rcc
+
+template <> struct std::hash<rcc::SlotIndex> {
+  [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept {
+    return std::hash<std::uint64_t>{}(Index.value());
+  }
+};
+
+#endif // RCC_CODEGEN_SLOTINDEXES_H
diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
index 4448933..3fd0e55 100644
--- a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
+++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h
@@ -3,8 +3,8 @@
 #ifndef RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H
 #define RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H
 
+#include "rcc/CodeGen/LiveInterval.h"
 #include "rcc/CodeGen/MachineFrameInfo.h"
-#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/TargetRegisterInfo.h"
 
 #include <cstdint>