From 924dcd36ebed84f04729de05ec08b311a36a04c1 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sat, 1 Aug 2026 16:07:24 +0800 Subject: [CodeGen] Add target register descriptions Introduce an immutable register topology for units, subregisters, classes, banks, and preserved masks. Bind instruction descriptors to this topology through TargetDescription so builders, cloning, and verification share one target-aware contract. Add the test-only TestTarget model and positive and negative target fact coverage. --- backend/lib/CodeGen/CMakeLists.txt | 8 + backend/lib/CodeGen/InstructionDescriptor.cpp | 8 - backend/lib/CodeGen/MachineFunctionCloner.cpp | 7 +- backend/lib/CodeGen/MachineIRBuilder.cpp | 39 +- backend/lib/CodeGen/MachineVerifier.cpp | 20 +- backend/lib/CodeGen/TargetDescription.cpp | 610 ++++++++++++++++++++++++++ backend/lib/CodeGen/TargetRegisterInfo.cpp | 603 +++++++++++++++++++++++++ 7 files changed, 1259 insertions(+), 36 deletions(-) create mode 100644 backend/lib/CodeGen/TargetDescription.cpp create mode 100644 backend/lib/CodeGen/TargetRegisterInfo.cpp (limited to 'backend/lib') diff --git a/backend/lib/CodeGen/CMakeLists.txt b/backend/lib/CodeGen/CMakeLists.txt index 68ebf04..3a45cec 100644 --- a/backend/lib/CodeGen/CMakeLists.txt +++ b/backend/lib/CodeGen/CMakeLists.txt @@ -23,7 +23,9 @@ set( Register.cpp RegisterMask.cpp TargetConstant.cpp + TargetDescription.cpp TargetFunctionState.cpp + TargetRegisterInfo.cpp ) set( RCCBackendCodeGenHeaders @@ -49,7 +51,9 @@ set( "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/RegisterMask.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/StableID.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetConstant.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetDescription.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetFunctionState.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/TargetRegisterInfo.h" ) add_library(RCCBackendCodeGen ${RCCBackendCodeGenSources}) @@ -102,7 +106,9 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp" ${RCCBackendCodeGenHeaders} ) rcc_backend_register_tidy_files( @@ -127,5 +133,7 @@ rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/Register.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RegisterMask.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetConstant.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetDescription.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/TargetFunctionState.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/TargetRegisterInfo.cpp" ) diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp index 9f4a178..3d97440 100644 --- a/backend/lib/CodeGen/InstructionDescriptor.cpp +++ b/backend/lib/CodeGen/InstructionDescriptor.cpp @@ -493,14 +493,6 @@ Expected InstructionSet::validateOperand(const OperandDescriptor &Descript auto Info = RegInfo.virtualRegisterInfo(*Reg); if (!Info) return std::unexpected(Info.error()); - if (Descriptor.RegBank && Info->get().Bank != Descriptor.RegBank) { - return makeUnexpected(ErrorCode::VerificationError, - "virtual register bank does not match operand descriptor"); - } - if (Descriptor.RegClass && Info->get().RegClass != Descriptor.RegClass) { - return makeUnexpected(ErrorCode::VerificationError, - "virtual register class does not match operand descriptor"); - } } } diff --git a/backend/lib/CodeGen/MachineFunctionCloner.cpp b/backend/lib/CodeGen/MachineFunctionCloner.cpp index a8fe15e..d365fd0 100644 --- a/backend/lib/CodeGen/MachineFunctionCloner.cpp +++ b/backend/lib/CodeGen/MachineFunctionCloner.cpp @@ -15,6 +15,7 @@ #include "rcc/CodeGen/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/MachineVerifier.h" +#include "rcc/CodeGen/TargetDescription.h" #include "rcc/CodeGen/TargetFunctionState.h" #include @@ -553,9 +554,9 @@ MachineFunctionCloneResult::operator=(MachineFunctionCloneResult &&) noexcept = MachineFunctionCloneResult::~MachineFunctionCloneResult() = default; Expected cloneMachineFunction(const MachineFunction &Source, - const InstructionSet &Instructions, + const TargetDescription &Target, MachineFunctionCloneOptions Options) { - auto SourceVerification = MachineVerifier::verify(Source, Instructions); + auto SourceVerification = MachineVerifier::verify(Source, Target); if (!SourceVerification) return std::unexpected(SourceVerification.error()); if (!Options.NewStableID.isValid()) { @@ -615,7 +616,7 @@ Expected cloneMachineFunction(const MachineFunction return std::unexpected(CompilationStatus.error()); Result.ClonedFunction->compilationStatus() = std::move(*CompilationStatus); Result.ClonedFunction->properties() = Source.properties(); - auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Instructions); + auto DestinationVerification = MachineVerifier::verify(*Result.ClonedFunction, Target); if (!DestinationVerification) return std::unexpected(DestinationVerification.error()); return Result; diff --git a/backend/lib/CodeGen/MachineIRBuilder.cpp b/backend/lib/CodeGen/MachineIRBuilder.cpp index 74ca55b..7f6421b 100644 --- a/backend/lib/CodeGen/MachineIRBuilder.cpp +++ b/backend/lib/CodeGen/MachineIRBuilder.cpp @@ -20,16 +20,15 @@ namespace rcc { -MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, - const InstructionSet &Instructions, +MachineInstrBuilder::MachineInstrBuilder(MachineFunction &Function, const TargetDescription &Target, const InstructionDescriptor &Descriptor, MachineBasicBlock &InsertBlock, MachineInstr *InsertBefore) noexcept - : Function(&Function), Instructions(&Instructions), Descriptor(&Descriptor), - InsertBlock(&InsertBlock), InsertBefore(InsertBefore) {} + : Function(&Function), Target(&Target), Descriptor(&Descriptor), InsertBlock(&InsertBlock), + InsertBefore(InsertBefore) {} MachineInstrBuilder::MachineInstrBuilder(MachineInstrBuilder &&Other) noexcept - : Function(Other.Function), Instructions(Other.Instructions), Descriptor(Other.Descriptor), + : Function(Other.Function), Target(Other.Target), Descriptor(Other.Descriptor), InsertBlock(Other.InsertBlock), InsertBefore(Other.InsertBefore), ExplicitOperands(std::move(Other.ExplicitOperands)), ExtraImplicitOperands(std::move(Other.ExtraImplicitOperands)), @@ -37,7 +36,7 @@ MachineInstrBuilder::MachineInstrBuilder(MachineInstrBuilder &&Other) noexcept Flags(Other.Flags), Location(std::move(Other.Location)), Origin(Other.Origin), IsBuilt(Other.IsBuilt) { Other.Function = nullptr; - Other.Instructions = nullptr; + Other.Target = nullptr; Other.Descriptor = nullptr; Other.InsertBlock = nullptr; Other.InsertBefore = nullptr; @@ -49,7 +48,7 @@ MachineInstrBuilder &MachineInstrBuilder::operator=(MachineInstrBuilder &&Other) return *this; Function = Other.Function; - Instructions = Other.Instructions; + Target = Other.Target; Descriptor = Other.Descriptor; InsertBlock = Other.InsertBlock; InsertBefore = Other.InsertBefore; @@ -63,7 +62,7 @@ MachineInstrBuilder &MachineInstrBuilder::operator=(MachineInstrBuilder &&Other) IsBuilt = Other.IsBuilt; Other.Function = nullptr; - Other.Instructions = nullptr; + Other.Target = nullptr; Other.Descriptor = nullptr; Other.InsertBlock = nullptr; Other.InsertBefore = nullptr; @@ -448,12 +447,12 @@ Expected MachineInstrBuilder::build() { } } - auto ExplicitValidation = Instructions->validateExplicitOperands( + auto ExplicitValidation = Target->validateExplicitOperands( Descriptor->InstructionOpcode, ExplicitOperands, Function->registerInfo()); if (!ExplicitValidation) return std::unexpected(ExplicitValidation.error()); - auto DefaultImplicit = Instructions->createDefaultImplicitOperands(*Descriptor); + auto DefaultImplicit = Target->createDefaultImplicitOperands(*Descriptor); if (!DefaultImplicit) return std::unexpected(DefaultImplicit.error()); @@ -463,19 +462,23 @@ Expected MachineInstrBuilder::build() { ImplicitOperands.push_back(&Operand); for (const MachineOperand &Operand : ExtraImplicitOperands) ImplicitOperands.push_back(&Operand); - auto ImplicitValidation = - Instructions->validateImplicitOperands(Descriptor->InstructionOpcode, ImplicitOperands); + auto ImplicitValidation = Target->validateImplicitOperands( + Descriptor->InstructionOpcode, ImplicitOperands, Function->registerInfo()); if (!ImplicitValidation) return std::unexpected(ImplicitValidation.error()); const std::vector Ties = collectOperandTies(); - auto TieValidation = - Instructions->validateOperandTies(Descriptor->InstructionOpcode, ExplicitOperands, Ties); + auto TieValidation = Target->validateOperandTies(Descriptor->InstructionOpcode, ExplicitOperands, + Ties, Function->registerInfo()); if (!TieValidation) return std::unexpected(TieValidation.error()); - auto MemoryValidation = - Instructions->validateMemOperands(Descriptor->InstructionOpcode, MemOperands); + auto EarlyClobberValidation = + Target->validateEarlyClobber(ExplicitOperands, ImplicitOperands, Ties); + if (!EarlyClobberValidation) + return std::unexpected(EarlyClobberValidation.error()); + + auto MemoryValidation = Target->validateMemOperands(Descriptor->InstructionOpcode, MemOperands); if (!MemoryValidation) return std::unexpected(MemoryValidation.error()); @@ -577,7 +580,7 @@ Expected MachineIRBuilder::buildInstr(Opcode InstructionOpc if (InsertBlock == nullptr) { return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder has no insertion point"); } - const InstructionDescriptor *Descriptor = Instructions->descriptor(InstructionOpcode); + const InstructionDescriptor *Descriptor = Target->instructionDescriptor(InstructionOpcode); if (Descriptor == nullptr) { return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder opcode is not registered"); @@ -589,7 +592,7 @@ Expected MachineIRBuilder::buildInstr(Opcode InstructionOpc return makeUnexpected(ErrorCode::InvalidArgument, "machine IR builder insertion cursor is stale"); } - return MachineInstrBuilder(*Function, *Instructions, *Descriptor, *InsertBlock, InsertBefore); + return MachineInstrBuilder(*Function, *Target, *Descriptor, *InsertBlock, InsertBefore); } } // namespace rcc diff --git a/backend/lib/CodeGen/MachineVerifier.cpp b/backend/lib/CodeGen/MachineVerifier.cpp index 0c05a07..b507079 100644 --- a/backend/lib/CodeGen/MachineVerifier.cpp +++ b/backend/lib/CodeGen/MachineVerifier.cpp @@ -26,9 +26,9 @@ namespace { class FunctionVerifier final { public: - FunctionVerifier(const MachineFunction &Function, const InstructionSet &Instructions, + FunctionVerifier(const MachineFunction &Function, const TargetDescription &Target, MachineVerifierOptions Options) noexcept - : Function(Function), Instructions(Instructions), Options(Options) {} + : Function(Function), Target(Target), Options(Options) {} [[nodiscard]] Expected run() { if (Function.name().empty() || !Function.stableID().isValid()) @@ -346,10 +346,10 @@ private: if (!LocalResult) return LocalResult; - const InstructionDescriptor *Descriptor = Instructions.descriptor(Instruction.opcode()); + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Instruction.opcode()); if (Descriptor == nullptr) return fail("live instruction uses an unregistered opcode"); - auto DescriptorResult = Instructions.validateInstruction(Instruction, Function.registerInfo()); + auto DescriptorResult = Target.validateInstruction(Instruction, Function.registerInfo()); if (!DescriptorResult) return failWith("instruction descriptor", DescriptorResult.error()); @@ -466,6 +466,9 @@ private: return fail("block live-in list contains invalid or duplicate entries"); } } + auto TargetLiveInResult = Target.validateBlockLiveIns(*Block); + if (!TargetLiveInResult) + return failWith("block live-ins", TargetLiveInResult.error()); } return {}; } @@ -509,6 +512,9 @@ private: return fail("virtual register has an invalid or duplicate allocation hint"); } } + auto TargetResult = Target.validateRegisterInfo(RegInfo); + if (!TargetResult) + return failWith("target register info", TargetResult.error()); return {}; } @@ -577,7 +583,7 @@ private: } const MachineFunction &Function; - const InstructionSet &Instructions; + const TargetDescription &Target; MachineVerifierOptions Options; std::unordered_set RegisteredBlocks; std::unordered_set LinkedBlocks; @@ -600,9 +606,9 @@ private: } // namespace Expected MachineVerifier::verify(const MachineFunction &Function, - const InstructionSet &Instructions, + const TargetDescription &Target, MachineVerifierOptions Options) { - return FunctionVerifier(Function, Instructions, Options).run(); + return FunctionVerifier(Function, Target, Options).run(); } } // namespace rcc diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp new file mode 100644 index 0000000..3a6ea31 --- /dev/null +++ b/backend/lib/CodeGen/TargetDescription.cpp @@ -0,0 +1,610 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TargetDescription.h" + +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] const OperandDescriptor &descriptorForOperand(const InstructionDescriptor &Descriptor, + std::size_t Index) { + if (Index < Descriptor.Operands.size()) + return Descriptor.Operands[Index]; + return Descriptor.Operands.back(); +} + +[[nodiscard]] std::uint64_t minimumTypeSizeInBits(LLT Type) noexcept { + if (Type.isToken()) + return 0; + const std::uint64_t ScalarSize = Type.scalarBitWidth(); + if (!Type.isVector()) + return ScalarSize; + return ScalarSize * Type.minimumElementCount(); +} + +[[nodiscard]] bool isPureDef(const MachineOperand &Operand) noexcept { + return Operand.isRegister() && Operand.isDef() && !Operand.isUse(); +} + +[[nodiscard]] bool isPureUse(const MachineOperand &Operand) noexcept { + return Operand.isRegister() && Operand.isUse() && !Operand.isDef(); +} + +} // namespace + +Expected TargetDescription::create(InstructionSet Instructions, + TargetRegisterInfo Registers) { + for (const InstructionDescriptor &Instruction : Instructions.descriptors()) { + for (const OperandDescriptor &Operand : Instruction.Operands) { + if (Operand.RegClass && Registers.registerClass(*Operand.RegClass) == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction operand references an unknown target register class"); + } + if (Operand.RegBank && Registers.registerBank(*Operand.RegBank) == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction operand references an unknown target register bank"); + } + if (Operand.RegClass && Operand.RegBank && + !Registers.bankCoversClass(*Operand.RegBank, *Operand.RegClass)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction operand register class is not covered by its bank"); + } + } + + auto ValidateImplicit = + [&Registers](const ImplicitRegisterDescriptor &Implicit) -> Expected { + const PhysicalRegisterDesc *Register = Registers.physicalRegister(Implicit.Reg); + if (Register == nullptr) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "instruction implicit operand references an unknown physical register"); + } + if (Implicit.Renamable && (Register->IsConstant || Register->IsArtificial)) { + return makeUnexpected( + ErrorCode::InvalidArgument, + "renamable implicit operand references a constant or artificial register"); + } + return {}; + }; + for (const ImplicitRegisterDescriptor &Implicit : Instruction.ImplicitDefs) { + auto Validation = ValidateImplicit(Implicit); + if (!Validation) + return std::unexpected(Validation.error()); + } + for (const ImplicitRegisterDescriptor &Implicit : Instruction.ImplicitUses) { + auto Validation = ValidateImplicit(Implicit); + if (!Validation) + return std::unexpected(Validation.error()); + } + for (const ImplicitRegisterDescriptor &Def : Instruction.ImplicitDefs) { + if (!Def.EarlyClobber) + continue; + if (std::ranges::any_of(Instruction.ImplicitUses, + [&Registers, Def](const ImplicitRegisterDescriptor &Use) { + return Registers.regsOverlap(Def.Reg, Use.Reg); + })) { + return makeUnexpected(ErrorCode::InvalidArgument, + "early-clobber implicit definition overlaps an implicit use"); + } + } + } + + return TargetDescription(std::move(Instructions), std::move(Registers)); +} + +Expected TargetDescription::validateVirtualRegister(Register Reg, + const VirtualRegisterInfo &Info) const { + if (!Reg.isVirtual()) { + return makeUnexpected(ErrorCode::InternalError, + "target virtual-register validation received a non-virtual register"); + } + + const RegisterBankDesc *Bank = nullptr; + if (Info.Bank) { + Bank = Registers.registerBank(*Info.Bank); + if (Bank == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register references an unknown target register bank"); + } + } + + const RegisterClassDesc *Class = nullptr; + if (Info.RegClass) { + Class = Registers.registerClass(*Info.RegClass); + if (Class == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register references an unknown target register class"); + } + } + + if (Info.Bank && Info.RegClass && !Registers.bankCoversClass(*Info.Bank, *Info.RegClass)) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register class is not covered by its selected register bank"); + } + + if (Info.Type) { + const std::uint64_t MinimumSize = minimumTypeSizeInBits(*Info.Type); + if (MinimumSize == 0 && (Bank != nullptr || Class != nullptr)) { + return makeUnexpected(ErrorCode::VerificationError, + "token virtual register cannot have a bank or register class"); + } + if (Bank != nullptr && MinimumSize > Bank->MaximumSizeInBits) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register type exceeds its register bank maximum size"); + } + if (Class != nullptr && MinimumSize > Class->SizeInBits) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register type exceeds its register class size"); + } + } + + for (const PhysicalRegister Hint : Info.AllocationHints) { + const PhysicalRegisterDesc *HintDesc = Registers.physicalRegister(Hint); + if (HintDesc == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register allocation hint names an unknown physical register"); + } + if (HintDesc->IsConstant || HintDesc->IsArtificial) { + return makeUnexpected( + ErrorCode::VerificationError, + "virtual register allocation hint names a constant or artificial register"); + } + if (Info.RegClass && !Registers.registerClassContains(*Info.RegClass, Hint)) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register allocation hint is outside its register class"); + } + if (!Info.RegClass && Info.Bank && !Registers.bankContainsRegister(*Info.Bank, Hint)) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register allocation hint is outside its register bank"); + } + } + return {}; +} + +std::optional +TargetDescription::effectiveRegisterClass(const MachineOperand &Operand, + const MachineRegisterInfo &RegInfo) const { + const Register *Reg = Operand.getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return std::nullopt; + + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::nullopt; + const std::optional RegClass = Info->get().RegClass; + if (!RegClass) + return std::nullopt; + if (Operand.subReg().value() == 0) + return RegClass; + return Registers.subRegClass(*RegClass, Operand.subReg()); +} + +Expected TargetDescription::validateTargetOperand(const OperandDescriptor *Descriptor, + const MachineOperand &Operand, + const MachineRegisterInfo &RegInfo) const { + if (const auto *Mask = Operand.getIf(); Mask != nullptr) { + if (!Mask->Mask) { + return makeUnexpected(ErrorCode::VerificationError, + "register-mask operand contains a null mask"); + } + return Registers.validateRegisterMask(*Mask->Mask); + } + + const Register *Reg = Operand.getIf(); + if (Reg == nullptr) + return {}; + if (Reg->isNoRegister()) { + if (Operand.subReg().value() != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "noreg operand cannot carry a subregister index"); + } + if (Operand.registerFlags().has(RegisterOperandFlag::Renamable)) { + return makeUnexpected(ErrorCode::VerificationError, "noreg operand cannot be renamable"); + } + return {}; + } + + if (const auto PhysReg = Reg->physicalRegister()) { + const PhysicalRegister PhysRegValue = *PhysReg; + const PhysicalRegisterDesc *PhysRegDesc = Registers.physicalRegister(PhysRegValue); + if (PhysRegDesc == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "operand references an unknown physical register"); + } + if (Operand.subReg().value() != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register operand cannot carry a subregister index"); + } + if (Descriptor != nullptr && Descriptor->RegClass && + !Registers.registerClassContains(*Descriptor->RegClass, PhysRegValue)) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register operand is outside its required register class"); + } + if (Descriptor != nullptr && Descriptor->RegBank && + !Registers.bankContainsRegister(*Descriptor->RegBank, PhysRegValue)) { + return makeUnexpected(ErrorCode::VerificationError, + "physical register operand is outside its required register bank"); + } + const bool IsReservedOrAlias = std::ranges::any_of( + RegInfo.reservedRegisters(), [this, PhysRegValue](PhysicalRegister Reserved) { + return Registers.regsOverlap(Reserved, PhysRegValue); + }); + if (Operand.registerFlags().has(RegisterOperandFlag::Renamable) && + (IsReservedOrAlias || PhysRegDesc->IsConstant || PhysRegDesc->IsArtificial)) { + return makeUnexpected(ErrorCode::VerificationError, + "fixed physical register operand cannot be renamable"); + } + return {}; + } + + if (Operand.registerFlags().has(RegisterOperandFlag::Renamable)) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register operand cannot be renamable"); + } + + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + auto RegisterValidation = validateVirtualRegister(*Reg, Info->get()); + if (!RegisterValidation) + return std::unexpected(RegisterValidation.error()); + + if (Operand.subReg().value() != 0) { + if (Registers.subRegIndex(Operand.subReg()) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "operand references an unknown subregister index"); + } + const std::optional RegClass = Info->get().RegClass; + if (!RegClass) { + return makeUnexpected(ErrorCode::VerificationError, + "generic virtual register cannot carry a subregister index"); + } + if (!Registers.subRegClass(*RegClass, Operand.subReg())) { + return makeUnexpected( + ErrorCode::VerificationError, + "virtual register class does not support the operand subregister index"); + } + } + + if (Descriptor != nullptr && Descriptor->RegBank && Info->get().Bank != Descriptor->RegBank) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register bank does not match the operand descriptor"); + } + if (Descriptor != nullptr && Descriptor->RegClass) { + const auto EffectiveClass = effectiveRegisterClass(Operand, RegInfo); + if (!EffectiveClass || !Registers.isSubclass(*EffectiveClass, *Descriptor->RegClass)) { + return makeUnexpected(ErrorCode::VerificationError, + "virtual register class does not satisfy the operand descriptor"); + } + } + return {}; +} + +Expected +TargetDescription::validateExplicitOperands(Opcode InstructionOpcode, + std::span Operands, + const MachineRegisterInfo &RegInfo) const { + auto StructuralValidation = + Instructions.validateExplicitOperands(InstructionOpcode, Operands, RegInfo); + if (!StructuralValidation) + return std::unexpected(StructuralValidation.error()); + + const InstructionDescriptor *Descriptor = Instructions.descriptor(InstructionOpcode); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + } + for (std::size_t Index = 0; Index < Operands.size(); ++Index) { + auto TargetValidation = + validateTargetOperand(&descriptorForOperand(*Descriptor, Index), Operands[Index], RegInfo); + if (!TargetValidation) + return std::unexpected(TargetValidation.error()); + } + return {}; +} + +Expected +TargetDescription::validateTieCompatibility(const MachineOperand &Def, const MachineOperand &Use, + const MachineRegisterInfo &RegInfo) const { + const Register *DefReg = Def.getIf(); + const Register *UseReg = Use.getIf(); + if (DefReg == nullptr || UseReg == nullptr) { + return makeUnexpected(ErrorCode::InternalError, + "target tie validation received a non-register operand"); + } + if (DefReg->isNoRegister() || UseReg->isNoRegister()) + return {}; + + const auto DefPhys = DefReg->physicalRegister(); + const auto UsePhys = UseReg->physicalRegister(); + if (DefPhys && UsePhys) { + if (*DefPhys != *UsePhys) { + return makeUnexpected(ErrorCode::VerificationError, + "tied physical register operands must name the same register"); + } + return {}; + } + + const auto DefClass = effectiveRegisterClass(Def, RegInfo); + const auto UseClass = effectiveRegisterClass(Use, RegInfo); + if (DefClass && UseClass && !Registers.registerClassesOverlap(*DefClass, *UseClass)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied virtual register classes have no compatible physical register"); + } + + auto BankFor = [&RegInfo](Register Reg) -> std::optional { + if (!Reg.isVirtual()) + return std::nullopt; + auto Info = RegInfo.virtualRegisterInfo(Reg); + return Info ? Info->get().Bank : std::nullopt; + }; + const auto DefBank = BankFor(*DefReg); + const auto UseBank = BankFor(*UseReg); + + auto ClassIntersectsBank = [this](RegisterClassID ClassID, RegisterBankID BankID) { + const RegisterClassDesc *Class = Registers.registerClass(ClassID); + return Class != nullptr && + std::ranges::any_of(Class->Registers, [this, BankID](PhysicalRegister Reg) { + return Registers.bankContainsRegister(BankID, Reg); + }); + }; + + if (DefPhys && UseClass && !Registers.registerClassContains(*UseClass, *DefPhys)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied physical register is outside the virtual use register class"); + } + if (UsePhys && DefClass && !Registers.registerClassContains(*DefClass, *UsePhys)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied physical register is outside the virtual def register class"); + } + if (DefPhys && UseBank && !Registers.bankContainsRegister(*UseBank, *DefPhys)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied physical register is outside the virtual use register bank"); + } + if (UsePhys && DefBank && !Registers.bankContainsRegister(*DefBank, *UsePhys)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied physical register is outside the virtual def register bank"); + } + if (DefClass && UseBank && !ClassIntersectsBank(*DefClass, *UseBank)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied def register class and use register bank do not intersect"); + } + if (UseClass && DefBank && !ClassIntersectsBank(*UseClass, *DefBank)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied use register class and def register bank do not intersect"); + } + if (!DefClass && !UseClass && DefBank && UseBank && + !Registers.registerBanksOverlap(*DefBank, *UseBank)) { + return makeUnexpected(ErrorCode::VerificationError, + "tied virtual register banks have no compatible physical register"); + } + return {}; +} + +Expected TargetDescription::validateOperandTies( + Opcode InstructionOpcode, std::span ExplicitOperands, + std::span Ties, const MachineRegisterInfo &RegInfo) const { + auto StructuralValidation = + Instructions.validateOperandTies(InstructionOpcode, ExplicitOperands, Ties); + if (!StructuralValidation) + return std::unexpected(StructuralValidation.error()); + + for (const MachineOperandTie Tie : Ties) { + auto Compatibility = validateTieCompatibility(ExplicitOperands[Tie.DefOperand], + ExplicitOperands[Tie.UseOperand], RegInfo); + if (!Compatibility) + return std::unexpected(Compatibility.error()); + } + return {}; +} + +Expected +TargetDescription::validateImplicitOperands(Opcode InstructionOpcode, + std::span ImplicitOperands, + const MachineRegisterInfo &RegInfo) const { + auto StructuralValidation = + Instructions.validateImplicitOperands(InstructionOpcode, ImplicitOperands); + if (!StructuralValidation) + return std::unexpected(StructuralValidation.error()); + + for (const MachineOperand *Operand : ImplicitOperands) { + if (Operand == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "implicit operand sequence contains a null operand"); + } + auto TargetValidation = validateTargetOperand(nullptr, *Operand, RegInfo); + if (!TargetValidation) + return std::unexpected(TargetValidation.error()); + } + return {}; +} + +Expected +TargetDescription::validateEarlyClobber(std::span ExplicitOperands, + std::span ImplicitOperands, + std::span Ties) const { + struct IndexedOperand final { + const MachineOperand *Operand = nullptr; + std::optional ExplicitIndex; + }; + + std::vector Operands; + Operands.reserve(ExplicitOperands.size() + ImplicitOperands.size()); + for (std::size_t Index = 0; Index < ExplicitOperands.size(); ++Index) + Operands.push_back(IndexedOperand{&ExplicitOperands[Index], Index}); + for (const MachineOperand *Operand : ImplicitOperands) + Operands.push_back(IndexedOperand{Operand, std::nullopt}); + + auto AreTied = [Ties](const IndexedOperand &Def, const IndexedOperand &Use) { + if (!Def.ExplicitIndex || !Use.ExplicitIndex) + return false; + return std::ranges::any_of(Ties, [&Def, &Use](MachineOperandTie Tie) { + return Tie.DefOperand == *Def.ExplicitIndex && Tie.UseOperand == *Use.ExplicitIndex; + }); + }; + + for (const IndexedOperand &DefEntry : Operands) { + if (DefEntry.Operand == nullptr) + continue; + const MachineOperand &Def = *DefEntry.Operand; + if (!Def.isDef() || !Def.registerFlags().has(RegisterOperandFlag::EarlyClobber)) + continue; + + const Register *DefReg = Def.getIf(); + if (DefReg == nullptr || DefReg->isNoRegister()) + continue; + for (const IndexedOperand &UseEntry : Operands) { + if (UseEntry.Operand == nullptr || UseEntry.Operand == DefEntry.Operand) + continue; + const MachineOperand &Use = *UseEntry.Operand; + if (!Use.isUse() || AreTied(DefEntry, UseEntry)) + continue; + + const Register *UseReg = Use.getIf(); + if (UseReg == nullptr || UseReg->isNoRegister()) + continue; + if (DefReg->isVirtual() && UseReg->isVirtual() && *DefReg == *UseReg) { + return makeUnexpected(ErrorCode::VerificationError, + "early-clobber virtual definition overlaps an untied use"); + } + + const auto DefPhys = DefReg->physicalRegister(); + const auto UsePhys = UseReg->physicalRegister(); + if (DefPhys && UsePhys && Registers.regsOverlap(*DefPhys, *UsePhys)) { + return makeUnexpected(ErrorCode::VerificationError, + "early-clobber physical definition overlaps an untied use"); + } + } + } + return {}; +} + +Expected TargetDescription::validateInstruction(const MachineInstr &Instruction, + const MachineRegisterInfo &RegInfo) const { + auto StructuralValidation = Instructions.validateInstruction(Instruction, RegInfo); + if (!StructuralValidation) + return std::unexpected(StructuralValidation.error()); + + const auto Operands = Instruction.operands(); + std::size_t ExplicitCount = 0; + while (ExplicitCount < Operands.size() && !Operands[ExplicitCount].isImplicit()) { + ++ExplicitCount; + } + + auto ExplicitValidation = + validateExplicitOperands(Instruction.opcode(), Operands.first(ExplicitCount), RegInfo); + if (!ExplicitValidation) + return std::unexpected(ExplicitValidation.error()); + + std::vector ImplicitOperands; + for (std::size_t Index = ExplicitCount; Index < Operands.size(); ++Index) + ImplicitOperands.push_back(&Operands[Index]); + auto ImplicitValidation = + validateImplicitOperands(Instruction.opcode(), ImplicitOperands, RegInfo); + if (!ImplicitValidation) + return std::unexpected(ImplicitValidation.error()); + + std::vector Ties; + for (std::size_t Index = 0; Index < ExplicitCount; ++Index) { + const MachineOperand &Operand = Operands[Index]; + if (!Operand.tiedOperandIndex() || Index > *Operand.tiedOperandIndex()) { + continue; + } + const std::size_t OtherIndex = *Operand.tiedOperandIndex(); + if (isPureDef(Operand) && isPureUse(Operands[OtherIndex])) { + Ties.push_back(MachineOperandTie{Index, OtherIndex}); + } else { + Ties.push_back(MachineOperandTie{OtherIndex, Index}); + } + } + auto TieValidation = + validateOperandTies(Instruction.opcode(), Operands.first(ExplicitCount), Ties, RegInfo); + if (!TieValidation) + return std::unexpected(TieValidation.error()); + + return validateEarlyClobber(Operands.first(ExplicitCount), ImplicitOperands, Ties); +} + +Expected TargetDescription::validateRegisterInfo(const MachineRegisterInfo &RegInfo) const { + for (const PhysicalRegisterLiveIn &LiveIn : RegInfo.liveIns()) { + if (!Registers.isKnownPhysicalRegister(LiveIn.PhysReg)) { + return makeUnexpected(ErrorCode::VerificationError, + "function live-in names an unknown physical register"); + } + if (!LiveIn.InitialVirtualRegister) + continue; + auto Info = RegInfo.virtualRegisterInfo(*LiveIn.InitialVirtualRegister); + if (!Info) + return std::unexpected(Info.error()); + const std::optional RegClass = Info->get().RegClass; + if (RegClass && !Registers.registerClassContains(*RegClass, LiveIn.PhysReg)) { + return makeUnexpected( + ErrorCode::VerificationError, + "function live-in physical register is outside its initial virtual register class"); + } + const std::optional Bank = Info->get().Bank; + if (Bank && !Registers.bankContainsRegister(*Bank, LiveIn.PhysReg)) { + return makeUnexpected( + ErrorCode::VerificationError, + "function live-in physical register is outside its initial virtual register bank"); + } + } + for (const PhysicalRegister Reg : RegInfo.reservedRegisters()) { + if (!Registers.isKnownPhysicalRegister(Reg)) { + return makeUnexpected(ErrorCode::VerificationError, + "reserved-register list names an unknown physical register"); + } + } + + const auto VirtualRegisters = RegInfo.virtualRegisters(); + for (std::size_t Index = 0; Index < VirtualRegisters.size(); ++Index) { + const VirtualRegisterInfo &Info = VirtualRegisters[Index]; + if (Info.IsTombstone) + continue; + auto Reg = Register::makeVirtual(Index); + if (!Reg) + return std::unexpected(Reg.error()); + auto Validation = validateVirtualRegister(*Reg, Info); + if (!Validation) + return std::unexpected(Validation.error()); + for (const PhysicalRegister Hint : Info.AllocationHints) { + if (std::ranges::any_of(RegInfo.reservedRegisters(), [this, Hint](PhysicalRegister Reserved) { + return Registers.regsOverlap(Reserved, Hint); + })) { + return makeUnexpected( + ErrorCode::VerificationError, + "virtual register allocation hint overlaps a reserved physical register"); + } + } + } + return {}; +} + +Expected TargetDescription::validateBlockLiveIns(const MachineBasicBlock &Block) const { + for (const MachineBasicBlockLiveIn &LiveIn : Block.liveIns()) { + if (!Registers.isKnownPhysicalRegister(LiveIn.PhysReg)) { + return makeUnexpected(ErrorCode::VerificationError, + "block live-in names an unknown physical register"); + } + if (!Registers.isValidLaneMask(LiveIn.PhysReg, LiveIn.Lanes)) { + return makeUnexpected(ErrorCode::VerificationError, + "block live-in lane mask is not valid for its physical register"); + } + } + return {}; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/TargetRegisterInfo.cpp b/backend/lib/CodeGen/TargetRegisterInfo.cpp new file mode 100644 index 0000000..7bd4834 --- /dev/null +++ b/backend/lib/CodeGen/TargetRegisterInfo.cpp @@ -0,0 +1,603 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/TargetRegisterInfo.h" + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace rcc { +namespace { + +[[nodiscard]] std::unexpected invalidDescription(std::string Message) { + return makeUnexpected(ErrorCode::InvalidArgument, + "target register description: " + std::move(Message)); +} + +[[nodiscard]] bool isPowerOfTwo(std::uint32_t Value) noexcept { + return Value != 0 && std::has_single_bit(Value); +} + +template +[[nodiscard]] bool contains(const RangeT &Range, const ValueT &Value) { + return std::ranges::find(Range, Value) != std::ranges::end(Range); +} + +[[nodiscard]] const RegisterUnitLane *findUnit(const PhysicalRegisterDesc &Register, + RegisterUnitID Unit) noexcept { + const auto Position = std::ranges::find(Register.Units, Unit, &RegisterUnitLane::Unit); + return Position == Register.Units.end() ? nullptr : &*Position; +} + +} // namespace + +Expected TargetRegisterInfo::create(TargetRegisterInfoDesc Description) { + if (Description.RegisterUnits.empty() || Description.PhysicalRegisters.empty() || + Description.RegisterClasses.empty() || Description.RegisterBanks.empty()) { + return invalidDescription( + "register units, physical registers, classes, and banks must be nonempty"); + } + + TargetRegisterInfo Result(std::move(Description)); + + std::unordered_set UnitNames; + for (std::size_t Index = 0; Index < Result.Description.RegisterUnits.size(); ++Index) { + const RegisterUnitDesc &Unit = Result.Description.RegisterUnits[Index]; + if (Unit.ID.value() == 0 || Unit.Name.empty()) { + return invalidDescription("register unit requires a nonzero ID and name"); + } + if (!Result.UnitToIndex.emplace(Unit.ID, Index).second || !UnitNames.insert(Unit.Name).second) { + return invalidDescription("register unit IDs and names must be unique"); + } + } + + for (std::size_t Index = 0; Index < Result.Description.PhysicalRegisters.size(); ++Index) { + const PhysicalRegisterDesc &Register = Result.Description.PhysicalRegisters[Index]; + if (!Register.Reg.isValid() || Register.Name.empty()) { + return invalidDescription("physical register requires a valid number and name"); + } + if (!Result.RegisterToIndex.emplace(Register.Reg, Index).second || + !Result.RegisterNameToIndex.emplace(Register.Name, Index).second) { + return invalidDescription("physical register numbers and names must be unique"); + } + } + + std::unordered_set SubRegNames; + for (std::size_t Index = 0; Index < Result.Description.SubRegIndices.size(); ++Index) { + const SubRegIndexDesc &SubReg = Result.Description.SubRegIndices[Index]; + if (SubReg.ID.value() == 0 || SubReg.Name.empty() || SubReg.Lanes.empty() || + SubReg.SizeInBits == 0 || + static_cast(SubReg.OffsetInBits) + SubReg.SizeInBits > + std::numeric_limits::max()) { + return invalidDescription( + "subregister index requires a nonzero ID, name, lanes, and valid bit range"); + } + if (!Result.SubRegIndexToIndex.emplace(SubReg.ID, Index).second || + !SubRegNames.insert(SubReg.Name).second) { + return invalidDescription("subregister index IDs and names must be unique"); + } + } + + std::unordered_set ClassNames; + for (std::size_t Index = 0; Index < Result.Description.RegisterClasses.size(); ++Index) { + const RegisterClassDesc &Class = Result.Description.RegisterClasses[Index]; + if (Class.ID.value() == 0 || Class.Name.empty()) { + return invalidDescription("register class requires a nonzero ID and name"); + } + if (!Result.ClassToIndex.emplace(Class.ID, Index).second || + !ClassNames.insert(Class.Name).second) { + return invalidDescription("register class IDs and names must be unique"); + } + } + + std::unordered_set BankNames; + for (std::size_t Index = 0; Index < Result.Description.RegisterBanks.size(); ++Index) { + const RegisterBankDesc &Bank = Result.Description.RegisterBanks[Index]; + if (Bank.ID.value() == 0 || Bank.Name.empty() || Bank.MaximumSizeInBits == 0) { + return invalidDescription("register bank requires a nonzero ID, name, and maximum size"); + } + if (!Result.BankToIndex.emplace(Bank.ID, Index).second || !BankNames.insert(Bank.Name).second) { + return invalidDescription("register bank IDs and names must be unique"); + } + } + + std::unordered_set ReferencedUnits; + for (const PhysicalRegisterDesc &Register : Result.Description.PhysicalRegisters) { + if (Register.Units.empty()) + return invalidDescription("physical register must reference at least one register unit"); + + std::unordered_set SeenUnits; + LaneMask RegisterLanes; + for (const RegisterUnitLane &Unit : Register.Units) { + if (Result.registerUnit(Unit.Unit) == nullptr || Unit.Lanes.empty() || + !SeenUnits.insert(Unit.Unit).second) { + return invalidDescription( + "physical register has an unknown, empty-lane, or duplicate register unit"); + } + ReferencedUnits.insert(Unit.Unit); + RegisterLanes = RegisterLanes | Unit.Lanes; + } + if (RegisterLanes.empty()) + return invalidDescription("physical register has no addressable lanes"); + } + if (ReferencedUnits.size() != Result.Description.RegisterUnits.size()) + return invalidDescription("every declared register unit must be used by a physical register"); + + const std::size_t RegisterCount = Result.Description.PhysicalRegisters.size(); + std::vector> IsSubRegister(RegisterCount, + std::vector(RegisterCount, false)); + for (const PhysicalSubRegisterDesc &Mapping : Result.Description.PhysicalSubRegisters) { + const PhysicalRegisterDesc *Super = Result.physicalRegister(Mapping.SuperReg); + const PhysicalRegisterDesc *Sub = Result.physicalRegister(Mapping.SubReg); + const SubRegIndexDesc *Index = Result.subRegIndex(Mapping.Index); + if (Super == nullptr || Sub == nullptr || Index == nullptr || + Mapping.SuperReg == Mapping.SubReg) { + return invalidDescription( + "physical subregister mapping references an unknown or identical register"); + } + + const std::uint64_t Key = pairKey(Mapping.SuperReg.number(), Mapping.Index.value()); + if (!Result.SubRegisterMap.emplace(Key, Mapping.SubReg).second) + return invalidDescription("physical subregister mapping key must be unique"); + + LaneMask ProjectedLanes; + for (const RegisterUnitLane &SubUnit : Sub->Units) { + const RegisterUnitLane *SuperUnit = findUnit(*Super, SubUnit.Unit); + if (SuperUnit == nullptr) { + return invalidDescription( + "physical subregister units must be a subset of its superregister units"); + } + ProjectedLanes = ProjectedLanes | SuperUnit->Lanes; + } + if (ProjectedLanes != Index->Lanes) { + return invalidDescription( + "physical subregister units do not match the subregister index lane mask"); + } + + const std::size_t SuperIndex = Result.RegisterToIndex.at(Mapping.SuperReg); + const std::size_t SubIndex = Result.RegisterToIndex.at(Mapping.SubReg); + IsSubRegister[SuperIndex][SubIndex] = true; + } + + for (std::size_t Through = 0; Through < RegisterCount; ++Through) { + for (std::size_t Super = 0; Super < RegisterCount; ++Super) { + if (!IsSubRegister[Super][Through]) + continue; + for (std::size_t Sub = 0; Sub < RegisterCount; ++Sub) + IsSubRegister[Super][Sub] = IsSubRegister[Super][Sub] || IsSubRegister[Through][Sub]; + } + } + for (std::size_t Index = 0; Index < RegisterCount; ++Index) { + if (IsSubRegister[Index][Index]) + return invalidDescription("physical subregister graph must be acyclic"); + } + + Result.SuperRegisters.resize(RegisterCount); + for (std::size_t Sub = 0; Sub < RegisterCount; ++Sub) { + for (std::size_t Super = 0; Super < RegisterCount; ++Super) { + if (IsSubRegister[Super][Sub]) { + Result.SuperRegisters[Sub].push_back(Result.Description.PhysicalRegisters[Super].Reg); + } + } + } + + for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) { + const SubRegIndexDesc *First = Result.subRegIndex(Composition.First); + const SubRegIndexDesc *Second = Result.subRegIndex(Composition.Second); + const SubRegIndexDesc *Composed = Result.subRegIndex(Composition.Result); + if (First == nullptr || Second == nullptr || Composed == nullptr) { + return invalidDescription("subregister composition references an unknown index"); + } + const std::uint64_t ComposedOffset = + static_cast(First->OffsetInBits) + Second->OffsetInBits; + if (static_cast(Second->OffsetInBits) + Second->SizeInBits > First->SizeInBits || + Composed->SizeInBits != Second->SizeInBits || Composed->OffsetInBits != ComposedOffset) { + return invalidDescription("subregister composition has inconsistent bit ranges"); + } + const std::uint64_t Key = pairKey(Composition.First.value(), Composition.Second.value()); + if (!Result.CompositionMap.emplace(Key, Composition.Result).second) + return invalidDescription("subregister composition key must be unique"); + } + + for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) { + for (const PhysicalRegisterDesc &Super : Result.Description.PhysicalRegisters) { + const auto Intermediate = Result.subRegister(Super.Reg, Composition.First); + if (!Intermediate) + continue; + const auto Final = Result.subRegister(*Intermediate, Composition.Second); + if (!Final) + continue; + const auto Composed = Result.subRegister(Super.Reg, Composition.Result); + if (!Composed || *Composed != *Final) { + return invalidDescription( + "subregister composition conflicts with physical subregister mappings"); + } + } + } + + for (const RegisterBankDesc &Bank : Result.Description.RegisterBanks) { + if (Bank.RegisterClasses.empty()) + return invalidDescription("register bank must cover at least one register class"); + + std::unordered_set SeenClasses; + for (const RegisterClassID ClassID : Bank.RegisterClasses) { + const RegisterClassDesc *Class = Result.registerClass(ClassID); + if (Class == nullptr || !SeenClasses.insert(ClassID).second) { + return invalidDescription("register bank has an unknown or duplicate register class"); + } + if (Class->SizeInBits > Bank.MaximumSizeInBits) { + return invalidDescription( + "register bank maximum size is smaller than a covered register class"); + } + } + } + + for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) { + if (Class.Registers.empty() || Class.SizeInBits == 0 || + Class.SpillSizeInBits < Class.SizeInBits || !isPowerOfTwo(Class.SpillAlignmentInBits) || + Class.Lanes.empty()) { + return invalidDescription( + "register class requires members, sizes, power-of-two spill alignment, and lanes"); + } + + std::unordered_set Members; + for (const PhysicalRegister Reg : Class.Registers) { + if (!Result.isKnownPhysicalRegister(Reg) || !Members.insert(Reg).second || + !Result.isValidLaneMask(Reg, Class.Lanes)) { + return invalidDescription( + "register class has an unknown, duplicate, or lane-incompatible member"); + } + } + + std::unordered_set AllocationRegisters; + for (const PhysicalRegister Reg : Class.AllocationOrder) { + if (!Members.contains(Reg) || !AllocationRegisters.insert(Reg).second) { + return invalidDescription( + "register class allocation order must contain unique class members"); + } + } + if ((Class.Allocatable && Class.AllocationOrder.empty()) || + (!Class.Allocatable && !Class.AllocationOrder.empty())) { + return invalidDescription( + "allocatable classes require an allocation order and nonallocatable classes forbid one"); + } + + std::unordered_set SupportedSubRegs; + LaneMask CoveredSubRegLanes; + for (const SubRegIndex SubReg : Class.SupportedSubRegs) { + const SubRegIndexDesc *SubRegDesc = Result.subRegIndex(SubReg); + if (SubRegDesc == nullptr || !SupportedSubRegs.insert(SubReg).second || + !Class.Lanes.contains(SubRegDesc->Lanes)) { + return invalidDescription( + "register class has an unknown, duplicate, or lane-incompatible subregister index"); + } + CoveredSubRegLanes = CoveredSubRegLanes | SubRegDesc->Lanes; + } + if (Class.CoveredBySubRegs && + (Class.SupportedSubRegs.empty() || !CoveredSubRegLanes.contains(Class.Lanes))) { + return invalidDescription( + "subregister-covered class must cover every class lane with supported indices"); + } + + std::unordered_set SuperClasses; + for (const RegisterClassID SuperClass : Class.SuperClasses) { + if (Result.registerClass(SuperClass) == nullptr || SuperClass == Class.ID || + !SuperClasses.insert(SuperClass).second) { + return invalidDescription("register class has an unknown, self, or duplicate superclass"); + } + Result.SubclassRelations.insert(pairKey(Class.ID.value(), SuperClass.value())); + } + Result.SubclassRelations.insert(pairKey(Class.ID.value(), Class.ID.value())); + + if (Result.registerBank(Class.DefaultBank) == nullptr || + !Result.bankCoversClass(Class.DefaultBank, Class.ID)) { + return invalidDescription( + "register class default bank must exist and explicitly cover the class"); + } + } + + bool RelationsChanged = true; + while (RelationsChanged) { + RelationsChanged = false; + for (const RegisterClassDesc &Candidate : Result.Description.RegisterClasses) { + for (const RegisterClassDesc &Intermediate : Result.Description.RegisterClasses) { + if (!Result.isSubclass(Candidate.ID, Intermediate.ID)) + continue; + for (const RegisterClassDesc &Required : Result.Description.RegisterClasses) { + if (!Result.isSubclass(Intermediate.ID, Required.ID)) + continue; + RelationsChanged |= + Result.SubclassRelations.insert(pairKey(Candidate.ID.value(), Required.ID.value())) + .second; + } + } + } + } + + for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) { + for (const RegisterClassDesc &Other : Result.Description.RegisterClasses) { + if (Class.ID != Other.ID && Result.isSubclass(Class.ID, Other.ID) && + Result.isSubclass(Other.ID, Class.ID)) { + return invalidDescription("register class hierarchy must be acyclic"); + } + } + for (const RegisterClassID SuperID : Class.SuperClasses) { + const RegisterClassDesc *Super = Result.registerClass(SuperID); + if (Super == nullptr || Class.SizeInBits != Super->SizeInBits || + Class.SpillSizeInBits != Super->SpillSizeInBits || + Class.SpillAlignmentInBits != Super->SpillAlignmentInBits || + !std::ranges::all_of(Class.Registers, [Super](PhysicalRegister Reg) { + return contains(Super->Registers, Reg); + })) { + return invalidDescription( + "register class must be storage-compatible with each declared superclass"); + } + } + } + + for (const SubRegClassMapping &Mapping : Result.Description.SubRegClassMappings) { + const RegisterClassDesc *Source = Result.registerClass(Mapping.SourceClass); + const SubRegIndexDesc *Index = Result.subRegIndex(Mapping.Index); + const RegisterClassDesc *Mapped = Result.registerClass(Mapping.ResultClass); + if (Source == nullptr || Index == nullptr || Mapped == nullptr || + !contains(Source->SupportedSubRegs, Mapping.Index)) { + return invalidDescription( + "subregister class mapping references an unknown or unsupported entity"); + } + if (Mapped->SizeInBits != Index->SizeInBits) { + return invalidDescription("subregister class mapping result size must match its index size"); + } + if (static_cast(Index->OffsetInBits) + Index->SizeInBits > Source->SizeInBits) { + return invalidDescription("subregister class mapping index exceeds its source class size"); + } + + const std::uint64_t Key = pairKey(Mapping.SourceClass.value(), Mapping.Index.value()); + if (!Result.SubRegClassMap.emplace(Key, Mapping.ResultClass).second) { + return invalidDescription("subregister class mapping key must be unique"); + } + for (const PhysicalRegister SuperReg : Source->Registers) { + const auto SubReg = Result.subRegister(SuperReg, Mapping.Index); + if (!SubReg || !Result.registerClassContains(Mapping.ResultClass, *SubReg)) { + return invalidDescription("subregister class mapping does not cover every source register"); + } + } + } + + for (const RegisterClassDesc &Class : Result.Description.RegisterClasses) { + for (const SubRegIndex SubReg : Class.SupportedSubRegs) { + if (!Result.subRegClass(Class.ID, SubReg)) { + return invalidDescription( + "every supported class subregister index requires a class mapping"); + } + } + } + + for (const SubRegIndexComposition &Composition : Result.Description.SubRegCompositions) { + for (const RegisterClassDesc &Source : Result.Description.RegisterClasses) { + const auto Intermediate = Result.subRegClass(Source.ID, Composition.First); + if (!Intermediate) + continue; + const auto Final = Result.subRegClass(*Intermediate, Composition.Second); + if (!Final) + continue; + const auto Composed = Result.subRegClass(Source.ID, Composition.Result); + if (!Composed || !Result.isSubclass(*Final, *Composed)) { + return invalidDescription("subregister composition conflicts with register class mappings"); + } + } + } + + for (const PhysicalRegisterDesc &Register : Result.Description.PhysicalRegisters) { + if (std::ranges::none_of(Result.Description.RegisterClasses, + [&Register](const RegisterClassDesc &Class) { + return contains(Class.Registers, Register.Reg); + })) { + return invalidDescription( + "every physical register must belong to at least one register class"); + } + } + + Result.Aliases.resize(RegisterCount); + for (std::size_t Left = 0; Left < RegisterCount; ++Left) { + for (std::size_t Right = 0; Right < RegisterCount; ++Right) { + if (Left != Right && Result.regsOverlap(Result.Description.PhysicalRegisters[Left].Reg, + Result.Description.PhysicalRegisters[Right].Reg)) { + Result.Aliases[Left].push_back(Result.Description.PhysicalRegisters[Right].Reg); + } + } + } + + return Result; +} + +const RegisterUnitDesc *TargetRegisterInfo::registerUnit(RegisterUnitID ID) const noexcept { + const auto Position = UnitToIndex.find(ID); + return Position == UnitToIndex.end() ? nullptr : &Description.RegisterUnits[Position->second]; +} + +const PhysicalRegisterDesc * +TargetRegisterInfo::physicalRegister(PhysicalRegister Reg) const noexcept { + const auto Position = RegisterToIndex.find(Reg); + return Position == RegisterToIndex.end() ? nullptr + : &Description.PhysicalRegisters[Position->second]; +} + +const PhysicalRegisterDesc * +TargetRegisterInfo::physicalRegister(std::string_view Name) const noexcept { + const auto Position = RegisterNameToIndex.find(std::string(Name)); + return Position == RegisterNameToIndex.end() ? nullptr + : &Description.PhysicalRegisters[Position->second]; +} + +const SubRegIndexDesc *TargetRegisterInfo::subRegIndex(SubRegIndex Index) const noexcept { + const auto Position = SubRegIndexToIndex.find(Index); + return Position == SubRegIndexToIndex.end() ? nullptr + : &Description.SubRegIndices[Position->second]; +} + +const RegisterClassDesc *TargetRegisterInfo::registerClass(RegisterClassID ID) const noexcept { + const auto Position = ClassToIndex.find(ID); + return Position == ClassToIndex.end() ? nullptr : &Description.RegisterClasses[Position->second]; +} + +const RegisterBankDesc *TargetRegisterInfo::registerBank(RegisterBankID ID) const noexcept { + const auto Position = BankToIndex.find(ID); + return Position == BankToIndex.end() ? nullptr : &Description.RegisterBanks[Position->second]; +} + +LaneMask TargetRegisterInfo::registerLaneMask(PhysicalRegister Reg) const noexcept { + const PhysicalRegisterDesc *Register = physicalRegister(Reg); + if (Register == nullptr) + return {}; + + LaneMask Result; + for (const RegisterUnitLane &Unit : Register->Units) + Result = Result | Unit.Lanes; + return Result; +} + +bool TargetRegisterInfo::isValidLaneMask(PhysicalRegister Reg, LaneMask Lanes) const noexcept { + if (physicalRegister(Reg) == nullptr || Lanes.empty()) + return false; + if (Lanes == LaneMask::all()) + return true; + return registerLaneMask(Reg).contains(Lanes); +} + +bool TargetRegisterInfo::regsOverlap(PhysicalRegister Left, PhysicalRegister Right) const noexcept { + const PhysicalRegisterDesc *LeftDesc = physicalRegister(Left); + const PhysicalRegisterDesc *RightDesc = physicalRegister(Right); + if (LeftDesc == nullptr || RightDesc == nullptr) + return false; + + return std::ranges::any_of(LeftDesc->Units, [RightDesc](const RegisterUnitLane &Unit) { + return findUnit(*RightDesc, Unit.Unit) != nullptr; + }); +} + +std::span TargetRegisterInfo::aliases(PhysicalRegister Reg) const noexcept { + const auto Position = RegisterToIndex.find(Reg); + if (Position == RegisterToIndex.end()) + return {}; + return Aliases[Position->second]; +} + +std::optional TargetRegisterInfo::subRegister(PhysicalRegister SuperReg, + SubRegIndex Index) const noexcept { + const auto Position = SubRegisterMap.find(pairKey(SuperReg.number(), Index.value())); + if (Position == SubRegisterMap.end()) + return std::nullopt; + return Position->second; +} + +bool TargetRegisterInfo::isSubRegister(PhysicalRegister SuperReg, + PhysicalRegister SubReg) const noexcept { + const auto Position = RegisterToIndex.find(SubReg); + if (Position == RegisterToIndex.end()) + return false; + return contains(SuperRegisters[Position->second], SuperReg); +} + +std::span +TargetRegisterInfo::superRegisters(PhysicalRegister Reg) const noexcept { + const auto Position = RegisterToIndex.find(Reg); + if (Position == RegisterToIndex.end()) + return {}; + return SuperRegisters[Position->second]; +} + +std::optional +TargetRegisterInfo::composeSubRegIndices(SubRegIndex First, SubRegIndex Second) const noexcept { + const auto Position = CompositionMap.find(pairKey(First.value(), Second.value())); + if (Position == CompositionMap.end()) + return std::nullopt; + return Position->second; +} + +bool TargetRegisterInfo::registerClassContains(RegisterClassID Class, + PhysicalRegister Reg) const noexcept { + const RegisterClassDesc *ClassDesc = registerClass(Class); + return ClassDesc != nullptr && contains(ClassDesc->Registers, Reg); +} + +bool TargetRegisterInfo::isSubclass(RegisterClassID Candidate, + RegisterClassID Required) const noexcept { + return SubclassRelations.contains(pairKey(Candidate.value(), Required.value())); +} + +bool TargetRegisterInfo::registerClassesOverlap(RegisterClassID Left, + RegisterClassID Right) const noexcept { + const RegisterClassDesc *LeftClass = registerClass(Left); + const RegisterClassDesc *RightClass = registerClass(Right); + if (LeftClass == nullptr || RightClass == nullptr) + return false; + return std::ranges::any_of(LeftClass->Registers, [RightClass](PhysicalRegister Reg) { + return contains(RightClass->Registers, Reg); + }); +} + +std::optional TargetRegisterInfo::subRegClass(RegisterClassID Source, + SubRegIndex Index) const noexcept { + const auto Position = SubRegClassMap.find(pairKey(Source.value(), Index.value())); + if (Position == SubRegClassMap.end()) + return std::nullopt; + return Position->second; +} + +bool TargetRegisterInfo::bankCoversClass(RegisterBankID Bank, + RegisterClassID Class) const noexcept { + const RegisterBankDesc *BankDesc = registerBank(Bank); + return BankDesc != nullptr && contains(BankDesc->RegisterClasses, Class); +} + +bool TargetRegisterInfo::bankContainsRegister(RegisterBankID Bank, + PhysicalRegister Reg) const noexcept { + const RegisterBankDesc *BankDesc = registerBank(Bank); + if (BankDesc == nullptr) + return false; + return std::ranges::any_of(BankDesc->RegisterClasses, [this, Reg](RegisterClassID Class) { + return registerClassContains(Class, Reg); + }); +} + +bool TargetRegisterInfo::registerBanksOverlap(RegisterBankID Left, + RegisterBankID Right) const noexcept { + const RegisterBankDesc *LeftBank = registerBank(Left); + const RegisterBankDesc *RightBank = registerBank(Right); + if (LeftBank == nullptr || RightBank == nullptr) + return false; + return std::ranges::any_of(Description.PhysicalRegisters, + [this, Left, Right](const PhysicalRegisterDesc &Register) { + return bankContainsRegister(Left, Register.Reg) && + bankContainsRegister(Right, Register.Reg); + }); +} + +Expected TargetRegisterInfo::validateRegisterMask(const RegisterMask &Mask) const { + constexpr std::uint64_t BitsPerWord = 64; + for (std::size_t WordIndex = 0; WordIndex < Mask.words().size(); ++WordIndex) { + std::uint64_t Word = Mask.words()[WordIndex]; + while (Word != 0) { + const std::uint64_t BitIndex = static_cast(std::countr_zero(Word)); + const std::uint64_t RegisterNumber = + static_cast(WordIndex) * BitsPerWord + BitIndex; + const auto Reg = PhysicalRegister::create(RegisterNumber); + if (!Reg || !isKnownPhysicalRegister(*Reg)) { + return makeUnexpected(ErrorCode::VerificationError, + "register mask preserves an unknown physical register"); + } + Word &= Word - 1; + } + } + return {}; +} + +} // namespace rcc -- cgit v1.2.3