From 495c675771f43cfa12ab7a426a538be72fec1805 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 9 Aug 2026 17:03:19 +0800 Subject: [CodeGen] Implement machine optimization and scheduling --- .../include/rcc/CodeGen/InstructionDescriptor.h | 1 + .../include/rcc/CodeGen/MachineBlockPlacement.h | 25 +++ .../rcc/CodeGen/MachineBranchOptimization.h | 39 +++++ .../include/rcc/CodeGen/MachineBranchRelaxation.h | 39 +++++ backend/include/rcc/CodeGen/MachineCSE.h | 35 ++++ backend/include/rcc/CodeGen/MachineCombiner.h | 40 +++++ .../include/rcc/CodeGen/MachineCombinerPattern.h | 82 ++++++++++ .../include/rcc/CodeGen/MachineCompilationStatus.h | 1 + .../include/rcc/CodeGen/MachineCopyPropagation.h | 46 ++++++ backend/include/rcc/CodeGen/MachineDCE.h | 24 +++ backend/include/rcc/CodeGen/MachineFallthrough.h | 27 ++++ backend/include/rcc/CodeGen/MachineFinalization.h | 36 +++++ backend/include/rcc/CodeGen/MachineFunction.h | 4 + .../include/rcc/CodeGen/MachineFunctionRecords.h | 3 + backend/include/rcc/CodeGen/MachineIRTypes.h | 4 + backend/include/rcc/CodeGen/MachineLICM.h | 45 ++++++ .../include/rcc/CodeGen/MachineLivenessRepair.h | 23 +++ backend/include/rcc/CodeGen/MachineMemoryFolding.h | 39 +++++ backend/include/rcc/CodeGen/MachineOperand.h | 1 + .../rcc/CodeGen/MachineOptimizationPipeline.h | 43 +++++ .../include/rcc/CodeGen/MachinePseudoExpansion.h | 72 +++++++++ backend/include/rcc/CodeGen/MachineScheduler.h | 37 +++++ .../include/rcc/CodeGen/MachineShrinkWrapping.h | 36 +++++ backend/include/rcc/CodeGen/MachineSink.h | 38 +++++ .../include/rcc/CodeGen/MachineStackSlotColoring.h | 34 ++++ .../include/rcc/CodeGen/MachineTailDuplication.h | 40 +++++ backend/include/rcc/CodeGen/MachineTailMerge.h | 39 +++++ backend/include/rcc/CodeGen/PostRAScheduler.h | 31 ++++ backend/include/rcc/CodeGen/RegisterPressure.h | 107 +++++++++++++ backend/include/rcc/CodeGen/ScheduleDAG.h | 110 +++++++++++++ .../include/rcc/CodeGen/ScheduleHazardRecognizer.h | 68 ++++++++ backend/include/rcc/CodeGen/TargetBranchInfo.h | 66 ++++++++ backend/include/rcc/CodeGen/TargetFrameLowering.h | 5 + backend/include/rcc/CodeGen/TargetMemoryFolding.h | 43 +++++ .../include/rcc/CodeGen/TargetPseudoExpansion.h | 40 +++++ .../include/rcc/CodeGen/TargetSchedulingModel.h | 178 +++++++++++++++++++++ 36 files changed, 1501 insertions(+) create mode 100644 backend/include/rcc/CodeGen/MachineBlockPlacement.h create mode 100644 backend/include/rcc/CodeGen/MachineBranchOptimization.h create mode 100644 backend/include/rcc/CodeGen/MachineBranchRelaxation.h create mode 100644 backend/include/rcc/CodeGen/MachineCSE.h create mode 100644 backend/include/rcc/CodeGen/MachineCombiner.h create mode 100644 backend/include/rcc/CodeGen/MachineCombinerPattern.h create mode 100644 backend/include/rcc/CodeGen/MachineCopyPropagation.h create mode 100644 backend/include/rcc/CodeGen/MachineDCE.h create mode 100644 backend/include/rcc/CodeGen/MachineFallthrough.h create mode 100644 backend/include/rcc/CodeGen/MachineFinalization.h create mode 100644 backend/include/rcc/CodeGen/MachineLICM.h create mode 100644 backend/include/rcc/CodeGen/MachineLivenessRepair.h create mode 100644 backend/include/rcc/CodeGen/MachineMemoryFolding.h create mode 100644 backend/include/rcc/CodeGen/MachineOptimizationPipeline.h create mode 100644 backend/include/rcc/CodeGen/MachinePseudoExpansion.h create mode 100644 backend/include/rcc/CodeGen/MachineScheduler.h create mode 100644 backend/include/rcc/CodeGen/MachineShrinkWrapping.h create mode 100644 backend/include/rcc/CodeGen/MachineSink.h create mode 100644 backend/include/rcc/CodeGen/MachineStackSlotColoring.h create mode 100644 backend/include/rcc/CodeGen/MachineTailDuplication.h create mode 100644 backend/include/rcc/CodeGen/MachineTailMerge.h create mode 100644 backend/include/rcc/CodeGen/PostRAScheduler.h create mode 100644 backend/include/rcc/CodeGen/RegisterPressure.h create mode 100644 backend/include/rcc/CodeGen/ScheduleDAG.h create mode 100644 backend/include/rcc/CodeGen/ScheduleHazardRecognizer.h create mode 100644 backend/include/rcc/CodeGen/TargetBranchInfo.h create mode 100644 backend/include/rcc/CodeGen/TargetMemoryFolding.h create mode 100644 backend/include/rcc/CodeGen/TargetPseudoExpansion.h create mode 100644 backend/include/rcc/CodeGen/TargetSchedulingModel.h (limited to 'backend/include/rcc/CodeGen') diff --git a/backend/include/rcc/CodeGen/InstructionDescriptor.h b/backend/include/rcc/CodeGen/InstructionDescriptor.h index ca2c5cf..ad71213 100644 --- a/backend/include/rcc/CodeGen/InstructionDescriptor.h +++ b/backend/include/rcc/CodeGen/InstructionDescriptor.h @@ -199,6 +199,7 @@ enum class PseudoOwner : std::uint8_t { PostRAExpansion, Finalization, AsmPrinter, + TargetLateExpansion, }; enum class PipelineStage : std::uint8_t { diff --git a/backend/include/rcc/CodeGen/MachineBlockPlacement.h b/backend/include/rcc/CodeGen/MachineBlockPlacement.h new file mode 100644 index 0000000..27a06f4 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineBlockPlacement.h @@ -0,0 +1,25 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEBLOCKPLACEMENT_H +#define RCC_CODEGEN_MACHINEBLOCKPLACEMENT_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class MachineBlockPlacementPass final : public MachineFunctionPass { +public: + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) const; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEBLOCKPLACEMENT_H diff --git a/backend/include/rcc/CodeGen/MachineBranchOptimization.h b/backend/include/rcc/CodeGen/MachineBranchOptimization.h new file mode 100644 index 0000000..a71c20f --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineBranchOptimization.h @@ -0,0 +1,39 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEBRANCHOPTIMIZATION_H +#define RCC_CODEGEN_MACHINEBRANCHOPTIMIZATION_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetBranchInfo; + +struct MachineBranchOptimizationOptions final { + std::size_t MaximumThreadedEdges = 10'000; +}; + +class MachineBranchOptimizationPass final : public MachineFunctionPass { +public: + explicit MachineBranchOptimizationPass(const TargetBranchInfo &Info, + MachineBranchOptimizationOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetBranchInfo *Info; + MachineBranchOptimizationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEBRANCHOPTIMIZATION_H diff --git a/backend/include/rcc/CodeGen/MachineBranchRelaxation.h b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h new file mode 100644 index 0000000..1793a54 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineBranchRelaxation.h @@ -0,0 +1,39 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEBRANCHRELAXATION_H +#define RCC_CODEGEN_MACHINEBRANCHRELAXATION_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetBranchInfo; + +struct MachineBranchRelaxationOptions final { + std::size_t ConvergenceWatchdog = 1000000; +}; + +class MachineBranchRelaxationPass final : public MachineFunctionPass { +public: + explicit MachineBranchRelaxationPass(const TargetBranchInfo &Info, + MachineBranchRelaxationOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetBranchInfo *Info; + MachineBranchRelaxationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEBRANCHRELAXATION_H diff --git a/backend/include/rcc/CodeGen/MachineCSE.h b/backend/include/rcc/CodeGen/MachineCSE.h new file mode 100644 index 0000000..1c2057b --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineCSE.h @@ -0,0 +1,35 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINECSE_H +#define RCC_CODEGEN_MACHINECSE_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +struct MachineCSEOptions final { + std::size_t MaximumComparisons = 100'000; +}; + +class MachineCSEPass final : public MachineFunctionPass { +public: + explicit MachineCSEPass(MachineCSEOptions Options = {}) : Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses); + + MachineCSEOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINECSE_H diff --git a/backend/include/rcc/CodeGen/MachineCombiner.h b/backend/include/rcc/CodeGen/MachineCombiner.h new file mode 100644 index 0000000..943d6ad --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineCombiner.h @@ -0,0 +1,40 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINECOMBINER_H +#define RCC_CODEGEN_MACHINECOMBINER_H + +#include "rcc/CodeGen/MachineCombinerPattern.h" +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +struct MachineCombinerOptions final { + std::size_t MaximumRewrites = 4096; + std::size_t MaximumIterations = 8; +}; + +class MachineCombinerPass final : public MachineFunctionPass { +public: + MachineCombinerPass(const TargetMachineCombinerInfo &Info, MachineCombinerStage Stage, + MachineCombinerOptions Options = {}) noexcept + : Info(&Info), Stage(Stage), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetMachineCombinerInfo *Info; + MachineCombinerStage Stage; + MachineCombinerOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINECOMBINER_H diff --git a/backend/include/rcc/CodeGen/MachineCombinerPattern.h b/backend/include/rcc/CodeGen/MachineCombinerPattern.h new file mode 100644 index 0000000..69df70a --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineCombinerPattern.h @@ -0,0 +1,82 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINECOMBINERPATTERN_H +#define RCC_CODEGEN_MACHINECOMBINERPATTERN_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +enum class MachineCombinerStage : std::uint8_t { + SelectedSSA, + PreRegisterAllocation, + PostRegisterAllocation, + PostFrame, +}; + +using MachineCombinerStageMask = std::uint8_t; + +[[nodiscard]] constexpr MachineCombinerStageMask +machineCombinerStageMask(MachineCombinerStage Stage) noexcept { + return static_cast(1U << static_cast(Stage)); +} + +enum class MachineCombinerPredicateKind : std::uint8_t { + ImmediateEquals, + RegisterEquals, + PhysicalRegisterEquals, + RegisterIsVirtual, + RegisterIsPhysical, +}; + +struct MachineCombinerPredicate final { + MachineCombinerPredicateKind Kind = MachineCombinerPredicateKind::ImmediateEquals; + std::size_t Operand = 0; + std::size_t OtherOperand = 0; + std::int64_t Value = 0; +}; + +enum class MachineCombinerActionKind : std::uint8_t { + ReplaceDefWithOperandAndErase, +}; + +struct MachineCombinerAction final { + MachineCombinerActionKind Kind = MachineCombinerActionKind::ReplaceDefWithOperandAndErase; + std::size_t DefinitionOperand = 0; + std::size_t SourceOperand = 0; +}; + +struct MachineCombinerPattern final { + std::string Name; + Opcode RootOpcode; + MachineCombinerStageMask Stages = 0; + std::vector Predicates; + MachineCombinerAction Action; +}; + +class TargetMachineCombinerInfo final { +public: + [[nodiscard]] static Expected + create(std::vector Patterns); + + [[nodiscard]] std::span patterns(Opcode RootOpcode) const noexcept; + +private: + explicit TargetMachineCombinerInfo(std::vector Patterns) + : Patterns(std::move(Patterns)) {} + + std::vector Patterns; + std::unordered_map> MatchTable; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINECOMBINERPATTERN_H diff --git a/backend/include/rcc/CodeGen/MachineCompilationStatus.h b/backend/include/rcc/CodeGen/MachineCompilationStatus.h index f889574..9746a4d 100644 --- a/backend/include/rcc/CodeGen/MachineCompilationStatus.h +++ b/backend/include/rcc/CodeGen/MachineCompilationStatus.h @@ -29,6 +29,7 @@ enum class MachineCompilationState : std::uint8_t { FinalizationFailed, AssemblyLoweringFailed, InternalError, + SchedulingFailed, Count, }; diff --git a/backend/include/rcc/CodeGen/MachineCopyPropagation.h b/backend/include/rcc/CodeGen/MachineCopyPropagation.h new file mode 100644 index 0000000..5f84ac6 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineCopyPropagation.h @@ -0,0 +1,46 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINECOPYPROPAGATION_H +#define RCC_CODEGEN_MACHINECOPYPROPAGATION_H + +#include "rcc/CodeGen/MachinePass.h" + +#include +#include + +namespace rcc { + +class TargetSSAInfo; + +enum class MachineCopyPropagationStage : std::uint8_t { + PreRegisterAllocation, + PostRegisterAllocation, +}; + +struct MachineCopyPropagationOptions final { + std::size_t MaximumPropagatedCopies = 10'000; +}; + +class MachineCopyPropagationPass final : public MachineFunctionPass { +public: + MachineCopyPropagationPass(const TargetSSAInfo &Info, MachineCopyPropagationStage Stage, + MachineCopyPropagationOptions Options = {}) noexcept + : Info(&Info), Stage(Stage), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetSSAInfo *Info; + MachineCopyPropagationStage Stage; + MachineCopyPropagationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINECOPYPROPAGATION_H diff --git a/backend/include/rcc/CodeGen/MachineDCE.h b/backend/include/rcc/CodeGen/MachineDCE.h new file mode 100644 index 0000000..893108d --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineDCE.h @@ -0,0 +1,24 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEDCE_H +#define RCC_CODEGEN_MACHINEDCE_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class MachineDCEPass final : public MachineFunctionPass { +public: + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target); +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEDCE_H diff --git a/backend/include/rcc/CodeGen/MachineFallthrough.h b/backend/include/rcc/CodeGen/MachineFallthrough.h new file mode 100644 index 0000000..413efe2 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineFallthrough.h @@ -0,0 +1,27 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEFALLTHROUGH_H +#define RCC_CODEGEN_MACHINEFALLTHROUGH_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetBranchInfo; + +class MachineFallthroughPass final : public MachineFunctionPass { +public: + explicit MachineFallthroughPass(const TargetBranchInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetBranchInfo *Info; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEFALLTHROUGH_H diff --git a/backend/include/rcc/CodeGen/MachineFinalization.h b/backend/include/rcc/CodeGen/MachineFinalization.h new file mode 100644 index 0000000..147da86 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineFinalization.h @@ -0,0 +1,36 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEFINALIZATION_H +#define RCC_CODEGEN_MACHINEFINALIZATION_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetBranchInfo; + +class FinalizeEmissionPseudosPass final : public MachineFunctionPass { +public: + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; +}; + +class FinalEncodabilityVerifierPass final : public MachineFunctionPass { +public: + explicit FinalEncodabilityVerifierPass(const TargetBranchInfo &BranchInfo) noexcept + : BranchInfo(&BranchInfo) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetBranchInfo *BranchInfo; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEFINALIZATION_H diff --git a/backend/include/rcc/CodeGen/MachineFunction.h b/backend/include/rcc/CodeGen/MachineFunction.h index c188d4a..563aa4e 100644 --- a/backend/include/rcc/CodeGen/MachineFunction.h +++ b/backend/include/rcc/CodeGen/MachineFunction.h @@ -157,6 +157,10 @@ public: [[nodiscard]] Expected appendBlock(MachineBasicBlock &Block); [[nodiscard]] Expected insertBlockBefore(MachineBasicBlock &Position, MachineBasicBlock &Block); + [[nodiscard]] Expected moveBlockBefore(MachineBasicBlock &Position, + MachineBasicBlock &Block); + [[nodiscard]] Expected moveBlockAfter(MachineBasicBlock &Position, + MachineBasicBlock &Block); [[nodiscard]] Expected removeBlock(MachineBasicBlock &Block); [[nodiscard]] MachineBasicBlock *firstBlock() noexcept { diff --git a/backend/include/rcc/CodeGen/MachineFunctionRecords.h b/backend/include/rcc/CodeGen/MachineFunctionRecords.h index b792494..645d514 100644 --- a/backend/include/rcc/CodeGen/MachineFunctionRecords.h +++ b/backend/include/rcc/CodeGen/MachineFunctionRecords.h @@ -117,6 +117,9 @@ public: [[nodiscard]] Expected addCalledGlobal(MachineCalledGlobal CalledGlobal); + [[nodiscard]] Expected replaceInstructionReference(MachineInstrStableID OldInstruction, + MachineInstrStableID NewInstruction); + [[nodiscard]] std::span prefetchTargets() const noexcept { return PrefetchTargets; } diff --git a/backend/include/rcc/CodeGen/MachineIRTypes.h b/backend/include/rcc/CodeGen/MachineIRTypes.h index ea65eff..45b5ecf 100644 --- a/backend/include/rcc/CodeGen/MachineIRTypes.h +++ b/backend/include/rcc/CodeGen/MachineIRTypes.h @@ -50,6 +50,8 @@ struct RegisterUnitIDTag; struct RegisterBankIDTag; struct RegisterClassIDTag; struct SchedulingClassIDTag; +struct ProcessorResourceIDTag; +struct RegisterPressureSetIDTag; struct ImmediatePredicateIDTag; struct NamedOperandIDTag; struct TargetOperandTypeIDTag; @@ -76,6 +78,8 @@ using RegisterUnitID = MachineIndex; using RegisterBankID = MachineIndex; using RegisterClassID = MachineIndex; using SchedulingClassID = MachineIndex; +using ProcessorResourceID = MachineIndex; +using RegisterPressureSetID = MachineIndex; using ImmediatePredicateID = MachineIndex; using NamedOperandID = MachineIndex; using TargetOperandTypeID = MachineIndex; diff --git a/backend/include/rcc/CodeGen/MachineLICM.h b/backend/include/rcc/CodeGen/MachineLICM.h new file mode 100644 index 0000000..66b7ef8 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineLICM.h @@ -0,0 +1,45 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINELICM_H +#define RCC_CODEGEN_MACHINELICM_H + +#include "rcc/CodeGen/MachinePass.h" + +#include +#include + +namespace rcc { + +enum class MachineCodeMotionStage : std::uint8_t { + SelectedSSA, + PostRegisterAllocation, +}; + +struct MachineLICMOptions final { + std::size_t MaximumHoistedInstructions = 10'000; + std::size_t MaximumHoistedDefinitionsPerLoop = 256; +}; + +class MachineLICMPass final : public MachineFunctionPass { +public: + explicit MachineLICMPass(MachineLICMOptions Options = {}) : Options(Options) {} + MachineLICMPass(MachineCodeMotionStage Stage, MachineLICMOptions Options = {}) + : Stage(Stage), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses); + + MachineCodeMotionStage Stage = MachineCodeMotionStage::SelectedSSA; + MachineLICMOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINELICM_H diff --git a/backend/include/rcc/CodeGen/MachineLivenessRepair.h b/backend/include/rcc/CodeGen/MachineLivenessRepair.h new file mode 100644 index 0000000..049e166 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineLivenessRepair.h @@ -0,0 +1,23 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINELIVENESSREPAIR_H +#define RCC_CODEGEN_MACHINELIVENESSREPAIR_H + +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/Support/Error.h" + +#include + +namespace rcc { + +class MachineBasicBlock; +class TargetDescription; + +[[nodiscard]] Expected +repairPostRAMachineBlockLiveness(std::span Blocks, + const TargetDescription &Target, + const LiveVariablesAnalysis::Result &Liveness); + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINELIVENESSREPAIR_H diff --git a/backend/include/rcc/CodeGen/MachineMemoryFolding.h b/backend/include/rcc/CodeGen/MachineMemoryFolding.h new file mode 100644 index 0000000..9a5b47a --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineMemoryFolding.h @@ -0,0 +1,39 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEMEMORYFOLDING_H +#define RCC_CODEGEN_MACHINEMEMORYFOLDING_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetMemoryFoldingInfo; + +struct MachineMemoryFoldingOptions final { + std::size_t MaximumFolds = 4'096; +}; + +class MachineMemoryFoldingPass final : public MachineFunctionPass { +public: + explicit MachineMemoryFoldingPass(const TargetMemoryFoldingInfo &Info, + MachineMemoryFoldingOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetMemoryFoldingInfo *Info; + MachineMemoryFoldingOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEMEMORYFOLDING_H diff --git a/backend/include/rcc/CodeGen/MachineOperand.h b/backend/include/rcc/CodeGen/MachineOperand.h index 31ad7e4..986ba0e 100644 --- a/backend/include/rcc/CodeGen/MachineOperand.h +++ b/backend/include/rcc/CodeGen/MachineOperand.h @@ -450,6 +450,7 @@ public: [[nodiscard]] Expected setRegisterFlags(RegisterOperandFlags Flags); [[nodiscard]] Expected setSubReg(SubRegIndex SubReg); [[nodiscard]] Expected setBasicBlock(MachineBasicBlock &Block); + [[nodiscard]] Expected setFrameIndex(FrameIndex Index); [[nodiscard]] std::optional tiedOperandIndex() const noexcept { return TiedOperandIndex; diff --git a/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h b/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h new file mode 100644 index 0000000..0953437 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineOptimizationPipeline.h @@ -0,0 +1,43 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEOPTIMIZATIONPIPELINE_H +#define RCC_CODEGEN_MACHINEOPTIMIZATIONPIPELINE_H + +#include "rcc/CodeGen/MachinePass.h" + +namespace rcc { + +class TargetBranchInfo; +class TargetFrameLowering; +class TargetMachineCombinerInfo; +class TargetMemoryFoldingInfo; +class TargetPseudoExpansionInfo; +class TargetSchedulingModel; +class TargetSSAInfo; + +struct MachineOptimizationPipelineTargetInfo final { + const TargetSSAInfo &SSA; + const TargetMachineCombinerInfo &Combiner; + const TargetMemoryFoldingInfo &MemoryFolding; + const TargetFrameLowering &FrameLowering; + const TargetPseudoExpansionInfo &PseudoExpansion; + const TargetSchedulingModel &SchedulingModel; + const TargetBranchInfo &BranchInfo; +}; + +[[nodiscard]] Expected registerMachineOptimizationAnalyses(MachineAnalysisManager &Analyses); + +[[nodiscard]] Expected +addSelectedSSAOptimizationPipeline(MachinePassManager &Pipeline, + const MachineOptimizationPipelineTargetInfo &TargetInfo); + +[[nodiscard]] Expected addPreRegisterAllocationOptimizationPipeline( + MachinePassManager &Pipeline, const MachineOptimizationPipelineTargetInfo &TargetInfo); + +[[nodiscard]] Expected +addPostRegisterAllocationPipeline(MachinePassManager &Pipeline, + const MachineOptimizationPipelineTargetInfo &TargetInfo); + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEOPTIMIZATIONPIPELINE_H diff --git a/backend/include/rcc/CodeGen/MachinePseudoExpansion.h b/backend/include/rcc/CodeGen/MachinePseudoExpansion.h new file mode 100644 index 0000000..1dfb6ba --- /dev/null +++ b/backend/include/rcc/CodeGen/MachinePseudoExpansion.h @@ -0,0 +1,72 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEPSEUDOEXPANSION_H +#define RCC_CODEGEN_MACHINEPSEUDOEXPANSION_H + +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/TargetPseudoExpansion.h" + +namespace rcc { + +class TargetBranchInfo; +class TargetPseudoExpansionInfo; + +class PreparePostRAPseudosPass final : public MachineFunctionPass { +public: + explicit PreparePostRAPseudosPass(const TargetPseudoExpansionInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetPseudoExpansionInfo *Info; +}; + +class PrePEITargetPseudoExpansionPass final : public MachineFunctionPass { +public: + explicit PrePEITargetPseudoExpansionPass(const TargetPseudoExpansionInfo &Info) noexcept + : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetPseudoExpansionInfo *Info; +}; + +class ExpandPostRAPseudosPass final : public MachineFunctionPass { +public: + explicit ExpandPostRAPseudosPass(const TargetPseudoExpansionInfo &Info) noexcept : Info(&Info) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetPseudoExpansionInfo *Info; +}; + +class TargetLatePseudoExpansionPass final : public MachineFunctionPass { +public: + TargetLatePseudoExpansionPass(const TargetPseudoExpansionInfo &Info, + const TargetBranchInfo &BranchInfo) noexcept + : Info(&Info), BranchInfo(&BranchInfo) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetPseudoExpansionInfo *Info; + const TargetBranchInfo *BranchInfo; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEPSEUDOEXPANSION_H diff --git a/backend/include/rcc/CodeGen/MachineScheduler.h b/backend/include/rcc/CodeGen/MachineScheduler.h new file mode 100644 index 0000000..2b48fe7 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineScheduler.h @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINESCHEDULER_H +#define RCC_CODEGEN_MACHINESCHEDULER_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetSchedulingModel; + +struct MachineSchedulerOptions final { + std::size_t MaximumRegionSize = 512; + bool EnableBidirectionalScheduling = true; +}; + +class MachineSchedulerPass final : public MachineFunctionPass { +public: + explicit MachineSchedulerPass(const TargetSchedulingModel &Model, + MachineSchedulerOptions Options = {}) noexcept + : Model(&Model), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetSchedulingModel *Model; + MachineSchedulerOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINESCHEDULER_H diff --git a/backend/include/rcc/CodeGen/MachineShrinkWrapping.h b/backend/include/rcc/CodeGen/MachineShrinkWrapping.h new file mode 100644 index 0000000..ec295cd --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineShrinkWrapping.h @@ -0,0 +1,36 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINESHRINKWRAPPING_H +#define RCC_CODEGEN_MACHINESHRINKWRAPPING_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetFrameLowering; + +struct MachineShrinkWrappingOptions final { + std::size_t MaximumAnalyzedBlocks = 10'000; +}; + +class MachineShrinkWrappingPass final : public MachineFunctionPass { +public: + explicit MachineShrinkWrappingPass(const TargetFrameLowering &Info, + MachineShrinkWrappingOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetFrameLowering *Info; + MachineShrinkWrappingOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINESHRINKWRAPPING_H diff --git a/backend/include/rcc/CodeGen/MachineSink.h b/backend/include/rcc/CodeGen/MachineSink.h new file mode 100644 index 0000000..92aceba --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineSink.h @@ -0,0 +1,38 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINESINK_H +#define RCC_CODEGEN_MACHINESINK_H + +#include "rcc/CodeGen/MachineLICM.h" + +#include + +namespace rcc { + +struct MachineSinkOptions final { + std::size_t MaximumSunkInstructions = 10'000; +}; + +class MachineSinkPass final : public MachineFunctionPass { +public: + explicit MachineSinkPass(MachineSinkOptions Options = {}) : Options(Options) {} + MachineSinkPass(MachineCodeMotionStage Stage, MachineSinkOptions Options = {}) + : Stage(Stage), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses); + + MachineCodeMotionStage Stage = MachineCodeMotionStage::SelectedSSA; + MachineSinkOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINESINK_H diff --git a/backend/include/rcc/CodeGen/MachineStackSlotColoring.h b/backend/include/rcc/CodeGen/MachineStackSlotColoring.h new file mode 100644 index 0000000..19c1c70 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineStackSlotColoring.h @@ -0,0 +1,34 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINESTACKSLOTCOLORING_H +#define RCC_CODEGEN_MACHINESTACKSLOTCOLORING_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +struct MachineStackSlotColoringOptions final { + std::size_t MaximumColoredSlots = 4'096; +}; + +class MachineStackSlotColoringPass final : public MachineFunctionPass { +public: + explicit MachineStackSlotColoringPass(MachineStackSlotColoringOptions Options = {}) noexcept + : Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function) const; + + MachineStackSlotColoringOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINESTACKSLOTCOLORING_H diff --git a/backend/include/rcc/CodeGen/MachineTailDuplication.h b/backend/include/rcc/CodeGen/MachineTailDuplication.h new file mode 100644 index 0000000..cd62509 --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineTailDuplication.h @@ -0,0 +1,40 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINETAILDUPLICATION_H +#define RCC_CODEGEN_MACHINETAILDUPLICATION_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetBranchInfo; + +struct MachineTailDuplicationOptions final { + std::size_t MaximumTailInstructions = 8; + std::size_t MaximumDuplicatedInstructions = 4'096; +}; + +class MachineTailDuplicationPass final : public MachineFunctionPass { +public: + explicit MachineTailDuplicationPass(const TargetBranchInfo &Info, + MachineTailDuplicationOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetBranchInfo *Info; + MachineTailDuplicationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINETAILDUPLICATION_H diff --git a/backend/include/rcc/CodeGen/MachineTailMerge.h b/backend/include/rcc/CodeGen/MachineTailMerge.h new file mode 100644 index 0000000..94084ac --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineTailMerge.h @@ -0,0 +1,39 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINETAILMERGE_H +#define RCC_CODEGEN_MACHINETAILMERGE_H + +#include "rcc/CodeGen/MachinePass.h" + +#include + +namespace rcc { + +class TargetBranchInfo; + +struct MachineTailMergeOptions final { + std::size_t MaximumMergedBlocks = 4'096; +}; + +class MachineTailMergePass final : public MachineFunctionPass { +public: + explicit MachineTailMergePass(const TargetBranchInfo &Info, + MachineTailMergeOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected + runImplementation(MachineFunction &Function, const TargetDescription &Target) const; + + const TargetBranchInfo *Info; + MachineTailMergeOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINETAILMERGE_H diff --git a/backend/include/rcc/CodeGen/PostRAScheduler.h b/backend/include/rcc/CodeGen/PostRAScheduler.h new file mode 100644 index 0000000..13b08df --- /dev/null +++ b/backend/include/rcc/CodeGen/PostRAScheduler.h @@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_POSTRASCHEDULER_H +#define RCC_CODEGEN_POSTRASCHEDULER_H + +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/MachineScheduler.h" + +namespace rcc { + +class TargetSchedulingModel; + +class PostRASchedulerPass final : public MachineFunctionPass { +public: + explicit PostRASchedulerPass(const TargetSchedulingModel &Model, + MachineSchedulerOptions Options = {}) noexcept + : Model(&Model), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetSchedulingModel *Model; + MachineSchedulerOptions Options; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_POSTRASCHEDULER_H diff --git a/backend/include/rcc/CodeGen/RegisterPressure.h b/backend/include/rcc/CodeGen/RegisterPressure.h new file mode 100644 index 0000000..fa1209a --- /dev/null +++ b/backend/include/rcc/CodeGen/RegisterPressure.h @@ -0,0 +1,107 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_REGISTERPRESSURE_H +#define RCC_CODEGEN_REGISTERPRESSURE_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/ScheduleDAG.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineFunction; +class TargetDescription; +class TargetSchedulingModel; +struct MachineBlockLiveness; + +namespace detail { +struct RegisterPressureBuilder; +} + +struct RegisterPressureValue final { + RegisterPressureSetID Set; + std::uint32_t Current = 0; + std::uint32_t Maximum = 0; + std::uint32_t Limit = 0; + + friend constexpr bool operator==(RegisterPressureValue, RegisterPressureValue) noexcept = default; +}; + +struct RegisterPressureCost final { + std::uint64_t CurrentPressure = 0; + std::uint64_t CurrentExcess = 0; + std::uint64_t PeakExcess = 0; + std::uint64_t PeakIncrease = 0; + + friend constexpr bool operator==(RegisterPressureCost, RegisterPressureCost) noexcept = default; +}; + +enum class RegisterPressureDirection : std::uint8_t { + TopDown, + BottomUp, +}; + +class RegisterPressureTracker final { +public: + [[nodiscard]] static Expected + create(const ScheduleDAG &DAG, const MachineFunction &Function, const TargetDescription &Target, + const TargetSchedulingModel &Model, ScheduleDAGMode Mode, + const MachineBlockLiveness &Liveness, + RegisterPressureDirection Direction = RegisterPressureDirection::TopDown); + + [[nodiscard]] std::span pressure() const noexcept { + return Pressure; + } + + [[nodiscard]] bool wasScheduled(std::size_t UnitID) const noexcept { + return UnitID < Scheduled.size() && Scheduled[UnitID]; + } + + [[nodiscard]] Expected evaluate(std::size_t UnitID) const; + [[nodiscard]] Expected schedule(std::size_t UnitID); + [[nodiscard]] RegisterPressureCost cost() const noexcept; + +private: + using EntityID = std::size_t; + + struct Entity final { + std::vector Sets; + std::size_t RemainingUses = 0; + bool HasDefinition = false; + bool DefinitionPending = false; + bool LiveOut = false; + bool Live = false; + }; + + struct Event final { + std::vector Uses; + std::vector Definitions; + }; + + struct UnitEffects final { + std::vector Events; + }; + + [[nodiscard]] Expected applyEvent(const Event &Value); + [[nodiscard]] Expected makeLive(EntityID Entity); + [[nodiscard]] Expected makeDead(EntityID Entity); + + std::vector Pressure; + std::unordered_map PressureIndexes; + std::vector Entities; + std::vector Effects; + std::vector Scheduled; + RegisterPressureDirection Direction = RegisterPressureDirection::TopDown; + + friend struct detail::RegisterPressureBuilder; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_REGISTERPRESSURE_H diff --git a/backend/include/rcc/CodeGen/ScheduleDAG.h b/backend/include/rcc/CodeGen/ScheduleDAG.h new file mode 100644 index 0000000..644d98a --- /dev/null +++ b/backend/include/rcc/CodeGen/ScheduleDAG.h @@ -0,0 +1,110 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_SCHEDULEDAG_H +#define RCC_CODEGEN_SCHEDULEDAG_H + +#include "rcc/CodeGen/StableID.h" +#include "rcc/CodeGen/TargetSchedulingModel.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class TargetDescription; + +enum class ScheduleDAGMode : std::uint8_t { + PreRegisterAllocation, + PostRegisterAllocation, +}; + +enum class ScheduleDependencyKind : std::uint8_t { + Data, + Anti, + Output, + Order, + Memory, + Barrier, + Artificial, + RegisterUnit, + RegisterMask, +}; + +struct ScheduleDependency final { + std::size_t Source = 0; + std::size_t Destination = 0; + ScheduleDependencyKind Kind = ScheduleDependencyKind::Artificial; + std::uint32_t Latency = 0; + + friend constexpr bool operator==(const ScheduleDependency &, + const ScheduleDependency &) noexcept = default; +}; + +struct ScheduleUnit final { + std::size_t ID = 0; + std::vector Instructions; + std::vector Predecessors; + std::vector Successors; + std::vector Resources; + std::uint32_t MicroOps = 0; + std::uint32_t Latency = 0; + std::uint64_t Depth = 0; + std::uint64_t Height = 0; + MachineInstrStableID StableID; +}; + +class ScheduleDAG final { +public: + [[nodiscard]] static Expected + build(MachineBasicBlock &Block, std::span Instructions, + const MachineFunction &Function, const TargetDescription &Target, + const TargetSchedulingModel &Model, ScheduleDAGMode Mode); + + [[nodiscard]] MachineBasicBlock &block() const noexcept { + return *Block; + } + + [[nodiscard]] std::span units() const noexcept { + return Units; + } + + [[nodiscard]] std::span units() noexcept { + return Units; + } + + [[nodiscard]] const ScheduleUnit *unit(std::size_t ID) const noexcept { + return ID < Units.size() ? &Units[ID] : nullptr; + } + + [[nodiscard]] Expected addArtificialDependency(std::size_t Source, std::size_t Destination, + std::uint32_t Latency); + +private: + explicit ScheduleDAG(MachineBasicBlock &Block) : Block(&Block) {} + + [[nodiscard]] Expected buildUnits(std::span Instructions, + const TargetDescription &Target, + const TargetSchedulingModel &Model); + [[nodiscard]] Expected buildRegisterDependencies(const MachineFunction &Function, + const TargetDescription &Target, + const TargetSchedulingModel &Model, + ScheduleDAGMode Mode); + [[nodiscard]] Expected buildMemoryDependencies(const TargetDescription &Target); + [[nodiscard]] Expected buildOrderDependencies(const TargetDescription &Target); + void addDependency(std::size_t Source, std::size_t Destination, ScheduleDependencyKind Kind, + std::uint32_t Latency); + void computeCriticalPaths(); + + MachineBasicBlock *Block; + std::vector Units; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_SCHEDULEDAG_H diff --git a/backend/include/rcc/CodeGen/ScheduleHazardRecognizer.h b/backend/include/rcc/CodeGen/ScheduleHazardRecognizer.h new file mode 100644 index 0000000..947db5e --- /dev/null +++ b/backend/include/rcc/CodeGen/ScheduleHazardRecognizer.h @@ -0,0 +1,68 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_SCHEDULEHAZARDRECOGNIZER_H +#define RCC_CODEGEN_SCHEDULEHAZARDRECOGNIZER_H + +#include "rcc/CodeGen/TargetSchedulingModel.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include + +namespace rcc { + +struct ScheduleUnit; + +class ScheduleHazardRecognizer final { +public: + [[nodiscard]] static Expected + create(const TargetSchedulingModel &Model, + ScheduleDirection Direction = ScheduleDirection::TopDown); + + ScheduleHazardRecognizer(const ScheduleHazardRecognizer &Other); + ScheduleHazardRecognizer &operator=(const ScheduleHazardRecognizer &Other); + ScheduleHazardRecognizer(ScheduleHazardRecognizer &&) noexcept = default; + ScheduleHazardRecognizer &operator=(ScheduleHazardRecognizer &&) noexcept = default; + ~ScheduleHazardRecognizer() = default; + + [[nodiscard]] std::uint64_t currentCycle() const noexcept { + return CurrentCycle; + } + + [[nodiscard]] Expected canIssue(const ScheduleUnit &Unit, std::uint64_t Cycle) const; + [[nodiscard]] Expected earliestIssueCycle(const ScheduleUnit &Unit, + std::uint64_t Earliest) const; + [[nodiscard]] Expected issue(const ScheduleUnit &Unit, std::uint64_t Cycle); + +private: + struct ResourceState final { + ProcessorResourceID ID; + std::vector AvailableAt; + }; + + ScheduleHazardRecognizer(const TargetSchedulingModel &Model, ScheduleDirection Direction) noexcept + : Model(&Model), Direction(Direction) {} + + [[nodiscard]] Expected reset(); + [[nodiscard]] Expected moveToCycle(std::uint64_t Cycle); + [[nodiscard]] Expected issueImplementation(const ScheduleUnit &Unit, std::uint64_t Cycle); + [[nodiscard]] Expected reserveResource(ProcessorResourceID Resource, std::uint32_t Cycles, + std::uint64_t Cycle); + + const TargetSchedulingModel *Model; + ScheduleDirection Direction = ScheduleDirection::TopDown; + std::unique_ptr TargetHazards; + std::vector Resources; + std::unordered_map ResourceIndexes; + std::uint64_t CurrentCycle = 0; + std::uint64_t DispatchAvailableAt = 0; + std::uint32_t IssuedMicroOps = 0; + std::uint32_t DispatchedUnits = 0; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_SCHEDULEHAZARDRECOGNIZER_H diff --git a/backend/include/rcc/CodeGen/TargetBranchInfo.h b/backend/include/rcc/CodeGen/TargetBranchInfo.h new file mode 100644 index 0000000..39c5122 --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetBranchInfo.h @@ -0,0 +1,66 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETBRANCHINFO_H +#define RCC_CODEGEN_TARGETBRANCHINFO_H + +#include "rcc/Support/Error.h" + +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class TargetDescription; + +struct MachineBranchAnalysis final { + MachineInstr *Conditional = nullptr; + MachineInstr *Unconditional = nullptr; + MachineBasicBlock *TrueTarget = nullptr; + MachineBasicBlock *FalseTarget = nullptr; + bool HasUnanalyzableTerminator = false; +}; + +class TargetBranchInfo { +public: + virtual ~TargetBranchInfo() = default; + + [[nodiscard]] virtual Expected + analyzeBranch(MachineBasicBlock &Block, MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected + reverseBranchCondition(MachineInstr &Branch, MachineBasicBlock &NewTarget, + MachineFunction &Function, const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected removeBranch(MachineInstr &Branch, MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected + rewriteBranchTarget(MachineBasicBlock &Block, MachineBasicBlock &OldTarget, + MachineBasicBlock &NewTarget, MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected + insertUnconditionalBranch(MachineBasicBlock &Block, MachineBasicBlock &TargetBlock, + MachineFunction &Function, const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected + instructionSize(const MachineInstr &Instruction, const MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected + branchTarget(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target) const = 0; + [[nodiscard]] virtual Expected> + evaluateBranchCondition(const MachineInstr &, const MachineFunction &, + const TargetDescription &) const { + return std::optional{}; + } + [[nodiscard]] virtual bool isBranchOffsetInRange(const MachineInstr &Instruction, + std::int64_t Offset) const noexcept = 0; + [[nodiscard]] virtual Expected relaxBranch(MachineInstr &Instruction, std::int64_t Offset, + MachineFunction &Function, + const TargetDescription &Target) const = 0; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETBRANCHINFO_H diff --git a/backend/include/rcc/CodeGen/TargetFrameLowering.h b/backend/include/rcc/CodeGen/TargetFrameLowering.h index 1712616..b63ce22 100644 --- a/backend/include/rcc/CodeGen/TargetFrameLowering.h +++ b/backend/include/rcc/CodeGen/TargetFrameLowering.h @@ -39,6 +39,11 @@ public: [[nodiscard]] virtual Expected finalizeFrame(MachineFunction &Function, const TargetDescription &Target) const = 0; + [[nodiscard]] virtual bool isCalleeSavedRegister(PhysicalRegister, const MachineFunction &, + const TargetDescription &) const noexcept { + return false; + } + [[nodiscard]] virtual bool isCallFramePseudo(const MachineInstr &Instruction) const noexcept = 0; [[nodiscard]] virtual Expected eliminateCallFramePseudo(MachineInstr &Instruction, MachineFunction &Function, diff --git a/backend/include/rcc/CodeGen/TargetMemoryFolding.h b/backend/include/rcc/CodeGen/TargetMemoryFolding.h new file mode 100644 index 0000000..e40fbc0 --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetMemoryFolding.h @@ -0,0 +1,43 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETMEMORYFOLDING_H +#define RCC_CODEGEN_TARGETMEMORYFOLDING_H + +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/Support/Error.h" + +#include +#include + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +class TargetMemoryFoldingInfo { +public: + virtual ~TargetMemoryFoldingInfo() = default; + + [[nodiscard]] virtual Expected + canFoldMemoryOperand(const MachineInstr &Consumer, std::size_t OperandIndex, + const MachineInstr &MemoryInstruction, const MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected + foldMemoryOperand(MachineInstr &Consumer, std::size_t OperandIndex, + MachineInstr &MemoryInstruction, MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected + unfoldMemoryOperand(MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target) const = 0; + + [[nodiscard]] virtual Expected> + getFoldedMemorySize(const MachineInstr &Instruction, const MachineFunction &Function, + const TargetDescription &Target) const = 0; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETMEMORYFOLDING_H diff --git a/backend/include/rcc/CodeGen/TargetPseudoExpansion.h b/backend/include/rcc/CodeGen/TargetPseudoExpansion.h new file mode 100644 index 0000000..4d9f556 --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetPseudoExpansion.h @@ -0,0 +1,40 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETPSEUDOEXPANSION_H +#define RCC_CODEGEN_TARGETPSEUDOEXPANSION_H + +#include "rcc/Support/Error.h" + +#include + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +enum class MachinePseudoExpansionPhase : std::uint8_t { + PrePEI, + PostRA, + TargetLate, +}; + +class TargetPseudoExpansionInfo { +public: + virtual ~TargetPseudoExpansionInfo() = default; + + [[nodiscard]] virtual Expected preparePostRAPseudo(MachineInstr &, MachineFunction &, + const TargetDescription &) const { + return false; + } + + [[nodiscard]] virtual Expected expandPseudo(MachineInstr &, MachinePseudoExpansionPhase, + MachineFunction &, + const TargetDescription &) const { + return false; + } +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETPSEUDOEXPANSION_H diff --git a/backend/include/rcc/CodeGen/TargetSchedulingModel.h b/backend/include/rcc/CodeGen/TargetSchedulingModel.h new file mode 100644 index 0000000..4d7b3ce --- /dev/null +++ b/backend/include/rcc/CodeGen/TargetSchedulingModel.h @@ -0,0 +1,178 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_TARGETSCHEDULINGMODEL_H +#define RCC_CODEGEN_TARGETSCHEDULINGMODEL_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class ScheduleDAG; +class TargetDescription; +struct ScheduleUnit; + +enum class ScheduleDAGMode : std::uint8_t; + +enum class ScheduleDirection : std::uint8_t { + TopDown, + BottomUp, +}; + +enum class ScheduleHazardType : std::uint8_t { + NoHazard, + Hazard, + NoopHazard, +}; + +struct ProcessorResourceDesc final { + ProcessorResourceID ID; + std::string Name; + std::uint32_t Units = 1; + std::optional Parent; +}; + +struct SchedulingResourceUse final { + ProcessorResourceID Resource; + std::uint32_t Cycles = 1; + + friend constexpr bool operator==(SchedulingResourceUse, SchedulingResourceUse) noexcept = default; +}; + +struct SchedulingWriteLatency final { + std::uint32_t OperandIndex = 0; + std::uint32_t Cycles = 0; + + friend constexpr bool operator==(SchedulingWriteLatency, + SchedulingWriteLatency) noexcept = default; +}; + +struct SchedulingReadAdvance final { + std::uint32_t OperandIndex = 0; + std::optional ProducerClass; + std::uint32_t Cycles = 0; + + friend constexpr bool operator==(const SchedulingReadAdvance &, + const SchedulingReadAdvance &) noexcept = default; +}; + +struct SchedulingClassModelDesc final { + SchedulingClassID ID; + std::string Name; + std::uint32_t MicroOps = 1; + std::uint32_t Latency = 1; + std::vector Resources; + std::vector WriteLatencies; + std::vector ReadAdvances; +}; + +struct RegisterPressureSetDesc final { + RegisterPressureSetID ID; + std::string Name; + std::vector RegisterClasses; + std::uint32_t Limit = 1; +}; + +class TargetScheduleHazardRecognizer { +public: + virtual ~TargetScheduleHazardRecognizer() = default; + + [[nodiscard]] virtual std::unique_ptr clone() const = 0; + [[nodiscard]] virtual Expected getHazardType(const ScheduleUnit &Unit) const; + [[nodiscard]] virtual Expected emitInstruction(const ScheduleUnit &Unit); + [[nodiscard]] virtual Expected advanceCycle(); + [[nodiscard]] virtual Expected recedeCycle(); + [[nodiscard]] virtual Expected reset(); +}; + +class TargetSchedulingHooks { +public: + virtual ~TargetSchedulingHooks() = default; + + [[nodiscard]] virtual bool isSchedulingBoundary(const MachineInstr &Instruction, + const TargetDescription &Target) const noexcept; + [[nodiscard]] virtual Expected mutateScheduleDAG(ScheduleDAG &DAG, + const MachineFunction &Function, + const TargetDescription &Target, + ScheduleDAGMode Mode) const; + [[nodiscard]] virtual std::int64_t + candidatePreference(const ScheduleUnit &Unit, ScheduleDirection Direction, + const MachineBasicBlock &Block, std::uint64_t BlockFrequency) const noexcept; + [[nodiscard]] virtual std::unique_ptr + createHazardRecognizer(ScheduleDirection Direction) const; +}; + +struct TargetSchedulingModelDesc final { + std::uint32_t IssueWidth = 1; + std::uint32_t DispatchLimit = 1; + std::vector ProcessorResources; + std::vector SchedulingClasses; + std::vector PressureSets; + const TargetSchedulingHooks *Hooks = nullptr; +}; + +class TargetSchedulingModel final { +public: + [[nodiscard]] static Expected + create(TargetSchedulingModelDesc Description); + + [[nodiscard]] std::uint32_t issueWidth() const noexcept { + return Description.IssueWidth; + } + + [[nodiscard]] std::uint32_t dispatchLimit() const noexcept { + return Description.DispatchLimit; + } + + [[nodiscard]] std::span processorResources() const noexcept { + return Description.ProcessorResources; + } + + [[nodiscard]] std::span schedulingClasses() const noexcept { + return Description.SchedulingClasses; + } + + [[nodiscard]] std::span pressureSets() const noexcept { + return Description.PressureSets; + } + + [[nodiscard]] const ProcessorResourceDesc * + processorResource(ProcessorResourceID ID) const noexcept; + [[nodiscard]] const SchedulingClassModelDesc * + schedulingClass(SchedulingClassID ID) const noexcept; + [[nodiscard]] const RegisterPressureSetDesc *pressureSet(RegisterPressureSetID ID) const noexcept; + [[nodiscard]] std::span + pressureSetsForClass(RegisterClassID Class) const noexcept; + [[nodiscard]] Expected operandLatency(SchedulingClassID ProducerClass, + std::size_t DefinitionOperand, + SchedulingClassID ConsumerClass, + std::size_t UseOperand) const; + [[nodiscard]] const TargetSchedulingHooks &hooks() const noexcept; + +private: + explicit TargetSchedulingModel(TargetSchedulingModelDesc Description) + : Description(std::move(Description)) {} + + TargetSchedulingModelDesc Description; + std::unordered_map ResourceToIndex; + std::unordered_map ClassToIndex; + std::unordered_map PressureSetToIndex; + std::unordered_map> ClassToPressureSets; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_TARGETSCHEDULINGMODEL_H -- cgit v1.2.3