From a2f8d7c5e22b510965327383410bd576f7cf28e7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Thu, 13 Aug 2026 04:17:52 +0800 Subject: [CodeGen] Split machine liveness components --- backend/include/rcc/CodeGen/MachineLiveness.h | 410 -------------------------- 1 file changed, 410 deletions(-) delete mode 100644 backend/include/rcc/CodeGen/MachineLiveness.h (limited to 'backend/include/rcc/CodeGen/MachineLiveness.h') diff --git a/backend/include/rcc/CodeGen/MachineLiveness.h b/backend/include/rcc/CodeGen/MachineLiveness.h deleted file mode 100644 index 678f309..0000000 --- a/backend/include/rcc/CodeGen/MachineLiveness.h +++ /dev/null @@ -1,410 +0,0 @@ -// SPDX-License-Identifier: GPL-3.0-or-later - -#ifndef RCC_CODEGEN_MACHINELIVENESS_H -#define RCC_CODEGEN_MACHINELIVENESS_H - -#include "rcc/CodeGen/MachineIRTypes.h" -#include "rcc/CodeGen/MachinePass.h" -#include "rcc/CodeGen/Register.h" -#include "rcc/CodeGen/StableID.h" -#include "rcc/Support/Error.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -namespace rcc { - -class MachineBasicBlock; -class MachineFunction; -class MachineInstr; -class RegisterMask; -class TargetDescription; - -enum class SlotIndexKind : std::uint8_t { - Block, - EarlyClobber, - Register, - Dead, -}; - -class SlotIndex final { -public: - constexpr SlotIndex() noexcept = default; - - [[nodiscard]] static constexpr SlotIndex fromValue(std::uint64_t Value) noexcept { - return SlotIndex(Value); - } - - [[nodiscard]] constexpr bool isValid() const noexcept { - return Value != 0; - } - - [[nodiscard]] constexpr std::uint64_t value() const noexcept { - return Value; - } - - [[nodiscard]] constexpr SlotIndexKind kind() const noexcept { - return static_cast(Value & KindMask); - } - - [[nodiscard]] constexpr SlotIndex baseIndex() const noexcept { - return SlotIndex(Value & ~KindMask); - } - - [[nodiscard]] constexpr SlotIndex withKind(SlotIndexKind Kind) const noexcept { - return isValid() ? SlotIndex((Value & ~KindMask) | static_cast(Kind)) - : SlotIndex{}; - } - - [[nodiscard]] constexpr SlotIndex earlyClobberSlot() const noexcept { - return withKind(SlotIndexKind::EarlyClobber); - } - - [[nodiscard]] constexpr SlotIndex registerSlot() const noexcept { - return withKind(SlotIndexKind::Register); - } - - [[nodiscard]] constexpr SlotIndex deadSlot() const noexcept { - return withKind(SlotIndexKind::Dead); - } - - friend constexpr bool operator==(SlotIndex, SlotIndex) noexcept = default; - friend constexpr auto operator<=>(SlotIndex, SlotIndex) noexcept = default; - -private: - static constexpr std::uint64_t KindMask = 3; - - explicit constexpr SlotIndex(std::uint64_t Value) noexcept : Value(Value) {} - - std::uint64_t Value = 0; -}; - -class SlotIndexesAnalysis final { -public: - class Result final { - public: - [[nodiscard]] SlotIndex instructionIndex(const MachineInstr &Instruction) const noexcept; - [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept { - return instructionIndex(Instruction); - } - [[nodiscard]] SlotIndex blockStart(const MachineBasicBlock &Block) const noexcept; - [[nodiscard]] SlotIndex blockEnd(const MachineBasicBlock &Block) const noexcept; - [[nodiscard]] const MachineInstr *instructionFromIndex(SlotIndex Index) const noexcept; - [[nodiscard]] const MachineBasicBlock *blockFromIndex(SlotIndex Index) const noexcept; - - [[nodiscard]] Expected insertInstruction(const MachineInstr &Instruction); - [[nodiscard]] Expected eraseInstruction(const MachineInstr &Instruction); - [[nodiscard]] Expected renumber(MachineFunction &Function); - - [[nodiscard]] bool invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept; - - private: - std::unordered_map InstructionSlots; - std::unordered_map SlotToInstruction; - std::unordered_map BlockStarts; - std::unordered_map BlockEnds; - std::vector BlocksByStart; - - friend class SlotIndexesAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "SlotIndexes"; - } - - [[nodiscard]] static Expected - run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); -}; - -class RegisterLaneSet final { -public: - [[nodiscard]] LaneMask lanes(Register Reg) const noexcept; - [[nodiscard]] bool contains(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool intersects(Register Reg, LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool empty() const noexcept { - return Values.empty(); - } - - void add(Register Reg, LaneMask Lanes); - void remove(Register Reg, LaneMask Lanes); - void unite(const RegisterLaneSet &Other); - void subtract(const RegisterLaneSet &Other); - - [[nodiscard]] const std::unordered_map &entries() const noexcept { - return Values; - } - - friend bool operator==(const RegisterLaneSet &, const RegisterLaneSet &) = default; - -private: - std::unordered_map Values; -}; - -class RegisterUnitLaneSet final { -public: - [[nodiscard]] LaneMask lanes(RegisterUnitID Unit) const noexcept; - [[nodiscard]] bool contains(RegisterUnitID Unit, LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool intersects(RegisterUnitID Unit, - LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool empty() const noexcept { - return Values.empty(); - } - - void add(RegisterUnitID Unit, LaneMask Lanes); - void remove(RegisterUnitID Unit, LaneMask Lanes); - void unite(const RegisterUnitLaneSet &Other); - void subtract(const RegisterUnitLaneSet &Other); - - [[nodiscard]] const std::unordered_map &entries() const noexcept { - return Values; - } - - friend bool operator==(const RegisterUnitLaneSet &, const RegisterUnitLaneSet &) = default; - -private: - std::unordered_map Values; -}; - -struct MachineBlockLiveness final { - RegisterLaneSet VirtualUses; - RegisterLaneSet VirtualDefs; - RegisterLaneSet VirtualLiveIn; - RegisterLaneSet VirtualLiveOut; - RegisterUnitLaneSet PhysicalUses; - RegisterUnitLaneSet PhysicalDefs; - RegisterUnitLaneSet PhysicalLiveIn; - RegisterUnitLaneSet PhysicalLiveOut; -}; - -class LiveVariablesAnalysis final { -public: - class Result final { - public: - [[nodiscard]] MachineBlockLiveness &getOrCreateBlock(const MachineBasicBlock &Block); - [[nodiscard]] const MachineBlockLiveness *block(const MachineBasicBlock &Block) const noexcept; - [[nodiscard]] bool isLiveIn(const MachineBasicBlock &Block, Register Reg, - LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool isLiveOut(const MachineBasicBlock &Block, Register Reg, - LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool isUnitLiveIn(const MachineBasicBlock &Block, RegisterUnitID Unit, - LaneMask Lanes = LaneMask::all()) const noexcept; - [[nodiscard]] bool isUnitLiveOut(const MachineBasicBlock &Block, RegisterUnitID Unit, - LaneMask Lanes = LaneMask::all()) const noexcept; - - [[nodiscard]] bool invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept; - - private: - std::unordered_map Blocks; - - friend class LiveVariablesAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "LiveVariables"; - } - - [[nodiscard]] static Expected - run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); -}; - -class LiveValueNumberID final { -public: - constexpr LiveValueNumberID() noexcept = default; - - [[nodiscard]] static constexpr LiveValueNumberID fromValue(std::uint32_t Value) noexcept { - return LiveValueNumberID(Value); - } - - [[nodiscard]] constexpr bool isValid() const noexcept { - return Value != 0; - } - - [[nodiscard]] constexpr std::uint32_t value() const noexcept { - return Value; - } - - friend constexpr bool operator==(LiveValueNumberID, LiveValueNumberID) noexcept = default; - friend constexpr auto operator<=>(LiveValueNumberID, LiveValueNumberID) noexcept = default; - -private: - explicit constexpr LiveValueNumberID(std::uint32_t Value) noexcept : Value(Value) {} - - std::uint32_t Value = 0; -}; - -enum class LiveValueState : std::uint8_t { - Normal, - Phi, - Unused, - Redefined, -}; - -struct LiveValueNumber final { - LiveValueNumberID ID; - SlotIndex Definition; - LiveValueState State = LiveValueState::Normal; - std::optional Origin; - - friend bool operator==(const LiveValueNumber &, const LiveValueNumber &) = default; -}; - -struct LiveSegment final { - SlotIndex Start; - SlotIndex End; - LiveValueNumberID Value; - - [[nodiscard]] constexpr bool empty() const noexcept { - return !(Start < End); - } - - [[nodiscard]] constexpr bool contains(SlotIndex Position) const noexcept { - return !(Position < Start) && Position < End; - } - - [[nodiscard]] constexpr bool overlaps(const LiveSegment &Other) const noexcept { - return Start < Other.End && Other.Start < End; - } - - friend constexpr bool operator==(const LiveSegment &, const LiveSegment &) noexcept = default; -}; - -class LiveRange final { -public: - [[nodiscard]] std::span segments() const noexcept { - return Segments; - } - [[nodiscard]] std::span values() const noexcept { - return Values; - } - [[nodiscard]] bool empty() const noexcept { - return Segments.empty(); - } - - [[nodiscard]] const LiveSegment *segmentAt(SlotIndex Position) const noexcept; - [[nodiscard]] const LiveValueNumber *value(LiveValueNumberID ID) const noexcept; - [[nodiscard]] const LiveValueNumber *valueAt(SlotIndex Position) const noexcept; - [[nodiscard]] bool liveAt(SlotIndex Position) const noexcept; - [[nodiscard]] bool overlaps(const LiveRange &Other) const noexcept; - - [[nodiscard]] Expected - createValue(SlotIndex Definition, LiveValueState State = LiveValueState::Normal, - std::optional Origin = std::nullopt); - [[nodiscard]] Expected addSegment(LiveSegment Segment); - [[nodiscard]] Expected extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End); - [[nodiscard]] Expected remove(SlotIndex Start, SlotIndex End); - [[nodiscard]] Expected shrinkToUses(std::span Uses); - [[nodiscard]] Expected verify() const; - -private: - void mergeAdjacent(); - - std::vector Segments; - std::vector Values; -}; - -struct LiveSubRange final { - LaneMask Lanes; - LiveRange Range; -}; - -struct LiveInterval final { - Register Reg; - LiveRange MainRange; - std::vector SubRanges; - std::uint64_t SpillWeight = 0; - bool Spillable = true; - std::vector AllocationHints; - std::optional SplitParent; - std::optional Origin; - - [[nodiscard]] bool overlaps(const LiveInterval &Other) const noexcept { - return MainRange.overlaps(Other.MainRange); - } -}; - -struct RegMaskPosition final { - SlotIndex Position; - MachineInstrStableID Instruction; - std::shared_ptr Mask; -}; - -class LiveIntervalsAnalysis final { -public: - class Result final { - public: - [[nodiscard]] const SlotIndexesAnalysis::Result &slotIndexes() const noexcept { - return Indexes; - } - [[nodiscard]] SlotIndex slot(const MachineInstr &Instruction) const noexcept { - return Indexes.instructionIndex(Instruction); - } - [[nodiscard]] const LiveInterval *interval(Register Reg) const noexcept; - [[nodiscard]] LiveInterval *interval(Register Reg) noexcept; - [[nodiscard]] const LiveRange *regUnitRange(RegisterUnitID Unit) const noexcept; - [[nodiscard]] std::span regMaskPositions() const noexcept { - return RegMasks; - } - [[nodiscard]] bool interferes(Register Left, Register Right) const noexcept; - [[nodiscard]] bool regMaskClobbers(const LiveInterval &Interval, - PhysicalRegister Candidate) const noexcept; - [[nodiscard]] Expected shrinkToUses(Register Reg, std::span Uses); - - [[nodiscard]] bool invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept; - - private: - SlotIndexesAnalysis::Result Indexes; - std::unordered_map Intervals; - std::unordered_map RegisterUnitRanges; - std::vector RegMasks; - - friend class LiveIntervalsAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "LiveIntervals"; - } - - [[nodiscard]] static Expected - run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); -}; - -class RebuildMachineLivenessPass final : public MachineFunctionPass { -public: - [[nodiscard]] const MachinePassContract &contract() const noexcept override; - [[nodiscard]] Expected run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) override; -}; - -[[nodiscard]] Expected verifyTrackedMachineLiveness(const MachineFunction &Function, - const TargetDescription &Target); -[[nodiscard]] Expected rebuildMachineLiveness(MachineFunction &Function, - const TargetDescription &Target); -[[nodiscard]] Expected registerStage11MachineAnalyses(MachineAnalysisManager &Analyses); - -} // namespace rcc - -template <> struct std::hash { - [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept { - return std::hash{}(Index.value()); - } -}; - -template <> struct std::hash { - [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept { - return std::hash{}(ID.value()); - } -}; - -#endif // RCC_CODEGEN_MACHINELIVENESS_H -- cgit v1.2.3