[CodeGen] Split machine liveness components

1 files changed, 316 insertions, 0 deletions

diff --git a/backend/unittests/CodeGen/LiveVariablesTest.cpp b/backend/unittests/CodeGen/LiveVariablesTest.cpp
new file mode 100644
index 0000000..577ecde
--- /dev/null
+++ b/backend/unittests/CodeGen/LiveVariablesTest.cpp
@@ -0,0 +1,316 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/LiveVariables.h"
+
+#include "LiveTestSupport.h"
+#include "rcc/CodeGen/LiveIntervals.h"
+#include "rcc/Target/RISCV/RISCVInstructions.h"
+#include "rcc/Target/RISCV/RISCVRegisters.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+namespace {
+
+using namespace rcc::test::liveness;
+
+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");
+
+  auto ConservativeLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0));
+  Context.expect(ConservativeLiveIn.has_value() &&
+                     rcc::MachineVerifier::verify(Function, Target).has_value(),
+                 "MachineVerifier must accept conservative physical live-ins");
+  Entry.clearLiveIns();
+
+  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 testTrackedLiveThroughPhysicalRegister(TestContext &Context,
+                                            const rcc::TargetDescription &Target) {
+  auto Fixture = createFunction("tracked-live-through", 11, 2);
+  if (!Fixture) {
+    Context.expect(false, "tracked live-through fixture creation must succeed");
+    return;
+  }
+  auto &Function = *Fixture->Function;
+  auto &Predecessor = *Fixture->Blocks[0];
+  auto &Successor = *Fixture->Blocks[1];
+  const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0));
+  auto Edge =
+      Function.cfgUpdater().addSuccessor(Predecessor, Successor, rcc::BranchProbability::one());
+  auto Use = buildUse(Function, Target, Successor, G0);
+  auto LiveIn = Successor.addLiveIn(physical(rcc::test::TestRegister::G0));
+  if (!Edge || !Use || !LiveIn) {
+    Context.expect(false, "tracked live-through MachineIR must be constructed");
+    return;
+  }
+
+  Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness);
+  Context.expect(rcc::verifyTrackedMachineLiveness(Function, Target).has_value() &&
+                     Predecessor.liveIns().empty(),
+                 "a predecessor must not declare a physical register used only by its successor");
+  Successor.clearLiveIns();
+  Context.expect(!rcc::verifyTrackedMachineLiveness(Function, Target),
+                 "a block must declare a physical register that it reads before defining");
+}
+
+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 testRISCVReservedRegisterLiveness(TestContext &Context) {
+  auto Target = rcc::riscv::createTargetDescription();
+  auto Fixture = createFunction("riscv-reserved-liveness", 10, 1);
+  if (!Target || !Fixture) {
+    Context.expect(false, "RV64GC reserved-register liveness fixture creation must succeed");
+    return;
+  }
+  auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0);
+  auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5);
+  if (!X0 || !X5) {
+    Context.expect(false, "RV64GC reserved-register fixture registers must resolve");
+    return;
+  }
+
+  rcc::MachineIRBuilder Builder(*Fixture->Function, *Target);
+  auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]);
+  auto Pending = Point ? Builder.buildInstr(rcc::Opcode::fromValue(
+                             static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI)))
+                       : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())};
+  auto Def = Pending ? Pending->addDef(rcc::Register::fromPhysical(*X5))
+                     : rcc::Expected<void>{std::unexpected(Pending.error())};
+  auto Use = Def ? Pending->addUse(rcc::Register::fromPhysical(*X0))
+                 : rcc::Expected<void>{std::unexpected(Def.error())};
+  auto Immediate =
+      Use ? Pending->addImmediate(1) : rcc::Expected<void>{std::unexpected(Use.error())};
+  auto Instruction = Immediate
+                         ? Pending->build()
+                         : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Immediate.error())};
+  auto DeadDef =
+      Instruction ? Builder.buildInstr(rcc::Opcode::fromValue(
+                        static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI)))
+                  : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Instruction.error())};
+  auto DeadDefDestination = DeadDef ? DeadDef->addDef(rcc::Register::fromPhysical(*X0))
+                                    : rcc::Expected<void>{std::unexpected(DeadDef.error())};
+  auto DeadDefSource = DeadDefDestination
+                           ? DeadDef->addUse(rcc::Register::fromPhysical(*X0))
+                           : rcc::Expected<void>{std::unexpected(DeadDefDestination.error())};
+  auto DeadDefImmediate = DeadDefSource
+                              ? DeadDef->addImmediate(0)
+                              : rcc::Expected<void>{std::unexpected(DeadDefSource.error())};
+  auto DeadDefInstruction =
+      DeadDefImmediate
+          ? DeadDef->build()
+          : rcc::Expected<rcc::MachineInstr *>{std::unexpected(DeadDefImmediate.error())};
+  if (!Instruction || !DeadDefInstruction) {
+    Context.expect(false, "RV64GC reserved-register liveness instruction must be built");
+    return;
+  }
+
+  auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, *Target);
+  const rcc::MachineOperand *ZeroUse = (*Instruction)->operandAt(1);
+  const rcc::MachineOperand *ZeroDef = (*DeadDefInstruction)->operandAt(0);
+  const rcc::MachineOperand *DeadDefZeroUse = (*DeadDefInstruction)->operandAt(1);
+  Context.expect(Rebuilt && Fixture->Blocks[0]->liveIns().empty() && ZeroUse != nullptr &&
+                     !ZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill) &&
+                     ZeroDef != nullptr &&
+                     ZeroDef->registerFlags().has(rcc::RegisterOperandFlag::Dead) &&
+                     DeadDefZeroUse != nullptr &&
+                     !DeadDefZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill),
+                 "reserved uses must remain available while dead defs retain precise liveness");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = createTarget();
+  Context.expect(Target.has_value(), "liveness TestTarget must be created");
+  if (!Target)
+    return Context.result();
+
+  testLivenessRebuildAndVerifier(Context, *Target);
+  testTrackedLiveThroughPhysicalRegister(Context, *Target);
+  testFailedRebuildIsAtomic(Context, *Target);
+  testAnalysisRegistrationAndInvalidation(Context, *Target);
+  testRISCVReservedRegisterLiveness(Context);
+  return Context.result();
+}