aboutsummaryrefslogtreecommitdiff
path: root/backend/lib/Tooling
diff options
context:
space:
mode:
Diffstat (limited to 'backend/lib/Tooling')
-rw-r--r--backend/lib/Tooling/ArtifactStore.cpp532
-rw-r--r--backend/lib/Tooling/BackendDriver.cpp214
-rw-r--r--backend/lib/Tooling/BackendInvocation.cpp500
-rw-r--r--backend/lib/Tooling/BackendManifest.cpp733
-rw-r--r--backend/lib/Tooling/CMakeLists.txt76
-rw-r--r--backend/lib/Tooling/MIRFuzzer.cpp613
-rw-r--r--backend/lib/Tooling/MIRReducer.cpp534
-rw-r--r--backend/lib/Tooling/PipelineDriver.cpp436
8 files changed, 3638 insertions, 0 deletions
diff --git a/backend/lib/Tooling/ArtifactStore.cpp b/backend/lib/Tooling/ArtifactStore.cpp
new file mode 100644
index 0000000..76fc0df
--- /dev/null
+++ b/backend/lib/Tooling/ArtifactStore.cpp
@@ -0,0 +1,532 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/ArtifactStore.h"
+
+#include "rcc/CodeGen/CompilationUnit.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Support/SHA256.h"
+#include "rcc/Support/TextDiagnostic.h"
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include <atomic>
+#include <cstddef>
+#include <cstdint>
+#include <filesystem>
+#include <fstream>
+#include <iterator>
+#include <limits>
+#include <optional>
+#include <span>
+#include <string>
+#include <string_view>
+#include <system_error>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+constexpr std::uintmax_t MaximumPackageFileSize = std::uintmax_t{1} << 30U;
+std::atomic<std::uint64_t> TemporarySequence = 0;
+
+[[nodiscard]] bool isMIRArtifact(ArtifactKind Artifact) noexcept {
+ switch (Artifact) {
+ case ArtifactKind::PreLegalizerMIR:
+ case ArtifactKind::LegalizedMIR:
+ case ArtifactKind::RegisterBankMIR:
+ case ArtifactKind::SelectedMIR:
+ case ArtifactKind::PostSSAMIR:
+ case ArtifactKind::PostRegisterAllocationMIR:
+ case ArtifactKind::FinalMIR:
+ return true;
+ case ArtifactKind::Assembly:
+ case ArtifactKind::RelocatableObject:
+ return false;
+ }
+ return false;
+}
+
+[[nodiscard]] bool isCacheableArtifact(ArtifactKind Artifact) noexcept {
+ switch (Artifact) {
+ case ArtifactKind::PreLegalizerMIR:
+ case ArtifactKind::SelectedMIR:
+ case ArtifactKind::PostRegisterAllocationMIR:
+ case ArtifactKind::FinalMIR:
+ case ArtifactKind::Assembly:
+ case ArtifactKind::RelocatableObject:
+ return true;
+ case ArtifactKind::LegalizedMIR:
+ case ArtifactKind::RegisterBankMIR:
+ case ArtifactKind::PostSSAMIR:
+ return false;
+ }
+ return false;
+}
+
+[[nodiscard]] std::string_view artifactFileName(ArtifactKind Artifact) noexcept {
+ switch (Artifact) {
+ case ArtifactKind::PreLegalizerMIR:
+ case ArtifactKind::LegalizedMIR:
+ case ArtifactKind::RegisterBankMIR:
+ case ArtifactKind::SelectedMIR:
+ case ArtifactKind::PostSSAMIR:
+ case ArtifactKind::PostRegisterAllocationMIR:
+ case ArtifactKind::FinalMIR:
+ return "artifact.mir";
+ case ArtifactKind::Assembly:
+ return "artifact.s";
+ case ArtifactKind::RelocatableObject:
+ return "artifact.o";
+ }
+ return "artifact.bin";
+}
+
+[[nodiscard]] std::filesystem::path cacheEntryPath(const std::filesystem::path &Root,
+ std::string_view Key) {
+ return Root / std::string(Key.substr(0, 2)) / std::string(Key);
+}
+
+[[nodiscard]] Expected<std::vector<std::uint8_t>> readBytes(const std::filesystem::path &Path,
+ ErrorCode Code) {
+ std::error_code FileError;
+ const std::uintmax_t Size = std::filesystem::file_size(Path, FileError);
+ if (FileError)
+ return makeUnexpected(Code, "cannot inspect package file '" + Path.string() + "'");
+ if (Size > MaximumPackageFileSize ||
+ Size > static_cast<std::uintmax_t>(std::numeric_limits<std::size_t>::max())) {
+ return makeUnexpected(Code, "package file exceeds the supported size limit");
+ }
+ std::ifstream Input(Path, std::ios::binary);
+ if (!Input)
+ return makeUnexpected(Code, "cannot open package file '" + Path.string() + "'");
+ std::vector<std::uint8_t> Result(static_cast<std::size_t>(Size));
+ if (!Result.empty()) {
+ Input.read(reinterpret_cast<char *>(Result.data()),
+ static_cast<std::streamsize>(Result.size()));
+ }
+ if (!Input)
+ return makeUnexpected(Code, "cannot read package file '" + Path.string() + "'");
+ return Result;
+}
+
+[[nodiscard]] Expected<std::string> readText(const std::filesystem::path &Path, ErrorCode Code) {
+ auto Bytes = readBytes(Path, Code);
+ if (!Bytes)
+ return std::unexpected(Bytes.error());
+ return std::string(reinterpret_cast<const char *>(Bytes->data()), Bytes->size());
+}
+
+[[nodiscard]] Expected<void> writeBytes(const std::filesystem::path &Path,
+ std::span<const std::uint8_t> Bytes, ErrorCode Code) {
+ std::ofstream Output(Path, std::ios::binary | std::ios::trunc);
+ if (!Output)
+ return makeUnexpected(Code, "cannot create package file '" + Path.string() + "'");
+ if (!Bytes.empty()) {
+ Output.write(reinterpret_cast<const char *>(Bytes.data()),
+ static_cast<std::streamsize>(Bytes.size()));
+ }
+ Output.close();
+ if (!Output)
+ return makeUnexpected(Code, "cannot write package file '" + Path.string() + "'");
+ return {};
+}
+
+[[nodiscard]] Expected<void> writeText(const std::filesystem::path &Path, std::string_view Text,
+ ErrorCode Code) {
+ const auto *Bytes = reinterpret_cast<const std::uint8_t *>(Text.data());
+ return writeBytes(Path, std::span<const std::uint8_t>(Bytes, Text.size()), Code);
+}
+
+[[nodiscard]] std::filesystem::path temporaryPath(const std::filesystem::path &Destination) {
+ const std::uint64_t Sequence = TemporarySequence.fetch_add(1, std::memory_order_relaxed);
+ return Destination.parent_path() /
+ (Destination.filename().string() + ".tmp." + std::to_string(Sequence));
+}
+
+[[nodiscard]] Expected<void> replaceTextAtomically(const std::filesystem::path &Path,
+ std::string_view Text, ErrorCode Code) {
+ const std::filesystem::path Temporary = temporaryPath(Path);
+ auto Written = writeText(Temporary, Text, Code);
+ if (!Written)
+ return Written;
+ std::error_code FileError;
+ std::filesystem::rename(Temporary, Path, FileError);
+ if (!FileError)
+ return {};
+ std::error_code CleanupError;
+ std::filesystem::remove(Temporary, CleanupError);
+ return makeUnexpected(Code, "cannot atomically replace package file '" + Path.string() + "'");
+}
+
+[[nodiscard]] Expected<void>
+writePackageAtomically(const std::filesystem::path &Destination, std::string_view ManifestText,
+ std::string_view InputMIR, std::string_view ArtifactName,
+ std::span<const std::uint8_t> Artifact, bool HasArtifact, ErrorCode Code) {
+ if (Destination.empty())
+ return makeUnexpected(Code, "package destination cannot be empty");
+ std::error_code FileError;
+ const std::filesystem::path Parent = Destination.parent_path();
+ if (!Parent.empty()) {
+ std::filesystem::create_directories(Parent, FileError);
+ if (FileError)
+ return makeUnexpected(Code, "cannot create package parent directory");
+ }
+ if (std::filesystem::exists(Destination, FileError))
+ return makeUnexpected(Code, "package destination already exists");
+ if (FileError)
+ return makeUnexpected(Code, "cannot inspect package destination");
+
+ const std::filesystem::path Temporary = temporaryPath(Destination);
+ std::filesystem::create_directory(Temporary, FileError);
+ if (FileError)
+ return makeUnexpected(Code, "cannot create temporary package directory");
+ const auto Cleanup = [&]() {
+ std::error_code CleanupError;
+ std::filesystem::remove_all(Temporary, CleanupError);
+ };
+ auto Written = writeText(Temporary / "manifest.yaml", ManifestText, Code);
+ if (!Written) {
+ Cleanup();
+ return Written;
+ }
+ Written = writeText(Temporary / "input.mir", InputMIR, Code);
+ if (!Written) {
+ Cleanup();
+ return Written;
+ }
+ if (HasArtifact) {
+ Written = writeBytes(Temporary / ArtifactName, Artifact, Code);
+ if (!Written) {
+ Cleanup();
+ return Written;
+ }
+ }
+ std::filesystem::rename(Temporary, Destination, FileError);
+ if (FileError) {
+ Cleanup();
+ return makeUnexpected(Code, "cannot publish package atomically");
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> verifyFunctions(const mir::MIRDocument &Document,
+ const TargetDescription &Target) {
+ auto UnitVerification = Document.unit().verify();
+ if (!UnitVerification)
+ return std::unexpected(UnitVerification.error());
+ for (std::size_t Index = 0; Index < Document.unit().functionCount(); ++Index) {
+ const MachineFunction *Function = Document.unit().functionAt(Index);
+ if (Function == nullptr)
+ return makeUnexpected(ErrorCode::VerificationError,
+ "MIR document contains a null machine function");
+ auto FunctionVerification = MachineVerifier::verify(*Function, Target);
+ if (!FunctionVerification)
+ return std::unexpected(FunctionVerification.error());
+ }
+ return {};
+}
+
+[[nodiscard]] Error parseFailure(const mir::MIRDocumentParseResult &Parsed, ErrorCode Code) {
+ if (Parsed.diagnostics().empty())
+ return Error(Code, "MIR package input could not be parsed");
+ return Error(Code, formatTextDiagnostic(Parsed.diagnostics().front(), Parsed.source()));
+}
+
+[[nodiscard]] Expected<void> verifyManifestIdentity(const BackendManifest &Manifest,
+ ManifestKind Kind, ArtifactKind Artifact,
+ const BackendInvocation &Invocation,
+ std::string_view InputHash,
+ std::string_view TargetFingerprint,
+ std::string_view CacheKey, ErrorCode Code) {
+ if (Manifest.Kind != Kind || Manifest.Artifact != Artifact || Manifest.Invocation != Invocation ||
+ Manifest.InputMIRHash != InputHash || Manifest.TargetFingerprint != TargetFingerprint ||
+ Manifest.CacheKey != CacheKey) {
+ return makeUnexpected(Code, "package manifest does not match the requested backend input");
+ }
+ return {};
+}
+
+} // namespace
+
+Expected<CanonicalMIR> parseAndCanonicalizeMIR(std::string SourceName, std::string SourceText,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ BackendInvocation CanonicalInvocation = Invocation;
+ auto InvocationVerification = CanonicalInvocation.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ if (CanonicalInvocation != Invocation) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "MIR parsing requires a canonical backend invocation");
+ }
+ mir::MIRDocumentParserOptions ParseOptions;
+ ParseOptions.DataLayout = Invocation.DataLayout;
+ ParseOptions.DefaultPointerSizeInBits = 64;
+ ParseOptions.VerifyMachineFunctions = true;
+ mir::MIRDocumentParseResult Parsed =
+ mir::parseMIRDocument(Target, std::move(SourceName), std::move(SourceText), ParseOptions);
+ if (!Parsed.succeeded())
+ return std::unexpected(parseFailure(Parsed, ErrorCode::ParseError));
+ if (Parsed.document() == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "successful MIR parse has no document");
+ auto Verification = verifyFunctions(*Parsed.document(), Target);
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ mir::MIRDocumentPrinterOptions PrintOptions;
+ PrintOptions.Mode = mir::MIPrintMode::Complete;
+ PrintOptions.EmitEmbeddedIR = true;
+ PrintOptions.DataLayout = Invocation.DataLayout;
+ PrintOptions.DefaultPointerSizeInBits = 64;
+ auto Printed = mir::printMIRDocument(*Parsed.document(), Target, std::move(PrintOptions));
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ return CanonicalMIR{
+ .Document = std::move(*Parsed.document()),
+ .Text = std::move(*Printed),
+ };
+}
+
+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::vector<StructuredDiagnostic> Diagnostics) {
+ BackendInvocation CanonicalInvocation = Invocation;
+ auto InvocationVerification = CanonicalInvocation.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ if (CanonicalInvocation != Invocation) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "manifest creation requires a canonical backend invocation");
+ }
+ auto Fingerprint = computeTargetDescriptionFingerprint(Target);
+ if (!Fingerprint)
+ return std::unexpected(Fingerprint.error());
+ auto Key = computeCacheKey(CanonicalInputMIR, Invocation, *Fingerprint);
+ if (!Key)
+ return std::unexpected(Key.error());
+ BackendManifest Result{
+ .SchemaVersion = BackendManifestSchemaVersion,
+ .Kind = Kind,
+ .Artifact = Artifact,
+ .Invocation = Invocation,
+ .InputMIRHash = sha256Hex(CanonicalInputMIR),
+ .TargetFingerprint = std::move(*Fingerprint),
+ .CacheKey = std::move(*Key),
+ .ArtifactHash = std::nullopt,
+ .Diagnostics = std::move(Diagnostics),
+ };
+ if (ArtifactBytes) {
+ const auto *Bytes = reinterpret_cast<const std::byte *>(ArtifactBytes->data());
+ Result.ArtifactHash = sha256Hex(
+ std::span<const std::byte>(Bytes, static_cast<std::size_t>(ArtifactBytes->size())));
+ }
+ auto Verification = Result.verify();
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ return Result;
+}
+
+Expected<void> storeCacheEntry(const std::filesystem::path &CacheRoot,
+ const BackendManifest &Manifest, std::string_view CanonicalInputMIR,
+ std::span<const std::uint8_t> Artifact) {
+ auto Verification = Manifest.verify();
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ if (Manifest.Kind != ManifestKind::Cache || !Manifest.ArtifactHash) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "cache entry requires a cache manifest and artifact hash");
+ }
+ if (!isCacheableArtifact(Manifest.Artifact)) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest artifact is not an allowed cache boundary");
+ }
+ if (sha256Hex(CanonicalInputMIR) != Manifest.InputMIRHash) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "cache input MIR does not match its manifest hash");
+ }
+ const auto *ArtifactBytes = reinterpret_cast<const std::byte *>(Artifact.data());
+ if (sha256Hex(std::span<const std::byte>(ArtifactBytes, Artifact.size())) !=
+ *Manifest.ArtifactHash) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "cache artifact does not match its manifest hash");
+ }
+ auto Printed = printBackendManifest(Manifest);
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ const std::filesystem::path Destination = cacheEntryPath(CacheRoot, Manifest.CacheKey);
+ return writePackageAtomically(Destination, *Printed, CanonicalInputMIR,
+ artifactFileName(Manifest.Artifact), Artifact, true,
+ ErrorCode::IoError);
+}
+
+Expected<CacheEntry> loadCacheEntry(const std::filesystem::path &CacheRoot, ArtifactKind Artifact,
+ const BackendInvocation &Invocation,
+ const TargetDescription &Target,
+ std::string_view CanonicalInputMIR) {
+ if (!isCacheableArtifact(Artifact))
+ return makeUnexpected(ErrorCode::CacheMiss, "requested artifact is not a cache boundary");
+ BackendInvocation CanonicalInvocation = Invocation;
+ auto InvocationVerification = CanonicalInvocation.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ if (CanonicalInvocation != Invocation)
+ return makeUnexpected(ErrorCode::CacheMiss, "cache invocation is not canonical");
+ auto Fingerprint = computeTargetDescriptionFingerprint(Target);
+ if (!Fingerprint)
+ return std::unexpected(Fingerprint.error());
+ auto Key = computeCacheKey(CanonicalInputMIR, Invocation, *Fingerprint);
+ if (!Key)
+ return std::unexpected(Key.error());
+ const std::filesystem::path EntryPath = cacheEntryPath(CacheRoot, *Key);
+ std::error_code FileError;
+ if (!std::filesystem::is_directory(EntryPath, FileError) || FileError)
+ return makeUnexpected(ErrorCode::CacheMiss, "cache entry is absent");
+ auto ManifestText = readText(EntryPath / "manifest.yaml", ErrorCode::CacheMiss);
+ if (!ManifestText)
+ return std::unexpected(ManifestText.error());
+ auto Manifest =
+ parseBackendManifest((EntryPath / "manifest.yaml").string(), std::move(*ManifestText));
+ if (!Manifest)
+ return makeUnexpected(ErrorCode::CacheMiss, std::string(Manifest.error().message()));
+ const std::string InputHash = sha256Hex(CanonicalInputMIR);
+ auto Identity = verifyManifestIdentity(*Manifest, ManifestKind::Cache, Artifact, Invocation,
+ InputHash, *Fingerprint, *Key, ErrorCode::CacheMiss);
+ if (!Identity)
+ return std::unexpected(Identity.error());
+ if (!Manifest->ArtifactHash)
+ return makeUnexpected(ErrorCode::CacheMiss, "cache manifest has no artifact hash");
+
+ auto StoredInput = readText(EntryPath / "input.mir", ErrorCode::CacheMiss);
+ if (!StoredInput)
+ return std::unexpected(StoredInput.error());
+ if (*StoredInput != CanonicalInputMIR || sha256Hex(*StoredInput) != Manifest->InputMIRHash)
+ return makeUnexpected(ErrorCode::CacheMiss, "cached input MIR is inconsistent");
+ auto StrictInput = parseAndCanonicalizeMIR("cache-input.mir", *StoredInput, Target, Invocation);
+ if (!StrictInput || StrictInput->Text != *StoredInput)
+ return makeUnexpected(ErrorCode::CacheMiss, "cached input MIR is not canonical and valid");
+
+ auto ArtifactBytes = readBytes(EntryPath / artifactFileName(Artifact), ErrorCode::CacheMiss);
+ if (!ArtifactBytes)
+ return std::unexpected(ArtifactBytes.error());
+ const auto *Bytes = reinterpret_cast<const std::byte *>(ArtifactBytes->data());
+ if (sha256Hex(std::span<const std::byte>(Bytes, ArtifactBytes->size())) !=
+ *Manifest->ArtifactHash) {
+ return makeUnexpected(ErrorCode::CacheMiss, "cached artifact hash is inconsistent");
+ }
+ std::optional<CanonicalMIR> ParsedArtifact;
+ if (isMIRArtifact(Artifact)) {
+ std::string ArtifactText(reinterpret_cast<const char *>(ArtifactBytes->data()),
+ ArtifactBytes->size());
+ auto Parsed = parseAndCanonicalizeMIR("cache-artifact.mir", ArtifactText, Target, Invocation);
+ if (!Parsed || Parsed->Text != ArtifactText)
+ return makeUnexpected(ErrorCode::CacheMiss, "cached MIR artifact is not canonical and valid");
+ ParsedArtifact = std::move(*Parsed);
+ }
+ return CacheEntry{
+ .Manifest = std::move(*Manifest),
+ .InputMIR = std::move(*StoredInput),
+ .Artifact = std::move(*ArtifactBytes),
+ .ParsedArtifact = std::move(ParsedArtifact),
+ };
+}
+
+Expected<void> writeReproducer(const std::filesystem::path &PackagePath,
+ const BackendManifest &Manifest,
+ std::string_view CanonicalInputMIR) {
+ auto Verification = Manifest.verify();
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ if (Manifest.Kind != ManifestKind::Reproducer || Manifest.ArtifactHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer requires a reproducer manifest without an artifact hash");
+ }
+ if (sha256Hex(CanonicalInputMIR) != Manifest.InputMIRHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer input MIR does not match its manifest hash");
+ }
+ auto Printed = printBackendManifest(Manifest);
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ return writePackageAtomically(PackagePath, *Printed, CanonicalInputMIR, {}, {}, false,
+ ErrorCode::ReproducerError);
+}
+
+Expected<void> updateReproducerDiagnostics(const std::filesystem::path &PackagePath,
+ std::vector<StructuredDiagnostic> Diagnostics) {
+ const std::filesystem::path ManifestPath = PackagePath / "manifest.yaml";
+ auto ManifestText = readText(ManifestPath, ErrorCode::ReproducerError);
+ if (!ManifestText)
+ return std::unexpected(ManifestText.error());
+ auto Manifest = parseBackendManifest(ManifestPath.string(), std::move(*ManifestText));
+ if (!Manifest) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "cannot update an invalid reproducer manifest: " +
+ std::string(Manifest.error().message()));
+ }
+ if (Manifest->Kind != ManifestKind::Reproducer || Manifest->ArtifactHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "diagnostics can only update a reproducer package");
+ }
+ auto Input = readText(PackagePath / "input.mir", ErrorCode::ReproducerError);
+ if (!Input)
+ return std::unexpected(Input.error());
+ if (sha256Hex(*Input) != Manifest->InputMIRHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer input changed before diagnostic update");
+ }
+ Manifest->Diagnostics = std::move(Diagnostics);
+ auto Printed = printBackendManifest(*Manifest);
+ if (!Printed)
+ return makeUnexpected(ErrorCode::ReproducerError, std::string(Printed.error().message()));
+ return replaceTextAtomically(ManifestPath, *Printed, ErrorCode::ReproducerError);
+}
+
+Expected<ReproducerPackage> loadReproducer(const std::filesystem::path &PackagePath,
+ const TargetDescription &Target) {
+ auto ManifestText = readText(PackagePath / "manifest.yaml", ErrorCode::ReproducerError);
+ if (!ManifestText)
+ return std::unexpected(ManifestText.error());
+ auto Manifest =
+ parseBackendManifest((PackagePath / "manifest.yaml").string(), std::move(*ManifestText));
+ if (!Manifest)
+ return makeUnexpected(ErrorCode::ReproducerError, std::string(Manifest.error().message()));
+ if (Manifest->Kind != ManifestKind::Reproducer || Manifest->ArtifactHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "package does not contain a valid reproducer manifest");
+ }
+ auto Fingerprint = computeTargetDescriptionFingerprint(Target);
+ if (!Fingerprint)
+ return std::unexpected(Fingerprint.error());
+ if (Manifest->TargetFingerprint != *Fingerprint) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer target fingerprint does not match this backend");
+ }
+ auto InputText = readText(PackagePath / "input.mir", ErrorCode::ReproducerError);
+ if (!InputText)
+ return std::unexpected(InputText.error());
+ auto Input = parseAndCanonicalizeMIR((PackagePath / "input.mir").string(), *InputText, Target,
+ Manifest->Invocation);
+ if (!Input)
+ return makeUnexpected(ErrorCode::ReproducerError, std::string(Input.error().message()));
+ if (Input->Text != *InputText || sha256Hex(Input->Text) != Manifest->InputMIRHash) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer input MIR is not canonical or has the wrong hash");
+ }
+ auto Key = computeCacheKey(Input->Text, Manifest->Invocation, *Fingerprint);
+ if (!Key)
+ return std::unexpected(Key.error());
+ if (*Key != Manifest->CacheKey) {
+ return makeUnexpected(ErrorCode::ReproducerError,
+ "reproducer cache key is inconsistent with its explicit inputs");
+ }
+ return ReproducerPackage{
+ .Manifest = std::move(*Manifest),
+ .Input = std::move(*Input),
+ };
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/BackendDriver.cpp b/backend/lib/Tooling/BackendDriver.cpp
new file mode 100644
index 0000000..85a2cf9
--- /dev/null
+++ b/backend/lib/Tooling/BackendDriver.cpp
@@ -0,0 +1,214 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/BackendDriver.h"
+
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Target/RISCV/RISCVAssemblyPrinter.h"
+#include "rcc/Target/RISCV/RISCVObjectFile.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+[[nodiscard]] bool isMIR(BackendOutputKind Output) noexcept {
+ return Output <= BackendOutputKind::FinalMIR;
+}
+
+[[nodiscard]] BackendStage outputStage(BackendOutputKind Output) noexcept {
+ switch (Output) {
+ case BackendOutputKind::PreLegalizerMIR:
+ return BackendStage::PreLegalizerMIR;
+ case BackendOutputKind::LegalizedMIR:
+ return BackendStage::LegalizedMIR;
+ case BackendOutputKind::RegisterBankMIR:
+ return BackendStage::RegisterBankMIR;
+ case BackendOutputKind::SelectedMIR:
+ return BackendStage::SelectedMIR;
+ case BackendOutputKind::PostSSAMIR:
+ return BackendStage::PostSSAMIR;
+ case BackendOutputKind::PostRegisterAllocationMIR:
+ return BackendStage::PostRegisterAllocationMIR;
+ case BackendOutputKind::FinalMIR:
+ case BackendOutputKind::Assembly:
+ case BackendOutputKind::RelocatableObject:
+ return BackendStage::FinalMIR;
+ }
+ return BackendStage::FinalMIR;
+}
+
+[[nodiscard]] std::uint8_t ordinal(BackendStage Stage) noexcept {
+ return static_cast<std::uint8_t>(Stage);
+}
+
+[[nodiscard]] Expected<std::vector<std::uint8_t>> printMIR(const mir::MIRDocument &Document,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ mir::MIRDocumentPrinterOptions Options;
+ Options.Mode = mir::MIPrintMode::Complete;
+ Options.EmitEmbeddedIR = true;
+ Options.DataLayout = Invocation.DataLayout;
+ Options.DefaultPointerSizeInBits = 64;
+ auto Printed = mir::printMIRDocument(Document, Target, std::move(Options));
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ return std::vector<std::uint8_t>(Printed->begin(), Printed->end());
+}
+
+} // namespace
+
+std::string_view BackendRunResult::text() const noexcept {
+ if (Kind == BackendOutputKind::RelocatableObject || Output.empty())
+ return {};
+ return {reinterpret_cast<const char *>(Output.data()), Output.size()};
+}
+
+Expected<BackendRunResult> runBackend(CanonicalMIR Input, const TargetDescription &Target,
+ const BackendInvocation &Invocation, BackendOutputKind Output,
+ PipelineControls Controls,
+ MachinePassInstrumentation *Instrumentation) {
+ auto InvocationVerification = verifyRV64GCInvocation(Invocation);
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ if (Input.Document.unit().functionCount() == 0) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "backend input must contain at least one machine function");
+ }
+
+ BackendStage InitialStage = BackendStage::FinalMIR;
+ for (std::size_t Index = 0; Index < Input.Document.unit().functionCount(); ++Index) {
+ const MachineFunction *Function = Input.Document.unit().functionAt(Index);
+ if (Function == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "backend input contains a null function");
+ const BackendStage Stage = stageForFunction(*Function);
+ if (Index == 0 || ordinal(Stage) < ordinal(InitialStage))
+ InitialStage = Stage;
+ }
+ const BackendStage RequiredStage = outputStage(Output);
+ if (isMIR(Output) && ordinal(RequiredStage) < ordinal(InitialStage)) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend cannot reconstruct an earlier MIR stage from a later snapshot");
+ }
+
+ if (isMIR(Output)) {
+ if (Controls.StopAtStage && *Controls.StopAtStage != RequiredStage) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "output stage conflicts with the explicit pipeline stop stage");
+ }
+ Controls.StopAtStage = RequiredStage;
+ }
+
+ MachinePassInstrumentation LocalInstrumentation;
+ MachinePassInstrumentation *ActiveInstrumentation =
+ Instrumentation == nullptr ? &LocalInstrumentation : Instrumentation;
+ auto Pipeline = runRV64GCPipeline(Input.Document, Target, Invocation, std::move(Controls),
+ ActiveInstrumentation);
+ if (!Pipeline)
+ return std::unexpected(Pipeline.error());
+
+ std::vector<std::uint8_t> Bytes;
+ if (isMIR(Output)) {
+ auto Printed = printMIR(Input.Document, Target, Invocation);
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ Bytes = std::move(*Printed);
+ } else if (Output == BackendOutputKind::Assembly) {
+ auto Assembly = riscv::emitAssembly(Input.Document.unit(), Target);
+ if (!Assembly)
+ return std::unexpected(Assembly.error());
+ Bytes.assign(Assembly->begin(), Assembly->end());
+ } else {
+ auto Object = riscv::emitObject(Input.Document.unit(), Target);
+ if (!Object)
+ return std::unexpected(Object.error());
+ Bytes = std::move(*Object);
+ }
+
+ return BackendRunResult{
+ .Kind = Output,
+ .Output = std::move(Bytes),
+ .Pipeline = std::move(*Pipeline),
+ .Actions = ActiveInstrumentation->actionEvents(),
+ };
+}
+
+std::string_view spelling(BackendOutputKind Output) noexcept {
+ switch (Output) {
+ case BackendOutputKind::PreLegalizerMIR:
+ return "prelegalizer-mir";
+ case BackendOutputKind::LegalizedMIR:
+ return "legalized-mir";
+ case BackendOutputKind::RegisterBankMIR:
+ return "regbank-mir";
+ case BackendOutputKind::SelectedMIR:
+ return "selected-mir";
+ case BackendOutputKind::PostSSAMIR:
+ return "post-ssa-mir";
+ case BackendOutputKind::PostRegisterAllocationMIR:
+ return "post-ra-mir";
+ case BackendOutputKind::FinalMIR:
+ return "final-mir";
+ case BackendOutputKind::Assembly:
+ return "assembly";
+ case BackendOutputKind::RelocatableObject:
+ return "object";
+ }
+ return "invalid";
+}
+
+Expected<BackendOutputKind> parseBackendOutputKind(std::string_view Value) {
+ if (Value == "prelegalizer-mir")
+ return BackendOutputKind::PreLegalizerMIR;
+ if (Value == "legalized-mir")
+ return BackendOutputKind::LegalizedMIR;
+ if (Value == "regbank-mir")
+ return BackendOutputKind::RegisterBankMIR;
+ if (Value == "selected-mir")
+ return BackendOutputKind::SelectedMIR;
+ if (Value == "post-ssa-mir")
+ return BackendOutputKind::PostSSAMIR;
+ if (Value == "post-ra-mir")
+ return BackendOutputKind::PostRegisterAllocationMIR;
+ if (Value == "final-mir")
+ return BackendOutputKind::FinalMIR;
+ if (Value == "assembly" || Value == "asm")
+ return BackendOutputKind::Assembly;
+ if (Value == "object" || Value == "obj")
+ return BackendOutputKind::RelocatableObject;
+ return makeUnexpected(ErrorCode::InvalidInvocation, "unknown backend output kind");
+}
+
+ArtifactKind manifestArtifactKind(BackendOutputKind Output) noexcept {
+ return static_cast<ArtifactKind>(static_cast<std::uint8_t>(Output));
+}
+
+Expected<ArtifactKind> cacheArtifactKind(BackendOutputKind Output) {
+ switch (Output) {
+ case BackendOutputKind::PreLegalizerMIR:
+ return ArtifactKind::PreLegalizerMIR;
+ case BackendOutputKind::SelectedMIR:
+ return ArtifactKind::SelectedMIR;
+ case BackendOutputKind::PostRegisterAllocationMIR:
+ return ArtifactKind::PostRegisterAllocationMIR;
+ case BackendOutputKind::FinalMIR:
+ return ArtifactKind::FinalMIR;
+ case BackendOutputKind::Assembly:
+ return ArtifactKind::Assembly;
+ case BackendOutputKind::RelocatableObject:
+ return ArtifactKind::RelocatableObject;
+ case BackendOutputKind::LegalizedMIR:
+ case BackendOutputKind::RegisterBankMIR:
+ case BackendOutputKind::PostSSAMIR:
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "the selected intermediate stage is not a cache boundary");
+ }
+ return makeUnexpected(ErrorCode::InvalidInvocation, "invalid backend output kind");
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/BackendInvocation.cpp b/backend/lib/Tooling/BackendInvocation.cpp
new file mode 100644
index 0000000..677cd2d
--- /dev/null
+++ b/backend/lib/Tooling/BackendInvocation.cpp
@@ -0,0 +1,500 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/BackendInvocation.h"
+
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/RegisterMask.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/CodeGen/TargetMIRTextInfo.h"
+#include "rcc/CodeGen/TargetRegisterInfo.h"
+#include "rcc/Support/SHA256.h"
+
+#include <algorithm>
+#include <cctype>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <unordered_set>
+#include <utility>
+
+namespace rcc::tooling {
+namespace {
+
+void appendField(std::string &Output, std::string_view Name, std::string_view Value) {
+ Output.append(Name);
+ Output.push_back('=');
+ Output.append(std::to_string(Value.size()));
+ Output.push_back(':');
+ Output.append(Value);
+ Output.push_back('\n');
+}
+
+template <typename IntegerT>
+void appendInteger(std::string &Output, std::string_view Name, IntegerT Value) {
+ appendField(Output, Name, std::to_string(Value));
+}
+
+void appendBoolean(std::string &Output, std::string_view Name, bool Value) {
+ appendField(Output, Name, Value ? "true" : "false");
+}
+
+[[nodiscard]] bool isValidName(std::string_view Value) noexcept {
+ return !Value.empty() && std::ranges::all_of(Value, [](unsigned char Character) {
+ return std::isalnum(Character) != 0 || Character == '-' || Character == '_' || Character == '.';
+ });
+}
+
+[[nodiscard]] Expected<void> canonicalizeOptions(std::vector<BackendOption> &Options,
+ std::string_view Category) {
+ std::ranges::sort(Options, {}, &BackendOption::Name);
+ for (std::size_t Index = 0; Index < Options.size(); ++Index) {
+ if (!isValidName(Options[Index].Name)) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ std::string(Category) + " option has an invalid name");
+ }
+ if (Index != 0 && Options[Index - 1].Name == Options[Index].Name) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ std::string(Category) + " option names must be unique");
+ }
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> canonicalizeFeatures(std::vector<std::string> &Features) {
+ for (std::string &Feature : Features) {
+ if (Feature.empty())
+ return makeUnexpected(ErrorCode::InvalidInvocation, "target feature cannot be empty");
+ if (Feature.front() != '+' && Feature.front() != '-')
+ Feature.insert(Feature.begin(), '+');
+ if (!isValidName(std::string_view(Feature).substr(1))) {
+ return makeUnexpected(ErrorCode::InvalidInvocation, "target feature has an invalid spelling");
+ }
+ }
+ std::ranges::sort(Features, [](const std::string &Left, const std::string &Right) {
+ return std::string_view(Left).substr(1) < std::string_view(Right).substr(1);
+ });
+ for (std::size_t Index = 1; Index < Features.size(); ++Index) {
+ if (std::string_view(Features[Index - 1]).substr(1) ==
+ std::string_view(Features[Index]).substr(1)) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "target feature names must be unique and non-conflicting");
+ }
+ }
+ return {};
+}
+
+[[nodiscard]] bool isSHA256(std::string_view Value) noexcept {
+ return Value.size() == 64 && std::ranges::all_of(Value, [](unsigned char Character) {
+ return std::isxdigit(Character) != 0 &&
+ (std::isdigit(Character) != 0 || std::islower(Character) != 0);
+ });
+}
+
+void appendOperandDescriptor(std::string &Output, const OperandDescriptor &Operand) {
+ appendInteger(Output, "operand.kinds", Operand.Kinds.rawValue());
+ appendInteger(Output, "operand.role", static_cast<unsigned>(Operand.RegisterRole));
+ appendInteger(Output, "operand.reg-class", Operand.RegClass ? Operand.RegClass->value() : 0U);
+ appendInteger(Output, "operand.reg-bank", Operand.RegBank ? Operand.RegBank->value() : 0U);
+ appendInteger(Output, "operand.immediate-predicate",
+ Operand.ImmediatePredicate ? Operand.ImmediatePredicate->value() : 0U);
+ appendInteger(Output, "operand.memory-role", static_cast<unsigned>(Operand.MemoryRole));
+ appendInteger(Output, "operand.tie",
+ Operand.DefaultTiedOperand ? *Operand.DefaultTiedOperand + 1U : 0U);
+ appendBoolean(Output, "operand.early-clobber", Operand.EarlyClobber);
+ appendBoolean(Output, "operand.optional", Operand.Optional);
+ appendBoolean(Output, "operand.variadic-group", Operand.VariadicGroup);
+ appendBoolean(Output, "operand.allow-subreg", Operand.AllowSubReg);
+ appendBoolean(Output, "operand.allow-any-target-flags", Operand.AllowAnyTargetFlags);
+ appendInteger(Output, "operand.named", Operand.Name ? Operand.Name->value() : 0U);
+ appendInteger(Output, "operand.target-type",
+ Operand.TargetOperandType ? Operand.TargetOperandType->value() : 0U);
+ appendInteger(Output, "operand.target-flags", Operand.AllowedTargetFlags);
+ appendInteger(Output, "operand.type-kinds",
+ Operand.TypeConstraint ? Operand.TypeConstraint->Kinds.rawValue() : 0U);
+ appendInteger(Output, "operand.type-equality",
+ Operand.TypeConstraint && Operand.TypeConstraint->EqualityGroup
+ ? static_cast<std::uint32_t>(*Operand.TypeConstraint->EqualityGroup) + 1U
+ : 0U);
+}
+
+void appendInstructionSet(std::string &Output, const InstructionSet &Instructions) {
+ appendInteger(Output, "instructions.count", Instructions.descriptors().size());
+ for (const InstructionDescriptor &Descriptor : Instructions.descriptors()) {
+ appendInteger(Output, "instruction.opcode", Descriptor.InstructionOpcode.value());
+ appendField(Output, "instruction.name", Descriptor.Name);
+ appendInteger(Output, "instruction.explicit-defs", Descriptor.NumExplicitDefs);
+ appendBoolean(Output, "instruction.variadic", Descriptor.Variadic);
+ appendInteger(Output, "instruction.minimum-variadic", Descriptor.MinimumVariadicRepetitions);
+ appendBoolean(Output, "instruction.extra-implicit", Descriptor.AllowExtraImplicitOperands);
+ appendInteger(Output, "instruction.flags", Descriptor.Flags.rawValue());
+ appendInteger(Output, "instruction.scheduling-class", Descriptor.SchedulingClass.value());
+ appendInteger(Output, "instruction.encoding-category", Descriptor.EncodingCategory.value());
+ appendInteger(Output, "instruction.assembly-format", Descriptor.AssemblyFormat.value());
+ appendBoolean(Output, "instruction.memory-operands", Descriptor.RequiresMemoryOperands);
+ appendInteger(Output, "instruction.pseudo-owner", static_cast<unsigned>(Descriptor.Owner));
+ appendInteger(Output, "instruction.deadline", static_cast<unsigned>(Descriptor.Deadline));
+ appendBoolean(Output, "instruction.explicit-verifier",
+ Descriptor.VerifyExplicitOperands != nullptr);
+ appendBoolean(Output, "instruction.semantic-verifier",
+ Descriptor.VerifyInstructionSemantics != nullptr);
+ appendInteger(Output, "instruction.operands", Descriptor.Operands.size());
+ for (const OperandDescriptor &Operand : Descriptor.Operands)
+ appendOperandDescriptor(Output, Operand);
+ appendInteger(Output, "instruction.implicit-defs", Descriptor.ImplicitDefs.size());
+ for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) {
+ appendInteger(Output, "implicit.register", Implicit.Reg.number());
+ appendBoolean(Output, "implicit.early-clobber", Implicit.EarlyClobber);
+ appendBoolean(Output, "implicit.renamable", Implicit.Renamable);
+ }
+ appendInteger(Output, "instruction.implicit-uses", Descriptor.ImplicitUses.size());
+ for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) {
+ appendInteger(Output, "implicit.register", Implicit.Reg.number());
+ appendBoolean(Output, "implicit.early-clobber", Implicit.EarlyClobber);
+ appendBoolean(Output, "implicit.renamable", Implicit.Renamable);
+ }
+ }
+}
+
+void appendRegisterInfo(std::string &Output, const TargetRegisterInfo &Registers,
+ const TargetMIRTextInfo &MIRText) {
+ appendInteger(Output, "register-units.count", Registers.registerUnits().size());
+ for (const RegisterUnitDesc &Unit : Registers.registerUnits()) {
+ appendInteger(Output, "register-unit.id", Unit.ID.value());
+ appendField(Output, "register-unit.name", Unit.Name);
+ }
+ appendInteger(Output, "registers.count", Registers.physicalRegisters().size());
+ for (const PhysicalRegisterDesc &Register : Registers.physicalRegisters()) {
+ appendInteger(Output, "register.id", Register.Reg.number());
+ appendField(Output, "register.name", Register.Name);
+ appendInteger(Output, "register.encoding", Register.Encoding);
+ appendBoolean(Output, "register.constant", Register.IsConstant);
+ appendBoolean(Output, "register.artificial", Register.IsArtificial);
+ appendBoolean(Output, "register.reserved", Register.IsReserved);
+ for (const RegisterUnitLane &Unit : Register.Units) {
+ appendInteger(Output, "register.unit", Unit.Unit.value());
+ appendInteger(Output, "register.lanes", Unit.Lanes.rawValue());
+ }
+ for (const std::string &Name : Register.AlternativeNames)
+ appendField(Output, "register.alternative-name", Name);
+ appendInteger(
+ Output, "register.dwarf",
+ MIRText.dwarfRegister(Register.Reg).value_or(std::numeric_limits<std::uint32_t>::max()));
+ }
+ appendInteger(Output, "subregister-indices.count", Registers.subRegIndices().size());
+ for (const SubRegIndexDesc &Index : Registers.subRegIndices()) {
+ appendInteger(Output, "subregister-index.id", Index.ID.value());
+ appendField(Output, "subregister-index.name", Index.Name);
+ appendInteger(Output, "subregister-index.lanes", Index.Lanes.rawValue());
+ appendInteger(Output, "subregister-index.size", Index.SizeInBits);
+ appendInteger(Output, "subregister-index.offset", Index.OffsetInBits);
+ }
+ appendInteger(Output, "register-classes.count", Registers.registerClasses().size());
+ for (const RegisterClassDesc &Class : Registers.registerClasses()) {
+ appendInteger(Output, "register-class.id", Class.ID.value());
+ appendField(Output, "register-class.name", Class.Name);
+ appendInteger(Output, "register-class.size", Class.SizeInBits);
+ appendInteger(Output, "register-class.spill-size", Class.SpillSizeInBits);
+ appendInteger(Output, "register-class.spill-alignment", Class.SpillAlignmentInBits);
+ appendInteger(Output, "register-class.lanes", Class.Lanes.rawValue());
+ appendInteger(Output, "register-class.bank", Class.DefaultBank.value());
+ appendBoolean(Output, "register-class.allocatable", Class.Allocatable);
+ appendInteger(Output, "register-class.copy-cost", Class.CopyCost);
+ appendBoolean(Output, "register-class.covered-by-subregs", Class.CoveredBySubRegs);
+ for (PhysicalRegister Register : Class.Registers)
+ appendInteger(Output, "register-class.register", Register.number());
+ for (PhysicalRegister Register : Class.AllocationOrder)
+ appendInteger(Output, "register-class.allocation-order", Register.number());
+ for (SubRegIndex Index : Class.SupportedSubRegs)
+ appendInteger(Output, "register-class.subregister", Index.value());
+ for (RegisterClassID SuperClass : Class.SuperClasses)
+ appendInteger(Output, "register-class.superclass", SuperClass.value());
+ }
+ appendInteger(Output, "register-banks.count", Registers.registerBanks().size());
+ for (const RegisterBankDesc &Bank : Registers.registerBanks()) {
+ appendInteger(Output, "register-bank.id", Bank.ID.value());
+ appendField(Output, "register-bank.name", Bank.Name);
+ appendInteger(Output, "register-bank.maximum-size", Bank.MaximumSizeInBits);
+ for (RegisterClassID Class : Bank.RegisterClasses)
+ appendInteger(Output, "register-bank.class", Class.value());
+ }
+}
+
+void appendMIRTextInfo(std::string &Output, const TargetMIRTextInfo &MIRText) {
+ appendInteger(Output, "mir.direct-flag-mask", MIRText.directOperandFlagMask());
+ for (const MIRRegisterMaskDesc &Mask : MIRText.registerMasks()) {
+ appendField(Output, "mir.register-mask", Mask.Name);
+ if (Mask.Mask != nullptr) {
+ for (std::uint64_t Word : Mask.Mask->words())
+ appendInteger(Output, "mir.register-mask-word", Word);
+ }
+ }
+ for (const MIRTargetIndexDesc &Index : MIRText.targetIndices()) {
+ appendField(Output, "mir.target-index-name", Index.Name);
+ appendInteger(Output, "mir.target-index", Index.Index.value());
+ }
+ for (const MIROperandFlagDesc &Flag : MIRText.directOperandFlags()) {
+ appendField(Output, "mir.direct-flag-name", Flag.Name);
+ appendInteger(Output, "mir.direct-flag", Flag.Value);
+ }
+ for (const MIROperandFlagDesc &Flag : MIRText.bitmaskOperandFlags()) {
+ appendField(Output, "mir.bitmask-flag-name", Flag.Name);
+ appendInteger(Output, "mir.bitmask-flag", Flag.Value);
+ }
+ for (const MIRMachineMemOperandFlagDesc &Flag : MIRText.machineMemOperandFlags()) {
+ appendField(Output, "mir.mmo-flag-name", Flag.Name);
+ appendInteger(Output, "mir.mmo-flag", Flag.Value);
+ }
+ for (const MIRVirtualRegisterFlagDesc &Flag : MIRText.virtualRegisterFlags()) {
+ appendField(Output, "mir.vreg-flag-name", Flag.Name);
+ appendInteger(Output, "mir.vreg-flag", Flag.Value);
+ }
+ for (const MIRIntrinsicDesc &Intrinsic : MIRText.intrinsics()) {
+ appendField(Output, "mir.intrinsic-name", Intrinsic.Name);
+ appendInteger(Output, "mir.intrinsic", Intrinsic.ID.value());
+ }
+ for (StackID ID : MIRText.supportedStackIDs())
+ appendInteger(Output, "mir.stack-id", ID.value());
+ appendInteger(Output, "mir.function-state-type",
+ MIRText.functionStateType() ? MIRText.functionStateType()->value() : 0U);
+}
+
+} // namespace
+
+std::string_view spelling(RelocationModel Value) noexcept {
+ switch (Value) {
+ case RelocationModel::Static:
+ return "static";
+ case RelocationModel::PositionIndependent:
+ return "pic";
+ }
+ return "invalid";
+}
+
+std::string_view spelling(CodeModel Value) noexcept {
+ switch (Value) {
+ case CodeModel::Small:
+ return "small";
+ case CodeModel::Medium:
+ return "medium";
+ case CodeModel::Large:
+ return "large";
+ }
+ return "invalid";
+}
+
+std::string_view spelling(OptimizationLevel Value) noexcept {
+ switch (Value) {
+ case OptimizationLevel::O0:
+ return "O0";
+ case OptimizationLevel::O1:
+ return "O1";
+ case OptimizationLevel::O2:
+ return "O2";
+ case OptimizationLevel::O3:
+ return "O3";
+ case OptimizationLevel::Os:
+ return "Os";
+ case OptimizationLevel::Oz:
+ return "Oz";
+ }
+ return "invalid";
+}
+
+std::string_view spelling(LayoutOwnership Value) noexcept {
+ switch (Value) {
+ case LayoutOwnership::NativeObject:
+ return "native-object";
+ case LayoutOwnership::CompilerFinalLayout:
+ return "compiler-final-layout";
+ case LayoutOwnership::ExternalRelaxation:
+ return "external-relaxation";
+ }
+ return "invalid";
+}
+
+Expected<RelocationModel> parseRelocationModel(std::string_view Value) {
+ if (Value == "static")
+ return RelocationModel::Static;
+ if (Value == "pic")
+ return RelocationModel::PositionIndependent;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown relocation model");
+}
+
+Expected<CodeModel> parseCodeModel(std::string_view Value) {
+ if (Value == "small")
+ return CodeModel::Small;
+ if (Value == "medium")
+ return CodeModel::Medium;
+ if (Value == "large")
+ return CodeModel::Large;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown code model");
+}
+
+Expected<OptimizationLevel> parseOptimizationLevel(std::string_view Value) {
+ if (Value == "O0")
+ return OptimizationLevel::O0;
+ if (Value == "O1")
+ return OptimizationLevel::O1;
+ if (Value == "O2")
+ return OptimizationLevel::O2;
+ if (Value == "O3")
+ return OptimizationLevel::O3;
+ if (Value == "Os")
+ return OptimizationLevel::Os;
+ if (Value == "Oz")
+ return OptimizationLevel::Oz;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown optimization level");
+}
+
+Expected<LayoutOwnership> parseLayoutOwnership(std::string_view Value) {
+ if (Value == "native-object")
+ return LayoutOwnership::NativeObject;
+ if (Value == "compiler-final-layout")
+ return LayoutOwnership::CompilerFinalLayout;
+ if (Value == "external-relaxation")
+ return LayoutOwnership::ExternalRelaxation;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown layout ownership");
+}
+
+Expected<void> BackendInvocation::canonicalizeAndVerify() {
+ if (SchemaVersion != BackendInvocationSchemaVersion) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation schema version is unsupported");
+ }
+ if (Triple.empty() || CPU.empty() || TuneCPU.empty() || ABI.empty() || DataLayout.empty() ||
+ MIRReferenceRevision.empty() || GenericOpcodeVersion.empty() ||
+ TargetABILoweringVersion.empty() || BuildFingerprint.empty()) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation is missing a required target or version fact");
+ }
+ if (Determinism.ThreadCount == 0) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation thread count must be nonzero");
+ }
+ auto FeatureResult = canonicalizeFeatures(Features);
+ if (!FeatureResult)
+ return FeatureResult;
+ auto TargetOptionResult = canonicalizeOptions(TargetOptions, "target");
+ if (!TargetOptionResult)
+ return TargetOptionResult;
+ auto AssemblerOptionResult = canonicalizeOptions(AssemblerOptions, "assembler");
+ if (!AssemblerOptionResult)
+ return AssemblerOptionResult;
+ if (PassPipeline.empty() ||
+ std::ranges::any_of(PassPipeline, [](const std::string &Pass) { return Pass.empty(); })) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation pass pipeline cannot be empty");
+ }
+ if (Layout == LayoutOwnership::ExternalRelaxation &&
+ (AssemblerFlavor.empty() || AssemblerVersion.empty())) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "external relaxation requires explicit assembler flavor and version");
+ }
+ if (AssemblerFlavor.empty() != AssemblerVersion.empty()) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "assembler flavor and version must be specified together");
+ }
+ std::ranges::sort(EnabledActions);
+ if (std::ranges::any_of(EnabledActions,
+ [](const std::string &Action) { return !isValidName(Action); }) ||
+ std::ranges::adjacent_find(EnabledActions) != EnabledActions.end()) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "enabled action names must be valid and unique");
+ }
+ return {};
+}
+
+std::string BackendInvocation::canonicalText() const {
+ std::string Output;
+ appendInteger(Output, "schema", SchemaVersion);
+ appendField(Output, "triple", Triple);
+ appendField(Output, "cpu", CPU);
+ appendField(Output, "tune-cpu", TuneCPU);
+ for (const std::string &Feature : Features)
+ appendField(Output, "feature", Feature);
+ appendField(Output, "abi", ABI);
+ appendField(Output, "data-layout", DataLayout);
+ appendField(Output, "relocation-model", spelling(Relocation));
+ appendField(Output, "code-model", spelling(Code));
+ for (const BackendOption &Option : TargetOptions) {
+ appendField(Output, "target-option-name", Option.Name);
+ appendField(Output, "target-option-value", Option.Value);
+ }
+ appendField(Output, "layout-ownership", spelling(Layout));
+ appendField(Output, "assembler-flavor", AssemblerFlavor);
+ appendField(Output, "assembler-version", AssemblerVersion);
+ for (const BackendOption &Option : AssemblerOptions) {
+ appendField(Output, "assembler-option-name", Option.Name);
+ appendField(Output, "assembler-option-value", Option.Value);
+ }
+ appendField(Output, "optimization-level", spelling(Optimization));
+ for (const std::string &Pass : PassPipeline)
+ appendField(Output, "pass", Pass);
+ appendInteger(Output, "random-seed", Determinism.RandomSeed);
+ appendInteger(Output, "thread-count", Determinism.ThreadCount);
+ appendBoolean(Output, "stable-scheduling", Determinism.StableScheduling);
+ appendField(Output, "action-fuel", ActionFuel ? std::to_string(*ActionFuel) : "unlimited");
+ for (const std::string &Action : EnabledActions)
+ appendField(Output, "enabled-action", Action);
+ appendField(Output, "mir-reference-revision", MIRReferenceRevision);
+ appendField(Output, "generic-opcode-version", GenericOpcodeVersion);
+ appendField(Output, "target-abi-lowering-version", TargetABILoweringVersion);
+ appendField(Output, "build-fingerprint", BuildFingerprint);
+ return Output;
+}
+
+BackendInvocation defaultRV64GCInvocation() {
+ BackendInvocation Result;
+ Result.Triple = "riscv64-unknown-linux-gnu";
+ Result.CPU = "generic-rv64gc";
+ Result.TuneCPU = "generic-rv64gc";
+ Result.Features = {"+i", "+m", "+a", "+f", "+d", "+c", "+zicsr", "+zifencei"};
+ Result.ABI = "lp64d";
+ Result.DataLayout = "e-m:e-p:64:64-i64:64-i128:128-n32:64-S128";
+ Result.TargetOptions = {
+ {"function-sections", "false"},
+ {"omit-frame-pointer", "true"},
+ {"stack-realignment", "false"},
+ };
+ Result.AssemblerFlavor = "rcc-integrated-gnu";
+ Result.AssemblerVersion = "rcc-mc-v1";
+ Result.AssemblerOptions = {{"relax", "true"}};
+ auto Verified = Result.canonicalizeAndVerify();
+ (void)Verified;
+ return Result;
+}
+
+Expected<std::string> computeTargetDescriptionFingerprint(const TargetDescription &Target) {
+ std::string Canonical;
+ appendField(Canonical, "fingerprint-schema", "rcc-target-fingerprint-v1");
+ appendInstructionSet(Canonical, Target.instructions());
+ appendRegisterInfo(Canonical, Target.registers(), Target.mirText());
+ appendMIRTextInfo(Canonical, Target.mirText());
+ return sha256Hex(Canonical);
+}
+
+Expected<std::string> computeCacheKey(std::string_view CanonicalMIR,
+ const BackendInvocation &Invocation,
+ std::string_view TargetFingerprint) {
+ BackendInvocation CanonicalInvocation = Invocation;
+ auto Verified = CanonicalInvocation.canonicalizeAndVerify();
+ if (!Verified)
+ return std::unexpected(Verified.error());
+ if (!isSHA256(TargetFingerprint)) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "target description fingerprint must be a lowercase SHA-256 digest");
+ }
+ std::string Input;
+ appendField(Input, "cache-key-schema", "rcc-backend-cache-key-v1");
+ appendField(Input, "input-mir-semantic-hash", sha256Hex(CanonicalMIR));
+ appendField(Input, "target-description-fingerprint", TargetFingerprint);
+ appendField(Input, "invocation", CanonicalInvocation.canonicalText());
+ return sha256Hex(Input);
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/BackendManifest.cpp b/backend/lib/Tooling/BackendManifest.cpp
new file mode 100644
index 0000000..04c410a
--- /dev/null
+++ b/backend/lib/Tooling/BackendManifest.cpp
@@ -0,0 +1,733 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/BackendManifest.h"
+
+#include "rcc/Support/YAML.h"
+
+#include <algorithm>
+#include <cctype>
+#include <charconv>
+#include <cstddef>
+#include <cstdint>
+#include <initializer_list>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <unordered_set>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+[[nodiscard]] bool isDigest(std::string_view Value) noexcept {
+ return Value.size() == 64 && std::ranges::all_of(Value, [](unsigned char Character) {
+ return (Character >= '0' && Character <= '9') || (Character >= 'a' && Character <= 'f');
+ });
+}
+
+[[nodiscard]] std::string quoted(std::string_view Value) {
+ constexpr std::string_view Hex = "0123456789abcdef";
+ std::string Result{"\""};
+ for (char RawCharacter : Value) {
+ const auto Character = static_cast<unsigned char>(RawCharacter);
+ switch (Character) {
+ case '\\':
+ Result.append("\\\\");
+ break;
+ case '"':
+ Result.append("\\\"");
+ break;
+ case '\n':
+ Result.append("\\n");
+ break;
+ case '\r':
+ Result.append("\\r");
+ break;
+ case '\t':
+ Result.append("\\t");
+ break;
+ default:
+ if (Character < 0x20U || Character == 0x7fU) {
+ Result.append("\\u00");
+ Result.push_back(Hex[Character >> 4U]);
+ Result.push_back(Hex[Character & 0x0fU]);
+ } else {
+ Result.push_back(static_cast<char>(Character));
+ }
+ break;
+ }
+ }
+ Result.push_back('"');
+ return Result;
+}
+
+void appendScalar(std::string &Output, std::string_view Indent, std::string_view Name,
+ std::string_view Value) {
+ Output.append(Indent);
+ Output.append(Name);
+ Output.append(": ");
+ Output.append(quoted(Value));
+ Output.push_back('\n');
+}
+
+template <typename IntegerT>
+void appendInteger(std::string &Output, std::string_view Indent, std::string_view Name,
+ IntegerT Value) {
+ Output.append(Indent);
+ Output.append(Name);
+ Output.append(": ");
+ Output.append(std::to_string(Value));
+ Output.push_back('\n');
+}
+
+void appendBoolean(std::string &Output, std::string_view Indent, std::string_view Name,
+ bool Value) {
+ Output.append(Indent);
+ Output.append(Name);
+ Output.append(Value ? ": true\n" : ": false\n");
+}
+
+void appendStringSequence(std::string &Output, std::string_view Indent, std::string_view Name,
+ std::span<const std::string> Values) {
+ Output.append(Indent);
+ Output.append(Name);
+ if (Values.empty()) {
+ Output.append(": []\n");
+ return;
+ }
+ Output.append(":\n");
+ for (const std::string &Value : Values) {
+ Output.append(Indent);
+ Output.append(" - ");
+ Output.append(quoted(Value));
+ Output.push_back('\n');
+ }
+}
+
+void appendOptions(std::string &Output, std::string_view Indent, std::string_view Name,
+ std::span<const BackendOption> Options) {
+ Output.append(Indent);
+ Output.append(Name);
+ if (Options.empty()) {
+ Output.append(": []\n");
+ return;
+ }
+ Output.append(":\n");
+ for (const BackendOption &Option : Options) {
+ Output.append(Indent);
+ Output.append(" - name: ");
+ Output.append(quoted(Option.Name));
+ Output.push_back('\n');
+ appendScalar(Output, std::string(Indent) + " ", "value", Option.Value);
+ }
+}
+
+void appendInvocation(std::string &Output, const BackendInvocation &Invocation) {
+ appendInteger(Output, " ", "schema", Invocation.SchemaVersion);
+ appendScalar(Output, " ", "triple", Invocation.Triple);
+ appendScalar(Output, " ", "cpu", Invocation.CPU);
+ appendScalar(Output, " ", "tune_cpu", Invocation.TuneCPU);
+ appendStringSequence(Output, " ", "features", Invocation.Features);
+ appendScalar(Output, " ", "abi", Invocation.ABI);
+ appendScalar(Output, " ", "data_layout", Invocation.DataLayout);
+ appendScalar(Output, " ", "relocation_model", spelling(Invocation.Relocation));
+ appendScalar(Output, " ", "code_model", spelling(Invocation.Code));
+ appendOptions(Output, " ", "target_options", Invocation.TargetOptions);
+ appendScalar(Output, " ", "layout_ownership", spelling(Invocation.Layout));
+ appendScalar(Output, " ", "assembler_flavor", Invocation.AssemblerFlavor);
+ appendScalar(Output, " ", "assembler_version", Invocation.AssemblerVersion);
+ appendOptions(Output, " ", "assembler_options", Invocation.AssemblerOptions);
+ appendScalar(Output, " ", "optimization_level", spelling(Invocation.Optimization));
+ appendStringSequence(Output, " ", "pass_pipeline", Invocation.PassPipeline);
+ appendInteger(Output, " ", "random_seed", Invocation.Determinism.RandomSeed);
+ appendInteger(Output, " ", "thread_count", Invocation.Determinism.ThreadCount);
+ appendBoolean(Output, " ", "stable_scheduling", Invocation.Determinism.StableScheduling);
+ if (Invocation.ActionFuel) {
+ appendInteger(Output, " ", "action_fuel", *Invocation.ActionFuel);
+ } else {
+ Output.append(" action_fuel: null\n");
+ }
+ appendStringSequence(Output, " ", "enabled_actions", Invocation.EnabledActions);
+ appendScalar(Output, " ", "mir_reference_revision", Invocation.MIRReferenceRevision);
+ appendScalar(Output, " ", "generic_opcode_version", Invocation.GenericOpcodeVersion);
+ appendScalar(Output, " ", "target_abi_lowering_version", Invocation.TargetABILoweringVersion);
+ appendScalar(Output, " ", "build_fingerprint", Invocation.BuildFingerprint);
+}
+
+void appendOptionalInteger(std::string &Output, std::string_view Indent, std::string_view Name,
+ std::optional<std::uint64_t> Value) {
+ if (Value) {
+ appendInteger(Output, Indent, Name, *Value);
+ } else {
+ Output.append(Indent);
+ Output.append(Name);
+ Output.append(": null\n");
+ }
+}
+
+class ManifestParser final {
+public:
+ ManifestParser(std::string SourceName, std::string SourceText)
+ : Parsed(yaml::parse(std::move(SourceName), std::move(SourceText))) {}
+
+ [[nodiscard]] Expected<BackendManifest> run() {
+ if (!Parsed.succeeded()) {
+ const std::span<const TextDiagnostic> Diagnostics = Parsed.diagnostics();
+ return makeUnexpected(ErrorCode::ManifestError, Diagnostics.empty()
+ ? "manifest YAML parsing failed"
+ : Diagnostics.front().Message);
+ }
+ Stream = Parsed.stream();
+ if (Stream == nullptr || Stream->documents().size() != 1) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest must contain exactly one YAML document");
+ }
+ const yaml::Node *Root = Stream->node(Stream->documents().front().Root);
+ auto RootMapping = requireMapping(Root, "manifest root");
+ if (!RootMapping)
+ return std::unexpected(RootMapping.error());
+ auto RootKeys =
+ rejectUnknown(**RootMapping,
+ {"schema", "kind", "artifact", "input_mir_hash", "target_fingerprint",
+ "cache_key", "artifact_hash", "invocation", "diagnostics"},
+ "manifest root");
+ if (!RootKeys)
+ return std::unexpected(RootKeys.error());
+
+ BackendManifest Result;
+ auto Schema = requiredUnsigned<std::uint32_t>(**RootMapping, "schema", "manifest root");
+ auto Kind = requiredScalar(**RootMapping, "kind", "manifest root");
+ auto Artifact = requiredScalar(**RootMapping, "artifact", "manifest root");
+ auto InputHash = requiredScalar(**RootMapping, "input_mir_hash", "manifest root");
+ auto TargetHash = requiredScalar(**RootMapping, "target_fingerprint", "manifest root");
+ auto CacheKey = requiredScalar(**RootMapping, "cache_key", "manifest root");
+ const yaml::Node *Invocation = mappingValue(**RootMapping, "invocation");
+ const yaml::Node *Diagnostics = mappingValue(**RootMapping, "diagnostics");
+ if (!Schema || !Kind || !Artifact || !InputHash || !TargetHash || !CacheKey)
+ return firstError(Schema, Kind, Artifact, InputHash, TargetHash, CacheKey);
+ Result.SchemaVersion = *Schema;
+ auto ParsedKind = parseManifestKind(*Kind);
+ if (!ParsedKind)
+ return std::unexpected(ParsedKind.error());
+ Result.Kind = *ParsedKind;
+ auto ParsedArtifact = parseArtifactKind(*Artifact);
+ if (!ParsedArtifact)
+ return std::unexpected(ParsedArtifact.error());
+ Result.Artifact = *ParsedArtifact;
+ Result.InputMIRHash = std::move(*InputHash);
+ Result.TargetFingerprint = std::move(*TargetHash);
+ Result.CacheKey = std::move(*CacheKey);
+ if (const yaml::Node *ArtifactHash = mappingValue(**RootMapping, "artifact_hash");
+ ArtifactHash != nullptr && ArtifactHash->kind() != yaml::NodeKind::Null) {
+ auto Value = scalar(ArtifactHash, "manifest artifact_hash");
+ if (!Value)
+ return std::unexpected(Value.error());
+ Result.ArtifactHash = std::move(*Value);
+ }
+ auto ParsedInvocation = parseInvocation(Invocation);
+ if (!ParsedInvocation)
+ return std::unexpected(ParsedInvocation.error());
+ Result.Invocation = std::move(*ParsedInvocation);
+ auto ParsedDiagnostics = parseDiagnostics(Diagnostics);
+ if (!ParsedDiagnostics)
+ return std::unexpected(ParsedDiagnostics.error());
+ Result.Diagnostics = std::move(*ParsedDiagnostics);
+ auto Verification = Result.verify();
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ return Result;
+ }
+
+private:
+ template <typename... Results>
+ [[nodiscard]] Expected<BackendManifest> firstError(const Results &...Values) const {
+ std::optional<Error> Failure;
+ const auto Capture = [&Failure](const auto &Value) {
+ if (!Value && !Failure)
+ Failure = Value.error();
+ };
+ (Capture(Values), ...);
+ if (!Failure) {
+ return makeUnexpected(ErrorCode::InternalError,
+ "manifest parser requested a missing field error without a failure");
+ }
+ return std::unexpected(*Failure);
+ }
+
+ [[nodiscard]] Expected<const yaml::Node *> requireMapping(const yaml::Node *Node,
+ std::string_view Context) const {
+ if (Node == nullptr || Node->kind() != yaml::NodeKind::Mapping) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) + " must be a mapping");
+ }
+ return Node;
+ }
+
+ [[nodiscard]] Expected<void> rejectUnknown(const yaml::Node &Node,
+ std::initializer_list<std::string_view> Allowed,
+ std::string_view Context) const {
+ std::unordered_set<std::string_view> Seen;
+ for (const yaml::MappingEntry &Entry : Node.mapping()) {
+ if (std::ranges::find(Allowed, Entry.Key) == Allowed.end()) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ std::string(Context) + " contains unknown key '" + Entry.Key + "'");
+ }
+ if (!Seen.insert(Entry.Key).second) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ std::string(Context) + " contains duplicate key '" + Entry.Key + "'");
+ }
+ }
+ return {};
+ }
+
+ [[nodiscard]] const yaml::Node *mappingValue(const yaml::Node &Node,
+ std::string_view Name) const noexcept {
+ const std::optional<yaml::NodeID> ID = Node.mappingValue(Name);
+ return ID && Stream != nullptr ? Stream->node(*ID) : nullptr;
+ }
+
+ [[nodiscard]] Expected<std::string> scalar(const yaml::Node *Node,
+ std::string_view Context) const {
+ if (Node == nullptr || Node->kind() != yaml::NodeKind::Scalar) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) + " must be a scalar");
+ }
+ return std::string(Node->scalar());
+ }
+
+ [[nodiscard]] Expected<std::string> requiredScalar(const yaml::Node &Node, std::string_view Name,
+ std::string_view Context) const {
+ const yaml::Node *Value = mappingValue(Node, Name);
+ if (Value == nullptr) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) +
+ " is missing required key '" +
+ std::string(Name) + "'");
+ }
+ return scalar(Value, std::string(Context) + "." + std::string(Name));
+ }
+
+ template <typename IntegerT>
+ [[nodiscard]] Expected<IntegerT> unsignedValue(const yaml::Node *Node,
+ std::string_view Context) const {
+ auto Text = scalar(Node, Context);
+ if (!Text)
+ return std::unexpected(Text.error());
+ IntegerT Result = 0;
+ const char *Begin = Text->data();
+ const char *End = Begin + Text->size();
+ const auto [Position, ErrorValue] = std::from_chars(Begin, End, Result);
+ if (ErrorValue != std::errc{} || Position != End) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ std::string(Context) + " must be an unsigned integer");
+ }
+ return Result;
+ }
+
+ template <typename IntegerT>
+ [[nodiscard]] Expected<IntegerT> requiredUnsigned(const yaml::Node &Node, std::string_view Name,
+ std::string_view Context) const {
+ const yaml::Node *Value = mappingValue(Node, Name);
+ if (Value == nullptr) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) +
+ " is missing required key '" +
+ std::string(Name) + "'");
+ }
+ return unsignedValue<IntegerT>(Value, std::string(Context) + "." + std::string(Name));
+ }
+
+ [[nodiscard]] Expected<bool> requiredBoolean(const yaml::Node &Node, std::string_view Name,
+ std::string_view Context) const {
+ auto Value = requiredScalar(Node, Name, Context);
+ if (!Value)
+ return std::unexpected(Value.error());
+ if (*Value == "true")
+ return true;
+ if (*Value == "false")
+ return false;
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) + "." + std::string(Name) +
+ " must be true or false");
+ }
+
+ [[nodiscard]] Expected<std::vector<std::string>> stringSequence(const yaml::Node *Node,
+ std::string_view Context) const {
+ if (Node == nullptr || Node->kind() != yaml::NodeKind::Sequence) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) + " must be a sequence");
+ }
+ std::vector<std::string> Result;
+ Result.reserve(Node->sequence().size());
+ for (yaml::NodeID ID : Node->sequence()) {
+ auto Value = scalar(Stream->node(ID), Context);
+ if (!Value)
+ return std::unexpected(Value.error());
+ Result.push_back(std::move(*Value));
+ }
+ return Result;
+ }
+
+ [[nodiscard]] Expected<std::vector<BackendOption>> parseOptions(const yaml::Node *Node,
+ std::string_view Context) const {
+ if (Node == nullptr || Node->kind() != yaml::NodeKind::Sequence) {
+ return makeUnexpected(ErrorCode::ManifestError, std::string(Context) + " must be a sequence");
+ }
+ std::vector<BackendOption> Result;
+ Result.reserve(Node->sequence().size());
+ for (yaml::NodeID ID : Node->sequence()) {
+ auto Entry = requireMapping(Stream->node(ID), Context);
+ if (!Entry)
+ return std::unexpected(Entry.error());
+ auto Keys = rejectUnknown(**Entry, {"name", "value"}, Context);
+ if (!Keys)
+ return std::unexpected(Keys.error());
+ auto Name = requiredScalar(**Entry, "name", Context);
+ auto Value = requiredScalar(**Entry, "value", Context);
+ if (!Name)
+ return std::unexpected(Name.error());
+ if (!Value)
+ return std::unexpected(Value.error());
+ Result.push_back({std::move(*Name), std::move(*Value)});
+ }
+ return Result;
+ }
+
+ [[nodiscard]] Expected<BackendInvocation> parseInvocation(const yaml::Node *Node) const {
+ auto Mapping = requireMapping(Node, "manifest invocation");
+ if (!Mapping)
+ return std::unexpected(Mapping.error());
+ auto Keys = rejectUnknown(**Mapping,
+ {"schema",
+ "triple",
+ "cpu",
+ "tune_cpu",
+ "features",
+ "abi",
+ "data_layout",
+ "relocation_model",
+ "code_model",
+ "target_options",
+ "layout_ownership",
+ "assembler_flavor",
+ "assembler_version",
+ "assembler_options",
+ "optimization_level",
+ "pass_pipeline",
+ "random_seed",
+ "thread_count",
+ "stable_scheduling",
+ "action_fuel",
+ "enabled_actions",
+ "mir_reference_revision",
+ "generic_opcode_version",
+ "target_abi_lowering_version",
+ "build_fingerprint"},
+ "manifest invocation");
+ if (!Keys)
+ return std::unexpected(Keys.error());
+
+ BackendInvocation Result;
+ auto Schema = requiredUnsigned<std::uint32_t>(**Mapping, "schema", "manifest invocation");
+ auto Triple = requiredScalar(**Mapping, "triple", "manifest invocation");
+ auto CPU = requiredScalar(**Mapping, "cpu", "manifest invocation");
+ auto TuneCPU = requiredScalar(**Mapping, "tune_cpu", "manifest invocation");
+ auto Features = stringSequence(mappingValue(**Mapping, "features"), "invocation.features");
+ auto ABI = requiredScalar(**Mapping, "abi", "manifest invocation");
+ auto DataLayout = requiredScalar(**Mapping, "data_layout", "manifest invocation");
+ auto Relocation = requiredScalar(**Mapping, "relocation_model", "manifest invocation");
+ auto Code = requiredScalar(**Mapping, "code_model", "manifest invocation");
+ auto TargetOptions =
+ parseOptions(mappingValue(**Mapping, "target_options"), "invocation.target_options");
+ auto Layout = requiredScalar(**Mapping, "layout_ownership", "manifest invocation");
+ auto AssemblerFlavor = requiredScalar(**Mapping, "assembler_flavor", "manifest invocation");
+ auto AssemblerVersion = requiredScalar(**Mapping, "assembler_version", "manifest invocation");
+ auto AssemblerOptions =
+ parseOptions(mappingValue(**Mapping, "assembler_options"), "invocation.assembler_options");
+ auto Optimization = requiredScalar(**Mapping, "optimization_level", "manifest invocation");
+ auto Pipeline =
+ stringSequence(mappingValue(**Mapping, "pass_pipeline"), "invocation.pass_pipeline");
+ auto RandomSeed =
+ requiredUnsigned<std::uint64_t>(**Mapping, "random_seed", "manifest invocation");
+ auto ThreadCount =
+ requiredUnsigned<std::uint32_t>(**Mapping, "thread_count", "manifest invocation");
+ auto Stable = requiredBoolean(**Mapping, "stable_scheduling", "manifest invocation");
+ auto Actions =
+ stringSequence(mappingValue(**Mapping, "enabled_actions"), "invocation.enabled_actions");
+ auto MIRRevision = requiredScalar(**Mapping, "mir_reference_revision", "manifest invocation");
+ auto GenericVersion =
+ requiredScalar(**Mapping, "generic_opcode_version", "manifest invocation");
+ auto ABIVersion =
+ requiredScalar(**Mapping, "target_abi_lowering_version", "manifest invocation");
+ auto Build = requiredScalar(**Mapping, "build_fingerprint", "manifest invocation");
+
+ if (!Schema || !Triple || !CPU || !TuneCPU || !Features || !ABI || !DataLayout || !Relocation ||
+ !Code || !TargetOptions || !Layout || !AssemblerFlavor || !AssemblerVersion ||
+ !AssemblerOptions || !Optimization || !Pipeline || !RandomSeed || !ThreadCount || !Stable ||
+ !Actions || !MIRRevision || !GenericVersion || !ABIVersion || !Build) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest invocation is missing or has an invalid required field");
+ }
+ Result.SchemaVersion = *Schema;
+ Result.Triple = std::move(*Triple);
+ Result.CPU = std::move(*CPU);
+ Result.TuneCPU = std::move(*TuneCPU);
+ Result.Features = std::move(*Features);
+ Result.ABI = std::move(*ABI);
+ Result.DataLayout = std::move(*DataLayout);
+ auto ParsedRelocation = parseRelocationModel(*Relocation);
+ auto ParsedCode = parseCodeModel(*Code);
+ auto ParsedLayout = parseLayoutOwnership(*Layout);
+ auto ParsedOptimization = parseOptimizationLevel(*Optimization);
+ if (!ParsedRelocation || !ParsedCode || !ParsedLayout || !ParsedOptimization) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest invocation contains an unknown enum value");
+ }
+ Result.Relocation = *ParsedRelocation;
+ Result.Code = *ParsedCode;
+ Result.TargetOptions = std::move(*TargetOptions);
+ Result.Layout = *ParsedLayout;
+ Result.AssemblerFlavor = std::move(*AssemblerFlavor);
+ Result.AssemblerVersion = std::move(*AssemblerVersion);
+ Result.AssemblerOptions = std::move(*AssemblerOptions);
+ Result.Optimization = *ParsedOptimization;
+ Result.PassPipeline = std::move(*Pipeline);
+ Result.Determinism = {
+ .RandomSeed = *RandomSeed,
+ .ThreadCount = *ThreadCount,
+ .StableScheduling = *Stable,
+ };
+ const yaml::Node *Fuel = mappingValue(**Mapping, "action_fuel");
+ if (Fuel == nullptr) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest invocation is missing required key 'action_fuel'");
+ }
+ if (Fuel->kind() != yaml::NodeKind::Null) {
+ auto Value = unsignedValue<std::uint64_t>(Fuel, "invocation.action_fuel");
+ if (!Value)
+ return std::unexpected(Value.error());
+ Result.ActionFuel = *Value;
+ }
+ Result.EnabledActions = std::move(*Actions);
+ Result.MIRReferenceRevision = std::move(*MIRRevision);
+ Result.GenericOpcodeVersion = std::move(*GenericVersion);
+ Result.TargetABILoweringVersion = std::move(*ABIVersion);
+ Result.BuildFingerprint = std::move(*Build);
+ auto Verified = Result.canonicalizeAndVerify();
+ if (!Verified)
+ return std::unexpected(Verified.error());
+ return Result;
+ }
+
+ [[nodiscard]] Expected<std::vector<StructuredDiagnostic>>
+ parseDiagnostics(const yaml::Node *Node) const {
+ if (Node == nullptr || Node->kind() != yaml::NodeKind::Sequence) {
+ return makeUnexpected(ErrorCode::ManifestError, "manifest diagnostics must be a sequence");
+ }
+ std::vector<StructuredDiagnostic> Result;
+ for (yaml::NodeID ID : Node->sequence()) {
+ auto Mapping = requireMapping(Stream->node(ID), "manifest diagnostic");
+ if (!Mapping)
+ return std::unexpected(Mapping.error());
+ auto Keys =
+ rejectUnknown(**Mapping,
+ {"category", "stage", "pass", "function", "block", "instruction", "operand",
+ "source_location", "target_constraint", "rule", "message"},
+ "manifest diagnostic");
+ if (!Keys)
+ return std::unexpected(Keys.error());
+ StructuredDiagnostic Diagnostic;
+ auto Category = requiredScalar(**Mapping, "category", "manifest diagnostic");
+ auto Stage = requiredScalar(**Mapping, "stage", "manifest diagnostic");
+ auto Pass = requiredScalar(**Mapping, "pass", "manifest diagnostic");
+ auto Function = requiredScalar(**Mapping, "function", "manifest diagnostic");
+ auto Source = requiredScalar(**Mapping, "source_location", "manifest diagnostic");
+ auto Constraint = requiredScalar(**Mapping, "target_constraint", "manifest diagnostic");
+ auto Rule = requiredScalar(**Mapping, "rule", "manifest diagnostic");
+ auto Message = requiredScalar(**Mapping, "message", "manifest diagnostic");
+ if (!Category || !Stage || !Pass || !Function || !Source || !Constraint || !Rule ||
+ !Message) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest diagnostic is missing a required string field");
+ }
+ Diagnostic.Category = std::move(*Category);
+ Diagnostic.Stage = std::move(*Stage);
+ Diagnostic.Pass = std::move(*Pass);
+ Diagnostic.Function = std::move(*Function);
+ Diagnostic.SourceLocation = std::move(*Source);
+ Diagnostic.TargetConstraint = std::move(*Constraint);
+ Diagnostic.Rule = std::move(*Rule);
+ Diagnostic.Message = std::move(*Message);
+ auto OptionalValue = [&](std::string_view Name, auto &Destination) -> Expected<void> {
+ const yaml::Node *Value = mappingValue(**Mapping, Name);
+ if (Value == nullptr) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest diagnostic is missing key '" + std::string(Name) + "'");
+ }
+ if (Value->kind() == yaml::NodeKind::Null)
+ return {};
+ using ValueT = typename std::remove_reference_t<decltype(Destination)>::value_type;
+ auto ParsedValue = unsignedValue<ValueT>(Value, Name);
+ if (!ParsedValue)
+ return std::unexpected(ParsedValue.error());
+ Destination = *ParsedValue;
+ return {};
+ };
+ auto Block = OptionalValue("block", Diagnostic.Block);
+ auto Instruction = OptionalValue("instruction", Diagnostic.Instruction);
+ auto Operand = OptionalValue("operand", Diagnostic.Operand);
+ if (!Block)
+ return std::unexpected(Block.error());
+ if (!Instruction)
+ return std::unexpected(Instruction.error());
+ if (!Operand)
+ return std::unexpected(Operand.error());
+ Result.push_back(std::move(Diagnostic));
+ }
+ return Result;
+ }
+
+ [[nodiscard]] Expected<ManifestKind> parseManifestKind(std::string_view Value) const {
+ if (Value == "cache")
+ return ManifestKind::Cache;
+ if (Value == "reproducer")
+ return ManifestKind::Reproducer;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown manifest kind");
+ }
+
+ [[nodiscard]] Expected<ArtifactKind> parseArtifactKind(std::string_view Value) const {
+ if (Value == "prelegalizer-mir")
+ return ArtifactKind::PreLegalizerMIR;
+ if (Value == "legalized-mir")
+ return ArtifactKind::LegalizedMIR;
+ if (Value == "regbank-mir")
+ return ArtifactKind::RegisterBankMIR;
+ if (Value == "selected-mir")
+ return ArtifactKind::SelectedMIR;
+ if (Value == "post-ssa-mir")
+ return ArtifactKind::PostSSAMIR;
+ if (Value == "post-ra-mir")
+ return ArtifactKind::PostRegisterAllocationMIR;
+ if (Value == "final-mir")
+ return ArtifactKind::FinalMIR;
+ if (Value == "assembly")
+ return ArtifactKind::Assembly;
+ if (Value == "object")
+ return ArtifactKind::RelocatableObject;
+ return makeUnexpected(ErrorCode::ManifestError, "unknown artifact kind");
+ }
+
+ yaml::ParseResult Parsed;
+ const yaml::Stream *Stream = nullptr;
+};
+
+} // namespace
+
+std::string_view spelling(ManifestKind Value) noexcept {
+ switch (Value) {
+ case ManifestKind::Cache:
+ return "cache";
+ case ManifestKind::Reproducer:
+ return "reproducer";
+ }
+ return "invalid";
+}
+
+std::string_view spelling(ArtifactKind Value) noexcept {
+ switch (Value) {
+ case ArtifactKind::PreLegalizerMIR:
+ return "prelegalizer-mir";
+ case ArtifactKind::LegalizedMIR:
+ return "legalized-mir";
+ case ArtifactKind::RegisterBankMIR:
+ return "regbank-mir";
+ case ArtifactKind::SelectedMIR:
+ return "selected-mir";
+ case ArtifactKind::PostSSAMIR:
+ return "post-ssa-mir";
+ case ArtifactKind::PostRegisterAllocationMIR:
+ return "post-ra-mir";
+ case ArtifactKind::FinalMIR:
+ return "final-mir";
+ case ArtifactKind::Assembly:
+ return "assembly";
+ case ArtifactKind::RelocatableObject:
+ return "object";
+ }
+ return "invalid";
+}
+
+Expected<void> BackendManifest::verify() const {
+ if (SchemaVersion != BackendManifestSchemaVersion) {
+ return makeUnexpected(ErrorCode::ManifestError, "manifest schema version is unsupported");
+ }
+ BackendInvocation Canonical = Invocation;
+ auto InvocationVerification = Canonical.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ if (Canonical != Invocation) {
+ return makeUnexpected(ErrorCode::ManifestError, "manifest invocation is not in canonical form");
+ }
+ if (!isDigest(InputMIRHash) || !isDigest(TargetFingerprint) || !isDigest(CacheKey) ||
+ (ArtifactHash && !isDigest(*ArtifactHash))) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest hashes must be lowercase SHA-256 digests");
+ }
+ for (const StructuredDiagnostic &Diagnostic : Diagnostics) {
+ if (Diagnostic.Category.empty() || Diagnostic.Message.empty()) {
+ return makeUnexpected(ErrorCode::ManifestError,
+ "manifest diagnostic category and message cannot be empty");
+ }
+ }
+ return {};
+}
+
+Expected<std::string> printBackendManifest(const BackendManifest &Manifest) {
+ auto Verification = Manifest.verify();
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ std::string Output;
+ Output.append("---\n");
+ appendInteger(Output, "", "schema", Manifest.SchemaVersion);
+ appendScalar(Output, "", "kind", spelling(Manifest.Kind));
+ appendScalar(Output, "", "artifact", spelling(Manifest.Artifact));
+ appendScalar(Output, "", "input_mir_hash", Manifest.InputMIRHash);
+ appendScalar(Output, "", "target_fingerprint", Manifest.TargetFingerprint);
+ appendScalar(Output, "", "cache_key", Manifest.CacheKey);
+ if (Manifest.ArtifactHash) {
+ appendScalar(Output, "", "artifact_hash", *Manifest.ArtifactHash);
+ } else {
+ Output.append("artifact_hash: null\n");
+ }
+ Output.append("invocation:\n");
+ appendInvocation(Output, Manifest.Invocation);
+ if (Manifest.Diagnostics.empty()) {
+ Output.append("diagnostics: []\n");
+ return Output;
+ }
+ Output.append("diagnostics:\n");
+ for (const StructuredDiagnostic &Diagnostic : Manifest.Diagnostics) {
+ Output.append(" - category: ");
+ Output.append(quoted(Diagnostic.Category));
+ Output.push_back('\n');
+ appendScalar(Output, " ", "stage", Diagnostic.Stage);
+ appendScalar(Output, " ", "pass", Diagnostic.Pass);
+ appendScalar(Output, " ", "function", Diagnostic.Function);
+ appendOptionalInteger(Output, " ", "block", Diagnostic.Block);
+ appendOptionalInteger(Output, " ", "instruction", Diagnostic.Instruction);
+ if (Diagnostic.Operand) {
+ appendInteger(Output, " ", "operand", *Diagnostic.Operand);
+ } else {
+ Output.append(" operand: null\n");
+ }
+ appendScalar(Output, " ", "source_location", Diagnostic.SourceLocation);
+ appendScalar(Output, " ", "target_constraint", Diagnostic.TargetConstraint);
+ appendScalar(Output, " ", "rule", Diagnostic.Rule);
+ appendScalar(Output, " ", "message", Diagnostic.Message);
+ }
+ return Output;
+}
+
+Expected<BackendManifest> parseBackendManifest(std::string SourceName, std::string SourceText) {
+ return ManifestParser(std::move(SourceName), std::move(SourceText)).run();
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/CMakeLists.txt b/backend/lib/Tooling/CMakeLists.txt
new file mode 100644
index 0000000..bf20e37
--- /dev/null
+++ b/backend/lib/Tooling/CMakeLists.txt
@@ -0,0 +1,76 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(
+ RCCBackendToolingSources
+ BackendInvocation.cpp
+ BackendManifest.cpp
+ BackendDriver.cpp
+ ArtifactStore.cpp
+ MIRFuzzer.cpp
+ MIRReducer.cpp
+ PipelineDriver.cpp
+)
+set(
+ RCCBackendToolingHeaders
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/BackendInvocation.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/BackendManifest.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/BackendDriver.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/ArtifactStore.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/MIRFuzzer.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/MIRReducer.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Tooling/PipelineDriver.h"
+)
+
+add_library(RCCBackendTooling ${RCCBackendToolingSources})
+add_library(RCCBackend::Tooling ALIAS RCCBackendTooling)
+
+rcc_backend_configure_target(RCCBackendTooling)
+
+target_include_directories(
+ RCCBackendTooling
+ PUBLIC
+ "$<BUILD_INTERFACE:${RCC_BACKEND_SOURCE_DIR}/include>"
+ "$<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}>"
+)
+target_link_libraries(
+ RCCBackendTooling
+ PUBLIC
+ RCCBackend::MIR
+ RCCBackend::RISCV
+ RCCBackend::Support
+)
+
+set_target_properties(
+ RCCBackendTooling
+ PROPERTIES
+ EXPORT_NAME Tooling
+ OUTPUT_NAME RCCBackendTooling
+)
+
+install(
+ TARGETS RCCBackendTooling
+ EXPORT RCCBackendTargets
+ ARCHIVE DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ LIBRARY DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ RUNTIME DESTINATION "${CMAKE_INSTALL_BINDIR}"
+)
+
+rcc_backend_register_format_files(
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendInvocation.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendManifest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendDriver.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/ArtifactStore.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MIRFuzzer.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MIRReducer.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/PipelineDriver.cpp"
+ ${RCCBackendToolingHeaders}
+)
+rcc_backend_register_tidy_files(
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendInvocation.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendManifest.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/BackendDriver.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/ArtifactStore.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MIRFuzzer.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/MIRReducer.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/PipelineDriver.cpp"
+)
diff --git a/backend/lib/Tooling/MIRFuzzer.cpp b/backend/lib/Tooling/MIRFuzzer.cpp
new file mode 100644
index 0000000..e8a1a7a
--- /dev/null
+++ b/backend/lib/Tooling/MIRFuzzer.cpp
@@ -0,0 +1,613 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/MIRFuzzer.h"
+
+#include "rcc/CodeGen/GenericOpcodes.h"
+#include "rcc/CodeGen/InstructionDescriptor.h"
+#include "rcc/CodeGen/LowLevelType.h"
+#include "rcc/CodeGen/MachineBasicBlock.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineIRBuilder.h"
+#include "rcc/CodeGen/MachineInstr.h"
+#include "rcc/CodeGen/MachineOperand.h"
+#include "rcc/CodeGen/MachineRegisterInfo.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Target/RISCV/RISCVPipeline.h"
+#include "rcc/Tooling/ArtifactStore.h"
+#include "rcc/Tooling/BackendDriver.h"
+
+#include <algorithm>
+#include <array>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <string_view>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+class DeterministicRandom final {
+public:
+ explicit DeterministicRandom(std::uint64_t Seed) noexcept
+ : State(Seed == 0 ? 0x243f6a8885a308d3ULL : Seed) {}
+
+ [[nodiscard]] std::uint64_t next() noexcept {
+ State ^= State >> 12U;
+ State ^= State << 25U;
+ State ^= State >> 27U;
+ return State * 0x2545f4914f6cdd1dULL;
+ }
+
+ [[nodiscard]] std::size_t index(std::size_t Bound) noexcept {
+ return Bound == 0 ? 0 : static_cast<std::size_t>(next() % Bound);
+ }
+
+private:
+ std::uint64_t State;
+};
+
+[[nodiscard]] std::vector<MIRFuzzLayer> defaultLayers() {
+ return {
+ MIRFuzzLayer::Parser, MIRFuzzLayer::BuilderStructural, MIRFuzzLayer::PropertyStage,
+ MIRFuzzLayer::Mutation, MIRFuzzLayer::Pipeline, MIRFuzzLayer::RestrictedSemantics,
+ };
+}
+
+[[nodiscard]] Error fuzzFailure(MIRFuzzLayer Layer, std::size_t Iteration, const Error &Failure) {
+ return Error(ErrorCode::FuzzingFailure,
+ std::string(spelling(Layer)) + " fuzz case " + std::to_string(Iteration) +
+ " violated an invariant: " + std::string(Failure.message()));
+}
+
+[[nodiscard]] std::string byteMutation(std::string_view Input, DeterministicRandom &Random,
+ std::size_t MaximumSize) {
+ std::string Result(Input);
+ switch (Random.index(5)) {
+ case 0:
+ if (!Result.empty())
+ Result[Random.index(Result.size())] = static_cast<char>(Random.next() & 0xffU);
+ break;
+ case 1:
+ if (!Result.empty())
+ Result.erase(Random.index(Result.size()), 1);
+ break;
+ case 2:
+ if (Result.size() < MaximumSize)
+ Result.insert(Result.begin() + static_cast<std::ptrdiff_t>(Random.index(Result.size() + 1U)),
+ static_cast<char>(Random.next() & 0xffU));
+ break;
+ case 3:
+ if (!Result.empty())
+ Result.resize(Random.index(Result.size()));
+ break;
+ case 4:
+ if (!Result.empty() && Result.size() < MaximumSize) {
+ const std::size_t Begin = Random.index(Result.size());
+ const std::size_t Length = std::min(Random.index(32U) + 1U, Result.size() - Begin);
+ const std::string Fragment = Result.substr(Begin, Length);
+ const std::size_t Available = MaximumSize - Result.size();
+ Result.append(Fragment.substr(0, Available));
+ }
+ break;
+ default:
+ break;
+ }
+ return Result;
+}
+
+[[nodiscard]] std::string structuralTextMutation(std::string_view Input,
+ DeterministicRandom &Random) {
+ std::string Result(Input);
+ std::vector<std::size_t> LineStarts{0};
+ for (std::size_t Position = 0; Position < Result.size(); ++Position) {
+ if (Result[Position] == '\n' && Position + 1U < Result.size())
+ LineStarts.push_back(Position + 1U);
+ }
+ if (LineStarts.empty())
+ return Result;
+ const std::size_t LineIndex = Random.index(LineStarts.size());
+ const std::size_t Begin = LineStarts[LineIndex];
+ const std::size_t End = Result.find('\n', Begin);
+ const std::size_t LineEnd = End == std::string::npos ? Result.size() : End + 1U;
+ switch (Random.index(4)) {
+ case 0:
+ Result.erase(Begin, LineEnd - Begin);
+ break;
+ case 1:
+ Result.insert(LineEnd, Result.substr(Begin, LineEnd - Begin));
+ break;
+ case 2: {
+ const std::size_t Digit = Result.find_first_of("0123456789", Begin);
+ if (Digit < LineEnd)
+ Result[Digit] = static_cast<char>('0' + Random.index(10));
+ break;
+ }
+ case 3: {
+ const std::size_t Percent = Result.find('%', Begin);
+ if (Percent < LineEnd && Percent + 1U < Result.size())
+ Result[Percent + 1U] = static_cast<char>('0' + Random.index(10));
+ break;
+ }
+ default:
+ break;
+ }
+ return Result;
+}
+
+[[nodiscard]] Expected<void> verifyCanonicalRoundTrip(std::string Text,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ auto First = parseAndCanonicalizeMIR("fuzz-round-trip.mir", std::move(Text), Target, Invocation);
+ if (!First)
+ return std::unexpected(First.error());
+ auto Second = parseAndCanonicalizeMIR("fuzz-round-trip-2.mir", First->Text, Target, Invocation);
+ if (!Second)
+ return std::unexpected(Second.error());
+ if (First->Text != Second->Text) {
+ return makeUnexpected(ErrorCode::FuzzingFailure,
+ "successful MIR round-trip is not structurally deterministic");
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<bool> parserCase(std::string_view Canonical, DeterministicRandom &Random,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation,
+ std::size_t MaximumSize) {
+ std::string Mutated = byteMutation(Canonical, Random, MaximumSize);
+ auto Parsed = parseAndCanonicalizeMIR("parser-fuzz.mir", Mutated, Target, Invocation);
+ if (!Parsed)
+ return false;
+ auto RoundTrip = verifyCanonicalRoundTrip(std::move(Parsed->Text), Target, Invocation);
+ if (!RoundTrip)
+ return std::unexpected(RoundTrip.error());
+ return true;
+}
+
+[[nodiscard]] Expected<bool> builderCase(std::string_view Canonical,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ auto Parsed =
+ parseAndCanonicalizeMIR("builder-fuzz.mir", std::string(Canonical), Target, Invocation);
+ if (!Parsed)
+ return std::unexpected(Parsed.error());
+ MachineFunction *Function = Parsed->Document.unit().functionAt(0);
+ if (Function == nullptr || stageForFunction(*Function) != BackendStage::PreLegalizerMIR)
+ return false;
+ MachineBasicBlock *Block = Function->firstBlock();
+ if (Block == nullptr)
+ return false;
+ auto Type = LLT::makeInteger(64);
+ if (!Type)
+ return std::unexpected(Type.error());
+ auto Register = Function->registerInfo().createVirtualRegister(*Type);
+ if (!Register)
+ return std::unexpected(Register.error());
+ MachineIRBuilder Builder(*Function, Target);
+ Expected<void> InsertPoint = Block->firstInstruction() == nullptr
+ ? Builder.setInsertPoint(*Block)
+ : Builder.setInsertPointBefore(*Block->firstInstruction());
+ if (!InsertPoint)
+ return std::unexpected(InsertPoint.error());
+ auto Pending = Builder.buildInstr(opcode(GenericOpcode::G_IMPLICIT_DEF));
+ if (!Pending)
+ return std::unexpected(Pending.error());
+ auto Added = Pending->addDef(*Register);
+ if (!Added)
+ return std::unexpected(Added.error());
+ auto Built = Pending->build();
+ if (!Built)
+ return std::unexpected(Built.error());
+ auto Verified = MachineVerifier::verify(*Function, Target);
+ if (!Verified)
+ return std::unexpected(Verified.error());
+
+ mir::MIRDocumentPrinterOptions PrintOptions;
+ PrintOptions.Mode = mir::MIPrintMode::Complete;
+ PrintOptions.EmitEmbeddedIR = true;
+ PrintOptions.DataLayout = Invocation.DataLayout;
+ PrintOptions.DefaultPointerSizeInBits = 64;
+ auto Printed = mir::printMIRDocument(Parsed->Document, Target, std::move(PrintOptions));
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ auto RoundTrip = verifyCanonicalRoundTrip(std::move(*Printed), Target, Invocation);
+ if (!RoundTrip)
+ return std::unexpected(RoundTrip.error());
+ return true;
+}
+
+[[nodiscard]] BackendOutputKind outputForStage(BackendStage Stage) noexcept {
+ return static_cast<BackendOutputKind>(static_cast<std::uint8_t>(Stage));
+}
+
+[[nodiscard]] Expected<bool> propertyCase(std::string_view Canonical, DeterministicRandom &Random,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ auto Parsed =
+ parseAndCanonicalizeMIR("property-fuzz.mir", std::string(Canonical), Target, Invocation);
+ if (!Parsed)
+ return std::unexpected(Parsed.error());
+ const auto Stage = static_cast<BackendStage>(Random.index(7U));
+ const MachineFunction *Function = Parsed->Document.unit().functionAt(0);
+ if (Function == nullptr ||
+ static_cast<std::uint8_t>(Stage) < static_cast<std::uint8_t>(stageForFunction(*Function))) {
+ return false;
+ }
+ auto Run = runBackend(std::move(*Parsed), Target, Invocation, outputForStage(Stage));
+ if (!Run)
+ return std::unexpected(Run.error());
+ auto RoundTrip = verifyCanonicalRoundTrip(std::string(Run->text()), Target, Invocation);
+ if (!RoundTrip)
+ return std::unexpected(RoundTrip.error());
+ return true;
+}
+
+[[nodiscard]] Expected<bool> mutationCase(std::string_view Canonical, DeterministicRandom &Random,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ std::string Mutated = structuralTextMutation(Canonical, Random);
+ auto Parsed =
+ parseAndCanonicalizeMIR("mutation-fuzz.mir", std::move(Mutated), Target, Invocation);
+ if (!Parsed)
+ return false;
+ auto RoundTrip = verifyCanonicalRoundTrip(std::move(Parsed->Text), Target, Invocation);
+ if (!RoundTrip)
+ return std::unexpected(RoundTrip.error());
+ return true;
+}
+
+[[nodiscard]] Expected<bool> pipelineCase(std::string_view Canonical, DeterministicRandom &Random,
+ const TargetDescription &Target,
+ BackendInvocation Invocation) {
+ auto Parsed =
+ parseAndCanonicalizeMIR("pipeline-fuzz.mir", std::string(Canonical), Target, Invocation);
+ if (!Parsed)
+ return std::unexpected(Parsed.error());
+ const MachineFunction *Function = Parsed->Document.unit().functionAt(0);
+ if (Function == nullptr)
+ return std::unexpected(Error(ErrorCode::InternalError, "pipeline fuzz input has no function"));
+ auto Names = riscv::canonicalPipelinePassNames(*Function);
+ if (!Names)
+ return std::unexpected(Names.error());
+ PipelineControls Controls;
+ if (!Names->empty())
+ Controls.StopAfter = (*Names)[Random.index(Names->size())];
+ Controls.VerifyEach = true;
+ Controls.DetectUnreportedChanges = true;
+ Invocation.Determinism.ThreadCount = std::array<std::uint32_t, 3>{1, 2, 4}[Random.index(3U)];
+ const std::string Stop = Controls.StopAfter ? *Controls.StopAfter : "end";
+ auto Run =
+ runBackend(std::move(*Parsed), Target, Invocation, BackendOutputKind::FinalMIR, Controls);
+ if (!Run)
+ return std::unexpected(Run.error());
+ auto RoundTrip = verifyCanonicalRoundTrip(std::string(Run->text()), Target, Invocation);
+ if (!RoundTrip) {
+ return std::unexpected(
+ Error(RoundTrip.error().code(),
+ "pipeline stop-after '" + Stop + "': " + std::string(RoundTrip.error().message())));
+ }
+ return true;
+}
+
+using RegisterValues = std::unordered_map<std::uint64_t, std::uint64_t>;
+
+[[nodiscard]] Expected<Register> registerAt(const MachineInstr &Instruction, std::size_t Index) {
+ const MachineOperand *Operand = Instruction.operandAt(Index);
+ if (Operand == nullptr)
+ return makeUnexpected(ErrorCode::Unsupported, "semantic subset requires register operands");
+ const std::optional<Register> Reg = Operand->registerValue();
+ if (!Reg)
+ return makeUnexpected(ErrorCode::Unsupported, "semantic subset requires register operands");
+ return *Reg;
+}
+
+[[nodiscard]] Expected<std::uint64_t> immediateAt(const MachineInstr &Instruction,
+ std::size_t Index) {
+ const MachineOperand *Operand = Instruction.operandAt(Index);
+ if (Operand == nullptr)
+ return makeUnexpected(ErrorCode::Unsupported, "semantic subset requires an immediate operand");
+ if (const auto *Immediate = Operand->getIf<std::int64_t>())
+ return static_cast<std::uint64_t>(*Immediate);
+ if (const auto *Immediate = Operand->getIf<IntegerImmediateOperand>()) {
+ if (Immediate->Value.bitWidth() > 64 || Immediate->Value.words().empty())
+ return makeUnexpected(ErrorCode::Unsupported,
+ "semantic subset only supports integer immediates up to 64 bits");
+ return Immediate->Value.words().front();
+ }
+ return makeUnexpected(ErrorCode::Unsupported, "semantic subset requires an integer immediate");
+}
+
+[[nodiscard]] std::uint64_t readRegister(Register Reg, const RegisterValues &Values,
+ PhysicalRegister Zero) noexcept {
+ if (Reg.physicalRegister() == Zero)
+ return 0;
+ const auto Position = Values.find(Reg.opaqueValue());
+ return Position == Values.end() ? 0 : Position->second;
+}
+
+[[nodiscard]] Expected<std::uint64_t> interpretStraightLine(const MachineFunction &Function,
+ const TargetDescription &Target) {
+ if (Function.blockCount() != 1 || Function.firstBlock() == nullptr ||
+ !Function.firstBlock()->successors().empty()) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "semantic subset requires one straight-line basic block");
+ }
+ const PhysicalRegisterDesc *ZeroDescription = Target.registers().physicalRegister("x0");
+ const PhysicalRegisterDesc *ReturnDescription = Target.registers().physicalRegister("x10");
+ if (ZeroDescription == nullptr || ReturnDescription == nullptr)
+ return makeUnexpected(ErrorCode::Unsupported,
+ "semantic subset requires RV64 integer registers");
+ const PhysicalRegister Zero = ZeroDescription->Reg;
+ const Register Return = Register::fromPhysical(ReturnDescription->Reg);
+ RegisterValues Values;
+
+ for (const MachineInstr *Instruction = Function.firstBlock()->firstInstruction();
+ Instruction != nullptr; Instruction = Instruction->next()) {
+ const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode());
+ if (Descriptor == nullptr)
+ return makeUnexpected(ErrorCode::Unsupported,
+ "semantic subset encountered an unknown opcode");
+ const std::string_view Name = Descriptor->Name;
+ if (Name == "PseudoRET" || Name == "JALR_RET")
+ return readRegister(Return, Values, Zero);
+
+ if (Name == "G_CONSTANT") {
+ auto Destination = registerAt(*Instruction, 0);
+ auto Immediate = immediateAt(*Instruction, 1);
+ if (!Destination || !Immediate)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported generic constant form");
+ Values[Destination->opaqueValue()] = *Immediate;
+ continue;
+ }
+ if (Name == "COPY") {
+ auto Destination = registerAt(*Instruction, 0);
+ auto Source = registerAt(*Instruction, 1);
+ if (!Destination || !Source)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported copy form");
+ Values[Destination->opaqueValue()] = readRegister(*Source, Values, Zero);
+ continue;
+ }
+ if (Name == "LUI") {
+ auto Destination = registerAt(*Instruction, 0);
+ auto Immediate = immediateAt(*Instruction, 1);
+ if (!Destination || !Immediate)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported LUI form");
+ Values[Destination->opaqueValue()] = *Immediate << 12U;
+ continue;
+ }
+
+ const bool ImmediateForm = Name == "ADDI" || Name == "XORI" || Name == "ORI" ||
+ Name == "ANDI" || Name == "SLLI" || Name == "SRLI" || Name == "SRAI";
+ const bool RegisterForm =
+ Name == "G_ADD" || Name == "G_SUB" || Name == "G_MUL" || Name == "G_AND" ||
+ Name == "G_OR" || Name == "G_XOR" || Name == "G_SHL" || Name == "G_LSHR" ||
+ Name == "G_ASHR" || Name == "ADD" || Name == "SUB" || Name == "MUL" || Name == "AND" ||
+ Name == "OR" || Name == "XOR" || Name == "SLL" || Name == "SRL" || Name == "SRA";
+ if (!ImmediateForm && !RegisterForm && !Descriptor->Flags.has(InstructionFlag::ProducesCode)) {
+ continue;
+ }
+ if (!ImmediateForm && !RegisterForm) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "semantic subset does not model opcode '" + std::string(Name) + "'");
+ }
+ auto Destination = registerAt(*Instruction, 0);
+ auto LeftRegister = registerAt(*Instruction, 1);
+ if (!Destination || !LeftRegister)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported binary instruction form");
+ const std::uint64_t Left = readRegister(*LeftRegister, Values, Zero);
+ std::uint64_t Right = 0;
+ if (ImmediateForm) {
+ auto Immediate = immediateAt(*Instruction, 2);
+ if (!Immediate)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported immediate instruction form");
+ Right = *Immediate;
+ } else {
+ auto RightRegister = registerAt(*Instruction, 2);
+ if (!RightRegister)
+ return makeUnexpected(ErrorCode::Unsupported, "unsupported register instruction form");
+ Right = readRegister(*RightRegister, Values, Zero);
+ }
+ std::uint64_t Value = 0;
+ if (Name == "G_ADD" || Name == "ADD" || Name == "ADDI")
+ Value = Left + Right;
+ else if (Name == "G_SUB" || Name == "SUB")
+ Value = Left - Right;
+ else if (Name == "G_MUL" || Name == "MUL")
+ Value = Left * Right;
+ else if (Name == "G_AND" || Name == "AND" || Name == "ANDI")
+ Value = Left & Right;
+ else if (Name == "G_OR" || Name == "OR" || Name == "ORI")
+ Value = Left | Right;
+ else if (Name == "G_XOR" || Name == "XOR" || Name == "XORI")
+ Value = Left ^ Right;
+ else if (Name == "G_SHL" || Name == "SLL" || Name == "SLLI")
+ Value = Left << (Right & 63U);
+ else if (Name == "G_LSHR" || Name == "SRL" || Name == "SRLI")
+ Value = Left >> (Right & 63U);
+ else
+ Value = static_cast<std::uint64_t>(std::bit_cast<std::int64_t>(Left) >> (Right & 63U));
+ Values[Destination->opaqueValue()] = Value;
+ }
+ return makeUnexpected(ErrorCode::Unsupported, "semantic subset did not encounter a return");
+}
+
+[[nodiscard]] Expected<bool> semanticCase(std::string_view Canonical,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation) {
+ auto Original =
+ parseAndCanonicalizeMIR("semantic-input.mir", std::string(Canonical), Target, Invocation);
+ if (!Original)
+ return std::unexpected(Original.error());
+ const MachineFunction *InputFunction = Original->Document.unit().functionAt(0);
+ if (InputFunction == nullptr)
+ return std::unexpected(Error(ErrorCode::InternalError, "semantic fuzz input has no function"));
+ auto ExpectedValue = interpretStraightLine(*InputFunction, Target);
+ if (!ExpectedValue && ExpectedValue.error().code() == ErrorCode::Unsupported)
+ return false;
+ if (!ExpectedValue)
+ return std::unexpected(ExpectedValue.error());
+
+ auto CompiledInput =
+ parseAndCanonicalizeMIR("semantic-pipeline.mir", std::string(Canonical), Target, Invocation);
+ if (!CompiledInput)
+ return std::unexpected(CompiledInput.error());
+ auto Compiled =
+ runBackend(std::move(*CompiledInput), Target, Invocation, BackendOutputKind::FinalMIR);
+ if (!Compiled)
+ return std::unexpected(Compiled.error());
+ auto Final = parseAndCanonicalizeMIR("semantic-final.mir", std::string(Compiled->text()), Target,
+ Invocation);
+ if (!Final)
+ return std::unexpected(Final.error());
+ const MachineFunction *FinalFunction = Final->Document.unit().functionAt(0);
+ if (FinalFunction == nullptr)
+ return std::unexpected(Error(ErrorCode::InternalError, "semantic final MIR has no function"));
+ auto ActualValue = interpretStraightLine(*FinalFunction, Target);
+ if (!ActualValue && ActualValue.error().code() == ErrorCode::Unsupported)
+ return false;
+ if (!ActualValue)
+ return std::unexpected(ActualValue.error());
+ if (*ExpectedValue != *ActualValue) {
+ return makeUnexpected(ErrorCode::FuzzingFailure,
+ "restricted semantic comparison changed the integer return value from " +
+ std::to_string(*ExpectedValue) + " to " +
+ std::to_string(*ActualValue));
+ }
+ return true;
+}
+
+} // namespace
+
+std::size_t MIRFuzzResult::executed() const noexcept {
+ std::size_t Result = 0;
+ for (const MIRFuzzLayerResult &Layer : Layers)
+ Result += Layer.Executed;
+ return Result;
+}
+
+std::size_t MIRFuzzResult::accepted() const noexcept {
+ std::size_t Result = 0;
+ for (const MIRFuzzLayerResult &Layer : Layers)
+ Result += Layer.Accepted;
+ return Result;
+}
+
+std::size_t MIRFuzzResult::rejected() const noexcept {
+ std::size_t Result = 0;
+ for (const MIRFuzzLayerResult &Layer : Layers)
+ Result += Layer.Rejected;
+ return Result;
+}
+
+Expected<MIRFuzzResult> fuzzMIR(std::string SourceName, std::string SourceText,
+ BackendInvocation Invocation, const TargetDescription &Target,
+ MIRFuzzOptions Options) {
+ if (Options.Iterations == 0 || Options.MaximumInputSize == 0) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "MIR fuzzing requires nonzero iteration and input-size limits");
+ }
+ if (std::ranges::any_of(Options.Layers,
+ [](MIRFuzzLayer Layer) { return spelling(Layer) == "invalid"; })) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "MIR fuzz layer is not recognized");
+ }
+ auto InvocationVerification = Invocation.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ auto Input =
+ parseAndCanonicalizeMIR(std::move(SourceName), std::move(SourceText), Target, Invocation);
+ if (!Input)
+ return std::unexpected(Input.error());
+ if (Input->Text.size() > Options.MaximumInputSize)
+ return makeUnexpected(ErrorCode::InvalidArgument, "MIR fuzz seed exceeds the input-size limit");
+ if (Options.Layers.empty())
+ Options.Layers = defaultLayers();
+ std::ranges::sort(Options.Layers);
+ if (std::ranges::adjacent_find(Options.Layers) != Options.Layers.end()) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "MIR fuzz layers must be unique");
+ }
+
+ MIRFuzzResult Result{.Seed = Options.Seed, .Layers = {}};
+ DeterministicRandom Random(Options.Seed);
+ for (MIRFuzzLayer Layer : Options.Layers) {
+ MIRFuzzLayerResult LayerResult{.Layer = Layer};
+ const std::size_t Iterations =
+ Layer == MIRFuzzLayer::RestrictedSemantics ? 1U : Options.Iterations;
+ for (std::size_t Iteration = 0; Iteration < Iterations; ++Iteration) {
+ ++LayerResult.Executed;
+ Expected<bool> Case = false;
+ switch (Layer) {
+ case MIRFuzzLayer::Parser:
+ Case = parserCase(Input->Text, Random, Target, Invocation, Options.MaximumInputSize);
+ break;
+ case MIRFuzzLayer::BuilderStructural:
+ Case = builderCase(Input->Text, Target, Invocation);
+ break;
+ case MIRFuzzLayer::PropertyStage:
+ Case = propertyCase(Input->Text, Random, Target, Invocation);
+ break;
+ case MIRFuzzLayer::Mutation:
+ Case = mutationCase(Input->Text, Random, Target, Invocation);
+ break;
+ case MIRFuzzLayer::Pipeline:
+ Case = pipelineCase(Input->Text, Random, Target, Invocation);
+ break;
+ case MIRFuzzLayer::RestrictedSemantics:
+ Case = semanticCase(Input->Text, Target, Invocation);
+ break;
+ }
+ if (!Case)
+ return std::unexpected(fuzzFailure(Layer, Iteration, Case.error()));
+ if (*Case)
+ ++LayerResult.Accepted;
+ else
+ ++LayerResult.Rejected;
+ }
+ Result.Layers.push_back(LayerResult);
+ }
+ return Result;
+}
+
+std::string_view spelling(MIRFuzzLayer Layer) noexcept {
+ switch (Layer) {
+ case MIRFuzzLayer::Parser:
+ return "parser";
+ case MIRFuzzLayer::BuilderStructural:
+ return "builder";
+ case MIRFuzzLayer::PropertyStage:
+ return "property-stage";
+ case MIRFuzzLayer::Mutation:
+ return "mutation";
+ case MIRFuzzLayer::Pipeline:
+ return "pipeline";
+ case MIRFuzzLayer::RestrictedSemantics:
+ return "semantics";
+ }
+ return "invalid";
+}
+
+Expected<MIRFuzzLayer> parseMIRFuzzLayer(std::string_view Value) {
+ if (Value == "parser")
+ return MIRFuzzLayer::Parser;
+ if (Value == "builder")
+ return MIRFuzzLayer::BuilderStructural;
+ if (Value == "property-stage")
+ return MIRFuzzLayer::PropertyStage;
+ if (Value == "mutation")
+ return MIRFuzzLayer::Mutation;
+ if (Value == "pipeline")
+ return MIRFuzzLayer::Pipeline;
+ if (Value == "semantics")
+ return MIRFuzzLayer::RestrictedSemantics;
+ return makeUnexpected(ErrorCode::InvalidInvocation, "unknown MIR fuzz layer");
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/MIRReducer.cpp b/backend/lib/Tooling/MIRReducer.cpp
new file mode 100644
index 0000000..a247584
--- /dev/null
+++ b/backend/lib/Tooling/MIRReducer.cpp
@@ -0,0 +1,534 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/MIRReducer.h"
+
+#include "rcc/CodeGen/TargetDescription.h"
+#include "rcc/Tooling/ArtifactStore.h"
+
+#include <algorithm>
+#include <cctype>
+#include <cstddef>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <set>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+struct Line final {
+ std::size_t Begin = 0;
+ std::size_t End = 0;
+ std::size_t ContentEnd = 0;
+ std::size_t Indent = 0;
+};
+
+struct Candidate final {
+ std::string MIR;
+ BackendInvocation Invocation;
+ std::string Description;
+};
+
+[[nodiscard]] std::vector<ReductionGranularity> defaultGranularities() {
+ return {
+ ReductionGranularity::MachineFunction, ReductionGranularity::BasicBlock,
+ ReductionGranularity::CFGEdge, ReductionGranularity::RegisterSubgraph,
+ ReductionGranularity::Instruction, ReductionGranularity::Operand,
+ ReductionGranularity::FrameObject, ReductionGranularity::ConstantPool,
+ ReductionGranularity::JumpTable, ReductionGranularity::TargetFeature,
+ ReductionGranularity::PassPipeline,
+ };
+}
+
+[[nodiscard]] std::vector<Line> lines(std::string_view Text) {
+ std::vector<Line> Result;
+ std::size_t Begin = 0;
+ while (Begin < Text.size()) {
+ const std::size_t Newline = Text.find('\n', Begin);
+ const std::size_t End = Newline == std::string_view::npos ? Text.size() : Newline + 1U;
+ std::size_t ContentEnd = Newline == std::string_view::npos ? Text.size() : Newline;
+ if (ContentEnd > Begin && Text[ContentEnd - 1U] == '\r')
+ --ContentEnd;
+ std::size_t Indent = 0;
+ while (Begin + Indent < ContentEnd && Text[Begin + Indent] == ' ')
+ ++Indent;
+ Result.push_back({Begin, End, ContentEnd, Indent});
+ Begin = End;
+ }
+ if (Text.empty())
+ Result.push_back({});
+ return Result;
+}
+
+[[nodiscard]] std::string_view lineText(std::string_view Text, const Line &Value) {
+ return Text.substr(Value.Begin, Value.ContentEnd - Value.Begin);
+}
+
+[[nodiscard]] std::string_view trimmedLine(std::string_view Text, const Line &Value) {
+ return Text.substr(Value.Begin + Value.Indent, Value.ContentEnd - Value.Begin - Value.Indent);
+}
+
+[[nodiscard]] std::string withoutRange(std::string_view Text, std::size_t Begin, std::size_t End) {
+ std::string Result;
+ Result.reserve(Text.size() - (End - Begin));
+ Result.append(Text.substr(0, Begin));
+ Result.append(Text.substr(End));
+ return Result;
+}
+
+void addCandidate(std::vector<Candidate> &Result, std::set<std::string> &Seen,
+ std::string CandidateMIR, const BackendInvocation &Invocation,
+ std::string Description, std::string_view OriginalMIR) {
+ if (CandidateMIR == OriginalMIR || !Seen.insert(CandidateMIR).second)
+ return;
+ Result.push_back({std::move(CandidateMIR), Invocation, std::move(Description)});
+}
+
+[[nodiscard]] bool isBodyStart(std::string_view Text, const Line &Value) {
+ return Value.Indent == 0 && trimmedLine(Text, Value) == "body: |";
+}
+
+[[nodiscard]] bool isBlockLabel(std::string_view Text, const Line &Value) {
+ const std::string_view Trimmed = trimmedLine(Text, Value);
+ return Value.Indent == 2 && Trimmed.starts_with("bb.") && Trimmed.ends_with(':');
+}
+
+[[nodiscard]] bool isInstructionLine(std::string_view Text, const Line &Value, bool InBody) {
+ if (!InBody || Value.Indent < 4)
+ return false;
+ const std::string_view Trimmed = trimmedLine(Text, Value);
+ return !Trimmed.empty() && !Trimmed.starts_with("liveins:") &&
+ !Trimmed.starts_with("successors:") && !Trimmed.starts_with("align ") &&
+ !Trimmed.starts_with(';');
+}
+
+[[nodiscard]] std::vector<Candidate> functionCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<std::size_t> Starts;
+ for (std::size_t Index = 0; Index < Lines.size(); ++Index) {
+ if (lineText(MIR, Lines[Index]) == "---")
+ Starts.push_back(Index);
+ }
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ if (Starts.size() <= 1)
+ return Result;
+ for (std::size_t Position = 0; Position < Starts.size(); ++Position) {
+ const std::size_t Begin = Lines[Starts[Position]].Begin;
+ const std::size_t End =
+ Position + 1U < Starts.size() ? Lines[Starts[Position + 1U]].Begin : MIR.size();
+ addCandidate(Result, Seen, withoutRange(MIR, Begin, End), Invocation,
+ "remove YAML document " + std::to_string(Position), MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> blockCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ bool InBody = false;
+ for (std::size_t Index = 0; Index < Lines.size(); ++Index) {
+ if (isBodyStart(MIR, Lines[Index])) {
+ InBody = true;
+ continue;
+ }
+ if (InBody && Lines[Index].Indent == 0) {
+ InBody = isBodyStart(MIR, Lines[Index]);
+ continue;
+ }
+ if (!InBody || !isBlockLabel(MIR, Lines[Index]))
+ continue;
+ std::size_t EndIndex = Index + 1U;
+ while (EndIndex < Lines.size() && Lines[EndIndex].Indent != 0 &&
+ !isBlockLabel(MIR, Lines[EndIndex])) {
+ ++EndIndex;
+ }
+ const std::size_t End = EndIndex < Lines.size() ? Lines[EndIndex].Begin : MIR.size();
+ addCandidate(Result, Seen, withoutRange(MIR, Lines[Index].Begin, End), Invocation,
+ "remove machine basic block", MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> instructionCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ bool InBody = false;
+ for (const Line &Value : Lines) {
+ if (isBodyStart(MIR, Value)) {
+ InBody = true;
+ continue;
+ }
+ if (InBody && Value.Indent == 0) {
+ InBody = false;
+ continue;
+ }
+ if (!isInstructionLine(MIR, Value, InBody))
+ continue;
+ addCandidate(Result, Seen, withoutRange(MIR, Value.Begin, Value.End), Invocation,
+ "remove machine instruction", MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> cfgEdgeCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ bool InBody = false;
+ for (const Line &Value : Lines) {
+ if (isBodyStart(MIR, Value)) {
+ InBody = true;
+ continue;
+ }
+ if (InBody && Value.Indent == 0) {
+ InBody = false;
+ continue;
+ }
+ const std::string_view Trimmed = trimmedLine(MIR, Value);
+ if (!InBody || !Trimmed.starts_with("successors:"))
+ continue;
+ const std::size_t LastComma = Trimmed.rfind(',');
+ if (LastComma == std::string_view::npos) {
+ addCandidate(Result, Seen, withoutRange(MIR, Value.Begin, Value.End), Invocation,
+ "remove CFG successor list", MIR);
+ continue;
+ }
+ const std::size_t EraseBegin = Value.Begin + Value.Indent + LastComma;
+ addCandidate(Result, Seen, withoutRange(MIR, EraseBegin, Value.ContentEnd), Invocation,
+ "remove CFG successor", MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> operandCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ bool InBody = false;
+ for (const Line &Value : Lines) {
+ if (isBodyStart(MIR, Value)) {
+ InBody = true;
+ continue;
+ }
+ if (InBody && Value.Indent == 0) {
+ InBody = false;
+ continue;
+ }
+ if (!isInstructionLine(MIR, Value, InBody))
+ continue;
+ const std::string_view Text = lineText(MIR, Value);
+ const std::size_t LastComma = Text.rfind(',');
+ if (LastComma != std::string_view::npos) {
+ addCandidate(Result, Seen, withoutRange(MIR, Value.Begin + LastComma, Value.ContentEnd),
+ Invocation, "remove trailing machine operand", MIR);
+ }
+ const std::size_t Implicit = Text.rfind(" implicit ");
+ if (Implicit != std::string_view::npos) {
+ addCandidate(Result, Seen, withoutRange(MIR, Value.Begin + Implicit, Value.ContentEnd),
+ Invocation, "remove implicit machine operand", MIR);
+ }
+ }
+ return Result;
+}
+
+[[nodiscard]] bool containsRegisterToken(std::string_view LineText, std::string_view Token) {
+ std::size_t Position = 0;
+ while ((Position = LineText.find(Token, Position)) != std::string_view::npos) {
+ const std::size_t End = Position + Token.size();
+ const bool LeftBoundary = Position == 0 || LineText[Position - 1U] != '%';
+ const bool RightBoundary =
+ End == LineText.size() || std::isdigit(static_cast<unsigned char>(LineText[End])) == 0;
+ if (LeftBoundary && RightBoundary)
+ return true;
+ Position = End;
+ }
+ return false;
+}
+
+[[nodiscard]] std::vector<Candidate> registerCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::set<std::string> Registers;
+ bool InBody = false;
+ for (const Line &Value : Lines) {
+ if (isBodyStart(MIR, Value)) {
+ InBody = true;
+ continue;
+ }
+ if (InBody && Value.Indent == 0) {
+ InBody = false;
+ continue;
+ }
+ if (!isInstructionLine(MIR, Value, InBody))
+ continue;
+ const std::string_view Text = lineText(MIR, Value);
+ for (std::size_t Position = 0; Position < Text.size(); ++Position) {
+ if (Text[Position] != '%' || Position + 1U >= Text.size() ||
+ std::isdigit(static_cast<unsigned char>(Text[Position + 1U])) == 0) {
+ continue;
+ }
+ std::size_t End = Position + 2U;
+ while (End < Text.size() && std::isdigit(static_cast<unsigned char>(Text[End])) != 0) {
+ ++End;
+ }
+ Registers.emplace(Text.substr(Position, End - Position));
+ Position = End - 1U;
+ }
+ }
+
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ for (const std::string &Register : Registers) {
+ std::string CandidateMIR;
+ CandidateMIR.reserve(MIR.size());
+ InBody = false;
+ for (const Line &Value : Lines) {
+ if (isBodyStart(MIR, Value))
+ InBody = true;
+ else if (InBody && Value.Indent == 0)
+ InBody = false;
+ if (isInstructionLine(MIR, Value, InBody) &&
+ containsRegisterToken(lineText(MIR, Value), Register)) {
+ continue;
+ }
+ CandidateMIR.append(MIR.substr(Value.Begin, Value.End - Value.Begin));
+ }
+ addCandidate(Result, Seen, std::move(CandidateMIR), Invocation,
+ "remove register subgraph " + Register, MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> sequenceItemCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation,
+ std::string_view Field,
+ std::size_t ItemIndent,
+ std::string_view Description) {
+ const std::vector<Line> Lines = lines(MIR);
+ std::vector<Candidate> Result;
+ std::set<std::string> Seen;
+ bool InField = false;
+ for (std::size_t Index = 0; Index < Lines.size(); ++Index) {
+ const std::string_view Trimmed = trimmedLine(MIR, Lines[Index]);
+ if (Lines[Index].Indent == 0 && Trimmed == std::string(Field) + ":") {
+ InField = true;
+ continue;
+ }
+ if (InField && Lines[Index].Indent == 0) {
+ InField = false;
+ continue;
+ }
+ if (!InField || Lines[Index].Indent != ItemIndent || !Trimmed.starts_with("- "))
+ continue;
+ std::size_t EndIndex = Index + 1U;
+ while (EndIndex < Lines.size() && Lines[EndIndex].Indent > ItemIndent)
+ ++EndIndex;
+ const std::size_t End = EndIndex < Lines.size() ? Lines[EndIndex].Begin : MIR.size();
+ addCandidate(Result, Seen, withoutRange(MIR, Lines[Index].Begin, End), Invocation,
+ std::string(Description), MIR);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> invocationCandidates(std::string_view MIR,
+ const BackendInvocation &Invocation,
+ ReductionGranularity Granularity) {
+ std::vector<Candidate> Result;
+ if (Granularity == ReductionGranularity::TargetFeature) {
+ for (std::size_t Index = Invocation.Features.size(); Index > 0; --Index) {
+ BackendInvocation CandidateInvocation = Invocation;
+ const std::string Feature = CandidateInvocation.Features[Index - 1U];
+ CandidateInvocation.Features.erase(CandidateInvocation.Features.begin() +
+ static_cast<std::ptrdiff_t>(Index - 1U));
+ auto Verified = CandidateInvocation.canonicalizeAndVerify();
+ if (Verified) {
+ Result.push_back(
+ {std::string(MIR), std::move(CandidateInvocation), "remove target feature " + Feature});
+ }
+ }
+ } else if (Granularity == ReductionGranularity::PassPipeline &&
+ (Invocation.PassPipeline.size() != 1 ||
+ Invocation.PassPipeline.front() != "default")) {
+ for (std::size_t Index = Invocation.PassPipeline.size(); Index > 0; --Index) {
+ if (Invocation.PassPipeline.size() == 1)
+ break;
+ BackendInvocation CandidateInvocation = Invocation;
+ const std::string Pass = CandidateInvocation.PassPipeline[Index - 1U];
+ CandidateInvocation.PassPipeline.erase(CandidateInvocation.PassPipeline.begin() +
+ static_cast<std::ptrdiff_t>(Index - 1U));
+ Result.push_back(
+ {std::string(MIR), std::move(CandidateInvocation), "remove pipeline pass " + Pass});
+ }
+ }
+ return Result;
+}
+
+[[nodiscard]] std::vector<Candidate> candidatesFor(ReductionGranularity Granularity,
+ std::string_view MIR,
+ const BackendInvocation &Invocation) {
+ switch (Granularity) {
+ case ReductionGranularity::CompilationUnit:
+ case ReductionGranularity::MachineFunction:
+ return functionCandidates(MIR, Invocation);
+ case ReductionGranularity::BasicBlock:
+ return blockCandidates(MIR, Invocation);
+ case ReductionGranularity::CFGEdge:
+ return cfgEdgeCandidates(MIR, Invocation);
+ case ReductionGranularity::Instruction:
+ return instructionCandidates(MIR, Invocation);
+ case ReductionGranularity::Operand:
+ return operandCandidates(MIR, Invocation);
+ case ReductionGranularity::RegisterSubgraph:
+ return registerCandidates(MIR, Invocation);
+ case ReductionGranularity::FrameObject: {
+ std::vector<Candidate> Result =
+ sequenceItemCandidates(MIR, Invocation, "fixedStack", 2, "remove fixed stack object");
+ std::vector<Candidate> Stack =
+ sequenceItemCandidates(MIR, Invocation, "stack", 2, "remove stack object");
+ Result.insert(Result.end(), std::make_move_iterator(Stack.begin()),
+ std::make_move_iterator(Stack.end()));
+ return Result;
+ }
+ case ReductionGranularity::ConstantPool:
+ return sequenceItemCandidates(MIR, Invocation, "constants", 2, "remove constant-pool entry");
+ case ReductionGranularity::JumpTable:
+ return sequenceItemCandidates(MIR, Invocation, "entries", 4, "remove jump-table entry");
+ case ReductionGranularity::TargetFeature:
+ case ReductionGranularity::PassPipeline:
+ return invocationCandidates(MIR, Invocation, Granularity);
+ }
+ return {};
+}
+
+} // namespace
+
+std::string_view spelling(ReductionGranularity Granularity) noexcept {
+ switch (Granularity) {
+ case ReductionGranularity::CompilationUnit:
+ return "compilation-unit";
+ case ReductionGranularity::MachineFunction:
+ return "machine-function";
+ case ReductionGranularity::BasicBlock:
+ return "basic-block";
+ case ReductionGranularity::CFGEdge:
+ return "cfg-edge";
+ case ReductionGranularity::Instruction:
+ return "instruction";
+ case ReductionGranularity::Operand:
+ return "operand";
+ case ReductionGranularity::RegisterSubgraph:
+ return "register-subgraph";
+ case ReductionGranularity::FrameObject:
+ return "frame-object";
+ case ReductionGranularity::ConstantPool:
+ return "constant-pool";
+ case ReductionGranularity::JumpTable:
+ return "jump-table";
+ case ReductionGranularity::TargetFeature:
+ return "target-feature";
+ case ReductionGranularity::PassPipeline:
+ return "pass-pipeline";
+ }
+ return "invalid";
+}
+
+Expected<MIRReductionResult> reduceMIR(std::string SourceName, std::string SourceText,
+ BackendInvocation Invocation,
+ const TargetDescription &Target,
+ const MIRInterestingnessTest &Interesting,
+ MIRReducerOptions Options) {
+ if (Options.Mode == ReductionMode::PreserveFailure && !Interesting)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "failure-preserving MIR reduction requires an interestingness test");
+ if (Options.MaximumAttempts == 0)
+ return makeUnexpected(ErrorCode::InvalidArgument, "MIR reducer attempt budget must be nonzero");
+ std::set<ReductionGranularity> SeenGranularities;
+ for (ReductionGranularity Granularity : Options.Granularities) {
+ if (spelling(Granularity) == "invalid") {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "MIR reducer granularity is not recognized");
+ }
+ if (!SeenGranularities.insert(Granularity).second) {
+ return makeUnexpected(ErrorCode::InvalidArgument, "MIR reducer granularities must be unique");
+ }
+ }
+ auto InvocationVerification = Invocation.canonicalizeAndVerify();
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ auto Initial =
+ parseAndCanonicalizeMIR(std::move(SourceName), std::move(SourceText), Target, Invocation);
+ if (!Initial)
+ return std::unexpected(Initial.error());
+ if (Options.Mode == ReductionMode::PreserveFailure) {
+ auto InitiallyInteresting = Interesting(Initial->Text, Invocation);
+ if (!InitiallyInteresting)
+ return std::unexpected(InitiallyInteresting.error());
+ if (!*InitiallyInteresting) {
+ return makeUnexpected(ErrorCode::ReductionFailed,
+ "initial MIR input does not satisfy the interestingness test");
+ }
+ }
+ if (Options.Granularities.empty())
+ Options.Granularities = defaultGranularities();
+
+ MIRReductionResult Result{
+ .MIR = std::move(Initial->Text),
+ .Invocation = std::move(Invocation),
+ .Steps = {},
+ .Attempts = 0,
+ .Exhausted = false,
+ };
+ for (ReductionGranularity Granularity : Options.Granularities) {
+ bool Changed = true;
+ while (Changed && Result.Attempts < Options.MaximumAttempts) {
+ Changed = false;
+ std::vector<Candidate> Candidates = candidatesFor(Granularity, Result.MIR, Result.Invocation);
+ for (Candidate &CandidateValue : Candidates) {
+ if (Result.Attempts == Options.MaximumAttempts)
+ break;
+ ++Result.Attempts;
+ auto Canonical = parseAndCanonicalizeMIR("reducer-candidate.mir", CandidateValue.MIR,
+ Target, CandidateValue.Invocation);
+ if (!Canonical)
+ continue;
+ if (Canonical->Text == Result.MIR && CandidateValue.Invocation == Result.Invocation)
+ continue;
+ if (Options.Mode == ReductionMode::PreserveFailure) {
+ auto IsInteresting = Interesting(Canonical->Text, CandidateValue.Invocation);
+ if (!IsInteresting)
+ return std::unexpected(IsInteresting.error());
+ if (!*IsInteresting)
+ continue;
+ }
+ const std::size_t PreviousSize = Result.MIR.size();
+ Result.MIR = std::move(Canonical->Text);
+ Result.Invocation = std::move(CandidateValue.Invocation);
+ Result.Steps.push_back({
+ .Granularity = Granularity,
+ .Description = std::move(CandidateValue.Description),
+ .PreviousSize = PreviousSize,
+ .ReducedSize = Result.MIR.size(),
+ });
+ Changed = true;
+ break;
+ }
+ }
+ }
+ Result.Exhausted = Result.Attempts == Options.MaximumAttempts;
+ return Result;
+}
+
+} // namespace rcc::tooling
diff --git a/backend/lib/Tooling/PipelineDriver.cpp b/backend/lib/Tooling/PipelineDriver.cpp
new file mode 100644
index 0000000..330730e
--- /dev/null
+++ b/backend/lib/Tooling/PipelineDriver.cpp
@@ -0,0 +1,436 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Tooling/PipelineDriver.h"
+
+#include "rcc/CodeGen/CompilationUnit.h"
+#include "rcc/CodeGen/MachineFunction.h"
+#include "rcc/CodeGen/MachineOptimizationPipeline.h"
+#include "rcc/CodeGen/MachineVerifier.h"
+#include "rcc/MIR/MIRDocument.h"
+#include "rcc/Target/RISCV/RISCVPipeline.h"
+
+#include <algorithm>
+#include <atomic>
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <mutex>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <string_view>
+#include <thread>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+namespace rcc::tooling {
+namespace {
+
+struct FunctionRunResult final {
+ std::vector<ExecutedPass> ExecutedPasses;
+ std::vector<PipelineSnapshot> Snapshots;
+ std::optional<Error> Failure;
+};
+
+[[nodiscard]] unsigned stageOrdinal(BackendStage Stage) noexcept {
+ return static_cast<unsigned>(Stage);
+}
+
+[[nodiscard]] bool selectorMatches(std::string_view Selector, std::string_view Pass,
+ std::uint32_t Occurrence) {
+ if (Selector == "all" || Selector == Pass)
+ return true;
+ std::string Qualified(Pass);
+ Qualified.push_back('#');
+ Qualified.append(std::to_string(Occurrence));
+ return Selector == Qualified;
+}
+
+[[nodiscard]] bool anySelectorMatches(std::span<const std::string> Selectors, std::string_view Pass,
+ std::uint32_t Occurrence) {
+ return std::ranges::any_of(Selectors, [Pass, Occurrence](const std::string &Selector) {
+ return selectorMatches(Selector, Pass, Occurrence);
+ });
+}
+
+[[nodiscard]] std::optional<BackendStage> stageAfterPass(std::string_view Pass) noexcept {
+ if (Pass == "Legalizer")
+ return BackendStage::LegalizedMIR;
+ if (Pass == "RegisterBankSelect")
+ return BackendStage::RegisterBankMIR;
+ if (Pass == "InstructionSelect")
+ return BackendStage::SelectedMIR;
+ if (Pass == "TwoAddressRewrite")
+ return BackendStage::PostSSAMIR;
+ if (Pass == "PBQPAllocator")
+ return BackendStage::PostRegisterAllocationMIR;
+ if (Pass == "final-encodability-verifier")
+ return BackendStage::FinalMIR;
+ return std::nullopt;
+}
+
+[[nodiscard]] Expected<MachinePassManager::PassList>
+createPasses(const MachineFunction &Function, const BackendInvocation &Invocation,
+ MachinePassManagerOptions Options) {
+ MachinePassManager Pipeline(Options);
+ if (Invocation.PassPipeline.size() == 1 && Invocation.PassPipeline.front() == "default") {
+ auto Added = riscv::addCanonicalPipeline(Pipeline, Function);
+ if (!Added)
+ return std::unexpected(Added.error());
+ } else {
+ if (std::ranges::find(Invocation.PassPipeline, "default") != Invocation.PassPipeline.end()) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "the default pipeline marker cannot be mixed with named passes");
+ }
+ for (const std::string &Name : Invocation.PassPipeline) {
+ auto Pass = riscv::createCanonicalPipelinePass(Name);
+ if (!Pass)
+ return std::unexpected(Pass.error());
+ auto Added = Pipeline.addPass(std::move(*Pass));
+ if (!Added)
+ return std::unexpected(Added.error());
+ }
+ }
+ return std::move(Pipeline).takePasses();
+}
+
+[[nodiscard]] Expected<void> validateSelector(std::string_view Selector) {
+ if (Selector == "all")
+ return {};
+ const std::size_t Hash = Selector.rfind('#');
+ const std::string_view Name =
+ Hash == std::string_view::npos ? Selector : Selector.substr(0, Hash);
+ if (Name.empty())
+ return makeUnexpected(ErrorCode::InvalidInvocation, "empty pipeline pass selector");
+ auto Pass = riscv::createCanonicalPipelinePass(Name);
+ if (!Pass)
+ return std::unexpected(Pass.error());
+ if (Hash != std::string_view::npos) {
+ const std::string_view Occurrence = Selector.substr(Hash + 1U);
+ if (Occurrence.empty() || Occurrence == "0" ||
+ !std::ranges::all_of(Occurrence,
+ [](char Character) { return Character >= '0' && Character <= '9'; })) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "pipeline pass occurrence must be a positive integer");
+ }
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void> validateControls(const PipelineControls &Controls) {
+ if (Controls.StopBefore) {
+ auto Result = validateSelector(*Controls.StopBefore);
+ if (!Result)
+ return Result;
+ }
+ if (Controls.StopAfter) {
+ auto Result = validateSelector(*Controls.StopAfter);
+ if (!Result)
+ return Result;
+ }
+ for (const std::string &Selector : Controls.PrintBefore) {
+ auto Result = validateSelector(Selector);
+ if (!Result)
+ return Result;
+ }
+ for (const std::string &Selector : Controls.PrintAfter) {
+ auto Result = validateSelector(Selector);
+ if (!Result)
+ return Result;
+ }
+ return {};
+}
+
+[[nodiscard]] Expected<void>
+captureSnapshot(FunctionRunResult &Result, const mir::MIRDocument &Document,
+ const TargetDescription &Target, const BackendInvocation &Invocation,
+ SnapshotPhase Phase, BackendStage Stage, std::string_view Function,
+ std::string_view Pass, std::uint32_t Occurrence) {
+ mir::MIRDocumentPrinterOptions PrintOptions;
+ PrintOptions.Mode = mir::MIPrintMode::Complete;
+ PrintOptions.EmitEmbeddedIR = true;
+ PrintOptions.DataLayout = Invocation.DataLayout;
+ PrintOptions.DefaultPointerSizeInBits = 64;
+ auto Printed = mir::printMIRDocument(Document, Target, std::move(PrintOptions));
+ if (!Printed)
+ return std::unexpected(Printed.error());
+ Result.Snapshots.push_back({
+ .Phase = Phase,
+ .Stage = Stage,
+ .Function = std::string(Function),
+ .Pass = std::string(Pass),
+ .Occurrence = Occurrence,
+ .MIR = std::move(*Printed),
+ });
+ return {};
+}
+
+[[nodiscard]] Expected<FunctionRunResult>
+runFunction(MachineFunction &Function, mir::MIRDocument &Document, const TargetDescription &Target,
+ const BackendInvocation &Invocation, const PipelineControls &Controls,
+ bool AllowSnapshots, MachinePassInstrumentation *Instrumentation) {
+ FunctionRunResult Result;
+ MachinePassManagerOptions ManagerOptions{
+ .VerifyBefore = true,
+ .VerifyEach = Controls.VerifyEach,
+ .DetectUnreportedChanges = Controls.DetectUnreportedChanges,
+ };
+ auto Passes = createPasses(Function, Invocation, ManagerOptions);
+ if (!Passes)
+ return std::unexpected(Passes.error());
+ MachineAnalysisManager Analyses;
+ auto Registered = registerMachineOptimizationAnalyses(Analyses);
+ if (!Registered)
+ return std::unexpected(Registered.error());
+
+ BackendStage CurrentStage = stageForFunction(Function);
+ if (AllowSnapshots && Controls.CaptureStageSnapshots) {
+ auto Captured = captureSnapshot(Result, Document, Target, Invocation, SnapshotPhase::Stage,
+ CurrentStage, Function.name(), {}, 0);
+ if (!Captured)
+ return std::unexpected(Captured.error());
+ }
+ if (Controls.StopAtStage && stageOrdinal(CurrentStage) >= stageOrdinal(*Controls.StopAtStage)) {
+ return Result;
+ }
+
+ std::unordered_map<std::string, std::uint32_t> Occurrences;
+ for (std::unique_ptr<MachineFunctionPass> &Pass : *Passes) {
+ if (Pass == nullptr)
+ return makeUnexpected(ErrorCode::InternalError, "pipeline contains a null pass");
+ const std::string Name = Pass->contract().Name;
+ const std::uint32_t Occurrence = ++Occurrences[Name];
+ if (Controls.StopBefore && selectorMatches(*Controls.StopBefore, Name, Occurrence))
+ break;
+ if (AllowSnapshots && anySelectorMatches(Controls.PrintBefore, Name, Occurrence)) {
+ auto Captured =
+ captureSnapshot(Result, Document, Target, Invocation, SnapshotPhase::BeforePass,
+ CurrentStage, Function.name(), Name, Occurrence);
+ if (!Captured)
+ return std::unexpected(Captured.error());
+ }
+
+ MachinePassManager SinglePass(ManagerOptions);
+ auto Added = SinglePass.addPass(std::move(Pass));
+ if (!Added)
+ return std::unexpected(Added.error());
+ auto Run = SinglePass.run(Function, Target, Analyses, Instrumentation);
+ if (!Run)
+ return std::unexpected(Run.error());
+ Result.ExecutedPasses.push_back({
+ .Function = std::string(Function.name()),
+ .Pass = Name,
+ .Occurrence = Occurrence,
+ });
+
+ if (const std::optional<BackendStage> NewStage = stageAfterPass(Name))
+ CurrentStage = *NewStage;
+ if (AllowSnapshots && anySelectorMatches(Controls.PrintAfter, Name, Occurrence)) {
+ auto Captured =
+ captureSnapshot(Result, Document, Target, Invocation, SnapshotPhase::AfterPass,
+ CurrentStage, Function.name(), Name, Occurrence);
+ if (!Captured)
+ return std::unexpected(Captured.error());
+ }
+ if (AllowSnapshots && Controls.CaptureStageSnapshots && stageAfterPass(Name)) {
+ auto Captured = captureSnapshot(Result, Document, Target, Invocation, SnapshotPhase::Stage,
+ CurrentStage, Function.name(), Name, Occurrence);
+ if (!Captured)
+ return std::unexpected(Captured.error());
+ }
+ if (Controls.StopAfter && selectorMatches(*Controls.StopAfter, Name, Occurrence))
+ break;
+ if (Controls.StopAtStage && stageOrdinal(CurrentStage) >= stageOrdinal(*Controls.StopAtStage)) {
+ break;
+ }
+ }
+ return Result;
+}
+
+[[nodiscard]] bool requiresSequentialExecution(const PipelineControls &Controls) noexcept {
+ return Controls.CaptureStageSnapshots || !Controls.PrintBefore.empty() ||
+ !Controls.PrintAfter.empty();
+}
+
+} // namespace
+
+BackendStage stageForFunction(const MachineFunction &Function) noexcept {
+ const MachineFunctionProperties &Properties = Function.properties();
+ if (Properties.has(MachineFunctionProperty::Selected) &&
+ Properties.has(MachineFunctionProperty::NoExecutablePseudos))
+ return BackendStage::FinalMIR;
+ if (Properties.has(MachineFunctionProperty::Selected) &&
+ Properties.has(MachineFunctionProperty::NoVRegs))
+ return BackendStage::PostRegisterAllocationMIR;
+ if (Properties.has(MachineFunctionProperty::Selected) &&
+ Properties.has(MachineFunctionProperty::TiedOpsRewritten)) {
+ return BackendStage::PostSSAMIR;
+ }
+ if (Properties.has(MachineFunctionProperty::Selected))
+ return BackendStage::SelectedMIR;
+ if (Properties.has(MachineFunctionProperty::RegBankSelected))
+ return BackendStage::RegisterBankMIR;
+ if (Properties.has(MachineFunctionProperty::Legalized))
+ return BackendStage::LegalizedMIR;
+ return BackendStage::PreLegalizerMIR;
+}
+
+std::string_view spelling(BackendStage Stage) noexcept {
+ switch (Stage) {
+ case BackendStage::PreLegalizerMIR:
+ return "prelegalizer-mir";
+ case BackendStage::LegalizedMIR:
+ return "legalized-mir";
+ case BackendStage::RegisterBankMIR:
+ return "regbank-mir";
+ case BackendStage::SelectedMIR:
+ return "selected-mir";
+ case BackendStage::PostSSAMIR:
+ return "post-ssa-mir";
+ case BackendStage::PostRegisterAllocationMIR:
+ return "post-ra-mir";
+ case BackendStage::FinalMIR:
+ return "final-mir";
+ }
+ return "invalid";
+}
+
+Expected<BackendStage> parseBackendStage(std::string_view Value) {
+ if (Value == "prelegalizer-mir")
+ return BackendStage::PreLegalizerMIR;
+ if (Value == "legalized-mir")
+ return BackendStage::LegalizedMIR;
+ if (Value == "regbank-mir")
+ return BackendStage::RegisterBankMIR;
+ if (Value == "selected-mir")
+ return BackendStage::SelectedMIR;
+ if (Value == "post-ssa-mir")
+ return BackendStage::PostSSAMIR;
+ if (Value == "post-ra-mir")
+ return BackendStage::PostRegisterAllocationMIR;
+ if (Value == "final-mir")
+ return BackendStage::FinalMIR;
+ return makeUnexpected(ErrorCode::InvalidInvocation, "unknown backend stage");
+}
+
+Expected<void> verifyRV64GCInvocation(const BackendInvocation &Invocation) {
+ BackendInvocation Canonical = Invocation;
+ auto Verified = Canonical.canonicalizeAndVerify();
+ if (!Verified)
+ return std::unexpected(Verified.error());
+ if (Canonical != Invocation) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "RV64GC backend invocation must be canonicalized before execution");
+ }
+ const BackendInvocation Expected = defaultRV64GCInvocation();
+ if (Invocation.Triple != Expected.Triple || Invocation.CPU != Expected.CPU ||
+ Invocation.TuneCPU != Expected.TuneCPU || Invocation.Features != Expected.Features ||
+ Invocation.ABI != Expected.ABI || Invocation.DataLayout != Expected.DataLayout) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation does not select the supported RV64GC LP64D target");
+ }
+ if (Invocation.MIRReferenceRevision != LLVMReferenceRevision ||
+ Invocation.GenericOpcodeVersion != GenericOpcodeReferenceVersion ||
+ Invocation.TargetABILoweringVersion != RV64GCTargetABILoweringVersion) {
+ return makeUnexpected(ErrorCode::InvalidInvocation,
+ "backend invocation reference versions do not match this build");
+ }
+ return {};
+}
+
+Expected<PipelineRunResult> runRV64GCPipeline(mir::MIRDocument &Document,
+ const TargetDescription &Target,
+ const BackendInvocation &Invocation,
+ PipelineControls Controls,
+ MachinePassInstrumentation *Instrumentation) {
+ auto InvocationVerification = verifyRV64GCInvocation(Invocation);
+ if (!InvocationVerification)
+ return std::unexpected(InvocationVerification.error());
+ auto ControlVerification = validateControls(Controls);
+ if (!ControlVerification)
+ return std::unexpected(ControlVerification.error());
+ auto UnitVerification = Document.unit().verify();
+ if (!UnitVerification)
+ return std::unexpected(UnitVerification.error());
+ if (Document.unit().functionCount() == 0) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "pipeline input must contain at least one machine function");
+ }
+
+ MachinePassInstrumentation LocalInstrumentation;
+ MachinePassInstrumentation *ActiveInstrumentation =
+ Instrumentation == nullptr ? &LocalInstrumentation : Instrumentation;
+ ActiveInstrumentation->setPerFunctionFuel(Invocation.ActionFuel);
+ if (!Invocation.EnabledActions.empty()) {
+ const std::vector<std::string> Enabled = Invocation.EnabledActions;
+ ActiveInstrumentation->setActionFilter([Enabled](const MachineActionID &Action, std::uint64_t) {
+ return std::ranges::binary_search(Enabled, Action.Rule) ||
+ std::ranges::binary_search(Enabled, Action.Pass) ||
+ std::ranges::binary_search(Enabled, Action.toString());
+ });
+ }
+
+ const std::size_t FunctionCount = Document.unit().functionCount();
+ std::vector<FunctionRunResult> FunctionResults(FunctionCount);
+ const bool Sequential = requiresSequentialExecution(Controls) ||
+ Invocation.Determinism.ThreadCount == 1 || FunctionCount == 1;
+ if (Sequential) {
+ for (std::size_t Index = 0; Index < FunctionCount; ++Index) {
+ MachineFunction *Function = Document.unit().functionAt(Index);
+ if (Function == nullptr)
+ return makeUnexpected(ErrorCode::InternalError,
+ "compilation unit contains a null function");
+ auto Run = runFunction(*Function, Document, Target, Invocation, Controls, true,
+ ActiveInstrumentation);
+ if (!Run)
+ return std::unexpected(Run.error());
+ FunctionResults[Index] = std::move(*Run);
+ }
+ } else {
+ const std::size_t WorkerCount =
+ std::min<std::size_t>(Invocation.Determinism.ThreadCount, 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 = Document.unit().functionAt(Index);
+ if (Function == nullptr) {
+ FunctionResults[Index].Failure =
+ Error(ErrorCode::InternalError, "compilation unit contains a null function");
+ continue;
+ }
+ auto Run = runFunction(*Function, Document, Target, Invocation, Controls, false,
+ ActiveInstrumentation);
+ if (!Run) {
+ FunctionResults[Index].Failure = Run.error();
+ } else {
+ FunctionResults[Index] = std::move(*Run);
+ }
+ }
+ };
+ std::vector<std::thread> Workers;
+ Workers.reserve(WorkerCount);
+ for (std::size_t Index = 0; Index < WorkerCount; ++Index)
+ Workers.emplace_back(Worker);
+ for (std::thread &Thread : Workers)
+ Thread.join();
+ }
+
+ PipelineRunResult Result;
+ for (FunctionRunResult &FunctionResult : FunctionResults) {
+ if (FunctionResult.Failure)
+ return std::unexpected(std::move(*FunctionResult.Failure));
+ Result.ExecutedPasses.insert(Result.ExecutedPasses.end(),
+ std::make_move_iterator(FunctionResult.ExecutedPasses.begin()),
+ std::make_move_iterator(FunctionResult.ExecutedPasses.end()));
+ Result.Snapshots.insert(Result.Snapshots.end(),
+ std::make_move_iterator(FunctionResult.Snapshots.begin()),
+ std::make_move_iterator(FunctionResult.Snapshots.end()));
+ }
+ return Result;
+}
+
+} // namespace rcc::tooling
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 10:07:59 +0000