From adcf8c9b1bd1b47e00bf859693112cea1f7e8c9f Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Mon, 10 Aug 2026 20:36:50 +0800 Subject: [Tooling] Complete backend tooling and validation --- backend/lib/Tooling/ArtifactStore.cpp | 532 ++++++++++++++++++++++ backend/lib/Tooling/BackendDriver.cpp | 214 +++++++++ backend/lib/Tooling/BackendInvocation.cpp | 500 ++++++++++++++++++++ backend/lib/Tooling/BackendManifest.cpp | 733 ++++++++++++++++++++++++++++++ backend/lib/Tooling/CMakeLists.txt | 76 ++++ backend/lib/Tooling/MIRFuzzer.cpp | 613 +++++++++++++++++++++++++ backend/lib/Tooling/MIRReducer.cpp | 534 ++++++++++++++++++++++ backend/lib/Tooling/PipelineDriver.cpp | 436 ++++++++++++++++++ 8 files changed, 3638 insertions(+) create mode 100644 backend/lib/Tooling/ArtifactStore.cpp create mode 100644 backend/lib/Tooling/BackendDriver.cpp create mode 100644 backend/lib/Tooling/BackendInvocation.cpp create mode 100644 backend/lib/Tooling/BackendManifest.cpp create mode 100644 backend/lib/Tooling/CMakeLists.txt create mode 100644 backend/lib/Tooling/MIRFuzzer.cpp create mode 100644 backend/lib/Tooling/MIRReducer.cpp create mode 100644 backend/lib/Tooling/PipelineDriver.cpp (limited to 'backend/lib/Tooling') 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::tooling { +namespace { + +constexpr std::uintmax_t MaximumPackageFileSize = std::uintmax_t{1} << 30U; +std::atomic 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> 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::numeric_limits::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 Result(static_cast(Size)); + if (!Result.empty()) { + Input.read(reinterpret_cast(Result.data()), + static_cast(Result.size())); + } + if (!Input) + return makeUnexpected(Code, "cannot read package file '" + Path.string() + "'"); + return Result; +} + +[[nodiscard]] Expected 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(Bytes->data()), Bytes->size()); +} + +[[nodiscard]] Expected writeBytes(const std::filesystem::path &Path, + std::span 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(Bytes.data()), + static_cast(Bytes.size())); + } + Output.close(); + if (!Output) + return makeUnexpected(Code, "cannot write package file '" + Path.string() + "'"); + return {}; +} + +[[nodiscard]] Expected writeText(const std::filesystem::path &Path, std::string_view Text, + ErrorCode Code) { + const auto *Bytes = reinterpret_cast(Text.data()); + return writeBytes(Path, std::span(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 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 +writePackageAtomically(const std::filesystem::path &Destination, std::string_view ManifestText, + std::string_view InputMIR, std::string_view ArtifactName, + std::span 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 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 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 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 +createBackendManifest(ManifestKind Kind, ArtifactKind Artifact, const BackendInvocation &Invocation, + const TargetDescription &Target, std::string_view CanonicalInputMIR, + std::optional> ArtifactBytes, + std::vector 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(ArtifactBytes->data()); + Result.ArtifactHash = sha256Hex( + std::span(Bytes, static_cast(ArtifactBytes->size()))); + } + auto Verification = Result.verify(); + if (!Verification) + return std::unexpected(Verification.error()); + return Result; +} + +Expected storeCacheEntry(const std::filesystem::path &CacheRoot, + const BackendManifest &Manifest, std::string_view CanonicalInputMIR, + std::span 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(Artifact.data()); + if (sha256Hex(std::span(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 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(ArtifactBytes->data()); + if (sha256Hex(std::span(Bytes, ArtifactBytes->size())) != + *Manifest->ArtifactHash) { + return makeUnexpected(ErrorCode::CacheMiss, "cached artifact hash is inconsistent"); + } + std::optional ParsedArtifact; + if (isMIRArtifact(Artifact)) { + std::string ArtifactText(reinterpret_cast(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 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 updateReproducerDiagnostics(const std::filesystem::path &PackagePath, + std::vector 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 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 +#include +#include +#include +#include +#include + +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(Stage); +} + +[[nodiscard]] Expected> 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(Printed->begin(), Printed->end()); +} + +} // namespace + +std::string_view BackendRunResult::text() const noexcept { + if (Kind == BackendOutputKind::RelocatableObject || Output.empty()) + return {}; + return {reinterpret_cast(Output.data()), Output.size()}; +} + +Expected 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 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 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(static_cast(Output)); +} + +Expected 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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 +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 canonicalizeOptions(std::vector &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 canonicalizeFeatures(std::vector &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(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(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(*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(Descriptor.Owner)); + appendInteger(Output, "instruction.deadline", static_cast(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::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 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 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 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 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 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 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 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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(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(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 +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 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 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 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 run() { + if (!Parsed.succeeded()) { + const std::span 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(**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 + [[nodiscard]] Expected firstError(const Results &...Values) const { + std::optional 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 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 rejectUnknown(const yaml::Node &Node, + std::initializer_list Allowed, + std::string_view Context) const { + std::unordered_set 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 ID = Node.mappingValue(Name); + return ID && Stream != nullptr ? Stream->node(*ID) : nullptr; + } + + [[nodiscard]] Expected 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 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 + [[nodiscard]] Expected 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 + [[nodiscard]] Expected 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(Value, std::string(Context) + "." + std::string(Name)); + } + + [[nodiscard]] Expected 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> 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 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> 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 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 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(**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(**Mapping, "random_seed", "manifest invocation"); + auto ThreadCount = + requiredUnsigned(**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(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> + 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 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 { + 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::value_type; + auto ParsedValue = unsignedValue(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 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 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 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 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 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 + "$" + "$" +) +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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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(next() % Bound); + } + +private: + std::uint64_t State; +}; + +[[nodiscard]] std::vector 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(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(Random.index(Result.size() + 1U)), + static_cast(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 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('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('0' + Random.index(10)); + break; + } + default: + break; + } + return Result; +} + +[[nodiscard]] Expected 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 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 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 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(static_cast(Stage)); +} + +[[nodiscard]] Expected 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(Random.index(7U)); + const MachineFunction *Function = Parsed->Document.unit().functionAt(0); + if (Function == nullptr || + static_cast(Stage) < static_cast(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 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 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{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; + +[[nodiscard]] Expected 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 Reg = Operand->registerValue(); + if (!Reg) + return makeUnexpected(ErrorCode::Unsupported, "semantic subset requires register operands"); + return *Reg; +} + +[[nodiscard]] Expected 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()) + return static_cast(*Immediate); + if (const auto *Immediate = Operand->getIf()) { + 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 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::bit_cast(Left) >> (Right & 63U)); + Values[Destination->opaqueValue()] = Value; + } + return makeUnexpected(ErrorCode::Unsupported, "semantic subset did not encounter a return"); +} + +[[nodiscard]] Expected 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 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 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 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +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 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 lines(std::string_view Text) { + std::vector 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 &Result, std::set &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 functionCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::vector Starts; + for (std::size_t Index = 0; Index < Lines.size(); ++Index) { + if (lineText(MIR, Lines[Index]) == "---") + Starts.push_back(Index); + } + std::vector Result; + std::set 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 blockCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::vector Result; + std::set 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 instructionCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::vector Result; + std::set 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 cfgEdgeCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::vector Result; + std::set 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 operandCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::vector Result; + std::set 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(LineText[End])) == 0; + if (LeftBoundary && RightBoundary) + return true; + Position = End; + } + return false; +} + +[[nodiscard]] std::vector registerCandidates(std::string_view MIR, + const BackendInvocation &Invocation) { + const std::vector Lines = lines(MIR); + std::set 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(Text[Position + 1U])) == 0) { + continue; + } + std::size_t End = Position + 2U; + while (End < Text.size() && std::isdigit(static_cast(Text[End])) != 0) { + ++End; + } + Registers.emplace(Text.substr(Position, End - Position)); + Position = End - 1U; + } + } + + std::vector Result; + std::set 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 sequenceItemCandidates(std::string_view MIR, + const BackendInvocation &Invocation, + std::string_view Field, + std::size_t ItemIndent, + std::string_view Description) { + const std::vector Lines = lines(MIR); + std::vector Result; + std::set 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 invocationCandidates(std::string_view MIR, + const BackendInvocation &Invocation, + ReductionGranularity Granularity) { + std::vector 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(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(Index - 1U)); + Result.push_back( + {std::string(MIR), std::move(CandidateInvocation), "remove pipeline pass " + Pass}); + } + } + return Result; +} + +[[nodiscard]] std::vector 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 Result = + sequenceItemCandidates(MIR, Invocation, "fixedStack", 2, "remove fixed stack object"); + std::vector 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 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 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 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::tooling { +namespace { + +struct FunctionRunResult final { + std::vector ExecutedPasses; + std::vector Snapshots; + std::optional Failure; +}; + +[[nodiscard]] unsigned stageOrdinal(BackendStage Stage) noexcept { + return static_cast(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 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 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 +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 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 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 +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 +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 Occurrences; + for (std::unique_ptr &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 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 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 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 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 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 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(Invocation.Determinism.ThreadCount, FunctionCount); + std::atomic 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 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 -- cgit v1.2.3