From a2f8d7c5e22b510965327383410bd576f7cf28e7 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Thu, 13 Aug 2026 04:17:52 +0800 Subject: [CodeGen] Split machine liveness components --- backend/lib/CodeGen/CMakeLists.txt | 29 +- .../lib/CodeGen/GlobalISel/InstructionSelect.cpp | 2 +- backend/lib/CodeGen/GlobalISel/Legalizer.cpp | 2 +- backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp | 2 +- backend/lib/CodeGen/LiveInterval.cpp | 184 ++ backend/lib/CodeGen/LiveIntervals.cpp | 421 +++++ backend/lib/CodeGen/LivePhysRegs.cpp | 174 ++ backend/lib/CodeGen/LiveRegUnits.cpp | 280 +++ backend/lib/CodeGen/LiveVariables.cpp | 1031 +++++++++++ backend/lib/CodeGen/MachineBranchOptimization.cpp | 2 +- backend/lib/CodeGen/MachineBranchRelaxation.cpp | 2 +- backend/lib/CodeGen/MachineCSE.cpp | 2 +- backend/lib/CodeGen/MachineCombiner.cpp | 2 +- backend/lib/CodeGen/MachineCopyPropagation.cpp | 2 +- backend/lib/CodeGen/MachineDCE.cpp | 2 +- backend/lib/CodeGen/MachineFallthrough.cpp | 4 +- backend/lib/CodeGen/MachineLICM.cpp | 2 +- backend/lib/CodeGen/MachineLiveness.cpp | 1942 -------------------- .../lib/CodeGen/MachineOptimizationPipeline.cpp | 2 +- backend/lib/CodeGen/MachinePseudoExpansion.cpp | 2 +- backend/lib/CodeGen/MachineScheduler.cpp | 2 +- backend/lib/CodeGen/MachineSchedulerInternal.h | 2 +- backend/lib/CodeGen/MachineSink.cpp | 2 +- backend/lib/CodeGen/MachineTailDuplication.cpp | 2 +- backend/lib/CodeGen/MachineTailMerge.cpp | 2 +- backend/lib/CodeGen/MachineVerifier.cpp | 2 +- backend/lib/CodeGen/PHIElimination.cpp | 2 +- backend/lib/CodeGen/PostRAScheduler.cpp | 218 +-- backend/lib/CodeGen/PrologueEpilogueInsertion.cpp | 2 +- backend/lib/CodeGen/RegAllocBase.cpp | 2 +- backend/lib/CodeGen/RegAllocBase.h | 2 +- backend/lib/CodeGen/RegAllocBasic.cpp | 3 +- backend/lib/CodeGen/RegAllocFast.cpp | 2 +- backend/lib/CodeGen/RegAllocInternal.h | 2 +- backend/lib/CodeGen/RegAllocPBQP.cpp | 3 +- backend/lib/CodeGen/RegisterPressure.cpp | 2 +- backend/lib/CodeGen/SlotIndexes.cpp | 159 ++ backend/lib/CodeGen/TwoAddressInstructionPass.cpp | 2 +- backend/lib/CodeGen/VirtRegMap.cpp | 3 +- 39 files changed, 2309 insertions(+), 2194 deletions(-) create mode 100644 backend/lib/CodeGen/LiveInterval.cpp create mode 100644 backend/lib/CodeGen/LiveIntervals.cpp create mode 100644 backend/lib/CodeGen/LivePhysRegs.cpp create mode 100644 backend/lib/CodeGen/LiveRegUnits.cpp create mode 100644 backend/lib/CodeGen/LiveVariables.cpp delete mode 100644 backend/lib/CodeGen/MachineLiveness.cpp create mode 100644 backend/lib/CodeGen/SlotIndexes.cpp (limited to 'backend/lib') 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 +#include +#include +#include +#include + +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 LiveRange::createValue(SlotIndex Definition, LiveValueState State, + std::optional Origin) { + if (!Definition.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); + if (Values.size() >= std::numeric_limits::max()) + return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); + const LiveValueNumberID ID = + LiveValueNumberID::fromValue(static_cast(Values.size() + 1U)); + Values.push_back({ID, Definition, State, Origin}); + return ID; +} + +Expected 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 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 LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { + return addSegment({Start, End, Value}); +} + +Expected 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 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 LiveRange::shrinkToUses(std::span Uses) { + std::vector 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 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 LiveRange::verify() const { + std::unordered_set 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 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 +#include +#include +#include +#include +#include +#include + +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 Filter) noexcept { + return !Filter || Access.intersects(*Filter); +} + +struct InstructionRangeEvent final { + bool HasUse = false; + bool HasNormalDef = false; + bool HasEarlyDef = false; + bool HasRegMaskClobber = false; +}; + +[[nodiscard]] Expected +virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional Filter, + const MachineFunction &Function, const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + const Register *OperandReg = Operand.getIf(); + 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 unitRangeEvent(const MachineInstr &Instruction, + RegisterUnitID Unit, + std::optional Filter, + const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + if (Operand.isRegister()) { + const Register *Reg = Operand.getIf(); + 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(); + 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(); + 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 +[[nodiscard]] Expected +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 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 { + 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 virtualRegisterFullLanes(Register Reg, + const MachineFunction &Function, + const TargetDescription &Target) { + return virtualRegisterLanes(Reg, Function, Target); +} + +[[nodiscard]] Expected> +partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, + const TargetDescription &Target) { + auto Full = virtualRegisterFullLanes(Reg, Function, Target); + if (!Full) + return std::unexpected(Full.error()); + std::vector 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 Groups{*Full}; + for (const LaneMask Access : AccessMasks) { + std::vector 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 LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, + std::span 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()); +} + +Expected +LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Indexes = Analyses.getResult(Function, Target); + if (!Indexes) + return std::unexpected(Indexes.error()); + auto Variables = Analyses.getResult(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::max() - 10U + ? std::numeric_limits::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(); + 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 +#include +#include +#include + +namespace rcc { + +namespace { +struct OperandFlagUpdate final { + MachineOperand *Operand = nullptr; + RegisterOperandFlags Flags; +}; + +[[nodiscard]] bool intersects(const LiveRegUnits &Live, + const std::vector &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 &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.add(Unit.Unit, Unit.Lanes); +} + +void removeUnits(LiveRegUnits &Live, const std::vector &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.remove(Unit.Unit, Unit.Lanes); +} + +[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector &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> +buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, + const MachineBlockLiveness &Boundary) { + LiveRegUnits Live = Boundary.PhysicalLiveOut; + std::vector Updates; + for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *Mask = Operand.getIf(); + 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(); + 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(); + 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(); + 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(); + 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 repairPostRAMachineBlockLiveness(std::span Blocks, + const TargetDescription &Target, + const LiveVariablesAnalysis::Result &Liveness) { + std::vector 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 +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +template +void addLanes(std::unordered_map &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 +void removeLanes(std::unordered_map &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 +[[nodiscard]] LaneMask lanesFor(const std::unordered_map &Values, + KeyT Key) noexcept { + const auto Position = Values.find(Key); + return Position == Values.end() ? LaneMask{} : Position->second; +} + +template +[[nodiscard]] bool containsLanes(const std::unordered_map &Values, KeyT Key, + LaneMask Lanes) noexcept { + const LaneMask Present = lanesFor(Values, Key); + return !Present.empty() && Present.contains(Lanes); +} + +template +[[nodiscard]] bool intersectsLanes(const std::unordered_map &Values, KeyT Key, + LaneMask Lanes) noexcept { + return lanesFor(Values, Key).intersects(Lanes); +} + +template +void uniteLanes(std::unordered_map &Values, + const std::unordered_map &Other) { + for (const auto &[Key, Lanes] : Other) + addLanes(Values, Key, Lanes); +} + +template +void subtractLaneSets(std::unordered_map &Values, + const std::unordered_map &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::popcount(Lanes.rawValue())); + } + return Result; +} + +[[nodiscard]] Expected 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 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 virtualOperandLanes(const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf(); + 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> +physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { + const Register *Reg = Operand.getIf(); + const std::optional 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 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 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 Physical = Reg.physicalRegister(); + return Physical && (Function.registerInfo().isReserved(*Physical) || + Target.registers().isReservedRegister(*Physical)); +} + +[[nodiscard]] Expected 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 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/LiveVariables.cpp b/backend/lib/CodeGen/LiveVariables.cpp new file mode 100644 index 0000000..7323e0d --- /dev/null +++ b/backend/lib/CodeGen/LiveVariables.cpp @@ -0,0 +1,1031 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#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" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +template +void addLanes(std::unordered_map &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 +void removeLanes(std::unordered_map &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 +[[nodiscard]] LaneMask lanesFor(const std::unordered_map &Values, + KeyT Key) noexcept { + const auto Position = Values.find(Key); + return Position == Values.end() ? LaneMask{} : Position->second; +} + +template +[[nodiscard]] bool containsLanes(const std::unordered_map &Values, KeyT Key, + LaneMask Lanes) noexcept { + const LaneMask Present = lanesFor(Values, Key); + return !Present.empty() && Present.contains(Lanes); +} + +template +[[nodiscard]] bool intersectsLanes(const std::unordered_map &Values, KeyT Key, + LaneMask Lanes) noexcept { + return lanesFor(Values, Key).intersects(Lanes); +} + +template +void uniteLanes(std::unordered_map &Values, + const std::unordered_map &Other) { + for (const auto &[Key, Lanes] : Other) + addLanes(Values, Key, Lanes); +} + +template +void subtractLaneSets(std::unordered_map &Values, + const std::unordered_map &Other) { + for (const auto &[Key, Lanes] : Other) + removeLanes(Values, Key, Lanes); +} + +[[nodiscard]] Expected addOperandUse(RegisterLaneSet &VirtualUses, LiveRegUnits &PhysicalUses, + const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || Reg->isNoRegister() || Operand.isDebugUse() || + Operand.registerFlags().has(RegisterOperandFlag::Undef)) { + return {}; + } + if (Reg->isVirtual()) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + VirtualUses.add(*Reg, *Lanes); + return {}; + } + if (isReservedPhysicalRegister(*Reg, Function, Target)) + return {}; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + for (const PhysicalUnitAccess &Unit : *Units) + PhysicalUses.add(Unit.Unit, Unit.Lanes); + return {}; +} + +[[nodiscard]] Expected addOperandDef(RegisterLaneSet &VirtualDefs, LiveRegUnits &PhysicalDefs, + const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || Reg->isNoRegister()) + return {}; + if (Reg->isVirtual()) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + VirtualDefs.add(*Reg, *Lanes); + return {}; + } + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + for (const PhysicalUnitAccess &Unit : *Units) + PhysicalDefs.add(Unit.Unit, Unit.Lanes); + return {}; +} + +struct LivenessEdgeKey final { + const MachineBasicBlock *Predecessor = nullptr; + const MachineBasicBlock *Successor = nullptr; + + friend bool operator==(const LivenessEdgeKey &, const LivenessEdgeKey &) = default; +}; + +struct LivenessEdgeKeyHash final { + [[nodiscard]] std::size_t operator()(const LivenessEdgeKey &Key) const noexcept { + const std::size_t Left = std::hash{}(Key.Predecessor); + const std::size_t Right = std::hash{}(Key.Successor); + return Left ^ (Right + 0x9e3779b9U + (Left << 6U) + (Left >> 2U)); + } +}; + +struct EdgeLivenessUses final { + RegisterLaneSet Virtual; + LiveRegUnits Physical; +}; + +[[nodiscard]] Expected +computeLiveVariables(const MachineFunction &Function, const TargetDescription &Target) { + LiveVariablesAnalysis::Result Result; + std::vector Blocks; + std::unordered_map EdgeUses; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + Blocks.push_back(Block); + (void)Result.getOrCreateBlock(*Block); + } + + for (const MachineBasicBlock *Block : Blocks) { + MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); + if (Block == Function.firstBlock()) { + for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) { + const PhysicalRegisterDesc *Description = + Target.registers().physicalRegister(LiveIn.PhysReg); + if (Description == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "function live-in references an unknown physical register"); + } + addPhysicalRegister(Liveness.PhysicalUses, *Description); + if (LiveIn.InitialVirtualRegister) { + auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + Liveness.VirtualDefs.add(*LiveIn.InitialVirtualRegister, *Lanes); + } + } + } + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown instruction descriptor"); + } + const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); + if (IsPhi) { + if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered a malformed PHI instruction"); + } + std::unordered_set IncomingBlocks; + for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) { + const MachineOperand *Incoming = Instruction->operandAt(Index); + const MachineOperand *PredecessorOperand = Instruction->operandAt(Index + 1U); + const auto *Predecessor = PredecessorOperand == nullptr + ? nullptr + : PredecessorOperand->getIf(); + if (Incoming == nullptr || Predecessor == nullptr || Predecessor->Block == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered a malformed PHI incoming pair"); + } + const MachineBasicBlock *IncomingBlock = Predecessor->Block; + const bool HasPredecessor = std::ranges::find(Block->predecessors(), IncomingBlock) != + Block->predecessors().end(); + const bool HasSuccessor = std::ranges::any_of( + IncomingBlock->successors(), + [Block](const MachineSuccessor &Successor) { return Successor.Block == Block; }); + if (&IncomingBlock->function() != &Function || !IncomingBlock->isLinked() || + !HasPredecessor || !HasSuccessor || !IncomingBlocks.insert(IncomingBlock).second) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered a PHI incoming without a unique CFG edge"); + } + EdgeLivenessUses &Uses = EdgeUses[{IncomingBlock, Block}]; + auto Added = addOperandUse(Uses.Virtual, Uses.Physical, *Incoming, Function, Target); + if (!Added) + return std::unexpected(Added.error()); + } + } + + RegisterLaneSet InstructionVirtualUses; + RegisterLaneSet InstructionVirtualDefs; + LiveRegUnits InstructionPhysicalUses; + LiveRegUnits InstructionPhysicalDefs; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand &Operand = *Instruction->operandAt(Index); + if (Operand.isRegister()) { + if (Operand.isUse() && (!IsPhi || Index == 0)) { + auto Use = addOperandUse(InstructionVirtualUses, InstructionPhysicalUses, Operand, + Function, Target); + if (!Use) + return std::unexpected(Use.error()); + } + if (Operand.isDef()) { + auto Def = addOperandDef(InstructionVirtualDefs, InstructionPhysicalDefs, Operand, + Function, Target); + if (!Def) + return std::unexpected(Def.error()); + } + continue; + } + if (const auto *MaskOperand = Operand.getIf(); + MaskOperand != nullptr) { + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered a null register mask"); + auto Added = addRegisterMaskDefs(InstructionPhysicalDefs, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + continue; + } + if (const auto *MaskOperand = Operand.getIf(); + MaskOperand != nullptr) { + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered a null live-out register mask"); + auto Added = addRegisterMaskUses(InstructionPhysicalUses, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + } + } + + RegisterLaneSet NewVirtualUses = InstructionVirtualUses; + NewVirtualUses.subtract(Liveness.VirtualDefs); + Liveness.VirtualUses.unite(NewVirtualUses); + Liveness.VirtualDefs.unite(InstructionVirtualDefs); + + LiveRegUnits NewPhysicalUses = InstructionPhysicalUses; + NewPhysicalUses.subtract(Liveness.PhysicalDefs); + Liveness.PhysicalUses.unite(NewPhysicalUses); + Liveness.PhysicalDefs.unite(InstructionPhysicalDefs); + } + } + + bool Changed = true; + while (Changed) { + Changed = false; + for (const MachineBasicBlock *Block : Blocks | std::views::reverse) { + MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); + RegisterLaneSet VirtualOut; + LiveRegUnits PhysicalOut; + for (const MachineSuccessor &Successor : Block->successors()) { + if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an invalid CFG successor"); + } + const MachineBlockLiveness &SuccessorLiveness = *Result.block(*Successor.Block); + VirtualOut.unite(SuccessorLiveness.VirtualLiveIn); + PhysicalOut.unite(SuccessorLiveness.PhysicalLiveIn); + const auto Edge = EdgeUses.find({Block, Successor.Block}); + if (Edge != EdgeUses.end()) { + VirtualOut.unite(Edge->second.Virtual); + PhysicalOut.unite(Edge->second.Physical); + } + } + + RegisterLaneSet VirtualIn = VirtualOut; + VirtualIn.subtract(Liveness.VirtualDefs); + VirtualIn.unite(Liveness.VirtualUses); + LiveRegUnits PhysicalIn = PhysicalOut; + PhysicalIn.subtract(Liveness.PhysicalDefs); + PhysicalIn.unite(Liveness.PhysicalUses); + + if (VirtualOut != Liveness.VirtualLiveOut || VirtualIn != Liveness.VirtualLiveIn || + PhysicalOut != Liveness.PhysicalLiveOut || PhysicalIn != Liveness.PhysicalLiveIn) { + Liveness.VirtualLiveOut = std::move(VirtualOut); + Liveness.VirtualLiveIn = std::move(VirtualIn); + Liveness.PhysicalLiveOut = std::move(PhysicalOut); + Liveness.PhysicalLiveIn = std::move(PhysicalIn); + Changed = true; + } + } + } + return Result; +} +[[nodiscard]] Expected> +canonicalPhysicalLiveIns(const LiveRegUnits &Units, const TargetDescription &Target) { + struct Candidate final { + const PhysicalRegisterDesc *Description = nullptr; + LaneMask RegisterLanes; + LiveRegUnits Coverage; + std::size_t ExtraLanes = 0; + bool Selected = false; + }; + + std::vector Candidates; + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + const LaneMask FullLanes = physicalRegisterLanes(Description); + std::uint64_t SelectableLanes = 0; + LaneMask RelevantLanes; + for (const RegisterUnitLane &Unit : Description.Units) { + RelevantLanes = RelevantLanes | denormalizeUnitLanes(Units.lanes(Unit.Unit), Unit.Lanes); + } + std::uint64_t PendingLanes = RelevantLanes.rawValue(); + while (PendingLanes != 0) { + const std::uint64_t Lane = std::uint64_t{1} << std::countr_zero(PendingLanes); + const LiveRegUnits Coverage = physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane)); + if (isSubset(Coverage, Units)) + SelectableLanes |= Lane; + PendingLanes &= PendingLanes - 1U; + } + if (SelectableLanes == 0) + continue; + Candidate Value; + Value.Description = &Description; + Value.RegisterLanes = LaneMask::fromRaw(SelectableLanes); + Value.Coverage = physicalRegisterCoverage(Description, Value.RegisterLanes); + Value.ExtraLanes = static_cast(std::popcount(FullLanes.rawValue()) - + std::popcount(SelectableLanes)); + Candidates.push_back(std::move(Value)); + } + + LiveRegUnits Covered; + std::vector Result; + while (Covered != Units) { + Candidate *Best = nullptr; + std::size_t BestNewLanes = 0; + std::size_t BestCoverage = 0; + for (Candidate &Value : Candidates) { + if (Value.Selected) + continue; + LiveRegUnits NewCoverage = Value.Coverage; + NewCoverage.subtract(Covered); + const std::size_t NewLanes = laneCount(NewCoverage); + if (NewLanes == 0) + continue; + const std::size_t Coverage = laneCount(Value.Coverage); + if (Best == nullptr || NewLanes > BestNewLanes || + (NewLanes == BestNewLanes && Value.ExtraLanes < Best->ExtraLanes) || + (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes && + Coverage > BestCoverage) || + (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes && + Coverage == BestCoverage && + Value.Description->Reg.number() < Best->Description->Reg.number())) { + Best = &Value; + BestNewLanes = NewLanes; + BestCoverage = Coverage; + } + } + if (Best == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "physical live-in units cannot be represented by target registers"); + } + Best->Selected = true; + Covered.unite(Best->Coverage); + const LaneMask FullLanes = physicalRegisterLanes(*Best->Description); + const LaneMask Lanes = Best->RegisterLanes == FullLanes ? LaneMask::all() : Best->RegisterLanes; + Result.push_back({Best->Description->Reg, Lanes}); + } + std::ranges::sort(Result, + [](const MachineBasicBlockLiveIn &Left, const MachineBasicBlockLiveIn &Right) { + return Left.PhysReg.number() < Right.PhysReg.number(); + }); + return Result; +} + +[[nodiscard]] Expected liveInUnits(std::span LiveIns, + const TargetDescription &Target) { + LiveRegUnits Result; + for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) { + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg); + if (Description == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "block live-in references an unknown physical register"); + } + Result.unite(physicalRegisterCoverage(*Description, LiveIn.Lanes)); + } + return Result; +} + +struct OperandFlagPlan final { + MachineInstrStableID Instruction; + std::size_t OperandIndex = 0; + RegisterOperandFlags Original; + RegisterOperandFlags Rebuilt; + bool KillIsValid = false; + bool DeadIsValid = false; +}; + +struct BlockLivenessPlan final { + MachineBlockStableID Block; + std::vector OriginalLiveIns; + std::vector RebuiltLiveIns; +}; + +struct LivenessRebuildPlan final { + std::vector Blocks; + std::vector Operands; +}; + +[[nodiscard]] Expected +liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, + const LiveRegUnits &Physical, const MachineFunction &Function, + const TargetDescription &Target, bool TreatReservedAsLive) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || Reg->isNoRegister()) + return false; + if (Reg->isVirtual()) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + return Virtual.intersects(*Reg, *Lanes); + } + if (TreatReservedAsLive && isReservedPhysicalRegister(*Reg, Function, Target)) + return true; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + return std::ranges::any_of(*Units, [&Physical](const PhysicalUnitAccess &Unit) { + return Physical.intersects(Unit.Unit, Unit.Lanes); + }); +} + +[[nodiscard]] Expected removeOperandFromLiveSet(const MachineOperand &Operand, + RegisterLaneSet &Virtual, + LiveRegUnits &Physical, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || Reg->isNoRegister()) + return {}; + if (Reg->isVirtual()) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + Virtual.remove(*Reg, *Lanes); + return {}; + } + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + for (const PhysicalUnitAccess &Unit : *Units) + Physical.remove(Unit.Unit, Unit.Lanes); + return {}; +} + +[[nodiscard]] Expected addOperandToLiveSet(const MachineOperand &Operand, + RegisterLaneSet &Virtual, LiveRegUnits &Physical, + const MachineFunction &Function, + const TargetDescription &Target) { + return addOperandUse(Virtual, Physical, Operand, Function, Target); +} + +[[nodiscard]] Expected requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, + const MachineFunction &Function, + const TargetDescription &Target) { + RegisterLaneSet Virtual; + LiveRegUnits Physical; + for (const MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness verification encountered an unknown instruction descriptor"); + } + const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *MaskOperand = Operand.getIf(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness verification encountered a null live-out register mask"); + } + auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + } + + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister() && Operand.isDef()) { + auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target); + if (!Removed) + return std::unexpected(Removed.error()); + continue; + } + const auto *MaskOperand = Operand.getIf(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness verification encountered a null register mask"); + } + LiveRegUnits Clobbers; + auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + Physical.subtract(Clobbers); + } + + if (IsPhi) + continue; + for (const MachineOperand &Operand : Instruction->operands()) { + if (!Operand.isRegister() || !Operand.isUse()) + continue; + auto Added = addOperandToLiveSet(Operand, Virtual, Physical, Function, Target); + if (!Added) + return std::unexpected(Added.error()); + } + } + return Physical; +} + +[[nodiscard]] Expected +buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescription &Target) { + auto Variables = computeLiveVariables(Function, Target); + if (!Variables) + return std::unexpected(Variables.error()); + + LivenessRebuildPlan Plan; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + const MachineBlockLiveness *BlockVariables = Variables->block(*Block); + if (BlockVariables == nullptr) + return makeUnexpected(ErrorCode::InternalError, "liveness result omitted a machine block"); + auto NewLiveIns = canonicalPhysicalLiveIns(BlockVariables->PhysicalLiveIn, Target); + if (!NewLiveIns) + return std::unexpected(NewLiveIns.error()); + Plan.Blocks.push_back( + {Block->stableID(), + std::vector(Block->liveIns().begin(), Block->liveIns().end()), + std::move(*NewLiveIns)}); + + RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut; + LiveRegUnits Physical = BlockVariables->PhysicalLiveOut; + for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness rebuild encountered an unknown instruction descriptor"); + } + const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *MaskOperand = Operand.getIf(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "liveness rebuild encountered a null live-out register mask"); + auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister() || !Operand->isDef()) + continue; + auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, false); + if (!IsLive) + return std::unexpected(IsLive.error()); + RegisterOperandFlags Flags = Operand->registerFlags(); + Flags.clear(RegisterOperandFlag::Dead); + if (!*IsLive) + Flags.set(RegisterOperandFlag::Dead); + Plan.Operands.push_back( + {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, !*IsLive}); + } + + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister() && Operand.isDef()) { + auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target); + if (!Removed) + return std::unexpected(Removed.error()); + continue; + } + const auto *MaskOperand = Operand.getIf(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "liveness rebuild encountered a null register mask"); + LiveRegUnits Clobbers; + auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); + if (!Added) + return std::unexpected(Added.error()); + Physical.subtract(Clobbers); + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister() || !Operand->isUse()) + continue; + if (IsPhi) { + RegisterOperandFlags Flags = Operand->registerFlags(); + Flags.clear(RegisterOperandFlag::Kill); + const auto Existing = std::ranges::find_if( + Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) { + return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index; + }); + if (Existing == Plan.Operands.end()) { + Plan.Operands.push_back( + {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, false}); + } else { + Existing->Rebuilt.clear(RegisterOperandFlag::Kill); + Existing->KillIsValid = false; + } + continue; + } + const bool IsSemanticUse = !Operand->isDebugUse() && + !Operand->registerFlags().has(RegisterOperandFlag::Undef) && + !Operand->registerValue()->isNoRegister(); + bool IsKill = false; + if (IsSemanticUse) { + auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, true); + if (!IsLive) + return std::unexpected(IsLive.error()); + IsKill = !*IsLive; + } + RegisterOperandFlags Flags = Operand->registerFlags(); + Flags.clear(RegisterOperandFlag::Kill); + if (IsKill) + Flags.set(RegisterOperandFlag::Kill); + + const auto Existing = + std::ranges::find_if(Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) { + return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index; + }); + if (Existing == Plan.Operands.end()) { + Plan.Operands.push_back( + {Instruction->stableID(), Index, Operand->registerFlags(), Flags, IsKill, false}); + } else { + Existing->Rebuilt.clear(RegisterOperandFlag::Kill); + if (IsKill) + Existing->Rebuilt.set(RegisterOperandFlag::Kill); + Existing->KillIsValid = IsKill; + } + if (IsSemanticUse) { + auto Added = addOperandToLiveSet(*Operand, Virtual, Physical, Function, Target); + if (!Added) + return std::unexpected(Added.error()); + } + } + } + + if (Block == Function.firstBlock()) { + for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) { + const PhysicalRegisterDesc *Description = + Target.registers().physicalRegister(LiveIn.PhysReg); + if (Description == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness rebuild encountered an unknown function live-in"); + } + addPhysicalRegister(Physical, *Description); + if (LiveIn.InitialVirtualRegister) { + auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + Virtual.remove(*LiveIn.InitialVirtualRegister, *Lanes); + } + } + } + + if (Virtual != BlockVariables->VirtualLiveIn || Physical != BlockVariables->PhysicalLiveIn) { + return makeUnexpected(ErrorCode::InternalError, + "reverse liveness reconstruction disagrees with block dataflow"); + } + } + return Plan; +} + +struct ResolvedBlockLivenessPlan final { + MachineBasicBlock *Block = nullptr; + const BlockLivenessPlan *Plan = nullptr; +}; + +struct ResolvedOperandFlagPlan final { + MachineOperand *Operand = nullptr; + const OperandFlagPlan *Plan = nullptr; +}; + +struct ResolvedLivenessRebuildPlan final { + std::vector Blocks; + std::vector Operands; +}; + +[[nodiscard]] Expected +resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) { + ResolvedLivenessRebuildPlan Result; + Result.Blocks.reserve(Plan.Blocks.size()); + for (const BlockLivenessPlan &BlockPlan : Plan.Blocks) { + const auto Position = + std::ranges::find_if(Function.allBlocks(), [&BlockPlan](const MachineBasicBlock *Block) { + return Block != nullptr && Block->stableID() == BlockPlan.Block; + }); + if (Position == Function.allBlocks().end() || !(*Position)->isLinked()) { + return makeUnexpected(ErrorCode::InternalError, + "liveness rebuild plan references an unavailable machine block"); + } + Result.Blocks.push_back({*Position, &BlockPlan}); + } + + Result.Operands.reserve(Plan.Operands.size()); + for (const OperandFlagPlan &OperandPlan : Plan.Operands) { + const auto Position = std::ranges::find_if( + Function.allInstructions(), [&OperandPlan](const MachineInstr *Instruction) { + return Instruction != nullptr && Instruction->stableID() == OperandPlan.Instruction; + }); + if (Position == Function.allInstructions().end() || !(*Position)->isLinked()) { + return makeUnexpected(ErrorCode::InternalError, + "liveness rebuild plan references an unavailable instruction"); + } + MachineOperand *Operand = (*Position)->operandAt(OperandPlan.OperandIndex); + if (Operand == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "liveness rebuild plan references an unavailable operand"); + } + Result.Operands.push_back({Operand, &OperandPlan}); + } + return Result; +} + +[[nodiscard]] Expected restoreLivenessPlan(const ResolvedLivenessRebuildPlan &Plan) { + for (const ResolvedBlockLivenessPlan &Resolved : Plan.Blocks) { + Resolved.Block->clearLiveIns(); + for (const MachineBasicBlockLiveIn &LiveIn : Resolved.Plan->OriginalLiveIns) { + auto Restored = Resolved.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); + if (!Restored) + return std::unexpected(Restored.error()); + } + } + for (const ResolvedOperandFlagPlan &Resolved : Plan.Operands) { + auto Restored = Resolved.Operand->setRegisterFlags(Resolved.Plan->Original); + if (!Restored) + return std::unexpected(Restored.error()); + } + return {}; +} + +[[nodiscard]] Expected applyLivenessPlan(MachineFunction &Function, + const LivenessRebuildPlan &Plan) { + auto Resolved = resolveLivenessPlan(Function, Plan); + if (!Resolved) + return std::unexpected(Resolved.error()); + + bool Changed = false; + for (const ResolvedBlockLivenessPlan &BlockPlan : Resolved->Blocks) { + Changed |= BlockPlan.Plan->OriginalLiveIns != BlockPlan.Plan->RebuiltLiveIns; + BlockPlan.Block->clearLiveIns(); + for (const MachineBasicBlockLiveIn &LiveIn : BlockPlan.Plan->RebuiltLiveIns) { + auto Added = BlockPlan.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); + if (!Added) { + auto Restored = restoreLivenessPlan(*Resolved); + if (!Restored) + return makeUnexpected(ErrorCode::InternalError, + "liveness rebuild failed and rollback also failed"); + return std::unexpected(Added.error()); + } + } + } + for (const ResolvedOperandFlagPlan &OperandPlan : Resolved->Operands) { + Changed |= OperandPlan.Plan->Original != OperandPlan.Plan->Rebuilt; + auto Updated = OperandPlan.Operand->setRegisterFlags(OperandPlan.Plan->Rebuilt); + if (!Updated) { + auto Restored = restoreLivenessPlan(*Resolved); + if (!Restored) + return makeUnexpected(ErrorCode::InternalError, + "liveness rebuild failed and rollback also failed"); + return std::unexpected(Updated.error()); + } + } + return Changed; +} +} // namespace + +LaneMask RegisterLaneSet::lanes(Register Reg) const noexcept { + return lanesFor(Values, Reg); +} + +bool RegisterLaneSet::contains(Register Reg, LaneMask Lanes) const noexcept { + return containsLanes(Values, Reg, Lanes); +} + +bool RegisterLaneSet::intersects(Register Reg, LaneMask Lanes) const noexcept { + return intersectsLanes(Values, Reg, Lanes); +} + +void RegisterLaneSet::add(Register Reg, LaneMask Lanes) { + if (!Reg.isNoRegister()) + addLanes(Values, Reg, Lanes); +} + +void RegisterLaneSet::remove(Register Reg, LaneMask Lanes) { + removeLanes(Values, Reg, Lanes); +} + +void RegisterLaneSet::unite(const RegisterLaneSet &Other) { + uniteLanes(Values, Other.Values); +} + +void RegisterLaneSet::subtract(const RegisterLaneSet &Other) { + subtractLaneSets(Values, Other.Values); +} +const MachineBlockLiveness * +LiveVariablesAnalysis::Result::block(const MachineBasicBlock &Block) const noexcept { + const auto Position = Blocks.find(&Block); + return Position == Blocks.end() ? nullptr : &Position->second; +} + +MachineBlockLiveness & +LiveVariablesAnalysis::Result::getOrCreateBlock(const MachineBasicBlock &Block) { + return Blocks[&Block]; +} + +bool LiveVariablesAnalysis::Result::isLiveIn(const MachineBasicBlock &Block, Register Reg, + LaneMask Lanes) const noexcept { + const MachineBlockLiveness *Value = block(Block); + return Value != nullptr && Value->VirtualLiveIn.intersects(Reg, Lanes); +} + +bool LiveVariablesAnalysis::Result::isLiveOut(const MachineBasicBlock &Block, Register Reg, + LaneMask Lanes) const noexcept { + const MachineBlockLiveness *Value = block(Block); + return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); +} + +bool LiveVariablesAnalysis::Result::isUnitLiveIn(const MachineBasicBlock &Block, + RegisterUnitID Unit, + LaneMask Lanes) const noexcept { + const MachineBlockLiveness *Value = block(Block); + return Value != nullptr && Value->PhysicalLiveIn.intersects(Unit, Lanes); +} + +bool LiveVariablesAnalysis::Result::isUnitLiveOut(const MachineBasicBlock &Block, + RegisterUnitID Unit, + LaneMask Lanes) const noexcept { + const MachineBlockLiveness *Value = block(Block); + return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit, Lanes); +} + +bool LiveVariablesAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id()); +} + +Expected LiveVariablesAnalysis::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + return computeLiveVariables(Function, Target); +} +const MachinePassContract &RebuildMachineLivenessPass::contract() const noexcept { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "RebuildMachineLiveness", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten}, + .Sets = {MachineFunctionProperty::TracksLiveness}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = std::nullopt, + }; + Value.DeclaredChanges = {MachinePassChange::Operands}; + return Value; + }(); + return Contract; +} + +Expected RebuildMachineLivenessPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties()); + if (!Missing.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "RebuildMachineLiveness requires properties: " + Missing.toString()); + } + auto Applied = rebuildMachineLiveness(Function, Target); + if (!Applied) + return std::unexpected(Applied.error()); + + MachinePassResult Result; + Result.Changed = *Applied; + if (Result.Changed) + Result.Changes.add(MachinePassChange::Operands); + Result.Preserved = PreservedAnalyses::all(); + return Result; +} + +Expected rebuildMachineLiveness(MachineFunction &Function, const TargetDescription &Target) { + auto Plan = buildLivenessRebuildPlan(Function, Target); + if (!Plan) + return std::unexpected(Plan.error()); + return applyLivenessPlan(Function, *Plan); +} + +Expected verifyTrackedMachineLiveness(const MachineFunction &Function, + const TargetDescription &Target) { + auto Plan = buildLivenessRebuildPlan(Function, Target); + if (!Plan) + return std::unexpected(Plan.error()); + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + auto Actual = liveInUnits(Block->liveIns(), Target); + if (!Actual) + return std::unexpected(Actual.error()); + auto Expected = requiredLocalPhysicalLiveIns(*Block, Function, Target); + if (!Expected) + return std::unexpected(Expected.error()); + if (!isSubset(*Expected, *Actual)) { + const auto Missing = std::ranges::find_if(Expected->entries(), [&Actual](const auto &Entry) { + return !Actual->contains(Entry.first, Entry.second); + }); + if (Missing != Expected->entries().end()) { + return makeUnexpected(ErrorCode::VerificationError, + "TracksLiveness block " + std::to_string(Block->stableID().value()) + + " is missing required physical register unit " + + std::to_string(Missing->first.value())); + } + return makeUnexpected(ErrorCode::VerificationError, + "TracksLiveness block is missing required physical live-ins"); + } + } + for (const OperandFlagPlan &OperandPlan : Plan->Operands) { + if (OperandPlan.Original.has(RegisterOperandFlag::Kill) && !OperandPlan.KillIsValid) { + return makeUnexpected(ErrorCode::VerificationError, + "TracksLiveness operand has a stale kill flag"); + } + if (OperandPlan.Original.has(RegisterOperandFlag::Dead) && !OperandPlan.DeadIsValid) { + return makeUnexpected(ErrorCode::VerificationError, + "TracksLiveness operand has a stale dead flag"); + } + } + return {}; +} + +Expected registerStage11MachineAnalyses(MachineAnalysisManager &Analyses) { + const std::array IDs{ + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + MachineAnalysisManager::id(), + }; + const std::size_t Registered = static_cast( + std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); })); + if (Registered == IDs.size()) + return {}; + if (Registered != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "standard liveness analyses are only partially registered"); + } + + auto Candidate = Analyses.forkEmpty(); + if (!Candidate) + return std::unexpected(Candidate.error()); + MachineAnalysisManager &Staging = **Candidate; + auto Slots = Staging.registerAnalysis({ + .Name = "SlotIndexes", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::BlockLayout}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Slots) + return std::unexpected(Slots.error()); + auto Variables = Staging.registerAnalysis({ + .Name = "LiveVariables", + .Dependencies = {}, + .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers, MachinePassChange::CFG, + MachinePassChange::TargetState}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Variables) + return std::unexpected(Variables.error()); + auto Intervals = Staging.registerAnalysis({ + .Name = "LiveIntervals", + .Dependencies = {MachineAnalysisManager::id(), + MachineAnalysisManager::id()}, + .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers, MachinePassChange::CFG, + MachinePassChange::BlockLayout, MachinePassChange::TargetState}, + .ThreadSafety = PassThreadSafety::ThreadSafe, + }); + if (!Intervals) + return std::unexpected(Intervals.error()); + Analyses.Registry = std::move(Staging.Registry); + return {}; +} + +} // namespace rcc 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/MachineLiveness.cpp b/backend/lib/CodeGen/MachineLiveness.cpp deleted file mode 100644 index 9882b11..0000000 --- a/backend/lib/CodeGen/MachineLiveness.cpp +++ /dev/null @@ -1,1942 +0,0 @@ -// SPDX-License-Identifier: GPL-3.0-or-later - -#include "rcc/CodeGen/MachineLiveness.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 "rcc/CodeGen/TargetRegisterInfo.h" - -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include -#include - -namespace rcc { -namespace { - -constexpr std::uint64_t SlotSpacing = 16; -constexpr std::uint64_t SlotAlignmentMask = 3; - -[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { - return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); -} - -template -void addLanes(std::unordered_map &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 -void removeLanes(std::unordered_map &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 -[[nodiscard]] LaneMask lanesFor(const std::unordered_map &Values, - KeyT Key) noexcept { - const auto Position = Values.find(Key); - return Position == Values.end() ? LaneMask{} : Position->second; -} - -template -[[nodiscard]] bool containsLanes(const std::unordered_map &Values, KeyT Key, - LaneMask Lanes) noexcept { - const LaneMask Present = lanesFor(Values, Key); - return !Present.empty() && Present.contains(Lanes); -} - -template -[[nodiscard]] bool intersectsLanes(const std::unordered_map &Values, KeyT Key, - LaneMask Lanes) noexcept { - return lanesFor(Values, Key).intersects(Lanes); -} - -template -void uniteLanes(std::unordered_map &Values, - const std::unordered_map &Other) { - for (const auto &[Key, Lanes] : Other) - addLanes(Values, Key, Lanes); -} - -template -void subtractLaneSets(std::unordered_map &Values, - const std::unordered_map &Other) { - for (const auto &[Key, Lanes] : Other) - 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::popcount(Lanes.rawValue())); - } - return Result; -} - -[[nodiscard]] Expected 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 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 virtualOperandLanes(const MachineOperand &Operand, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - 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> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - const std::optional 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 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 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 Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] Expected 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 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 addOperandUse(RegisterLaneSet &VirtualUses, - RegisterUnitLaneSet &PhysicalUses, - const MachineOperand &Operand, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - if (Reg == nullptr || Reg->isNoRegister() || Operand.isDebugUse() || - Operand.registerFlags().has(RegisterOperandFlag::Undef)) { - return {}; - } - if (Reg->isVirtual()) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - VirtualUses.add(*Reg, *Lanes); - return {}; - } - if (isReservedPhysicalRegister(*Reg, Function, Target)) - return {}; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - for (const PhysicalUnitAccess &Unit : *Units) - PhysicalUses.add(Unit.Unit, Unit.Lanes); - return {}; -} - -[[nodiscard]] Expected addOperandDef(RegisterLaneSet &VirtualDefs, - RegisterUnitLaneSet &PhysicalDefs, - const MachineOperand &Operand, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - if (Reg == nullptr || Reg->isNoRegister()) - return {}; - if (Reg->isVirtual()) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - VirtualDefs.add(*Reg, *Lanes); - return {}; - } - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - for (const PhysicalUnitAccess &Unit : *Units) - PhysicalDefs.add(Unit.Unit, Unit.Lanes); - return {}; -} - -struct LivenessEdgeKey final { - const MachineBasicBlock *Predecessor = nullptr; - const MachineBasicBlock *Successor = nullptr; - - friend bool operator==(const LivenessEdgeKey &, const LivenessEdgeKey &) = default; -}; - -struct LivenessEdgeKeyHash final { - [[nodiscard]] std::size_t operator()(const LivenessEdgeKey &Key) const noexcept { - const std::size_t Left = std::hash{}(Key.Predecessor); - const std::size_t Right = std::hash{}(Key.Successor); - return Left ^ (Right + 0x9e3779b9U + (Left << 6U) + (Left >> 2U)); - } -}; - -struct EdgeLivenessUses final { - RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; -}; - -[[nodiscard]] Expected -computeLiveVariables(const MachineFunction &Function, const TargetDescription &Target) { - LiveVariablesAnalysis::Result Result; - std::vector Blocks; - std::unordered_map EdgeUses; - for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; - Block = Block->next()) { - Blocks.push_back(Block); - (void)Result.getOrCreateBlock(*Block); - } - - for (const MachineBasicBlock *Block : Blocks) { - MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); - if (Block == Function.firstBlock()) { - for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) { - const PhysicalRegisterDesc *Description = - Target.registers().physicalRegister(LiveIn.PhysReg); - if (Description == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "function live-in references an unknown physical register"); - } - addPhysicalRegister(Liveness.PhysicalUses, *Description); - if (LiveIn.InitialVirtualRegister) { - auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - Liveness.VirtualDefs.add(*LiveIn.InitialVirtualRegister, *Lanes); - } - } - } - for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); - if (Descriptor == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown instruction descriptor"); - } - const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); - if (IsPhi) { - if (Instruction->operandCount() < 3 || (Instruction->operandCount() - 1U) % 2U != 0) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered a malformed PHI instruction"); - } - std::unordered_set IncomingBlocks; - for (std::size_t Index = 1; Index < Instruction->operandCount(); Index += 2U) { - const MachineOperand *Incoming = Instruction->operandAt(Index); - const MachineOperand *PredecessorOperand = Instruction->operandAt(Index + 1U); - const auto *Predecessor = PredecessorOperand == nullptr - ? nullptr - : PredecessorOperand->getIf(); - if (Incoming == nullptr || Predecessor == nullptr || Predecessor->Block == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered a malformed PHI incoming pair"); - } - const MachineBasicBlock *IncomingBlock = Predecessor->Block; - const bool HasPredecessor = std::ranges::find(Block->predecessors(), IncomingBlock) != - Block->predecessors().end(); - const bool HasSuccessor = std::ranges::any_of( - IncomingBlock->successors(), - [Block](const MachineSuccessor &Successor) { return Successor.Block == Block; }); - if (&IncomingBlock->function() != &Function || !IncomingBlock->isLinked() || - !HasPredecessor || !HasSuccessor || !IncomingBlocks.insert(IncomingBlock).second) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered a PHI incoming without a unique CFG edge"); - } - EdgeLivenessUses &Uses = EdgeUses[{IncomingBlock, Block}]; - auto Added = addOperandUse(Uses.Virtual, Uses.Physical, *Incoming, Function, Target); - if (!Added) - return std::unexpected(Added.error()); - } - } - - RegisterLaneSet InstructionVirtualUses; - RegisterLaneSet InstructionVirtualDefs; - RegisterUnitLaneSet InstructionPhysicalUses; - RegisterUnitLaneSet InstructionPhysicalDefs; - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - const MachineOperand &Operand = *Instruction->operandAt(Index); - if (Operand.isRegister()) { - if (Operand.isUse() && (!IsPhi || Index == 0)) { - auto Use = addOperandUse(InstructionVirtualUses, InstructionPhysicalUses, Operand, - Function, Target); - if (!Use) - return std::unexpected(Use.error()); - } - if (Operand.isDef()) { - auto Def = addOperandDef(InstructionVirtualDefs, InstructionPhysicalDefs, Operand, - Function, Target); - if (!Def) - return std::unexpected(Def.error()); - } - continue; - } - if (const auto *MaskOperand = Operand.getIf(); - MaskOperand != nullptr) { - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered a null register mask"); - auto Added = addRegisterMaskDefs(InstructionPhysicalDefs, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - continue; - } - if (const auto *MaskOperand = Operand.getIf(); - MaskOperand != nullptr) { - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered a null live-out register mask"); - auto Added = addRegisterMaskUses(InstructionPhysicalUses, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - } - } - - RegisterLaneSet NewVirtualUses = InstructionVirtualUses; - NewVirtualUses.subtract(Liveness.VirtualDefs); - Liveness.VirtualUses.unite(NewVirtualUses); - Liveness.VirtualDefs.unite(InstructionVirtualDefs); - - RegisterUnitLaneSet NewPhysicalUses = InstructionPhysicalUses; - NewPhysicalUses.subtract(Liveness.PhysicalDefs); - Liveness.PhysicalUses.unite(NewPhysicalUses); - Liveness.PhysicalDefs.unite(InstructionPhysicalDefs); - } - } - - bool Changed = true; - while (Changed) { - Changed = false; - for (const MachineBasicBlock *Block : Blocks | std::views::reverse) { - MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); - RegisterLaneSet VirtualOut; - RegisterUnitLaneSet PhysicalOut; - for (const MachineSuccessor &Successor : Block->successors()) { - if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an invalid CFG successor"); - } - const MachineBlockLiveness &SuccessorLiveness = *Result.block(*Successor.Block); - VirtualOut.unite(SuccessorLiveness.VirtualLiveIn); - PhysicalOut.unite(SuccessorLiveness.PhysicalLiveIn); - const auto Edge = EdgeUses.find({Block, Successor.Block}); - if (Edge != EdgeUses.end()) { - VirtualOut.unite(Edge->second.Virtual); - PhysicalOut.unite(Edge->second.Physical); - } - } - - RegisterLaneSet VirtualIn = VirtualOut; - VirtualIn.subtract(Liveness.VirtualDefs); - VirtualIn.unite(Liveness.VirtualUses); - RegisterUnitLaneSet PhysicalIn = PhysicalOut; - PhysicalIn.subtract(Liveness.PhysicalDefs); - PhysicalIn.unite(Liveness.PhysicalUses); - - if (VirtualOut != Liveness.VirtualLiveOut || VirtualIn != Liveness.VirtualLiveIn || - PhysicalOut != Liveness.PhysicalLiveOut || PhysicalIn != Liveness.PhysicalLiveIn) { - Liveness.VirtualLiveOut = std::move(VirtualOut); - Liveness.VirtualLiveIn = std::move(VirtualIn); - Liveness.PhysicalLiveOut = std::move(PhysicalOut); - Liveness.PhysicalLiveIn = std::move(PhysicalIn); - Changed = true; - } - } - } - return Result; -} - -[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional Filter) noexcept { - return !Filter || Access.intersects(*Filter); -} - -struct InstructionRangeEvent final { - bool HasUse = false; - bool HasNormalDef = false; - bool HasEarlyDef = false; - bool HasRegMaskClobber = false; -}; - -[[nodiscard]] Expected -virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional Filter, - const MachineFunction &Function, const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - const Register *OperandReg = Operand.getIf(); - 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 unitRangeEvent(const MachineInstr &Instruction, - RegisterUnitID Unit, - std::optional Filter, - const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - if (Operand.isRegister()) { - const Register *Reg = Operand.getIf(); - 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(); - 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(); - 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 -[[nodiscard]] Expected -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 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 { - 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 virtualRegisterFullLanes(Register Reg, - const MachineFunction &Function, - const TargetDescription &Target) { - return virtualRegisterLanes(Reg, Function, Target); -} - -[[nodiscard]] Expected> -partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, - const TargetDescription &Target) { - auto Full = virtualRegisterFullLanes(Reg, Function, Target); - if (!Full) - return std::unexpected(Full.error()); - std::vector 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 Groups{*Full}; - for (const LaneMask Access : AccessMasks) { - std::vector 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> -canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescription &Target) { - struct Candidate final { - const PhysicalRegisterDesc *Description = nullptr; - LaneMask RegisterLanes; - RegisterUnitLaneSet Coverage; - std::size_t ExtraLanes = 0; - bool Selected = false; - }; - - std::vector Candidates; - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - const LaneMask FullLanes = physicalRegisterLanes(Description); - std::uint64_t SelectableLanes = 0; - LaneMask RelevantLanes; - for (const RegisterUnitLane &Unit : Description.Units) { - RelevantLanes = RelevantLanes | denormalizeUnitLanes(Units.lanes(Unit.Unit), Unit.Lanes); - } - 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)); - if (isSubset(Coverage, Units)) - SelectableLanes |= Lane; - PendingLanes &= PendingLanes - 1U; - } - if (SelectableLanes == 0) - continue; - Candidate Value; - Value.Description = &Description; - Value.RegisterLanes = LaneMask::fromRaw(SelectableLanes); - Value.Coverage = physicalRegisterCoverage(Description, Value.RegisterLanes); - Value.ExtraLanes = static_cast(std::popcount(FullLanes.rawValue()) - - std::popcount(SelectableLanes)); - Candidates.push_back(std::move(Value)); - } - - RegisterUnitLaneSet Covered; - std::vector Result; - while (Covered != Units) { - Candidate *Best = nullptr; - std::size_t BestNewLanes = 0; - std::size_t BestCoverage = 0; - for (Candidate &Value : Candidates) { - if (Value.Selected) - continue; - RegisterUnitLaneSet NewCoverage = Value.Coverage; - NewCoverage.subtract(Covered); - const std::size_t NewLanes = laneCount(NewCoverage); - if (NewLanes == 0) - continue; - const std::size_t Coverage = laneCount(Value.Coverage); - if (Best == nullptr || NewLanes > BestNewLanes || - (NewLanes == BestNewLanes && Value.ExtraLanes < Best->ExtraLanes) || - (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes && - Coverage > BestCoverage) || - (NewLanes == BestNewLanes && Value.ExtraLanes == Best->ExtraLanes && - Coverage == BestCoverage && - Value.Description->Reg.number() < Best->Description->Reg.number())) { - Best = &Value; - BestNewLanes = NewLanes; - BestCoverage = Coverage; - } - } - if (Best == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "physical live-in units cannot be represented by target registers"); - } - Best->Selected = true; - Covered.unite(Best->Coverage); - const LaneMask FullLanes = physicalRegisterLanes(*Best->Description); - const LaneMask Lanes = Best->RegisterLanes == FullLanes ? LaneMask::all() : Best->RegisterLanes; - Result.push_back({Best->Description->Reg, Lanes}); - } - std::ranges::sort(Result, - [](const MachineBasicBlockLiveIn &Left, const MachineBasicBlockLiveIn &Right) { - return Left.PhysReg.number() < Right.PhysReg.number(); - }); - return Result; -} - -[[nodiscard]] Expected -liveInUnits(std::span LiveIns, const TargetDescription &Target) { - RegisterUnitLaneSet Result; - for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) { - const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg); - if (Description == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "block live-in references an unknown physical register"); - } - Result.unite(physicalRegisterCoverage(*Description, LiveIn.Lanes)); - } - return Result; -} - -struct OperandFlagPlan final { - MachineInstrStableID Instruction; - std::size_t OperandIndex = 0; - RegisterOperandFlags Original; - RegisterOperandFlags Rebuilt; - bool KillIsValid = false; - bool DeadIsValid = false; -}; - -struct BlockLivenessPlan final { - MachineBlockStableID Block; - std::vector OriginalLiveIns; - std::vector RebuiltLiveIns; -}; - -struct LivenessRebuildPlan final { - std::vector Blocks; - std::vector Operands; -}; - -[[nodiscard]] Expected -liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, - const RegisterUnitLaneSet &Physical, const MachineFunction &Function, - const TargetDescription &Target, bool TreatReservedAsLive) { - const Register *Reg = Operand.getIf(); - if (Reg == nullptr || Reg->isNoRegister()) - return false; - if (Reg->isVirtual()) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - return Virtual.intersects(*Reg, *Lanes); - } - if (TreatReservedAsLive && isReservedPhysicalRegister(*Reg, Function, Target)) - return true; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - return std::ranges::any_of(*Units, [&Physical](const PhysicalUnitAccess &Unit) { - return Physical.intersects(Unit.Unit, Unit.Lanes); - }); -} - -[[nodiscard]] Expected removeOperandFromLiveSet(const MachineOperand &Operand, - RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - if (Reg == nullptr || Reg->isNoRegister()) - return {}; - if (Reg->isVirtual()) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - Virtual.remove(*Reg, *Lanes); - return {}; - } - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - for (const PhysicalUnitAccess &Unit : *Units) - Physical.remove(Unit.Unit, Unit.Lanes); - return {}; -} - -[[nodiscard]] Expected addOperandToLiveSet(const MachineOperand &Operand, - RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, - const MachineFunction &Function, - const TargetDescription &Target) { - return addOperandUse(Virtual, Physical, Operand, Function, Target); -} - -[[nodiscard]] Expected -requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, const MachineFunction &Function, - const TargetDescription &Target) { - RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; - for (const MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); - if (Descriptor == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness verification encountered an unknown instruction descriptor"); - } - const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *MaskOperand = Operand.getIf(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness verification encountered a null live-out register mask"); - } - auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - } - - for (const MachineOperand &Operand : Instruction->operands()) { - if (Operand.isRegister() && Operand.isDef()) { - auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target); - if (!Removed) - return std::unexpected(Removed.error()); - continue; - } - const auto *MaskOperand = Operand.getIf(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness verification encountered a null register mask"); - } - RegisterUnitLaneSet Clobbers; - auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - Physical.subtract(Clobbers); - } - - if (IsPhi) - continue; - for (const MachineOperand &Operand : Instruction->operands()) { - if (!Operand.isRegister() || !Operand.isUse()) - continue; - auto Added = addOperandToLiveSet(Operand, Virtual, Physical, Function, Target); - if (!Added) - return std::unexpected(Added.error()); - } - } - return Physical; -} - -[[nodiscard]] Expected -buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescription &Target) { - auto Variables = computeLiveVariables(Function, Target); - if (!Variables) - return std::unexpected(Variables.error()); - - LivenessRebuildPlan Plan; - for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; - Block = Block->next()) { - const MachineBlockLiveness *BlockVariables = Variables->block(*Block); - if (BlockVariables == nullptr) - return makeUnexpected(ErrorCode::InternalError, "liveness result omitted a machine block"); - auto NewLiveIns = canonicalPhysicalLiveIns(BlockVariables->PhysicalLiveIn, Target); - if (!NewLiveIns) - return std::unexpected(NewLiveIns.error()); - Plan.Blocks.push_back( - {Block->stableID(), - std::vector(Block->liveIns().begin(), Block->liveIns().end()), - std::move(*NewLiveIns)}); - - RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut; - RegisterUnitLaneSet Physical = BlockVariables->PhysicalLiveOut; - for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); - if (Descriptor == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness rebuild encountered an unknown instruction descriptor"); - } - const bool IsPhi = Descriptor->Flags.has(InstructionFlag::Phi); - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *MaskOperand = Operand.getIf(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "liveness rebuild encountered a null live-out register mask"); - auto Added = addRegisterMaskUses(Physical, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - const MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister() || !Operand->isDef()) - continue; - auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, false); - if (!IsLive) - return std::unexpected(IsLive.error()); - RegisterOperandFlags Flags = Operand->registerFlags(); - Flags.clear(RegisterOperandFlag::Dead); - if (!*IsLive) - Flags.set(RegisterOperandFlag::Dead); - Plan.Operands.push_back( - {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, !*IsLive}); - } - - for (const MachineOperand &Operand : Instruction->operands()) { - if (Operand.isRegister() && Operand.isDef()) { - auto Removed = removeOperandFromLiveSet(Operand, Virtual, Physical, Function, Target); - if (!Removed) - return std::unexpected(Removed.error()); - continue; - } - const auto *MaskOperand = Operand.getIf(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "liveness rebuild encountered a null register mask"); - RegisterUnitLaneSet Clobbers; - auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); - if (!Added) - return std::unexpected(Added.error()); - Physical.subtract(Clobbers); - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - const MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister() || !Operand->isUse()) - continue; - if (IsPhi) { - RegisterOperandFlags Flags = Operand->registerFlags(); - Flags.clear(RegisterOperandFlag::Kill); - const auto Existing = std::ranges::find_if( - Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) { - return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index; - }); - if (Existing == Plan.Operands.end()) { - Plan.Operands.push_back( - {Instruction->stableID(), Index, Operand->registerFlags(), Flags, false, false}); - } else { - Existing->Rebuilt.clear(RegisterOperandFlag::Kill); - Existing->KillIsValid = false; - } - continue; - } - const bool IsSemanticUse = !Operand->isDebugUse() && - !Operand->registerFlags().has(RegisterOperandFlag::Undef) && - !Operand->registerValue()->isNoRegister(); - bool IsKill = false; - if (IsSemanticUse) { - auto IsLive = liveSetIntersects(*Operand, Virtual, Physical, Function, Target, true); - if (!IsLive) - return std::unexpected(IsLive.error()); - IsKill = !*IsLive; - } - RegisterOperandFlags Flags = Operand->registerFlags(); - Flags.clear(RegisterOperandFlag::Kill); - if (IsKill) - Flags.set(RegisterOperandFlag::Kill); - - const auto Existing = - std::ranges::find_if(Plan.Operands, [Instruction, Index](const OperandFlagPlan &Entry) { - return Entry.Instruction == Instruction->stableID() && Entry.OperandIndex == Index; - }); - if (Existing == Plan.Operands.end()) { - Plan.Operands.push_back( - {Instruction->stableID(), Index, Operand->registerFlags(), Flags, IsKill, false}); - } else { - Existing->Rebuilt.clear(RegisterOperandFlag::Kill); - if (IsKill) - Existing->Rebuilt.set(RegisterOperandFlag::Kill); - Existing->KillIsValid = IsKill; - } - if (IsSemanticUse) { - auto Added = addOperandToLiveSet(*Operand, Virtual, Physical, Function, Target); - if (!Added) - return std::unexpected(Added.error()); - } - } - } - - if (Block == Function.firstBlock()) { - for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) { - const PhysicalRegisterDesc *Description = - Target.registers().physicalRegister(LiveIn.PhysReg); - if (Description == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness rebuild encountered an unknown function live-in"); - } - addPhysicalRegister(Physical, *Description); - if (LiveIn.InitialVirtualRegister) { - auto Lanes = virtualRegisterLanes(*LiveIn.InitialVirtualRegister, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - Virtual.remove(*LiveIn.InitialVirtualRegister, *Lanes); - } - } - } - - if (Virtual != BlockVariables->VirtualLiveIn || Physical != BlockVariables->PhysicalLiveIn) { - return makeUnexpected(ErrorCode::InternalError, - "reverse liveness reconstruction disagrees with block dataflow"); - } - } - return Plan; -} - -struct ResolvedBlockLivenessPlan final { - MachineBasicBlock *Block = nullptr; - const BlockLivenessPlan *Plan = nullptr; -}; - -struct ResolvedOperandFlagPlan final { - MachineOperand *Operand = nullptr; - const OperandFlagPlan *Plan = nullptr; -}; - -struct ResolvedLivenessRebuildPlan final { - std::vector Blocks; - std::vector Operands; -}; - -[[nodiscard]] Expected -resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) { - ResolvedLivenessRebuildPlan Result; - Result.Blocks.reserve(Plan.Blocks.size()); - for (const BlockLivenessPlan &BlockPlan : Plan.Blocks) { - const auto Position = - std::ranges::find_if(Function.allBlocks(), [&BlockPlan](const MachineBasicBlock *Block) { - return Block != nullptr && Block->stableID() == BlockPlan.Block; - }); - if (Position == Function.allBlocks().end() || !(*Position)->isLinked()) { - return makeUnexpected(ErrorCode::InternalError, - "liveness rebuild plan references an unavailable machine block"); - } - Result.Blocks.push_back({*Position, &BlockPlan}); - } - - Result.Operands.reserve(Plan.Operands.size()); - for (const OperandFlagPlan &OperandPlan : Plan.Operands) { - const auto Position = std::ranges::find_if( - Function.allInstructions(), [&OperandPlan](const MachineInstr *Instruction) { - return Instruction != nullptr && Instruction->stableID() == OperandPlan.Instruction; - }); - if (Position == Function.allInstructions().end() || !(*Position)->isLinked()) { - return makeUnexpected(ErrorCode::InternalError, - "liveness rebuild plan references an unavailable instruction"); - } - MachineOperand *Operand = (*Position)->operandAt(OperandPlan.OperandIndex); - if (Operand == nullptr) { - return makeUnexpected(ErrorCode::InternalError, - "liveness rebuild plan references an unavailable operand"); - } - Result.Operands.push_back({Operand, &OperandPlan}); - } - return Result; -} - -[[nodiscard]] Expected restoreLivenessPlan(const ResolvedLivenessRebuildPlan &Plan) { - for (const ResolvedBlockLivenessPlan &Resolved : Plan.Blocks) { - Resolved.Block->clearLiveIns(); - for (const MachineBasicBlockLiveIn &LiveIn : Resolved.Plan->OriginalLiveIns) { - auto Restored = Resolved.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); - if (!Restored) - return std::unexpected(Restored.error()); - } - } - for (const ResolvedOperandFlagPlan &Resolved : Plan.Operands) { - auto Restored = Resolved.Operand->setRegisterFlags(Resolved.Plan->Original); - if (!Restored) - return std::unexpected(Restored.error()); - } - return {}; -} - -[[nodiscard]] Expected applyLivenessPlan(MachineFunction &Function, - const LivenessRebuildPlan &Plan) { - auto Resolved = resolveLivenessPlan(Function, Plan); - if (!Resolved) - return std::unexpected(Resolved.error()); - - bool Changed = false; - for (const ResolvedBlockLivenessPlan &BlockPlan : Resolved->Blocks) { - Changed |= BlockPlan.Plan->OriginalLiveIns != BlockPlan.Plan->RebuiltLiveIns; - BlockPlan.Block->clearLiveIns(); - for (const MachineBasicBlockLiveIn &LiveIn : BlockPlan.Plan->RebuiltLiveIns) { - auto Added = BlockPlan.Block->addLiveIn(LiveIn.PhysReg, LiveIn.Lanes); - if (!Added) { - auto Restored = restoreLivenessPlan(*Resolved); - if (!Restored) - return makeUnexpected(ErrorCode::InternalError, - "liveness rebuild failed and rollback also failed"); - return std::unexpected(Added.error()); - } - } - } - for (const ResolvedOperandFlagPlan &OperandPlan : Resolved->Operands) { - Changed |= OperandPlan.Plan->Original != OperandPlan.Plan->Rebuilt; - auto Updated = OperandPlan.Operand->setRegisterFlags(OperandPlan.Plan->Rebuilt); - if (!Updated) { - auto Restored = restoreLivenessPlan(*Resolved); - if (!Restored) - return makeUnexpected(ErrorCode::InternalError, - "liveness rebuild failed and rollback also failed"); - return std::unexpected(Updated.error()); - } - } - 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 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 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 SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { - Result NewResult; - std::uint64_t Position = SlotSpacing; - auto Advance = [&Position]() -> Expected { - if (Position > std::numeric_limits::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()); -} - -Expected 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); -} - -bool RegisterLaneSet::contains(Register Reg, LaneMask Lanes) const noexcept { - return containsLanes(Values, Reg, Lanes); -} - -bool RegisterLaneSet::intersects(Register Reg, LaneMask Lanes) const noexcept { - return intersectsLanes(Values, Reg, Lanes); -} - -void RegisterLaneSet::add(Register Reg, LaneMask Lanes) { - if (!Reg.isNoRegister()) - addLanes(Values, Reg, Lanes); -} - -void RegisterLaneSet::remove(Register Reg, LaneMask Lanes) { - removeLanes(Values, Reg, Lanes); -} - -void RegisterLaneSet::unite(const RegisterLaneSet &Other) { - uniteLanes(Values, Other.Values); -} - -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); - return Position == Blocks.end() ? nullptr : &Position->second; -} - -MachineBlockLiveness & -LiveVariablesAnalysis::Result::getOrCreateBlock(const MachineBasicBlock &Block) { - return Blocks[&Block]; -} - -bool LiveVariablesAnalysis::Result::isLiveIn(const MachineBasicBlock &Block, Register Reg, - LaneMask Lanes) const noexcept { - const MachineBlockLiveness *Value = block(Block); - return Value != nullptr && Value->VirtualLiveIn.intersects(Reg, Lanes); -} - -bool LiveVariablesAnalysis::Result::isLiveOut(const MachineBasicBlock &Block, Register Reg, - LaneMask Lanes) const noexcept { - const MachineBlockLiveness *Value = block(Block); - return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); -} - -bool LiveVariablesAnalysis::Result::isUnitLiveIn(const MachineBasicBlock &Block, - RegisterUnitID Unit, - LaneMask Lanes) const noexcept { - const MachineBlockLiveness *Value = block(Block); - return Value != nullptr && Value->PhysicalLiveIn.intersects(Unit, Lanes); -} - -bool LiveVariablesAnalysis::Result::isUnitLiveOut(const MachineBasicBlock &Block, - RegisterUnitID Unit, - LaneMask Lanes) const noexcept { - const MachineBlockLiveness *Value = block(Block); - return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit, Lanes); -} - -bool LiveVariablesAnalysis::Result::invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept { - return !Preserved.preserves(MachineAnalysisManager::id()); -} - -Expected LiveVariablesAnalysis::run(MachineFunction &Function, - const TargetDescription &Target, - 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 LiveRange::createValue(SlotIndex Definition, LiveValueState State, - std::optional Origin) { - if (!Definition.isValid()) - return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); - if (Values.size() >= std::numeric_limits::max()) - return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); - const LiveValueNumberID ID = - LiveValueNumberID::fromValue(static_cast(Values.size() + 1U)); - Values.push_back({ID, Definition, State, Origin}); - return ID; -} - -Expected 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 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 LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { - return addSegment({Start, End, Value}); -} - -Expected 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 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 LiveRange::shrinkToUses(std::span Uses) { - std::vector 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 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 LiveRange::verify() const { - std::unordered_set 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 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 LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, - std::span 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()); -} - -Expected -LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &Analyses) { - auto Indexes = Analyses.getResult(Function, Target); - if (!Indexes) - return std::unexpected(Indexes.error()); - auto Variables = Analyses.getResult(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::max() - 10U - ? std::numeric_limits::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(); - 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{ - .Name = "RebuildMachineLiveness", - .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, - MachineFunctionProperty::TiedOpsRewritten}, - .Sets = {MachineFunctionProperty::TracksLiveness}, - .Clears = {}, - .RequiredAnalyses = {}, - .VerificationStage = std::nullopt, - }; - Value.DeclaredChanges = {MachinePassChange::Operands}; - return Value; - }(); - return Contract; -} - -Expected RebuildMachineLivenessPass::run(MachineFunction &Function, - const TargetDescription &Target, - MachineAnalysisManager &) { - const MachineFunctionProperties Missing = contract().Requires.missingFrom(Function.properties()); - if (!Missing.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "RebuildMachineLiveness requires properties: " + Missing.toString()); - } - auto Applied = rebuildMachineLiveness(Function, Target); - if (!Applied) - return std::unexpected(Applied.error()); - - MachinePassResult Result; - Result.Changed = *Applied; - if (Result.Changed) - Result.Changes.add(MachinePassChange::Operands); - Result.Preserved = PreservedAnalyses::all(); - return Result; -} - -Expected rebuildMachineLiveness(MachineFunction &Function, const TargetDescription &Target) { - auto Plan = buildLivenessRebuildPlan(Function, Target); - if (!Plan) - return std::unexpected(Plan.error()); - return applyLivenessPlan(Function, *Plan); -} - -Expected verifyTrackedMachineLiveness(const MachineFunction &Function, - const TargetDescription &Target) { - auto Plan = buildLivenessRebuildPlan(Function, Target); - if (!Plan) - return std::unexpected(Plan.error()); - for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; - Block = Block->next()) { - auto Actual = liveInUnits(Block->liveIns(), Target); - if (!Actual) - return std::unexpected(Actual.error()); - auto Expected = requiredLocalPhysicalLiveIns(*Block, Function, Target); - if (!Expected) - return std::unexpected(Expected.error()); - if (!isSubset(*Expected, *Actual)) { - const auto Missing = std::ranges::find_if(Expected->entries(), [&Actual](const auto &Entry) { - return !Actual->contains(Entry.first, Entry.second); - }); - if (Missing != Expected->entries().end()) { - return makeUnexpected(ErrorCode::VerificationError, - "TracksLiveness block " + std::to_string(Block->stableID().value()) + - " is missing required physical register unit " + - std::to_string(Missing->first.value())); - } - return makeUnexpected(ErrorCode::VerificationError, - "TracksLiveness block is missing required physical live-ins"); - } - } - for (const OperandFlagPlan &OperandPlan : Plan->Operands) { - if (OperandPlan.Original.has(RegisterOperandFlag::Kill) && !OperandPlan.KillIsValid) { - return makeUnexpected(ErrorCode::VerificationError, - "TracksLiveness operand has a stale kill flag"); - } - if (OperandPlan.Original.has(RegisterOperandFlag::Dead) && !OperandPlan.DeadIsValid) { - return makeUnexpected(ErrorCode::VerificationError, - "TracksLiveness operand has a stale dead flag"); - } - } - return {}; -} - -Expected registerStage11MachineAnalyses(MachineAnalysisManager &Analyses) { - const std::array IDs{ - MachineAnalysisManager::id(), - MachineAnalysisManager::id(), - MachineAnalysisManager::id(), - }; - const std::size_t Registered = static_cast( - std::ranges::count_if(IDs, [&Analyses](AnalysisID ID) { return Analyses.isRegistered(ID); })); - if (Registered == IDs.size()) - return {}; - if (Registered != 0) { - return makeUnexpected(ErrorCode::InvalidArgument, - "standard liveness analyses are only partially registered"); - } - - auto Candidate = Analyses.forkEmpty(); - if (!Candidate) - return std::unexpected(Candidate.error()); - MachineAnalysisManager &Staging = **Candidate; - auto Slots = Staging.registerAnalysis({ - .Name = "SlotIndexes", - .Dependencies = {}, - .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::BlockLayout}, - .ThreadSafety = PassThreadSafety::ThreadSafe, - }); - if (!Slots) - return std::unexpected(Slots.error()); - auto Variables = Staging.registerAnalysis({ - .Name = "LiveVariables", - .Dependencies = {}, - .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, - MachinePassChange::Registers, MachinePassChange::CFG, - MachinePassChange::TargetState}, - .ThreadSafety = PassThreadSafety::ThreadSafe, - }); - if (!Variables) - return std::unexpected(Variables.error()); - auto Intervals = Staging.registerAnalysis({ - .Name = "LiveIntervals", - .Dependencies = {MachineAnalysisManager::id(), - MachineAnalysisManager::id()}, - .InvalidatedBy = {MachinePassChange::Instructions, MachinePassChange::Operands, - MachinePassChange::Registers, MachinePassChange::CFG, - MachinePassChange::BlockLayout, MachinePassChange::TargetState}, - .ThreadSafety = PassThreadSafety::ThreadSafe, - }); - if (!Intervals) - return std::unexpected(Intervals.error()); - Analyses.Registry = std::move(Staging.Registry); - return {}; -} - -} // namespace rcc 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> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf(); - std::optional 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 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 &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 &Units) { - for (const PhysicalUnitAccess &Unit : Units) - Live.add(Unit.Unit, Unit.Lanes); -} - -void removeUnits(RegisterUnitLaneSet &Live, const std::vector &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 Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector &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> -buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, - const MachineBlockLiveness &Boundary) { - RegisterUnitLaneSet Live = Boundary.PhysicalLiveOut; - std::vector Updates; - for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *Mask = Operand.getIf(); - 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(); - 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(); - 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(); - 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(); - 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 repairPostRAMachineBlockLiveness(std::span Blocks, - const TargetDescription &Target, - const LiveVariablesAnalysis::Result &Liveness) { - std::vector 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 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 #include 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 +#include + +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 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 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 SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { + Result NewResult; + std::uint64_t Position = SlotSpacing; + auto Advance = [&Position]() -> Expected { + if (Position > std::numeric_limits::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()); +} + +Expected 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" -- cgit v1.2.3