diff options
Diffstat (limited to 'backend/lib/CodeGen/ScheduleDAG.cpp')
| -rw-r--r-- | backend/lib/CodeGen/ScheduleDAG.cpp | 637 |
1 files changed, 637 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/ScheduleDAG.cpp b/backend/lib/CodeGen/ScheduleDAG.cpp new file mode 100644 index 0000000..9fba862 --- /dev/null +++ b/backend/lib/CodeGen/ScheduleDAG.cpp @@ -0,0 +1,637 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/ScheduleDAG.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineAnalyses.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <span> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +struct RegisterDependencyKey final { + bool IsUnit = false; + std::uint32_t Value = 0; + + friend constexpr bool operator==(RegisterDependencyKey, RegisterDependencyKey) noexcept = default; +}; + +struct RegisterDependencyKeyHash final { + [[nodiscard]] std::size_t operator()(RegisterDependencyKey Key) const noexcept { + const std::uint64_t Value = (static_cast<std::uint64_t>(Key.IsUnit) << 32U) | Key.Value; + return std::hash<std::uint64_t>{}(Value); + } +}; + +struct RegisterDependencyState final { + struct Definition final { + std::size_t Unit = 0; + MachineInstr *Instruction = nullptr; + std::size_t OperandIndex = 0; + }; + + std::optional<Definition> LastDefinition; + std::vector<std::size_t> LastUses; +}; + +struct RegisterAccess final { + RegisterDependencyKey Key; + MachineInstr *Instruction = nullptr; + std::size_t OperandIndex = 0; +}; + +[[nodiscard]] bool keyLess(RegisterDependencyKey Left, RegisterDependencyKey Right) noexcept { + return Left.IsUnit == Right.IsUnit ? Left.Value < Right.Value : Left.IsUnit < Right.IsUnit; +} + +[[nodiscard]] std::uint32_t saturatingAdd(std::uint32_t Left, std::uint32_t Right) noexcept { + return std::numeric_limits<std::uint32_t>::max() - Left < Right + ? std::numeric_limits<std::uint32_t>::max() + : Left + Right; +} + +[[nodiscard]] std::uint64_t saturatingAdd(std::uint64_t Left, std::uint64_t Right) noexcept { + return std::numeric_limits<std::uint64_t>::max() - Left < Right + ? std::numeric_limits<std::uint64_t>::max() + : Left + Right; +} + +[[nodiscard]] Expected<std::vector<RegisterDependencyKey>> +operandKeys(const MachineOperand &Operand, const MachineFunction &Function, + const TargetDescription &Target, ScheduleDAGMode Mode) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + return std::vector<RegisterDependencyKey>{}; + if (Reg->isVirtual()) { + if (Mode == ScheduleDAGMode::PostRegisterAllocation) { + return makeUnexpected(ErrorCode::VerificationError, + "post-RA scheduling region contains a virtual register"); + } + if (!Function.registerInfo().isKnownVirtualRegister(*Reg)) { + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown virtual register"); + } + return std::vector<RegisterDependencyKey>{{false, Reg->opaqueValue()}}; + } + + std::optional<PhysicalRegister> Physical = Reg->physicalRegister(); + if (!Physical) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an invalid physical register"); + if (Operand.subReg().value() != 0) { + const std::optional<PhysicalRegister> SubReg = + Target.registers().subRegister(*Physical, Operand.subReg()); + if (!SubReg) { + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an invalid physical subregister"); + } + Physical = SubReg; + } + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(*Physical); + if (Description == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown physical register"); + std::vector<RegisterDependencyKey> Result; + Result.reserve(Description->Units.size()); + for (const RegisterUnitLane &Unit : Description->Units) + Result.push_back({true, Unit.Unit.value()}); + std::ranges::sort(Result, {}, &RegisterDependencyKey::Value); + const auto [FirstDuplicate, End] = std::ranges::unique(Result); + Result.erase(FirstDuplicate, End); + return Result; +} + +[[nodiscard]] Expected<std::vector<RegisterDependencyKey>> +maskKeys(const RegisterMask &Mask, const TargetDescription &Target) { + std::vector<RegisterDependencyKey> Result; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (!Mask.clobbers(Register.Reg)) + continue; + for (const RegisterUnitLane &Unit : Register.Units) + Result.push_back({true, Unit.Unit.value()}); + } + std::ranges::sort(Result, {}, &RegisterDependencyKey::Value); + const auto [FirstDuplicate, End] = std::ranges::unique(Result); + Result.erase(FirstDuplicate, End); + return Result; +} + +[[nodiscard]] bool mayAlias(const MachineInstr &Earlier, const MachineInstr &Later, + const MachineAliasAnalysis::Result &Aliases) noexcept { + if (Earlier.memOperands().empty() || Later.memOperands().empty()) + return true; + for (const MachineMemOperand *Left : Earlier.memOperands()) { + if (Left == nullptr) + return true; + for (const MachineMemOperand *Right : Later.memOperands()) { + if (Right == nullptr || Aliases.alias(*Left, *Right) != MachineAliasResult::NoAlias) + return true; + } + } + return false; +} + +[[nodiscard]] bool hasOrderedMemory(const MachineInstr &Instruction) noexcept { + return std::ranges::any_of(Instruction.memOperands(), [](const MachineMemOperand *Memory) { + return Memory == nullptr || Memory->isAtomic() || Memory->isVolatile(); + }); +} + +[[nodiscard]] bool hasLoad(const MachineInstr &Instruction) noexcept { + return std::ranges::any_of(Instruction.memOperands(), [](const MachineMemOperand *Memory) { + return Memory == nullptr || Memory->isLoad(); + }); +} + +[[nodiscard]] bool hasStore(const MachineInstr &Instruction) noexcept { + return std::ranges::any_of(Instruction.memOperands(), [](const MachineMemOperand *Memory) { + return Memory == nullptr || Memory->isStore(); + }); +} + +[[nodiscard]] bool isHazardDependency(ScheduleDependencyKind Kind) noexcept { + return Kind == ScheduleDependencyKind::Anti || Kind == ScheduleDependencyKind::Output; +} + +} // namespace + +Expected<ScheduleDAG> +ScheduleDAG::build(MachineBasicBlock &Block, std::span<MachineInstr *const> Instructions, + const MachineFunction &Function, const TargetDescription &Target, + const TargetSchedulingModel &Model, ScheduleDAGMode Mode, bool EmitDebugOutput) { + if (&Block.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "schedule DAG block belongs to another function"); + ScheduleDAG Result(Block); + auto Units = Result.buildUnits(Instructions, Target, Model); + if (!Units) + return std::unexpected(Units.error()); + auto Registers = Result.buildRegisterDependencies(Function, Target, Model, Mode); + if (!Registers) + return std::unexpected(Registers.error()); + auto Memory = Result.buildMemoryDependencies(Target); + if (!Memory) + return std::unexpected(Memory.error()); + auto Order = Result.buildOrderDependencies(Target); + if (!Order) + return std::unexpected(Order.error()); + auto Mutated = Model.hooks().mutateScheduleDAG(Result, Function, Target, Mode, EmitDebugOutput); + if (!Mutated) + return std::unexpected(Mutated.error()); + auto CriticalPaths = Result.computeCriticalPaths(); + if (!CriticalPaths) + return std::unexpected(CriticalPaths.error()); + return Result; +} + +Expected<void> ScheduleDAG::buildUnits(std::span<MachineInstr *const> Instructions, + const TargetDescription &Target, + const TargetSchedulingModel &Model) { + MachineInstr *ExpectedInstruction = Instructions.empty() ? nullptr : Instructions.front(); + for (std::size_t Index = 0; Index < Instructions.size();) { + MachineInstr *Instruction = Instructions[Index]; + if (Instruction == nullptr || Instruction->parent() != Block) + return makeUnexpected(ErrorCode::InvalidArgument, + "schedule region contains a detached or foreign instruction"); + if (Instruction != ExpectedInstruction) { + return makeUnexpected(ErrorCode::InvalidArgument, + "schedule region is not a contiguous instruction sequence"); + } + if (Instruction->flags().has(MachineInstrFlag::BundledWithPred)) { + return makeUnexpected(ErrorCode::VerificationError, + "schedule region begins in the middle of an instruction bundle"); + } + + ScheduleUnit Unit; + Unit.ID = Units.size(); + Unit.StableID = Instruction->stableID(); + std::unordered_map<ProcessorResourceID, std::uint32_t> ResourceCycles; + for (;;) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown instruction descriptor"); + } + const SchedulingClassModelDesc *Class = Model.schedulingClass(Descriptor->SchedulingClass); + if (Class == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction references an unknown scheduling class"); + } + Unit.MicroOps = saturatingAdd(Unit.MicroOps, Class->MicroOps); + Unit.Latency = std::max(Unit.Latency, Class->Latency); + for (const SchedulingResourceUse &Use : Class->Resources) { + ResourceCycles[Use.Resource] = saturatingAdd(ResourceCycles[Use.Resource], Use.Cycles); + } + Unit.Instructions.push_back(Instruction); + const bool HasSuccessor = Instruction->flags().has(MachineInstrFlag::BundledWithSucc); + ++Index; + if (!HasSuccessor) + break; + if (Index >= Instructions.size()) { + return makeUnexpected(ErrorCode::VerificationError, + "schedule region ends in the middle of an instruction bundle"); + } + MachineInstr *Next = Instructions[Index]; + if (Next == nullptr || Next->parent() != Block || + !Next->flags().has(MachineInstrFlag::BundledWithPred) || Instruction->next() != Next) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction bundle links are not reciprocal and contiguous"); + } + Instruction = Next; + } + Unit.Resources.reserve(ResourceCycles.size()); + for (const auto &[Resource, Cycles] : ResourceCycles) + Unit.Resources.push_back({Resource, Cycles}); + std::ranges::sort(Unit.Resources, {}, &SchedulingResourceUse::Resource); + ExpectedInstruction = Unit.Instructions.back()->next(); + Units.push_back(std::move(Unit)); + } + return {}; +} + +Expected<void> ScheduleDAG::buildRegisterDependencies(const MachineFunction &Function, + const TargetDescription &Target, + const TargetSchedulingModel &Model, + ScheduleDAGMode Mode) { + std::unordered_map<RegisterDependencyKey, RegisterDependencyState, RegisterDependencyKeyHash> + States; + for (ScheduleUnit &Unit : Units) { + std::vector<RegisterAccess> Uses; + std::vector<RegisterAccess> Definitions; + for (MachineInstr *Instruction : Unit.Instructions) { + for (std::size_t OperandIndex = 0; OperandIndex < Instruction->operandCount(); + ++OperandIndex) { + const MachineOperand *Operand = Instruction->operandAt(OperandIndex); + if (Operand == nullptr) + continue; + if (const auto *Mask = Operand->getIf<RegisterMaskOperand>()) { + if (!Mask->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered a null register mask"); + auto Keys = maskKeys(*Mask->Mask, Target); + if (!Keys) + return std::unexpected(Keys.error()); + for (const RegisterDependencyKey Key : *Keys) + Definitions.push_back({Key, Instruction, OperandIndex}); + continue; + } + if (const auto *Mask = Operand->getIf<LiveOutRegisterMaskOperand>()) { + if (!Mask->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered a null live-out register mask"); + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (!Mask->Mask->preserves(Register.Reg)) + continue; + for (const RegisterUnitLane &RegisterUnit : Register.Units) + Uses.push_back({{true, RegisterUnit.Unit.value()}, Instruction, OperandIndex}); + } + continue; + } + if (!Operand->isRegister() || Operand->isDebugUse() || + Operand->registerFlags().has(RegisterOperandFlag::Undef)) { + continue; + } + auto Keys = operandKeys(*Operand, Function, Target, Mode); + if (!Keys) + return std::unexpected(Keys.error()); + if (Operand->isUse()) { + for (const RegisterDependencyKey Key : *Keys) + Uses.push_back({Key, Instruction, OperandIndex}); + } + if (Operand->isDef()) { + for (const RegisterDependencyKey Key : *Keys) + Definitions.push_back({Key, Instruction, OperandIndex}); + } + } + } + std::ranges::stable_sort(Uses, [](const RegisterAccess &Left, const RegisterAccess &Right) { + return keyLess(Left.Key, Right.Key); + }); + std::ranges::stable_sort(Definitions, + [](const RegisterAccess &Left, const RegisterAccess &Right) { + return keyLess(Left.Key, Right.Key); + }); + + for (std::size_t Begin = 0; Begin < Uses.size();) { + std::size_t End = Begin + 1; + while (End < Uses.size() && Uses[End].Key == Uses[Begin].Key) + ++End; + RegisterDependencyState &State = States[Uses[Begin].Key]; + if (State.LastDefinition) { + std::uint32_t Latency = 0; + for (std::size_t Index = Begin; Index < End; ++Index) { + const InstructionDescriptor *Producer = + Target.instructionDescriptor(State.LastDefinition->Instruction->opcode()); + const InstructionDescriptor *Consumer = + Target.instructionDescriptor(Uses[Index].Instruction->opcode()); + if (Producer == nullptr || Consumer == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "scheduler latency lookup encountered an unknown instruction"); + } + auto OperandLatency = + Model.operandLatency(Producer->SchedulingClass, State.LastDefinition->OperandIndex, + Consumer->SchedulingClass, Uses[Index].OperandIndex); + if (!OperandLatency) + return std::unexpected(OperandLatency.error()); + Latency = std::max(Latency, *OperandLatency); + } + addDependency(State.LastDefinition->Unit, Unit.ID, + Uses[Begin].Key.IsUnit ? ScheduleDependencyKind::RegisterUnit + : ScheduleDependencyKind::Data, + Latency); + } + if (State.LastUses.empty() || State.LastUses.back() != Unit.ID) + State.LastUses.push_back(Unit.ID); + Begin = End; + } + + for (std::size_t Begin = 0; Begin < Definitions.size();) { + std::size_t End = Begin + 1; + while (End < Definitions.size() && Definitions[End].Key == Definitions[Begin].Key) { + ++End; + } + RegisterDependencyState &State = States[Definitions[Begin].Key]; + if (State.LastDefinition) { + addDependency(State.LastDefinition->Unit, Unit.ID, ScheduleDependencyKind::Output, 0); + } + for (const std::size_t Use : State.LastUses) + addDependency(Use, Unit.ID, ScheduleDependencyKind::Anti, 0); + State.LastUses.clear(); + const RegisterAccess &Last = Definitions[End - 1]; + State.LastDefinition = + RegisterDependencyState::Definition{Unit.ID, Last.Instruction, Last.OperandIndex}; + Begin = End; + } + } + return {}; +} + +Expected<void> ScheduleDAG::addArtificialDependency(std::size_t Source, std::size_t Destination, + std::uint32_t Latency) { + if (Source >= Units.size() || Destination >= Units.size() || Source == Destination) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target schedule mutation requires distinct known schedule units"); + } + if (hasPath(Destination, Source)) + return makeUnexpected(ErrorCode::SchedulingFailed, + "target schedule mutation would introduce a dependency cycle"); + addDependency(Source, Destination, ScheduleDependencyKind::Artificial, Latency); + return {}; +} + +bool ScheduleDAG::hasPath(std::size_t Source, std::size_t Destination) const { + if (Source >= Units.size() || Destination >= Units.size()) + return false; + std::vector<bool> Visited(Units.size()); + std::vector<std::size_t> Pending = {Source}; + Visited[Source] = true; + while (!Pending.empty()) { + const std::size_t Current = Pending.back(); + Pending.pop_back(); + for (const ScheduleDependency &Dependency : Units[Current].Successors) { + if (Dependency.Destination == Destination) + return true; + if (!Visited[Dependency.Destination]) { + Visited[Dependency.Destination] = true; + Pending.push_back(Dependency.Destination); + } + } + } + return false; +} + +bool ScheduleDAG::hasDirectDependency(std::size_t Source, std::size_t Destination) const { + if (Source >= Units.size() || Destination >= Units.size()) + return false; + return std::ranges::any_of(Units[Source].Successors, + [Destination](const ScheduleDependency &Dependency) { + return Dependency.Destination == Destination; + }); +} + +Expected<bool> ScheduleDAG::fuseInstructionPair(std::size_t First, std::size_t Second) { + if (First >= Units.size() || Second >= Units.size() || First == Second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "macro fusion requires two distinct known schedule units"); + } + ScheduleUnit &FirstUnit = Units[First]; + ScheduleUnit &SecondUnit = Units[Second]; + if (FirstUnit.ClusterPredecessor || FirstUnit.ClusterSuccessor || SecondUnit.ClusterPredecessor || + SecondUnit.ClusterSuccessor || hasPath(Second, First)) { + return false; + } + + struct Binding final { + std::size_t Source = 0; + std::size_t Destination = 0; + }; + std::vector<Binding> Bindings; + const std::vector<ScheduleDependency> FirstSuccessors = FirstUnit.Successors; + const std::vector<ScheduleDependency> SecondPredecessors = SecondUnit.Predecessors; + for (const ScheduleDependency &Dependency : FirstSuccessors) { + if (Dependency.Kind == ScheduleDependencyKind::Cluster || isHazardDependency(Dependency.Kind) || + Dependency.Destination == Second || hasDirectDependency(Dependency.Destination, Second)) { + continue; + } + if (hasPath(Dependency.Destination, Second)) + return false; + Bindings.push_back({Second, Dependency.Destination}); + } + for (const ScheduleDependency &Dependency : SecondPredecessors) { + if (Dependency.Kind == ScheduleDependencyKind::Cluster || isHazardDependency(Dependency.Kind) || + Dependency.Source == First || hasDirectDependency(First, Dependency.Source)) { + continue; + } + if (hasPath(First, Dependency.Source)) + return false; + Bindings.push_back({Dependency.Source, First}); + } + + addDependency(First, Second, ScheduleDependencyKind::Cluster, 0); + FirstUnit.ClusterSuccessor = Second; + SecondUnit.ClusterPredecessor = First; + for (ScheduleDependency &Dependency : FirstUnit.Successors) { + if (Dependency.Destination == Second) + Dependency.Latency = 0; + } + for (ScheduleDependency &Dependency : SecondUnit.Predecessors) { + if (Dependency.Source == First) + Dependency.Latency = 0; + } + for (const Binding &Binding : Bindings) + addDependency(Binding.Source, Binding.Destination, ScheduleDependencyKind::Artificial, 0); + return true; +} + +Expected<void> ScheduleDAG::buildMemoryDependencies(const TargetDescription &Target) { + MachineAliasAnalysis::Result Aliases; + for (std::size_t LaterIndex = 0; LaterIndex < Units.size(); ++LaterIndex) { + for (std::size_t EarlierIndex = 0; EarlierIndex < LaterIndex; ++EarlierIndex) { + bool NeedsEdge = false; + for (MachineInstr *Earlier : Units[EarlierIndex].Instructions) { + const InstructionDescriptor *EarlierDescriptor = + Target.instructionDescriptor(Earlier->opcode()); + if (EarlierDescriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown instruction descriptor"); + const bool EarlierMemory = EarlierDescriptor->Flags.has(InstructionFlag::MayLoad) || + EarlierDescriptor->Flags.has(InstructionFlag::MayStore) || + !Earlier->memOperands().empty(); + if (!EarlierMemory) + continue; + for (MachineInstr *Later : Units[LaterIndex].Instructions) { + const InstructionDescriptor *LaterDescriptor = + Target.instructionDescriptor(Later->opcode()); + if (LaterDescriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown instruction descriptor"); + const bool LaterMemory = LaterDescriptor->Flags.has(InstructionFlag::MayLoad) || + LaterDescriptor->Flags.has(InstructionFlag::MayStore) || + !Later->memOperands().empty(); + if (!LaterMemory) + continue; + if (hasOrderedMemory(*Earlier) || hasOrderedMemory(*Later) || + ((hasStore(*Earlier) || hasStore(*Later)) && mayAlias(*Earlier, *Later, Aliases)) || + (Earlier->memOperands().empty() || Later->memOperands().empty()) || + (!hasLoad(*Earlier) && !hasStore(*Earlier)) || + (!hasLoad(*Later) && !hasStore(*Later))) { + NeedsEdge = true; + break; + } + } + if (NeedsEdge) + break; + } + if (NeedsEdge) + addDependency(EarlierIndex, LaterIndex, ScheduleDependencyKind::Memory, 0); + } + } + return {}; +} + +Expected<void> ScheduleDAG::buildOrderDependencies(const TargetDescription &Target) { + for (std::size_t Barrier = 0; Barrier < Units.size(); ++Barrier) { + bool IsBarrier = false; + for (const MachineInstr *Instruction : Units[Barrier].Instructions) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "scheduler encountered an unknown instruction descriptor"); + } + const InstructionFlags Flags = Descriptor->Flags; + IsBarrier |= Flags.has(InstructionFlag::Terminator) || Flags.has(InstructionFlag::Branch) || + Flags.has(InstructionFlag::Call) || Flags.has(InstructionFlag::Return) || + Flags.has(InstructionFlag::Barrier) || + Flags.has(InstructionFlag::HasSideEffects) || + Flags.has(InstructionFlag::UnmodeledSideEffects) || + Flags.has(InstructionFlag::Convergent) || Flags.has(InstructionFlag::Phi) || + Flags.has(InstructionFlag::Meta); + } + if (!IsBarrier) + continue; + for (std::size_t Earlier = 0; Earlier < Barrier; ++Earlier) + addDependency(Earlier, Barrier, ScheduleDependencyKind::Barrier, 0); + for (std::size_t Later = Barrier + 1; Later < Units.size(); ++Later) + addDependency(Barrier, Later, ScheduleDependencyKind::Barrier, 0); + } + return {}; +} + +void ScheduleDAG::addDependency(std::size_t Source, std::size_t Destination, + ScheduleDependencyKind Kind, std::uint32_t Latency) { + if (Source >= Units.size() || Destination >= Units.size() || Source == Destination) + return; + const auto Existing = std::ranges::find_if( + Units[Source].Successors, [Destination, Kind](const ScheduleDependency &Dependency) { + return Dependency.Destination == Destination && Dependency.Kind == Kind; + }); + if (Existing != Units[Source].Successors.end()) { + Existing->Latency = std::max(Existing->Latency, Latency); + const auto Predecessor = std::ranges::find_if( + Units[Destination].Predecessors, [Source, Kind](const ScheduleDependency &Dependency) { + return Dependency.Source == Source && Dependency.Kind == Kind; + }); + if (Predecessor != Units[Destination].Predecessors.end()) + Predecessor->Latency = Existing->Latency; + return; + } + const ScheduleDependency Dependency{Source, Destination, Kind, Latency}; + Units[Source].Successors.push_back(Dependency); + Units[Destination].Predecessors.push_back(Dependency); +} + +Expected<void> ScheduleDAG::computeCriticalPaths() { + std::vector<std::size_t> RemainingPredecessors; + RemainingPredecessors.reserve(Units.size()); + for (const ScheduleUnit &Unit : Units) + RemainingPredecessors.push_back(Unit.Predecessors.size()); + std::vector<std::size_t> TopologicalOrder; + TopologicalOrder.reserve(Units.size()); + std::vector<bool> Emitted(Units.size()); + for (std::size_t Count = 0; Count < Units.size(); ++Count) { + std::optional<std::size_t> Next; + for (const ScheduleUnit &Unit : Units) { + if (!Emitted[Unit.ID] && RemainingPredecessors[Unit.ID] == 0) { + Next = Unit.ID; + break; + } + } + if (!Next) { + return makeUnexpected(ErrorCode::SchedulingFailed, + "schedule DAG contains a cyclic target mutation"); + } + Emitted[*Next] = true; + TopologicalOrder.push_back(*Next); + for (const ScheduleDependency &Dependency : Units[*Next].Successors) { + if (RemainingPredecessors[Dependency.Destination] == 0) { + return makeUnexpected(ErrorCode::InternalError, + "schedule DAG predecessor count underflowed"); + } + --RemainingPredecessors[Dependency.Destination]; + } + } + for (const std::size_t ID : TopologicalOrder) { + ScheduleUnit &Unit = Units[ID]; + Unit.Depth = 0; + for (const ScheduleDependency &Dependency : Unit.Predecessors) { + Unit.Depth = + std::max(Unit.Depth, saturatingAdd(Units[Dependency.Source].Depth, + static_cast<std::uint64_t>(Dependency.Latency))); + } + } + for (auto Position = TopologicalOrder.rbegin(); Position != TopologicalOrder.rend(); ++Position) { + ScheduleUnit &Unit = Units[*Position]; + Unit.Height = Unit.Latency; + for (const ScheduleDependency &Dependency : Unit.Successors) { + Unit.Height = + std::max(Unit.Height, saturatingAdd(Units[Dependency.Destination].Height, + static_cast<std::uint64_t>(Dependency.Latency))); + } + } + for (ScheduleUnit &Unit : Units) { + std::ranges::sort(Unit.Predecessors, {}, &ScheduleDependency::Source); + std::ranges::sort(Unit.Successors, {}, &ScheduleDependency::Destination); + } + return {}; +} + +} // namespace rcc |