diff options
Diffstat (limited to 'backend/lib/CodeGen/InstructionDescriptor.cpp')
| -rw-r--r-- | backend/lib/CodeGen/InstructionDescriptor.cpp | 769 |
1 files changed, 769 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/InstructionDescriptor.cpp b/backend/lib/CodeGen/InstructionDescriptor.cpp new file mode 100644 index 0000000..027f738 --- /dev/null +++ b/backend/lib/CodeGen/InstructionDescriptor.cpp @@ -0,0 +1,769 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/InstructionDescriptor.h" + +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" + +#include <algorithm> +#include <cstddef> +#include <cstdint> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] bool isRegisterOnly(const OperandKindSet &Kinds) noexcept { + OperandKindSet RegisterKind{MachineOperand::Kind::Register}; + return Kinds == RegisterKind; +} + +[[nodiscard]] bool isDefRole(RegisterOperandRole Role) noexcept { + return Role == RegisterOperandRole::Def || Role == RegisterOperandRole::DefUse; +} + +[[nodiscard]] bool isUseRole(RegisterOperandRole Role) noexcept { + return Role == RegisterOperandRole::Use || Role == RegisterOperandRole::DefUse; +} + +[[nodiscard]] bool formsDefUsePair(RegisterOperandRole Left, RegisterOperandRole Right) noexcept { + return (Left == RegisterOperandRole::Def && Right == RegisterOperandRole::Use) || + (Left == RegisterOperandRole::Use && Right == RegisterOperandRole::Def); +} + +[[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(); +} + +[[nodiscard]] Expected<void> validateDescriptorStructure(const InstructionDescriptor &Descriptor) { + if (!Descriptor.InstructionOpcode.isValid()) + return makeUnexpected(ErrorCode::InvalidArgument, "instruction descriptor opcode is invalid"); + if (Descriptor.Name.empty()) + return makeUnexpected(ErrorCode::InvalidArgument, "instruction descriptor name is empty"); + if (Descriptor.NumExplicitDefs > Descriptor.Operands.size()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction descriptor explicit def count is out of range"); + } + + bool SawOptional = false; + std::optional<std::size_t> VariadicBegin; + std::optional<std::size_t> VariadicEnd; + for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) { + const OperandDescriptor &Operand = Descriptor.Operands[Index]; + if (Operand.Kinds.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "operand descriptor must accept at least one operand kind"); + } + + const bool IsRegister = Operand.Kinds.contains(MachineOperand::Kind::Register); + if (IsRegister != (Operand.RegisterRole != RegisterOperandRole::None)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register-capable operand descriptor must declare a register role"); + } + if (isDefRole(Operand.RegisterRole) && !isRegisterOnly(Operand.Kinds)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register definition descriptor must accept only registers"); + } + if (!IsRegister && + (Operand.RegClass || Operand.RegBank || Operand.EarlyClobber || Operand.AllowSubReg)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "non-register operand descriptor has register constraints"); + } + if (Operand.TypeConstraint) { + if (!isRegisterOnly(Operand.Kinds) || Operand.TypeConstraint->Kinds.empty() || + Operand.TypeConstraint->Kinds.contains(LowLevelType::Kind::Invalid)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "typed operand descriptor requires a nonempty register type set"); + } + } + if (Operand.EarlyClobber && !isDefRole(Operand.RegisterRole)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "early-clobber operand descriptor must define a register"); + } + if (Descriptor.Variadic && Operand.Optional) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic instruction descriptor cannot contain optional operands"); + } + if (Operand.Optional) + SawOptional = true; + else if (SawOptional && !Operand.VariadicGroup) { + return makeUnexpected(ErrorCode::InvalidArgument, + "optional operand descriptors must form a trailing suffix"); + } + + if (Operand.VariadicGroup && (Operand.Optional || Operand.DefaultTiedOperand)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic operand descriptor cannot be optional or have a default tie"); + } + if (Operand.VariadicGroup) { + if (!Descriptor.Variadic) { + return makeUnexpected(ErrorCode::InvalidArgument, + "non-variadic instruction descriptor has a variadic group"); + } + if (!VariadicBegin) + VariadicBegin = Index; + VariadicEnd = Index + 1; + } else if (VariadicEnd) { + const bool LaterGroup = + std::ranges::any_of(Descriptor.Operands.begin() + static_cast<std::ptrdiff_t>(Index), + Descriptor.Operands.end(), [](const OperandDescriptor &Candidate) { + return Candidate.VariadicGroup; + }); + if (LaterGroup) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic operand group descriptors must be contiguous"); + } + } + } + + if (Descriptor.Variadic && !VariadicBegin) { + return makeUnexpected(ErrorCode::InvalidArgument, + "variadic instruction descriptor requires a variadic group"); + } + if (!Descriptor.Variadic && Descriptor.MinimumVariadicRepetitions != 0) { + return makeUnexpected(ErrorCode::InvalidArgument, + "non-variadic instruction has a minimum variadic repetition count"); + } + + bool SawUse = false; + std::size_t MinimumDefs = 0; + for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) { + const OperandDescriptor &Operand = Descriptor.Operands[Index]; + const std::size_t Repetitions = + Operand.VariadicGroup ? Descriptor.MinimumVariadicRepetitions : 1; + for (std::size_t Repeat = 0; Repeat < Repetitions; ++Repeat) { + if (isDefRole(Operand.RegisterRole)) { + if (SawUse) { + return makeUnexpected(ErrorCode::InvalidArgument, + "register definition appears after an instruction use"); + } + ++MinimumDefs; + } else { + SawUse = true; + } + } + } + if (Descriptor.NumExplicitDefs != MinimumDefs) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction descriptor explicit def count does not match its shape"); + } + + for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) { + const OperandDescriptor &Operand = Descriptor.Operands[Index]; + if (!Operand.DefaultTiedOperand) + continue; + const std::size_t OtherIndex = *Operand.DefaultTiedOperand; + if (OtherIndex >= Descriptor.Operands.size() || OtherIndex == Index || + Descriptor.Operands[OtherIndex].DefaultTiedOperand != Index) { + return makeUnexpected(ErrorCode::InvalidArgument, + "default operand tie must be reciprocal and in range"); + } + if (Operand.Optional || Descriptor.Operands[OtherIndex].Optional || + !isRegisterOnly(Operand.Kinds) || !isRegisterOnly(Descriptor.Operands[OtherIndex].Kinds) || + !formsDefUsePair(Operand.RegisterRole, Descriptor.Operands[OtherIndex].RegisterRole)) { + return makeUnexpected(ErrorCode::InvalidArgument, + "default operand tie must connect required register def and use"); + } + } + + std::unordered_set<NamedOperandID> OperandNames; + for (const OperandDescriptor &Operand : Descriptor.Operands) { + if (Operand.Name && !OperandNames.insert(*Operand.Name).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction descriptor has duplicate named operands"); + } + } + + std::unordered_set<PhysicalRegister> ImplicitDefs; + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) { + if (!Implicit.Reg.isValid() || !ImplicitDefs.insert(Implicit.Reg).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "implicit definitions must name unique physical registers"); + } + } + std::unordered_set<PhysicalRegister> ImplicitUses; + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) { + if (!Implicit.Reg.isValid() || Implicit.EarlyClobber || + !ImplicitUses.insert(Implicit.Reg).second) { + return makeUnexpected(ErrorCode::InvalidArgument, + "implicit uses must name unique physical registers and cannot " + "early-clobber"); + } + } + + const bool IsBranch = Descriptor.Flags.has(InstructionFlag::Branch); + const bool IsTerminator = Descriptor.Flags.has(InstructionFlag::Terminator); + if ((IsBranch || Descriptor.Flags.has(InstructionFlag::Return) || + Descriptor.Flags.has(InstructionFlag::Barrier) || + Descriptor.Flags.has(InstructionFlag::IndirectBranch)) && + !IsTerminator) { + return makeUnexpected(ErrorCode::InvalidArgument, + "branch, return, and barrier descriptors must be terminators"); + } + if (Descriptor.Flags.has(InstructionFlag::IndirectBranch) && !IsBranch) { + return makeUnexpected(ErrorCode::InvalidArgument, + "indirect branch descriptor must also be a branch"); + } + + const bool IsPseudo = Descriptor.Flags.has(InstructionFlag::Pseudo); + const bool IsMeta = Descriptor.Flags.has(InstructionFlag::Meta); + if (IsMeta && (!IsPseudo || Descriptor.Flags.has(InstructionFlag::ProducesCode))) { + return makeUnexpected(ErrorCode::InvalidArgument, + "meta instruction must be a non-emitting pseudo"); + } + if (!IsPseudo && Descriptor.Owner != PseudoOwner::None) { + return makeUnexpected(ErrorCode::InvalidArgument, + "non-pseudo instruction cannot have a pseudo owner"); + } + if (IsPseudo && !IsMeta && Descriptor.Owner == PseudoOwner::None) { + return makeUnexpected(ErrorCode::InvalidArgument, + "executable pseudo must declare its expansion owner"); + } + if (Descriptor.Flags.has(InstructionFlag::TerminalEmission) && + (!IsPseudo || Descriptor.Owner != PseudoOwner::AsmPrinter || + !Descriptor.Flags.has(InstructionFlag::ProducesCode))) { + return makeUnexpected(ErrorCode::InvalidArgument, + "terminal emission pseudo must produce code and be owned by AsmPrinter"); + } + if (Descriptor.RequiresMemoryOperands && !Descriptor.Flags.has(InstructionFlag::MayLoad) && + !Descriptor.Flags.has(InstructionFlag::MayStore)) { + return makeUnexpected(ErrorCode::InvalidArgument, "MMO requirement needs mayLoad or mayStore"); + } + + return {}; +} + +struct OperandShape final { + std::size_t VariadicBegin = 0; + std::size_t VariadicEnd = 0; + std::size_t Repetitions = 0; +}; + +[[nodiscard]] Expected<OperandShape> resolveOperandShape(const InstructionDescriptor &Descriptor, + std::size_t OperandCount) { + if (!Descriptor.Variadic) { + std::size_t RequiredCount = Descriptor.Operands.size(); + while (RequiredCount != 0 && Descriptor.Operands[RequiredCount - 1].Optional) + --RequiredCount; + if (OperandCount < RequiredCount || OperandCount > Descriptor.Operands.size()) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction has an invalid explicit operand count"); + } + return OperandShape{}; + } + + const auto Begin = std::ranges::find_if( + Descriptor.Operands, [](const OperandDescriptor &Operand) { return Operand.VariadicGroup; }); + const auto End = std::ranges::find_if_not( + Begin, Descriptor.Operands.end(), + [](const OperandDescriptor &Operand) { return Operand.VariadicGroup; }); + const std::size_t VariadicBegin = + static_cast<std::size_t>(std::distance(Descriptor.Operands.begin(), Begin)); + const std::size_t VariadicEnd = + static_cast<std::size_t>(std::distance(Descriptor.Operands.begin(), End)); + const std::size_t GroupSize = VariadicEnd - VariadicBegin; + const std::size_t FixedCount = Descriptor.Operands.size() - GroupSize; + if (GroupSize == 0 || OperandCount < FixedCount) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction has an invalid variadic operand count"); + } + const std::size_t VariableCount = OperandCount - FixedCount; + if (VariableCount % GroupSize != 0 || + VariableCount / GroupSize < Descriptor.MinimumVariadicRepetitions) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction has an incomplete or undersized variadic operand group"); + } + return OperandShape{VariadicBegin, VariadicEnd, VariableCount / GroupSize}; +} + +[[nodiscard]] const OperandDescriptor &descriptorForOperand(const InstructionDescriptor &Descriptor, + const OperandShape &Shape, + std::size_t Index) { + if (!Descriptor.Variadic) + return Descriptor.Operands[Index]; + if (Index < Shape.VariadicBegin) + return Descriptor.Operands[Index]; + const std::size_t GroupSize = Shape.VariadicEnd - Shape.VariadicBegin; + const std::size_t VariableCount = Shape.Repetitions * GroupSize; + if (Index < Shape.VariadicBegin + VariableCount) { + return Descriptor.Operands[Shape.VariadicBegin + (Index - Shape.VariadicBegin) % GroupSize]; + } + return Descriptor.Operands[Shape.VariadicEnd + (Index - Shape.VariadicBegin - VariableCount)]; +} + +} // namespace + +Expected<std::vector<const OperandDescriptor *>> +resolveExplicitOperandDescriptors(const InstructionDescriptor &Descriptor, + std::size_t OperandCount) { + auto Shape = resolveOperandShape(Descriptor, OperandCount); + if (!Shape) + return std::unexpected(Shape.error()); + std::vector<const OperandDescriptor *> Result; + Result.reserve(OperandCount); + for (std::size_t Index = 0; Index < OperandCount; ++Index) + Result.push_back(&descriptorForOperand(Descriptor, *Shape, Index)); + return Result; +} + +OperandKindSet::OperandKindSet(std::initializer_list<MachineOperand::Kind> Kinds) noexcept { + for (const MachineOperand::Kind Kind : Kinds) + add(Kind); +} + +LowLevelTypeKindSet::LowLevelTypeKindSet(std::initializer_list<LowLevelType::Kind> Kinds) noexcept { + for (const LowLevelType::Kind Kind : Kinds) + add(Kind); +} + +InstructionFlags::InstructionFlags(std::initializer_list<InstructionFlag> Flags) noexcept { + for (const InstructionFlag Flag : Flags) + set(Flag); +} + +Expected<InstructionSet> +InstructionSet::create(std::vector<InstructionDescriptor> Descriptors, + std::vector<ImmediatePredicate> ImmediatePredicates) { + if (Descriptors.empty()) { + return makeUnexpected(ErrorCode::InvalidArgument, + "instruction set requires at least one descriptor"); + } + + InstructionSet Result(std::move(Descriptors), std::move(ImmediatePredicates)); + + std::unordered_set<std::string> PredicateNames; + for (std::size_t Index = 0; Index < Result.ImmediatePredicates.size(); ++Index) { + const ImmediatePredicate &Predicate = Result.ImmediatePredicates[Index]; + if (Predicate.Name.empty() || !Predicate.Predicate) { + return makeUnexpected(ErrorCode::InvalidArgument, + "immediate predicate requires a name and callable"); + } + if (!Result.PredicateToIndex.emplace(Predicate.ID, Index).second) { + return makeUnexpected(ErrorCode::InvalidArgument, "duplicate immediate predicate ID"); + } + if (!PredicateNames.insert(Predicate.Name).second) { + return makeUnexpected(ErrorCode::InvalidArgument, "duplicate immediate predicate name"); + } + } + + for (std::size_t Index = 0; Index < Result.Descriptors.size(); ++Index) { + const InstructionDescriptor &Descriptor = Result.Descriptors[Index]; + const auto Validation = validateDescriptorStructure(Descriptor); + if (!Validation) + return std::unexpected(Validation.error()); + if (!Result.OpcodeToIndex.emplace(Descriptor.InstructionOpcode, Index).second) + return makeUnexpected(ErrorCode::InvalidArgument, "duplicate instruction opcode"); + if (!Result.NameToIndex.emplace(Descriptor.Name, Index).second) + return makeUnexpected(ErrorCode::InvalidArgument, "duplicate instruction name"); + + for (const OperandDescriptor &Operand : Descriptor.Operands) { + if (Operand.ImmediatePredicate && + Result.immediatePredicate(*Operand.ImmediatePredicate) == nullptr) { + return makeUnexpected(ErrorCode::InvalidArgument, + "operand descriptor references an unknown immediate predicate"); + } + } + } + + return Result; +} + +const InstructionDescriptor *InstructionSet::descriptor(Opcode InstructionOpcode) const noexcept { + const auto Position = OpcodeToIndex.find(InstructionOpcode); + if (Position == OpcodeToIndex.end()) + return nullptr; + return &Descriptors[Position->second]; +} + +const InstructionDescriptor *InstructionSet::descriptor(std::string_view Name) const noexcept { + const auto Position = NameToIndex.find(std::string(Name)); + if (Position == NameToIndex.end()) + return nullptr; + return &Descriptors[Position->second]; +} + +Expected<void> InstructionSet::validateExplicitOperands(const InstructionDescriptor &Descriptor, + std::span<const MachineOperand> Operands, + const MachineRegisterInfo &RegInfo) const { + auto Shape = resolveOperandShape(Descriptor, Operands.size()); + if (!Shape) + return std::unexpected(Shape.error()); + + bool SawUse = false; + std::unordered_map<std::uint16_t, LowLevelType> EqualityGroups; + for (std::size_t Index = 0; Index < Operands.size(); ++Index) { + const MachineOperand &Operand = Operands[Index]; + if (Operand.isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "explicit operand sequence contains an implicit register"); + } + const OperandDescriptor &OperandDesc = descriptorForOperand(Descriptor, *Shape, Index); + const auto Validation = validateOperand(OperandDesc, Operand, RegInfo); + if (!Validation) { + return makeUnexpected(Validation.error().code(), + "operand " + std::to_string(Index) + " of '" + Descriptor.Name + + "': " + std::string(Validation.error().message())); + } + if (Operand.isRegister()) { + if (isDefRole(OperandDesc.RegisterRole)) { + if (SawUse) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction register definition appears after a use"); + } + } else { + SawUse = true; + } + } else { + SawUse = true; + } + + if (!OperandDesc.TypeConstraint) + continue; + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) { + return makeUnexpected(ErrorCode::VerificationError, + "typed instruction operand must use a virtual register"); + } + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + const std::optional<LowLevelType> &RegisterType = Info->get().Type; + if (!RegisterType) { + return makeUnexpected(ErrorCode::VerificationError, + "typed instruction operand virtual register has no LowLevelType"); + } + const LowLevelType Type = RegisterType.value(); + if (!OperandDesc.TypeConstraint->Kinds.contains(Type.kind())) { + return makeUnexpected( + ErrorCode::VerificationError, + "instruction operand LowLevelType kind is not permitted by its descriptor"); + } + if (OperandDesc.TypeConstraint->EqualityGroup) { + const auto [Position, Inserted] = + EqualityGroups.emplace(*OperandDesc.TypeConstraint->EqualityGroup, Type); + if (!Inserted && Position->second != Type) { + return makeUnexpected( + ErrorCode::VerificationError, + "instruction operands in one LowLevelType group have different types"); + } + } + } + if (Descriptor.VerifyExplicitOperands != nullptr) + return Descriptor.VerifyExplicitOperands(Descriptor.InstructionOpcode, Operands, RegInfo); + return {}; +} + +Expected<void> InstructionSet::validateExplicitOperands(Opcode InstructionOpcode, + std::span<const MachineOperand> Operands, + const MachineRegisterInfo &RegInfo) const { + const InstructionDescriptor *Descriptor = descriptor(InstructionOpcode); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + } + return validateExplicitOperands(*Descriptor, Operands, RegInfo); +} + +Expected<void> InstructionSet::validateOperandTies(const InstructionDescriptor &Descriptor, + std::span<const MachineOperand> ExplicitOperands, + std::span<const MachineOperandTie> Ties) const { + std::vector<std::optional<std::size_t>> Partners(ExplicitOperands.size()); + for (const MachineOperandTie Tie : Ties) { + if (Tie.DefOperand >= ExplicitOperands.size() || Tie.UseOperand >= ExplicitOperands.size() || + Tie.DefOperand == Tie.UseOperand || !isPureDef(ExplicitOperands[Tie.DefOperand]) || + !isPureUse(ExplicitOperands[Tie.UseOperand])) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction tie must connect an in-range pure register def and use"); + } + if (Partners[Tie.DefOperand] || Partners[Tie.UseOperand]) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction operand participates in duplicate or conflicting ties"); + } + Partners[Tie.DefOperand] = Tie.UseOperand; + Partners[Tie.UseOperand] = Tie.DefOperand; + } + + for (std::size_t Index = 0; Index < Descriptor.Operands.size(); ++Index) { + const OperandDescriptor &Operand = Descriptor.Operands[Index]; + if (Operand.DefaultTiedOperand && + (Index >= Partners.size() || Partners[Index] != Operand.DefaultTiedOperand)) { + return makeUnexpected(ErrorCode::VerificationError, + "required descriptor tie is not materialized"); + } + } + return {}; +} + +Expected<void> InstructionSet::validateOperandTies(Opcode InstructionOpcode, + std::span<const MachineOperand> ExplicitOperands, + std::span<const MachineOperandTie> Ties) const { + const InstructionDescriptor *Descriptor = descriptor(InstructionOpcode); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + } + return validateOperandTies(*Descriptor, ExplicitOperands, Ties); +} + +Expected<void> InstructionSet::validateImplicitOperands( + const InstructionDescriptor &Descriptor, + std::span<const MachineOperand *const> ImplicitOperands) const { + const std::size_t DefaultCount = Descriptor.ImplicitDefs.size() + Descriptor.ImplicitUses.size(); + if (ImplicitOperands.size() < DefaultCount || + (!Descriptor.AllowExtraImplicitOperands && ImplicitOperands.size() != DefaultCount)) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction implicit operand count does not match its descriptor"); + } + + std::size_t Index = 0; + auto ValidateDefault = [&](const ImplicitRegisterDescriptor &Implicit, + bool IsDef) -> Expected<void> { + const MachineOperand *Operand = ImplicitOperands[Index++]; + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || Reg->physicalRegister() != Implicit.Reg || Operand->isDef() != IsDef || + Operand->isUse() == IsDef || !Operand->isImplicit() || + Operand->registerFlags().has(RegisterOperandFlag::EarlyClobber) != Implicit.EarlyClobber || + Operand->registerFlags().has(RegisterOperandFlag::Renamable) != Implicit.Renamable) { + return makeUnexpected(ErrorCode::VerificationError, + "default implicit register operand does not match its descriptor"); + } + return {}; + }; + + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) { + auto Validation = ValidateDefault(Implicit, true); + if (!Validation) + return std::unexpected(Validation.error()); + } + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) { + auto Validation = ValidateDefault(Implicit, false); + if (!Validation) + return std::unexpected(Validation.error()); + } + for (; Index < ImplicitOperands.size(); ++Index) { + const MachineOperand *Operand = ImplicitOperands[Index]; + if (Operand == nullptr || !Operand->isRegister() || !Operand->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "dynamic implicit operand must be an implicit register"); + } + } + return {}; +} + +Expected<void> InstructionSet::validateImplicitOperands( + Opcode InstructionOpcode, std::span<const MachineOperand *const> ImplicitOperands) const { + const InstructionDescriptor *Descriptor = descriptor(InstructionOpcode); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + } + return validateImplicitOperands(*Descriptor, ImplicitOperands); +} + +Expected<void> +InstructionSet::validateMemOperands(const InstructionDescriptor &Descriptor, + std::span<const MachineMemOperand *const> MemOperands) const { + const bool MayLoad = Descriptor.Flags.has(InstructionFlag::MayLoad); + const bool MayStore = Descriptor.Flags.has(InstructionFlag::MayStore); + if (Descriptor.RequiresMemoryOperands && MemOperands.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "memory instruction is missing MachineMemOperand"); + } + if (!MayLoad && !MayStore && !MemOperands.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "non-memory instruction carries MachineMemOperand"); + } + for (const MachineMemOperand *MemOperand : MemOperands) { + if (MemOperand == nullptr || (MemOperand->isLoad() && !MayLoad) || + (MemOperand->isStore() && !MayStore)) { + return makeUnexpected(ErrorCode::VerificationError, + "MachineMemOperand access conflicts with instruction descriptor"); + } + } + return {}; +} + +Expected<void> +InstructionSet::validateMemOperands(Opcode InstructionOpcode, + std::span<const MachineMemOperand *const> MemOperands) const { + const InstructionDescriptor *Descriptor = descriptor(InstructionOpcode); + if (Descriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + } + return validateMemOperands(*Descriptor, MemOperands); +} + +Expected<void> InstructionSet::validateOperand(const OperandDescriptor &Descriptor, + const MachineOperand &Operand, + const MachineRegisterInfo &RegInfo) const { + if (!Descriptor.Kinds.contains(Operand.kind())) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction operand kind does not match its descriptor"); + } + if (!Descriptor.AllowAnyTargetFlags && + (Operand.targetFlags() & ~Descriptor.AllowedTargetFlags) != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction operand uses unregistered target flags"); + } + + if (Operand.isRegister()) { + const bool IsDef = Operand.isDef(); + const bool IsUse = Operand.isUse(); + const bool ExpectedDef = isDefRole(Descriptor.RegisterRole); + const bool ExpectedUse = isUseRole(Descriptor.RegisterRole); + if (Descriptor.RegisterRole == RegisterOperandRole::Any) { + if (!IsDef && !IsUse) { + return makeUnexpected(ErrorCode::VerificationError, + "unclassified register operand must define or use its register"); + } + } else if (IsDef != ExpectedDef || IsUse != ExpectedUse) { + return makeUnexpected(ErrorCode::VerificationError, + "register operand def/use role does not match its descriptor"); + } + if (Operand.registerFlags().has(RegisterOperandFlag::EarlyClobber) != Descriptor.EarlyClobber) { + return makeUnexpected(ErrorCode::VerificationError, + "register operand early-clobber does not match its descriptor"); + } + if (!Descriptor.AllowSubReg && Operand.subReg().value() != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "register operand has a disallowed subregister index"); + } + + const Register *Reg = Operand.getIf<Register>(); + if (Reg == nullptr) { + return makeUnexpected(ErrorCode::InternalError, "register operand has inconsistent storage"); + } + if (Reg->isVirtual()) { + auto Info = RegInfo.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + } + } + + if (Descriptor.ImmediatePredicate && Operand.kind() == MachineOperand::Kind::Immediate) { + const ImmediatePredicate *Predicate = immediatePredicate(*Descriptor.ImmediatePredicate); + if (Predicate == nullptr || !Predicate->Predicate(Operand)) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction operand fails its immediate predicate"); + } + } + + return {}; +} + +Expected<void> InstructionSet::validateInstruction(const MachineInstr &Instruction, + const MachineRegisterInfo &RegInfo) const { + const InstructionDescriptor *Descriptor = descriptor(Instruction.opcode()); + if (Descriptor == nullptr) + return makeUnexpected(ErrorCode::VerificationError, "instruction opcode is not registered"); + + const auto AllOperands = Instruction.operands(); + std::size_t ExplicitCount = 0; + while (ExplicitCount < AllOperands.size() && !AllOperands[ExplicitCount].isImplicit()) + ++ExplicitCount; + for (std::size_t Index = ExplicitCount; Index < AllOperands.size(); ++Index) { + if (!AllOperands[Index].isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "explicit operand appears after implicit operands"); + } + } + + const auto ExplicitValidation = + validateExplicitOperands(*Descriptor, AllOperands.first(ExplicitCount), RegInfo); + if (!ExplicitValidation) + return std::unexpected(ExplicitValidation.error()); + + std::vector<MachineOperandTie> Ties; + for (std::size_t Index = 0; Index < ExplicitCount; ++Index) { + const MachineOperand &Operand = AllOperands[Index]; + if (!Operand.tiedOperandIndex()) + continue; + const std::size_t OtherIndex = *Operand.tiedOperandIndex(); + if (OtherIndex >= ExplicitCount || AllOperands[OtherIndex].tiedOperandIndex() != Index) { + return makeUnexpected(ErrorCode::VerificationError, + "instruction operand tie is out of range or not reciprocal"); + } + if (Index > OtherIndex) + continue; + if (isPureUse(Operand) && isPureDef(AllOperands[OtherIndex])) + Ties.push_back(MachineOperandTie{OtherIndex, Index}); + else + Ties.push_back(MachineOperandTie{Index, OtherIndex}); + } + + auto TieValidation = validateOperandTies(*Descriptor, AllOperands.first(ExplicitCount), Ties); + if (!TieValidation) + return std::unexpected(TieValidation.error()); + + std::vector<const MachineOperand *> ImplicitOperands; + ImplicitOperands.reserve(AllOperands.size() - ExplicitCount); + for (std::size_t Index = ExplicitCount; Index < AllOperands.size(); ++Index) { + if (AllOperands[Index].tiedOperandIndex()) { + return makeUnexpected(ErrorCode::VerificationError, + "implicit register operand cannot participate in a tie"); + } + ImplicitOperands.push_back(&AllOperands[Index]); + } + + auto ImplicitValidation = validateImplicitOperands(*Descriptor, ImplicitOperands); + if (!ImplicitValidation) + return std::unexpected(ImplicitValidation.error()); + auto MemoryValidation = validateMemOperands(*Descriptor, Instruction.memOperands()); + if (!MemoryValidation) + return std::unexpected(MemoryValidation.error()); + if (Descriptor->VerifyInstructionSemantics != nullptr) + return Descriptor->VerifyInstructionSemantics(Instruction, RegInfo); + return {}; +} + +Expected<std::vector<MachineOperand>> +InstructionSet::createDefaultImplicitOperands(const InstructionDescriptor &Descriptor) const { + std::vector<MachineOperand> Result; + Result.reserve(Descriptor.ImplicitDefs.size() + Descriptor.ImplicitUses.size()); + + auto AppendImplicit = [&Result](const ImplicitRegisterDescriptor &Implicit, + bool IsDef) -> Expected<void> { + RegisterOperandFlags Flags{ + IsDef ? RegisterOperandFlag::Define : RegisterOperandFlag::Use, + RegisterOperandFlag::Implicit, + }; + if (Implicit.EarlyClobber) + Flags.set(RegisterOperandFlag::EarlyClobber); + if (Implicit.Renamable) + Flags.set(RegisterOperandFlag::Renamable); + + auto Operand = MachineOperand::registerOperand(Register::fromPhysical(Implicit.Reg), Flags); + if (!Operand) + return std::unexpected(Operand.error()); + Result.push_back(std::move(*Operand)); + return {}; + }; + + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitDefs) { + auto AppendResult = AppendImplicit(Implicit, true); + if (!AppendResult) + return std::unexpected(AppendResult.error()); + } + for (const ImplicitRegisterDescriptor &Implicit : Descriptor.ImplicitUses) { + auto AppendResult = AppendImplicit(Implicit, false); + if (!AppendResult) + return std::unexpected(AppendResult.error()); + } + return Result; +} + +const ImmediatePredicate * +InstructionSet::immediatePredicate(ImmediatePredicateID ID) const noexcept { + const auto Position = PredicateToIndex.find(ID); + if (Position == PredicateToIndex.end()) + return nullptr; + return &ImmediatePredicates[Position->second]; +} + +} // namespace rcc |