diff options
Diffstat (limited to 'backend/include/rcc/IR')
| -rw-r--r-- | backend/include/rcc/IR/PassInstrumentation.h | 227 | ||||
| -rw-r--r-- | backend/include/rcc/IR/PassManager.h | 531 |
2 files changed, 758 insertions, 0 deletions
diff --git a/backend/include/rcc/IR/PassInstrumentation.h b/backend/include/rcc/IR/PassInstrumentation.h new file mode 100644 index 0000000..082ec81 --- /dev/null +++ b/backend/include/rcc/IR/PassInstrumentation.h @@ -0,0 +1,227 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_IR_PASSINSTRUMENTATION_H +#define RCC_IR_PASSINSTRUMENTATION_H + +#include "rcc/CodeGen/MachineFunctionAnalysisManager.h" + +#include <cstdint> +#include <functional> +#include <mutex> +#include <optional> +#include <string> +#include <string_view> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class CompilationUnit; +class MachineFunction; +class TargetDescription; +struct MachinePassResult; +struct CompilationUnitPassResult; + +enum class InstrumentationPhase : std::uint8_t { + Before, + After, +}; + +struct InstrumentationStatistic final { + std::string Name; + bool IsAnalysis = false; + std::uint64_t Invocations = 0; + std::uint64_t CacheHits = 0; + std::uint64_t Changes = 0; + std::uint64_t Failures = 0; + std::uint64_t TotalNanoseconds = 0; +}; + +struct MachineActionID final { + std::string Pass; + std::string Rule; + MachineFunctionStableID Function; + MachineInstrStableID Instruction; + + [[nodiscard]] std::string toString() const; + + friend bool operator==(const MachineActionID &, const MachineActionID &) = default; +}; + +struct MachineActionEvent final { + MachineActionID ID; + std::uint64_t Cost = 0; + bool Accepted = false; + + friend bool operator==(const MachineActionEvent &, const MachineActionEvent &) = default; +}; + +class MachinePassInstrumentation final { +public: + using BeforeCallback = std::function<void(std::string_view, const MachineFunction &)>; + using AfterCallback = + std::function<void(std::string_view, const MachineFunction &, const MachinePassResult &)>; + using FailureCallback = + std::function<void(std::string_view, const MachineFunction &, const Error &)>; + using BeforeAnalysisCallback = std::function<void(std::string_view, const MachineFunction &)>; + using AfterAnalysisCallback = + std::function<void(std::string_view, const MachineFunction &, bool, std::uint64_t)>; + using AnalysisFailureCallback = + std::function<void(std::string_view, const MachineFunction &, const Error &)>; + using IRPrintCallback = + std::function<void(InstrumentationPhase, std::string_view, const MachineFunction &)>; + using ChangeCallback = + std::function<void(std::string_view, const MachineFunction &, MachinePassChanges, bool)>; + using ActionFilter = std::function<bool(const MachineActionID &, std::uint64_t)>; + + using BeforeUnitCallback = std::function<void(std::string_view, const CompilationUnit &)>; + using AfterUnitCallback = std::function<void(std::string_view, const CompilationUnit &, + const CompilationUnitPassResult &)>; + using UnitFailureCallback = + std::function<void(std::string_view, const CompilationUnit &, const Error &)>; + using BeforeUnitAnalysisCallback = std::function<void(std::string_view, const CompilationUnit &)>; + using AfterUnitAnalysisCallback = + std::function<void(std::string_view, const CompilationUnit &, bool, std::uint64_t)>; + using UnitAnalysisFailureCallback = + std::function<void(std::string_view, const CompilationUnit &, const Error &)>; + + void addBeforeCallback(BeforeCallback Callback); + void addAfterCallback(AfterCallback Callback); + void addFailureCallback(FailureCallback Callback); + void addBeforeAnalysisCallback(BeforeAnalysisCallback Callback); + void addAfterAnalysisCallback(AfterAnalysisCallback Callback); + void addAnalysisFailureCallback(AnalysisFailureCallback Callback); + void addIRPrintCallback(IRPrintCallback Callback); + void addChangeCallback(ChangeCallback Callback); + void setActionFilter(ActionFilter Filter); + void setPerFunctionFuel(std::optional<std::uint64_t> Fuel); + + void addBeforeUnitCallback(BeforeUnitCallback Callback); + void addAfterUnitCallback(AfterUnitCallback Callback); + void addUnitFailureCallback(UnitFailureCallback Callback); + void addBeforeUnitAnalysisCallback(BeforeUnitAnalysisCallback Callback); + void addAfterUnitAnalysisCallback(AfterUnitAnalysisCallback Callback); + void addUnitAnalysisFailureCallback(UnitAnalysisFailureCallback Callback); + + [[nodiscard]] std::vector<InstrumentationStatistic> statistics() const; + [[nodiscard]] std::vector<MachineActionEvent> actionEvents() const; + + [[nodiscard]] Expected<bool> requestAction(std::string_view Pass, std::string_view Rule, + const MachineFunction &Function, + MachineInstrStableID Instruction, std::uint64_t Cost); + [[nodiscard]] Expected<bool> requestAction(std::string_view Pass, std::string_view Rule, + const MachineFunction &Function, std::nullptr_t, + std::uint64_t Cost); + +private: + struct BufferedEvents final { + const TargetDescription *Target = nullptr; + std::vector<std::function<void()>> Events; + }; + + [[nodiscard]] bool bufferFunctionEvent(const MachineFunction &Function, + std::function<void(const MachineFunction &)> Replay) const; + void beginBuffering(BufferedEvents &Buffer, const TargetDescription &Target) const noexcept; + void endBuffering() const noexcept; + void replayBufferedEvents(BufferedEvents &Buffer) const; + + void before(std::string_view Name, const MachineFunction &Function) const; + void after(std::string_view Name, const MachineFunction &Function, + const MachinePassResult &Result, std::uint64_t Nanoseconds) const; + void failure(std::string_view Name, const MachineFunction &Function, const Error &ErrorValue, + std::uint64_t Nanoseconds = 0) const; + void beforeAnalysis(std::string_view Name, const MachineFunction &Function) const; + void afterAnalysis(std::string_view Name, const MachineFunction &Function, bool CacheHit, + std::uint64_t Nanoseconds) const; + void analysisFailure(std::string_view Name, const MachineFunction &Function, + const Error &ErrorValue, std::uint64_t Nanoseconds) const; + void change(std::string_view Name, const MachineFunction &Function, MachinePassChanges Changes, + bool FingerprintChanged) const; + + void beforeUnit(std::string_view Name, const CompilationUnit &Unit) const; + void afterUnit(std::string_view Name, const CompilationUnit &Unit, + const CompilationUnitPassResult &Result, std::uint64_t Nanoseconds) const; + void unitFailure(std::string_view Name, const CompilationUnit &Unit, const Error &ErrorValue, + std::uint64_t Nanoseconds = 0) const; + void beforeAnalysis(std::string_view Name, const CompilationUnit &Unit) const; + void afterAnalysis(std::string_view Name, const CompilationUnit &Unit, bool CacheHit, + std::uint64_t Nanoseconds) const; + void analysisFailure(std::string_view Name, const CompilationUnit &Unit, const Error &ErrorValue, + std::uint64_t Nanoseconds) const; + + [[nodiscard]] InstrumentationStatistic &statistic(std::string_view Name, bool IsAnalysis) const; + + mutable std::mutex Mutex; + mutable std::mutex ActionMutex; + std::vector<BeforeCallback> Before; + std::vector<AfterCallback> After; + std::vector<FailureCallback> Failure; + std::vector<BeforeAnalysisCallback> BeforeAnalysis; + std::vector<AfterAnalysisCallback> AfterAnalysis; + std::vector<AnalysisFailureCallback> AnalysisFailure; + std::vector<IRPrintCallback> IRPrint; + std::vector<ChangeCallback> Change; + ActionFilter Filter; + std::optional<std::uint64_t> PerFunctionFuel; + std::unordered_map<std::uint64_t, std::uint64_t> ConsumedFuel; + std::vector<MachineActionEvent> ActionEvents; + + std::vector<BeforeUnitCallback> BeforeUnit; + std::vector<AfterUnitCallback> AfterUnit; + std::vector<UnitFailureCallback> UnitFailure; + std::vector<BeforeUnitAnalysisCallback> BeforeUnitAnalysis; + std::vector<AfterUnitAnalysisCallback> AfterUnitAnalysis; + std::vector<UnitAnalysisFailureCallback> UnitAnalysisFailure; + mutable std::unordered_map<std::string, InstrumentationStatistic> Statistics; + + static thread_local BufferedEvents *ActiveBuffer; + + template <typename, typename> friend struct AnalysisManagerInstrumentation; + template <typename, typename, typename> friend struct PassManagerCallbacks; +}; + +class MachineActionReplay final { +public: + template <typename AnalysisManagerT> + explicit MachineActionReplay(AnalysisManagerT &Analyses) + : Request([&Analyses](std::string_view Rule, const MachineFunction &Function, + MachineInstrStableID Instruction, std::uint64_t Cost) { + return Analyses.requestAction(Rule, Function, Instruction, Cost); + }) {} + + template <typename AnalysisManagerT> + MachineActionReplay( + AnalysisManagerT &Analyses, + const std::unordered_map<MachineInstrStableID, MachineInstrStableID> &SourceToClone) + : MachineActionReplay(Analyses) { + for (const auto &[Source, Clone] : SourceToClone) + RecordingInstructionIDs.try_emplace(Clone, Source); + } + + [[nodiscard]] Expected<bool> request(std::string_view Rule, const MachineFunction &Function, + MachineInstrStableID Instruction = {}, + std::uint64_t Cost = 1); + void beginReplay() noexcept; + [[nodiscard]] Expected<void> finishReplay() const; + +private: + struct Decision final { + std::string Rule; + MachineFunctionStableID Function; + MachineInstrStableID Instruction; + std::uint64_t Cost = 0; + bool Accepted = false; + }; + + std::function<Expected<bool>(std::string_view, const MachineFunction &, MachineInstrStableID, + std::uint64_t)> + Request; + std::unordered_map<MachineInstrStableID, MachineInstrStableID> RecordingInstructionIDs; + std::vector<Decision> Decisions; + std::size_t NextDecision = 0; + bool IsReplaying = false; +}; + +} // namespace rcc + +#endif // RCC_IR_PASSINSTRUMENTATION_H diff --git a/backend/include/rcc/IR/PassManager.h b/backend/include/rcc/IR/PassManager.h new file mode 100644 index 0000000..b3ab088 --- /dev/null +++ b/backend/include/rcc/IR/PassManager.h @@ -0,0 +1,531 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_IR_PASSMANAGER_H +#define RCC_IR_PASSMANAGER_H + +#include "rcc/Support/Error.h" + +#include <algorithm> +#include <chrono> +#include <concepts> +#include <cstddef> +#include <cstdint> +#include <functional> +#include <memory> +#include <optional> +#include <ranges> +#include <set> +#include <span> +#include <string> +#include <string_view> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { + +class TargetDescription; + +using AnalysisID = const void *; + +class PreservedAnalyses final { +public: + [[nodiscard]] static PreservedAnalyses all() noexcept { + PreservedAnalyses Result; + Result.PreserveAll = true; + return Result; + } + + [[nodiscard]] static PreservedAnalyses none() noexcept { + return {}; + } + + void preserve(AnalysisID ID) { + if (ID != nullptr) + Preserved.insert(ID); + } + + template <typename AnalysisT> void preserve() { + preserve(analysisID<AnalysisT>()); + } + + [[nodiscard]] bool preserves(AnalysisID ID) const noexcept { + return PreserveAll || (ID != nullptr && Preserved.contains(ID)); + } + + [[nodiscard]] bool preservesAll() const noexcept { + return PreserveAll; + } + + template <typename AnalysisT> [[nodiscard]] static AnalysisID analysisID() noexcept { + static const std::uint8_t Token = 0; + return &Token; + } + +private: + bool PreserveAll = false; + std::unordered_set<AnalysisID> Preserved; +}; + +enum class PassThreadSafety : std::uint8_t { + NotThreadSafe, + ThreadSafe, +}; + +struct PassParameter final { + std::string Name; + std::string Description; + std::optional<std::string> DefaultValue; + bool Required = false; +}; + +template <typename IRUnitT, typename InstrumentationT> struct AnalysisManagerInstrumentation { + static void beforeAnalysis(InstrumentationT *, std::string_view, const IRUnitT &) {} + static void afterAnalysis(InstrumentationT *, std::string_view, const IRUnitT &, bool, + std::uint64_t) {} + static void analysisFailure(InstrumentationT *, std::string_view, const IRUnitT &, const Error &, + std::uint64_t) {} + + template <typename InstructionT> + [[nodiscard]] static Expected<bool> requestAction(InstrumentationT *, std::string_view, + std::string_view, const IRUnitT &, InstructionT, + std::uint64_t) { + return true; + } +}; + +template <typename ChangeT> struct AnalysisRegistration final { + AnalysisID ID = nullptr; + std::string Name; + std::vector<AnalysisID> Dependencies; + ChangeT InvalidatedBy = ChangeT::all(); + PassThreadSafety ThreadSafety = PassThreadSafety::NotThreadSafe; +}; + +template <typename IRUnitT, typename PassT, typename OptionsT> struct PassManagerCallbacks; + +template <typename IRUnitT, typename PassT, typename OptionsT> class PassManager { +public: + using PassList = std::vector<std::unique_ptr<PassT>>; + using Callbacks = PassManagerCallbacks<IRUnitT, PassT, OptionsT>; + + explicit PassManager(OptionsT Options = {}) : Options(Options) {} + PassManager(const PassManager &) = delete; + PassManager &operator=(const PassManager &) = delete; + PassManager(PassManager &&) = default; + PassManager &operator=(PassManager &&) = default; + ~PassManager() = default; + + [[nodiscard]] Expected<void> addPass(std::unique_ptr<PassT> Pass) { + if (!Pass) + return makeUnexpected(ErrorCode::InvalidArgument, "pass manager cannot add a null pass"); + auto Validation = Callbacks::validate(*Pass); + if (!Validation) + return std::unexpected(Validation.error()); + Passes.push_back(std::move(Pass)); + return {}; + } + + template <typename... Args> + [[nodiscard]] Expected<void> run(IRUnitT &Unit, Args &&...Arguments) const { + return Callbacks::run(Passes, Options, Unit, std::forward<Args>(Arguments)...); + } + + template <typename... Args> + [[nodiscard]] Expected<void> runFunctions(Args &&...Arguments) const + requires requires(const PassList &InputPasses, const OptionsT &InputOptions, + Args &&...InputArguments) { + Callbacks::runFunctions(InputPasses, InputOptions, std::forward<Args>(InputArguments)...); + } + { + return Callbacks::runFunctions(Passes, Options, std::forward<Args>(Arguments)...); + } + + [[nodiscard]] std::size_t size() const noexcept { + return Passes.size(); + } + + [[nodiscard]] PassList takePasses() && noexcept { + return std::move(Passes); + } + +private: + PassList Passes; + OptionsT Options; +}; + +template <typename IRUnitT, typename RegistrationT, typename ChangeT, typename InstrumentationT> +class AnalysisManager { +public: + using Self = AnalysisManager<IRUnitT, RegistrationT, ChangeT, InstrumentationT>; + + AnalysisManager() = default; + AnalysisManager(const AnalysisManager &) = delete; + AnalysisManager &operator=(const AnalysisManager &) = delete; + AnalysisManager(AnalysisManager &&) = delete; + AnalysisManager &operator=(AnalysisManager &&) = delete; + ~AnalysisManager() = default; + + template <typename AnalysisT> [[nodiscard]] static AnalysisID id() noexcept { + return PreservedAnalyses::analysisID<AnalysisT>(); + } + + template <typename AnalysisT> + [[nodiscard]] Expected<void> registerAnalysis(RegistrationT Registration = {}) { + using ResultT = typename AnalysisT::Result; + if (Registration.ID == nullptr) + Registration.ID = id<AnalysisT>(); + if (Registration.Name.empty()) { + if constexpr (requires { + { AnalysisT::name() } -> std::convertible_to<std::string_view>; + }) + Registration.Name = std::string(AnalysisT::name()); + else + Registration.Name = "unnamed-analysis"; + } + + ErasedRunner Runner = [](IRUnitT &Unit, const TargetDescription &Target, + Self &Manager) -> Expected<std::shared_ptr<void>> { + auto Computed = AnalysisT::run(Unit, Target, Manager); + if (!Computed) + return std::unexpected(Computed.error()); + return std::shared_ptr<void>(new ResultT(std::move(*Computed)), + [](void *Value) { delete static_cast<ResultT *>(Value); }); + }; + ErasedInvalidator Invalidator = [](void *Value, const IRUnitT &Unit, + const PreservedAnalyses &Preserved) -> bool { + if constexpr (requires(ResultT &Result, const IRUnitT &InputUnit, + const PreservedAnalyses &Analyses) { + { Result.invalidate(InputUnit, Analyses) } -> std::convertible_to<bool>; + }) + return static_cast<ResultT *>(Value)->invalidate(Unit, Preserved); + return true; + }; + return registerAnalysisImpl(std::move(Registration), std::move(Runner), std::move(Invalidator)); + } + + template <typename AnalysisT> + [[nodiscard]] Expected<typename AnalysisT::Result *> getResult(IRUnitT &Unit, + const TargetDescription &Target) { + const AnalysisID Key = id<AnalysisT>(); + if (!isRegistered(Key)) { + auto Registered = registerAnalysis<AnalysisT>(); + if (!Registered) + return std::unexpected(Registered.error()); + } + auto Result = getResultImpl(Key, Unit, Target); + if (!Result) + return std::unexpected(Result.error()); + return static_cast<typename AnalysisT::Result *>(*Result); + } + + [[nodiscard]] Expected<void *> getResultByID(AnalysisID ID, IRUnitT &Unit, + const TargetDescription &Target) { + return getResultImpl(ID, Unit, Target); + } + + void invalidate(IRUnitT &Unit, const PreservedAnalyses &Preserved, ChangeT Changes) noexcept { + const auto UnitPosition = Cache.find(&Unit); + if (UnitPosition == Cache.end() || Preserved.preservesAll() || Changes.empty()) + return; + + std::set<AnalysisID> Invalid; + for (auto &[ID, Entry] : UnitPosition->second) { + if (Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration == Registry.end() || + Registration->second.Info.InvalidatedBy.intersects(Changes)) { + const bool ShouldInvalidate = + Registration == Registry.end() || !Entry.Value || !Registration->second.Invalidator || + Registration->second.Invalidator(Entry.Value.get(), Unit, Preserved); + if (ShouldInvalidate) + Invalid.insert(ID); + } + } + + bool Added = true; + while (Added) { + Added = false; + for (const auto &[ID, Entry] : UnitPosition->second) { + (void)Entry; + if (Invalid.contains(ID) || Preserved.preserves(ID)) + continue; + const auto Registration = Registry.find(ID); + if (Registration != Registry.end() && + std::ranges::any_of( + Registration->second.Info.Dependencies, + [&Invalid](AnalysisID Dependency) { return Invalid.contains(Dependency); })) + Added = Invalid.insert(ID).second || Added; + } + } + + for (const AnalysisID ID : Invalid) + UnitPosition->second.erase(ID); + if (UnitPosition->second.empty()) + Cache.erase(UnitPosition); + } + + void invalidate(IRUnitT &Unit, const PreservedAnalyses &Preserved) noexcept { + invalidate(Unit, Preserved, ChangeT::all()); + } + + [[nodiscard]] bool hasCached(const IRUnitT &Unit, AnalysisID ID) const noexcept { + const auto UnitPosition = Cache.find(const_cast<IRUnitT *>(&Unit)); + if (UnitPosition == Cache.end()) + return false; + const auto AnalysisPosition = UnitPosition->second.find(ID); + return AnalysisPosition != UnitPosition->second.end() && AnalysisPosition->second.Value; + } + + [[nodiscard]] std::size_t cachedResultCount(const IRUnitT &Unit) const noexcept { + const auto Position = Cache.find(const_cast<IRUnitT *>(&Unit)); + return Position == Cache.end() ? 0 : Position->second.size(); + } + + [[nodiscard]] bool isRegistered(AnalysisID ID) const noexcept { + return ID != nullptr && Registry.contains(ID); + } + + void clear(IRUnitT &Unit) noexcept { + Cache.erase(&Unit); + ActiveComputations.erase(&Unit); + } + + void clearAll() noexcept { + Cache.clear(); + ActiveComputations.clear(); + } + + [[nodiscard]] Expected<std::unique_ptr<Self>> forkEmpty() const { + if (!ActiveComputations.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, + "cannot fork an analysis manager during analysis computation"); + auto Result = std::make_unique<Self>(); + Result->Registry = Registry; + return Result; + } + + [[nodiscard]] Expected<void> replaceRegistrations(Self &&Source) { + if (!Cache.empty() || !ActiveComputations.empty() || !Source.Cache.empty() || + !Source.ActiveComputations.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, + "analysis registrations can only be replaced on empty managers"); + Registry = std::move(Source.Registry); + return {}; + } + + [[nodiscard]] Expected<void> + validateParallelRequirements(std::span<const AnalysisID> RequiredAnalyses) const { + std::vector<AnalysisID> Worklist(RequiredAnalyses.begin(), RequiredAnalyses.end()); + std::unordered_set<AnalysisID> Visited; + for (std::size_t Index = 0; Index < Worklist.size(); ++Index) { + const AnalysisID ID = Worklist[Index]; + if (ID == nullptr || !Visited.insert(ID).second) + continue; + const auto Position = Registry.find(ID); + if (Position == Registry.end()) + return makeUnexpected(ErrorCode::InvalidArgument, + "parallel pass requires an unregistered analysis"); + if (Position->second.Info.ThreadSafety != PassThreadSafety::ThreadSafe) + return makeUnexpected(ErrorCode::InvalidArgument, "parallel pipeline requires analysis '" + + Position->second.Info.Name + + "' to be marked thread-safe"); + Worklist.insert(Worklist.end(), Position->second.Info.Dependencies.begin(), + Position->second.Info.Dependencies.end()); + } + return {}; + } + + void setInstrumentation(InstrumentationT *NewInstrumentation) noexcept { + Instrumentation = NewInstrumentation; + } + + void setActivePass(std::string Name) { + ActivePass = std::move(Name); + } + + template <typename InstructionT> + [[nodiscard]] Expected<bool> requestAction(std::string_view Rule, const IRUnitT &Unit, + InstructionT Instruction, std::uint64_t Cost = 1) { + if (Rule.empty() || Cost == 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "pass action requires a name and nonzero cost"); + if (Instrumentation == nullptr) + return true; + return AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::requestAction( + Instrumentation, ActivePass.empty() ? "unscoped" : ActivePass, Rule, Unit, Instruction, + Cost); + } + + [[nodiscard]] Expected<bool> requestAction(std::string_view Rule, const IRUnitT &Unit, + std::uint64_t Cost = 1) { + if (Rule.empty() || Cost == 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "pass action requires a name and nonzero cost"); + if (Instrumentation == nullptr) + return true; + return AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::requestAction( + Instrumentation, ActivePass.empty() ? "unscoped" : ActivePass, Rule, Unit, nullptr, Cost); + } + + [[nodiscard]] const std::string &activePass() const noexcept { + return ActivePass; + } + +private: + using ErasedRunner = + std::function<Expected<std::shared_ptr<void>>(IRUnitT &, const TargetDescription &, Self &)>; + using ErasedInvalidator = std::function<bool(void *, const IRUnitT &, const PreservedAnalyses &)>; + + struct RegisteredAnalysis final { + RegistrationT Info; + ErasedRunner Runner; + ErasedInvalidator Invalidator; + }; + + struct CacheEntry final { + std::shared_ptr<void> Value; + AnalysisID ID = nullptr; + }; + + [[nodiscard]] static bool hasDuplicateAnalysisIDs(std::span<const AnalysisID> IDs) { + std::unordered_set<AnalysisID> Unique; + for (const AnalysisID ID : IDs) { + if (ID == nullptr || !Unique.insert(ID).second) + return true; + } + return false; + } + + [[nodiscard]] Expected<void> registerAnalysisImpl(RegistrationT Registration, ErasedRunner Runner, + ErasedInvalidator Invalidator) { + if (Registration.ID == nullptr || Registration.Name.empty() || !Runner || !Invalidator) + return makeUnexpected(ErrorCode::InvalidArgument, "analysis registration is incomplete"); + if (hasDuplicateAnalysisIDs(Registration.Dependencies)) + return makeUnexpected(ErrorCode::InvalidArgument, + "analysis dependencies must be non-null and unique"); + if (std::ranges::find(Registration.Dependencies, Registration.ID) != + Registration.Dependencies.end()) + return makeUnexpected(ErrorCode::InvalidArgument, + "analysis cannot directly depend on itself"); + if (Registry.contains(Registration.ID)) + return makeUnexpected(ErrorCode::InvalidArgument, "analysis ID is already registered"); + if (std::ranges::any_of(Registry, [&Registration](const auto &Entry) { + return Entry.second.Info.Name == Registration.Name; + })) + return makeUnexpected(ErrorCode::InvalidArgument, "analysis name is already registered"); + Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner), + std::move(Invalidator)}); + return {}; + } + + [[nodiscard]] Expected<void *> getResultImpl(AnalysisID ID, IRUnitT &Unit, + const TargetDescription &Target) { + if (ID == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "analysis ID cannot be null"); + auto &UnitCache = Cache[&Unit]; + if (const auto Cached = UnitCache.find(ID); Cached != UnitCache.end() && Cached->second.Value) { + const auto Registration = Registry.find(ID); + const std::string_view Name = Registration == Registry.end() + ? std::string_view{"unknown-analysis"} + : std::string_view{Registration->second.Info.Name}; + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::afterAnalysis( + Instrumentation, Name, Unit, true, 0); + return Cached->second.Value.get(); + } + + const auto RegistrationPosition = Registry.find(ID); + if (RegistrationPosition == Registry.end()) + return makeUnexpected(ErrorCode::InvalidArgument, "analysis ID is not registered"); + const RegisteredAnalysis &Registration = RegistrationPosition->second; + auto &Stack = ActiveComputations[&Unit]; + if (std::ranges::find(Stack, ID) != Stack.end()) { + Error Failure(ErrorCode::InvalidArgument, + "analysis dependency cycle reaches '" + Registration.Info.Name + "'"); + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::analysisFailure( + Instrumentation, Registration.Info.Name, Unit, Failure, 0); + return std::unexpected(std::move(Failure)); + } + + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::beforeAnalysis( + Instrumentation, Registration.Info.Name, Unit); + const auto Start = std::chrono::steady_clock::now(); + Stack.push_back(ID); + for (const AnalysisID Dependency : Registration.Info.Dependencies) { + if (!Registry.contains(Dependency)) { + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Unit); + return makeUnexpected(ErrorCode::InvalidArgument, + "analysis depends on an unregistered analysis"); + } + auto DependencyResult = getResultImpl(Dependency, Unit, Target); + if (!DependencyResult) { + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Unit); + Error Failure = DependencyResult.error(); + std::string Message = "analysis '" + Registration.Info.Name + "' failed: "; + Message.append(Failure.message()); + Failure = Error(Failure.code(), std::move(Message)); + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::analysisFailure( + Instrumentation, Registration.Info.Name, Unit, Failure, elapsedNanoseconds(Start)); + return std::unexpected(std::move(Failure)); + } + } + + auto Computed = Registration.Runner(Unit, Target, *this); + Stack.pop_back(); + if (Stack.empty()) + ActiveComputations.erase(&Unit); + const std::uint64_t Duration = elapsedNanoseconds(Start); + if (!Computed) { + Error Failure = Computed.error(); + std::string Message = "analysis '" + Registration.Info.Name + "' failed: "; + Message.append(Failure.message()); + Failure = Error(Failure.code(), std::move(Message)); + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::analysisFailure( + Instrumentation, Registration.Info.Name, Unit, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + if (!*Computed) { + Error Failure(ErrorCode::InternalError, + "analysis '" + Registration.Info.Name + "' returned a null result"); + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::analysisFailure( + Instrumentation, Registration.Info.Name, Unit, Failure, Duration); + return std::unexpected(std::move(Failure)); + } + + void *Result = Computed->get(); + UnitCache.emplace(ID, CacheEntry{std::move(*Computed), ID}); + if (Instrumentation != nullptr) + AnalysisManagerInstrumentation<IRUnitT, InstrumentationT>::afterAnalysis( + Instrumentation, Registration.Info.Name, Unit, false, Duration); + return Result; + } + + [[nodiscard]] static std::uint64_t + elapsedNanoseconds(std::chrono::steady_clock::time_point Start) noexcept { + const auto Elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>( + std::chrono::steady_clock::now() - Start); + return Elapsed.count() <= 0 ? 0 : static_cast<std::uint64_t>(Elapsed.count()); + } + + std::unordered_map<AnalysisID, RegisteredAnalysis> Registry; + std::unordered_map<IRUnitT *, std::unordered_map<AnalysisID, CacheEntry>> Cache; + std::unordered_map<IRUnitT *, std::vector<AnalysisID>> ActiveComputations; + InstrumentationT *Instrumentation = nullptr; + std::string ActivePass; +}; + +} // namespace rcc + +#endif // RCC_IR_PASSMANAGER_H |