diff options
Diffstat (limited to 'backend/lib/CodeGen/TargetSchedulingModel.cpp')
| -rw-r--r-- | backend/lib/CodeGen/TargetSchedulingModel.cpp | 260 |
1 files changed, 260 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/TargetSchedulingModel.cpp b/backend/lib/CodeGen/TargetSchedulingModel.cpp new file mode 100644 index 0000000..97abecd --- /dev/null +++ b/backend/lib/CodeGen/TargetSchedulingModel.cpp @@ -0,0 +1,260 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TargetSchedulingModel.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <functional> +#include <limits> +#include <memory> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <utility> + +namespace rcc { +namespace { + +template <typename IDT> [[nodiscard]] bool isValidID(IDT ID) noexcept { + return ID.value() != 0; +} + +} // namespace + +Expected<ScheduleHazardType> +TargetScheduleHazardRecognizer::getHazardType(const ScheduleUnit &) const { + return ScheduleHazardType::NoHazard; +} + +Expected<void> TargetScheduleHazardRecognizer::emitInstruction(const ScheduleUnit &) { + return {}; +} + +Expected<void> TargetScheduleHazardRecognizer::advanceCycle() { + return {}; +} + +Expected<void> TargetScheduleHazardRecognizer::recedeCycle() { + return {}; +} + +Expected<void> TargetScheduleHazardRecognizer::reset() { + return {}; +} + +bool TargetSchedulingHooks::isSchedulingBoundary(const MachineInstr &, + const TargetDescription &) const noexcept { + return false; +} + +Expected<void> TargetSchedulingHooks::mutateScheduleDAG(ScheduleDAG &, const MachineFunction &, + const TargetDescription &, + ScheduleDAGMode) const { + return {}; +} + +std::int64_t TargetSchedulingHooks::candidatePreference(const ScheduleUnit &, ScheduleDirection, + const MachineBasicBlock &, + std::uint64_t) const noexcept { + return 0; +} + +std::unique_ptr<TargetScheduleHazardRecognizer> +TargetSchedulingHooks::createHazardRecognizer(ScheduleDirection) const { + return nullptr; +} + +Expected<TargetSchedulingModel> +TargetSchedulingModel::create(TargetSchedulingModelDesc Description) { + if (Description.IssueWidth == 0 || Description.DispatchLimit == 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target scheduling model requires nonzero issue and dispatch widths"); + } + + TargetSchedulingModel Result(std::move(Description)); + std::unordered_set<std::string> Names; + for (std::size_t Index = 0; Index < Result.Description.ProcessorResources.size(); ++Index) { + const ProcessorResourceDesc &Resource = Result.Description.ProcessorResources[Index]; + if (!isValidID(Resource.ID) || Resource.Name.empty() || Resource.Units == 0 || + !Result.ResourceToIndex.emplace(Resource.ID, Index).second || + !Names.insert(Resource.Name).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target scheduling model has an invalid processor resource"); + } + } + for (const ProcessorResourceDesc &Resource : Result.Description.ProcessorResources) { + if (Resource.Parent && + (Resource.Parent == Resource.ID || !Result.ResourceToIndex.contains(*Resource.Parent))) { + return makeUnexpected(ErrorCode::InvalidArgument, + "processor resource has an invalid parent resource"); + } + std::unordered_set<ProcessorResourceID> Path; + const ProcessorResourceDesc *Current = &Resource; + while (Current->Parent) { + if (!Path.insert(Current->ID).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "processor resource hierarchy contains a cycle"); + } + Current = &Result.Description.ProcessorResources[Result.ResourceToIndex.at(*Current->Parent)]; + } + } + + Names.clear(); + for (std::size_t Index = 0; Index < Result.Description.SchedulingClasses.size(); ++Index) { + SchedulingClassModelDesc &Class = Result.Description.SchedulingClasses[Index]; + if (!isValidID(Class.ID) || Class.Name.empty() || Class.MicroOps == 0 || Class.Latency == 0 || + !Result.ClassToIndex.emplace(Class.ID, Index).second || !Names.insert(Class.Name).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target scheduling model has an invalid scheduling class"); + } + } + for (SchedulingClassModelDesc &Class : Result.Description.SchedulingClasses) { + std::unordered_set<ProcessorResourceID> UsedResources; + for (const SchedulingResourceUse &Use : Class.Resources) { + if (!isValidID(Use.Resource) || Use.Cycles == 0 || + !Result.ResourceToIndex.contains(Use.Resource) || + !UsedResources.insert(Use.Resource).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "scheduling class has an invalid resource use"); + } + } + std::ranges::sort(Class.Resources, {}, + [](const SchedulingResourceUse &Use) { return Use.Resource.value(); }); + + std::unordered_set<std::uint32_t> WriteOperands; + for (const SchedulingWriteLatency &Latency : Class.WriteLatencies) { + if (!WriteOperands.insert(Latency.OperandIndex).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "scheduling class has duplicate write latencies"); + } + } + std::ranges::sort(Class.WriteLatencies, {}, &SchedulingWriteLatency::OperandIndex); + + std::unordered_set<std::uint64_t> ReadAdvanceKeys; + for (const SchedulingReadAdvance &Advance : Class.ReadAdvances) { + if (Advance.ProducerClass && !Result.ClassToIndex.contains(*Advance.ProducerClass)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "read advance references an unknown producer class"); + } + const std::uint64_t Producer = Advance.ProducerClass ? Advance.ProducerClass->value() : 0; + const std::uint64_t Key = (Producer << 32U) | Advance.OperandIndex; + if (!ReadAdvanceKeys.insert(Key).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "scheduling class has duplicate read advances"); + } + } + std::ranges::sort(Class.ReadAdvances, + [](const SchedulingReadAdvance &Left, const SchedulingReadAdvance &Right) { + if (Left.OperandIndex != Right.OperandIndex) + return Left.OperandIndex < Right.OperandIndex; + return Left.ProducerClass.value_or(SchedulingClassID{}).value() < + Right.ProducerClass.value_or(SchedulingClassID{}).value(); + }); + } + + Names.clear(); + for (std::size_t Index = 0; Index < Result.Description.PressureSets.size(); ++Index) { + RegisterPressureSetDesc &Set = Result.Description.PressureSets[Index]; + if (!isValidID(Set.ID) || Set.Name.empty() || Set.Limit == 0 || Set.RegisterClasses.empty() || + !Result.PressureSetToIndex.emplace(Set.ID, Index).second || + !Names.insert(Set.Name).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target scheduling model has an invalid register pressure set"); + } + std::ranges::sort(Set.RegisterClasses, [](RegisterClassID Left, RegisterClassID Right) { + return Left.value() < Right.value(); + }); + if (std::ranges::adjacent_find(Set.RegisterClasses) != Set.RegisterClasses.end() || + std::ranges::any_of(Set.RegisterClasses, + [](RegisterClassID Class) { return !isValidID(Class); })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register pressure set has duplicate or invalid register classes"); + } + for (const RegisterClassID Class : Set.RegisterClasses) + Result.ClassToPressureSets[Class].push_back(Set.ID); + } + for (auto &[Class, Sets] : Result.ClassToPressureSets) { + (void)Class; + std::ranges::sort(Sets, [](RegisterPressureSetID Left, RegisterPressureSetID Right) { + return Left.value() < Right.value(); + }); + } + return Result; +} + +const ProcessorResourceDesc * +TargetSchedulingModel::processorResource(ProcessorResourceID ID) const noexcept { + const auto Position = ResourceToIndex.find(ID); + return Position == ResourceToIndex.end() ? nullptr + : &Description.ProcessorResources[Position->second]; +} + +const SchedulingClassModelDesc * +TargetSchedulingModel::schedulingClass(SchedulingClassID ID) const noexcept { + const auto Position = ClassToIndex.find(ID); + return Position == ClassToIndex.end() ? nullptr + : &Description.SchedulingClasses[Position->second]; +} + +const RegisterPressureSetDesc * +TargetSchedulingModel::pressureSet(RegisterPressureSetID ID) const noexcept { + const auto Position = PressureSetToIndex.find(ID); + return Position == PressureSetToIndex.end() ? nullptr + : &Description.PressureSets[Position->second]; +} + +std::span<const RegisterPressureSetID> +TargetSchedulingModel::pressureSetsForClass(RegisterClassID Class) const noexcept { + const auto Position = ClassToPressureSets.find(Class); + return Position == ClassToPressureSets.end() + ? std::span<const RegisterPressureSetID>{} + : std::span<const RegisterPressureSetID>(Position->second); +} + +Expected<std::uint32_t> TargetSchedulingModel::operandLatency(SchedulingClassID ProducerClass, + std::size_t DefinitionOperand, + SchedulingClassID ConsumerClass, + std::size_t UseOperand) const { + if (DefinitionOperand > std::numeric_limits<std::uint32_t>::max() || + UseOperand > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::SchedulingFailed, + "scheduling operand index exceeds the target model range"); + } + const SchedulingClassModelDesc *Producer = schedulingClass(ProducerClass); + const SchedulingClassModelDesc *Consumer = schedulingClass(ConsumerClass); + if (Producer == nullptr || Consumer == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "operand latency references an unknown scheduling class"); + } + + const std::uint32_t DefinitionIndex = static_cast<std::uint32_t>(DefinitionOperand); + const std::uint32_t UseIndex = static_cast<std::uint32_t>(UseOperand); + std::uint32_t Latency = Producer->Latency; + if (const auto Position = std::ranges::find(Producer->WriteLatencies, DefinitionIndex, + &SchedulingWriteLatency::OperandIndex); + Position != Producer->WriteLatencies.end()) { + Latency = Position->Cycles; + } + + const SchedulingReadAdvance *Wildcard = nullptr; + const SchedulingReadAdvance *Exact = nullptr; + for (const SchedulingReadAdvance &Advance : Consumer->ReadAdvances) { + if (Advance.OperandIndex != UseIndex) + continue; + if (!Advance.ProducerClass) + Wildcard = &Advance; + else if (*Advance.ProducerClass == ProducerClass) + Exact = &Advance; + } + const SchedulingReadAdvance *Advance = Exact != nullptr ? Exact : Wildcard; + return Advance == nullptr || Advance->Cycles >= Latency ? (Advance == nullptr ? Latency : 0U) + : Latency - Advance->Cycles; +} + +const TargetSchedulingHooks &TargetSchedulingModel::hooks() const noexcept { + static const TargetSchedulingHooks DefaultHooks; + return Description.Hooks == nullptr ? DefaultHooks : *Description.Hooks; +} + +} // namespace rcc |