[CodeGen] Implement machine liveness analysis

6 files changed, 949 insertions, 21 deletions

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()))