[Tooling] Complete backend tooling and validation

20 files changed, 754 insertions, 25 deletions

diff --git a/backend/include/rcc/CodeGen/MachineBlockPlacement.h b/backend/include/rcc/CodeGen/MachineBlockPlacement.h
index 27a06f4..52ddafd 100644
--- a/backend/include/rcc/CodeGen/MachineBlockPlacement.h
+++ b/backend/include/rcc/CodeGen/MachineBlockPlacement.h
@@ -15,9 +15,10 @@ public:
                                                 MachineAnalysisManager &Analyses) override;
 
 private:
-  [[nodiscard]] Expected<MachinePassResult>
-  runImplementation(MachineFunction &Function, const TargetDescription &Target,
-                    MachineAnalysisManager &Analyses) const;
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineAnalysisManager &Analyses,
+                                                              MachineActionReplay &Actions) const;
 };
 
 } // namespace rcc
diff --git a/backend/include/rcc/CodeGen/MachineBranchRelaxation.h b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
index 1793a54..c88c1d5 100644
--- a/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
+++ b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h
@@ -27,8 +27,9 @@ public:
                                                 MachineAnalysisManager &Analyses) override;
 
 private:
-  [[nodiscard]] Expected<MachinePassResult>
-  runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineActionReplay &Actions) const;
 
   const TargetBranchInfo *Info;
   MachineBranchRelaxationOptions Options;
diff --git a/backend/include/rcc/CodeGen/MachineCombiner.h b/backend/include/rcc/CodeGen/MachineCombiner.h
index 943d6ad..ef7f432 100644
--- a/backend/include/rcc/CodeGen/MachineCombiner.h
+++ b/backend/include/rcc/CodeGen/MachineCombiner.h
@@ -27,8 +27,9 @@ public:
                                                 MachineAnalysisManager &Analyses) override;
 
 private:
-  [[nodiscard]] Expected<MachinePassResult>
-  runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineActionReplay &Actions) const;
 
   const TargetMachineCombinerInfo *Info;
   MachineCombinerStage Stage;
diff --git a/backend/include/rcc/CodeGen/MachineCopyPropagation.h b/backend/include/rcc/CodeGen/MachineCopyPropagation.h
index 5f84ac6..e8ee788 100644
--- a/backend/include/rcc/CodeGen/MachineCopyPropagation.h
+++ b/backend/include/rcc/CodeGen/MachineCopyPropagation.h
@@ -33,8 +33,9 @@ public:
                                                 MachineAnalysisManager &Analyses) override;
 
 private:
-  [[nodiscard]] Expected<MachinePassResult>
-  runImplementation(MachineFunction &Function, const TargetDescription &Target) const;
+  [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
+                                                              const TargetDescription &Target,
+                                                              MachineActionReplay &Actions) const;
 
   const TargetSSAInfo *Info;
   MachineCopyPropagationStage Stage;
diff --git a/backend/include/rcc/CodeGen/MachinePass.h b/backend/include/rcc/CodeGen/MachinePass.h
index 1637954..ee67924 100644
--- a/backend/include/rcc/CodeGen/MachinePass.h
+++ b/backend/include/rcc/CodeGen/MachinePass.h
@@ -5,6 +5,7 @@
 
 #include "rcc/CodeGen/InstructionDescriptor.h"
 #include "rcc/CodeGen/MachineFunctionProperties.h"
+#include "rcc/CodeGen/StableID.h"
 #include "rcc/Support/Error.h"
 
 #include <concepts>
@@ -279,6 +280,9 @@ public:
   [[nodiscard]] Expected<std::unique_ptr<MachineAnalysisManager>> forkEmpty() const;
   [[nodiscard]] Expected<bool>
   requestAction(std::string_view Action, const MachineFunction &Function, std::uint64_t Cost = 1);
+  [[nodiscard]] Expected<bool> requestAction(std::string_view Rule, const MachineFunction &Function,
+                                             MachineInstrStableID Instruction,
+                                             std::uint64_t Cost = 1);
 
 private:
   using ErasedRunner = std::function<Expected<std::shared_ptr<void>>(
@@ -315,6 +319,7 @@ private:
   std::unordered_map<MachineFunction *, std::unordered_map<AnalysisID, CacheEntry>> Cache;
   std::unordered_map<MachineFunction *, std::vector<AnalysisID>> ActiveComputations;
   MachinePassInstrumentation *Instrumentation = nullptr;
+  std::string ActivePass;
 
   friend class MachinePassManager;
   friend class CompilationUnitPassManager;
@@ -473,6 +478,58 @@ struct InstrumentationStatistic final {
   std::uint64_t TotalNanoseconds = 0;
 };
 
+struct MachineActionID final {
+  std::string Pass;
+  std::string Rule;
+  MachineFunctionStableID Function;
+  MachineInstrStableID Instruction;
+
+  [[nodiscard]] std::string toString() const;
+
+  friend bool operator==(const MachineActionID &, const MachineActionID &) = default;
+};
+
+struct MachineActionEvent final {
+  MachineActionID ID;
+  std::uint64_t Cost = 0;
+  bool Accepted = false;
+
+  friend bool operator==(const MachineActionEvent &, const MachineActionEvent &) = default;
+};
+
+class MachineActionReplay final {
+public:
+  explicit MachineActionReplay(MachineAnalysisManager &Analyses) noexcept : Analyses(&Analyses) {}
+  MachineActionReplay(
+      MachineAnalysisManager &Analyses,
+      const std::unordered_map<MachineInstrStableID, MachineInstrStableID> &SourceToClone)
+      : Analyses(&Analyses) {
+    for (const auto &[Source, Clone] : SourceToClone)
+      RecordingInstructionIDs.try_emplace(Clone, Source);
+  }
+
+  [[nodiscard]] Expected<bool> request(std::string_view Rule, const MachineFunction &Function,
+                                       MachineInstrStableID Instruction = {},
+                                       std::uint64_t Cost = 1);
+  void beginReplay() noexcept;
+  [[nodiscard]] Expected<void> finishReplay() const;
+
+private:
+  struct Decision final {
+    std::string Rule;
+    MachineFunctionStableID Function;
+    MachineInstrStableID Instruction;
+    std::uint64_t Cost = 0;
+    bool Accepted = false;
+  };
+
+  MachineAnalysisManager *Analyses = nullptr;
+  std::unordered_map<MachineInstrStableID, MachineInstrStableID> RecordingInstructionIDs;
+  std::vector<Decision> Decisions;
+  std::size_t NextDecision = 0;
+  bool IsReplaying = false;
+};
+
 class MachinePassInstrumentation final {
 public:
   using BeforeCallback = std::function<void(std::string_view, const MachineFunction &)>;
@@ -489,8 +546,7 @@ public:
       std::function<void(InstrumentationPhase, std::string_view, const MachineFunction &)>;
   using ChangeCallback =
       std::function<void(std::string_view, const MachineFunction &, MachinePassChanges, bool)>;
-  using ActionFilter =
-      std::function<bool(std::string_view, const MachineFunction &, std::uint64_t)>;
+  using ActionFilter = std::function<bool(const MachineActionID &, std::uint64_t)>;
 
   using BeforeUnitCallback = std::function<void(std::string_view, const CompilationUnit &)>;
   using AfterUnitCallback = std::function<void(std::string_view, const CompilationUnit &,
@@ -522,6 +578,7 @@ public:
   void addUnitAnalysisFailureCallback(UnitAnalysisFailureCallback Callback);
 
   [[nodiscard]] std::vector<InstrumentationStatistic> statistics() const;
+  [[nodiscard]] std::vector<MachineActionEvent> actionEvents() const;
   void clearStatistics();
 
 private:
@@ -548,7 +605,7 @@ private:
                        const Error &ErrorValue, std::uint64_t Nanoseconds) const;
   void change(std::string_view Name, const MachineFunction &Function, MachinePassChanges Changes,
               bool FingerprintChanged) const;
-  [[nodiscard]] Expected<bool> requestAction(std::string_view Action,
+  [[nodiscard]] Expected<bool> requestAction(const MachineActionID &Action,
                                              const MachineFunction &Function, std::uint64_t Cost);
 
   void beforeUnit(std::string_view Name, const CompilationUnit &Unit) const;
@@ -577,6 +634,7 @@ private:
   ActionFilter Filter;
   std::optional<std::uint64_t> PerFunctionFuel;
   std::unordered_map<std::uint64_t, std::uint64_t> ConsumedFuel;
+  std::vector<MachineActionEvent> ActionEvents;
 
   std::vector<BeforeUnitCallback> BeforeUnit;
   std::vector<AfterUnitCallback> AfterUnit;
@@ -602,6 +660,8 @@ struct MachinePassManagerOptions final {
 
 class MachinePassManager final {
 public:
+  using PassList = std::vector<std::unique_ptr<MachineFunctionPass>>;
+
   explicit MachinePassManager(MachinePassManagerOptions Options = {}) : Options(Options) {}
 
   MachinePassManager(const MachinePassManager &) = delete;
@@ -620,11 +680,15 @@ public:
     return Passes.size();
   }
 
+  [[nodiscard]] PassList takePasses() && noexcept {
+    return std::move(Passes);
+  }
+
 private:
   [[nodiscard]] Expected<void> validateContract(const MachinePassContract &Contract) const;
 
   MachinePassManagerOptions Options;
-  std::vector<std::unique_ptr<MachineFunctionPass>> Passes;
+  PassList Passes;
 };
 
 struct CompilationUnitPassManagerOptions final {
diff --git a/backend/include/rcc/CodeGen/MachinePipelinePasses.h b/backend/include/rcc/CodeGen/MachinePipelinePasses.h
index c5bdac0..08f0dac 100644
--- a/backend/include/rcc/CodeGen/MachinePipelinePasses.h
+++ b/backend/include/rcc/CodeGen/MachinePipelinePasses.h
@@ -21,7 +21,7 @@ public:
 private:
   [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
                                                               const TargetDescription &Target,
-                                                              MachineAnalysisManager &Analyses);
+                                                              MachineActionReplay &Actions);
 
   const TargetLegalizerInfo *Info;
 };
@@ -53,7 +53,7 @@ public:
 private:
   [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
                                                               const TargetDescription &Target,
-                                                              MachineAnalysisManager &Analyses);
+                                                              MachineActionReplay &Actions);
 
   const TargetInstructionSelector *Info;
 };
diff --git a/backend/include/rcc/CodeGen/MachineSSAExit.h b/backend/include/rcc/CodeGen/MachineSSAExit.h
index d98c0b9..fdf74f0 100644
--- a/backend/include/rcc/CodeGen/MachineSSAExit.h
+++ b/backend/include/rcc/CodeGen/MachineSSAExit.h
@@ -21,7 +21,7 @@ public:
 private:
   [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
                                                               const TargetDescription &Target,
-                                                              MachineAnalysisManager &Analyses);
+                                                              MachineActionReplay &Actions);
 
   const TargetSSAInfo *Info = nullptr;
 };
@@ -39,7 +39,7 @@ public:
 private:
   [[nodiscard]] Expected<MachinePassResult> runImplementation(MachineFunction &Function,
                                                               const TargetDescription &Target,
-                                                              MachineAnalysisManager &Analyses);
+                                                              MachineActionReplay &Actions);
 
   const TargetSSAInfo *Info = nullptr;
 };
diff --git a/backend/include/rcc/CodeGen/PBQP/Solver.h b/backend/include/rcc/CodeGen/PBQP/Solver.h
index ff14857..f010fd1 100644
--- a/backend/include/rcc/CodeGen/PBQP/Solver.h
+++ b/backend/include/rcc/CodeGen/PBQP/Solver.h
@@ -9,6 +9,7 @@
 #include <algorithm>
 #include <cstddef>
 #include <cstdint>
+#include <functional>
 #include <map>
 #include <optional>
 #include <set>
@@ -18,9 +19,24 @@
 
 namespace rcc::pbqp {
 
+enum class SolverActionKind : std::uint8_t {
+  Reduction,
+  Choice,
+};
+
+struct SolverAction final {
+  SolverActionKind Kind = SolverActionKind::Reduction;
+  ReductionKind Reduction = ReductionKind::DegreeZero;
+  NodeID Node;
+  std::size_t Value = 0;
+};
+
 class DeterministicSolver final {
 public:
-  [[nodiscard]] Expected<Solution> solve(const Graph &Problem) const {
+  using ActionCallback = std::function<Expected<bool>(const SolverAction &)>;
+
+  [[nodiscard]] Expected<Solution> solve(const Graph &Problem,
+                                         const ActionCallback &Action = {}) const {
     auto Verified = Problem.verify();
     if (!Verified)
       return std::unexpected(Verified.error());
@@ -31,10 +47,24 @@ public:
     while (Work.activeNodeCount() != 0) {
       const NodeID Selected = Work.selectReductionNode();
       const std::size_t Degree = Work.degree(Selected);
-      Expected<ReductionRecord> Reduced = Degree == 0   ? Work.reduceDegreeZero(Selected)
-                                          : Degree == 1 ? Work.reduceDegreeOne(Selected)
-                                          : Degree == 2 ? Work.reduceDegreeTwo(Selected)
-                                                        : Work.reduceHeuristically(Selected);
+      const ReductionKind Kind = Degree == 0   ? ReductionKind::DegreeZero
+                                 : Degree == 1 ? ReductionKind::DegreeOne
+                                 : Degree == 2 ? ReductionKind::DegreeTwo
+                                               : ReductionKind::Heuristic;
+      if (Action) {
+        auto Accepted = Action({SolverActionKind::Reduction, Kind, Selected, Degree});
+        if (!Accepted)
+          return std::unexpected(Accepted.error());
+        if (!*Accepted) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "PBQP reduction action was rejected");
+        }
+      }
+      Expected<ReductionRecord> Reduced =
+          Kind == ReductionKind::DegreeZero  ? Work.reduceDegreeZero(Selected)
+          : Kind == ReductionKind::DegreeOne ? Work.reduceDegreeOne(Selected)
+          : Kind == ReductionKind::DegreeTwo ? Work.reduceDegreeTwo(Selected)
+                                             : Work.reduceHeuristically(Selected);
       if (!Reduced)
         return std::unexpected(Reduced.error());
       Reductions.push_back(std::move(*Reduced));
@@ -71,6 +101,15 @@ public:
           return makeUnexpected(ErrorCode::RegisterAllocationFailed,
                                 "PBQP reductions produced no finite option");
       }
+      if (Action) {
+        auto Accepted = Action({SolverActionKind::Choice, Record.Kind, Record.Node, Choice});
+        if (!Accepted)
+          return std::unexpected(Accepted.error());
+        if (!*Accepted) {
+          return makeUnexpected(ErrorCode::RegisterAllocationFailed,
+                                "PBQP choice action was rejected");
+        }
+      }
       auto Set = Result.setSelection(Record.Node, Choice);
       if (!Set)
         return std::unexpected(Set.error());
diff --git a/backend/include/rcc/CodeGen/RegisterPressure.h b/backend/include/rcc/CodeGen/RegisterPressure.h
index fa1209a..107bc29 100644
--- a/backend/include/rcc/CodeGen/RegisterPressure.h
+++ b/backend/include/rcc/CodeGen/RegisterPressure.h
@@ -22,7 +22,7 @@ struct MachineBlockLiveness;
 
 namespace detail {
 struct RegisterPressureBuilder;
-}
+} // namespace detail
 
 struct RegisterPressureValue final {
   RegisterPressureSetID Set;
diff --git a/backend/include/rcc/CodeGen/Spiller.h b/backend/include/rcc/CodeGen/Spiller.h
index 3d1fc66..f63158d 100644
--- a/backend/include/rcc/CodeGen/Spiller.h
+++ b/backend/include/rcc/CodeGen/Spiller.h
@@ -11,13 +11,16 @@
 
 namespace rcc {
 
+class MachineActionReplay;
+
 class Spiller final {
 public:
   Spiller(MachineFunction &Function, const TargetDescription &Target,
           const TargetRegisterAllocationInfo &TargetInfo, VirtRegMap &Mapping,
-          bool EnableRematerialization = true)
+          bool EnableRematerialization = true, MachineActionReplay *Actions = nullptr)
       : Function(&Function), Target(&Target), TargetInfo(&TargetInfo), Mapping(&Mapping),
-        Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization) {}
+        Edit(Function, Target, Mapping), EnableRematerialization(EnableRematerialization),
+        Actions(Actions) {}
 
   [[nodiscard]] Expected<std::vector<Register>> spill(Register VirtualReg);
 
@@ -34,6 +37,7 @@ private:
   VirtRegMap *Mapping;
   LiveRangeEdit Edit;
   bool EnableRematerialization;
+  MachineActionReplay *Actions;
 };
 
 } // namespace rcc
diff --git a/backend/include/rcc/Support/Error.h b/backend/include/rcc/Support/Error.h
index 63c0b2f..0429cc0 100644
--- a/backend/include/rcc/Support/Error.h
+++ b/backend/include/rcc/Support/Error.h
@@ -30,6 +30,12 @@ enum class ErrorCode : std::uint8_t {
   FixupApplicationFailed,
   RelocationFailed,
   ObjectWritingFailed,
+  InvalidInvocation,
+  ManifestError,
+  CacheMiss,
+  ReproducerError,
+  ReductionFailed,
+  FuzzingFailure,
 };
 
 [[nodiscard]] std::string_view getErrorCodeName(ErrorCode Code) noexcept;
diff --git a/backend/include/rcc/Support/SHA256.h b/backend/include/rcc/Support/SHA256.h
new file mode 100644
index 0000000..ff7b50b
--- /dev/null
+++ b/backend/include/rcc/Support/SHA256.h
@@ -0,0 +1,24 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_SUPPORT_SHA256_H
+#define RCC_SUPPORT_SHA256_H
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <span>
+#include <string>
+#include <string_view>
+
+namespace rcc {
+
+using SHA256Digest = std::array<std::uint8_t, 32>;
+
+[[nodiscard]] SHA256Digest sha256(std::span<const std::byte> Input);
+[[nodiscard]] SHA256Digest sha256(std::string_view Input);
+[[nodiscard]] std::string sha256Hex(std::span<const std::byte> Input);
+[[nodiscard]] std::string sha256Hex(std::string_view Input);
+
+} // namespace rcc
+
+#endif // RCC_SUPPORT_SHA256_H
diff --git a/backend/include/rcc/Target/RISCV/RISCVPipeline.h b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
new file mode 100644
index 0000000..8bd79e9
--- /dev/null
+++ b/backend/include/rcc/Target/RISCV/RISCVPipeline.h
@@ -0,0 +1,35 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TARGET_RISCV_RISCVPIPELINE_H
+#define RCC_TARGET_RISCV_RISCVPIPELINE_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/Support/Error.h"
+
+#include <memory>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class MachineFunction;
+class TargetDescription;
+
+namespace riscv {
+
+[[nodiscard]] Expected<void> addCanonicalPipeline(MachinePassManager &Pipeline,
+                                                  const MachineFunction &Function);
+[[nodiscard]] Expected<std::unique_ptr<MachineFunctionPass>>
+createCanonicalPipelinePass(std::string_view Name);
+[[nodiscard]] Expected<std::vector<std::string>>
+canonicalPipelinePassNames(const MachineFunction &Function);
+[[nodiscard]] Expected<void>
+runCanonicalPipeline(MachineFunction &Function, const TargetDescription &Target,
+                     MachinePassManagerOptions Options = {},
+                     MachinePassInstrumentation *Instrumentation = nullptr);
+
+} // namespace riscv
+} // namespace rcc
+
+#endif // RCC_TARGET_RISCV_RISCVPIPELINE_H
diff --git a/backend/include/rcc/Tooling/ArtifactStore.h b/backend/include/rcc/Tooling/ArtifactStore.h
new file mode 100644
index 0000000..a30f572
--- /dev/null
+++ b/backend/include/rcc/Tooling/ArtifactStore.h
@@ -0,0 +1,73 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_ARTIFACTSTORE_H
+#define RCC_TOOLING_ARTIFACTSTORE_H
+
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Support/Error.h"
+#include "rcc/Tooling/BackendManifest.h"
+
+#include <cstdint>
+#include <filesystem>
+#include <optional>
+#include <span>
+#include <string>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+struct CanonicalMIR final {
+  mir::MIRDocument Document;
+  std::string Text;
+};
+
+struct CacheEntry final {
+  BackendManifest Manifest;
+  std::string InputMIR;
+  std::vector<std::uint8_t> Artifact;
+  std::optional<CanonicalMIR> ParsedArtifact;
+};
+
+struct ReproducerPackage final {
+  BackendManifest Manifest;
+  CanonicalMIR Input;
+};
+
+[[nodiscard]] Expected<CanonicalMIR> parseAndCanonicalizeMIR(std::string SourceName,
+                                                             std::string SourceText,
+                                                             const TargetDescription &Target,
+                                                             const BackendInvocation &Invocation);
+
+[[nodiscard]] Expected<BackendManifest>
+createBackendManifest(ManifestKind Kind, ArtifactKind Artifact, const BackendInvocation &Invocation,
+                      const TargetDescription &Target, std::string_view CanonicalInputMIR,
+                      std::optional<std::span<const std::uint8_t>> ArtifactBytes = std::nullopt,
+                      std::vector<StructuredDiagnostic> Diagnostics = {});
+
+[[nodiscard]] Expected<void> storeCacheEntry(const std::filesystem::path &CacheRoot,
+                                             const BackendManifest &Manifest,
+                                             std::string_view CanonicalInputMIR,
+                                             std::span<const std::uint8_t> Artifact);
+[[nodiscard]] Expected<CacheEntry> loadCacheEntry(const std::filesystem::path &CacheRoot,
+                                                  ArtifactKind Artifact,
+                                                  const BackendInvocation &Invocation,
+                                                  const TargetDescription &Target,
+                                                  std::string_view CanonicalInputMIR);
+
+[[nodiscard]] Expected<void> writeReproducer(const std::filesystem::path &PackagePath,
+                                             const BackendManifest &Manifest,
+                                             std::string_view CanonicalInputMIR);
+[[nodiscard]] Expected<void>
+updateReproducerDiagnostics(const std::filesystem::path &PackagePath,
+                            std::vector<StructuredDiagnostic> Diagnostics);
+[[nodiscard]] Expected<ReproducerPackage> loadReproducer(const std::filesystem::path &PackagePath,
+                                                         const TargetDescription &Target);
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_ARTIFACTSTORE_H
diff --git a/backend/include/rcc/Tooling/BackendDriver.h b/backend/include/rcc/Tooling/BackendDriver.h
new file mode 100644
index 0000000..f762c1e
--- /dev/null
+++ b/backend/include/rcc/Tooling/BackendDriver.h
@@ -0,0 +1,56 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_BACKENDDRIVER_H
+#define RCC_TOOLING_BACKENDDRIVER_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/Support/Error.h"
+#include "rcc/Tooling/ArtifactStore.h"
+#include "rcc/Tooling/PipelineDriver.h"
+
+#include <cstdint>
+#include <span>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+enum class BackendOutputKind : std::uint8_t {
+  PreLegalizerMIR,
+  LegalizedMIR,
+  RegisterBankMIR,
+  SelectedMIR,
+  PostSSAMIR,
+  PostRegisterAllocationMIR,
+  FinalMIR,
+  Assembly,
+  RelocatableObject,
+};
+
+struct BackendRunResult final {
+  BackendOutputKind Kind = BackendOutputKind::FinalMIR;
+  std::vector<std::uint8_t> Output;
+  PipelineRunResult Pipeline;
+  std::vector<MachineActionEvent> Actions;
+
+  [[nodiscard]] std::string_view text() const noexcept;
+};
+
+[[nodiscard]] Expected<BackendRunResult>
+runBackend(CanonicalMIR Input, const TargetDescription &Target, const BackendInvocation &Invocation,
+           BackendOutputKind Output, PipelineControls Controls = {},
+           MachinePassInstrumentation *Instrumentation = nullptr);
+
+[[nodiscard]] std::string_view spelling(BackendOutputKind Output) noexcept;
+[[nodiscard]] Expected<BackendOutputKind> parseBackendOutputKind(std::string_view Value);
+[[nodiscard]] ArtifactKind manifestArtifactKind(BackendOutputKind Output) noexcept;
+[[nodiscard]] Expected<ArtifactKind> cacheArtifactKind(BackendOutputKind Output);
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_BACKENDDRIVER_H
diff --git a/backend/include/rcc/Tooling/BackendInvocation.h b/backend/include/rcc/Tooling/BackendInvocation.h
new file mode 100644
index 0000000..db1c5d2
--- /dev/null
+++ b/backend/include/rcc/Tooling/BackendInvocation.h
@@ -0,0 +1,119 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_BACKENDINVOCATION_H
+#define RCC_TOOLING_BACKENDINVOCATION_H
+
+#include "rcc/Support/Error.h"
+
+#include <cstdint>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+inline constexpr std::uint32_t BackendInvocationSchemaVersion = 1;
+inline constexpr std::string_view LLVMReferenceRevision =
+    "2b40c303e79f64c5c7642032554eda026594d604";
+inline constexpr std::string_view GenericOpcodeReferenceVersion = "rcc-generic-opcode-v1";
+inline constexpr std::string_view RV64GCTargetABILoweringVersion = "rcc-rv64gc-lp64d-v1";
+inline constexpr std::string_view CompilerBuildFingerprint = "rcc-backend-0.1.0-stage17";
+
+enum class RelocationModel : std::uint8_t {
+  Static,
+  PositionIndependent,
+};
+
+enum class CodeModel : std::uint8_t {
+  Small,
+  Medium,
+  Large,
+};
+
+enum class OptimizationLevel : std::uint8_t {
+  O0,
+  O1,
+  O2,
+  O3,
+  Os,
+  Oz,
+};
+
+enum class LayoutOwnership : std::uint8_t {
+  NativeObject,
+  CompilerFinalLayout,
+  ExternalRelaxation,
+};
+
+struct BackendOption final {
+  std::string Name;
+  std::string Value;
+
+  friend bool operator==(const BackendOption &, const BackendOption &) = default;
+};
+
+struct DeterminismOptions final {
+  std::uint64_t RandomSeed = 0;
+  std::uint32_t ThreadCount = 1;
+  bool StableScheduling = true;
+
+  friend bool operator==(const DeterminismOptions &, const DeterminismOptions &) = default;
+};
+
+struct BackendInvocation final {
+  std::uint32_t SchemaVersion = BackendInvocationSchemaVersion;
+  std::string Triple;
+  std::string CPU;
+  std::string TuneCPU;
+  std::vector<std::string> Features;
+  std::string ABI;
+  std::string DataLayout;
+  RelocationModel Relocation = RelocationModel::PositionIndependent;
+  CodeModel Code = CodeModel::Small;
+  std::vector<BackendOption> TargetOptions;
+  LayoutOwnership Layout = LayoutOwnership::NativeObject;
+  std::string AssemblerFlavor;
+  std::string AssemblerVersion;
+  std::vector<BackendOption> AssemblerOptions;
+  OptimizationLevel Optimization = OptimizationLevel::O2;
+  std::vector<std::string> PassPipeline{"default"};
+  DeterminismOptions Determinism;
+  std::optional<std::uint64_t> ActionFuel;
+  std::vector<std::string> EnabledActions;
+  std::string MIRReferenceRevision{LLVMReferenceRevision};
+  std::string GenericOpcodeVersion{GenericOpcodeReferenceVersion};
+  std::string TargetABILoweringVersion{RV64GCTargetABILoweringVersion};
+  std::string BuildFingerprint{CompilerBuildFingerprint};
+
+  [[nodiscard]] Expected<void> canonicalizeAndVerify();
+  [[nodiscard]] std::string canonicalText() const;
+
+  friend bool operator==(const BackendInvocation &, const BackendInvocation &) = default;
+};
+
+[[nodiscard]] BackendInvocation defaultRV64GCInvocation();
+[[nodiscard]] Expected<std::string>
+computeTargetDescriptionFingerprint(const TargetDescription &Target);
+[[nodiscard]] Expected<std::string> computeCacheKey(std::string_view CanonicalMIR,
+                                                    const BackendInvocation &Invocation,
+                                                    std::string_view TargetFingerprint);
+
+[[nodiscard]] std::string_view spelling(RelocationModel Value) noexcept;
+[[nodiscard]] std::string_view spelling(CodeModel Value) noexcept;
+[[nodiscard]] std::string_view spelling(OptimizationLevel Value) noexcept;
+[[nodiscard]] std::string_view spelling(LayoutOwnership Value) noexcept;
+[[nodiscard]] Expected<RelocationModel> parseRelocationModel(std::string_view Value);
+[[nodiscard]] Expected<CodeModel> parseCodeModel(std::string_view Value);
+[[nodiscard]] Expected<OptimizationLevel> parseOptimizationLevel(std::string_view Value);
+[[nodiscard]] Expected<LayoutOwnership> parseLayoutOwnership(std::string_view Value);
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_BACKENDINVOCATION_H
diff --git a/backend/include/rcc/Tooling/BackendManifest.h b/backend/include/rcc/Tooling/BackendManifest.h
new file mode 100644
index 0000000..d5d5733
--- /dev/null
+++ b/backend/include/rcc/Tooling/BackendManifest.h
@@ -0,0 +1,75 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_BACKENDMANIFEST_H
+#define RCC_TOOLING_BACKENDMANIFEST_H
+
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc::tooling {
+
+inline constexpr std::uint32_t BackendManifestSchemaVersion = 1;
+
+enum class ManifestKind : std::uint8_t {
+  Cache,
+  Reproducer,
+};
+
+enum class ArtifactKind : std::uint8_t {
+  PreLegalizerMIR,
+  LegalizedMIR,
+  RegisterBankMIR,
+  SelectedMIR,
+  PostSSAMIR,
+  PostRegisterAllocationMIR,
+  FinalMIR,
+  Assembly,
+  RelocatableObject,
+};
+
+struct StructuredDiagnostic final {
+  std::string Category;
+  std::string Stage;
+  std::string Pass;
+  std::string Function;
+  std::optional<std::uint64_t> Block;
+  std::optional<std::uint64_t> Instruction;
+  std::optional<std::uint32_t> Operand;
+  std::string SourceLocation;
+  std::string TargetConstraint;
+  std::string Rule;
+  std::string Message;
+
+  friend bool operator==(const StructuredDiagnostic &, const StructuredDiagnostic &) = default;
+};
+
+struct BackendManifest final {
+  std::uint32_t SchemaVersion = BackendManifestSchemaVersion;
+  ManifestKind Kind = ManifestKind::Reproducer;
+  ArtifactKind Artifact = ArtifactKind::FinalMIR;
+  BackendInvocation Invocation;
+  std::string InputMIRHash;
+  std::string TargetFingerprint;
+  std::string CacheKey;
+  std::optional<std::string> ArtifactHash;
+  std::vector<StructuredDiagnostic> Diagnostics;
+
+  [[nodiscard]] Expected<void> verify() const;
+
+  friend bool operator==(const BackendManifest &, const BackendManifest &) = default;
+};
+
+[[nodiscard]] Expected<std::string> printBackendManifest(const BackendManifest &Manifest);
+[[nodiscard]] Expected<BackendManifest> parseBackendManifest(std::string SourceName,
+                                                             std::string SourceText);
+[[nodiscard]] std::string_view spelling(ManifestKind Value) noexcept;
+[[nodiscard]] std::string_view spelling(ArtifactKind Value) noexcept;
+
+} // namespace rcc::tooling
+
+#endif // RCC_TOOLING_BACKENDMANIFEST_H
diff --git a/backend/include/rcc/Tooling/MIRFuzzer.h b/backend/include/rcc/Tooling/MIRFuzzer.h
new file mode 100644
index 0000000..7fccb6d
--- /dev/null
+++ b/backend/include/rcc/Tooling/MIRFuzzer.h
@@ -0,0 +1,66 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_MIRFUZZER_H
+#define RCC_TOOLING_MIRFUZZER_H
+
+#include "rcc/Support/Error.h"
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+enum class MIRFuzzLayer : std::uint8_t {
+  Parser,
+  BuilderStructural,
+  PropertyStage,
+  Mutation,
+  Pipeline,
+  RestrictedSemantics,
+};
+
+struct MIRFuzzOptions final {
+  std::uint64_t Seed = 0;
+  std::size_t Iterations = 100;
+  std::size_t MaximumInputSize = 1U << 20U;
+  std::vector<MIRFuzzLayer> Layers;
+};
+
+struct MIRFuzzLayerResult final {
+  MIRFuzzLayer Layer = MIRFuzzLayer::Parser;
+  std::size_t Executed = 0;
+  std::size_t Accepted = 0;
+  std::size_t Rejected = 0;
+
+  friend bool operator==(const MIRFuzzLayerResult &, const MIRFuzzLayerResult &) = default;
+};
+
+struct MIRFuzzResult final {
+  std::uint64_t Seed = 0;
+  std::vector<MIRFuzzLayerResult> Layers;
+
+  [[nodiscard]] std::size_t executed() const noexcept;
+  [[nodiscard]] std::size_t accepted() const noexcept;
+  [[nodiscard]] std::size_t rejected() const noexcept;
+};
+
+[[nodiscard]] Expected<MIRFuzzResult> fuzzMIR(std::string SourceName, std::string SourceText,
+                                              BackendInvocation Invocation,
+                                              const TargetDescription &Target,
+                                              MIRFuzzOptions Options = {});
+
+[[nodiscard]] std::string_view spelling(MIRFuzzLayer Layer) noexcept;
+[[nodiscard]] Expected<MIRFuzzLayer> parseMIRFuzzLayer(std::string_view Value);
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_MIRFUZZER_H
diff --git a/backend/include/rcc/Tooling/MIRReducer.h b/backend/include/rcc/Tooling/MIRReducer.h
new file mode 100644
index 0000000..35ef9c0
--- /dev/null
+++ b/backend/include/rcc/Tooling/MIRReducer.h
@@ -0,0 +1,81 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_MIRREDUCER_H
+#define RCC_TOOLING_MIRREDUCER_H
+
+#include "rcc/Support/Error.h"
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <functional>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+enum class ReductionMode : std::uint8_t {
+  PreserveValidity,
+  PreserveFailure,
+};
+
+enum class ReductionGranularity : std::uint8_t {
+  CompilationUnit,
+  MachineFunction,
+  BasicBlock,
+  CFGEdge,
+  Instruction,
+  Operand,
+  RegisterSubgraph,
+  FrameObject,
+  ConstantPool,
+  JumpTable,
+  TargetFeature,
+  PassPipeline,
+};
+
+struct MIRReducerOptions final {
+  ReductionMode Mode = ReductionMode::PreserveFailure;
+  std::size_t MaximumAttempts = 100'000;
+  std::vector<ReductionGranularity> Granularities;
+};
+
+using MIRInterestingnessTest =
+    std::function<Expected<bool>(std::string_view, const BackendInvocation &)>;
+
+// PreserveFailure requires and evaluates the interestingness test. PreserveValidity accepts every
+// smaller candidate that reparses, canonicalizes, and verifies; its interestingness test is
+// ignored.
+
+struct MIRReductionStep final {
+  ReductionGranularity Granularity = ReductionGranularity::Instruction;
+  std::string Description;
+  std::size_t PreviousSize = 0;
+  std::size_t ReducedSize = 0;
+};
+
+struct MIRReductionResult final {
+  std::string MIR;
+  BackendInvocation Invocation;
+  std::vector<MIRReductionStep> Steps;
+  std::size_t Attempts = 0;
+  bool Exhausted = false;
+};
+
+[[nodiscard]] Expected<MIRReductionResult> reduceMIR(std::string SourceName, std::string SourceText,
+                                                     BackendInvocation Invocation,
+                                                     const TargetDescription &Target,
+                                                     const MIRInterestingnessTest &Interesting,
+                                                     MIRReducerOptions Options = {});
+
+[[nodiscard]] std::string_view spelling(ReductionGranularity Granularity) noexcept;
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_MIRREDUCER_H
diff --git a/backend/include/rcc/Tooling/PipelineDriver.h b/backend/include/rcc/Tooling/PipelineDriver.h
new file mode 100644
index 0000000..2de341c
--- /dev/null
+++ b/backend/include/rcc/Tooling/PipelineDriver.h
@@ -0,0 +1,83 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef RCC_TOOLING_PIPELINEDRIVER_H
+#define RCC_TOOLING_PIPELINEDRIVER_H
+
+#include "rcc/CodeGen/MachinePass.h"
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include <cstdint>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+
+class TargetDescription;
+
+namespace tooling {
+
+enum class BackendStage : std::uint8_t {
+  PreLegalizerMIR,
+  LegalizedMIR,
+  RegisterBankMIR,
+  SelectedMIR,
+  PostSSAMIR,
+  PostRegisterAllocationMIR,
+  FinalMIR,
+};
+
+enum class SnapshotPhase : std::uint8_t {
+  Stage,
+  BeforePass,
+  AfterPass,
+};
+
+struct PipelineControls final {
+  std::optional<std::string> StopBefore;
+  std::optional<std::string> StopAfter;
+  std::vector<std::string> PrintBefore;
+  std::vector<std::string> PrintAfter;
+  std::optional<BackendStage> StopAtStage;
+  bool CaptureStageSnapshots = false;
+  bool VerifyEach = true;
+  bool DetectUnreportedChanges = true;
+};
+
+struct PipelineSnapshot final {
+  SnapshotPhase Phase = SnapshotPhase::Stage;
+  BackendStage Stage = BackendStage::PreLegalizerMIR;
+  std::string Function;
+  std::string Pass;
+  std::uint32_t Occurrence = 0;
+  std::string MIR;
+};
+
+struct ExecutedPass final {
+  std::string Function;
+  std::string Pass;
+  std::uint32_t Occurrence = 0;
+
+  friend bool operator==(const ExecutedPass &, const ExecutedPass &) = default;
+};
+
+struct PipelineRunResult final {
+  std::vector<ExecutedPass> ExecutedPasses;
+  std::vector<PipelineSnapshot> Snapshots;
+};
+
+[[nodiscard]] Expected<void> verifyRV64GCInvocation(const BackendInvocation &Invocation);
+[[nodiscard]] Expected<PipelineRunResult>
+runRV64GCPipeline(mir::MIRDocument &Document, const TargetDescription &Target,
+                  const BackendInvocation &Invocation, PipelineControls Controls = {},
+                  MachinePassInstrumentation *Instrumentation = nullptr);
+[[nodiscard]] BackendStage stageForFunction(const MachineFunction &Function) noexcept;
+[[nodiscard]] std::string_view spelling(BackendStage Stage) noexcept;
+[[nodiscard]] Expected<BackendStage> parseBackendStage(std::string_view Value);
+
+} // namespace tooling
+} // namespace rcc
+
+#endif // RCC_TOOLING_PIPELINEDRIVER_H