[CodeGen] Implement machine optimization and scheduling

5 files changed, 1365 insertions, 0 deletions

diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt
index 65d9168..1b66194 100644
--- a/backend/unittests/CodeGen/CMakeLists.txt
+++ b/backend/unittests/CodeGen/CMakeLists.txt
@@ -20,8 +20,10 @@ set(
   MachineLivenessTest.cpp
   MachineMetadataTest.cpp
   MachineOperandTest.cpp
+  MachineOptimizationTest.cpp
   MachinePassTest.cpp
   MachinePipelinePassesTest.cpp
+  MachineSchedulingTest.cpp
   PBQPTest.cpp
   RegisterAllocationTest.cpp
   MachineSSAExitTest.cpp
@@ -355,6 +357,22 @@ target_link_libraries(
 
 add_test(NAME RCCBackend.CodeGen.MachineAnalyses COMMAND RCCBackendCodeGenMachineAnalysesTests)
 
+add_executable(RCCBackendCodeGenMachineOptimizationTests MachineOptimizationTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineOptimizationTests)
+target_link_libraries(
+  RCCBackendCodeGenMachineOptimizationTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV
+)
+add_test(NAME RCCBackend.CodeGen.MachineOptimization COMMAND RCCBackendCodeGenMachineOptimizationTests)
+
+add_executable(RCCBackendCodeGenMachineSchedulingTests MachineSchedulingTest.cpp)
+rcc_backend_configure_target(RCCBackendCodeGenMachineSchedulingTests)
+target_link_libraries(
+  RCCBackendCodeGenMachineSchedulingTests
+  PRIVATE RCCBackend::CodeGen RCCBackend::RISCV
+)
+add_test(NAME RCCBackend.CodeGen.MachineScheduling COMMAND RCCBackendCodeGenMachineSchedulingTests)
+
 add_executable(RCCBackendCodeGenMachineSSAExitTests MachineSSAExitTest.cpp)
 rcc_backend_configure_target(RCCBackendCodeGenMachineSSAExitTests)
 target_link_libraries(
@@ -439,8 +457,10 @@ rcc_backend_register_format_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
@@ -479,8 +499,10 @@ rcc_backend_register_tidy_files(
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePassTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePassesTest.cpp"
+  "${CMAKE_CURRENT_SOURCE_DIR}/MachineSchedulingTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/PBQPTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/RegisterAllocationTest.cpp"
   "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExitTest.cpp"
diff --git a/backend/unittests/CodeGen/InstructionDescriptorTest.cpp b/backend/unittests/CodeGen/InstructionDescriptorTest.cpp
index 424d2e4..687e723 100644
--- a/backend/unittests/CodeGen/InstructionDescriptorTest.cpp
+++ b/backend/unittests/CodeGen/InstructionDescriptorTest.cpp
@@ -86,6 +86,7 @@ private:
   RegisterOrImmediate.Kinds = {
       rcc::MachineOperand::Kind::Register,
       rcc::MachineOperand::Kind::Immediate,
+      rcc::MachineOperand::Kind::GlobalSymbol,
   };
   RegisterOrImmediate.RegisterRole = rcc::RegisterOperandRole::Use;
   RegisterOrImmediate.ImmediatePredicate = rcc::ImmediatePredicateID::fromValue(1);
@@ -218,6 +219,15 @@ void testOperandValidation(TestContext &Context) {
           .has_value(),
       "matching roles, constraints, flags, and predicate must validate");
 
+  std::vector<rcc::MachineOperand> SymbolOperands;
+  SymbolOperands.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Define}));
+  SymbolOperands.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
+  SymbolOperands.push_back(*rcc::MachineOperand::globalSymbol("object", 0, 0x1));
+  Context.expect(
+      InstructionSet->validateExplicitOperands(rcc::Opcode::fromValue(1), SymbolOperands, RegInfo)
+          .has_value(),
+      "an immediate predicate must not reject another allowed symbolic operand kind");
+
   std::vector<rcc::MachineOperand> WrongRole;
   WrongRole.push_back(*registerOperand(*Destination, {rcc::RegisterOperandFlag::Use}));
   WrongRole.push_back(*registerOperand(*Source, {rcc::RegisterOperandFlag::Use}));
diff --git a/backend/unittests/CodeGen/MachineOperandTest.cpp b/backend/unittests/CodeGen/MachineOperandTest.cpp
index 1b246ca..3cc7060 100644
--- a/backend/unittests/CodeGen/MachineOperandTest.cpp
+++ b/backend/unittests/CodeGen/MachineOperandTest.cpp
@@ -264,6 +264,48 @@ void testOperandFactories(TestContext &Context) {
                  "detached operand cloning must preserve the new payload kinds");
 }
 
+void testFrameIndexRewrite(TestContext &Context) {
+  auto Function = createFunction(Context, 5, "frame-index-rewrite");
+  if (!Function)
+    return;
+  rcc::MachineBasicBlock *Block = appendBlock(Context, *Function);
+  auto Align = rcc::Alignment::create(8);
+  if (Block == nullptr || !Align)
+    return;
+
+  rcc::StackObjectDesc Description;
+  Description.Kind = rcc::StackObjectKind::SpillSlot;
+  Description.Size = 8;
+  Description.Align = *Align;
+  auto First = Function->frameInfo().createObject(Description);
+  auto Second = Function->frameInfo().createObject(Description);
+  Context.expect(First.has_value() && Second.has_value(),
+                 "frame-index rewrite objects must be created");
+  if (!First || !Second)
+    return;
+
+  auto Instruction = Function->createInstruction(rcc::Opcode::fromValue(OperandOpcode));
+  Context.expect(Instruction.has_value() &&
+                     (*Instruction)->addOperand(rcc::MachineOperand::frameIndex(*First, 4)) &&
+                     Block->appendInstruction(**Instruction),
+                 "frame-index rewrite operand must be linked to its function");
+  if (!Instruction || (*Instruction)->operandCount() == 0)
+    return;
+  rcc::MachineOperand *Operand = (*Instruction)->operandAt(0);
+  Context.expect(Operand != nullptr && Operand->setFrameIndex(*Second).has_value() &&
+                     Operand->getIf<rcc::FrameIndexOperand>()->Index == *Second &&
+                     Operand->getIf<rcc::FrameIndexOperand>()->Offset == 4,
+                 "setFrameIndex must rewrite only the object identity");
+
+  const rcc::FrameIndex Unknown = rcc::FrameIndex::fromValue(99);
+  Context.expect(Operand != nullptr && !Operand->setFrameIndex(Unknown) &&
+                     Operand->getIf<rcc::FrameIndexOperand>()->Index == *Second,
+                 "setFrameIndex must reject an unknown attached object atomically");
+  auto Immediate = rcc::MachineOperand::immediate(0);
+  Context.expect(!Immediate.setFrameIndex(*First),
+                 "setFrameIndex must reject non-frame-index operands");
+}
+
 void testCFIInfo(TestContext &Context) {
   const auto R1 = rcc::DwarfRegisterNumber::fromValue(1);
   const auto R2 = rcc::DwarfRegisterNumber::fromValue(2);
@@ -476,6 +518,7 @@ int main() {
   TestContext Context;
   testIntegerImmediate(Context);
   testOperandFactories(Context);
+  testFrameIndexRewrite(Context);
   testCFIInfo(Context);
   testBuilderVerifierAndClone(Context);
   return Context.result();
diff --git a/backend/unittests/CodeGen/MachineOptimizationTest.cpp b/backend/unittests/CodeGen/MachineOptimizationTest.cpp
new file mode 100644
index 0000000..8d01a65
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineOptimizationTest.cpp
@@ -0,0 +1,772 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineCFGUpdater.h"
+#include "rcc/CodeGen/MachineCSE.h"
+#include "rcc/CodeGen/MachineCombiner.h"
+#include "rcc/CodeGen/MachineDCE.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLICM.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineMemOperand.h"
+#include "rcc/CodeGen/MachineMemoryFolding.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineSink.h"
+#include "rcc/CodeGen/TargetMemoryFolding.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+
+namespace {
+
+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;
+};
+
+struct Fixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  rcc::MachineBasicBlock *Entry = nullptr;
+};
+
+[[nodiscard]] rcc::Opcode opcode(rcc::riscv::InstructionOpcode Value) noexcept;
+
+class TestMemoryFoldingInfo final : public rcc::TargetMemoryFoldingInfo {
+public:
+  explicit TestMemoryFoldingInfo(bool DropMemory = false) noexcept : DropMemory(DropMemory) {}
+
+  [[nodiscard]] rcc::Expected<bool>
+  canFoldMemoryOperand(const rcc::MachineInstr &Consumer, std::size_t OperandIndex,
+                       const rcc::MachineInstr &MemoryInstruction, const rcc::MachineFunction &,
+                       const rcc::TargetDescription &) const override {
+    return Consumer.opcode() == opcode(rcc::riscv::InstructionOpcode::ADDI) && OperandIndex == 1 &&
+           MemoryInstruction.opcode() == opcode(rcc::riscv::InstructionOpcode::LD);
+  }
+
+  [[nodiscard]] rcc::Expected<rcc::MachineInstr *>
+  foldMemoryOperand(rcc::MachineInstr &Consumer, std::size_t, rcc::MachineInstr &MemoryInstruction,
+                    rcc::MachineFunction &Function,
+                    const rcc::TargetDescription &Target) const override {
+    const rcc::MachineOperand *DestinationOperand = Consumer.operandAt(0);
+    const rcc::MachineOperand *BaseOperand = MemoryInstruction.operandAt(1);
+    const rcc::MachineOperand *OffsetOperand = MemoryInstruction.operandAt(2);
+    const rcc::Register *Destination =
+        DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf<rcc::Register>();
+    const rcc::Register *Base =
+        BaseOperand == nullptr ? nullptr : BaseOperand->getIf<rcc::Register>();
+    const std::int64_t *Offset =
+        OffsetOperand == nullptr ? nullptr : OffsetOperand->getIf<std::int64_t>();
+    rcc::MachineBasicBlock *Block = Consumer.parent();
+    if (Destination == nullptr || Base == nullptr || Offset == nullptr || Block == nullptr ||
+        MemoryInstruction.parent() != Block) {
+      return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                 "test memory fold received an invalid candidate");
+    }
+
+    rcc::MachineIRBuilder Builder(Function, Target);
+    if (auto Point = Builder.setInsertPointBefore(Consumer); !Point)
+      return std::unexpected(Point.error());
+    auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::LD));
+    if (!Pending)
+      return std::unexpected(Pending.error());
+    if (auto Added = Pending->addDef(*Destination); !Added)
+      return std::unexpected(Added.error());
+    if (auto Added = Pending->addUse(*Base); !Added)
+      return std::unexpected(Added.error());
+    if (auto Added = Pending->addImmediate(*Offset); !Added)
+      return std::unexpected(Added.error());
+    for (const rcc::MachineMemOperand *Memory : MemoryInstruction.memOperands()) {
+      if (Memory == nullptr)
+        return rcc::makeUnexpected(rcc::ErrorCode::VerificationError,
+                                   "test memory fold received a null MMO");
+      if (auto Added = Pending->addMemOperand(*Memory); !Added)
+        return std::unexpected(Added.error());
+    }
+    auto Folded = Pending->build();
+    if (!Folded)
+      return std::unexpected(Folded.error());
+    if (DropMemory) {
+      while (!(*Folded)->memOperands().empty()) {
+        if (auto Erased = (*Folded)->eraseMemOperand(0); !Erased)
+          return std::unexpected(Erased.error());
+      }
+    }
+    if (auto Removed = Block->removeInstruction(MemoryInstruction); !Removed)
+      return std::unexpected(Removed.error());
+    if (auto Removed = Block->removeInstruction(Consumer); !Removed)
+      return std::unexpected(Removed.error());
+    return *Folded;
+  }
+
+  [[nodiscard]] rcc::Expected<bool>
+  unfoldMemoryOperand(rcc::MachineInstr &, rcc::MachineFunction &,
+                      const rcc::TargetDescription &) const override {
+    return false;
+  }
+
+  [[nodiscard]] rcc::Expected<std::optional<rcc::MemorySize>>
+  getFoldedMemorySize(const rcc::MachineInstr &, const rcc::MachineFunction &,
+                      const rcc::TargetDescription &) const override {
+    auto Size = rcc::MemorySize::fixed(8);
+    if (!Size)
+      return std::unexpected(Size.error());
+    return std::optional<rcc::MemorySize>(*Size);
+  }
+
+private:
+  bool DropMemory;
+};
+
+[[nodiscard]] rcc::Opcode opcode(rcc::riscv::InstructionOpcode Value) noexcept {
+  return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] Fixture makeFixture(TestContext &Context, std::string Name, std::uint64_t ID) {
+  auto Function =
+      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  Context.expect(Function.has_value(), "optimization fixture function creation must succeed");
+  if (!Function)
+    return {};
+  auto Entry = (*Function)->createBasicBlock();
+  Context.expect(Entry.has_value(), "optimization fixture block creation must succeed");
+  if (!Entry || !(*Function)->appendBlock(**Entry))
+    return {};
+  (*Function)->properties().set(rcc::MachineFunctionProperty::IsSSA);
+  (*Function)->properties().set(rcc::MachineFunctionProperty::Legalized);
+  (*Function)->properties().set(rcc::MachineFunctionProperty::RegBankSelected);
+  (*Function)->properties().set(rcc::MachineFunctionProperty::Selected);
+  return {std::move(*Function), *Entry};
+}
+
+void setPostRAProperties(rcc::MachineFunction &Function) {
+  Function.properties().clear(rcc::MachineFunctionProperty::IsSSA);
+  Function.properties().set(rcc::MachineFunctionProperty::NoPHIs);
+  Function.properties().set(rcc::MachineFunctionProperty::TiedOpsRewritten);
+  Function.properties().set(rcc::MachineFunctionProperty::NoVRegs);
+  Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness);
+}
+
+[[nodiscard]] rcc::Register makeGPR(TestContext &Context, rcc::MachineFunction &Function) {
+  auto Type = rcc::LLT::makeInteger(64);
+  auto Reg = Type ? Function.registerInfo().createVirtualRegister(*Type)
+                  : rcc::Expected<rcc::Register>(std::unexpected(
+                        rcc::Error(rcc::ErrorCode::InternalError, "test LLT creation failed")));
+  Context.expect(Reg.has_value(), "optimization virtual register creation must succeed");
+  if (!Reg)
+    return {};
+  const auto Bank =
+      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
+  const auto Class =
+      rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR));
+  Context.expect(Function.registerInfo().setRegisterBank(*Reg, Bank).has_value() &&
+                     Function.registerInfo().setRegisterClass(*Reg, Class).has_value(),
+                 "optimization register constraints must be assigned");
+  return *Reg;
+}
+
+[[nodiscard]] rcc::PhysicalRegister physical(TestContext &Context,
+                                             rcc::riscv::PhysicalRegisterID ID) {
+  auto Reg = rcc::riscv::physicalRegister(ID);
+  Context.expect(Reg.has_value(), "optimization physical register lookup must succeed");
+  return Reg.value_or(rcc::PhysicalRegister{});
+}
+
+[[nodiscard]] rcc::MachineInstr *buildADDI(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                           rcc::Register Destination, rcc::Register Source,
+                                           std::int64_t Immediate) {
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADDI));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Source) ||
+      !Pending->addImmediate(Immediate)) {
+    Context.expect(false, "ADDI construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "ADDI insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+[[nodiscard]] rcc::MachineInstr *buildADD(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                          rcc::Register Destination, rcc::Register Left,
+                                          rcc::Register Right) {
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADD));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Left) ||
+      !Pending->addUse(Right)) {
+    Context.expect(false, "ADD construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "ADD insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+[[nodiscard]] const rcc::MachineMemOperand *
+makeMemory(TestContext &Context, rcc::MachineFunction &Function, bool Store, bool Invariant) {
+  auto Size = rcc::MemorySize::fixed(8);
+  auto Align = rcc::Alignment::create(8);
+  Context.expect(Size.has_value() && Align.has_value(), "memory shape creation must succeed");
+  if (!Size || !Align)
+    return nullptr;
+  rcc::MemoryAccessFlags Flags{Store ? rcc::MemoryAccessFlag::Store : rcc::MemoryAccessFlag::Load};
+  if (Invariant) {
+    Flags.set(rcc::MemoryAccessFlag::Invariant);
+    Flags.set(rcc::MemoryAccessFlag::Dereferenceable);
+  }
+  rcc::MachineMemOperandDesc Description;
+  Description.Accesses = Flags;
+  Description.Size = *Size;
+  Description.Align = *Align;
+  Description.Base = Invariant ? rcc::MemoryBase::constantPoolPseudo() : rcc::MemoryBase::stack();
+  auto Memory = Function.createMemOperand(std::move(Description));
+  Context.expect(Memory.has_value(), "memory operand creation must succeed");
+  return Memory.value_or(nullptr);
+}
+
+[[nodiscard]] rcc::MachineInstr *buildStore(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                            rcc::Register Value, rcc::PhysicalRegister StackPointer,
+                                            const rcc::MachineMemOperand &Memory) {
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::SD));
+  if (!Pending || !Pending->addUse(Value) ||
+      !Pending->addUse(rcc::Register::fromPhysical(StackPointer)) || !Pending->addImmediate(0) ||
+      !Pending->addMemOperand(Memory)) {
+    Context.expect(false, "store construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "store insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+[[nodiscard]] rcc::MachineInstr *buildLoad(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                           rcc::Register Destination, rcc::Register Address,
+                                           const rcc::MachineMemOperand &Memory) {
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::LD));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Address) ||
+      !Pending->addImmediate(0) || !Pending->addMemOperand(Memory)) {
+    Context.expect(false, "load construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "load insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+void testDCEFixedPointAndDebugUses(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "dce", 1);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "DCE insert point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::PhysicalRegister X2 = physical(Context, rcc::riscv::PhysicalRegisterID::X2);
+
+  const rcc::Register LiveRoot = makeGPR(Context, *Fixture.Function);
+  const rcc::Register LiveValue = makeGPR(Context, *Fixture.Function);
+  const rcc::Register DeadRoot = makeGPR(Context, *Fixture.Function);
+  const rcc::Register DeadValue = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, LiveRoot, rcc::Register::fromPhysical(X0), 1);
+  (void)buildADDI(Context, Builder, LiveValue, LiveRoot, 2);
+  (void)buildADDI(Context, Builder, DeadRoot, rcc::Register::fromPhysical(X0), 3);
+  (void)buildADDI(Context, Builder, DeadValue, DeadRoot, 4);
+
+  auto Debug = Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::DBG_VALUE));
+  Context.expect(Debug.has_value() &&
+                     Debug->addUse(DeadValue, {rcc::RegisterOperandFlag::Debug}).has_value() &&
+                     Debug->build().has_value(),
+                 "debug-only use construction must succeed");
+  const rcc::MachineMemOperand *Memory = makeMemory(Context, *Fixture.Function, true, false);
+  if (Memory == nullptr)
+    return;
+  rcc::MachineInstr *Store = buildStore(Context, Builder, LiveValue, X2, *Memory);
+  const std::size_t Before = Fixture.Entry->instructionCount();
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineDCEPass Pass;
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine DCE failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "machine DCE must remove the debug-only dead chain");
+  Context.expect(Fixture.Entry->instructionCount() + 2 == Before,
+                 "machine DCE must reach a fixed point across the dead chain");
+  Context.expect(Store != nullptr && Store->isLinked(), "machine DCE must preserve a store");
+  Context.expect(!Fixture.Function->registerInfo().isKnownVirtualRegister(DeadRoot) &&
+                     !Fixture.Function->registerInfo().isKnownVirtualRegister(DeadValue),
+                 "machine DCE must retire removed virtual registers");
+  rcc::MachineInstr *DebugInstruction = nullptr;
+  for (rcc::MachineInstr *Instruction = Fixture.Entry->firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (Instruction->opcode() == rcc::opcode(rcc::GenericOpcode::DBG_VALUE))
+      DebugInstruction = Instruction;
+  }
+  const rcc::MachineOperand *DebugOperand =
+      DebugInstruction == nullptr ? nullptr : DebugInstruction->operandAt(0);
+  Context.expect(DebugOperand != nullptr && DebugOperand->registerValue().has_value() &&
+                     DebugOperand->registerValue()->isNoRegister(),
+                 "machine DCE must clear a dangling debug register use");
+}
+
+void testMachineCombinerIdentityRules(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "combiner", 6);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "combiner insert point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::PhysicalRegister X2 = physical(Context, rcc::riscv::PhysicalRegisterID::X2);
+  const rcc::Register Seed = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Identity = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Consumer = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, Seed, rcc::Register::fromPhysical(X0), 7);
+  rcc::MachineInstr *IdentityInstruction = buildADDI(Context, Builder, Identity, Seed, 0);
+  rcc::MachineInstr *ConsumerInstruction = buildADD(Context, Builder, Consumer, Identity, Seed);
+  const rcc::MachineMemOperand *Memory = makeMemory(Context, *Fixture.Function, true, false);
+  if (Memory == nullptr)
+    return;
+  (void)buildStore(Context, Builder, Consumer, X2, *Memory);
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineCombinerPass Pass(rcc::riscv::machineCombinerInfo(),
+                                rcc::MachineCombinerStage::SelectedSSA);
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine combiner failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "machine combiner must apply a registered RV64GC identity rule");
+  Context.expect(IdentityInstruction != nullptr && !IdentityInstruction->isLinked() &&
+                     !Fixture.Function->registerInfo().isKnownVirtualRegister(Identity),
+                 "machine combiner must erase the identity and retire its result");
+  const rcc::MachineOperand *ConsumerUse =
+      ConsumerInstruction == nullptr ? nullptr : ConsumerInstruction->operandAt(1);
+  Context.expect(ConsumerUse != nullptr && ConsumerUse->registerValue() == Seed,
+                 "machine combiner executor must rewrite all result uses");
+}
+
+void testPostRAMachineCombinerIdentity(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "post_ra_combiner", 7);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  Fixture.Function->properties().clear(rcc::MachineFunctionProperty::IsSSA);
+  Fixture.Function->properties().set(rcc::MachineFunctionProperty::NoPHIs);
+  Fixture.Function->properties().set(rcc::MachineFunctionProperty::TiedOpsRewritten);
+  Fixture.Function->properties().set(rcc::MachineFunctionProperty::NoVRegs);
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "post-RA combiner insert point must be established");
+  const rcc::PhysicalRegister X10 = physical(Context, rcc::riscv::PhysicalRegisterID::X10);
+  rcc::MachineInstr *Identity = buildADDI(Context, Builder, rcc::Register::fromPhysical(X10),
+                                          rcc::Register::fromPhysical(X10), 0);
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineCombinerPass Pass(rcc::riscv::machineCombinerInfo(),
+                                rcc::MachineCombinerStage::PostRegisterAllocation);
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  Context.expect(
+      Result.has_value() && Result->Changed && Identity != nullptr && !Identity->isLinked(),
+      "post-RA combiner must erase a physical-register no-op only when identities match");
+}
+
+void testCSERegisterAndMemoryRules(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "cse", 2);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "CSE insert point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+
+  const rcc::Register Seed = makeGPR(Context, *Fixture.Function);
+  const rcc::Register First = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Redundant = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Consumer = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, Seed, rcc::Register::fromPhysical(X0), 9);
+  rcc::MachineInstr *FirstInstruction = buildADDI(Context, Builder, First, Seed, 7);
+  rcc::MachineInstr *RedundantInstruction = buildADDI(Context, Builder, Redundant, Seed, 7);
+  rcc::MachineInstr *ConsumerInstruction = buildADD(Context, Builder, Consumer, Redundant, Seed);
+
+  const rcc::Register MutableLoadOne = makeGPR(Context, *Fixture.Function);
+  const rcc::Register MutableLoadTwo = makeGPR(Context, *Fixture.Function);
+  const rcc::Register InvariantLoadOne = makeGPR(Context, *Fixture.Function);
+  const rcc::Register InvariantLoadTwo = makeGPR(Context, *Fixture.Function);
+  const rcc::MachineMemOperand *MutableMemory =
+      makeMemory(Context, *Fixture.Function, false, false);
+  const rcc::MachineMemOperand *InvariantMemory =
+      makeMemory(Context, *Fixture.Function, false, true);
+  if (MutableMemory == nullptr || InvariantMemory == nullptr)
+    return;
+  rcc::MachineInstr *MutableOne = buildLoad(Context, Builder, MutableLoadOne, Seed, *MutableMemory);
+  rcc::MachineInstr *MutableTwo = buildLoad(Context, Builder, MutableLoadTwo, Seed, *MutableMemory);
+  rcc::MachineInstr *InvariantOne =
+      buildLoad(Context, Builder, InvariantLoadOne, Seed, *InvariantMemory);
+  rcc::MachineInstr *InvariantTwo =
+      buildLoad(Context, Builder, InvariantLoadTwo, Seed, *InvariantMemory);
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineCSEPass Pass;
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine CSE failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "machine CSE must eliminate safe redundant expressions");
+  Context.expect(FirstInstruction != nullptr && FirstInstruction->isLinked() &&
+                     RedundantInstruction != nullptr && !RedundantInstruction->isLinked(),
+                 "machine CSE must keep the dominating expression only");
+  const rcc::MachineOperand *ConsumerUse =
+      ConsumerInstruction == nullptr ? nullptr : ConsumerInstruction->operandAt(1);
+  Context.expect(ConsumerUse != nullptr && ConsumerUse->registerValue() == First,
+                 "machine CSE must rewrite uses to the dominating result");
+  Context.expect(MutableOne != nullptr && MutableOne->isLinked() && MutableTwo != nullptr &&
+                     MutableTwo->isLinked(),
+                 "machine CSE must not merge mutable loads");
+  Context.expect(InvariantOne != nullptr && InvariantOne->isLinked() && InvariantTwo != nullptr &&
+                     !InvariantTwo->isLinked(),
+                 "machine CSE must merge invariant dereferenceable loads");
+  Context.expect(!Fixture.Function->registerInfo().isKnownVirtualRegister(Redundant) &&
+                     !Fixture.Function->registerInfo().isKnownVirtualRegister(InvariantLoadTwo),
+                 "machine CSE must retire redundant result registers");
+}
+
+void testCSEBudgetPreservesLegalMIR(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "cse_budget", 3);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "CSE budget insert point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::Register Seed = makeGPR(Context, *Fixture.Function);
+  const rcc::Register First = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Second = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, Seed, rcc::Register::fromPhysical(X0), 1);
+  (void)buildADDI(Context, Builder, First, Seed, 2);
+  rcc::MachineInstr *SecondInstruction = buildADDI(Context, Builder, Second, Seed, 2);
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineCSEPass Pass({.MaximumComparisons = 0});
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine CSE budget failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && !Result->Changed && SecondInstruction != nullptr &&
+                     SecondInstruction->isLinked(),
+                 "machine CSE budget exhaustion must stop without rejecting or mutating MIR");
+}
+
+void testLICMHoistsOnlyInvariantInstructions(TestContext &Context,
+                                             const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "licm", 4);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  auto Header = Fixture.Function->createBasicBlock();
+  auto Body = Fixture.Function->createBasicBlock();
+  auto Exit = Fixture.Function->createBasicBlock();
+  Context.expect(Header.has_value() && Body.has_value() && Exit.has_value() &&
+                     Fixture.Function->appendBlock(**Header).has_value() &&
+                     Fixture.Function->appendBlock(**Body).has_value() &&
+                     Fixture.Function->appendBlock(**Exit).has_value(),
+                 "LICM loop blocks must be created");
+  if (!Header || !Body || !Exit)
+    return;
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  Context.expect(Half.has_value(), "LICM branch probability must be created");
+  if (!Half)
+    return;
+  auto Updater = Fixture.Function->cfgUpdater();
+  Context.expect(
+      Updater.addSuccessor(*Fixture.Entry, **Header, rcc::BranchProbability::one()).has_value() &&
+          Updater.addSuccessor(**Header, **Body, *Half).has_value() &&
+          Updater.addSuccessor(**Header, **Exit, *Half).has_value() &&
+          Updater.addSuccessor(**Body, **Header, rcc::BranchProbability::one()).has_value(),
+      "LICM loop CFG must be connected");
+
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "LICM preheader insertion point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::Register Seed = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, Seed, rcc::Register::fromPhysical(X0), 1);
+
+  Context.expect(Builder.setInsertPoint(**Body).has_value(),
+                 "LICM body insertion point must be established");
+  const rcc::Register HoistedValue = makeGPR(Context, *Fixture.Function);
+  const rcc::Register DependentValue = makeGPR(Context, *Fixture.Function);
+  rcc::MachineInstr *Hoisted = buildADDI(Context, Builder, HoistedValue, Seed, 8);
+  rcc::MachineInstr *Dependent = buildADDI(Context, Builder, DependentValue, HoistedValue, 9);
+  const rcc::Register MutableLoad = makeGPR(Context, *Fixture.Function);
+  const rcc::MachineMemOperand *Memory = makeMemory(Context, *Fixture.Function, false, false);
+  rcc::MachineInstr *Load =
+      Memory == nullptr ? nullptr : buildLoad(Context, Builder, MutableLoad, Seed, *Memory);
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineLICMPass Pass;
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine LICM failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "machine LICM must hoist loop-invariant instructions");
+  Context.expect(Hoisted != nullptr && Hoisted->parent() == Fixture.Entry && Dependent != nullptr &&
+                     Dependent->parent() == Fixture.Entry,
+                 "machine LICM must reach a fixed point for dependent invariants");
+  Context.expect(Load != nullptr && Load->parent() == *Body,
+                 "machine LICM must keep mutable loads in the loop");
+}
+
+void testMachineSinkUsesColdUniqueSuccessor(TestContext &Context,
+                                            const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "sink", 5);
+  if (!Fixture.Function || Fixture.Entry == nullptr)
+    return;
+  auto Cold = Fixture.Function->createBasicBlock();
+  auto Hot = Fixture.Function->createBasicBlock();
+  Context.expect(Cold.has_value() && Hot.has_value() &&
+                     Fixture.Function->appendBlock(**Cold).has_value() &&
+                     Fixture.Function->appendBlock(**Hot).has_value(),
+                 "machine sink successor blocks must be created");
+  if (!Cold || !Hot)
+    return;
+  auto ColdProbability = rcc::BranchProbability::fromFraction(1, 10);
+  auto HotProbability = rcc::BranchProbability::fromFraction(9, 10);
+  Context.expect(ColdProbability.has_value() && HotProbability.has_value(),
+                 "machine sink probabilities must be created");
+  if (!ColdProbability || !HotProbability)
+    return;
+  auto Updater = Fixture.Function->cfgUpdater();
+  Context.expect(Updater.addSuccessor(*Fixture.Entry, **Cold, *ColdProbability).has_value() &&
+                     Updater.addSuccessor(*Fixture.Entry, **Hot, *HotProbability).has_value(),
+                 "machine sink CFG must be connected");
+
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Entry).has_value(),
+                 "machine sink source insertion point must be established");
+  const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::Register Seed = makeGPR(Context, *Fixture.Function);
+  const rcc::Register SunkValue = makeGPR(Context, *Fixture.Function);
+  (void)buildADDI(Context, Builder, Seed, rcc::Register::fromPhysical(X0), 1);
+  rcc::MachineInstr *Sunk = buildADDI(Context, Builder, SunkValue, Seed, 4);
+
+  Context.expect(Builder.setInsertPoint(**Cold).has_value(),
+                 "machine sink destination insertion point must be established");
+  const rcc::Register Consumer = makeGPR(Context, *Fixture.Function);
+  rcc::MachineInstr *Use = buildADD(Context, Builder, Consumer, SunkValue, Seed);
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineSinkPass Pass;
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine sink failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "machine sink must move a cold-path-only expression");
+  Context.expect(Sunk != nullptr && Sunk->parent() == *Cold && Use != nullptr &&
+                     Sunk->next() == Use,
+                 "machine sink must place the definition immediately before its first use");
+}
+
+void testPostRACodeMotion(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto LICMFixture = makeFixture(Context, "post-ra-licm", 10);
+  if (!LICMFixture.Function || LICMFixture.Entry == nullptr)
+    return;
+  auto Header = LICMFixture.Function->createBasicBlock();
+  auto Body = LICMFixture.Function->createBasicBlock();
+  auto Exit = LICMFixture.Function->createBasicBlock();
+  if (!Header || !Body || !Exit || !LICMFixture.Function->appendBlock(**Header) ||
+      !LICMFixture.Function->appendBlock(**Body) || !LICMFixture.Function->appendBlock(**Exit)) {
+    Context.expect(false, "post-RA LICM blocks must be created");
+    return;
+  }
+  auto Half = rcc::BranchProbability::fromFraction(1, 2);
+  if (!Half)
+    return;
+  auto LICMUpdater = LICMFixture.Function->cfgUpdater();
+  if (!LICMUpdater.addSuccessor(*LICMFixture.Entry, **Header, rcc::BranchProbability::one()) ||
+      !LICMUpdater.addSuccessor(**Header, **Body, *Half) ||
+      !LICMUpdater.addSuccessor(**Header, **Exit, *Half) ||
+      !LICMUpdater.addSuccessor(**Body, **Header, rcc::BranchProbability::one())) {
+    Context.expect(false, "post-RA LICM CFG must be connected");
+    return;
+  }
+  rcc::MachineIRBuilder LICMBuilder(*LICMFixture.Function, Target);
+  if (!LICMBuilder.setInsertPoint(*LICMFixture.Entry))
+    return;
+  const rcc::Register X0 =
+      rcc::Register::fromPhysical(physical(Context, rcc::riscv::PhysicalRegisterID::X0));
+  const rcc::Register X2 =
+      rcc::Register::fromPhysical(physical(Context, rcc::riscv::PhysicalRegisterID::X2));
+  const rcc::Register X10 =
+      rcc::Register::fromPhysical(physical(Context, rcc::riscv::PhysicalRegisterID::X10));
+  const rcc::Register X12 =
+      rcc::Register::fromPhysical(physical(Context, rcc::riscv::PhysicalRegisterID::X12));
+  const rcc::Register X13 =
+      rcc::Register::fromPhysical(physical(Context, rcc::riscv::PhysicalRegisterID::X13));
+  (void)buildADDI(Context, LICMBuilder, X10, X0, 1);
+  if (!LICMBuilder.setInsertPoint(**Header))
+    return;
+  rcc::MachineInstr *Hoisted = buildADDI(Context, LICMBuilder, X12, X10, 4);
+  if (Hoisted == nullptr)
+    return;
+  Hoisted->setFlags({rcc::MachineInstrFlag::NoFPExcept});
+  if (!LICMBuilder.setInsertPoint(**Body))
+    return;
+  (void)buildADDI(Context, LICMBuilder, X13, X12, 1);
+  if (!LICMBuilder.setInsertPoint(**Exit))
+    return;
+  const rcc::MachineMemOperand *LICMMemory =
+      makeMemory(Context, *LICMFixture.Function, true, false);
+  if (LICMMemory == nullptr)
+    return;
+  (void)buildStore(Context, LICMBuilder, X12, *X2.physicalRegister(), *LICMMemory);
+  setPostRAProperties(*LICMFixture.Function);
+  Context.expect(rcc::rebuildMachineLiveness(*LICMFixture.Function, Target).has_value(),
+                 "post-RA LICM fixture liveness must be built");
+  rcc::MachineAnalysisManager LICMAnalyses;
+  rcc::MachineLICMPass PostRALICM(rcc::MachineCodeMotionStage::PostRegisterAllocation);
+  auto LICMResult = PostRALICM.run(*LICMFixture.Function, Target, LICMAnalyses);
+  Context.expect(LICMResult && LICMResult->Changed && Hoisted->parent() == LICMFixture.Entry &&
+                     rcc::verifyTrackedMachineLiveness(*LICMFixture.Function, Target).has_value(),
+                 "post-RA LICM must hoist a safe physical-register invariant and repair liveness");
+
+  auto SinkFixture = makeFixture(Context, "post-ra-sink", 11);
+  if (!SinkFixture.Function || SinkFixture.Entry == nullptr)
+    return;
+  auto Cold = SinkFixture.Function->createBasicBlock();
+  auto Hot = SinkFixture.Function->createBasicBlock();
+  if (!Cold || !Hot || !SinkFixture.Function->appendBlock(**Cold) ||
+      !SinkFixture.Function->appendBlock(**Hot)) {
+    return;
+  }
+  auto ColdProbability = rcc::BranchProbability::fromFraction(1, 10);
+  auto HotProbability = rcc::BranchProbability::fromFraction(9, 10);
+  if (!ColdProbability || !HotProbability)
+    return;
+  auto SinkUpdater = SinkFixture.Function->cfgUpdater();
+  if (!SinkUpdater.addSuccessor(*SinkFixture.Entry, **Cold, *ColdProbability) ||
+      !SinkUpdater.addSuccessor(*SinkFixture.Entry, **Hot, *HotProbability)) {
+    return;
+  }
+  rcc::MachineIRBuilder SinkBuilder(*SinkFixture.Function, Target);
+  if (!SinkBuilder.setInsertPoint(*SinkFixture.Entry))
+    return;
+  (void)buildADDI(Context, SinkBuilder, X10, X0, 2);
+  rcc::MachineInstr *Sunk = buildADDI(Context, SinkBuilder, X12, X10, 8);
+  if (Sunk == nullptr)
+    return;
+  Sunk->setFlags({rcc::MachineInstrFlag::NoFPExcept});
+  if (!SinkBuilder.setInsertPoint(**Cold))
+    return;
+  rcc::MachineInstr *ColdUse = buildADDI(Context, SinkBuilder, X13, X12, 1);
+  setPostRAProperties(*SinkFixture.Function);
+  Context.expect(rcc::rebuildMachineLiveness(*SinkFixture.Function, Target).has_value(),
+                 "post-RA sink fixture liveness must be built");
+  rcc::MachineAnalysisManager SinkAnalyses;
+  rcc::MachineSinkPass PostRASink(rcc::MachineCodeMotionStage::PostRegisterAllocation);
+  auto SinkResult = PostRASink.run(*SinkFixture.Function, Target, SinkAnalyses);
+  Context.expect(SinkResult && SinkResult->Changed && Sunk->parent() == *Cold &&
+                     Sunk->next() == ColdUse &&
+                     rcc::verifyTrackedMachineLiveness(*SinkFixture.Function, Target).has_value(),
+                 "post-RA sinking must move a physical definition to its sole cold use");
+}
+
+void testMemoryFoldingContract(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto BuildCandidate = [&](std::string Name, std::uint64_t ID) {
+    Fixture Candidate = makeFixture(Context, std::move(Name), ID);
+    if (!Candidate.Function || Candidate.Entry == nullptr)
+      return Candidate;
+    rcc::MachineIRBuilder Builder(*Candidate.Function, Target);
+    if (!Builder.setInsertPoint(*Candidate.Entry))
+      return Candidate;
+    const rcc::PhysicalRegister X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+    const rcc::PhysicalRegister X2 = physical(Context, rcc::riscv::PhysicalRegisterID::X2);
+    const rcc::Register Address = makeGPR(Context, *Candidate.Function);
+    const rcc::Register Loaded = makeGPR(Context, *Candidate.Function);
+    const rcc::Register FoldedResult = makeGPR(Context, *Candidate.Function);
+    (void)buildADDI(Context, Builder, Address, rcc::Register::fromPhysical(X0), 0);
+    const rcc::MachineMemOperand *LoadMemory =
+        makeMemory(Context, *Candidate.Function, false, false);
+    const rcc::MachineMemOperand *StoreMemory =
+        makeMemory(Context, *Candidate.Function, true, false);
+    if (LoadMemory == nullptr || StoreMemory == nullptr)
+      return Candidate;
+    (void)buildLoad(Context, Builder, Loaded, Address, *LoadMemory);
+    (void)buildADDI(Context, Builder, FoldedResult, Loaded, 0);
+    (void)buildStore(Context, Builder, FoldedResult, X2, *StoreMemory);
+    return Candidate;
+  };
+
+  Fixture Folded = BuildCandidate("memory-fold", 8);
+  if (!Folded.Function || Folded.Entry == nullptr)
+    return;
+  TestMemoryFoldingInfo GoodInfo;
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineMemoryFoldingPass Pass(GoodInfo);
+  auto Result = Pass.run(*Folded.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "machine memory folding failure: " << Result.error().message() << '\n';
+  std::size_t LoadCount = 0;
+  rcc::MachineInstr *FoldedLoad = nullptr;
+  for (rcc::MachineInstr *Instruction = Folded.Entry->firstInstruction(); Instruction != nullptr;
+       Instruction = Instruction->next()) {
+    if (Instruction->opcode() == opcode(rcc::riscv::InstructionOpcode::LD)) {
+      ++LoadCount;
+      FoldedLoad = Instruction;
+    }
+  }
+  Context.expect(Result && Result->Changed && LoadCount == 1 && FoldedLoad != nullptr &&
+                     FoldedLoad->memOperands().size() == 1,
+                 "memory folding must replace an adjacent load-use pair and migrate its MMO");
+
+  Fixture Rejected = BuildCandidate("memory-fold-missing-mmo", 9);
+  if (!Rejected.Function || Rejected.Entry == nullptr)
+    return;
+  rcc::MachineInstr *OriginalLoad = Rejected.Entry->firstInstruction();
+  OriginalLoad = OriginalLoad == nullptr ? nullptr : OriginalLoad->next();
+  rcc::MachineInstr *OriginalConsumer = OriginalLoad == nullptr ? nullptr : OriginalLoad->next();
+  const std::size_t OriginalCount = Rejected.Entry->instructionCount();
+  TestMemoryFoldingInfo BadInfo(true);
+  rcc::MachineMemoryFoldingPass BadPass(BadInfo);
+  auto Failure = BadPass.run(*Rejected.Function, Target, Analyses);
+  Context.expect(!Failure && Failure.error().code() == rcc::ErrorCode::VerificationError &&
+                     Rejected.Entry->instructionCount() == OriginalCount &&
+                     OriginalLoad != nullptr && OriginalLoad->isLinked() &&
+                     OriginalConsumer != nullptr && OriginalConsumer->isLinked(),
+                 "memory folding must reject missing MMO migration without mutating the function");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = rcc::riscv::createTargetDescription();
+  Context.expect(Target.has_value(), "optimization target construction must succeed");
+  if (!Target)
+    return Context.result();
+  testDCEFixedPointAndDebugUses(Context, *Target);
+  testMachineCombinerIdentityRules(Context, *Target);
+  testPostRAMachineCombinerIdentity(Context, *Target);
+  testCSERegisterAndMemoryRules(Context, *Target);
+  testCSEBudgetPreservesLegalMIR(Context, *Target);
+  testLICMHoistsOnlyInvariantInstructions(Context, *Target);
+  testMachineSinkUsesColdUniqueSuccessor(Context, *Target);
+  testPostRACodeMotion(Context, *Target);
+  testMemoryFoldingContract(Context, *Target);
+  return Context.result();
+}
diff --git a/backend/unittests/CodeGen/MachineSchedulingTest.cpp b/backend/unittests/CodeGen/MachineSchedulingTest.cpp
new file mode 100644
index 0000000..a485146
--- /dev/null
+++ b/backend/unittests/CodeGen/MachineSchedulingTest.cpp
@@ -0,0 +1,518 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineLiveness.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineScheduler.h"
+#include "rcc/CodeGen/PostRAScheduler.h"
+#include "rcc/CodeGen/ScheduleDAG.h"
+#include "rcc/CodeGen/ScheduleHazardRecognizer.h"
+#include "rcc/CodeGen/TargetSchedulingModel.h"
+#include "rcc/Target/RISCV/RISCVCodeGen.h"
+#include "rcc/Target/RISCV/RISCVTarget.h"
+
+#include <array>
+#include <cstdint>
+#include <iostream>
+#include <memory>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace {
+
+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;
+};
+
+struct Fixture final {
+  std::unique_ptr<rcc::MachineFunction> Function;
+  rcc::MachineBasicBlock *Block = nullptr;
+};
+
+class OnePerCycleHazard final : public rcc::TargetScheduleHazardRecognizer {
+public:
+  [[nodiscard]] std::unique_ptr<rcc::TargetScheduleHazardRecognizer> clone() const override {
+    return std::make_unique<OnePerCycleHazard>(*this);
+  }
+
+  [[nodiscard]] rcc::Expected<rcc::ScheduleHazardType>
+  getHazardType(const rcc::ScheduleUnit &) const override {
+    return Emitted ? rcc::ScheduleHazardType::Hazard : rcc::ScheduleHazardType::NoHazard;
+  }
+
+  [[nodiscard]] rcc::Expected<void> emitInstruction(const rcc::ScheduleUnit &) override {
+    Emitted = true;
+    return {};
+  }
+
+  [[nodiscard]] rcc::Expected<void> advanceCycle() override {
+    Emitted = false;
+    return {};
+  }
+
+  [[nodiscard]] rcc::Expected<void> recedeCycle() override {
+    Emitted = false;
+    return {};
+  }
+
+  [[nodiscard]] rcc::Expected<void> reset() override {
+    Emitted = false;
+    return {};
+  }
+
+private:
+  bool Emitted = false;
+};
+
+class TestSchedulingHooks final : public rcc::TargetSchedulingHooks {
+public:
+  bool MakeADDIBoundary = false;
+  bool AddMutation = false;
+  bool PreferSecondUnit = false;
+  bool EnableDynamicHazards = false;
+
+  [[nodiscard]] bool isSchedulingBoundary(const rcc::MachineInstr &Instruction,
+                                          const rcc::TargetDescription &) const noexcept override {
+    return MakeADDIBoundary &&
+           Instruction.opcode() == rcc::Opcode::fromValue(static_cast<std::uint32_t>(
+                                       rcc::riscv::InstructionOpcode::ADDI));
+  }
+
+  [[nodiscard]] rcc::Expected<void> mutateScheduleDAG(rcc::ScheduleDAG &DAG,
+                                                      const rcc::MachineFunction &,
+                                                      const rcc::TargetDescription &,
+                                                      rcc::ScheduleDAGMode) const override {
+    if (!AddMutation || DAG.units().size() < 2)
+      return {};
+    return DAG.addArtificialDependency(0, 1, 2);
+  }
+
+  [[nodiscard]] std::int64_t candidatePreference(const rcc::ScheduleUnit &Unit,
+                                                 rcc::ScheduleDirection,
+                                                 const rcc::MachineBasicBlock &,
+                                                 std::uint64_t) const noexcept override {
+    return PreferSecondUnit && Unit.ID == 1 ? 100 : 0;
+  }
+
+  [[nodiscard]] std::unique_ptr<rcc::TargetScheduleHazardRecognizer>
+  createHazardRecognizer(rcc::ScheduleDirection) const override {
+    return EnableDynamicHazards ? std::make_unique<OnePerCycleHazard>() : nullptr;
+  }
+};
+
+[[nodiscard]] rcc::Opcode opcode(rcc::riscv::InstructionOpcode Value) noexcept {
+  return rcc::Opcode::fromValue(static_cast<std::uint32_t>(Value));
+}
+
+[[nodiscard]] rcc::Expected<rcc::TargetSchedulingModel>
+makeSchedulingModel(const rcc::TargetSchedulingHooks *Hooks = nullptr) {
+  rcc::TargetSchedulingModelDesc Description;
+  Description.IssueWidth = 2;
+  Description.DispatchLimit = 2;
+  for (const rcc::riscv::SchedulingClassInfo &Class : rcc::riscv::schedulingClasses()) {
+    Description.SchedulingClasses.push_back({
+        .ID = Class.ID,
+        .Name = std::string(Class.Name),
+        .MicroOps = Class.MicroOps,
+        .Latency = Class.Latency,
+        .Resources = {},
+        .WriteLatencies = {{0, Class.Latency}},
+        .ReadAdvances = {},
+    });
+  }
+  Description.PressureSets.push_back({
+      .ID = rcc::RegisterPressureSetID::fromValue(1),
+      .Name = "gpr",
+      .RegisterClasses =
+          {
+              rcc::RegisterClassID::fromValue(
+                  static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR)),
+          },
+      .Limit = 27,
+  });
+  Description.Hooks = Hooks;
+  return rcc::TargetSchedulingModel::create(std::move(Description));
+}
+
+[[nodiscard]] rcc::Register physical(TestContext &Context, rcc::riscv::PhysicalRegisterID ID) {
+  auto Value = rcc::riscv::physicalRegister(ID);
+  Context.expect(Value.has_value(), "physical register creation must succeed");
+  return Value ? rcc::Register::fromPhysical(*Value) : rcc::Register{};
+}
+
+[[nodiscard]] Fixture makeFixture(TestContext &Context, std::string Name, std::uint64_t ID) {
+  auto Function =
+      rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID));
+  Context.expect(Function.has_value(), "scheduler function creation must succeed");
+  if (!Function)
+    return {};
+  auto Block = (*Function)->createBasicBlock();
+  Context.expect(Block.has_value() && (*Function)->appendBlock(**Block).has_value(),
+                 "scheduler block creation must succeed");
+  if (!Block)
+    return {};
+  (*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);
+  return {std::move(*Function), *Block};
+}
+
+[[nodiscard]] rcc::Register makeGPR(TestContext &Context, rcc::MachineFunction &Function) {
+  auto Type = rcc::LLT::makeInteger(64);
+  auto Reg = Type ? Function.registerInfo().createVirtualRegister(*Type)
+                  : rcc::Expected<rcc::Register>(std::unexpected(
+                        rcc::Error(rcc::ErrorCode::InternalError, "test LLT creation failed")));
+  Context.expect(Reg.has_value(), "scheduler virtual register creation must succeed");
+  if (!Reg)
+    return {};
+  const auto Bank =
+      rcc::RegisterBankID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterBank::GPR));
+  const auto Class =
+      rcc::RegisterClassID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterClass::GPR));
+  Context.expect(Function.registerInfo().setRegisterBank(*Reg, Bank).has_value() &&
+                     Function.registerInfo().setRegisterClass(*Reg, Class).has_value(),
+                 "scheduler virtual register constraints must be assigned");
+  return *Reg;
+}
+
+[[nodiscard]] rcc::MachineInstr *buildADDI(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                           rcc::Register Destination, rcc::Register Source,
+                                           std::int64_t Immediate) {
+  auto Pending = Builder.buildInstr(opcode(rcc::riscv::InstructionOpcode::ADDI));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Source) ||
+      !Pending->addImmediate(Immediate)) {
+    Context.expect(false, "scheduler ADDI construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "scheduler ADDI insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+[[nodiscard]] rcc::MachineInstr *buildBinary(TestContext &Context, rcc::MachineIRBuilder &Builder,
+                                             rcc::riscv::InstructionOpcode Opcode,
+                                             rcc::Register Destination, rcc::Register Left,
+                                             rcc::Register Right) {
+  auto Pending = Builder.buildInstr(opcode(Opcode));
+  if (!Pending || !Pending->addDef(Destination) || !Pending->addUse(Left) ||
+      !Pending->addUse(Right)) {
+    Context.expect(false, "scheduler binary instruction construction must succeed");
+    return nullptr;
+  }
+  auto Built = Pending->build();
+  Context.expect(Built.has_value(), "scheduler binary instruction insertion must succeed");
+  return Built.value_or(nullptr);
+}
+
+[[nodiscard]] bool hasDependency(const rcc::ScheduleUnit &Unit, std::size_t Destination,
+                                 rcc::ScheduleDependencyKind Kind) {
+  for (const rcc::ScheduleDependency &Dependency : Unit.Successors) {
+    if (Dependency.Destination == Destination && Dependency.Kind == Kind)
+      return true;
+  }
+  return false;
+}
+
+void testDAGRegisterDependencies(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "schedule_dag", 1);
+  if (!Fixture.Function || Fixture.Block == nullptr)
+    return;
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Block).has_value(),
+                 "schedule DAG insertion point must be established");
+  const rcc::Register X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::Register X10 = physical(Context, rcc::riscv::PhysicalRegisterID::X10);
+  const rcc::Register Value = makeGPR(Context, *Fixture.Function);
+  const rcc::Register Consumer = makeGPR(Context, *Fixture.Function);
+  rcc::MachineInstr *Definition = buildADDI(Context, Builder, Value, X0, 1);
+  rcc::MachineInstr *Use =
+      buildBinary(Context, Builder, rcc::riscv::InstructionOpcode::ADD, Consumer, Value, X10);
+  rcc::MachineInstr *Redefinition = buildADDI(Context, Builder, Value, X0, 2);
+  std::array<rcc::MachineInstr *, 3> Instructions{Definition, Use, Redefinition};
+  auto DAG = rcc::ScheduleDAG::build(*Fixture.Block, Instructions, *Fixture.Function, Target,
+                                     rcc::riscv::schedulingModel(),
+                                     rcc::ScheduleDAGMode::PreRegisterAllocation);
+  if (!DAG)
+    std::cerr << "schedule DAG failure: " << DAG.error().message() << '\n';
+  Context.expect(DAG.has_value() && DAG->units().size() == 3,
+                 "schedule DAG must create one unit per instruction");
+  if (!DAG)
+    return;
+  Context.expect(hasDependency(DAG->units()[0], 1, rcc::ScheduleDependencyKind::Data),
+                 "schedule DAG must model virtual-register data dependencies");
+  Context.expect(hasDependency(DAG->units()[0], 2, rcc::ScheduleDependencyKind::Output),
+                 "schedule DAG must model virtual-register output dependencies");
+  Context.expect(hasDependency(DAG->units()[1], 2, rcc::ScheduleDependencyKind::Anti),
+                 "schedule DAG must model virtual-register anti dependencies");
+  Context.expect(DAG->units()[0].Latency != 0 && DAG->units()[0].MicroOps != 0,
+                 "schedule DAG must attach target latency and resource facts");
+}
+
+void testHazardScoreboard(TestContext &Context) {
+  auto Hazards = rcc::ScheduleHazardRecognizer::create(rcc::riscv::schedulingModel());
+  Context.expect(Hazards.has_value(), "hazard recognizer construction must succeed");
+  if (!Hazards)
+    return;
+  const auto Memory = rcc::ProcessorResourceID::fromValue(3);
+  rcc::ScheduleUnit Load;
+  Load.MicroOps = 1;
+  Load.Resources = {{Memory, 1}};
+  Context.expect(Hazards->issue(Load, 0).has_value(),
+                 "first memory operation must issue in cycle zero");
+  auto SecondCycle = Hazards->earliestIssueCycle(Load, 0);
+  Context.expect(SecondCycle.has_value() && *SecondCycle == 1,
+                 "single-unit memory resource must serialize operations");
+
+  rcc::ScheduleUnit Wide;
+  Wide.MicroOps = 5;
+  auto Fresh = rcc::ScheduleHazardRecognizer::create(rcc::riscv::schedulingModel());
+  Context.expect(Fresh.has_value() && Fresh->issue(Wide, 0).has_value(),
+                 "multi-cycle dispatch must accept instructions wider than issue width");
+  auto AfterWide = Fresh ? Fresh->earliestIssueCycle(Load, 0)
+                         : rcc::Expected<std::uint64_t>(std::unexpected(
+                               rcc::Error(rcc::ErrorCode::InternalError, "no recognizer")));
+  Context.expect(AfterWide.has_value() && *AfterWide == 3,
+                 "multi-cycle dispatch must block the complete dispatch interval");
+}
+
+void testOperandLatencyAndModelValidation(TestContext &Context) {
+  const rcc::SchedulingClassID ALU = rcc::SchedulingClassID::fromValue(
+      static_cast<std::uint32_t>(rcc::riscv::SchedulingClass::ALU));
+  const rcc::SchedulingClassID Load = rcc::SchedulingClassID::fromValue(
+      static_cast<std::uint32_t>(rcc::riscv::SchedulingClass::LOAD));
+  auto Forwarded = rcc::riscv::schedulingModel().operandLatency(Load, 0, ALU, 1);
+  auto Unforwarded = rcc::riscv::schedulingModel().operandLatency(Load, 0, ALU, 0);
+  auto ALUChain = rcc::riscv::schedulingModel().operandLatency(ALU, 0, ALU, 1);
+  Context.expect(Forwarded.has_value() && *Forwarded == 2 && Unforwarded.has_value() &&
+                     *Unforwarded == 3 && ALUChain.has_value() && *ALUChain == 1,
+                 "operand latency must combine write latency with exact read advance");
+
+  rcc::TargetSchedulingModelDesc Invalid;
+  Invalid.SchedulingClasses.push_back({
+      .ID = ALU,
+      .Name = "invalid",
+      .MicroOps = 1,
+      .Latency = 1,
+      .Resources = {},
+      .WriteLatencies = {{0, 1}, {0, 2}},
+      .ReadAdvances = {},
+  });
+  auto Rejected = rcc::TargetSchedulingModel::create(std::move(Invalid));
+  Context.expect(!Rejected && Rejected.error().code() == rcc::ErrorCode::InvalidArgument,
+                 "scheduling model must reject duplicate operand latency facts");
+}
+
+void testDynamicTargetHazards(TestContext &Context) {
+  TestSchedulingHooks Hooks;
+  Hooks.EnableDynamicHazards = true;
+  auto Model = makeSchedulingModel(&Hooks);
+  Context.expect(Model.has_value(), "dynamic-hazard scheduling model construction must succeed");
+  if (!Model)
+    return;
+
+  rcc::ScheduleUnit First;
+  First.ID = 1;
+  First.MicroOps = 1;
+  rcc::ScheduleUnit Second;
+  Second.ID = 2;
+  Second.MicroOps = 1;
+  auto Top = rcc::ScheduleHazardRecognizer::create(*Model, rcc::ScheduleDirection::TopDown);
+  Context.expect(Top.has_value() && Top->issue(First, 0).has_value(),
+                 "target dynamic hazard must accept the first top-down issue");
+  auto TopCycle = Top ? Top->earliestIssueCycle(Second, 0)
+                      : rcc::Expected<std::uint64_t>(std::unexpected(
+                            rcc::Error(rcc::ErrorCode::InternalError, "no top-down recognizer")));
+  Context.expect(TopCycle.has_value() && *TopCycle == 1,
+                 "target dynamic hazard must advance the top-down cycle");
+
+  auto Bottom = rcc::ScheduleHazardRecognizer::create(*Model, rcc::ScheduleDirection::BottomUp);
+  Context.expect(Bottom.has_value() && Bottom->issue(First, 0).has_value(),
+                 "target dynamic hazard must accept the first bottom-up issue");
+  auto BottomCycle = Bottom ? Bottom->earliestIssueCycle(Second, 0)
+                            : rcc::Expected<std::uint64_t>(std::unexpected(rcc::Error(
+                                  rcc::ErrorCode::InternalError, "no bottom-up recognizer")));
+  Context.expect(BottomCycle.has_value() && *BottomCycle == 1,
+                 "target dynamic hazard must recede the bottom-up cycle");
+}
+
+void testTargetSchedulingHooks(TestContext &Context, const rcc::TargetDescription &Target) {
+  TestSchedulingHooks MutationHooks;
+  MutationHooks.AddMutation = true;
+  auto MutationModel = makeSchedulingModel(&MutationHooks);
+  auto Fixture = makeFixture(Context, "schedule_mutation", 4);
+  if (!MutationModel || !Fixture.Function || Fixture.Block == nullptr) {
+    Context.expect(false, "target schedule mutation fixture must be created");
+    return;
+  }
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Block).has_value(),
+                 "target schedule mutation insertion point must be established");
+  const rcc::Register X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  rcc::MachineInstr *First =
+      buildADDI(Context, Builder, makeGPR(Context, *Fixture.Function), X0, 1);
+  rcc::MachineInstr *Second =
+      buildADDI(Context, Builder, makeGPR(Context, *Fixture.Function), X0, 2);
+  std::array<rcc::MachineInstr *, 2> Instructions{First, Second};
+  auto DAG = rcc::ScheduleDAG::build(*Fixture.Block, Instructions, *Fixture.Function, Target,
+                                     *MutationModel, rcc::ScheduleDAGMode::PreRegisterAllocation);
+  Context.expect(DAG.has_value() &&
+                     hasDependency(DAG->units()[0], 1, rcc::ScheduleDependencyKind::Artificial),
+                 "target schedule mutation must add a checked artificial dependency");
+
+  TestSchedulingHooks PreferenceHooks;
+  PreferenceHooks.PreferSecondUnit = true;
+  auto PreferenceModel = makeSchedulingModel(&PreferenceHooks);
+  if (!PreferenceModel) {
+    Context.expect(false, "target scheduling preference model must be created");
+    return;
+  }
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineSchedulerPass PreferencePass(
+      *PreferenceModel, {.MaximumRegionSize = 8, .EnableBidirectionalScheduling = false});
+  auto Preferred = PreferencePass.run(*Fixture.Function, Target, Analyses);
+  Context.expect(Preferred.has_value() && Preferred->Changed &&
+                     Fixture.Block->firstInstruction() == Second,
+                 "target candidate preference must affect the production scheduler");
+
+  auto BoundaryFixture = makeFixture(Context, "schedule_boundary", 5);
+  TestSchedulingHooks BoundaryHooks;
+  BoundaryHooks.MakeADDIBoundary = true;
+  auto BoundaryModel = makeSchedulingModel(&BoundaryHooks);
+  if (!BoundaryFixture.Function || BoundaryFixture.Block == nullptr || !BoundaryModel) {
+    Context.expect(false, "target schedule boundary fixture must be created");
+    return;
+  }
+  rcc::MachineIRBuilder BoundaryBuilder(*BoundaryFixture.Function, Target);
+  Context.expect(BoundaryBuilder.setInsertPoint(*BoundaryFixture.Block).has_value(),
+                 "target schedule boundary insertion point must be established");
+  rcc::MachineInstr *BoundaryFirst =
+      buildADDI(Context, BoundaryBuilder, makeGPR(Context, *BoundaryFixture.Function), X0, 1);
+  (void)buildADDI(Context, BoundaryBuilder, makeGPR(Context, *BoundaryFixture.Function), X0, 2);
+  rcc::MachineAnalysisManager BoundaryAnalyses;
+  rcc::MachineSchedulerPass BoundaryPass(
+      *BoundaryModel, {.MaximumRegionSize = 8, .EnableBidirectionalScheduling = false});
+  auto BoundaryResult = BoundaryPass.run(*BoundaryFixture.Function, Target, BoundaryAnalyses);
+  Context.expect(BoundaryResult.has_value() && !BoundaryResult->Changed &&
+                     BoundaryFixture.Block->firstInstruction() == BoundaryFirst,
+                 "target scheduling boundary must split production schedule regions");
+}
+
+void buildSchedulingChain(TestContext &Context, Fixture &Fixture,
+                          const rcc::TargetDescription &Target, bool PhysicalRegisters,
+                          rcc::MachineInstr *&Short, rcc::MachineInstr *&Long) {
+  rcc::MachineIRBuilder Builder(*Fixture.Function, Target);
+  Context.expect(Builder.setInsertPoint(*Fixture.Block).has_value(),
+                 "scheduler chain insertion point must be established");
+  const rcc::Register X0 = physical(Context, rcc::riscv::PhysicalRegisterID::X0);
+  const rcc::Register X10 = physical(Context, rcc::riscv::PhysicalRegisterID::X10);
+  const rcc::Register X11 = physical(Context, rcc::riscv::PhysicalRegisterID::X11);
+  const rcc::Register ShortValue = PhysicalRegisters
+                                       ? physical(Context, rcc::riscv::PhysicalRegisterID::X12)
+                                       : makeGPR(Context, *Fixture.Function);
+  const rcc::Register LongValue = PhysicalRegisters
+                                      ? physical(Context, rcc::riscv::PhysicalRegisterID::X13)
+                                      : makeGPR(Context, *Fixture.Function);
+  const rcc::Register LongResult = PhysicalRegisters
+                                       ? physical(Context, rcc::riscv::PhysicalRegisterID::X14)
+                                       : makeGPR(Context, *Fixture.Function);
+  const rcc::Register ShortResult = PhysicalRegisters
+                                        ? physical(Context, rcc::riscv::PhysicalRegisterID::X15)
+                                        : makeGPR(Context, *Fixture.Function);
+  Short = buildADDI(Context, Builder, ShortValue, X0, 1);
+  Long = buildBinary(Context, Builder, rcc::riscv::InstructionOpcode::DIV, LongValue, X10, X11);
+  (void)buildBinary(Context, Builder, rcc::riscv::InstructionOpcode::ADD, LongResult, LongValue,
+                    X10);
+  (void)buildBinary(Context, Builder, rcc::riscv::InstructionOpcode::ADD, ShortResult, ShortValue,
+                    X11);
+}
+
+void testPreRAScheduler(TestContext &Context, const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "pre_ra_schedule", 2);
+  if (!Fixture.Function || Fixture.Block == nullptr)
+    return;
+  rcc::MachineInstr *Short = nullptr;
+  rcc::MachineInstr *Long = nullptr;
+  buildSchedulingChain(Context, Fixture, Target, false, Short, Long);
+  Context.expect(Fixture.Block->firstInstruction() == Short,
+                 "pre-RA fixture must begin in intentionally suboptimal order");
+  rcc::MachineAnalysisManager Analyses;
+  rcc::MachineSchedulerPass Pass(rcc::riscv::schedulingModel(),
+                                 {.MaximumRegionSize = 64, .EnableBidirectionalScheduling = false});
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "pre-RA scheduler failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "pre-RA scheduler must reorder the latency-critical chain");
+  Context.expect(Fixture.Block->firstInstruction() == Long,
+                 "pre-RA scheduler must prioritize the long critical path");
+}
+
+void testPostRASchedulerAndLivenessRepair(TestContext &Context,
+                                          const rcc::TargetDescription &Target) {
+  auto Fixture = makeFixture(Context, "post_ra_schedule", 3);
+  if (!Fixture.Function || Fixture.Block == nullptr)
+    return;
+  Fixture.Function->properties().set(rcc::MachineFunctionProperty::NoVRegs);
+  Fixture.Function->properties().set(rcc::MachineFunctionProperty::TracksLiveness);
+  rcc::MachineInstr *Short = nullptr;
+  rcc::MachineInstr *Long = nullptr;
+  buildSchedulingChain(Context, Fixture, Target, true, Short, Long);
+  auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture.Function, Target);
+  Context.expect(Rebuilt.has_value(), "post-RA fixture liveness rebuild must succeed");
+  if (!Rebuilt)
+    return;
+
+  rcc::MachineAnalysisManager Analyses;
+  rcc::PostRASchedulerPass Pass(rcc::riscv::schedulingModel(),
+                                {.MaximumRegionSize = 64, .EnableBidirectionalScheduling = false});
+  auto Result = Pass.run(*Fixture.Function, Target, Analyses);
+  if (!Result)
+    std::cerr << "post-RA scheduler failure: " << Result.error().message() << '\n';
+  Context.expect(Result.has_value() && Result->Changed,
+                 "post-RA scheduler must reorder the latency-critical chain");
+  Context.expect(Fixture.Block->firstInstruction() == Long,
+                 "post-RA scheduler must prioritize the long critical path");
+  auto Verified = rcc::verifyTrackedMachineLiveness(*Fixture.Function, Target);
+  if (!Verified)
+    std::cerr << "post-RA liveness verification failure: " << Verified.error().message() << '\n';
+  Context.expect(Verified.has_value(),
+                 "post-RA scheduler must locally repair exact kill/dead state");
+}
+
+} // namespace
+
+int main() {
+  TestContext Context;
+  auto Target = rcc::riscv::createTargetDescription();
+  Context.expect(Target.has_value(), "scheduler target creation must succeed");
+  if (!Target)
+    return Context.result();
+  testDAGRegisterDependencies(Context, *Target);
+  testHazardScoreboard(Context);
+  testOperandLatencyAndModelValidation(Context);
+  testDynamicTargetHazards(Context);
+  testTargetSchedulingHooks(Context, *Target);
+  testPreRAScheduler(Context, *Target);
+  testPostRASchedulerAndLivenessRepair(Context, *Target);
+  return Context.result();
+}