diff options
64 files changed, 3051 insertions, 2604 deletions
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 <compare> +#include <cstdint> +#include <limits> +#include <optional> +#include <span> +#include <vector> + +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<MachineInstrStableID> 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<const LiveSegment> segments() const noexcept { + return Segments; + } + [[nodiscard]] std::span<const LiveValueNumber> 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<LiveValueNumberID> + createValue(SlotIndex Definition, LiveValueState State = LiveValueState::Normal, + std::optional<MachineInstrStableID> Origin = std::nullopt); + [[nodiscard]] Expected<void> addSegment(LiveSegment Segment); + [[nodiscard]] Expected<void> extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End); + [[nodiscard]] Expected<void> remove(SlotIndex Start, SlotIndex End); + [[nodiscard]] Expected<void> shrinkToUses(std::span<const SlotIndex> Uses); + [[nodiscard]] Expected<void> verify() const; + +private: + void mergeAdjacent(); + + std::vector<LiveSegment> Segments; + std::vector<LiveValueNumber> Values; +}; + +struct LiveSubRange final { + LaneMask Lanes; + LiveRange Range; +}; + +struct LiveInterval final { + Register Reg; + LiveRange MainRange; + std::vector<LiveSubRange> SubRanges; + std::uint64_t SpillWeight = 0; + bool Spillable = true; + std::vector<PhysicalRegister> AllocationHints; + std::optional<Register> SplitParent; + std::optional<Register> Origin; + + [[nodiscard]] bool overlaps(const LiveInterval &Other) const noexcept { + return MainRange.overlaps(Other.MainRange); + } +}; + +} // namespace rcc + +template <> struct std::hash<rcc::LiveValueNumberID> { + [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept { + return std::hash<std::uint32_t>{}(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 <cstdint> +#include <memory> +#include <optional> +#include <span> +#include <string_view> +#include <unordered_map> +#include <vector> + +namespace rcc { + +class MachineFunction; +class MachineInstr; +class TargetDescription; + +struct RegMaskPosition final { + SlotIndex Position; + MachineInstrStableID Instruction; + std::shared_ptr<const RegisterMask> 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<const RegMaskPosition> 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<void> shrinkToUses(Register Reg, std::span<const SlotIndex> Uses); + + [[nodiscard]] bool invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept; + + private: + SlotIndexesAnalysis::Result Indexes; + std::unordered_map<Register, LiveInterval> Intervals; + std::unordered_map<RegisterUnitID, LiveRange> RegisterUnitRanges; + std::vector<RegMaskPosition> RegMasks; + + friend class LiveIntervalsAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "LiveIntervals"; + } + + [[nodiscard]] static Expected<Result> + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_LIVEINTERVALS_H diff --git a/backend/include/rcc/CodeGen/MachineLivenessRepair.h b/backend/include/rcc/CodeGen/LivePhysRegs.h index 049e166..3d4b7ef 100644 --- a/backend/include/rcc/CodeGen/MachineLivenessRepair.h +++ b/backend/include/rcc/CodeGen/LivePhysRegs.h @@ -1,9 +1,9 @@ // SPDX-License-Identifier: GPL-3.0-or-later -#ifndef RCC_CODEGEN_MACHINELIVENESSREPAIR_H -#define RCC_CODEGEN_MACHINELIVENESSREPAIR_H +#ifndef RCC_CODEGEN_LIVEPHYSREGS_H +#define RCC_CODEGEN_LIVEPHYSREGS_H -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/Support/Error.h" #include <span> @@ -20,4 +20,4 @@ repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks, } // namespace rcc -#endif // RCC_CODEGEN_MACHINELIVENESSREPAIR_H +#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 <cstdint> 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 <cstddef> +#include <cstdint> +#include <optional> +#include <span> +#include <unordered_map> +#include <vector> + +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<RegisterUnitID, LaneMask> &entries() const noexcept { + return Values; + } + + friend bool operator==(const LiveRegUnits &, const LiveRegUnits &) = default; + +private: + std::unordered_map<RegisterUnitID, LaneMask> 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<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> +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<void> addRegisterMaskDefs(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target); +[[nodiscard]] Expected<void> 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 <cstddef> +#include <cstdint> +#include <string_view> +#include <unordered_map> + +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<Register, LaneMask> &entries() const noexcept { + return Values; + } + + friend bool operator==(const RegisterLaneSet &, const RegisterLaneSet &) = default; + +private: + std::unordered_map<Register, LaneMask> 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<const MachineBasicBlock *, MachineBlockLiveness> Blocks; + + friend class LiveVariablesAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "LiveVariables"; + } + + [[nodiscard]] static Expected<Result> + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +class RebuildMachineLivenessPass final : public MachineFunctionPass { +public: + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; +}; + +[[nodiscard]] Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected<bool> rebuildMachineLiveness(MachineFunction &Function, + const TargetDescription &Target); +[[nodiscard]] Expected<void> 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 <compare> -#include <cstddef> -#include <cstdint> -#include <functional> -#include <memory> -#include <optional> -#include <span> -#include <string_view> -#include <unordered_map> -#include <vector> - -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<SlotIndexKind>(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<std::uint64_t>(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<void> insertInstruction(const MachineInstr &Instruction); - [[nodiscard]] Expected<void> eraseInstruction(const MachineInstr &Instruction); - [[nodiscard]] Expected<void> renumber(MachineFunction &Function); - - [[nodiscard]] bool invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept; - - private: - std::unordered_map<MachineInstrStableID, SlotIndex> InstructionSlots; - std::unordered_map<std::uint64_t, const MachineInstr *> SlotToInstruction; - std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockStarts; - std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockEnds; - std::vector<const MachineBasicBlock *> BlocksByStart; - - friend class SlotIndexesAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "SlotIndexes"; - } - - [[nodiscard]] static Expected<Result> - 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<Register, LaneMask> &entries() const noexcept { - return Values; - } - - friend bool operator==(const RegisterLaneSet &, const RegisterLaneSet &) = default; - -private: - std::unordered_map<Register, LaneMask> 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<RegisterUnitID, LaneMask> &entries() const noexcept { - return Values; - } - - friend bool operator==(const RegisterUnitLaneSet &, const RegisterUnitLaneSet &) = default; - -private: - std::unordered_map<RegisterUnitID, LaneMask> 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<const MachineBasicBlock *, MachineBlockLiveness> Blocks; - - friend class LiveVariablesAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "LiveVariables"; - } - - [[nodiscard]] static Expected<Result> - 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<MachineInstrStableID> 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<const LiveSegment> segments() const noexcept { - return Segments; - } - [[nodiscard]] std::span<const LiveValueNumber> 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<LiveValueNumberID> - createValue(SlotIndex Definition, LiveValueState State = LiveValueState::Normal, - std::optional<MachineInstrStableID> Origin = std::nullopt); - [[nodiscard]] Expected<void> addSegment(LiveSegment Segment); - [[nodiscard]] Expected<void> extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End); - [[nodiscard]] Expected<void> remove(SlotIndex Start, SlotIndex End); - [[nodiscard]] Expected<void> shrinkToUses(std::span<const SlotIndex> Uses); - [[nodiscard]] Expected<void> verify() const; - -private: - void mergeAdjacent(); - - std::vector<LiveSegment> Segments; - std::vector<LiveValueNumber> Values; -}; - -struct LiveSubRange final { - LaneMask Lanes; - LiveRange Range; -}; - -struct LiveInterval final { - Register Reg; - LiveRange MainRange; - std::vector<LiveSubRange> SubRanges; - std::uint64_t SpillWeight = 0; - bool Spillable = true; - std::vector<PhysicalRegister> AllocationHints; - std::optional<Register> SplitParent; - std::optional<Register> Origin; - - [[nodiscard]] bool overlaps(const LiveInterval &Other) const noexcept { - return MainRange.overlaps(Other.MainRange); - } -}; - -struct RegMaskPosition final { - SlotIndex Position; - MachineInstrStableID Instruction; - std::shared_ptr<const RegisterMask> 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<const RegMaskPosition> 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<void> shrinkToUses(Register Reg, std::span<const SlotIndex> Uses); - - [[nodiscard]] bool invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept; - - private: - SlotIndexesAnalysis::Result Indexes; - std::unordered_map<Register, LiveInterval> Intervals; - std::unordered_map<RegisterUnitID, LiveRange> RegisterUnitRanges; - std::vector<RegMaskPosition> RegMasks; - - friend class LiveIntervalsAnalysis; - }; - - [[nodiscard]] static constexpr std::string_view name() noexcept { - return "LiveIntervals"; - } - - [[nodiscard]] static Expected<Result> - run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); -}; - -class RebuildMachineLivenessPass final : public MachineFunctionPass { -public: - [[nodiscard]] const MachinePassContract &contract() const noexcept override; - [[nodiscard]] Expected<MachinePassResult> run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &Analyses) override; -}; - -[[nodiscard]] Expected<void> verifyTrackedMachineLiveness(const MachineFunction &Function, - const TargetDescription &Target); -[[nodiscard]] Expected<bool> rebuildMachineLiveness(MachineFunction &Function, - const TargetDescription &Target); -[[nodiscard]] Expected<void> registerStage11MachineAnalyses(MachineAnalysisManager &Analyses); - -} // namespace rcc - -template <> struct std::hash<rcc::SlotIndex> { - [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept { - return std::hash<std::uint64_t>{}(Index.value()); - } -}; - -template <> struct std::hash<rcc::LiveValueNumberID> { - [[nodiscard]] std::size_t operator()(rcc::LiveValueNumberID ID) const noexcept { - return std::hash<std::uint32_t>{}(ID.value()); - } -}; - -#endif // RCC_CODEGEN_MACHINELIVENESS_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 <compare> +#include <cstddef> +#include <cstdint> +#include <string_view> +#include <unordered_map> +#include <vector> + +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<SlotIndexKind>(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<std::uint64_t>(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<void> insertInstruction(const MachineInstr &Instruction); + [[nodiscard]] Expected<void> eraseInstruction(const MachineInstr &Instruction); + [[nodiscard]] Expected<void> renumber(MachineFunction &Function); + + [[nodiscard]] bool invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept; + + private: + std::unordered_map<MachineInstrStableID, SlotIndex> InstructionSlots; + std::unordered_map<std::uint64_t, const MachineInstr *> SlotToInstruction; + std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockStarts; + std::unordered_map<const MachineBasicBlock *, SlotIndex> BlockEnds; + std::vector<const MachineBasicBlock *> BlocksByStart; + + friend class SlotIndexesAnalysis; + }; + + [[nodiscard]] static constexpr std::string_view name() noexcept { + return "SlotIndexes"; + } + + [[nodiscard]] static Expected<Result> + run(MachineFunction &Function, const TargetDescription &Target, MachineAnalysisManager &Analyses); +}; + +} // namespace rcc + +template <> struct std::hash<rcc::SlotIndex> { + [[nodiscard]] std::size_t operator()(rcc::SlotIndex Index) const noexcept { + return std::hash<std::uint64_t>{}(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 <cstdint> diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 22bf032..470571d 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -37,7 +37,12 @@ set( MachineInstr.cpp MachineJumpTableInfo.cpp MachineLICM.cpp - MachineLiveness.cpp + SlotIndexes.cpp + LiveVariables.cpp + LiveInterval.cpp + LiveIntervals.cpp + LivePhysRegs.cpp + LiveRegUnits.cpp MachineMemoryFolding.cpp MachineMemOperand.cpp MachineMetadata.cpp @@ -120,8 +125,12 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineJumpTableInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLICM.h" - "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLiveness.h" - "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLivenessRepair.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/SlotIndexes.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveVariables.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveInterval.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveIntervals.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LivePhysRegs.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRegUnits.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemoryFolding.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMetadata.h" @@ -242,7 +251,12 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineLICM.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariables.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveInterval.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervals.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegs.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnits.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemoryFolding.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" @@ -325,7 +339,12 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineLICM.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariables.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveInterval.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervals.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegs.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnits.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemoryFolding.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" diff --git a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp index 8937fd8..ff32eda 100644 --- a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp +++ b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/GlobalISel/InstructionSelect.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index e61a801..60f388d 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp index 337db80..c36c500 100644 --- a/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp +++ b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp @@ -2,10 +2,10 @@ #include "rcc/CodeGen/GlobalISel/RegBankSelect.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/LiveInterval.cpp b/backend/lib/CodeGen/LiveInterval.cpp new file mode 100644 index 0000000..22e0164 --- /dev/null +++ b/backend/lib/CodeGen/LiveInterval.cpp @@ -0,0 +1,184 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveInterval.h" + +#include <algorithm> +#include <cstddef> +#include <limits> +#include <ranges> +#include <unordered_set> + +namespace rcc { + +const LiveSegment *LiveRange::segmentAt(SlotIndex Position) const noexcept { + const auto Candidate = std::ranges::upper_bound( + Segments, Position, {}, [](const LiveSegment &Segment) { return Segment.Start; }); + if (Candidate == Segments.begin()) + return nullptr; + const LiveSegment &Previous = *std::prev(Candidate); + return Previous.contains(Position) ? &Previous : nullptr; +} + +const LiveValueNumber *LiveRange::value(LiveValueNumberID ID) const noexcept { + if (!ID.isValid() || ID.value() > Values.size()) + return nullptr; + const LiveValueNumber &Result = Values[ID.value() - 1U]; + return Result.ID == ID ? &Result : nullptr; +} + +const LiveValueNumber *LiveRange::valueAt(SlotIndex Position) const noexcept { + const LiveSegment *Segment = segmentAt(Position); + return Segment == nullptr ? nullptr : value(Segment->Value); +} + +bool LiveRange::liveAt(SlotIndex Position) const noexcept { + return segmentAt(Position) != nullptr; +} + +bool LiveRange::overlaps(const LiveRange &Other) const noexcept { + std::size_t Left = 0; + std::size_t Right = 0; + while (Left < Segments.size() && Right < Other.Segments.size()) { + if (Segments[Left].overlaps(Other.Segments[Right])) + return true; + if (Segments[Left].End <= Other.Segments[Right].Start) + ++Left; + else + ++Right; + } + return false; +} + +Expected<LiveValueNumberID> LiveRange::createValue(SlotIndex Definition, LiveValueState State, + std::optional<MachineInstrStableID> Origin) { + if (!Definition.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); + if (Values.size() >= std::numeric_limits<std::uint32_t>::max()) + return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); + const LiveValueNumberID ID = + LiveValueNumberID::fromValue(static_cast<std::uint32_t>(Values.size() + 1U)); + Values.push_back({ID, Definition, State, Origin}); + return ID; +} + +Expected<void> LiveRange::addSegment(LiveSegment Segment) { + if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || + value(Segment.Value) == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "live segment requires ordered indexes and a known value number"); + } + std::vector<LiveSegment> Candidate = Segments; + Candidate.push_back(Segment); + std::ranges::sort(Candidate, [](const LiveSegment &Left, const LiveSegment &Right) { + if (Left.Start != Right.Start) + return Left.Start < Right.Start; + return Left.End < Right.End; + }); + for (std::size_t Index = 1; Index < Candidate.size(); ++Index) { + if (Candidate[Index].Start < Candidate[Index - 1U].End && + Candidate[Index].Value != Candidate[Index - 1U].Value) { + return makeUnexpected(ErrorCode::VerificationError, + "live segments with different values overlap"); + } + } + Segments = std::move(Candidate); + mergeAdjacent(); + return {}; +} + +Expected<void> LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { + return addSegment({Start, End, Value}); +} + +Expected<void> LiveRange::remove(SlotIndex Start, SlotIndex End) { + if (!Start.isValid() || !End.isValid() || !(Start < End)) { + return makeUnexpected(ErrorCode::InvalidArgument, "removed live range must be nonempty"); + } + std::vector<LiveSegment> Result; + for (const LiveSegment &Segment : Segments) { + if (!(Segment.Start < End && Start < Segment.End)) { + Result.push_back(Segment); + continue; + } + if (Segment.Start < Start) + Result.push_back({Segment.Start, Start, Segment.Value}); + if (End < Segment.End) + Result.push_back({End, Segment.End, Segment.Value}); + } + Segments = std::move(Result); + mergeAdjacent(); + return {}; +} + +Expected<void> LiveRange::shrinkToUses(std::span<const SlotIndex> Uses) { + std::vector<LiveSegment> Result; + for (const LiveSegment &Segment : Segments) { + const LiveValueNumber *Value = value(Segment.Value); + if (Value == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "live segment references an unknown value number"); + std::optional<SlotIndex> LastUse; + for (const SlotIndex Use : Uses) { + if (Segment.contains(Use) && (!LastUse || *LastUse < Use)) + LastUse = Use; + } + if (!LastUse) { + if (Value->State == LiveValueState::Unused) + Result.push_back(Segment); + continue; + } + SlotIndex NewEnd = LastUse->deadSlot(); + if (Segment.End < NewEnd) + NewEnd = Segment.End; + if (Segment.Start < NewEnd) + Result.push_back({Segment.Start, NewEnd, Segment.Value}); + } + Segments = std::move(Result); + mergeAdjacent(); + return verify(); +} + +Expected<void> LiveRange::verify() const { + std::unordered_set<LiveValueNumberID> IDs; + for (std::size_t Index = 0; Index < Values.size(); ++Index) { + const LiveValueNumber &Value = Values[Index]; + if (!Value.ID.isValid() || Value.ID.value() != Index + 1U || !IDs.insert(Value.ID).second || + !Value.Definition.isValid()) { + return makeUnexpected(ErrorCode::VerificationError, + "live range contains an invalid value number"); + } + } + for (std::size_t Index = 0; Index < Segments.size(); ++Index) { + const LiveSegment &Segment = Segments[Index]; + if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || + value(Segment.Value) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "live range contains an invalid segment"); + } + if (Index != 0 && Segments[Index - 1U].End > Segment.Start) { + return makeUnexpected(ErrorCode::VerificationError, + "live range segments are not ordered and disjoint"); + } + } + return {}; +} + +void LiveRange::mergeAdjacent() { + if (Segments.empty()) + return; + std::vector<LiveSegment> Result; + Result.reserve(Segments.size()); + Result.push_back(Segments.front()); + for (std::size_t Index = 1; Index < Segments.size(); ++Index) { + LiveSegment &Previous = Result.back(); + const LiveSegment &Current = Segments[Index]; + if (Current.Value == Previous.Value && Current.Start <= Previous.End) { + if (Previous.End < Current.End) + Previous.End = Current.End; + continue; + } + Result.push_back(Current); + } + Segments = std::move(Result); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveIntervals.cpp b/backend/lib/CodeGen/LiveIntervals.cpp new file mode 100644 index 0000000..d8cb539 --- /dev/null +++ b/backend/lib/CodeGen/LiveIntervals.cpp @@ -0,0 +1,421 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveIntervals.h" + +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <vector> + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional<LaneMask> Filter) noexcept { + return !Filter || Access.intersects(*Filter); +} + +struct InstructionRangeEvent final { + bool HasUse = false; + bool HasNormalDef = false; + bool HasEarlyDef = false; + bool HasRegMaskClobber = false; +}; + +[[nodiscard]] Expected<InstructionRangeEvent> +virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional<LaneMask> Filter, + const MachineFunction &Function, const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + const Register *OperandReg = Operand.getIf<Register>(); + if (OperandReg == nullptr || *OperandReg != Reg) + continue; + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + if (!maskIntersects(*Lanes, Filter)) + continue; + Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef); + if (Operand.isDef()) { + if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) + Event.HasEarlyDef = true; + else + Event.HasNormalDef = true; + } + } + return Event; +} + +[[nodiscard]] Expected<InstructionRangeEvent> unitRangeEvent(const MachineInstr &Instruction, + RegisterUnitID Unit, + std::optional<LaneMask> Filter, + const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + if (Operand.isRegister()) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isPhysical()) + continue; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + const auto Position = std::ranges::find_if( + *Units, [Unit](const PhysicalUnitAccess &Access) { return Access.Unit == Unit; }); + if (Position == Units->end() || !maskIntersects(Position->Lanes, Filter)) + continue; + Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef); + if (Operand.isDef()) { + if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) + Event.HasEarlyDef = true; + else + Event.HasNormalDef = true; + } + continue; + } + if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); + MaskOperand != nullptr && MaskOperand->Mask) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (!MaskOperand->Mask->clobbers(Description.Reg)) + continue; + if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { + return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); + })) { + Event.HasRegMaskClobber = true; + break; + } + } + continue; + } + if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>(); + MaskOperand != nullptr && MaskOperand->Mask) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (!MaskOperand->Mask->preserves(Description.Reg)) + continue; + if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { + return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); + })) { + Event.HasUse = true; + break; + } + } + } + } + return Event; +} + +template <typename EventFn, typename LiveOutFn> +[[nodiscard]] Expected<LiveRange> +buildLiveRange(MachineFunction &Function, const SlotIndexesAnalysis::Result &Indexes, + const EventFn &EventForInstruction, const LiveOutFn &IsLiveOut) { + LiveRange Range; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + std::optional<SlotIndex> End; + bool SawLaterDefinition = false; + if (IsLiveOut(*Block)) + End = Indexes.blockEnd(*Block); + + for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + auto Event = EventForInstruction(*Instruction); + if (!Event) + return std::unexpected(Event.error()); + if (!Event->HasUse && !Event->HasNormalDef && !Event->HasEarlyDef && + !Event->HasRegMaskClobber) { + continue; + } + + const SlotIndex InstructionSlot = Indexes.instructionIndex(*Instruction); + if (!InstructionSlot.isValid()) { + return makeUnexpected(ErrorCode::InternalError, + "live-range construction has no instruction SlotIndex"); + } + auto AddDefinition = [&](SlotIndex DefSlot, bool IsRegMask) -> Expected<void> { + const bool HasLiveValue = End && DefSlot < *End; + if (IsRegMask && !HasLiveValue) { + End.reset(); + SawLaterDefinition = true; + return {}; + } + const LiveValueState State = IsRegMask ? LiveValueState::Redefined + : HasLiveValue ? LiveValueState::Normal + : SawLaterDefinition ? LiveValueState::Redefined + : LiveValueState::Unused; + auto Value = Range.createValue(DefSlot, State, Instruction->stableID()); + if (!Value) + return std::unexpected(Value.error()); + const SlotIndex SegmentEnd = HasLiveValue ? *End : InstructionSlot.deadSlot(); + if (DefSlot < SegmentEnd) { + auto Added = Range.addSegment({DefSlot, SegmentEnd, *Value}); + if (!Added) + return std::unexpected(Added.error()); + } + End.reset(); + SawLaterDefinition = true; + return {}; + }; + + if (Event->HasNormalDef) { + auto Added = AddDefinition(InstructionSlot.registerSlot(), false); + if (!Added) + return std::unexpected(Added.error()); + } + if (Event->HasUse) { + const SlotIndex UseEnd = + Event->HasNormalDef ? InstructionSlot.registerSlot() : InstructionSlot.deadSlot(); + if (!End || *End < UseEnd) + End = UseEnd; + } + if (Event->HasEarlyDef) { + auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), false); + if (!Added) + return std::unexpected(Added.error()); + } else if (Event->HasRegMaskClobber) { + auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), true); + if (!Added) + return std::unexpected(Added.error()); + } + } + + if (End) { + const SlotIndex Start = Indexes.blockStart(*Block); + if (!Start.isValid() || !(*End > Start)) { + return makeUnexpected(ErrorCode::InternalError, + "live-in range has invalid block boundary indexes"); + } + auto Value = Range.createValue(Start, LiveValueState::Phi); + if (!Value) + return std::unexpected(Value.error()); + auto Added = Range.addSegment({Start, *End, *Value}); + if (!Added) + return std::unexpected(Added.error()); + } + } + auto Verification = Range.verify(); + if (!Verification) + return std::unexpected(Verification.error()); + return Range; +} + +[[nodiscard]] Expected<LaneMask> virtualRegisterFullLanes(Register Reg, + const MachineFunction &Function, + const TargetDescription &Target) { + return virtualRegisterLanes(Reg, Function, Target); +} + +[[nodiscard]] Expected<std::vector<LaneMask>> +partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, + const TargetDescription &Target) { + auto Full = virtualRegisterFullLanes(Reg, Function, Target); + if (!Full) + return std::unexpected(Full.error()); + std::vector<LaneMask> AccessMasks; + for (const MachineOperand &Operand : Function.registerInfo().regNoDebugOperands(Reg)) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + if (*Lanes != *Full && std::ranges::find(AccessMasks, *Lanes) == AccessMasks.end()) + AccessMasks.push_back(*Lanes); + } + if (AccessMasks.empty()) + return {}; + + std::vector<LaneMask> Groups{*Full}; + for (const LaneMask Access : AccessMasks) { + std::vector<LaneMask> Refined; + for (const LaneMask Group : Groups) { + const LaneMask Intersection = Group & Access; + const LaneMask Difference = subtractLanes(Group, Access); + if (!Intersection.empty()) + Refined.push_back(Intersection); + if (!Difference.empty()) + Refined.push_back(Difference); + } + Groups = std::move(Refined); + } + std::ranges::sort( + Groups, [](LaneMask Left, LaneMask Right) { return Left.rawValue() < Right.rawValue(); }); + return Groups; +} +} // namespace + +const LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) const noexcept { + const auto Position = Intervals.find(Reg); + return Position == Intervals.end() ? nullptr : &Position->second; +} + +LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) noexcept { + const auto Position = Intervals.find(Reg); + return Position == Intervals.end() ? nullptr : &Position->second; +} + +const LiveRange *LiveIntervalsAnalysis::Result::regUnitRange(RegisterUnitID Unit) const noexcept { + const auto Position = RegisterUnitRanges.find(Unit); + return Position == RegisterUnitRanges.end() ? nullptr : &Position->second; +} + +bool LiveIntervalsAnalysis::Result::interferes(Register Left, Register Right) const noexcept { + const LiveInterval *LeftInterval = interval(Left); + const LiveInterval *RightInterval = interval(Right); + return LeftInterval != nullptr && RightInterval != nullptr && + LeftInterval->overlaps(*RightInterval); +} + +bool LiveIntervalsAnalysis::Result::regMaskClobbers(const LiveInterval &Interval, + PhysicalRegister Candidate) const noexcept { + for (const RegMaskPosition &Position : RegMasks) { + if (Position.Mask && Position.Mask->clobbers(Candidate) && + Interval.MainRange.liveAt(Position.Position)) { + return true; + } + } + return false; +} + +Expected<void> LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, + std::span<const SlotIndex> Uses) { + LiveInterval *Value = interval(Reg); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no live interval"); + auto Main = Value->MainRange.shrinkToUses(Uses); + if (!Main) + return std::unexpected(Main.error()); + for (LiveSubRange &SubRange : Value->SubRanges) { + auto Shrunk = SubRange.Range.shrinkToUses(Uses); + if (!Shrunk) + return std::unexpected(Shrunk.error()); + } + return {}; +} + +bool LiveIntervalsAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id<LiveIntervalsAnalysis>()); +} + +Expected<LiveIntervalsAnalysis::Result> +LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Indexes = Analyses.getResult<SlotIndexesAnalysis>(Function, Target); + if (!Indexes) + return std::unexpected(Indexes.error()); + auto Variables = Analyses.getResult<LiveVariablesAnalysis>(Function, Target); + if (!Variables) + return std::unexpected(Variables.error()); + + Result ResultValue; + ResultValue.Indexes = **Indexes; + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { + auto RegValue = Register::makeVirtual(Index); + if (!RegValue || !Function.registerInfo().isKnownVirtualRegister(*RegValue)) + continue; + const Register Reg = *RegValue; + auto MainRange = buildLiveRange( + Function, ResultValue.Indexes, + [&Function, &Target, Reg](const MachineInstr &Instruction) { + return virtualRangeEvent(Instruction, Reg, std::nullopt, Function, Target); + }, + [&Variables, Reg](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->VirtualLiveOut.intersects(Reg); + }); + if (!MainRange) + return std::unexpected(MainRange.error()); + if (MainRange->empty()) + continue; + + LiveInterval Interval; + Interval.Reg = Reg; + Interval.MainRange = std::move(*MainRange); + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + // Preserve the target-provided hint order. MachineRegisterInfo already de-duplicates + // hints, and their order is the deterministic preference order consumed by allocators. + Interval.AllocationHints = Info->get().AllocationHints; + + std::uint64_t Weight = 1; + for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) { + if (Operand.parent() == nullptr || Operand.registerFlags().has(RegisterOperandFlag::Undef)) { + continue; + } + Weight = Weight > std::numeric_limits<std::uint64_t>::max() - 10U + ? std::numeric_limits<std::uint64_t>::max() + : Weight + 10U; + } + Interval.SpillWeight = Weight; + + auto LaneGroups = partitionVirtualRegisterLanes(Reg, Function, Target); + if (!LaneGroups) + return std::unexpected(LaneGroups.error()); + for (const LaneMask Lanes : *LaneGroups) { + auto SubRange = buildLiveRange( + Function, ResultValue.Indexes, + [&Function, &Target, Reg, Lanes](const MachineInstr &Instruction) { + return virtualRangeEvent(Instruction, Reg, Lanes, Function, Target); + }, + [&Variables, Reg, Lanes](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); + }); + if (!SubRange) + return std::unexpected(SubRange.error()); + if (!SubRange->empty()) + Interval.SubRanges.push_back({Lanes, std::move(*SubRange)}); + } + ResultValue.Intervals.emplace(Reg, std::move(Interval)); + } + + for (const RegisterUnitDesc &Unit : Target.registers().registerUnits()) { + auto Range = buildLiveRange( + Function, ResultValue.Indexes, + [&Target, Unit](const MachineInstr &Instruction) { + return unitRangeEvent(Instruction, Unit.ID, std::nullopt, Target); + }, + [&Variables, Unit](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit.ID); + }); + if (!Range) + return std::unexpected(Range.error()); + if (!Range->empty()) + ResultValue.RegisterUnitRanges.emplace(Unit.ID, std::move(*Range)); + } + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "live intervals encountered a null register mask"); + ResultValue.RegMasks.push_back( + {ResultValue.Indexes.instructionIndex(*Instruction).earlyClobberSlot(), + Instruction->stableID(), MaskOperand->Mask}); + } + } + } + return ResultValue; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LivePhysRegs.cpp b/backend/lib/CodeGen/LivePhysRegs.cpp new file mode 100644 index 0000000..9bbc069 --- /dev/null +++ b/backend/lib/CodeGen/LivePhysRegs.cpp @@ -0,0 +1,174 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LivePhysRegs.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <cstddef> +#include <ranges> +#include <vector> + +namespace rcc { + +namespace { +struct OperandFlagUpdate final { + MachineOperand *Operand = nullptr; + RegisterOperandFlags Flags; +}; + +[[nodiscard]] bool intersects(const LiveRegUnits &Live, + const std::vector<PhysicalUnitAccess> &Units) noexcept { + return std::ranges::any_of(Units, [&Live](const PhysicalUnitAccess &Unit) { + return Live.intersects(Unit.Unit, Unit.Lanes); + }); +} + +void addUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.add(Unit.Unit, Unit.Lanes); +} + +void removeUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.remove(Unit.Unit, Unit.Lanes); +} + +[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector<OperandFlagUpdate> &Updates, + MachineOperand &Operand) { + const auto Position = std::ranges::find_if( + Updates, [&Operand](const OperandFlagUpdate &Update) { return Update.Operand == &Operand; }); + if (Position != Updates.end()) + return *Position; + Updates.push_back({&Operand, Operand.registerFlags()}); + return Updates.back(); +} + +[[nodiscard]] Expected<std::vector<OperandFlagUpdate>> +buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, + const MachineBlockLiveness &Boundary) { + LiveRegUnits Live = Boundary.PhysicalLiveOut; + std::vector<OperandFlagUpdate> Updates; + for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); + if (Mask == nullptr) + continue; + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "post-RA liveness repair encountered a null live-out mask"); + } + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (Mask->Mask->preserves(Register.Reg)) + addPhysicalRegister(Live, Register); + } + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); + Update.Flags.clear(RegisterOperandFlag::Dead); + if (!Operand->isDef()) + continue; + const Register *Reg = Operand->getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + auto Units = physicalOperandUnits(*Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + if (!intersects(Live, *Units)) + Update.Flags.set(RegisterOperandFlag::Dead); + } + + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister() && Operand.isDef()) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + removeUnits(Live, *Units); + continue; + } + const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + if (Mask == nullptr) + continue; + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "post-RA liveness repair encountered a null register mask"); + } + LiveRegUnits Clobbers; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (Mask->Mask->clobbers(Register.Reg)) + addPhysicalRegister(Clobbers, Register); + } + Live.subtract(Clobbers); + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); + Update.Flags.clear(RegisterOperandFlag::Kill); + if (!Operand->isUse() || Operand->isDebugUse() || + Operand->registerFlags().has(RegisterOperandFlag::Undef)) { + continue; + } + const Register *Reg = Operand->getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + if (isReservedPhysicalRegister(*Reg, Block.function(), Target)) + continue; + auto Units = physicalOperandUnits(*Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + if (!intersects(Live, *Units)) + Update.Flags.set(RegisterOperandFlag::Kill); + addUnits(Live, *Units); + } + } + if (Live != Boundary.PhysicalLiveIn) { + return makeUnexpected(ErrorCode::InternalError, + "post-RA local liveness repair changed the block boundary"); + } + return Updates; +} +} // namespace + +Expected<bool> repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks, + const TargetDescription &Target, + const LiveVariablesAnalysis::Result &Liveness) { + std::vector<OperandFlagUpdate> Updates; + for (MachineBasicBlock *Block : Blocks) { + const MachineBlockLiveness *Boundary = Liveness.block(*Block); + if (Boundary == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "post-RA scheduler lost a block liveness boundary"); + } + auto BlockUpdates = buildBlockLivenessRepairPlan(*Block, Target, *Boundary); + if (!BlockUpdates) + return std::unexpected(BlockUpdates.error()); + Updates.insert(Updates.end(), BlockUpdates->begin(), BlockUpdates->end()); + } + bool Changed = false; + for (const OperandFlagUpdate &Update : Updates) { + Changed |= Update.Operand->registerFlags() != Update.Flags; + auto Applied = Update.Operand->setRegisterFlags(Update.Flags); + if (!Applied) + return std::unexpected(Applied.error()); + } + return Changed; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveRegUnits.cpp b/backend/lib/CodeGen/LiveRegUnits.cpp new file mode 100644 index 0000000..7df55c0 --- /dev/null +++ b/backend/lib/CodeGen/LiveRegUnits.cpp @@ -0,0 +1,280 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegUnits.h" + +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <bit> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <ranges> +#include <unordered_map> +#include <vector> + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +template <typename KeyT> +void addLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) { + if (Lanes.empty()) + return; + const auto Position = Values.find(Key); + if (Position == Values.end()) { + Values.emplace(Key, Lanes); + return; + } + Position->second = Position->second | Lanes; +} + +template <typename KeyT> +void removeLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) { + const auto Position = Values.find(Key); + if (Position == Values.end() || Lanes.empty()) + return; + Position->second = subtractLanes(Position->second, Lanes); + if (Position->second.empty()) + Values.erase(Position); +} + +template <typename KeyT> +[[nodiscard]] LaneMask lanesFor(const std::unordered_map<KeyT, LaneMask> &Values, + KeyT Key) noexcept { + const auto Position = Values.find(Key); + return Position == Values.end() ? LaneMask{} : Position->second; +} + +template <typename KeyT> +[[nodiscard]] bool containsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, + LaneMask Lanes) noexcept { + const LaneMask Present = lanesFor(Values, Key); + return !Present.empty() && Present.contains(Lanes); +} + +template <typename KeyT> +[[nodiscard]] bool intersectsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, + LaneMask Lanes) noexcept { + return lanesFor(Values, Key).intersects(Lanes); +} + +template <typename KeyT> +void uniteLanes(std::unordered_map<KeyT, LaneMask> &Values, + const std::unordered_map<KeyT, LaneMask> &Other) { + for (const auto &[Key, Lanes] : Other) + addLanes(Values, Key, Lanes); +} + +template <typename KeyT> +void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values, + const std::unordered_map<KeyT, LaneMask> &Other) { + for (const auto &[Key, Lanes] : Other) + removeLanes(Values, Key, Lanes); +} + +} // namespace + +LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept { + std::uint64_t View = UnitViewLanes.rawValue(); + const std::uint64_t Selected = View & RegisterLanes.rawValue(); + std::uint64_t Normalized = 0; + std::uint32_t UnitLane = 0; + while (View != 0) { + const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); + if ((Selected & RegisterLane) != 0) + Normalized |= std::uint64_t{1} << UnitLane; + View &= View - 1U; + ++UnitLane; + } + return LaneMask::fromRaw(Normalized); +} + +LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept { + std::uint64_t View = UnitViewLanes.rawValue(); + const std::uint64_t Selected = UnitLanes.rawValue(); + std::uint64_t RegisterLanes = 0; + std::uint32_t UnitLane = 0; + while (View != 0) { + const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); + if ((Selected & (std::uint64_t{1} << UnitLane)) != 0) + RegisterLanes |= RegisterLane; + View &= View - 1U; + ++UnitLane; + } + return LaneMask::fromRaw(RegisterLanes); +} + +LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept { + LaneMask Result; + for (const RegisterUnitLane &Unit : Description.Units) + Result = Result | Unit.Lanes; + return Result; +} + +LiveRegUnits physicalRegisterCoverage(const PhysicalRegisterDesc &Description, LaneMask Requested) { + LiveRegUnits Result; + for (const RegisterUnitLane &Unit : Description.Units) + Result.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes, Requested)); + return Result; +} + +bool isSubset(const LiveRegUnits &Subset, const LiveRegUnits &Superset) noexcept { + return std::ranges::all_of(Subset.entries(), [&Superset](const auto &Entry) { + return Superset.contains(Entry.first, Entry.second); + }); +} + +std::size_t laneCount(const LiveRegUnits &Set) noexcept { + std::size_t Result = 0; + for (const auto &[Unit, Lanes] : Set.entries()) { + (void)Unit; + Result += static_cast<std::size_t>(std::popcount(Lanes.rawValue())); + } + return Result; +} + +[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) { + if (!Reg.isVirtual()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "virtual lane query requires a virtual register"); + } + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional<RegisterClassID> ClassID = Info->get().RegClass; + if (!ClassID) + return LaneMask::all(); + const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID); + if (Class == nullptr || Class->Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or empty register class"); + } + return Class->Lanes; +} + +[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "virtual lane query requires a virtual-register operand"); + } + if (Operand.subReg().value() != 0) { + const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg()); + if (SubReg == nullptr || SubReg->Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or empty subregister lane mask"); + } + return SubReg->Lanes; + } + + return virtualRegisterLanes(*Reg, Function, Target); +} + +[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> +physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { + const Register *Reg = Operand.getIf<Register>(); + const std::optional<PhysicalRegister> Original = + Reg == nullptr ? std::nullopt : Reg->physicalRegister(); + if (!Original) { + return makeUnexpected(ErrorCode::InvalidArgument, + "physical unit query requires a physical-register operand"); + } + + PhysicalRegister Effective = *Original; + if (Operand.subReg().value() != 0) { + const std::optional<PhysicalRegister> SubRegister = + Target.registers().subRegister(*Original, Operand.subReg()); + if (!SubRegister) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register has no requested subregister projection"); + } + Effective = *SubRegister; + } + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Effective); + if (Description == nullptr || Description->Units.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or unitless physical register"); + } + + std::vector<PhysicalUnitAccess> Result; + Result.reserve(Description->Units.size()); + for (const RegisterUnitLane &Unit : Description->Units) { + if (Unit.Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register unit has an empty lane mask"); + } + Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes, LaneMask::all())}); + } + return Result; +} + +void addPhysicalRegister(LiveRegUnits &Set, const PhysicalRegisterDesc &Description, + LaneMask Requested) { + Set.unite(physicalRegisterCoverage(Description, Requested)); +} + +[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) noexcept { + const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); + return Physical && (Function.registerInfo().isReserved(*Physical) || + Target.registers().isReservedRegister(*Physical)); +} + +[[nodiscard]] Expected<void> addRegisterMaskDefs(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (Mask.clobbers(Description.Reg)) + addPhysicalRegister(Set, Description); + } + return {}; +} + +[[nodiscard]] Expected<void> addRegisterMaskUses(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (Mask.preserves(Description.Reg)) + addPhysicalRegister(Set, Description); + } + return {}; +} +LaneMask LiveRegUnits::lanes(RegisterUnitID Unit) const noexcept { + return lanesFor(Values, Unit); +} + +bool LiveRegUnits::contains(RegisterUnitID Unit, LaneMask Lanes) const noexcept { + return containsLanes(Values, Unit, Lanes); +} + +bool LiveRegUnits::intersects(RegisterUnitID Unit, LaneMask Lanes) const noexcept { + return intersectsLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::add(RegisterUnitID Unit, LaneMask Lanes) { + if (Unit.value() != 0 && !Lanes.empty()) + addLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::remove(RegisterUnitID Unit, LaneMask Lanes) { + removeLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::unite(const LiveRegUnits &Other) { + uniteLanes(Values, Other.Values); +} + +void LiveRegUnits::subtract(const LiveRegUnits &Other) { + subtractLaneSets(Values, Other.Values); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineLiveness.cpp b/backend/lib/CodeGen/LiveVariables.cpp index 9882b11..7323e0d 100644 --- a/backend/lib/CodeGen/MachineLiveness.cpp +++ b/backend/lib/CodeGen/LiveVariables.cpp @@ -1,13 +1,16 @@ // SPDX-License-Identifier: GPL-3.0-or-later -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/CodeGen/LiveInterval.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/SlotIndexes.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetRegisterInfo.h" @@ -20,16 +23,14 @@ #include <optional> #include <ranges> #include <string> +#include <unordered_map> #include <unordered_set> #include <utility> #include <vector> namespace rcc { -namespace { - -constexpr std::uint64_t SlotSpacing = 16; -constexpr std::uint64_t SlotAlignmentMask = 3; +namespace { [[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); } @@ -90,182 +91,7 @@ void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values, removeLanes(Values, Key, Lanes); } -struct PhysicalUnitAccess final { - RegisterUnitID Unit; - LaneMask Lanes; -}; - -[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - const std::uint64_t Selected = View & RegisterLanes.rawValue(); - std::uint64_t Normalized = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); - if ((Selected & RegisterLane) != 0) - Normalized |= std::uint64_t{1} << UnitLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(Normalized); -} - -[[nodiscard]] LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - const std::uint64_t Selected = UnitLanes.rawValue(); - std::uint64_t RegisterLanes = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); - if ((Selected & (std::uint64_t{1} << UnitLane)) != 0) - RegisterLanes |= RegisterLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(RegisterLanes); -} - -[[nodiscard]] LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept { - LaneMask Result; - for (const RegisterUnitLane &Unit : Description.Units) - Result = Result | Unit.Lanes; - return Result; -} - -[[nodiscard]] RegisterUnitLaneSet physicalRegisterCoverage(const PhysicalRegisterDesc &Description, - LaneMask Requested) { - RegisterUnitLaneSet Result; - for (const RegisterUnitLane &Unit : Description.Units) - Result.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes, Requested)); - return Result; -} - -[[nodiscard]] bool isSubset(const RegisterUnitLaneSet &Subset, - const RegisterUnitLaneSet &Superset) noexcept { - return std::ranges::all_of(Subset.entries(), [&Superset](const auto &Entry) { - return Superset.contains(Entry.first, Entry.second); - }); -} - -[[nodiscard]] std::size_t laneCount(const RegisterUnitLaneSet &Set) noexcept { - std::size_t Result = 0; - for (const auto &[Unit, Lanes] : Set.entries()) { - (void)Unit; - Result += static_cast<std::size_t>(std::popcount(Lanes.rawValue())); - } - return Result; -} - -[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) { - if (!Reg.isVirtual()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "virtual lane query requires a virtual register"); - } - auto Info = Function.registerInfo().virtualRegisterInfo(Reg); - if (!Info) - return std::unexpected(Info.error()); - const std::optional<RegisterClassID> ClassID = Info->get().RegClass; - if (!ClassID) - return LaneMask::all(); - const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID); - if (Class == nullptr || Class->Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or empty register class"); - } - return Class->Lanes; -} - -[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || !Reg->isVirtual()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "virtual lane query requires a virtual-register operand"); - } - if (Operand.subReg().value() != 0) { - const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg()); - if (SubReg == nullptr || SubReg->Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or empty subregister lane mask"); - } - return SubReg->Lanes; - } - - return virtualRegisterLanes(*Reg, Function, Target); -} - -[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - const std::optional<PhysicalRegister> Original = - Reg == nullptr ? std::nullopt : Reg->physicalRegister(); - if (!Original) { - return makeUnexpected(ErrorCode::InvalidArgument, - "physical unit query requires a physical-register operand"); - } - - PhysicalRegister Effective = *Original; - if (Operand.subReg().value() != 0) { - const std::optional<PhysicalRegister> SubRegister = - Target.registers().subRegister(*Original, Operand.subReg()); - if (!SubRegister) { - return makeUnexpected(ErrorCode::VerificationError, - "physical register has no requested subregister projection"); - } - Effective = *SubRegister; - } - const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Effective); - if (Description == nullptr || Description->Units.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or unitless physical register"); - } - - std::vector<PhysicalUnitAccess> Result; - Result.reserve(Description->Units.size()); - for (const RegisterUnitLane &Unit : Description->Units) { - if (Unit.Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "physical register unit has an empty lane mask"); - } - Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes, LaneMask::all())}); - } - return Result; -} - -void addPhysicalRegister(RegisterUnitLaneSet &Set, const PhysicalRegisterDesc &Description, - LaneMask Requested = LaneMask::all()) { - Set.unite(physicalRegisterCoverage(Description, Requested)); -} - -[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) noexcept { - const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] Expected<void> addRegisterMaskDefs(RegisterUnitLaneSet &Set, const RegisterMask &Mask, - const TargetDescription &Target) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (Mask.clobbers(Description.Reg)) - addPhysicalRegister(Set, Description); - } - return {}; -} - -[[nodiscard]] Expected<void> addRegisterMaskUses(RegisterUnitLaneSet &Set, const RegisterMask &Mask, - const TargetDescription &Target) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (Mask.preserves(Description.Reg)) - addPhysicalRegister(Set, Description); - } - return {}; -} - -[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses, - RegisterUnitLaneSet &PhysicalUses, +[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses, LiveRegUnits &PhysicalUses, const MachineOperand &Operand, const MachineFunction &Function, const TargetDescription &Target) { @@ -291,8 +117,7 @@ void addPhysicalRegister(RegisterUnitLaneSet &Set, const PhysicalRegisterDesc &D return {}; } -[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs, - RegisterUnitLaneSet &PhysicalDefs, +[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs, LiveRegUnits &PhysicalDefs, const MachineOperand &Operand, const MachineFunction &Function, const TargetDescription &Target) { @@ -331,7 +156,7 @@ struct LivenessEdgeKeyHash final { struct EdgeLivenessUses final { RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; + LiveRegUnits Physical; }; [[nodiscard]] Expected<LiveVariablesAnalysis::Result> @@ -408,8 +233,8 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T RegisterLaneSet InstructionVirtualUses; RegisterLaneSet InstructionVirtualDefs; - RegisterUnitLaneSet InstructionPhysicalUses; - RegisterUnitLaneSet InstructionPhysicalDefs; + LiveRegUnits InstructionPhysicalUses; + LiveRegUnits InstructionPhysicalDefs; for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { const MachineOperand &Operand = *Instruction->operandAt(Index); if (Operand.isRegister()) { @@ -453,7 +278,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T Liveness.VirtualUses.unite(NewVirtualUses); Liveness.VirtualDefs.unite(InstructionVirtualDefs); - RegisterUnitLaneSet NewPhysicalUses = InstructionPhysicalUses; + LiveRegUnits NewPhysicalUses = InstructionPhysicalUses; NewPhysicalUses.subtract(Liveness.PhysicalDefs); Liveness.PhysicalUses.unite(NewPhysicalUses); Liveness.PhysicalDefs.unite(InstructionPhysicalDefs); @@ -466,7 +291,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T for (const MachineBasicBlock *Block : Blocks | std::views::reverse) { MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); RegisterLaneSet VirtualOut; - RegisterUnitLaneSet PhysicalOut; + LiveRegUnits PhysicalOut; for (const MachineSuccessor &Successor : Block->successors()) { if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) { return makeUnexpected(ErrorCode::VerificationError, @@ -485,7 +310,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T RegisterLaneSet VirtualIn = VirtualOut; VirtualIn.subtract(Liveness.VirtualDefs); VirtualIn.unite(Liveness.VirtualUses); - RegisterUnitLaneSet PhysicalIn = PhysicalOut; + LiveRegUnits PhysicalIn = PhysicalOut; PhysicalIn.subtract(Liveness.PhysicalDefs); PhysicalIn.unite(Liveness.PhysicalUses); @@ -501,241 +326,12 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T } return Result; } - -[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional<LaneMask> Filter) noexcept { - return !Filter || Access.intersects(*Filter); -} - -struct InstructionRangeEvent final { - bool HasUse = false; - bool HasNormalDef = false; - bool HasEarlyDef = false; - bool HasRegMaskClobber = false; -}; - -[[nodiscard]] Expected<InstructionRangeEvent> -virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional<LaneMask> Filter, - const MachineFunction &Function, const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - const Register *OperandReg = Operand.getIf<Register>(); - if (OperandReg == nullptr || *OperandReg != Reg) - continue; - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - if (!maskIntersects(*Lanes, Filter)) - continue; - Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && - !Operand.registerFlags().has(RegisterOperandFlag::Undef); - if (Operand.isDef()) { - if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) - Event.HasEarlyDef = true; - else - Event.HasNormalDef = true; - } - } - return Event; -} - -[[nodiscard]] Expected<InstructionRangeEvent> unitRangeEvent(const MachineInstr &Instruction, - RegisterUnitID Unit, - std::optional<LaneMask> Filter, - const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - if (Operand.isRegister()) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || !Reg->isPhysical()) - continue; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - const auto Position = std::ranges::find_if( - *Units, [Unit](const PhysicalUnitAccess &Access) { return Access.Unit == Unit; }); - if (Position == Units->end() || !maskIntersects(Position->Lanes, Filter)) - continue; - Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && - !Operand.registerFlags().has(RegisterOperandFlag::Undef); - if (Operand.isDef()) { - if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) - Event.HasEarlyDef = true; - else - Event.HasNormalDef = true; - } - continue; - } - if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); - MaskOperand != nullptr && MaskOperand->Mask) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (!MaskOperand->Mask->clobbers(Description.Reg)) - continue; - if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { - return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); - })) { - Event.HasRegMaskClobber = true; - break; - } - } - continue; - } - if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>(); - MaskOperand != nullptr && MaskOperand->Mask) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (!MaskOperand->Mask->preserves(Description.Reg)) - continue; - if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { - return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); - })) { - Event.HasUse = true; - break; - } - } - } - } - return Event; -} - -template <typename EventFn, typename LiveOutFn> -[[nodiscard]] Expected<LiveRange> -buildLiveRange(MachineFunction &Function, const SlotIndexesAnalysis::Result &Indexes, - const EventFn &EventForInstruction, const LiveOutFn &IsLiveOut) { - LiveRange Range; - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - std::optional<SlotIndex> End; - bool SawLaterDefinition = false; - if (IsLiveOut(*Block)) - End = Indexes.blockEnd(*Block); - - for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - auto Event = EventForInstruction(*Instruction); - if (!Event) - return std::unexpected(Event.error()); - if (!Event->HasUse && !Event->HasNormalDef && !Event->HasEarlyDef && - !Event->HasRegMaskClobber) { - continue; - } - - const SlotIndex InstructionSlot = Indexes.instructionIndex(*Instruction); - if (!InstructionSlot.isValid()) { - return makeUnexpected(ErrorCode::InternalError, - "live-range construction has no instruction SlotIndex"); - } - auto AddDefinition = [&](SlotIndex DefSlot, bool IsRegMask) -> Expected<void> { - const bool HasLiveValue = End && DefSlot < *End; - if (IsRegMask && !HasLiveValue) { - End.reset(); - SawLaterDefinition = true; - return {}; - } - const LiveValueState State = IsRegMask ? LiveValueState::Redefined - : HasLiveValue ? LiveValueState::Normal - : SawLaterDefinition ? LiveValueState::Redefined - : LiveValueState::Unused; - auto Value = Range.createValue(DefSlot, State, Instruction->stableID()); - if (!Value) - return std::unexpected(Value.error()); - const SlotIndex SegmentEnd = HasLiveValue ? *End : InstructionSlot.deadSlot(); - if (DefSlot < SegmentEnd) { - auto Added = Range.addSegment({DefSlot, SegmentEnd, *Value}); - if (!Added) - return std::unexpected(Added.error()); - } - End.reset(); - SawLaterDefinition = true; - return {}; - }; - - if (Event->HasNormalDef) { - auto Added = AddDefinition(InstructionSlot.registerSlot(), false); - if (!Added) - return std::unexpected(Added.error()); - } - if (Event->HasUse) { - const SlotIndex UseEnd = - Event->HasNormalDef ? InstructionSlot.registerSlot() : InstructionSlot.deadSlot(); - if (!End || *End < UseEnd) - End = UseEnd; - } - if (Event->HasEarlyDef) { - auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), false); - if (!Added) - return std::unexpected(Added.error()); - } else if (Event->HasRegMaskClobber) { - auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), true); - if (!Added) - return std::unexpected(Added.error()); - } - } - - if (End) { - const SlotIndex Start = Indexes.blockStart(*Block); - if (!Start.isValid() || !(*End > Start)) { - return makeUnexpected(ErrorCode::InternalError, - "live-in range has invalid block boundary indexes"); - } - auto Value = Range.createValue(Start, LiveValueState::Phi); - if (!Value) - return std::unexpected(Value.error()); - auto Added = Range.addSegment({Start, *End, *Value}); - if (!Added) - return std::unexpected(Added.error()); - } - } - auto Verification = Range.verify(); - if (!Verification) - return std::unexpected(Verification.error()); - return Range; -} - -[[nodiscard]] Expected<LaneMask> virtualRegisterFullLanes(Register Reg, - const MachineFunction &Function, - const TargetDescription &Target) { - return virtualRegisterLanes(Reg, Function, Target); -} - -[[nodiscard]] Expected<std::vector<LaneMask>> -partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, - const TargetDescription &Target) { - auto Full = virtualRegisterFullLanes(Reg, Function, Target); - if (!Full) - return std::unexpected(Full.error()); - std::vector<LaneMask> AccessMasks; - for (const MachineOperand &Operand : Function.registerInfo().regNoDebugOperands(Reg)) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - if (*Lanes != *Full && std::ranges::find(AccessMasks, *Lanes) == AccessMasks.end()) - AccessMasks.push_back(*Lanes); - } - if (AccessMasks.empty()) - return {}; - - std::vector<LaneMask> Groups{*Full}; - for (const LaneMask Access : AccessMasks) { - std::vector<LaneMask> Refined; - for (const LaneMask Group : Groups) { - const LaneMask Intersection = Group & Access; - const LaneMask Difference = subtractLanes(Group, Access); - if (!Intersection.empty()) - Refined.push_back(Intersection); - if (!Difference.empty()) - Refined.push_back(Difference); - } - Groups = std::move(Refined); - } - std::ranges::sort( - Groups, [](LaneMask Left, LaneMask Right) { return Left.rawValue() < Right.rawValue(); }); - return Groups; -} - [[nodiscard]] Expected<std::vector<MachineBasicBlockLiveIn>> -canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescription &Target) { +canonicalPhysicalLiveIns(const LiveRegUnits &Units, const TargetDescription &Target) { struct Candidate final { const PhysicalRegisterDesc *Description = nullptr; LaneMask RegisterLanes; - RegisterUnitLaneSet Coverage; + LiveRegUnits Coverage; std::size_t ExtraLanes = 0; bool Selected = false; }; @@ -751,8 +347,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti std::uint64_t PendingLanes = RelevantLanes.rawValue(); while (PendingLanes != 0) { const std::uint64_t Lane = std::uint64_t{1} << std::countr_zero(PendingLanes); - const RegisterUnitLaneSet Coverage = - physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane)); + const LiveRegUnits Coverage = physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane)); if (isSubset(Coverage, Units)) SelectableLanes |= Lane; PendingLanes &= PendingLanes - 1U; @@ -768,7 +363,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti Candidates.push_back(std::move(Value)); } - RegisterUnitLaneSet Covered; + LiveRegUnits Covered; std::vector<MachineBasicBlockLiveIn> Result; while (Covered != Units) { Candidate *Best = nullptr; @@ -777,7 +372,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti for (Candidate &Value : Candidates) { if (Value.Selected) continue; - RegisterUnitLaneSet NewCoverage = Value.Coverage; + LiveRegUnits NewCoverage = Value.Coverage; NewCoverage.subtract(Covered); const std::size_t NewLanes = laneCount(NewCoverage); if (NewLanes == 0) @@ -812,9 +407,9 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti return Result; } -[[nodiscard]] Expected<RegisterUnitLaneSet> -liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns, const TargetDescription &Target) { - RegisterUnitLaneSet Result; +[[nodiscard]] Expected<LiveRegUnits> liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns, + const TargetDescription &Target) { + LiveRegUnits Result; for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) { const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg); if (Description == nullptr) { @@ -848,7 +443,7 @@ struct LivenessRebuildPlan final { [[nodiscard]] Expected<bool> liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, - const RegisterUnitLaneSet &Physical, const MachineFunction &Function, + const LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target, bool TreatReservedAsLive) { const Register *Reg = Operand.getIf<Register>(); if (Reg == nullptr || Reg->isNoRegister()) @@ -871,7 +466,7 @@ liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, [[nodiscard]] Expected<void> removeOperandFromLiveSet(const MachineOperand &Operand, RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, + LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target) { const Register *Reg = Operand.getIf<Register>(); @@ -893,18 +488,17 @@ liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, } [[nodiscard]] Expected<void> addOperandToLiveSet(const MachineOperand &Operand, - RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, + RegisterLaneSet &Virtual, LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target) { return addOperandUse(Virtual, Physical, Operand, Function, Target); } -[[nodiscard]] Expected<RegisterUnitLaneSet> -requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, const MachineFunction &Function, - const TargetDescription &Target) { +[[nodiscard]] Expected<LiveRegUnits> requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, + const MachineFunction &Function, + const TargetDescription &Target) { RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; + LiveRegUnits Physical; for (const MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; Instruction = Instruction->previous()) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); @@ -940,7 +534,7 @@ requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, const MachineFuncti return makeUnexpected(ErrorCode::VerificationError, "liveness verification encountered a null register mask"); } - RegisterUnitLaneSet Clobbers; + LiveRegUnits Clobbers; auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); if (!Added) return std::unexpected(Added.error()); @@ -981,7 +575,7 @@ buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescriptio std::move(*NewLiveIns)}); RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut; - RegisterUnitLaneSet Physical = BlockVariables->PhysicalLiveOut; + LiveRegUnits Physical = BlockVariables->PhysicalLiveOut; for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; Instruction = Instruction->previous()) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); @@ -1030,7 +624,7 @@ buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescriptio if (!MaskOperand->Mask) return makeUnexpected(ErrorCode::VerificationError, "liveness rebuild encountered a null register mask"); - RegisterUnitLaneSet Clobbers; + LiveRegUnits Clobbers; auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); if (!Added) return std::unexpected(Added.error()); @@ -1221,149 +815,8 @@ resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) } return Changed; } - } // namespace -SlotIndex -SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept { - const auto Position = InstructionSlots.find(Instruction.stableID()); - return Position == InstructionSlots.end() ? SlotIndex{} : Position->second; -} - -SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept { - const auto Position = BlockStarts.find(&Block); - return Position == BlockStarts.end() ? SlotIndex{} : Position->second; -} - -SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept { - const auto Position = BlockEnds.find(&Block); - return Position == BlockEnds.end() ? SlotIndex{} : Position->second; -} - -const MachineInstr * -SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept { - if (!Index.isValid()) - return nullptr; - const auto Position = SlotToInstruction.find(Index.baseIndex().value()); - return Position == SlotToInstruction.end() ? nullptr : Position->second; -} - -const MachineBasicBlock * -SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept { - if (!Index.isValid()) - return nullptr; - for (const MachineBasicBlock *Block : BlocksByStart) { - const SlotIndex Start = blockStart(*Block); - const SlotIndex End = blockEnd(*Block); - if (!(Index < Start) && Index < End) - return Block; - } - return nullptr; -} - -Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) { - const MachineBasicBlock *Block = Instruction.parent(); - if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) { - return makeUnexpected(ErrorCode::InvalidArgument, - "SlotIndex insertion requires a linked indexed instruction"); - } - if (InstructionSlots.contains(Instruction.stableID())) { - return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex"); - } - - const MachineInstr *Previous = Instruction.previous(); - const MachineInstr *Next = Instruction.next(); - const SlotIndex LowerIndex = - Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous); - const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next); - if (!LowerIndex.isValid() || !UpperIndex.isValid()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "adjacent instructions are missing SlotIndexes"); - } - const std::uint64_t Lower = LowerIndex.baseIndex().value(); - const std::uint64_t Upper = UpperIndex.baseIndex().value(); - if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) { - return makeUnexpected(ErrorCode::Unsupported, - "local SlotIndex space is exhausted; renumbering is required"); - } - std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask; - if (Candidate <= Lower) - Candidate = Lower + SlotAlignmentMask + 1U; - if (Candidate >= Upper) { - return makeUnexpected(ErrorCode::Unsupported, - "local SlotIndex space is exhausted; renumbering is required"); - } - const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot(); - InstructionSlots.emplace(Instruction.stableID(), Index); - SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction); - return {}; -} - -Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) { - const auto Position = InstructionSlots.find(Instruction.stableID()); - if (Position == InstructionSlots.end()) - return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex"); - SlotToInstruction.erase(Position->second.baseIndex().value()); - InstructionSlots.erase(Position); - return {}; -} - -Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { - Result NewResult; - std::uint64_t Position = SlotSpacing; - auto Advance = [&Position]() -> Expected<void> { - if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) { - return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted"); - } - Position += SlotSpacing; - return {}; - }; - - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block); - NewResult.BlockStarts.emplace(Block, Start); - NewResult.BlocksByStart.push_back(Block); - auto Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - - for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot(); - if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second || - !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) { - return makeUnexpected(ErrorCode::VerificationError, - "duplicate instruction identity during SlotIndex construction"); - } - Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - } - NewResult.BlockEnds.emplace(Block, - SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block)); - Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - } - *this = std::move(NewResult); - return {}; -} - -bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept { - return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>()); -} - -Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function, - const TargetDescription &, - MachineAnalysisManager &) { - Result ResultValue; - auto Numbered = ResultValue.renumber(Function); - if (!Numbered) - return std::unexpected(Numbered.error()); - return ResultValue; -} - LaneMask RegisterLaneSet::lanes(Register Reg) const noexcept { return lanesFor(Values, Reg); } @@ -1392,36 +845,6 @@ void RegisterLaneSet::unite(const RegisterLaneSet &Other) { void RegisterLaneSet::subtract(const RegisterLaneSet &Other) { subtractLaneSets(Values, Other.Values); } - -LaneMask RegisterUnitLaneSet::lanes(RegisterUnitID Unit) const noexcept { - return lanesFor(Values, Unit); -} - -bool RegisterUnitLaneSet::contains(RegisterUnitID Unit, LaneMask Lanes) const noexcept { - return containsLanes(Values, Unit, Lanes); -} - -bool RegisterUnitLaneSet::intersects(RegisterUnitID Unit, LaneMask Lanes) const noexcept { - return intersectsLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::add(RegisterUnitID Unit, LaneMask Lanes) { - if (Unit.value() != 0 && !Lanes.empty()) - addLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::remove(RegisterUnitID Unit, LaneMask Lanes) { - removeLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::unite(const RegisterUnitLaneSet &Other) { - uniteLanes(Values, Other.Values); -} - -void RegisterUnitLaneSet::subtract(const RegisterUnitLaneSet &Other) { - subtractLaneSets(Values, Other.Values); -} - const MachineBlockLiveness * LiveVariablesAnalysis::Result::block(const MachineBasicBlock &Block) const noexcept { const auto Position = Blocks.find(&Block); @@ -1469,340 +892,6 @@ Expected<LiveVariablesAnalysis::Result> LiveVariablesAnalysis::run(MachineFuncti MachineAnalysisManager &) { return computeLiveVariables(Function, Target); } - -const LiveSegment *LiveRange::segmentAt(SlotIndex Position) const noexcept { - const auto Candidate = std::ranges::upper_bound( - Segments, Position, {}, [](const LiveSegment &Segment) { return Segment.Start; }); - if (Candidate == Segments.begin()) - return nullptr; - const LiveSegment &Previous = *std::prev(Candidate); - return Previous.contains(Position) ? &Previous : nullptr; -} - -const LiveValueNumber *LiveRange::value(LiveValueNumberID ID) const noexcept { - if (!ID.isValid() || ID.value() > Values.size()) - return nullptr; - const LiveValueNumber &Result = Values[ID.value() - 1U]; - return Result.ID == ID ? &Result : nullptr; -} - -const LiveValueNumber *LiveRange::valueAt(SlotIndex Position) const noexcept { - const LiveSegment *Segment = segmentAt(Position); - return Segment == nullptr ? nullptr : value(Segment->Value); -} - -bool LiveRange::liveAt(SlotIndex Position) const noexcept { - return segmentAt(Position) != nullptr; -} - -bool LiveRange::overlaps(const LiveRange &Other) const noexcept { - std::size_t Left = 0; - std::size_t Right = 0; - while (Left < Segments.size() && Right < Other.Segments.size()) { - if (Segments[Left].overlaps(Other.Segments[Right])) - return true; - if (Segments[Left].End <= Other.Segments[Right].Start) - ++Left; - else - ++Right; - } - return false; -} - -Expected<LiveValueNumberID> LiveRange::createValue(SlotIndex Definition, LiveValueState State, - std::optional<MachineInstrStableID> Origin) { - if (!Definition.isValid()) - return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); - if (Values.size() >= std::numeric_limits<std::uint32_t>::max()) - return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); - const LiveValueNumberID ID = - LiveValueNumberID::fromValue(static_cast<std::uint32_t>(Values.size() + 1U)); - Values.push_back({ID, Definition, State, Origin}); - return ID; -} - -Expected<void> LiveRange::addSegment(LiveSegment Segment) { - if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || - value(Segment.Value) == nullptr) { - return makeUnexpected(ErrorCode::InvalidArgument, - "live segment requires ordered indexes and a known value number"); - } - std::vector<LiveSegment> Candidate = Segments; - Candidate.push_back(Segment); - std::ranges::sort(Candidate, [](const LiveSegment &Left, const LiveSegment &Right) { - if (Left.Start != Right.Start) - return Left.Start < Right.Start; - return Left.End < Right.End; - }); - for (std::size_t Index = 1; Index < Candidate.size(); ++Index) { - if (Candidate[Index].Start < Candidate[Index - 1U].End && - Candidate[Index].Value != Candidate[Index - 1U].Value) { - return makeUnexpected(ErrorCode::VerificationError, - "live segments with different values overlap"); - } - } - Segments = std::move(Candidate); - mergeAdjacent(); - return {}; -} - -Expected<void> LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { - return addSegment({Start, End, Value}); -} - -Expected<void> LiveRange::remove(SlotIndex Start, SlotIndex End) { - if (!Start.isValid() || !End.isValid() || !(Start < End)) { - return makeUnexpected(ErrorCode::InvalidArgument, "removed live range must be nonempty"); - } - std::vector<LiveSegment> Result; - for (const LiveSegment &Segment : Segments) { - if (!(Segment.Start < End && Start < Segment.End)) { - Result.push_back(Segment); - continue; - } - if (Segment.Start < Start) - Result.push_back({Segment.Start, Start, Segment.Value}); - if (End < Segment.End) - Result.push_back({End, Segment.End, Segment.Value}); - } - Segments = std::move(Result); - mergeAdjacent(); - return {}; -} - -Expected<void> LiveRange::shrinkToUses(std::span<const SlotIndex> Uses) { - std::vector<LiveSegment> Result; - for (const LiveSegment &Segment : Segments) { - const LiveValueNumber *Value = value(Segment.Value); - if (Value == nullptr) - return makeUnexpected(ErrorCode::VerificationError, - "live segment references an unknown value number"); - std::optional<SlotIndex> LastUse; - for (const SlotIndex Use : Uses) { - if (Segment.contains(Use) && (!LastUse || *LastUse < Use)) - LastUse = Use; - } - if (!LastUse) { - if (Value->State == LiveValueState::Unused) - Result.push_back(Segment); - continue; - } - SlotIndex NewEnd = LastUse->deadSlot(); - if (Segment.End < NewEnd) - NewEnd = Segment.End; - if (Segment.Start < NewEnd) - Result.push_back({Segment.Start, NewEnd, Segment.Value}); - } - Segments = std::move(Result); - mergeAdjacent(); - return verify(); -} - -Expected<void> LiveRange::verify() const { - std::unordered_set<LiveValueNumberID> IDs; - for (std::size_t Index = 0; Index < Values.size(); ++Index) { - const LiveValueNumber &Value = Values[Index]; - if (!Value.ID.isValid() || Value.ID.value() != Index + 1U || !IDs.insert(Value.ID).second || - !Value.Definition.isValid()) { - return makeUnexpected(ErrorCode::VerificationError, - "live range contains an invalid value number"); - } - } - for (std::size_t Index = 0; Index < Segments.size(); ++Index) { - const LiveSegment &Segment = Segments[Index]; - if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || - value(Segment.Value) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, "live range contains an invalid segment"); - } - if (Index != 0 && Segments[Index - 1U].End > Segment.Start) { - return makeUnexpected(ErrorCode::VerificationError, - "live range segments are not ordered and disjoint"); - } - } - return {}; -} - -void LiveRange::mergeAdjacent() { - if (Segments.empty()) - return; - std::vector<LiveSegment> Result; - Result.reserve(Segments.size()); - Result.push_back(Segments.front()); - for (std::size_t Index = 1; Index < Segments.size(); ++Index) { - LiveSegment &Previous = Result.back(); - const LiveSegment &Current = Segments[Index]; - if (Current.Value == Previous.Value && Current.Start <= Previous.End) { - if (Previous.End < Current.End) - Previous.End = Current.End; - continue; - } - Result.push_back(Current); - } - Segments = std::move(Result); -} - -const LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) const noexcept { - const auto Position = Intervals.find(Reg); - return Position == Intervals.end() ? nullptr : &Position->second; -} - -LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) noexcept { - const auto Position = Intervals.find(Reg); - return Position == Intervals.end() ? nullptr : &Position->second; -} - -const LiveRange *LiveIntervalsAnalysis::Result::regUnitRange(RegisterUnitID Unit) const noexcept { - const auto Position = RegisterUnitRanges.find(Unit); - return Position == RegisterUnitRanges.end() ? nullptr : &Position->second; -} - -bool LiveIntervalsAnalysis::Result::interferes(Register Left, Register Right) const noexcept { - const LiveInterval *LeftInterval = interval(Left); - const LiveInterval *RightInterval = interval(Right); - return LeftInterval != nullptr && RightInterval != nullptr && - LeftInterval->overlaps(*RightInterval); -} - -bool LiveIntervalsAnalysis::Result::regMaskClobbers(const LiveInterval &Interval, - PhysicalRegister Candidate) const noexcept { - for (const RegMaskPosition &Position : RegMasks) { - if (Position.Mask && Position.Mask->clobbers(Candidate) && - Interval.MainRange.liveAt(Position.Position)) { - return true; - } - } - return false; -} - -Expected<void> LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, - std::span<const SlotIndex> Uses) { - LiveInterval *Value = interval(Reg); - if (Value == nullptr) - return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no live interval"); - auto Main = Value->MainRange.shrinkToUses(Uses); - if (!Main) - return std::unexpected(Main.error()); - for (LiveSubRange &SubRange : Value->SubRanges) { - auto Shrunk = SubRange.Range.shrinkToUses(Uses); - if (!Shrunk) - return std::unexpected(Shrunk.error()); - } - return {}; -} - -bool LiveIntervalsAnalysis::Result::invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept { - return !Preserved.preserves(MachineAnalysisManager::id<LiveIntervalsAnalysis>()); -} - -Expected<LiveIntervalsAnalysis::Result> -LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &Analyses) { - auto Indexes = Analyses.getResult<SlotIndexesAnalysis>(Function, Target); - if (!Indexes) - return std::unexpected(Indexes.error()); - auto Variables = Analyses.getResult<LiveVariablesAnalysis>(Function, Target); - if (!Variables) - return std::unexpected(Variables.error()); - - Result ResultValue; - ResultValue.Indexes = **Indexes; - for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { - auto RegValue = Register::makeVirtual(Index); - if (!RegValue || !Function.registerInfo().isKnownVirtualRegister(*RegValue)) - continue; - const Register Reg = *RegValue; - auto MainRange = buildLiveRange( - Function, ResultValue.Indexes, - [&Function, &Target, Reg](const MachineInstr &Instruction) { - return virtualRangeEvent(Instruction, Reg, std::nullopt, Function, Target); - }, - [&Variables, Reg](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->VirtualLiveOut.intersects(Reg); - }); - if (!MainRange) - return std::unexpected(MainRange.error()); - if (MainRange->empty()) - continue; - - LiveInterval Interval; - Interval.Reg = Reg; - Interval.MainRange = std::move(*MainRange); - auto Info = Function.registerInfo().virtualRegisterInfo(Reg); - if (!Info) - return std::unexpected(Info.error()); - // Preserve the target-provided hint order. MachineRegisterInfo already de-duplicates - // hints, and their order is the deterministic preference order consumed by allocators. - Interval.AllocationHints = Info->get().AllocationHints; - - std::uint64_t Weight = 1; - for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) { - if (Operand.parent() == nullptr || Operand.registerFlags().has(RegisterOperandFlag::Undef)) { - continue; - } - Weight = Weight > std::numeric_limits<std::uint64_t>::max() - 10U - ? std::numeric_limits<std::uint64_t>::max() - : Weight + 10U; - } - Interval.SpillWeight = Weight; - - auto LaneGroups = partitionVirtualRegisterLanes(Reg, Function, Target); - if (!LaneGroups) - return std::unexpected(LaneGroups.error()); - for (const LaneMask Lanes : *LaneGroups) { - auto SubRange = buildLiveRange( - Function, ResultValue.Indexes, - [&Function, &Target, Reg, Lanes](const MachineInstr &Instruction) { - return virtualRangeEvent(Instruction, Reg, Lanes, Function, Target); - }, - [&Variables, Reg, Lanes](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); - }); - if (!SubRange) - return std::unexpected(SubRange.error()); - if (!SubRange->empty()) - Interval.SubRanges.push_back({Lanes, std::move(*SubRange)}); - } - ResultValue.Intervals.emplace(Reg, std::move(Interval)); - } - - for (const RegisterUnitDesc &Unit : Target.registers().registerUnits()) { - auto Range = buildLiveRange( - Function, ResultValue.Indexes, - [&Target, Unit](const MachineInstr &Instruction) { - return unitRangeEvent(Instruction, Unit.ID, std::nullopt, Target); - }, - [&Variables, Unit](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit.ID); - }); - if (!Range) - return std::unexpected(Range.error()); - if (!Range->empty()) - ResultValue.RegisterUnitRanges.emplace(Unit.ID, std::move(*Range)); - } - - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "live intervals encountered a null register mask"); - ResultValue.RegMasks.push_back( - {ResultValue.Indexes.instructionIndex(*Instruction).earlyClobberSlot(), - Instruction->stableID(), MaskOperand->Mask}); - } - } - } - return ResultValue; -} - const MachinePassContract &RebuildMachineLivenessPass::contract() const noexcept { static const MachinePassContract Contract = [] { MachinePassContract Value{ diff --git a/backend/lib/CodeGen/MachineBranchOptimization.cpp b/backend/lib/CodeGen/MachineBranchOptimization.cpp index df25a4a..5880dbc 100644 --- a/backend/lib/CodeGen/MachineBranchOptimization.cpp +++ b/backend/lib/CodeGen/MachineBranchOptimization.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineBranchOptimization.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -11,7 +12,6 @@ #include "rcc/CodeGen/MachineFunctionRecords.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineBranchRelaxation.cpp b/backend/lib/CodeGen/MachineBranchRelaxation.cpp index 9ffb821..78640f1 100644 --- a/backend/lib/CodeGen/MachineBranchRelaxation.cpp +++ b/backend/lib/CodeGen/MachineBranchRelaxation.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/MachineBranchRelaxation.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineCSE.cpp b/backend/lib/CodeGen/MachineCSE.cpp index 47bba04..9d80b4e 100644 --- a/backend/lib/CodeGen/MachineCSE.cpp +++ b/backend/lib/CodeGen/MachineCSE.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineCSE.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" diff --git a/backend/lib/CodeGen/MachineCombiner.cpp b/backend/lib/CodeGen/MachineCombiner.cpp index 9a87b6f..df9c002 100644 --- a/backend/lib/CodeGen/MachineCombiner.cpp +++ b/backend/lib/CodeGen/MachineCombiner.cpp @@ -3,11 +3,11 @@ #include "rcc/CodeGen/MachineCombiner.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineCopyPropagation.cpp b/backend/lib/CodeGen/MachineCopyPropagation.cpp index 60992a5..581cb4f 100644 --- a/backend/lib/CodeGen/MachineCopyPropagation.cpp +++ b/backend/lib/CodeGen/MachineCopyPropagation.cpp @@ -4,11 +4,11 @@ #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineDCE.cpp b/backend/lib/CodeGen/MachineDCE.cpp index 9ba9a1b..4dd0e59 100644 --- a/backend/lib/CodeGen/MachineDCE.cpp +++ b/backend/lib/CodeGen/MachineDCE.cpp @@ -3,11 +3,11 @@ #include "rcc/CodeGen/MachineDCE.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineFallthrough.cpp b/backend/lib/CodeGen/MachineFallthrough.cpp index e912f0b..5c58e67 100644 --- a/backend/lib/CodeGen/MachineFallthrough.cpp +++ b/backend/lib/CodeGen/MachineFallthrough.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/MachineFallthrough.h" +#include "rcc/CodeGen/LivePhysRegs.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" -#include "rcc/CodeGen/MachineLiveness.h" -#include "rcc/CodeGen/MachineLivenessRepair.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineLICM.cpp b/backend/lib/CodeGen/MachineLICM.cpp index 52fffe7..758e13c 100644 --- a/backend/lib/CodeGen/MachineLICM.cpp +++ b/backend/lib/CodeGen/MachineLICM.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineLICM.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp index 6d24034..4f116f0 100644 --- a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp +++ b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp @@ -2,6 +2,7 @@ #include "rcc/CodeGen/MachineOptimizationPipeline.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBlockPlacement.h" #include "rcc/CodeGen/MachineBranchOptimization.h" @@ -13,7 +14,6 @@ #include "rcc/CodeGen/MachineFallthrough.h" #include "rcc/CodeGen/MachineFinalization.h" #include "rcc/CodeGen/MachineLICM.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemoryFolding.h" #include "rcc/CodeGen/MachinePseudoExpansion.h" #include "rcc/CodeGen/MachineScheduler.h" diff --git a/backend/lib/CodeGen/MachinePseudoExpansion.cpp b/backend/lib/CodeGen/MachinePseudoExpansion.cpp index b97d926..b5afe8e 100644 --- a/backend/lib/CodeGen/MachinePseudoExpansion.cpp +++ b/backend/lib/CodeGen/MachinePseudoExpansion.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachinePseudoExpansion.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp index c85489b..e589675 100644 --- a/backend/lib/CodeGen/MachineScheduler.cpp +++ b/backend/lib/CodeGen/MachineScheduler.cpp @@ -4,11 +4,11 @@ #include "MachineSchedulerInternal.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/RegisterPressure.h" #include "rcc/CodeGen/ScheduleDAG.h" #include "rcc/CodeGen/ScheduleHazardRecognizer.h" diff --git a/backend/lib/CodeGen/MachineSchedulerInternal.h b/backend/lib/CodeGen/MachineSchedulerInternal.h index 92f8eea..1815eaa 100644 --- a/backend/lib/CodeGen/MachineSchedulerInternal.h +++ b/backend/lib/CodeGen/MachineSchedulerInternal.h @@ -5,8 +5,8 @@ #ifndef RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H #define RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineScheduler.h" #include "rcc/CodeGen/ScheduleDAG.h" #include "rcc/Support/Error.h" diff --git a/backend/lib/CodeGen/MachineSink.cpp b/backend/lib/CodeGen/MachineSink.cpp index 873de67..21b17f8 100644 --- a/backend/lib/CodeGen/MachineSink.cpp +++ b/backend/lib/CodeGen/MachineSink.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineSink.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineTailDuplication.cpp b/backend/lib/CodeGen/MachineTailDuplication.cpp index 80c58c9..5abd473 100644 --- a/backend/lib/CodeGen/MachineTailDuplication.cpp +++ b/backend/lib/CodeGen/MachineTailDuplication.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineTailDuplication.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -10,7 +11,6 @@ #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineTailMerge.cpp b/backend/lib/CodeGen/MachineTailMerge.cpp index 07608cc..c4d6de9 100644 --- a/backend/lib/CodeGen/MachineTailMerge.cpp +++ b/backend/lib/CodeGen/MachineTailMerge.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineTailMerge.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -10,7 +11,6 @@ #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index 00be72f..8f1ebf4 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineVerifier.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionProperties.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineMetadata.h" #include "rcc/CodeGen/MachineOperand.h" diff --git a/backend/lib/CodeGen/PHIElimination.cpp b/backend/lib/CodeGen/PHIElimination.cpp index 5539708..75472f2 100644 --- a/backend/lib/CodeGen/PHIElimination.cpp +++ b/backend/lib/CodeGen/PHIElimination.cpp @@ -3,13 +3,13 @@ #include "rcc/CodeGen/PHIElimination.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineCFGUpdater.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp index 38fd582..f7d6181 100644 --- a/backend/lib/CodeGen/PostRAScheduler.cpp +++ b/backend/lib/CodeGen/PostRAScheduler.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/PostRAScheduler.h" #include "MachineSchedulerInternal.h" +#include "rcc/CodeGen/LivePhysRegs.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" -#include "rcc/CodeGen/MachineLivenessRepair.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/RegisterMask.h" #include "rcc/CodeGen/TargetDescription.h" @@ -53,222 +53,8 @@ namespace { return Error(Failure.code(), std::move(Prefix)); } -struct PhysicalUnitAccess final { - RegisterUnitID Unit; - LaneMask Lanes; -}; - -struct OperandFlagUpdate final { - MachineOperand *Operand = nullptr; - RegisterOperandFlags Flags; -}; - -[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - std::uint64_t Normalized = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - Normalized |= std::uint64_t{1} << UnitLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(Normalized); -} - -[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - std::optional<PhysicalRegister> Physical = - Reg == nullptr ? std::nullopt : Reg->physicalRegister(); - if (!Physical) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a virtual register"); - } - if (Operand.subReg().value() != 0) { - Physical = Target.registers().subRegister(*Physical, Operand.subReg()); - if (!Physical) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered an invalid subregister"); - } - } - const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(*Physical); - if (Description == nullptr || Description->Units.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a unitless register"); - } - std::vector<PhysicalUnitAccess> Result; - Result.reserve(Description->Units.size()); - for (const RegisterUnitLane &Unit : Description->Units) { - if (Unit.Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered empty register-unit lanes"); - } - Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes)}); - } - return Result; -} - -void addPhysicalRegister(RegisterUnitLaneSet &Live, const PhysicalRegisterDesc &Register) { - for (const RegisterUnitLane &Unit : Register.Units) - Live.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes)); -} - -[[nodiscard]] bool intersects(const RegisterUnitLaneSet &Live, - const std::vector<PhysicalUnitAccess> &Units) noexcept { - return std::ranges::any_of(Units, [&Live](const PhysicalUnitAccess &Unit) { - return Live.intersects(Unit.Unit, Unit.Lanes); - }); -} - -void addUnits(RegisterUnitLaneSet &Live, const std::vector<PhysicalUnitAccess> &Units) { - for (const PhysicalUnitAccess &Unit : Units) - Live.add(Unit.Unit, Unit.Lanes); -} - -void removeUnits(RegisterUnitLaneSet &Live, const std::vector<PhysicalUnitAccess> &Units) { - for (const PhysicalUnitAccess &Unit : Units) - Live.remove(Unit.Unit, Unit.Lanes); -} - -[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) noexcept { - const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector<OperandFlagUpdate> &Updates, - MachineOperand &Operand) { - const auto Position = std::ranges::find_if( - Updates, [&Operand](const OperandFlagUpdate &Update) { return Update.Operand == &Operand; }); - if (Position != Updates.end()) - return *Position; - Updates.push_back({&Operand, Operand.registerFlags()}); - return Updates.back(); -} - -[[nodiscard]] Expected<std::vector<OperandFlagUpdate>> -buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, - const MachineBlockLiveness &Boundary) { - RegisterUnitLaneSet Live = Boundary.PhysicalLiveOut; - std::vector<OperandFlagUpdate> Updates; - for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); - if (Mask == nullptr) - continue; - if (!Mask->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a null live-out mask"); - } - for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { - if (Mask->Mask->preserves(Register.Reg)) - addPhysicalRegister(Live, Register); - } - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister()) - continue; - OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); - Update.Flags.clear(RegisterOperandFlag::Dead); - if (!Operand->isDef()) - continue; - const Register *Reg = Operand->getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - auto Units = physicalOperandUnits(*Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - if (!intersects(Live, *Units)) - Update.Flags.set(RegisterOperandFlag::Dead); - } - - for (const MachineOperand &Operand : Instruction->operands()) { - if (Operand.isRegister() && Operand.isDef()) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - removeUnits(Live, *Units); - continue; - } - const auto *Mask = Operand.getIf<RegisterMaskOperand>(); - if (Mask == nullptr) - continue; - if (!Mask->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a null register mask"); - } - RegisterUnitLaneSet Clobbers; - for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { - if (Mask->Mask->clobbers(Register.Reg)) - addPhysicalRegister(Clobbers, Register); - } - Live.subtract(Clobbers); - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister()) - continue; - OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); - Update.Flags.clear(RegisterOperandFlag::Kill); - if (!Operand->isUse() || Operand->isDebugUse() || - Operand->registerFlags().has(RegisterOperandFlag::Undef)) { - continue; - } - const Register *Reg = Operand->getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - if (isReservedPhysicalRegister(*Reg, Block.function(), Target)) - continue; - auto Units = physicalOperandUnits(*Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - if (!intersects(Live, *Units)) - Update.Flags.set(RegisterOperandFlag::Kill); - addUnits(Live, *Units); - } - } - if (Live != Boundary.PhysicalLiveIn) { - return makeUnexpected(ErrorCode::InternalError, - "post-RA local liveness repair changed the block boundary"); - } - return Updates; -} - } // namespace -Expected<bool> repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks, - const TargetDescription &Target, - const LiveVariablesAnalysis::Result &Liveness) { - std::vector<OperandFlagUpdate> Updates; - for (MachineBasicBlock *Block : Blocks) { - const MachineBlockLiveness *Boundary = Liveness.block(*Block); - if (Boundary == nullptr) { - return makeUnexpected(ErrorCode::InternalError, - "post-RA scheduler lost a block liveness boundary"); - } - auto BlockUpdates = buildBlockLivenessRepairPlan(*Block, Target, *Boundary); - if (!BlockUpdates) - return std::unexpected(BlockUpdates.error()); - Updates.insert(Updates.end(), BlockUpdates->begin(), BlockUpdates->end()); - } - bool Changed = false; - for (const OperandFlagUpdate &Update : Updates) { - Changed |= Update.Operand->registerFlags() != Update.Flags; - auto Applied = Update.Operand->setRegisterFlags(Update.Flags); - if (!Applied) - return std::unexpected(Applied.error()); - } - return Changed; -} - const MachinePassContract &PostRASchedulerPass::contract() const noexcept { return postRASchedulerContract(); } diff --git a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp index 36315f7..47b74f6 100644 --- a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp +++ b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp @@ -7,7 +7,7 @@ #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineVerifier.h" diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp index 5d065dd..0fac6aa 100644 --- a/backend/lib/CodeGen/RegAllocBase.cpp +++ b/backend/lib/CodeGen/RegAllocBase.cpp @@ -2,7 +2,7 @@ #include "RegAllocBase.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/Spiller.h" #include <algorithm> diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h index a1682b2..318a82d 100644 --- a/backend/lib/CodeGen/RegAllocBase.h +++ b/backend/lib/CodeGen/RegAllocBase.h @@ -6,7 +6,7 @@ #define RCC_LIB_CODEGEN_REGALLOCBASE_H #include "RegAllocInternal.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/RegAllocCommon.h" #include "rcc/CodeGen/TargetRegisterAllocationInfo.h" #include "rcc/CodeGen/VirtRegMap.h" diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp index 7f88f25..9d14d15 100644 --- a/backend/lib/CodeGen/RegAllocBasic.cpp +++ b/backend/lib/CodeGen/RegAllocBasic.cpp @@ -3,8 +3,9 @@ #include "RegAllocBasic.h" #include "RegAllocBase.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" #include <algorithm> #include <memory> diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp index 897f217..1399f10 100644 --- a/backend/lib/CodeGen/RegAllocFast.cpp +++ b/backend/lib/CodeGen/RegAllocFast.cpp @@ -4,11 +4,11 @@ #include "RegAllocInternal.h" #include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/Spiller.h" diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h index 5cd98e8..0becb92 100644 --- a/backend/lib/CodeGen/RegAllocInternal.h +++ b/backend/lib/CodeGen/RegAllocInternal.h @@ -6,11 +6,11 @@ #define RCC_LIB_CODEGEN_REGALLOCINTERNAL_H #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/MachineVerifier.h" diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp index f1da2c1..3b0e684 100644 --- a/backend/lib/CodeGen/RegAllocPBQP.cpp +++ b/backend/lib/CodeGen/RegAllocPBQP.cpp @@ -4,11 +4,12 @@ #include "RegAllocBase.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/PBQP/Solver.h" diff --git a/backend/lib/CodeGen/RegisterPressure.cpp b/backend/lib/CodeGen/RegisterPressure.cpp index cbd8d8e..201e85b 100644 --- a/backend/lib/CodeGen/RegisterPressure.cpp +++ b/backend/lib/CodeGen/RegisterPressure.cpp @@ -2,10 +2,10 @@ #include "rcc/CodeGen/RegisterPressure.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/SlotIndexes.cpp b/backend/lib/CodeGen/SlotIndexes.cpp new file mode 100644 index 0000000..57e35b5 --- /dev/null +++ b/backend/lib/CodeGen/SlotIndexes.cpp @@ -0,0 +1,159 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/SlotIndexes.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" + +#include <cstdint> +#include <limits> + +namespace rcc { + +namespace { +constexpr std::uint64_t SlotSpacing = 16; +constexpr std::uint64_t SlotAlignmentMask = 3; +} // namespace + +SlotIndex +SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept { + const auto Position = InstructionSlots.find(Instruction.stableID()); + return Position == InstructionSlots.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockStarts.find(&Block); + return Position == BlockStarts.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockEnds.find(&Block); + return Position == BlockEnds.end() ? SlotIndex{} : Position->second; +} + +const MachineInstr * +SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + const auto Position = SlotToInstruction.find(Index.baseIndex().value()); + return Position == SlotToInstruction.end() ? nullptr : Position->second; +} + +const MachineBasicBlock * +SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + for (const MachineBasicBlock *Block : BlocksByStart) { + const SlotIndex Start = blockStart(*Block); + const SlotIndex End = blockEnd(*Block); + if (!(Index < Start) && Index < End) + return Block; + } + return nullptr; +} + +Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) { + const MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "SlotIndex insertion requires a linked indexed instruction"); + } + if (InstructionSlots.contains(Instruction.stableID())) { + return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex"); + } + + const MachineInstr *Previous = Instruction.previous(); + const MachineInstr *Next = Instruction.next(); + const SlotIndex LowerIndex = + Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous); + const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next); + if (!LowerIndex.isValid() || !UpperIndex.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "adjacent instructions are missing SlotIndexes"); + } + const std::uint64_t Lower = LowerIndex.baseIndex().value(); + const std::uint64_t Upper = UpperIndex.baseIndex().value(); + if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask; + if (Candidate <= Lower) + Candidate = Lower + SlotAlignmentMask + 1U; + if (Candidate >= Upper) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot(); + InstructionSlots.emplace(Instruction.stableID(), Index); + SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction); + return {}; +} + +Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) { + const auto Position = InstructionSlots.find(Instruction.stableID()); + if (Position == InstructionSlots.end()) + return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex"); + SlotToInstruction.erase(Position->second.baseIndex().value()); + InstructionSlots.erase(Position); + return {}; +} + +Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { + Result NewResult; + std::uint64_t Position = SlotSpacing; + auto Advance = [&Position]() -> Expected<void> { + if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) { + return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted"); + } + Position += SlotSpacing; + return {}; + }; + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block); + NewResult.BlockStarts.emplace(Block, Start); + NewResult.BlocksByStart.push_back(Block); + auto Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot(); + if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second || + !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) { + return makeUnexpected(ErrorCode::VerificationError, + "duplicate instruction identity during SlotIndex construction"); + } + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + NewResult.BlockEnds.emplace(Block, + SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block)); + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + *this = std::move(NewResult); + return {}; +} + +bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>()); +} + +Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function, + const TargetDescription &, + MachineAnalysisManager &) { + Result ResultValue; + auto Numbered = ResultValue.renumber(Function); + if (!Numbered) + return std::unexpected(Numbered.error()); + return ResultValue; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp index 1959b90..be4db82 100644 --- a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp +++ b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/TwoAddressInstructionPass.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/VirtRegMap.cpp b/backend/lib/CodeGen/VirtRegMap.cpp index 624a931..a55a486 100644 --- a/backend/lib/CodeGen/VirtRegMap.cpp +++ b/backend/lib/CodeGen/VirtRegMap.cpp @@ -3,11 +3,12 @@ #include "rcc/CodeGen/VirtRegMap.h" #include "RegAllocInternal.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/unittests/CodeGen/CMakeLists.txt b/backend/unittests/CodeGen/CMakeLists.txt index 7e79344..0715def 100644 --- a/backend/unittests/CodeGen/CMakeLists.txt +++ b/backend/unittests/CodeGen/CMakeLists.txt @@ -17,7 +17,13 @@ set( MachineIRCoreTest.cpp MachineAnalysesTest.cpp MachineJumpTableInfoTest.cpp - MachineLivenessTest.cpp + SlotIndexesTest.cpp + LiveVariablesTest.cpp + LiveIntervalTest.cpp + LiveIntervalsTest.cpp + LivePhysRegsTest.cpp + LiveRegUnitsTest.cpp + LiveTestSupport.h MachineMetadataTest.cpp MachineOperandTest.cpp MachineOptimizationTest.cpp @@ -292,17 +298,26 @@ add_test( COMMAND RCCBackendCodeGenMachineJumpTableInfoTests ) -add_executable(RCCBackendCodeGenMachineLivenessTests MachineLivenessTest.cpp) -rcc_backend_configure_target(RCCBackendCodeGenMachineLivenessTests) -target_link_libraries( - RCCBackendCodeGenMachineLivenessTests - PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget RCCBackend::RISCV -) - -add_test( - NAME RCCBackend.CodeGen.MachineLiveness - COMMAND RCCBackendCodeGenMachineLivenessTests -) +foreach( + Component + SlotIndexes + LiveVariables + LiveInterval + LiveIntervals + LivePhysRegs + LiveRegUnits +) + add_executable(RCCBackendCodeGen${Component}Tests ${Component}Test.cpp) + rcc_backend_configure_target(RCCBackendCodeGen${Component}Tests) + target_link_libraries( + RCCBackendCodeGen${Component}Tests + PRIVATE RCCBackend::CodeGen RCCBackend::TestTarget RCCBackend::RISCV + ) + add_test( + NAME RCCBackend.CodeGen.${Component} + COMMAND RCCBackendCodeGen${Component}Tests + ) +endforeach() add_executable(RCCBackendCodeGenMachineMetadataTests MachineMetadataTest.cpp) rcc_backend_configure_target(RCCBackendCodeGenMachineMetadataTests) @@ -470,7 +485,13 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalysesTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfoTest.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariablesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervalTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervalsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnitsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveTestSupport.h" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp" @@ -513,7 +534,13 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineIRCoreTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineAnalysesTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfoTest.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLivenessTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariablesTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervalTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervalsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnitsTest.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveTestSupport.h" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadataTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOperandTest.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineOptimizationTest.cpp" diff --git a/backend/unittests/CodeGen/LiveIntervalTest.cpp b/backend/unittests/CodeGen/LiveIntervalTest.cpp new file mode 100644 index 0000000..7e48b05 --- /dev/null +++ b/backend/unittests/CodeGen/LiveIntervalTest.cpp @@ -0,0 +1,116 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveInterval.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveIntervals.h" +#include "rcc/CodeGen/LiveVariables.h" + +namespace { + +using namespace rcc::test::liveness; + +void testLiveRange(TestContext &Context) { + const rcc::SlotIndex S16 = rcc::SlotIndex::fromValue(16).registerSlot(); + const rcc::SlotIndex S24 = rcc::SlotIndex::fromValue(24).registerSlot(); + const rcc::SlotIndex S32 = rcc::SlotIndex::fromValue(32).registerSlot(); + const rcc::SlotIndex S40 = rcc::SlotIndex::fromValue(40).registerSlot(); + const rcc::SlotIndex S48 = rcc::SlotIndex::fromValue(48).registerSlot(); + + rcc::LiveRange Range; + auto First = Range.createValue(S16); + Context.expect(First.has_value(), "live value creation must succeed"); + if (!First) + return; + Context.expect(Range.addSegment({S16, S32, *First}).has_value() && + Range.addSegment({S32, S48, *First}).has_value() && + Range.segments().size() == 1, + "adjacent same-value live segments must merge"); + auto Second = Range.createValue(S40, rcc::LiveValueState::Redefined); + Context.expect(Second.has_value() && !Range.addSegment({S24, S40, *Second}), + "overlapping different live values must be rejected"); + Context.expect(Range.valueAt(S24) != nullptr && Range.liveAt(S40) && + Range.remove(S24, S40).has_value() && Range.segments().size() == 2 && + Range.verify().has_value(), + "live-range lookup and removal must preserve ordered half-open segments"); + + rcc::LiveRange Shrunk; + auto Value = Shrunk.createValue(S16); + if (!Value) { + Context.expect(false, "shrink test value creation must succeed"); + return; + } + const std::array Uses{S32}; + Context.expect(Shrunk.addSegment({S16, S48.deadSlot(), *Value}).has_value() && + Shrunk.shrinkToUses(Uses).has_value() && Shrunk.segments().size() == 1 && + Shrunk.segments().front().End == S32.deadSlot(), + "shrinkToUses must retain exactly through the final use dead slot"); +} + +void testLaneSubrangesAndEarlyClobber(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("lane-subranges", 3, 1); + if (!Fixture) { + Context.expect(false, "lane-subrange fixture creation must succeed"); + return; + } + auto Reg = createVReg(*Fixture->Function); + auto Early = createVReg(*Fixture->Function); + if (!Reg || !Early) { + Context.expect(false, "lane-subrange registers must be created"); + return; + } + auto LowDef = + buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32); + auto LowUse = + buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32); + auto HighDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, + rcc::test::TestSubReg::High32); + auto HighUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, + rcc::test::TestSubReg::High32); + auto EarlyDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Early, {}, true); + auto EarlyUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Early); + if (!LowDef || !LowUse || !HighDef || !HighUse || !EarlyDef || !EarlyUse) { + Context.expect(false, "lane-subrange instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Intervals = Registered + ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(Registered.error())}; + if (!Intervals) { + Context.expect(false, "lane-subrange intervals must materialize"); + return; + } + const rcc::LiveInterval *Interval = (*Intervals)->interval(*Reg); + const rcc::LiveInterval *EarlyInterval = (*Intervals)->interval(*Early); + const bool HasLow = Interval != nullptr && + std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) { + return Range.Lanes == rcc::LaneMask::fromRaw(0x3); + }); + const bool HasHigh = Interval != nullptr && + std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) { + return Range.Lanes == rcc::LaneMask::fromRaw(0xC); + }); + Context.expect(Interval != nullptr && Interval->SubRanges.size() == 2 && HasLow && HasHigh, + "partial virtual-register accesses must form disjoint lane subranges"); + Context.expect(EarlyInterval != nullptr && !EarlyInterval->MainRange.values().empty() && + EarlyInterval->MainRange.values().front().Definition.kind() == + rcc::SlotIndexKind::EarlyClobber, + "early-clobber definitions must use the early-clobber slot"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testLiveRange(Context); + testLaneSubrangesAndEarlyClobber(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/LiveIntervalsTest.cpp b/backend/unittests/CodeGen/LiveIntervalsTest.cpp new file mode 100644 index 0000000..5c127a2 --- /dev/null +++ b/backend/unittests/CodeGen/LiveIntervalsTest.cpp @@ -0,0 +1,265 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveIntervals.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +namespace { + +using namespace rcc::test::liveness; + +void testCFGAndValueNumbers(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("cfg-liveness", 2, 8); + if (!Fixture) { + Context.expect(false, "CFG liveness fixture creation must succeed"); + return; + } + auto &Function = *Fixture->Function; + auto &Entry = *Fixture->Blocks[0]; + auto &Left = *Fixture->Blocks[1]; + auto &Right = *Fixture->Blocks[2]; + auto &Join = *Fixture->Blocks[3]; + auto &Header = *Fixture->Blocks[4]; + auto &Body = *Fixture->Blocks[5]; + auto &Exit = *Fixture->Blocks[6]; + auto &Dead = *Fixture->Blocks[7]; + auto Half = rcc::BranchProbability::fromFraction(1, 2); + auto Updater = Function.cfgUpdater(); + const bool CFGValid = Half && Updater.addSuccessor(Entry, Left, *Half) && + Updater.addSuccessor(Entry, Right, *Half) && + Updater.addSuccessor(Left, Join, rcc::BranchProbability::one()) && + Updater.addSuccessor(Right, Join, rcc::BranchProbability::one()) && + Updater.addSuccessor(Join, Header, rcc::BranchProbability::one()) && + Updater.addSuccessor(Header, Body, *Half) && + Updater.addSuccessor(Header, Exit, *Half) && + Updater.addSuccessor(Body, Header, rcc::BranchProbability::one()); + Context.expect(CFGValid, "diamond and loop CFG construction must succeed"); + if (!CFGValid) + return; + + auto Across = createVReg(Function); + auto Merged = createVReg(Function); + auto Unreachable = createVReg(Function); + auto Redefined = createVReg(Function); + if (!Across || !Merged || !Unreachable || !Redefined) { + Context.expect(false, "CFG liveness virtual registers must be created"); + return; + } + auto AcrossDef = buildDef(Function, Target, Entry, *Across); + auto LeftDef = buildDef(Function, Target, Left, *Merged); + auto RightDef = buildDef(Function, Target, Right, *Merged); + auto MergedUse = buildUse(Function, Target, Join, *Merged); + auto LoopUse = buildUse(Function, Target, Body, *Across); + auto DeadUse = buildUse(Function, Target, Dead, *Unreachable); + auto FirstRedef = buildDef(Function, Target, Exit, *Redefined); + auto SecondRedef = buildDef(Function, Target, Exit, *Redefined); + if (!AcrossDef || !LeftDef || !RightDef || !MergedUse || !LoopUse || !DeadUse || !FirstRedef || + !SecondRedef) { + Context.expect(false, "CFG liveness instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Variables = Registered ? Analyses.getResult<rcc::LiveVariablesAnalysis>(Function, Target) + : rcc::Expected<rcc::LiveVariablesAnalysis::Result *>{ + std::unexpected(Registered.error())}; + auto Intervals = Registered ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(Registered.error())}; + if (!Variables || !Intervals) { + Context.expect(false, "CFG liveness analyses must materialize"); + return; + } + Context.expect((*Variables)->isLiveOut(Entry, *Across) && (*Variables)->isLiveIn(Left, *Across) && + (*Variables)->isLiveIn(Right, *Across) && + (*Variables)->isLiveIn(Header, *Across) && + (*Variables)->isLiveOut(Body, *Across), + "CFG fixed point must propagate a value through a diamond and loop backedge"); + Context.expect( + (*Variables)->isLiveOut(Left, *Merged) && (*Variables)->isLiveOut(Right, *Merged) && + (*Variables)->isLiveIn(Join, *Merged) && (*Variables)->isLiveIn(Dead, *Unreachable), + "liveness must merge predecessor definitions and retain unreachable uses"); + + const rcc::LiveInterval *MergedInterval = (*Intervals)->interval(*Merged); + const rcc::LiveInterval *AcrossInterval = (*Intervals)->interval(*Across); + const rcc::LiveInterval *RedefinedInterval = (*Intervals)->interval(*Redefined); + const bool HasPhi = MergedInterval != nullptr && + std::ranges::any_of(MergedInterval->MainRange.values(), + [](const rcc::LiveValueNumber &Value) { + return Value.State == rcc::LiveValueState::Phi; + }); + const bool HasRedefined = + RedefinedInterval != nullptr && + std::ranges::any_of(RedefinedInterval->MainRange.values(), + [](const rcc::LiveValueNumber &Value) { + return Value.State == rcc::LiveValueState::Redefined; + }); + Context.expect(MergedInterval != nullptr && MergedInterval->MainRange.values().size() >= 3 && + HasPhi && HasRedefined, + "non-SSA intervals must retain multiple definitions, PHI, and redefined values"); + Context.expect(AcrossInterval != nullptr && (*Intervals)->interferes(*Across, *Merged), + "live intervals must expose CFG-derived interference"); +} + +void testPhysicalUnitsAndRegMasks(TestContext &Context, const rcc::TargetDescription &Target) { + const rcc::RegisterUnitID MultiLaneUnit = rcc::RegisterUnitID::fromValue(9); + rcc::LiveRegUnits PartialLanes; + PartialLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x3)); + rcc::LiveRegUnits RemovedLanes; + RemovedLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)); + PartialLanes.subtract(RemovedLanes); + Context.expect(PartialLanes.lanes(MultiLaneUnit) == rcc::LaneMask::fromRaw(0x1) && + PartialLanes.contains(MultiLaneUnit, rcc::LaneMask::fromRaw(0x1)) && + !PartialLanes.intersects(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)), + "RegisterUnit lane sets must preserve partial union and subtraction"); + + auto AliasFixture = createFunction("physical-alias", 4, 1); + if (!AliasFixture) { + Context.expect(false, "physical-alias fixture creation must succeed"); + return; + } + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + const rcc::Register G0High = + rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0High32)); + auto G0Def = buildDef(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0); + auto G0HighUse = buildUse(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0High); + if (!G0Def || !G0HighUse) { + Context.expect(false, "physical-alias instructions must be built"); + return; + } + rcc::MachineAnalysisManager AliasAnalyses; + auto AliasRegistered = rcc::registerStage11MachineAnalyses(AliasAnalyses); + auto AliasIntervals = + AliasRegistered + ? AliasAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*AliasFixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(AliasRegistered.error())}; + const rcc::RegisterUnitID HighUnit = rcc::RegisterUnitID::fromValue(3); + Context.expect(AliasIntervals && (*AliasIntervals)->regUnitRange(HighUnit) != nullptr && + (*AliasIntervals)->regUnitRange(HighUnit)->segments().size() == 1, + "shared RegisterUnits must connect super-register defs to subregister uses"); + + auto MaskFixture = createFunction("regmask", 5, 1); + if (!MaskFixture) { + Context.expect(false, "RegMask fixture creation must succeed"); + return; + } + auto Across = createVReg(*MaskFixture->Function); + auto Output = createVReg(*MaskFixture->Function); + if (!Across || !Output) { + Context.expect(false, "RegMask virtual registers must be created"); + return; + } + const auto Mask = rcc::test::createTestCallPreservedMask(); + auto AcrossDef = buildDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); + auto FirstMask = buildMask(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], Mask); + auto AcrossUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); + auto OutputDef = + buildMaskedDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output, Mask); + auto OutputUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output); + if (!AcrossDef || !FirstMask || !AcrossUse || !OutputDef || !OutputUse) { + Context.expect(false, "RegMask instructions must be built"); + return; + } + rcc::MachineAnalysisManager MaskAnalyses; + auto MaskRegistered = rcc::registerStage11MachineAnalyses(MaskAnalyses); + auto MaskIntervals = + MaskRegistered + ? MaskAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*MaskFixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(MaskRegistered.error())}; + if (!MaskIntervals) { + Context.expect(false, "RegMask intervals must materialize"); + return; + } + const rcc::PhysicalRegister Candidate = physical(rcc::test::TestRegister::G0); + const rcc::LiveInterval *AcrossInterval = (*MaskIntervals)->interval(*Across); + const rcc::LiveInterval *OutputInterval = (*MaskIntervals)->interval(*Output); + Context.expect((*MaskIntervals)->regMaskPositions().size() == 2 && + std::ranges::all_of((*MaskIntervals)->regMaskPositions(), + [](const rcc::RegMaskPosition &Position) { + return Position.Position.kind() == + rcc::SlotIndexKind::EarlyClobber; + }), + "RegMask interference positions must use early-clobber slots"); + Context.expect(AcrossInterval != nullptr && OutputInterval != nullptr && + (*MaskIntervals)->regMaskClobbers(*AcrossInterval, Candidate) && + !(*MaskIntervals)->regMaskClobbers(*OutputInterval, Candidate), + "RegMask queries must reject live-through values but accept same-call outputs"); + Context.expect((*MaskIntervals)->regUnitRange(rcc::RegisterUnitID::fromValue(1)) == nullptr, + "unused RegMask clobbers must not expand into physical live ranges"); +} + +void testRISCVLiveness(TestContext &Context) { + auto Target = rcc::riscv::createTargetDescription(); + auto Fixture = createFunction("riscv-liveness", 8, 1); + if (!Target || !Fixture) { + Context.expect(false, "RV64GC liveness fixture creation must succeed"); + return; + } + auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5); + auto X6 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X6); + auto X7 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X7); + if (!X5 || !X6 || !X7) { + Context.expect(false, "RV64GC physical registers must resolve"); + return; + } + auto BuildADDI = [&](rcc::PhysicalRegister Destination, rcc::PhysicalRegister Source, + std::int64_t Immediate) -> rcc::Expected<rcc::MachineInstr *> { + rcc::MachineIRBuilder Builder(*Fixture->Function, *Target); + auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr( + rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(rcc::Register::fromPhysical(Destination)); + if (!Def) + return std::unexpected(Def.error()); + auto Use = Pending->addUse(rcc::Register::fromPhysical(Source)); + if (!Use) + return std::unexpected(Use.error()); + auto Imm = Pending->addImmediate(Immediate); + if (!Imm) + return std::unexpected(Imm.error()); + return Pending->build(); + }; + auto First = BuildADDI(*X6, *X5, 1); + auto Second = BuildADDI(*X7, *X6, 2); + if (!First || !Second) { + Context.expect(false, "RV64GC ADDI instructions must be built"); + return; + } + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Intervals = Registered + ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, *Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(Registered.error())}; + const auto Unit = + rcc::RegisterUnitID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterUnit::U_X6)); + Context.expect(Intervals && (*Intervals)->regUnitRange(Unit) != nullptr && + (*Intervals)->regUnitRange(Unit)->segments().size() == 1, + "production RV64GC register units must participate in LiveIntervals"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testCFGAndValueNumbers(Context, *Target); + testPhysicalUnitsAndRegMasks(Context, *Target); + testRISCVLiveness(Context); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/LivePhysRegsTest.cpp b/backend/unittests/CodeGen/LivePhysRegsTest.cpp new file mode 100644 index 0000000..ee579be --- /dev/null +++ b/backend/unittests/CodeGen/LivePhysRegsTest.cpp @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LivePhysRegs.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveVariables.h" + +namespace { + +using namespace rcc::test::liveness; + +void testPostRALivenessRepair(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("post-ra-repair", 12, 1); + if (!Fixture) { + Context.expect(false, "post-RA repair fixture creation must succeed"); + return; + } + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + auto Def = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], G0); + auto FirstUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], G0); + auto LastUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], G0); + if (!Def || !FirstUse || !LastUse) { + Context.expect(false, "post-RA repair instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Liveness = Registered + ? Analyses.getResult<rcc::LiveVariablesAnalysis>(*Fixture->Function, Target) + : rcc::Expected<rcc::LiveVariablesAnalysis::Result *>{ + std::unexpected(Registered.error())}; + if (!Liveness) { + Context.expect(false, "post-RA repair liveness must materialize"); + return; + } + const std::array Blocks{Fixture->Blocks[0]}; + auto Repaired = rcc::repairPostRAMachineBlockLiveness(Blocks, Target, **Liveness); + Context.expect(Repaired && *Repaired, "post-RA repair must update stale kill/dead flags"); + Context.expect(!hasFlag(**Def, 0, rcc::RegisterOperandFlag::Dead) && + !hasFlag(**FirstUse, 0, rcc::RegisterOperandFlag::Kill) && + hasFlag(**LastUse, 0, rcc::RegisterOperandFlag::Kill), + "post-RA repair must derive precise physical kill/dead flags"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testPostRALivenessRepair(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/LiveRegUnitsTest.cpp b/backend/unittests/CodeGen/LiveRegUnitsTest.cpp new file mode 100644 index 0000000..7f224ac --- /dev/null +++ b/backend/unittests/CodeGen/LiveRegUnitsTest.cpp @@ -0,0 +1,37 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegUnits.h" + +#include "LiveTestSupport.h" + +namespace { + +using namespace rcc::test::liveness; + +void testLiveRegUnits(TestContext &Context) { + const rcc::RegisterUnitID Unit = rcc::RegisterUnitID::fromValue(9); + rcc::LiveRegUnits Present; + rcc::LiveRegUnits Removed; + Present.add(Unit, rcc::LaneMask::fromRaw(0x3)); + Removed.add(Unit, rcc::LaneMask::fromRaw(0x2)); + Present.subtract(Removed); + Context.expect(Present.lanes(Unit) == rcc::LaneMask::fromRaw(0x1) && + Present.contains(Unit, rcc::LaneMask::fromRaw(0x1)) && + !Present.intersects(Unit, rcc::LaneMask::fromRaw(0x2)), + "LiveRegUnits must preserve partial union and subtraction"); + Present.unite(Removed); + Context.expect(Present.contains(Unit, rcc::LaneMask::fromRaw(0x3)), + "LiveRegUnits union must restore all selected lanes"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testLiveRegUnits(Context); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/LiveTestSupport.h b/backend/unittests/CodeGen/LiveTestSupport.h new file mode 100644 index 0000000..ebd8811 --- /dev/null +++ b/backend/unittests/CodeGen/LiveTestSupport.h @@ -0,0 +1,264 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_BACKEND_LIVE_TEST_SUPPORT_H +#define RCC_BACKEND_LIVE_TEST_SUPPORT_H + +#include "Target/TestTarget.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineCFGUpdater.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <array> +#include <cstddef> +#include <cstdint> +#include <iostream> +#include <memory> +#include <span> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +namespace rcc::test::liveness { + +constexpr std::uint32_t DefOpcode = 2048; +constexpr std::uint32_t UseOpcode = 2049; +constexpr std::uint32_t EarlyDefOpcode = 2050; +constexpr std::uint32_t MaskOpcode = 2051; +constexpr std::uint32_t MaskedDefOpcode = 2052; +constexpr std::uint32_t LiveOutMaskOpcode = 2053; + +class TestContext final { +public: + void expect(bool Condition, std::string_view Message) { + if (Condition) + return; + std::cerr << Message << '\n'; + ++Failures; + } + + [[nodiscard]] int result() const noexcept { + return Failures == 0 ? 0 : 1; + } + +private: + int Failures = 0; +}; + +[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) { + return rcc::Opcode::fromValue(Value); +} + +[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role, + bool EarlyClobber = false) { + rcc::OperandDescriptor Result; + Result.Kinds = {rcc::MachineOperand::Kind::Register}; + Result.RegisterRole = Role; + Result.EarlyClobber = EarlyClobber; + Result.AllowSubReg = true; + return Result; +} + +[[nodiscard]] rcc::OperandDescriptor plainOperand(rcc::MachineOperand::Kind Kind) { + rcc::OperandDescriptor Result; + Result.Kinds = {Kind}; + return Result; +} + +[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) { + rcc::InstructionDescriptor Result; + Result.InstructionOpcode = testOpcode(Value); + Result.Name = std::move(Name); + Result.Flags = {rcc::InstructionFlag::ProducesCode}; + return Result; +} + +[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() { + std::vector<rcc::InstructionDescriptor> Descriptors; + std::vector<rcc::ImmediatePredicate> Predicates; + auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates); + if (!Generic) + return std::unexpected(Generic.error()); + + auto Def = instruction(DefOpcode, "LIVENESS_DEF"); + Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)}; + Def.NumExplicitDefs = 1; + Descriptors.push_back(std::move(Def)); + + auto Use = instruction(UseOpcode, "LIVENESS_USE"); + Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)}; + Descriptors.push_back(std::move(Use)); + + auto EarlyDef = instruction(EarlyDefOpcode, "LIVENESS_EARLY_DEF"); + EarlyDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def, true)}; + EarlyDef.NumExplicitDefs = 1; + Descriptors.push_back(std::move(EarlyDef)); + + auto Mask = instruction(MaskOpcode, "LIVENESS_MASK"); + Mask.Operands = {plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; + Mask.Flags.set(rcc::InstructionFlag::Call); + Mask.Flags.set(rcc::InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(Mask)); + + auto MaskedDef = instruction(MaskedDefOpcode, "LIVENESS_MASKED_DEF"); + MaskedDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def), + plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; + MaskedDef.NumExplicitDefs = 1; + MaskedDef.Flags.set(rcc::InstructionFlag::Call); + MaskedDef.Flags.set(rcc::InstructionFlag::HasSideEffects); + Descriptors.push_back(std::move(MaskedDef)); + + auto LiveOutMask = instruction(LiveOutMaskOpcode, "LIVENESS_LIVEOUT_MASK"); + LiveOutMask.Operands = {plainOperand(rcc::MachineOperand::Kind::LiveOutRegisterMask)}; + Descriptors.push_back(std::move(LiveOutMask)); + + auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates)); + if (!Instructions) + return std::unexpected(Instructions.error()); + return rcc::test::createTestTargetDescription(std::move(*Instructions)); +} + +struct FunctionFixture final { + std::unique_ptr<rcc::MachineFunction> Function; + std::vector<rcc::MachineBasicBlock *> Blocks; +}; + +[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name, std::uint64_t ID, + std::size_t BlockCount) { + auto Function = + rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID)); + if (!Function) + return std::unexpected(Function.error()); + FunctionFixture Result{std::move(*Function), {}}; + Result.Blocks.reserve(BlockCount); + for (std::size_t Index = 0; Index < BlockCount; ++Index) { + auto Block = Result.Function->createBasicBlock(); + if (!Block) + return std::unexpected(Block.error()); + auto Appended = Result.Function->appendBlock(**Block); + if (!Appended) + return std::unexpected(Appended.error()); + Result.Blocks.push_back(*Block); + } + return Result; +} + +[[nodiscard]] rcc::Expected<rcc::Register> createVReg(rcc::MachineFunction &Function) { + auto Type = rcc::LLT::makeInteger(64); + if (!Type) + return std::unexpected(Type.error()); + auto Reg = Function.registerInfo().createVirtualRegister(*Type); + if (!Reg) + return std::unexpected(Reg.error()); + auto Bank = Function.registerInfo().setRegisterBank(*Reg, rcc::test::TestRegisterBank::GPR); + if (!Bank) + return std::unexpected(Bank.error()); + auto Class = Function.registerInfo().setRegisterClass(*Reg, rcc::test::TestRegisterClass::GPR64); + if (!Class) + return std::unexpected(Class.error()); + return *Reg; +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {}, + bool EarlyClobber = false) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(EarlyClobber ? EarlyDefOpcode : DefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + rcc::RegisterOperandFlags Flags; + if (EarlyClobber) + Flags.set(rcc::RegisterOperandFlag::EarlyClobber); + auto Added = Pending->addDef(Reg, Flags, SubReg); + if (!Added) + return std::unexpected(Added.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildUse(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {}, + rcc::MachineInstr *Before = nullptr) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = + Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(UseOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Added = Pending->addUse(Reg, {}, SubReg); + if (!Added) + return std::unexpected(Added.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildMask(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, std::shared_ptr<const rcc::RegisterMask> Mask) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(MaskOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Added = Pending->addRegisterMask(std::move(Mask)); + if (!Added) + return std::unexpected(Added.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::Expected<rcc::MachineInstr *> +buildMaskedDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, + rcc::MachineBasicBlock &Block, rcc::Register Reg, + std::shared_ptr<const rcc::RegisterMask> Mask) { + rcc::MachineIRBuilder Builder(Function, Target); + auto Point = Builder.setInsertPoint(Block); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(testOpcode(MaskedDefOpcode)); + if (!Pending) + return std::unexpected(Pending.error()); + auto Def = Pending->addDef(Reg); + if (!Def) + return std::unexpected(Def.error()); + auto MaskResult = Pending->addRegisterMask(std::move(Mask)); + if (!MaskResult) + return std::unexpected(MaskResult.error()); + return Pending->build(); +} + +[[nodiscard]] rcc::PhysicalRegister physical(std::uint32_t Number) { + return *rcc::PhysicalRegister::create(Number); +} + +[[nodiscard]] bool hasFlag(const rcc::MachineInstr &Instruction, std::size_t OperandIndex, + rcc::RegisterOperandFlag Flag) { + const rcc::MachineOperand *Operand = Instruction.operandAt(OperandIndex); + return Operand != nullptr && Operand->registerFlags().has(Flag); +} + +inline void setRebuildProperties(rcc::MachineFunction &Function) { + Function.properties().set(rcc::MachineFunctionProperty::Legalized); + Function.properties().set(rcc::MachineFunctionProperty::RegBankSelected); + Function.properties().set(rcc::MachineFunctionProperty::Selected); + Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); + Function.properties().set(rcc::MachineFunctionProperty::TiedOpsRewritten); +} + +} // namespace rcc::test::liveness + +#endif // RCC_BACKEND_LIVE_TEST_SUPPORT_H diff --git a/backend/unittests/CodeGen/LiveVariablesTest.cpp b/backend/unittests/CodeGen/LiveVariablesTest.cpp new file mode 100644 index 0000000..577ecde --- /dev/null +++ b/backend/unittests/CodeGen/LiveVariablesTest.cpp @@ -0,0 +1,316 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveVariables.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveIntervals.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +namespace { + +using namespace rcc::test::liveness; + +void testLivenessRebuildAndVerifier(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("rebuild", 6, 2); + if (!Fixture) { + Context.expect(false, "liveness-rebuild fixture creation must succeed"); + return; + } + auto &Function = *Fixture->Function; + auto &Entry = *Fixture->Blocks[0]; + auto &Exit = *Fixture->Blocks[1]; + auto Edge = Function.cfgUpdater().addSuccessor(Entry, Exit, rcc::BranchProbability::one()); + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + const rcc::Register G1 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G1)); + auto LiveDef = buildDef(Function, Target, Entry, G0); + auto FirstUse = buildUse(Function, Target, Exit, G0); + auto LastUse = buildUse(Function, Target, Exit, G0); + auto DeadDef = buildDef(Function, Target, Exit, G1); + if (!Edge || !LiveDef || !FirstUse || !LastUse || !DeadDef) { + Context.expect(false, "liveness-rebuild MachineIR must be constructed"); + return; + } + auto StaleLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0)); + Context.expect(StaleLiveIn.has_value(), "stale live-in setup must succeed"); + setRebuildProperties(Function); + + rcc::MachinePassManager Pipeline; + auto Added = Pipeline.addPass(std::make_unique<rcc::RebuildMachineLivenessPass>()); + rcc::MachineAnalysisManager Analyses; + auto Run = Added ? Pipeline.run(Function, Target, Analyses) + : rcc::Expected<void>{std::unexpected(Added.error())}; + if (!Run) + std::cerr << "liveness rebuild pipeline error: " << Run.error().message() << '\n'; + Context.expect(Run.has_value() && + Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness), + "RebuildMachineLiveness must publish TracksLiveness through the pass manager"); + if (!Run) + return; + Context.expect( + Entry.liveIns().empty() && Exit.liveIns().size() == 1 && + Exit.liveIns().front().PhysReg == physical(rcc::test::TestRegister::G0) && + Exit.liveIns().front().Lanes == rcc::LaneMask::all(), + "liveness rebuild must replace stale live-ins with canonical whole-register input"); + Context.expect(!hasFlag(**LiveDef, 0, rcc::RegisterOperandFlag::Dead) && + !hasFlag(**FirstUse, 0, rcc::RegisterOperandFlag::Kill) && + hasFlag(**LastUse, 0, rcc::RegisterOperandFlag::Kill) && + hasFlag(**DeadDef, 0, rcc::RegisterOperandFlag::Dead), + "reverse reconstruction must derive conservative kill and dead flags"); + Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(), + "rebuilt tracked liveness must pass the MachineVerifier"); + + auto ConservativeLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0)); + Context.expect(ConservativeLiveIn.has_value() && + rcc::MachineVerifier::verify(Function, Target).has_value(), + "MachineVerifier must accept conservative physical live-ins"); + Entry.clearLiveIns(); + + rcc::MachineOperand *FirstUseOperand = (*FirstUse)->operandAt(0); + if (FirstUseOperand == nullptr) { + Context.expect(false, "first use operand must exist"); + return; + } + rcc::RegisterOperandFlags StaleFlags = FirstUseOperand->registerFlags(); + StaleFlags.set(rcc::RegisterOperandFlag::Kill); + auto StaleKill = FirstUseOperand->setRegisterFlags(StaleFlags); + Context.expect(StaleKill.has_value() && !rcc::MachineVerifier::verify(Function, Target), + "MachineVerifier must reject an overstrong tracked kill flag"); + StaleFlags.clear(rcc::RegisterOperandFlag::Kill); + auto ClearedKill = FirstUseOperand->setRegisterFlags(StaleFlags); + Context.expect(ClearedKill.has_value(), "stale kill flag cleanup must succeed"); + Exit.clearLiveIns(); + Context.expect(!rcc::MachineVerifier::verify(Function, Target), + "MachineVerifier must reject stale tracked physical live-ins"); + + rcc::RebuildMachineLivenessPass Rebuild; + auto Repaired = Rebuild.run(Function, Target, Analyses); + Context.expect(Repaired && rcc::MachineVerifier::verify(Function, Target), + "a second liveness rebuild must repair stale derived state"); +} + +void testTrackedLiveThroughPhysicalRegister(TestContext &Context, + const rcc::TargetDescription &Target) { + auto Fixture = createFunction("tracked-live-through", 11, 2); + if (!Fixture) { + Context.expect(false, "tracked live-through fixture creation must succeed"); + return; + } + auto &Function = *Fixture->Function; + auto &Predecessor = *Fixture->Blocks[0]; + auto &Successor = *Fixture->Blocks[1]; + const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); + auto Edge = + Function.cfgUpdater().addSuccessor(Predecessor, Successor, rcc::BranchProbability::one()); + auto Use = buildUse(Function, Target, Successor, G0); + auto LiveIn = Successor.addLiveIn(physical(rcc::test::TestRegister::G0)); + if (!Edge || !Use || !LiveIn) { + Context.expect(false, "tracked live-through MachineIR must be constructed"); + return; + } + + Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness); + Context.expect(rcc::verifyTrackedMachineLiveness(Function, Target).has_value() && + Predecessor.liveIns().empty(), + "a predecessor must not declare a physical register used only by its successor"); + Successor.clearLiveIns(); + Context.expect(!rcc::verifyTrackedMachineLiveness(Function, Target), + "a block must declare a physical register that it reads before defining"); +} + +void testFailedRebuildIsAtomic(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("failed-rebuild", 9, 2); + if (!Fixture) { + Context.expect(false, "failed-rebuild fixture creation must succeed"); + return; + } + auto Destination = createVReg(*Fixture->Function); + auto Source = createVReg(*Fixture->Function); + if (!Destination || !Source) { + Context.expect(false, "failed-rebuild virtual registers must be created"); + return; + } + + auto &Predecessor = *Fixture->Blocks[0]; + auto &PhiBlock = *Fixture->Blocks[1]; + const auto LiveIn = + PhiBlock.addLiveIn(physical(rcc::test::TestRegister::G0), rcc::LaneMask::fromRaw(0x1)); + rcc::RegisterOperandFlags KillFlags; + KillFlags.set(rcc::RegisterOperandFlag::Kill); + rcc::MachineIRBuilder Builder(*Fixture->Function, Target); + auto Point = Builder.setInsertPoint(PhiBlock); + auto Pending = Point ? Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI)) + : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())}; + auto Def = Pending ? Pending->addDef(*Destination) + : rcc::Expected<void>{std::unexpected(Pending.error())}; + auto Use = + Def ? Pending->addUse(*Source, KillFlags) : rcc::Expected<void>{std::unexpected(Def.error())}; + auto Incoming = + Use ? Pending->addBasicBlock(Predecessor) : rcc::Expected<void>{std::unexpected(Use.error())}; + auto Phi = Incoming ? Pending->build() + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Incoming.error())}; + if (!LiveIn || !Phi) { + Context.expect(false, "malformed-edge PHI setup must succeed"); + return; + } + + const std::vector<rcc::MachineBasicBlockLiveIn> OriginalLiveIns(PhiBlock.liveIns().begin(), + PhiBlock.liveIns().end()); + const rcc::RegisterOperandFlags OriginalFlags = (*Phi)->operandAt(1)->registerFlags(); + auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, Target); + Context.expect(!Rebuilt && Rebuilt.error().code() == rcc::ErrorCode::VerificationError && + std::ranges::equal(PhiBlock.liveIns(), OriginalLiveIns) && + (*Phi)->operandAt(1)->registerFlags() == OriginalFlags, + "malformed PHI edges must fail without changing live-ins or operand flags"); +} + +class DummyAnalysis final { +public: + struct Result final {}; + + [[nodiscard]] static rcc::Expected<Result> + run(rcc::MachineFunction &, const rcc::TargetDescription &, rcc::MachineAnalysisManager &) { + return Result{}; + } +}; + +void testAnalysisRegistrationAndInvalidation(TestContext &Context, + const rcc::TargetDescription &Target) { + auto Fixture = createFunction("analysis-invalidation", 7, 1); + if (!Fixture) { + Context.expect(false, "analysis-invalidation fixture creation must succeed"); + return; + } + auto Reg = createVReg(*Fixture->Function); + auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; + auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; + if (!Reg || !Def || !Use) { + Context.expect(false, "analysis-invalidation instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto FirstRegistration = rcc::registerStage11MachineAnalyses(Analyses); + auto SecondRegistration = rcc::registerStage11MachineAnalyses(Analyses); + auto Intervals = FirstRegistration + ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target) + : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ + std::unexpected(FirstRegistration.error())}; + Context.expect(FirstRegistration && SecondRegistration && Intervals && + Analyses.cachedResultCount(*Fixture->Function) == 3, + "Stage 11 analyses must register idempotently and materialize dependencies"); + Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), + {rcc::MachinePassChange::Frame}); + Context.expect(Analyses.cachedResultCount(*Fixture->Function) == 3, + "debug-only changes must preserve all liveness analyses"); + Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), + {rcc::MachinePassChange::Operands}); + Context.expect( + Analyses.cachedResultCount(*Fixture->Function) == 1 && + Analyses.hasCached(*Fixture->Function, + rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()), + "operand changes must retain SlotIndexes while invalidating liveness dependents"); + auto Recomputed = Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target); + Context.expect(Recomputed && Analyses.cachedResultCount(*Fixture->Function) == 3, + "invalidated liveness dependencies must recompute on demand"); + Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), + {rcc::MachinePassChange::BlockLayout}); + Context.expect( + Analyses.cachedResultCount(*Fixture->Function) == 1 && + Analyses.hasCached(*Fixture->Function, + rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()), + "layout changes must invalidate SlotIndexes and LiveIntervals only"); + + rcc::MachineAnalysisManager Atomic; + rcc::MachineAnalysisRegistration DummyRegistration; + DummyRegistration.Name = "SlotIndexes"; + auto Dummy = Atomic.registerAnalysis<DummyAnalysis>(std::move(DummyRegistration)); + auto Rejected = rcc::registerStage11MachineAnalyses(Atomic); + Context.expect( + Dummy && !Rejected && Atomic.isRegistered(rcc::MachineAnalysisManager::id<DummyAnalysis>()) && + !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()) && + !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()), + "failed standard-analysis registration must leave the manager unchanged"); +} + +void testRISCVReservedRegisterLiveness(TestContext &Context) { + auto Target = rcc::riscv::createTargetDescription(); + auto Fixture = createFunction("riscv-reserved-liveness", 10, 1); + if (!Target || !Fixture) { + Context.expect(false, "RV64GC reserved-register liveness fixture creation must succeed"); + return; + } + auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0); + auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5); + if (!X0 || !X5) { + Context.expect(false, "RV64GC reserved-register fixture registers must resolve"); + return; + } + + rcc::MachineIRBuilder Builder(*Fixture->Function, *Target); + auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]); + auto Pending = Point ? Builder.buildInstr(rcc::Opcode::fromValue( + static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))) + : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())}; + auto Def = Pending ? Pending->addDef(rcc::Register::fromPhysical(*X5)) + : rcc::Expected<void>{std::unexpected(Pending.error())}; + auto Use = Def ? Pending->addUse(rcc::Register::fromPhysical(*X0)) + : rcc::Expected<void>{std::unexpected(Def.error())}; + auto Immediate = + Use ? Pending->addImmediate(1) : rcc::Expected<void>{std::unexpected(Use.error())}; + auto Instruction = Immediate + ? Pending->build() + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Immediate.error())}; + auto DeadDef = + Instruction ? Builder.buildInstr(rcc::Opcode::fromValue( + static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))) + : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Instruction.error())}; + auto DeadDefDestination = DeadDef ? DeadDef->addDef(rcc::Register::fromPhysical(*X0)) + : rcc::Expected<void>{std::unexpected(DeadDef.error())}; + auto DeadDefSource = DeadDefDestination + ? DeadDef->addUse(rcc::Register::fromPhysical(*X0)) + : rcc::Expected<void>{std::unexpected(DeadDefDestination.error())}; + auto DeadDefImmediate = DeadDefSource + ? DeadDef->addImmediate(0) + : rcc::Expected<void>{std::unexpected(DeadDefSource.error())}; + auto DeadDefInstruction = + DeadDefImmediate + ? DeadDef->build() + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(DeadDefImmediate.error())}; + if (!Instruction || !DeadDefInstruction) { + Context.expect(false, "RV64GC reserved-register liveness instruction must be built"); + return; + } + + auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, *Target); + const rcc::MachineOperand *ZeroUse = (*Instruction)->operandAt(1); + const rcc::MachineOperand *ZeroDef = (*DeadDefInstruction)->operandAt(0); + const rcc::MachineOperand *DeadDefZeroUse = (*DeadDefInstruction)->operandAt(1); + Context.expect(Rebuilt && Fixture->Blocks[0]->liveIns().empty() && ZeroUse != nullptr && + !ZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill) && + ZeroDef != nullptr && + ZeroDef->registerFlags().has(rcc::RegisterOperandFlag::Dead) && + DeadDefZeroUse != nullptr && + !DeadDefZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill), + "reserved uses must remain available while dead defs retain precise liveness"); +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + + testLivenessRebuildAndVerifier(Context, *Target); + testTrackedLiveThroughPhysicalRegister(Context, *Target); + testFailedRebuildIsAtomic(Context, *Target); + testAnalysisRegistrationAndInvalidation(Context, *Target); + testRISCVReservedRegisterLiveness(Context); + return Context.result(); +} diff --git a/backend/unittests/CodeGen/MachineLivenessTest.cpp b/backend/unittests/CodeGen/MachineLivenessTest.cpp deleted file mode 100644 index 50e6ffc..0000000 --- a/backend/unittests/CodeGen/MachineLivenessTest.cpp +++ /dev/null @@ -1,971 +0,0 @@ -// SPDX-License-Identifier: GPL-3.0-or-later - -#include "rcc/CodeGen/MachineLiveness.h" - -#include "Target/TestTarget.h" -#include "rcc/CodeGen/GenericOpcodes.h" -#include "rcc/CodeGen/MachineBasicBlock.h" -#include "rcc/CodeGen/MachineCFGUpdater.h" -#include "rcc/CodeGen/MachineFunction.h" -#include "rcc/CodeGen/MachineIRBuilder.h" -#include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineOperand.h" -#include "rcc/CodeGen/MachineRegisterInfo.h" -#include "rcc/CodeGen/MachineVerifier.h" -#include "rcc/CodeGen/TargetDescription.h" -#include "rcc/Target/RISCV/RISCVInstructions.h" -#include "rcc/Target/RISCV/RISCVRegisters.h" -#include "rcc/Target/RISCV/RISCVTarget.h" - -#include <algorithm> -#include <array> -#include <cstddef> -#include <cstdint> -#include <iostream> -#include <memory> -#include <span> -#include <string> -#include <string_view> -#include <utility> -#include <vector> - -namespace { - -constexpr std::uint32_t DefOpcode = 2048; -constexpr std::uint32_t UseOpcode = 2049; -constexpr std::uint32_t EarlyDefOpcode = 2050; -constexpr std::uint32_t MaskOpcode = 2051; -constexpr std::uint32_t MaskedDefOpcode = 2052; -constexpr std::uint32_t LiveOutMaskOpcode = 2053; - -class TestContext final { -public: - void expect(bool Condition, std::string_view Message) { - if (Condition) - return; - std::cerr << Message << '\n'; - ++Failures; - } - - [[nodiscard]] int result() const noexcept { - return Failures == 0 ? 0 : 1; - } - -private: - int Failures = 0; -}; - -[[nodiscard]] rcc::Opcode testOpcode(std::uint32_t Value) { - return rcc::Opcode::fromValue(Value); -} - -[[nodiscard]] rcc::OperandDescriptor registerOperand(rcc::RegisterOperandRole Role, - bool EarlyClobber = false) { - rcc::OperandDescriptor Result; - Result.Kinds = {rcc::MachineOperand::Kind::Register}; - Result.RegisterRole = Role; - Result.EarlyClobber = EarlyClobber; - Result.AllowSubReg = true; - return Result; -} - -[[nodiscard]] rcc::OperandDescriptor plainOperand(rcc::MachineOperand::Kind Kind) { - rcc::OperandDescriptor Result; - Result.Kinds = {Kind}; - return Result; -} - -[[nodiscard]] rcc::InstructionDescriptor instruction(std::uint32_t Value, std::string Name) { - rcc::InstructionDescriptor Result; - Result.InstructionOpcode = testOpcode(Value); - Result.Name = std::move(Name); - Result.Flags = {rcc::InstructionFlag::ProducesCode}; - return Result; -} - -[[nodiscard]] rcc::Expected<rcc::TargetDescription> createTarget() { - std::vector<rcc::InstructionDescriptor> Descriptors; - std::vector<rcc::ImmediatePredicate> Predicates; - auto Generic = rcc::appendGenericInstructionInfo(Descriptors, Predicates); - if (!Generic) - return std::unexpected(Generic.error()); - - auto Def = instruction(DefOpcode, "LIVENESS_DEF"); - Def.Operands = {registerOperand(rcc::RegisterOperandRole::Def)}; - Def.NumExplicitDefs = 1; - Descriptors.push_back(std::move(Def)); - - auto Use = instruction(UseOpcode, "LIVENESS_USE"); - Use.Operands = {registerOperand(rcc::RegisterOperandRole::Use)}; - Descriptors.push_back(std::move(Use)); - - auto EarlyDef = instruction(EarlyDefOpcode, "LIVENESS_EARLY_DEF"); - EarlyDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def, true)}; - EarlyDef.NumExplicitDefs = 1; - Descriptors.push_back(std::move(EarlyDef)); - - auto Mask = instruction(MaskOpcode, "LIVENESS_MASK"); - Mask.Operands = {plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; - Mask.Flags.set(rcc::InstructionFlag::Call); - Mask.Flags.set(rcc::InstructionFlag::HasSideEffects); - Descriptors.push_back(std::move(Mask)); - - auto MaskedDef = instruction(MaskedDefOpcode, "LIVENESS_MASKED_DEF"); - MaskedDef.Operands = {registerOperand(rcc::RegisterOperandRole::Def), - plainOperand(rcc::MachineOperand::Kind::RegisterMask)}; - MaskedDef.NumExplicitDefs = 1; - MaskedDef.Flags.set(rcc::InstructionFlag::Call); - MaskedDef.Flags.set(rcc::InstructionFlag::HasSideEffects); - Descriptors.push_back(std::move(MaskedDef)); - - auto LiveOutMask = instruction(LiveOutMaskOpcode, "LIVENESS_LIVEOUT_MASK"); - LiveOutMask.Operands = {plainOperand(rcc::MachineOperand::Kind::LiveOutRegisterMask)}; - Descriptors.push_back(std::move(LiveOutMask)); - - auto Instructions = rcc::InstructionSet::create(std::move(Descriptors), std::move(Predicates)); - if (!Instructions) - return std::unexpected(Instructions.error()); - return rcc::test::createTestTargetDescription(std::move(*Instructions)); -} - -struct FunctionFixture final { - std::unique_ptr<rcc::MachineFunction> Function; - std::vector<rcc::MachineBasicBlock *> Blocks; -}; - -[[nodiscard]] rcc::Expected<FunctionFixture> createFunction(std::string Name, std::uint64_t ID, - std::size_t BlockCount) { - auto Function = - rcc::MachineFunction::create(std::move(Name), rcc::MachineFunctionStableID::fromValue(ID)); - if (!Function) - return std::unexpected(Function.error()); - FunctionFixture Result{std::move(*Function), {}}; - Result.Blocks.reserve(BlockCount); - for (std::size_t Index = 0; Index < BlockCount; ++Index) { - auto Block = Result.Function->createBasicBlock(); - if (!Block) - return std::unexpected(Block.error()); - auto Appended = Result.Function->appendBlock(**Block); - if (!Appended) - return std::unexpected(Appended.error()); - Result.Blocks.push_back(*Block); - } - return Result; -} - -[[nodiscard]] rcc::Expected<rcc::Register> createVReg(rcc::MachineFunction &Function) { - auto Type = rcc::LLT::makeInteger(64); - if (!Type) - return std::unexpected(Type.error()); - auto Reg = Function.registerInfo().createVirtualRegister(*Type); - if (!Reg) - return std::unexpected(Reg.error()); - auto Bank = Function.registerInfo().setRegisterBank(*Reg, rcc::test::TestRegisterBank::GPR); - if (!Bank) - return std::unexpected(Bank.error()); - auto Class = Function.registerInfo().setRegisterClass(*Reg, rcc::test::TestRegisterClass::GPR64); - if (!Class) - return std::unexpected(Class.error()); - return *Reg; -} - -[[nodiscard]] rcc::Expected<rcc::MachineInstr *> -buildDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {}, - bool EarlyClobber = false) { - rcc::MachineIRBuilder Builder(Function, Target); - auto Point = Builder.setInsertPoint(Block); - if (!Point) - return std::unexpected(Point.error()); - auto Pending = Builder.buildInstr(testOpcode(EarlyClobber ? EarlyDefOpcode : DefOpcode)); - if (!Pending) - return std::unexpected(Pending.error()); - rcc::RegisterOperandFlags Flags; - if (EarlyClobber) - Flags.set(rcc::RegisterOperandFlag::EarlyClobber); - auto Added = Pending->addDef(Reg, Flags, SubReg); - if (!Added) - return std::unexpected(Added.error()); - return Pending->build(); -} - -[[nodiscard]] rcc::Expected<rcc::MachineInstr *> -buildUse(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, rcc::Register Reg, rcc::SubRegIndex SubReg = {}, - rcc::MachineInstr *Before = nullptr) { - rcc::MachineIRBuilder Builder(Function, Target); - auto Point = - Before == nullptr ? Builder.setInsertPoint(Block) : Builder.setInsertPointBefore(*Before); - if (!Point) - return std::unexpected(Point.error()); - auto Pending = Builder.buildInstr(testOpcode(UseOpcode)); - if (!Pending) - return std::unexpected(Pending.error()); - auto Added = Pending->addUse(Reg, {}, SubReg); - if (!Added) - return std::unexpected(Added.error()); - return Pending->build(); -} - -[[nodiscard]] rcc::Expected<rcc::MachineInstr *> -buildMask(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, std::shared_ptr<const rcc::RegisterMask> Mask) { - rcc::MachineIRBuilder Builder(Function, Target); - auto Point = Builder.setInsertPoint(Block); - if (!Point) - return std::unexpected(Point.error()); - auto Pending = Builder.buildInstr(testOpcode(MaskOpcode)); - if (!Pending) - return std::unexpected(Pending.error()); - auto Added = Pending->addRegisterMask(std::move(Mask)); - if (!Added) - return std::unexpected(Added.error()); - return Pending->build(); -} - -[[nodiscard]] rcc::Expected<rcc::MachineInstr *> -buildMaskedDef(rcc::MachineFunction &Function, const rcc::TargetDescription &Target, - rcc::MachineBasicBlock &Block, rcc::Register Reg, - std::shared_ptr<const rcc::RegisterMask> Mask) { - rcc::MachineIRBuilder Builder(Function, Target); - auto Point = Builder.setInsertPoint(Block); - if (!Point) - return std::unexpected(Point.error()); - auto Pending = Builder.buildInstr(testOpcode(MaskedDefOpcode)); - if (!Pending) - return std::unexpected(Pending.error()); - auto Def = Pending->addDef(Reg); - if (!Def) - return std::unexpected(Def.error()); - auto MaskResult = Pending->addRegisterMask(std::move(Mask)); - if (!MaskResult) - return std::unexpected(MaskResult.error()); - return Pending->build(); -} - -[[nodiscard]] rcc::PhysicalRegister physical(std::uint32_t Number) { - return *rcc::PhysicalRegister::create(Number); -} - -[[nodiscard]] bool hasFlag(const rcc::MachineInstr &Instruction, std::size_t OperandIndex, - rcc::RegisterOperandFlag Flag) { - const rcc::MachineOperand *Operand = Instruction.operandAt(OperandIndex); - return Operand != nullptr && Operand->registerFlags().has(Flag); -} - -void testLiveRange(TestContext &Context) { - const rcc::SlotIndex S16 = rcc::SlotIndex::fromValue(16).registerSlot(); - const rcc::SlotIndex S24 = rcc::SlotIndex::fromValue(24).registerSlot(); - const rcc::SlotIndex S32 = rcc::SlotIndex::fromValue(32).registerSlot(); - const rcc::SlotIndex S40 = rcc::SlotIndex::fromValue(40).registerSlot(); - const rcc::SlotIndex S48 = rcc::SlotIndex::fromValue(48).registerSlot(); - - rcc::LiveRange Range; - auto First = Range.createValue(S16); - Context.expect(First.has_value(), "live value creation must succeed"); - if (!First) - return; - Context.expect(Range.addSegment({S16, S32, *First}).has_value() && - Range.addSegment({S32, S48, *First}).has_value() && - Range.segments().size() == 1, - "adjacent same-value live segments must merge"); - auto Second = Range.createValue(S40, rcc::LiveValueState::Redefined); - Context.expect(Second.has_value() && !Range.addSegment({S24, S40, *Second}), - "overlapping different live values must be rejected"); - Context.expect(Range.valueAt(S24) != nullptr && Range.liveAt(S40) && - Range.remove(S24, S40).has_value() && Range.segments().size() == 2 && - Range.verify().has_value(), - "live-range lookup and removal must preserve ordered half-open segments"); - - rcc::LiveRange Shrunk; - auto Value = Shrunk.createValue(S16); - if (!Value) { - Context.expect(false, "shrink test value creation must succeed"); - return; - } - const std::array Uses{S32}; - Context.expect(Shrunk.addSegment({S16, S48.deadSlot(), *Value}).has_value() && - Shrunk.shrinkToUses(Uses).has_value() && Shrunk.segments().size() == 1 && - Shrunk.segments().front().End == S32.deadSlot(), - "shrinkToUses must retain exactly through the final use dead slot"); -} - -void testSlotIndexes(TestContext &Context, const rcc::TargetDescription &Target) { - auto Fixture = createFunction("slot-indexes", 1, 1); - if (!Fixture) { - Context.expect(false, "SlotIndexes fixture creation must succeed"); - return; - } - auto Reg = createVReg(*Fixture->Function); - auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; - auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; - if (!Reg || !Def || !Use) { - Context.expect(false, "SlotIndexes instructions must be built"); - return; - } - - rcc::MachineAnalysisManager Analyses; - auto Registered = rcc::registerStage11MachineAnalyses(Analyses); - auto Indexes = - Registered - ? Analyses.getResult<rcc::SlotIndexesAnalysis>(*Fixture->Function, Target) - : rcc::Expected<rcc::SlotIndexesAnalysis::Result *>{std::unexpected(Registered.error())}; - if (!Indexes) { - Context.expect(false, "SlotIndexes analysis must materialize"); - return; - } - const rcc::SlotIndex DefIndex = (*Indexes)->instructionIndex(**Def); - const rcc::SlotIndex UseIndex = (*Indexes)->instructionIndex(**Use); - Context.expect((*Indexes)->blockStart(*Fixture->Blocks[0]) < DefIndex.earlyClobberSlot() && - DefIndex.earlyClobberSlot() < DefIndex && DefIndex < DefIndex.deadSlot() && - DefIndex.deadSlot() < UseIndex && - UseIndex < (*Indexes)->blockEnd(*Fixture->Blocks[0]), - "SlotIndexes must order block, early-clobber, register, and dead slots"); - Context.expect((*Indexes)->instructionFromIndex(DefIndex.deadSlot()) == *Def && - (*Indexes)->blockFromIndex(UseIndex) == Fixture->Blocks[0], - "SlotIndexes reverse mappings must accept every instruction subslot"); - - auto Inserted = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Use); - Context.expect(Inserted && (*Indexes)->insertInstruction(**Inserted).has_value(), - "local SlotIndex insertion must use reserved numbering space"); - if (Inserted) { - const rcc::SlotIndex InsertedIndex = (*Indexes)->instructionIndex(**Inserted); - Context.expect(DefIndex < InsertedIndex && InsertedIndex < UseIndex, - "locally inserted SlotIndex must lie between adjacent instructions"); - Context.expect((*Indexes)->eraseInstruction(**Inserted).has_value() && - !(*Indexes)->instructionIndex(**Inserted).isValid() && - (*Indexes)->renumber(*Fixture->Function).has_value() && - (*Indexes)->instructionIndex(**Inserted).isValid(), - "SlotIndex erasure and full renumbering must rebuild exact mappings"); - - auto Second = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Inserted); - auto SecondIndexed = Second ? (*Indexes)->insertInstruction(**Second) - : rcc::Expected<void>{std::unexpected(Second.error())}; - auto Third = Second - ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Second) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Second.error())}; - auto ThirdIndexed = Third ? (*Indexes)->insertInstruction(**Third) - : rcc::Expected<void>{std::unexpected(Third.error())}; - auto Exhausted = - Third ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Third) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Third.error())}; - auto ExhaustedIndex = Exhausted ? (*Indexes)->insertInstruction(**Exhausted) - : rcc::Expected<void>{std::unexpected(Exhausted.error())}; - Context.expect(SecondIndexed && ThirdIndexed && Exhausted && !ExhaustedIndex && - ExhaustedIndex.error().code() == rcc::ErrorCode::Unsupported && - (*Indexes)->renumber(*Fixture->Function).has_value() && - (*Indexes)->instructionIndex(**Exhausted).isValid(), - "local SlotIndex exhaustion must request and recover through full renumbering"); - } -} - -void testCFGAndValueNumbers(TestContext &Context, const rcc::TargetDescription &Target) { - auto Fixture = createFunction("cfg-liveness", 2, 8); - if (!Fixture) { - Context.expect(false, "CFG liveness fixture creation must succeed"); - return; - } - auto &Function = *Fixture->Function; - auto &Entry = *Fixture->Blocks[0]; - auto &Left = *Fixture->Blocks[1]; - auto &Right = *Fixture->Blocks[2]; - auto &Join = *Fixture->Blocks[3]; - auto &Header = *Fixture->Blocks[4]; - auto &Body = *Fixture->Blocks[5]; - auto &Exit = *Fixture->Blocks[6]; - auto &Dead = *Fixture->Blocks[7]; - auto Half = rcc::BranchProbability::fromFraction(1, 2); - auto Updater = Function.cfgUpdater(); - const bool CFGValid = Half && Updater.addSuccessor(Entry, Left, *Half) && - Updater.addSuccessor(Entry, Right, *Half) && - Updater.addSuccessor(Left, Join, rcc::BranchProbability::one()) && - Updater.addSuccessor(Right, Join, rcc::BranchProbability::one()) && - Updater.addSuccessor(Join, Header, rcc::BranchProbability::one()) && - Updater.addSuccessor(Header, Body, *Half) && - Updater.addSuccessor(Header, Exit, *Half) && - Updater.addSuccessor(Body, Header, rcc::BranchProbability::one()); - Context.expect(CFGValid, "diamond and loop CFG construction must succeed"); - if (!CFGValid) - return; - - auto Across = createVReg(Function); - auto Merged = createVReg(Function); - auto Unreachable = createVReg(Function); - auto Redefined = createVReg(Function); - if (!Across || !Merged || !Unreachable || !Redefined) { - Context.expect(false, "CFG liveness virtual registers must be created"); - return; - } - auto AcrossDef = buildDef(Function, Target, Entry, *Across); - auto LeftDef = buildDef(Function, Target, Left, *Merged); - auto RightDef = buildDef(Function, Target, Right, *Merged); - auto MergedUse = buildUse(Function, Target, Join, *Merged); - auto LoopUse = buildUse(Function, Target, Body, *Across); - auto DeadUse = buildUse(Function, Target, Dead, *Unreachable); - auto FirstRedef = buildDef(Function, Target, Exit, *Redefined); - auto SecondRedef = buildDef(Function, Target, Exit, *Redefined); - if (!AcrossDef || !LeftDef || !RightDef || !MergedUse || !LoopUse || !DeadUse || !FirstRedef || - !SecondRedef) { - Context.expect(false, "CFG liveness instructions must be built"); - return; - } - - rcc::MachineAnalysisManager Analyses; - auto Registered = rcc::registerStage11MachineAnalyses(Analyses); - auto Variables = Registered ? Analyses.getResult<rcc::LiveVariablesAnalysis>(Function, Target) - : rcc::Expected<rcc::LiveVariablesAnalysis::Result *>{ - std::unexpected(Registered.error())}; - auto Intervals = Registered ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(Function, Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(Registered.error())}; - if (!Variables || !Intervals) { - Context.expect(false, "CFG liveness analyses must materialize"); - return; - } - Context.expect((*Variables)->isLiveOut(Entry, *Across) && (*Variables)->isLiveIn(Left, *Across) && - (*Variables)->isLiveIn(Right, *Across) && - (*Variables)->isLiveIn(Header, *Across) && - (*Variables)->isLiveOut(Body, *Across), - "CFG fixed point must propagate a value through a diamond and loop backedge"); - Context.expect( - (*Variables)->isLiveOut(Left, *Merged) && (*Variables)->isLiveOut(Right, *Merged) && - (*Variables)->isLiveIn(Join, *Merged) && (*Variables)->isLiveIn(Dead, *Unreachable), - "liveness must merge predecessor definitions and retain unreachable uses"); - - const rcc::LiveInterval *MergedInterval = (*Intervals)->interval(*Merged); - const rcc::LiveInterval *AcrossInterval = (*Intervals)->interval(*Across); - const rcc::LiveInterval *RedefinedInterval = (*Intervals)->interval(*Redefined); - const bool HasPhi = MergedInterval != nullptr && - std::ranges::any_of(MergedInterval->MainRange.values(), - [](const rcc::LiveValueNumber &Value) { - return Value.State == rcc::LiveValueState::Phi; - }); - const bool HasRedefined = - RedefinedInterval != nullptr && - std::ranges::any_of(RedefinedInterval->MainRange.values(), - [](const rcc::LiveValueNumber &Value) { - return Value.State == rcc::LiveValueState::Redefined; - }); - Context.expect(MergedInterval != nullptr && MergedInterval->MainRange.values().size() >= 3 && - HasPhi && HasRedefined, - "non-SSA intervals must retain multiple definitions, PHI, and redefined values"); - Context.expect(AcrossInterval != nullptr && (*Intervals)->interferes(*Across, *Merged), - "live intervals must expose CFG-derived interference"); -} - -void testLaneSubrangesAndEarlyClobber(TestContext &Context, const rcc::TargetDescription &Target) { - auto Fixture = createFunction("lane-subranges", 3, 1); - if (!Fixture) { - Context.expect(false, "lane-subrange fixture creation must succeed"); - return; - } - auto Reg = createVReg(*Fixture->Function); - auto Early = createVReg(*Fixture->Function); - if (!Reg || !Early) { - Context.expect(false, "lane-subrange registers must be created"); - return; - } - auto LowDef = - buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32); - auto LowUse = - buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, rcc::test::TestSubReg::Low32); - auto HighDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, - rcc::test::TestSubReg::High32); - auto HighUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, - rcc::test::TestSubReg::High32); - auto EarlyDef = buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Early, {}, true); - auto EarlyUse = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Early); - if (!LowDef || !LowUse || !HighDef || !HighUse || !EarlyDef || !EarlyUse) { - Context.expect(false, "lane-subrange instructions must be built"); - return; - } - - rcc::MachineAnalysisManager Analyses; - auto Registered = rcc::registerStage11MachineAnalyses(Analyses); - auto Intervals = Registered - ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(Registered.error())}; - if (!Intervals) { - Context.expect(false, "lane-subrange intervals must materialize"); - return; - } - const rcc::LiveInterval *Interval = (*Intervals)->interval(*Reg); - const rcc::LiveInterval *EarlyInterval = (*Intervals)->interval(*Early); - const bool HasLow = Interval != nullptr && - std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) { - return Range.Lanes == rcc::LaneMask::fromRaw(0x3); - }); - const bool HasHigh = Interval != nullptr && - std::ranges::any_of(Interval->SubRanges, [](const rcc::LiveSubRange &Range) { - return Range.Lanes == rcc::LaneMask::fromRaw(0xC); - }); - Context.expect(Interval != nullptr && Interval->SubRanges.size() == 2 && HasLow && HasHigh, - "partial virtual-register accesses must form disjoint lane subranges"); - Context.expect(EarlyInterval != nullptr && !EarlyInterval->MainRange.values().empty() && - EarlyInterval->MainRange.values().front().Definition.kind() == - rcc::SlotIndexKind::EarlyClobber, - "early-clobber definitions must use the early-clobber slot"); -} - -void testPhysicalUnitsAndRegMasks(TestContext &Context, const rcc::TargetDescription &Target) { - const rcc::RegisterUnitID MultiLaneUnit = rcc::RegisterUnitID::fromValue(9); - rcc::RegisterUnitLaneSet PartialLanes; - PartialLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x3)); - rcc::RegisterUnitLaneSet RemovedLanes; - RemovedLanes.add(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)); - PartialLanes.subtract(RemovedLanes); - Context.expect(PartialLanes.lanes(MultiLaneUnit) == rcc::LaneMask::fromRaw(0x1) && - PartialLanes.contains(MultiLaneUnit, rcc::LaneMask::fromRaw(0x1)) && - !PartialLanes.intersects(MultiLaneUnit, rcc::LaneMask::fromRaw(0x2)), - "RegisterUnit lane sets must preserve partial union and subtraction"); - - auto AliasFixture = createFunction("physical-alias", 4, 1); - if (!AliasFixture) { - Context.expect(false, "physical-alias fixture creation must succeed"); - return; - } - const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); - const rcc::Register G0High = - rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0High32)); - auto G0Def = buildDef(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0); - auto G0HighUse = buildUse(*AliasFixture->Function, Target, *AliasFixture->Blocks[0], G0High); - if (!G0Def || !G0HighUse) { - Context.expect(false, "physical-alias instructions must be built"); - return; - } - rcc::MachineAnalysisManager AliasAnalyses; - auto AliasRegistered = rcc::registerStage11MachineAnalyses(AliasAnalyses); - auto AliasIntervals = - AliasRegistered - ? AliasAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*AliasFixture->Function, Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(AliasRegistered.error())}; - const rcc::RegisterUnitID HighUnit = rcc::RegisterUnitID::fromValue(3); - Context.expect(AliasIntervals && (*AliasIntervals)->regUnitRange(HighUnit) != nullptr && - (*AliasIntervals)->regUnitRange(HighUnit)->segments().size() == 1, - "shared RegisterUnits must connect super-register defs to subregister uses"); - - auto MaskFixture = createFunction("regmask", 5, 1); - if (!MaskFixture) { - Context.expect(false, "RegMask fixture creation must succeed"); - return; - } - auto Across = createVReg(*MaskFixture->Function); - auto Output = createVReg(*MaskFixture->Function); - if (!Across || !Output) { - Context.expect(false, "RegMask virtual registers must be created"); - return; - } - const auto Mask = rcc::test::createTestCallPreservedMask(); - auto AcrossDef = buildDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); - auto FirstMask = buildMask(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], Mask); - auto AcrossUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Across); - auto OutputDef = - buildMaskedDef(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output, Mask); - auto OutputUse = buildUse(*MaskFixture->Function, Target, *MaskFixture->Blocks[0], *Output); - if (!AcrossDef || !FirstMask || !AcrossUse || !OutputDef || !OutputUse) { - Context.expect(false, "RegMask instructions must be built"); - return; - } - rcc::MachineAnalysisManager MaskAnalyses; - auto MaskRegistered = rcc::registerStage11MachineAnalyses(MaskAnalyses); - auto MaskIntervals = - MaskRegistered - ? MaskAnalyses.getResult<rcc::LiveIntervalsAnalysis>(*MaskFixture->Function, Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(MaskRegistered.error())}; - if (!MaskIntervals) { - Context.expect(false, "RegMask intervals must materialize"); - return; - } - const rcc::PhysicalRegister Candidate = physical(rcc::test::TestRegister::G0); - const rcc::LiveInterval *AcrossInterval = (*MaskIntervals)->interval(*Across); - const rcc::LiveInterval *OutputInterval = (*MaskIntervals)->interval(*Output); - Context.expect((*MaskIntervals)->regMaskPositions().size() == 2 && - std::ranges::all_of((*MaskIntervals)->regMaskPositions(), - [](const rcc::RegMaskPosition &Position) { - return Position.Position.kind() == - rcc::SlotIndexKind::EarlyClobber; - }), - "RegMask interference positions must use early-clobber slots"); - Context.expect(AcrossInterval != nullptr && OutputInterval != nullptr && - (*MaskIntervals)->regMaskClobbers(*AcrossInterval, Candidate) && - !(*MaskIntervals)->regMaskClobbers(*OutputInterval, Candidate), - "RegMask queries must reject live-through values but accept same-call outputs"); - Context.expect((*MaskIntervals)->regUnitRange(rcc::RegisterUnitID::fromValue(1)) == nullptr, - "unused RegMask clobbers must not expand into physical live ranges"); -} - -void setRebuildProperties(rcc::MachineFunction &Function) { - Function.properties().set(rcc::MachineFunctionProperty::Legalized); - Function.properties().set(rcc::MachineFunctionProperty::RegBankSelected); - Function.properties().set(rcc::MachineFunctionProperty::Selected); - Function.properties().set(rcc::MachineFunctionProperty::NoPHIs); - Function.properties().set(rcc::MachineFunctionProperty::TiedOpsRewritten); -} - -void testLivenessRebuildAndVerifier(TestContext &Context, const rcc::TargetDescription &Target) { - auto Fixture = createFunction("rebuild", 6, 2); - if (!Fixture) { - Context.expect(false, "liveness-rebuild fixture creation must succeed"); - return; - } - auto &Function = *Fixture->Function; - auto &Entry = *Fixture->Blocks[0]; - auto &Exit = *Fixture->Blocks[1]; - auto Edge = Function.cfgUpdater().addSuccessor(Entry, Exit, rcc::BranchProbability::one()); - const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); - const rcc::Register G1 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G1)); - auto LiveDef = buildDef(Function, Target, Entry, G0); - auto FirstUse = buildUse(Function, Target, Exit, G0); - auto LastUse = buildUse(Function, Target, Exit, G0); - auto DeadDef = buildDef(Function, Target, Exit, G1); - if (!Edge || !LiveDef || !FirstUse || !LastUse || !DeadDef) { - Context.expect(false, "liveness-rebuild MachineIR must be constructed"); - return; - } - auto StaleLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0)); - Context.expect(StaleLiveIn.has_value(), "stale live-in setup must succeed"); - setRebuildProperties(Function); - - rcc::MachinePassManager Pipeline; - auto Added = Pipeline.addPass(std::make_unique<rcc::RebuildMachineLivenessPass>()); - rcc::MachineAnalysisManager Analyses; - auto Run = Added ? Pipeline.run(Function, Target, Analyses) - : rcc::Expected<void>{std::unexpected(Added.error())}; - if (!Run) - std::cerr << "liveness rebuild pipeline error: " << Run.error().message() << '\n'; - Context.expect(Run.has_value() && - Function.properties().has(rcc::MachineFunctionProperty::TracksLiveness), - "RebuildMachineLiveness must publish TracksLiveness through the pass manager"); - if (!Run) - return; - Context.expect( - Entry.liveIns().empty() && Exit.liveIns().size() == 1 && - Exit.liveIns().front().PhysReg == physical(rcc::test::TestRegister::G0) && - Exit.liveIns().front().Lanes == rcc::LaneMask::all(), - "liveness rebuild must replace stale live-ins with canonical whole-register input"); - Context.expect(!hasFlag(**LiveDef, 0, rcc::RegisterOperandFlag::Dead) && - !hasFlag(**FirstUse, 0, rcc::RegisterOperandFlag::Kill) && - hasFlag(**LastUse, 0, rcc::RegisterOperandFlag::Kill) && - hasFlag(**DeadDef, 0, rcc::RegisterOperandFlag::Dead), - "reverse reconstruction must derive conservative kill and dead flags"); - Context.expect(rcc::MachineVerifier::verify(Function, Target).has_value(), - "rebuilt tracked liveness must pass the MachineVerifier"); - - auto ConservativeLiveIn = Entry.addLiveIn(physical(rcc::test::TestRegister::F0)); - Context.expect(ConservativeLiveIn.has_value() && - rcc::MachineVerifier::verify(Function, Target).has_value(), - "MachineVerifier must accept conservative physical live-ins"); - Entry.clearLiveIns(); - - rcc::MachineOperand *FirstUseOperand = (*FirstUse)->operandAt(0); - if (FirstUseOperand == nullptr) { - Context.expect(false, "first use operand must exist"); - return; - } - rcc::RegisterOperandFlags StaleFlags = FirstUseOperand->registerFlags(); - StaleFlags.set(rcc::RegisterOperandFlag::Kill); - auto StaleKill = FirstUseOperand->setRegisterFlags(StaleFlags); - Context.expect(StaleKill.has_value() && !rcc::MachineVerifier::verify(Function, Target), - "MachineVerifier must reject an overstrong tracked kill flag"); - StaleFlags.clear(rcc::RegisterOperandFlag::Kill); - auto ClearedKill = FirstUseOperand->setRegisterFlags(StaleFlags); - Context.expect(ClearedKill.has_value(), "stale kill flag cleanup must succeed"); - Exit.clearLiveIns(); - Context.expect(!rcc::MachineVerifier::verify(Function, Target), - "MachineVerifier must reject stale tracked physical live-ins"); - - rcc::RebuildMachineLivenessPass Rebuild; - auto Repaired = Rebuild.run(Function, Target, Analyses); - Context.expect(Repaired && rcc::MachineVerifier::verify(Function, Target), - "a second liveness rebuild must repair stale derived state"); -} - -void testTrackedLiveThroughPhysicalRegister(TestContext &Context, - const rcc::TargetDescription &Target) { - auto Fixture = createFunction("tracked-live-through", 11, 2); - if (!Fixture) { - Context.expect(false, "tracked live-through fixture creation must succeed"); - return; - } - auto &Function = *Fixture->Function; - auto &Predecessor = *Fixture->Blocks[0]; - auto &Successor = *Fixture->Blocks[1]; - const rcc::Register G0 = rcc::Register::fromPhysical(physical(rcc::test::TestRegister::G0)); - auto Edge = - Function.cfgUpdater().addSuccessor(Predecessor, Successor, rcc::BranchProbability::one()); - auto Use = buildUse(Function, Target, Successor, G0); - auto LiveIn = Successor.addLiveIn(physical(rcc::test::TestRegister::G0)); - if (!Edge || !Use || !LiveIn) { - Context.expect(false, "tracked live-through MachineIR must be constructed"); - return; - } - - Function.properties().set(rcc::MachineFunctionProperty::TracksLiveness); - Context.expect(rcc::verifyTrackedMachineLiveness(Function, Target).has_value() && - Predecessor.liveIns().empty(), - "a predecessor must not declare a physical register used only by its successor"); - Successor.clearLiveIns(); - Context.expect(!rcc::verifyTrackedMachineLiveness(Function, Target), - "a block must declare a physical register that it reads before defining"); -} - -void testFailedRebuildIsAtomic(TestContext &Context, const rcc::TargetDescription &Target) { - auto Fixture = createFunction("failed-rebuild", 9, 2); - if (!Fixture) { - Context.expect(false, "failed-rebuild fixture creation must succeed"); - return; - } - auto Destination = createVReg(*Fixture->Function); - auto Source = createVReg(*Fixture->Function); - if (!Destination || !Source) { - Context.expect(false, "failed-rebuild virtual registers must be created"); - return; - } - - auto &Predecessor = *Fixture->Blocks[0]; - auto &PhiBlock = *Fixture->Blocks[1]; - const auto LiveIn = - PhiBlock.addLiveIn(physical(rcc::test::TestRegister::G0), rcc::LaneMask::fromRaw(0x1)); - rcc::RegisterOperandFlags KillFlags; - KillFlags.set(rcc::RegisterOperandFlag::Kill); - rcc::MachineIRBuilder Builder(*Fixture->Function, Target); - auto Point = Builder.setInsertPoint(PhiBlock); - auto Pending = Point ? Builder.buildInstr(rcc::opcode(rcc::GenericOpcode::PHI)) - : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())}; - auto Def = Pending ? Pending->addDef(*Destination) - : rcc::Expected<void>{std::unexpected(Pending.error())}; - auto Use = - Def ? Pending->addUse(*Source, KillFlags) : rcc::Expected<void>{std::unexpected(Def.error())}; - auto Incoming = - Use ? Pending->addBasicBlock(Predecessor) : rcc::Expected<void>{std::unexpected(Use.error())}; - auto Phi = Incoming ? Pending->build() - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Incoming.error())}; - if (!LiveIn || !Phi) { - Context.expect(false, "malformed-edge PHI setup must succeed"); - return; - } - - const std::vector<rcc::MachineBasicBlockLiveIn> OriginalLiveIns(PhiBlock.liveIns().begin(), - PhiBlock.liveIns().end()); - const rcc::RegisterOperandFlags OriginalFlags = (*Phi)->operandAt(1)->registerFlags(); - auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, Target); - Context.expect(!Rebuilt && Rebuilt.error().code() == rcc::ErrorCode::VerificationError && - std::ranges::equal(PhiBlock.liveIns(), OriginalLiveIns) && - (*Phi)->operandAt(1)->registerFlags() == OriginalFlags, - "malformed PHI edges must fail without changing live-ins or operand flags"); -} - -class DummyAnalysis final { -public: - struct Result final {}; - - [[nodiscard]] static rcc::Expected<Result> - run(rcc::MachineFunction &, const rcc::TargetDescription &, rcc::MachineAnalysisManager &) { - return Result{}; - } -}; - -void testAnalysisRegistrationAndInvalidation(TestContext &Context, - const rcc::TargetDescription &Target) { - auto Fixture = createFunction("analysis-invalidation", 7, 1); - if (!Fixture) { - Context.expect(false, "analysis-invalidation fixture creation must succeed"); - return; - } - auto Reg = createVReg(*Fixture->Function); - auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; - auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; - if (!Reg || !Def || !Use) { - Context.expect(false, "analysis-invalidation instructions must be built"); - return; - } - - rcc::MachineAnalysisManager Analyses; - auto FirstRegistration = rcc::registerStage11MachineAnalyses(Analyses); - auto SecondRegistration = rcc::registerStage11MachineAnalyses(Analyses); - auto Intervals = FirstRegistration - ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(FirstRegistration.error())}; - Context.expect(FirstRegistration && SecondRegistration && Intervals && - Analyses.cachedResultCount(*Fixture->Function) == 3, - "Stage 11 analyses must register idempotently and materialize dependencies"); - Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), - {rcc::MachinePassChange::Frame}); - Context.expect(Analyses.cachedResultCount(*Fixture->Function) == 3, - "debug-only changes must preserve all liveness analyses"); - Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), - {rcc::MachinePassChange::Operands}); - Context.expect( - Analyses.cachedResultCount(*Fixture->Function) == 1 && - Analyses.hasCached(*Fixture->Function, - rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()), - "operand changes must retain SlotIndexes while invalidating liveness dependents"); - auto Recomputed = Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, Target); - Context.expect(Recomputed && Analyses.cachedResultCount(*Fixture->Function) == 3, - "invalidated liveness dependencies must recompute on demand"); - Analyses.invalidate(*Fixture->Function, rcc::PreservedAnalyses::none(), - {rcc::MachinePassChange::BlockLayout}); - Context.expect( - Analyses.cachedResultCount(*Fixture->Function) == 1 && - Analyses.hasCached(*Fixture->Function, - rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()), - "layout changes must invalidate SlotIndexes and LiveIntervals only"); - - rcc::MachineAnalysisManager Atomic; - rcc::MachineAnalysisRegistration DummyRegistration; - DummyRegistration.Name = "SlotIndexes"; - auto Dummy = Atomic.registerAnalysis<DummyAnalysis>(std::move(DummyRegistration)); - auto Rejected = rcc::registerStage11MachineAnalyses(Atomic); - Context.expect( - Dummy && !Rejected && Atomic.isRegistered(rcc::MachineAnalysisManager::id<DummyAnalysis>()) && - !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::SlotIndexesAnalysis>()) && - !Atomic.isRegistered(rcc::MachineAnalysisManager::id<rcc::LiveVariablesAnalysis>()), - "failed standard-analysis registration must leave the manager unchanged"); -} - -void testRISCVLiveness(TestContext &Context) { - auto Target = rcc::riscv::createTargetDescription(); - auto Fixture = createFunction("riscv-liveness", 8, 1); - if (!Target || !Fixture) { - Context.expect(false, "RV64GC liveness fixture creation must succeed"); - return; - } - auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5); - auto X6 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X6); - auto X7 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X7); - if (!X5 || !X6 || !X7) { - Context.expect(false, "RV64GC physical registers must resolve"); - return; - } - auto BuildADDI = [&](rcc::PhysicalRegister Destination, rcc::PhysicalRegister Source, - std::int64_t Immediate) -> rcc::Expected<rcc::MachineInstr *> { - rcc::MachineIRBuilder Builder(*Fixture->Function, *Target); - auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]); - if (!Point) - return std::unexpected(Point.error()); - auto Pending = Builder.buildInstr( - rcc::Opcode::fromValue(static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))); - if (!Pending) - return std::unexpected(Pending.error()); - auto Def = Pending->addDef(rcc::Register::fromPhysical(Destination)); - if (!Def) - return std::unexpected(Def.error()); - auto Use = Pending->addUse(rcc::Register::fromPhysical(Source)); - if (!Use) - return std::unexpected(Use.error()); - auto Imm = Pending->addImmediate(Immediate); - if (!Imm) - return std::unexpected(Imm.error()); - return Pending->build(); - }; - auto First = BuildADDI(*X6, *X5, 1); - auto Second = BuildADDI(*X7, *X6, 2); - if (!First || !Second) { - Context.expect(false, "RV64GC ADDI instructions must be built"); - return; - } - rcc::MachineAnalysisManager Analyses; - auto Registered = rcc::registerStage11MachineAnalyses(Analyses); - auto Intervals = Registered - ? Analyses.getResult<rcc::LiveIntervalsAnalysis>(*Fixture->Function, *Target) - : rcc::Expected<rcc::LiveIntervalsAnalysis::Result *>{ - std::unexpected(Registered.error())}; - const auto Unit = - rcc::RegisterUnitID::fromValue(static_cast<std::uint32_t>(rcc::riscv::RegisterUnit::U_X6)); - Context.expect(Intervals && (*Intervals)->regUnitRange(Unit) != nullptr && - (*Intervals)->regUnitRange(Unit)->segments().size() == 1, - "production RV64GC register units must participate in LiveIntervals"); -} - -void testRISCVReservedRegisterLiveness(TestContext &Context) { - auto Target = rcc::riscv::createTargetDescription(); - auto Fixture = createFunction("riscv-reserved-liveness", 10, 1); - if (!Target || !Fixture) { - Context.expect(false, "RV64GC reserved-register liveness fixture creation must succeed"); - return; - } - auto X0 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X0); - auto X5 = rcc::riscv::physicalRegister(rcc::riscv::PhysicalRegisterID::X5); - if (!X0 || !X5) { - Context.expect(false, "RV64GC reserved-register fixture registers must resolve"); - return; - } - - rcc::MachineIRBuilder Builder(*Fixture->Function, *Target); - auto Point = Builder.setInsertPoint(*Fixture->Blocks[0]); - auto Pending = Point ? Builder.buildInstr(rcc::Opcode::fromValue( - static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))) - : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Point.error())}; - auto Def = Pending ? Pending->addDef(rcc::Register::fromPhysical(*X5)) - : rcc::Expected<void>{std::unexpected(Pending.error())}; - auto Use = Def ? Pending->addUse(rcc::Register::fromPhysical(*X0)) - : rcc::Expected<void>{std::unexpected(Def.error())}; - auto Immediate = - Use ? Pending->addImmediate(1) : rcc::Expected<void>{std::unexpected(Use.error())}; - auto Instruction = Immediate - ? Pending->build() - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Immediate.error())}; - auto DeadDef = - Instruction ? Builder.buildInstr(rcc::Opcode::fromValue( - static_cast<std::uint32_t>(rcc::riscv::InstructionOpcode::ADDI))) - : rcc::Expected<rcc::MachineInstrBuilder>{std::unexpected(Instruction.error())}; - auto DeadDefDestination = DeadDef ? DeadDef->addDef(rcc::Register::fromPhysical(*X0)) - : rcc::Expected<void>{std::unexpected(DeadDef.error())}; - auto DeadDefSource = DeadDefDestination - ? DeadDef->addUse(rcc::Register::fromPhysical(*X0)) - : rcc::Expected<void>{std::unexpected(DeadDefDestination.error())}; - auto DeadDefImmediate = DeadDefSource - ? DeadDef->addImmediate(0) - : rcc::Expected<void>{std::unexpected(DeadDefSource.error())}; - auto DeadDefInstruction = - DeadDefImmediate - ? DeadDef->build() - : rcc::Expected<rcc::MachineInstr *>{std::unexpected(DeadDefImmediate.error())}; - if (!Instruction || !DeadDefInstruction) { - Context.expect(false, "RV64GC reserved-register liveness instruction must be built"); - return; - } - - auto Rebuilt = rcc::rebuildMachineLiveness(*Fixture->Function, *Target); - const rcc::MachineOperand *ZeroUse = (*Instruction)->operandAt(1); - const rcc::MachineOperand *ZeroDef = (*DeadDefInstruction)->operandAt(0); - const rcc::MachineOperand *DeadDefZeroUse = (*DeadDefInstruction)->operandAt(1); - Context.expect(Rebuilt && Fixture->Blocks[0]->liveIns().empty() && ZeroUse != nullptr && - !ZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill) && - ZeroDef != nullptr && - ZeroDef->registerFlags().has(rcc::RegisterOperandFlag::Dead) && - DeadDefZeroUse != nullptr && - !DeadDefZeroUse->registerFlags().has(rcc::RegisterOperandFlag::Kill), - "reserved uses must remain available while dead defs retain precise liveness"); -} - -} // namespace - -int main() { - TestContext Context; - auto Target = createTarget(); - Context.expect(Target.has_value(), "liveness TestTarget must be created"); - if (!Target) - return Context.result(); - - testLiveRange(Context); - testSlotIndexes(Context, *Target); - testCFGAndValueNumbers(Context, *Target); - testLaneSubrangesAndEarlyClobber(Context, *Target); - testPhysicalUnitsAndRegMasks(Context, *Target); - testLivenessRebuildAndVerifier(Context, *Target); - testTrackedLiveThroughPhysicalRegister(Context, *Target); - testFailedRebuildIsAtomic(Context, *Target); - testAnalysisRegistrationAndInvalidation(Context, *Target); - testRISCVLiveness(Context); - testRISCVReservedRegisterLiveness(Context); - return Context.result(); -} diff --git a/backend/unittests/CodeGen/MachineOptimizationTest.cpp b/backend/unittests/CodeGen/MachineOptimizationTest.cpp index f4233f8..d246e39 100644 --- a/backend/unittests/CodeGen/MachineOptimizationTest.cpp +++ b/backend/unittests/CodeGen/MachineOptimizationTest.cpp @@ -2,6 +2,7 @@ #include "RISCV.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineCFGUpdater.h" #include "rcc/CodeGen/MachineCSE.h" @@ -11,7 +12,6 @@ #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineLICM.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineMemoryFolding.h" #include "rcc/CodeGen/MachineOperand.h" diff --git a/backend/unittests/CodeGen/MachineSchedulingTest.cpp b/backend/unittests/CodeGen/MachineSchedulingTest.cpp index 83f7000..bcd4100 100644 --- a/backend/unittests/CodeGen/MachineSchedulingTest.cpp +++ b/backend/unittests/CodeGen/MachineSchedulingTest.cpp @@ -1,11 +1,11 @@ // SPDX-License-Identifier: GPL-3.0-or-later #include "RISCV.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/MachineScheduler.h" #include "rcc/CodeGen/PostRAScheduler.h" diff --git a/backend/unittests/CodeGen/RegisterAllocationTest.cpp b/backend/unittests/CodeGen/RegisterAllocationTest.cpp index a44cd2e..1a7c5c7 100644 --- a/backend/unittests/CodeGen/RegisterAllocationTest.cpp +++ b/backend/unittests/CodeGen/RegisterAllocationTest.cpp @@ -2,15 +2,16 @@ #include "Target/TestTarget.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRangeEdit.h" #include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineCFGUpdater.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachinePass.h" diff --git a/backend/unittests/CodeGen/RegisterAllocationTestSupport.h b/backend/unittests/CodeGen/RegisterAllocationTestSupport.h index 5a3bae2..49c9e8a 100644 --- a/backend/unittests/CodeGen/RegisterAllocationTestSupport.h +++ b/backend/unittests/CodeGen/RegisterAllocationTestSupport.h @@ -7,12 +7,13 @@ #include "Target/TestTarget.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/RegAllocFast.h" #include "rcc/CodeGen/RegAllocPBQP.h" #include "rcc/CodeGen/Spiller.h" diff --git a/backend/unittests/CodeGen/SSAExitTestSupport.h b/backend/unittests/CodeGen/SSAExitTestSupport.h index a5eeff1..5729293 100644 --- a/backend/unittests/CodeGen/SSAExitTestSupport.h +++ b/backend/unittests/CodeGen/SSAExitTestSupport.h @@ -7,11 +7,11 @@ #include "Target/TestTarget.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/unittests/CodeGen/SlotIndexesTest.cpp b/backend/unittests/CodeGen/SlotIndexesTest.cpp new file mode 100644 index 0000000..d34ff84 --- /dev/null +++ b/backend/unittests/CodeGen/SlotIndexesTest.cpp @@ -0,0 +1,93 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/SlotIndexes.h" + +#include "LiveTestSupport.h" +#include "rcc/CodeGen/LiveVariables.h" + +namespace { + +using namespace rcc::test::liveness; + +void testSlotIndexes(TestContext &Context, const rcc::TargetDescription &Target) { + auto Fixture = createFunction("slot-indexes", 1, 1); + if (!Fixture) { + Context.expect(false, "SlotIndexes fixture creation must succeed"); + return; + } + auto Reg = createVReg(*Fixture->Function); + auto Def = Reg ? buildDef(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; + auto Use = Reg ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Reg.error())}; + if (!Reg || !Def || !Use) { + Context.expect(false, "SlotIndexes instructions must be built"); + return; + } + + rcc::MachineAnalysisManager Analyses; + auto Registered = rcc::registerStage11MachineAnalyses(Analyses); + auto Indexes = + Registered + ? Analyses.getResult<rcc::SlotIndexesAnalysis>(*Fixture->Function, Target) + : rcc::Expected<rcc::SlotIndexesAnalysis::Result *>{std::unexpected(Registered.error())}; + if (!Indexes) { + Context.expect(false, "SlotIndexes analysis must materialize"); + return; + } + const rcc::SlotIndex DefIndex = (*Indexes)->instructionIndex(**Def); + const rcc::SlotIndex UseIndex = (*Indexes)->instructionIndex(**Use); + Context.expect((*Indexes)->blockStart(*Fixture->Blocks[0]) < DefIndex.earlyClobberSlot() && + DefIndex.earlyClobberSlot() < DefIndex && DefIndex < DefIndex.deadSlot() && + DefIndex.deadSlot() < UseIndex && + UseIndex < (*Indexes)->blockEnd(*Fixture->Blocks[0]), + "SlotIndexes must order block, early-clobber, register, and dead slots"); + Context.expect((*Indexes)->instructionFromIndex(DefIndex.deadSlot()) == *Def && + (*Indexes)->blockFromIndex(UseIndex) == Fixture->Blocks[0], + "SlotIndexes reverse mappings must accept every instruction subslot"); + + auto Inserted = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Use); + Context.expect(Inserted && (*Indexes)->insertInstruction(**Inserted).has_value(), + "local SlotIndex insertion must use reserved numbering space"); + if (Inserted) { + const rcc::SlotIndex InsertedIndex = (*Indexes)->instructionIndex(**Inserted); + Context.expect(DefIndex < InsertedIndex && InsertedIndex < UseIndex, + "locally inserted SlotIndex must lie between adjacent instructions"); + Context.expect((*Indexes)->eraseInstruction(**Inserted).has_value() && + !(*Indexes)->instructionIndex(**Inserted).isValid() && + (*Indexes)->renumber(*Fixture->Function).has_value() && + (*Indexes)->instructionIndex(**Inserted).isValid(), + "SlotIndex erasure and full renumbering must rebuild exact mappings"); + + auto Second = buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Inserted); + auto SecondIndexed = Second ? (*Indexes)->insertInstruction(**Second) + : rcc::Expected<void>{std::unexpected(Second.error())}; + auto Third = Second + ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Second) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Second.error())}; + auto ThirdIndexed = Third ? (*Indexes)->insertInstruction(**Third) + : rcc::Expected<void>{std::unexpected(Third.error())}; + auto Exhausted = + Third ? buildUse(*Fixture->Function, Target, *Fixture->Blocks[0], *Reg, {}, *Third) + : rcc::Expected<rcc::MachineInstr *>{std::unexpected(Third.error())}; + auto ExhaustedIndex = Exhausted ? (*Indexes)->insertInstruction(**Exhausted) + : rcc::Expected<void>{std::unexpected(Exhausted.error())}; + Context.expect(SecondIndexed && ThirdIndexed && Exhausted && !ExhaustedIndex && + ExhaustedIndex.error().code() == rcc::ErrorCode::Unsupported && + (*Indexes)->renumber(*Fixture->Function).has_value() && + (*Indexes)->instructionIndex(**Exhausted).isValid(), + "local SlotIndex exhaustion must request and recover through full renumbering"); + } +} + +} // namespace + +int main() { + TestContext Context; + auto Target = createTarget(); + Context.expect(Target.has_value(), "liveness TestTarget must be created"); + if (!Target) + return Context.result(); + testSlotIndexes(Context, *Target); + return Context.result(); +} diff --git a/backend/unittests/Target/RISCVLateCodeGenTest.cpp b/backend/unittests/Target/RISCVLateCodeGenTest.cpp index 92fbc55..702f058 100644 --- a/backend/unittests/Target/RISCVLateCodeGenTest.cpp +++ b/backend/unittests/Target/RISCVLateCodeGenTest.cpp @@ -3,6 +3,7 @@ #include "RISCV.h" #include "RISCVInstrInfo.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBlockPlacement.h" #include "rcc/CodeGen/MachineBranchOptimization.h" @@ -14,7 +15,6 @@ #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemoryFolding.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineOptimizationPipeline.h" diff --git a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp index ad81615..0e60e63 100644 --- a/backend/unittests/Target/RISCVRegisterAllocationTest.cpp +++ b/backend/unittests/Target/RISCVRegisterAllocationTest.cpp @@ -1,13 +1,14 @@ // SPDX-License-Identifier: GPL-3.0-or-later #include "RISCV.h" +#include "rcc/CodeGen/LiveIntervals.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachinePass.h" diff --git a/backend/unittests/Target/RISCVSSAExitTest.cpp b/backend/unittests/Target/RISCVSSAExitTest.cpp index 3f81d1d..ab30572 100644 --- a/backend/unittests/Target/RISCVSSAExitTest.cpp +++ b/backend/unittests/Target/RISCVSSAExitTest.cpp @@ -3,12 +3,12 @@ #include "RISCV.h" #include "RISCVInstrInfo.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineCFGUpdater.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachinePass.h" #include "rcc/CodeGen/MachineVerifier.h" |