[CodeGen] Implement machine liveness analysis

15 files changed, 3294 insertions, 53 deletions

diff --git a/backend/include/rcc/CodeGen/MachineBasicBlock.h b/backend/include/rcc/CodeGen/MachineBasicBlock.h
index d82477a..da538db 100644
--- a/backend/include/rcc/CodeGen/MachineBasicBlock.h
+++ b/backend/include/rcc/CodeGen/MachineBasicBlock.h
@@ -113,6 +113,9 @@ public:
   [[nodiscard]] Expected<void> addLiveIn(PhysicalRegister PhysReg,
                                          LaneMask Lanes = LaneMask::all());
   [[nodiscard]] Expected<void> removeLiveIn(PhysicalRegister PhysReg);
+  void clearLiveIns() noexcept {
+    LiveIns.clear();
+  }
   [[nodiscard]] std::span<const MachineBasicBlockLiveIn> liveIns() const noexcept {
     return LiveIns;
   }
diff --git a/backend/include/rcc/CodeGen/MachineLiveness.h b/backend/include/rcc/CodeGen/MachineLiveness.h
new file mode 100644
index 0000000..678f309
--- /dev/null
+++ b/backend/include/rcc/CodeGen/MachineLiveness.h
@@ -0,0 +1,410 @@
+// 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/MachinePass.h b/backend/include/rcc/CodeGen/MachinePass.h
index 66e3b6b..1637954 100644
--- a/backend/include/rcc/CodeGen/MachinePass.h
+++ b/backend/include/rcc/CodeGen/MachinePass.h
@@ -319,6 +319,7 @@ private:
   friend class MachinePassManager;
   friend class CompilationUnitPassManager;
   friend Expected<void> registerStage8MachineAnalyses(MachineAnalysisManager &Analyses);
+  friend Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses);
 };
 
 class CompilationUnitAnalysisManager final {
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt
index 5cff572..4c2887c 100644
--- a/backend/lib/CodeGen/CMakeLists.txt
+++ b/backend/lib/CodeGen/CMakeLists.txt
@@ -23,6 +23,7 @@ set(
   MachineAnalyses.cpp
   MachineInstr.cpp
   MachineJumpTableInfo.cpp
+  MachineLiveness.cpp
   MachineMemOperand.cpp
   MachineMetadata.cpp
   MachineOperand.cpp
@@ -65,6 +66,7 @@ set(
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineAnalyses.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineJumpTableInfo.h"
+  "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLiveness.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMetadata.h"
   "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineOperand.h"
@@ -137,6 +139,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalyses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
@@ -179,6 +182,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalyses.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperand.cpp"
diff --git a/backend/lib/CodeGen/MachineLiveness.cpp b/backend/lib/CodeGen/MachineLiveness.cpp
new file mode 100644
index 0000000..b3d88cd
--- /dev/null
+++ b/backend/lib/CodeGen/MachineLiveness.cpp
@@ -0,0 +1,1863 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineLiveness.h"
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+
+#include <algorithm>
+#include <array>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+constexpr std::uint64_t SlotSpacing = 16;
+constexpr std::uint64_t SlotAlignmentMask = 3;
+
+[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept {
+  return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue());
+}
+
+template <typename KeyT>
+void addLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) {
+  if (Lanes.empty())
+    return;
+  const auto Position = Values.find(Key);
+  if (Position == Values.end()) {
+    Values.emplace(Key, Lanes);
+    return;
+  }
+  Position->second = Position->second | Lanes;
+}
+
+template <typename KeyT>
+void removeLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) {
+  const auto Position = Values.find(Key);
+  if (Position == Values.end() || Lanes.empty())
+    return;
+  Position->second = subtractLanes(Position->second, Lanes);
+  if (Position->second.empty())
+    Values.erase(Position);
+}
+
+template <typename KeyT>
+[[nodiscard]] LaneMask lanesFor(const std::unordered_map<KeyT, LaneMask> &Values,
+                                KeyT Key) noexcept {
+  const auto Position = Values.find(Key);
+  return Position == Values.end() ? LaneMask{} : Position->second;
+}
+
+template <typename KeyT>
+[[nodiscard]] bool containsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key,
+                                 LaneMask Lanes) noexcept {
+  const LaneMask Present = lanesFor(Values, Key);
+  return !Present.empty() && Present.contains(Lanes);
+}
+
+template <typename KeyT>
+[[nodiscard]] bool intersectsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key,
+                                   LaneMask Lanes) noexcept {
+  return lanesFor(Values, Key).intersects(Lanes);
+}
+
+template <typename KeyT>
+void uniteLanes(std::unordered_map<KeyT, LaneMask> &Values,
+                const std::unordered_map<KeyT, LaneMask> &Other) {
+  for (const auto &[Key, Lanes] : Other)
+    addLanes(Values, Key, Lanes);
+}
+
+template <typename KeyT>
+void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values,
+                      const std::unordered_map<KeyT, LaneMask> &Other) {
+  for (const auto &[Key, Lanes] : Other)
+    removeLanes(Values, Key, Lanes);
+}
+
+struct PhysicalUnitAccess final {
+  RegisterUnitID Unit;
+  LaneMask Lanes;
+};
+
+[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept {
+  std::uint64_t View = UnitViewLanes.rawValue();
+  const std::uint64_t Selected = View & RegisterLanes.rawValue();
+  std::uint64_t Normalized = 0;
+  std::uint32_t UnitLane = 0;
+  while (View != 0) {
+    const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View);
+    if ((Selected & RegisterLane) != 0)
+      Normalized |= std::uint64_t{1} << UnitLane;
+    View &= View - 1U;
+    ++UnitLane;
+  }
+  return LaneMask::fromRaw(Normalized);
+}
+
+[[nodiscard]] LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept {
+  std::uint64_t View = UnitViewLanes.rawValue();
+  const std::uint64_t Selected = UnitLanes.rawValue();
+  std::uint64_t RegisterLanes = 0;
+  std::uint32_t UnitLane = 0;
+  while (View != 0) {
+    const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View);
+    if ((Selected & (std::uint64_t{1} << UnitLane)) != 0)
+      RegisterLanes |= RegisterLane;
+    View &= View - 1U;
+    ++UnitLane;
+  }
+  return LaneMask::fromRaw(RegisterLanes);
+}
+
+[[nodiscard]] LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept {
+  LaneMask Result;
+  for (const RegisterUnitLane &Unit : Description.Units)
+    Result = Result | Unit.Lanes;
+  return Result;
+}
+
+[[nodiscard]] RegisterUnitLaneSet physicalRegisterCoverage(const PhysicalRegisterDesc &Description,
+                                                           LaneMask Requested) {
+  RegisterUnitLaneSet Result;
+  for (const RegisterUnitLane &Unit : Description.Units)
+    Result.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes, Requested));
+  return Result;
+}
+
+[[nodiscard]] bool isSubset(const RegisterUnitLaneSet &Subset,
+                            const RegisterUnitLaneSet &Superset) noexcept {
+  return std::ranges::all_of(Subset.entries(), [&Superset](const auto &Entry) {
+    return Superset.contains(Entry.first, Entry.second);
+  });
+}
+
+[[nodiscard]] std::size_t laneCount(const RegisterUnitLaneSet &Set) noexcept {
+  std::size_t Result = 0;
+  for (const auto &[Unit, Lanes] : Set.entries()) {
+    (void)Unit;
+    Result += static_cast<std::size_t>(std::popcount(Lanes.rawValue()));
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function,
+                                                      const TargetDescription &Target) {
+  if (!Reg.isVirtual()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "virtual lane query requires a virtual register");
+  }
+  auto Info = Function.registerInfo().virtualRegisterInfo(Reg);
+  if (!Info)
+    return std::unexpected(Info.error());
+  const std::optional<RegisterClassID> ClassID = Info->get().RegClass;
+  if (!ClassID)
+    return LaneMask::all();
+  const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID);
+  if (Class == nullptr || Class->Lanes.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "liveness encountered an unknown or empty register class");
+  }
+  return Class->Lanes;
+}
+
+[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand,
+                                                     const MachineFunction &Function,
+                                                     const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || !Reg->isVirtual()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "virtual lane query requires a virtual-register operand");
+  }
+  if (Operand.subReg().value() != 0) {
+    const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg());
+    if (SubReg == nullptr || SubReg->Lanes.empty()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "liveness encountered an unknown or empty subregister lane mask");
+    }
+    return SubReg->Lanes;
+  }
+
+  return virtualRegisterLanes(*Reg, Function, Target);
+}
+
+[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>>
+physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  const std::optional<PhysicalRegister> Original =
+      Reg == nullptr ? std::nullopt : Reg->physicalRegister();
+  if (!Original) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "physical unit query requires a physical-register operand");
+  }
+
+  PhysicalRegister Effective = *Original;
+  if (Operand.subReg().value() != 0) {
+    const std::optional<PhysicalRegister> SubRegister =
+        Target.registers().subRegister(*Original, Operand.subReg());
+    if (!SubRegister) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical register has no requested subregister projection");
+    }
+    Effective = *SubRegister;
+  }
+  const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Effective);
+  if (Description == nullptr || Description->Units.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "liveness encountered an unknown or unitless physical register");
+  }
+
+  std::vector<PhysicalUnitAccess> Result;
+  Result.reserve(Description->Units.size());
+  for (const RegisterUnitLane &Unit : Description->Units) {
+    if (Unit.Lanes.empty()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical register unit has an empty lane mask");
+    }
+    Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes, LaneMask::all())});
+  }
+  return Result;
+}
+
+void addPhysicalRegister(RegisterUnitLaneSet &Set, const PhysicalRegisterDesc &Description,
+                         LaneMask Requested = LaneMask::all()) {
+  Set.unite(physicalRegisterCoverage(Description, Requested));
+}
+
+[[nodiscard]] Expected<void> addRegisterMaskDefs(RegisterUnitLaneSet &Set, const RegisterMask &Mask,
+                                                 const TargetDescription &Target) {
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    if (Mask.clobbers(Description.Reg))
+      addPhysicalRegister(Set, Description);
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> addRegisterMaskUses(RegisterUnitLaneSet &Set, const RegisterMask &Mask,
+                                                 const TargetDescription &Target) {
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    if (Mask.preserves(Description.Reg))
+      addPhysicalRegister(Set, Description);
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses,
+                                           RegisterUnitLaneSet &PhysicalUses,
+                                           const MachineOperand &Operand,
+                                           const MachineFunction &Function,
+                                           const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister() || Operand.isDebugUse() ||
+      Operand.registerFlags().has(RegisterOperandFlag::Undef)) {
+    return {};
+  }
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    VirtualUses.add(*Reg, *Lanes);
+    return {};
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    PhysicalUses.add(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs,
+                                           RegisterUnitLaneSet &PhysicalDefs,
+                                           const MachineOperand &Operand,
+                                           const MachineFunction &Function,
+                                           const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return {};
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    VirtualDefs.add(*Reg, *Lanes);
+    return {};
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    PhysicalDefs.add(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+struct LivenessEdgeKey final {
+  const MachineBasicBlock *Predecessor = nullptr;
+  const MachineBasicBlock *Successor = nullptr;
+
+  friend bool operator==(const LivenessEdgeKey &, const LivenessEdgeKey &) = default;
+};
+
+struct LivenessEdgeKeyHash final {
+  [[nodiscard]] std::size_t operator()(const LivenessEdgeKey &Key) const noexcept {
+    const std::size_t Left = std::hash<const MachineBasicBlock *>{}(Key.Predecessor);
+    const std::size_t Right = std::hash<const MachineBasicBlock *>{}(Key.Successor);
+    return Left ^ (Right + 0x9e3779b9U + (Left << 6U) + (Left >> 2U));
+  }
+};
+
+struct EdgeLivenessUses final {
+  RegisterLaneSet Virtual;
+  RegisterUnitLaneSet Physical;
+};
+
+[[nodiscard]] Expected<LiveVariablesAnalysis::Result>
+computeLiveVariables(const MachineFunction &Function, const TargetDescription &Target) {
+  LiveVariablesAnalysis::Result Result;
+  std::vector<const MachineBasicBlock *> Blocks;
+  std::unordered_map<LivenessEdgeKey, EdgeLivenessUses, LivenessEdgeKeyHash> EdgeUses;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    Blocks.push_back(Block);
+    (void)Result.getOrCreateBlock(*Block);
+  }
+
+  for (const MachineBasicBlock *Block : Blocks) {
+    MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block);
+    if (Block == Function.firstBlock()) {
+      for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) {
+        const PhysicalRegisterDesc *Description =
+            Target.registers().physicalRegister(LiveIn.PhysReg);
+        if (Description == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "function live-in references an unknown physical register");
+        }
+        addPhysicalRegister(Liveness.PhysicalUses, *Description);
+        if (LiveIn.InitialVirtualRegister) {
+          auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target);
+          if (!Lanes)
+            return std::unexpected(Lanes.error());
+          Liveness.VirtualDefs.add(*LiveIn.InitialVirtualRegister, *Lanes);
+        }
+      }
+    }
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness encountered an unknown instruction descriptor");
+      }
+      const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi);
+      if (IsPhi) {
+        if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness encountered a malformed PHI instruction");
+        }
+        std::unordered_set<const MachineBasicBlock *> IncomingBlocks;
+        for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) {
+          const MachineOperand *Incoming = Instruction->operandAt(Index);
+          const MachineOperand *PredecessorOperand = Instruction->operandAt(Index + 1U);
+          const auto *Predecessor = PredecessorOperand == nullptr
+                                        ? nullptr
+                                        : PredecessorOperand->getIf<BasicBlockOperand>();
+          if (Incoming == nullptr || Predecessor == nullptr || Predecessor->Block == nullptr) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a malformed PHI incoming pair");
+          }
+          const MachineBasicBlock *IncomingBlock = Predecessor->Block;
+          const bool HasPredecessor = std::ranges::find(Block->predecessors(), IncomingBlock) !=
+                                      Block->predecessors().end();
+          const bool HasSuccessor = std::ranges::any_of(
+              IncomingBlock->successors(),
+              [Block](const MachineSuccessor &Successor) { return Successor.Block == Block; });
+          if (&IncomingBlock->function() != &Function || !IncomingBlock->isLinked() ||
+              !HasPredecessor || !HasSuccessor || !IncomingBlocks.insert(IncomingBlock).second) {
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a PHI incoming without a unique CFG edge");
+          }
+          EdgeLivenessUses &Uses = EdgeUses[{IncomingBlock, Block}];
+          auto Added = addOperandUse(Uses.Virtual, Uses.Physical, *Incoming, Function, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+
+      RegisterLaneSet InstructionVirtualUses;
+      RegisterLaneSet InstructionVirtualDefs;
+      RegisterUnitLaneSet InstructionPhysicalUses;
+      RegisterUnitLaneSet InstructionPhysicalDefs;
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand &Operand = *Instruction->operandAt(Index);
+        if (Operand.isRegister()) {
+          if (Operand.isUse() && (!IsPhi || Index == 0)) {
+            auto Use = addOperandUse(InstructionVirtualUses, InstructionPhysicalUses, Operand,
+                                     Function, Target);
+            if (!Use)
+              return std::unexpected(Use.error());
+          }
+          if (Operand.isDef()) {
+            auto Def = addOperandDef(InstructionVirtualDefs, InstructionPhysicalDefs, Operand,
+                                     Function, Target);
+            if (!Def)
+              return std::unexpected(Def.error());
+          }
+          continue;
+        }
+        if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+            MaskOperand != nullptr) {
+          if (!MaskOperand->Mask)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a null register mask");
+          auto Added = addRegisterMaskDefs(InstructionPhysicalDefs, *MaskOperand->Mask, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+          continue;
+        }
+        if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+            MaskOperand != nullptr) {
+          if (!MaskOperand->Mask)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "liveness encountered a null live-out register mask");
+          auto Added = addRegisterMaskUses(InstructionPhysicalUses, *MaskOperand->Mask, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+
+      RegisterLaneSet NewVirtualUses = InstructionVirtualUses;
+      NewVirtualUses.subtract(Liveness.VirtualDefs);
+      Liveness.VirtualUses.unite(NewVirtualUses);
+      Liveness.VirtualDefs.unite(InstructionVirtualDefs);
+
+      RegisterUnitLaneSet NewPhysicalUses = InstructionPhysicalUses;
+      NewPhysicalUses.subtract(Liveness.PhysicalDefs);
+      Liveness.PhysicalUses.unite(NewPhysicalUses);
+      Liveness.PhysicalDefs.unite(InstructionPhysicalDefs);
+    }
+  }
+
+  bool Changed = true;
+  while (Changed) {
+    Changed = false;
+    for (const MachineBasicBlock *Block : Blocks | std::views::reverse) {
+      MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block);
+      RegisterLaneSet VirtualOut;
+      RegisterUnitLaneSet PhysicalOut;
+      for (const MachineSuccessor &Successor : Block->successors()) {
+        if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness encountered an invalid CFG successor");
+        }
+        const MachineBlockLiveness &SuccessorLiveness = *Result.block(*Successor.Block);
+        VirtualOut.unite(SuccessorLiveness.VirtualLiveIn);
+        PhysicalOut.unite(SuccessorLiveness.PhysicalLiveIn);
+        const auto Edge = EdgeUses.find({Block, Successor.Block});
+        if (Edge != EdgeUses.end()) {
+          VirtualOut.unite(Edge->second.Virtual);
+          PhysicalOut.unite(Edge->second.Physical);
+        }
+      }
+
+      RegisterLaneSet VirtualIn = VirtualOut;
+      VirtualIn.subtract(Liveness.VirtualDefs);
+      VirtualIn.unite(Liveness.VirtualUses);
+      RegisterUnitLaneSet PhysicalIn = PhysicalOut;
+      PhysicalIn.subtract(Liveness.PhysicalDefs);
+      PhysicalIn.unite(Liveness.PhysicalUses);
+
+      if (VirtualOut != Liveness.VirtualLiveOut || VirtualIn != Liveness.VirtualLiveIn ||
+          PhysicalOut != Liveness.PhysicalLiveOut || PhysicalIn != Liveness.PhysicalLiveIn) {
+        Liveness.VirtualLiveOut = std::move(VirtualOut);
+        Liveness.VirtualLiveIn = std::move(VirtualIn);
+        Liveness.PhysicalLiveOut = std::move(PhysicalOut);
+        Liveness.PhysicalLiveIn = std::move(PhysicalIn);
+        Changed = true;
+      }
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional<LaneMask> Filter) noexcept {
+  return !Filter || Access.intersects(*Filter);
+}
+
+struct InstructionRangeEvent final {
+  bool HasUse = false;
+  bool HasNormalDef = false;
+  bool HasEarlyDef = false;
+  bool HasRegMaskClobber = false;
+};
+
+[[nodiscard]] Expected<InstructionRangeEvent>
+virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional<LaneMask> Filter,
+                  const MachineFunction &Function, const TargetDescription &Target) {
+  InstructionRangeEvent Event;
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    const Register *OperandReg = Operand.getIf<Register>();
+    if (OperandReg == nullptr || *OperandReg != Reg)
+      continue;
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    if (!maskIntersects(*Lanes, Filter))
+      continue;
+    Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() &&
+                    !Operand.registerFlags().has(RegisterOperandFlag::Undef);
+    if (Operand.isDef()) {
+      if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber))
+        Event.HasEarlyDef = true;
+      else
+        Event.HasNormalDef = true;
+    }
+  }
+  return Event;
+}
+
+[[nodiscard]] Expected<InstructionRangeEvent> unitRangeEvent(const MachineInstr &Instruction,
+                                                             RegisterUnitID Unit,
+                                                             std::optional<LaneMask> Filter,
+                                                             const TargetDescription &Target) {
+  InstructionRangeEvent Event;
+  for (const MachineOperand &Operand : Instruction.operands()) {
+    if (Operand.isRegister()) {
+      const Register *Reg = Operand.getIf<Register>();
+      if (Reg == nullptr || !Reg->isPhysical())
+        continue;
+      auto Units = physicalOperandUnits(Operand, Target);
+      if (!Units)
+        return std::unexpected(Units.error());
+      const auto Position = std::ranges::find_if(
+          *Units, [Unit](const PhysicalUnitAccess &Access) { return Access.Unit == Unit; });
+      if (Position == Units->end() || !maskIntersects(Position->Lanes, Filter))
+        continue;
+      Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() &&
+                      !Operand.registerFlags().has(RegisterOperandFlag::Undef);
+      if (Operand.isDef()) {
+        if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber))
+          Event.HasEarlyDef = true;
+        else
+          Event.HasNormalDef = true;
+      }
+      continue;
+    }
+    if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+        MaskOperand != nullptr && MaskOperand->Mask) {
+      for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+        if (!MaskOperand->Mask->clobbers(Description.Reg))
+          continue;
+        if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) {
+              return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter);
+            })) {
+          Event.HasRegMaskClobber = true;
+          break;
+        }
+      }
+      continue;
+    }
+    if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+        MaskOperand != nullptr && MaskOperand->Mask) {
+      for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+        if (!MaskOperand->Mask->preserves(Description.Reg))
+          continue;
+        if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) {
+              return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter);
+            })) {
+          Event.HasUse = true;
+          break;
+        }
+      }
+    }
+  }
+  return Event;
+}
+
+template <typename EventFn, typename LiveOutFn>
+[[nodiscard]] Expected<LiveRange>
+buildLiveRange(MachineFunction &Function, const SlotIndexesAnalysis::Result &Indexes,
+               const EventFn &EventForInstruction, const LiveOutFn &IsLiveOut) {
+  LiveRange Range;
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    std::optional<SlotIndex> End;
+    bool SawLaterDefinition = false;
+    if (IsLiveOut(*Block))
+      End = Indexes.blockEnd(*Block);
+
+    for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr;
+         Instruction = Instruction->previous()) {
+      auto Event = EventForInstruction(*Instruction);
+      if (!Event)
+        return std::unexpected(Event.error());
+      if (!Event->HasUse && !Event->HasNormalDef && !Event->HasEarlyDef &&
+          !Event->HasRegMaskClobber) {
+        continue;
+      }
+
+      const SlotIndex InstructionSlot = Indexes.instructionIndex(*Instruction);
+      if (!InstructionSlot.isValid()) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "live-range construction has no instruction SlotIndex");
+      }
+      auto AddDefinition = [&](SlotIndex DefSlot, bool IsRegMask) -> Expected<void> {
+        const bool HasLiveValue = End && DefSlot < *End;
+        if (IsRegMask && !HasLiveValue) {
+          End.reset();
+          SawLaterDefinition = true;
+          return {};
+        }
+        const LiveValueState State = IsRegMask            ? LiveValueState::Redefined
+                                     : HasLiveValue       ? LiveValueState::Normal
+                                     : SawLaterDefinition ? LiveValueState::Redefined
+                                                          : LiveValueState::Unused;
+        auto Value = Range.createValue(DefSlot, State, Instruction->stableID());
+        if (!Value)
+          return std::unexpected(Value.error());
+        const SlotIndex SegmentEnd = HasLiveValue ? *End : InstructionSlot.deadSlot();
+        if (DefSlot < SegmentEnd) {
+          auto Added = Range.addSegment({DefSlot, SegmentEnd, *Value});
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+        End.reset();
+        SawLaterDefinition = true;
+        return {};
+      };
+
+      if (Event->HasNormalDef) {
+        auto Added = AddDefinition(InstructionSlot.registerSlot(), false);
+        if (!Added)
+          return std::unexpected(Added.error());
+      }
+      if (Event->HasUse) {
+        const SlotIndex UseEnd =
+            Event->HasNormalDef ? InstructionSlot.registerSlot() : InstructionSlot.deadSlot();
+        if (!End || *End < UseEnd)
+          End = UseEnd;
+      }
+      if (Event->HasEarlyDef) {
+        auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), false);
+        if (!Added)
+          return std::unexpected(Added.error());
+      } else if (Event->HasRegMaskClobber) {
+        auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), true);
+        if (!Added)
+          return std::unexpected(Added.error());
+      }
+    }
+
+    if (End) {
+      const SlotIndex Start = Indexes.blockStart(*Block);
+      if (!Start.isValid() || !(*End > Start)) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "live-in range has invalid block boundary indexes");
+      }
+      auto Value = Range.createValue(Start, LiveValueState::Phi);
+      if (!Value)
+        return std::unexpected(Value.error());
+      auto Added = Range.addSegment({Start, *End, *Value});
+      if (!Added)
+        return std::unexpected(Added.error());
+    }
+  }
+  auto Verification = Range.verify();
+  if (!Verification)
+    return std::unexpected(Verification.error());
+  return Range;
+}
+
+[[nodiscard]] Expected<LaneMask> virtualRegisterFullLanes(Register Reg,
+                                                          const MachineFunction &Function,
+                                                          const TargetDescription &Target) {
+  return virtualRegisterLanes(Reg, Function, Target);
+}
+
+[[nodiscard]] Expected<std::vector<LaneMask>>
+partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function,
+                              const TargetDescription &Target) {
+  auto Full = virtualRegisterFullLanes(Reg, Function, Target);
+  if (!Full)
+    return std::unexpected(Full.error());
+  std::vector<LaneMask> AccessMasks;
+  for (const MachineOperand &Operand : Function.registerInfo().regNoDebugOperands(Reg)) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    if (*Lanes != *Full && std::ranges::find(AccessMasks, *Lanes) == AccessMasks.end())
+      AccessMasks.push_back(*Lanes);
+  }
+  if (AccessMasks.empty())
+    return {};
+
+  std::vector<LaneMask> Groups{*Full};
+  for (const LaneMask Access : AccessMasks) {
+    std::vector<LaneMask> Refined;
+    for (const LaneMask Group : Groups) {
+      const LaneMask Intersection = Group & Access;
+      const LaneMask Difference = subtractLanes(Group, Access);
+      if (!Intersection.empty())
+        Refined.push_back(Intersection);
+      if (!Difference.empty())
+        Refined.push_back(Difference);
+    }
+    Groups = std::move(Refined);
+  }
+  std::ranges::sort(
+      Groups, [](LaneMask Left, LaneMask Right) { return Left.rawValue() < Right.rawValue(); });
+  return Groups;
+}
+
+[[nodiscard]] Expected<std::vector<MachineBasicBlockLiveIn>>
+canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescription &Target) {
+  struct Candidate final {
+    const PhysicalRegisterDesc *Description = nullptr;
+    LaneMask RegisterLanes;
+    RegisterUnitLaneSet Coverage;
+    std::size_t ExtraLanes = 0;
+    bool Selected = false;
+  };
+
+  std::vector<Candidate> Candidates;
+  for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) {
+    const LaneMask FullLanes = physicalRegisterLanes(Description);
+    std::uint64_t SelectableLanes = 0;
+    LaneMask RelevantLanes;
+    for (const RegisterUnitLane &Unit : Description.Units) {
+      RelevantLanes = RelevantLanes | denormalizeUnitLanes(Units.lanes(Unit.Unit), Unit.Lanes);
+    }
+    std::uint64_t PendingLanes = RelevantLanes.rawValue();
+    while (PendingLanes != 0) {
+      const std::uint64_t Lane = std::uint64_t{1} << std::countr_zero(PendingLanes);
+      const RegisterUnitLaneSet Coverage =
+          physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane));
+      if (isSubset(Coverage, Units))
+        SelectableLanes |= Lane;
+      PendingLanes &= PendingLanes - 1U;
+    }
+    if (SelectableLanes == 0)
+      continue;
+    Candidate Value;
+    Value.Description = &Description;
+    Value.RegisterLanes = LaneMask::fromRaw(SelectableLanes);
+    Value.Coverage = physicalRegisterCoverage(Description, Value.RegisterLanes);
+    Value.ExtraLanes = static_cast<std::size_t>(std::popcount(FullLanes.rawValue()) -
+                                                std::popcount(SelectableLanes));
+    Candidates.push_back(std::move(Value));
+  }
+
+  RegisterUnitLaneSet Covered;
+  std::vector<MachineBasicBlockLiveIn> Result;
+  while (Covered != Units) {
+    Candidate *Best = nullptr;
+    std::size_t BestNewLanes = 0;
+    std::size_t BestCoverage = 0;
+    for (Candidate &Value : Candidates) {
+      if (Value.Selected)
+        continue;
+      RegisterUnitLaneSet NewCoverage = Value.Coverage;
+      NewCoverage.subtract(Covered);
+      const std::size_t NewLanes = laneCount(NewCoverage);
+      if (NewLanes == 0)
+        continue;
+      const std::size_t Coverage = laneCount(Value.Coverage);
+      if (Best == nullptr || NewLanes > BestNewLanes ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes < Best->ExtraLanes) ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes &&
+           Coverage > BestCoverage) ||
+          (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes &&
+           Coverage == BestCoverage &&
+           Value.Description->Reg.number() < Best->Description->Reg.number())) {
+        Best = &Value;
+        BestNewLanes = NewLanes;
+        BestCoverage = Coverage;
+      }
+    }
+    if (Best == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "physical live-in units cannot be represented by target registers");
+    }
+    Best->Selected = true;
+    Covered.unite(Best->Coverage);
+    const LaneMask FullLanes = physicalRegisterLanes(*Best->Description);
+    const LaneMask Lanes = Best->RegisterLanes == FullLanes ? LaneMask::all() : Best->RegisterLanes;
+    Result.push_back({Best->Description->Reg, Lanes});
+  }
+  std::ranges::sort(Result,
+                    [](const MachineBasicBlockLiveIn &Left, const MachineBasicBlockLiveIn &Right) {
+                      return Left.PhysReg.number() < Right.PhysReg.number();
+                    });
+  return Result;
+}
+
+[[nodiscard]] Expected<RegisterUnitLaneSet>
+liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns, const TargetDescription &Target) {
+  RegisterUnitLaneSet Result;
+  for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) {
+    const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg);
+    if (Description == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "block live-in references an unknown physical register");
+    }
+    Result.unite(physicalRegisterCoverage(*Description, LiveIn.Lanes));
+  }
+  return Result;
+}
+
+struct OperandFlagPlan final {
+  MachineInstrStableID Instruction;
+  std::size_t OperandIndex = 0;
+  RegisterOperandFlags Original;
+  RegisterOperandFlags Rebuilt;
+  bool KillIsValid = false;
+  bool DeadIsValid = false;
+};
+
+struct BlockLivenessPlan final {
+  MachineBlockStableID Block;
+  std::vector<MachineBasicBlockLiveIn> OriginalLiveIns;
+  std::vector<MachineBasicBlockLiveIn> RebuiltLiveIns;
+};
+
+struct LivenessRebuildPlan final {
+  std::vector<BlockLivenessPlan> Blocks;
+  std::vector<OperandFlagPlan> Operands;
+};
+
+[[nodiscard]] Expected<bool> liveSetIntersects(const MachineOperand &Operand,
+                                               const RegisterLaneSet &Virtual,
+                                               const RegisterUnitLaneSet &Physical,
+                                               const MachineFunction &Function,
+                                               const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return false;
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    return Virtual.intersects(*Reg, *Lanes);
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  return std::ranges::any_of(*Units, [&Physical](const PhysicalUnitAccess &Unit) {
+    return Physical.intersects(Unit.Unit, Unit.Lanes);
+  });
+}
+
+[[nodiscard]] Expected<void> removeOperandFromLiveSet(const MachineOperand &Operand,
+                                                      RegisterLaneSet &Virtual,
+                                                      RegisterUnitLaneSet &Physical,
+                                                      const MachineFunction &Function,
+                                                      const TargetDescription &Target) {
+  const Register *Reg = Operand.getIf<Register>();
+  if (Reg == nullptr || Reg->isNoRegister())
+    return {};
+  if (Reg->isVirtual()) {
+    auto Lanes = virtualOperandLanes(Operand, Function, Target);
+    if (!Lanes)
+      return std::unexpected(Lanes.error());
+    Virtual.remove(*Reg, *Lanes);
+    return {};
+  }
+  auto Units = physicalOperandUnits(Operand, Target);
+  if (!Units)
+    return std::unexpected(Units.error());
+  for (const PhysicalUnitAccess &Unit : *Units)
+    Physical.remove(Unit.Unit, Unit.Lanes);
+  return {};
+}
+
+[[nodiscard]] Expected<void> addOperandToLiveSet(const MachineOperand &Operand,
+                                                 RegisterLaneSet &Virtual,
+                                                 RegisterUnitLaneSet &Physical,
+                                                 const MachineFunction &Function,
+                                                 const TargetDescription &Target) {
+  return addOperandUse(Virtual, Physical, Operand, Function, Target);
+}
+
+[[nodiscard]] Expected<LivenessRebuildPlan>
+buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescription &Target) {
+  auto Variables = computeLiveVariables(Function, Target);
+  if (!Variables)
+    return std::unexpected(Variables.error());
+
+  LivenessRebuildPlan Plan;
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    const MachineBlockLiveness *BlockVariables = Variables->block(*Block);
+    if (BlockVariables == nullptr)
+      return makeUnexpected(ErrorCode::InternalError, "liveness result omitted a machine block");
+    auto NewLiveIns = canonicalPhysicalLiveIns(BlockVariables->PhysicalLiveIn, Target);
+    if (!NewLiveIns)
+      return std::unexpected(NewLiveIns.error());
+    Plan.Blocks.push_back(
+        {Block->stableID(),
+         std::vector<MachineBasicBlockLiveIn>(Block->liveIns().begin(), Block->liveIns().end()),
+         std::move(*NewLiveIns)});
+
+    RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut;
+    RegisterUnitLaneSet Physical = BlockVariables->PhysicalLiveOut;
+    for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr;
+         Instruction = Instruction->previous()) {
+      const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+      if (Descriptor == nullptr) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "liveness rebuild encountered an unknown instruction descriptor");
+      }
+      const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi);
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>();
+        if (MaskOperand == nullptr)
+          continue;
+        if (!MaskOperand->Mask)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered a null live-out register mask");
+        auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target);
+        if (!Added)
+          return std::unexpected(Added.error());
+      }
+
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        if (Operand == nullptr || !Operand->isRegister() || !Operand->isDef())
+          continue;
+        auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target);
+        if (!IsLive)
+          return std::unexpected(IsLive.error());
+        RegisterOperandFlags Flags = Operand->registerFlags();
+        Flags.clear(RegisterOperandFlag::Dead);
+        if (!*IsLive)
+          Flags.set(RegisterOperandFlag::Dead);
+        Plan.Operands.push_back(
+            {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, !*IsLive});
+      }
+
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        if (Operand.isRegister() && Operand.isDef()) {
+          auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target);
+          if (!Removed)
+            return std::unexpected(Removed.error());
+          continue;
+        }
+        const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+        if (MaskOperand == nullptr)
+          continue;
+        if (!MaskOperand->Mask)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered a null register mask");
+        RegisterUnitLaneSet Clobbers;
+        auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target);
+        if (!Added)
+          return std::unexpected(Added.error());
+        Physical.subtract(Clobbers);
+      }
+
+      for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
+        const MachineOperand *Operand = Instruction->operandAt(Index);
+        if (Operand == nullptr || !Operand->isRegister() || !Operand->isUse())
+          continue;
+        if (IsPhi) {
+          RegisterOperandFlags Flags = Operand->registerFlags();
+          Flags.clear(RegisterOperandFlag::Kill);
+          const auto Existing = std::ranges::find_if(
+              Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) {
+                return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index;
+              });
+          if (Existing == Plan.Operands.end()) {
+            Plan.Operands.push_back(
+                {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, false});
+          } else {
+            Existing->Rebuilt.clear(RegisterOperandFlag::Kill);
+            Existing->KillIsValid = false;
+          }
+          continue;
+        }
+        const bool IsSemanticUse = !Operand->isDebugUse() &&
+                                   !Operand->registerFlags().has(RegisterOperandFlag::Undef) &&
+                                   !Operand->registerValue()->isNoRegister();
+        bool IsKill = false;
+        if (IsSemanticUse) {
+          auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target);
+          if (!IsLive)
+            return std::unexpected(IsLive.error());
+          IsKill = !*IsLive;
+        }
+        RegisterOperandFlags Flags = Operand->registerFlags();
+        Flags.clear(RegisterOperandFlag::Kill);
+        if (IsKill)
+          Flags.set(RegisterOperandFlag::Kill);
+
+        const auto Existing =
+            std::ranges::find_if(Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) {
+              return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index;
+            });
+        if (Existing == Plan.Operands.end()) {
+          Plan.Operands.push_back(
+              {Instruction->stableID(), Index, Operand->registerFlags(), Flags, IsKill, false});
+        } else {
+          Existing->Rebuilt.clear(RegisterOperandFlag::Kill);
+          if (IsKill)
+            Existing->Rebuilt.set(RegisterOperandFlag::Kill);
+          Existing->KillIsValid = IsKill;
+        }
+        if (IsSemanticUse) {
+          auto Added = addOperandToLiveSet(*Operand, Virtual, Physical, Function, Target);
+          if (!Added)
+            return std::unexpected(Added.error());
+        }
+      }
+    }
+
+    if (Block == Function.firstBlock()) {
+      for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) {
+        const PhysicalRegisterDesc *Description =
+            Target.registers().physicalRegister(LiveIn.PhysReg);
+        if (Description == nullptr) {
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "liveness rebuild encountered an unknown function live-in");
+        }
+        addPhysicalRegister(Physical, *Description);
+        if (LiveIn.InitialVirtualRegister) {
+          auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target);
+          if (!Lanes)
+            return std::unexpected(Lanes.error());
+          Virtual.remove(*LiveIn.InitialVirtualRegister, *Lanes);
+        }
+      }
+    }
+
+    if (Virtual != BlockVariables->VirtualLiveIn || Physical != BlockVariables->PhysicalLiveIn) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "reverse liveness reconstruction disagrees with block dataflow");
+    }
+  }
+  return Plan;
+}
+
+struct ResolvedBlockLivenessPlan final {
+  MachineBasicBlock *Block = nullptr;
+  const BlockLivenessPlan *Plan = nullptr;
+};
+
+struct ResolvedOperandFlagPlan final {
+  MachineOperand *Operand = nullptr;
+  const OperandFlagPlan *Plan = nullptr;
+};
+
+struct ResolvedLivenessRebuildPlan final {
+  std::vector<ResolvedBlockLivenessPlan> Blocks;
+  std::vector<ResolvedOperandFlagPlan> Operands;
+};
+
+[[nodiscard]] Expected<ResolvedLivenessRebuildPlan>
+resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) {
+  ResolvedLivenessRebuildPlan Result;
+  Result.Blocks.reserve(Plan.Blocks.size());
+  for (const BlockLivenessPlan &BlockPlan : Plan.Blocks) {
+    const auto Position =
+        std::ranges::find_if(Function.allBlocks(), [&BlockPlan](const MachineBasicBlock *Block) {
+          return Block != nullptr && Block->stableID() == BlockPlan.Block;
+        });
+    if (Position == Function.allBlocks().end() || !(*Position)->isLinked()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable machine block");
+    }
+    Result.Blocks.push_back({*Position, &BlockPlan});
+  }
+
+  Result.Operands.reserve(Plan.Operands.size());
+  for (const OperandFlagPlan &OperandPlan : Plan.Operands) {
+    const auto Position = std::ranges::find_if(
+        Function.allInstructions(), [&OperandPlan](const MachineInstr *Instruction) {
+          return Instruction != nullptr && Instruction->stableID() == OperandPlan.Instruction;
+        });
+    if (Position == Function.allInstructions().end() || !(*Position)->isLinked()) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable instruction");
+    }
+    MachineOperand *Operand = (*Position)->operandAt(OperandPlan.OperandIndex);
+    if (Operand == nullptr) {
+      return makeUnexpected(ErrorCode::InternalError,
+                            "liveness rebuild plan references an unavailable operand");
+    }
+    Result.Operands.push_back({Operand, &OperandPlan});
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<void> restoreLivenessPlan(const ResolvedLivenessRebuildPlan &Plan) {
+  for (const ResolvedBlockLivenessPlan &Resolved : Plan.Blocks) {
+    Resolved.Block->clearLiveIns();
+    for (const MachineBasicBlockLiveIn &LiveIn : Resolved.Plan->OriginalLiveIns) {
+      auto Restored = Resolved.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+      if (!Restored)
+        return std::unexpected(Restored.error());
+    }
+  }
+  for (const ResolvedOperandFlagPlan &Resolved : Plan.Operands) {
+    auto Restored = Resolved.Operand->setRegisterFlags(Resolved.Plan->Original);
+    if (!Restored)
+      return std::unexpected(Restored.error());
+  }
+  return {};
+}
+
+[[nodiscard]] Expected<bool> applyLivenessPlan(MachineFunction &Function,
+                                               const LivenessRebuildPlan &Plan) {
+  auto Resolved = resolveLivenessPlan(Function, Plan);
+  if (!Resolved)
+    return std::unexpected(Resolved.error());
+
+  bool Changed = false;
+  for (const ResolvedBlockLivenessPlan &BlockPlan : Resolved->Blocks) {
+    Changed |= BlockPlan.Plan->OriginalLiveIns != BlockPlan.Plan->RebuiltLiveIns;
+    BlockPlan.Block->clearLiveIns();
+    for (const MachineBasicBlockLiveIn &LiveIn : BlockPlan.Plan->RebuiltLiveIns) {
+      auto Added = BlockPlan.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes);
+      if (!Added) {
+        auto Restored = restoreLivenessPlan(*Resolved);
+        if (!Restored)
+          return makeUnexpected(ErrorCode::InternalError,
+                                "liveness rebuild failed and rollback also failed");
+        return std::unexpected(Added.error());
+      }
+    }
+  }
+  for (const ResolvedOperandFlagPlan &OperandPlan : Resolved->Operands) {
+    Changed |= OperandPlan.Plan->Original != OperandPlan.Plan->Rebuilt;
+    auto Updated = OperandPlan.Operand->setRegisterFlags(OperandPlan.Plan->Rebuilt);
+    if (!Updated) {
+      auto Restored = restoreLivenessPlan(*Resolved);
+      if (!Restored)
+        return makeUnexpected(ErrorCode::InternalError,
+                              "liveness rebuild failed and rollback also failed");
+      return std::unexpected(Updated.error());
+    }
+  }
+  return Changed;
+}
+
+} // namespace
+
+SlotIndex
+SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept {
+  const auto Position = InstructionSlots.find(Instruction.stableID());
+  return Position == InstructionSlots.end() ? SlotIndex{} : Position->second;
+}
+
+SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept {
+  const auto Position = BlockStarts.find(&Block);
+  return Position == BlockStarts.end() ? SlotIndex{} : Position->second;
+}
+
+SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept {
+  const auto Position = BlockEnds.find(&Block);
+  return Position == BlockEnds.end() ? SlotIndex{} : Position->second;
+}
+
+const MachineInstr *
+SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept {
+  if (!Index.isValid())
+    return nullptr;
+  const auto Position = SlotToInstruction.find(Index.baseIndex().value());
+  return Position == SlotToInstruction.end() ? nullptr : Position->second;
+}
+
+const MachineBasicBlock *
+SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept {
+  if (!Index.isValid())
+    return nullptr;
+  for (const MachineBasicBlock *Block : BlocksByStart) {
+    const SlotIndex Start = blockStart(*Block);
+    const SlotIndex End = blockEnd(*Block);
+    if (!(Index < Start) && Index < End)
+      return Block;
+  }
+  return nullptr;
+}
+
+Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) {
+  const MachineBasicBlock *Block = Instruction.parent();
+  if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "SlotIndex insertion requires a linked indexed instruction");
+  }
+  if (InstructionSlots.contains(Instruction.stableID())) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex");
+  }
+
+  const MachineInstr *Previous = Instruction.previous();
+  const MachineInstr *Next = Instruction.next();
+  const SlotIndex LowerIndex =
+      Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous);
+  const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next);
+  if (!LowerIndex.isValid() || !UpperIndex.isValid()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "adjacent instructions are missing SlotIndexes");
+  }
+  const std::uint64_t Lower = LowerIndex.baseIndex().value();
+  const std::uint64_t Upper = UpperIndex.baseIndex().value();
+  if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "local SlotIndex space is exhausted; renumbering is required");
+  }
+  std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask;
+  if (Candidate <= Lower)
+    Candidate = Lower + SlotAlignmentMask + 1U;
+  if (Candidate >= Upper) {
+    return makeUnexpected(ErrorCode::Unsupported,
+                          "local SlotIndex space is exhausted; renumbering is required");
+  }
+  const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot();
+  InstructionSlots.emplace(Instruction.stableID(), Index);
+  SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction);
+  return {};
+}
+
+Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) {
+  const auto Position = InstructionSlots.find(Instruction.stableID());
+  if (Position == InstructionSlots.end())
+    return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex");
+  SlotToInstruction.erase(Position->second.baseIndex().value());
+  InstructionSlots.erase(Position);
+  return {};
+}
+
+Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) {
+  Result NewResult;
+  std::uint64_t Position = SlotSpacing;
+  auto Advance = [&Position]() -> Expected<void> {
+    if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) {
+      return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted");
+    }
+    Position += SlotSpacing;
+    return {};
+  };
+
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block);
+    NewResult.BlockStarts.emplace(Block, Start);
+    NewResult.BlocksByStart.push_back(Block);
+    auto Advanced = Advance();
+    if (!Advanced)
+      return std::unexpected(Advanced.error());
+
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot();
+      if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second ||
+          !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "duplicate instruction identity during SlotIndex construction");
+      }
+      Advanced = Advance();
+      if (!Advanced)
+        return std::unexpected(Advanced.error());
+    }
+    NewResult.BlockEnds.emplace(Block,
+                                SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block));
+    Advanced = Advance();
+    if (!Advanced)
+      return std::unexpected(Advanced.error());
+  }
+  *this = std::move(NewResult);
+  return {};
+}
+
+bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &,
+                                             const PreservedAnalyses &Preserved) const noexcept {
+  return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>());
+}
+
+Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function,
+                                                               const TargetDescription &,
+                                                               MachineAnalysisManager &) {
+  Result ResultValue;
+  auto Numbered = ResultValue.renumber(Function);
+  if (!Numbered)
+    return std::unexpected(Numbered.error());
+  return ResultValue;
+}
+
+LaneMask RegisterLaneSet::lanes(Register Reg) const noexcept {
+  return lanesFor(Values, Reg);
+}
+
+bool RegisterLaneSet::contains(Register Reg, LaneMask Lanes) const noexcept {
+  return containsLanes(Values, Reg, Lanes);
+}
+
+bool RegisterLaneSet::intersects(Register Reg, LaneMask Lanes) const noexcept {
+  return intersectsLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::add(Register Reg, LaneMask Lanes) {
+  if (!Reg.isNoRegister())
+    addLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::remove(Register Reg, LaneMask Lanes) {
+  removeLanes(Values, Reg, Lanes);
+}
+
+void RegisterLaneSet::unite(const RegisterLaneSet &Other) {
+  uniteLanes(Values, Other.Values);
+}
+
+void RegisterLaneSet::subtract(const RegisterLaneSet &Other) {
+  subtractLaneSets(Values, Other.Values);
+}
+
+LaneMask RegisterUnitLaneSet::lanes(RegisterUnitID Unit) const noexcept {
+  return lanesFor(Values, Unit);
+}
+
+bool RegisterUnitLaneSet::contains(RegisterUnitID Unit, LaneMask Lanes) const noexcept {
+  return containsLanes(Values, Unit, Lanes);
+}
+
+bool RegisterUnitLaneSet::intersects(RegisterUnitID Unit, LaneMask Lanes) const noexcept {
+  return intersectsLanes(Values, Unit, Lanes);
+}
+
+void RegisterUnitLaneSet::add(RegisterUnitID Unit, LaneMask Lanes) {
+  if (Unit.value() != 0 && !Lanes.empty())
+    addLanes(Values, Unit, Lanes);
+}
+
+void RegisterUnitLaneSet::remove(RegisterUnitID Unit, LaneMask Lanes) {
+  removeLanes(Values, Unit, Lanes);
+}
+
+void RegisterUnitLaneSet::unite(const RegisterUnitLaneSet &Other) {
+  uniteLanes(Values, Other.Values);
+}
+
+void RegisterUnitLaneSet::subtract(const RegisterUnitLaneSet &Other) {
+  subtractLaneSets(Values, Other.Values);
+}
+
+const MachineBlockLiveness *
+LiveVariablesAnalysis::Result::block(const MachineBasicBlock &Block) const noexcept {
+  const auto Position = Blocks.find(&Block);
+  return Position == Blocks.end() ? nullptr : &Position->second;
+}
+
+MachineBlockLiveness &
+LiveVariablesAnalysis::Result::getOrCreateBlock(const MachineBasicBlock &Block) {
+  return Blocks[&Block];
+}
+
+bool LiveVariablesAnalysis::Result::isLiveIn(const MachineBasicBlock &Block, Register Reg,
+                                             LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->VirtualLiveIn.intersects(Reg, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isLiveOut(const MachineBasicBlock &Block, Register Reg,
+                                              LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isUnitLiveIn(const MachineBasicBlock &Block,
+                                                 RegisterUnitID Unit,
+                                                 LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->PhysicalLiveIn.intersects(Unit, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::isUnitLiveOut(const MachineBasicBlock &Block,
+                                                  RegisterUnitID Unit,
+                                                  LaneMask Lanes) const noexcept {
+  const MachineBlockLiveness *Value = block(Block);
+  return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit, Lanes);
+}
+
+bool LiveVariablesAnalysis::Result::invalidate(const MachineFunction &,
+                                               const PreservedAnalyses &Preserved) const noexcept {
+  return !Preserved.preserves(MachineAnalysisManager::id<LiveVariablesAnalysis>());
+}
+
+Expected<LiveVariablesAnalysis::Result> LiveVariablesAnalysis::run(MachineFunction &Function,
+                                                                   const TargetDescription &Target,
+                                                                   MachineAnalysisManager &) {
+  return computeLiveVariables(Function, Target);
+}
+
+const LiveSegment *LiveRange::segmentAt(SlotIndex Position) const noexcept {
+  const auto Candidate = std::ranges::upper_bound(
+      Segments, Position, {}, [](const LiveSegment &Segment) { return Segment.Start; });
+  if (Candidate == Segments.begin())
+    return nullptr;
+  const LiveSegment &Previous = *std::prev(Candidate);
+  return Previous.contains(Position) ? &Previous : nullptr;
+}
+
+const LiveValueNumber *LiveRange::value(LiveValueNumberID ID) const noexcept {
+  if (!ID.isValid() || ID.value() > Values.size())
+    return nullptr;
+  const LiveValueNumber &Result = Values[ID.value() - 1U];
+  return Result.ID == ID ? &Result : nullptr;
+}
+
+const LiveValueNumber *LiveRange::valueAt(SlotIndex Position) const noexcept {
+  const LiveSegment *Segment = segmentAt(Position);
+  return Segment == nullptr ? nullptr : value(Segment->Value);
+}
+
+bool LiveRange::liveAt(SlotIndex Position) const noexcept {
+  return segmentAt(Position) != nullptr;
+}
+
+bool LiveRange::overlaps(const LiveRange &Other) const noexcept {
+  std::size_t Left = 0;
+  std::size_t Right = 0;
+  while (Left < Segments.size() && Right < Other.Segments.size()) {
+    if (Segments[Left].overlaps(Other.Segments[Right]))
+      return true;
+    if (Segments[Left].End <= Other.Segments[Right].Start)
+      ++Left;
+    else
+      ++Right;
+  }
+  return false;
+}
+
+Expected<LiveValueNumberID> LiveRange::createValue(SlotIndex Definition, LiveValueState State,
+                                                   std::optional<MachineInstrStableID> Origin) {
+  if (!Definition.isValid())
+    return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition");
+  if (Values.size() >= std::numeric_limits<std::uint32_t>::max())
+    return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted");
+  const LiveValueNumberID ID =
+      LiveValueNumberID::fromValue(static_cast<std::uint32_t>(Values.size() + 1U));
+  Values.push_back({ID, Definition, State, Origin});
+  return ID;
+}
+
+Expected<void> LiveRange::addSegment(LiveSegment Segment) {
+  if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() ||
+      value(Segment.Value) == nullptr) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "live segment requires ordered indexes and a known value number");
+  }
+  std::vector<LiveSegment> Candidate = Segments;
+  Candidate.push_back(Segment);
+  std::ranges::sort(Candidate, [](const LiveSegment &Left, const LiveSegment &Right) {
+    if (Left.Start != Right.Start)
+      return Left.Start < Right.Start;
+    return Left.End < Right.End;
+  });
+  for (std::size_t Index = 1; Index < Candidate.size(); ++Index) {
+    if (Candidate[Index].Start < Candidate[Index - 1U].End &&
+        Candidate[Index].Value != Candidate[Index - 1U].Value) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "live segments with different values overlap");
+    }
+  }
+  Segments = std::move(Candidate);
+  mergeAdjacent();
+  return {};
+}
+
+Expected<void> LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) {
+  return addSegment({Start, End, Value});
+}
+
+Expected<void> LiveRange::remove(SlotIndex Start, SlotIndex End) {
+  if (!Start.isValid() || !End.isValid() || !(Start < End)) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "removed live range must be nonempty");
+  }
+  std::vector<LiveSegment> Result;
+  for (const LiveSegment &Segment : Segments) {
+    if (!(Segment.Start < End && Start < Segment.End)) {
+      Result.push_back(Segment);
+      continue;
+    }
+    if (Segment.Start < Start)
+      Result.push_back({Segment.Start, Start, Segment.Value});
+    if (End < Segment.End)
+      Result.push_back({End, Segment.End, Segment.Value});
+  }
+  Segments = std::move(Result);
+  mergeAdjacent();
+  return {};
+}
+
+Expected<void> LiveRange::shrinkToUses(std::span<const SlotIndex> Uses) {
+  std::vector<LiveSegment> Result;
+  for (const LiveSegment &Segment : Segments) {
+    const LiveValueNumber *Value = value(Segment.Value);
+    if (Value == nullptr)
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "live segment references an unknown value number");
+    std::optional<SlotIndex> LastUse;
+    for (const SlotIndex Use : Uses) {
+      if (Segment.contains(Use) && (!LastUse || *LastUse < Use))
+        LastUse = Use;
+    }
+    if (!LastUse) {
+      if (Value->State == LiveValueState::Unused)
+        Result.push_back(Segment);
+      continue;
+    }
+    SlotIndex NewEnd = LastUse->deadSlot();
+    if (Segment.End < NewEnd)
+      NewEnd = Segment.End;
+    if (Segment.Start < NewEnd)
+      Result.push_back({Segment.Start, NewEnd, Segment.Value});
+  }
+  Segments = std::move(Result);
+  mergeAdjacent();
+  return verify();
+}
+
+Expected<void> LiveRange::verify() const {
+  std::unordered_set<LiveValueNumberID> IDs;
+  for (std::size_t Index = 0; Index < Values.size(); ++Index) {
+    const LiveValueNumber &Value = Values[Index];
+    if (!Value.ID.isValid() || Value.ID.value() != Index + 1U || !IDs.insert(Value.ID).second ||
+        !Value.Definition.isValid()) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "live range contains an invalid value number");
+    }
+  }
+  for (std::size_t Index = 0; Index < Segments.size(); ++Index) {
+    const LiveSegment &Segment = Segments[Index];
+    if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() ||
+        value(Segment.Value) == nullptr) {
+      return makeUnexpected(ErrorCode::VerificationError, "live range contains an invalid segment");
+    }
+    if (Index != 0 && Segments[Index - 1U].End > Segment.Start) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "live range segments are not ordered and disjoint");
+    }
+  }
+  return {};
+}
+
+void LiveRange::mergeAdjacent() {
+  if (Segments.empty())
+    return;
+  std::vector<LiveSegment> Result;
+  Result.reserve(Segments.size());
+  Result.push_back(Segments.front());
+  for (std::size_t Index = 1; Index < Segments.size(); ++Index) {
+    LiveSegment &Previous = Result.back();
+    const LiveSegment &Current = Segments[Index];
+    if (Current.Value == Previous.Value && Current.Start <= Previous.End) {
+      if (Previous.End < Current.End)
+        Previous.End = Current.End;
+      continue;
+    }
+    Result.push_back(Current);
+  }
+  Segments = std::move(Result);
+}
+
+const LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) const noexcept {
+  const auto Position = Intervals.find(Reg);
+  return Position == Intervals.end() ? nullptr : &Position->second;
+}
+
+LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) noexcept {
+  const auto Position = Intervals.find(Reg);
+  return Position == Intervals.end() ? nullptr : &Position->second;
+}
+
+const LiveRange *LiveIntervalsAnalysis::Result::regUnitRange(RegisterUnitID Unit) const noexcept {
+  const auto Position = RegisterUnitRanges.find(Unit);
+  return Position == RegisterUnitRanges.end() ? nullptr : &Position->second;
+}
+
+bool LiveIntervalsAnalysis::Result::interferes(Register Left, Register Right) const noexcept {
+  const LiveInterval *LeftInterval = interval(Left);
+  const LiveInterval *RightInterval = interval(Right);
+  return LeftInterval != nullptr && RightInterval != nullptr &&
+         LeftInterval->overlaps(*RightInterval);
+}
+
+bool LiveIntervalsAnalysis::Result::regMaskClobbers(const LiveInterval &Interval,
+                                                    PhysicalRegister Candidate) const noexcept {
+  for (const RegMaskPosition &Position : RegMasks) {
+    if (Position.Mask && Position.Mask->clobbers(Candidate) &&
+        Interval.MainRange.liveAt(Position.Position)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+Expected<void> LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg,
+                                                           std::span<const SlotIndex> Uses) {
+  LiveInterval *Value = interval(Reg);
+  if (Value == nullptr)
+    return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no live interval");
+  auto Main = Value->MainRange.shrinkToUses(Uses);
+  if (!Main)
+    return std::unexpected(Main.error());
+  for (LiveSubRange &SubRange : Value->SubRanges) {
+    auto Shrunk = SubRange.Range.shrinkToUses(Uses);
+    if (!Shrunk)
+      return std::unexpected(Shrunk.error());
+  }
+  return {};
+}
+
+bool LiveIntervalsAnalysis::Result::invalidate(const MachineFunction &,
+                                               const PreservedAnalyses &Preserved) const noexcept {
+  return !Preserved.preserves(MachineAnalysisManager::id<LiveIntervalsAnalysis>());
+}
+
+Expected<LiveIntervalsAnalysis::Result>
+LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target,
+                           MachineAnalysisManager &Analyses) {
+  auto Indexes = Analyses.getResult<SlotIndexesAnalysis>(Function, Target);
+  if (!Indexes)
+    return std::unexpected(Indexes.error());
+  auto Variables = Analyses.getResult<LiveVariablesAnalysis>(Function, Target);
+  if (!Variables)
+    return std::unexpected(Variables.error());
+
+  Result ResultValue;
+  ResultValue.Indexes = **Indexes;
+  for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) {
+    auto RegValue = Register::makeVirtual(Index);
+    if (!RegValue || !Function.registerInfo().isKnownVirtualRegister(*RegValue))
+      continue;
+    const Register Reg = *RegValue;
+    auto MainRange = buildLiveRange(
+        Function, ResultValue.Indexes,
+        [&Function, &Target, Reg](const MachineInstr &Instruction) {
+          return virtualRangeEvent(Instruction, Reg, std::nullopt, Function, Target);
+        },
+        [&Variables, Reg](const MachineBasicBlock &Block) {
+          const MachineBlockLiveness *Value = (*Variables)->block(Block);
+          return Value != nullptr && Value->VirtualLiveOut.intersects(Reg);
+        });
+    if (!MainRange)
+      return std::unexpected(MainRange.error());
+    if (MainRange->empty())
+      continue;
+
+    LiveInterval Interval;
+    Interval.Reg = Reg;
+    Interval.MainRange = std::move(*MainRange);
+    auto Info = Function.registerInfo().virtualRegisterInfo(Reg);
+    if (!Info)
+      return std::unexpected(Info.error());
+    Interval.AllocationHints = Info->get().AllocationHints;
+    std::ranges::sort(Interval.AllocationHints, [](PhysicalRegister Left, PhysicalRegister Right) {
+      return Left.number() < Right.number();
+    });
+
+    std::uint64_t Weight = 1;
+    for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) {
+      if (Operand.parent() == nullptr || Operand.registerFlags().has(RegisterOperandFlag::Undef)) {
+        continue;
+      }
+      Weight = Weight > std::numeric_limits<std::uint64_t>::max() - 10U
+                   ? std::numeric_limits<std::uint64_t>::max()
+                   : Weight + 10U;
+    }
+    Interval.SpillWeight = Weight;
+
+    auto LaneGroups = partitionVirtualRegisterLanes(Reg, Function, Target);
+    if (!LaneGroups)
+      return std::unexpected(LaneGroups.error());
+    for (const LaneMask Lanes : *LaneGroups) {
+      auto SubRange = buildLiveRange(
+          Function, ResultValue.Indexes,
+          [&Function, &Target, Reg, Lanes](const MachineInstr &Instruction) {
+            return virtualRangeEvent(Instruction, Reg, Lanes, Function, Target);
+          },
+          [&Variables, Reg, Lanes](const MachineBasicBlock &Block) {
+            const MachineBlockLiveness *Value = (*Variables)->block(Block);
+            return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes);
+          });
+      if (!SubRange)
+        return std::unexpected(SubRange.error());
+      if (!SubRange->empty())
+        Interval.SubRanges.push_back({Lanes, std::move(*SubRange)});
+    }
+    ResultValue.Intervals.emplace(Reg, std::move(Interval));
+  }
+
+  for (const RegisterUnitDesc &Unit : Target.registers().registerUnits()) {
+    auto Range = buildLiveRange(
+        Function, ResultValue.Indexes,
+        [&Target, Unit](const MachineInstr &Instruction) {
+          return unitRangeEvent(Instruction, Unit.ID, std::nullopt, Target);
+        },
+        [&Variables, Unit](const MachineBasicBlock &Block) {
+          const MachineBlockLiveness *Value = (*Variables)->block(Block);
+          return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit.ID);
+        });
+    if (!Range)
+      return std::unexpected(Range.error());
+    if (!Range->empty())
+      ResultValue.RegisterUnitRanges.emplace(Unit.ID, std::move(*Range));
+  }
+
+  for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
+    for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>();
+        if (MaskOperand == nullptr)
+          continue;
+        if (!MaskOperand->Mask)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "live intervals encountered a null register mask");
+        ResultValue.RegMasks.push_back(
+            {ResultValue.Indexes.instructionIndex(*Instruction).earlyClobberSlot(),
+             Instruction->stableID(), MaskOperand->Mask});
+      }
+    }
+  }
+  return ResultValue;
+}
+
+const MachinePassContract &RebuildMachineLivenessPass::contract() const noexcept {
+  static const MachinePassContract Contract = [] {
+    MachinePassContract Value{
+        .Name = "RebuildMachineLiveness",
+        .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
+                     MachineFunctionProperty::TiedOpsRewritten},
+        .Sets = {MachineFunctionProperty::TracksLiveness},
+        .Clears = {},
+        .RequiredAnalyses = {},
+        .VerificationStage = std::nullopt,
+    };
+    Value.DeclaredChanges = {MachinePassChange::Operands};
+    return Value;
+  }();
+  return Contract;
+}
+
+Expected<MachinePassResult> RebuildMachineLivenessPass::run(MachineFunction &Function,
+                                                            const TargetDescription &Target,
+                                                            MachineAnalysisManager &) {
+  const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties());
+  if (!Missing.empty()) {
+    return makeUnexpected(ErrorCode::VerificationError,
+                          "RebuildMachineLiveness requires properties: " + Missing.toString());
+  }
+  auto Applied = rebuildMachineLiveness(Function, Target);
+  if (!Applied)
+    return std::unexpected(Applied.error());
+
+  MachinePassResult Result;
+  Result.Changed = *Applied;
+  if (Result.Changed)
+    Result.Changes.add(MachinePassChange::Operands);
+  Result.Preserved = PreservedAnalyses::all();
+  return Result;
+}
+
+Expected<bool> rebuildMachineLiveness(MachineFunction &Function, const TargetDescription &Target) {
+  auto Plan = buildLivenessRebuildPlan(Function, Target);
+  if (!Plan)
+    return std::unexpected(Plan.error());
+  return applyLivenessPlan(Function, *Plan);
+}
+
+Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function,
+                                            const TargetDescription &Target) {
+  auto Plan = buildLivenessRebuildPlan(Function, Target);
+  if (!Plan)
+    return std::unexpected(Plan.error());
+  for (const BlockLivenessPlan &BlockPlan : Plan->Blocks) {
+    auto Actual = liveInUnits(BlockPlan.OriginalLiveIns, Target);
+    if (!Actual)
+      return std::unexpected(Actual.error());
+    auto Expected = liveInUnits(BlockPlan.RebuiltLiveIns, Target);
+    if (!Expected)
+      return std::unexpected(Expected.error());
+    if (*Actual != *Expected) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness block has stale physical live-ins");
+    }
+  }
+  for (const OperandFlagPlan &OperandPlan : Plan->Operands) {
+    if (OperandPlan.Original.has(RegisterOperandFlag::Kill) && !OperandPlan.KillIsValid) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness operand has a stale kill flag");
+    }
+    if (OperandPlan.Original.has(RegisterOperandFlag::Dead) && !OperandPlan.DeadIsValid) {
+      return makeUnexpected(ErrorCode::VerificationError,
+                            "TracksLiveness operand has a stale dead flag");
+    }
+  }
+  return {};
+}
+
+Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses) {
+  const std::array IDs{
+      MachineAnalysisManager::id<SlotIndexesAnalysis>(),
+      MachineAnalysisManager::id<LiveVariablesAnalysis>(),
+      MachineAnalysisManager::id<LiveIntervalsAnalysis>(),
+  };
+  const std::size_t Registered = static_cast<std::size_t>(
+      std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); }));
+  if (Registered == IDs.size())
+    return {};
+  if (Registered != 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "standard liveness analyses are only partially registered");
+  }
+
+  auto Candidate = Analyses.forkEmpty();
+  if (!Candidate)
+    return std::unexpected(Candidate.error());
+  MachineAnalysisManager &Staging = **Candidate;
+  auto Slots = Staging.registerAnalysis<SlotIndexesAnalysis>({
+      .Name = "SlotIndexes",
+      .Dependencies = {},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::BlockLayout},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Slots)
+    return std::unexpected(Slots.error());
+  auto Variables = Staging.registerAnalysis<LiveVariablesAnalysis>({
+      .Name = "LiveVariables",
+      .Dependencies = {},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                        MachinePassChange::Registers, MachinePassChange::CFG,
+                        MachinePassChange::TargetState},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Variables)
+    return std::unexpected(Variables.error());
+  auto Intervals = Staging.registerAnalysis<LiveIntervalsAnalysis>({
+      .Name = "LiveIntervals",
+      .Dependencies = {MachineAnalysisManager::id<SlotIndexesAnalysis>(),
+                       MachineAnalysisManager::id<LiveVariablesAnalysis>()},
+      .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands,
+                        MachinePassChange::Registers, MachinePassChange::CFG,
+                        MachinePassChange::BlockLayout, MachinePassChange::TargetState},
+      .ThreadSafety = PassThreadSafety::ThreadSafe,
+  });
+  if (!Intervals)
+    return std::unexpected(Intervals.error());
+  Analyses.Registry = std::move(Staging.Registry);
+  return {};
+}
+
+} // namespace rcc
diff --git a/backend/lib/CodeGen/MachinePipelinePasses.cpp b/backend/lib/CodeGen/MachinePipelinePasses.cpp
index c3ee653..209439c 100644
--- a/backend/lib/CodeGen/MachinePipelinePasses.cpp
+++ b/backend/lib/CodeGen/MachinePipelinePasses.cpp
@@ -7,6 +7,7 @@
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineFunctionCloner.h"
 #include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/TargetDescription.h"
 
@@ -232,6 +233,20 @@ registerConfigurationFingerprint(const MachineRegisterInfo &RegInfo) noexcept {
   return Error(Source.code(), std::move(Prefix));
 }
 
+[[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    return {};
+  }
+  auto Rebuilt = rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  if (*Rebuilt)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
+}
+
 } // namespace
 
 const MachinePassContract &LegalizerPass::contract() const noexcept {
@@ -359,6 +374,9 @@ Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Fu
       return std::unexpected(
           prefixedError(FinalValidation.error(), "legalizer produced invalid MachineIR: "));
   }
+  auto Liveness = repairTrackedLiveness(Function, Target, Result);
+  if (!Liveness)
+    return std::unexpected(prefixedError(Liveness.error(), "legalizer liveness repair failed: "));
   Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
   return Result;
 }
@@ -470,6 +488,14 @@ Expected<MachinePassResult> RegisterBankSelectPass::run(MachineFunction &Functio
     Result.Changes.add(MachinePassChange::Registers);
   }
 
+  auto Liveness = repairTrackedLiveness(Function, Target, Result);
+  if (!Liveness) {
+    auto Restored = Restore();
+    if (!Restored)
+      return std::unexpected(prefixedError(Restored.error(), "register-bank rollback failed: "));
+    return std::unexpected(
+        prefixedError(Liveness.error(), "register-bank liveness repair failed: "));
+  }
   Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
   return Result;
 }
@@ -607,6 +633,11 @@ InstructionSelectPass::runImplementation(MachineFunction &Function, const Target
   if (!RegisterValidation)
     return std::unexpected(prefixedError(RegisterValidation.error(),
                                          "instruction selection produced invalid registers: "));
+  auto Liveness = repairTrackedLiveness(Function, Target, Result);
+  if (!Liveness) {
+    return std::unexpected(
+        prefixedError(Liveness.error(), "instruction-selection liveness repair failed: "));
+  }
   Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
   return Result;
 }
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp
index e77bb2a..e413b45 100644
--- a/backend/lib/CodeGen/MachineSSAExit.cpp
+++ b/backend/lib/CodeGen/MachineSSAExit.cpp
@@ -9,6 +9,7 @@
 #include "rcc/CodeGen/MachineFunctionCloner.h"
 #include "rcc/CodeGen/MachineIRBuilder.h"
 #include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/TargetDescription.h"
@@ -458,29 +459,18 @@ placePhiCopiesOnEdge(MachineFunction &Function, const TargetDescription &Target,
   return EdgeBlock;
 }
 
-[[nodiscard]] Expected<bool> clearStaleLivenessFlags(MachineFunction &Function) {
-  bool Changed = false;
-  for (MachineInstr *Instruction : Function.allInstructions()) {
-    if (Instruction->parent() == nullptr)
-      continue;
-    for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) {
-      MachineOperand *Operand = Instruction->operandAt(Index);
-      if (Operand == nullptr || !Operand->isRegister())
-        continue;
-      RegisterOperandFlags Flags = Operand->registerFlags();
-      const bool HadStaleFlag =
-          Flags.has(RegisterOperandFlag::Kill) || Flags.has(RegisterOperandFlag::Dead);
-      if (!HadStaleFlag)
-        continue;
-      Flags.clear(RegisterOperandFlag::Kill);
-      Flags.clear(RegisterOperandFlag::Dead);
-      auto Updated = Operand->setRegisterFlags(Flags);
-      if (!Updated)
-        return std::unexpected(Updated.error());
-      Changed = true;
-    }
+[[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
+                                                   const TargetDescription &Target,
+                                                   MachinePassResult &Result) {
+  if (!Result.Changed || !Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
+    return {};
   }
-  return Changed;
+  auto Rebuilt = rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
+  if (*Rebuilt)
+    Result.Changes.add(MachinePassChange::Operands);
+  return {};
 }
 
 [[nodiscard]] Expected<SubRegIndex> subRegIndex(const MachineOperand &Operand,
@@ -900,11 +890,10 @@ Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunctio
   }
 
   if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
-    auto Cleared = clearStaleLivenessFlags(Function);
-    if (!Cleared)
-      return std::unexpected(Cleared.error());
-    if (*Cleared)
-      Result.Changes.add(MachinePassChange::Operands);
+    auto Repaired = repairTrackedLiveness(Function, Target, Result);
+    if (!Repaired)
+      return std::unexpected(
+          prefixedError(Repaired.error(), "PHI-elimination liveness repair failed: "));
   }
   Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
   return Result;
@@ -1077,11 +1066,10 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
   if (!FinalState)
     return std::unexpected(FinalState.error());
   if (Result.Changed && Function.properties().has(MachineFunctionProperty::TracksLiveness)) {
-    auto Cleared = clearStaleLivenessFlags(Function);
-    if (!Cleared)
-      return std::unexpected(Cleared.error());
-    if (*Cleared)
-      Result.Changes.add(MachinePassChange::Operands);
+    auto Repaired = repairTrackedLiveness(Function, Target, Result);
+    if (!Repaired)
+      return std::unexpected(
+          prefixedError(Repaired.error(), "two-address liveness repair failed: "));
   }
   Result.Preserved = Result.Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
   return Result;
diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp
index 8f4809a..957213b 100644
--- a/backend/lib/CodeGen/MachineVerifier.cpp
+++ b/backend/lib/CodeGen/MachineVerifier.cpp
@@ -8,6 +8,7 @@
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
 #include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineMemOperand.h"
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
@@ -877,6 +878,11 @@ private:
     if (Has(MachineFunctionProperty::TiedOpsRewritten) && HasStageTenPseudo) {
       return fail("TiedOpsRewritten function contains a Stage 10 pseudo");
     }
+    if (Has(MachineFunctionProperty::TracksLiveness)) {
+      auto Liveness = verifyTrackedMachineLiveness(Function, Target);
+      if (!Liveness)
+        return failWith("tracked machine liveness", Liveness.error());
+    }
 
     const bool NeedsTypes = Options.Mode == MachineVerifierMode::PreLegalizer ||
                             Has(MachineFunctionProperty::Legalized) ||
diff --git a/backend/lib/CodeGen/TargetRegisterInfo.cpp b/backend/lib/CodeGen/TargetRegisterInfo.cpp
index 42ae935..7ddf676 100644
--- a/backend/lib/CodeGen/TargetRegisterInfo.cpp
+++ b/backend/lib/CodeGen/TargetRegisterInfo.cpp
@@ -135,6 +135,7 @@ Expected<TargetRegisterInfo> TargetRegisterInfo::create(TargetRegisterInfoDesc D
   }
 
   std::unordered_set<RegisterUnitID> ReferencedUnits;
+  std::unordered_map<RegisterUnitID, int> UnitLaneCardinalities;
   for (const PhysicalRegisterDesc &Register : Result.Description.PhysicalRegisters) {
     if (Register.Units.empty())
       return invalidDescription("physical register must reference at least one register unit");
@@ -147,6 +148,12 @@ Expected<TargetRegisterInfo> TargetRegisterInfo::create(TargetRegisterInfoDesc D
         return invalidDescription(
             "physical register has an unknown, empty-lane, or duplicate register unit");
       }
+      const int Cardinality = std::popcount(Unit.Lanes.rawValue());
+      const auto [Position, Inserted] = UnitLaneCardinalities.emplace(Unit.Unit, Cardinality);
+      if (!Inserted && Position->second != Cardinality) {
+        return invalidDescription(
+            "every physical-register view of a register unit must have the same lane count");
+      }
       ReferencedUnits.insert(Unit.Unit);
       RegisterLanes = RegisterLanes | Unit.Lanes;
     }
diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index c8ea9b8..b3f071b 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -17,6 +17,7 @@ set(
   MachineIRCoreTest.cpp
   MachineAnalysesTest.cpp
   MachineJumpTableInfoTest.cpp
+  MachineLivenessTest.cpp
   MachineMetadataTest.cpp
   MachineOperandTest.cpp
   MachinePassTest.cpp
@@ -221,6 +222,18 @@ add_test(
   COMMAND RCCBackendCodeGenMachineJumpTableInfoTests
 )
 
+add_executable(RCCBackendCodeGenMachineLivenessTests MachineLivenessTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineLivenessTests)
+target_link_libraries(
+  RCCBackendCodeGenMachineLivenessTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget RCCBackend::RISCV
+)
+
+add_test(
+  NAME RCCBackend.CodeGen.MachineLiveness
+  COMMAND RCCBackendCodeGenMachineLivenessTests
+)
+
 add_executable(RCCBackendCodeGenMachineMetadataTests MachineMetadataTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenMachineMetadataTests)
 target_link_libraries(
@@ -355,6 +368,7 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalysesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfoTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
@@ -385,6 +399,7 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalysesTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfoTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
diff --git a/backend/unittests/CodeGen/MachineLivenessTest.cpp b/backend/unittests/CodeGen/MachineLivenessTest.cpp
new file mode 100644
index 0000000..a375e25
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineLivenessTest.cpp
@@ -0,0 +1,872 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineLiveness.h"
+
+#include "Target/TestTarget.h"
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVRegisters.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <algorithm>
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace {
+
+constexpr std::uint32_t DefOpcode = 2048;
+constexpr std::uint32_t UseOpcode = 2049;
+constexpr std::uint32_t EarlyDefOpcode = 2050;
+constexpr std::uint32_t MaskOpcode = 2051;
+constexpr std::uint32_t MaskedDefOpcode = 2052;
+constexpr std::uint32_t LiveOutMaskOpcode = 2053;
+
+class TestContext final {
+public:
+  void expect(bool Condition, std::string_view Message) {
+    if (Condition)
+      return;
+    std::cerr << Message << '\n';
+    ++Failures;
+  }
+
+  [[nodiscard]] int result() const noexcept {
+    return Failures == 0 ? 0 : 1;
+  }
+
+private:
+  int Failures = 0;
+};
+
+[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) {
+  return rcc::Opcode::fromValue(Value);
+}
+
+[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role,
+                                                     bool EarlyClobber = false) {
+  rcc::OperandDescriptor Result;
+  Result.Kinds = {rcc::MachineOperand::Kind::Register};
+  Result.RegisterRole = Role;
+  Result.EarlyClobber = EarlyClobber;
+  Result.AllowSubReg = true;
+  return Result;
+}
+
+[[nodiscard]] rcc::OperandDescriptor plainOperand(rcc::MachineOperand::Kind Kind) {
+  rcc::OperandDescriptor Result;
+  Result.Kinds = {Kind};
+  return Result;
+}
+
+[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) {
+  rcc::InstructionDescriptor Result;
+  Result.InstructionOpcode = testOpcode(Value);
+  Result.Name = std::move(Name);
+  Result.Flags = {rcc::InstructionFlag::ProducesCode};
+  return Result;
+}
+
+[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() {
+  std::vector<rcc::InstructionDescriptor> Descriptors;
+  std::vector<rcc::ImmediatePredicate> Predicates;
+  auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates);
+  if (!Generic)
+    return std::unexpected(Generic.error());
+
+  auto Def = instruction(DefOpcode, "LIVENESS_DEF");
+  Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)};
+  Def.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(Def));
+
+  auto Use = instruction(UseOpcode, "LIVENESS_USE");
+  Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)};
+  Descriptors.push_back(std::move(Use));
+
+  auto EarlyDef = instruction(EarlyDefOpcode, "LIVENESS_EARLY_DEF");
+  EarlyDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def, true)};
+  EarlyDef.NumExplicitDefs = 1;
+  Descriptors.push_back(std::move(EarlyDef));
+
+  auto Mask = instruction(MaskOpcode, "LIVENESS_MASK");
+  Mask.Operands = {plainOperand(rcc::MachineOperand::Kind::RegisterMask)};
+  Mask.Flags.set(rcc::InstructionFlag::Call);
+  Mask.Flags.set(rcc::InstructionFlag::HasSideEffects);
+  Descriptors.push_back(std::move(Mask));
+
+  auto MaskedDef = instruction(MaskedDefOpcode, "LIVENESS_MASKED_DEF");
+  MaskedDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def),
+                        plainOperand(rcc::MachineOperand::Kind::RegisterMask)};
+  MaskedDef.NumExplicitDefs = 1;
+  MaskedDef.Flags.set(rcc::InstructionFlag::Call);
+  MaskedDef.Flags.set(rcc::InstructionFlag::HasSideEffects);
+  Descriptors.push_back(std::move(MaskedDef));
+
+  auto LiveOutMask = instruction(LiveOutMaskOpcode, "LIVENESS_LIVEOUT_MASK");
+  LiveOutMask.Operands = {plainOperand(rcc::MachineOperand::Kind::LiveOutRegisterMask)};
+  Descriptors.push_back(std::move(LiveOutMask));
+
+  auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates));
+  if (!Instructions)
+    return std::unexpected(Instructions.error());
+  return rcc::test::createTestTargetDescription(std::move(*Instructions));
+}
+
+struct FunctionFixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  std::vector<rcc::MachineBasicBlock *> Blocks;
+};
+
+[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name, std::uint64_t ID,
+                                                            std::size_t BlockCount) {
+  auto Function =
+      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  if (!Function)
+    return std::unexpected(Function.error());
+  FunctionFixture Result{std::move(*Function), {}};
+  Result.Blocks.reserve(BlockCount);
+  for (std::size_t Index = 0; Index < BlockCount; ++Index) {
+    auto Block = Result.Function->createBasicBlock();
+    if (!Block)
+      return std::unexpected(Block.error());
+    auto Appended = Result.Function->appendBlock(**Block);
+    if (!Appended)
+      return std::unexpected(Appended.error());
+    Result.Blocks.push_back(*Block);
+  }
+  return Result;
+}
+
+[[nodiscard]] rcc::Expected<rcc::Register> createVReg(rcc::MachineFunction &Function) {
+  auto Type = rcc::LLT::makeInteger(64);
+  if (!Type)
+    return std::unexpected(Type.error());
+  auto Reg = Function.registerInfo().createVirtualRegister(*Type);
+  if (!Reg)
+    return std::unexpected(Reg.error());
+  auto Bank = Function.registerInfo().setRegisterBank(*Reg, rcc::test::TestRegisterBank::GPR);
+  if (!Bank)
+    return std::unexpected(Bank.error());
+  auto Class = Function.registerInfo().setRegisterClass(*Reg, rcc::test::TestRegisterClass::GPR64);
+  if (!Class)
+    return std::unexpected(Class.error());
+  return *Reg;
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+         rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {},
+         bool EarlyClobber = false) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(testOpcode(EarlyClobber ? EarlyDefOpcode : DefOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  rcc::RegisterOperandFlags Flags;
+  if (EarlyClobber)
+    Flags.set(rcc::RegisterOperandFlag::EarlyClobber);
+  auto Added = Pending->addDef(Reg, Flags, SubReg);
+  if (!Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildUse(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+         rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {},
+         rcc::MachineInstr *Before = nullptr) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point =
+      Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(testOpcode(UseOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Added = Pending->addUse(Reg, {}, SubReg);
+  if (!Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildMask(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+          rcc::MachineBasicBlock &Block, std::shared_ptr<const rcc::RegisterMask> Mask) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(testOpcode(MaskOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Added = Pending->addRegisterMask(std::move(Mask));
+  if (!Added)
+    return std::unexpected(Added.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+buildMaskedDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
+               rcc::MachineBasicBlock &Block, rcc::Register Reg,
+               std::shared_ptr<const rcc::RegisterMask> Mask) {
+  rcc::MachineIRBuilder Builder(Function, Target);
+  auto Point = Builder.setInsertPoint(Block);
+  if (!Point)
+    return std::unexpected(Point.error());
+  auto Pending = Builder.buildInstr(testOpcode(MaskedDefOpcode));
+  if (!Pending)
+    return std::unexpected(Pending.error());
+  auto Def = Pending->addDef(Reg);
+  if (!Def)
+    return std::unexpected(Def.error());
+  auto MaskResult = Pending->addRegisterMask(std::move(Mask));
+  if (!MaskResult)
+    return std::unexpected(MaskResult.error());
+  return Pending->build();
+}
+
+[[nodiscard]] rcc::PhysicalRegister physical(std::uint32_t Number) {
+  return *rcc::PhysicalRegister::create(Number);
+}
+
+[[nodiscard]] bool hasFlag(const rcc::MachineInstr &Instruction, std::size_t OperandIndex,
+                           rcc::RegisterOperandFlag Flag) {
+  const rcc::MachineOperand *Operand = Instruction.operandAt(OperandIndex);
+  return Operand != nullptr && Operand->registerFlags().has(Flag);
+}
+
+void testLiveRange(TestContext &Context) {
+  const rcc::SlotIndex S16 = rcc::SlotIndex::fromValue(16).registerSlot();
+  const rcc::SlotIndex S24 = rcc::SlotIndex::fromValue(24).registerSlot();
+  const rcc::SlotIndex S32 = rcc::SlotIndex::fromValue(32).registerSlot();
+  const rcc::SlotIndex S40 = rcc::SlotIndex::fromValue(40).registerSlot();
+  const rcc::SlotIndex S48 = rcc::SlotIndex::fromValue(48).registerSlot();
+
+  rcc::LiveRange Range;
+  auto First = Range.createValue(S16);
+  Context.expect(First.has_value(), "live value creation must succeed");
+  if (!First)
+    return;
+  Context.expect(Range.addSegment({S16, S32, *First}).has_value() &&
+                     Range.addSegment({S32, S48, *First}).has_value() &&
+                     Range.segments().size() == 1,
+                 "adjacent same-value live segments must merge");
+  auto Second = Range.createValue(S40, rcc::LiveValueState::Redefined);
+  Context.expect(Second.has_value() && !Range.addSegment({S24, S40, *Second}),
+                 "overlapping different live values must be rejected");
+  Context.expect(Range.valueAt(S24) != nullptr && Range.liveAt(S40) &&
+                     Range.remove(S24, S40).has_value() && Range.segments().size() == 2 &&
+                     Range.verify().has_value(),
+                 "live-range lookup and removal must preserve ordered half-open segments");
+
+  rcc::LiveRange Shrunk;
+  auto Value = Shrunk.createValue(S16);
+  if (!Value) {
+    Context.expect(false, "shrink test value creation must succeed");
+    return;
+  }
+  const std::array Uses{S32};
+  Context.expect(Shrunk.addSegment({S16, S48.deadSlot(), *Value}).has_value() &&
+                     Shrunk.shrinkToUses(Uses).has_value() && Shrunk.segments().size() == 1 &&
+                     Shrunk.segments().front().End == S32.deadSlot(),
+                 "shrinkToUses must retain exactly through the final use dead slot");
+}
+
+void testSlotIndexes(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("slot-indexes", 1, 1);
+  if (!Fixture) {
+    Context.expect(false, "SlotIndexes fixture creation must succeed");
+    return;
+  }
+  auto Reg = createVReg(*Fixture->Function);
+  auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg)
+                 : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())};
+  auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg)
+                 : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())};
+  if (!Reg || !Def || !Use) {
+    Context.expect(false, "SlotIndexes instructions must be built");
+    return;
+  }
+
+  rcc::MachineAnalysisManager Analyses;
+  auto Registered = rcc::registerStage11MachineAnalyses(Analyses);
+  auto Indexes =
+      Registered
+          ? Analyses.getResult<rcc::SlotIndexesAnalysis>(*Fixture->Function, Target)
+          : rcc::Expected<rcc::SlotIndexesAnalysis::Result *>{std::unexpected(Registered.error())};
+  if (!Indexes) {
+    Context.expect(false, "SlotIndexes analysis must materialize");
+    return;
+  }
+  const rcc::SlotIndex DefIndex = (*Indexes)->instructionIndex(**Def);
+  const rcc::SlotIndex UseIndex = (*Indexes)->instructionIndex(**Use);
+  Context.expect((*Indexes)->blockStart(*Fixture->Blocks[0]) < DefIndex.earlyClobberSlot() &&
+                     DefIndex.earlyClobberSlot() < DefIndex && DefIndex < DefIndex.deadSlot() &&
+                     DefIndex.deadSlot() < UseIndex &&
+                     UseIndex < (*Indexes)->blockEnd(*Fixture->Blocks[0]),
+                 "SlotIndexes must order block, early-clobber, register, and dead slots");
+  Context.expect((*Indexes)->instructionFromIndex(DefIndex.deadSlot()) == *Def &&
+                     (*Indexes)->blockFromIndex(UseIndex) == Fixture->Blocks[0],
+                 "SlotIndexes reverse mappings must accept every instruction subslot");
+
+  auto Inserted = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Use);
+  Context.expect(Inserted && (*Indexes)->insertInstruction(**Inserted).has_value(),
+                 "local SlotIndex insertion must use reserved numbering space");
+  if (Inserted) {
+    const rcc::SlotIndex InsertedIndex = (*Indexes)->instructionIndex(**Inserted);
+    Context.expect(DefIndex < InsertedIndex && InsertedIndex < UseIndex,
+                   "locally inserted SlotIndex must lie between adjacent instructions");
+    Context.expect((*Indexes)->eraseInstruction(**Inserted).has_value() &&
+                       !(*Indexes)->instructionIndex(**Inserted).isValid() &&
+                       (*Indexes)->renumber(*Fixture->Function).has_value() &&
+                       (*Indexes)->instructionIndex(**Inserted).isValid(),
+                   "SlotIndex erasure and full renumbering must rebuild exact mappings");
+
+    auto Second = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Inserted);
+    auto SecondIndexed = Second ? (*Indexes)->insertInstruction(**Second)
+                                : rcc::Expected<void>{std::unexpected(Second.error())};
+    auto Third = Second
+                     ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Second)
+                     : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Second.error())};
+    auto ThirdIndexed = Third ? (*Indexes)->insertInstruction(**Third)
+                              : rcc::Expected<void>{std::unexpected(Third.error())};
+    auto Exhausted =
+        Third ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Third)
+              : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Third.error())};
+    auto ExhaustedIndex = Exhausted ? (*Indexes)->insertInstruction(**Exhausted)
+                                    : rcc::Expected<void>{std::unexpected(Exhausted.error())};
+    Context.expect(SecondIndexed && ThirdIndexed && Exhausted && !ExhaustedIndex &&
+                       ExhaustedIndex.error().code() == rcc::ErrorCode::Unsupported &&
+                       (*Indexes)->renumber(*Fixture->Function).has_value() &&
+                       (*Indexes)->instructionIndex(**Exhausted).isValid(),
+                   "local SlotIndex exhaustion must request and recover through full renumbering");
+  }
+}
+
+void testCFGAndValueNumbers(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("cfg-liveness", 2, 8);
+  if (!Fixture) {
+    Context.expect(false, "CFG liveness fixture creation must succeed");
+    return;
+  }
+  auto &Function = *Fixture->Function;
+  auto &Entry = *Fixture->Blocks[0];
+  auto &Left = *Fixture->Blocks[1];
+  auto &Right = *Fixture->Blocks[2];
+  auto &Join = *Fixture->Blocks[3];
+  auto &Header = *Fixture->Blocks[4];
+  auto &Body = *Fixture->Blocks[5];
+  auto &Exit = *Fixture->Blocks[6];
+  auto &Dead = *Fixture->Blocks[7];
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  auto Updater = Function.cfgUpdater();
+  const bool CFGValid = Half && Updater.addSuccessor(Entry, Left, *Half) &&
+                        Updater.addSuccessor(Entry, Right, *Half) &&
+                        Updater.addSuccessor(Left, Join, rcc::BranchProbability::one()) &&
+                        Updater.addSuccessor(Right, Join, rcc::BranchProbability::one()) &&
+                        Updater.addSuccessor(Join, Header, rcc::BranchProbability::one()) &&
+                        Updater.addSuccessor(Header, Body, *Half) &&
+                        Updater.addSuccessor(Header, Exit, *Half) &&
+                        Updater.addSuccessor(Body, Header, rcc::BranchProbability::one());
+  Context.expect(CFGValid, "diamond and loop CFG construction must succeed");
+  if (!CFGValid)
+    return;
+
+  auto Across = createVReg(Function);
+  auto Merged = createVReg(Function);
+  auto Unreachable = createVReg(Function);
+  auto Redefined = createVReg(Function);
+  if (!Across || !Merged || !Unreachable || !Redefined) {
+    Context.expect(false, "CFG liveness virtual registers must be created");
+    return;
+  }
+  auto AcrossDef = buildDef(Function, Target, Entry, *Across);
+  auto LeftDef = buildDef(Function, Target, Left, *Merged);
+  auto RightDef = buildDef(Function, Target, Right, *Merged);
+  auto MergedUse = buildUse(Function, Target, Join, *Merged);
+  auto LoopUse = buildUse(Function, Target, Body, *Across);
+  auto DeadUse = buildUse(Function, Target, Dead, *Unreachable);
+  auto FirstRedef = buildDef(Function, Target, Exit, *Redefined);
+  auto SecondRedef = buildDef(Function, Target, Exit, *Redefined);
+  if (!AcrossDef || !LeftDef || !RightDef || !MergedUse || !LoopUse || !DeadUse || !FirstRedef ||
+      !SecondRedef) {
+    Context.expect(false, "CFG liveness instructions must be built");
+    return;
+  }
+
+  rcc::MachineAnalysisManager Analyses;
+  auto Registered = rcc::registerStage11MachineAnalyses(Analyses);
+  auto Variables = Registered ? Analyses.getResult<rcc::LiveVariablesAnalysis>(Function, Target)
+                              : rcc::Expected<rcc::LiveVariablesAnalysis::Result *>{
+                                    std::unexpected(Registered.error())};
+  auto Intervals = Registered ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(Function, Target)
+                              : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                                    std::unexpected(Registered.error())};
+  if (!Variables || !Intervals) {
+    Context.expect(false, "CFG liveness analyses must materialize");
+    return;
+  }
+  Context.expect((*Variables)->isLiveOut(Entry, *Across) && (*Variables)->isLiveIn(Left, *Across) &&
+                     (*Variables)->isLiveIn(Right, *Across) &&
+                     (*Variables)->isLiveIn(Header, *Across) &&
+                     (*Variables)->isLiveOut(Body, *Across),
+                 "CFG fixed point must propagate a value through a diamond and loop backedge");
+  Context.expect(
+      (*Variables)->isLiveOut(Left, *Merged) && (*Variables)->isLiveOut(Right, *Merged) &&
+          (*Variables)->isLiveIn(Join, *Merged) && (*Variables)->isLiveIn(Dead, *Unreachable),
+      "liveness must merge predecessor definitions and retain unreachable uses");
+
+  const rcc::LiveInterval *MergedInterval = (*Intervals)->interval(*Merged);
+  const rcc::LiveInterval *AcrossInterval = (*Intervals)->interval(*Across);
+  const rcc::LiveInterval *RedefinedInterval = (*Intervals)->interval(*Redefined);
+  const bool HasPhi = MergedInterval != nullptr &&
+                      std::ranges::any_of(MergedInterval->MainRange.values(),
+                                          [](const rcc::LiveValueNumber &Value) {
+                                            return Value.State == rcc::LiveValueState::Phi;
+                                          });
+  const bool HasRedefined =
+      RedefinedInterval != nullptr &&
+      std::ranges::any_of(RedefinedInterval->MainRange.values(),
+                          [](const rcc::LiveValueNumber &Value) {
+                            return Value.State == rcc::LiveValueState::Redefined;
+                          });
+  Context.expect(MergedInterval != nullptr && MergedInterval->MainRange.values().size() >= 3 &&
+                     HasPhi && HasRedefined,
+                 "non-SSA intervals must retain multiple definitions, PHI, and redefined values");
+  Context.expect(AcrossInterval != nullptr && (*Intervals)->interferes(*Across, *Merged),
+                 "live intervals must expose CFG-derived interference");
+}
+
+void testLaneSubrangesAndEarlyClobber(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("lane-subranges", 3, 1);
+  if (!Fixture) {
+    Context.expect(false, "lane-subrange fixture creation must succeed");
+    return;
+  }
+  auto Reg = createVReg(*Fixture->Function);
+  auto Early = createVReg(*Fixture->Function);
+  if (!Reg || !Early) {
+    Context.expect(false, "lane-subrange registers must be created");
+    return;
+  }
+  auto LowDef =
+      buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32);
+  auto LowUse =
+      buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32);
+  auto HighDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg,
+                          rcc::test::TestSubReg::High32);
+  auto HighUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg,
+                          rcc::test::TestSubReg::High32);
+  auto EarlyDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Early, {}, true);
+  auto EarlyUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Early);
+  if (!LowDef || !LowUse || !HighDef || !HighUse || !EarlyDef || !EarlyUse) {
+    Context.expect(false, "lane-subrange instructions must be built");
+    return;
+  }
+
+  rcc::MachineAnalysisManager Analyses;
+  auto Registered = rcc::registerStage11MachineAnalyses(Analyses);
+  auto Intervals = Registered
+                       ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target)
+                       : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                             std::unexpected(Registered.error())};
+  if (!Intervals) {
+    Context.expect(false, "lane-subrange intervals must materialize");
+    return;
+  }
+  const rcc::LiveInterval *Interval = (*Intervals)->interval(*Reg);
+  const rcc::LiveInterval *EarlyInterval = (*Intervals)->interval(*Early);
+  const bool HasLow = Interval != nullptr &&
+                      std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) {
+                        return Range.Lanes == rcc::LaneMask::fromRaw(0x3);
+                      });
+  const bool HasHigh = Interval != nullptr &&
+                       std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) {
+                         return Range.Lanes == rcc::LaneMask::fromRaw(0xC);
+                       });
+  Context.expect(Interval != nullptr && Interval->SubRanges.size() == 2 && HasLow && HasHigh,
+                 "partial virtual-register accesses must form disjoint lane subranges");
+  Context.expect(EarlyInterval != nullptr && !EarlyInterval->MainRange.values().empty() &&
+                     EarlyInterval->MainRange.values().front().Definition.kind() ==
+                         rcc::SlotIndexKind::EarlyClobber,
+                 "early-clobber definitions must use the early-clobber slot");
+}
+
+void testPhysicalUnitsAndRegMasks(TestContext &Context, const rcc::TargetDescription &Target) {
+  const rcc::RegisterUnitID MultiLaneUnit = rcc::RegisterUnitID::fromValue(9);
+  rcc::RegisterUnitLaneSet PartialLanes;
+  PartialLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x3));
+  rcc::RegisterUnitLaneSet RemovedLanes;
+  RemovedLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2));
+  PartialLanes.subtract(RemovedLanes);
+  Context.expect(PartialLanes.lanes(MultiLaneUnit) == rcc::LaneMask::fromRaw(0x1) &&
+                     PartialLanes.contains(MultiLaneUnit, rcc::LaneMask::fromRaw(0x1)) &&
+                     !PartialLanes.intersects(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)),
+                 "RegisterUnit lane sets must preserve partial union and subtraction");
+
+  auto AliasFixture = createFunction("physical-alias", 4, 1);
+  if (!AliasFixture) {
+    Context.expect(false, "physical-alias fixture creation must succeed");
+    return;
+  }
+  const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0));
+  const rcc::Register G0High =
+      rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0High32));
+  auto G0Def = buildDef(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0);
+  auto G0HighUse = buildUse(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0High);
+  if (!G0Def || !G0HighUse) {
+    Context.expect(false, "physical-alias instructions must be built");
+    return;
+  }
+  rcc::MachineAnalysisManager AliasAnalyses;
+  auto AliasRegistered = rcc::registerStage11MachineAnalyses(AliasAnalyses);
+  auto AliasIntervals =
+      AliasRegistered
+          ? AliasAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*AliasFixture->Function, Target)
+          : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                std::unexpected(AliasRegistered.error())};
+  const rcc::RegisterUnitID HighUnit = rcc::RegisterUnitID::fromValue(3);
+  Context.expect(AliasIntervals && (*AliasIntervals)->regUnitRange(HighUnit) != nullptr &&
+                     (*AliasIntervals)->regUnitRange(HighUnit)->segments().size() == 1,
+                 "shared RegisterUnits must connect super-register defs to subregister uses");
+
+  auto MaskFixture = createFunction("regmask", 5, 1);
+  if (!MaskFixture) {
+    Context.expect(false, "RegMask fixture creation must succeed");
+    return;
+  }
+  auto Across = createVReg(*MaskFixture->Function);
+  auto Output = createVReg(*MaskFixture->Function);
+  if (!Across || !Output) {
+    Context.expect(false, "RegMask virtual registers must be created");
+    return;
+  }
+  const auto Mask = rcc::test::createTestCallPreservedMask();
+  auto AcrossDef = buildDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across);
+  auto FirstMask = buildMask(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], Mask);
+  auto AcrossUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across);
+  auto OutputDef =
+      buildMaskedDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output, Mask);
+  auto OutputUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output);
+  if (!AcrossDef || !FirstMask || !AcrossUse || !OutputDef || !OutputUse) {
+    Context.expect(false, "RegMask instructions must be built");
+    return;
+  }
+  rcc::MachineAnalysisManager MaskAnalyses;
+  auto MaskRegistered = rcc::registerStage11MachineAnalyses(MaskAnalyses);
+  auto MaskIntervals =
+      MaskRegistered
+          ? MaskAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*MaskFixture->Function, Target)
+          : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                std::unexpected(MaskRegistered.error())};
+  if (!MaskIntervals) {
+    Context.expect(false, "RegMask intervals must materialize");
+    return;
+  }
+  const rcc::PhysicalRegister Candidate = physical(rcc::test::TestRegister::G0);
+  const rcc::LiveInterval *AcrossInterval = (*MaskIntervals)->interval(*Across);
+  const rcc::LiveInterval *OutputInterval = (*MaskIntervals)->interval(*Output);
+  Context.expect((*MaskIntervals)->regMaskPositions().size() == 2 &&
+                     std::ranges::all_of((*MaskIntervals)->regMaskPositions(),
+                                         [](const rcc::RegMaskPosition &Position) {
+                                           return Position.Position.kind() ==
+                                                  rcc::SlotIndexKind::EarlyClobber;
+                                         }),
+                 "RegMask interference positions must use early-clobber slots");
+  Context.expect(AcrossInterval != nullptr && OutputInterval != nullptr &&
+                     (*MaskIntervals)->regMaskClobbers(*AcrossInterval, Candidate) &&
+                     !(*MaskIntervals)->regMaskClobbers(*OutputInterval, Candidate),
+                 "RegMask queries must reject live-through values but accept same-call outputs");
+  Context.expect((*MaskIntervals)->regUnitRange(rcc::RegisterUnitID::fromValue(1)) == nullptr,
+                 "unused RegMask clobbers must not expand into physical live ranges");
+}
+
+void setRebuildProperties(rcc::MachineFunction &Function) {
+  Function.properties().set(rcc::MachineFunctionProperty::Legalized);
+  Function.properties().set(rcc::MachineFunctionProperty::RegBankSelected);
+  Function.properties().set(rcc::MachineFunctionProperty::Selected);
+  Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
+  Function.properties().set(rcc::MachineFunctionProperty::TiedOpsRewritten);
+}
+
+void testLivenessRebuildAndVerifier(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("rebuild", 6, 2);
+  if (!Fixture) {
+    Context.expect(false, "liveness-rebuild fixture creation must succeed");
+    return;
+  }
+  auto &Function = *Fixture->Function;
+  auto &Entry = *Fixture->Blocks[0];
+  auto &Exit = *Fixture->Blocks[1];
+  auto Edge = Function.cfgUpdater().addSuccessor(Entry, Exit, rcc::BranchProbability::one());
+  const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0));
+  const rcc::Register G1 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G1));
+  auto LiveDef = buildDef(Function, Target, Entry, G0);
+  auto FirstUse = buildUse(Function, Target, Exit, G0);
+  auto LastUse = buildUse(Function, Target, Exit, G0);
+  auto DeadDef = buildDef(Function, Target, Exit, G1);
+  if (!Edge || !LiveDef || !FirstUse || !LastUse || !DeadDef) {
+    Context.expect(false, "liveness-rebuild MachineIR must be constructed");
+    return;
+  }
+  auto StaleLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0));
+  Context.expect(StaleLiveIn.has_value(), "stale live-in setup must succeed");
+  setRebuildProperties(Function);
+
+  rcc::MachinePassManager Pipeline;
+  auto Added = Pipeline.addPass(std::make_unique<rcc::RebuildMachineLivenessPass>());
+  rcc::MachineAnalysisManager Analyses;
+  auto Run = Added ? Pipeline.run(Function, Target, Analyses)
+                   : rcc::Expected<void>{std::unexpected(Added.error())};
+  if (!Run)
+    std::cerr << "liveness rebuild pipeline error: " << Run.error().message() << '\n';
+  Context.expect(Run.has_value() &&
+                     Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness),
+                 "RebuildMachineLiveness must publish TracksLiveness through the pass manager");
+  if (!Run)
+    return;
+  Context.expect(
+      Entry.liveIns().empty() && Exit.liveIns().size() == 1 &&
+          Exit.liveIns().front().PhysReg == physical(rcc::test::TestRegister::G0) &&
+          Exit.liveIns().front().Lanes == rcc::LaneMask::all(),
+      "liveness rebuild must replace stale live-ins with canonical whole-register input");
+  Context.expect(!hasFlag(**LiveDef, 0, rcc::RegisterOperandFlag::Dead) &&
+                     !hasFlag(**FirstUse, 0, rcc::RegisterOperandFlag::Kill) &&
+                     hasFlag(**LastUse, 0, rcc::RegisterOperandFlag::Kill) &&
+                     hasFlag(**DeadDef, 0, rcc::RegisterOperandFlag::Dead),
+                 "reverse reconstruction must derive conservative kill and dead flags");
+  Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
+                 "rebuilt tracked liveness must pass the MachineVerifier");
+
+  rcc::MachineOperand *FirstUseOperand = (*FirstUse)->operandAt(0);
+  if (FirstUseOperand == nullptr) {
+    Context.expect(false, "first use operand must exist");
+    return;
+  }
+  rcc::RegisterOperandFlags StaleFlags = FirstUseOperand->registerFlags();
+  StaleFlags.set(rcc::RegisterOperandFlag::Kill);
+  auto StaleKill = FirstUseOperand->setRegisterFlags(StaleFlags);
+  Context.expect(StaleKill.has_value() && !rcc::MachineVerifier::verify(Function, Target),
+                 "MachineVerifier must reject an overstrong tracked kill flag");
+  StaleFlags.clear(rcc::RegisterOperandFlag::Kill);
+  auto ClearedKill = FirstUseOperand->setRegisterFlags(StaleFlags);
+  Context.expect(ClearedKill.has_value(), "stale kill flag cleanup must succeed");
+  Exit.clearLiveIns();
+  Context.expect(!rcc::MachineVerifier::verify(Function, Target),
+                 "MachineVerifier must reject stale tracked physical live-ins");
+
+  rcc::RebuildMachineLivenessPass Rebuild;
+  auto Repaired = Rebuild.run(Function, Target, Analyses);
+  Context.expect(Repaired && rcc::MachineVerifier::verify(Function, Target),
+                 "a second liveness rebuild must repair stale derived state");
+}
+
+void testFailedRebuildIsAtomic(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("failed-rebuild", 9, 2);
+  if (!Fixture) {
+    Context.expect(false, "failed-rebuild fixture creation must succeed");
+    return;
+  }
+  auto Destination = createVReg(*Fixture->Function);
+  auto Source = createVReg(*Fixture->Function);
+  if (!Destination || !Source) {
+    Context.expect(false, "failed-rebuild virtual registers must be created");
+    return;
+  }
+
+  auto &Predecessor = *Fixture->Blocks[0];
+  auto &PhiBlock = *Fixture->Blocks[1];
+  const auto LiveIn =
+      PhiBlock.addLiveIn(physical(rcc::test::TestRegister::G0), rcc::LaneMask::fromRaw(0x1));
+  rcc::RegisterOperandFlags KillFlags;
+  KillFlags.set(rcc::RegisterOperandFlag::Kill);
+  rcc::MachineIRBuilder Builder(*Fixture->Function, Target);
+  auto Point = Builder.setInsertPoint(PhiBlock);
+  auto Pending = Point ? Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI))
+                       : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())};
+  auto Def = Pending ? Pending->addDef(*Destination)
+                     : rcc::Expected<void>{std::unexpected(Pending.error())};
+  auto Use =
+      Def ? Pending->addUse(*Source, KillFlags) : rcc::Expected<void>{std::unexpected(Def.error())};
+  auto Incoming =
+      Use ? Pending->addBasicBlock(Predecessor) : rcc::Expected<void>{std::unexpected(Use.error())};
+  auto Phi = Incoming ? Pending->build()
+                      : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Incoming.error())};
+  if (!LiveIn || !Phi) {
+    Context.expect(false, "malformed-edge PHI setup must succeed");
+    return;
+  }
+
+  const std::vector<rcc::MachineBasicBlockLiveIn> OriginalLiveIns(PhiBlock.liveIns().begin(),
+                                                                  PhiBlock.liveIns().end());
+  const rcc::RegisterOperandFlags OriginalFlags = (*Phi)->operandAt(1)->registerFlags();
+  auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, Target);
+  Context.expect(!Rebuilt && Rebuilt.error().code() == rcc::ErrorCode::VerificationError &&
+                     std::ranges::equal(PhiBlock.liveIns(), OriginalLiveIns) &&
+                     (*Phi)->operandAt(1)->registerFlags() == OriginalFlags,
+                 "malformed PHI edges must fail without changing live-ins or operand flags");
+}
+
+class DummyAnalysis final {
+public:
+  struct Result final {};
+
+  [[nodiscard]] static rcc::Expected<Result>
+  run(rcc::MachineFunction &, const rcc::TargetDescription &, rcc::MachineAnalysisManager &) {
+    return Result{};
+  }
+};
+
+void testAnalysisRegistrationAndInvalidation(TestContext &Context,
+                                             const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("analysis-invalidation", 7, 1);
+  if (!Fixture) {
+    Context.expect(false, "analysis-invalidation fixture creation must succeed");
+    return;
+  }
+  auto Reg = createVReg(*Fixture->Function);
+  auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg)
+                 : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())};
+  auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg)
+                 : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())};
+  if (!Reg || !Def || !Use) {
+    Context.expect(false, "analysis-invalidation instructions must be built");
+    return;
+  }
+
+  rcc::MachineAnalysisManager Analyses;
+  auto FirstRegistration = rcc::registerStage11MachineAnalyses(Analyses);
+  auto SecondRegistration = rcc::registerStage11MachineAnalyses(Analyses);
+  auto Intervals = FirstRegistration
+                       ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target)
+                       : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                             std::unexpected(FirstRegistration.error())};
+  Context.expect(FirstRegistration && SecondRegistration && Intervals &&
+                     Analyses.cachedResultCount(*Fixture->Function) == 3,
+                 "Stage 11 analyses must register idempotently and materialize dependencies");
+  Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(),
+                      {rcc::MachinePassChange::Frame});
+  Context.expect(Analyses.cachedResultCount(*Fixture->Function) == 3,
+                 "debug-only changes must preserve all liveness analyses");
+  Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(),
+                      {rcc::MachinePassChange::Operands});
+  Context.expect(
+      Analyses.cachedResultCount(*Fixture->Function) == 1 &&
+          Analyses.hasCached(*Fixture->Function,
+                             rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()),
+      "operand changes must retain SlotIndexes while invalidating liveness dependents");
+  auto Recomputed = Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target);
+  Context.expect(Recomputed && Analyses.cachedResultCount(*Fixture->Function) == 3,
+                 "invalidated liveness dependencies must recompute on demand");
+  Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(),
+                      {rcc::MachinePassChange::BlockLayout});
+  Context.expect(
+      Analyses.cachedResultCount(*Fixture->Function) == 1 &&
+          Analyses.hasCached(*Fixture->Function,
+                             rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()),
+      "layout changes must invalidate SlotIndexes and LiveIntervals only");
+
+  rcc::MachineAnalysisManager Atomic;
+  rcc::MachineAnalysisRegistration DummyRegistration;
+  DummyRegistration.Name = "SlotIndexes";
+  auto Dummy = Atomic.registerAnalysis<DummyAnalysis>(std::move(DummyRegistration));
+  auto Rejected = rcc::registerStage11MachineAnalyses(Atomic);
+  Context.expect(
+      Dummy && !Rejected && Atomic.isRegistered(rcc::MachineAnalysisManager::id<DummyAnalysis>()) &&
+          !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()) &&
+          !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()),
+      "failed standard-analysis registration must leave the manager unchanged");
+}
+
+void testRISCVLiveness(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFunction("riscv-liveness", 8, 1);
+  if (!Target || !Fixture) {
+    Context.expect(false, "RV64GC liveness fixture creation must succeed");
+    return;
+  }
+  auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5);
+  auto X6 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X6);
+  auto X7 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X7);
+  if (!X5 || !X6 || !X7) {
+    Context.expect(false, "RV64GC physical registers must resolve");
+    return;
+  }
+  auto BuildADDI = [&](rcc::PhysicalRegister Destination, rcc::PhysicalRegister Source,
+                       std::int64_t Immediate) -> rcc::Expected<rcc::MachineInstr *> {
+    rcc::MachineIRBuilder Builder(*Fixture->Function, *Target);
+    auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]);
+    if (!Point)
+      return std::unexpected(Point.error());
+    auto Pending = Builder.buildInstr(
+        rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI)));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    auto Def = Pending->addDef(rcc::Register::fromPhysical(Destination));
+    if (!Def)
+      return std::unexpected(Def.error());
+    auto Use = Pending->addUse(rcc::Register::fromPhysical(Source));
+    if (!Use)
+      return std::unexpected(Use.error());
+    auto Imm = Pending->addImmediate(Immediate);
+    if (!Imm)
+      return std::unexpected(Imm.error());
+    return Pending->build();
+  };
+  auto First = BuildADDI(*X6, *X5, 1);
+  auto Second = BuildADDI(*X7, *X6, 2);
+  if (!First || !Second) {
+    Context.expect(false, "RV64GC ADDI instructions must be built");
+    return;
+  }
+  rcc::MachineAnalysisManager Analyses;
+  auto Registered = rcc::registerStage11MachineAnalyses(Analyses);
+  auto Intervals = Registered
+                       ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, *Target)
+                       : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{
+                             std::unexpected(Registered.error())};
+  const auto Unit =
+      rcc::RegisterUnitID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterUnit::U_X6));
+  Context.expect(Intervals && (*Intervals)->regUnitRange(Unit) != nullptr &&
+                     (*Intervals)->regUnitRange(Unit)->segments().size() == 1,
+                 "production RV64GC register units must participate in LiveIntervals");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = createTarget();
+  Context.expect(Target.has_value(), "liveness TestTarget must be created");
+  if (!Target)
+    return Context.result();
+
+  testLiveRange(Context);
+  testSlotIndexes(Context, *Target);
+  testCFGAndValueNumbers(Context, *Target);
+  testLaneSubrangesAndEarlyClobber(Context, *Target);
+  testPhysicalUnitsAndRegMasks(Context, *Target);
+  testLivenessRebuildAndVerifier(Context, *Target);
+  testFailedRebuildIsAtomic(Context, *Target);
+  testAnalysisRegistrationAndInvalidation(Context, *Target);
+  testRISCVLiveness(Context);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/MachineSSAExitTest.cpp b/backend/unittests/CodeGen/MachineSSAExitTest.cpp
index 7c65345..a3940c2 100644
--- a/backend/unittests/CodeGen/MachineSSAExitTest.cpp
+++ b/backend/unittests/CodeGen/MachineSSAExitTest.cpp
@@ -9,6 +9,7 @@
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineIRBuilder.h"
 #include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachinePass.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
@@ -413,13 +414,18 @@ buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
   return Pending->build();
 }
 
-void setSelectedSSAProperties(rcc::MachineFunction &Function) {
+[[nodiscard]] rcc::Expected<void> setSelectedSSAProperties(rcc::MachineFunction &Function,
+                                                           const rcc::TargetDescription &Target) {
+  auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
   for (rcc::MachineFunctionProperty Property :
        {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
         rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
         rcc::MachineFunctionProperty::Selected}) {
     Function.properties().set(Property);
   }
+  return {};
 }
 
 [[nodiscard]] rcc::Expected<void> runPHIElimination(rcc::MachineFunction &Function,
@@ -531,7 +537,10 @@ void testParallelPHIsAndPlacement(TestContext &Context, const rcc::TargetDescrip
                                           KilledUse, {}, {rcc::RegisterOperandFlag::Kill}) &&
                      buildJump(Function, Target, Backedge, Header),
                  "parallel PHI backedge must be populated");
-  setSelectedSSAProperties(Function);
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "parallel PHI liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
 
   auto Run = runPHIElimination(Function, Target, Info);
   Context.expect(Run.has_value(), "parallel PHI elimination must succeed");
@@ -666,7 +675,14 @@ void testCriticalEdgeAndPhysicalLiveIn(TestContext &Context, const rcc::TargetDe
       std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, &Other}};
   Context.expect(buildPhi(Function, Target, Merge, *Destination, Incoming).has_value(),
                  "critical-edge PHI must be built");
-  setSelectedSSAProperties(Function);
+  const std::array G1Use{rcc::Register::fromPhysical(G1)};
+  Context.expect(buildRegisterInstruction(Function, Target, Merge, testOpcode(UseOpcode), {}, G1Use)
+                     .has_value(),
+                 "merge block must consume its inherited physical live-in");
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "critical-edge PHI liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
 
   auto Run = runPHIElimination(Function, Target, Info);
   Context.expect(Run.has_value(), "critical-edge PHI elimination must succeed");
@@ -730,7 +746,8 @@ void testUndefAndFailureAtomicity(TestContext &Context, const rcc::TargetDescrip
                   {rcc::RegisterOperandFlag::Undef})) {
       return Fixture;
     }
-    setSelectedSSAProperties(*Fixture.Function);
+    Context.expect(setSelectedSSAProperties(*Fixture.Function, Target).has_value(),
+                   "undef PHI liveness rebuild must succeed");
     return Fixture;
   };
 
@@ -887,7 +904,10 @@ void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::Target
   auto Return = Builder.buildInstr(testOpcode(ReturnOpcode));
   Context.expect(Return && Return->build(), "two-address return must be built");
 
-  setSelectedSSAProperties(Function);
+  auto InitialLiveness = setSelectedSSAProperties(Function, Target);
+  Context.expect(InitialLiveness.has_value(), "two-address liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
   Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
   rcc::MachinePassManager Pipeline;
   Context.expect(Pipeline.addPass(std::make_unique<rcc::TwoAddressRewritePass>(Info)).has_value(),
@@ -939,18 +959,20 @@ void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::Target
                                    Copy->operandAt(0)->subReg() == rcc::test::TestSubReg::Low32;
                           }),
       "INSERT_SUBREG must copy its inserted value into the requested destination lane");
-  Context.expect(
-      std::ranges::all_of(Function.allInstructions(),
-                          [](const rcc::MachineInstr *MI) {
-                            if (MI->parent() == nullptr)
-                              return true;
-                            return std::ranges::none_of(
-                                MI->operands(), [](const rcc::MachineOperand &Op) {
-                                  return Op.registerFlags().has(rcc::RegisterOperandFlag::Kill) ||
-                                         Op.registerFlags().has(rcc::RegisterOperandFlag::Dead);
-                                });
-                          }),
-      "two-address rewrite must conservatively clear stale kill/dead flags");
+  const bool HasKill = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
+    return MI->parent() != nullptr &&
+           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
+             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Kill);
+           });
+  });
+  const bool HasDead = std::ranges::any_of(Function.allInstructions(), [](const auto *MI) {
+    return MI->parent() != nullptr &&
+           std::ranges::any_of(MI->operands(), [](const rcc::MachineOperand &Operand) {
+             return Operand.registerFlags().has(rcc::RegisterOperandFlag::Dead);
+           });
+  });
+  Context.expect(HasKill && HasDead,
+                 "two-address rewrite must rebuild precise kill and dead flags");
   Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(),
                  "two-address and subregister expansion result must verify");
 
@@ -983,7 +1005,10 @@ void testTwoAddressAndSubregisterPseudos(TestContext &Context, const rcc::Target
                  "two-address atomicity tied instruction must build");
   if (!AtomicInstruction)
     return;
-  setSelectedSSAProperties(*AtomicFixture.Function);
+  auto AtomicLiveness = setSelectedSSAProperties(*AtomicFixture.Function, Target);
+  Context.expect(AtomicLiveness.has_value(), "two-address atomicity liveness rebuild must succeed");
+  if (!AtomicLiveness)
+    return;
   AtomicFixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs);
   const std::size_t AtomicInstructionsBefore = AtomicFixture.Function->allInstructions().size();
   const std::size_t AtomicRegistersBefore =
diff --git a/backend/unittests/CodeGen/TargetRegisterInfoTest.cpp b/backend/unittests/CodeGen/TargetRegisterInfoTest.cpp
index 49f23c0..2c44237 100644
--- a/backend/unittests/CodeGen/TargetRegisterInfoTest.cpp
+++ b/backend/unittests/CodeGen/TargetRegisterInfoTest.cpp
@@ -187,6 +187,12 @@ void testDescriptionRejection(TestContext &Context) {
   }
   {
     auto Description = rcc::test::createTestTargetRegisterInfoDescription();
+    Description.PhysicalRegisters[2].Units.front().Lanes = rcc::LaneMask::fromRaw(0x3);
+    Context.expect(!rcc::TargetRegisterInfo::create(std::move(Description)),
+                   "register-unit views with different lane counts must be rejected");
+  }
+  {
+    auto Description = rcc::test::createTestTargetRegisterInfoDescription();
     Description.RegisterClasses.front().SuperClasses.push_back(
         rcc::test::TestRegisterClass::GPR64Alloc);
     Context.expect(!rcc::TargetRegisterInfo::create(std::move(Description)),
diff --git a/backend/unittests/MIR/MIRDocumentTest.cpp b/backend/unittests/MIR/MIRDocumentTest.cpp
index 7ea82c1..1117bf1 100644
--- a/backend/unittests/MIR/MIRDocumentTest.cpp
+++ b/backend/unittests/MIR/MIRDocumentTest.cpp
@@ -278,7 +278,7 @@ private:
       rcc::MachineOperand::Kind::GlobalSymbol,
       rcc::MachineOperand::Kind::ExternalSymbol,
   };
-  Global.Operands.push_back(std::move(GlobalOperand));
+  Global.Operands.push_back(GlobalOperand);
   Global.Flags.set(rcc::InstructionFlag::ProducesCode);
 
   std::vector<rcc::InstructionDescriptor> Descriptors;
@@ -372,6 +372,7 @@ machineMetadataNodes:
   - '!10 = distinct !{!0, !"machine", null}'
 body: |
   bb.0.entry (%ir-block.entry):
+    liveins: $g0
     %7:gpr64 = TEST_LOAD $g0 :: (load syncscope("agent") acquire 8 from %ir.slot, align 8)
     TEST_GLOBAL @ordinary
     TEST_BRANCH %bb.0.entry
diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp
index 1440855..8e1f5a2 100644
--- a/backend/unittests/Target/RISCVSSAExitTest.cpp
+++ b/backend/unittests/Target/RISCVSSAExitTest.cpp
@@ -6,6 +6,7 @@
 #include "rcc/CodeGen/MachineFunction.h"
 #include "rcc/CodeGen/MachineIRBuilder.h"
 #include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
 #include "rcc/CodeGen/MachineOperand.h"
 #include "rcc/CodeGen/MachinePass.h"
 #include "rcc/CodeGen/MachineSSAExit.h"
@@ -167,13 +168,18 @@ buildPhi(rcc::MachineFunction &Function, const rcc::TargetDescription &Target,
   return Result;
 }
 
-void setSelectedSSAProperties(rcc::MachineFunction &Function) {
+[[nodiscard]] rcc::Expected<void> setSelectedSSAProperties(rcc::MachineFunction &Function,
+                                                           const rcc::TargetDescription &Target) {
+  auto Rebuilt = rcc::rebuildMachineLiveness(Function, Target);
+  if (!Rebuilt)
+    return std::unexpected(Rebuilt.error());
   for (rcc::MachineFunctionProperty Property :
        {rcc::MachineFunctionProperty::IsSSA, rcc::MachineFunctionProperty::TracksLiveness,
         rcc::MachineFunctionProperty::Legalized, rcc::MachineFunctionProperty::RegBankSelected,
         rcc::MachineFunctionProperty::Selected}) {
     Function.properties().set(Property);
   }
+  return {};
 }
 
 void testBehaviorAndCopyLegality(TestContext &Context, const rcc::TargetDescription &Target) {
@@ -286,7 +292,10 @@ void testRV64GCCriticalEdge(TestContext &Context, const rcc::TargetDescription &
       std::pair<rcc::Register, rcc::MachineBasicBlock *>{*OtherValue, *Other}};
   Context.expect(buildPhi(**Function, Target, **Merge, *Destination, Incoming).has_value(),
                  "RV64GC critical-edge PHI must be built");
-  setSelectedSSAProperties(**Function);
+  auto InitialLiveness = setSelectedSSAProperties(**Function, Target);
+  Context.expect(InitialLiveness.has_value(), "RV64GC PHI liveness rebuild must succeed");
+  if (!InitialLiveness)
+    return;
 
   rcc::MachinePassManager Pipeline;
   Context.expect(Pipeline.addPass(std::make_unique<rcc::PHIEliminationPass>(rcc::riscv::ssaInfo()))