[CodeGen] Align pass manager ownership

1 files changed, 1099 insertions, 0 deletions

diff --git a/backend/lib/CodeGen/MachinePassManager.cpp b/backend/lib/CodeGen/MachinePassManager.cpp
new file mode 100644
index 0000000..0810965
--- /dev/null
+++ b/backend/lib/CodeGen/MachinePassManager.cpp
@@ -0,0 +1,1099 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/CodeGen/MachinePassManager.h"
+
+#include "rcc/CodeGen/CompilationUnit.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineFunctionCloner.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+
+#include <algorithm>
+#include <atomic>
+#include <chrono>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <memory>
+#include <optional>
+#include <ranges>
+#include <set>
+#include <string>
+#include <string_view>
+#include <thread>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+
+thread_local MachinePassInstrumentation::BufferedEvents *MachinePassInstrumentation::ActiveBuffer =
+    nullptr;
+
+namespace {
+
+using Clock = std::chrono::steady_clock;
+
+[[nodiscard]] std::uint64_t elapsedNanoseconds(Clock::time_point Start) noexcept {
+  const auto Elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(Clock::now() - Start);
+  if (Elapsed.count() <= 0)
+    return 0;
+  return static_cast<std::uint64_t>(Elapsed.count());
+}
+
+[[nodiscard]] Error prefixedError(const Error &Source, std::string Prefix) {
+  Prefix.append(Source.message());
+  return Error(Source.code(), std::move(Prefix));
+}
+
+[[nodiscard]] bool hasDuplicateAnalysisIDs(std::span<const AnalysisID> IDs) {
+  std::unordered_set<AnalysisID> Unique;
+  for (const AnalysisID ID : IDs) {
+    if (ID == nullptr || !Unique.insert(ID).second)
+      return true;
+  }
+  return false;
+}
+
+[[nodiscard]] Expected<void> validateParameters(std::span<const PassParameter> Parameters) {
+  std::unordered_set<std::string> Names;
+  for (const PassParameter &Parameter : Parameters) {
+    if (Parameter.Name.empty())
+      return makeUnexpected(ErrorCode::InvalidArgument, "pass parameter name cannot be empty");
+    if (!Names.insert(Parameter.Name).second)
+      return makeUnexpected(ErrorCode::InvalidArgument, "pass parameter names must be unique");
+    if (Parameter.Required && Parameter.DefaultValue) {
+      return makeUnexpected(ErrorCode::InvalidArgument,
+                            "a required pass parameter cannot have a default value");
+    }
+  }
+  return {};
+}
+
+void combineFingerprint(std::uint64_t &State, std::uint64_t Value) noexcept {
+  State ^= Value + 0x9e3779b97f4a7c15ULL + (State << 6U) + (State >> 2U);
+}
+
+[[nodiscard]] std::uint64_t machineFunctionFingerprint(const MachineFunction &Function) noexcept {
+  std::uint64_t Result = 0xcbf29ce484222325ULL;
+  combineFingerprint(Result, Function.stableID().value());
+  combineFingerprint(Result, Function.properties().rawValue());
+  combineFingerprint(Result, Function.blockCount());
+  combineFingerprint(Result, Function.allInstructions().size());
+  combineFingerprint(Result, Function.allMemOperands().size());
+
+  for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr;
+       Block = Block->next()) {
+    combineFingerprint(Result, Block->stableID().value());
+    combineFingerprint(Result, Block->instructionCount());
+    combineFingerprint(Result, Block->successors().size());
+    for (const MachineSuccessor &Successor : Block->successors()) {
+      combineFingerprint(Result,
+                         Successor.Block == nullptr ? 0 : Successor.Block->stableID().value());
+      combineFingerprint(Result, Successor.Probability.rawValue());
+    }
+    for (const MachineBasicBlockLiveIn &LiveIn : Block->liveIns()) {
+      combineFingerprint(Result, LiveIn.PhysReg.number());
+      combineFingerprint(Result, LiveIn.Lanes.rawValue());
+    }
+
+    for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
+         Instruction = Instruction->next()) {
+      combineFingerprint(Result, Instruction->stableID().value());
+      combineFingerprint(Result, Instruction->opcode().value());
+      combineFingerprint(Result, Instruction->flags().rawValue());
+      combineFingerprint(Result, Instruction->operandCount());
+      combineFingerprint(Result, Instruction->memOperands().size());
+      for (const MachineOperand &Operand : Instruction->operands()) {
+        combineFingerprint(Result, static_cast<std::uint64_t>(Operand.kind()));
+        combineFingerprint(Result, Operand.targetFlags());
+        combineFingerprint(Result, Operand.registerFlags().rawValue());
+        combineFingerprint(Result, Operand.subReg().value());
+        if (const Register *Reg = Operand.getIf<Register>())
+          combineFingerprint(Result, Reg->opaqueValue());
+        else if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>())
+          combineFingerprint(Result, static_cast<std::uint64_t>(*Immediate));
+      }
+    }
+  }
+  return Result;
+}
+
+[[nodiscard]] Expected<void> verifyCompilationUnit(const CompilationUnit &Unit,
+                                                   const TargetDescription &Target) {
+  auto UnitVerification = Unit.verify();
+  if (!UnitVerification)
+    return std::unexpected(UnitVerification.error());
+  for (std::size_t Index = 0; Index < Unit.functionCount(); ++Index) {
+    const MachineFunction *Function = Unit.functionAt(Index);
+    if (Function == nullptr)
+      return makeUnexpected(ErrorCode::InternalError,
+                            "compilation unit function order contains a null entry");
+    auto FunctionVerification = MachineVerifier::verify(*Function, Target);
+    if (!FunctionVerification)
+      return std::unexpected(FunctionVerification.error());
+  }
+  return {};
+}
+
+} // namespace
+
+void AnalysisManagerInstrumentation<MachineFunction, MachinePassInstrumentation>::beforeAnalysis(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name,
+    const MachineFunction &Function) {
+  Instrumentation->beforeAnalysis(Name, Function);
+}
+
+void AnalysisManagerInstrumentation<MachineFunction, MachinePassInstrumentation>::afterAnalysis(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name,
+    const MachineFunction &Function, bool CacheHit, std::uint64_t Nanoseconds) {
+  Instrumentation->afterAnalysis(Name, Function, CacheHit, Nanoseconds);
+}
+
+void AnalysisManagerInstrumentation<MachineFunction, MachinePassInstrumentation>::analysisFailure(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name,
+    const MachineFunction &Function, const Error &Failure, std::uint64_t Nanoseconds) {
+  Instrumentation->analysisFailure(Name, Function, Failure, Nanoseconds);
+}
+
+Expected<bool>
+AnalysisManagerInstrumentation<MachineFunction, MachinePassInstrumentation>::requestAction(
+    MachinePassInstrumentation *Instrumentation, std::string_view Pass, std::string_view Rule,
+    const MachineFunction &Function, MachineInstrStableID Instruction, std::uint64_t Cost) {
+  return Instrumentation->requestAction(Pass, Rule, Function, Instruction, Cost);
+}
+
+Expected<bool>
+AnalysisManagerInstrumentation<MachineFunction, MachinePassInstrumentation>::requestAction(
+    MachinePassInstrumentation *Instrumentation, std::string_view Pass, std::string_view Rule,
+    const MachineFunction &Function, std::nullptr_t, std::uint64_t Cost) {
+  return Instrumentation->requestAction(Pass, Rule, Function, nullptr, Cost);
+}
+
+void AnalysisManagerInstrumentation<CompilationUnit, MachinePassInstrumentation>::beforeAnalysis(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name,
+    const CompilationUnit &Unit) {
+  Instrumentation->beforeAnalysis(Name, Unit);
+}
+
+void AnalysisManagerInstrumentation<CompilationUnit, MachinePassInstrumentation>::afterAnalysis(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name, const CompilationUnit &Unit,
+    bool CacheHit, std::uint64_t Nanoseconds) {
+  Instrumentation->afterAnalysis(Name, Unit, CacheHit, Nanoseconds);
+}
+
+void AnalysisManagerInstrumentation<CompilationUnit, MachinePassInstrumentation>::analysisFailure(
+    MachinePassInstrumentation *Instrumentation, std::string_view Name, const CompilationUnit &Unit,
+    const Error &Failure, std::uint64_t Nanoseconds) {
+  Instrumentation->analysisFailure(Name, Unit, Failure, Nanoseconds);
+}
+
+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 = Request(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 {};
+}
+
+void MachinePassInstrumentation::addBeforeCallback(BeforeCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  Before.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addAfterCallback(AfterCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  After.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addFailureCallback(FailureCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  Failure.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addBeforeAnalysisCallback(BeforeAnalysisCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  BeforeAnalysis.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addAfterAnalysisCallback(AfterAnalysisCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  AfterAnalysis.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addAnalysisFailureCallback(AnalysisFailureCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  AnalysisFailure.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addIRPrintCallback(IRPrintCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  IRPrint.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addChangeCallback(ChangeCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  Change.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::setActionFilter(ActionFilter NewFilter) {
+  std::scoped_lock Lock(Mutex);
+  Filter = std::move(NewFilter);
+}
+
+void MachinePassInstrumentation::setPerFunctionFuel(std::optional<std::uint64_t> Fuel) {
+  std::scoped_lock Lock(Mutex);
+  PerFunctionFuel = Fuel;
+  ConsumedFuel.clear();
+  ActionEvents.clear();
+}
+
+void MachinePassInstrumentation::addBeforeUnitCallback(BeforeUnitCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  BeforeUnit.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addAfterUnitCallback(AfterUnitCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  AfterUnit.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addUnitFailureCallback(UnitFailureCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  UnitFailure.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addBeforeUnitAnalysisCallback(
+    BeforeUnitAnalysisCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  BeforeUnitAnalysis.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addAfterUnitAnalysisCallback(AfterUnitAnalysisCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  AfterUnitAnalysis.push_back(std::move(Callback));
+}
+
+void MachinePassInstrumentation::addUnitAnalysisFailureCallback(
+    UnitAnalysisFailureCallback Callback) {
+  if (!Callback)
+    return;
+  std::scoped_lock Lock(Mutex);
+  UnitAnalysisFailure.push_back(std::move(Callback));
+}
+
+InstrumentationStatistic &MachinePassInstrumentation::statistic(std::string_view Name,
+                                                                bool IsAnalysis) const {
+  const std::string Key = std::string(IsAnalysis ? "analysis:" : "pass:") + std::string(Name);
+  auto [Position, Inserted] = Statistics.try_emplace(Key);
+  if (Inserted) {
+    Position->second.Name = std::string(Name);
+    Position->second.IsAnalysis = IsAnalysis;
+  }
+  return Position->second;
+}
+
+bool MachinePassInstrumentation::bufferFunctionEvent(
+    const MachineFunction &Function, std::function<void(const MachineFunction &)> Replay) const {
+  if (ActiveBuffer == nullptr)
+    return false;
+
+  std::shared_ptr<const MachineFunction> Snapshot;
+  auto Cloned = cloneMachineFunction(
+      Function, *ActiveBuffer->Target,
+      MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
+  if (Cloned) {
+    Snapshot = std::shared_ptr<const MachineFunction>(std::move(Cloned->ClonedFunction));
+  } else {
+    Snapshot =
+        std::shared_ptr<const MachineFunction>(&Function, [](const MachineFunction *) noexcept {});
+  }
+  ActiveBuffer->Events.emplace_back(
+      [Snapshot = std::move(Snapshot), Replay = std::move(Replay)]() { Replay(*Snapshot); });
+  return true;
+}
+
+void MachinePassInstrumentation::beginBuffering(BufferedEvents &Buffer,
+                                                const TargetDescription &Target) const noexcept {
+  Buffer.Target = &Target;
+  Buffer.Events.clear();
+  ActiveBuffer = &Buffer;
+}
+
+void MachinePassInstrumentation::endBuffering() const noexcept {
+  ActiveBuffer = nullptr;
+}
+
+void MachinePassInstrumentation::replayBufferedEvents(BufferedEvents &Buffer) const {
+  for (const std::function<void()> &Event : Buffer.Events)
+    Event();
+  Buffer.Events.clear();
+  Buffer.Target = nullptr;
+}
+
+void MachinePassInstrumentation::before(std::string_view Name,
+                                        const MachineFunction &Function) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name)](const MachineFunction &Input) {
+        before(Name, Input);
+      })) {
+    return;
+  }
+  std::vector<BeforeCallback> Callbacks;
+  std::vector<IRPrintCallback> Printers;
+  {
+    std::scoped_lock Lock(Mutex);
+    Callbacks = Before;
+    Printers = IRPrint;
+  }
+  for (const BeforeCallback &Callback : Callbacks)
+    Callback(Name, Function);
+  for (const IRPrintCallback &Printer : Printers)
+    Printer(InstrumentationPhase::Before, Name, Function);
+}
+
+void MachinePassInstrumentation::after(std::string_view Name, const MachineFunction &Function,
+                                       const MachinePassResult &Result,
+                                       std::uint64_t Nanoseconds) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name), Result,
+                                     Nanoseconds](const MachineFunction &Input) {
+        after(Name, Input, Result, Nanoseconds);
+      })) {
+    return;
+  }
+  std::vector<AfterCallback> Callbacks;
+  std::vector<IRPrintCallback> Printers;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic(Name, false);
+    ++Record.Invocations;
+    Record.Changes += Result.Changed ? 1U : 0U;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = After;
+    Printers = IRPrint;
+  }
+  for (const AfterCallback &Callback : Callbacks)
+    Callback(Name, Function, Result);
+  for (const IRPrintCallback &Printer : Printers)
+    Printer(InstrumentationPhase::After, Name, Function);
+}
+
+void MachinePassInstrumentation::failure(std::string_view Name, const MachineFunction &Function,
+                                         const Error &ErrorValue, std::uint64_t Nanoseconds) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name), ErrorValue,
+                                     Nanoseconds](const MachineFunction &Input) {
+        failure(Name, Input, ErrorValue, Nanoseconds);
+      })) {
+    return;
+  }
+  std::vector<FailureCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic(Name, false);
+    ++Record.Invocations;
+    ++Record.Failures;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = Failure;
+  }
+  for (const FailureCallback &Callback : Callbacks)
+    Callback(Name, Function, ErrorValue);
+}
+
+void MachinePassInstrumentation::beforeAnalysis(std::string_view Name,
+                                                const MachineFunction &Function) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name)](const MachineFunction &Input) {
+        beforeAnalysis(Name, Input);
+      })) {
+    return;
+  }
+  std::vector<BeforeAnalysisCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    Callbacks = BeforeAnalysis;
+  }
+  for (const BeforeAnalysisCallback &Callback : Callbacks)
+    Callback(Name, Function);
+}
+
+void MachinePassInstrumentation::afterAnalysis(std::string_view Name,
+                                               const MachineFunction &Function, bool CacheHit,
+                                               std::uint64_t Nanoseconds) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name), CacheHit,
+                                     Nanoseconds](const MachineFunction &Input) {
+        afterAnalysis(Name, Input, CacheHit, Nanoseconds);
+      })) {
+    return;
+  }
+  std::vector<AfterAnalysisCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic(Name, true);
+    ++Record.Invocations;
+    Record.CacheHits += CacheHit ? 1U : 0U;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = AfterAnalysis;
+  }
+  for (const AfterAnalysisCallback &Callback : Callbacks)
+    Callback(Name, Function, CacheHit, Nanoseconds);
+}
+
+void MachinePassInstrumentation::analysisFailure(std::string_view Name,
+                                                 const MachineFunction &Function,
+                                                 const Error &ErrorValue,
+                                                 std::uint64_t Nanoseconds) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name), ErrorValue,
+                                     Nanoseconds](const MachineFunction &Input) {
+        analysisFailure(Name, Input, ErrorValue, Nanoseconds);
+      })) {
+    return;
+  }
+  std::vector<AnalysisFailureCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic(Name, true);
+    ++Record.Invocations;
+    ++Record.Failures;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = AnalysisFailure;
+  }
+  for (const AnalysisFailureCallback &Callback : Callbacks)
+    Callback(Name, Function, ErrorValue);
+}
+
+void MachinePassInstrumentation::change(std::string_view Name, const MachineFunction &Function,
+                                        MachinePassChanges Changes, bool FingerprintChanged) const {
+  if (bufferFunctionEvent(Function, [this, Name = std::string(Name), Changes,
+                                     FingerprintChanged](const MachineFunction &Input) {
+        change(Name, Input, Changes, FingerprintChanged);
+      })) {
+    return;
+  }
+  std::vector<ChangeCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    Callbacks = Change;
+  }
+  for (const ChangeCallback &Callback : Callbacks)
+    Callback(Name, Function, Changes, FingerprintChanged);
+}
+
+Expected<bool> MachinePassInstrumentation::requestAction(std::string_view Pass,
+                                                         std::string_view Rule,
+                                                         const MachineFunction &Function,
+                                                         MachineInstrStableID Instruction,
+                                                         std::uint64_t Cost) {
+  MachineActionID Action{
+      .Pass = std::string(Pass),
+      .Rule = std::string(Rule),
+      .Function = Function.stableID(),
+      .Instruction = Instruction,
+  };
+  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, Cost)) {
+    std::scoped_lock Lock(Mutex);
+    ActionEvents.push_back({Action, Cost, false});
+    return false;
+  }
+
+  std::scoped_lock Lock(Mutex);
+  if (!PerFunctionFuel) {
+    ActionEvents.push_back({Action, Cost, true});
+    return true;
+  }
+  std::uint64_t &Consumed = ConsumedFuel[Function.stableID().value()];
+  if (Consumed > *PerFunctionFuel || Cost > *PerFunctionFuel - Consumed) {
+    ActionEvents.push_back({Action, Cost, false});
+    return false;
+  }
+  Consumed += Cost;
+  ActionEvents.push_back({Action, Cost, true});
+  return true;
+}
+
+Expected<bool> MachinePassInstrumentation::requestAction(std::string_view Pass,
+                                                         std::string_view Rule,
+                                                         const MachineFunction &Function,
+                                                         std::nullptr_t, std::uint64_t Cost) {
+  return requestAction(Pass, Rule, Function, MachineInstrStableID{}, Cost);
+}
+
+void MachinePassInstrumentation::beforeUnit(std::string_view Name,
+                                            const CompilationUnit &Unit) const {
+  std::vector<BeforeUnitCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    Callbacks = BeforeUnit;
+  }
+  for (const BeforeUnitCallback &Callback : Callbacks)
+    Callback(Name, Unit);
+}
+
+void MachinePassInstrumentation::afterUnit(std::string_view Name, const CompilationUnit &Unit,
+                                           const CompilationUnitPassResult &Result,
+                                           std::uint64_t Nanoseconds) const {
+  std::vector<AfterUnitCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), false);
+    ++Record.Invocations;
+    Record.Changes += Result.Changed ? 1U : 0U;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = AfterUnit;
+  }
+  for (const AfterUnitCallback &Callback : Callbacks)
+    Callback(Name, Unit, Result);
+}
+
+void MachinePassInstrumentation::unitFailure(std::string_view Name, const CompilationUnit &Unit,
+                                             const Error &ErrorValue,
+                                             std::uint64_t Nanoseconds) const {
+  std::vector<UnitFailureCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), false);
+    ++Record.Invocations;
+    ++Record.Failures;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = UnitFailure;
+  }
+  for (const UnitFailureCallback &Callback : Callbacks)
+    Callback(Name, Unit, ErrorValue);
+}
+
+void MachinePassInstrumentation::beforeAnalysis(std::string_view Name,
+                                                const CompilationUnit &Unit) const {
+  std::vector<BeforeUnitAnalysisCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    Callbacks = BeforeUnitAnalysis;
+  }
+  for (const BeforeUnitAnalysisCallback &Callback : Callbacks)
+    Callback(Name, Unit);
+}
+
+void MachinePassInstrumentation::afterAnalysis(std::string_view Name, const CompilationUnit &Unit,
+                                               bool CacheHit, std::uint64_t Nanoseconds) const {
+  std::vector<AfterUnitAnalysisCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), true);
+    ++Record.Invocations;
+    Record.CacheHits += CacheHit ? 1U : 0U;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = AfterUnitAnalysis;
+  }
+  for (const AfterUnitAnalysisCallback &Callback : Callbacks)
+    Callback(Name, Unit, CacheHit, Nanoseconds);
+}
+
+void MachinePassInstrumentation::analysisFailure(std::string_view Name, const CompilationUnit &Unit,
+                                                 const Error &ErrorValue,
+                                                 std::uint64_t Nanoseconds) const {
+  std::vector<UnitAnalysisFailureCallback> Callbacks;
+  {
+    std::scoped_lock Lock(Mutex);
+    InstrumentationStatistic &Record = statistic("unit:" + std::string(Name), true);
+    ++Record.Invocations;
+    ++Record.Failures;
+    Record.TotalNanoseconds += Nanoseconds;
+    Callbacks = UnitAnalysisFailure;
+  }
+  for (const UnitAnalysisFailureCallback &Callback : Callbacks)
+    Callback(Name, Unit, ErrorValue);
+}
+
+std::vector<InstrumentationStatistic> MachinePassInstrumentation::statistics() const {
+  std::vector<InstrumentationStatistic> Result;
+  {
+    std::scoped_lock Lock(Mutex);
+    Result.reserve(Statistics.size());
+    for (const auto &[Key, Record] : Statistics) {
+      (void)Key;
+      Result.push_back(Record);
+    }
+  }
+  std::ranges::sort(
+      Result, [](const InstrumentationStatistic &Left, const InstrumentationStatistic &Right) {
+        if (Left.IsAnalysis != Right.IsAnalysis)
+          return Left.IsAnalysis < Right.IsAnalysis;
+        return Left.Name < Right.Name;
+      });
+  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;
+}
+
+Expected<void>
+PassManagerCallbacks<MachineFunction, MachineFunctionPass, MachinePassManagerOptions>::validate(
+    const MachineFunctionPass &Pass) {
+  const MachinePassContract &Contract = Pass.contract();
+  if (Contract.Name.empty())
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine pass must have a non-empty name");
+  if (Contract.Sets.intersects(Contract.Clears)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine pass cannot set and clear the same property");
+  }
+  if (hasDuplicateAnalysisIDs(Contract.RequiredAnalyses)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "machine pass required analyses must be non-null and unique");
+  }
+  return validateParameters(Contract.Parameters);
+}
+
+Expected<void>
+PassManagerCallbacks<MachineFunction, MachineFunctionPass, MachinePassManagerOptions>::run(
+    const PassList &Passes, const MachinePassManagerOptions &Options, MachineFunction &Function,
+    const TargetDescription &Target, MachineFunctionAnalysisManager &Analyses,
+    MachinePassInstrumentation *Instrumentation) {
+  Analyses.setInstrumentation(Instrumentation);
+  for (const std::unique_ptr<MachineFunctionPass> &Pass : Passes) {
+    const MachinePassContract &Contract = Pass->contract();
+    const std::string_view Name = Contract.Name;
+
+    if (const MachineFunctionProperties Missing =
+            Contract.Requires.missingFrom(Function.properties());
+        !Missing.empty()) {
+      Error Failure(ErrorCode::VerificationError,
+                    "pass '" + std::string(Name) + "' requires properties: " + Missing.toString());
+      if (Instrumentation != nullptr)
+        Instrumentation->failure(Name, Function, Failure);
+      Analyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+
+    if (Options.VerifyBefore) {
+      auto Verification = MachineVerifier::verify(Function, Target);
+      if (!Verification) {
+        Error Failure = prefixedError(Verification.error(), "pass '" + std::string(Name) +
+                                                                "' received invalid MachineIR: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->failure(Name, Function, Failure);
+        Analyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+
+    for (const AnalysisID Required : Contract.RequiredAnalyses) {
+      auto Result = Analyses.getResultByID(Required, Function, Target);
+      if (!Result) {
+        Error Failure =
+            prefixedError(Result.error(), "pass '" + std::string(Name) +
+                                              "' could not materialize a required analysis: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->failure(Name, Function, Failure);
+        Analyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+
+    const std::uint64_t FingerprintBefore =
+        Options.DetectUnreportedChanges ? machineFunctionFingerprint(Function) : 0;
+    if (Instrumentation != nullptr)
+      Instrumentation->before(Name, Function);
+    const Clock::time_point Start = Clock::now();
+    Analyses.setActivePass(std::string(Name));
+    auto PassResult = Pass->run(Function, Target, Analyses);
+    Analyses.setActivePass({});
+    const std::uint64_t Duration = elapsedNanoseconds(Start);
+    if (!PassResult) {
+      Error Failure =
+          prefixedError(PassResult.error(), "pass '" + std::string(Name) + "' failed: ");
+      if (Instrumentation != nullptr)
+        Instrumentation->failure(Name, Function, Failure, Duration);
+      Analyses.clear(Function);
+      Analyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+
+    if (PassResult->Changed != !PassResult->Changes.empty()) {
+      Error Failure(ErrorCode::VerificationError,
+                    "pass '" + std::string(Name) +
+                        "' reported inconsistent changed state and modification categories");
+      if (Instrumentation != nullptr)
+        Instrumentation->failure(Name, Function, Failure, Duration);
+      Analyses.clear(Function);
+      Analyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+    if (!Contract.DeclaredChanges.contains(PassResult->Changes)) {
+      Error Failure(ErrorCode::VerificationError,
+                    "pass '" + std::string(Name) +
+                        "' reported a modification category absent from its registration");
+      if (Instrumentation != nullptr)
+        Instrumentation->failure(Name, Function, Failure, Duration);
+      Analyses.clear(Function);
+      Analyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+
+    bool FingerprintChanged = PassResult->Changed;
+    if (Options.DetectUnreportedChanges) {
+      FingerprintChanged = FingerprintBefore != machineFunctionFingerprint(Function);
+      if (FingerprintChanged && !PassResult->Changed) {
+        Error Failure(ErrorCode::VerificationError,
+                      "pass '" + std::string(Name) +
+                          "' changed MachineIR without reporting a modification");
+        if (Instrumentation != nullptr)
+          Instrumentation->failure(Name, Function, Failure, Duration);
+        Analyses.clear(Function);
+        Analyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+    if (Instrumentation != nullptr)
+      Instrumentation->change(Name, Function, PassResult->Changes, FingerprintChanged);
+
+    auto Transition =
+        Function.properties().applyTransition(Contract.Requires, Contract.Sets, Contract.Clears);
+    if (!Transition) {
+      Error Failure =
+          prefixedError(Transition.error(), "pass '" + std::string(Name) +
+                                                "' produced an invalid property transition: ");
+      if (Instrumentation != nullptr)
+        Instrumentation->failure(Name, Function, Failure, Duration);
+      Analyses.clear(Function);
+      Analyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+    Analyses.invalidate(Function, PassResult->Preserved, PassResult->Changes);
+
+    if (Options.VerifyEach) {
+      MachineVerifierOptions VerifyOptions;
+      VerifyOptions.Stage = Contract.VerificationStage;
+      auto Verification = MachineVerifier::verify(Function, Target, VerifyOptions);
+      if (!Verification) {
+        Error Failure = prefixedError(Verification.error(),
+                                      "pass '" + std::string(Name) + "' left invalid MachineIR: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->failure(Name, Function, Failure, Duration);
+        Analyses.clear(Function);
+        Analyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+    if (Instrumentation != nullptr)
+      Instrumentation->after(Name, Function, *PassResult, Duration);
+  }
+  Analyses.setInstrumentation(nullptr);
+  return {};
+}
+
+Expected<void>
+PassManagerCallbacks<MachineFunction, MachineFunctionPass, MachinePassManagerOptions>::runFunctions(
+    const PassList &Passes, const MachinePassManagerOptions &Options, CompilationUnit &Unit,
+    const TargetDescription &Target, const MachineFunctionAnalysisManager &AnalysisPrototype,
+    std::size_t ThreadCount, MachinePassInstrumentation *Instrumentation) {
+  if (ThreadCount == 0)
+    return makeUnexpected(ErrorCode::InvalidArgument, "machine pass thread count must be nonzero");
+  auto UnitVerification = verifyCompilationUnit(Unit, Target);
+  if (!UnitVerification)
+    return std::unexpected(UnitVerification.error());
+  const std::size_t FunctionCount = Unit.functionCount();
+  if (FunctionCount == 0)
+    return {};
+  const std::size_t WorkerCount = std::min(ThreadCount, FunctionCount);
+  if (WorkerCount > 1) {
+    for (const std::unique_ptr<MachineFunctionPass> &Pass : Passes) {
+      if (Pass->contract().ThreadSafety != PassThreadSafety::ThreadSafe) {
+        return makeUnexpected(ErrorCode::InvalidArgument,
+                              "parallel machine pipeline contains a pass not marked thread-safe");
+      }
+      auto AnalysisSafety =
+          AnalysisPrototype.validateParallelRequirements(Pass->contract().RequiredAnalyses);
+      if (!AnalysisSafety)
+        return std::unexpected(AnalysisSafety.error());
+    }
+  }
+  std::vector<std::unique_ptr<MachineFunctionAnalysisManager>> Managers;
+  Managers.reserve(FunctionCount);
+  for (std::size_t Index = 0; Index < FunctionCount; ++Index) {
+    auto Manager = AnalysisPrototype.forkEmpty();
+    if (!Manager)
+      return std::unexpected(Manager.error());
+    Managers.push_back(std::move(*Manager));
+  }
+
+  std::vector<std::optional<Error>> Failures(FunctionCount);
+  std::vector<MachinePassInstrumentation::BufferedEvents> EventBuffers(FunctionCount);
+  std::atomic<std::size_t> NextFunction = 0;
+  const auto Worker = [&]() {
+    while (true) {
+      const std::size_t Index = NextFunction.fetch_add(1, std::memory_order_relaxed);
+      if (Index >= FunctionCount)
+        return;
+      MachineFunction *Function = Unit.functionAt(Index);
+      if (Function == nullptr) {
+        Failures[Index] = Error(ErrorCode::InternalError,
+                                "compilation unit contains a null function during parallel run");
+        continue;
+      }
+      if (Instrumentation != nullptr)
+        Instrumentation->beginBuffering(EventBuffers[Index], Target);
+      auto Result = PassManagerCallbacks::run(Passes, Options, *Function, Target, *Managers[Index],
+                                              Instrumentation);
+      if (Instrumentation != nullptr)
+        Instrumentation->endBuffering();
+      if (!Result)
+        Failures[Index] = Result.error();
+    }
+  };
+
+  std::vector<std::thread> Workers;
+  Workers.reserve(WorkerCount);
+  for (std::size_t Index = 0; Index < WorkerCount; ++Index)
+    Workers.emplace_back(Worker);
+  for (std::thread &WorkerThread : Workers)
+    WorkerThread.join();
+
+  for (std::size_t Index = 0; Index < FunctionCount; ++Index) {
+    if (Instrumentation != nullptr)
+      Instrumentation->replayBufferedEvents(EventBuffers[Index]);
+    const auto &Failure = Failures[Index];
+    if (Failure) {
+      return std::unexpected(prefixedError(
+          *Failure, "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: "));
+    }
+  }
+  return {};
+}
+
+Expected<void>
+PassManagerCallbacks<CompilationUnit, CompilationUnitPass,
+                     CompilationUnitPassManagerOptions>::validate(const CompilationUnitPass &Pass) {
+  const CompilationUnitPassContract &Contract = Pass.contract();
+  if (Contract.Name.empty()) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "compilation-unit pass must have a non-empty name");
+  }
+  if (hasDuplicateAnalysisIDs(Contract.RequiredAnalyses)) {
+    return makeUnexpected(ErrorCode::InvalidArgument,
+                          "compilation-unit pass required analyses must be non-null and unique");
+  }
+  auto Parameters = validateParameters(Contract.Parameters);
+  if (!Parameters)
+    return std::unexpected(Parameters.error());
+  return {};
+}
+
+Expected<void>
+PassManagerCallbacks<CompilationUnit, CompilationUnitPass, CompilationUnitPassManagerOptions>::run(
+    const PassList &Passes, const CompilationUnitPassManagerOptions &Options, CompilationUnit &Unit,
+    const TargetDescription &Target, CompilationUnitAnalysisManager &UnitAnalyses,
+    MachineFunctionAnalysisManager &FunctionAnalyses, MachinePassInstrumentation *Instrumentation) {
+  UnitAnalyses.setInstrumentation(Instrumentation);
+  FunctionAnalyses.setInstrumentation(Instrumentation);
+  for (const std::unique_ptr<CompilationUnitPass> &Pass : Passes) {
+    const CompilationUnitPassContract &Contract = Pass->contract();
+    const std::string_view Name = Contract.Name;
+
+    if (Options.VerifyBefore) {
+      auto Verification = verifyCompilationUnit(Unit, Target);
+      if (!Verification) {
+        Error Failure =
+            prefixedError(Verification.error(), "compilation-unit pass '" + std::string(Name) +
+                                                    "' received invalid MachineIR: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->unitFailure(Name, Unit, Failure);
+        UnitAnalyses.setInstrumentation(nullptr);
+        FunctionAnalyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+
+    for (const AnalysisID Required : Contract.RequiredAnalyses) {
+      auto Result = UnitAnalyses.getResultByID(Required, Unit, Target);
+      if (!Result) {
+        Error Failure =
+            prefixedError(Result.error(), "compilation-unit pass '" + std::string(Name) +
+                                              "' could not materialize a required analysis: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->unitFailure(Name, Unit, Failure);
+        UnitAnalyses.setInstrumentation(nullptr);
+        FunctionAnalyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+
+    if (Instrumentation != nullptr)
+      Instrumentation->beforeUnit(Name, Unit);
+    const Clock::time_point Start = Clock::now();
+    auto Result = Pass->run(Unit, Target, UnitAnalyses, FunctionAnalyses);
+    const std::uint64_t Duration = elapsedNanoseconds(Start);
+    if (!Result) {
+      Error Failure = prefixedError(Result.error(),
+                                    "compilation-unit pass '" + std::string(Name) + "' failed: ");
+      if (Instrumentation != nullptr)
+        Instrumentation->unitFailure(Name, Unit, Failure, Duration);
+      UnitAnalyses.clearAll();
+      FunctionAnalyses.clearAll();
+      UnitAnalyses.setInstrumentation(nullptr);
+      FunctionAnalyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+    if (Result->Changed != !Result->Changes.empty() ||
+        !Contract.DeclaredChanges.contains(Result->Changes)) {
+      Error Failure(ErrorCode::VerificationError,
+                    "compilation-unit pass '" + std::string(Name) +
+                        "' reported inconsistent or undeclared modifications");
+      if (Instrumentation != nullptr)
+        Instrumentation->unitFailure(Name, Unit, Failure, Duration);
+      UnitAnalyses.clearAll();
+      FunctionAnalyses.clearAll();
+      UnitAnalyses.setInstrumentation(nullptr);
+      FunctionAnalyses.setInstrumentation(nullptr);
+      return std::unexpected(std::move(Failure));
+    }
+
+    UnitAnalyses.invalidate(Unit, Result->PreservedUnitAnalyses, Result->Changes);
+    for (std::size_t Index = 0; Index < Unit.functionCount(); ++Index) {
+      MachineFunction *Function = Unit.functionAt(Index);
+      if (Function != nullptr) {
+        FunctionAnalyses.invalidate(*Function, Result->PreservedFunctionAnalyses, Result->Changes);
+      }
+    }
+    if (Options.VerifyEach) {
+      auto Verification = verifyCompilationUnit(Unit, Target);
+      if (!Verification) {
+        Error Failure =
+            prefixedError(Verification.error(), "compilation-unit pass '" + std::string(Name) +
+                                                    "' left invalid MachineIR: ");
+        if (Instrumentation != nullptr)
+          Instrumentation->unitFailure(Name, Unit, Failure, Duration);
+        UnitAnalyses.clearAll();
+        FunctionAnalyses.clearAll();
+        UnitAnalyses.setInstrumentation(nullptr);
+        FunctionAnalyses.setInstrumentation(nullptr);
+        return std::unexpected(std::move(Failure));
+      }
+    }
+    if (Instrumentation != nullptr)
+      Instrumentation->afterUnit(Name, Unit, *Result, Duration);
+  }
+  UnitAnalyses.setInstrumentation(nullptr);
+  FunctionAnalyses.setInstrumentation(nullptr);
+  return {};
+}
+
+} // namespace rcc