diff options
Diffstat (limited to 'backend/lib')
19 files changed, 830 insertions, 78 deletions
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 6a7f38d..2fc7254 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -58,6 +58,7 @@ set( PostRAScheduler.cpp RegisterPressure.cpp RegisterScavenger.cpp + MacroFusion.cpp ScheduleDAG.cpp ScheduleHazardRecognizer.cpp InlineSpiller.cpp @@ -95,6 +96,7 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InstructionDescriptor.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/InlineAsm.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LowLevelType.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MacroFusion.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineBasicBlockAttributes.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCFIInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineCompilationStatus.h" diff --git a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp index f96d544..adec384 100644 --- a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp +++ b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp @@ -71,7 +71,8 @@ Expected<void> addPreRegisterAllocationOptimizationPipeline( MachineCombinerStage::PreRegisterAllocation); if (!Added) return std::unexpected(Added.error()); - return addPass<MachineSchedulerPass>(Pipeline, TargetInfo.SchedulingModel); + return addPass<MachineSchedulerPass>(Pipeline, TargetInfo.SchedulingModel, + TargetInfo.SchedulerOptions); } Expected<void> @@ -112,7 +113,8 @@ addPostRegisterAllocationPipeline(MachineFunctionPassManager &Pipeline, Added = addPass<ExpandPostRAPseudosPass>(Pipeline, TargetInfo.PseudoExpansion); if (!Added) return std::unexpected(Added.error()); - Added = addPass<PostRASchedulerPass>(Pipeline, TargetInfo.SchedulingModel); + Added = addPass<PostRASchedulerPass>(Pipeline, TargetInfo.SchedulingModel, + TargetInfo.SchedulerOptions); if (!Added) return std::unexpected(Added.error()); Added = addPass<MachineBlockPlacementPass>(Pipeline); diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp index 9fffa65..302173f 100644 --- a/backend/lib/CodeGen/MachineScheduler.cpp +++ b/backend/lib/CodeGen/MachineScheduler.cpp @@ -18,6 +18,7 @@ #include <algorithm> #include <cstddef> #include <cstdint> +#include <iostream> #include <limits> #include <optional> #include <ranges> @@ -89,14 +90,17 @@ struct ScheduleCandidate final { std::uint64_t CriticalPath = 0; std::uint32_t Latency = 0; std::int64_t TargetPreference = 0; + bool ContinuesCluster = false; bool OptimizeLatency = false; - std::uint64_t StableID = 0; + std::size_t StableOrder = 0; }; [[nodiscard]] bool isBetterCandidate(const ScheduleCandidate &Left, const ScheduleCandidate &Right) noexcept { if (Left.Cycle != Right.Cycle) return Left.Cycle < Right.Cycle; + if (Left.ContinuesCluster != Right.ContinuesCluster) + return Left.ContinuesCluster; if (Left.TargetPreference != Right.TargetPreference) return Left.TargetPreference > Right.TargetPreference; if (Left.OptimizeLatency && Right.OptimizeLatency) { @@ -115,8 +119,8 @@ struct ScheduleCandidate final { return Left.CriticalPath > Right.CriticalPath; if (Left.Latency != Right.Latency) return Left.Latency > Right.Latency; - if (Left.StableID != Right.StableID) - return Left.StableID < Right.StableID; + if (Left.StableOrder != Right.StableOrder) + return Left.StableOrder < Right.StableOrder; return !Left.Bottom && Right.Bottom; } @@ -177,8 +181,9 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function, Unit.Latency, Model.hooks().candidatePreference(Unit, ScheduleDirection::TopDown, DAG.block(), BlockFrequency), + Unit.ClusterPredecessor && Scheduled[*Unit.ClusterPredecessor], BlockFrequency >= MachineBlockFrequencyAnalysis::EntryFrequency, - Unit.StableID.value()}; + Unit.ID}; if (!Best || isBetterCandidate(Candidate, *Best)) Best = Candidate; } @@ -198,8 +203,9 @@ scheduleDAG(const ScheduleDAG &DAG, const MachineFunction &Function, Unit.Latency, Model.hooks().candidatePreference(Unit, ScheduleDirection::BottomUp, DAG.block(), BlockFrequency), + Unit.ClusterSuccessor && Scheduled[*Unit.ClusterSuccessor], BlockFrequency >= MachineBlockFrequencyAnalysis::EntryFrequency, - Unit.StableID.value()}; + Unit.ID}; if (!Best || isBetterCandidate(Candidate, *Best)) Best = Candidate; } @@ -270,7 +276,11 @@ scheduleRegion(MachineBasicBlock &Block, std::span<MachineInstr *const> Instruct MachineSchedulerOptions Options, MachineActionReplay *Actions) { if (Instructions.size() < 2 || Instructions.size() > Options.MaximumRegionSize) return false; - auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode); + if (Options.EmitDebugOutput) { + std::cerr << Function.name() << ":%bb." << Block.denseNumber().value_or(0) << '\n'; + } + auto DAG = ScheduleDAG::build(Block, Instructions, Function, Target, Model, Mode, + Options.EmitDebugOutput); if (!DAG) return std::unexpected(DAG.error()); if (DAG->units().size() < 2) @@ -408,9 +418,11 @@ Expected<MachinePassResult> MachineSchedulerPass::run(MachineFunction &Function, if (!TrialFrequencies) return std::unexpected(TrialFrequencies.error()); MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + MachineSchedulerOptions TrialOptions = Options; + TrialOptions.EmitDebugOutput = false; auto TrialResult = runMachineScheduler(*Trial->ClonedFunction, Target, *Model, ScheduleDAGMode::PreRegisterAllocation, **TrialLiveness, - **TrialFrequencies, Options, &Actions); + **TrialFrequencies, TrialOptions, &Actions); if (!TrialResult) return std::unexpected(TrialResult.error()); diff --git a/backend/lib/CodeGen/MacroFusion.cpp b/backend/lib/CodeGen/MacroFusion.cpp new file mode 100644 index 0000000..726ca59 --- /dev/null +++ b/backend/lib/CodeGen/MacroFusion.cpp @@ -0,0 +1,168 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/MacroFusion.h" + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/ScheduleDAG.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <cstddef> +#include <iostream> +#include <optional> +#include <ranges> +#include <span> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] const MachineInstr *instructionFor(MacroFusionInstruction Side, + const MachineInstr *First, + const MachineInstr &Second) noexcept { + return Side == MacroFusionInstruction::First ? First : &Second; +} + +[[nodiscard]] std::optional<Register> registerAt(const MachineInstr &Instruction, + std::uint32_t OperandIndex) noexcept { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + return Operand == nullptr ? std::nullopt : Operand->registerValue(); +} + +[[nodiscard]] const std::int64_t *immediateAt(const MachineInstr &Instruction, + std::uint32_t OperandIndex) noexcept { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + return Operand == nullptr ? nullptr : Operand->getIf<std::int64_t>(); +} + +[[nodiscard]] bool containsOpcode(std::span<const Opcode> Opcodes, Opcode Value) noexcept { + return std::ranges::contains(Opcodes, Value); +} + +[[nodiscard]] bool matchesLink(const MacroFusionRule &Rule, const MachineInstr &First, + const MachineInstr &Second) noexcept { + const std::optional<Register> FirstDefinition = registerAt(First, Rule.FirstDefinitionOperand); + const std::optional<Register> SecondUse = registerAt(Second, Rule.SecondUseOperand); + const std::optional<Register> AlternateSecondUse = + Rule.CommutableSecondUseOperand == MacroFusionRule::NoOperand + ? std::nullopt + : registerAt(Second, Rule.CommutableSecondUseOperand); + if (!FirstDefinition || + (*FirstDefinition != SecondUse && *FirstDefinition != AlternateSecondUse)) { + return false; + } + + if (Rule.RequireSingleNonDebugUse && FirstDefinition->isVirtual() && + !Second.function().registerInfo().hasOneUse(*FirstDefinition, false)) { + return false; + } + + if (!Rule.RequireSecondDestinationTie) + return true; + const std::optional<Register> SecondDefinition = registerAt(Second, Rule.SecondDefinitionOperand); + if (!SecondDefinition || SecondDefinition->isVirtual()) + return SecondDefinition.has_value(); + return *SecondDefinition == SecondUse || *SecondDefinition == AlternateSecondUse; +} + +[[nodiscard]] bool isFusionCandidateDependency(ScheduleDependencyKind Kind) noexcept { + return Kind != ScheduleDependencyKind::Anti && Kind != ScheduleDependencyKind::Output && + Kind != ScheduleDependencyKind::Cluster; +} + +[[nodiscard]] std::string_view opcodeName(const TargetDescription &Target, Opcode Value) noexcept { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Value); + return Descriptor == nullptr ? std::string_view{"<unknown>"} : Descriptor->Name; +} + +} // namespace + +bool matchesMacroFusion(const MacroFusionRule &Rule, const MachineInstr *First, + const MachineInstr &Second) noexcept { + if (!containsOpcode(Rule.SecondOpcodes, Second.opcode())) + return false; + if (First == nullptr) + return true; + if (!containsOpcode(Rule.FirstOpcodes, First->opcode())) + return false; + if (!Rule.OpcodePairs.empty() && + std::ranges::none_of(Rule.OpcodePairs, [First, &Second](MacroFusionOpcodePair Pair) { + return Pair.First == First->opcode() && Pair.Second == Second.opcode(); + })) { + return false; + } + + for (const MacroFusionImmediatePredicate &Predicate : Rule.ImmediatePredicates) { + const MachineInstr *Instruction = instructionFor(Predicate.Instruction, First, Second); + const std::int64_t *Value = + Instruction == nullptr ? nullptr : immediateAt(*Instruction, Predicate.OperandIndex); + if (Value == nullptr || *Value < Predicate.Minimum || *Value > Predicate.Maximum) + return false; + } + for (const MacroFusionRegisterInequality &Predicate : Rule.RegisterInequalities) { + const MachineInstr *Instruction = instructionFor(Predicate.Instruction, First, Second); + if (Instruction == nullptr) + return false; + const std::optional<Register> Left = registerAt(*Instruction, Predicate.LeftOperand); + const std::optional<Register> Right = registerAt(*Instruction, Predicate.RightOperand); + if (!Left || !Right || *Left == *Right) + return false; + } + for (const MacroFusionImmediateRelation &Predicate : Rule.ImmediateRelations) { + const std::int64_t *FirstValue = immediateAt(*First, Predicate.FirstOperand); + const std::int64_t *SecondValue = immediateAt(Second, Predicate.SecondOperand); + if (FirstValue == nullptr || SecondValue == nullptr || *FirstValue > *SecondValue) + return false; + } + return matchesLink(Rule, *First, Second); +} + +Expected<void> applyMacroFusion(ScheduleDAG &DAG, std::span<const MacroFusionRule> Rules, + const TargetDescription &Target, bool EmitDebugOutput) { + if (Rules.empty()) + return {}; + for (ScheduleUnit &Anchor : DAG.units()) { + if (Anchor.Instructions.size() != 1 || Anchor.ClusterPredecessor || Anchor.ClusterSuccessor) + continue; + const MachineInstr &Second = *Anchor.Instructions.front(); + if (std::ranges::none_of(Rules, [&Second](const MacroFusionRule &Rule) { + return matchesMacroFusion(Rule, nullptr, Second); + })) { + continue; + } + const std::vector<ScheduleDependency> Predecessors = Anchor.Predecessors; + for (const ScheduleDependency &Dependency : Predecessors) { + if (!isFusionCandidateDependency(Dependency.Kind)) + continue; + const ScheduleUnit *FirstUnit = DAG.unit(Dependency.Source); + if (FirstUnit == nullptr || FirstUnit->Instructions.size() != 1 || + FirstUnit->ClusterPredecessor || FirstUnit->ClusterSuccessor) { + continue; + } + const MachineInstr &First = *FirstUnit->Instructions.front(); + if (std::ranges::none_of(Rules, [&First, &Second](const MacroFusionRule &Rule) { + return matchesMacroFusion(Rule, &First, Second); + })) { + continue; + } + auto Fused = DAG.fuseInstructionPair(FirstUnit->ID, Anchor.ID); + if (!Fused) + return std::unexpected(Fused.error()); + if (!*Fused) + continue; + if (EmitDebugOutput) { + std::cerr << "Macro fuse: SU(" << FirstUnit->ID << ") - SU(" << Anchor.ID << ") / " + << opcodeName(Target, First.opcode()) << " - " + << opcodeName(Target, Second.opcode()) << '\n'; + } + break; + } + } + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp index d2feb92..7f5c697 100644 --- a/backend/lib/CodeGen/PostRAScheduler.cpp +++ b/backend/lib/CodeGen/PostRAScheduler.cpp @@ -73,9 +73,11 @@ Expected<MachinePassResult> PostRASchedulerPass::run(MachineFunction &Function, if (!TrialFrequencies) return std::unexpected(TrialFrequencies.error()); MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + MachineSchedulerOptions TrialOptions = Options; + TrialOptions.EmitDebugOutput = false; auto TrialRun = runMachineScheduler(*Trial->ClonedFunction, Target, *Model, ScheduleDAGMode::PostRegisterAllocation, **TrialLiveness, - **TrialFrequencies, Options, &Actions); + **TrialFrequencies, TrialOptions, &Actions); if (!TrialRun) return std::unexpected(TrialRun.error()); auto TrialRepair = diff --git a/backend/lib/CodeGen/ScheduleDAG.cpp b/backend/lib/CodeGen/ScheduleDAG.cpp index 8696f2e..9fba862 100644 --- a/backend/lib/CodeGen/ScheduleDAG.cpp +++ b/backend/lib/CodeGen/ScheduleDAG.cpp @@ -168,13 +168,16 @@ maskKeys(const RegisterMask &Mask, const TargetDescription &Target) { }); } +[[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) { +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"); @@ -191,10 +194,12 @@ Expected<ScheduleDAG> ScheduleDAG::build(MachineBasicBlock &Block, auto Order = Result.buildOrderDependencies(Target); if (!Order) return std::unexpected(Order.error()); - auto Mutated = Model.hooks().mutateScheduleDAG(Result, Function, Target, Mode); + auto Mutated = Model.hooks().mutateScheduleDAG(Result, Function, Target, Mode, EmitDebugOutput); if (!Mutated) return std::unexpected(Mutated.error()); - Result.computeCriticalPaths(); + auto CriticalPaths = Result.computeCriticalPaths(); + if (!CriticalPaths) + return std::unexpected(CriticalPaths.error()); return Result; } @@ -382,15 +387,101 @@ Expected<void> ScheduleDAG::buildRegisterDependencies(const MachineFunction &Fun 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 a forward dependency between known units"); + 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) { @@ -488,8 +579,38 @@ void ScheduleDAG::addDependency(std::size_t Source, std::size_t Destination, Units[Destination].Predecessors.push_back(Dependency); } -void ScheduleDAG::computeCriticalPaths() { - for (ScheduleUnit &Unit : Units) { +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 = @@ -497,18 +618,20 @@ void ScheduleDAG::computeCriticalPaths() { static_cast<std::uint64_t>(Dependency.Latency))); } } - for (auto Position = Units.rbegin(); Position != Units.rend(); ++Position) { - Position->Height = Position->Latency; - for (const ScheduleDependency &Dependency : Position->Successors) { - Position->Height = - std::max(Position->Height, saturatingAdd(Units[Dependency.Destination].Height, - 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 diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp index ab77965..3701add 100644 --- a/backend/lib/CodeGen/TargetDescription.cpp +++ b/backend/lib/CodeGen/TargetDescription.cpp @@ -345,10 +345,10 @@ Expected<void> TargetDescription::validateTargetOperand(const OperandDescriptor if (!EffectiveClass || !Registers.isSubclass(*EffectiveClass, *Descriptor->RegClass)) { const std::string ActualClass = EffectiveClass ? std::to_string(EffectiveClass->value()) : "<none>"; - return makeUnexpected( - ErrorCode::VerificationError, - "virtual register class " + ActualClass + " does not satisfy required class " + - std::to_string(Descriptor->RegClass->value())); + return makeUnexpected(ErrorCode::VerificationError, + "virtual register class " + ActualClass + + " does not satisfy required class " + + std::to_string(Descriptor->RegClass->value())); } } return {}; @@ -469,9 +469,9 @@ TargetDescription::validateExplicitOperands(Opcode InstructionOpcode, auto TargetValidation = validateTargetOperand(&descriptorForOperand(*Descriptor, Index), Operands[Index], RegInfo); if (!TargetValidation) - return std::unexpected(withErrorContext( - TargetValidation.error(), "operand " + std::to_string(Index) + " of '" + - Descriptor->Name + "': ")); + return std::unexpected( + withErrorContext(TargetValidation.error(), "operand " + std::to_string(Index) + " of '" + + Descriptor->Name + "': ")); } return {}; } diff --git a/backend/lib/CodeGen/TargetSchedulingModel.cpp b/backend/lib/CodeGen/TargetSchedulingModel.cpp index 97abecd..f462c21 100644 --- a/backend/lib/CodeGen/TargetSchedulingModel.cpp +++ b/backend/lib/CodeGen/TargetSchedulingModel.cpp @@ -49,8 +49,8 @@ bool TargetSchedulingHooks::isSchedulingBoundary(const MachineInstr &, } Expected<void> TargetSchedulingHooks::mutateScheduleDAG(ScheduleDAG &, const MachineFunction &, - const TargetDescription &, - ScheduleDAGMode) const { + const TargetDescription &, ScheduleDAGMode, + bool) const { return {}; } diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp index 6c3b866..c383aed 100644 --- a/backend/lib/TableGen/Parser.cpp +++ b/backend/lib/TableGen/Parser.cpp @@ -41,7 +41,7 @@ public: "register_classes", "register_masks", "mir_operand_flags", "named_operands", "immediate_predicates", "scheduling_classes", "encoding_categories", "assembly_formats", "calling_conventions", "instructions", "selection_rules", - "combiner_rules"}, + "combiner_rules", "macro_fusion_rules"}, "target description root")) { return std::nullopt; } @@ -83,6 +83,7 @@ public: requiredNode(*Root, "instructions", "target description root"); const yaml::Node *SelectionRulesNode = optionalNode(*Root, "selection_rules"); const yaml::Node *CombinerRulesNode = optionalNode(*Root, "combiner_rules"); + const yaml::Node *MacroFusionRulesNode = optionalNode(*Root, "macro_fusion_rules"); if (UnitsNode == nullptr || RegistersNode == nullptr || BanksNode == nullptr || ClassesNode == nullptr || MasksNode == nullptr || NamedOperandsNode == nullptr || ImmediatePredicatesNode == nullptr || SchedulingClassesNode == nullptr || @@ -105,7 +106,9 @@ public: (SelectionRulesNode != nullptr && !parseSelectionRules(*SelectionRulesNode, Result.SelectionRules)) || (CombinerRulesNode != nullptr && - !parseCombinerRules(*CombinerRulesNode, Result.CombinerRules))) { + !parseCombinerRules(*CombinerRulesNode, Result.CombinerRules)) || + (MacroFusionRulesNode != nullptr && + !parseMacroFusionRules(*MacroFusionRulesNode, Result.MacroFusionRules))) { return std::nullopt; } return Result; @@ -1891,6 +1894,211 @@ private: return true; } + [[nodiscard]] bool parseMacroFusionOpcodePairs(const yaml::Node &Node, + std::vector<SourceMacroFusionOpcodePair> &Result) { + if (!requireSequence(&Node, "macro fusion opcode pairs")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "macro fusion opcode pair") || + !checkKeys(*Element, {"first", "second"}, "macro fusion opcode pair")) { + return false; + } + const auto First = requiredScalar(*Element, "first", "macro fusion opcode pair"); + const auto Second = requiredScalar(*Element, "second", "macro fusion opcode pair"); + if (!First || !Second) + return false; + Result.push_back({*First, *Second, Element->range()}); + } + return true; + } + + [[nodiscard]] bool + parseMacroFusionImmediatePredicates(const yaml::Node &Node, + std::vector<SourceMacroFusionImmediatePredicate> &Result) { + if (!requireSequence(&Node, "macro fusion immediate predicates")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "macro fusion immediate predicate") || + !checkKeys(*Element, {"instruction", "operand", "min", "max"}, + "macro fusion immediate predicate")) { + return false; + } + const auto Instruction = + requiredScalar(*Element, "instruction", "macro fusion immediate predicate"); + const yaml::Node *OperandNode = + requiredNode(*Element, "operand", "macro fusion immediate predicate"); + const yaml::Node *MinimumNode = + requiredNode(*Element, "min", "macro fusion immediate predicate"); + const yaml::Node *MaximumNode = + requiredNode(*Element, "max", "macro fusion immediate predicate"); + if (!Instruction || OperandNode == nullptr || MinimumNode == nullptr || + MaximumNode == nullptr) { + return false; + } + const auto Operand = unsignedInteger32(*OperandNode, "macro fusion immediate operand"); + const auto Minimum = signedInteger(*MinimumNode, "macro fusion immediate minimum"); + const auto Maximum = signedInteger(*MaximumNode, "macro fusion immediate maximum"); + if (!Operand || !Minimum || !Maximum) + return false; + Result.push_back({*Instruction, *Operand, *Minimum, *Maximum, Element->range()}); + } + return true; + } + + [[nodiscard]] bool + parseMacroFusionRegisterInequalities(const yaml::Node &Node, + std::vector<SourceMacroFusionRegisterInequality> &Result) { + if (!requireSequence(&Node, "macro fusion register inequalities")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "macro fusion register inequality") || + !checkKeys(*Element, {"instruction", "left", "right"}, + "macro fusion register inequality")) { + return false; + } + const auto Instruction = + requiredScalar(*Element, "instruction", "macro fusion register inequality"); + const yaml::Node *LeftNode = + requiredNode(*Element, "left", "macro fusion register inequality"); + const yaml::Node *RightNode = + requiredNode(*Element, "right", "macro fusion register inequality"); + if (!Instruction || LeftNode == nullptr || RightNode == nullptr) + return false; + const auto Left = unsignedInteger32(*LeftNode, "macro fusion left register operand"); + const auto Right = unsignedInteger32(*RightNode, "macro fusion right register operand"); + if (!Left || !Right) + return false; + Result.push_back({*Instruction, *Left, *Right, Element->range()}); + } + return true; + } + + [[nodiscard]] bool + parseMacroFusionImmediateRelations(const yaml::Node &Node, + std::vector<SourceMacroFusionImmediateRelation> &Result) { + if (!requireSequence(&Node, "macro fusion immediate relations")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "macro fusion immediate relation") || + !checkKeys(*Element, {"kind", "first_operand", "second_operand"}, + "macro fusion immediate relation")) { + return false; + } + const auto Kind = requiredScalar(*Element, "kind", "macro fusion immediate relation"); + const yaml::Node *FirstNode = + requiredNode(*Element, "first_operand", "macro fusion immediate relation"); + const yaml::Node *SecondNode = + requiredNode(*Element, "second_operand", "macro fusion immediate relation"); + if (!Kind || FirstNode == nullptr || SecondNode == nullptr) + return false; + const auto First = unsignedInteger32(*FirstNode, "macro fusion first immediate operand"); + const auto Second = unsignedInteger32(*SecondNode, "macro fusion second immediate operand"); + if (!First || !Second) + return false; + Result.push_back({*Kind, *First, *Second, Element->range()}); + } + return true; + } + + [[nodiscard]] bool parseMacroFusionLink(const yaml::Node &Node, SourceMacroFusionRule &Result) { + if (!requireMapping(&Node, "macro fusion link") || + !checkKeys(Node, + {"first_definition", "second_use", "second_definition", "commutable_second_use", + "one_non_debug_use", "second_destination_tied"}, + "macro fusion link")) { + return false; + } + const yaml::Node *FirstNode = requiredNode(Node, "first_definition", "macro fusion link"); + const yaml::Node *SecondUseNode = requiredNode(Node, "second_use", "macro fusion link"); + const yaml::Node *SecondDefinitionNode = + requiredNode(Node, "second_definition", "macro fusion link"); + const yaml::Node *SingleUseNode = requiredNode(Node, "one_non_debug_use", "macro fusion link"); + const yaml::Node *TiedNode = requiredNode(Node, "second_destination_tied", "macro fusion link"); + if (FirstNode == nullptr || SecondUseNode == nullptr || SecondDefinitionNode == nullptr || + SingleUseNode == nullptr || TiedNode == nullptr) { + return false; + } + const auto First = unsignedInteger32(*FirstNode, "macro fusion first definition"); + const auto SecondUse = unsignedInteger32(*SecondUseNode, "macro fusion second use"); + const auto SecondDefinition = + unsignedInteger32(*SecondDefinitionNode, "macro fusion second definition"); + const auto SingleUse = boolean(*SingleUseNode, "macro fusion one_non_debug_use"); + const auto Tied = boolean(*TiedNode, "macro fusion second_destination_tied"); + if (!First || !SecondUse || !SecondDefinition || !SingleUse || !Tied) + return false; + Result.FirstDefinitionOperand = *First; + Result.SecondUseOperand = *SecondUse; + Result.SecondDefinitionOperand = *SecondDefinition; + Result.RequireSingleNonDebugUse = *SingleUse; + Result.RequireSecondDestinationTie = *Tied; + if (const yaml::Node *Commutable = optionalNode(Node, "commutable_second_use")) { + const auto Value = unsignedInteger32(*Commutable, "macro fusion commutable second use"); + if (!Value) + return false; + Result.CommutableSecondUseOperand = *Value; + } + return true; + } + + [[nodiscard]] bool parseMacroFusionRules(const yaml::Node &Node, + std::vector<SourceMacroFusionRule> &Result) { + if (!requireSequence(&Node, "macro_fusion_rules")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "macro fusion rule") || + !checkKeys(*Element, + {"id", "feature", "first_opcodes", "second_opcodes", "opcode_pairs", + "immediates", "register_not_equal", "immediate_relations", "link"}, + "macro fusion rule")) { + return false; + } + const auto Symbol = requiredScalar(*Element, "id", "macro fusion rule"); + const auto Feature = requiredScalar(*Element, "feature", "macro fusion rule"); + const yaml::Node *FirstNode = requiredNode(*Element, "first_opcodes", "macro fusion rule"); + const yaml::Node *SecondNode = requiredNode(*Element, "second_opcodes", "macro fusion rule"); + const yaml::Node *LinkNode = requiredNode(*Element, "link", "macro fusion rule"); + if (!Symbol || !Feature || FirstNode == nullptr || SecondNode == nullptr || + LinkNode == nullptr) { + return false; + } + auto FirstOpcodes = scalarSequence(*FirstNode, "macro fusion first opcodes"); + auto SecondOpcodes = scalarSequence(*SecondNode, "macro fusion second opcodes"); + if (!FirstOpcodes || !SecondOpcodes) + return false; + SourceMacroFusionRule Rule; + Rule.Symbol = *Symbol; + Rule.Feature = *Feature; + Rule.FirstOpcodeSymbols = std::move(*FirstOpcodes); + Rule.SecondOpcodeSymbols = std::move(*SecondOpcodes); + Rule.Range = Element->range(); + if (!parseMacroFusionLink(*LinkNode, Rule)) + return false; + if (const yaml::Node *Pairs = optionalNode(*Element, "opcode_pairs")) { + if (!parseMacroFusionOpcodePairs(*Pairs, Rule.OpcodePairs)) + return false; + } + if (const yaml::Node *Immediates = optionalNode(*Element, "immediates")) { + if (!parseMacroFusionImmediatePredicates(*Immediates, Rule.ImmediatePredicates)) + return false; + } + if (const yaml::Node *Inequalities = optionalNode(*Element, "register_not_equal")) { + if (!parseMacroFusionRegisterInequalities(*Inequalities, Rule.RegisterInequalities)) + return false; + } + if (const yaml::Node *Relations = optionalNode(*Element, "immediate_relations")) { + if (!parseMacroFusionImmediateRelations(*Relations, Rule.ImmediateRelations)) + return false; + } + Result.push_back(std::move(Rule)); + } + return true; + } + [[nodiscard]] bool parseInstructions(const yaml::Node &Node, std::vector<SourceInstruction> &Result) { if (!requireSequence(&Node, "instructions")) diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt index 2e1e224..00de7bd 100644 --- a/backend/lib/Target/RISCV/CMakeLists.txt +++ b/backend/lib/Target/RISCV/CMakeLists.txt @@ -20,6 +20,7 @@ set( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelShift.rccdesc" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelFloating.rccdesc" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelCombiner.rccdesc" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVMacroFusion.rccdesc" ) set(RCCBackendRISCVTableGenArguments) foreach(RCCBackendRISCVDescriptionSource IN LISTS RCCBackendRISCVDescriptionSources) @@ -45,6 +46,10 @@ set( RCCBackendRISCVGeneratedGlobalISelCombiner "${RCC_BACKEND_BINARY_DIR}/generated/lib/Target/RISCV/RISCVGenGlobalISelCombiner.inc" ) +set( + RCCBackendRISCVGeneratedMacroFusion + "${RCC_BACKEND_BINARY_DIR}/generated/lib/Target/RISCV/RISCVGenMacroFusion.inc" +) add_custom_command( OUTPUT @@ -53,6 +58,7 @@ add_custom_command( "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" "${RCCBackendRISCVGeneratedGlobalISelCombiner}" + "${RCCBackendRISCVGeneratedMacroFusion}" COMMAND "$<TARGET_FILE:RCCBackendTableGenTool>" ${RCCBackendRISCVTableGenArguments} @@ -61,6 +67,7 @@ add_custom_command( --tables "${RCCBackendRISCVGeneratedTables}" --global-isel "${RCCBackendRISCVGeneratedGlobalISel}" --global-isel-combiner "${RCCBackendRISCVGeneratedGlobalISelCombiner}" + --macro-fusion "${RCCBackendRISCVGeneratedMacroFusion}" DEPENDS RCCBackendTableGenTool ${RCCBackendRISCVDescriptionSources} COMMENT "Generating RCC RV64GC target tables" VERBATIM @@ -74,6 +81,7 @@ add_custom_target( "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" "${RCCBackendRISCVGeneratedGlobalISelCombiner}" + "${RCCBackendRISCVGeneratedMacroFusion}" ) set_source_files_properties( @@ -82,6 +90,7 @@ set_source_files_properties( "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" "${RCCBackendRISCVGeneratedGlobalISelCombiner}" + "${RCCBackendRISCVGeneratedMacroFusion}" PROPERTIES GENERATED TRUE HEADER_FILE_ONLY TRUE ) @@ -117,6 +126,7 @@ add_library( "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" "${RCCBackendRISCVGeneratedGlobalISelCombiner}" + "${RCCBackendRISCVGeneratedMacroFusion}" ) add_library(RCCBackend::RISCV ALIAS RCCBackendRISCV) add_dependencies(RCCBackendRISCV RCCBackendRISCVGeneratedTablesTarget) diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp index 094f9cb..ca702ed 100644 --- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp +++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp @@ -5,9 +5,9 @@ #include "RISCVInstrInfo.h" #include "RISCVRegisterBankInfo.h" #include "rcc/CodeGen/GenericOpcodes.h" -#include "rcc/CodeGen/GlobalObject.h" #include "rcc/CodeGen/GlobalISel/GISelValueTracking.h" #include "rcc/CodeGen/GlobalISel/InstructionSelector.h" +#include "rcc/CodeGen/GlobalObject.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" @@ -727,8 +727,8 @@ public: } private: - [[nodiscard]] Expected<const MachineMemOperand *> - createGOTLoad(MachineFunction &Function, LowLevelType Type) const { + [[nodiscard]] Expected<const MachineMemOperand *> createGOTLoad(MachineFunction &Function, + LowLevelType Type) const { auto Size = MemorySize::fixed(Type.minimumBitWidth() / 8U); if (!Size) return std::unexpected(Size.error()); @@ -745,9 +745,9 @@ private: return Function.createMemOperand(std::move(Description)); } - [[nodiscard]] Expected<void> - selectGlobalAddress(MachineInstr &Instruction, MachineFunction &Function, - const TargetDescription &Target) const { + [[nodiscard]] Expected<void> selectGlobalAddress(MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const { const MachineOperand *DestinationOperand = Instruction.operandAt(0); const MachineOperand *SymbolOperand = Instruction.operandAt(1); const Register *Destination = @@ -775,8 +775,8 @@ private: } const bool TaggedGlobals = Subtarget.features().has(RISCVSubtargetOption::TaggedGlobals); - const bool UseGOT = Subtarget.relocationModel() == RelocationModel::PositionIndependent || - TaggedGlobals; + const bool UseGOT = + Subtarget.relocationModel() == RelocationModel::PositionIndependent || TaggedGlobals; const auto ReplaceWithPseudo = [&](InstructionOpcode OpcodeValue) -> Expected<void> { auto SetOpcode = Instruction.setOpcode(instructionOpcode(OpcodeValue)); if (!SetOpcode) diff --git a/backend/lib/Target/RISCV/RISCV.h b/backend/lib/Target/RISCV/RISCV.h index 4699091..4eeaf64 100644 --- a/backend/lib/Target/RISCV/RISCV.h +++ b/backend/lib/Target/RISCV/RISCV.h @@ -27,13 +27,18 @@ createRISCVInstructionSelector(const RISCVSubtarget &Subtarget, const RISCVRegisterBankInfo &RegisterBanks); [[nodiscard]] const TargetRegisterAllocationInfo ®isterAllocationInfo() noexcept; [[nodiscard]] const TargetFrameLowering &frameLowering() noexcept; -[[nodiscard]] const TargetSchedulingModel &schedulingModel() noexcept; +[[nodiscard]] std::unique_ptr<TargetSchedulingHooks> +createSchedulingHooks(const RISCVSubtargetFeatures &Features); +[[nodiscard]] Expected<TargetSchedulingModel> +createSchedulingModel(const TargetSchedulingHooks &Hooks); [[nodiscard]] const TargetMachineCombinerInfo &machineCombinerInfo() noexcept; [[nodiscard]] const GIMatchTable &giselCombinerTable() noexcept; [[nodiscard]] const GIMatchTableExecutor &giselCombinerExecutor() noexcept; [[nodiscard]] const TargetMemoryFoldingInfo &memoryFoldingInfo() noexcept; [[nodiscard]] const TargetPseudoExpansionInfo &pseudoExpansionInfo() noexcept; -[[nodiscard]] MachineOptimizationPipelineTargetInfo optimizationPipelineInfo() noexcept; +[[nodiscard]] MachineOptimizationPipelineTargetInfo +optimizationPipelineInfo(const RISCVSubtarget &Subtarget, + bool EmitSchedulerDebugOutput = false) noexcept; } // namespace riscv } // namespace rcc diff --git a/backend/lib/Target/RISCV/RISCVInstrInfoI.rccdesc b/backend/lib/Target/RISCV/RISCVInstrInfoI.rccdesc index 7bb30e5..13ea700 100644 --- a/backend/lib/Target/RISCV/RISCVInstrInfoI.rccdesc +++ b/backend/lib/Target/RISCV/RISCVInstrInfoI.rccdesc @@ -188,7 +188,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS2 } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, commutable] scheduling_class: ALU encoding_category: R assembly_format: RD_RS1_RS2 @@ -233,7 +233,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS2 } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, commutable] scheduling_class: ALU encoding_category: R assembly_format: RD_RS1_RS2 @@ -248,7 +248,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS2 } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, commutable] scheduling_class: ALU encoding_category: R assembly_format: RD_RS1_RS2 @@ -263,7 +263,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS2 } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, commutable] scheduling_class: ALU encoding_category: R assembly_format: RD_RS1_RS2 @@ -666,7 +666,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS2 } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, commutable] scheduling_class: ALU encoding_category: R assembly_format: RD_RS1_RS2 diff --git a/backend/lib/Target/RISCV/RISCVMacroFusion.rccdesc b/backend/lib/Target/RISCV/RISCVMacroFusion.rccdesc new file mode 100644 index 0000000..2c432a2 --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVMacroFusion.rccdesc @@ -0,0 +1,139 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +macro_fusion_rules: + - + id: TuneLUIADDIFusion + feature: fusion-lui-addi + first_opcodes: [LUI] + second_opcodes: [ADDI, ADDIW] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneAUIPCADDIFusion + feature: fusion-auipc-addi + first_opcodes: [AUIPC] + second_opcodes: [ADDI] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneZExtHFusion + feature: fusion-zexth + first_opcodes: [SLLI] + second_opcodes: [SRLI] + immediates: + - { instruction: first, operand: 2, min: 48, max: 48 } + - { instruction: second, operand: 2, min: 48, max: 48 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneZExtWFusion + feature: fusion-zextw + first_opcodes: [SLLI] + second_opcodes: [SRLI] + immediates: + - { instruction: first, operand: 2, min: 32, max: 32 } + - { instruction: second, operand: 2, min: 32, max: 32 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneShiftedZExtWFusion + feature: fusion-shifted-zextw + first_opcodes: [SLLI] + second_opcodes: [SRLI] + immediates: + - { instruction: first, operand: 2, min: 32, max: 32 } + - { instruction: second, operand: 2, min: 0, max: 31 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneLDADDFusion + feature: fusion-ld-add + first_opcodes: [ADD] + second_opcodes: [LD] + immediates: + - { instruction: second, operand: 2, min: 0, max: 0 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneADDLoadFusion + feature: fusion-add-load + first_opcodes: [ADD, ADD_UW] + second_opcodes: [LB, LH, LW, LD, LBU, LHU, LWU] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneAUIPCLoadFusion + feature: fusion-auipc-load + first_opcodes: [AUIPC] + second_opcodes: [LB, LH, LW, LD, LBU, LHU, LWU] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneLUILoadFusion + feature: fusion-lui-load + first_opcodes: [LUI] + second_opcodes: [LB, LH, LW, LD, LBU, LHU, LWU] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneBFExtFusion + feature: fusion-bfext + first_opcodes: [SLLI] + second_opcodes: [SRLI] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneADDILoadFusion + feature: fusion-addi-load + first_opcodes: [ADDI] + second_opcodes: [LB, LH, LW, LD, LBU, LHU, LWU] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneSHXADDLoadFusion + feature: fusion-shxadd-load + first_opcodes: [SH1ADD, SH2ADD, SH3ADD, SH1ADD_UW, SH2ADD_UW, SH3ADD_UW] + second_opcodes: [LB, LH, LW, LD, LBU, LHU, LWU] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneFusionLogicRegReg + feature: fusion-logic-reg-reg + first_opcodes: [AND, OR, XOR] + second_opcodes: [AND, OR, XOR] + link: { first_definition: 0, second_use: 1, second_definition: 0, commutable_second_use: 2, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneFusionLogicRegImm + feature: fusion-logic-reg-imm + first_opcodes: [AND, OR, XOR] + second_opcodes: [ANDI, ORI, XORI] + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneFusionLogicImmReg + feature: fusion-logic-imm-reg + first_opcodes: [ANDI, ORI, XORI] + second_opcodes: [AND, OR, XOR] + link: { first_definition: 0, second_use: 1, second_definition: 0, commutable_second_use: 2, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneFusionMulAdd + feature: fusion-mul-add + first_opcodes: [MUL, MULW] + second_opcodes: [ADD, ADDW] + opcode_pairs: + - { first: MUL, second: ADD } + - { first: MULW, second: ADDW } + register_not_equal: + - { instruction: second, left: 0, right: 2 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } + - + id: TuneFusionAddMem + feature: fusion-add-mem + first_opcodes: [ADD] + second_opcodes: [LB, LBU, LH, LHU, LW, LWU, LD, FLW, FLD, SB, SH, SW, SD, FSW, FSD] + immediates: + - { instruction: second, operand: 2, min: 0, max: 0 } + register_not_equal: + - { instruction: first, left: 0, right: 1 } + - { instruction: first, left: 0, right: 2 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: false, second_destination_tied: false } + - + id: TuneFusionShiftBitExtract + feature: fusion-shift-bit-extract + first_opcodes: [SLLI, SLLIW] + second_opcodes: [SRLI, SRLIW, SRAI, SRAIW] + opcode_pairs: + - { first: SLLI, second: SRLI } + - { first: SLLI, second: SRAI } + - { first: SLLIW, second: SRLIW } + - { first: SLLIW, second: SRAIW } + immediate_relations: + - { kind: less_equal, first_operand: 2, second_operand: 2 } + link: { first_definition: 0, second_use: 1, second_definition: 0, one_non_debug_use: true, second_destination_tied: true } diff --git a/backend/lib/Target/RISCV/RISCVOptimizationPipeline.cpp b/backend/lib/Target/RISCV/RISCVOptimizationPipeline.cpp index 5bacc9c..7571832 100644 --- a/backend/lib/Target/RISCV/RISCVOptimizationPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVOptimizationPipeline.cpp @@ -5,14 +5,16 @@ namespace rcc::riscv { -MachineOptimizationPipelineTargetInfo optimizationPipelineInfo() noexcept { +MachineOptimizationPipelineTargetInfo +optimizationPipelineInfo(const RISCVSubtarget &Subtarget, bool EmitSchedulerDebugOutput) noexcept { return { .InstrInfo = instrInfo(), .Combiner = machineCombinerInfo(), .MemoryFolding = memoryFoldingInfo(), .FrameLowering = frameLowering(), .PseudoExpansion = pseudoExpansionInfo(), - .SchedulingModel = schedulingModel(), + .SchedulingModel = Subtarget.schedulingModel(), + .SchedulerOptions = {.EmitDebugOutput = EmitSchedulerDebugOutput}, }; } diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp index c24c57f..2af1d43 100644 --- a/backend/lib/Target/RISCV/RISCVPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp @@ -55,8 +55,11 @@ template <typename PassT, typename... ArgumentT> return addPass<InstructionSelect>(Pipeline, Subtarget.getInstructionSelector()); } -[[nodiscard]] Expected<void> addSSAExitPipeline(MachineFunctionPassManager &Pipeline) { - auto Added = addSelectedSSAOptimizationPipeline(Pipeline, optimizationPipelineInfo()); +[[nodiscard]] Expected<void> addSSAExitPipeline(MachineFunctionPassManager &Pipeline, + const RISCVSubtarget &Subtarget, + RISCVPipelineOptions Options) { + auto Added = addSelectedSSAOptimizationPipeline( + Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler)); if (!Added) return std::unexpected(Added.error()); Added = addPass<PHIEliminationPass>(Pipeline, instrInfo()); @@ -65,11 +68,14 @@ template <typename PassT, typename... ArgumentT> return addPass<TwoAddressInstructionPass>(Pipeline, instrInfo()); } -[[nodiscard]] Expected<void> addRegisterAllocationPipeline(MachineFunctionPassManager &Pipeline) { +[[nodiscard]] Expected<void> addRegisterAllocationPipeline(MachineFunctionPassManager &Pipeline, + const RISCVSubtarget &Subtarget, + RISCVPipelineOptions Options) { auto Added = addPass<PreRATargetPseudoExpansionPass>(Pipeline, pseudoExpansionInfo()); if (!Added) return std::unexpected(Added.error()); - Added = addPreRegisterAllocationOptimizationPipeline(Pipeline, optimizationPipelineInfo()); + Added = addPreRegisterAllocationOptimizationPipeline( + Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler)); if (!Added) return std::unexpected(Added.error()); return addPass<PBQPAllocatorPass>(Pipeline, registerAllocationInfo()); @@ -81,14 +87,14 @@ template <typename PassT, typename... ArgumentT> auto Added = addInitialPipeline(Pipeline, Subtarget, Options); if (!Added) return std::unexpected(Added.error()); - Added = addSSAExitPipeline(Pipeline); + Added = addSSAExitPipeline(Pipeline, Subtarget, Options); if (!Added) return std::unexpected(Added.error()); - Added = addRegisterAllocationPipeline(Pipeline); + Added = addRegisterAllocationPipeline(Pipeline, Subtarget, Options); if (!Added) return std::unexpected(Added.error()); return addPostRegisterAllocationPipeline( - Pipeline, optimizationPipelineInfo(), + Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler), MachineOptimizationPipelineOptions{.UseTargetCopyInstructions = Options.UseTargetCopyInstructions}); } @@ -119,7 +125,8 @@ Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline, return std::unexpected(Added.error()); } if (!Function.properties().has(MachineFunctionProperty::TiedOpsRewritten)) { - auto Added = addSelectedSSAOptimizationPipeline(Pipeline, optimizationPipelineInfo()); + auto Added = addSelectedSSAOptimizationPipeline( + Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler)); if (!Added) return std::unexpected(Added.error()); if (!Function.properties().has(MachineFunctionProperty::NoPHIs)) { @@ -134,13 +141,13 @@ Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline, return std::unexpected(Added.error()); } if (!Function.properties().has(MachineFunctionProperty::NoVRegs)) { - auto Added = addRegisterAllocationPipeline(Pipeline); + auto Added = addRegisterAllocationPipeline(Pipeline, Subtarget, Options); if (!Added) return std::unexpected(Added.error()); } if (!Function.properties().has(MachineFunctionProperty::NoExecutablePseudos)) { auto Added = addPostRegisterAllocationPipeline( - Pipeline, optimizationPipelineInfo(), + Pipeline, optimizationPipelineInfo(Subtarget, Options.DebugMachineScheduler), MachineOptimizationPipelineOptions{.UseTargetCopyInstructions = Options.UseTargetCopyInstructions}); if (!Added) diff --git a/backend/lib/Target/RISCV/RISCVScheduling.cpp b/backend/lib/Target/RISCV/RISCVScheduling.cpp index a58b913..b7947d4 100644 --- a/backend/lib/Target/RISCV/RISCVScheduling.cpp +++ b/backend/lib/Target/RISCV/RISCVScheduling.cpp @@ -1,11 +1,15 @@ // SPDX-License-Identifier: GPL-3.0-or-later #include "RISCV.h" +#include "rcc/CodeGen/MacroFusion.h" +#include "rcc/CodeGen/ScheduleDAG.h" #include "rcc/Target/RISCV/RISCVTarget.h" +#include <array> #include <cstdint> -#include <cstdlib> +#include <memory> #include <optional> +#include <span> #include <string> #include <utility> #include <vector> @@ -13,6 +17,28 @@ namespace rcc::riscv { namespace { +#define GET_MACRO_FUSION_RULES +#include "RISCVGenMacroFusion.inc" + +class RISCVSchedulingHooks final : public TargetSchedulingHooks { +public: + explicit RISCVSchedulingHooks(const RISCVSubtargetFeatures &Features) { + for (const MacroFusionRule &Rule : generatedMacroFusionRules()) { + if (Features.hasFeature(Rule.Feature)) + MacroFusionRules.push_back(Rule); + } + } + + [[nodiscard]] Expected<void> mutateScheduleDAG(ScheduleDAG &DAG, const MachineFunction &, + const TargetDescription &Target, ScheduleDAGMode, + bool EmitDebugOutput) const override { + return applyMacroFusion(DAG, MacroFusionRules, Target, EmitDebugOutput); + } + +private: + std::vector<MacroFusionRule> MacroFusionRules; +}; + enum class Resource : std::uint32_t { Core = 1, IntegerALU = 2, @@ -72,7 +98,7 @@ enum class PressureSet : std::uint32_t { return {}; } -[[nodiscard]] TargetSchedulingModelDesc createDescription() { +[[nodiscard]] TargetSchedulingModelDesc createDescription(const TargetSchedulingHooks &Hooks) { TargetSchedulingModelDesc Description; Description.IssueWidth = 2; Description.DispatchLimit = 2; @@ -121,17 +147,19 @@ enum class PressureSet : std::uint32_t { registerClass(RegisterClass::FPR32), registerClass(RegisterClass::FPR32C)}, 32}, }; + Description.Hooks = &Hooks; return Description; } } // namespace -const TargetSchedulingModel &schedulingModel() noexcept { - static const Expected<TargetSchedulingModel> Model = - TargetSchedulingModel::create(createDescription()); - if (!Model) - std::abort(); - return *Model; +std::unique_ptr<TargetSchedulingHooks> +createSchedulingHooks(const RISCVSubtargetFeatures &Features) { + return std::make_unique<RISCVSchedulingHooks>(Features); +} + +Expected<TargetSchedulingModel> createSchedulingModel(const TargetSchedulingHooks &Hooks) { + return TargetSchedulingModel::create(createDescription(Hooks)); } } // namespace rcc::riscv diff --git a/backend/lib/Target/RISCV/RISCVSubtarget.cpp b/backend/lib/Target/RISCV/RISCVSubtarget.cpp index 4b3064d..c30c898 100644 --- a/backend/lib/Target/RISCV/RISCVSubtarget.cpp +++ b/backend/lib/Target/RISCV/RISCVSubtarget.cpp @@ -7,10 +7,13 @@ #include "GISel/RISCVRegisterBankInfo.h" #include "RISCV.h" #include "rcc/CodeGen/GlobalISel/InstructionSelector.h" +#include "rcc/CodeGen/TargetSchedulingModel.h" #include <array> #include <cstddef> +#include <cstdlib> #include <string_view> +#include <utility> namespace rcc::riscv { namespace { @@ -50,6 +53,7 @@ constexpr std::array OptionNames{ OptionName{"fusion-addi-load", RISCVSubtargetOption::FusionAddImmediateLoad}, OptionName{"fusion-auipc-addi", RISCVSubtargetOption::FusionAUIPCAddImmediate}, OptionName{"fusion-auipc-load", RISCVSubtargetOption::FusionAUIPCLoad}, + OptionName{"fusion-bfext", RISCVSubtargetOption::FusionBitfieldExtract}, OptionName{"fusion-ld-add", RISCVSubtargetOption::FusionLoadDoubleAdd}, OptionName{"fusion-logic-imm-reg", RISCVSubtargetOption::FusionLogicImmediateRegister}, OptionName{"fusion-logic-reg-imm", RISCVSubtargetOption::FusionLogicRegisterImmediate}, @@ -58,6 +62,7 @@ constexpr std::array OptionNames{ OptionName{"fusion-lui-load", RISCVSubtargetOption::FusionLUILoad}, OptionName{"fusion-mul-add", RISCVSubtargetOption::FusionMultiplyAdd}, OptionName{"fusion-shift-bit-extract", RISCVSubtargetOption::FusionShiftBitExtract}, + OptionName{"fusion-shxadd-load", RISCVSubtargetOption::FusionShiftedAddLoad}, OptionName{"fusion-shifted-zextw", RISCVSubtargetOption::FusionShiftedZeroExtendWord}, OptionName{"fusion-zexth", RISCVSubtargetOption::FusionZeroExtendHalf}, OptionName{"fusion-zextw", RISCVSubtargetOption::FusionZeroExtendWord}, @@ -171,9 +176,23 @@ bool RISCVSubtargetFeatures::has(RISCVSubtargetOption Option) const noexcept { return (Options & optionBit(Option)) != 0; } +bool RISCVSubtargetFeatures::hasFeature(std::string_view Feature) const noexcept { + if (const OptionName *Option = findOption(Feature)) + return has(Option->Option); + if (const ExtensionName *Extension = findExtension(Feature)) + return has(Extension->Extension); + return false; +} + RISCVSubtarget::RISCVSubtarget(RISCVSubtargetFeatures Features, RelocationModel Relocation, CodeModel Code) - : Features(Features), Relocation(Relocation), Code(Code) {} + : Features(Features), Relocation(Relocation), Code(Code), + SchedulingHooks(createSchedulingHooks(Features)) { + auto Model = createSchedulingModel(*SchedulingHooks); + if (!Model) + std::abort(); + SchedulingModel = std::make_unique<TargetSchedulingModel>(std::move(*Model)); +} RISCVSubtarget::~RISCVSubtarget() = default; @@ -201,4 +220,8 @@ const RISCVRegisterBankInfo *RISCVSubtarget::getRegBankInfo() const { return RegBankInfo.get(); } +const TargetSchedulingModel &RISCVSubtarget::schedulingModel() const noexcept { + return *SchedulingModel; +} + } // namespace rcc::riscv diff --git a/backend/lib/Tooling/PipelineDriver.cpp b/backend/lib/Tooling/PipelineDriver.cpp index 76951b6..0ba0c54 100644 --- a/backend/lib/Tooling/PipelineDriver.cpp +++ b/backend/lib/Tooling/PipelineDriver.cpp @@ -79,6 +79,24 @@ struct FunctionRunResult final { }); } +[[nodiscard]] bool hasDebugType(const BackendInvocation &Invocation, + std::string_view DebugType) noexcept { + const auto Option = std::ranges::find(Invocation.TargetOptions, std::string_view{"debug-only"}, + &BackendOption::Name); + if (Option == Invocation.TargetOptions.end()) + return false; + std::string_view Types = Option->Value; + while (!Types.empty()) { + const std::size_t Comma = Types.find(','); + if (Types.substr(0, Comma) == DebugType) + return true; + if (Comma == std::string_view::npos) + break; + Types.remove_prefix(Comma + 1U); + } + return false; +} + [[nodiscard]] std::optional<BackendStage> stageAfterPass(std::string_view Pass) noexcept { if (Pass == "legalizer") return BackendStage::LegalizedMIR; @@ -108,12 +126,14 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio GlobalISelAbort = *Parsed; } MachineFunctionPassManager Pipeline(Options); + const bool DebugMachineScheduler = hasDebugType(Invocation, "machine-scheduler"); if (Invocation.PassPipeline.size() == 1 && Invocation.PassPipeline.front() == "default") { auto Added = riscv::addCanonicalPipeline( Pipeline, Function, Subtarget, riscv::RISCVPipelineOptions{.Optimization = Invocation.Optimization, .UseTargetCopyInstructions = true, - .GlobalISelAbort = GlobalISelAbort}); + .GlobalISelAbort = GlobalISelAbort, + .DebugMachineScheduler = DebugMachineScheduler}); if (!Added) return std::unexpected(Added.error()); } else { @@ -130,7 +150,8 @@ createPasses(const MachineFunction &Function, const BackendInvocation &Invocatio Name, Subtarget, riscv::RISCVPipelineOptions{.Optimization = Invocation.Optimization, .UseTargetCopyInstructions = UseTargetCopyInstructions, - .GlobalISelAbort = GlobalISelAbort}); + .GlobalISelAbort = GlobalISelAbort, + .DebugMachineScheduler = DebugMachineScheduler}); if (!Pass) return std::unexpected(Pass.error()); auto Added = Pipeline.addPass(std::move(*Pass)); |