From f99ef4322a7a2c09380fff61f88ab9440f05a92c Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Fri, 7 Aug 2026 22:06:28 +0800 Subject: [CodeGen] Complete machine pass and ABI lowering infrastructure --- backend/include/rcc/CodeGen/MachineAnalyses.h | 244 ++++++++++++++++++++++++++ 1 file changed, 244 insertions(+) create mode 100644 backend/include/rcc/CodeGen/MachineAnalyses.h (limited to 'backend/include/rcc/CodeGen/MachineAnalyses.h') diff --git a/backend/include/rcc/CodeGen/MachineAnalyses.h b/backend/include/rcc/CodeGen/MachineAnalyses.h new file mode 100644 index 0000000..eda550d --- /dev/null +++ b/backend/include/rcc/CodeGen/MachineAnalyses.h @@ -0,0 +1,244 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_MACHINEANALYSES_H +#define RCC_CODEGEN_MACHINEANALYSES_H + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/StableID.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +class MachineMemOperand; +class TargetDescription; + +class MachineDominatorTreeAnalysis final { +public: + class Result final { + public: + [[nodiscard]] bool isReachable(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] bool dominates(const MachineBasicBlock &Dominator, + const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] bool dominates(const MachineInstr &Dominator, + const MachineInstr &Instruction) const noexcept; + [[nodiscard]] const MachineBasicBlock * + immediateDominator(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] const MachineBasicBlock * + nearestCommonDominator(const MachineBasicBlock &Left, + const MachineBasicBlock &Right) const noexcept; + [[nodiscard]] std::span unreachableBlocks() const noexcept { + return UnreachableBlocks; + } + + [[nodiscard]] Expected updateAfterCFGChange(MachineFunction &Function); + + private: + [[nodiscard]] Expected build(MachineFunction &Function); + + std::vector Blocks; + std::unordered_map BlockToIndex; + std::vector> Dominators; + std::vector ImmediateDominators; + std::vector Reachable; + std::vector UnreachableBlocks; + + friend class MachineDominatorTreeAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineDominatorTree"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +struct MachineLoop final { + MachineBasicBlock *Header = nullptr; + std::vector Blocks; + std::vector Latches; + std::size_t Parent = static_cast(-1); + std::vector Children; + std::uint32_t Depth = 1; +}; + +struct IrreducibleMachineRegion final { + std::vector Blocks; + std::vector Entries; +}; + +class MachineLoopAnalysis final { +public: + class Result final { + public: + [[nodiscard]] std::span loops() const noexcept { + return Loops; + } + [[nodiscard]] std::span irreducibleRegions() const noexcept { + return IrreducibleRegions; + } + [[nodiscard]] const MachineLoop *loopFor(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] std::uint32_t loopDepth(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] bool isIrreducible(const MachineBasicBlock &Block) const noexcept; + + private: + std::vector Loops; + std::vector IrreducibleRegions; + std::unordered_map InnermostLoop; + std::unordered_set IrreducibleBlocks; + + friend class MachineLoopAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineLoopInfo"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +class MachineBranchProbabilityAnalysis final { +public: + class Result final { + public: + [[nodiscard]] BranchProbability probability(const MachineBasicBlock &From, + const MachineBasicBlock &To) const noexcept; + [[nodiscard]] std::span + successors(const MachineBasicBlock &Block) const noexcept; + + private: + std::unordered_map> Probabilities; + + friend class MachineBranchProbabilityAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineBranchProbability"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +class MachineBlockFrequencyAnalysis final { +public: + static constexpr std::uint64_t EntryFrequency = std::uint64_t{1} << 32U; + + class Result final { + public: + [[nodiscard]] std::uint64_t frequency(const MachineBasicBlock &Block) const noexcept; + + private: + std::unordered_map Frequencies; + + friend class MachineBlockFrequencyAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineBlockFrequency"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +enum class MachineAliasResult : std::uint8_t { + NoAlias, + MayAlias, + PartialAlias, + MustAlias, +}; + +class MachineAliasAnalysis final { +public: + class Result final { + public: + [[nodiscard]] MachineAliasResult alias(const MachineMemOperand &Left, + const MachineMemOperand &Right) const noexcept; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineAliasAnalysis"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +enum class MachineMemoryDependencyKind : std::uint8_t { + Flow, + Anti, + Output, + Ordered, +}; + +struct MachineMemoryDependency final { + MachineInstrStableID Source; + MachineInstrStableID Destination; + MachineMemoryDependencyKind Kind = MachineMemoryDependencyKind::Ordered; +}; + +struct MachineMemoryDependenceRegion final { + const MachineBasicBlock *Block = nullptr; + std::vector Instructions; +}; + +class MachineMemoryDependenceAnalysis final { +public: + class Result final { + public: + [[nodiscard]] std::span regions() const noexcept { + return Regions; + } + [[nodiscard]] const MachineMemoryDependenceRegion * + regionFor(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] std::span + dependencies(const MachineBasicBlock &Block) const noexcept; + [[nodiscard]] std::span + dependencies(const MachineInstr &Instruction) const noexcept; + [[nodiscard]] std::span allDependencies() const noexcept { + return Dependencies; + } + + private: + struct Range final { + std::size_t Begin = 0; + std::size_t Size = 0; + }; + + std::vector Dependencies; + std::vector Regions; + std::unordered_map BlockToRegion; + std::unordered_map BlockRanges; + std::unordered_map DestinationRanges; + + friend class MachineMemoryDependenceAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "MachineMemoryDependence"; + } + + [[nodiscard]] static Expected + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +[[nodiscard]] Expected registerStage8MachineAnalyses(MachineAnalysisManager &Analyses); + +} // namespace rcc + +#endif // RCC_CODEGEN_MACHINEANALYSES_H -- cgit v1.2.3