diff options
Diffstat (limited to 'backend/lib')
38 files changed, 1310 insertions, 1195 deletions
diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 22bf032..470571d 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -37,7 +37,12 @@ set( MachineInstr.cpp MachineJumpTableInfo.cpp MachineLICM.cpp - MachineLiveness.cpp + SlotIndexes.cpp + LiveVariables.cpp + LiveInterval.cpp + LiveIntervals.cpp + LivePhysRegs.cpp + LiveRegUnits.cpp MachineMemoryFolding.cpp MachineMemOperand.cpp MachineMetadata.cpp @@ -120,8 +125,12 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineInstr.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineJumpTableInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLICM.h" - "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLiveness.h" - "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineLivenessRepair.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/SlotIndexes.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveVariables.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveInterval.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveIntervals.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LivePhysRegs.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRegUnits.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemoryFolding.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMemOperand.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineMetadata.h" @@ -242,7 +251,12 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineLICM.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariables.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveInterval.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervals.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegs.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnits.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemoryFolding.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" @@ -325,7 +339,12 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachineInstr.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineJumpTableInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineLICM.cpp" - "${CMAKE_CURRENT_SOURCE_DIR}/MachineLiveness.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/SlotIndexes.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveVariables.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveInterval.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveIntervals.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LivePhysRegs.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegUnits.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemoryFolding.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMemOperand.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineMetadata.cpp" diff --git a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp index 8937fd8..ff32eda 100644 --- a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp +++ b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/GlobalISel/InstructionSelect.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp index e61a801..60f388d 100644 --- a/backend/lib/CodeGen/GlobalISel/Legalizer.cpp +++ b/backend/lib/CodeGen/GlobalISel/Legalizer.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/GlobalISel/Legalizer.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp index 337db80..c36c500 100644 --- a/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp +++ b/backend/lib/CodeGen/GlobalISel/RegBankSelect.cpp @@ -2,10 +2,10 @@ #include "rcc/CodeGen/GlobalISel/RegBankSelect.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/LiveInterval.cpp b/backend/lib/CodeGen/LiveInterval.cpp new file mode 100644 index 0000000..22e0164 --- /dev/null +++ b/backend/lib/CodeGen/LiveInterval.cpp @@ -0,0 +1,184 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveInterval.h" + +#include <algorithm> +#include <cstddef> +#include <limits> +#include <ranges> +#include <unordered_set> + +namespace rcc { + +const LiveSegment *LiveRange::segmentAt(SlotIndex Position) const noexcept { + const auto Candidate = std::ranges::upper_bound( + Segments, Position, {}, [](const LiveSegment &Segment) { return Segment.Start; }); + if (Candidate == Segments.begin()) + return nullptr; + const LiveSegment &Previous = *std::prev(Candidate); + return Previous.contains(Position) ? &Previous : nullptr; +} + +const LiveValueNumber *LiveRange::value(LiveValueNumberID ID) const noexcept { + if (!ID.isValid() || ID.value() > Values.size()) + return nullptr; + const LiveValueNumber &Result = Values[ID.value() - 1U]; + return Result.ID == ID ? &Result : nullptr; +} + +const LiveValueNumber *LiveRange::valueAt(SlotIndex Position) const noexcept { + const LiveSegment *Segment = segmentAt(Position); + return Segment == nullptr ? nullptr : value(Segment->Value); +} + +bool LiveRange::liveAt(SlotIndex Position) const noexcept { + return segmentAt(Position) != nullptr; +} + +bool LiveRange::overlaps(const LiveRange &Other) const noexcept { + std::size_t Left = 0; + std::size_t Right = 0; + while (Left < Segments.size() && Right < Other.Segments.size()) { + if (Segments[Left].overlaps(Other.Segments[Right])) + return true; + if (Segments[Left].End <= Other.Segments[Right].Start) + ++Left; + else + ++Right; + } + return false; +} + +Expected<LiveValueNumberID> LiveRange::createValue(SlotIndex Definition, LiveValueState State, + std::optional<MachineInstrStableID> Origin) { + if (!Definition.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); + if (Values.size() >= std::numeric_limits<std::uint32_t>::max()) + return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); + const LiveValueNumberID ID = + LiveValueNumberID::fromValue(static_cast<std::uint32_t>(Values.size() + 1U)); + Values.push_back({ID, Definition, State, Origin}); + return ID; +} + +Expected<void> LiveRange::addSegment(LiveSegment Segment) { + if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || + value(Segment.Value) == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "live segment requires ordered indexes and a known value number"); + } + std::vector<LiveSegment> Candidate = Segments; + Candidate.push_back(Segment); + std::ranges::sort(Candidate, [](const LiveSegment &Left, const LiveSegment &Right) { + if (Left.Start != Right.Start) + return Left.Start < Right.Start; + return Left.End < Right.End; + }); + for (std::size_t Index = 1; Index < Candidate.size(); ++Index) { + if (Candidate[Index].Start < Candidate[Index - 1U].End && + Candidate[Index].Value != Candidate[Index - 1U].Value) { + return makeUnexpected(ErrorCode::VerificationError, + "live segments with different values overlap"); + } + } + Segments = std::move(Candidate); + mergeAdjacent(); + return {}; +} + +Expected<void> LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { + return addSegment({Start, End, Value}); +} + +Expected<void> LiveRange::remove(SlotIndex Start, SlotIndex End) { + if (!Start.isValid() || !End.isValid() || !(Start < End)) { + return makeUnexpected(ErrorCode::InvalidArgument, "removed live range must be nonempty"); + } + std::vector<LiveSegment> Result; + for (const LiveSegment &Segment : Segments) { + if (!(Segment.Start < End && Start < Segment.End)) { + Result.push_back(Segment); + continue; + } + if (Segment.Start < Start) + Result.push_back({Segment.Start, Start, Segment.Value}); + if (End < Segment.End) + Result.push_back({End, Segment.End, Segment.Value}); + } + Segments = std::move(Result); + mergeAdjacent(); + return {}; +} + +Expected<void> LiveRange::shrinkToUses(std::span<const SlotIndex> Uses) { + std::vector<LiveSegment> Result; + for (const LiveSegment &Segment : Segments) { + const LiveValueNumber *Value = value(Segment.Value); + if (Value == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "live segment references an unknown value number"); + std::optional<SlotIndex> LastUse; + for (const SlotIndex Use : Uses) { + if (Segment.contains(Use) && (!LastUse || *LastUse < Use)) + LastUse = Use; + } + if (!LastUse) { + if (Value->State == LiveValueState::Unused) + Result.push_back(Segment); + continue; + } + SlotIndex NewEnd = LastUse->deadSlot(); + if (Segment.End < NewEnd) + NewEnd = Segment.End; + if (Segment.Start < NewEnd) + Result.push_back({Segment.Start, NewEnd, Segment.Value}); + } + Segments = std::move(Result); + mergeAdjacent(); + return verify(); +} + +Expected<void> LiveRange::verify() const { + std::unordered_set<LiveValueNumberID> IDs; + for (std::size_t Index = 0; Index < Values.size(); ++Index) { + const LiveValueNumber &Value = Values[Index]; + if (!Value.ID.isValid() || Value.ID.value() != Index + 1U || !IDs.insert(Value.ID).second || + !Value.Definition.isValid()) { + return makeUnexpected(ErrorCode::VerificationError, + "live range contains an invalid value number"); + } + } + for (std::size_t Index = 0; Index < Segments.size(); ++Index) { + const LiveSegment &Segment = Segments[Index]; + if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || + value(Segment.Value) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "live range contains an invalid segment"); + } + if (Index != 0 && Segments[Index - 1U].End > Segment.Start) { + return makeUnexpected(ErrorCode::VerificationError, + "live range segments are not ordered and disjoint"); + } + } + return {}; +} + +void LiveRange::mergeAdjacent() { + if (Segments.empty()) + return; + std::vector<LiveSegment> Result; + Result.reserve(Segments.size()); + Result.push_back(Segments.front()); + for (std::size_t Index = 1; Index < Segments.size(); ++Index) { + LiveSegment &Previous = Result.back(); + const LiveSegment &Current = Segments[Index]; + if (Current.Value == Previous.Value && Current.Start <= Previous.End) { + if (Previous.End < Current.End) + Previous.End = Current.End; + continue; + } + Result.push_back(Current); + } + Segments = std::move(Result); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveIntervals.cpp b/backend/lib/CodeGen/LiveIntervals.cpp new file mode 100644 index 0000000..d8cb539 --- /dev/null +++ b/backend/lib/CodeGen/LiveIntervals.cpp @@ -0,0 +1,421 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveIntervals.h" + +#include "rcc/CodeGen/LiveRegUnits.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <vector> + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional<LaneMask> Filter) noexcept { + return !Filter || Access.intersects(*Filter); +} + +struct InstructionRangeEvent final { + bool HasUse = false; + bool HasNormalDef = false; + bool HasEarlyDef = false; + bool HasRegMaskClobber = false; +}; + +[[nodiscard]] Expected<InstructionRangeEvent> +virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional<LaneMask> Filter, + const MachineFunction &Function, const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + const Register *OperandReg = Operand.getIf<Register>(); + if (OperandReg == nullptr || *OperandReg != Reg) + continue; + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + if (!maskIntersects(*Lanes, Filter)) + continue; + Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef); + if (Operand.isDef()) { + if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) + Event.HasEarlyDef = true; + else + Event.HasNormalDef = true; + } + } + return Event; +} + +[[nodiscard]] Expected<InstructionRangeEvent> unitRangeEvent(const MachineInstr &Instruction, + RegisterUnitID Unit, + std::optional<LaneMask> Filter, + const TargetDescription &Target) { + InstructionRangeEvent Event; + for (const MachineOperand &Operand : Instruction.operands()) { + if (Operand.isRegister()) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isPhysical()) + continue; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + const auto Position = std::ranges::find_if( + *Units, [Unit](const PhysicalUnitAccess &Access) { return Access.Unit == Unit; }); + if (Position == Units->end() || !maskIntersects(Position->Lanes, Filter)) + continue; + Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && + !Operand.registerFlags().has(RegisterOperandFlag::Undef); + if (Operand.isDef()) { + if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) + Event.HasEarlyDef = true; + else + Event.HasNormalDef = true; + } + continue; + } + if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); + MaskOperand != nullptr && MaskOperand->Mask) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (!MaskOperand->Mask->clobbers(Description.Reg)) + continue; + if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { + return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); + })) { + Event.HasRegMaskClobber = true; + break; + } + } + continue; + } + if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>(); + MaskOperand != nullptr && MaskOperand->Mask) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (!MaskOperand->Mask->preserves(Description.Reg)) + continue; + if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { + return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); + })) { + Event.HasUse = true; + break; + } + } + } + } + return Event; +} + +template <typename EventFn, typename LiveOutFn> +[[nodiscard]] Expected<LiveRange> +buildLiveRange(MachineFunction &Function, const SlotIndexesAnalysis::Result &Indexes, + const EventFn &EventForInstruction, const LiveOutFn &IsLiveOut) { + LiveRange Range; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + std::optional<SlotIndex> End; + bool SawLaterDefinition = false; + if (IsLiveOut(*Block)) + End = Indexes.blockEnd(*Block); + + for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + auto Event = EventForInstruction(*Instruction); + if (!Event) + return std::unexpected(Event.error()); + if (!Event->HasUse && !Event->HasNormalDef && !Event->HasEarlyDef && + !Event->HasRegMaskClobber) { + continue; + } + + const SlotIndex InstructionSlot = Indexes.instructionIndex(*Instruction); + if (!InstructionSlot.isValid()) { + return makeUnexpected(ErrorCode::InternalError, + "live-range construction has no instruction SlotIndex"); + } + auto AddDefinition = [&](SlotIndex DefSlot, bool IsRegMask) -> Expected<void> { + const bool HasLiveValue = End && DefSlot < *End; + if (IsRegMask && !HasLiveValue) { + End.reset(); + SawLaterDefinition = true; + return {}; + } + const LiveValueState State = IsRegMask ? LiveValueState::Redefined + : HasLiveValue ? LiveValueState::Normal + : SawLaterDefinition ? LiveValueState::Redefined + : LiveValueState::Unused; + auto Value = Range.createValue(DefSlot, State, Instruction->stableID()); + if (!Value) + return std::unexpected(Value.error()); + const SlotIndex SegmentEnd = HasLiveValue ? *End : InstructionSlot.deadSlot(); + if (DefSlot < SegmentEnd) { + auto Added = Range.addSegment({DefSlot, SegmentEnd, *Value}); + if (!Added) + return std::unexpected(Added.error()); + } + End.reset(); + SawLaterDefinition = true; + return {}; + }; + + if (Event->HasNormalDef) { + auto Added = AddDefinition(InstructionSlot.registerSlot(), false); + if (!Added) + return std::unexpected(Added.error()); + } + if (Event->HasUse) { + const SlotIndex UseEnd = + Event->HasNormalDef ? InstructionSlot.registerSlot() : InstructionSlot.deadSlot(); + if (!End || *End < UseEnd) + End = UseEnd; + } + if (Event->HasEarlyDef) { + auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), false); + if (!Added) + return std::unexpected(Added.error()); + } else if (Event->HasRegMaskClobber) { + auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), true); + if (!Added) + return std::unexpected(Added.error()); + } + } + + if (End) { + const SlotIndex Start = Indexes.blockStart(*Block); + if (!Start.isValid() || !(*End > Start)) { + return makeUnexpected(ErrorCode::InternalError, + "live-in range has invalid block boundary indexes"); + } + auto Value = Range.createValue(Start, LiveValueState::Phi); + if (!Value) + return std::unexpected(Value.error()); + auto Added = Range.addSegment({Start, *End, *Value}); + if (!Added) + return std::unexpected(Added.error()); + } + } + auto Verification = Range.verify(); + if (!Verification) + return std::unexpected(Verification.error()); + return Range; +} + +[[nodiscard]] Expected<LaneMask> virtualRegisterFullLanes(Register Reg, + const MachineFunction &Function, + const TargetDescription &Target) { + return virtualRegisterLanes(Reg, Function, Target); +} + +[[nodiscard]] Expected<std::vector<LaneMask>> +partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, + const TargetDescription &Target) { + auto Full = virtualRegisterFullLanes(Reg, Function, Target); + if (!Full) + return std::unexpected(Full.error()); + std::vector<LaneMask> AccessMasks; + for (const MachineOperand &Operand : Function.registerInfo().regNoDebugOperands(Reg)) { + auto Lanes = virtualOperandLanes(Operand, Function, Target); + if (!Lanes) + return std::unexpected(Lanes.error()); + if (*Lanes != *Full && std::ranges::find(AccessMasks, *Lanes) == AccessMasks.end()) + AccessMasks.push_back(*Lanes); + } + if (AccessMasks.empty()) + return {}; + + std::vector<LaneMask> Groups{*Full}; + for (const LaneMask Access : AccessMasks) { + std::vector<LaneMask> Refined; + for (const LaneMask Group : Groups) { + const LaneMask Intersection = Group & Access; + const LaneMask Difference = subtractLanes(Group, Access); + if (!Intersection.empty()) + Refined.push_back(Intersection); + if (!Difference.empty()) + Refined.push_back(Difference); + } + Groups = std::move(Refined); + } + std::ranges::sort( + Groups, [](LaneMask Left, LaneMask Right) { return Left.rawValue() < Right.rawValue(); }); + return Groups; +} +} // namespace + +const LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) const noexcept { + const auto Position = Intervals.find(Reg); + return Position == Intervals.end() ? nullptr : &Position->second; +} + +LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) noexcept { + const auto Position = Intervals.find(Reg); + return Position == Intervals.end() ? nullptr : &Position->second; +} + +const LiveRange *LiveIntervalsAnalysis::Result::regUnitRange(RegisterUnitID Unit) const noexcept { + const auto Position = RegisterUnitRanges.find(Unit); + return Position == RegisterUnitRanges.end() ? nullptr : &Position->second; +} + +bool LiveIntervalsAnalysis::Result::interferes(Register Left, Register Right) const noexcept { + const LiveInterval *LeftInterval = interval(Left); + const LiveInterval *RightInterval = interval(Right); + return LeftInterval != nullptr && RightInterval != nullptr && + LeftInterval->overlaps(*RightInterval); +} + +bool LiveIntervalsAnalysis::Result::regMaskClobbers(const LiveInterval &Interval, + PhysicalRegister Candidate) const noexcept { + for (const RegMaskPosition &Position : RegMasks) { + if (Position.Mask && Position.Mask->clobbers(Candidate) && + Interval.MainRange.liveAt(Position.Position)) { + return true; + } + } + return false; +} + +Expected<void> LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, + std::span<const SlotIndex> Uses) { + LiveInterval *Value = interval(Reg); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no live interval"); + auto Main = Value->MainRange.shrinkToUses(Uses); + if (!Main) + return std::unexpected(Main.error()); + for (LiveSubRange &SubRange : Value->SubRanges) { + auto Shrunk = SubRange.Range.shrinkToUses(Uses); + if (!Shrunk) + return std::unexpected(Shrunk.error()); + } + return {}; +} + +bool LiveIntervalsAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id<LiveIntervalsAnalysis>()); +} + +Expected<LiveIntervalsAnalysis::Result> +LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + auto Indexes = Analyses.getResult<SlotIndexesAnalysis>(Function, Target); + if (!Indexes) + return std::unexpected(Indexes.error()); + auto Variables = Analyses.getResult<LiveVariablesAnalysis>(Function, Target); + if (!Variables) + return std::unexpected(Variables.error()); + + Result ResultValue; + ResultValue.Indexes = **Indexes; + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { + auto RegValue = Register::makeVirtual(Index); + if (!RegValue || !Function.registerInfo().isKnownVirtualRegister(*RegValue)) + continue; + const Register Reg = *RegValue; + auto MainRange = buildLiveRange( + Function, ResultValue.Indexes, + [&Function, &Target, Reg](const MachineInstr &Instruction) { + return virtualRangeEvent(Instruction, Reg, std::nullopt, Function, Target); + }, + [&Variables, Reg](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->VirtualLiveOut.intersects(Reg); + }); + if (!MainRange) + return std::unexpected(MainRange.error()); + if (MainRange->empty()) + continue; + + LiveInterval Interval; + Interval.Reg = Reg; + Interval.MainRange = std::move(*MainRange); + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + // Preserve the target-provided hint order. MachineRegisterInfo already de-duplicates + // hints, and their order is the deterministic preference order consumed by allocators. + Interval.AllocationHints = Info->get().AllocationHints; + + std::uint64_t Weight = 1; + for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) { + if (Operand.parent() == nullptr || Operand.registerFlags().has(RegisterOperandFlag::Undef)) { + continue; + } + Weight = Weight > std::numeric_limits<std::uint64_t>::max() - 10U + ? std::numeric_limits<std::uint64_t>::max() + : Weight + 10U; + } + Interval.SpillWeight = Weight; + + auto LaneGroups = partitionVirtualRegisterLanes(Reg, Function, Target); + if (!LaneGroups) + return std::unexpected(LaneGroups.error()); + for (const LaneMask Lanes : *LaneGroups) { + auto SubRange = buildLiveRange( + Function, ResultValue.Indexes, + [&Function, &Target, Reg, Lanes](const MachineInstr &Instruction) { + return virtualRangeEvent(Instruction, Reg, Lanes, Function, Target); + }, + [&Variables, Reg, Lanes](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); + }); + if (!SubRange) + return std::unexpected(SubRange.error()); + if (!SubRange->empty()) + Interval.SubRanges.push_back({Lanes, std::move(*SubRange)}); + } + ResultValue.Intervals.emplace(Reg, std::move(Interval)); + } + + for (const RegisterUnitDesc &Unit : Target.registers().registerUnits()) { + auto Range = buildLiveRange( + Function, ResultValue.Indexes, + [&Target, Unit](const MachineInstr &Instruction) { + return unitRangeEvent(Instruction, Unit.ID, std::nullopt, Target); + }, + [&Variables, Unit](const MachineBasicBlock &Block) { + const MachineBlockLiveness *Value = (*Variables)->block(Block); + return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit.ID); + }); + if (!Range) + return std::unexpected(Range.error()); + if (!Range->empty()) + ResultValue.RegisterUnitRanges.emplace(Unit.ID, std::move(*Range)); + } + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); + if (MaskOperand == nullptr) + continue; + if (!MaskOperand->Mask) + return makeUnexpected(ErrorCode::VerificationError, + "live intervals encountered a null register mask"); + ResultValue.RegMasks.push_back( + {ResultValue.Indexes.instructionIndex(*Instruction).earlyClobberSlot(), + Instruction->stableID(), MaskOperand->Mask}); + } + } + } + return ResultValue; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LivePhysRegs.cpp b/backend/lib/CodeGen/LivePhysRegs.cpp new file mode 100644 index 0000000..9bbc069 --- /dev/null +++ b/backend/lib/CodeGen/LivePhysRegs.cpp @@ -0,0 +1,174 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LivePhysRegs.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <cstddef> +#include <ranges> +#include <vector> + +namespace rcc { + +namespace { +struct OperandFlagUpdate final { + MachineOperand *Operand = nullptr; + RegisterOperandFlags Flags; +}; + +[[nodiscard]] bool intersects(const LiveRegUnits &Live, + const std::vector<PhysicalUnitAccess> &Units) noexcept { + return std::ranges::any_of(Units, [&Live](const PhysicalUnitAccess &Unit) { + return Live.intersects(Unit.Unit, Unit.Lanes); + }); +} + +void addUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.add(Unit.Unit, Unit.Lanes); +} + +void removeUnits(LiveRegUnits &Live, const std::vector<PhysicalUnitAccess> &Units) { + for (const PhysicalUnitAccess &Unit : Units) + Live.remove(Unit.Unit, Unit.Lanes); +} + +[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector<OperandFlagUpdate> &Updates, + MachineOperand &Operand) { + const auto Position = std::ranges::find_if( + Updates, [&Operand](const OperandFlagUpdate &Update) { return Update.Operand == &Operand; }); + if (Position != Updates.end()) + return *Position; + Updates.push_back({&Operand, Operand.registerFlags()}); + return Updates.back(); +} + +[[nodiscard]] Expected<std::vector<OperandFlagUpdate>> +buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, + const MachineBlockLiveness &Boundary) { + LiveRegUnits Live = Boundary.PhysicalLiveOut; + std::vector<OperandFlagUpdate> Updates; + for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; + Instruction = Instruction->previous()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); + if (Mask == nullptr) + continue; + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "post-RA liveness repair encountered a null live-out mask"); + } + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (Mask->Mask->preserves(Register.Reg)) + addPhysicalRegister(Live, Register); + } + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); + Update.Flags.clear(RegisterOperandFlag::Dead); + if (!Operand->isDef()) + continue; + const Register *Reg = Operand->getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + auto Units = physicalOperandUnits(*Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + if (!intersects(Live, *Units)) + Update.Flags.set(RegisterOperandFlag::Dead); + } + + for (const MachineOperand &Operand : Instruction->operands()) { + if (Operand.isRegister() && Operand.isDef()) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + auto Units = physicalOperandUnits(Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + removeUnits(Live, *Units); + continue; + } + const auto *Mask = Operand.getIf<RegisterMaskOperand>(); + if (Mask == nullptr) + continue; + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "post-RA liveness repair encountered a null register mask"); + } + LiveRegUnits Clobbers; + for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { + if (Mask->Mask->clobbers(Register.Reg)) + addPhysicalRegister(Clobbers, Register); + } + Live.subtract(Clobbers); + } + + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + if (Operand == nullptr || !Operand->isRegister()) + continue; + OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); + Update.Flags.clear(RegisterOperandFlag::Kill); + if (!Operand->isUse() || Operand->isDebugUse() || + Operand->registerFlags().has(RegisterOperandFlag::Undef)) { + continue; + } + const Register *Reg = Operand->getIf<Register>(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + if (isReservedPhysicalRegister(*Reg, Block.function(), Target)) + continue; + auto Units = physicalOperandUnits(*Operand, Target); + if (!Units) + return std::unexpected(Units.error()); + if (!intersects(Live, *Units)) + Update.Flags.set(RegisterOperandFlag::Kill); + addUnits(Live, *Units); + } + } + if (Live != Boundary.PhysicalLiveIn) { + return makeUnexpected(ErrorCode::InternalError, + "post-RA local liveness repair changed the block boundary"); + } + return Updates; +} +} // namespace + +Expected<bool> repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks, + const TargetDescription &Target, + const LiveVariablesAnalysis::Result &Liveness) { + std::vector<OperandFlagUpdate> Updates; + for (MachineBasicBlock *Block : Blocks) { + const MachineBlockLiveness *Boundary = Liveness.block(*Block); + if (Boundary == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "post-RA scheduler lost a block liveness boundary"); + } + auto BlockUpdates = buildBlockLivenessRepairPlan(*Block, Target, *Boundary); + if (!BlockUpdates) + return std::unexpected(BlockUpdates.error()); + Updates.insert(Updates.end(), BlockUpdates->begin(), BlockUpdates->end()); + } + bool Changed = false; + for (const OperandFlagUpdate &Update : Updates) { + Changed |= Update.Operand->registerFlags() != Update.Flags; + auto Applied = Update.Operand->setRegisterFlags(Update.Flags); + if (!Applied) + return std::unexpected(Applied.error()); + } + return Changed; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveRegUnits.cpp b/backend/lib/CodeGen/LiveRegUnits.cpp new file mode 100644 index 0000000..7df55c0 --- /dev/null +++ b/backend/lib/CodeGen/LiveRegUnits.cpp @@ -0,0 +1,280 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegUnits.h" + +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include <algorithm> +#include <bit> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <ranges> +#include <unordered_map> +#include <vector> + +namespace rcc { + +namespace { +[[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { + return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); +} + +template <typename KeyT> +void addLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) { + if (Lanes.empty()) + return; + const auto Position = Values.find(Key); + if (Position == Values.end()) { + Values.emplace(Key, Lanes); + return; + } + Position->second = Position->second | Lanes; +} + +template <typename KeyT> +void removeLanes(std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, LaneMask Lanes) { + const auto Position = Values.find(Key); + if (Position == Values.end() || Lanes.empty()) + return; + Position->second = subtractLanes(Position->second, Lanes); + if (Position->second.empty()) + Values.erase(Position); +} + +template <typename KeyT> +[[nodiscard]] LaneMask lanesFor(const std::unordered_map<KeyT, LaneMask> &Values, + KeyT Key) noexcept { + const auto Position = Values.find(Key); + return Position == Values.end() ? LaneMask{} : Position->second; +} + +template <typename KeyT> +[[nodiscard]] bool containsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, + LaneMask Lanes) noexcept { + const LaneMask Present = lanesFor(Values, Key); + return !Present.empty() && Present.contains(Lanes); +} + +template <typename KeyT> +[[nodiscard]] bool intersectsLanes(const std::unordered_map<KeyT, LaneMask> &Values, KeyT Key, + LaneMask Lanes) noexcept { + return lanesFor(Values, Key).intersects(Lanes); +} + +template <typename KeyT> +void uniteLanes(std::unordered_map<KeyT, LaneMask> &Values, + const std::unordered_map<KeyT, LaneMask> &Other) { + for (const auto &[Key, Lanes] : Other) + addLanes(Values, Key, Lanes); +} + +template <typename KeyT> +void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values, + const std::unordered_map<KeyT, LaneMask> &Other) { + for (const auto &[Key, Lanes] : Other) + removeLanes(Values, Key, Lanes); +} + +} // namespace + +LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept { + std::uint64_t View = UnitViewLanes.rawValue(); + const std::uint64_t Selected = View & RegisterLanes.rawValue(); + std::uint64_t Normalized = 0; + std::uint32_t UnitLane = 0; + while (View != 0) { + const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); + if ((Selected & RegisterLane) != 0) + Normalized |= std::uint64_t{1} << UnitLane; + View &= View - 1U; + ++UnitLane; + } + return LaneMask::fromRaw(Normalized); +} + +LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept { + std::uint64_t View = UnitViewLanes.rawValue(); + const std::uint64_t Selected = UnitLanes.rawValue(); + std::uint64_t RegisterLanes = 0; + std::uint32_t UnitLane = 0; + while (View != 0) { + const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); + if ((Selected & (std::uint64_t{1} << UnitLane)) != 0) + RegisterLanes |= RegisterLane; + View &= View - 1U; + ++UnitLane; + } + return LaneMask::fromRaw(RegisterLanes); +} + +LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept { + LaneMask Result; + for (const RegisterUnitLane &Unit : Description.Units) + Result = Result | Unit.Lanes; + return Result; +} + +LiveRegUnits physicalRegisterCoverage(const PhysicalRegisterDesc &Description, LaneMask Requested) { + LiveRegUnits Result; + for (const RegisterUnitLane &Unit : Description.Units) + Result.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes, Requested)); + return Result; +} + +bool isSubset(const LiveRegUnits &Subset, const LiveRegUnits &Superset) noexcept { + return std::ranges::all_of(Subset.entries(), [&Superset](const auto &Entry) { + return Superset.contains(Entry.first, Entry.second); + }); +} + +std::size_t laneCount(const LiveRegUnits &Set) noexcept { + std::size_t Result = 0; + for (const auto &[Unit, Lanes] : Set.entries()) { + (void)Unit; + Result += static_cast<std::size_t>(std::popcount(Lanes.rawValue())); + } + return Result; +} + +[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) { + if (!Reg.isVirtual()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "virtual lane query requires a virtual register"); + } + auto Info = Function.registerInfo().virtualRegisterInfo(Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional<RegisterClassID> ClassID = Info->get().RegClass; + if (!ClassID) + return LaneMask::all(); + const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID); + if (Class == nullptr || Class->Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or empty register class"); + } + return Class->Lanes; +} + +[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand, + const MachineFunction &Function, + const TargetDescription &Target) { + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "virtual lane query requires a virtual-register operand"); + } + if (Operand.subReg().value() != 0) { + const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg()); + if (SubReg == nullptr || SubReg->Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or empty subregister lane mask"); + } + return SubReg->Lanes; + } + + return virtualRegisterLanes(*Reg, Function, Target); +} + +[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> +physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { + const Register *Reg = Operand.getIf<Register>(); + const std::optional<PhysicalRegister> Original = + Reg == nullptr ? std::nullopt : Reg->physicalRegister(); + if (!Original) { + return makeUnexpected(ErrorCode::InvalidArgument, + "physical unit query requires a physical-register operand"); + } + + PhysicalRegister Effective = *Original; + if (Operand.subReg().value() != 0) { + const std::optional<PhysicalRegister> SubRegister = + Target.registers().subRegister(*Original, Operand.subReg()); + if (!SubRegister) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register has no requested subregister projection"); + } + Effective = *SubRegister; + } + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Effective); + if (Description == nullptr || Description->Units.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "liveness encountered an unknown or unitless physical register"); + } + + std::vector<PhysicalUnitAccess> Result; + Result.reserve(Description->Units.size()); + for (const RegisterUnitLane &Unit : Description->Units) { + if (Unit.Lanes.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register unit has an empty lane mask"); + } + Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes, LaneMask::all())}); + } + return Result; +} + +void addPhysicalRegister(LiveRegUnits &Set, const PhysicalRegisterDesc &Description, + LaneMask Requested) { + Set.unite(physicalRegisterCoverage(Description, Requested)); +} + +[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, + const TargetDescription &Target) noexcept { + const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); + return Physical && (Function.registerInfo().isReserved(*Physical) || + Target.registers().isReservedRegister(*Physical)); +} + +[[nodiscard]] Expected<void> addRegisterMaskDefs(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (Mask.clobbers(Description.Reg)) + addPhysicalRegister(Set, Description); + } + return {}; +} + +[[nodiscard]] Expected<void> addRegisterMaskUses(LiveRegUnits &Set, const RegisterMask &Mask, + const TargetDescription &Target) { + for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { + if (Mask.preserves(Description.Reg)) + addPhysicalRegister(Set, Description); + } + return {}; +} +LaneMask LiveRegUnits::lanes(RegisterUnitID Unit) const noexcept { + return lanesFor(Values, Unit); +} + +bool LiveRegUnits::contains(RegisterUnitID Unit, LaneMask Lanes) const noexcept { + return containsLanes(Values, Unit, Lanes); +} + +bool LiveRegUnits::intersects(RegisterUnitID Unit, LaneMask Lanes) const noexcept { + return intersectsLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::add(RegisterUnitID Unit, LaneMask Lanes) { + if (Unit.value() != 0 && !Lanes.empty()) + addLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::remove(RegisterUnitID Unit, LaneMask Lanes) { + removeLanes(Values, Unit, Lanes); +} + +void LiveRegUnits::unite(const LiveRegUnits &Other) { + uniteLanes(Values, Other.Values); +} + +void LiveRegUnits::subtract(const LiveRegUnits &Other) { + subtractLaneSets(Values, Other.Values); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineLiveness.cpp b/backend/lib/CodeGen/LiveVariables.cpp index 9882b11..7323e0d 100644 --- a/backend/lib/CodeGen/MachineLiveness.cpp +++ b/backend/lib/CodeGen/LiveVariables.cpp @@ -1,13 +1,16 @@ // SPDX-License-Identifier: GPL-3.0-or-later -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/CodeGen/LiveInterval.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" +#include "rcc/CodeGen/SlotIndexes.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetRegisterInfo.h" @@ -20,16 +23,14 @@ #include <optional> #include <ranges> #include <string> +#include <unordered_map> #include <unordered_set> #include <utility> #include <vector> namespace rcc { -namespace { - -constexpr std::uint64_t SlotSpacing = 16; -constexpr std::uint64_t SlotAlignmentMask = 3; +namespace { [[nodiscard]] LaneMask subtractLanes(LaneMask Left, LaneMask Right) noexcept { return LaneMask::fromRaw(Left.rawValue() & ~Right.rawValue()); } @@ -90,182 +91,7 @@ void subtractLaneSets(std::unordered_map<KeyT, LaneMask> &Values, removeLanes(Values, Key, Lanes); } -struct PhysicalUnitAccess final { - RegisterUnitID Unit; - LaneMask Lanes; -}; - -[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - const std::uint64_t Selected = View & RegisterLanes.rawValue(); - std::uint64_t Normalized = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); - if ((Selected & RegisterLane) != 0) - Normalized |= std::uint64_t{1} << UnitLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(Normalized); -} - -[[nodiscard]] LaneMask denormalizeUnitLanes(LaneMask UnitLanes, LaneMask UnitViewLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - const std::uint64_t Selected = UnitLanes.rawValue(); - std::uint64_t RegisterLanes = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); - if ((Selected & (std::uint64_t{1} << UnitLane)) != 0) - RegisterLanes |= RegisterLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(RegisterLanes); -} - -[[nodiscard]] LaneMask physicalRegisterLanes(const PhysicalRegisterDesc &Description) noexcept { - LaneMask Result; - for (const RegisterUnitLane &Unit : Description.Units) - Result = Result | Unit.Lanes; - return Result; -} - -[[nodiscard]] RegisterUnitLaneSet physicalRegisterCoverage(const PhysicalRegisterDesc &Description, - LaneMask Requested) { - RegisterUnitLaneSet Result; - for (const RegisterUnitLane &Unit : Description.Units) - Result.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes, Requested)); - return Result; -} - -[[nodiscard]] bool isSubset(const RegisterUnitLaneSet &Subset, - const RegisterUnitLaneSet &Superset) noexcept { - return std::ranges::all_of(Subset.entries(), [&Superset](const auto &Entry) { - return Superset.contains(Entry.first, Entry.second); - }); -} - -[[nodiscard]] std::size_t laneCount(const RegisterUnitLaneSet &Set) noexcept { - std::size_t Result = 0; - for (const auto &[Unit, Lanes] : Set.entries()) { - (void)Unit; - Result += static_cast<std::size_t>(std::popcount(Lanes.rawValue())); - } - return Result; -} - -[[nodiscard]] Expected<LaneMask> virtualRegisterLanes(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) { - if (!Reg.isVirtual()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "virtual lane query requires a virtual register"); - } - auto Info = Function.registerInfo().virtualRegisterInfo(Reg); - if (!Info) - return std::unexpected(Info.error()); - const std::optional<RegisterClassID> ClassID = Info->get().RegClass; - if (!ClassID) - return LaneMask::all(); - const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID); - if (Class == nullptr || Class->Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or empty register class"); - } - return Class->Lanes; -} - -[[nodiscard]] Expected<LaneMask> virtualOperandLanes(const MachineOperand &Operand, - const MachineFunction &Function, - const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || !Reg->isVirtual()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "virtual lane query requires a virtual-register operand"); - } - if (Operand.subReg().value() != 0) { - const SubRegIndexDesc *SubReg = Target.registers().subRegIndex(Operand.subReg()); - if (SubReg == nullptr || SubReg->Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or empty subregister lane mask"); - } - return SubReg->Lanes; - } - - return virtualRegisterLanes(*Reg, Function, Target); -} - -[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - const std::optional<PhysicalRegister> Original = - Reg == nullptr ? std::nullopt : Reg->physicalRegister(); - if (!Original) { - return makeUnexpected(ErrorCode::InvalidArgument, - "physical unit query requires a physical-register operand"); - } - - PhysicalRegister Effective = *Original; - if (Operand.subReg().value() != 0) { - const std::optional<PhysicalRegister> SubRegister = - Target.registers().subRegister(*Original, Operand.subReg()); - if (!SubRegister) { - return makeUnexpected(ErrorCode::VerificationError, - "physical register has no requested subregister projection"); - } - Effective = *SubRegister; - } - const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Effective); - if (Description == nullptr || Description->Units.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "liveness encountered an unknown or unitless physical register"); - } - - std::vector<PhysicalUnitAccess> Result; - Result.reserve(Description->Units.size()); - for (const RegisterUnitLane &Unit : Description->Units) { - if (Unit.Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "physical register unit has an empty lane mask"); - } - Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes, LaneMask::all())}); - } - return Result; -} - -void addPhysicalRegister(RegisterUnitLaneSet &Set, const PhysicalRegisterDesc &Description, - LaneMask Requested = LaneMask::all()) { - Set.unite(physicalRegisterCoverage(Description, Requested)); -} - -[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) noexcept { - const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] Expected<void> addRegisterMaskDefs(RegisterUnitLaneSet &Set, const RegisterMask &Mask, - const TargetDescription &Target) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (Mask.clobbers(Description.Reg)) - addPhysicalRegister(Set, Description); - } - return {}; -} - -[[nodiscard]] Expected<void> addRegisterMaskUses(RegisterUnitLaneSet &Set, const RegisterMask &Mask, - const TargetDescription &Target) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (Mask.preserves(Description.Reg)) - addPhysicalRegister(Set, Description); - } - return {}; -} - -[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses, - RegisterUnitLaneSet &PhysicalUses, +[[nodiscard]] Expected<void> addOperandUse(RegisterLaneSet &VirtualUses, LiveRegUnits &PhysicalUses, const MachineOperand &Operand, const MachineFunction &Function, const TargetDescription &Target) { @@ -291,8 +117,7 @@ void addPhysicalRegister(RegisterUnitLaneSet &Set, const PhysicalRegisterDesc &D return {}; } -[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs, - RegisterUnitLaneSet &PhysicalDefs, +[[nodiscard]] Expected<void> addOperandDef(RegisterLaneSet &VirtualDefs, LiveRegUnits &PhysicalDefs, const MachineOperand &Operand, const MachineFunction &Function, const TargetDescription &Target) { @@ -331,7 +156,7 @@ struct LivenessEdgeKeyHash final { struct EdgeLivenessUses final { RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; + LiveRegUnits Physical; }; [[nodiscard]] Expected<LiveVariablesAnalysis::Result> @@ -408,8 +233,8 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T RegisterLaneSet InstructionVirtualUses; RegisterLaneSet InstructionVirtualDefs; - RegisterUnitLaneSet InstructionPhysicalUses; - RegisterUnitLaneSet InstructionPhysicalDefs; + LiveRegUnits InstructionPhysicalUses; + LiveRegUnits InstructionPhysicalDefs; for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { const MachineOperand &Operand = *Instruction->operandAt(Index); if (Operand.isRegister()) { @@ -453,7 +278,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T Liveness.VirtualUses.unite(NewVirtualUses); Liveness.VirtualDefs.unite(InstructionVirtualDefs); - RegisterUnitLaneSet NewPhysicalUses = InstructionPhysicalUses; + LiveRegUnits NewPhysicalUses = InstructionPhysicalUses; NewPhysicalUses.subtract(Liveness.PhysicalDefs); Liveness.PhysicalUses.unite(NewPhysicalUses); Liveness.PhysicalDefs.unite(InstructionPhysicalDefs); @@ -466,7 +291,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T for (const MachineBasicBlock *Block : Blocks | std::views::reverse) { MachineBlockLiveness &Liveness = Result.getOrCreateBlock(*Block); RegisterLaneSet VirtualOut; - RegisterUnitLaneSet PhysicalOut; + LiveRegUnits PhysicalOut; for (const MachineSuccessor &Successor : Block->successors()) { if (Successor.Block == nullptr || Result.block(*Successor.Block) == nullptr) { return makeUnexpected(ErrorCode::VerificationError, @@ -485,7 +310,7 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T RegisterLaneSet VirtualIn = VirtualOut; VirtualIn.subtract(Liveness.VirtualDefs); VirtualIn.unite(Liveness.VirtualUses); - RegisterUnitLaneSet PhysicalIn = PhysicalOut; + LiveRegUnits PhysicalIn = PhysicalOut; PhysicalIn.subtract(Liveness.PhysicalDefs); PhysicalIn.unite(Liveness.PhysicalUses); @@ -501,241 +326,12 @@ computeLiveVariables(const MachineFunction &Function, const TargetDescription &T } return Result; } - -[[nodiscard]] bool maskIntersects(LaneMask Access, std::optional<LaneMask> Filter) noexcept { - return !Filter || Access.intersects(*Filter); -} - -struct InstructionRangeEvent final { - bool HasUse = false; - bool HasNormalDef = false; - bool HasEarlyDef = false; - bool HasRegMaskClobber = false; -}; - -[[nodiscard]] Expected<InstructionRangeEvent> -virtualRangeEvent(const MachineInstr &Instruction, Register Reg, std::optional<LaneMask> Filter, - const MachineFunction &Function, const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - const Register *OperandReg = Operand.getIf<Register>(); - if (OperandReg == nullptr || *OperandReg != Reg) - continue; - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - if (!maskIntersects(*Lanes, Filter)) - continue; - Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && - !Operand.registerFlags().has(RegisterOperandFlag::Undef); - if (Operand.isDef()) { - if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) - Event.HasEarlyDef = true; - else - Event.HasNormalDef = true; - } - } - return Event; -} - -[[nodiscard]] Expected<InstructionRangeEvent> unitRangeEvent(const MachineInstr &Instruction, - RegisterUnitID Unit, - std::optional<LaneMask> Filter, - const TargetDescription &Target) { - InstructionRangeEvent Event; - for (const MachineOperand &Operand : Instruction.operands()) { - if (Operand.isRegister()) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || !Reg->isPhysical()) - continue; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - const auto Position = std::ranges::find_if( - *Units, [Unit](const PhysicalUnitAccess &Access) { return Access.Unit == Unit; }); - if (Position == Units->end() || !maskIntersects(Position->Lanes, Filter)) - continue; - Event.HasUse |= Operand.isUse() && !Operand.isDebugUse() && - !Operand.registerFlags().has(RegisterOperandFlag::Undef); - if (Operand.isDef()) { - if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber)) - Event.HasEarlyDef = true; - else - Event.HasNormalDef = true; - } - continue; - } - if (const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); - MaskOperand != nullptr && MaskOperand->Mask) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (!MaskOperand->Mask->clobbers(Description.Reg)) - continue; - if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { - return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); - })) { - Event.HasRegMaskClobber = true; - break; - } - } - continue; - } - if (const auto *MaskOperand = Operand.getIf<LiveOutRegisterMaskOperand>(); - MaskOperand != nullptr && MaskOperand->Mask) { - for (const PhysicalRegisterDesc &Description : Target.registers().physicalRegisters()) { - if (!MaskOperand->Mask->preserves(Description.Reg)) - continue; - if (std::ranges::any_of(Description.Units, [Unit, Filter](const RegisterUnitLane &Access) { - return Access.Unit == Unit && maskIntersects(Access.Lanes, Filter); - })) { - Event.HasUse = true; - break; - } - } - } - } - return Event; -} - -template <typename EventFn, typename LiveOutFn> -[[nodiscard]] Expected<LiveRange> -buildLiveRange(MachineFunction &Function, const SlotIndexesAnalysis::Result &Indexes, - const EventFn &EventForInstruction, const LiveOutFn &IsLiveOut) { - LiveRange Range; - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - std::optional<SlotIndex> End; - bool SawLaterDefinition = false; - if (IsLiveOut(*Block)) - End = Indexes.blockEnd(*Block); - - for (MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - auto Event = EventForInstruction(*Instruction); - if (!Event) - return std::unexpected(Event.error()); - if (!Event->HasUse && !Event->HasNormalDef && !Event->HasEarlyDef && - !Event->HasRegMaskClobber) { - continue; - } - - const SlotIndex InstructionSlot = Indexes.instructionIndex(*Instruction); - if (!InstructionSlot.isValid()) { - return makeUnexpected(ErrorCode::InternalError, - "live-range construction has no instruction SlotIndex"); - } - auto AddDefinition = [&](SlotIndex DefSlot, bool IsRegMask) -> Expected<void> { - const bool HasLiveValue = End && DefSlot < *End; - if (IsRegMask && !HasLiveValue) { - End.reset(); - SawLaterDefinition = true; - return {}; - } - const LiveValueState State = IsRegMask ? LiveValueState::Redefined - : HasLiveValue ? LiveValueState::Normal - : SawLaterDefinition ? LiveValueState::Redefined - : LiveValueState::Unused; - auto Value = Range.createValue(DefSlot, State, Instruction->stableID()); - if (!Value) - return std::unexpected(Value.error()); - const SlotIndex SegmentEnd = HasLiveValue ? *End : InstructionSlot.deadSlot(); - if (DefSlot < SegmentEnd) { - auto Added = Range.addSegment({DefSlot, SegmentEnd, *Value}); - if (!Added) - return std::unexpected(Added.error()); - } - End.reset(); - SawLaterDefinition = true; - return {}; - }; - - if (Event->HasNormalDef) { - auto Added = AddDefinition(InstructionSlot.registerSlot(), false); - if (!Added) - return std::unexpected(Added.error()); - } - if (Event->HasUse) { - const SlotIndex UseEnd = - Event->HasNormalDef ? InstructionSlot.registerSlot() : InstructionSlot.deadSlot(); - if (!End || *End < UseEnd) - End = UseEnd; - } - if (Event->HasEarlyDef) { - auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), false); - if (!Added) - return std::unexpected(Added.error()); - } else if (Event->HasRegMaskClobber) { - auto Added = AddDefinition(InstructionSlot.earlyClobberSlot(), true); - if (!Added) - return std::unexpected(Added.error()); - } - } - - if (End) { - const SlotIndex Start = Indexes.blockStart(*Block); - if (!Start.isValid() || !(*End > Start)) { - return makeUnexpected(ErrorCode::InternalError, - "live-in range has invalid block boundary indexes"); - } - auto Value = Range.createValue(Start, LiveValueState::Phi); - if (!Value) - return std::unexpected(Value.error()); - auto Added = Range.addSegment({Start, *End, *Value}); - if (!Added) - return std::unexpected(Added.error()); - } - } - auto Verification = Range.verify(); - if (!Verification) - return std::unexpected(Verification.error()); - return Range; -} - -[[nodiscard]] Expected<LaneMask> virtualRegisterFullLanes(Register Reg, - const MachineFunction &Function, - const TargetDescription &Target) { - return virtualRegisterLanes(Reg, Function, Target); -} - -[[nodiscard]] Expected<std::vector<LaneMask>> -partitionVirtualRegisterLanes(Register Reg, MachineFunction &Function, - const TargetDescription &Target) { - auto Full = virtualRegisterFullLanes(Reg, Function, Target); - if (!Full) - return std::unexpected(Full.error()); - std::vector<LaneMask> AccessMasks; - for (const MachineOperand &Operand : Function.registerInfo().regNoDebugOperands(Reg)) { - auto Lanes = virtualOperandLanes(Operand, Function, Target); - if (!Lanes) - return std::unexpected(Lanes.error()); - if (*Lanes != *Full && std::ranges::find(AccessMasks, *Lanes) == AccessMasks.end()) - AccessMasks.push_back(*Lanes); - } - if (AccessMasks.empty()) - return {}; - - std::vector<LaneMask> Groups{*Full}; - for (const LaneMask Access : AccessMasks) { - std::vector<LaneMask> Refined; - for (const LaneMask Group : Groups) { - const LaneMask Intersection = Group & Access; - const LaneMask Difference = subtractLanes(Group, Access); - if (!Intersection.empty()) - Refined.push_back(Intersection); - if (!Difference.empty()) - Refined.push_back(Difference); - } - Groups = std::move(Refined); - } - std::ranges::sort( - Groups, [](LaneMask Left, LaneMask Right) { return Left.rawValue() < Right.rawValue(); }); - return Groups; -} - [[nodiscard]] Expected<std::vector<MachineBasicBlockLiveIn>> -canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescription &Target) { +canonicalPhysicalLiveIns(const LiveRegUnits &Units, const TargetDescription &Target) { struct Candidate final { const PhysicalRegisterDesc *Description = nullptr; LaneMask RegisterLanes; - RegisterUnitLaneSet Coverage; + LiveRegUnits Coverage; std::size_t ExtraLanes = 0; bool Selected = false; }; @@ -751,8 +347,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti std::uint64_t PendingLanes = RelevantLanes.rawValue(); while (PendingLanes != 0) { const std::uint64_t Lane = std::uint64_t{1} << std::countr_zero(PendingLanes); - const RegisterUnitLaneSet Coverage = - physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane)); + const LiveRegUnits Coverage = physicalRegisterCoverage(Description, LaneMask::fromRaw(Lane)); if (isSubset(Coverage, Units)) SelectableLanes |= Lane; PendingLanes &= PendingLanes - 1U; @@ -768,7 +363,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti Candidates.push_back(std::move(Value)); } - RegisterUnitLaneSet Covered; + LiveRegUnits Covered; std::vector<MachineBasicBlockLiveIn> Result; while (Covered != Units) { Candidate *Best = nullptr; @@ -777,7 +372,7 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti for (Candidate &Value : Candidates) { if (Value.Selected) continue; - RegisterUnitLaneSet NewCoverage = Value.Coverage; + LiveRegUnits NewCoverage = Value.Coverage; NewCoverage.subtract(Covered); const std::size_t NewLanes = laneCount(NewCoverage); if (NewLanes == 0) @@ -812,9 +407,9 @@ canonicalPhysicalLiveIns(const RegisterUnitLaneSet &Units, const TargetDescripti return Result; } -[[nodiscard]] Expected<RegisterUnitLaneSet> -liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns, const TargetDescription &Target) { - RegisterUnitLaneSet Result; +[[nodiscard]] Expected<LiveRegUnits> liveInUnits(std::span<const MachineBasicBlockLiveIn> LiveIns, + const TargetDescription &Target) { + LiveRegUnits Result; for (const MachineBasicBlockLiveIn &LiveIn : LiveIns) { const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(LiveIn.PhysReg); if (Description == nullptr) { @@ -848,7 +443,7 @@ struct LivenessRebuildPlan final { [[nodiscard]] Expected<bool> liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, - const RegisterUnitLaneSet &Physical, const MachineFunction &Function, + const LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target, bool TreatReservedAsLive) { const Register *Reg = Operand.getIf<Register>(); if (Reg == nullptr || Reg->isNoRegister()) @@ -871,7 +466,7 @@ liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, [[nodiscard]] Expected<void> removeOperandFromLiveSet(const MachineOperand &Operand, RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, + LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target) { const Register *Reg = Operand.getIf<Register>(); @@ -893,18 +488,17 @@ liveSetIntersects(const MachineOperand &Operand, const RegisterLaneSet &Virtual, } [[nodiscard]] Expected<void> addOperandToLiveSet(const MachineOperand &Operand, - RegisterLaneSet &Virtual, - RegisterUnitLaneSet &Physical, + RegisterLaneSet &Virtual, LiveRegUnits &Physical, const MachineFunction &Function, const TargetDescription &Target) { return addOperandUse(Virtual, Physical, Operand, Function, Target); } -[[nodiscard]] Expected<RegisterUnitLaneSet> -requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, const MachineFunction &Function, - const TargetDescription &Target) { +[[nodiscard]] Expected<LiveRegUnits> requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, + const MachineFunction &Function, + const TargetDescription &Target) { RegisterLaneSet Virtual; - RegisterUnitLaneSet Physical; + LiveRegUnits Physical; for (const MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; Instruction = Instruction->previous()) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); @@ -940,7 +534,7 @@ requiredLocalPhysicalLiveIns(const MachineBasicBlock &Block, const MachineFuncti return makeUnexpected(ErrorCode::VerificationError, "liveness verification encountered a null register mask"); } - RegisterUnitLaneSet Clobbers; + LiveRegUnits Clobbers; auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); if (!Added) return std::unexpected(Added.error()); @@ -981,7 +575,7 @@ buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescriptio std::move(*NewLiveIns)}); RegisterLaneSet Virtual = BlockVariables->VirtualLiveOut; - RegisterUnitLaneSet Physical = BlockVariables->PhysicalLiveOut; + LiveRegUnits Physical = BlockVariables->PhysicalLiveOut; for (const MachineInstr *Instruction = Block->lastInstruction(); Instruction != nullptr; Instruction = Instruction->previous()) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); @@ -1030,7 +624,7 @@ buildLivenessRebuildPlan(const MachineFunction &Function, const TargetDescriptio if (!MaskOperand->Mask) return makeUnexpected(ErrorCode::VerificationError, "liveness rebuild encountered a null register mask"); - RegisterUnitLaneSet Clobbers; + LiveRegUnits Clobbers; auto Added = addRegisterMaskDefs(Clobbers, *MaskOperand->Mask, Target); if (!Added) return std::unexpected(Added.error()); @@ -1221,149 +815,8 @@ resolveLivenessPlan(MachineFunction &Function, const LivenessRebuildPlan &Plan) } return Changed; } - } // namespace -SlotIndex -SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept { - const auto Position = InstructionSlots.find(Instruction.stableID()); - return Position == InstructionSlots.end() ? SlotIndex{} : Position->second; -} - -SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept { - const auto Position = BlockStarts.find(&Block); - return Position == BlockStarts.end() ? SlotIndex{} : Position->second; -} - -SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept { - const auto Position = BlockEnds.find(&Block); - return Position == BlockEnds.end() ? SlotIndex{} : Position->second; -} - -const MachineInstr * -SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept { - if (!Index.isValid()) - return nullptr; - const auto Position = SlotToInstruction.find(Index.baseIndex().value()); - return Position == SlotToInstruction.end() ? nullptr : Position->second; -} - -const MachineBasicBlock * -SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept { - if (!Index.isValid()) - return nullptr; - for (const MachineBasicBlock *Block : BlocksByStart) { - const SlotIndex Start = blockStart(*Block); - const SlotIndex End = blockEnd(*Block); - if (!(Index < Start) && Index < End) - return Block; - } - return nullptr; -} - -Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) { - const MachineBasicBlock *Block = Instruction.parent(); - if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) { - return makeUnexpected(ErrorCode::InvalidArgument, - "SlotIndex insertion requires a linked indexed instruction"); - } - if (InstructionSlots.contains(Instruction.stableID())) { - return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex"); - } - - const MachineInstr *Previous = Instruction.previous(); - const MachineInstr *Next = Instruction.next(); - const SlotIndex LowerIndex = - Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous); - const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next); - if (!LowerIndex.isValid() || !UpperIndex.isValid()) { - return makeUnexpected(ErrorCode::InvalidArgument, - "adjacent instructions are missing SlotIndexes"); - } - const std::uint64_t Lower = LowerIndex.baseIndex().value(); - const std::uint64_t Upper = UpperIndex.baseIndex().value(); - if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) { - return makeUnexpected(ErrorCode::Unsupported, - "local SlotIndex space is exhausted; renumbering is required"); - } - std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask; - if (Candidate <= Lower) - Candidate = Lower + SlotAlignmentMask + 1U; - if (Candidate >= Upper) { - return makeUnexpected(ErrorCode::Unsupported, - "local SlotIndex space is exhausted; renumbering is required"); - } - const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot(); - InstructionSlots.emplace(Instruction.stableID(), Index); - SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction); - return {}; -} - -Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) { - const auto Position = InstructionSlots.find(Instruction.stableID()); - if (Position == InstructionSlots.end()) - return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex"); - SlotToInstruction.erase(Position->second.baseIndex().value()); - InstructionSlots.erase(Position); - return {}; -} - -Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { - Result NewResult; - std::uint64_t Position = SlotSpacing; - auto Advance = [&Position]() -> Expected<void> { - if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) { - return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted"); - } - Position += SlotSpacing; - return {}; - }; - - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block); - NewResult.BlockStarts.emplace(Block, Start); - NewResult.BlocksByStart.push_back(Block); - auto Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - - for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot(); - if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second || - !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) { - return makeUnexpected(ErrorCode::VerificationError, - "duplicate instruction identity during SlotIndex construction"); - } - Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - } - NewResult.BlockEnds.emplace(Block, - SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block)); - Advanced = Advance(); - if (!Advanced) - return std::unexpected(Advanced.error()); - } - *this = std::move(NewResult); - return {}; -} - -bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept { - return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>()); -} - -Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function, - const TargetDescription &, - MachineAnalysisManager &) { - Result ResultValue; - auto Numbered = ResultValue.renumber(Function); - if (!Numbered) - return std::unexpected(Numbered.error()); - return ResultValue; -} - LaneMask RegisterLaneSet::lanes(Register Reg) const noexcept { return lanesFor(Values, Reg); } @@ -1392,36 +845,6 @@ void RegisterLaneSet::unite(const RegisterLaneSet &Other) { void RegisterLaneSet::subtract(const RegisterLaneSet &Other) { subtractLaneSets(Values, Other.Values); } - -LaneMask RegisterUnitLaneSet::lanes(RegisterUnitID Unit) const noexcept { - return lanesFor(Values, Unit); -} - -bool RegisterUnitLaneSet::contains(RegisterUnitID Unit, LaneMask Lanes) const noexcept { - return containsLanes(Values, Unit, Lanes); -} - -bool RegisterUnitLaneSet::intersects(RegisterUnitID Unit, LaneMask Lanes) const noexcept { - return intersectsLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::add(RegisterUnitID Unit, LaneMask Lanes) { - if (Unit.value() != 0 && !Lanes.empty()) - addLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::remove(RegisterUnitID Unit, LaneMask Lanes) { - removeLanes(Values, Unit, Lanes); -} - -void RegisterUnitLaneSet::unite(const RegisterUnitLaneSet &Other) { - uniteLanes(Values, Other.Values); -} - -void RegisterUnitLaneSet::subtract(const RegisterUnitLaneSet &Other) { - subtractLaneSets(Values, Other.Values); -} - const MachineBlockLiveness * LiveVariablesAnalysis::Result::block(const MachineBasicBlock &Block) const noexcept { const auto Position = Blocks.find(&Block); @@ -1469,340 +892,6 @@ Expected<LiveVariablesAnalysis::Result> LiveVariablesAnalysis::run(MachineFuncti MachineAnalysisManager &) { return computeLiveVariables(Function, Target); } - -const LiveSegment *LiveRange::segmentAt(SlotIndex Position) const noexcept { - const auto Candidate = std::ranges::upper_bound( - Segments, Position, {}, [](const LiveSegment &Segment) { return Segment.Start; }); - if (Candidate == Segments.begin()) - return nullptr; - const LiveSegment &Previous = *std::prev(Candidate); - return Previous.contains(Position) ? &Previous : nullptr; -} - -const LiveValueNumber *LiveRange::value(LiveValueNumberID ID) const noexcept { - if (!ID.isValid() || ID.value() > Values.size()) - return nullptr; - const LiveValueNumber &Result = Values[ID.value() - 1U]; - return Result.ID == ID ? &Result : nullptr; -} - -const LiveValueNumber *LiveRange::valueAt(SlotIndex Position) const noexcept { - const LiveSegment *Segment = segmentAt(Position); - return Segment == nullptr ? nullptr : value(Segment->Value); -} - -bool LiveRange::liveAt(SlotIndex Position) const noexcept { - return segmentAt(Position) != nullptr; -} - -bool LiveRange::overlaps(const LiveRange &Other) const noexcept { - std::size_t Left = 0; - std::size_t Right = 0; - while (Left < Segments.size() && Right < Other.Segments.size()) { - if (Segments[Left].overlaps(Other.Segments[Right])) - return true; - if (Segments[Left].End <= Other.Segments[Right].Start) - ++Left; - else - ++Right; - } - return false; -} - -Expected<LiveValueNumberID> LiveRange::createValue(SlotIndex Definition, LiveValueState State, - std::optional<MachineInstrStableID> Origin) { - if (!Definition.isValid()) - return makeUnexpected(ErrorCode::InvalidArgument, "live value requires a valid definition"); - if (Values.size() >= std::numeric_limits<std::uint32_t>::max()) - return makeUnexpected(ErrorCode::Unsupported, "live value-number space is exhausted"); - const LiveValueNumberID ID = - LiveValueNumberID::fromValue(static_cast<std::uint32_t>(Values.size() + 1U)); - Values.push_back({ID, Definition, State, Origin}); - return ID; -} - -Expected<void> LiveRange::addSegment(LiveSegment Segment) { - if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || - value(Segment.Value) == nullptr) { - return makeUnexpected(ErrorCode::InvalidArgument, - "live segment requires ordered indexes and a known value number"); - } - std::vector<LiveSegment> Candidate = Segments; - Candidate.push_back(Segment); - std::ranges::sort(Candidate, [](const LiveSegment &Left, const LiveSegment &Right) { - if (Left.Start != Right.Start) - return Left.Start < Right.Start; - return Left.End < Right.End; - }); - for (std::size_t Index = 1; Index < Candidate.size(); ++Index) { - if (Candidate[Index].Start < Candidate[Index - 1U].End && - Candidate[Index].Value != Candidate[Index - 1U].Value) { - return makeUnexpected(ErrorCode::VerificationError, - "live segments with different values overlap"); - } - } - Segments = std::move(Candidate); - mergeAdjacent(); - return {}; -} - -Expected<void> LiveRange::extend(LiveValueNumberID Value, SlotIndex Start, SlotIndex End) { - return addSegment({Start, End, Value}); -} - -Expected<void> LiveRange::remove(SlotIndex Start, SlotIndex End) { - if (!Start.isValid() || !End.isValid() || !(Start < End)) { - return makeUnexpected(ErrorCode::InvalidArgument, "removed live range must be nonempty"); - } - std::vector<LiveSegment> Result; - for (const LiveSegment &Segment : Segments) { - if (!(Segment.Start < End && Start < Segment.End)) { - Result.push_back(Segment); - continue; - } - if (Segment.Start < Start) - Result.push_back({Segment.Start, Start, Segment.Value}); - if (End < Segment.End) - Result.push_back({End, Segment.End, Segment.Value}); - } - Segments = std::move(Result); - mergeAdjacent(); - return {}; -} - -Expected<void> LiveRange::shrinkToUses(std::span<const SlotIndex> Uses) { - std::vector<LiveSegment> Result; - for (const LiveSegment &Segment : Segments) { - const LiveValueNumber *Value = value(Segment.Value); - if (Value == nullptr) - return makeUnexpected(ErrorCode::VerificationError, - "live segment references an unknown value number"); - std::optional<SlotIndex> LastUse; - for (const SlotIndex Use : Uses) { - if (Segment.contains(Use) && (!LastUse || *LastUse < Use)) - LastUse = Use; - } - if (!LastUse) { - if (Value->State == LiveValueState::Unused) - Result.push_back(Segment); - continue; - } - SlotIndex NewEnd = LastUse->deadSlot(); - if (Segment.End < NewEnd) - NewEnd = Segment.End; - if (Segment.Start < NewEnd) - Result.push_back({Segment.Start, NewEnd, Segment.Value}); - } - Segments = std::move(Result); - mergeAdjacent(); - return verify(); -} - -Expected<void> LiveRange::verify() const { - std::unordered_set<LiveValueNumberID> IDs; - for (std::size_t Index = 0; Index < Values.size(); ++Index) { - const LiveValueNumber &Value = Values[Index]; - if (!Value.ID.isValid() || Value.ID.value() != Index + 1U || !IDs.insert(Value.ID).second || - !Value.Definition.isValid()) { - return makeUnexpected(ErrorCode::VerificationError, - "live range contains an invalid value number"); - } - } - for (std::size_t Index = 0; Index < Segments.size(); ++Index) { - const LiveSegment &Segment = Segments[Index]; - if (!Segment.Start.isValid() || !Segment.End.isValid() || Segment.empty() || - value(Segment.Value) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, "live range contains an invalid segment"); - } - if (Index != 0 && Segments[Index - 1U].End > Segment.Start) { - return makeUnexpected(ErrorCode::VerificationError, - "live range segments are not ordered and disjoint"); - } - } - return {}; -} - -void LiveRange::mergeAdjacent() { - if (Segments.empty()) - return; - std::vector<LiveSegment> Result; - Result.reserve(Segments.size()); - Result.push_back(Segments.front()); - for (std::size_t Index = 1; Index < Segments.size(); ++Index) { - LiveSegment &Previous = Result.back(); - const LiveSegment &Current = Segments[Index]; - if (Current.Value == Previous.Value && Current.Start <= Previous.End) { - if (Previous.End < Current.End) - Previous.End = Current.End; - continue; - } - Result.push_back(Current); - } - Segments = std::move(Result); -} - -const LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) const noexcept { - const auto Position = Intervals.find(Reg); - return Position == Intervals.end() ? nullptr : &Position->second; -} - -LiveInterval *LiveIntervalsAnalysis::Result::interval(Register Reg) noexcept { - const auto Position = Intervals.find(Reg); - return Position == Intervals.end() ? nullptr : &Position->second; -} - -const LiveRange *LiveIntervalsAnalysis::Result::regUnitRange(RegisterUnitID Unit) const noexcept { - const auto Position = RegisterUnitRanges.find(Unit); - return Position == RegisterUnitRanges.end() ? nullptr : &Position->second; -} - -bool LiveIntervalsAnalysis::Result::interferes(Register Left, Register Right) const noexcept { - const LiveInterval *LeftInterval = interval(Left); - const LiveInterval *RightInterval = interval(Right); - return LeftInterval != nullptr && RightInterval != nullptr && - LeftInterval->overlaps(*RightInterval); -} - -bool LiveIntervalsAnalysis::Result::regMaskClobbers(const LiveInterval &Interval, - PhysicalRegister Candidate) const noexcept { - for (const RegMaskPosition &Position : RegMasks) { - if (Position.Mask && Position.Mask->clobbers(Candidate) && - Interval.MainRange.liveAt(Position.Position)) { - return true; - } - } - return false; -} - -Expected<void> LiveIntervalsAnalysis::Result::shrinkToUses(Register Reg, - std::span<const SlotIndex> Uses) { - LiveInterval *Value = interval(Reg); - if (Value == nullptr) - return makeUnexpected(ErrorCode::InvalidArgument, "virtual register has no live interval"); - auto Main = Value->MainRange.shrinkToUses(Uses); - if (!Main) - return std::unexpected(Main.error()); - for (LiveSubRange &SubRange : Value->SubRanges) { - auto Shrunk = SubRange.Range.shrinkToUses(Uses); - if (!Shrunk) - return std::unexpected(Shrunk.error()); - } - return {}; -} - -bool LiveIntervalsAnalysis::Result::invalidate(const MachineFunction &, - const PreservedAnalyses &Preserved) const noexcept { - return !Preserved.preserves(MachineAnalysisManager::id<LiveIntervalsAnalysis>()); -} - -Expected<LiveIntervalsAnalysis::Result> -LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &Target, - MachineAnalysisManager &Analyses) { - auto Indexes = Analyses.getResult<SlotIndexesAnalysis>(Function, Target); - if (!Indexes) - return std::unexpected(Indexes.error()); - auto Variables = Analyses.getResult<LiveVariablesAnalysis>(Function, Target); - if (!Variables) - return std::unexpected(Variables.error()); - - Result ResultValue; - ResultValue.Indexes = **Indexes; - for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { - auto RegValue = Register::makeVirtual(Index); - if (!RegValue || !Function.registerInfo().isKnownVirtualRegister(*RegValue)) - continue; - const Register Reg = *RegValue; - auto MainRange = buildLiveRange( - Function, ResultValue.Indexes, - [&Function, &Target, Reg](const MachineInstr &Instruction) { - return virtualRangeEvent(Instruction, Reg, std::nullopt, Function, Target); - }, - [&Variables, Reg](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->VirtualLiveOut.intersects(Reg); - }); - if (!MainRange) - return std::unexpected(MainRange.error()); - if (MainRange->empty()) - continue; - - LiveInterval Interval; - Interval.Reg = Reg; - Interval.MainRange = std::move(*MainRange); - auto Info = Function.registerInfo().virtualRegisterInfo(Reg); - if (!Info) - return std::unexpected(Info.error()); - // Preserve the target-provided hint order. MachineRegisterInfo already de-duplicates - // hints, and their order is the deterministic preference order consumed by allocators. - Interval.AllocationHints = Info->get().AllocationHints; - - std::uint64_t Weight = 1; - for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) { - if (Operand.parent() == nullptr || Operand.registerFlags().has(RegisterOperandFlag::Undef)) { - continue; - } - Weight = Weight > std::numeric_limits<std::uint64_t>::max() - 10U - ? std::numeric_limits<std::uint64_t>::max() - : Weight + 10U; - } - Interval.SpillWeight = Weight; - - auto LaneGroups = partitionVirtualRegisterLanes(Reg, Function, Target); - if (!LaneGroups) - return std::unexpected(LaneGroups.error()); - for (const LaneMask Lanes : *LaneGroups) { - auto SubRange = buildLiveRange( - Function, ResultValue.Indexes, - [&Function, &Target, Reg, Lanes](const MachineInstr &Instruction) { - return virtualRangeEvent(Instruction, Reg, Lanes, Function, Target); - }, - [&Variables, Reg, Lanes](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->VirtualLiveOut.intersects(Reg, Lanes); - }); - if (!SubRange) - return std::unexpected(SubRange.error()); - if (!SubRange->empty()) - Interval.SubRanges.push_back({Lanes, std::move(*SubRange)}); - } - ResultValue.Intervals.emplace(Reg, std::move(Interval)); - } - - for (const RegisterUnitDesc &Unit : Target.registers().registerUnits()) { - auto Range = buildLiveRange( - Function, ResultValue.Indexes, - [&Target, Unit](const MachineInstr &Instruction) { - return unitRangeEvent(Instruction, Unit.ID, std::nullopt, Target); - }, - [&Variables, Unit](const MachineBasicBlock &Block) { - const MachineBlockLiveness *Value = (*Variables)->block(Block); - return Value != nullptr && Value->PhysicalLiveOut.intersects(Unit.ID); - }); - if (!Range) - return std::unexpected(Range.error()); - if (!Range->empty()) - ResultValue.RegisterUnitRanges.emplace(Unit.ID, std::move(*Range)); - } - - for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { - for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; - Instruction = Instruction->next()) { - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *MaskOperand = Operand.getIf<RegisterMaskOperand>(); - if (MaskOperand == nullptr) - continue; - if (!MaskOperand->Mask) - return makeUnexpected(ErrorCode::VerificationError, - "live intervals encountered a null register mask"); - ResultValue.RegMasks.push_back( - {ResultValue.Indexes.instructionIndex(*Instruction).earlyClobberSlot(), - Instruction->stableID(), MaskOperand->Mask}); - } - } - } - return ResultValue; -} - const MachinePassContract &RebuildMachineLivenessPass::contract() const noexcept { static const MachinePassContract Contract = [] { MachinePassContract Value{ diff --git a/backend/lib/CodeGen/MachineBranchOptimization.cpp b/backend/lib/CodeGen/MachineBranchOptimization.cpp index df25a4a..5880dbc 100644 --- a/backend/lib/CodeGen/MachineBranchOptimization.cpp +++ b/backend/lib/CodeGen/MachineBranchOptimization.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineBranchOptimization.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -11,7 +12,6 @@ #include "rcc/CodeGen/MachineFunctionRecords.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineBranchRelaxation.cpp b/backend/lib/CodeGen/MachineBranchRelaxation.cpp index 9ffb821..78640f1 100644 --- a/backend/lib/CodeGen/MachineBranchRelaxation.cpp +++ b/backend/lib/CodeGen/MachineBranchRelaxation.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/MachineBranchRelaxation.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineCSE.cpp b/backend/lib/CodeGen/MachineCSE.cpp index 47bba04..9d80b4e 100644 --- a/backend/lib/CodeGen/MachineCSE.cpp +++ b/backend/lib/CodeGen/MachineCSE.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineCSE.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" diff --git a/backend/lib/CodeGen/MachineCombiner.cpp b/backend/lib/CodeGen/MachineCombiner.cpp index 9a87b6f..df9c002 100644 --- a/backend/lib/CodeGen/MachineCombiner.cpp +++ b/backend/lib/CodeGen/MachineCombiner.cpp @@ -3,11 +3,11 @@ #include "rcc/CodeGen/MachineCombiner.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineCopyPropagation.cpp b/backend/lib/CodeGen/MachineCopyPropagation.cpp index 60992a5..581cb4f 100644 --- a/backend/lib/CodeGen/MachineCopyPropagation.cpp +++ b/backend/lib/CodeGen/MachineCopyPropagation.cpp @@ -4,11 +4,11 @@ #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineDCE.cpp b/backend/lib/CodeGen/MachineDCE.cpp index 9ba9a1b..4dd0e59 100644 --- a/backend/lib/CodeGen/MachineDCE.cpp +++ b/backend/lib/CodeGen/MachineDCE.cpp @@ -3,11 +3,11 @@ #include "rcc/CodeGen/MachineDCE.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineFallthrough.cpp b/backend/lib/CodeGen/MachineFallthrough.cpp index e912f0b..5c58e67 100644 --- a/backend/lib/CodeGen/MachineFallthrough.cpp +++ b/backend/lib/CodeGen/MachineFallthrough.cpp @@ -2,11 +2,11 @@ #include "rcc/CodeGen/MachineFallthrough.h" +#include "rcc/CodeGen/LivePhysRegs.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" -#include "rcc/CodeGen/MachineLiveness.h" -#include "rcc/CodeGen/MachineLivenessRepair.h" #include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetInstrInfo.h" diff --git a/backend/lib/CodeGen/MachineLICM.cpp b/backend/lib/CodeGen/MachineLICM.cpp index 52fffe7..758e13c 100644 --- a/backend/lib/CodeGen/MachineLICM.cpp +++ b/backend/lib/CodeGen/MachineLICM.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineLICM.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp index 6d24034..4f116f0 100644 --- a/backend/lib/CodeGen/MachineOptimizationPipeline.cpp +++ b/backend/lib/CodeGen/MachineOptimizationPipeline.cpp @@ -2,6 +2,7 @@ #include "rcc/CodeGen/MachineOptimizationPipeline.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBlockPlacement.h" #include "rcc/CodeGen/MachineBranchOptimization.h" @@ -13,7 +14,6 @@ #include "rcc/CodeGen/MachineFallthrough.h" #include "rcc/CodeGen/MachineFinalization.h" #include "rcc/CodeGen/MachineLICM.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemoryFolding.h" #include "rcc/CodeGen/MachinePseudoExpansion.h" #include "rcc/CodeGen/MachineScheduler.h" diff --git a/backend/lib/CodeGen/MachinePseudoExpansion.cpp b/backend/lib/CodeGen/MachinePseudoExpansion.cpp index b97d926..b5afe8e 100644 --- a/backend/lib/CodeGen/MachinePseudoExpansion.cpp +++ b/backend/lib/CodeGen/MachinePseudoExpansion.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachinePseudoExpansion.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineScheduler.cpp b/backend/lib/CodeGen/MachineScheduler.cpp index c85489b..e589675 100644 --- a/backend/lib/CodeGen/MachineScheduler.cpp +++ b/backend/lib/CodeGen/MachineScheduler.cpp @@ -4,11 +4,11 @@ #include "MachineSchedulerInternal.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/RegisterPressure.h" #include "rcc/CodeGen/ScheduleDAG.h" #include "rcc/CodeGen/ScheduleHazardRecognizer.h" diff --git a/backend/lib/CodeGen/MachineSchedulerInternal.h b/backend/lib/CodeGen/MachineSchedulerInternal.h index 92f8eea..1815eaa 100644 --- a/backend/lib/CodeGen/MachineSchedulerInternal.h +++ b/backend/lib/CodeGen/MachineSchedulerInternal.h @@ -5,8 +5,8 @@ #ifndef RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H #define RCC_LIB_CODEGEN_MACHINESCHEDULERINTERNAL_H +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineScheduler.h" #include "rcc/CodeGen/ScheduleDAG.h" #include "rcc/Support/Error.h" diff --git a/backend/lib/CodeGen/MachineSink.cpp b/backend/lib/CodeGen/MachineSink.cpp index 873de67..21b17f8 100644 --- a/backend/lib/CodeGen/MachineSink.cpp +++ b/backend/lib/CodeGen/MachineSink.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineSink.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineAnalyses.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineTailDuplication.cpp b/backend/lib/CodeGen/MachineTailDuplication.cpp index 80c58c9..5abd473 100644 --- a/backend/lib/CodeGen/MachineTailDuplication.cpp +++ b/backend/lib/CodeGen/MachineTailDuplication.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineTailDuplication.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -10,7 +11,6 @@ #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/MachineTailMerge.cpp b/backend/lib/CodeGen/MachineTailMerge.cpp index 07608cc..c4d6de9 100644 --- a/backend/lib/CodeGen/MachineTailMerge.cpp +++ b/backend/lib/CodeGen/MachineTailMerge.cpp @@ -3,6 +3,7 @@ #include "rcc/CodeGen/MachineTailMerge.h" #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineBasicBlockAttributes.h" #include "rcc/CodeGen/MachineCFGUpdater.h" @@ -10,7 +11,6 @@ #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" #include "rcc/CodeGen/MachineJumpTableInfo.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index 00be72f..8f1ebf4 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/MachineVerifier.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFrameInfo.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionProperties.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineMetadata.h" #include "rcc/CodeGen/MachineOperand.h" diff --git a/backend/lib/CodeGen/PHIElimination.cpp b/backend/lib/CodeGen/PHIElimination.cpp index 5539708..75472f2 100644 --- a/backend/lib/CodeGen/PHIElimination.cpp +++ b/backend/lib/CodeGen/PHIElimination.cpp @@ -3,13 +3,13 @@ #include "rcc/CodeGen/PHIElimination.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineCFGUpdater.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/PostRAScheduler.cpp b/backend/lib/CodeGen/PostRAScheduler.cpp index 38fd582..f7d6181 100644 --- a/backend/lib/CodeGen/PostRAScheduler.cpp +++ b/backend/lib/CodeGen/PostRAScheduler.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/PostRAScheduler.h" #include "MachineSchedulerInternal.h" +#include "rcc/CodeGen/LivePhysRegs.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" -#include "rcc/CodeGen/MachineLivenessRepair.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/RegisterMask.h" #include "rcc/CodeGen/TargetDescription.h" @@ -53,222 +53,8 @@ namespace { return Error(Failure.code(), std::move(Prefix)); } -struct PhysicalUnitAccess final { - RegisterUnitID Unit; - LaneMask Lanes; -}; - -struct OperandFlagUpdate final { - MachineOperand *Operand = nullptr; - RegisterOperandFlags Flags; -}; - -[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes) noexcept { - std::uint64_t View = UnitViewLanes.rawValue(); - std::uint64_t Normalized = 0; - std::uint32_t UnitLane = 0; - while (View != 0) { - Normalized |= std::uint64_t{1} << UnitLane; - View &= View - 1U; - ++UnitLane; - } - return LaneMask::fromRaw(Normalized); -} - -[[nodiscard]] Expected<std::vector<PhysicalUnitAccess>> -physicalOperandUnits(const MachineOperand &Operand, const TargetDescription &Target) { - const Register *Reg = Operand.getIf<Register>(); - std::optional<PhysicalRegister> Physical = - Reg == nullptr ? std::nullopt : Reg->physicalRegister(); - if (!Physical) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a virtual register"); - } - if (Operand.subReg().value() != 0) { - Physical = Target.registers().subRegister(*Physical, Operand.subReg()); - if (!Physical) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered an invalid subregister"); - } - } - const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(*Physical); - if (Description == nullptr || Description->Units.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a unitless register"); - } - std::vector<PhysicalUnitAccess> Result; - Result.reserve(Description->Units.size()); - for (const RegisterUnitLane &Unit : Description->Units) { - if (Unit.Lanes.empty()) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered empty register-unit lanes"); - } - Result.push_back({Unit.Unit, normalizeUnitLanes(Unit.Lanes)}); - } - return Result; -} - -void addPhysicalRegister(RegisterUnitLaneSet &Live, const PhysicalRegisterDesc &Register) { - for (const RegisterUnitLane &Unit : Register.Units) - Live.add(Unit.Unit, normalizeUnitLanes(Unit.Lanes)); -} - -[[nodiscard]] bool intersects(const RegisterUnitLaneSet &Live, - const std::vector<PhysicalUnitAccess> &Units) noexcept { - return std::ranges::any_of(Units, [&Live](const PhysicalUnitAccess &Unit) { - return Live.intersects(Unit.Unit, Unit.Lanes); - }); -} - -void addUnits(RegisterUnitLaneSet &Live, const std::vector<PhysicalUnitAccess> &Units) { - for (const PhysicalUnitAccess &Unit : Units) - Live.add(Unit.Unit, Unit.Lanes); -} - -void removeUnits(RegisterUnitLaneSet &Live, const std::vector<PhysicalUnitAccess> &Units) { - for (const PhysicalUnitAccess &Unit : Units) - Live.remove(Unit.Unit, Unit.Lanes); -} - -[[nodiscard]] bool isReservedPhysicalRegister(Register Reg, const MachineFunction &Function, - const TargetDescription &Target) noexcept { - const std::optional<PhysicalRegister> Physical = Reg.physicalRegister(); - return Physical && (Function.registerInfo().isReserved(*Physical) || - Target.registers().isReservedRegister(*Physical)); -} - -[[nodiscard]] OperandFlagUpdate &getFlagUpdate(std::vector<OperandFlagUpdate> &Updates, - MachineOperand &Operand) { - const auto Position = std::ranges::find_if( - Updates, [&Operand](const OperandFlagUpdate &Update) { return Update.Operand == &Operand; }); - if (Position != Updates.end()) - return *Position; - Updates.push_back({&Operand, Operand.registerFlags()}); - return Updates.back(); -} - -[[nodiscard]] Expected<std::vector<OperandFlagUpdate>> -buildBlockLivenessRepairPlan(MachineBasicBlock &Block, const TargetDescription &Target, - const MachineBlockLiveness &Boundary) { - RegisterUnitLaneSet Live = Boundary.PhysicalLiveOut; - std::vector<OperandFlagUpdate> Updates; - for (MachineInstr *Instruction = Block.lastInstruction(); Instruction != nullptr; - Instruction = Instruction->previous()) { - for (const MachineOperand &Operand : Instruction->operands()) { - const auto *Mask = Operand.getIf<LiveOutRegisterMaskOperand>(); - if (Mask == nullptr) - continue; - if (!Mask->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a null live-out mask"); - } - for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { - if (Mask->Mask->preserves(Register.Reg)) - addPhysicalRegister(Live, Register); - } - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister()) - continue; - OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); - Update.Flags.clear(RegisterOperandFlag::Dead); - if (!Operand->isDef()) - continue; - const Register *Reg = Operand->getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - auto Units = physicalOperandUnits(*Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - if (!intersects(Live, *Units)) - Update.Flags.set(RegisterOperandFlag::Dead); - } - - for (const MachineOperand &Operand : Instruction->operands()) { - if (Operand.isRegister() && Operand.isDef()) { - const Register *Reg = Operand.getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - auto Units = physicalOperandUnits(Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - removeUnits(Live, *Units); - continue; - } - const auto *Mask = Operand.getIf<RegisterMaskOperand>(); - if (Mask == nullptr) - continue; - if (!Mask->Mask) { - return makeUnexpected(ErrorCode::VerificationError, - "post-RA liveness repair encountered a null register mask"); - } - RegisterUnitLaneSet Clobbers; - for (const PhysicalRegisterDesc &Register : Target.registers().physicalRegisters()) { - if (Mask->Mask->clobbers(Register.Reg)) - addPhysicalRegister(Clobbers, Register); - } - Live.subtract(Clobbers); - } - - for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { - MachineOperand *Operand = Instruction->operandAt(Index); - if (Operand == nullptr || !Operand->isRegister()) - continue; - OperandFlagUpdate &Update = getFlagUpdate(Updates, *Operand); - Update.Flags.clear(RegisterOperandFlag::Kill); - if (!Operand->isUse() || Operand->isDebugUse() || - Operand->registerFlags().has(RegisterOperandFlag::Undef)) { - continue; - } - const Register *Reg = Operand->getIf<Register>(); - if (Reg == nullptr || Reg->isNoRegister()) - continue; - if (isReservedPhysicalRegister(*Reg, Block.function(), Target)) - continue; - auto Units = physicalOperandUnits(*Operand, Target); - if (!Units) - return std::unexpected(Units.error()); - if (!intersects(Live, *Units)) - Update.Flags.set(RegisterOperandFlag::Kill); - addUnits(Live, *Units); - } - } - if (Live != Boundary.PhysicalLiveIn) { - return makeUnexpected(ErrorCode::InternalError, - "post-RA local liveness repair changed the block boundary"); - } - return Updates; -} - } // namespace -Expected<bool> repairPostRAMachineBlockLiveness(std::span<MachineBasicBlock *const> Blocks, - const TargetDescription &Target, - const LiveVariablesAnalysis::Result &Liveness) { - std::vector<OperandFlagUpdate> Updates; - for (MachineBasicBlock *Block : Blocks) { - const MachineBlockLiveness *Boundary = Liveness.block(*Block); - if (Boundary == nullptr) { - return makeUnexpected(ErrorCode::InternalError, - "post-RA scheduler lost a block liveness boundary"); - } - auto BlockUpdates = buildBlockLivenessRepairPlan(*Block, Target, *Boundary); - if (!BlockUpdates) - return std::unexpected(BlockUpdates.error()); - Updates.insert(Updates.end(), BlockUpdates->begin(), BlockUpdates->end()); - } - bool Changed = false; - for (const OperandFlagUpdate &Update : Updates) { - Changed |= Update.Operand->registerFlags() != Update.Flags; - auto Applied = Update.Operand->setRegisterFlags(Update.Flags); - if (!Applied) - return std::unexpected(Applied.error()); - } - return Changed; -} - const MachinePassContract &PostRASchedulerPass::contract() const noexcept { return postRASchedulerContract(); } diff --git a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp index 36315f7..47b74f6 100644 --- a/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp +++ b/backend/lib/CodeGen/PrologueEpilogueInsertion.cpp @@ -7,7 +7,7 @@ #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineMemOperand.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineVerifier.h" diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp index 5d065dd..0fac6aa 100644 --- a/backend/lib/CodeGen/RegAllocBase.cpp +++ b/backend/lib/CodeGen/RegAllocBase.cpp @@ -2,7 +2,7 @@ #include "RegAllocBase.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/Spiller.h" #include <algorithm> diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h index a1682b2..318a82d 100644 --- a/backend/lib/CodeGen/RegAllocBase.h +++ b/backend/lib/CodeGen/RegAllocBase.h @@ -6,7 +6,7 @@ #define RCC_LIB_CODEGEN_REGALLOCBASE_H #include "RegAllocInternal.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/RegAllocCommon.h" #include "rcc/CodeGen/TargetRegisterAllocationInfo.h" #include "rcc/CodeGen/VirtRegMap.h" diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp index 7f88f25..9d14d15 100644 --- a/backend/lib/CodeGen/RegAllocBasic.cpp +++ b/backend/lib/CodeGen/RegAllocBasic.cpp @@ -3,8 +3,9 @@ #include "RegAllocBasic.h" #include "RegAllocBase.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" -#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/LiveVariables.h" #include <algorithm> #include <memory> diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp index 897f217..1399f10 100644 --- a/backend/lib/CodeGen/RegAllocFast.cpp +++ b/backend/lib/CodeGen/RegAllocFast.cpp @@ -4,11 +4,11 @@ #include "RegAllocInternal.h" #include "rcc/CodeGen/LiveRangeEdit.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/Spiller.h" diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h index 5cd98e8..0becb92 100644 --- a/backend/lib/CodeGen/RegAllocInternal.h +++ b/backend/lib/CodeGen/RegAllocInternal.h @@ -6,11 +6,11 @@ #define RCC_LIB_CODEGEN_REGALLOCINTERNAL_H #include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/MachineVerifier.h" diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp index f1da2c1..3b0e684 100644 --- a/backend/lib/CodeGen/RegAllocPBQP.cpp +++ b/backend/lib/CodeGen/RegAllocPBQP.cpp @@ -4,11 +4,12 @@ #include "RegAllocBase.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/PBQP/Solver.h" diff --git a/backend/lib/CodeGen/RegisterPressure.cpp b/backend/lib/CodeGen/RegisterPressure.cpp index cbd8d8e..201e85b 100644 --- a/backend/lib/CodeGen/RegisterPressure.cpp +++ b/backend/lib/CodeGen/RegisterPressure.cpp @@ -2,10 +2,10 @@ #include "rcc/CodeGen/RegisterPressure.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/RegisterMask.h" diff --git a/backend/lib/CodeGen/SlotIndexes.cpp b/backend/lib/CodeGen/SlotIndexes.cpp new file mode 100644 index 0000000..57e35b5 --- /dev/null +++ b/backend/lib/CodeGen/SlotIndexes.cpp @@ -0,0 +1,159 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/SlotIndexes.h" + +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" + +#include <cstdint> +#include <limits> + +namespace rcc { + +namespace { +constexpr std::uint64_t SlotSpacing = 16; +constexpr std::uint64_t SlotAlignmentMask = 3; +} // namespace + +SlotIndex +SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept { + const auto Position = InstructionSlots.find(Instruction.stableID()); + return Position == InstructionSlots.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockStarts.find(&Block); + return Position == BlockStarts.end() ? SlotIndex{} : Position->second; +} + +SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept { + const auto Position = BlockEnds.find(&Block); + return Position == BlockEnds.end() ? SlotIndex{} : Position->second; +} + +const MachineInstr * +SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + const auto Position = SlotToInstruction.find(Index.baseIndex().value()); + return Position == SlotToInstruction.end() ? nullptr : Position->second; +} + +const MachineBasicBlock * +SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept { + if (!Index.isValid()) + return nullptr; + for (const MachineBasicBlock *Block : BlocksByStart) { + const SlotIndex Start = blockStart(*Block); + const SlotIndex End = blockEnd(*Block); + if (!(Index < Start) && Index < End) + return Block; + } + return nullptr; +} + +Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) { + const MachineBasicBlock *Block = Instruction.parent(); + if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "SlotIndex insertion requires a linked indexed instruction"); + } + if (InstructionSlots.contains(Instruction.stableID())) { + return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex"); + } + + const MachineInstr *Previous = Instruction.previous(); + const MachineInstr *Next = Instruction.next(); + const SlotIndex LowerIndex = + Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous); + const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next); + if (!LowerIndex.isValid() || !UpperIndex.isValid()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "adjacent instructions are missing SlotIndexes"); + } + const std::uint64_t Lower = LowerIndex.baseIndex().value(); + const std::uint64_t Upper = UpperIndex.baseIndex().value(); + if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask; + if (Candidate <= Lower) + Candidate = Lower + SlotAlignmentMask + 1U; + if (Candidate >= Upper) { + return makeUnexpected(ErrorCode::Unsupported, + "local SlotIndex space is exhausted; renumbering is required"); + } + const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot(); + InstructionSlots.emplace(Instruction.stableID(), Index); + SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction); + return {}; +} + +Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) { + const auto Position = InstructionSlots.find(Instruction.stableID()); + if (Position == InstructionSlots.end()) + return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex"); + SlotToInstruction.erase(Position->second.baseIndex().value()); + InstructionSlots.erase(Position); + return {}; +} + +Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) { + Result NewResult; + std::uint64_t Position = SlotSpacing; + auto Advance = [&Position]() -> Expected<void> { + if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) { + return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted"); + } + Position += SlotSpacing; + return {}; + }; + + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block); + NewResult.BlockStarts.emplace(Block, Start); + NewResult.BlocksByStart.push_back(Block); + auto Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot(); + if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second || + !NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) { + return makeUnexpected(ErrorCode::VerificationError, + "duplicate instruction identity during SlotIndex construction"); + } + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + NewResult.BlockEnds.emplace(Block, + SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block)); + Advanced = Advance(); + if (!Advanced) + return std::unexpected(Advanced.error()); + } + *this = std::move(NewResult); + return {}; +} + +bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &, + const PreservedAnalyses &Preserved) const noexcept { + return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>()); +} + +Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function, + const TargetDescription &, + MachineAnalysisManager &) { + Result ResultValue; + auto Numbered = ResultValue.renumber(Function); + if (!Numbered) + return std::unexpected(Numbered.error()); + return ResultValue; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp index 1959b90..be4db82 100644 --- a/backend/lib/CodeGen/TwoAddressInstructionPass.cpp +++ b/backend/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -3,12 +3,12 @@ #include "rcc/CodeGen/TwoAddressInstructionPass.h" #include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineFunctionCloner.h" #include "rcc/CodeGen/MachineIRBuilder.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" diff --git a/backend/lib/CodeGen/VirtRegMap.cpp b/backend/lib/CodeGen/VirtRegMap.cpp index 624a931..a55a486 100644 --- a/backend/lib/CodeGen/VirtRegMap.cpp +++ b/backend/lib/CodeGen/VirtRegMap.cpp @@ -3,11 +3,12 @@ #include "rcc/CodeGen/VirtRegMap.h" #include "RegAllocInternal.h" +#include "rcc/CodeGen/LiveIntervals.h" #include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/LiveVariables.h" #include "rcc/CodeGen/MachineBasicBlock.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" -#include "rcc/CodeGen/MachineLiveness.h" #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" |