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/LiveInterval.h | 144 ++++++++ backend/include/rcc/CodeGen/LiveIntervals.h | 73 ++++ backend/include/rcc/CodeGen/LivePhysRegs.h | 23 ++ backend/include/rcc/CodeGen/LiveRegMatrix.h | 2 +- backend/include/rcc/CodeGen/LiveRegUnits.h | 84 +++++ backend/include/rcc/CodeGen/LiveVariables.h | 105 ++++++ backend/include/rcc/CodeGen/MachineLiveness.h | 410 --------------------- .../include/rcc/CodeGen/MachineLivenessRepair.h | 23 -- backend/include/rcc/CodeGen/SlotIndexes.h | 130 +++++++ .../rcc/CodeGen/TargetRegisterAllocationInfo.h | 2 +- 10 files changed, 561 insertions(+), 435 deletions(-) create mode 100644 backend/include/rcc/CodeGen/LiveInterval.h create mode 100644 backend/include/rcc/CodeGen/LiveIntervals.h create mode 100644 backend/include/rcc/CodeGen/LivePhysRegs.h create mode 100644 backend/include/rcc/CodeGen/LiveRegUnits.h create mode 100644 backend/include/rcc/CodeGen/LiveVariables.h delete mode 100644 backend/include/rcc/CodeGen/MachineLiveness.h delete mode 100644 backend/include/rcc/CodeGen/MachineLivenessRepair.h create mode 100644 backend/include/rcc/CodeGen/SlotIndexes.h (limited to 'backend/include') diff --git a/backend/include/rcc/CodeGen/LiveInterval.h b/backend/include/rcc/CodeGen/LiveInterval.h new file mode 100644 index 0000000..28791f1 --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveInterval.h @@ -0,0 +1,144 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEINTERVAL_H +#define RCC_CODEGEN_LIVEINTERVAL_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/CodeGen/SlotIndexes.h" +#include "rcc/CodeGen/StableID.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +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); + } +}; + +} // namespace rcc + +template <> struct std::hash { + [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept { + return std::hash{}(ID.value()); + } +}; + +#endif // RCC_CODEGEN_LIVEINTERVAL_H diff --git a/backend/include/rcc/CodeGen/LiveIntervals.h b/backend/include/rcc/CodeGen/LiveIntervals.h new file mode 100644 index 0000000..a45c593 --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveIntervals.h @@ -0,0 +1,73 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEINTERVALS_H +#define RCC_CODEGEN_LIVEINTERVALS_H + +#include "rcc/CodeGen/LiveInterval.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/RegisterMask.h" + +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +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); +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_LIVEINTERVALS_H diff --git a/backend/include/rcc/CodeGen/LivePhysRegs.h b/backend/include/rcc/CodeGen/LivePhysRegs.h new file mode 100644 index 0000000..3d4b7ef --- /dev/null +++ b/backend/include/rcc/CodeGen/LivePhysRegs.h @@ -0,0 +1,23 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEPHYSREGS_H +#define RCC_CODEGEN_LIVEPHYSREGS_H + +#include "rcc/CodeGen/LiveVariables.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_LIVEPHYSREGS_H diff --git a/backend/include/rcc/CodeGen/LiveRegMatrix.h b/backend/include/rcc/CodeGen/LiveRegMatrix.h index 953828c..fd1bac4 100644 --- a/backend/include/rcc/CodeGen/LiveRegMatrix.h +++ b/backend/include/rcc/CodeGen/LiveRegMatrix.h @@ -3,7 +3,7 @@ #ifndef RCC_CODEGEN_LIVEREGMATRIX_H #define RCC_CODEGEN_LIVEREGMATRIX_H -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/TargetRegisterInfo.h" #include diff --git a/backend/include/rcc/CodeGen/LiveRegUnits.h b/backend/include/rcc/CodeGen/LiveRegUnits.h new file mode 100644 index 0000000..6eb06a6 --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveRegUnits.h @@ -0,0 +1,84 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEREGUNITS_H +#define RCC_CODEGEN_LIVEREGUNITS_H + +#include "rcc/CodeGen/MachineIRTypes.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class MachineOperand; +class RegisterMask; +class TargetDescription; +struct PhysicalRegisterDesc; + +class LiveRegUnits 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 LiveRegUnits &Other); + void subtract(const LiveRegUnits &Other); + + [[nodiscard]] const std::unordered_map &entries() const noexcept { + return Values; + } + + friend bool operator==(const LiveRegUnits &, const LiveRegUnits &) = default; + +private: + std::unordered_map Values; +}; + +struct PhysicalUnitAccess final { + RegisterUnitID Unit; + LaneMask Lanes; +}; + +[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, + LaneMask RegisterLanes = LaneMask::all()) noexcept; +[[nodiscard]] LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept; +[[nodiscard]] LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept; +[[nodiscard]] LiveRegUnits physicalRegisterCoverage(const PhysicalRegisterDesc &Description, + LaneMask Requested = LaneMask::all()); +[[nodiscard]] bool isSubset(const LiveRegUnits &Subset, const LiveRegUnits &Superset) noexcept; +[[nodiscard]] std::size_t laneCount(const LiveRegUnits &Set) noexcept; + +[[nodiscard]] Expected virtualRegisterLanes(Register Reg, const MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected virtualOperandLanes(const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected> +physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target); + +void addPhysicalRegister(LiveRegUnits &Set, const PhysicalRegisterDesc &Description, + LaneMask Requested = LaneMask::all()); +[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) noexcept; +[[nodiscard]] Expected addRegisterMaskDefs(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target); +[[nodiscard]] Expected addRegisterMaskUses(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target); + +} // namespace rcc + +#endif // RCC_CODEGEN_LIVEREGUNITS_H diff --git a/backend/include/rcc/CodeGen/LiveVariables.h b/backend/include/rcc/CodeGen/LiveVariables.h new file mode 100644 index 0000000..28a66c1 --- /dev/null +++ b/backend/include/rcc/CodeGen/LiveVariables.h @@ -0,0 +1,105 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_LIVEVARIABLES_H +#define RCC_CODEGEN_LIVEVARIABLES_H + +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/MachinePass.h" +#include "rcc/CodeGen/Register.h" +#include "rcc/Support/Error.h" + +#include +#include +#include +#include + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class TargetDescription; + +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; +}; + +struct MachineBlockLiveness final { + RegisterLaneSet VirtualUses; + RegisterLaneSet VirtualDefs; + RegisterLaneSet VirtualLiveIn; + RegisterLaneSet VirtualLiveOut; + LiveRegUnits PhysicalUses; + LiveRegUnits PhysicalDefs; + LiveRegUnits PhysicalLiveIn; + LiveRegUnits 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 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 + +#endif // RCC_CODEGEN_LIVEVARIABLES_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 diff --git a/backend/include/rcc/CodeGen/MachineLivenessRepair.h b/backend/include/rcc/CodeGen/MachineLivenessRepair.h deleted file mode 100644 index 049e166..0000000 --- a/backend/include/rcc/CodeGen/MachineLivenessRepair.h +++ /dev/null @@ -1,23 +0,0 @@ -// 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/SlotIndexes.h b/backend/include/rcc/CodeGen/SlotIndexes.h new file mode 100644 index 0000000..1767596 --- /dev/null +++ b/backend/include/rcc/CodeGen/SlotIndexes.h @@ -0,0 +1,130 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_SLOTINDEXES_H +#define RCC_CODEGEN_SLOTINDEXES_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 + +namespace rcc { + +class MachineBasicBlock; +class MachineFunction; +class MachineInstr; +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); +}; + +} // namespace rcc + +template <> struct std::hash { + [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept { + return std::hash{}(Index.value()); + } +}; + +#endif // RCC_CODEGEN_SLOTINDEXES_H diff --git a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h index 4448933..3fd0e55 100644 --- a/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h +++ b/backend/include/rcc/CodeGen/TargetRegisterAllocationInfo.h @@ -3,8 +3,8 @@ #ifndef RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H #define RCC_CODEGEN_TARGETREGISTERALLOCATIONINFO_H +#include "rcc/CodeGen/LiveInterval.h" #include "rcc/CodeGen/MachineFrameInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/TargetRegisterInfo.h" #include -- cgit v1.2.3