[Tooling] Complete backend tooling and validation

7 files changed, 553 insertions, 0 deletions

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