[Tooling] Complete backend tooling and validation

22 files changed, 573 insertions, 124 deletions

diff --git a/backend/lib/CodeGen/InlineSpiller.cpp b/backend/lib/CodeGen/InlineSpiller.cpp
index 589b7b8..14de321 100644
--- a/backend/lib/CodeGen/InlineSpiller.cpp
+++ b/backend/lib/CodeGen/InlineSpiller.cpp
@@ -7,6 +7,7 @@
 #include "rcc/CodeGen/MachineIRBuilder.h"
 #include "rcc/CodeGen/MachineInstr.h"
 #include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachinePass.h"
 #include "rcc/CodeGen/MachineRegisterInfo.h"
 #include "rcc/CodeGen/Spiller.h"
 #include "rcc/CodeGen/TargetDescription.h"
@@ -42,11 +43,11 @@ Expected<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Registe
   const MachineInstr *DefiningInstruction = Definition == nullptr ? nullptr : Definition->parent();
   if (DefiningInstruction == nullptr || DefiningInstruction->parent() == nullptr)
     return std::optional<std::vector<Register>>{};
-  auto Accepted =
+  auto Rematerializable =
       TargetInfo->isRematerializable(*DefiningInstruction, VirtualReg, *Function, *Target);
-  if (!Accepted)
-    return std::unexpected(Accepted.error());
-  if (!*Accepted)
+  if (!Rematerializable)
+    return std::unexpected(Rematerializable.error());
+  if (!*Rematerializable)
     return std::optional<std::vector<Register>>{};
 
   struct UseSite final {
@@ -77,6 +78,16 @@ Expected<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Registe
   if (Sites.empty())
     return std::optional<std::vector<Register>>{};
 
+  if (Actions != nullptr) {
+    for (const UseSite &Site : Sites) {
+      auto Accepted = Actions->request("rematerialize", *Function, Site.Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted)
+        return std::optional<std::vector<Register>>{};
+    }
+  }
+
   std::vector<Register> NewRegisters;
   NewRegisters.reserve(Sites.size());
   for (UseSite &Site : Sites) {
@@ -169,6 +180,19 @@ Expected<std::vector<Register>> Spiller::spillAtInstructions(Register VirtualReg
   }
 
   std::vector<Register> NewRegisters;
+  if (Actions != nullptr) {
+    for (const SpillSite &Site : Sites) {
+      if (Site.OperandIndices.empty())
+        continue;
+      auto Accepted = Actions->request("split-live-range", *Function, Site.Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted) {
+        return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                              "required live-range split action was rejected");
+      }
+    }
+  }
   for (SpillSite &Site : Sites) {
     for (const std::size_t Index : Site.DebugIndices) {
       MachineOperand *Operand = Site.Instruction->operandAt(Index);
@@ -259,6 +283,19 @@ Expected<std::vector<Register>> Spiller::spill(Register VirtualReg) {
     return makeUnexpected(ErrorCode::RegisterAllocationFailed,
                           "register pressure requires spilling a non-spillable value");
   }
+  if (Actions != nullptr) {
+    const MachineOperand *Definition = Function->registerInfo().getUniqueVRegDef(VirtualReg);
+    const MachineInstr *Instruction = Definition == nullptr ? nullptr : Definition->parent();
+    auto Accepted =
+        Actions->request("spill", *Function,
+                         Instruction == nullptr ? MachineInstrStableID{} : Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                            "required spill action was rejected");
+    }
+  }
   auto Rematerialized = tryRematerialize(VirtualReg);
   if (!Rematerialized)
     return std::unexpected(Rematerialized.error());
diff --git a/backend/lib/CodeGen/MachineBlockPlacement.cpp b/backend/lib/CodeGen/MachineBlockPlacement.cpp
index fea1283..daccba0 100644
--- a/backend/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/backend/lib/CodeGen/MachineBlockPlacement.cpp
@@ -114,21 +114,25 @@ Expected<MachinePassResult> MachineBlockPlacementPass::run(MachineFunction &Func
   if (!Trial)
     return std::unexpected(prefixedError(Trial.error(), "block placement setup failed: "));
   MachineAnalysisManager TrialAnalyses;
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target, Analyses);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Analyses, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "block placement diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
-Expected<MachinePassResult>
-MachineBlockPlacementPass::runImplementation(MachineFunction &Function,
-                                             const TargetDescription &Target,
-                                             MachineAnalysisManager &Analyses) const {
+Expected<MachinePassResult> MachineBlockPlacementPass::runImplementation(
+    MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses,
+    MachineActionReplay &Actions) const {
   auto Probabilities = Analyses.getResult<MachineBranchProbabilityAnalysis>(Function, Target);
   if (!Probabilities)
     return std::unexpected(Probabilities.error());
@@ -154,7 +158,7 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function,
     return Result;
   }
 
-  auto factsFor = [&Facts](const MachineBasicBlock &Block) -> const PlacementFacts & {
+  auto FactsFor = [&Facts](const MachineBasicBlock &Block) -> const PlacementFacts & {
     return *std::ranges::find_if(
         Facts, [&Block](const PlacementFacts &Value) { return Value.Block == &Block; });
   };
@@ -186,7 +190,7 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function,
           continue;
         if (BestSuccessor == nullptr || BestProbability < Successor.Probability ||
             (BestProbability == Successor.Probability &&
-             betterRoot(factsFor(*Successor.Block), factsFor(*BestSuccessor)))) {
+             betterRoot(FactsFor(*Successor.Block), FactsFor(*BestSuccessor)))) {
           BestSuccessor = Successor.Block;
           BestProbability = Successor.Probability;
         }
@@ -223,7 +227,22 @@ MachineBlockPlacementPass::runImplementation(MachineFunction &Function,
 
   bool Changed = false;
   for (std::size_t Index = 1; Index < Order.size(); ++Index) {
-    Changed |= Order[Index - 1U]->next() != Order[Index];
+    if (Order[Index - 1U]->next() != Order[Index]) {
+      Changed = true;
+      break;
+    }
+  }
+  if (Changed) {
+    auto Accepted = Actions.request("apply-block-layout", Function);
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      MachinePassResult Result;
+      Result.Preserved = PreservedAnalyses::all();
+      return Result;
+    }
+  }
+  for (std::size_t Index = 1; Index < Order.size(); ++Index) {
     auto Moved = Function.moveBlockAfter(*Order[Index - 1U], *Order[Index]);
     if (!Moved)
       return std::unexpected(Moved.error());
diff --git a/backend/lib/CodeGen/MachineBranchRelaxation.cpp b/backend/lib/CodeGen/MachineBranchRelaxation.cpp
index d56f3a0..b2a330a 100644
--- a/backend/lib/CodeGen/MachineBranchRelaxation.cpp
+++ b/backend/lib/CodeGen/MachineBranchRelaxation.cpp
@@ -109,7 +109,7 @@ const MachinePassContract &MachineBranchRelaxationPass::contract() const noexcep
 
 Expected<MachinePassResult> MachineBranchRelaxationPass::run(MachineFunction &Function,
                                                              const TargetDescription &Target,
-                                                             MachineAnalysisManager &) {
+                                                             MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires)) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "branch relaxation requires finalized frame and tracked liveness");
@@ -119,20 +119,26 @@ Expected<MachinePassResult> MachineBranchRelaxationPass::run(MachineFunction &Fu
       MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
   if (!Trial)
     return std::unexpected(prefixedError(Trial.error(), "branch relaxation setup failed: "));
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "branch relaxation diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult>
 MachineBranchRelaxationPass::runImplementation(MachineFunction &Function,
-                                               const TargetDescription &Target) const {
+                                               const TargetDescription &Target,
+                                               MachineActionReplay &Actions) const {
   if (Options.ConvergenceWatchdog == 0)
     return makeUnexpected(ErrorCode::InvalidArgument, "branch relaxation watchdog must be nonzero");
   MachinePassResult Result;
@@ -162,6 +168,13 @@ MachineBranchRelaxationPass::runImplementation(MachineFunction &Function,
           return std::unexpected(Offset.error());
         if (Info->isBranchOffsetInRange(*Instruction, *Offset))
           continue;
+        auto Accepted = Actions.request("relax-branch", Function, Instruction->stableID());
+        if (!Accepted)
+          return std::unexpected(Accepted.error());
+        if (!*Accepted) {
+          return makeUnexpected(ErrorCode::BranchRelaxationFailed,
+                                "required branch relaxation action was rejected");
+        }
         auto Relaxed = Info->relaxBranch(*Instruction, *Offset, Function, Target);
         if (!Relaxed)
           return std::unexpected(Relaxed.error());
diff --git a/backend/lib/CodeGen/MachineCSE.cpp b/backend/lib/CodeGen/MachineCSE.cpp
index a144403..47bba04 100644
--- a/backend/lib/CodeGen/MachineCSE.cpp
+++ b/backend/lib/CodeGen/MachineCSE.cpp
@@ -161,8 +161,11 @@ template <typename ValueT>
     if (Reg == nullptr || !Reg->isVirtual())
       continue;
     auto Info = Registers.virtualRegisterInfo(*Reg);
-    if (Info && Info->get().Type && Info->get().Type->isFloat())
-      return true;
+    if (Info) {
+      const auto &Type = Info->get().Type;
+      if (Type && Type->isFloat())
+        return true;
+    }
   }
   return false;
 }
diff --git a/backend/lib/CodeGen/MachineCombiner.cpp b/backend/lib/CodeGen/MachineCombiner.cpp
index 513d282..54915ab 100644
--- a/backend/lib/CodeGen/MachineCombiner.cpp
+++ b/backend/lib/CodeGen/MachineCombiner.cpp
@@ -279,7 +279,7 @@ const MachinePassContract &MachineCombinerPass::contract() const noexcept {
 
 Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function,
                                                      const TargetDescription &Target,
-                                                     MachineAnalysisManager &) {
+                                                     MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires)) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "machine combiner input does not satisfy its stage contract");
@@ -291,20 +291,25 @@ Expected<MachinePassResult> MachineCombinerPass::run(MachineFunction &Function,
     return std::unexpected(
         prefixedError(Trial.error(), "machine combiner transaction setup failed: "));
   }
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "machine combiner diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult>
-MachineCombinerPass::runImplementation(MachineFunction &Function,
-                                       const TargetDescription &Target) const {
+MachineCombinerPass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
+                                       MachineActionReplay &Actions) const {
   if (Options.MaximumIterations == 0)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine combiner iteration budget must be nonzero");
@@ -321,6 +326,13 @@ MachineCombinerPass::runImplementation(MachineFunction &Function,
             continue;
           if (Rewrites == Options.MaximumRewrites)
             break;
+          std::string Rule = "combine.";
+          Rule.append(Pattern.Name);
+          auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+          if (!Accepted)
+            return std::unexpected(Accepted.error());
+          if (!*Accepted)
+            continue;
           auto Executed = executePattern(*Instruction, Pattern, Function, Target);
           if (!Executed)
             return std::unexpected(Executed.error());
diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp
index 3ebfa0f..df009a4 100644
--- a/backend/lib/CodeGen/MachineCompilationStatus.cpp
+++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp
@@ -55,6 +55,12 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep
   case ErrorCode::FixupApplicationFailed:
   case ErrorCode::RelocationFailed:
   case ErrorCode::ObjectWritingFailed:
+  case ErrorCode::InvalidInvocation:
+  case ErrorCode::ManifestError:
+  case ErrorCode::CacheMiss:
+  case ErrorCode::ReproducerError:
+  case ErrorCode::ReductionFailed:
+  case ErrorCode::FuzzingFailure:
   case ErrorCode::IoError:
   case ErrorCode::InternalError:
     return true;
diff --git a/backend/lib/CodeGen/MachineCopyPropagation.cpp b/backend/lib/CodeGen/MachineCopyPropagation.cpp
index e537a06..f9211f9 100644
--- a/backend/lib/CodeGen/MachineCopyPropagation.cpp
+++ b/backend/lib/CodeGen/MachineCopyPropagation.cpp
@@ -292,7 +292,7 @@ const MachinePassContract &MachineCopyPropagationPass::contract() const noexcept
 
 Expected<MachinePassResult> MachineCopyPropagationPass::run(MachineFunction &Function,
                                                             const TargetDescription &Target,
-                                                            MachineAnalysisManager &) {
+                                                            MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires)) {
     return makeUnexpected(ErrorCode::VerificationError,
                           "machine COPY propagation has unmet stage properties");
@@ -304,20 +304,26 @@ Expected<MachinePassResult> MachineCopyPropagationPass::run(MachineFunction &Fun
     return std::unexpected(
         prefixedError(Trial.error(), "COPY propagation transaction setup failed: "));
   }
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "COPY propagation diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult>
 MachineCopyPropagationPass::runImplementation(MachineFunction &Function,
-                                              const TargetDescription &Target) const {
+                                              const TargetDescription &Target,
+                                              MachineActionReplay &Actions) const {
   MachinePassResult Result;
   std::size_t PropagatedCopies = 0;
   for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
@@ -329,6 +335,13 @@ MachineCopyPropagationPass::runImplementation(MachineFunction &Function,
         Instruction = Next;
         continue;
       }
+      auto Accepted = Actions.request("propagate-copy", Function, Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted) {
+        Instruction = Next;
+        continue;
+      }
       Expected<bool> Changed =
           Stage == MachineCopyPropagationStage::PreRegisterAllocation
               ? propagateVirtualCopy(*Instruction, *Operands, Function, Target, *Info)
diff --git a/backend/lib/CodeGen/MachineLICM.cpp b/backend/lib/CodeGen/MachineLICM.cpp
index 8c8d732..52fffe7 100644
--- a/backend/lib/CodeGen/MachineLICM.cpp
+++ b/backend/lib/CodeGen/MachineLICM.cpp
@@ -146,8 +146,8 @@ namespace {
     auto Info = Function.registerInfo().virtualRegisterInfo(*Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (Info->get().Type && Info->get().Type->isFloat() &&
-        !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) {
+    const auto &Type = Info->get().Type;
+    if (Type && Type->isFloat() && !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) {
       return false;
     }
   }
diff --git a/backend/lib/CodeGen/MachinePass.cpp b/backend/lib/CodeGen/MachinePass.cpp
index ae69b1c..0ce6f70 100644
--- a/backend/lib/CodeGen/MachinePass.cpp
+++ b/backend/lib/CodeGen/MachinePass.cpp
@@ -141,6 +141,79 @@ void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
 
 } // namespace
 
+std::string MachineActionID::toString() const {
+  std::string Result;
+  Result.reserve(Pass.size() + Rule.size() + 48U);
+  Result.append(Pass);
+  Result.push_back(':');
+  Result.append(Rule);
+  Result.append(":f");
+  Result.append(std::to_string(Function.value()));
+  Result.append(":i");
+  Result.append(std::to_string(Instruction.value()));
+  return Result;
+}
+
+Expected<bool> MachineActionReplay::request(std::string_view Rule, const MachineFunction &Function,
+                                            MachineInstrStableID Instruction, std::uint64_t Cost) {
+  if (!IsReplaying) {
+    const auto Position = RecordingInstructionIDs.find(Instruction);
+    const MachineInstrStableID CanonicalInstruction =
+        Position == RecordingInstructionIDs.end() ? Instruction : Position->second;
+    auto Accepted = Analyses->requestAction(Rule, Function, CanonicalInstruction, Cost);
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    Decisions.push_back({
+        .Rule = std::string(Rule),
+        .Function = Function.stableID(),
+        .Instruction = CanonicalInstruction,
+        .Cost = Cost,
+        .Accepted = *Accepted,
+    });
+    return *Accepted;
+  }
+
+  if (NextDecision >= Decisions.size()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "machine action replay requested an unrecorded decision");
+  }
+  const Decision &Recorded = Decisions[NextDecision++];
+  if (Recorded.Rule != Rule || Recorded.Function != Function.stableID() ||
+      Recorded.Instruction != Instruction || Recorded.Cost != Cost) {
+    std::string Message = "machine action replay diverged from transaction preflight: recorded ";
+    Message.append(Recorded.Rule);
+    Message.append(":f");
+    Message.append(std::to_string(Recorded.Function.value()));
+    Message.append(":i");
+    Message.append(std::to_string(Recorded.Instruction.value()));
+    Message.append(" cost=");
+    Message.append(std::to_string(Recorded.Cost));
+    Message.append(", requested ");
+    Message.append(Rule);
+    Message.append(":f");
+    Message.append(std::to_string(Function.stableID().value()));
+    Message.append(":i");
+    Message.append(std::to_string(Instruction.value()));
+    Message.append(" cost=");
+    Message.append(std::to_string(Cost));
+    return makeUnexpected(ErrorCode::InternalError, std::move(Message));
+  }
+  return Recorded.Accepted;
+}
+
+void MachineActionReplay::beginReplay() noexcept {
+  IsReplaying = true;
+  NextDecision = 0;
+}
+
+Expected<void> MachineActionReplay::finishReplay() const {
+  if (!IsReplaying || NextDecision != Decisions.size()) {
+    return makeUnexpected(ErrorCode::InternalError,
+                          "machine action replay did not consume every recorded decision");
+  }
+  return {};
+}
+
 Expected<void>
 MachineAnalysisManager::registerAnalysisImpl(MachineAnalysisRegistration Registration,
                                              ErasedRunner Runner, ErasedInvalidator Invalidator) {
@@ -374,12 +447,25 @@ Expected<void> MachineAnalysisManager::validateParallelRequirements(
 Expected<bool> MachineAnalysisManager::requestAction(std::string_view Action,
                                                      const MachineFunction &Function,
                                                      std::uint64_t Cost) {
-  if (Action.empty() || Cost == 0)
+  return requestAction(Action, Function, MachineInstrStableID{}, Cost);
+}
+
+Expected<bool> MachineAnalysisManager::requestAction(std::string_view Rule,
+                                                     const MachineFunction &Function,
+                                                     MachineInstrStableID Instruction,
+                                                     std::uint64_t Cost) {
+  if (Rule.empty() || Cost == 0)
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine action requires a name and nonzero cost");
   if (Instrumentation == nullptr)
     return true;
-  return Instrumentation->requestAction(Action, Function, Cost);
+  MachineActionID ID{
+      .Pass = ActivePass.empty() ? "unscoped" : ActivePass,
+      .Rule = std::string(Rule),
+      .Function = Function.stableID(),
+      .Instruction = Instruction,
+  };
+  return Instrumentation->requestAction(ID, Function, Cost);
 }
 
 Expected<void> CompilationUnitAnalysisManager::registerAnalysisImpl(
@@ -639,6 +725,7 @@ void MachinePassInstrumentation::setPerFunctionFuel(std::optional<std::uint64_t>
   std::scoped_lock Lock(Mutex);
   PerFunctionFuel = Fuel;
   ConsumedFuel.clear();
+  ActionEvents.clear();
 }
 
 void MachinePassInstrumentation::addBeforeUnitCallback(BeforeUnitCallback Callback) {
@@ -879,25 +966,37 @@ void MachinePassInstrumentation::change(std::string_view Name, const MachineFunc
     Callback(Name, Function, Changes, FingerprintChanged);
 }
 
-Expected<bool> MachinePassInstrumentation::requestAction(std::string_view Action,
+Expected<bool> MachinePassInstrumentation::requestAction(const MachineActionID &Action,
                                                          const MachineFunction &Function,
                                                          std::uint64_t Cost) {
+  if (Action.Pass.empty() || Action.Rule.empty() || Action.Function != Function.stableID() ||
+      Cost == 0) {
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine action identity is invalid");
+  }
   std::scoped_lock ActionLock(ActionMutex);
   ActionFilter CurrentFilter;
   {
     std::scoped_lock Lock(Mutex);
     CurrentFilter = Filter;
   }
-  if (CurrentFilter && !CurrentFilter(Action, Function, Cost))
+  if (CurrentFilter && !CurrentFilter(Action, Cost)) {
+    std::scoped_lock Lock(Mutex);
+    ActionEvents.push_back({Action, Cost, false});
     return false;
+  }
 
   std::scoped_lock Lock(Mutex);
-  if (!PerFunctionFuel)
+  if (!PerFunctionFuel) {
+    ActionEvents.push_back({Action, Cost, true});
     return true;
+  }
   std::uint64_t &Consumed = ConsumedFuel[Function.stableID().value()];
-  if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed)
+  if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed) {
+    ActionEvents.push_back({Action, Cost, false});
     return false;
+  }
   Consumed += Cost;
+  ActionEvents.push_back({Action, Cost, true});
   return true;
 }
 
@@ -1007,10 +1106,33 @@ std::vector<InstrumentationStatistic> MachinePassInstrumentation::statistics() c
   return Result;
 }
 
+std::vector<MachineActionEvent> MachinePassInstrumentation::actionEvents() const {
+  std::vector<MachineActionEvent> Result;
+  {
+    std::scoped_lock Lock(Mutex);
+    Result = ActionEvents;
+  }
+  std::ranges::sort(Result, [](const MachineActionEvent &Left, const MachineActionEvent &Right) {
+    if (Left.ID.Function.value() != Right.ID.Function.value())
+      return Left.ID.Function.value() < Right.ID.Function.value();
+    if (Left.ID.Instruction.value() != Right.ID.Instruction.value())
+      return Left.ID.Instruction.value() < Right.ID.Instruction.value();
+    if (Left.ID.Pass != Right.ID.Pass)
+      return Left.ID.Pass < Right.ID.Pass;
+    if (Left.ID.Rule != Right.ID.Rule)
+      return Left.ID.Rule < Right.ID.Rule;
+    if (Left.Cost != Right.Cost)
+      return Left.Cost < Right.Cost;
+    return Left.Accepted < Right.Accepted;
+  });
+  return Result;
+}
+
 void MachinePassInstrumentation::clearStatistics() {
   std::scoped_lock Lock(Mutex);
   Statistics.clear();
   ConsumedFuel.clear();
+  ActionEvents.clear();
 }
 
 Expected<void> MachinePassManager::validateContract(const MachinePassContract &Contract) const {
@@ -1087,7 +1209,9 @@ Expected<void> MachinePassManager::run(MachineFunction &Function, const TargetDe
     if (Instrumentation != nullptr)
       Instrumentation->before(Name, Function);
     const Clock::time_point Start = Clock::now();
+    Analyses.ActivePass = std::string(Name);
     auto PassResult = Pass->run(Function, Target, Analyses);
+    Analyses.ActivePass.clear();
     const std::uint64_t Duration = elapsedNanoseconds(Start);
     if (!PassResult) {
       Error Failure =
diff --git a/backend/lib/CodeGen/MachinePipelinePasses.cpp b/backend/lib/CodeGen/MachinePipelinePasses.cpp
index 209439c..c7c5dc3 100644
--- a/backend/lib/CodeGen/MachinePipelinePasses.cpp
+++ b/backend/lib/CodeGen/MachinePipelinePasses.cpp
@@ -233,6 +233,36 @@ registerConfigurationFingerprint(const MachineRegisterInfo &RegInfo) noexcept {
   return Error(Source.code(), std::move(Prefix));
 }
 
+[[nodiscard]] std::string_view legalizationActionName(LegalizationAction Action) noexcept {
+  switch (Action) {
+  case LegalizationAction::Legal:
+    return "legal";
+  case LegalizationAction::Unsupported:
+    return "unsupported";
+  case LegalizationAction::Custom:
+    return "custom";
+  case LegalizationAction::Lower:
+    return "lower";
+  case LegalizationAction::Libcall:
+    return "libcall";
+  case LegalizationAction::WidenScalar:
+    return "widen-scalar";
+  case LegalizationAction::NarrowScalar:
+    return "narrow-scalar";
+  case LegalizationAction::MoreElements:
+    return "more-elements";
+  case LegalizationAction::FewerElements:
+    return "fewer-elements";
+  case LegalizationAction::Bitcast:
+    return "bitcast";
+  case LegalizationAction::ChangeElementType:
+    return "change-element-type";
+  case LegalizationAction::ChangeAddressSpace:
+    return "change-address-space";
+  }
+  return "unknown";
+}
+
 [[nodiscard]] Expected<void> repairTrackedLiveness(MachineFunction &Function,
                                                    const TargetDescription &Target,
                                                    MachinePassResult &Result) {
@@ -268,21 +298,25 @@ Expected<MachinePassResult> LegalizerPass::run(MachineFunction &Function,
       MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
   if (!Trial)
     return std::unexpected(prefixedError(Trial.error(), "legalizer transaction setup failed: "));
-  MachineAnalysisManager TrialAnalyses;
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target, Analyses);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "legalizer diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Function,
                                                              const TargetDescription &Target,
-                                                             MachineAnalysisManager &) {
+                                                             MachineActionReplay &Actions) {
 
   MachinePassResult Result;
   std::unordered_set<OpcodeState, OpcodeStateHash> SeenStates;
@@ -328,6 +362,18 @@ Expected<MachinePassResult> LegalizerPass::runImplementation(MachineFunction &Fu
     if (!LoweringValidation)
       return std::unexpected(
           prefixedError(LoweringValidation.error(), "legalizer lowering precondition failed: "));
+    std::string Rule = "legalize.";
+    Rule.append(legalizationActionName(*Action));
+    Rule.push_back('.');
+    Rule.append(Descriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return std::unexpected(
+          passFailure("required legalizer action was rejected for '" + Descriptor->Name + "'",
+                      ErrorCode::VerificationError));
+    }
     auto Lowered = Info->lower(*Instruction, Function, Target, *Action);
     if (!Lowered)
       return std::unexpected(Lowered.error());
@@ -521,22 +567,26 @@ Expected<MachinePassResult> InstructionSelectPass::run(MachineFunction &Function
     return std::unexpected(
         prefixedError(Trial.error(), "instruction-selection transaction setup failed: "));
   }
-  MachineAnalysisManager TrialAnalyses;
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = runImplementation(Function, Target, Analyses);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(
         prefixedError(Result.error(),
                       "instruction selection diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult>
 InstructionSelectPass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
-                                         MachineAnalysisManager &) {
+                                         MachineActionReplay &Actions) {
 
   MachinePassResult Result;
   std::vector<MachineInstr *> Worklist;
@@ -580,6 +630,16 @@ InstructionSelectPass::runImplementation(MachineFunction &Function, const Target
     auto Match = Info->canSelect(*Instruction, Function, Target);
     if (!Match)
       return std::unexpected(Match.error());
+    std::string Rule = "select.";
+    Rule.append(CurrentDescriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return std::unexpected(passFailure("required selection action was rejected for '" +
+                                             CurrentDescriptor->Name + "'",
+                                         ErrorCode::VerificationError));
+    }
     auto Selection = Info->select(*Instruction, Function, Target);
     if (!Selection)
       return std::unexpected(Selection.error());
diff --git a/backend/lib/CodeGen/MachinePseudoExpansion.cpp b/backend/lib/CodeGen/MachinePseudoExpansion.cpp
index e654d97..676804a 100644
--- a/backend/lib/CodeGen/MachinePseudoExpansion.cpp
+++ b/backend/lib/CodeGen/MachinePseudoExpansion.cpp
@@ -202,7 +202,7 @@ using BlockSizeSnapshot = std::vector<std::pair<MachineBlockStableID, std::uint6
 
 [[nodiscard]] Expected<MachinePassResult>
 prepareImplementation(MachineFunction &Function, const TargetDescription &Target,
-                      const TargetPseudoExpansionInfo &Info) {
+                      const TargetPseudoExpansionInfo &Info, MachineActionReplay &Actions) {
   bool Changed = false;
   for (MachineInstr *Instruction : Function.allInstructions()) {
     if (Instruction == nullptr || Instruction->parent() == nullptr)
@@ -213,6 +213,15 @@ prepareImplementation(MachineFunction &Function, const TargetDescription &Target
                             "pseudo preparation encountered an unknown opcode");
     if (Descriptor->Owner != PseudoOwner::PostRAExpansion)
       continue;
+    std::string Rule = "prepare-pseudo.";
+    Rule.append(Descriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return makeUnexpected(ErrorCode::PseudoExpansionFailed,
+                            "required pseudo preparation action was rejected");
+    }
     auto Prepared = Info.preparePostRAPseudo(*Instruction, Function, Target);
     if (!Prepared)
       return std::unexpected(Prepared.error());
@@ -232,7 +241,7 @@ prepareImplementation(MachineFunction &Function, const TargetDescription &Target
 [[nodiscard]] Expected<MachinePassResult>
 expandImplementation(MachineFunction &Function, const TargetDescription &Target,
                      const TargetPseudoExpansionInfo &Info, MachinePseudoExpansionPhase Phase,
-                     const TargetBranchInfo *BranchInfo) {
+                     const TargetBranchInfo *BranchInfo, MachineActionReplay &Actions) {
   const ResourceSnapshot Before = snapshotResources(Function);
   std::optional<BlockSizeSnapshot> SizesBefore;
   if (Phase == MachinePseudoExpansionPhase::TargetLate) {
@@ -261,6 +270,15 @@ expandImplementation(MachineFunction &Function, const TargetDescription &Target,
     if (!Descriptor->Flags.has(InstructionFlag::Pseudo) || Descriptor->Owner != ownerFor(Phase)) {
       continue;
     }
+    std::string Rule = "expand-pseudo.";
+    Rule.append(Descriptor->Name);
+    auto Accepted = Actions.request(Rule, Function, Instruction->stableID());
+    if (!Accepted)
+      return std::unexpected(Accepted.error());
+    if (!*Accepted) {
+      return makeUnexpected(ErrorCode::PseudoExpansionFailed,
+                            "required pseudo expansion action was rejected");
+    }
     MachineBasicBlock *ExpansionBlock = Instruction->parent();
     std::optional<std::uint64_t> ExpansionSizeBefore;
     if (Phase == MachinePseudoExpansionPhase::TargetLate) {
@@ -335,40 +353,51 @@ expandImplementation(MachineFunction &Function, const TargetDescription &Target,
 
 [[nodiscard]] Expected<MachinePassResult>
 runPreparationTransaction(MachineFunction &Function, const TargetDescription &Target,
-                          const TargetPseudoExpansionInfo &Info) {
+                          const TargetPseudoExpansionInfo &Info, MachineAnalysisManager &Analyses) {
   auto Trial = cloneMachineFunction(
       Function, Target,
       MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
   if (!Trial)
     return std::unexpected(prefixedError(Trial.error(), "pseudo preparation setup failed: "));
-  auto TrialResult = prepareImplementation(*Trial->ClonedFunction, Target, Info);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = prepareImplementation(*Trial->ClonedFunction, Target, Info, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = prepareImplementation(Function, Target, Info);
+  Actions.beginReplay();
+  auto Result = prepareImplementation(Function, Target, Info, Actions);
   if (!Result) {
     return std::unexpected(
         prefixedError(Result.error(), "pseudo preparation diverged after successful preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 [[nodiscard]] Expected<MachinePassResult>
 runExpansionTransaction(MachineFunction &Function, const TargetDescription &Target,
                         const TargetPseudoExpansionInfo &Info, MachinePseudoExpansionPhase Phase,
-                        const TargetBranchInfo *BranchInfo) {
+                        const TargetBranchInfo *BranchInfo, MachineAnalysisManager &Analyses) {
   auto Trial = cloneMachineFunction(
       Function, Target,
       MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
   if (!Trial)
     return std::unexpected(prefixedError(Trial.error(), "pseudo expansion setup failed: "));
-  auto TrialResult = expandImplementation(*Trial->ClonedFunction, Target, Info, Phase, BranchInfo);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult =
+      expandImplementation(*Trial->ClonedFunction, Target, Info, Phase, BranchInfo, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
-  auto Result = expandImplementation(Function, Target, Info, Phase, BranchInfo);
+  Actions.beginReplay();
+  auto Result = expandImplementation(Function, Target, Info, Phase, BranchInfo, Actions);
   if (!Result) {
     return std::unexpected(
         prefixedError(Result.error(), "pseudo expansion diverged after successful preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
@@ -380,11 +409,11 @@ const MachinePassContract &PreparePostRAPseudosPass::contract() const noexcept {
 
 Expected<MachinePassResult> PreparePostRAPseudosPass::run(MachineFunction &Function,
                                                           const TargetDescription &Target,
-                                                          MachineAnalysisManager &) {
+                                                          MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires))
     return makeUnexpected(ErrorCode::VerificationError,
                           "post-RA pseudo preparation requires selected MachineIR");
-  return runPreparationTransaction(Function, Target, *Info);
+  return runPreparationTransaction(Function, Target, *Info, Analyses);
 }
 
 const MachinePassContract &PrePEITargetPseudoExpansionPass::contract() const noexcept {
@@ -393,12 +422,12 @@ const MachinePassContract &PrePEITargetPseudoExpansionPass::contract() const noe
 
 Expected<MachinePassResult> PrePEITargetPseudoExpansionPass::run(MachineFunction &Function,
                                                                  const TargetDescription &Target,
-                                                                 MachineAnalysisManager &) {
+                                                                 MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires))
     return makeUnexpected(ErrorCode::VerificationError,
                           "pre-PEI pseudo expansion requires allocated tracked-liveness MIR");
   return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::PrePEI,
-                                 nullptr);
+                                 nullptr, Analyses);
 }
 
 const MachinePassContract &ExpandPostRAPseudosPass::contract() const noexcept {
@@ -407,12 +436,12 @@ const MachinePassContract &ExpandPostRAPseudosPass::contract() const noexcept {
 
 Expected<MachinePassResult> ExpandPostRAPseudosPass::run(MachineFunction &Function,
                                                          const TargetDescription &Target,
-                                                         MachineAnalysisManager &) {
+                                                         MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires))
     return makeUnexpected(ErrorCode::VerificationError,
                           "post-RA pseudo expansion requires finalized frame and liveness");
   return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::PostRA,
-                                 nullptr);
+                                 nullptr, Analyses);
 }
 
 const MachinePassContract &TargetLatePseudoExpansionPass::contract() const noexcept {
@@ -421,12 +450,12 @@ const MachinePassContract &TargetLatePseudoExpansionPass::contract() const noexc
 
 Expected<MachinePassResult> TargetLatePseudoExpansionPass::run(MachineFunction &Function,
                                                                const TargetDescription &Target,
-                                                               MachineAnalysisManager &) {
+                                                               MachineAnalysisManager &Analyses) {
   if (!Function.properties().containsAll(contract().Requires))
     return makeUnexpected(ErrorCode::VerificationError,
                           "target-late pseudo expansion requires finalized allocated MIR");
   return runExpansionTransaction(Function, Target, *Info, MachinePseudoExpansionPhase::TargetLate,
-                                 BranchInfo);
+                                 BranchInfo, Analyses);
 }
 
 } // namespace rcc
diff --git a/backend/lib/CodeGen/MachineSSAExit.cpp b/backend/lib/CodeGen/MachineSSAExit.cpp
index e413b45..f2b0102 100644
--- a/backend/lib/CodeGen/MachineSSAExit.cpp
+++ b/backend/lib/CodeGen/MachineSSAExit.cpp
@@ -805,22 +805,26 @@ Expected<MachinePassResult> PHIEliminationPass::run(MachineFunction &Function,
     return std::unexpected(
         prefixedError(Trial.error(), "PHI-elimination transaction setup failed: "));
   }
-  MachineAnalysisManager TrialAnalyses;
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
 
-  auto Result = runImplementation(Function, Target, Analyses);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "PHI elimination diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunction &Function,
                                                                   const TargetDescription &Target,
-                                                                  MachineAnalysisManager &) {
+                                                                  MachineActionReplay &Actions) {
   MachinePassResult Result;
   std::unordered_map<EdgeKey, MachineBasicBlock *, EdgeKeyHash> SplitEdges;
   const std::vector<MachineBasicBlock *> Blocks(Function.allBlocks().begin(),
@@ -834,6 +838,13 @@ Expected<MachinePassResult> PHIEliminationPass::runImplementation(MachineFunctio
       continue;
 
     for (PhiPlan &Plan : *Plans) {
+      auto Accepted = Actions.request("eliminate-phi", Function, Plan.Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted) {
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "required PHI elimination action was rejected");
+      }
       auto Fresh = cloneRegisterConstraints(Function, Plan.Destination.Reg);
       if (!Fresh)
         return std::unexpected(Fresh.error());
@@ -928,22 +939,26 @@ Expected<MachinePassResult> TwoAddressRewritePass::run(MachineFunction &Function
   if (!Trial) {
     return std::unexpected(prefixedError(Trial.error(), "two-address transaction setup failed: "));
   }
-  MachineAnalysisManager TrialAnalyses;
-  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, TrialAnalyses);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
 
-  auto Result = runImplementation(Function, Target, Analyses);
+  Actions.beginReplay();
+  auto Result = runImplementation(Function, Target, Actions);
   if (!Result) {
     return std::unexpected(prefixedError(
         Result.error(), "two-address rewrite diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   return Result;
 }
 
 Expected<MachinePassResult>
 TwoAddressRewritePass::runImplementation(MachineFunction &Function, const TargetDescription &Target,
-                                         MachineAnalysisManager &) {
+                                         MachineActionReplay &Actions) {
   MachinePassResult Result;
   const std::vector<MachineInstr *> Instructions(Function.allInstructions().begin(),
                                                  Function.allInstructions().end());
@@ -951,6 +966,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
     if (Instruction->parent() == nullptr)
       continue;
     if (Instruction->opcode() == opcode(GenericOpcode::REG_SEQUENCE)) {
+      auto Accepted = Actions.request("expand-reg-sequence", Function, Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "required REG_SEQUENCE expansion action was rejected");
       auto Expanded = expandRegSequence(*Instruction, Function, Target, *Info);
       if (!Expanded)
         return std::unexpected(Expanded.error());
@@ -959,6 +980,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
       continue;
     }
     if (Instruction->opcode() == opcode(GenericOpcode::INSERT_SUBREG)) {
+      auto Accepted = Actions.request("expand-insert-subreg", Function, Instruction->stableID());
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted)
+        return makeUnexpected(ErrorCode::VerificationError,
+                              "required INSERT_SUBREG expansion action was rejected");
       auto Expanded = expandInsertSubreg(*Instruction, Function, Target, *Info);
       if (!Expanded)
         return std::unexpected(Expanded.error());
@@ -1004,6 +1031,12 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
           continue;
 
         if (isImplicitlyUndef(Function, *Use)) {
+          auto Accepted = Actions.request("rewrite-undef-tie", Function, Instruction->stableID());
+          if (!Accepted)
+            return std::unexpected(Accepted.error());
+          if (!*Accepted)
+            return makeUnexpected(ErrorCode::VerificationError,
+                                  "required undef tie rewrite action was rejected");
           auto Rewritten = rewriteUndefTie(*Use, *Def);
           if (!Rewritten)
             return std::unexpected(Rewritten.error());
@@ -1012,28 +1045,46 @@ TwoAddressRewritePass::runImplementation(MachineFunction &Function, const Target
           continue;
         }
 
-        auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function);
-        if (!Commuted)
-          return std::unexpected(Commuted.error());
-        if (*Commuted) {
-          Result.Changed = true;
-          Result.Changes.add(MachinePassChange::Operands);
-          continue;
+        auto AllowCommute =
+            Actions.request("commute-tied-operands", Function, Instruction->stableID());
+        if (!AllowCommute)
+          return std::unexpected(AllowCommute.error());
+        if (*AllowCommute) {
+          auto Commuted = tryCommute(*Instruction, UseIndex, *DefReg, Target, Function);
+          if (!Commuted)
+            return std::unexpected(Commuted.error());
+          if (*Commuted) {
+            Result.Changed = true;
+            Result.Changes.add(MachinePassChange::Operands);
+            continue;
+          }
         }
 
-        auto Converted =
-            Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
-        if (!Converted)
-          return std::unexpected(Converted.error());
-        if (*Converted) {
-          Result.Changed = true;
-          Result.Changes.add(MachinePassChange::Instructions);
-          Result.Changes.add(MachinePassChange::Operands);
-          Result.Changes.add(MachinePassChange::Registers);
-          Restart = true;
-          break;
+        auto AllowConversion =
+            Actions.request("convert-three-address", Function, Instruction->stableID());
+        if (!AllowConversion)
+          return std::unexpected(AllowConversion.error());
+        if (*AllowConversion) {
+          auto Converted =
+              Info->tryConvertToThreeAddress(*Instruction, DefIndex, UseIndex, Function, Target);
+          if (!Converted)
+            return std::unexpected(Converted.error());
+          if (*Converted) {
+            Result.Changed = true;
+            Result.Changes.add(MachinePassChange::Instructions);
+            Result.Changes.add(MachinePassChange::Operands);
+            Result.Changes.add(MachinePassChange::Registers);
+            Restart = true;
+            break;
+          }
         }
 
+        auto AllowCopy = Actions.request("insert-tied-copy", Function, Instruction->stableID());
+        if (!AllowCopy)
+          return std::unexpected(AllowCopy.error());
+        if (!*AllowCopy)
+          return makeUnexpected(ErrorCode::VerificationError,
+                                "required tied COPY insertion action was rejected");
         MachineBasicBlock *Block = Instruction->parent();
         if (Block == nullptr)
           return makeUnexpected(ErrorCode::InternalError,
diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp
index f861be2..c85489b 100644
--- a/backend/lib/CodeGen/MachineScheduler.cpp
+++ b/backend/lib/CodeGen/MachineScheduler.cpp
@@ -129,7 +129,8 @@ struct ScheduleCandidate final {
 scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function,
             const TargetDescription &Target, const TargetSchedulingModel &Model,
             ScheduleDAGMode Mode, const MachineBlockLiveness &Liveness,
-            std::uint64_t BlockFrequency, bool EnableBidirectionalScheduling) {
+            std::uint64_t BlockFrequency, bool EnableBidirectionalScheduling,
+            MachineActionReplay *Actions) {
   auto TopPressure = RegisterPressureTracker::create(DAG, Function, Target, Model, Mode, Liveness,
                                                      RegisterPressureDirection::TopDown);
   if (!TopPressure)
@@ -214,6 +215,14 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function,
     }
 
     const ScheduleUnit &Selected = DAG.units()[Best->Unit];
+    if (Actions != nullptr) {
+      auto Accepted = Actions->request(Best->Bottom ? "schedule-bottom" : "schedule-top", Function,
+                                       Selected.StableID);
+      if (!Accepted)
+        return std::unexpected(Accepted.error());
+      if (!*Accepted)
+        return std::vector<std::size_t>{};
+    }
     Scheduled[Best->Unit] = true;
     if (Best->Bottom) {
       auto Issued = BottomHazards->issue(Selected, Best->Cycle);
@@ -263,7 +272,7 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct
                MachineFunction &Function, const TargetDescription &Target,
                const TargetSchedulingModel &Model, ScheduleDAGMode Mode,
                const MachineBlockLiveness &Liveness, std::uint64_t BlockFrequency,
-               MachineSchedulerOptions Options) {
+               MachineSchedulerOptions Options, MachineActionReplay *Actions) {
   if (Instructions.size() < 2 || Instructions.size() > Options.MaximumRegionSize)
     return false;
   auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode);
@@ -272,9 +281,11 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct
   if (DAG->units().size() < 2)
     return false;
   auto UnitOrder = scheduleDAG(*DAG, Function, Target, Model, Mode, Liveness, BlockFrequency,
-                               Options.EnableBidirectionalScheduling);
+                               Options.EnableBidirectionalScheduling, Actions);
   if (!UnitOrder)
     return std::unexpected(UnitOrder.error());
+  if (UnitOrder->empty())
+    return false;
 
   std::vector<MachineInstr *> NewOrder;
   NewOrder.reserve(Instructions.size());
@@ -305,10 +316,12 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct
 
 } // namespace
 
-Expected<MachineSchedulingRunResult> runMachineScheduler(
-    MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model,
-    ScheduleDAGMode Mode, const LiveVariablesAnalysis::Result &Liveness,
-    const MachineBlockFrequencyAnalysis::Result &Frequencies, MachineSchedulerOptions Options) {
+Expected<MachineSchedulingRunResult>
+runMachineScheduler(MachineFunction &Function, const TargetDescription &Target,
+                    const TargetSchedulingModel &Model, ScheduleDAGMode Mode,
+                    const LiveVariablesAnalysis::Result &Liveness,
+                    const MachineBlockFrequencyAnalysis::Result &Frequencies,
+                    MachineSchedulerOptions Options, MachineActionReplay *Actions) {
   if (Options.MaximumRegionSize == 0) {
     return makeUnexpected(ErrorCode::InvalidArgument,
                           "machine scheduler region budget must be nonzero");
@@ -324,7 +337,7 @@ Expected<MachineSchedulingRunResult> runMachineScheduler(
     std::vector<MachineInstr *> Region;
     auto FlushRegion = [&]() -> Expected<void> {
       auto Changed = scheduleRegion(*Block, Region, Function, Target, Model, Mode, *BlockLiveness,
-                                    Frequencies.frequency(*Block), Options);
+                                    Frequencies.frequency(*Block), Options, Actions);
       if (!Changed)
         return std::unexpected(Changed.error());
       BlockChanged |= *Changed;
@@ -403,9 +416,10 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function,
       TrialAnalyses.getResult<MachineBlockFrequencyAnalysis>(*Trial->ClonedFunction, Target);
   if (!TrialFrequencies)
     return std::unexpected(TrialFrequencies.error());
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
   auto TrialResult = runMachineScheduler(*Trial->ClonedFunction, Target, *Model,
                                          ScheduleDAGMode::PreRegisterAllocation, **TrialLiveness,
-                                         **TrialFrequencies, Options);
+                                         **TrialFrequencies, Options, &Actions);
   if (!TrialResult)
     return std::unexpected(TrialResult.error());
 
@@ -415,12 +429,16 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function,
   auto Frequencies = Analyses.getResult<MachineBlockFrequencyAnalysis>(Function, Target);
   if (!Frequencies)
     return std::unexpected(Frequencies.error());
+  Actions.beginReplay();
   auto Run = runMachineScheduler(Function, Target, *Model, ScheduleDAGMode::PreRegisterAllocation,
-                                 **Liveness, **Frequencies, Options);
+                                 **Liveness, **Frequencies, Options, &Actions);
   if (!Run) {
     return std::unexpected(prefixedError(
         Run.error(), "machine scheduler diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
 
   MachinePassResult Result;
   Result.Changed = Run->Changed;
diff --git a/backend/lib/CodeGen/MachineSchedulerInternal.h b/backend/lib/CodeGen/MachineSchedulerInternal.h
index a612548..92f8eea 100644
--- a/backend/lib/CodeGen/MachineSchedulerInternal.h
+++ b/backend/lib/CodeGen/MachineSchedulerInternal.h
@@ -1,5 +1,7 @@
 // SPDX-License-Identifier: GPL-3.0-or-later
 
+// The private header has no stable include-root-relative guard name.
+// NOLINTNEXTLINE(llvm-header-guard)
 #ifndef RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H
 #define RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H
 
@@ -14,6 +16,7 @@
 namespace rcc {
 
 class MachineBasicBlock;
+class MachineActionReplay;
 class MachineFunction;
 class TargetDescription;
 class TargetSchedulingModel;
@@ -22,10 +25,12 @@ struct MachineSchedulingRunResult final {
   std::vector<MachineBasicBlock *> ChangedBlocks;
 };
 
-[[nodiscard]] Expected<MachineSchedulingRunResult> runMachineScheduler(
-    MachineFunction &Function, const TargetDescription &Target, const TargetSchedulingModel &Model,
-    ScheduleDAGMode Mode, const LiveVariablesAnalysis::Result &Liveness,
-    const MachineBlockFrequencyAnalysis::Result &Frequencies, MachineSchedulerOptions Options);
+[[nodiscard]] Expected<MachineSchedulingRunResult>
+runMachineScheduler(MachineFunction &Function, const TargetDescription &Target,
+                    const TargetSchedulingModel &Model, ScheduleDAGMode Mode,
+                    const LiveVariablesAnalysis::Result &Liveness,
+                    const MachineBlockFrequencyAnalysis::Result &Frequencies,
+                    MachineSchedulerOptions Options, MachineActionReplay *Actions = nullptr);
 
 } // namespace rcc
 
diff --git a/backend/lib/CodeGen/MachineSink.cpp b/backend/lib/CodeGen/MachineSink.cpp
index 9e73cea..873de67 100644
--- a/backend/lib/CodeGen/MachineSink.cpp
+++ b/backend/lib/CodeGen/MachineSink.cpp
@@ -123,8 +123,8 @@ namespace {
     auto Info = Function.registerInfo().virtualRegisterInfo(*Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (Info->get().Type && Info->get().Type->isFloat() &&
-        !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) {
+    const auto &Type = Info->get().Type;
+    if (Type && Type->isFloat() && !Instruction.flags().has(MachineInstrFlag::NoFPExcept)) {
       return false;
     }
   }
diff --git a/backend/lib/CodeGen/MachineStackSlotColoring.cpp b/backend/lib/CodeGen/MachineStackSlotColoring.cpp
index b3b9af5..e60a7a2 100644
--- a/backend/lib/CodeGen/MachineStackSlotColoring.cpp
+++ b/backend/lib/CodeGen/MachineStackSlotColoring.cpp
@@ -178,7 +178,7 @@ collectSlotUses(MachineFunction &Function) {
 [[nodiscard]] bool intervalsOverlap(const SlotInterval &Left, const SlotInterval &Right) noexcept {
   if (Left.Block != Right.Block)
     return true;
-  return !(Left.Last < Right.First || Right.Last < Left.First);
+  return Left.Last >= Right.First && Right.Last >= Left.First;
 }
 
 struct StackColor final {
diff --git a/backend/lib/CodeGen/MachineTailDuplication.cpp b/backend/lib/CodeGen/MachineTailDuplication.cpp
index a130680..40d448f 100644
--- a/backend/lib/CodeGen/MachineTailDuplication.cpp
+++ b/backend/lib/CodeGen/MachineTailDuplication.cpp
@@ -286,7 +286,8 @@ MachineTailDuplicationPass::runImplementation(MachineFunction &Function,
       Tail = Next;
       continue;
     }
-    const std::size_t Cost = (*Candidate)->Body.size() + 1U;
+    const auto &TailCandidate = Candidate->value();
+    const std::size_t Cost = TailCandidate.Body.size() + 1U;
     const std::vector<MachineBasicBlock *> Predecessors(Tail->predecessors().begin(),
                                                         Tail->predecessors().end());
     for (MachineBasicBlock *Predecessor : Predecessors) {
@@ -296,7 +297,7 @@ MachineTailDuplicationPass::runImplementation(MachineFunction &Function,
         break;
       }
       auto Duplicated =
-          duplicateTailIntoPredecessor(**Candidate, *Tail, *Predecessor, Function, Target, *Info);
+          duplicateTailIntoPredecessor(TailCandidate, *Tail, *Predecessor, Function, Target, *Info);
       if (!Duplicated)
         return std::unexpected(Duplicated.error());
       if (!*Duplicated)
diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp
index 9aff5ac..026f763 100644
--- a/backend/lib/CodeGen/PostRAScheduler.cpp
+++ b/backend/lib/CodeGen/PostRAScheduler.cpp
@@ -287,9 +287,10 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function,
       TrialAnalyses.getResult<MachineBlockFrequencyAnalysis>(*Trial->ClonedFunction, Target);
   if (!TrialFrequencies)
     return std::unexpected(TrialFrequencies.error());
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
   auto TrialRun = runMachineScheduler(*Trial->ClonedFunction, Target, *Model,
                                       ScheduleDAGMode::PostRegisterAllocation, **TrialLiveness,
-                                      **TrialFrequencies, Options);
+                                      **TrialFrequencies, Options, &Actions);
   if (!TrialRun)
     return std::unexpected(TrialRun.error());
   auto TrialRepair =
@@ -303,12 +304,16 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function,
   auto Frequencies = Analyses.getResult<MachineBlockFrequencyAnalysis>(Function, Target);
   if (!Frequencies)
     return std::unexpected(Frequencies.error());
+  Actions.beginReplay();
   auto Run = runMachineScheduler(Function, Target, *Model, ScheduleDAGMode::PostRegisterAllocation,
-                                 **Liveness, **Frequencies, Options);
+                                 **Liveness, **Frequencies, Options, &Actions);
   if (!Run) {
     return std::unexpected(prefixedError(
         Run.error(), "post-RA scheduler diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   auto Repaired = repairPostRAMachineBlockLiveness(Run->ChangedBlocks, Target, **Liveness);
   if (!Repaired)
     return std::unexpected(Repaired.error());
diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp
index 1aae22d..5d065dd 100644
--- a/backend/lib/CodeGen/RegAllocBase.cpp
+++ b/backend/lib/CodeGen/RegAllocBase.cpp
@@ -63,7 +63,8 @@ Expected<regalloc_detail::AllocationRunResult> RegAllocBase::run() {
     std::ranges::sort(Round->Spilled, [](Register Left, Register Right) {
       return Left.opaqueValue() < Right.opaqueValue();
     });
-    Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization);
+    Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization,
+                         Actions);
     for (const Register VirtualReg : Round->Spilled) {
       VirtRegMapEntry *Entry = Mapping.entry(VirtualReg);
       if (Entry != nullptr) {
diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h
index 5af5ed0..a1682b2 100644
--- a/backend/lib/CodeGen/RegAllocBase.h
+++ b/backend/lib/CodeGen/RegAllocBase.h
@@ -28,9 +28,9 @@ public:
 protected:
   RegAllocBase(MachineFunction &Function, const TargetDescription &Target,
                const TargetRegisterAllocationInfo &TargetInfo, MachineAnalysisManager &Analyses,
-               RegisterAllocationOptions Options) noexcept
+               RegisterAllocationOptions Options, MachineActionReplay *Actions = nullptr) noexcept
       : Function(Function), Target(Target), TargetInfo(TargetInfo), Analyses(Analyses),
-        Options(Options) {}
+        Options(Options), Actions(Actions) {}
 
   [[nodiscard]] virtual Expected<AllocationRoundResult>
   allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) = 0;
@@ -40,6 +40,7 @@ protected:
   const TargetRegisterAllocationInfo &TargetInfo;
   MachineAnalysisManager &Analyses;
   RegisterAllocationOptions Options;
+  MachineActionReplay *Actions = nullptr;
 };
 
 [[nodiscard]] std::vector<const LiveInterval *>
diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp
index a5a12f7..f1da2c1 100644
--- a/backend/lib/CodeGen/RegAllocPBQP.cpp
+++ b/backend/lib/CodeGen/RegAllocPBQP.cpp
@@ -15,9 +15,10 @@
 #include <algorithm>
 #include <cstdint>
 #include <limits>
+#include <map>
 #include <optional>
 #include <ranges>
-#include <set>
+#include <string>
 #include <utility>
 #include <vector>
 
@@ -30,9 +31,9 @@ struct PBQPAllocationNode final {
   std::vector<std::optional<PhysicalRegister>> Options;
 };
 
-[[nodiscard]] std::set<std::pair<std::uint32_t, std::uint32_t>>
+[[nodiscard]] std::map<std::pair<std::uint32_t, std::uint32_t>, MachineInstrStableID>
 copyRelatedRegisters(const MachineFunction &Function) {
-  std::set<std::pair<std::uint32_t, std::uint32_t>> Result;
+  std::map<std::pair<std::uint32_t, std::uint32_t>, MachineInstrStableID> Result;
   for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
        Block = Block->next()) {
     for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
@@ -48,12 +49,33 @@ copyRelatedRegisters(const MachineFunction &Function) {
       std::uint32_t Right = Source->opaqueValue();
       if (Right < Left)
         std::swap(Left, Right);
-      Result.emplace(Left, Right);
+      Result.try_emplace({Left, Right}, Instruction->stableID());
     }
   }
   return Result;
 }
 
+[[nodiscard]] std::string_view reductionName(pbqp::ReductionKind Kind) noexcept {
+  switch (Kind) {
+  case pbqp::ReductionKind::DegreeZero:
+    return "degree-zero";
+  case pbqp::ReductionKind::DegreeOne:
+    return "degree-one";
+  case pbqp::ReductionKind::DegreeTwo:
+    return "degree-two";
+  case pbqp::ReductionKind::Heuristic:
+    return "heuristic";
+  }
+  return "unknown";
+}
+
+[[nodiscard]] MachineInstrStableID actionInstructionForRegister(const MachineFunction &Function,
+                                                                Register Reg) noexcept {
+  const MachineOperand *Definition = Function.registerInfo().getUniqueVRegDef(Reg);
+  const MachineInstr *Instruction = Definition == nullptr ? nullptr : Definition->parent();
+  return Instruction == nullptr ? MachineInstrStableID{} : Instruction->stableID();
+}
+
 [[nodiscard]] pbqp::Cost boundedCost(std::uint64_t Value) noexcept {
   const std::uint64_t Limit = static_cast<std::uint64_t>(pbqp::InfiniteCost - 1);
   return static_cast<pbqp::Cost>(std::min(Value, Limit));
@@ -63,8 +85,9 @@ class PBQPAllocatorEngine final : public RegAllocBase {
 public:
   PBQPAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
                       const TargetRegisterAllocationInfo &TargetInfo,
-                      MachineAnalysisManager &Analyses, RegisterAllocationOptions Options)
-      : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {}
+                      MachineAnalysisManager &Analyses, RegisterAllocationOptions Options,
+                      MachineActionReplay *Actions)
+      : RegAllocBase(Function, Target, TargetInfo, Analyses, Options, Actions) {}
 
 private:
   [[nodiscard]] Expected<AllocationRoundResult>
@@ -152,8 +175,14 @@ private:
         std::uint32_t RightKey = Right.VirtualReg.opaqueValue();
         if (RightKey < LeftKey)
           std::swap(LeftKey, RightKey);
-        const bool CopyRelated =
-            Options.EnableCopyCoalescing && CopyPairs.contains({LeftKey, RightKey});
+        const auto CopyPosition = CopyPairs.find({LeftKey, RightKey});
+        bool CopyRelated = Options.EnableCopyCoalescing && CopyPosition != CopyPairs.end();
+        if (CopyRelated && Actions != nullptr) {
+          auto Accepted = Actions->request("coalesce-copy", Function, CopyPosition->second);
+          if (!Accepted)
+            return std::unexpected(Accepted.error());
+          CopyRelated = *Accepted;
+        }
         pbqp::CostMatrix Costs(Left.Options.size(), Right.Options.size(), 0);
         bool HasCost = false;
         for (std::size_t LeftOption = 1; LeftOption < Left.Options.size(); ++LeftOption) {
@@ -188,7 +217,23 @@ private:
     }
 
     pbqp::DeterministicSolver Solver;
-    auto Solution = Solver.solve(Problem);
+    auto Solution = Solver.solve(Problem, [&](const pbqp::SolverAction &Action) -> Expected<bool> {
+      if (Actions == nullptr)
+        return true;
+      if (Action.Node.value() >= Nodes.size()) {
+        return makeUnexpected(ErrorCode::InternalError,
+                              "PBQP action names an unknown allocation node");
+      }
+      const Register VirtualReg = Nodes[Action.Node.value()].VirtualReg;
+      std::string Rule =
+          Action.Kind == pbqp::SolverActionKind::Reduction ? "pbqp-reduce." : "pbqp-choice.";
+      Rule.append(reductionName(Action.Reduction));
+      if (Action.Kind == pbqp::SolverActionKind::Choice) {
+        Rule.append(".option-");
+        Rule.append(std::to_string(Action.Value));
+      }
+      return Actions->request(Rule, Function, actionInstructionForRegister(Function, VirtualReg));
+    });
     if (!Solution)
       return std::unexpected(Solution.error());
 
@@ -267,7 +312,9 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
   auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
   if (!Registered)
     return std::unexpected(Registered.error());
-  PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options);
+  MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
+  PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options,
+                                     &Actions);
   auto TrialRun = TrialAllocator.run();
   if (!TrialRun)
     return std::unexpected(TrialRun.error());
@@ -275,12 +322,16 @@ Expected<MachinePassResult> PBQPAllocatorPass::run(MachineFunction &Function,
       regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
   if (!TrialVerification)
     return std::unexpected(TrialVerification.error());
-  PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
+  Actions.beginReplay();
+  PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options, &Actions);
   auto Allocated = Allocator.run();
   if (!Allocated) {
     return std::unexpected(regalloc_detail::withPrefix(
         Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: "));
   }
+  auto Replayed = Actions.finishReplay();
+  if (!Replayed)
+    return std::unexpected(Replayed.error());
   auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
   if (!Reserved)
     return std::unexpected(Reserved.error());
diff --git a/backend/lib/CodeGen/RegisterPressure.cpp b/backend/lib/CodeGen/RegisterPressure.cpp
index 523a443..cbd8d8e 100644
--- a/backend/lib/CodeGen/RegisterPressure.cpp
+++ b/backend/lib/CodeGen/RegisterPressure.cpp
@@ -102,12 +102,12 @@ struct RegisterPressureBuilder final {
     auto Info = Function->registerInfo().virtualRegisterInfo(Reg);
     if (!Info)
       return std::unexpected(Info.error());
-    if (!Info->get().RegClass) {
+    const auto &RegClass = Info->get().RegClass;
+    if (!RegClass) {
       return makeUnexpected(ErrorCode::VerificationError,
                             "pre-RA pressure tracking requires constrained virtual registers");
     }
-    const std::span<const RegisterPressureSetID> Sets =
-        Model->pressureSetsForClass(*Info->get().RegClass);
+    const std::span<const RegisterPressureSetID> Sets = Model->pressureSetsForClass(*RegClass);
     return std::vector<RegisterPressureSetID>{Sets.begin(), Sets.end()};
   }