From e5fdceb9b869f010a2a75638fd38aaf1867f3008 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 9 Aug 2026 04:40:17 +0800 Subject: [CodeGen] Complete register allocation infrastructure --- backend/lib/CodeGen/CMakeLists.txt | 40 ++ backend/lib/CodeGen/GenericConstant.cpp | 86 ++-- backend/lib/CodeGen/InlineSpiller.cpp | 270 ++++++++++ backend/lib/CodeGen/LiveRangeEdit.cpp | 126 +++++ backend/lib/CodeGen/LiveRegMatrix.cpp | 330 ++++++++++++ backend/lib/CodeGen/MachineAnalyses.cpp | 3 +- backend/lib/CodeGen/MachineCompilationStatus.cpp | 1 + backend/lib/CodeGen/MachineFrameInfo.cpp | 15 +- backend/lib/CodeGen/MachineFunctionCloner.cpp | 3 +- backend/lib/CodeGen/MachineJumpTableInfo.cpp | 5 +- backend/lib/CodeGen/MachineLiveness.cpp | 5 +- backend/lib/CodeGen/MachinePass.cpp | 23 +- backend/lib/CodeGen/MachineRegisterInfo.cpp | 5 + backend/lib/CodeGen/RegAllocBase.cpp | 91 ++++ backend/lib/CodeGen/RegAllocBase.h | 51 ++ backend/lib/CodeGen/RegAllocBasic.cpp | 136 +++++ backend/lib/CodeGen/RegAllocBasic.h | 31 ++ backend/lib/CodeGen/RegAllocFast.cpp | 608 +++++++++++++++++++++++ backend/lib/CodeGen/RegAllocInternal.h | 236 +++++++++ backend/lib/CodeGen/RegAllocPBQP.cpp | 281 +++++++++++ backend/lib/CodeGen/TargetMIRTextInfo.cpp | 6 +- backend/lib/CodeGen/VirtRegMap.cpp | 301 +++++++++++ 22 files changed, 2575 insertions(+), 78 deletions(-) create mode 100644 backend/lib/CodeGen/InlineSpiller.cpp create mode 100644 backend/lib/CodeGen/LiveRangeEdit.cpp create mode 100644 backend/lib/CodeGen/LiveRegMatrix.cpp create mode 100644 backend/lib/CodeGen/RegAllocBase.cpp create mode 100644 backend/lib/CodeGen/RegAllocBase.h create mode 100644 backend/lib/CodeGen/RegAllocBasic.cpp create mode 100644 backend/lib/CodeGen/RegAllocBasic.h create mode 100644 backend/lib/CodeGen/RegAllocFast.cpp create mode 100644 backend/lib/CodeGen/RegAllocInternal.h create mode 100644 backend/lib/CodeGen/RegAllocPBQP.cpp create mode 100644 backend/lib/CodeGen/VirtRegMap.cpp (limited to 'backend/lib/CodeGen') diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 4c2887c..d6233c2 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -30,6 +30,14 @@ set( MachinePass.cpp MachinePipelinePasses.cpp MachineRegisterInfo.cpp + InlineSpiller.cpp + LiveRangeEdit.cpp + LiveRegMatrix.cpp + RegAllocBase.cpp + RegAllocBasic.cpp + RegAllocFast.cpp + RegAllocPBQP.cpp + VirtRegMap.cpp MachineSSAExit.cpp MachineVerifier.cpp MachineFunctionProperties.cpp @@ -74,6 +82,19 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachinePipelinePasses.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetCodeGen.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineRegisterInfo.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Graph.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Math.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/ReductionRules.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Solution.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/PBQP/Solver.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRangeEdit.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/LiveRegMatrix.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocCommon.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocFast.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegAllocPBQP.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/Spiller.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterAllocationInfo.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/VirtRegMap.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineSSAExit.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineVerifier.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/MachineFunctionProperties.h" @@ -146,6 +167,17 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/InlineSpiller.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRangeEdit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrix.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.h" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.h" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocInternal.h" "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" @@ -189,6 +221,14 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/MachinePass.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachinePipelinePasses.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineRegisterInfo.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/InlineSpiller.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRangeEdit.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/LiveRegMatrix.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBase.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocBasic.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocFast.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RegAllocPBQP.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/VirtRegMap.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineSSAExit.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineVerifier.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/MachineFunctionProperties.cpp" diff --git a/backend/lib/CodeGen/GenericConstant.cpp b/backend/lib/CodeGen/GenericConstant.cpp index 2ef24bf..d9d9233 100644 --- a/backend/lib/CodeGen/GenericConstant.cpp +++ b/backend/lib/CodeGen/GenericConstant.cpp @@ -66,8 +66,7 @@ struct VectorShape final { friend constexpr bool operator==(VectorShape Left, VectorShape Right) noexcept = default; }; -[[nodiscard]] std::optional -vectorShape(const GenericConstantType &Type) noexcept { +[[nodiscard]] std::optional vectorShape(const GenericConstantType &Type) noexcept { const GenericConstantType &Resolved = resolvedType(Type); if (Resolved.Kind != GenericConstantTypeKind::Vector) return std::nullopt; @@ -121,8 +120,7 @@ pointerAddressSpace(const GenericConstantType &Type) noexcept { if (isIntegerScalarType(Type) || isFloatingScalarType(Type)) return true; const GenericConstantType *Element = vectorElementType(Type); - return Element != nullptr && - (isIntegerScalarType(*Element) || isFloatingScalarType(*Element)); + return Element != nullptr && (isIntegerScalarType(*Element) || isFloatingScalarType(*Element)); } [[nodiscard]] std::optional @@ -175,8 +173,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { isPointerScalarType(*PointerElement) && isIntegerScalarType(*IntegerElement); } -[[nodiscard]] bool isSizedType(const GenericConstantType &Type, - std::size_t Depth = 0) noexcept { +[[nodiscard]] bool isSizedType(const GenericConstantType &Type, std::size_t Depth = 0) noexcept { if (Depth > MaximumVerificationDepth) return false; const GenericConstantType &Resolved = resolvedType(Type); @@ -224,8 +221,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { [[nodiscard]] bool hasOnlyValuePayload(const GenericConstantData &Value) noexcept { return Value.Symbol.empty() && Value.Block.empty() && Value.ExpressionOpcode == GenericConstantExpressionOpcode::Invalid && - Value.ExpressionFlags.rawValue() == 0 && !Value.SourceElementType && - !Value.InRangeStart && !Value.InRangeEnd; + Value.ExpressionFlags.rawValue() == 0 && !Value.SourceElementType && !Value.InRangeStart && + !Value.InRangeEnd; } [[nodiscard]] Expected verifyType(const GenericConstantType &Type, std::size_t Depth, @@ -335,8 +332,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { (EffectiveType.Kind != GenericConstantTypeKind::Integer && EffectiveType.Kind != GenericConstantTypeKind::Byte) || Value.IntegerValue->bitWidth() != - (EffectiveType.Kind == GenericConstantTypeKind::Byte ? 8U - : EffectiveType.BitWidth)) { + (EffectiveType.Kind == GenericConstantTypeKind::Byte ? 8U : EffectiveType.BitWidth)) { return makeUnexpected(ErrorCode::VerificationError, "generic integer constant has an inconsistent payload"); } @@ -384,9 +380,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { } for (std::size_t Index = 0; Index < Value.Elements.size(); ++Index) { const GenericConstantType &ExpectedType = - EffectiveType.Kind == GenericConstantTypeKind::Struct - ? EffectiveType.Elements[Index] - : EffectiveType.Elements.front(); + EffectiveType.Kind == GenericConstantTypeKind::Struct ? EffectiveType.Elements[Index] + : EffectiveType.Elements.front(); if (Value.Elements[Index].Type != ExpectedType) { return makeUnexpected(ErrorCode::VerificationError, "generic aggregate element type does not match its container"); @@ -417,8 +412,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { Value.IntegerValue || Value.FloatingValue || !Value.ByteValue.empty() || !Value.Elements.empty() || !Value.Block.empty() || Value.ExpressionOpcode != GenericConstantExpressionOpcode::Invalid || - Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || - Value.InRangeStart || Value.InRangeEnd) { + Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || Value.InRangeStart || + Value.InRangeEnd) { return makeUnexpected(ErrorCode::VerificationError, "generic global-address constant has an inconsistent payload"); } @@ -428,13 +423,13 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { Value.Block.empty() || Value.IntegerValue || Value.FloatingValue || !Value.ByteValue.empty() || !Value.Elements.empty() || Value.ExpressionOpcode != GenericConstantExpressionOpcode::Invalid || - Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || - Value.InRangeStart || Value.InRangeEnd) { + Value.ExpressionFlags.rawValue() != 0 || Value.SourceElementType || Value.InRangeStart || + Value.InRangeEnd) { return makeUnexpected(ErrorCode::VerificationError, "generic block-address constant has an inconsistent payload"); } return {}; - case GenericConstantKind::PointerAuth: + case GenericConstantKind::PointerAuth: { if (EffectiveType.Kind != GenericConstantTypeKind::Pointer || Value.Elements.size() < 2 || Value.Elements.size() > 5 || Value.IntegerValue || Value.FloatingValue || !Value.ByteValue.empty() || !hasOnlyValuePayload(Value)) { @@ -446,19 +441,20 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { if (!Result) return Result; } + const auto KeyBitWidth = integerScalarBitWidth(Value.Elements[1].Type); if (!isPointerScalarType(Value.Elements[0].Type) || - !sameResolvedType(Value.Type, Value.Elements[0].Type) || - !integerScalarBitWidth(Value.Elements[1].Type) || - *integerScalarBitWidth(Value.Elements[1].Type) != 32) { + !sameResolvedType(Value.Type, Value.Elements[0].Type) || !KeyBitWidth || + KeyBitWidth.value() != 32) { return makeUnexpected(ErrorCode::VerificationError, "generic pointer-auth constant has invalid pointer or key operands"); } - if (Value.Elements.size() >= 3 && - (!integerScalarBitWidth(Value.Elements[2].Type) || - *integerScalarBitWidth(Value.Elements[2].Type) != 64)) { - return makeUnexpected( - ErrorCode::VerificationError, - "generic pointer-auth constant integer discriminator must be a scalar i64"); + if (Value.Elements.size() >= 3) { + const auto DiscriminatorBitWidth = integerScalarBitWidth(Value.Elements[2].Type); + if (!DiscriminatorBitWidth || DiscriminatorBitWidth.value() != 64) { + return makeUnexpected( + ErrorCode::VerificationError, + "generic pointer-auth constant integer discriminator must be a scalar i64"); + } } for (std::size_t Index = 3; Index < Value.Elements.size(); ++Index) { if (!isPointerScalarType(Value.Elements[Index].Type)) { @@ -468,6 +464,7 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { } } return {}; + } case GenericConstantKind::Expression: if (Value.ExpressionOpcode == GenericConstantExpressionOpcode::Invalid || Value.Elements.empty() || Value.IntegerValue || Value.FloatingValue || @@ -495,18 +492,18 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { const bool IsBinary = Value.ExpressionOpcode == GenericConstantExpressionOpcode::Add || Value.ExpressionOpcode == GenericConstantExpressionOpcode::Sub || Value.ExpressionOpcode == GenericConstantExpressionOpcode::Xor; - const bool IsGEP = Value.ExpressionOpcode == - GenericConstantExpressionOpcode::GetElementPtr; + const bool IsGEP = Value.ExpressionOpcode == GenericConstantExpressionOpcode::GetElementPtr; const std::uint8_t Flags = Value.ExpressionFlags.rawValue(); const std::uint8_t BinaryFlags = - (std::uint8_t{1} << static_cast(GenericConstantExpressionFlag::NoUnsignedWrap)) | + (std::uint8_t{1} << static_cast( + GenericConstantExpressionFlag::NoUnsignedWrap)) | (std::uint8_t{1} << static_cast(GenericConstantExpressionFlag::NoSignedWrap)); const std::uint8_t GEPFlags = (std::uint8_t{1} << static_cast(GenericConstantExpressionFlag::InBounds)) | - (std::uint8_t{1} << - static_cast(GenericConstantExpressionFlag::NoUnsignedSignedWrap)) | - (std::uint8_t{1} << - static_cast(GenericConstantExpressionFlag::GEPNoUnsignedWrap)); + (std::uint8_t{1} << static_cast( + GenericConstantExpressionFlag::NoUnsignedSignedWrap)) | + (std::uint8_t{1} << static_cast( + GenericConstantExpressionFlag::GEPNoUnsignedWrap)); if ((!IsBinary && !IsGEP && Flags != 0) || (IsBinary && (Flags & ~BinaryFlags) != 0) || (IsGEP && (Flags & ~GEPFlags) != 0)) { return makeUnexpected(ErrorCode::VerificationError, @@ -594,14 +591,14 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { if (!isIntegerOrIntegerVectorType(Value.Type) || !sameResolvedType(Value.Elements[0].Type, Value.Type) || !sameResolvedType(Value.Elements[1].Type, Value.Type)) { - return makeUnexpected(ErrorCode::VerificationError, - "generic binary constant requires equal integer operand and result types"); + return makeUnexpected( + ErrorCode::VerificationError, + "generic binary constant requires equal integer operand and result types"); } return {}; case GenericConstantExpressionOpcode::GetElementPtr: { if (!Value.SourceElementType || !isSizedType(*Value.SourceElementType) || - !isPointerOrPointerVectorType(FirstType) || - !isPointerOrPointerVectorType(Value.Type)) { + !isPointerOrPointerVectorType(FirstType) || !isPointerOrPointerVectorType(Value.Type)) { return makeUnexpected(ErrorCode::VerificationError, "generic getelementptr constant has invalid source or pointer types"); } @@ -631,9 +628,8 @@ nonPointerFixedBitWidth(const GenericConstantType &Type) noexcept { return makeUnexpected(ErrorCode::VerificationError, "generic getelementptr result has an incompatible vector shape"); } - if (Value.InRangeStart && - (Value.InRangeStart->bitWidth() != Value.InRangeEnd->bitWidth() || - !signedIntegerLess(*Value.InRangeStart, *Value.InRangeEnd))) { + if (Value.InRangeStart && (Value.InRangeStart->bitWidth() != Value.InRangeEnd->bitWidth() || + !signedIntegerLess(*Value.InRangeStart, *Value.InRangeEnd))) { return makeUnexpected(ErrorCode::VerificationError, "generic getelementptr inrange interval is invalid"); } @@ -756,9 +752,8 @@ Expected GenericConstantType::array(std::uint64_t Count, return Type; } -Expected GenericConstantType::vector(std::uint64_t Count, - GenericConstantType Element, - bool IsScalable) { +Expected +GenericConstantType::vector(std::uint64_t Count, GenericConstantType Element, bool IsScalable) { if (Count == 0) return makeUnexpected(ErrorCode::InvalidArgument, "generic vector type cannot be empty"); auto Verification = Element.verify(); @@ -800,8 +795,7 @@ GenericConstantType::function(GenericConstantType Return, return Type; } -Expected GenericConstantType::named(std::string TypeName, - bool IsNumericName) { +Expected GenericConstantType::named(std::string TypeName, bool IsNumericName) { if (TypeName.empty()) return makeUnexpected(ErrorCode::InvalidArgument, "generic named type cannot be empty"); GenericConstantType Type; diff --git a/backend/lib/CodeGen/InlineSpiller.cpp b/backend/lib/CodeGen/InlineSpiller.cpp new file mode 100644 index 0000000..589b7b8 --- /dev/null +++ b/backend/lib/CodeGen/InlineSpiller.cpp @@ -0,0 +1,270 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/Spiller.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] Expected clearDebugRegisterOperand(MachineOperand &Operand) { + RegisterOperandFlags Flags = Operand.registerFlags(); + Flags.set(RegisterOperandFlag::Undef); + auto SetReg = Operand.setRegister(Register{}); + if (!SetReg) + return std::unexpected(SetReg.error()); + auto SetSubReg = Operand.setSubReg(SubRegIndex{}); + if (!SetSubReg) + return std::unexpected(SetSubReg.error()); + return Operand.setRegisterFlags(Flags); +} + +} // namespace + +Expected>> Spiller::tryRematerialize(Register VirtualReg) { + if (!EnableRematerialization) + return std::optional>{}; + const MachineOperand *Definition = Function->registerInfo().getUniqueVRegDef(VirtualReg); + const MachineInstr *DefiningInstruction = Definition == nullptr ? nullptr : Definition->parent(); + if (DefiningInstruction == nullptr || DefiningInstruction->parent() == nullptr) + return std::optional>{}; + auto Accepted = + TargetInfo->isRematerializable(*DefiningInstruction, VirtualReg, *Function, *Target); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return std::optional>{}; + + struct UseSite final { + MachineInstr *Instruction = nullptr; + std::vector OperandIndices; + }; + std::vector Sites; + for (MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + UseSite Site{Instruction, {}}; + bool HasDefinition = false; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf(); + if (Reg == nullptr || *Reg != VirtualReg) + continue; + HasDefinition |= Operand->isDef(); + if (Operand->isUse() && !Operand->isDebugUse()) + Site.OperandIndices.push_back(Index); + } + if (HasDefinition && !Site.OperandIndices.empty()) + return std::optional>{}; + if (!Site.OperandIndices.empty()) + Sites.push_back(std::move(Site)); + } + } + if (Sites.empty()) + return std::optional>{}; + + std::vector NewRegisters; + NewRegisters.reserve(Sites.size()); + for (UseSite &Site : Sites) { + auto Child = Edit.createFrom(VirtualReg, false); + if (!Child) + return std::unexpected(Child.error()); + MachineIRBuilder Builder(*Function, *Target); + auto Positioned = Builder.setInsertPointBefore(*Site.Instruction); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Materialized = + TargetInfo->rematerialize(Builder, *DefiningInstruction, *Child, VirtualReg, *Target); + if (!Materialized) + return std::unexpected(Materialized.error()); + for (const std::size_t Index : Site.OperandIndices) { + MachineOperand *Operand = Site.Instruction->operandAt(Index); + auto Replaced = Operand->setRegister(*Child); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + VirtRegMapEntry *Entry = Mapping->entry(VirtualReg); + if (Entry != nullptr) + ++Entry->Spill.RematerializationCount; + NewRegisters.push_back(*Child); + } + + bool HasNonDebugUse = false; + for (const MachineOperand &Operand : Function->registerInfo().useOperands(VirtualReg, false)) { + if (Operand.parent() != nullptr) { + HasNonDebugUse = true; + break; + } + } + if (!HasNonDebugUse) { + MachineBasicBlock *Block = const_cast(DefiningInstruction->parent()); + auto Removed = Block->removeInstruction(*const_cast(DefiningInstruction)); + if (!Removed) + return std::unexpected(Removed.error()); + } + return std::optional>(std::move(NewRegisters)); +} + +Expected> Spiller::spillAtInstructions(Register VirtualReg) { + auto ClassID = regalloc_detail::registerClassFor(*Function, VirtualReg); + if (!ClassID) + return std::unexpected(ClassID.error()); + auto Validated = TargetInfo->validateSpillReload(*ClassID, *Target); + if (!Validated) { + std::string Message = + "target declares an allocatable spillable class without spill/reload support: "; + Message.append(Validated.error().message()); + return makeUnexpected(ErrorCode::InternalError, std::move(Message)); + } + auto StackSlot = Edit.getOrCreateSpillSlot(VirtualReg); + if (!StackSlot) + return std::unexpected(StackSlot.error()); + auto LiveInSpill = spillLiveIn(VirtualReg, *ClassID, *StackSlot); + if (!LiveInSpill) + return std::unexpected(LiveInSpill.error()); + + struct SpillSite final { + MachineInstr *Instruction = nullptr; + std::vector OperandIndices; + std::vector DebugIndices; + bool HasUse = false; + bool HasDef = false; + }; + std::vector Sites; + for (MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + SpillSite Site; + Site.Instruction = Instruction; + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + const MachineOperand *Operand = Instruction->operandAt(Index); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf(); + if (Reg == nullptr || *Reg != VirtualReg) + continue; + if (Operand->isDebugUse()) { + Site.DebugIndices.push_back(Index); + continue; + } + Site.OperandIndices.push_back(Index); + Site.HasUse |= Operand->isUse(); + Site.HasDef |= Operand->isDef(); + } + if (!Site.OperandIndices.empty() || !Site.DebugIndices.empty()) + Sites.push_back(std::move(Site)); + } + } + + std::vector NewRegisters; + for (SpillSite &Site : Sites) { + for (const std::size_t Index : Site.DebugIndices) { + MachineOperand *Operand = Site.Instruction->operandAt(Index); + auto Cleared = clearDebugRegisterOperand(*Operand); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + if (Site.OperandIndices.empty()) + continue; + + auto Child = Edit.createFrom(VirtualReg, false); + if (!Child) + return std::unexpected(Child.error()); + if (Site.HasUse) { + MachineIRBuilder Builder(*Function, *Target); + auto Positioned = Builder.setInsertPointBefore(*Site.Instruction); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Reload = TargetInfo->emitReload(Builder, *Child, *ClassID, *StackSlot, LaneMask::all()); + if (!Reload) + return std::unexpected(Reload.error()); + VirtRegMapEntry *Entry = Mapping->entry(VirtualReg); + if (Entry != nullptr) + ++Entry->Spill.ReloadCount; + } + for (const std::size_t Index : Site.OperandIndices) { + MachineOperand *Operand = Site.Instruction->operandAt(Index); + auto Replaced = Operand->setRegister(*Child); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + if (Site.HasDef) { + const InstructionDescriptor *Descriptor = + Target->instructionDescriptor(Site.Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "a terminator-defined value cannot be spilled on its outgoing edge"); + } + MachineIRBuilder Builder(*Function, *Target); + auto Positioned = Builder.setInsertPointAfter(*Site.Instruction); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Spill = TargetInfo->emitSpill(Builder, *Child, *ClassID, *StackSlot, LaneMask::all()); + if (!Spill) + return std::unexpected(Spill.error()); + VirtRegMapEntry *Entry = Mapping->entry(VirtualReg); + if (Entry != nullptr) + ++Entry->Spill.SpillCount; + } + NewRegisters.push_back(*Child); + } + return NewRegisters; +} + +Expected Spiller::spillLiveIn(Register VirtualReg, RegisterClassID Class, + FrameIndex StackSlot) { + const auto LiveIn = std::ranges::find_if(Function->registerInfo().liveIns(), + [VirtualReg](const PhysicalRegisterLiveIn &Value) { + return Value.InitialVirtualRegister == VirtualReg; + }); + if (LiveIn == Function->registerInfo().liveIns().end()) + return {}; + MachineBasicBlock *EntryBlock = Function->firstBlock(); + if (EntryBlock == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "function live-in spill requires an entry block"); + } + MachineIRBuilder Builder(*Function, *Target); + Expected Positioned = EntryBlock->firstInstruction() != nullptr + ? Builder.setInsertPointBefore(*EntryBlock->firstInstruction()) + : Builder.setInsertPoint(*EntryBlock); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Spill = TargetInfo->emitSpill(Builder, Register::fromPhysical(LiveIn->PhysReg), Class, + StackSlot, LaneMask::all()); + if (!Spill) + return std::unexpected(Spill.error()); + VirtRegMapEntry *Entry = Mapping->entry(VirtualReg); + if (Entry != nullptr) + ++Entry->Spill.SpillCount; + return {}; +} + +Expected> Spiller::spill(Register VirtualReg) { + if (!VirtualReg.isVirtual() || !Function->registerInfo().isKnownVirtualRegister(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, "Spiller requires a known virtual register"); + if (!Mapping->isSpillable(VirtualReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "register pressure requires spilling a non-spillable value"); + } + auto Rematerialized = tryRematerialize(VirtualReg); + if (!Rematerialized) + return std::unexpected(Rematerialized.error()); + if (*Rematerialized) + return std::move(**Rematerialized); + return spillAtInstructions(VirtualReg); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveRangeEdit.cpp b/backend/lib/CodeGen/LiveRangeEdit.cpp new file mode 100644 index 0000000..23a7b3d --- /dev/null +++ b/backend/lib/CodeGen/LiveRangeEdit.cpp @@ -0,0 +1,126 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRangeEdit.h" + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +namespace rcc { + +Expected LiveRangeEdit::createFrom(Register Parent, bool Spillable, + std::optional Origin) { + auto ParentInfo = Function->registerInfo().virtualRegisterInfo(Parent); + if (!ParentInfo) + return std::unexpected(ParentInfo.error()); + const VirtualRegisterInfo &Source = ParentInfo->get(); + Expected Created = Source.Type + ? Function->registerInfo().createVirtualRegister(*Source.Type) + : Function->registerInfo().createVirtualRegister(); + if (!Created) + return std::unexpected(Created.error()); + const Register Child = *Created; + auto Fail = [&](const Error &Failure) -> Expected { + auto Erased = Function->registerInfo().eraseVirtualRegister(Child); + if (!Erased) + return makeUnexpected(ErrorCode::InternalError, + "split virtual-register setup and rollback both failed"); + return std::unexpected(Failure); + }; + if (Source.Bank) { + auto Set = Function->registerInfo().setRegisterBank(Child, *Source.Bank); + if (!Set) + return Fail(Set.error()); + } + if (Source.RegClass) { + auto Set = Function->registerInfo().setRegisterClass(Child, *Source.RegClass); + if (!Set) + return Fail(Set.error()); + } + for (const PhysicalRegister Hint : Source.AllocationHints) { + auto Added = Function->registerInfo().addAllocationHint(Child, Hint); + if (!Added) + return Fail(Added.error()); + } + if (Source.TargetFlags != 0) { + auto Set = Function->registerInfo().setTargetRegisterFlags(Child, Source.TargetFlags); + if (!Set) + return Fail(Set.error()); + } + const VirtRegMapEntry *ParentEntry = Mapping->entry(Parent); + const Register Root = Origin.value_or( + ParentEntry != nullptr && ParentEntry->Origin ? *ParentEntry->Origin : Parent); + const std::optional ParentStackSlot = + ParentEntry == nullptr ? std::nullopt : ParentEntry->Spill.StackSlot; + const LaneMask ParentSpillLanes = + ParentEntry == nullptr ? LaneMask::all() : ParentEntry->Spill.Lanes; + auto Added = Mapping->add(Child, Spillable, Parent, Root); + if (!Added) + return Fail(Added.error()); + auto Split = Mapping->markSplit(Child, Parent, Root); + if (!Split) + return Fail(Split.error()); + if (ParentStackSlot) { + auto SharedSlot = Mapping->assignStackSlot(Child, *ParentStackSlot, ParentSpillLanes); + if (!SharedSlot) + return Fail(SharedSlot.error()); + } + return Child; +} + +Expected LiveRangeEdit::getOrCreateSpillSlot(Register VirtualReg) { + if (const auto Existing = Mapping->stackSlot(VirtualReg)) + return *Existing; + const VirtRegMapEntry *Entry = Mapping->entry(VirtualReg); + const Register Original = Entry != nullptr && Entry->Origin ? *Entry->Origin : VirtualReg; + if (Original != VirtualReg) { + if (const auto Existing = Mapping->stackSlot(Original)) { + auto Shared = Mapping->assignStackSlot(VirtualReg, *Existing); + if (!Shared) + return std::unexpected(Shared.error()); + return *Existing; + } + } + auto ClassID = regalloc_detail::registerClassFor(*Function, Original); + if (!ClassID) + return std::unexpected(ClassID.error()); + const RegisterClassDesc *Class = Target->registers().registerClass(*ClassID); + if (Class == nullptr || Class->SpillSizeInBits == 0 || Class->SpillAlignmentInBits == 0 || + Class->SpillSizeInBits % 8U != 0 || Class->SpillAlignmentInBits % 8U != 0) { + return makeUnexpected(ErrorCode::InternalError, + "allocatable register class has no valid spill size and alignment"); + } + auto Align = Alignment::create(Class->SpillAlignmentInBits / 8U); + if (!Align) + return std::unexpected(Align.error()); + StackObjectDesc Description; + Description.Kind = StackObjectKind::SpillSlot; + Description.Size = Class->SpillSizeInBits / 8U; + Description.Align = *Align; + auto Slot = Function->frameInfo().createObject(std::move(Description)); + if (!Slot) + return std::unexpected(Slot.error()); + auto AssignedOriginal = Mapping->assignStackSlot(Original, *Slot); + if (!AssignedOriginal) + return std::unexpected(AssignedOriginal.error()); + if (Original != VirtualReg) { + auto AssignedChild = Mapping->assignStackSlot(VirtualReg, *Slot); + if (!AssignedChild) + return std::unexpected(AssignedChild.error()); + } + return *Slot; +} + +Expected LiveRangeEdit::eraseVirtualRegister(Register VirtualReg) { + if (!Function->registerInfo().useEmpty(VirtualReg)) + return makeUnexpected(ErrorCode::InternalError, + "cannot erase a split virtual register with remaining uses"); + for (const MachineOperand &Operand : Function->registerInfo().defOperands(VirtualReg)) { + if (Operand.parent() != nullptr) + return makeUnexpected(ErrorCode::InternalError, + "cannot erase a split virtual register with remaining definitions"); + } + return Function->registerInfo().eraseVirtualRegister(VirtualReg); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/LiveRegMatrix.cpp b/backend/lib/CodeGen/LiveRegMatrix.cpp new file mode 100644 index 0000000..64c7046 --- /dev/null +++ b/backend/lib/CodeGen/LiveRegMatrix.cpp @@ -0,0 +1,330 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/LiveRegMatrix.h" + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] std::optional relevantLanes(const LiveInterval &Interval, + RegisterUnitLane Unit) noexcept { + if (Interval.SubRanges.empty()) + return Unit.Lanes; + LaneMask Result; + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (SubRange.Lanes.intersects(Unit.Lanes)) + Result = Result | (SubRange.Lanes & Unit.Lanes); + } + if (Result.empty()) + return std::nullopt; + return Result; +} + +[[nodiscard]] LaneMask normalizeUnitLanes(LaneMask UnitViewLanes, LaneMask RegisterLanes) noexcept { + std::uint64_t View = UnitViewLanes.rawValue(); + const std::uint64_t Selected = View & RegisterLanes.rawValue(); + std::uint64_t Normalized = 0; + std::uint32_t UnitLane = 0; + while (View != 0) { + const std::uint64_t RegisterLane = std::uint64_t{1} << std::countr_zero(View); + if ((Selected & RegisterLane) != 0) + Normalized |= std::uint64_t{1} << UnitLane; + View &= View - 1U; + ++UnitLane; + } + return LaneMask::fromRaw(Normalized); +} + +[[nodiscard]] LaneMask intervalUnitLanes(const LiveInterval &Interval, + RegisterUnitLane Unit) noexcept { + if (Interval.SubRanges.empty()) + return normalizeUnitLanes(Unit.Lanes, Unit.Lanes); + LaneMask Result; + for (const LiveSubRange &SubRange : Interval.SubRanges) + Result = Result | normalizeUnitLanes(Unit.Lanes, SubRange.Lanes); + return Result; +} + +[[nodiscard]] bool intervalLiveAtFixedRegister(const LiveInterval &Interval, + const PhysicalRegisterDesc &Candidate, + const PhysicalRegisterDesc &Fixed, + SlotIndex Position) noexcept { + for (const RegisterUnitLane CandidateUnit : Candidate.Units) { + const auto FixedUnit = + std::ranges::find(Fixed.Units, CandidateUnit.Unit, &RegisterUnitLane::Unit); + if (FixedUnit == Fixed.Units.end()) + continue; + const LaneMask FixedLanes = normalizeUnitLanes(FixedUnit->Lanes, FixedUnit->Lanes); + if (Interval.SubRanges.empty()) { + if (normalizeUnitLanes(CandidateUnit.Lanes, CandidateUnit.Lanes).intersects(FixedLanes) && + Interval.MainRange.liveAt(Position)) { + return true; + } + continue; + } + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (normalizeUnitLanes(CandidateUnit.Lanes, SubRange.Lanes).intersects(FixedLanes) && + SubRange.Range.liveAt(Position)) { + return true; + } + } + } + return false; +} + +[[nodiscard]] bool rangeForUnitOverlaps(const LiveInterval &Interval, RegisterUnitLane Unit, + const LiveRange &Other) noexcept { + if (!relevantLanes(Interval, Unit)) + return false; + if (Interval.SubRanges.empty()) + return Interval.MainRange.overlaps(Other); + for (const LiveSubRange &SubRange : Interval.SubRanges) { + if (SubRange.Lanes.intersects(Unit.Lanes) && SubRange.Range.overlaps(Other)) + return true; + } + return false; +} + +} // namespace + +bool regalloc_detail::intervalsOverlapOnPhysicalRegisters( + const LiveInterval &Left, PhysicalRegister LeftReg, const LiveInterval &Right, + PhysicalRegister RightReg, const TargetRegisterInfo &Registers) noexcept { + const PhysicalRegisterDesc *LeftDescription = Registers.physicalRegister(LeftReg); + const PhysicalRegisterDesc *RightDescription = Registers.physicalRegister(RightReg); + if (LeftDescription == nullptr || RightDescription == nullptr) + return true; + for (const RegisterUnitLane LeftUnit : LeftDescription->Units) { + for (const RegisterUnitLane RightUnit : RightDescription->Units) { + if (LeftUnit.Unit != RightUnit.Unit) + continue; + const LaneMask LeftUnitLanes = intervalUnitLanes(Left, LeftUnit); + const LaneMask RightUnitLanes = intervalUnitLanes(Right, RightUnit); + if (!LeftUnitLanes.intersects(RightUnitLanes)) + continue; + if (Left.SubRanges.empty() && Right.SubRanges.empty()) + return Left.MainRange.overlaps(Right.MainRange); + const auto LeftRanges = Left.SubRanges.empty() + ? std::span{} + : std::span(Left.SubRanges); + const auto RightRanges = Right.SubRanges.empty() + ? std::span{} + : std::span(Right.SubRanges); + if (LeftRanges.empty()) { + for (const LiveSubRange &RightRange : RightRanges) { + const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes); + if (LeftUnitLanes.intersects(RightRangeLanes) && + Left.MainRange.overlaps(RightRange.Range)) + return true; + } + continue; + } + if (RightRanges.empty()) { + for (const LiveSubRange &LeftRange : LeftRanges) { + const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes); + if (LeftRangeLanes.intersects(RightUnitLanes) && + LeftRange.Range.overlaps(Right.MainRange)) + return true; + } + continue; + } + for (const LiveSubRange &LeftRange : LeftRanges) { + const LaneMask LeftRangeLanes = normalizeUnitLanes(LeftUnit.Lanes, LeftRange.Lanes); + if (LeftRangeLanes.empty()) + continue; + for (const LiveSubRange &RightRange : RightRanges) { + const LaneMask RightRangeLanes = normalizeUnitLanes(RightUnit.Lanes, RightRange.Lanes); + if (LeftRangeLanes.intersects(RightRangeLanes) && + LeftRange.Range.overlaps(RightRange.Range)) + return true; + } + } + } + } + return false; +} + +bool LiveRegMatrix::intervalOverlapsUnit(const LiveInterval &Interval, RegisterUnitLane Unit, + const LiveRange &UnitRange) const noexcept { + return rangeForUnitOverlaps(Interval, Unit, UnitRange); +} + +bool LiveRegMatrix::intervalsOverlapOnCandidates(const LiveInterval &Left, PhysicalRegister LeftReg, + const LiveInterval &Right, + PhysicalRegister RightReg) const noexcept { + return regalloc_detail::intervalsOverlapOnPhysicalRegisters(Left, LeftReg, Right, RightReg, + Target->registers()); +} + +std::vector +LiveRegMatrix::collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const { + std::vector Result; + const LiveInterval *Interval = Intervals->interval(VirtualReg); + const PhysicalRegisterDesc *Candidate = Target->registers().physicalRegister(PhysicalReg); + if (Interval == nullptr || Candidate == nullptr) + return Result; + + for (const MachineBasicBlock *Block = Function->firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const SlotIndex Position = Intervals->slot(*Instruction); + if (!Position.isValid()) + continue; + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isPhysical()) + continue; + const auto Fixed = Reg->physicalRegister(); + if (!Fixed) + continue; + const PhysicalRegister FixedReg = Fixed.value(); + if (!Target->registers().regsOverlap(FixedReg, PhysicalReg)) + continue; + const PhysicalRegisterDesc *FixedDescription = + Target->registers().physicalRegister(FixedReg); + if (FixedDescription == nullptr) + continue; + const SlotIndex OperandPosition = + Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber) + ? Position.earlyClobberSlot() + : Position.registerSlot(); + if (intervalLiveAtFixedRegister(*Interval, *Candidate, *FixedDescription, + OperandPosition)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::FixedRegister, + std::nullopt, FixedReg, std::nullopt, + Instruction->stableID()}); + } + } + } + } + + for (const RegMaskPosition &Mask : Intervals->regMaskPositions()) { + if (Mask.Mask && Mask.Mask->clobbers(PhysicalReg) && + Interval->MainRange.liveAt(Mask.Position)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterMask, std::nullopt, + std::nullopt, std::nullopt, Mask.Instruction}); + } + } + + for (const RegisterUnitLane Unit : Candidate->Units) { + const LiveRange *FixedRange = Intervals->regUnitRange(Unit.Unit); + if (FixedRange != nullptr && intervalOverlapsUnit(*Interval, Unit, *FixedRange)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::RegisterUnit, std::nullopt, + std::nullopt, Unit.Unit, std::nullopt}); + } + } + + for (const auto &[OtherReg, OtherPhysical] : OrderedAssignments) { + if (OtherReg == VirtualReg) + continue; + const LiveInterval *OtherInterval = Intervals->interval(OtherReg); + if (OtherInterval != nullptr && + intervalsOverlapOnCandidates(*Interval, PhysicalReg, *OtherInterval, OtherPhysical)) { + Result.push_back(RegisterInterference{RegisterInterferenceKind::VirtualRegister, OtherReg, + std::nullopt, std::nullopt, std::nullopt}); + } + } + + std::ranges::sort( + Result, [](const RegisterInterference &Left, const RegisterInterference &Right) { + return std::tuple{Left.Kind, Left.VirtualReg.value_or(Register{}).opaqueValue(), + Left.FixedReg.value_or(PhysicalRegister{}).number(), + Left.Unit ? Left.Unit->value() : 0U, + Left.Instruction ? Left.Instruction->value() : 0ULL} < + std::tuple{Right.Kind, Right.VirtualReg.value_or(Register{}).opaqueValue(), + Right.FixedReg.value_or(PhysicalRegister{}).number(), + Right.Unit ? Right.Unit->value() : 0U, + Right.Instruction ? Right.Instruction->value() : 0ULL}; + }); + Result.erase(std::unique(Result.begin(), Result.end(), + [](const RegisterInterference &Left, const RegisterInterference &Right) { + return Left.Kind == Right.Kind && + Left.VirtualReg == Right.VirtualReg && + Left.FixedReg == Right.FixedReg && Left.Unit == Right.Unit && + Left.Instruction == Right.Instruction; + }), + Result.end()); + return Result; +} + +RegisterInterference LiveRegMatrix::checkInterference(Register VirtualReg, + PhysicalRegister PhysicalReg) const noexcept { + const std::vector Values = collectInterferences(VirtualReg, PhysicalReg); + if (Values.empty()) + return {}; + return Values.front(); +} + +Expected LiveRegMatrix::assign(Register VirtualReg, PhysicalRegister PhysicalReg) { + if (!VirtualReg.isVirtual() || Intervals->interval(VirtualReg) == nullptr || + Target->registers().physicalRegister(PhysicalReg) == nullptr) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "LiveRegMatrix assignment requires a known interval and physical register"); + } + if (regalloc_detail::isUnavailablePhysicalRegister(*Function, Target->registers(), PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix cannot assign an unavailable physical register"); + } + auto Info = Function->registerInfo().virtualRegisterInfo(VirtualReg); + if (!Info) + return std::unexpected(Info.error()); + const auto ClassID = Info->get().RegClass; + if (ClassID) { + if (!Target->registers().registerClassContains(ClassID.value(), PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix assignment is outside the virtual register class"); + } + } + if (!regalloc_detail::candidateSupportsSubRegisters(*Function, Target->registers(), VirtualReg, + PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "LiveRegMatrix assignment lacks a required subregister view"); + } + if (Assignments.contains(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is already assigned"); + const RegisterInterference Interference = checkInterference(VirtualReg, PhysicalReg); + if (Interference.Kind != RegisterInterferenceKind::Free) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "physical register assignment has live interference"); + } + Assignments.emplace(VirtualReg, PhysicalReg); + OrderedAssignments.emplace_back(VirtualReg, PhysicalReg); + std::ranges::sort(OrderedAssignments, [](const auto &Left, const auto &Right) { + return Left.first.opaqueValue() < Right.first.opaqueValue(); + }); + return {}; +} + +Expected LiveRegMatrix::unassign(Register VirtualReg) { + if (!Assignments.erase(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, "virtual register is not assigned"); + std::erase_if(OrderedAssignments, + [VirtualReg](const auto &Entry) { return Entry.first == VirtualReg; }); + return {}; +} + +std::optional LiveRegMatrix::assignment(Register VirtualReg) const noexcept { + const auto Position = Assignments.find(VirtualReg); + if (Position == Assignments.end()) + return std::nullopt; + return Position->second; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/MachineAnalyses.cpp b/backend/lib/CodeGen/MachineAnalyses.cpp index cbc46fd..33dc14f 100644 --- a/backend/lib/CodeGen/MachineAnalyses.cpp +++ b/backend/lib/CodeGen/MachineAnalyses.cpp @@ -12,6 +12,7 @@ #include #include #include +#include #include #include #include @@ -296,7 +297,7 @@ Expected MachineLoopAnalysis::run(MachineFunction & Result ResultValue; std::vector Blocks = linkedBlocks(Function); const auto Order = blockOrder(Blocks); - std::unordered_map> LoopBlocks; + std::map> LoopBlocks; std::unordered_map> LoopLatches; for (MachineBasicBlock *Latch : Blocks) { diff --git a/backend/lib/CodeGen/MachineCompilationStatus.cpp b/backend/lib/CodeGen/MachineCompilationStatus.cpp index 600deac..1091b52 100644 --- a/backend/lib/CodeGen/MachineCompilationStatus.cpp +++ b/backend/lib/CodeGen/MachineCompilationStatus.cpp @@ -42,6 +42,7 @@ isKnownDiagnosticSeverity(MachineCompilationDiagnosticSeverity Severity) noexcep case ErrorCode::ParseError: case ErrorCode::VerificationError: case ErrorCode::Unsupported: + case ErrorCode::RegisterAllocationFailed: case ErrorCode::IoError: case ErrorCode::InternalError: return true; diff --git a/backend/lib/CodeGen/MachineFrameInfo.cpp b/backend/lib/CodeGen/MachineFrameInfo.cpp index 21a4b78..a6f7a77 100644 --- a/backend/lib/CodeGen/MachineFrameInfo.cpp +++ b/backend/lib/CodeGen/MachineFrameInfo.cpp @@ -66,8 +66,7 @@ parseMachineFramePointerPolicy(std::string_view Name) noexcept { return std::nullopt; } -std::string_view -getMachineFramePointerPolicyName(MachineFramePointerPolicy Policy) noexcept { +std::string_view getMachineFramePointerPolicyName(MachineFramePointerPolicy Policy) noexcept { switch (Policy) { case MachineFramePointerPolicy::None: return "none"; @@ -96,8 +95,8 @@ bool StackObject::isSpill() const noexcept { bool StackObject::isFixed() const noexcept { const StackObjectDesc *Desc = description(); - return Desc != nullptr && (Desc->Kind == StackObjectKind::FixedABI || - Desc->Kind == StackObjectKind::FixedSpillSlot); + return Desc != nullptr && + (Desc->Kind == StackObjectKind::FixedABI || Desc->Kind == StackObjectKind::FixedSpillSlot); } bool StackObject::isVariableSized() const noexcept { @@ -142,9 +141,8 @@ Expected MachineFrameInfo::verifyDescription(const StackObjectDesc &Descri return makeUnexpected(ErrorCode::InvalidArgument, "callee-saved stack objects require a nonzero physical register"); } - if (Description.LocalOffset && - (Description.Kind == StackObjectKind::FixedABI || - Description.Kind == StackObjectKind::FixedSpillSlot)) { + if (Description.LocalOffset && (Description.Kind == StackObjectKind::FixedABI || + Description.Kind == StackObjectKind::FixedSpillSlot)) { return makeUnexpected(ErrorCode::InvalidArgument, "fixed ABI stack objects cannot have a local frame offset"); } @@ -196,8 +194,7 @@ Expected MachineFrameInfo::verifyStateStructure(const MachineFrameState &S for (const PhysicalRegister Reg : Point.Registers) { if (Reg.number() == 0 || !Registers.insert(Reg).second) { return makeUnexpected(ErrorCode::InvalidArgument, - std::string(Kind) + - " point registers must be nonzero and unique"); + std::string(Kind) + " point registers must be nonzero and unique"); } } } diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp index ced3b1a..0048194 100644 --- a/backend/lib/CodeGen/MachineFunctionCloner.cpp +++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp @@ -526,8 +526,7 @@ cloneMemOperand(const MachineMemOperand &SourceOperand, CloneState &State) { } return {}; }; - auto SaveResult = - ClonePoints(State.Source.frameInfo().state().SavePoints, FrameState.SavePoints); + auto SaveResult = ClonePoints(State.Source.frameInfo().state().SavePoints, FrameState.SavePoints); if (!SaveResult) return SaveResult; auto RestoreResult = diff --git a/backend/lib/CodeGen/MachineJumpTableInfo.cpp b/backend/lib/CodeGen/MachineJumpTableInfo.cpp index 5ba0853..c832e7c 100644 --- a/backend/lib/CodeGen/MachineJumpTableInfo.cpp +++ b/backend/lib/CodeGen/MachineJumpTableInfo.cpp @@ -84,9 +84,8 @@ Expected MachineJumpTableInfo::reserveTable() { return Index; } -Expected -MachineJumpTableInfo::defineReservedTable(JumpTableIndex Index, - MachineJumpTableDesc Description) { +Expected MachineJumpTableInfo::defineReservedTable(JumpTableIndex Index, + MachineJumpTableDesc Description) { if (Frozen) { return makeUnexpected(ErrorCode::InvalidArgument, "frozen jump table info cannot define reserved tables"); diff --git a/backend/lib/CodeGen/MachineLiveness.cpp b/backend/lib/CodeGen/MachineLiveness.cpp index b3d88cd..327ae7d 100644 --- a/backend/lib/CodeGen/MachineLiveness.cpp +++ b/backend/lib/CodeGen/MachineLiveness.cpp @@ -1662,10 +1662,9 @@ LiveIntervalsAnalysis::run(MachineFunction &Function, const TargetDescription &T 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::ranges::sort(Interval.AllocationHints, [](PhysicalRegister Left, PhysicalRegister Right) { - return Left.number() < Right.number(); - }); std::uint64_t Weight = 1; for (const MachineOperand &Operand : Function.registerInfo().useOperands(Reg, false)) { diff --git a/backend/lib/CodeGen/MachinePass.cpp b/backend/lib/CodeGen/MachinePass.cpp index e6dccd0..ae69b1c 100644 --- a/backend/lib/CodeGen/MachinePass.cpp +++ b/backend/lib/CodeGen/MachinePass.cpp @@ -20,6 +20,7 @@ #include #include #include +#include #include #include #include @@ -164,8 +165,9 @@ MachineAnalysisManager::registerAnalysisImpl(MachineAnalysisRegistration Registr return makeUnexpected(ErrorCode::InvalidArgument, "machine analysis name is already registered"); } - Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner), - std::move(Invalidator)}); + const AnalysisID RegistrationID = Registration.ID; + Registry.emplace(RegistrationID, RegisteredAnalysis{std::move(Registration), std::move(Runner), + std::move(Invalidator)}); return {}; } @@ -287,7 +289,7 @@ void MachineAnalysisManager::invalidate(MachineFunction &Function, if (FunctionPosition == Cache.end() || Preserved.preservesAll() || Changes.empty()) return; - std::unordered_set Invalid; + std::set Invalid; for (auto &[ID, Entry] : FunctionPosition->second) { if (Preserved.preserves(ID)) continue; @@ -406,8 +408,9 @@ Expected CompilationUnitAnalysisManager::registerAnalysisImpl( return makeUnexpected(ErrorCode::InvalidArgument, "compilation-unit analysis name is already registered"); } - Registry.emplace(Registration.ID, RegisteredAnalysis{std::move(Registration), std::move(Runner), - std::move(Invalidator)}); + const AnalysisID RegistrationID = Registration.ID; + Registry.emplace(RegistrationID, RegisteredAnalysis{std::move(Registration), std::move(Runner), + std::move(Invalidator)}); return {}; } @@ -524,7 +527,7 @@ void CompilationUnitAnalysisManager::invalidate(CompilationUnit &Unit, if (UnitPosition == Cache.end() || Preserved.preservesAll() || Changes.empty()) return; - std::unordered_set Invalid; + std::set Invalid; for (auto &[ID, Entry] : UnitPosition->second) { if (Preserved.preserves(ID)) continue; @@ -1238,10 +1241,10 @@ Expected MachinePassManager::runFunctions(CompilationUnit &Unit, for (std::size_t Index = 0; Index < FunctionCount; ++Index) { if (Instrumentation != nullptr) Instrumentation->replayBufferedEvents(EventBuffers[Index]); - if (Failures[Index]) { - return std::unexpected( - prefixedError(*Failures[Index], - "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: ")); + const auto &Failure = Failures[Index]; + if (Failure) { + return std::unexpected(prefixedError( + *Failure, "function '" + std::string(Unit.functionAt(Index)->name()) + "' failed: ")); } } return {}; diff --git a/backend/lib/CodeGen/MachineRegisterInfo.cpp b/backend/lib/CodeGen/MachineRegisterInfo.cpp index 3784b22..7bd0ef3 100644 --- a/backend/lib/CodeGen/MachineRegisterInfo.cpp +++ b/backend/lib/CodeGen/MachineRegisterInfo.cpp @@ -229,6 +229,11 @@ Expected MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg, return {}; } +void MachineRegisterInfo::clearLiveInVirtualRegisters() noexcept { + for (PhysicalRegisterLiveIn &LiveIn : LiveIns) + LiveIn.InitialVirtualRegister.reset(); +} + Expected MachineRegisterInfo::reservePhysicalRegister(PhysicalRegister PhysReg) { if (!PhysReg.isValid()) { return makeUnexpected(ErrorCode::InvalidArgument, diff --git a/backend/lib/CodeGen/RegAllocBase.cpp b/backend/lib/CodeGen/RegAllocBase.cpp new file mode 100644 index 0000000..1aae22d --- /dev/null +++ b/backend/lib/CodeGen/RegAllocBase.cpp @@ -0,0 +1,91 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RegAllocBase.h" + +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/Spiller.h" + +#include +#include +#include +#include + +namespace rcc { + +std::vector +orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals, + const MachineFunction &Function) { + std::vector Result; + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { + auto Reg = Register::makeVirtual(Index); + if (!Reg) + continue; + const LiveInterval *Interval = Intervals.interval(*Reg); + if (Interval != nullptr && !Interval->MainRange.empty()) + Result.push_back(Interval); + } + std::ranges::sort(Result, [](const LiveInterval *Left, const LiveInterval *Right) { + const LiveSegment &LeftSegment = Left->MainRange.segments().front(); + const LiveSegment &RightSegment = Right->MainRange.segments().front(); + if (LeftSegment.Start != RightSegment.Start) + return LeftSegment.Start < RightSegment.Start; + if (LeftSegment.End != RightSegment.End) + return LeftSegment.End < RightSegment.End; + return Left->Reg.opaqueValue() < Right->Reg.opaqueValue(); + }); + return Result; +} + +Expected RegAllocBase::run() { + const std::uint64_t InitialFingerprint = regalloc_detail::allocationFingerprint(Function); + const std::size_t InitialFrameObjects = Function.frameInfo().liveObjectCount(); + VirtRegMap Mapping(Function); + auto Initialized = regalloc_detail::initializeMapping(Function, Mapping); + if (!Initialized) + return std::unexpected(Initialized.error()); + + std::unordered_set SeenFingerprints; + while (true) { + const std::uint64_t Fingerprint = regalloc_detail::allocationFingerprint(Function); + if (!SeenFingerprints.insert(Fingerprint).second) { + return makeUnexpected(ErrorCode::InternalError, + "register allocation spill/rebuild cycle made no progress"); + } + auto Intervals = Analyses.getResult(Function, Target); + if (!Intervals) + return std::unexpected(Intervals.error()); + auto Round = allocateRound(**Intervals, Mapping); + if (!Round) + return std::unexpected(Round.error()); + if (Round->Spilled.empty()) + break; + + std::ranges::sort(Round->Spilled, [](Register Left, Register Right) { + return Left.opaqueValue() < Right.opaqueValue(); + }); + Spiller ValueSpiller(Function, Target, TargetInfo, Mapping, Options.EnableRematerialization); + for (const Register VirtualReg : Round->Spilled) { + VirtRegMapEntry *Entry = Mapping.entry(VirtualReg); + if (Entry != nullptr) { + Entry->PhysicalReg.reset(); + Entry->State = VirtRegAllocationState::Unassigned; + } + auto NewRegisters = ValueSpiller.spill(VirtualReg); + if (!NewRegisters) + return std::unexpected(NewRegisters.error()); + } + Analyses.clear(Function); + } + + auto Rewritten = rewriteVirtualRegisters(Function, Target, Mapping); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + const std::uint64_t FinalFingerprint = regalloc_detail::allocationFingerprint(Function); + regalloc_detail::AllocationRunResult Result; + Result.Changed = InitialFingerprint != FinalFingerprint || *Rewritten; + Result.ChangedInstructions = InitialFingerprint != FinalFingerprint; + Result.ChangedFrame = InitialFrameObjects != Function.frameInfo().liveObjectCount(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/RegAllocBase.h b/backend/lib/CodeGen/RegAllocBase.h new file mode 100644 index 0000000..5af5ed0 --- /dev/null +++ b/backend/lib/CodeGen/RegAllocBase.h @@ -0,0 +1,51 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +// The private header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) +#ifndef RCC_LIB_CODEGEN_REGALLOCBASE_H +#define RCC_LIB_CODEGEN_REGALLOCBASE_H + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/MachineLiveness.h" +#include "rcc/CodeGen/RegAllocCommon.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" +#include "rcc/CodeGen/VirtRegMap.h" + +#include + +namespace rcc { + +struct AllocationRoundResult final { + std::vector Spilled; +}; + +class RegAllocBase { +public: + virtual ~RegAllocBase() = default; + + [[nodiscard]] Expected run(); + +protected: + RegAllocBase(MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo, MachineAnalysisManager &Analyses, + RegisterAllocationOptions Options) noexcept + : Function(Function), Target(Target), TargetInfo(TargetInfo), Analyses(Analyses), + Options(Options) {} + + [[nodiscard]] virtual Expected + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) = 0; + + MachineFunction &Function; + const TargetDescription &Target; + const TargetRegisterAllocationInfo &TargetInfo; + MachineAnalysisManager &Analyses; + RegisterAllocationOptions Options; +}; + +[[nodiscard]] std::vector +orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals, + const MachineFunction &Function); + +} // namespace rcc + +#endif // RCC_LIB_CODEGEN_REGALLOCBASE_H diff --git a/backend/lib/CodeGen/RegAllocBasic.cpp b/backend/lib/CodeGen/RegAllocBasic.cpp new file mode 100644 index 0000000..4bb7b23 --- /dev/null +++ b/backend/lib/CodeGen/RegAllocBasic.cpp @@ -0,0 +1,136 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RegAllocBasic.h" + +#include "RegAllocBase.h" +#include "rcc/CodeGen/LiveRegMatrix.h" +#include "rcc/CodeGen/MachineLiveness.h" + +#include +#include +#include + +namespace rcc { +namespace { + +class BasicAllocatorEngine final : public RegAllocBase { +public: + BasicAllocatorEngine(MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo, + MachineAnalysisManager &Analyses, RegisterAllocationOptions Options) + : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {} + +private: + [[nodiscard]] Expected + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override { + LiveRegMatrix Matrix(Function, Target, Intervals); + AllocationRoundResult Result; + std::vector Worklist = orderedAllocationIntervals(Intervals, Function); + std::ranges::stable_sort(Worklist, [&](const LiveInterval *Left, const LiveInterval *Right) { + const bool LeftSpillable = Mapping.isSpillable(Left->Reg); + const bool RightSpillable = Mapping.isSpillable(Right->Reg); + if (LeftSpillable != RightSpillable) + return !LeftSpillable; + if (Left->SpillWeight != Right->SpillWeight) + return Left->SpillWeight > Right->SpillWeight; + return false; + }); + for (const LiveInterval *Interval : Worklist) { + const Register VirtualReg = Interval->Reg; + if (regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg)) { + auto Marked = Mapping.setSpillable(VirtualReg, false); + if (!Marked) + return std::unexpected(Marked.error()); + } + auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg); + if (!Candidates) + return std::unexpected(Candidates.error()); + bool Assigned = false; + for (const PhysicalRegister Candidate : *Candidates) { + if (Matrix.checkInterference(VirtualReg, Candidate).Kind != RegisterInterferenceKind::Free) + continue; + auto MatrixAssignment = Matrix.assign(VirtualReg, Candidate); + if (!MatrixAssignment) + continue; + auto MapAssignment = Mapping.assign(VirtualReg, Candidate); + if (!MapAssignment) + return std::unexpected(MapAssignment.error()); + Assigned = true; + break; + } + if (!Assigned) { + if (!Mapping.isSpillable(VirtualReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "BasicAllocator cannot assign a non-spillable virtual register"); + } + Result.Spilled.push_back(VirtualReg); + } + } + return Result; + } +}; + +[[nodiscard]] const MachinePassContract &basicContract() { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "BasicAllocator", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten, + MachineFunctionProperty::TracksLiveness}, + .Sets = {MachineFunctionProperty::NoVRegs}, + .Clears = {}, + .RequiredAnalyses = {MachineAnalysisManager::id()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +} // namespace + +const MachinePassContract &BasicAllocatorPass::contract() const noexcept { + return basicContract(); +} + +Expected BasicAllocatorPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "BasicAllocator requires target behavior"); + auto Required = regalloc_detail::requireAllocationProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + auto Trial = regalloc_detail::cloneForAllocation(Function, Target); + if (!Trial) + return std::unexpected(Trial.error()); + MachineAnalysisManager TrialAnalyses; + auto Registered = registerStage11MachineAnalyses(TrialAnalyses); + if (!Registered) + return std::unexpected(Registered.error()); + BasicAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, + Options); + auto TrialRun = TrialAllocator.run(); + if (!TrialRun) + return std::unexpected(TrialRun.error()); + auto TrialVerification = + regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract()); + if (!TrialVerification) + return std::unexpected(TrialVerification.error()); + BasicAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options); + auto Allocated = Allocator.run(); + if (!Allocated) { + return std::unexpected(regalloc_detail::withPrefix( + Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: ")); + } + return regalloc_detail::passResult(*Allocated); +} + +std::unique_ptr +createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info, + RegisterAllocationOptions Options) { + return std::make_unique(Info, Options); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/RegAllocBasic.h b/backend/lib/CodeGen/RegAllocBasic.h new file mode 100644 index 0000000..8a68f5f --- /dev/null +++ b/backend/lib/CodeGen/RegAllocBasic.h @@ -0,0 +1,31 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +// The private header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) +#ifndef RCC_LIB_CODEGEN_REGALLOCBASIC_H +#define RCC_LIB_CODEGEN_REGALLOCBASIC_H + +#include "rcc/CodeGen/RegAllocCommon.h" +#include "rcc/CodeGen/TargetRegisterAllocationInfo.h" + +namespace rcc { + +class BasicAllocatorPass final : public MachineFunctionPass { +public: + explicit BasicAllocatorPass(const TargetRegisterAllocationInfo &Info, + RegisterAllocationOptions Options = {}) noexcept + : Info(&Info), Options(Options) {} + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) override; + +private: + const TargetRegisterAllocationInfo *Info; + RegisterAllocationOptions Options; +}; + +} // namespace rcc + +#endif // RCC_LIB_CODEGEN_REGALLOCBASIC_H diff --git a/backend/lib/CodeGen/RegAllocFast.cpp b/backend/lib/CodeGen/RegAllocFast.cpp new file mode 100644 index 0000000..9b087cc --- /dev/null +++ b/backend/lib/CodeGen/RegAllocFast.cpp @@ -0,0 +1,608 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/RegAllocFast.h" + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/LiveRangeEdit.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" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +class FastAllocatorEngine final { +public: + FastAllocatorEngine(MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo, + const LiveVariablesAnalysis::Result &Liveness) + : Function(Function), Target(Target), TargetInfo(TargetInfo), Liveness(Liveness), + Mapping(Function), Edit(Function, Target, Mapping) {} + + [[nodiscard]] Expected run() { + const std::uint64_t InitialFingerprint = regalloc_detail::allocationFingerprint(Function); + const std::size_t InitialFrameObjects = Function.frameInfo().liveObjectCount(); + auto Initialized = regalloc_detail::initializeMapping(Function, Mapping); + if (!Initialized) + return std::unexpected(Initialized.error()); + + bool IsEntry = true; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + auto Allocated = allocateBlock(*Block, IsEntry); + if (!Allocated) + return std::unexpected(Allocated.error()); + IsEntry = false; + } + + Function.registerInfo().clearLiveInVirtualRegisters(); + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); + ++Index) { + auto Reg = regalloc_detail::virtualRegisterAt(Index); + if (!Reg) + return std::unexpected(Reg.error()); + if (!Function.registerInfo().isKnownVirtualRegister(*Reg)) + continue; + auto Erased = Function.registerInfo().eraseVirtualRegister(*Reg); + if (!Erased) + return std::unexpected(Erased.error()); + } + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + + regalloc_detail::AllocationRunResult Result; + const std::uint64_t FinalFingerprint = regalloc_detail::allocationFingerprint(Function); + Result.Changed = InitialFingerprint != FinalFingerprint; + Result.ChangedInstructions = Result.Changed; + Result.ChangedFrame = InitialFrameObjects != Function.frameInfo().liveObjectCount(); + return Result; + } + +private: + struct Location final { + PhysicalRegister PhysicalReg; + bool Dirty = false; + }; + + struct InstructionRegister final { + Register VirtualReg; + std::vector Operands; + bool HasUse = false; + bool HasDef = false; + std::size_t FirstOperand = 0; + }; + + struct BlockLiveInState final { + PhysicalRegister Reg; + std::size_t RemainingUses = 0; + }; + + [[nodiscard]] bool liveOut(const MachineBasicBlock &Block, Register Reg) const noexcept { + return Liveness.isLiveOut(Block, Reg); + } + + [[nodiscard]] bool neededLater(const MachineBasicBlock &Block, Register Reg) const noexcept { + const auto Position = RemainingUses.find(Reg); + return (Position != RemainingUses.end() && Position->second != 0) || liveOut(Block, Reg); + } + + [[nodiscard]] std::optional ownerOf(PhysicalRegister Reg) const noexcept { + for (const auto &[VirtualReg, Value] : Locations) { + if (Target.registers().regsOverlap(Value.PhysicalReg, Reg)) + return VirtualReg; + } + return std::nullopt; + } + + [[nodiscard]] bool physicalLiveOut(const MachineBasicBlock &Block, + PhysicalRegister Reg) const noexcept { + const PhysicalRegisterDesc *Description = Target.registers().physicalRegister(Reg); + if (Description == nullptr) + return true; + return std::ranges::any_of(Description->Units, [&](const RegisterUnitLane &Unit) { + return Liveness.isUnitLiveOut(Block, Unit.Unit, Unit.Lanes); + }); + } + + [[nodiscard]] bool blockedByBlockLiveIn(PhysicalRegister Reg) const noexcept { + return std::ranges::any_of(BlockLiveIns, [&](const BlockLiveInState &LiveIn) { + return Target.registers().regsOverlap(LiveIn.Reg, Reg); + }); + } + + void initializeBlockLiveIns(const MachineBasicBlock &Block) { + BlockLiveIns.clear(); + for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) { + if (LiveIn.Lanes.empty() || + std::ranges::any_of(BlockLiveIns, [&](const BlockLiveInState &Existing) { + return Existing.Reg == LiveIn.PhysReg; + })) + continue; + BlockLiveIns.push_back({LiveIn.PhysReg, 0}); + } + + for (const MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isPhysical() || !Operand.isUse()) + continue; + const auto PhysicalValue = Reg->physicalRegister(); + if (!PhysicalValue) + continue; + const PhysicalRegister Physical = PhysicalValue.value(); + for (BlockLiveInState &LiveIn : BlockLiveIns) { + if (Target.registers().regsOverlap(LiveIn.Reg, Physical)) + ++LiveIn.RemainingUses; + } + } + } + } + + void updateBlockLiveIns(const MachineBasicBlock &Block, const MachineInstr &Instruction) { + std::vector Defined; + std::vector Masks; + for (const MachineOperand &Operand : Instruction.operands()) { + if (const Register *Reg = Operand.getIf(); Reg != nullptr && Reg->isPhysical()) { + const auto PhysicalValue = Reg->physicalRegister(); + if (Operand.isDef() && PhysicalValue) + Defined.push_back(PhysicalValue.value()); + } + if (const auto *Mask = Operand.getIf(); Mask != nullptr && Mask->Mask) + Masks.push_back(Mask->Mask.get()); + } + + for (auto Position = BlockLiveIns.begin(); Position != BlockLiveIns.end();) { + BlockLiveInState &LiveIn = *Position; + for (const MachineOperand &Operand : Instruction.operands()) { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isPhysical() || !Operand.isUse()) + continue; + const auto PhysicalValue = Reg->physicalRegister(); + if (!PhysicalValue || !Target.registers().regsOverlap(LiveIn.Reg, PhysicalValue.value())) + continue; + if (LiveIn.RemainingUses != 0) + --LiveIn.RemainingUses; + } + + const bool DefinedHere = std::ranges::any_of(Defined, [&](PhysicalRegister Reg) { + return Target.registers().regsOverlap(LiveIn.Reg, Reg); + }); + const bool MaskClobbered = std::ranges::any_of( + Masks, [&](const RegisterMask *Mask) { return Mask->clobbers(LiveIn.Reg); }); + const bool KeepForOutput = physicalLiveOut(Block, LiveIn.Reg); + if (!KeepForOutput && (DefinedHere || MaskClobbered || LiveIn.RemainingUses == 0)) + Position = BlockLiveIns.erase(Position); + else + ++Position; + } + } + + [[nodiscard]] bool overlapsAny(PhysicalRegister Candidate, + std::span Values) const noexcept { + return std::ranges::any_of(Values, [&](PhysicalRegister Value) { + return Target.registers().regsOverlap(Candidate, Value); + }); + } + + [[nodiscard]] Expected spillSlot(Register Reg) { + auto ClassID = regalloc_detail::registerClassFor(Function, Reg); + if (!ClassID) + return std::unexpected(ClassID.error()); + auto Validated = TargetInfo.validateSpillReload(*ClassID, Target); + if (!Validated) { + return makeUnexpected( + ErrorCode::InternalError, + "target declares an allocatable class without FastAllocator spill hooks"); + } + return Edit.getOrCreateSpillSlot(Reg); + } + + [[nodiscard]] Expected emitSpillBefore(Register Reg, PhysicalRegister PhysicalReg, + MachineInstr *Before, MachineBasicBlock &Block) { + auto ClassID = regalloc_detail::registerClassFor(Function, Reg); + if (!ClassID) + return std::unexpected(ClassID.error()); + auto Slot = spillSlot(Reg); + if (!Slot) + return std::unexpected(Slot.error()); + MachineIRBuilder Builder(Function, Target); + Expected Positioned = + Before != nullptr ? Builder.setInsertPointBefore(*Before) : Builder.setInsertPoint(Block); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Spill = TargetInfo.emitSpill(Builder, Register::fromPhysical(PhysicalReg), *ClassID, *Slot, + LaneMask::all()); + if (!Spill) + return std::unexpected(Spill.error()); + VirtRegMapEntry *Entry = Mapping.entry(Reg); + if (Entry != nullptr) + ++Entry->Spill.SpillCount; + return {}; + } + + [[nodiscard]] Expected evict(Register Reg, MachineInstr &Before, MachineBasicBlock &Block, + bool Preserve) { + const auto Position = Locations.find(Reg); + if (Position == Locations.end()) + return {}; + if (Position->second.Dirty && Preserve) { + auto Stored = emitSpillBefore(Reg, Position->second.PhysicalReg, &Before, Block); + if (!Stored) + return std::unexpected(Stored.error()); + } + Locations.erase(Position); + return {}; + } + + [[nodiscard]] Expected + ensureLocation(Register Reg, bool NeedsValue, MachineInstr &Instruction, MachineBasicBlock &Block, + std::span Fixed, std::span Locked, + const std::unordered_set &CurrentRegisters) { + const auto Existing = Locations.find(Reg); + if (Existing != Locations.end() && !overlapsAny(Existing->second.PhysicalReg, Fixed) && + !overlapsAny(Existing->second.PhysicalReg, Locked)) + return Existing->second.PhysicalReg; + if (Existing != Locations.end()) { + auto Evicted = evict(Reg, Instruction, Block, NeedsValue || neededLater(Block, Reg)); + if (!Evicted) + return std::unexpected(Evicted.error()); + } + + auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg); + if (!Candidates) + return std::unexpected(Candidates.error()); + for (const PhysicalRegister Candidate : *Candidates) { + if (overlapsAny(Candidate, Fixed) || overlapsAny(Candidate, Locked)) + continue; + if (blockedByBlockLiveIn(Candidate)) + continue; + if (const auto Owner = ownerOf(Candidate)) { + if (CurrentRegisters.contains(*Owner)) + continue; + auto Evicted = evict(*Owner, Instruction, Block, neededLater(Block, *Owner)); + if (!Evicted) + return std::unexpected(Evicted.error()); + } + if (ownerOf(Candidate)) + continue; + + if (NeedsValue) { + auto ClassID = regalloc_detail::registerClassFor(Function, Reg); + if (!ClassID) + return std::unexpected(ClassID.error()); + auto Slot = spillSlot(Reg); + if (!Slot) + return std::unexpected(Slot.error()); + MachineIRBuilder Builder(Function, Target); + auto Positioned = Builder.setInsertPointBefore(Instruction); + if (!Positioned) + return std::unexpected(Positioned.error()); + auto Reload = TargetInfo.emitReload(Builder, Register::fromPhysical(Candidate), *ClassID, + *Slot, LaneMask::all()); + if (!Reload) + return std::unexpected(Reload.error()); + VirtRegMapEntry *Entry = Mapping.entry(Reg); + if (Entry != nullptr) + ++Entry->Spill.ReloadCount; + } + Locations.emplace(Reg, Location{Candidate, false}); + return Candidate; + } + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "FastAllocator cannot satisfy simultaneous register constraints"); + } + + [[nodiscard]] Expected installEntryLiveIns(MachineBasicBlock &Block) { + if (&Block != Function.firstBlock()) + return {}; + for (const PhysicalRegisterLiveIn &LiveIn : Function.registerInfo().liveIns()) { + if (!LiveIn.InitialVirtualRegister) + continue; + const Register Reg = *LiveIn.InitialVirtualRegister; + if (!Function.registerInfo().isKnownVirtualRegister(Reg)) + continue; + auto Candidates = regalloc_detail::allocationOrder(Function, Target, Reg); + if (!Candidates) + return std::unexpected(Candidates.error()); + if (std::ranges::find(*Candidates, LiveIn.PhysReg) == Candidates->end()) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "function live-in is outside its allocation order"); + } + if (ownerOf(LiveIn.PhysReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "overlapping function live-ins require the same physical register"); + } + Locations.emplace(Reg, Location{LiveIn.PhysReg, true}); + } + return {}; + } + + [[nodiscard]] Expected allocateInstruction(MachineInstr &Instruction, + MachineBasicBlock &Block) { + std::vector Fixed; + std::vector Masks; + std::map Registers; + std::vector DebugOperands; + for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) { + MachineOperand *Operand = Instruction.operandAt(Index); + if (const auto *Mask = Operand->getIf(); Mask != nullptr && Mask->Mask) + Masks.push_back(Mask->Mask.get()); + const Register *Reg = Operand->getIf(); + if (Reg == nullptr || Reg->isNoRegister()) + continue; + if (Reg->isPhysical()) { + const auto PhysicalValue = Reg->physicalRegister(); + if (!PhysicalValue) { + return makeUnexpected(ErrorCode::InternalError, + "physical register operand lacks a physical register value"); + } + Fixed.push_back(PhysicalValue.value()); + continue; + } + if (Operand->isDebugUse()) { + DebugOperands.push_back(Index); + continue; + } + auto [Position, Inserted] = Registers.try_emplace( + Reg->opaqueValue(), InstructionRegister{*Reg, {}, false, false, Index}); + if (!Inserted) + Position->second.FirstOperand = std::min(Position->second.FirstOperand, Index); + Position->second.Operands.push_back(Index); + Position->second.HasUse |= Operand->isUse(); + Position->second.HasDef |= Operand->isDef(); + } + std::ranges::sort(Fixed, {}, &PhysicalRegister::number); + Fixed.erase(std::unique(Fixed.begin(), Fixed.end()), Fixed.end()); + + std::unordered_set CurrentRegisters; + std::unordered_set DefinedRegisters; + for (const auto &[Key, Value] : Registers) { + (void)Key; + CurrentRegisters.insert(Value.VirtualReg); + if (Value.HasDef) + DefinedRegisters.insert(Value.VirtualReg); + } + for (const auto &[Reg, Value] : + std::vector>(Locations.begin(), Locations.end())) { + bool Clobbered = false; + for (const RegisterMask *Mask : Masks) + Clobbered |= Mask->clobbers(Value.PhysicalReg); + if (Clobbered) { + auto Evicted = evict(Reg, Instruction, Block, neededLater(Block, Reg)); + if (!Evicted) + return std::unexpected(Evicted.error()); + } + } + + std::vector Ordered; + Ordered.reserve(Registers.size()); + for (auto &[Key, Value] : Registers) { + (void)Key; + Ordered.push_back(&Value); + } + std::ranges::sort(Ordered, + [](const InstructionRegister *Left, const InstructionRegister *Right) { + if (Left->HasUse != Right->HasUse) + return Left->HasUse > Right->HasUse; + return Left->FirstOperand < Right->FirstOperand; + }); + + std::vector Locked; + for (InstructionRegister *Value : Ordered) { + auto Physical = ensureLocation(Value->VirtualReg, Value->HasUse, Instruction, Block, Fixed, + Locked, CurrentRegisters); + if (!Physical) + return std::unexpected(Physical.error()); + Locked.push_back(*Physical); + for (const std::size_t Index : Value->Operands) { + MachineOperand *Operand = Instruction.operandAt(Index); + PhysicalRegister Effective = *Physical; + if (Operand->subReg().value() != 0) { + const auto Sub = Target.registers().subRegister(*Physical, Operand->subReg()); + if (!Sub) + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "FastAllocator assignment lacks a required subregister"); + Effective = *Sub; + } + auto Set = Operand->setRegister(Register::fromPhysical(Effective)); + if (!Set) + return std::unexpected(Set.error()); + if (Operand->subReg().value() != 0) { + auto Cleared = Operand->setSubReg(SubRegIndex{}); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + } + if (Value->HasDef) + Locations[Value->VirtualReg].Dirty = true; + } + + for (const std::size_t Index : DebugOperands) { + MachineOperand *Operand = Instruction.operandAt(Index); + const Register *Reg = Operand->getIf(); + const auto Position = Reg == nullptr ? Locations.end() : Locations.find(*Reg); + Register Replacement; + if (Position != Locations.end()) + Replacement = Register::fromPhysical(Position->second.PhysicalReg); + auto Set = Operand->setRegister(Replacement); + if (!Set) + return std::unexpected(Set.error()); + if (Operand->subReg().value() != 0) { + auto Cleared = Operand->setSubReg(SubRegIndex{}); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + if (Replacement.isNoRegister()) { + RegisterOperandFlags Flags = Operand->registerFlags(); + Flags.set(RegisterOperandFlag::Undef); + auto Updated = Operand->setRegisterFlags(Flags); + if (!Updated) + return std::unexpected(Updated.error()); + } + } + + for (InstructionRegister *Value : Ordered) { + if (Value->HasUse) { + auto Position = RemainingUses.find(Value->VirtualReg); + if (Position != RemainingUses.end() && Position->second != 0) + --Position->second; + } + if (!neededLater(Block, Value->VirtualReg)) + Locations.erase(Value->VirtualReg); + } + for (const RegisterMask *Mask : Masks) { + for (auto Position = Locations.begin(); Position != Locations.end();) { + if (Mask->clobbers(Position->second.PhysicalReg) && + !DefinedRegisters.contains(Position->first)) + Position = Locations.erase(Position); + else + ++Position; + } + } + return {}; + } + + [[nodiscard]] Expected flushLiveOuts(MachineBasicBlock &Block) { + MachineInstr *Terminator = regalloc_detail::firstTerminator(Block, Target); + for (const auto &[Reg, Value] : + std::vector>(Locations.begin(), Locations.end())) { + if (!Value.Dirty || !liveOut(Block, Reg)) + continue; + if (Terminator != nullptr) { + for (const MachineOperand &Operand : Terminator->operands()) { + const Register *OperandReg = Operand.getIf(); + if (OperandReg != nullptr && *OperandReg == Reg && Operand.isDef()) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "FastAllocator cannot spill a terminator-defined live-out"); + } + } + } + auto Stored = emitSpillBefore(Reg, Value.PhysicalReg, Terminator, Block); + if (!Stored) + return std::unexpected(Stored.error()); + } + Locations.clear(); + return {}; + } + + [[nodiscard]] Expected allocateBlock(MachineBasicBlock &Block, bool IsEntry) { + (void)IsEntry; + Locations.clear(); + RemainingUses.clear(); + initializeBlockLiveIns(Block); + std::vector Instructions; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Instructions.push_back(Instruction); + std::unordered_set UsesInInstruction; + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf(); + if (Reg != nullptr && Reg->isVirtual() && Operand.isUse() && !Operand.isDebugUse()) + UsesInInstruction.insert(*Reg); + } + for (const Register Reg : UsesInInstruction) + ++RemainingUses[Reg]; + } + auto EntryValues = installEntryLiveIns(Block); + if (!EntryValues) + return std::unexpected(EntryValues.error()); + for (MachineInstr *Instruction : Instructions) { + auto Allocated = allocateInstruction(*Instruction, Block); + if (!Allocated) + return std::unexpected(Allocated.error()); + updateBlockLiveIns(Block, *Instruction); + } + auto Flushed = flushLiveOuts(Block); + BlockLiveIns.clear(); + return Flushed; + } + + MachineFunction &Function; + const TargetDescription &Target; + const TargetRegisterAllocationInfo &TargetInfo; + const LiveVariablesAnalysis::Result &Liveness; + VirtRegMap Mapping; + LiveRangeEdit Edit; + std::unordered_map Locations; + std::unordered_map RemainingUses; + std::vector BlockLiveIns; +}; + +} // namespace + +const MachinePassContract &FastAllocatorPass::contract() const noexcept { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "FastAllocator", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten, + MachineFunctionProperty::TracksLiveness}, + .Sets = {MachineFunctionProperty::NoVRegs}, + .Clears = {}, + .RequiredAnalyses = {MachineAnalysisManager::id()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +Expected FastAllocatorPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "FastAllocator requires target behavior"); + auto Required = regalloc_detail::requireAllocationProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + auto Trial = regalloc_detail::cloneForAllocation(Function, Target); + if (!Trial) + return std::unexpected(Trial.error()); + MachineAnalysisManager TrialAnalyses; + auto Registered = registerStage11MachineAnalyses(TrialAnalyses); + if (!Registered) + return std::unexpected(Registered.error()); + auto TrialLiveness = + TrialAnalyses.getResult(*Trial->ClonedFunction, Target); + if (!TrialLiveness) + return std::unexpected(TrialLiveness.error()); + FastAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, **TrialLiveness); + auto TrialRun = TrialAllocator.run(); + if (!TrialRun) + return std::unexpected(TrialRun.error()); + auto TrialVerification = + regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract()); + if (!TrialVerification) + return std::unexpected(TrialVerification.error()); + auto Liveness = Analyses.getResult(Function, Target); + if (!Liveness) + return std::unexpected(Liveness.error()); + FastAllocatorEngine Allocator(Function, Target, *Info, **Liveness); + auto Allocated = Allocator.run(); + if (!Allocated) { + return std::unexpected(regalloc_detail::withPrefix( + Allocated.error(), "FastAllocator diverged after a successful transaction preflight: ")); + } + return regalloc_detail::passResult(*Allocated); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/RegAllocInternal.h b/backend/lib/CodeGen/RegAllocInternal.h new file mode 100644 index 0000000..5d0f434 --- /dev/null +++ b/backend/lib/CodeGen/RegAllocInternal.h @@ -0,0 +1,236 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +// The private header has no stable include-root-relative guard name. +// NOLINTNEXTLINE(llvm-header-guard) +#ifndef RCC_LIB_CODEGEN_REGALLOCINTERNAL_H +#define RCC_LIB_CODEGEN_REGALLOCINTERNAL_H + +#include "rcc/CodeGen/InstructionDescriptor.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" +#include "rcc/CodeGen/RegAllocCommon.h" +#include "rcc/CodeGen/TargetDescription.h" +#include "rcc/CodeGen/TargetRegisterInfo.h" +#include "rcc/CodeGen/VirtRegMap.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc::regalloc_detail { + +struct AllocationRunResult final { + bool Changed = false; + bool ChangedInstructions = false; + bool ChangedFrame = false; +}; + +[[nodiscard]] inline Error withPrefix(const Error &Failure, std::string_view Prefix) { + std::string Message(Prefix); + Message.append(Failure.message()); + return Error(Failure.code(), std::move(Message)); +} + +[[nodiscard]] inline Expected virtualRegisterAt(std::size_t Index) { + auto Reg = Register::makeVirtual(Index); + if (!Reg) + return std::unexpected(Reg.error()); + return *Reg; +} + +[[nodiscard]] inline Expected registerClassFor(const MachineFunction &Function, + Register VirtualReg) { + auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg); + if (!Info) + return std::unexpected(Info.error()); + const auto ClassID = Info->get().RegClass; + if (!ClassID) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "virtual register has no register class after instruction selection"); + } + return ClassID.value(); +} + +[[nodiscard]] inline bool isUnavailablePhysicalRegister(const MachineFunction &Function, + const TargetRegisterInfo &Registers, + PhysicalRegister Reg) noexcept { + const PhysicalRegisterDesc *Description = Registers.physicalRegister(Reg); + return Description == nullptr || Description->IsConstant || Description->IsArtificial || + Description->IsReserved || Registers.isReservedRegister(Reg) || + Function.registerInfo().isReserved(Reg); +} + +[[nodiscard]] inline bool candidateSupportsSubRegisters(const MachineFunction &Function, + const TargetRegisterInfo &Registers, + Register VirtualReg, + PhysicalRegister Candidate) noexcept { + for (const MachineOperand &Operand : + const_cast(Function.registerInfo()).regOperands(VirtualReg)) { + if (Operand.subReg().value() != 0 && !Registers.subRegister(Candidate, Operand.subReg())) + return false; + } + return true; +} + +[[nodiscard]] inline Expected> +allocationOrder(const MachineFunction &Function, const TargetDescription &Target, + Register VirtualReg) { + auto ClassID = registerClassFor(Function, VirtualReg); + if (!ClassID) + return std::unexpected(ClassID.error()); + const RegisterClassDesc *Class = Target.registers().registerClass(*ClassID); + if (Class == nullptr || !Class->Allocatable || Class->AllocationOrder.empty()) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "virtual register class has no allocatable physical registers"); + } + + auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg); + if (!Info) + return std::unexpected(Info.error()); + std::vector Result; + Result.reserve(Class->AllocationOrder.size()); + for (const PhysicalRegister Hint : Info->get().AllocationHints) { + if (std::ranges::find(Class->AllocationOrder, Hint) != Class->AllocationOrder.end() && + std::ranges::find(Result, Hint) == Result.end()) + Result.push_back(Hint); + } + for (const PhysicalRegister Candidate : Class->AllocationOrder) { + if (std::ranges::find(Result, Candidate) == Result.end()) + Result.push_back(Candidate); + } + std::erase_if(Result, [&](PhysicalRegister Candidate) { + return isUnavailablePhysicalRegister(Function, Target.registers(), Candidate) || + !candidateSupportsSubRegisters(Function, Target.registers(), VirtualReg, Candidate); + }); + return Result; +} + +[[nodiscard]] inline MachineInstr *firstTerminator(MachineBasicBlock &Block, + const TargetDescription &Target) noexcept { + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) + return Instruction; + } + return nullptr; +} + +[[nodiscard]] inline bool hasTerminatorDefinition(const MachineFunction &Function, + const TargetDescription &Target, + Register VirtualReg) noexcept { + for (const MachineOperand &Operand : + const_cast(Function.registerInfo()).defOperands(VirtualReg)) { + const MachineInstr *Instruction = Operand.parent(); + const InstructionDescriptor *Descriptor = + Instruction == nullptr ? nullptr : Target.instructionDescriptor(Instruction->opcode()); + if (Descriptor != nullptr && Descriptor->Flags.has(InstructionFlag::Terminator)) + return true; + } + return false; +} + +[[nodiscard]] inline std::uint64_t allocationFingerprint(const MachineFunction &Function) noexcept { + std::uint64_t Hash = 1469598103934665603ULL; + auto Mix = [&Hash](std::uint64_t Value) { + Hash ^= Value; + Hash *= 1099511628211ULL; + }; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + Mix(Block->stableID().value()); + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Mix(Instruction->opcode().value()); + Mix(Instruction->stableID().value()); + for (const MachineOperand &Operand : Instruction->operands()) { + Mix(static_cast(Operand.kind())); + if (const Register *Reg = Operand.getIf()) + Mix(Reg->opaqueValue()); + } + } + } + return Hash; +} + +[[nodiscard]] inline Expected initializeMapping(MachineFunction &Function, + VirtRegMap &Mapping) { + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { + auto Reg = virtualRegisterAt(Index); + if (!Reg) + return std::unexpected(Reg.error()); + if (!Function.registerInfo().isKnownVirtualRegister(*Reg)) + continue; + auto Added = Mapping.add(*Reg); + if (!Added) + return std::unexpected(Added.error()); + } + return {}; +} + +[[nodiscard]] inline MachinePassResult passResult(const AllocationRunResult &Run) { + MachinePassResult Result; + Result.Changed = Run.Changed; + if (Run.Changed) { + Result.Changes.add(MachinePassChange::Registers); + Result.Changes.add(MachinePassChange::Operands); + } + if (Run.ChangedInstructions) + Result.Changes.add(MachinePassChange::Instructions); + if (Run.ChangedFrame) + Result.Changes.add(MachinePassChange::Frame); + Result.Preserved = PreservedAnalyses::none(); + return Result; +} + +[[nodiscard]] inline Expected +requireAllocationProperties(const MachineFunction &Function, const MachinePassContract &Contract) { + const MachineFunctionProperties Missing = Contract.Requires.missingFrom(Function.properties()); + if (!Missing.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + Contract.Name + " requires properties: " + Missing.toString()); + } + return {}; +} + +[[nodiscard]] inline Expected verifyAllocationTrial(MachineFunction &Function, + const TargetDescription &Target, + const MachinePassContract &Contract) { + auto Transition = + Function.properties().applyTransition(Contract.Requires, Contract.Sets, Contract.Clears); + if (!Transition) + return std::unexpected(Transition.error()); + return MachineVerifier::verify(Function, Target, + MachineVerifierOptions{.Mode = MachineVerifierMode::Generic, + .Stage = Contract.VerificationStage, + .VerifyProperties = true}); +} + +[[nodiscard]] inline Expected +cloneForAllocation(const MachineFunction &Function, const TargetDescription &Target) { + return cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); +} + +[[nodiscard]] bool +intervalsOverlapOnPhysicalRegisters(const LiveInterval &Left, PhysicalRegister LeftReg, + const LiveInterval &Right, PhysicalRegister RightReg, + const TargetRegisterInfo &Registers) noexcept; + +} // namespace rcc::regalloc_detail + +#endif // RCC_LIB_CODEGEN_REGALLOCINTERNAL_H diff --git a/backend/lib/CodeGen/RegAllocPBQP.cpp b/backend/lib/CodeGen/RegAllocPBQP.cpp new file mode 100644 index 0000000..5e56728 --- /dev/null +++ b/backend/lib/CodeGen/RegAllocPBQP.cpp @@ -0,0 +1,281 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/RegAllocPBQP.h" + +#include "RegAllocBase.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/LiveRegMatrix.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" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +struct PBQPAllocationNode final { + Register VirtualReg; + pbqp::NodeID Node; + std::vector> Options; +}; + +[[nodiscard]] std::set> +copyRelatedRegisters(const MachineFunction &Function) { + std::set> Result; + for (const MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (const MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + if (Instruction->opcode() != opcode(GenericOpcode::COPY) || Instruction->operandCount() < 2) + continue; + const Register *Destination = Instruction->operands()[0].getIf(); + const Register *Source = Instruction->operands()[1].getIf(); + if (Destination == nullptr || Source == nullptr || !Destination->isVirtual() || + !Source->isVirtual() || *Destination == *Source) + continue; + std::uint32_t Left = Destination->opaqueValue(); + std::uint32_t Right = Source->opaqueValue(); + if (Right < Left) + std::swap(Left, Right); + Result.emplace(Left, Right); + } + } + return Result; +} + +[[nodiscard]] pbqp::Cost boundedCost(std::uint64_t Value) noexcept { + const std::uint64_t Limit = static_cast(pbqp::InfiniteCost - 1); + return static_cast(std::min(Value, Limit)); +} + +class PBQPAllocatorEngine final : public RegAllocBase { +public: + PBQPAllocatorEngine(MachineFunction &Function, const TargetDescription &Target, + const TargetRegisterAllocationInfo &TargetInfo, + MachineAnalysisManager &Analyses, RegisterAllocationOptions Options) + : RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {} + +private: + [[nodiscard]] Expected + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override { + LiveRegMatrix FixedMatrix(Function, Target, Intervals); + pbqp::Graph Problem; + std::vector Nodes; + for (const LiveInterval *Interval : orderedAllocationIntervals(Intervals, Function)) { + const Register VirtualReg = Interval->Reg; + const bool TerminatorDefined = + regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg); + if (TerminatorDefined) { + auto Marked = Mapping.setSpillable(VirtualReg, false); + if (!Marked) + return std::unexpected(Marked.error()); + } + auto ClassID = regalloc_detail::registerClassFor(Function, VirtualReg); + if (!ClassID) + return std::unexpected(ClassID.error()); + auto Candidates = regalloc_detail::allocationOrder(Function, Target, VirtualReg); + if (!Candidates) + return std::unexpected(Candidates.error()); + std::erase_if(*Candidates, [&](PhysicalRegister Candidate) { + return FixedMatrix.checkInterference(VirtualReg, Candidate).Kind != + RegisterInterferenceKind::Free; + }); + + std::vector> NodeOptions; + NodeOptions.reserve(Candidates->size() + 1U); + NodeOptions.push_back(std::nullopt); + for (const PhysicalRegister Candidate : *Candidates) + NodeOptions.push_back(Candidate); + pbqp::CostVector Costs(NodeOptions.size(), 0); + if (!Mapping.isSpillable(VirtualReg)) { + Costs[0] = pbqp::InfiniteCost; + } else { + const std::uint64_t TargetSpillCost = TargetInfo.spillCost(Function, *Interval, *ClassID); + const std::uint64_t Weight = std::max(1, Interval->SpillWeight); + const std::uint64_t Scaled = + TargetSpillCost > std::numeric_limits::max() / Weight + ? std::numeric_limits::max() + : TargetSpillCost * Weight; + const std::uint64_t Adjusted = + Scaled == std::numeric_limits::max() ? Scaled : Scaled + 1U; + Costs[0] = boundedCost(Adjusted); + } + auto Info = Function.registerInfo().virtualRegisterInfo(VirtualReg); + if (!Info) + return std::unexpected(Info.error()); + for (std::size_t Index = 1; Index < NodeOptions.size(); ++Index) { + const auto CandidateOption = NodeOptions[Index]; + if (!CandidateOption) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP allocation node has an unexpected spill option"); + } + const PhysicalRegister Candidate = CandidateOption.value(); + std::uint64_t Cost = + TargetInfo.physicalRegisterCost(Function, VirtualReg, Candidate, *ClassID, true); + const auto Hint = std::ranges::find(Info->get().AllocationHints, Candidate); + const std::uint64_t HintCost = + Hint == Info->get().AllocationHints.end() + ? 2U + : static_cast(Hint - Info->get().AllocationHints.begin()); + Cost = Cost > std::numeric_limits::max() - HintCost + ? std::numeric_limits::max() + : Cost + HintCost; + Costs[Index] = boundedCost(Cost); + } + auto NodeID = Problem.addNode(std::move(Costs), VirtualReg.opaqueValue()); + if (!NodeID) + return std::unexpected(NodeID.error()); + Nodes.push_back(PBQPAllocationNode{VirtualReg, *NodeID, std::move(NodeOptions)}); + } + + const auto CopyPairs = copyRelatedRegisters(Function); + for (std::size_t LeftIndex = 0; LeftIndex < Nodes.size(); ++LeftIndex) { + const PBQPAllocationNode &Left = Nodes[LeftIndex]; + const LiveInterval *LeftInterval = Intervals.interval(Left.VirtualReg); + for (std::size_t RightIndex = LeftIndex + 1U; RightIndex < Nodes.size(); ++RightIndex) { + const PBQPAllocationNode &Right = Nodes[RightIndex]; + const LiveInterval *RightInterval = Intervals.interval(Right.VirtualReg); + if (LeftInterval == nullptr || RightInterval == nullptr) + continue; + std::uint32_t LeftKey = Left.VirtualReg.opaqueValue(); + std::uint32_t RightKey = Right.VirtualReg.opaqueValue(); + if (RightKey < LeftKey) + std::swap(LeftKey, RightKey); + const bool CopyRelated = + Options.EnableCopyCoalescing && CopyPairs.contains({LeftKey, RightKey}); + pbqp::CostMatrix Costs(Left.Options.size(), Right.Options.size(), 0); + bool HasCost = false; + for (std::size_t LeftOption = 1; LeftOption < Left.Options.size(); ++LeftOption) { + for (std::size_t RightOption = 1; RightOption < Right.Options.size(); ++RightOption) { + const auto LeftRegister = Left.Options[LeftOption]; + const auto RightRegister = Right.Options[RightOption]; + if (!LeftRegister || !RightRegister) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP edge has an unexpected spill option"); + } + const PhysicalRegister LeftReg = LeftRegister.value(); + const PhysicalRegister RightReg = RightRegister.value(); + if (regalloc_detail::intervalsOverlapOnPhysicalRegisters( + *LeftInterval, LeftReg, *RightInterval, RightReg, Target.registers())) { + Costs.at(LeftOption, RightOption) = pbqp::InfiniteCost; + HasCost = true; + } else if (CopyRelated && LeftReg == RightReg) { + Costs.at(LeftOption, RightOption) = -1; + HasCost = true; + } + } + } + if (!HasCost) + continue; + const std::uint64_t StableKey = + (static_cast(Left.VirtualReg.opaqueValue()) << 32U) | + Right.VirtualReg.opaqueValue(); + auto Edge = Problem.addEdge(Left.Node, Right.Node, std::move(Costs), StableKey); + if (!Edge) + return std::unexpected(Edge.error()); + } + } + + pbqp::DeterministicSolver Solver; + auto Solution = Solver.solve(Problem); + if (!Solution) + return std::unexpected(Solution.error()); + + LiveRegMatrix AssignedMatrix(Function, Target, Intervals); + AllocationRoundResult Result; + for (const PBQPAllocationNode &Node : Nodes) { + const auto Selection = Solution->selection(Node.Node); + if (!Selection) + return makeUnexpected(ErrorCode::InternalError, + "PBQP solver returned an invalid selection"); + const std::size_t SelectedOption = Selection.value(); + if (SelectedOption >= Node.Options.size()) { + return makeUnexpected(ErrorCode::InternalError, + "PBQP solver selected an out-of-range option"); + } + const auto AssignedOption = Node.Options[SelectedOption]; + if (!AssignedOption) { + Result.Spilled.push_back(Node.VirtualReg); + continue; + } + const PhysicalRegister Assigned = AssignedOption.value(); + auto MatrixAssignment = AssignedMatrix.assign(Node.VirtualReg, Assigned); + if (!MatrixAssignment) + return makeUnexpected(ErrorCode::InternalError, + "PBQP solution violates its encoded interference constraints"); + auto MapAssignment = Mapping.assign(Node.VirtualReg, Assigned); + if (!MapAssignment) + return std::unexpected(MapAssignment.error()); + } + return Result; + } +}; + +[[nodiscard]] const MachinePassContract &pbqpContract() { + static const MachinePassContract Contract = [] { + MachinePassContract Value{ + .Name = "PBQPAllocator", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten, + MachineFunctionProperty::TracksLiveness}, + .Sets = {MachineFunctionProperty::NoVRegs}, + .Clears = {}, + .RequiredAnalyses = {MachineAnalysisManager::id()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +} // namespace + +const MachinePassContract &PBQPAllocatorPass::contract() const noexcept { + return pbqpContract(); +} + +Expected PBQPAllocatorPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &Analyses) { + if (Info == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "PBQPAllocator requires target behavior"); + auto Required = regalloc_detail::requireAllocationProperties(Function, contract()); + if (!Required) + return std::unexpected(Required.error()); + auto Trial = regalloc_detail::cloneForAllocation(Function, Target); + if (!Trial) + return std::unexpected(Trial.error()); + MachineAnalysisManager TrialAnalyses; + auto Registered = registerStage11MachineAnalyses(TrialAnalyses); + if (!Registered) + return std::unexpected(Registered.error()); + PBQPAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses, Options); + auto TrialRun = TrialAllocator.run(); + if (!TrialRun) + return std::unexpected(TrialRun.error()); + auto TrialVerification = + regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract()); + if (!TrialVerification) + return std::unexpected(TrialVerification.error()); + PBQPAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options); + auto Allocated = Allocator.run(); + if (!Allocated) { + return std::unexpected(regalloc_detail::withPrefix( + Allocated.error(), "PBQPAllocator diverged after a successful transaction preflight: ")); + } + return regalloc_detail::passResult(*Allocated); +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TargetMIRTextInfo.cpp b/backend/lib/CodeGen/TargetMIRTextInfo.cpp index 65e3c65..5d54ea6 100644 --- a/backend/lib/CodeGen/TargetMIRTextInfo.cpp +++ b/backend/lib/CodeGen/TargetMIRTextInfo.cpp @@ -509,8 +509,7 @@ TargetMIRTextInfo::printFunctionState(const TargetFunctionState &State) const { return Node; } -Expected -TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const { +Expected TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const { if (Description.ParseTargetConstant == nullptr) { return makeUnexpected(ErrorCode::Unsupported, "target does not define a target constant MIR schema"); @@ -524,8 +523,7 @@ TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const { return Constant; } -Expected -TargetMIRTextInfo::printTargetConstant(const TargetConstant &Constant) const { +Expected TargetMIRTextInfo::printTargetConstant(const TargetConstant &Constant) const { if (Description.PrintTargetConstant == nullptr) { return makeUnexpected(ErrorCode::Unsupported, "target does not define a target constant MIR schema"); diff --git a/backend/lib/CodeGen/VirtRegMap.cpp b/backend/lib/CodeGen/VirtRegMap.cpp new file mode 100644 index 0000000..624a931 --- /dev/null +++ b/backend/lib/CodeGen/VirtRegMap.cpp @@ -0,0 +1,301 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/VirtRegMap.h" + +#include "RegAllocInternal.h" +#include "rcc/CodeGen/LiveRegMatrix.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" + +#include +#include +#include +#include +#include +#include + +namespace rcc { + +Expected VirtRegMap::add(Register VirtualReg, bool Spillable, + std::optional SplitParent, + std::optional Origin) { + if (!VirtualReg.isVirtual() || !Function->registerInfo().isKnownVirtualRegister(VirtualReg)) + return makeUnexpected(ErrorCode::InvalidArgument, + "VirtRegMap requires a known virtual register"); + if (SplitParent && !SplitParent->isVirtual()) + return makeUnexpected(ErrorCode::InvalidArgument, "split parent must be a virtual register"); + if (Origin && !Origin->isVirtual()) + return makeUnexpected(ErrorCode::InvalidArgument, "split origin must be a virtual register"); + auto [Position, Inserted] = + Entries.try_emplace(VirtualReg, VirtRegMapEntry{VirtualReg, + VirtRegAllocationState::Unassigned, + std::nullopt, + SplitParent, + Origin, + Spillable, + {}}); + if (!Inserted) { + Position->second.Spillable = Spillable; + if (SplitParent) + Position->second.SplitParent = SplitParent; + if (Origin) + Position->second.Origin = Origin; + } + return {}; +} + +Expected VirtRegMap::assign(Register VirtualReg, PhysicalRegister PhysicalReg) { + VirtRegMapEntry *Value = entry(VirtualReg); + if (Value == nullptr || !PhysicalReg.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap assignment is invalid"); + Value->PhysicalReg = PhysicalReg; + Value->State = VirtRegAllocationState::Assigned; + return {}; +} + +Expected VirtRegMap::assignStackSlot(Register VirtualReg, FrameIndex StackSlot, + LaneMask Lanes) { + VirtRegMapEntry *Value = entry(VirtualReg); + if (Value == nullptr || Function->frameInfo().object(StackSlot) == nullptr || Lanes.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap spill assignment is invalid"); + Value->PhysicalReg.reset(); + Value->State = VirtRegAllocationState::Spilled; + Value->Spill.StackSlot = StackSlot; + Value->Spill.Lanes = Lanes; + return {}; +} + +Expected VirtRegMap::markSplit(Register VirtualReg, Register Parent, Register Origin) { + VirtRegMapEntry *Value = entry(VirtualReg); + if (Value == nullptr || !Parent.isVirtual() || !Origin.isVirtual() || Parent == VirtualReg || + Origin == VirtualReg || !Function->registerInfo().isKnownVirtualRegister(Parent) || + !Function->registerInfo().isKnownVirtualRegister(Origin)) + return makeUnexpected(ErrorCode::InvalidArgument, "VirtRegMap split relationship is invalid"); + Value->State = VirtRegAllocationState::Split; + Value->SplitParent = Parent; + Value->Origin = Origin; + return {}; +} + +Expected VirtRegMap::setSpillable(Register VirtualReg, bool Spillable) { + VirtRegMapEntry *Value = entry(VirtualReg); + if (Value == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, "unknown virtual register in VirtRegMap"); + Value->Spillable = Spillable; + return {}; +} + +VirtRegMapEntry *VirtRegMap::entry(Register VirtualReg) noexcept { + const auto Position = Entries.find(VirtualReg); + return Position == Entries.end() ? nullptr : &Position->second; +} + +const VirtRegMapEntry *VirtRegMap::entry(Register VirtualReg) const noexcept { + const auto Position = Entries.find(VirtualReg); + return Position == Entries.end() ? nullptr : &Position->second; +} + +std::optional VirtRegMap::physicalRegister(Register VirtualReg) const noexcept { + const VirtRegMapEntry *Value = entry(VirtualReg); + return Value == nullptr ? std::nullopt : Value->PhysicalReg; +} + +std::optional VirtRegMap::stackSlot(Register VirtualReg) const noexcept { + const VirtRegMapEntry *Value = entry(VirtualReg); + return Value == nullptr ? std::nullopt : Value->Spill.StackSlot; +} + +bool VirtRegMap::isSpillable(Register VirtualReg) const noexcept { + const VirtRegMapEntry *Value = entry(VirtualReg); + return Value != nullptr && Value->Spillable; +} + +std::vector VirtRegMap::orderedEntries() const { + std::vector Result; + Result.reserve(Entries.size()); + for (const auto &[Reg, Value] : Entries) { + (void)Reg; + Result.push_back(&Value); + } + std::ranges::sort(Result, [](const VirtRegMapEntry *Left, const VirtRegMapEntry *Right) { + return Left->VirtualReg.opaqueValue() < Right->VirtualReg.opaqueValue(); + }); + return Result; +} + +Expected VirtRegMap::verify() const { + if (Function == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has no MachineFunction"); + for (const VirtRegMapEntry *Value : orderedEntries()) { + if (Value == nullptr || !Value->VirtualReg.isVirtual() || + !Function->registerInfo().isKnownVirtualRegister(Value->VirtualReg)) + return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap contains an invalid entry"); + if (Value->State == VirtRegAllocationState::Assigned && + (!Value->PhysicalReg || !Value->PhysicalReg->isValid())) + return makeUnexpected(ErrorCode::VerificationError, + "assigned VirtRegMap entry has no register"); + if (Value->State == VirtRegAllocationState::Spilled && !Value->Spill.StackSlot) + return makeUnexpected(ErrorCode::VerificationError, + "spilled VirtRegMap entry has no stack slot"); + if (Value->Spill.StackSlot && Value->Spill.Lanes.empty()) + return makeUnexpected(ErrorCode::VerificationError, + "VirtRegMap spill metadata has an empty lane mask"); + if (Value->SplitParent && + (!Value->SplitParent->isVirtual() || *Value->SplitParent == Value->VirtualReg || + !Function->registerInfo().isKnownVirtualRegister(*Value->SplitParent))) + return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has an invalid split parent"); + if (Value->Origin && (!Value->Origin->isVirtual() || *Value->Origin == Value->VirtualReg || + !Function->registerInfo().isKnownVirtualRegister(*Value->Origin))) + return makeUnexpected(ErrorCode::VerificationError, "VirtRegMap has an invalid split origin"); + if (Value->State == VirtRegAllocationState::Split && (!Value->SplitParent || !Value->Origin)) + return makeUnexpected(ErrorCode::VerificationError, + "split VirtRegMap entry lacks parent or origin metadata"); + } + return {}; +} + +Expected rewriteVirtualRegisters(MachineFunction &Function, const TargetDescription &Target, + const VirtRegMap &Mapping) { + if (&Mapping.function() != &Function) + return makeUnexpected(ErrorCode::InvalidArgument, + "VirtRegMap belongs to a different MachineFunction"); + auto MappingVerification = Mapping.verify(); + if (!MappingVerification) + return std::unexpected(MappingVerification.error()); + + MachineAnalysisManager ValidationAnalyses; + auto Registered = registerStage11MachineAnalyses(ValidationAnalyses); + if (!Registered) + return std::unexpected(Registered.error()); + auto Intervals = ValidationAnalyses.getResult(Function, Target); + if (!Intervals) + return std::unexpected(Intervals.error()); + LiveRegMatrix ValidationMatrix(Function, Target, **Intervals); + for (const VirtRegMapEntry *Entry : Mapping.orderedEntries()) { + if (Entry == nullptr || !Entry->PhysicalReg) + continue; + auto ClassID = regalloc_detail::registerClassFor(Function, Entry->VirtualReg); + if (!ClassID) + return std::unexpected(ClassID.error()); + if (!Target.registers().registerClassContains(*ClassID, *Entry->PhysicalReg)) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "VirtRegMap physical register is outside the virtual register class"); + } + const LiveInterval *Interval = (*Intervals)->interval(Entry->VirtualReg); + if (Interval == nullptr || Interval->MainRange.empty()) + continue; + auto Assigned = ValidationMatrix.assign(Entry->VirtualReg, *Entry->PhysicalReg); + if (!Assigned) + return std::unexpected(Assigned.error()); + } + + struct Rewrite final { + MachineOperand *Operand = nullptr; + Register NewRegister; + }; + std::vector Rewrites; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + for (std::size_t Index = 0; Index < Instruction->operandCount(); ++Index) { + MachineOperand *Operand = Instruction->operandAt(Index); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + continue; + const auto Assigned = Mapping.physicalRegister(*Reg); + if (!Assigned) { + if (Operand->isDebugUse()) { + Rewrites.push_back({Operand, Register{}}); + continue; + } + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "physical rewrite found an unassigned virtual register " + + Reg->toString()); + } + PhysicalRegister Effective = *Assigned; + if (Operand->subReg().value() != 0) { + const auto Sub = Target.registers().subRegister(*Assigned, Operand->subReg()); + if (!Sub) { + return makeUnexpected(ErrorCode::RegisterAllocationFailed, + "physical assignment does not support a required subregister"); + } + Effective = *Sub; + } + Rewrites.push_back({Operand, Register::fromPhysical(Effective)}); + } + } + } + + for (const Rewrite &Plan : Rewrites) { + auto SetRegister = Plan.Operand->setRegister(Plan.NewRegister); + if (!SetRegister) + return std::unexpected(SetRegister.error()); + if (Plan.Operand->subReg().value() != 0) { + auto Cleared = Plan.Operand->setSubReg(SubRegIndex{}); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + if (Plan.NewRegister.isNoRegister()) { + RegisterOperandFlags Flags = Plan.Operand->registerFlags(); + Flags.set(RegisterOperandFlag::Undef); + auto Updated = Plan.Operand->setRegisterFlags(Flags); + if (!Updated) + return std::unexpected(Updated.error()); + } + } + + Function.registerInfo().clearLiveInVirtualRegisters(); + for (std::size_t Index = 0; Index < Function.registerInfo().virtualRegisters().size(); ++Index) { + auto Reg = regalloc_detail::virtualRegisterAt(Index); + if (!Reg) + return std::unexpected(Reg.error()); + if (!Function.registerInfo().isKnownVirtualRegister(*Reg)) + continue; + auto Erased = Function.registerInfo().eraseVirtualRegister(*Reg); + if (!Erased) + return std::unexpected(Erased.error()); + } + auto Liveness = rebuildMachineLiveness(Function, Target); + if (!Liveness) + return std::unexpected(Liveness.error()); + return !Rewrites.empty(); +} + +const MachinePassContract &VirtualRegisterRewritePass::contract() const noexcept { + static const MachinePassContract Contract{ + .Name = "VirtualRegisterRewrite", + .Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs, + MachineFunctionProperty::TiedOpsRewritten}, + .Sets = {MachineFunctionProperty::NoVRegs}, + .Clears = {}, + .RequiredAnalyses = {}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + return Contract; +} + +Expected VirtualRegisterRewritePass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineAnalysisManager &) { + if (Mapping == nullptr) + return makeUnexpected(ErrorCode::InvalidArgument, + "VirtualRegisterRewrite requires a VirtRegMap"); + auto Rewritten = rewriteVirtualRegisters(Function, Target, *Mapping); + if (!Rewritten) + return std::unexpected(Rewritten.error()); + MachinePassResult Result; + Result.Changed = *Rewritten; + if (Result.Changed) { + Result.Changes.add(MachinePassChange::Registers); + Result.Changes.add(MachinePassChange::Operands); + } + Result.Preserved = PreservedAnalyses::none(); + return Result; +} + +} // namespace rcc -- cgit v1.2.3