diff options
Diffstat (limited to 'backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp')
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp | 1611 |
1 files changed, 1611 insertions, 0 deletions
diff --git a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp new file mode 100644 index 0000000..88fcc24 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp @@ -0,0 +1,1611 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" + +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/Utils.h" +#include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineIRBuilder.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineMemOperand.h" +#include "rcc/CodeGen/MachineOperand.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include <algorithm> +#include <charconv> +#include <cstddef> +#include <cstdint> +#include <iterator> +#include <limits> +#include <optional> +#include <ranges> +#include <string> +#include <utility> +#include <vector> + +namespace rcc { +namespace { + +[[nodiscard]] Expected<std::optional<LowLevelType>> operandType(const MachineInstr &Instruction, + const MachineFunction &Function, + std::size_t OperandIndex) { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return std::optional<LowLevelType>{}; + auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + return Info->get().Type; +} + +[[nodiscard]] Expected<bool> matchesType(const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + auto Type = operandType(Instruction, Function, Step.OperandIndex); + if (!Type) + return std::unexpected(Type.error()); + if (!*Type) + return false; + + const auto Kind = static_cast<GIMatchTypeKind>(Step.Auxiliary); + switch (Kind) { + case GIMatchTypeKind::Any: + return Step.Value == 0 || (*Type)->scalarBitWidth() == Step.Value; + case GIMatchTypeKind::Scalar: + return (*Type)->isCategoryNeutralScalar() && (*Type)->scalarBitWidth() == Step.Value; + case GIMatchTypeKind::Pointer: + return (*Type)->isPointer() && (*Type)->scalarBitWidth() == Step.Value; + } + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid type predicate"); +} + +[[nodiscard]] bool matchesInstructionFlags(const MachineInstr &Instruction, + const GIMatchTableInstruction &Step) noexcept { + return (Instruction.flags().rawValue() & Step.Value) == Step.Value; +} + +[[nodiscard]] Expected<bool> matchesMemorySize(const MachineInstr &Instruction, + const GIMatchTableInstruction &Step) { + if (Step.Value == 0) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid memory size"); + } + if (Step.OperandIndex >= Instruction.memOperands().size()) + return false; + const MachineMemOperand *Memory = Instruction.memOperands()[Step.OperandIndex]; + if (Memory == nullptr) + return false; + const MemorySize Size = Memory->description().Size; + return Size.isKnown() && !Size.isScalable() && Size.minimumBytes() == Step.Value; +} + +[[nodiscard]] Expected<bool> matchesBank(const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return false; + auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + const VirtualRegisterInfo &RegisterInfo = Info->get(); + if (!RegisterInfo.Bank) + return false; + return RegisterInfo.Bank->value() == Step.Value; +} + +[[nodiscard]] Expected<bool> matchesClass(const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return false; + auto Info = Function.registerInfo().virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + const VirtualRegisterInfo &RegisterInfo = Info->get(); + if (!RegisterInfo.RegClass) + return false; + return RegisterInfo.RegClass->value() == Step.Value; +} + +[[nodiscard]] Expected<bool> matchesIntegerPredicate(const MachineInstr &Instruction, + std::size_t OperandIndex, + std::uint32_t PredicateValue) { + if (PredicateValue >= static_cast<std::uint32_t>(IntegerPredicate::Count)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid integer predicate"); + } + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const auto *Predicate = Operand == nullptr ? nullptr : Operand->getIf<PredicateOperand>(); + const IntegerPredicate *Integer = Predicate == nullptr ? nullptr : Predicate->integerPredicate(); + return Integer != nullptr && static_cast<std::uint32_t>(*Integer) == PredicateValue; +} + +[[nodiscard]] Expected<bool> matchesFloatingPredicate(const MachineInstr &Instruction, + std::size_t OperandIndex, + std::uint32_t PredicateValue) { + if (PredicateValue >= static_cast<std::uint32_t>(FloatingPredicate::Count)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid floating predicate"); + } + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const auto *Predicate = Operand == nullptr ? nullptr : Operand->getIf<PredicateOperand>(); + const FloatingPredicate *Floating = + Predicate == nullptr ? nullptr : Predicate->floatingPredicate(); + return Floating != nullptr && static_cast<std::uint32_t>(*Floating) == PredicateValue; +} + +[[nodiscard]] std::optional<std::int64_t> immediateValue(const MachineOperand &Operand) { + if (const std::int64_t *Immediate = Operand.getIf<std::int64_t>()) + return *Immediate; + const auto *Integer = Operand.getIf<IntegerImmediateOperand>(); + if (Integer == nullptr) + return std::optional<std::int64_t>{}; + const std::string Text = Integer->Value.toSignedDecimal(); + std::int64_t Parsed = 0; + const auto [End, Error] = std::from_chars(Text.data(), Text.data() + Text.size(), Parsed); + if (Error != std::errc{} || End != Text.data() + Text.size()) + return std::optional<std::int64_t>{}; + return Parsed; +} + +[[nodiscard]] Expected<std::optional<std::int64_t>> +operandDefConstantValue(const MachineInstr &Instruction, const MachineFunction &Function, + std::size_t OperandIndex) { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return std::optional<std::int64_t>{}; + const MachineInstr *Definition = Function.registerInfo().getVRegDef(*Reg); + if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT)) + return std::optional<std::int64_t>{}; + const MachineOperand *Value = Definition->operandAt(1); + if (Value == nullptr) + return std::optional<std::int64_t>{}; + return immediateValue(*Value); +} + +[[nodiscard]] Expected<std::optional<std::int64_t>> +operandOrDefConstantValue(const MachineInstr &Instruction, const MachineFunction &Function, + std::size_t OperandIndex) { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + if (Operand == nullptr) + return std::optional<std::int64_t>{}; + if (const auto Value = immediateValue(*Operand)) + return Value; + return operandDefConstantValue(Instruction, Function, OperandIndex); +} + +[[nodiscard]] Expected<bool> matchesConstantRanges(const GIMatchTable &Table, std::size_t First, + std::size_t Count, + std::optional<std::int64_t> Value) { + if (Count == 0 || First > Table.ConstantRanges.size() || + Count > Table.ConstantRanges.size() - First) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid constant range"); + } + if (!Value) + return false; + for (std::size_t Index = First; Index < First + Count; ++Index) { + const GIMatchTableConstantRange &Range = Table.ConstantRanges[Index]; + if (Range.Minimum > Range.Maximum) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an inverted constant range"); + } + if (*Value >= Range.Minimum && *Value <= Range.Maximum) + return true; + } + return false; +} + +[[nodiscard]] Expected<bool> matchesOperandImmediateRanges(const GIMatchTable &Table, + const MachineInstr &Instruction, + const GIMatchTableInstruction &Step) { + const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); + const std::optional<std::int64_t> Value = + Operand == nullptr ? std::optional<std::int64_t>{} : immediateValue(*Operand); + return matchesConstantRanges(Table, Step.Value, Step.Auxiliary, Value); +} + +[[nodiscard]] Expected<bool> matchesOperandDefConstantRanges(const GIMatchTable &Table, + const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + auto Value = operandDefConstantValue(Instruction, Function, Step.OperandIndex); + if (!Value) + return std::unexpected(Value.error()); + return matchesConstantRanges(Table, Step.Value, Step.Auxiliary, *Value); +} + +[[nodiscard]] const MachineInstr *operandDefinition(const MachineInstr &Instruction, + const MachineFunction &Function, + std::size_t OperandIndex) { + const MachineOperand *Operand = Instruction.operandAt(OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + return Reg != nullptr && Reg->isVirtual() ? Function.registerInfo().getVRegDef(*Reg) : nullptr; +} + +[[nodiscard]] Expected<bool> matchesOperandDefOpcode(const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + if (Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid def-use opcode"); + const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex); + return Definition != nullptr && Definition->opcode().value() == Step.Value; +} + +[[nodiscard]] Expected<bool> +matchesOperandDefIntegerPredicate(const MachineInstr &Instruction, const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex); + if (Definition == nullptr) + return false; + return matchesIntegerPredicate(*Definition, Step.Auxiliary, Step.Value); +} + +[[nodiscard]] Expected<bool> +matchesOperandDefOperandConstantRanges(const GIMatchTable &Table, const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + if (Step.Immediate <= 0 || + static_cast<std::uint64_t>(Step.Immediate) > std::numeric_limits<std::uint32_t>::max()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid def-use constant range count"); + } + const std::size_t Count = static_cast<std::size_t>(Step.Immediate); + const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex); + if (Definition == nullptr) + return false; + auto Value = operandOrDefConstantValue(*Definition, Function, Step.Auxiliary); + if (!Value) + return std::unexpected(Value.error()); + return matchesConstantRanges(Table, Step.Value, Count, *Value); +} + +[[nodiscard]] Expected<RegisterOperandFlags> registerFlagsFromRaw(std::uint32_t Raw) { + constexpr std::uint32_t ValidBits = + (std::uint32_t{1} << static_cast<std::uint16_t>(RegisterOperandFlag::Count)) - 1U; + if ((Raw & ~ValidBits) != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has invalid register flags"); + } + RegisterOperandFlags Flags; + for (std::uint16_t Index = 0; Index < static_cast<std::uint16_t>(RegisterOperandFlag::Count); + ++Index) { + if ((Raw & (std::uint32_t{1} << Index)) != 0) + Flags.set(static_cast<RegisterOperandFlag>(Index)); + } + return Flags; +} + +struct MatchedRule final { + struct CapturedOperand final { + std::uint32_t ID = 0; + MachineOperand Operand; + }; + + struct Temporary final { + std::uint32_t ID = 0; + LowLevelType Type; + }; + + struct RenderedOperand final { + enum class Kind : std::uint8_t { + RootOperand, + ComplexOperand, + CapturedOperand, + PhysicalRegister, + Temporary, + CapturedImmediate, + CapturedTypeBits, + Immediate, + }; + + Kind SourceKind = Kind::RootOperand; + std::uint32_t Value = 0; + std::uint32_t Flags = 0; + std::string_view ComplexRenderer; + GIMatchImmediateTransform Transform = GIMatchImmediateTransform::Identity; + std::int64_t Immediate = 0; + }; + + struct Instruction final { + Opcode ResultOpcode; + bool ReplacesRoot = false; + std::vector<RenderedOperand> Operands; + }; + + std::vector<Temporary> Temporaries; + std::vector<CapturedOperand> CapturedOperands; + std::vector<Instruction> Instructions; + std::vector<Register> EraseOperandDefinitions; + std::optional<std::uint32_t> ReplaceRootCapture; + std::uint32_t ClearInstructionFlags = 0; +}; + +[[nodiscard]] bool hasTemporary(const MatchedRule &Rule, std::uint32_t ID) { + return std::ranges::any_of(Rule.Temporaries, [ID](const MatchedRule::Temporary &Temporary) { + return Temporary.ID == ID; + }); +} + +[[nodiscard]] bool hasCapturedOperand(const MatchedRule &Rule, std::uint32_t ID) { + return std::ranges::any_of( + Rule.CapturedOperands, + [ID](const MatchedRule::CapturedOperand &Capture) { return Capture.ID == ID; }); +} + +[[nodiscard]] bool hasRootInstruction(const MatchedRule &Rule) { + return std::ranges::any_of(Rule.Instructions, &MatchedRule::Instruction::ReplacesRoot); +} + +[[nodiscard]] const MatchedRule::CapturedOperand * +findCapturedOperand(const std::vector<MatchedRule::CapturedOperand> &Captures, std::uint32_t ID) { + const auto Position = std::ranges::find(Captures, ID, &MatchedRule::CapturedOperand::ID); + return Position == Captures.end() ? nullptr : &*Position; +} + +template <typename TargetPredicateMatcher> +[[nodiscard]] Expected<std::optional<MatchedRule>> +matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target, + TargetPredicateMatcher &&MatchesTargetPredicate) { + const std::size_t First = Rule.FirstInstruction; + const std::size_t Count = Rule.InstructionCount; + if (First > Table.Instructions.size() || Count > Table.Instructions.size() - First) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table rule has an invalid instruction range"); + } + + MatchedRule Result; + bool Applying = false; + bool Complete = false; + for (std::size_t Index = First; Index < First + Count; ++Index) { + const GIMatchTableInstruction &Step = Table.Instructions[Index]; + switch (Step.Opcode) { + case GIMatchTableOpcode::CheckOpcode: + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + if (Instruction.opcode().value() != Step.Value) + return std::optional<MatchedRule>{}; + break; + case GIMatchTableOpcode::CheckOperandType: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesType(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckInstructionFlag: + if (Applying || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid instruction flag predicate"); + if (!matchesInstructionFlags(Instruction, Step)) + return std::optional<MatchedRule>{}; + break; + case GIMatchTableOpcode::ClearInstructionFlags: + if (!Applying || Complete || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid flag clear action"); + if (Result.ClearInstructionFlags != 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table clears instruction flags twice"); + Result.ClearInstructionFlags = Step.Value; + break; + case GIMatchTableOpcode::CheckOperandBank: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesBank(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandClass: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesClass(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckIntegerPredicate: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesIntegerPredicate(Instruction, Step.OperandIndex, Step.Value); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckFloatingPredicate: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesFloatingPredicate(Instruction, Step.OperandIndex, Step.Value); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckMemorySize: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesMemorySize(Instruction, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckTargetPredicate: { + if (Applying || Step.Symbol.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid target predicate"); + } + auto Matched = MatchesTargetPredicate(Step.Symbol, Instruction, Function, Target); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandImmediateRanges: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesOperandImmediateRanges(Table, Instruction, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandDefConstantRanges: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesOperandDefConstantRanges(Table, Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandDefOpcode: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesOperandDefOpcode(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandDefIntegerPredicate: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesOperandDefIntegerPredicate(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CheckOperandDefOperandConstantRanges: { + if (Applying) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after an action"); + } + auto Matched = matchesOperandDefOperandConstantRanges(Table, Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional<MatchedRule>{}; + break; + } + case GIMatchTableOpcode::CaptureDefOperand: { + if (Applying || Complete || Step.Value == 0 || hasCapturedOperand(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid def-use capture"); + } + const MachineInstr *Definition = operandDefinition(Instruction, Function, Step.OperandIndex); + const MachineOperand *Operand = + Definition == nullptr ? nullptr : Definition->operandAt(Step.Auxiliary); + if (Operand == nullptr || Operand->isImplicit()) + return std::optional<MatchedRule>{}; + Result.CapturedOperands.push_back({ + .ID = Step.Value, + .Operand = Operand->cloneDetached(), + }); + break; + } + case GIMatchTableOpcode::CreateTemporary: { + if (Complete || Step.Value == 0 || hasTemporary(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid temporary"); + } + auto Type = operandType(Instruction, Function, Step.OperandIndex); + if (!Type) + return std::unexpected(Type.error()); + if (!*Type) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table temporary has no type source"); + } + Applying = true; + Result.Temporaries.push_back({ + .ID = Step.Value, + .Type = **Type, + }); + break; + } + case GIMatchTableOpcode::CreateTemporaryType: { + if (Complete || Step.Value == 0 || hasTemporary(Result, Step.Value) || + Step.Auxiliary != static_cast<std::uint32_t>(GIMatchTypeKind::Scalar) || + Step.Immediate <= 0 || + static_cast<std::uint64_t>(Step.Immediate) > LowLevelType::MaxBitWidth) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid explicit temporary type"); + } + auto Type = + LowLevelType::makeCategoryNeutralScalar(static_cast<std::uint64_t>(Step.Immediate)); + if (!Type) + return std::unexpected(Type.error()); + Applying = true; + Result.Temporaries.push_back({.ID = Step.Value, .Type = *Type}); + break; + } + case GIMatchTableOpcode::MutateOpcode: + if (Complete || Step.Value == 0 || hasRootInstruction(Result)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid root mutation"); + } + Applying = true; + Result.Instructions.push_back({ + .ResultOpcode = Opcode::fromValue(Step.Value), + .ReplacesRoot = true, + .Operands = {}, + }); + break; + case GIMatchTableOpcode::BuildInstruction: + if (Complete || Step.Value == 0) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid instruction action"); + } + Applying = true; + Result.Instructions.push_back({ + .ResultOpcode = Opcode::fromValue(Step.Value), + .ReplacesRoot = false, + .Operands = {}, + }); + break; + case GIMatchTableOpcode::RenderOperand: + if (Complete || Result.Instructions.empty() || + Instruction.operandAt(Step.OperandIndex) == nullptr || + Instruction.operandAt(Step.OperandIndex)->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid operand renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::RootOperand, + .Value = Step.OperandIndex, + .ComplexRenderer = {}, + }); + break; + case GIMatchTableOpcode::RenderComplexOperand: + if (Complete || Result.Instructions.empty() || Step.Symbol.empty() || + Instruction.operandAt(Step.OperandIndex) == nullptr || + Instruction.operandAt(Step.OperandIndex)->isImplicit()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid complex operand renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::ComplexOperand, + .Value = Step.OperandIndex, + .ComplexRenderer = Step.Symbol, + }); + break; + case GIMatchTableOpcode::RenderCapturedOperand: + if (Complete || Result.Instructions.empty() || Step.Value == 0 || + !hasCapturedOperand(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid captured operand renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedOperand, + .Value = Step.Value, + .ComplexRenderer = {}, + }); + break; + case GIMatchTableOpcode::RenderCapturedTypeBits: + if (Complete || Result.Instructions.empty() || Step.Value == 0 || + !hasCapturedOperand(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid captured type renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedTypeBits, + .Value = Step.Value, + .ComplexRenderer = {}, + }); + break; + case GIMatchTableOpcode::RenderPhysicalRegister: + if (Complete || Result.Instructions.empty() || Step.Value == 0) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid physical register renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::PhysicalRegister, + .Value = Step.Value, + .Flags = Step.Auxiliary, + .ComplexRenderer = {}, + }); + break; + case GIMatchTableOpcode::RenderTemporary: + if (Complete || Result.Instructions.empty() || !hasTemporary(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid temporary renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::Temporary, + .Value = Step.Value, + .Flags = Step.Auxiliary, + .ComplexRenderer = {}, + }); + break; + case GIMatchTableOpcode::RenderCapturedImmediate: { + if (Complete || Result.Instructions.empty() || + Step.Value > static_cast<std::uint32_t>(GIMatchImmediateTransform::PlusOne)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid captured immediate renderer"); + } + auto Value = operandDefConstantValue(Instruction, Function, Step.OperandIndex); + if (!Value) + return std::unexpected(Value.error()); + if (!*Value) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table lost a captured constant"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedImmediate, + .Value = Step.OperandIndex, + .ComplexRenderer = {}, + .Transform = static_cast<GIMatchImmediateTransform>(Step.Value), + }); + break; + } + case GIMatchTableOpcode::RenderImmediate: + if (Complete || Result.Instructions.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid immediate renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::Immediate, + .ComplexRenderer = {}, + .Immediate = Step.Immediate, + }); + break; + case GIMatchTableOpcode::ReplaceRootWithCapturedOperand: + if (Table.Kind != GIMatchTableKind::Combiner || Complete || Applying || + !Result.Instructions.empty() || Step.Value == 0 || + !hasCapturedOperand(Result, Step.Value) || Result.ReplaceRootCapture) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid root replacement action"); + } + Applying = true; + Result.ReplaceRootCapture = Step.Value; + break; + case GIMatchTableOpcode::EraseOperandDefinition: { + if (Complete || (Result.Instructions.empty() && !Result.ReplaceRootCapture)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid erased definition"); + } + const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table erases a non-virtual operand definition"); + } + Result.EraseOperandDefinitions.push_back(*Reg); + break; + } + case GIMatchTableOpcode::Complete: + if (Complete || (Result.Instructions.empty() && !Result.ReplaceRootCapture) || + Index + 1 != First + Count) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid completion action"); + } + Complete = true; + break; + } + } + + if (!Complete || + (Table.Kind == GIMatchTableKind::Selection && + (Result.Instructions.empty() || !hasRootInstruction(Result))) || + (Table.Kind == GIMatchTableKind::Combiner && Result.Instructions.empty() && + !Result.ReplaceRootCapture) || + (Table.Kind == GIMatchTableKind::Combiner && !Result.Instructions.empty() && + Result.ReplaceRootCapture)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table rule does not complete rendering"); + } + return std::optional<MatchedRule>(std::move(Result)); +} + +template <typename ComplexRenderer> +[[nodiscard]] Expected<bool> +complexRenderersMatch(const MatchedRule &Rule, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target, + ComplexRenderer &&RenderComplex) { + for (const MatchedRule::Instruction &Action : Rule.Instructions) { + for (const MatchedRule::RenderedOperand &Rendered : Action.Operands) { + if (Rendered.SourceKind != MatchedRule::RenderedOperand::Kind::ComplexOperand) + continue; + auto Complex = + RenderComplex(Rendered.ComplexRenderer, Instruction, Function, Target, Rendered.Value); + if (!Complex) + return std::unexpected(Complex.error()); + if (!*Complex) + return false; + } + } + return true; +} + +[[nodiscard]] std::size_t explicitOperandCount(const MachineInstr &Instruction) noexcept { + std::size_t Count = 0; + while (Count < Instruction.operandCount() && !Instruction.operandAt(Count)->isImplicit()) + ++Count; + return Count; +} + +[[nodiscard]] Expected<void> +restoreInstruction(MachineInstr &Instruction, Opcode OriginalOpcode, + const std::vector<MachineOperand> &OriginalOperands, + const std::vector<std::pair<std::size_t, std::size_t>> &Ties) { + while (Instruction.operandCount() != 0) { + auto Erased = Instruction.eraseOperand(Instruction.operandCount() - 1U); + if (!Erased) + return std::unexpected(Erased.error()); + } + auto RestoredOpcode = Instruction.setOpcode(OriginalOpcode); + if (!RestoredOpcode) + return std::unexpected(RestoredOpcode.error()); + for (const MachineOperand &Operand : OriginalOperands) { + auto Added = Instruction.addOperand(Operand.cloneDetached()); + if (!Added) + return std::unexpected(Added.error()); + } + for (const auto [DefIndex, UseIndex] : Ties) { + auto Tied = Instruction.tieOperands(DefIndex, UseIndex); + if (!Tied) + return std::unexpected(Tied.error()); + } + return {}; +} + +struct MaterializedTemporary final { + std::uint32_t ID = 0; + Register Reg; +}; + +struct RegisterConstraintSnapshot final { + Register Reg; + std::optional<RegisterBankID> Bank; + std::optional<RegisterClassID> RegClass; +}; + +[[nodiscard]] const MaterializedTemporary * +findTemporary(const std::vector<MaterializedTemporary> &Temporaries, std::uint32_t ID) { + const auto Position = std::ranges::find(Temporaries, ID, &MaterializedTemporary::ID); + return Position == Temporaries.end() ? nullptr : &*Position; +} + +[[nodiscard]] Expected<void> +eraseTemporaries(MachineRegisterInfo &Registers, + const std::vector<MaterializedTemporary> &Temporaries) { + for (auto Iterator = Temporaries.rbegin(); Iterator != Temporaries.rend(); ++Iterator) { + if (!Registers.isKnownVirtualRegister(Iterator->Reg)) + continue; + auto Erased = Registers.eraseVirtualRegister(Iterator->Reg); + if (!Erased) + return std::unexpected(Erased.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> eraseRegisters(MachineRegisterInfo &Registers, + const std::vector<Register> &RegistersToErase) { + for (auto Iterator = RegistersToErase.rbegin(); Iterator != RegistersToErase.rend(); ++Iterator) { + if (!Registers.isKnownVirtualRegister(*Iterator)) + continue; + auto Erased = Registers.eraseVirtualRegister(*Iterator); + if (!Erased) + return std::unexpected(Erased.error()); + } + return {}; +} + +[[nodiscard]] Expected<void> +restoreRegisterConstraints(MachineRegisterInfo &Registers, + const std::vector<RegisterConstraintSnapshot> &Snapshots) { + for (auto Iterator = Snapshots.rbegin(); Iterator != Snapshots.rend(); ++Iterator) { + if (!Registers.isKnownVirtualRegister(Iterator->Reg)) + continue; + if (Iterator->Bank) { + auto Restored = Registers.setRegisterBank(Iterator->Reg, *Iterator->Bank); + if (!Restored) + return std::unexpected(Restored.error()); + } else { + auto Cleared = Registers.clearRegisterBank(Iterator->Reg); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + if (Iterator->RegClass) { + auto Restored = Registers.setRegisterClass(Iterator->Reg, *Iterator->RegClass); + if (!Restored) + return std::unexpected(Restored.error()); + } else { + auto Cleared = Registers.clearRegisterClass(Iterator->Reg); + if (!Cleared) + return std::unexpected(Cleared.error()); + } + } + return {}; +} + +[[nodiscard]] Expected<void> +constrainRenderedInstruction(const InstructionDescriptor &Descriptor, + std::span<const MachineOperand> Operands, MachineFunction &Function, + const TargetDescription &Target, + std::vector<RegisterConstraintSnapshot> &Snapshots) { + if (Descriptor.Operands.empty() && !Operands.empty()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table result has no operand descriptors"); + } + + MachineRegisterInfo &Registers = Function.registerInfo(); + const auto Remember = [&Snapshots](Register Reg, const VirtualRegisterInfo &Info) { + if (std::ranges::find(Snapshots, Reg, &RegisterConstraintSnapshot::Reg) == Snapshots.end()) + Snapshots.push_back({.Reg = Reg, .Bank = Info.Bank, .RegClass = Info.RegClass}); + }; + + for (std::size_t Index = 0; Index < Operands.size(); ++Index) { + const Register *Reg = Operands[Index].getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + continue; + + const OperandDescriptor &OperandDescriptor = Index < Descriptor.Operands.size() + ? Descriptor.Operands[Index] + : Descriptor.Operands.back(); + if (!OperandDescriptor.RegBank && !OperandDescriptor.RegClass) + continue; + + auto Info = Registers.virtualRegisterInfo(*Reg); + if (!Info) + return std::unexpected(Info.error()); + if (OperandDescriptor.RegBank) { + if (Info->get().Bank && *Info->get().Bank != *OperandDescriptor.RegBank) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table result has an incompatible register bank"); + } + if (!Info->get().Bank) { + Remember(*Reg, Info->get()); + auto SetBank = Registers.setRegisterBank(*Reg, *OperandDescriptor.RegBank); + if (!SetBank) + return std::unexpected(SetBank.error()); + } + } + if (OperandDescriptor.RegClass) { + if (Info->get().RegClass && + !Target.registers().isSubclass(*Info->get().RegClass, *OperandDescriptor.RegClass)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table result has an incompatible register class"); + } + if (!Info->get().RegClass) { + Remember(*Reg, Info->get()); + auto SetClass = Registers.setRegisterClass(*Reg, *OperandDescriptor.RegClass); + if (!SetClass) + return std::unexpected(SetClass.error()); + } + } + } + return {}; +} + +[[nodiscard]] Expected<MachineOperand> +renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target, + const std::vector<MaterializedTemporary> &Temporaries, + const std::vector<MatchedRule::CapturedOperand> &CapturedOperands, + std::size_t OriginalExplicitCount) { + switch (Rendered.SourceKind) { + case MatchedRule::RenderedOperand::Kind::RootOperand: + if (Rendered.Value >= OriginalExplicitCount) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an implicit or missing operand"); + } + return Instruction.operandAt(Rendered.Value)->cloneDetached(); + case MatchedRule::RenderedOperand::Kind::ComplexOperand: + return makeUnexpected(ErrorCode::VerificationError, + "generated match table did not resolve a complex operand renderer"); + case MatchedRule::RenderedOperand::Kind::CapturedOperand: { + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(CapturedOperands, Rendered.Value); + if (Captured == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an unknown captured operand"); + } + return Captured->Operand.cloneDetached(); + } + case MatchedRule::RenderedOperand::Kind::CapturedTypeBits: { + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(CapturedOperands, Rendered.Value); + if (Captured == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an unknown captured type"); + const Register *Reg = Captured->Operand.getIf<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not a virtual register"); + auto Type = Function.registerInfo().getType(*Reg); + if (!Type) + return std::unexpected(Type.error()); + if (!Type->isCategoryNeutralScalar()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not scalar"); + return MachineOperand::immediate(static_cast<std::int64_t>(Type->scalarBitWidth())); + } + case MatchedRule::RenderedOperand::Kind::PhysicalRegister: { + auto Physical = PhysicalRegister::create(Rendered.Value); + if (!Physical || Target.registers().physicalRegister(*Physical) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an unknown physical register"); + } + auto Flags = registerFlagsFromRaw(Rendered.Flags); + if (!Flags) + return std::unexpected(Flags.error()); + return MachineOperand::registerOperand(Register::fromPhysical(*Physical), *Flags); + } + case MatchedRule::RenderedOperand::Kind::Temporary: { + const MaterializedTemporary *Temporary = findTemporary(Temporaries, Rendered.Value); + if (Temporary == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an unknown temporary"); + } + auto Flags = registerFlagsFromRaw(Rendered.Flags); + if (!Flags) + return std::unexpected(Flags.error()); + return MachineOperand::registerOperand(Temporary->Reg, *Flags); + } + case MatchedRule::RenderedOperand::Kind::CapturedImmediate: { + auto Captured = operandDefConstantValue(Instruction, Function, Rendered.Value); + if (!Captured) + return std::unexpected(Captured.error()); + if (!*Captured) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table lost a captured constant"); + } + std::int64_t Value = **Captured; + switch (Rendered.Transform) { + case GIMatchImmediateTransform::Identity: + break; + case GIMatchImmediateTransform::Negate: + if (Value == std::numeric_limits<std::int64_t>::min()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table immediate negation overflows"); + } + Value = -Value; + break; + case GIMatchImmediateTransform::PlusOne: + if (Value == std::numeric_limits<std::int64_t>::max()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table immediate increment overflows"); + } + ++Value; + break; + } + return MachineOperand::immediate(Value); + } + case MatchedRule::RenderedOperand::Kind::Immediate: + return MachineOperand::immediate(Rendered.Immediate); + } + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid operand renderer"); +} + +[[nodiscard]] bool compatibleReplacement(Register Destination, Register Source, + const MachineFunction &Function, + const TargetDescription &Target) { + if (!Destination.isVirtual() || Source.isNoRegister()) + return false; + auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(Destination); + if (!DestinationInfo) + return false; + const VirtualRegisterInfo &DestinationValue = DestinationInfo->get(); + if (Source.isPhysical()) { + const std::optional<PhysicalRegister> Physical = Source.physicalRegister(); + if (!Physical) + return false; + if (DestinationValue.RegClass && + !Target.registers().registerClassContains(*DestinationValue.RegClass, *Physical)) + return false; + return !DestinationValue.Bank || + Target.registers().bankContainsRegister(*DestinationValue.Bank, *Physical); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source); + if (!SourceInfo) + return false; + const VirtualRegisterInfo &SourceValue = SourceInfo->get(); + if (DestinationValue.Type != SourceValue.Type) + return false; + if (DestinationValue.Bank && + (!SourceValue.Bank || + !Target.registers().registerBanksOverlap(*DestinationValue.Bank, *SourceValue.Bank))) + return false; + if (DestinationValue.RegClass && + (!SourceValue.RegClass || !Target.registers().registerClassesOverlap( + *DestinationValue.RegClass, *SourceValue.RegClass))) + return false; + return true; +} + +[[nodiscard]] Expected<bool> replaceRootWithCapturedOperand(const MatchedRule &Rule, + MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) { + if (!Rule.ReplaceRootCapture) + return false; + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(Rule.CapturedOperands, *Rule.ReplaceRootCapture); + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Destination = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + const Register *Source = Captured == nullptr ? nullptr : Captured->Operand.getIf<Register>(); + if (Destination == nullptr || Source == nullptr || !Definition->isDef() || Definition->isUse() || + (!Source->isVirtual() && !Source->isPhysical()) || Destination->isNoRegister() || + Source->isNoRegister() || !Destination->isVirtual() || + Function.registerInfo().getUniqueVRegDef(*Destination) != Definition || + !compatibleReplacement(*Destination, *Source, Function, Target)) { + return false; + } + if (Instruction.parent() == nullptr) + return makeUnexpected(ErrorCode::InternalError, "generated combiner root is detached"); + std::vector<MachineOperand *> Uses; + for (MachineOperand &Use : Function.registerInfo().useOperands(*Destination, true)) + Uses.push_back(&Use); + for (MachineOperand *Use : Uses) { + auto Replaced = Use->setRegister(*Source); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + auto Erased = eraseInstr(Instruction, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + return true; +} + +template <typename Finalizer, typename ComplexRenderer> +[[nodiscard]] Expected<void> applyRule(const MatchedRule &Rule, MachineInstr &Instruction, + MachineFunction &Function, const TargetDescription &Target, + Finalizer &&Finalize, ComplexRenderer &&RenderComplex) { + const InstructionDescriptor *InputDescriptor = Target.instructionDescriptor(Instruction.opcode()); + if (InputDescriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table input has no instruction descriptor"); + } + if (Rule.ReplaceRootCapture) { + auto Replaced = replaceRootWithCapturedOperand(Rule, Instruction, Function, Target); + if (!Replaced) + return std::unexpected(Replaced.error()); + if (!*Replaced) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner root replacement is incompatible"); + for (const Register Reg : Rule.EraseOperandDefinitions) { + MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); + if (Definition == nullptr || !isTriviallyDead(*Definition, Function.registerInfo(), Target)) + continue; + auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast<std::uint32_t>(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast<MachineInstrFlag>(Index)); + } + Instruction.setFlags(Flags); + } + return {}; + } + const auto RootPosition = + std::ranges::find(Rule.Instructions, true, &MatchedRule::Instruction::ReplacesRoot); + if (RootPosition == Rule.Instructions.end()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table selection has no root instruction"); + const std::size_t RootIndex = + static_cast<std::size_t>(std::distance(Rule.Instructions.begin(), RootPosition)); + const MachineInstrFlags InputFlags = Instruction.flags(); + const bool InputMayRaiseFPException = + InputDescriptor->Flags.has(InstructionFlag::MayRaiseFPException); + const std::size_t OriginalExplicitCount = explicitOperandCount(Instruction); + const std::size_t OriginalOperandCount = Instruction.operandCount(); + const Opcode OriginalOpcode = Instruction.opcode(); + + std::vector<MachineOperand> OriginalOperands; + OriginalOperands.reserve(OriginalOperandCount); + for (const MachineOperand &Operand : Instruction.operands()) + OriginalOperands.push_back(Operand.cloneDetached()); + + std::vector<std::pair<std::size_t, std::size_t>> Ties; + for (std::size_t Index = 0; Index < OriginalOperandCount; ++Index) { + const std::optional<std::size_t> Other = Instruction.operandAt(Index)->tiedOperandIndex(); + if (Other && Index < *Other) + Ties.emplace_back(Index, *Other); + } + + std::vector<MaterializedTemporary> Temporaries; + Temporaries.reserve(Rule.Temporaries.size()); + for (const MatchedRule::Temporary &Temporary : Rule.Temporaries) { + auto Reg = Function.registerInfo().createVirtualRegister(Temporary.Type); + if (!Reg) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return std::unexpected(Reg.error()); + } + Temporaries.push_back({.ID = Temporary.ID, .Reg = *Reg}); + } + + struct PendingComplexInstruction final { + Opcode ResultOpcode; + std::vector<MachineOperand> Operands; + }; + + std::vector<Register> ComplexRegisters; + std::vector<PendingComplexInstruction> PendingComplexInstructions; + std::vector<MachineInstr *> AddedInstructions; + const auto CleanupGeneratedRegisters = [&]() -> Expected<void> { + auto ErasedTemporaries = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!ErasedTemporaries) + return std::unexpected(ErasedTemporaries.error()); + return eraseRegisters(Function.registerInfo(), ComplexRegisters); + }; + + std::vector<std::vector<MachineOperand>> RenderedInstructions; + RenderedInstructions.reserve(Rule.Instructions.size()); + std::vector<std::optional<std::size_t>> SourceToOutput(OriginalOperandCount); + for (std::size_t InstructionIndex = 0; InstructionIndex < Rule.Instructions.size(); + ++InstructionIndex) { + const MatchedRule::Instruction &Planned = Rule.Instructions[InstructionIndex]; + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Planned.ResultOpcode); + if (Descriptor == nullptr || + (!Descriptor->Variadic && Descriptor->Operands.size() != Planned.Operands.size())) { + auto Cleanup = CleanupGeneratedRegisters(); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return makeUnexpected(ErrorCode::VerificationError, + "generated match table result has an incompatible descriptor"); + } + std::vector<MachineOperand> Operands; + Operands.reserve(Planned.Operands.size()); + for (const MatchedRule::RenderedOperand &Rendered : Planned.Operands) { + Expected<MachineOperand> Operand = [&]() -> Expected<MachineOperand> { + if (Rendered.SourceKind != MatchedRule::RenderedOperand::Kind::ComplexOperand) + return renderOperand(Rendered, Instruction, Function, Target, Temporaries, + Rule.CapturedOperands, OriginalExplicitCount); + + auto Complex = + RenderComplex(Rendered.ComplexRenderer, Instruction, Function, Target, Rendered.Value); + if (!Complex) + return std::unexpected(Complex.error()); + if (!*Complex) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table complex operand unexpectedly did not match"); + if ((*Complex)->Operand && (*Complex)->Instruction) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table complex operand has two renderings"); + if ((*Complex)->Operand) + return std::move(*(*Complex)->Operand); + if (!(*Complex)->Instruction) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table complex operand has no rendering"); + + GIMatchComplexInstruction &Plan = *(*Complex)->Instruction; + if (!Plan.ResultType.isValid()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table complex instruction has no result type"); + auto Result = Function.registerInfo().createVirtualRegister(Plan.ResultType); + if (!Result) + return std::unexpected(Result.error()); + ComplexRegisters.push_back(*Result); + auto Definition = MachineOperand::registerOperand(*Result, {RegisterOperandFlag::Define}); + if (!Definition) + return std::unexpected(Definition.error()); + std::vector<MachineOperand> PlannedOperands; + PlannedOperands.reserve(Plan.Operands.size() + 1U); + PlannedOperands.push_back(std::move(*Definition)); + for (MachineOperand &PlanOperand : Plan.Operands) + PlannedOperands.push_back(std::move(PlanOperand)); + PendingComplexInstructions.push_back({ + .ResultOpcode = Plan.ResultOpcode, + .Operands = std::move(PlannedOperands), + }); + return MachineOperand::registerOperand(*Result, {RegisterOperandFlag::Use}); + }(); + if (!Operand) { + auto Cleanup = CleanupGeneratedRegisters(); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return std::unexpected(Operand.error()); + } + if (InstructionIndex == RootIndex && + Rendered.SourceKind == MatchedRule::RenderedOperand::Kind::RootOperand) { + if (SourceToOutput[Rendered.Value] && + Instruction.operandAt(Rendered.Value)->tiedOperandIndex()) { + auto Cleanup = CleanupGeneratedRegisters(); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return makeUnexpected(ErrorCode::VerificationError, + "generated match table duplicates a tied operand"); + } + SourceToOutput[Rendered.Value] = Operands.size(); + } + Operands.push_back(std::move(*Operand)); + } + RenderedInstructions.push_back(std::move(Operands)); + } + + std::vector<RegisterConstraintSnapshot> ConstraintSnapshots; + bool RootModified = false; + const auto Rollback = [&](Error Failure) -> Expected<void> { + for (auto Iterator = AddedInstructions.rbegin(); Iterator != AddedInstructions.rend(); + ++Iterator) { + if ((*Iterator)->parent() == nullptr) + continue; + auto Erased = eraseInstr(**Iterator, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + } + if (RootModified) { + auto Restored = restoreInstruction(Instruction, OriginalOpcode, OriginalOperands, Ties); + if (!Restored) + return std::unexpected(Restored.error()); + } + auto RestoredConstraints = + restoreRegisterConstraints(Function.registerInfo(), ConstraintSnapshots); + if (!RestoredConstraints) + return std::unexpected(RestoredConstraints.error()); + auto ErasedGenerated = CleanupGeneratedRegisters(); + if (!ErasedGenerated) + return std::unexpected(ErasedGenerated.error()); + return std::unexpected(std::move(Failure)); + }; + + for (const PendingComplexInstruction &Pending : PendingComplexInstructions) { + const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Pending.ResultOpcode); + if (Descriptor == nullptr || + (!Descriptor->Variadic && Descriptor->Operands.size() != Pending.Operands.size())) { + return Rollback(Error(ErrorCode::VerificationError, + "generated match table complex renderer has an incompatible result")); + } + auto Constraint = constrainRenderedInstruction(*Descriptor, Pending.Operands, Function, Target, + ConstraintSnapshots); + if (!Constraint) + return Rollback(Constraint.error()); + } + + for (std::size_t Index = 0; Index < Rule.Instructions.size(); ++Index) { + const InstructionDescriptor *Descriptor = + Target.instructionDescriptor(Rule.Instructions[Index].ResultOpcode); + if (Descriptor == nullptr) + return Rollback(Error(ErrorCode::VerificationError, + "generated match table selects an unknown instruction opcode")); + auto Constraint = constrainRenderedInstruction(*Descriptor, RenderedInstructions[Index], + Function, Target, ConstraintSnapshots); + if (!Constraint) + return Rollback(Constraint.error()); + } + + MachineIRBuilder Builder(Function, Target); + MachineInstr *ComplexAnchor = nullptr; + for (PendingComplexInstruction &Pending : PendingComplexInstructions) { + auto Point = ComplexAnchor == nullptr ? Builder.setInsertPointBefore(Instruction) + : Builder.setInsertPointAfter(*ComplexAnchor); + if (!Point) + return Rollback(Point.error()); + auto Built = Builder.buildInstr(Pending.ResultOpcode); + if (!Built) + return Rollback(Built.error()); + for (MachineOperand &Operand : Pending.Operands) { + auto Added = Built->addOperand(std::move(Operand)); + if (!Added) + return Rollback(Added.error()); + } + auto Complete = Built->build(); + if (!Complete) + return Rollback(Complete.error()); + AddedInstructions.push_back(*Complete); + auto Finalized = Finalize(**Complete, InputFlags, InputMayRaiseFPException); + if (!Finalized) + return Rollback(Finalized.error()); + ComplexAnchor = *Complete; + } + + const auto BuildAction = [&](std::size_t Index, MachineInstr *&Anchor) -> Expected<void> { + auto Point = Anchor == nullptr ? Builder.setInsertPointBefore(Instruction) + : Builder.setInsertPointAfter(*Anchor); + if (!Point) + return std::unexpected(Point.error()); + auto Pending = Builder.buildInstr(Rule.Instructions[Index].ResultOpcode); + if (!Pending) + return std::unexpected(Pending.error()); + for (MachineOperand &Operand : RenderedInstructions[Index]) { + auto Added = Pending->addOperand(std::move(Operand)); + if (!Added) + return std::unexpected(Added.error()); + } + auto Built = Pending->build(); + if (!Built) + return std::unexpected(Built.error()); + AddedInstructions.push_back(*Built); + auto Finalized = Finalize(**Built, InputFlags, InputMayRaiseFPException); + if (!Finalized) + return std::unexpected(Finalized.error()); + Anchor = *Built; + return {}; + }; + + MachineInstr *BeforeAnchor = ComplexAnchor; + for (std::size_t Index = 0; Index < RootIndex; ++Index) { + auto Built = BuildAction(Index, BeforeAnchor); + if (!Built) + return Rollback(Built.error()); + } + + const MatchedRule::Instruction &RootAction = Rule.Instructions[RootIndex]; + RootModified = true; + auto SetOpcode = Instruction.setOpcode(RootAction.ResultOpcode); + if (!SetOpcode) + return Rollback(SetOpcode.error()); + while (Instruction.operandCount() != 0) { + auto Erased = Instruction.eraseOperand(Instruction.operandCount() - 1U); + if (!Erased) + return Rollback(Erased.error()); + } + for (MachineOperand &Operand : RenderedInstructions[RootIndex]) { + auto Added = Instruction.addOperand(std::move(Operand)); + if (!Added) + return Rollback(Added.error()); + } + for (std::size_t Index = OriginalExplicitCount; Index < OriginalOperandCount; ++Index) { + SourceToOutput[Index] = Instruction.operandCount(); + auto Added = Instruction.addOperand(OriginalOperands[Index].cloneDetached()); + if (!Added) + return Rollback(Added.error()); + } + for (const auto [OldDef, OldUse] : Ties) { + const std::optional<std::size_t> &NewDef = SourceToOutput[OldDef]; + const std::optional<std::size_t> &NewUse = SourceToOutput[OldUse]; + if (!NewDef || !NewUse) + continue; + auto Tied = Instruction.tieOperands(*NewDef, *NewUse); + if (!Tied) + return Rollback(Tied.error()); + } + + MachineInstr *AfterAnchor = &Instruction; + for (std::size_t Index = RootIndex + 1U; Index < Rule.Instructions.size(); ++Index) { + auto Built = BuildAction(Index, AfterAnchor); + if (!Built) + return Rollback(Built.error()); + } + + for (const Register Reg : Rule.EraseOperandDefinitions) { + MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); + if (Definition == nullptr || Definition == &Instruction || + !isTriviallyDead(*Definition, Function.registerInfo(), Target)) { + continue; + } + auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); + if (!Erased) + return Rollback(Erased.error()); + } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast<std::uint32_t>(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast<MachineInstrFlag>(Index)); + } + Instruction.setFlags(Flags); + } + return {}; +} + +} // namespace + +Expected<void> GIMatchTableExecutor::finalizeGeneratedInstruction(MachineInstr &, MachineFunction &, + const TargetDescription &, + MachineInstrFlags, bool) const { + return {}; +} + +Expected<bool> GIMatchTableExecutor::matchesTargetPredicate(std::string_view Name, + const MachineInstr &, + const MachineFunction &, + const TargetDescription &) const { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table uses unknown target predicate '" + + std::string(Name) + "'"); +} + +Expected<std::optional<GIMatchComplexOperand>> +GIMatchTableExecutor::renderComplexOperand(std::string_view, const MachineInstr &, + const MachineFunction &, const TargetDescription &, + std::uint32_t) const { + return std::optional<GIMatchComplexOperand>{}; +} + +Expected<bool> GIMatchTableExecutor::match(const GIMatchTable &Table, + const MachineInstr &Instruction, + const MachineFunction &Function, + const TargetDescription &Target) const { + for (const GIMatchTableRule &Rule : Table.Rules) { + auto Match = matchRule(Table, Rule, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, + const TargetDescription &InputTarget) { + return matchesTargetPredicate(Name, Input, InputFunction, InputTarget); + }); + if (!Match) + return std::unexpected(Match.error()); + if (!*Match) + continue; + auto Complex = complexRenderersMatch( + **Match, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Complex) + return std::unexpected(Complex.error()); + if (!*Complex) + continue; + for (const MatchedRule::Instruction &Action : (*Match)->Instructions) { + if (Target.instructionDescriptor(Action.ResultOpcode) == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table selects an unknown instruction opcode"); + } + } + return true; + } + return false; +} + +Expected<bool> GIMatchTableExecutor::select(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const { + for (const GIMatchTableRule &Rule : Table.Rules) { + auto Match = matchRule(Table, Rule, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, + const TargetDescription &InputTarget) { + return matchesTargetPredicate(Name, Input, InputFunction, InputTarget); + }); + if (!Match) + return std::unexpected(Match.error()); + if (!*Match) + continue; + auto Complex = complexRenderersMatch( + **Match, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Complex) + return std::unexpected(Complex.error()); + if (!*Complex) + continue; + auto Applied = applyRule( + **Match, Instruction, Function, Target, + [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) { + return finalizeGeneratedInstruction(Output, Function, Target, InputFlags, + InputMayRaiseFPException); + }, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Applied) + return std::unexpected(Applied.error()); + return true; + } + return false; +} + +Expected<bool> GIMatchTableExecutor::combine(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const { + if (Table.Kind != GIMatchTableKind::Combiner) + return makeUnexpected(ErrorCode::InvalidArgument, + "GlobalISel combiner received a selection match table"); + for (const GIMatchTableRule &Rule : Table.Rules) { + auto Match = matchRule(Table, Rule, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, + const TargetDescription &InputTarget) { + return matchesTargetPredicate(Name, Input, InputFunction, InputTarget); + }); + if (!Match) + return std::unexpected(Match.error()); + if (!*Match) + continue; + if (!(*Match)->ReplaceRootCapture) { + for (const MatchedRule::Instruction &Action : (*Match)->Instructions) { + if (Target.instructionDescriptor(Action.ResultOpcode) == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner selects an unknown instruction opcode"); + } + } + auto Applied = applyRule( + **Match, Instruction, Function, Target, + [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) { + return finalizeGeneratedInstruction(Output, Function, Target, InputFlags, + InputMayRaiseFPException); + }, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Applied) + return std::unexpected(Applied.error()); + return true; + } + return false; +} + +} // namespace rcc |