diff options
Diffstat (limited to 'backend/lib')
35 files changed, 2955 insertions, 154 deletions
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> -vectorShape(const GenericConstantType &Type) noexcept { +[[nodiscard]] std::optional<VectorShape> 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<std::uint64_t> @@ -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<void> 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<std::uint8_t>(GenericConstantExpressionFlag::NoUnsignedWrap)) | + (std::uint8_t{1} << static_cast<std::uint8_t>( + GenericConstantExpressionFlag::NoUnsignedWrap)) | (std::uint8_t{1} << static_cast<std::uint8_t>(GenericConstantExpressionFlag::NoSignedWrap)); const std::uint8_t GEPFlags = (std::uint8_t{1} << static_cast<std::uint8_t>(GenericConstantExpressionFlag::InBounds)) | - (std::uint8_t{1} << - static_cast<std::uint8_t>(GenericConstantExpressionFlag::NoUnsignedSignedWrap)) | - (std::uint8_t{1} << - static_cast<std::uint8_t>(GenericConstantExpressionFlag::GEPNoUnsignedWrap)); + (std::uint8_t{1} << static_cast<std::uint8_t>( + GenericConstantExpressionFlag::NoUnsignedSignedWrap)) | + (std::uint8_t{1} << static_cast<std::uint8_t>( + 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> GenericConstantType::array(std::uint64_t Count, return Type; } -Expected<GenericConstantType> GenericConstantType::vector(std::uint64_t Count, - GenericConstantType Element, - bool IsScalable) { +Expected<GenericConstantType> +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> GenericConstantType::named(std::string TypeName, - bool IsNumericName) { +Expected<GenericConstantType> 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 <cstddef> +#include <optional> +#include <ranges> +#include <string> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] Expected<void> 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<std::optional<std::vector<Register>>> Spiller::tryRematerialize(Register VirtualReg) { + if (!EnableRematerialization) + return std::optional<std::vector<Register>>{}; + const MachineOperand *Definition = Function->registerInfo().getUniqueVRegDef(VirtualReg); + const MachineInstr *DefiningInstruction = Definition == nullptr ? nullptr : Definition->parent(); + if (DefiningInstruction == nullptr || DefiningInstruction->parent() == nullptr) + return std::optional<std::vector<Register>>{}; + auto Accepted = + TargetInfo->isRematerializable(*DefiningInstruction, VirtualReg, *Function, *Target); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) + return std::optional<std::vector<Register>>{}; + + struct UseSite final { + MachineInstr *Instruction = nullptr; + std::vector<std::size_t> OperandIndices; + }; + std::vector<UseSite> 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<Register>(); + 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<std::vector<Register>>{}; + if (!Site.OperandIndices.empty()) + Sites.push_back(std::move(Site)); + } + } + if (Sites.empty()) + return std::optional<std::vector<Register>>{}; + + std::vector<Register> 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<MachineBasicBlock *>(DefiningInstruction->parent()); + auto Removed = Block->removeInstruction(*const_cast<MachineInstr *>(DefiningInstruction)); + if (!Removed) + return std::unexpected(Removed.error()); + } + return std::optional<std::vector<Register>>(std::move(NewRegisters)); +} + +Expected<std::vector<Register>> 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<std::size_t> OperandIndices; + std::vector<std::size_t> DebugIndices; + bool HasUse = false; + bool HasDef = false; + }; + std::vector<SpillSite> 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<Register>(); + 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<Register> 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<void> 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<void> 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<std::vector<Register>> 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<Register> LiveRangeEdit::createFrom(Register Parent, bool Spillable, + std::optional<Register> Origin) { + auto ParentInfo = Function->registerInfo().virtualRegisterInfo(Parent); + if (!ParentInfo) + return std::unexpected(ParentInfo.error()); + const VirtualRegisterInfo &Source = ParentInfo->get(); + Expected<Register> 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<Register> { + 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<FrameIndex> 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<FrameIndex> 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<void> 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 <algorithm> +#include <bit> +#include <cstdint> +#include <optional> +#include <ranges> +#include <span> +#include <tuple> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] std::optional<LaneMask> 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<const LiveSubRange>{} + : std::span<const LiveSubRange>(Left.SubRanges); + const auto RightRanges = Right.SubRanges.empty() + ? std::span<const LiveSubRange>{} + : std::span<const LiveSubRange>(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<RegisterInterference> +LiveRegMatrix::collectInterferences(Register VirtualReg, PhysicalRegister PhysicalReg) const { + std::vector<RegisterInterference> 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<Register>(); + 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<RegisterInterference> Values = collectInterferences(VirtualReg, PhysicalReg); + if (Values.empty()) + return {}; + return Values.front(); +} + +Expected<void> 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<void> 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<PhysicalRegister> 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 <cstddef> #include <cstdint> #include <limits> +#include <map> #include <optional> #include <ranges> #include <span> @@ -296,7 +297,7 @@ Expected<MachineLoopAnalysis::Result> MachineLoopAnalysis::run(MachineFunction & Result ResultValue; std::vector<MachineBasicBlock *> Blocks = linkedBlocks(Function); const auto Order = blockOrder(Blocks); - std::unordered_map<MachineBasicBlock *, std::unordered_set<MachineBasicBlock *>> LoopBlocks; + std::map<MachineBasicBlock *, std::unordered_set<MachineBasicBlock *>> LoopBlocks; std::unordered_map<MachineBasicBlock *, std::vector<MachineBasicBlock *>> 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<void> 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<void> 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<JumpTableIndex> MachineJumpTableInfo::reserveTable() { return Index; } -Expected<void> -MachineJumpTableInfo::defineReservedTable(JumpTableIndex Index, - MachineJumpTableDesc Description) { +Expected<void> 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 <memory> #include <optional> #include <ranges> +#include <set> #include <string> #include <string_view> #include <thread> @@ -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<AnalysisID> Invalid; + std::set<AnalysisID> Invalid; for (auto &[ID, Entry] : FunctionPosition->second) { if (Preserved.preserves(ID)) continue; @@ -406,8 +408,9 @@ Expected<void> 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<AnalysisID> Invalid; + std::set<AnalysisID> Invalid; for (auto &[ID, Entry] : UnitPosition->second) { if (Preserved.preserves(ID)) continue; @@ -1238,10 +1241,10 @@ Expected<void> 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<void> MachineRegisterInfo::addLiveIn(PhysicalRegister PhysReg, return {}; } +void MachineRegisterInfo::clearLiveInVirtualRegisters() noexcept { + for (PhysicalRegisterLiveIn &LiveIn : LiveIns) + LiveIn.InitialVirtualRegister.reset(); +} + Expected<void> 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 <algorithm> +#include <cstdint> +#include <unordered_set> +#include <utility> + +namespace rcc { + +std::vector<const LiveInterval *> +orderedAllocationIntervals(const LiveIntervalsAnalysis::Result &Intervals, + const MachineFunction &Function) { + std::vector<const LiveInterval *> 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<regalloc_detail::AllocationRunResult> 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<std::uint64_t> 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<LiveIntervalsAnalysis>(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 <vector> + +namespace rcc { + +struct AllocationRoundResult final { + std::vector<Register> Spilled; +}; + +class RegAllocBase { +public: + virtual ~RegAllocBase() = default; + + [[nodiscard]] Expected<regalloc_detail::AllocationRunResult> 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<AllocationRoundResult> + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) = 0; + + MachineFunction &Function; + const TargetDescription &Target; + const TargetRegisterAllocationInfo &TargetInfo; + MachineAnalysisManager &Analyses; + RegisterAllocationOptions Options; +}; + +[[nodiscard]] std::vector<const LiveInterval *> +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 <algorithm> +#include <memory> +#include <ranges> + +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<AllocationRoundResult> + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override { + LiveRegMatrix Matrix(Function, Target, Intervals); + AllocationRoundResult Result; + std::vector<const LiveInterval *> 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<LiveIntervalsAnalysis>()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +} // namespace + +const MachinePassContract &BasicAllocatorPass::contract() const noexcept { + return basicContract(); +} + +Expected<MachinePassResult> 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<MachineFunctionPass> +createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info, + RegisterAllocationOptions Options) { + return std::make_unique<BasicAllocatorPass>(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<MachinePassResult> 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 <algorithm> +#include <cstddef> +#include <map> +#include <optional> +#include <ranges> +#include <span> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +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<regalloc_detail::AllocationRunResult> 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<std::size_t> 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<Register> 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<Register>(); + 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<PhysicalRegister> Defined; + std::vector<const RegisterMask *> Masks; + for (const MachineOperand &Operand : Instruction.operands()) { + if (const Register *Reg = Operand.getIf<Register>(); Reg != nullptr && Reg->isPhysical()) { + const auto PhysicalValue = Reg->physicalRegister(); + if (Operand.isDef() && PhysicalValue) + Defined.push_back(PhysicalValue.value()); + } + if (const auto *Mask = Operand.getIf<RegisterMaskOperand>(); 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<Register>(); + 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<const PhysicalRegister> Values) const noexcept { + return std::ranges::any_of(Values, [&](PhysicalRegister Value) { + return Target.registers().regsOverlap(Candidate, Value); + }); + } + + [[nodiscard]] Expected<FrameIndex> 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<void> 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<void> 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<void> 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<PhysicalRegister> + ensureLocation(Register Reg, bool NeedsValue, MachineInstr &Instruction, MachineBasicBlock &Block, + std::span<const PhysicalRegister> Fixed, std::span<const PhysicalRegister> Locked, + const std::unordered_set<Register> &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<void> 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<void> allocateInstruction(MachineInstr &Instruction, + MachineBasicBlock &Block) { + std::vector<PhysicalRegister> Fixed; + std::vector<const RegisterMask *> Masks; + std::map<std::uint32_t, InstructionRegister> Registers; + std::vector<std::size_t> DebugOperands; + for (std::size_t Index = 0; Index < Instruction.operandCount(); ++Index) { + MachineOperand *Operand = Instruction.operandAt(Index); + if (const auto *Mask = Operand->getIf<RegisterMaskOperand>(); Mask != nullptr && Mask->Mask) + Masks.push_back(Mask->Mask.get()); + const Register *Reg = Operand->getIf<Register>(); + 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<Register> CurrentRegisters; + std::unordered_set<Register> 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<std::pair<Register, Location>>(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<InstructionRegister *> 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<PhysicalRegister> 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<Register>(); + 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<void> flushLiveOuts(MachineBasicBlock &Block) { + MachineInstr *Terminator = regalloc_detail::firstTerminator(Block, Target); + for (const auto &[Reg, Value] : + std::vector<std::pair<Register, Location>>(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<Register>(); + 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<void> allocateBlock(MachineBasicBlock &Block, bool IsEntry) { + (void)IsEntry; + Locations.clear(); + RemainingUses.clear(); + initializeBlockLiveIns(Block); + std::vector<MachineInstr *> Instructions; + for (MachineInstr *Instruction = Block.firstInstruction(); Instruction != nullptr; + Instruction = Instruction->next()) { + Instructions.push_back(Instruction); + std::unordered_set<Register> UsesInInstruction; + for (const MachineOperand &Operand : Instruction->operands()) { + const Register *Reg = Operand.getIf<Register>(); + 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<Register, Location> Locations; + std::unordered_map<Register, std::size_t> RemainingUses; + std::vector<BlockLiveInState> 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<LiveVariablesAnalysis>()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +Expected<MachinePassResult> 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<LiveVariablesAnalysis>(*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<LiveVariablesAnalysis>(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 <algorithm> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <ranges> +#include <span> +#include <string> +#include <string_view> +#include <utility> +#include <vector> + +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<Register> virtualRegisterAt(std::size_t Index) { + auto Reg = Register::makeVirtual(Index); + if (!Reg) + return std::unexpected(Reg.error()); + return *Reg; +} + +[[nodiscard]] inline Expected<RegisterClassID> 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<MachineRegisterInfo &>(Function.registerInfo()).regOperands(VirtualReg)) { + if (Operand.subReg().value() != 0 && !Registers.subRegister(Candidate, Operand.subReg())) + return false; + } + return true; +} + +[[nodiscard]] inline Expected<std::vector<PhysicalRegister>> +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<PhysicalRegister> 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<MachineRegisterInfo &>(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<std::uint64_t>(Operand.kind())); + if (const Register *Reg = Operand.getIf<Register>()) + Mix(Reg->opaqueValue()); + } + } + } + return Hash; +} + +[[nodiscard]] inline Expected<void> 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<void> +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<void> 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<MachineFunctionCloneResult> +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 <algorithm> +#include <cstdint> +#include <limits> +#include <optional> +#include <ranges> +#include <set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +struct PBQPAllocationNode final { + Register VirtualReg; + pbqp::NodeID Node; + std::vector<std::optional<PhysicalRegister>> Options; +}; + +[[nodiscard]] std::set<std::pair<std::uint32_t, std::uint32_t>> +copyRelatedRegisters(const MachineFunction &Function) { + std::set<std::pair<std::uint32_t, std::uint32_t>> 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<Register>(); + const Register *Source = Instruction->operands()[1].getIf<Register>(); + 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<std::uint64_t>(pbqp::InfiniteCost - 1); + return static_cast<pbqp::Cost>(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<AllocationRoundResult> + allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override { + LiveRegMatrix FixedMatrix(Function, Target, Intervals); + pbqp::Graph Problem; + std::vector<PBQPAllocationNode> 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<std::optional<PhysicalRegister>> 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<std::uint64_t>(1, Interval->SpillWeight); + const std::uint64_t Scaled = + TargetSpillCost > std::numeric_limits<std::uint64_t>::max() / Weight + ? std::numeric_limits<std::uint64_t>::max() + : TargetSpillCost * Weight; + const std::uint64_t Adjusted = + Scaled == std::numeric_limits<std::uint64_t>::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<std::uint64_t>(Hint - Info->get().AllocationHints.begin()); + Cost = Cost > std::numeric_limits<std::uint64_t>::max() - HintCost + ? std::numeric_limits<std::uint64_t>::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<std::uint64_t>(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<LiveIntervalsAnalysis>()}, + .VerificationStage = PipelineStage::RegisterAllocated, + }; + Value.ThreadSafety = PassThreadSafety::ThreadSafe; + return Value; + }(); + return Contract; +} + +} // namespace + +const MachinePassContract &PBQPAllocatorPass::contract() const noexcept { + return pbqpContract(); +} + +Expected<MachinePassResult> 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<TargetConstant> -TargetMIRTextInfo::parseTargetConstant(std::string_view Text) const { +Expected<TargetConstant> 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<std::string> -TargetMIRTextInfo::printTargetConstant(const TargetConstant &Constant) const { +Expected<std::string> 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 <algorithm> +#include <cstddef> +#include <optional> +#include <ranges> +#include <utility> +#include <vector> + +namespace rcc { + +Expected<void> VirtRegMap::add(Register VirtualReg, bool Spillable, + std::optional<Register> SplitParent, + std::optional<Register> 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<void> 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<void> 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<void> 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<void> 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<PhysicalRegister> VirtRegMap::physicalRegister(Register VirtualReg) const noexcept { + const VirtRegMapEntry *Value = entry(VirtualReg); + return Value == nullptr ? std::nullopt : Value->PhysicalReg; +} + +std::optional<FrameIndex> 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<const VirtRegMapEntry *> VirtRegMap::orderedEntries() const { + std::vector<const VirtRegMapEntry *> 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<void> 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<bool> 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<LiveIntervalsAnalysis>(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<Rewrite> 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<Register>(); + 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<MachinePassResult> 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 diff --git a/backend/lib/MIR/EmbeddedIR.cpp b/backend/lib/MIR/EmbeddedIR.cpp index b19748e..662faac 100644 --- a/backend/lib/MIR/EmbeddedIR.cpp +++ b/backend/lib/MIR/EmbeddedIR.cpp @@ -322,8 +322,8 @@ private: parseMetadataDefinition(Line, LineOffset, Position, End); } - void parseTypeDefinition(std::string_view Line, std::size_t LineOffset, - std::size_t Position, std::size_t End) { + void parseTypeDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Position, + std::size_t End) { auto Name = parseIdentifier(Line, LineOffset, Position, End, '%'); if (!Name || Failed) return; @@ -350,15 +350,14 @@ private: return; } const std::size_t TypeIndex = Index.TypeDefinitions.size(); - const bool NumericName = !Name->Name.empty() && Name->Name.front() >= '0' && - Name->Name.front() <= '9'; + const bool NumericName = + !Name->Name.empty() && Name->Name.front() >= '0' && Name->Name.front() <= '9'; Index.TypeNameToIndex.emplace(Name->Name, TypeIndex); Index.TypeDefinitions.push_back(EmbeddedIRTypeDefinition{ .Name = std::move(Name->Name), .Range = Name->Range, .Definition = std::string(Line.substr(Position, DefinitionEnd - Position)), - .DefinitionRange = - Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd), + .DefinitionRange = Index.Source.range(LineOffset + Position, LineOffset + DefinitionEnd), .NumericName = NumericName, }); } @@ -495,10 +494,10 @@ private: std::size_t Previous = IdentifierBegin; while (Previous > 0 && isHorizontalSpace(Line[Previous - 1])) --Previous; - const bool HasTypeBefore = Previous != 0 && Line[Previous - 1] != '(' && - Line[Previous - 1] != ','; - const bool EndsParameter = Following == End || Line[Following] == ',' || - Line[Following] == ')'; + const bool HasTypeBefore = + Previous != 0 && Line[Previous - 1] != '(' && Line[Previous - 1] != ','; + const bool EndsParameter = + Following == End || Line[Following] == ',' || Line[Following] == ')'; if (HasTypeBefore && EndsParameter) addLocalValue(*Name, Index.Functions[ActiveFunction.value()]); Position = Name->End - 1; @@ -630,9 +629,8 @@ private: }); } - void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset, - std::size_t Begin, std::size_t End, - EmbeddedIRFunction &Function) { + void parseLocalValueDefinition(std::string_view Line, std::size_t LineOffset, std::size_t Begin, + std::size_t End, EmbeddedIRFunction &Function) { std::size_t Position = skipHorizontalSpace(Line, Begin, End); if (Position >= End || Line[Position] != '%') return; diff --git a/backend/lib/MIR/LLVMConstantSyntax.cpp b/backend/lib/MIR/LLVMConstantSyntax.cpp index 543cc1a..8bc2c18 100644 --- a/backend/lib/MIR/LLVMConstantSyntax.cpp +++ b/backend/lib/MIR/LLVMConstantSyntax.cpp @@ -248,9 +248,7 @@ private: Words[Nibble / 16U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator)) << ((Nibble % 16U) * 4U); } - if ((BitWidth % 64U) != 0 && (Words.back() >> (BitWidth % 64U)) != 0) - return false; - return true; + return (BitWidth % 64U) == 0 || (Words.back() >> (BitWidth % 64U)) == 0; } [[nodiscard]] bool parseLegacyWideFloatHexWords(std::string_view Digits, @@ -1172,7 +1170,7 @@ convertRawDoubleNaN(FloatSemantics Semantics, bool Negative, std::uint64_t Fract "integer hexadecimal spelling contains a non-hexadecimal digit"); } - const auto FirstNonZero = + const auto *const FirstNonZero = std::ranges::find_if(Digits, [](char Character) { return hexDigitValue(Character) != 0; }); std::size_t ActiveBits = 0; if (FirstNonZero != Digits.end()) { @@ -1998,9 +1996,8 @@ Expected<GenericConstantData> ConstantParser::parseExpression(GenericConstantTyp case GenericConstantExpressionOpcode::Xor: case GenericConstantExpressionOpcode::ExtractElement: return 2; - case GenericConstantExpressionOpcode::InsertElement: - return 3; case GenericConstantExpressionOpcode::ShuffleVector: + case GenericConstantExpressionOpcode::InsertElement: return 3; case GenericConstantExpressionOpcode::GetElementPtr: return 1; @@ -2454,15 +2451,22 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT case GenericConstantKind::Invalid: break; case GenericConstantKind::Integer: + if (!Value.IntegerValue) + return makeUnexpected(ErrorCode::VerificationError, + "integer constant is missing its integer payload"); if (resolvedType(Value.Type).Kind == GenericConstantTypeKind::Integer && resolvedType(Value.Type).BitWidth == 1) - Result.append(Value.IntegerValue->isZero() ? "false" : "true"); + Result.append(Value.IntegerValue.value().isZero() ? "false" : "true"); else - Result.append(Value.IntegerValue->toUnsignedDecimal()); + Result.append(Value.IntegerValue.value().toUnsignedDecimal()); return Result; case GenericConstantKind::Floating: + if (!Value.FloatingValue) + return makeUnexpected(ErrorCode::VerificationError, + "floating constant is missing its floating payload"); Result.append("f0x"); - Result.append(hexadecimalWords(Value.FloatingValue->words(), Value.FloatingValue->bitWidth())); + Result.append(hexadecimalWords(Value.FloatingValue.value().words(), + Value.FloatingValue.value().bitWidth())); return Result; case GenericConstantKind::NullPointer: Result.append("null"); @@ -2549,15 +2553,25 @@ Expected<std::string> printValue(const GenericConstantData &Value, bool IncludeT if (Value.ExpressionFlags.has(GenericConstantExpressionFlag::NoSignedWrap)) Result.append(" nsw"); if (Value.InRangeStart) { + if (!Value.InRangeEnd) { + return makeUnexpected(ErrorCode::VerificationError, + "constant expression is missing its inrange end"); + } + const auto &InRangeStart = Value.InRangeStart.value(); + const auto &InRangeEnd = Value.InRangeEnd.value(); Result.append(" inrange("); - Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeStart->words()[0]))); + Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeStart.words()[0]))); Result.append(", "); - Result.append(std::to_string(std::bit_cast<std::int64_t>(Value.InRangeEnd->words()[0]))); + Result.append(std::to_string(std::bit_cast<std::int64_t>(InRangeEnd.words()[0]))); Result.push_back(')'); } Result.append(" ("); if (Value.ExpressionOpcode == GenericConstantExpressionOpcode::GetElementPtr) { - auto SourceType = printType(*Value.SourceElementType); + if (!Value.SourceElementType) { + return makeUnexpected(ErrorCode::VerificationError, + "getelementptr constant is missing its source element type"); + } + auto SourceType = printType(Value.SourceElementType.value()); if (!SourceType) return std::unexpected(SourceType.error()); Result.append(*SourceType); @@ -3004,14 +3018,12 @@ LayoutAlignment DataLayoutInfo::scalarAlignment(char Kind, std::uint32_t BitWidt if (Entry.Kind != Kind) continue; if (Kind == 'i') { - if (Entry.BitWidth >= BitWidth && - (Selected == nullptr || Entry.BitWidth < Selected->BitWidth)) { + const bool BetterMatch = + Selected == nullptr || + (Entry.BitWidth >= BitWidth && Entry.BitWidth < Selected->BitWidth) || + (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth); + if (BetterMatch) Selected = &Entry; - } else if (Selected == nullptr) { - Selected = &Entry; - } else if (Selected->BitWidth < BitWidth && Entry.BitWidth > Selected->BitWidth) { - Selected = &Entry; - } } else if (Entry.BitWidth == BitWidth) { Selected = &Entry; break; diff --git a/backend/lib/MIR/MIDebugSyntax.cpp b/backend/lib/MIR/MIDebugSyntax.cpp index bee82c4..fc08df6 100644 --- a/backend/lib/MIR/MIDebugSyntax.cpp +++ b/backend/lib/MIR/MIDebugSyntax.cpp @@ -16,15 +16,13 @@ namespace { [[nodiscard]] bool parseIndex(std::string_view Text, std::uint64_t &Value) noexcept { if (Text.empty()) return false; - const auto [End, Error] = - std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10); + const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Value, 10); return Error == std::errc{} && End == Text.data() + Text.size(); } } // namespace -std::optional<std::uint64_t> -parseDIExpressionOpcodeName(std::string_view Name) noexcept { +std::optional<std::uint64_t> parseDIExpressionOpcodeName(std::string_view Name) noexcept { const auto NumberedOpcode = [Name](std::string_view Prefix, std::uint64_t Base) -> std::optional<std::uint64_t> { if (!Name.starts_with(Prefix)) @@ -117,7 +115,7 @@ parseDIExpressionOpcodeName(std::string_view Name) noexcept { {"DW_OP_LLVM_implicit_pointer", 0x1004}, {"DW_OP_LLVM_arg", 0x1005}, }); - const auto Found = + const auto *const Found = std::ranges::find_if(NamedOpcodes, [Name](const auto &Entry) { return Entry.first == Name; }); if (Found == NamedOpcodes.end()) return std::nullopt; diff --git a/backend/lib/MIR/MIPrinter.cpp b/backend/lib/MIR/MIPrinter.cpp index 83fce40..8ad6d6c 100644 --- a/backend/lib/MIR/MIPrinter.cpp +++ b/backend/lib/MIR/MIPrinter.cpp @@ -1285,20 +1285,24 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) { return makeUnexpected(ErrorCode::VerificationError, "machine instruction has no target descriptor"); } - if (Descriptor->NumExplicitDefs > Instruction.operandCount()) { - return makeUnexpected(ErrorCode::VerificationError, - "machine instruction has fewer operands than explicit definitions"); + std::size_t ExplicitDefs = 0; + while (ExplicitDefs < Instruction.operandCount()) { + const MachineOperand *Operand = Instruction.operandAt(ExplicitDefs); + if (Operand == nullptr || !Operand->isRegister() || Operand->isImplicit() || + !Operand->isDef() || Operand->isUse()) + break; + ++ExplicitDefs; } Output.append(" "); - for (std::size_t Index = 0; Index < Descriptor->NumExplicitDefs; ++Index) { + for (std::size_t Index = 0; Index < ExplicitDefs; ++Index) { if (Index != 0) Output.append(", "); if (auto Printed = printOperand(*Instruction.operandAt(Index), true); !Printed) { return Printed; } } - if (Descriptor->NumExplicitDefs != 0) + if (ExplicitDefs != 0) Output.append(" = "); const MachineInstrFlags Flags = Instruction.flags(); @@ -1333,8 +1337,7 @@ Expected<void> BodyPrinter::printInstruction(const MachineInstr &Instruction) { Output.append(Descriptor->Name); bool HasPrintedTail = false; - for (std::size_t Index = Descriptor->NumExplicitDefs; Index < Instruction.operandCount(); - ++Index) { + for (std::size_t Index = ExplicitDefs; Index < Instruction.operandCount(); ++Index) { Output.append(HasPrintedTail ? ", " : " "); HasPrintedTail = true; if (auto Printed = printOperand(*Instruction.operandAt(Index), false); !Printed) { diff --git a/backend/lib/MIR/MIRDocument.cpp b/backend/lib/MIR/MIRDocument.cpp index 4808df7..67e6ffb 100644 --- a/backend/lib/MIR/MIRDocument.cpp +++ b/backend/lib/MIR/MIRDocument.cpp @@ -406,7 +406,8 @@ class MIRDocumentParser final { public: MIRDocumentParser(const TargetDescription &Target, std::string SourceName, std::string SourceText, MIRDocumentParserOptions Options) - : Target(Target), Options(Options), Result(std::move(SourceName), std::move(SourceText)) {} + : Target(Target), Options(std::move(Options)), + Result(std::move(SourceName), std::move(SourceText)) {} [[nodiscard]] MIRDocumentParseResult run(); @@ -2144,8 +2145,7 @@ bool MIRDocumentParser::parseFunctionRecords(const yaml::Node &Root, MachineFunc WideFlags > std::numeric_limits<std::uint32_t>::max()) { return true; } - if (ActiveDocument->EmbeddedIR && - ActiveDocument->EmbeddedIR->hasGlobalValue(Callee) == false) { + if (ActiveDocument->EmbeddedIR && !ActiveDocument->EmbeddedIR->hasGlobalValue(Callee)) { return fail(CalleeNode->range(), "called global references an undefined embedded global"); } auto AddResult = @@ -2765,7 +2765,8 @@ MIRDocumentParseResult::~MIRDocumentParseResult() = default; MIRDocumentParseResult parseMIRDocument(const TargetDescription &Target, std::string SourceName, std::string SourceText, MIRDocumentParserOptions Options) { - return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), Options).run(); + return MIRDocumentParser(Target, std::move(SourceName), std::move(SourceText), std::move(Options)) + .run(); } } // namespace rcc::mir diff --git a/backend/lib/MIR/MIRDocumentPrinter.cpp b/backend/lib/MIR/MIRDocumentPrinter.cpp index e9f9e1c..dba1ec7 100644 --- a/backend/lib/MIR/MIRDocumentPrinter.cpp +++ b/backend/lib/MIR/MIRDocumentPrinter.cpp @@ -85,7 +85,7 @@ class MIRDocumentPrinter final { public: MIRDocumentPrinter(const MIRDocument &Document, const TargetDescription &Target, MIRDocumentPrinterOptions Options) - : Document(Document), Target(Target), Options(Options) {} + : Document(Document), Target(Target), Options(std::move(Options)) {} [[nodiscard]] Expected<std::string> run(); @@ -1187,9 +1187,10 @@ Expected<void> MIRDocumentPrinter::printFunction(const MachineFunction &Function Output.append("---\nname: "); Output.append(yamlScalar(Function.name())); Output.push_back('\n'); - if (Function.attributes().alignment()) { + const auto Alignment = Function.attributes().alignment(); + if (Alignment) { Output.append("alignment: "); - Output.append(std::to_string(Function.attributes().alignment()->bytes())); + Output.append(std::to_string(Alignment->bytes())); Output.push_back('\n'); } @@ -1296,7 +1297,7 @@ Expected<std::string> MIRDocumentPrinter::run() { Expected<std::string> printMIRDocument(const MIRDocument &Document, const TargetDescription &Target, MIRDocumentPrinterOptions Options) { - return MIRDocumentPrinter(Document, Target, Options).run(); + return MIRDocumentPrinter(Document, Target, std::move(Options)).run(); } } // namespace rcc::mir diff --git a/backend/lib/MIR/MIRDocumentReferenceValidation.h b/backend/lib/MIR/MIRDocumentReferenceValidation.h index 0992d84..2ab6291 100644 --- a/backend/lib/MIR/MIRDocumentReferenceValidation.h +++ b/backend/lib/MIR/MIRDocumentReferenceValidation.h @@ -1,5 +1,7 @@ // 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_MIR_MIRDOCUMENTREFERENCEVALIDATION_H #define RCC_LIB_MIR_MIRDOCUMENTREFERENCEVALIDATION_H diff --git a/backend/lib/Support/Error.cpp b/backend/lib/Support/Error.cpp index dc7d590..817a2bb 100644 --- a/backend/lib/Support/Error.cpp +++ b/backend/lib/Support/Error.cpp @@ -14,6 +14,8 @@ std::string_view getErrorCodeName(ErrorCode Code) noexcept { return "verification error"; case ErrorCode::Unsupported: return "unsupported"; + case ErrorCode::RegisterAllocationFailed: + return "register allocation failed"; case ErrorCode::IoError: return "I/O error"; case ErrorCode::InternalError: diff --git a/backend/lib/Target/Description/TargetDescriptionGenerator.cpp b/backend/lib/Target/Description/TargetDescriptionGenerator.cpp index 3c5e817..9d6b8e1 100644 --- a/backend/lib/Target/Description/TargetDescriptionGenerator.cpp +++ b/backend/lib/Target/Description/TargetDescriptionGenerator.cpp @@ -1364,7 +1364,7 @@ private: const auto Value = unsignedInteger32(*Tie, "instruction operand default_tied_operand"); if (!Value) return std::nullopt; - Result.DefaultTiedOperand = *Value; + Result.DefaultTiedOperand = Value; } if (const yaml::Node *EarlyClobber = optionalNode(Node, "early_clobber")) { const auto Value = boolean(*EarlyClobber, "instruction operand early_clobber"); @@ -1614,7 +1614,7 @@ operandKindEnumerator(std::string_view Value) noexcept { {"debug_instr_ref", "DebugInstrRef"}, {"lane_mask", "LaneMask"}, }}; - const auto Position = std::ranges::find(Kinds, Value, &decltype(Kinds)::value_type::first); + const auto *const Position = std::ranges::find(Kinds, Value, &decltype(Kinds)::value_type::first); if (Position == Kinds.end()) return std::nullopt; return Position->second; @@ -1675,7 +1675,7 @@ instructionFlagEnumerator(std::string_view Value) noexcept { {"generic", "Generic"}, {"terminal_emission", "TerminalEmission"}, }}; - const auto Position = std::ranges::find(Flags, Value, &decltype(Flags)::value_type::first); + const auto *const Position = std::ranges::find(Flags, Value, &decltype(Flags)::value_type::first); if (Position == Flags.end()) return std::nullopt; return Position->second; @@ -1698,7 +1698,8 @@ pseudoOwnerEnumerator(std::string_view Value) noexcept { }}; if (Value == "asm_printer") return "AsmPrinter"; - const auto Position = std::ranges::find(Owners, Value, &decltype(Owners)::value_type::first); + const auto *const Position = + std::ranges::find(Owners, Value, &decltype(Owners)::value_type::first); if (Position == Owners.end()) return std::nullopt; return Position->second; @@ -1718,7 +1719,8 @@ pipelineStageEnumerator(std::string_view Value) noexcept { {"post_ra_finalized", "PostRAFinalized"}, {"emission", "Emission"}, }}; - const auto Position = std::ranges::find(Stages, Value, &decltype(Stages)::value_type::first); + const auto *const Position = + std::ranges::find(Stages, Value, &decltype(Stages)::value_type::first); if (Position == Stages.end()) return std::nullopt; return Position->second; @@ -2066,7 +2068,7 @@ private: fail(Convention.Range, "calling convention register classes must resolve"); return false; } - const auto normalizeRegisterList = [this, + const auto NormalizeRegisterList = [this, &Convention](const std::vector<std::string> &Symbols, const NormalizedRegisterClass &RegisterClass, std::vector<std::uint32_t> &Output) { @@ -2101,13 +2103,13 @@ private: .SupportsVarArgs = Convention.SupportsVarArgs, .SupportsTailCalls = Convention.SupportsTailCalls, }; - if (!normalizeRegisterList(Convention.IntegerArgumentRegisterSymbols, + if (!NormalizeRegisterList(Convention.IntegerArgumentRegisterSymbols, *IntegerClassDescription, Normalized.IntegerArgumentRegisters) || - !normalizeRegisterList(Convention.FloatingArgumentRegisterSymbols, + !NormalizeRegisterList(Convention.FloatingArgumentRegisterSymbols, *FloatingClassDescription, Normalized.FloatingArgumentRegisters) || - !normalizeRegisterList(Convention.IntegerReturnRegisterSymbols, *IntegerClassDescription, + !NormalizeRegisterList(Convention.IntegerReturnRegisterSymbols, *IntegerClassDescription, Normalized.IntegerReturnRegisters) || - !normalizeRegisterList(Convention.FloatingReturnRegisterSymbols, + !NormalizeRegisterList(Convention.FloatingReturnRegisterSymbols, *FloatingClassDescription, Normalized.FloatingReturnRegisters)) { return false; } @@ -3004,8 +3006,9 @@ void emitImmediatePredicate(std::ostream &Output, const NormalizedImmediatePredi } // namespace -DescriptionGenerationResult generateDescription(std::string SourceName, std::string SourceText) { - yaml::ParseResult YAMLResult = yaml::parse(SourceName, SourceText); +DescriptionGenerationResult generateDescription(const std::string &SourceName, + std::string SourceText) { + yaml::ParseResult YAMLResult = yaml::parse(SourceName, std::move(SourceText)); if (!YAMLResult.succeeded()) { DescriptionGenerationResult Result; for (const TextDiagnostic &Diagnostic : YAMLResult.diagnostics()) diff --git a/backend/lib/Target/Description/TargetDescriptionGenerator.h b/backend/lib/Target/Description/TargetDescriptionGenerator.h index c0d8ed5..9a03aa0 100644 --- a/backend/lib/Target/Description/TargetDescriptionGenerator.h +++ b/backend/lib/Target/Description/TargetDescriptionGenerator.h @@ -1,5 +1,7 @@ // 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_TARGET_DESCRIPTION_TARGETDESCRIPTIONGENERATOR_H #define RCC_TARGET_DESCRIPTION_TARGETDESCRIPTIONGENERATOR_H @@ -27,7 +29,7 @@ struct DescriptionGenerationResult final { } }; -[[nodiscard]] DescriptionGenerationResult generateDescription(std::string SourceName, +[[nodiscard]] DescriptionGenerationResult generateDescription(const std::string &SourceName, std::string SourceText); } // namespace rcc::targetgen diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt index 4728117..1d9a27a 100644 --- a/backend/lib/Target/RISCV/CMakeLists.txt +++ b/backend/lib/Target/RISCV/CMakeLists.txt @@ -49,6 +49,7 @@ add_library( RCCBackendRISCV RISCVCodeGen.cpp RISCVCallLowering.cpp + RISCVRegisterAllocation.cpp RISCVTarget.cpp "${RCCBackendRISCVGeneratedRegisterHeader}" "${RCCBackendRISCVGeneratedInstructionHeader}" @@ -93,6 +94,7 @@ install( rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCodeGen.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Target/RISCV/RISCVCallLowering.h" @@ -101,5 +103,6 @@ rcc_backend_register_format_files( rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCodeGen.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVCallLowering.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVRegisterAllocation.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVTarget.cpp" ) diff --git a/backend/lib/Target/RISCV/RISCV.rccdesc b/backend/lib/Target/RISCV/RISCV.rccdesc index a8dfdde..e248bc7 100644 --- a/backend/lib/Target/RISCV/RISCV.rccdesc +++ b/backend/lib/Target/RISCV/RISCV.rccdesc @@ -375,7 +375,7 @@ instructions: - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, name: RD } - { kinds: [immediate], immediate_predicate: SIMM20, name: IMM } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, rematerializable] scheduling_class: ALU encoding_category: U assembly_format: RD_IMM @@ -402,7 +402,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, rematerializable] scheduling_class: ALU encoding_category: I assembly_format: RD_RS1_IMM @@ -444,7 +444,7 @@ instructions: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 - flags: [produces_code] + flags: [produces_code, rematerializable] scheduling_class: ALU encoding_category: I assembly_format: RD_RS1_IMM @@ -709,7 +709,7 @@ instructions: assembly_mnemonic: lw operands: - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, memory_role: value, name: RD } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 flags: [may_load, produces_code] @@ -799,7 +799,7 @@ instructions: assembly_mnemonic: sw operands: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: value, name: RS2 } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 0 flags: [may_store, produces_code] @@ -1202,7 +1202,7 @@ instructions: assembly_mnemonic: ld operands: - { kinds: [register], role: def, register_class: GPR, register_bank: GPR, memory_role: value, name: RD } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 flags: [may_load, produces_code] @@ -1217,7 +1217,7 @@ instructions: assembly_mnemonic: sd operands: - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: value, name: RS2 } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 0 flags: [may_store, produces_code] @@ -1423,7 +1423,7 @@ instructions: assembly_mnemonic: flw operands: - { kinds: [register], role: def, register_class: FPR32, register_bank: FPR, memory_role: value, name: FRD } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 flags: [may_load, produces_code] @@ -1438,7 +1438,7 @@ instructions: assembly_mnemonic: fsw operands: - { kinds: [register], role: use, register_class: FPR32, register_bank: FPR, memory_role: value, name: FRS2 } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 0 flags: [may_store, produces_code] @@ -1854,7 +1854,7 @@ instructions: assembly_mnemonic: fld operands: - { kinds: [register], role: def, register_class: FPR64, register_bank: FPR, memory_role: value, name: FRD } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 1 flags: [may_load, produces_code] @@ -1869,7 +1869,7 @@ instructions: assembly_mnemonic: fsd operands: - { kinds: [register], role: use, register_class: FPR64, register_bank: FPR, memory_role: value, name: FRS2 } - - { kinds: [register], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } + - { kinds: [register, frame_index], role: use, register_class: GPR, register_bank: GPR, memory_role: address, name: RS1 } - { kinds: [immediate], immediate_predicate: SIMM12, name: IMM } num_explicit_defs: 0 flags: [may_store, produces_code] diff --git a/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp new file mode 100644 index 0000000..e437e18 --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVRegisterAllocation.cpp @@ -0,0 +1,279 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/InstructionDescriptor.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/Target/RISCV/RISCVCodeGen.h" +#include "rcc/Target/RISCV/RISCVInstructions.h" +#include "rcc/Target/RISCV/RISCVRegisters.h" +#include "rcc/Target/RISCV/RISCVTarget.h" + +#include <algorithm> +#include <array> +#include <cstddef> +#include <cstdint> +#include <optional> +#include <utility> + +namespace rcc::riscv { +namespace { + +struct SpillForm final { + InstructionOpcode Load; + InstructionOpcode Store; + std::uint64_t SizeInBytes; +}; + +[[nodiscard]] constexpr Opcode targetOpcode(InstructionOpcode Value) noexcept { + return Opcode::fromValue(static_cast<std::uint32_t>(Value)); +} + +[[nodiscard]] constexpr RegisterClassID registerClassID(RegisterClass Value) noexcept { + return RegisterClassID::fromValue(static_cast<std::uint32_t>(Value)); +} + +[[nodiscard]] constexpr std::optional<SpillForm> spillForm(RegisterClassID Class) noexcept { + if (Class == registerClassID(RegisterClass::GPR) || + Class == registerClassID(RegisterClass::GPRC) || + Class == registerClassID(RegisterClass::GPR_NX0) || + Class == registerClassID(RegisterClass::GPR_NX0_NX2)) { + return SpillForm{InstructionOpcode::LD, InstructionOpcode::SD, 8}; + } + if (Class == registerClassID(RegisterClass::FPR64) || + Class == registerClassID(RegisterClass::FPR64C)) { + return SpillForm{InstructionOpcode::FLD, InstructionOpcode::FSD, 8}; + } + if (Class == registerClassID(RegisterClass::FPR32) || + Class == registerClassID(RegisterClass::FPR32C)) { + return SpillForm{InstructionOpcode::FLW, InstructionOpcode::FSW, 4}; + } + return std::nullopt; +} + +[[nodiscard]] Expected<const MachineMemOperand *> +createStackMemoryOperand(MachineIRBuilder &Builder, FrameIndex StackSlot, MemoryAccessFlag Access, + std::uint64_t SizeInBytes, std::uint64_t AlignmentInBytes) { + auto Size = MemorySize::fixed(SizeInBytes); + if (!Size) + return std::unexpected(Size.error()); + auto Align = Alignment::create(AlignmentInBytes); + if (!Align) + return std::unexpected(Align.error()); + + MachineMemOperandDesc Description; + Description.Accesses = {Access}; + Description.Size = *Size; + Description.Align = *Align; + Description.Base = MemoryBase::frameIndex(StackSlot); + return Builder.function().createMemOperand(std::move(Description)); +} + +[[nodiscard]] bool isCalleeSaved(PhysicalRegister Reg) noexcept { + const std::uint32_t Number = Reg.number(); + const std::array GPRs{ + PhysicalRegisterID::X8, PhysicalRegisterID::X9, PhysicalRegisterID::X18, + PhysicalRegisterID::X19, PhysicalRegisterID::X20, PhysicalRegisterID::X21, + PhysicalRegisterID::X22, PhysicalRegisterID::X23, PhysicalRegisterID::X24, + PhysicalRegisterID::X25, PhysicalRegisterID::X26, PhysicalRegisterID::X27, + }; + const std::array FPRs{ + PhysicalRegisterID::F8, PhysicalRegisterID::F9, PhysicalRegisterID::F18, + PhysicalRegisterID::F19, PhysicalRegisterID::F20, PhysicalRegisterID::F21, + PhysicalRegisterID::F22, PhysicalRegisterID::F23, PhysicalRegisterID::F24, + PhysicalRegisterID::F25, PhysicalRegisterID::F26, PhysicalRegisterID::F27, + }; + const auto Matches = [Number](PhysicalRegisterID ID) { + return Number == static_cast<std::uint32_t>(ID); + }; + return std::ranges::any_of(GPRs, Matches) || std::ranges::any_of(FPRs, Matches); +} + +[[nodiscard]] bool isCompressedRegister(PhysicalRegister Reg) noexcept { + const std::uint32_t Number = Reg.number(); + const std::uint32_t X8 = static_cast<std::uint32_t>(PhysicalRegisterID::X8); + const std::uint32_t X15 = static_cast<std::uint32_t>(PhysicalRegisterID::X15); + const std::uint32_t F8 = static_cast<std::uint32_t>(PhysicalRegisterID::F8); + const std::uint32_t F15 = static_cast<std::uint32_t>(PhysicalRegisterID::F15); + return (Number >= X8 && Number <= X15) || (Number >= F8 && Number <= F15); +} + +class RISCVRegisterAllocationInfo final : public TargetRegisterAllocationInfo { +public: + [[nodiscard]] Expected<void> validateSpillReload(RegisterClassID Class, + const TargetDescription &Target) const override { + const RegisterClassDesc *Description = Target.registers().registerClass(Class); + const auto Form = spillForm(Class); + if (!Form) { + return makeUnexpected(ErrorCode::Unsupported, + "RV64GC register class has no scalar spill/reload form"); + } + if (Description == nullptr || !Description->Allocatable || + Description->SpillSizeInBits != Form->SizeInBytes * 8U || + Description->SpillAlignmentInBits == 0 || Description->SpillAlignmentInBits % 8U != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RV64GC register class has inconsistent spill properties"); + } + for (const InstructionOpcode OpcodeValue : {Form->Load, Form->Store}) { + const InstructionDescriptor *Instruction = + Target.instructionDescriptor(targetOpcode(OpcodeValue)); + if (Instruction == nullptr || Instruction->Operands.size() != 3 || + !Instruction->Operands[1].Kinds.contains(MachineOperand::Kind::FrameIndex) || + !Instruction->RequiresMemoryOperands) { + return makeUnexpected(ErrorCode::InternalError, + "RV64GC spill instruction descriptor is incomplete"); + } + } + return {}; + } + + [[nodiscard]] Expected<MachineInstr *> emitReload(MachineIRBuilder &Builder, Register Destination, + RegisterClassID Class, FrameIndex StackSlot, + LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + const RegisterClassDesc *Description = Builder.target().registers().registerClass(Class); + if (Lanes.empty() || !Lanes.intersects(Description->Lanes)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RV64GC reload requires a nonempty class lane mask"); + } + const auto FormValue = spillForm(Class); + if (!FormValue) { + return makeUnexpected(ErrorCode::InternalError, + "RV64GC reload lost its validated spill form"); + } + const SpillForm Form = FormValue.value(); + auto Memory = + createStackMemoryOperand(Builder, StackSlot, MemoryAccessFlag::Load, Form.SizeInBytes, + Description->SpillAlignmentInBits / 8U); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = Builder.buildInstr(targetOpcode(Form.Load)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addDef(Destination); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(0); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] Expected<MachineInstr *> emitSpill(MachineIRBuilder &Builder, Register Source, + RegisterClassID Class, FrameIndex StackSlot, + LaneMask Lanes) const override { + auto Validated = validateSpillReload(Class, Builder.target()); + if (!Validated) + return std::unexpected(Validated.error()); + const RegisterClassDesc *Description = Builder.target().registers().registerClass(Class); + if (Lanes.empty() || !Lanes.intersects(Description->Lanes)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RV64GC spill requires a nonempty class lane mask"); + } + const auto FormValue = spillForm(Class); + if (!FormValue) { + return makeUnexpected(ErrorCode::InternalError, "RV64GC spill lost its validated spill form"); + } + const SpillForm Form = FormValue.value(); + auto Memory = + createStackMemoryOperand(Builder, StackSlot, MemoryAccessFlag::Store, Form.SizeInBytes, + Description->SpillAlignmentInBits / 8U); + if (!Memory) + return std::unexpected(Memory.error()); + auto Pending = Builder.buildInstr(targetOpcode(Form.Store)); + if (!Pending) + return std::unexpected(Pending.error()); + if (auto Result = Pending->addUse(Source); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addFrameIndex(StackSlot); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addImmediate(0); !Result) + return std::unexpected(Result.error()); + if (auto Result = Pending->addMemOperand(**Memory); !Result) + return std::unexpected(Result.error()); + return Pending->build(); + } + + [[nodiscard]] Expected<bool> isRematerializable(const MachineInstr &Instruction, + Register VirtualReg, const MachineFunction &, + const TargetDescription &) const override { + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *DefinedReg = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + if (DefinedReg == nullptr || *DefinedReg != VirtualReg || !Definition->isDef()) + return false; + + if (Instruction.opcode() == targetOpcode(InstructionOpcode::LUI)) + return Instruction.operandCount() == 2 && Instruction.operandAt(1) != nullptr; + if (Instruction.opcode() != targetOpcode(InstructionOpcode::ADDI) && + Instruction.opcode() != targetOpcode(InstructionOpcode::ADDIW)) { + return false; + } + if (Instruction.operandCount() != 3) + return false; + const MachineOperand *Source = Instruction.operandAt(1); + const Register *SourceReg = Source == nullptr ? nullptr : Source->getIf<Register>(); + const auto Zero = physicalRegister(PhysicalRegisterID::X0); + return Zero && SourceReg != nullptr && *SourceReg == Register::fromPhysical(*Zero) && + Source->isUse(); + } + + [[nodiscard]] Expected<MachineInstr *> + rematerialize(MachineIRBuilder &Builder, const MachineInstr &Original, Register Destination, + Register OriginalRegister, const TargetDescription &Target) const override { + auto Accepted = isRematerializable(Original, OriginalRegister, Builder.function(), Target); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (!*Accepted) { + return makeUnexpected(ErrorCode::InvalidArgument, + "RV64GC instruction is not rematerializable"); + } + + auto Pending = Builder.buildInstr(Original.opcode()); + if (!Pending) + return std::unexpected(Pending.error()); + const MachineOperand *OriginalDef = Original.operandAt(0); + if (auto Result = Pending->addDef(Destination, {}, {}, OriginalDef->targetFlags()); !Result) + return std::unexpected(Result.error()); + for (std::size_t Index = 1; Index < Original.operandCount(); ++Index) { + const MachineOperand *Operand = Original.operandAt(Index); + if (Operand == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "RV64GC rematerialization found a missing operand"); + } + if (auto Result = Pending->addOperand(Operand->cloneDetached()); !Result) + return std::unexpected(Result.error()); + } + return Pending->build(); + } + + [[nodiscard]] std::uint64_t physicalRegisterCost(const MachineFunction &, Register, + PhysicalRegister Reg, RegisterClassID, + bool) const noexcept override { + if (Reg.number() == static_cast<std::uint32_t>(PhysicalRegisterID::X1)) + return 16; + if (isCalleeSaved(Reg)) + return 4; + return isCompressedRegister(Reg) ? 0 : 1; + } + + [[nodiscard]] std::uint64_t spillCost(const MachineFunction &, const LiveInterval &, + RegisterClassID Class) const noexcept override { + const auto Form = spillForm(Class); + return Form ? std::max<std::uint64_t>(1, Form->SizeInBytes / 4U) : 1; + } +}; + +} // namespace + +const TargetRegisterAllocationInfo ®isterAllocationInfo() noexcept { + static const RISCVRegisterAllocationInfo Info; + return Info; +} + +} // namespace rcc::riscv |