From e5fdceb9b869f010a2a75638fd38aaf1867f3008 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 9 Aug 2026 04:40:17 +0800 Subject: [CodeGen] Complete register allocation infrastructure --- backend/lib/CodeGen/LiveRegMatrix.cpp | 330 ++++++++++++++++++++++++++++++++++ 1 file changed, 330 insertions(+) create mode 100644 backend/lib/CodeGen/LiveRegMatrix.cpp (limited to 'backend/lib/CodeGen/LiveRegMatrix.cpp') diff --git a/backend/lib/CodeGen/LiveRegMatrix.cpp b/backend/lib/CodeGen/LiveRegMatrix.cpp new file mode 100644 index 0000000..64c7046 --- /dev/null +++ b/backend/lib/CodeGen/LiveRegMatrix.cpp @@ -0,0 +1,330 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegMatrix.h" + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] std::optional relevantLanes(const LiveInterval &Interval, + RegisterUnitLane Unit) noexcept { + if (Interval.SubRanges.empty()) + return Unit.Lanes; + LaneMask Result; + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (SubRange.Lanes.intersects(Unit.Lanes)) + Result = Result | (SubRange.Lanes & Unit.Lanes); + } + if (Result.empty()) + return std::nullopt; + return Result; +} + +[[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 intervalUnitLanes(const LiveInterval &Interval, + RegisterUnitLane Unit) noexcept { + if (Interval.SubRanges.empty()) + return normalizeUnitLanes(Unit.Lanes, Unit.Lanes); + LaneMask Result; + for (const LiveSubRange &SubRange : Interval.SubRanges) + Result = Result | normalizeUnitLanes(Unit.Lanes, SubRange.Lanes); + return Result; +} + +[[nodiscard]] bool intervalLiveAtFixedRegister(const LiveInterval &Interval, + const PhysicalRegisterDesc &Candidate, + const PhysicalRegisterDesc &Fixed, + SlotIndex Position) noexcept { + for (const RegisterUnitLane CandidateUnit : Candidate.Units) { + const auto FixedUnit = + std::ranges::find(Fixed.Units, CandidateUnit.Unit, &RegisterUnitLane::Unit); + if (FixedUnit == Fixed.Units.end()) + continue; + const LaneMask FixedLanes = normalizeUnitLanes(FixedUnit->Lanes, FixedUnit->Lanes); + if (Interval.SubRanges.empty()) { + if (normalizeUnitLanes(CandidateUnit.Lanes, CandidateUnit.Lanes).intersects(FixedLanes) && + Interval.MainRange.liveAt(Position)) { + return true; + } + continue; + } + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (normalizeUnitLanes(CandidateUnit.Lanes, SubRange.Lanes).intersects(FixedLanes) && + SubRange.Range.liveAt(Position)) { + return true; + } + } + } + return false; +} + +[[nodiscard]] bool rangeForUnitOverlaps(const LiveInterval &Interval, RegisterUnitLane Unit, + const LiveRange &Other) noexcept { + if (!relevantLanes(Interval, Unit)) + return false; + if (Interval.SubRanges.empty()) + return Interval.MainRange.overlaps(Other); + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (SubRange.Lanes.intersects(Unit.Lanes) && SubRange.Range.overlaps(Other)) + return true; + } + return false; +} + +} // namespace + +bool regalloc_detail::intervalsOverlapOnPhysicalRegisters( + const LiveInterval &Left, PhysicalRegister LeftReg, const LiveInterval &Right, + PhysicalRegister RightReg, const TargetRegisterInfo &Registers) noexcept { + const PhysicalRegisterDesc *LeftDescription = Registers.physicalRegister(LeftReg); + const PhysicalRegisterDesc *RightDescription = Registers.physicalRegister(RightReg); + if (LeftDescription == nullptr || RightDescription == nullptr) + return true; + for (const RegisterUnitLane LeftUnit : LeftDescription->Units) { + for (const RegisterUnitLane RightUnit : RightDescription->Units) { + if (LeftUnit.Unit != RightUnit.Unit) + continue; + const LaneMask LeftUnitLanes = intervalUnitLanes(Left, LeftUnit); + const LaneMask RightUnitLanes = intervalUnitLanes(Right, RightUnit); + if (!LeftUnitLanes.intersects(RightUnitLanes)) + continue; + if (Left.SubRanges.empty() && Right.SubRanges.empty()) + return Left.MainRange.overlaps(Right.MainRange); + const auto LeftRanges = Left.SubRanges.empty() + ? std::span{} + : std::span(Left.SubRanges); + const auto RightRanges = Right.SubRanges.empty() + ? std::span{} + : std::span(Right.SubRanges); + if (LeftRanges.empty()) { + for (const LiveSubRange &RightRange : RightRanges) { + const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes); + if (LeftUnitLanes.intersects(RightRangeLanes) && + Left.MainRange.overlaps(RightRange.Range)) + return true; + } + continue; + } + if (RightRanges.empty()) { + for (const LiveSubRange &LeftRange : LeftRanges) { + const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes); + if (LeftRangeLanes.intersects(RightUnitLanes) && + LeftRange.Range.overlaps(Right.MainRange)) + return true; + } + continue; + } + for (const LiveSubRange &LeftRange : LeftRanges) { + const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes); + if (LeftRangeLanes.empty()) + continue; + for (const LiveSubRange &RightRange : RightRanges) { + const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes); + if (LeftRangeLanes.intersects(RightRangeLanes) && + LeftRange.Range.overlaps(RightRange.Range)) + return true; + } + } + } + } + return false; +} + +bool LiveRegMatrix::intervalOverlapsUnit(const LiveInterval &Interval, RegisterUnitLane Unit, + const LiveRange &UnitRange) const noexcept { + return rangeForUnitOverlaps(Interval, Unit, UnitRange); +} + +bool LiveRegMatrix::intervalsOverlapOnCandidates(const LiveInterval &Left, PhysicalRegister LeftReg, + const LiveInterval &Right, + PhysicalRegister RightReg) const noexcept { + return regalloc_detail::intervalsOverlapOnPhysicalRegisters(Left, LeftReg, Right, RightReg, + Target->registers()); +} + +std::vector +LiveRegMatrix::collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const { + std::vector Result; + const LiveInterval *Interval = Intervals->interval(VirtualReg); + const PhysicalRegisterDesc *Candidate = Target->registers().physicalRegister(PhysicalReg); + if (Interval == nullptr || Candidate == nullptr) + return Result; + + for (const MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const SlotIndex Position = Intervals->slot(*Instruction); + if (!Position.isValid()) + continue; + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isPhysical()) + continue; + const auto Fixed = Reg->physicalRegister(); + if (!Fixed) + continue; + const PhysicalRegister FixedReg = Fixed.value(); + if (!Target->registers().regsOverlap(FixedReg, PhysicalReg)) + continue; + const PhysicalRegisterDesc *FixedDescription = + Target->registers().physicalRegister(FixedReg); + if (FixedDescription == nullptr) + continue; + const SlotIndex OperandPosition = + Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber) + ? Position.earlyClobberSlot() + : Position.registerSlot(); + if (intervalLiveAtFixedRegister(*Interval, *Candidate, *FixedDescription, + OperandPosition)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::FixedRegister, + std::nullopt, FixedReg, std::nullopt, + Instruction->stableID()}); + } + } + } + } + + for (const RegMaskPosition &Mask : Intervals->regMaskPositions()) { + if (Mask.Mask && Mask.Mask->clobbers(PhysicalReg) && + Interval->MainRange.liveAt(Mask.Position)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterMask, std::nullopt, + std::nullopt, std::nullopt, Mask.Instruction}); + } + } + + for (const RegisterUnitLane Unit : Candidate->Units) { + const LiveRange *FixedRange = Intervals->regUnitRange(Unit.Unit); + if (FixedRange != nullptr && intervalOverlapsUnit(*Interval, Unit, *FixedRange)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterUnit, std::nullopt, + std::nullopt, Unit.Unit, std::nullopt}); + } + } + + for (const auto &[OtherReg, OtherPhysical] : OrderedAssignments) { + if (OtherReg == VirtualReg) + continue; + const LiveInterval *OtherInterval = Intervals->interval(OtherReg); + if (OtherInterval != nullptr && + intervalsOverlapOnCandidates(*Interval, PhysicalReg, *OtherInterval, OtherPhysical)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::VirtualRegister, OtherReg, + std::nullopt, std::nullopt, std::nullopt}); + } + } + + std::ranges::sort( + Result, [](const RegisterInterference &Left, const RegisterInterference &Right) { + return std::tuple{Left.Kind, Left.VirtualReg.value_or(Register{}).opaqueValue(), + Left.FixedReg.value_or(PhysicalRegister{}).number(), + Left.Unit ? Left.Unit->value() : 0U, + Left.Instruction ? Left.Instruction->value() : 0ULL} < + std::tuple{Right.Kind, Right.VirtualReg.value_or(Register{}).opaqueValue(), + Right.FixedReg.value_or(PhysicalRegister{}).number(), + Right.Unit ? Right.Unit->value() : 0U, + Right.Instruction ? Right.Instruction->value() : 0ULL}; + }); + Result.erase(std::unique(Result.begin(), Result.end(), + [](const RegisterInterference &Left, const RegisterInterference &Right) { + return Left.Kind == Right.Kind && + Left.VirtualReg == Right.VirtualReg && + Left.FixedReg == Right.FixedReg && Left.Unit == Right.Unit && + Left.Instruction == Right.Instruction; + }), + Result.end()); + return Result; +} + +RegisterInterference LiveRegMatrix::checkInterference(Register VirtualReg, + PhysicalRegister PhysicalReg) const noexcept { + const std::vector Values = collectInterferences(VirtualReg, PhysicalReg); + if (Values.empty()) + return {}; + return Values.front(); +} + +Expected LiveRegMatrix::assign(Register VirtualReg, PhysicalRegister PhysicalReg) { + if (!VirtualReg.isVirtual() || Intervals->interval(VirtualReg) == nullptr || + Target->registers().physicalRegister(PhysicalReg) == nullptr) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "LiveRegMatrix assignment requires a known interval and physical register"); + } + if (regalloc_detail::isUnavailablePhysicalRegister(*Function, Target->registers(), PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix cannot assign an unavailable physical register"); + } + auto Info = Function->registerInfo().virtualRegisterInfo(VirtualReg); + if (!Info) + return std::unexpected(Info.error()); + const auto ClassID = Info->get().RegClass; + if (ClassID) { + if (!Target->registers().registerClassContains(ClassID.value(), PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix assignment is outside the virtual register class"); + } + } + if (!regalloc_detail::candidateSupportsSubRegisters(*Function, Target->registers(), VirtualReg, + PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix assignment lacks a required subregister view"); + } + if (Assignments.contains(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is already assigned"); + const RegisterInterference Interference = checkInterference(VirtualReg, PhysicalReg); + if (Interference.Kind != RegisterInterferenceKind::Free) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "physical register assignment has live interference"); + } + Assignments.emplace(VirtualReg, PhysicalReg); + OrderedAssignments.emplace_back(VirtualReg, PhysicalReg); + std::ranges::sort(OrderedAssignments, [](const auto &Left, const auto &Right) { + return Left.first.opaqueValue() < Right.first.opaqueValue(); + }); + return {}; +} + +Expected LiveRegMatrix::unassign(Register VirtualReg) { + if (!Assignments.erase(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is not assigned"); + std::erase_if(OrderedAssignments, + [VirtualReg](const auto &Entry) { return Entry.first == VirtualReg; }); + return {}; +} + +std::optional LiveRegMatrix::assignment(Register VirtualReg) const noexcept { + const auto Position = Assignments.find(VirtualReg); + if (Position == Assignments.end()) + return std::nullopt; + return Position->second; +} + +} // namespace rcc -- cgit v1.2.3