From 864a29abbdce86353ec91c3587757711d3a42f10 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 16 Aug 2026 17:28:49 +0800 Subject: [RISCV][GlobalISel] Generate integer comparisons --- .../rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h | 28 +- .../rcc/CodeGen/GlobalISel/InstructionSelector.h | 6 + backend/include/rcc/TableGen/Record.h | 30 +- .../CodeGen/GlobalISel/GIMatchTableExecutor.cpp | 679 +++++++++++++++++---- .../lib/CodeGen/GlobalISel/InstructionSelect.cpp | 10 + backend/lib/CodeGen/TargetDescription.cpp | 13 +- backend/lib/TableGen/Parser.cpp | 173 +++++- .../RISCV/GISel/RISCVInstructionSelector.cpp | 176 +----- backend/lib/Target/RISCV/RISCVGISel.rccdesc | 652 +++++++++++++++++++- backend/utils/TableGen/Common/CodeGenSelection.cpp | 221 +++++-- backend/utils/TableGen/Common/CodeGenTarget.h | 35 +- backend/utils/TableGen/GlobalISelEmitter.cpp | 73 ++- 12 files changed, 1664 insertions(+), 432 deletions(-) (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h index 7cceca3..afd0d70 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h +++ b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h @@ -22,17 +22,27 @@ enum class GIMatchTypeKind : std::uint8_t { Pointer, }; +enum class GIMatchImmediateTransform : std::uint8_t { + Identity, + Negate, + PlusOne, +}; + enum class GIMatchTableOpcode : std::uint8_t { CheckOpcode, CheckOperandType, CheckOperandBank, CheckOperandClass, CheckIntegerPredicate, - CheckOperandDefConstant, + CheckOperandDefConstantRanges, + CreateTemporary, MutateOpcode, + BuildInstruction, RenderOperand, RenderPhysicalRegister, - AppendImmediate, + RenderTemporary, + RenderCapturedImmediate, + RenderImmediate, EraseOperandDefinition, Complete, }; @@ -45,6 +55,11 @@ struct GIMatchTableInstruction final { std::int64_t Immediate = 0; }; +struct GIMatchTableConstantRange final { + std::int64_t Minimum = 0; + std::int64_t Maximum = 0; +}; + struct GIMatchTableRule final { std::string_view Name; std::uint32_t Priority = 0; @@ -55,10 +70,13 @@ struct GIMatchTableRule final { struct GIMatchTable final { std::span Instructions; std::span Rules; + std::span ConstantRanges; }; class GIMatchTableExecutor { public: + virtual ~GIMatchTableExecutor() = default; + [[nodiscard]] Expected match(const GIMatchTable &Table, const MachineInstr &Instruction, const MachineFunction &Function, const TargetDescription &Target) const; @@ -68,6 +86,12 @@ public: [[nodiscard]] Expected select(const GIMatchTable &Table, MachineInstr &Instruction, MachineFunction &Function, const TargetDescription &Target) const; + +protected: + [[nodiscard]] virtual Expected + finalizeGeneratedInstruction(MachineInstr &Output, MachineFunction &Function, + const TargetDescription &Target, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) const; }; } // namespace rcc diff --git a/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h index 36fca8d..f45b24d 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h +++ b/backend/include/rcc/CodeGen/GlobalISel/InstructionSelector.h @@ -38,6 +38,12 @@ public: [[nodiscard]] Expected propagateSelectionFlags(MachineInstr &Output, const MachineInstr &Input, const TargetDescription &Target) const; + +protected: + [[nodiscard]] Expected + finalizeGeneratedInstruction(MachineInstr &Output, MachineFunction &Function, + const TargetDescription &Target, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) const override; }; } // namespace rcc diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h index 4378af8..57e5832 100644 --- a/backend/include/rcc/TableGen/Record.h +++ b/backend/include/rcc/TableGen/Record.h @@ -237,17 +237,40 @@ struct SourceSelectionIntegerPredicate final { struct SourceSelectionOperandDefConstantPredicate final { std::uint32_t OperandIndex = 0; - std::int64_t Value = 0; + struct ConstantRange final { + std::int64_t Minimum = 0; + std::int64_t Maximum = 0; + TextRange SourceRange; + }; + + std::vector Ranges; + TextRange Range; +}; + +struct SourceSelectionTemporary final { + std::string Symbol; + std::uint32_t TypeFromOperand = 0; TextRange Range; }; struct SourceSelectionOperandRenderer final { std::optional OperandIndex; std::string PhysicalRegisterSymbol; + std::string TemporarySymbol; + std::optional CapturedImmediateOperand; + std::optional Immediate; + std::string ImmediateTransform; std::vector Flags; TextRange Range; }; +struct SourceSelectionAction final { + std::string ResultOpcodeSymbol; + bool ReplacesRoot = false; + std::vector OperandRenderers; + TextRange Range; +}; + struct SourceSelectionRule final { std::string Symbol; std::uint32_t Priority = 0; @@ -258,9 +281,8 @@ struct SourceSelectionRule final { std::vector OperandBanks; std::vector OperandClasses; std::vector OperandDefConstants; - std::string ResultOpcodeSymbol; - std::optional> OperandRenderers; - std::vector AppendedImmediates; + std::vector Temporaries; + std::vector Actions; std::vector EraseOperandDefinitions; TextRange Range; }; diff --git a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp index 38fb66d..7f7cb63 100644 --- a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp +++ b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp @@ -6,16 +6,21 @@ #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/MachineOperand.h" #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" +#include #include #include #include +#include #include +#include #include +#include #include namespace rcc { @@ -100,30 +105,58 @@ namespace { return Integer != nullptr && static_cast(*Integer) == Step.Value; } -[[nodiscard]] Expected matchesOperandDefConstant(const MachineInstr &Instruction, - const MachineFunction &Function, - const GIMatchTableInstruction &Step) { - const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); +[[nodiscard]] Expected> +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(); if (Reg == nullptr || !Reg->isVirtual()) - return false; + return std::optional{}; const MachineInstr *Definition = Function.registerInfo().getVRegDef(*Reg); if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT)) - return false; + return std::optional{}; const MachineOperand *Value = Definition->operandAt(1); if (Value == nullptr) - return false; + return std::optional{}; if (const std::int64_t *Immediate = Value->getIf()) - return *Immediate == Step.Immediate; + return *Immediate; const auto *Integer = Value->getIf(); if (Integer == nullptr) - return false; - if (Step.Immediate == 0) - return Integer->Value.isZero(); + return std::optional{}; 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); - return Error == std::errc{} && End == Text.data() + Text.size() && Parsed == Step.Immediate; + if (Error != std::errc{} || End != Text.data() + Text.size()) + return std::optional{}; + return Parsed; +} + +[[nodiscard]] Expected +matchesOperandDefConstantRanges(const GIMatchTable &Table, const MachineInstr &Instruction, + const MachineFunction &Function, + const GIMatchTableInstruction &Step) { + const std::size_t First = Step.Value; + const std::size_t Count = Step.Auxiliary; + if (Count == 0 || First > Table.ConstantRanges.size() || + Count > Table.ConstantRanges.size() - First) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid constant range"); + } + auto Value = operandDefConstantValue(Instruction, Function, Step.OperandIndex); + if (!Value) + return std::unexpected(Value.error()); + 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 registerFlagsFromRaw(std::uint32_t Raw) { @@ -143,23 +176,45 @@ namespace { } struct MatchedRule final { + struct Temporary final { + std::uint32_t ID = 0; + std::uint32_t TypeFromOperand = 0; + }; + struct RenderedOperand final { enum class Kind : std::uint8_t { RootOperand, PhysicalRegister, + Temporary, + CapturedImmediate, + Immediate, }; Kind SourceKind = Kind::RootOperand; std::uint32_t Value = 0; std::uint32_t Flags = 0; + GIMatchImmediateTransform Transform = GIMatchImmediateTransform::Identity; + std::int64_t Immediate = 0; + }; + + struct Instruction final { + Opcode ResultOpcode; + bool ReplacesRoot = false; + std::vector Operands; }; - Opcode ResultOpcode; - std::optional> OperandLayout; - std::vector AppendedImmediates; + std::vector Temporaries; + std::vector Instructions; std::vector EraseOperandDefinitions; }; +[[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]] Expected> matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const MachineInstr &Instruction, @@ -172,23 +227,24 @@ struct MatchedRule final { } MatchedRule Result; - bool HasResultOpcode = false; 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) + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); + "generated match table performs a predicate after an action"); + } if (Instruction.opcode().value() != Step.Value) return std::optional{}; break; case GIMatchTableOpcode::CheckOperandType: { - if (Applying) + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); + "generated match table performs a predicate after an action"); + } auto Matched = matchesType(Instruction, Function, Step); if (!Matched) return std::unexpected(Matched.error()); @@ -197,9 +253,10 @@ struct MatchedRule final { break; } case GIMatchTableOpcode::CheckOperandBank: { - if (Applying) + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); + "generated match table performs a predicate after an action"); + } auto Matched = matchesBank(Instruction, Function, Step); if (!Matched) return std::unexpected(Matched.error()); @@ -208,9 +265,10 @@ struct MatchedRule final { break; } case GIMatchTableOpcode::CheckOperandClass: { - if (Applying) + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); + "generated match table performs a predicate after an action"); + } auto Matched = matchesClass(Instruction, Function, Step); if (!Matched) return std::unexpected(Matched.error()); @@ -219,9 +277,10 @@ struct MatchedRule final { break; } case GIMatchTableOpcode::CheckIntegerPredicate: { - if (Applying) + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); + "generated match table performs a predicate after an action"); + } auto Matched = matchesIntegerPredicate(Instruction, Step); if (!Matched) return std::unexpected(Matched.error()); @@ -229,84 +288,153 @@ struct MatchedRule final { return std::optional{}; break; } - case GIMatchTableOpcode::CheckOperandDefConstant: { - if (Applying) + case GIMatchTableOpcode::CheckOperandDefConstantRanges: { + if (Applying) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table performs a predicate after rendering"); - auto Matched = matchesOperandDefConstant(Instruction, Function, Step); + "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{}; 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, + .TypeFromOperand = Step.OperandIndex, + }); + break; + } case GIMatchTableOpcode::MutateOpcode: - if (Complete || HasResultOpcode || Step.Value == 0) + if (Complete || Step.Value == 0 || !Result.Instructions.empty()) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table has an invalid opcode mutation"); + "generated match table has an invalid root mutation"); + } Applying = true; - Result.ResultOpcode = Opcode::fromValue(Step.Value); - HasResultOpcode = true; + Result.Instructions.push_back({ + .ResultOpcode = Opcode::fromValue(Step.Value), + .ReplacesRoot = true, + .Operands = {}, + }); + break; + case GIMatchTableOpcode::BuildInstruction: + if (Complete || Step.Value == 0 || Result.Instructions.empty()) { + 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 || !HasResultOpcode) + 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"); - Applying = true; - if (!Result.OperandLayout) - Result.OperandLayout.emplace(); - Result.OperandLayout->push_back({ + } + Result.Instructions.back().Operands.push_back({ .SourceKind = MatchedRule::RenderedOperand::Kind::RootOperand, .Value = Step.OperandIndex, - .Flags = 0, }); break; case GIMatchTableOpcode::RenderPhysicalRegister: - if (Complete || !HasResultOpcode || Step.Value == 0) + if (Complete || Result.Instructions.empty() || Step.Value == 0) { return makeUnexpected(ErrorCode::VerificationError, "generated match table has an invalid physical register renderer"); - Applying = true; - if (!Result.OperandLayout) - Result.OperandLayout.emplace(); - Result.OperandLayout->push_back({ + } + Result.Instructions.back().Operands.push_back({ .SourceKind = MatchedRule::RenderedOperand::Kind::PhysicalRegister, .Value = Step.Value, .Flags = Step.Auxiliary, }); break; - case GIMatchTableOpcode::AppendImmediate: - if (Complete || Result.OperandLayout) + case GIMatchTableOpcode::RenderTemporary: + if (Complete || Result.Instructions.empty() || !hasTemporary(Result, Step.Value)) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table renders after completion"); - Applying = true; - Result.AppendedImmediates.push_back(Step.Immediate); + "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, + }); + break; + case GIMatchTableOpcode::RenderCapturedImmediate: { + if (Complete || Result.Instructions.empty() || + Step.Value > static_cast(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, + .Transform = static_cast(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, + .Immediate = Step.Immediate, + }); break; case GIMatchTableOpcode::EraseOperandDefinition: { - if (Complete || !HasResultOpcode) + if (Complete || Result.Instructions.empty()) { 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(); if (Reg == nullptr || !Reg->isVirtual()) { return makeUnexpected(ErrorCode::VerificationError, "generated match table erases a non-virtual operand definition"); } - Applying = true; Result.EraseOperandDefinitions.push_back(*Reg); break; } case GIMatchTableOpcode::Complete: - if (Complete || !HasResultOpcode || Index + 1 != First + Count) + if (Complete || Result.Instructions.empty() || Index + 1 != First + Count) { return makeUnexpected(ErrorCode::VerificationError, "generated match table has an invalid completion action"); + } Complete = true; break; } } - if (!Complete || !HasResultOpcode) + if (!Complete || Result.Instructions.empty() || !Result.Instructions.front().ReplacesRoot) { return makeUnexpected(ErrorCode::VerificationError, "generated match table rule does not complete rendering"); + } return std::optional(std::move(Result)); } @@ -342,16 +470,210 @@ restoreInstruction(MachineInstr &Instruction, Opcode OriginalOpcode, return {}; } -[[nodiscard]] Expected applyRule(const MatchedRule &Rule, MachineInstr &Instruction, - MachineFunction &Function, const TargetDescription &Target) { - const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Rule.ResultOpcode); - if (Descriptor == nullptr) +struct MaterializedTemporary final { + std::uint32_t ID = 0; + Register Reg; +}; + +struct RegisterConstraintSnapshot final { + Register Reg; + std::optional Bank; + std::optional RegClass; +}; + +[[nodiscard]] const MaterializedTemporary * +findTemporary(const std::vector &Temporaries, std::uint32_t ID) { + const auto Position = + std::ranges::find(Temporaries, ID, &MaterializedTemporary::ID); + return Position == Temporaries.end() ? nullptr : &*Position; +} + +[[nodiscard]] Expected +eraseTemporaries(MachineRegisterInfo &Registers, + const std::vector &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 +restoreRegisterConstraints(MachineRegisterInfo &Registers, + const std::vector &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 +constrainRenderedInstruction(const InstructionDescriptor &Descriptor, + std::span Operands, + MachineFunction &Function, const TargetDescription &Target, + std::vector &Snapshots) { + if (Descriptor.Operands.empty() && !Operands.empty()) { return makeUnexpected(ErrorCode::VerificationError, - "generated match table selects an unknown instruction opcode"); + "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(); + 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 +renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr &Instruction, + const MachineFunction &Function, const TargetDescription &Target, + const std::vector &Temporaries, + 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::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::min()) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table immediate negation overflows"); + } + Value = -Value; + break; + case GIMatchImmediateTransform::PlusOne: + if (Value == std::numeric_limits::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"); +} + +template +[[nodiscard]] Expected +applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &Function, + const TargetDescription &Target, Finalizer &&Finalize) { + const InstructionDescriptor *InputDescriptor = + Target.instructionDescriptor(Instruction.opcode()); + if (InputDescriptor == nullptr) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table input has no instruction descriptor"); + } + 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 OriginalOperands; OriginalOperands.reserve(OriginalOperandCount); for (const MachineOperand &Operand : Instruction.operands()) @@ -364,110 +686,201 @@ restoreInstruction(MachineInstr &Instruction, Opcode OriginalOpcode, Ties.emplace_back(Index, *Other); } - std::vector NewOperands; + std::vector Temporaries; + Temporaries.reserve(Rule.Temporaries.size()); + for (const MatchedRule::Temporary &Temporary : Rule.Temporaries) { + const MachineOperand *SourceOperand = Instruction.operandAt(Temporary.TypeFromOperand); + const Register *Source = SourceOperand == nullptr ? nullptr : SourceOperand->getIf(); + if (Source == nullptr || !Source->isVirtual()) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return makeUnexpected(ErrorCode::VerificationError, + "generated match table temporary has an invalid type source"); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(*Source); + if (!SourceInfo) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return std::unexpected(SourceInfo.error()); + } + const std::optional Type = SourceInfo->get().Type; + if (!Type) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return makeUnexpected(ErrorCode::VerificationError, + "generated match table temporary type source has no type"); + } + auto Reg = Function.registerInfo().createVirtualRegister(*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}); + } + + std::vector> RenderedInstructions; + RenderedInstructions.reserve(Rule.Instructions.size()); std::vector> SourceToOutput(OriginalOperandCount); - std::size_t NewExplicitCount = 0; - if (Rule.OperandLayout) { - NewOperands.reserve(Rule.OperandLayout->size() + OriginalOperandCount - OriginalExplicitCount); - for (const MatchedRule::RenderedOperand &Rendered : *Rule.OperandLayout) { - if (Rendered.SourceKind == MatchedRule::RenderedOperand::Kind::RootOperand) { - if (Rendered.Value >= OriginalExplicitCount) { - return makeUnexpected(ErrorCode::VerificationError, - "generated match table renders an implicit or missing operand"); - } + 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 = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return makeUnexpected(ErrorCode::VerificationError, + "generated match table result has an incompatible descriptor"); + } + std::vector Operands; + Operands.reserve(Planned.Operands.size()); + for (const MatchedRule::RenderedOperand &Rendered : Planned.Operands) { + auto Operand = renderOperand(Rendered, Instruction, Function, Target, Temporaries, + OriginalExplicitCount); + if (!Operand) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); + return std::unexpected(Operand.error()); + } + if (InstructionIndex == 0 && + Rendered.SourceKind == MatchedRule::RenderedOperand::Kind::RootOperand) { if (SourceToOutput[Rendered.Value] && Instruction.operandAt(Rendered.Value)->tiedOperandIndex()) { + auto Cleanup = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!Cleanup) + return std::unexpected(Cleanup.error()); return makeUnexpected(ErrorCode::VerificationError, "generated match table duplicates a tied operand"); } - SourceToOutput[Rendered.Value] = NewOperands.size(); - NewOperands.push_back(Instruction.operandAt(Rendered.Value)->cloneDetached()); - } else { - 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()); - auto Operand = MachineOperand::registerOperand(Register::fromPhysical(*Physical), *Flags); - if (!Operand) - return std::unexpected(Operand.error()); - NewOperands.push_back(std::move(*Operand)); + SourceToOutput[Rendered.Value] = Operands.size(); } + Operands.push_back(std::move(*Operand)); } - NewExplicitCount = NewOperands.size(); - } else { - NewOperands.reserve(OriginalOperandCount + Rule.AppendedImmediates.size()); - for (std::size_t Index = 0; Index < OriginalExplicitCount; ++Index) { - SourceToOutput[Index] = NewOperands.size(); - NewOperands.push_back(Instruction.operandAt(Index)->cloneDetached()); - } - NewExplicitCount = NewOperands.size(); - for (const std::int64_t Immediate : Rule.AppendedImmediates) - NewOperands.push_back(MachineOperand::immediate(Immediate)); - NewExplicitCount = NewOperands.size(); + RenderedInstructions.push_back(std::move(Operands)); } - for (std::size_t Index = OriginalExplicitCount; Index < OriginalOperandCount; ++Index) { - SourceToOutput[Index] = NewOperands.size(); - NewOperands.push_back(Instruction.operandAt(Index)->cloneDetached()); + + std::vector AddedInstructions; + std::vector ConstraintSnapshots; + bool RootModified = false; + const auto Rollback = [&](Error Failure) -> Expected { + 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 ErasedTemporaries = eraseTemporaries(Function.registerInfo(), Temporaries); + if (!ErasedTemporaries) + return std::unexpected(ErasedTemporaries.error()); + return std::unexpected(std::move(Failure)); + }; + + 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()); } - if (!Descriptor->Variadic && Descriptor->Operands.size() != NewExplicitCount) { - return makeUnexpected(ErrorCode::VerificationError, - "generated match table result has an incompatible operand count"); + MachineIRBuilder Builder(Function, Target); + MachineInstr *Anchor = &Instruction; + for (std::size_t Index = 1; Index < Rule.Instructions.size(); ++Index) { + auto Point = Builder.setInsertPointAfter(*Anchor); + if (!Point) + return Rollback(Point.error()); + auto Pending = Builder.buildInstr(Rule.Instructions[Index].ResultOpcode); + if (!Pending) + return Rollback(Pending.error()); + for (MachineOperand &Operand : RenderedInstructions[Index]) { + auto Added = Pending->addOperand(std::move(Operand)); + if (!Added) + return Rollback(Added.error()); + } + auto Built = Pending->build(); + if (!Built) + return Rollback(Built.error()); + AddedInstructions.push_back(*Built); + auto Finalized = Finalize(**Built, InputFlags, InputMayRaiseFPException); + if (!Finalized) + return Rollback(Finalized.error()); + Anchor = *Built; } - auto SetOpcode = Instruction.setOpcode(Rule.ResultOpcode); + const MatchedRule::Instruction &RootAction = Rule.Instructions.front(); + RootModified = true; + auto SetOpcode = Instruction.setOpcode(RootAction.ResultOpcode); if (!SetOpcode) - return std::unexpected(SetOpcode.error()); + return Rollback(SetOpcode.error()); while (Instruction.operandCount() != 0) { auto Erased = Instruction.eraseOperand(Instruction.operandCount() - 1U); - if (!Erased) { - auto Restored = restoreInstruction(Instruction, OriginalOpcode, OriginalOperands, Ties); - if (!Restored) - return std::unexpected(Restored.error()); - return std::unexpected(Erased.error()); - } + if (!Erased) + return Rollback(Erased.error()); } - for (MachineOperand &Operand : NewOperands) { + for (MachineOperand &Operand : RenderedInstructions.front()) { auto Added = Instruction.addOperand(std::move(Operand)); - if (!Added) { - auto Restored = restoreInstruction(Instruction, OriginalOpcode, OriginalOperands, Ties); - if (!Restored) - return std::unexpected(Restored.error()); - return std::unexpected(Added.error()); - } + 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 &NewDef = SourceToOutput[OldDef]; const std::optional &NewUse = SourceToOutput[OldUse]; if (!NewDef || !NewUse) continue; - auto Tied = Instruction.tieOperands(NewDef.value(), NewUse.value()); - if (!Tied) { - auto Restored = restoreInstruction(Instruction, OriginalOpcode, OriginalOperands, Ties); - if (!Restored) - return std::unexpected(Restored.error()); - return std::unexpected(Tied.error()); - } + auto Tied = Instruction.tieOperands(*NewDef, *NewUse); + if (!Tied) + return Rollback(Tied.error()); } for (const Register Reg : Rule.EraseOperandDefinitions) { MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); if (Definition == nullptr || Definition == &Instruction || - !isTriviallyDead(*Definition, Function.registerInfo(), Target)) + !isTriviallyDead(*Definition, Function.registerInfo(), Target)) { continue; + } auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); if (!Erased) - return std::unexpected(Erased.error()); + return Rollback(Erased.error()); } return {}; } } // namespace +Expected GIMatchTableExecutor::finalizeGeneratedInstruction( + MachineInstr &, MachineFunction &, const TargetDescription &, MachineInstrFlags, bool) const { + return {}; +} + Expected GIMatchTableExecutor::match(const GIMatchTable &Table, const MachineInstr &Instruction, const MachineFunction &Function, @@ -478,9 +891,11 @@ Expected GIMatchTableExecutor::match(const GIMatchTable &Table, return std::unexpected(Match.error()); if (!*Match) continue; - if (Target.instructionDescriptor((*Match)->ResultOpcode) == nullptr) { - return makeUnexpected(ErrorCode::VerificationError, - "generated match table selects an unknown instruction opcode"); + 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; } @@ -496,7 +911,13 @@ Expected GIMatchTableExecutor::select(const GIMatchTable &Table, MachineIn return std::unexpected(Match.error()); if (!*Match) continue; - auto Applied = applyRule(**Match, Instruction, Function, Target); + auto Applied = applyRule( + **Match, Instruction, Function, Target, + [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) { + return finalizeGeneratedInstruction(Output, Function, Target, InputFlags, + InputMayRaiseFPException); + }); if (!Applied) return std::unexpected(Applied.error()); return true; diff --git a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp index 1f7f453..2e61d8e 100644 --- a/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp +++ b/backend/lib/CodeGen/GlobalISel/InstructionSelect.cpp @@ -199,6 +199,16 @@ Expected InstructionSelector::propagateSelectionFlags(MachineInstr &Output Target); } +Expected InstructionSelector::finalizeGeneratedInstruction( + MachineInstr &Output, MachineFunction &Function, const TargetDescription &Target, + MachineInstrFlags InputFlags, bool InputMayRaiseFPException) const { + auto Flags = + propagateSelectionFlags(Output, InputFlags, InputMayRaiseFPException, Target); + if (!Flags) + return std::unexpected(Flags.error()); + return constrainSelectedInstruction(Output, Function, Target); +} + const MachinePassContract &InstructionSelect::contract() const noexcept { return instructionSelectContract(); } diff --git a/backend/lib/CodeGen/TargetDescription.cpp b/backend/lib/CodeGen/TargetDescription.cpp index a867a5b..ab77965 100644 --- a/backend/lib/CodeGen/TargetDescription.cpp +++ b/backend/lib/CodeGen/TargetDescription.cpp @@ -17,6 +17,7 @@ #include #include #include +#include #include #include @@ -342,8 +343,12 @@ Expected TargetDescription::validateTargetOperand(const OperandDescriptor if (Descriptor != nullptr && Descriptor->RegClass) { const auto EffectiveClass = effectiveRegisterClass(Operand, RegInfo); if (!EffectiveClass || !Registers.isSubclass(*EffectiveClass, *Descriptor->RegClass)) { - return makeUnexpected(ErrorCode::VerificationError, - "virtual register class does not satisfy the operand descriptor"); + const std::string ActualClass = + EffectiveClass ? std::to_string(EffectiveClass->value()) : ""; + return makeUnexpected( + ErrorCode::VerificationError, + "virtual register class " + ActualClass + " does not satisfy required class " + + std::to_string(Descriptor->RegClass->value())); } } return {}; @@ -464,7 +469,9 @@ TargetDescription::validateExplicitOperands(Opcode InstructionOpcode, auto TargetValidation = validateTargetOperand(&descriptorForOperand(*Descriptor, Index), Operands[Index], RegInfo); if (!TargetValidation) - return std::unexpected(TargetValidation.error()); + return std::unexpected(withErrorContext( + TargetValidation.error(), "operand " + std::to_string(Index) + " of '" + + Descriptor->Name + "': ")); } return {}; } diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp index 9807534..c194448 100644 --- a/backend/lib/TableGen/Parser.cpp +++ b/backend/lib/TableGen/Parser.cpp @@ -1180,25 +1180,53 @@ private: for (const yaml::NodeID ElementID : Node.sequence()) { const yaml::Node *Element = Input.node(ElementID); if (!requireMapping(Element, "selection operand definition constant") || - !checkKeys(*Element, {"index", "value"}, "selection operand definition constant")) { + !checkKeys(*Element, {"index", "ranges"}, "selection operand definition constant")) { return false; } const yaml::Node *IndexNode = requiredNode(*Element, "index", "selection operand definition constant"); - const yaml::Node *ValueNode = - requiredNode(*Element, "value", "selection operand definition constant"); - if (IndexNode == nullptr || ValueNode == nullptr) + const yaml::Node *RangesNode = + requiredNode(*Element, "ranges", "selection operand definition constant"); + if (IndexNode == nullptr || RangesNode == nullptr) return false; const auto Index = unsignedInteger32(*IndexNode, "selection operand definition constant index"); - const auto Value = signedInteger(*ValueNode, "selection operand definition constant value"); - if (!Index || !Value) + if (!Index || !requireSequence(RangesNode, "selection operand definition constant ranges") || + RangesNode->sequence().empty()) { return false; - Result.push_back({ + } + + SourceSelectionOperandDefConstantPredicate Predicate{ .OperandIndex = *Index, - .Value = *Value, + .Ranges = {}, .Range = Element->range(), - }); + }; + for (const yaml::NodeID RangeID : RangesNode->sequence()) { + const yaml::Node *Range = Input.node(RangeID); + if (!requireMapping(Range, "selection operand definition constant range") || + !checkKeys(*Range, {"min", "max"}, "selection operand definition constant range")) { + return false; + } + const yaml::Node *MinimumNode = + requiredNode(*Range, "min", "selection operand definition constant range"); + const yaml::Node *MaximumNode = + requiredNode(*Range, "max", "selection operand definition constant range"); + if (MinimumNode == nullptr || MaximumNode == nullptr) + return false; + const auto Minimum = signedInteger(*MinimumNode, "selection constant range minimum"); + const auto Maximum = signedInteger(*MaximumNode, "selection constant range maximum"); + if (!Minimum || !Maximum || *Minimum > *Maximum) { + if (Minimum && Maximum) + fail(Range->range(), "selection operand definition constant range is invalid"); + return false; + } + Predicate.Ranges.push_back({ + .Minimum = *Minimum, + .Maximum = *Maximum, + .SourceRange = Range->range(), + }); + } + Result.push_back(std::move(Predicate)); } return true; } @@ -1211,20 +1239,33 @@ private: for (const yaml::NodeID ElementID : Node.sequence()) { const yaml::Node *Element = Input.node(ElementID); if (!requireMapping(Element, "selection operand renderer") || - !checkKeys(*Element, {"operand", "physical_register", "flags"}, + !checkKeys(*Element, + {"operand", "physical_register", "temporary", "captured_immediate", + "immediate", "transform", "flags"}, "selection operand renderer")) { return false; } const yaml::Node *OperandNode = optionalNode(*Element, "operand"); const yaml::Node *PhysicalRegisterNode = optionalNode(*Element, "physical_register"); - if ((OperandNode == nullptr) == (PhysicalRegisterNode == nullptr)) { - fail(Element->range(), "selection operand renderer requires exactly one of 'operand' or " - "'physical_register'"); + const yaml::Node *TemporaryNode = optionalNode(*Element, "temporary"); + const yaml::Node *CapturedImmediateNode = optionalNode(*Element, "captured_immediate"); + const yaml::Node *ImmediateNode = optionalNode(*Element, "immediate"); + const std::uint32_t SourceCount = static_cast(OperandNode != nullptr) + + static_cast(PhysicalRegisterNode != nullptr) + + static_cast(TemporaryNode != nullptr) + + static_cast(CapturedImmediateNode != nullptr) + + static_cast(ImmediateNode != nullptr); + if (SourceCount != 1) { + fail(Element->range(), "selection operand renderer requires exactly one source"); return false; } SourceSelectionOperandRenderer Renderer{ .OperandIndex = std::nullopt, .PhysicalRegisterSymbol = {}, + .TemporarySymbol = {}, + .CapturedImmediateOperand = std::nullopt, + .Immediate = std::nullopt, + .ImmediateTransform = "identity", .Flags = {}, .Range = Element->range(), }; @@ -1233,12 +1274,38 @@ private: if (!Index) return false; Renderer.OperandIndex = Index; - } else { + } else if (PhysicalRegisterNode != nullptr) { const auto Symbol = scalar(*PhysicalRegisterNode, "selection operand renderer physical register"); if (!Symbol) return false; Renderer.PhysicalRegisterSymbol = *Symbol; + } else if (TemporaryNode != nullptr) { + const auto Symbol = scalar(*TemporaryNode, "selection operand renderer temporary"); + if (!Symbol) + return false; + Renderer.TemporarySymbol = *Symbol; + } else if (CapturedImmediateNode != nullptr) { + const auto Index = + unsignedInteger32(*CapturedImmediateNode, "selection operand renderer captured immediate"); + if (!Index) + return false; + Renderer.CapturedImmediateOperand = *Index; + } else { + const auto Value = signedInteger(*ImmediateNode, "selection operand renderer immediate"); + if (!Value) + return false; + Renderer.Immediate = *Value; + } + if (const yaml::Node *TransformNode = optionalNode(*Element, "transform")) { + const auto Transform = scalar(*TransformNode, "selection operand renderer transform"); + if (!Transform) + return false; + Renderer.ImmediateTransform = *Transform; + } + if (!Renderer.CapturedImmediateOperand && Renderer.ImmediateTransform != "identity") { + fail(Element->range(), "selection operand renderer transform requires a captured immediate"); + return false; } if (const yaml::Node *FlagsNode = optionalNode(*Element, "flags")) { const auto Flags = scalarSequence(*FlagsNode, "selection operand renderer flags"); @@ -1251,6 +1318,63 @@ private: return true; } + [[nodiscard]] bool parseSelectionTemporaries(const yaml::Node &Node, + std::vector &Result) { + if (!requireSequence(&Node, "selection temporaries")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "selection temporary") || + !checkKeys(*Element, {"id", "type_from_operand"}, "selection temporary")) { + return false; + } + const auto Symbol = requiredScalar(*Element, "id", "selection temporary"); + const yaml::Node *TypeNode = requiredNode(*Element, "type_from_operand", "selection temporary"); + if (!Symbol || TypeNode == nullptr) + return false; + const auto TypeFromOperand = unsignedInteger32(*TypeNode, "selection temporary type operand"); + if (!TypeFromOperand) + return false; + Result.push_back({ + .Symbol = *Symbol, + .TypeFromOperand = *TypeFromOperand, + .Range = Element->range(), + }); + } + return true; + } + + [[nodiscard]] bool parseSelectionActions(const yaml::Node &Node, + std::vector &Result) { + if (!requireSequence(&Node, "selection instructions")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "selection instruction") || + !checkKeys(*Element, {"opcode", "root", "operands"}, "selection instruction")) { + return false; + } + const auto Opcode = requiredScalar(*Element, "opcode", "selection instruction"); + const yaml::Node *RootNode = requiredNode(*Element, "root", "selection instruction"); + const yaml::Node *OperandsNode = requiredNode(*Element, "operands", "selection instruction"); + if (!Opcode || RootNode == nullptr || OperandsNode == nullptr) + return false; + const auto ReplacesRoot = boolean(*RootNode, "selection instruction root"); + if (!ReplacesRoot) + return false; + std::vector Renderers; + if (!parseSelectionOperandRenderers(*OperandsNode, Renderers)) + return false; + Result.push_back({ + .ResultOpcodeSymbol = *Opcode, + .ReplacesRoot = *ReplacesRoot, + .OperandRenderers = std::move(Renderers), + .Range = Element->range(), + }); + } + return true; + } + [[nodiscard]] bool parseSelectionRuleMatch(const yaml::Node &Node, SourceSelectionRule &Result) { if (!requireMapping(&Node, "selection rule match") || !checkKeys(Node, @@ -1294,26 +1418,19 @@ private: [[nodiscard]] bool parseSelectionRuleApply(const yaml::Node &Node, SourceSelectionRule &Result) { if (!requireMapping(&Node, "selection rule apply") || - !checkKeys(Node, {"opcode", "append_immediates", "operands", "erase_operand_definitions"}, + !checkKeys(Node, {"temporaries", "instructions", "erase_operand_definitions"}, "selection rule apply")) { return false; } - const auto Opcode = requiredScalar(Node, "opcode", "selection rule apply"); - if (!Opcode) + const yaml::Node *Instructions = requiredNode(Node, "instructions", "selection rule apply"); + if (Instructions == nullptr) return false; - Result.ResultOpcodeSymbol = *Opcode; - if (const yaml::Node *Immediates = optionalNode(Node, "append_immediates")) { - auto Values = signedIntegerSequence(*Immediates, "selection rule appended immediates"); - if (!Values) + if (const yaml::Node *Temporaries = optionalNode(Node, "temporaries")) { + if (!parseSelectionTemporaries(*Temporaries, Result.Temporaries)) return false; - Result.AppendedImmediates = std::move(*Values); - } - if (const yaml::Node *Operands = optionalNode(Node, "operands")) { - std::vector Renderers; - if (!parseSelectionOperandRenderers(*Operands, Renderers)) - return false; - Result.OperandRenderers = std::move(Renderers); } + if (!parseSelectionActions(*Instructions, Result.Actions)) + return false; if (const yaml::Node *Erase = optionalNode(Node, "erase_operand_definitions")) { auto Indices = unsignedInteger32Sequence(*Erase, "selection operand definitions"); if (!Indices) diff --git a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp index 68574a3..38ef1af 100644 --- a/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp +++ b/backend/lib/Target/RISCV/GISel/RISCVInstructionSelector.cpp @@ -268,7 +268,6 @@ public: case GenericOpcode::G_SEXT: case GenericOpcode::G_SEXT_INREG: case GenericOpcode::G_ZEXT: - case GenericOpcode::G_ICMP: case GenericOpcode::G_FCMP: case GenericOpcode::G_FPEXT: case GenericOpcode::G_FPTRUNC: @@ -476,8 +475,6 @@ public: return Instruction.setOpcode(opcode(GenericOpcode::COPY)); case GenericOpcode::G_SEXT_INREG: return selectSignExtendInRegister(Instruction, Function, Target, Type); - case GenericOpcode::G_ICMP: - return selectIntegerCompare(Instruction, Function, Target); case GenericOpcode::G_FCMP: return selectFloatingCompare(Instruction, Function, Target); case GenericOpcode::G_FPEXT: @@ -748,9 +745,9 @@ private: const TargetDescription &Target, Register Source, LowLevelType Type, bool Signed) const { - if (!isSupportedIntegerScalar(Type)) + if (!isSupportedIntegerType(Type)) return makeUnexpected(ErrorCode::Unsupported, - "RISC-V integer normalization requires a scalar i1-i64 type"); + "RISC-V integer normalization requires an integer scalar or a 64-bit pointer"); const std::uint32_t Bits = Type.scalarBitWidth(); if (Bits == 64) return Source; @@ -1741,175 +1738,6 @@ private: return {}; } - [[nodiscard]] Expected selectIntegerCompare(MachineInstr &Instruction, - MachineFunction &Function, - const TargetDescription &Target) const { - const MachineOperand *PredicateMO = Instruction.operandAt(1); - const auto *Predicate = - PredicateMO == nullptr ? nullptr : PredicateMO->getIf(); - const MachineOperand *DestinationOperand = Instruction.operandAt(0); - const MachineOperand *LeftOperand = Instruction.operandAt(2); - const MachineOperand *RightOperand = Instruction.operandAt(3); - const Register *Destination = - DestinationOperand == nullptr ? nullptr : DestinationOperand->getIf(); - const Register *Left = LeftOperand == nullptr ? nullptr : LeftOperand->getIf(); - const Register *Right = RightOperand == nullptr ? nullptr : RightOperand->getIf(); - const std::optional LeftType = operandType(Function, Instruction, 2); - if (Predicate == nullptr || Predicate->integerPredicate() == nullptr || - Destination == nullptr || Left == nullptr || Right == nullptr || !LeftType) - return makeUnexpected(ErrorCode::VerificationError, - "RISC-V integer comparison has invalid operands"); - const IntegerPredicate Condition = *Predicate->integerPredicate(); - const Register DestinationRegister = *Destination; - const bool SignedOperands = Condition == IntegerPredicate::SignedGreaterThan || - Condition == IntegerPredicate::SignedGreaterEqual || - Condition == IntegerPredicate::SignedLessThan || - Condition == IntegerPredicate::SignedLessEqual; - auto LeftRegister = - normalizeIntegerBefore(Instruction, Function, Target, *Left, *LeftType, SignedOperands); - auto RightRegister = - normalizeIntegerBefore(Instruction, Function, Target, *Right, *LeftType, SignedOperands); - if (!LeftRegister || !RightRegister) - return std::unexpected(!LeftRegister ? LeftRegister.error() : RightRegister.error()); - auto ErasePredicate = Instruction.eraseOperand(1); - if (!ErasePredicate) - return std::unexpected(ErasePredicate.error()); - - const auto SetSources = [&Instruction](Register NewLeft, Register NewRight) -> Expected { - auto SetLeft = Instruction.operandAt(1)->setRegister(NewLeft); - if (!SetLeft) - return std::unexpected(SetLeft.error()); - return Instruction.operandAt(2)->setRegister(NewRight); - }; - const auto StrictOpcode = [](IntegerPredicate Value) -> std::optional { - switch (Value) { - case IntegerPredicate::SignedLessThan: - return InstructionOpcode::SLT; - case IntegerPredicate::UnsignedLessThan: - return InstructionOpcode::SLTU; - default: - return std::nullopt; - } - }; - - IntegerPredicate StrictCondition = Condition; - bool Swap = false; - bool Invert = false; - switch (Condition) { - case IntegerPredicate::Equal: - case IntegerPredicate::NotEqual: - break; - case IntegerPredicate::SignedGreaterThan: - StrictCondition = IntegerPredicate::SignedLessThan; - Swap = true; - break; - case IntegerPredicate::SignedGreaterEqual: - StrictCondition = IntegerPredicate::SignedLessThan; - Invert = true; - break; - case IntegerPredicate::SignedLessThan: - StrictCondition = IntegerPredicate::SignedLessThan; - break; - case IntegerPredicate::SignedLessEqual: - StrictCondition = IntegerPredicate::SignedLessThan; - Swap = true; - Invert = true; - break; - case IntegerPredicate::UnsignedGreaterThan: - StrictCondition = IntegerPredicate::UnsignedLessThan; - Swap = true; - break; - case IntegerPredicate::UnsignedGreaterEqual: - StrictCondition = IntegerPredicate::UnsignedLessThan; - Invert = true; - break; - case IntegerPredicate::UnsignedLessThan: - StrictCondition = IntegerPredicate::UnsignedLessThan; - break; - case IntegerPredicate::UnsignedLessEqual: - StrictCondition = IntegerPredicate::UnsignedLessThan; - Swap = true; - Invert = true; - break; - case IntegerPredicate::Count: - return makeUnexpected(ErrorCode::Unsupported, - "RISC-V integer comparison predicate is invalid"); - } - - MachineIRBuilder Builder(Function, Target); - if (Condition == IntegerPredicate::Equal || Condition == IntegerPredicate::NotEqual) { - auto Temporary = createTemporary(Function, *LeftType, Target); - if (!Temporary) - return std::unexpected(Temporary.error()); - auto SetDestination = Instruction.operandAt(0)->setRegister(*Temporary); - if (!SetDestination) - return std::unexpected(SetDestination.error()); - auto Set = SetSources(*LeftRegister, *RightRegister); - if (!Set) - return std::unexpected(Set.error()); - auto SetOpcode = Instruction.setOpcode(instructionOpcode(InstructionOpcode::XOR)); - if (!SetOpcode) - return std::unexpected(SetOpcode.error()); - if (Condition == IntegerPredicate::Equal) { - auto Result = buildImmediateAfter(Builder, Instruction, InstructionOpcode::SLTIU, - DestinationRegister, *Temporary, 1); - if (!Result) - return std::unexpected(Result.error()); - } else { - auto Zero = physicalRegister(PhysicalRegisterID::X0); - if (!Zero) - return std::unexpected(Zero.error()); - auto Result = - buildBinaryAfter(Builder, Instruction, InstructionOpcode::SLTU, DestinationRegister, - Register::fromPhysical(*Zero), *Temporary); - if (!Result) - return std::unexpected(Result.error()); - } - return {}; - } - - const std::optional OpcodeValue = StrictOpcode(StrictCondition); - if (!OpcodeValue) - return makeUnexpected(ErrorCode::Unsupported, - "RISC-V integer comparison predicate is invalid"); - if (Invert) { - auto Temporary = createTemporary(Function, *LeftType, Target); - if (!Temporary) - return std::unexpected(Temporary.error()); - auto SetDestination = Instruction.operandAt(0)->setRegister(*Temporary); - if (!SetDestination) - return std::unexpected(SetDestination.error()); - const Register Base = *Temporary; - if (Swap) { - auto Set = SetSources(*RightRegister, *LeftRegister); - if (!Set) - return std::unexpected(Set.error()); - } else { - auto Set = SetSources(*LeftRegister, *RightRegister); - if (!Set) - return std::unexpected(Set.error()); - } - auto SetOpcode = Instruction.setOpcode(instructionOpcode(*OpcodeValue)); - if (!SetOpcode) - return std::unexpected(SetOpcode.error()); - auto Result = buildImmediateAfter(Builder, Instruction, InstructionOpcode::XORI, - DestinationRegister, Base, 1); - if (!Result) - return std::unexpected(Result.error()); - return {}; - } - if (Swap) { - auto Set = SetSources(*RightRegister, *LeftRegister); - if (!Set) - return std::unexpected(Set.error()); - } else { - auto Set = SetSources(*LeftRegister, *RightRegister); - if (!Set) - return std::unexpected(Set.error()); - } - return Instruction.setOpcode(instructionOpcode(*OpcodeValue)); - } - [[nodiscard]] Expected selectFloatingCompare(MachineInstr &Instruction, MachineFunction &Function, const TargetDescription &Target) const { diff --git a/backend/lib/Target/RISCV/RISCVGISel.rccdesc b/backend/lib/Target/RISCV/RISCVGISel.rccdesc index bd946be..d8b0a42 100644 --- a/backend/lib/Target/RISCV/RISCVGISel.rccdesc +++ b/backend/lib/Target/RISCV/RISCVGISel.rccdesc @@ -12,7 +12,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: SLLW } + apply: + instructions: + - opcode: SLLW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_sraw priority: 100 @@ -26,7 +30,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: SRAW } + apply: + instructions: + - opcode: SRAW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_srlw priority: 100 @@ -40,7 +48,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: SRLW } + apply: + instructions: + - opcode: SRLW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_divw priority: 100 @@ -54,7 +66,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: DIVW } + apply: + instructions: + - opcode: DIVW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_divuw priority: 100 @@ -68,7 +84,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: DIVUW } + apply: + instructions: + - opcode: DIVUW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_remuw priority: 100 @@ -82,7 +102,11 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: GPR } - { index: 2, bank: GPR } - apply: { opcode: REMUW } + apply: + instructions: + - opcode: REMUW + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_fcvt_w_rv64_s32 priority: 100 @@ -94,7 +118,11 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCVT_W_S } + apply: + instructions: + - opcode: FCVT_W_S + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_fcvt_w_rv64_s64 priority: 100 @@ -106,7 +134,11 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCVT_W_D } + apply: + instructions: + - opcode: FCVT_W_D + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_fcvt_wu_rv64_s32 priority: 100 @@ -118,7 +150,11 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCVT_WU_S } + apply: + instructions: + - opcode: FCVT_WU_S + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_fcvt_wu_rv64_s64 priority: 100 @@ -130,7 +166,11 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCVT_WU_D } + apply: + instructions: + - opcode: FCVT_WU_D + root: true + operands: [{ operand: 0 }, { operand: 1 }, { operand: 2 }] - id: select_g_fclass_s32 priority: 100 @@ -142,7 +182,11 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCLASS_S } + apply: + instructions: + - opcode: FCLASS_S + root: true + operands: [{ operand: 0 }, { operand: 1 }] - id: select_g_fclass_s64 priority: 100 @@ -154,10 +198,207 @@ selection_rules: operand_banks: - { index: 0, bank: GPR } - { index: 1, bank: FPR } - apply: { opcode: FCLASS_D } + apply: + instructions: + - opcode: FCLASS_D + root: true + operands: [{ operand: 0 }, { operand: 1 }] + - + id: select_g_icmp_eq_zero + priority: 500 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: eq } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: 0, max: 0 }] + apply: + instructions: + - opcode: SLTIU + root: true + operands: [{ operand: 0 }, { operand: 2 }, { immediate: 1 }] + erase_operand_definitions: [3] - id: select_g_icmp_ne_zero - priority: 200 + priority: 500 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ne } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: 0, max: 0 }] + apply: + instructions: + - opcode: SLTU + root: true + operands: + - { operand: 0 } + - { physical_register: X0, flags: [use] } + - { operand: 2 } + erase_operand_definitions: [3] + - + id: select_g_icmp_ult_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ult } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: -2048, max: 2047 }] + apply: + instructions: + - opcode: SLTIU + root: true + operands: + - { operand: 0 } + - { operand: 2 } + - { captured_immediate: 3 } + erase_operand_definitions: [3] + - + id: select_g_icmp_slt_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: slt } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: -2048, max: 2047 }] + apply: + instructions: + - opcode: SLTI + root: true + operands: + - { operand: 0 } + - { operand: 2 } + - { captured_immediate: 3 } + erase_operand_definitions: [3] + - + id: select_g_icmp_ugt_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ugt } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: + - { min: -2049, max: -2 } + - { min: 1, max: 2046 } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTIU + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3, transform: plus_one } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + erase_operand_definitions: [3] + - + id: select_g_icmp_sgt_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sgt } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: + - { min: -2049, max: -1 } + - { min: 1, max: 2046 } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTI + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3, transform: plus_one } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + erase_operand_definitions: [3] + - + id: select_g_icmp_eq_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: eq } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: -2047, max: 2048 }] + apply: + temporaries: + - { id: difference, type_from_operand: 2 } + instructions: + - opcode: ADDI + root: true + operands: + - { temporary: difference, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3, transform: negate } + - opcode: SLTIU + root: false + operands: + - { operand: 0 } + - { temporary: difference, flags: [use] } + - { immediate: 1 } + erase_operand_definitions: [3] + - + id: select_g_icmp_ne_immediate + priority: 400 match: opcode: G_ICMP result_type: { kind: scalar, bits: 64 } @@ -168,11 +409,384 @@ selection_rules: - { index: 0, bank: GPR } - { index: 2, bank: GPR } operand_def_constants: - - { index: 3, value: 0 } + - index: 3 + ranges: [{ min: -2047, max: 2048 }] + apply: + temporaries: + - { id: difference, type_from_operand: 2 } + instructions: + - opcode: ADDI + root: true + operands: + - { temporary: difference, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3, transform: negate } + - opcode: SLTU + root: false + operands: + - { operand: 0 } + - { physical_register: X0, flags: [use] } + - { temporary: difference, flags: [use] } + erase_operand_definitions: [3] + - + id: select_g_icmp_ule_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ule } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: + - { min: -2049, max: -2 } + - { min: 1, max: 2046 } + apply: + instructions: + - opcode: SLTIU + root: true + operands: + - { operand: 0 } + - { operand: 2 } + - { captured_immediate: 3, transform: plus_one } + erase_operand_definitions: [3] + - + id: select_g_icmp_sle_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sle } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: + - { min: -2049, max: -1 } + - { min: 1, max: 2046 } + apply: + instructions: + - opcode: SLTI + root: true + operands: + - { operand: 0 } + - { operand: 2 } + - { captured_immediate: 3, transform: plus_one } + erase_operand_definitions: [3] + - + id: select_g_icmp_uge_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: uge } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: -2048, max: 2047 }] apply: - opcode: SLTU - operands: - - { operand: 0 } - - { physical_register: X0, flags: [use] } - - { operand: 2 } + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTIU + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } erase_operand_definitions: [3] + - + id: select_g_icmp_sge_immediate + priority: 400 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sge } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - index: 3 + ranges: [{ min: -2048, max: 2047 }] + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTI + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { captured_immediate: 3 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + erase_operand_definitions: [3] + - + id: select_g_icmp_ult_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ult } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + instructions: + - opcode: SLTU + root: true + operands: [{ operand: 0 }, { operand: 2 }, { operand: 3 }] + - + id: select_g_icmp_slt_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: slt } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + instructions: + - opcode: SLT + root: true + operands: [{ operand: 0 }, { operand: 2 }, { operand: 3 }] + - + id: select_g_icmp_ugt_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ugt } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + instructions: + - opcode: SLTU + root: true + operands: [{ operand: 0 }, { operand: 3 }, { operand: 2 }] + - + id: select_g_icmp_sgt_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sgt } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + instructions: + - opcode: SLT + root: true + operands: [{ operand: 0 }, { operand: 3 }, { operand: 2 }] + - + id: select_g_icmp_eq_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: eq } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: difference, type_from_operand: 2 } + instructions: + - opcode: XOR + root: true + operands: + - { temporary: difference, flags: [define] } + - { operand: 2 } + - { operand: 3 } + - opcode: SLTIU + root: false + operands: + - { operand: 0 } + - { temporary: difference, flags: [use] } + - { immediate: 1 } + - + id: select_g_icmp_ne_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ne } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: difference, type_from_operand: 2 } + instructions: + - opcode: XOR + root: true + operands: + - { temporary: difference, flags: [define] } + - { operand: 2 } + - { operand: 3 } + - opcode: SLTU + root: false + operands: + - { operand: 0 } + - { physical_register: X0, flags: [use] } + - { temporary: difference, flags: [use] } + - + id: select_g_icmp_ule_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ule } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTU + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 3 } + - { operand: 2 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + - + id: select_g_icmp_sle_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sle } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLT + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 3 } + - { operand: 2 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + - + id: select_g_icmp_uge_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: uge } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLTU + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { operand: 3 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } + - + id: select_g_icmp_sge_register + priority: 100 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: sge } + operand_types: + - { index: 2, kind: any, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + - { index: 3, bank: GPR } + apply: + temporaries: + - { id: compare, type_from_operand: 2 } + instructions: + - opcode: SLT + root: true + operands: + - { temporary: compare, flags: [define] } + - { operand: 2 } + - { operand: 3 } + - opcode: XORI + root: false + operands: + - { operand: 0 } + - { temporary: compare, flags: [use] } + - { immediate: 1 } diff --git a/backend/utils/TableGen/Common/CodeGenSelection.cpp b/backend/utils/TableGen/Common/CodeGenSelection.cpp index cc80e41..1e65e04 100644 --- a/backend/utils/TableGen/Common/CodeGenSelection.cpp +++ b/backend/utils/TableGen/Common/CodeGenSelection.cpp @@ -11,7 +11,9 @@ #include #include #include +#include #include +#include #include #include @@ -135,31 +137,18 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { std::unordered_set Symbols; for (const SourceSelectionRule &Rule : Input.SelectionRules) { const auto MatchOpcode = resolveOpcode(Result, Rule.MatchOpcodeSymbol); - const auto ResultOpcode = resolveOpcode(Result, Rule.ResultOpcodeSymbol); const NormalizedInstruction *MatchInstruction = findInstructionBySymbol(Result, Rule.MatchOpcodeSymbol); - const NormalizedInstruction *ResultInstruction = - findInstructionBySymbol(Result, Rule.ResultOpcodeSymbol); - if (!isIdentifier(Rule.Symbol) || !Symbols.insert(Rule.Symbol).second || !MatchOpcode || - !ResultOpcode) { - fail(Rule.Range, - "selection rules require a unique identifier and declared match/result opcodes"); + if (!isIdentifier(Rule.Symbol) || !Symbols.insert(Rule.Symbol).second || !MatchOpcode) { + fail(Rule.Range, "selection rules require a unique identifier and declared match opcode"); return false; } if (MatchInstruction != nullptr && !std::ranges::contains(MatchInstruction->Flags, "Generic")) { fail(Rule.Range, "selection rule match opcode must be generic"); return false; } - if (isGenericOpcode(Opcode::fromValue(*ResultOpcode)) || - (ResultInstruction != nullptr && - std::ranges::contains(ResultInstruction->Flags, "Generic"))) { - fail(Rule.Range, "selection rule result opcode must not be generic"); - return false; - } - if (!Rule.OperandRenderers && MatchInstruction != nullptr && ResultInstruction != nullptr && - ResultInstruction->Operands.size() != - MatchInstruction->Operands.size() + Rule.AppendedImmediates.size()) { - fail(Rule.Range, "selection rule result opcode has an incompatible operand count"); + if (Rule.Actions.empty()) { + fail(Rule.Range, "selection rule requires at least one generated instruction"); return false; } @@ -187,8 +176,6 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { Normalized.Priority = Rule.Priority; Normalized.Specificity = 1; Normalized.MatchOpcode = *MatchOpcode; - Normalized.ResultOpcode = *ResultOpcode; - Normalized.AppendedImmediates = Rule.AppendedImmediates; Normalized.EraseOperandDefinitions = Rule.EraseOperandDefinitions; if (Rule.ResultType) { auto Type = NormalizeType(*Rule.ResultType); @@ -278,32 +265,98 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { for (const SourceSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants) { if (!ConstantOperands.insert(Predicate.OperandIndex).second || (MatchInstruction != nullptr && - !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex))) { + !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex)) || Predicate.Ranges.empty()) { fail(Predicate.Range, "selection operand definition constant predicates require distinct register " - "operands"); + "operands and at least one range"); return false; } - Normalized.OperandDefConstants.push_back( - {.OperandIndex = Predicate.OperandIndex, .Value = Predicate.Value}); + NormalizedSelectionOperandDefConstantPredicate NormalizedPredicate{ + .OperandIndex = Predicate.OperandIndex, + .Ranges = {}, + }; + for (const SourceSelectionOperandDefConstantPredicate::ConstantRange &Range : + Predicate.Ranges) { + if (Range.Minimum > Range.Maximum) { + fail(Range.SourceRange, "selection operand definition constant range is invalid"); + return false; + } + NormalizedPredicate.Ranges.push_back({ + .Minimum = Range.Minimum, + .Maximum = Range.Maximum, + }); + } + std::ranges::sort(NormalizedPredicate.Ranges, {}, + &NormalizedSelectionOperandDefConstantPredicate::Range::Minimum); + for (std::size_t Index = 1; Index < NormalizedPredicate.Ranges.size(); ++Index) { + const auto &Previous = NormalizedPredicate.Ranges[Index - 1]; + const auto &Current = NormalizedPredicate.Ranges[Index]; + if (Current.Minimum <= Previous.Maximum) { + fail(Predicate.Range, "selection operand definition constant ranges overlap"); + return false; + } + } + Normalized.OperandDefConstants.push_back(std::move(NormalizedPredicate)); ++Normalized.Specificity; } - if (Rule.OperandRenderers) { - if (!Rule.AppendedImmediates.empty()) { - fail(Rule.Range, "selection rule cannot combine operand renderers and appended immediates"); + std::unordered_map TemporaryIDs; + for (const SourceSelectionTemporary &Temporary : Rule.Temporaries) { + if (!isIdentifier(Temporary.Symbol) || + !TemporaryIDs.emplace(Temporary.Symbol, TemporaryIDs.size() + 1U).second || + (MatchInstruction != nullptr && + !isRegisterOperand(*MatchInstruction, Temporary.TypeFromOperand))) { + fail(Temporary.Range, + "selection temporary requires a unique identifier and a register type source"); + return false; + } + Normalized.Temporaries.push_back({ + .ID = TemporaryIDs.at(Temporary.Symbol), + .TypeFromOperand = Temporary.TypeFromOperand, + }); + } + + bool HasRootAction = false; + for (std::size_t ActionIndex = 0; ActionIndex < Rule.Actions.size(); ++ActionIndex) { + const SourceSelectionAction &Action = Rule.Actions[ActionIndex]; + const auto ResultOpcode = resolveOpcode(Result, Action.ResultOpcodeSymbol); + const NormalizedInstruction *ResultInstruction = + findInstructionBySymbol(Result, Action.ResultOpcodeSymbol); + if (!ResultOpcode || ResultInstruction == nullptr || + isGenericOpcode(Opcode::fromValue(*ResultOpcode)) || + std::ranges::contains(ResultInstruction->Flags, "Generic")) { + fail(Action.Range, "selection instruction opcode must name a declared target instruction"); + return false; + } + if (Action.ReplacesRoot == HasRootAction || (Action.ReplacesRoot && ActionIndex != 0)) { + fail(Action.Range, + "selection instructions require exactly one root replacement as their first action"); return false; } - std::vector Renderers; - Renderers.reserve(Rule.OperandRenderers->size()); - for (const SourceSelectionOperandRenderer &Renderer : *Rule.OperandRenderers) { + HasRootAction |= Action.ReplacesRoot; + if (ResultInstruction->Operands.size() != Action.OperandRenderers.size()) { + fail(Action.Range, "selection instruction has an incompatible operand count"); + return false; + } + + NormalizedSelectionAction NormalizedAction{ + .ResultOpcode = *ResultOpcode, + .ReplacesRoot = Action.ReplacesRoot, + .OperandRenderers = {}, + }; + NormalizedAction.OperandRenderers.reserve(Action.OperandRenderers.size()); + for (const SourceSelectionOperandRenderer &Renderer : Action.OperandRenderers) { if (Renderer.OperandIndex) { if (MatchInstruction != nullptr && *Renderer.OperandIndex >= MatchInstruction->Operands.size()) { fail(Renderer.Range, "selection operand renderer references an unknown operand"); return false; } - Renderers.push_back({ + if (!Renderer.Flags.empty()) { + fail(Renderer.Range, "selection operand renderer cannot replace source register flags"); + return false; + } + NormalizedAction.OperandRenderers.push_back({ .SourceKind = NormalizedSelectionOperandRenderer::Kind::Operand, .Value = *Renderer.OperandIndex, .Flags = 0, @@ -311,34 +364,90 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { continue; } - const NormalizedRegister *Physical = - findRegisterBySymbol(Result, Renderer.PhysicalRegisterSymbol); - const auto Flags = registerOperandFlags(Renderer.Flags); - if (Physical == nullptr || Physical->ID == 0 || !Flags) { - fail(Renderer.Range, - "selection physical register renderer requires a declared register and valid " - "register flags"); - return false; + if (!Renderer.PhysicalRegisterSymbol.empty()) { + const NormalizedRegister *Physical = + findRegisterBySymbol(Result, Renderer.PhysicalRegisterSymbol); + const auto Flags = registerOperandFlags(Renderer.Flags); + if (Physical == nullptr || Physical->ID == 0 || !Flags || + !validRegisterOperandFlags(*Flags)) { + fail(Renderer.Range, + "selection physical register renderer requires a declared register and valid " + "register flags"); + return false; + } + NormalizedAction.OperandRenderers.push_back({ + .SourceKind = NormalizedSelectionOperandRenderer::Kind::PhysicalRegister, + .Value = Physical->ID, + .Flags = Flags->rawValue(), + }); + continue; } - if (!validRegisterOperandFlags(*Flags)) { - fail(Renderer.Range, "selection physical register renderer is invalid"); - return false; + + if (!Renderer.TemporarySymbol.empty()) { + const auto Temporary = TemporaryIDs.find(Renderer.TemporarySymbol); + const auto Flags = registerOperandFlags(Renderer.Flags); + if (Temporary == TemporaryIDs.end() || !Flags || !validRegisterOperandFlags(*Flags)) { + fail(Renderer.Range, + "selection temporary renderer requires a declared temporary and valid register " + "flags"); + return false; + } + NormalizedAction.OperandRenderers.push_back({ + .SourceKind = NormalizedSelectionOperandRenderer::Kind::Temporary, + .Value = Temporary->second, + .Flags = Flags->rawValue(), + }); + continue; } - Renderers.push_back({ - .SourceKind = NormalizedSelectionOperandRenderer::Kind::PhysicalRegister, - .Value = Physical->ID, - .Flags = Flags->rawValue(), - }); - } - if (ResultInstruction != nullptr && ResultInstruction->Operands.size() != Renderers.size()) { - fail(Rule.Range, "selection operand renderer has an incompatible operand count"); + + if (Renderer.CapturedImmediateOperand) { + const auto Transform = [&Renderer]() + -> std::optional { + if (Renderer.ImmediateTransform == "identity") + return NormalizedSelectionImmediateTransform::Identity; + if (Renderer.ImmediateTransform == "negate") + return NormalizedSelectionImmediateTransform::Negate; + if (Renderer.ImmediateTransform == "plus_one") + return NormalizedSelectionImmediateTransform::PlusOne; + return std::nullopt; + }(); + if (!ConstantOperands.contains(*Renderer.CapturedImmediateOperand) || !Transform || + !Renderer.Flags.empty()) { + fail(Renderer.Range, + "selection captured immediate renderer requires a matched constant and known " + "transform"); + return false; + } + NormalizedAction.OperandRenderers.push_back({ + .SourceKind = NormalizedSelectionOperandRenderer::Kind::CapturedImmediate, + .Value = *Renderer.CapturedImmediateOperand, + .Flags = 0, + .Transform = *Transform, + }); + continue; + } + + if (Renderer.Immediate) { + if (!Renderer.Flags.empty() || Renderer.ImmediateTransform != "identity") { + fail(Renderer.Range, "selection immediate renderer cannot carry register flags"); + return false; + } + NormalizedAction.OperandRenderers.push_back({ + .SourceKind = NormalizedSelectionOperandRenderer::Kind::Immediate, + .Value = 0, + .Flags = 0, + .Immediate = *Renderer.Immediate, + }); + continue; + } + + fail(Renderer.Range, "selection operand renderer has no normalized source"); return false; } - Normalized.OperandRenderers = std::move(Renderers); - } else if (ResultInstruction != nullptr && MatchInstruction != nullptr && - ResultInstruction->Operands.size() != - MatchInstruction->Operands.size() + Rule.AppendedImmediates.size()) { - fail(Rule.Range, "selection rule result opcode has an incompatible operand count"); + Normalized.Actions.push_back(std::move(NormalizedAction)); + } + if (!HasRootAction) { + fail(Rule.Range, "selection instructions require exactly one root replacement"); return false; } @@ -349,6 +458,10 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { fail(Rule.Range, "selection erased definitions require distinct register operands"); return false; } + if (!ConstantOperands.contains(OperandIndex)) { + fail(Rule.Range, "selection erased definition requires a matched constant operand"); + return false; + } } Result.SelectionRules.push_back(std::move(Normalized)); } diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h index bee814f..42a28c1 100644 --- a/backend/utils/TableGen/Common/CodeGenTarget.h +++ b/backend/utils/TableGen/Common/CodeGenTarget.h @@ -195,19 +195,47 @@ struct NormalizedSelectionIntegerPredicate final { }; struct NormalizedSelectionOperandDefConstantPredicate final { + struct Range final { + std::int64_t Minimum = 0; + std::int64_t Maximum = 0; + }; + std::uint32_t OperandIndex = 0; - std::int64_t Value = 0; + std::vector Ranges; +}; + +struct NormalizedSelectionTemporary final { + std::uint32_t ID = 0; + std::uint32_t TypeFromOperand = 0; +}; + +enum class NormalizedSelectionImmediateTransform : std::uint8_t { + Identity, + Negate, + PlusOne, }; struct NormalizedSelectionOperandRenderer final { enum class Kind : std::uint8_t { Operand, PhysicalRegister, + Temporary, + CapturedImmediate, + Immediate, }; Kind SourceKind = Kind::Operand; std::uint32_t Value = 0; std::uint16_t Flags = 0; + NormalizedSelectionImmediateTransform Transform = + NormalizedSelectionImmediateTransform::Identity; + std::int64_t Immediate = 0; +}; + +struct NormalizedSelectionAction final { + std::uint32_t ResultOpcode = 0; + bool ReplacesRoot = false; + std::vector OperandRenderers; }; struct NormalizedSelectionRule final { @@ -221,9 +249,8 @@ struct NormalizedSelectionRule final { std::vector OperandBanks; std::vector OperandClasses; std::vector OperandDefConstants; - std::uint32_t ResultOpcode = 0; - std::optional> OperandRenderers; - std::vector AppendedImmediates; + std::vector Temporaries; + std::vector Actions; std::vector EraseOperandDefinitions; }; diff --git a/backend/utils/TableGen/GlobalISelEmitter.cpp b/backend/utils/TableGen/GlobalISelEmitter.cpp index 4bfeb22..784d418 100644 --- a/backend/utils/TableGen/GlobalISelEmitter.cpp +++ b/backend/utils/TableGen/GlobalISelEmitter.cpp @@ -39,19 +39,29 @@ void emitTypePredicate(std::ostream &Output, std::uint32_t OperandIndex, } [[nodiscard]] std::size_t instructionCount(const NormalizedSelectionRule &Rule) noexcept { - return 3U + (Rule.ResultType ? 1U : 0U) + (Rule.IntegerPredicate ? 1U : 0U) + + std::size_t Count = 2U + (Rule.ResultType ? 1U : 0U) + + (Rule.IntegerPredicate ? 1U : 0U) + Rule.OperandTypes.size() + Rule.OperandBanks.size() + Rule.OperandClasses.size() + - Rule.OperandDefConstants.size() + - (Rule.OperandRenderers ? Rule.OperandRenderers->size() : 0U) + - Rule.AppendedImmediates.size() + Rule.EraseOperandDefinitions.size(); + Rule.OperandDefConstants.size() + Rule.Temporaries.size() + + Rule.EraseOperandDefinitions.size(); + for (const NormalizedSelectionAction &Action : Rule.Actions) + Count += 1U + Action.OperandRenderers.size(); + return Count; } } // namespace std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view SourceName) { std::size_t InstructionCount = 0; + std::size_t ConstantRangeCount = 0; for (const NormalizedSelectionRule &Rule : Model.SelectionRules) InstructionCount += instructionCount(Rule); + for (const NormalizedSelectionRule &Rule : Model.SelectionRules) { + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + Rule.OperandDefConstants) { + ConstantRangeCount += Predicate.Ranges.size(); + } + } std::ostringstream Output; Output << "// SPDX-License-Identifier: GPL-3.0-or-later\n\n"; @@ -59,8 +69,20 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view appendQuoted(Output, SourceName); Output << ". Do not edit it manually.\n\n"; Output << "#ifdef GET_GLOBALISEL_MATCH_TABLE\n\n"; + Output << "constexpr std::array GeneratedGlobalISelConstantRanges = {{\n"; + for (const NormalizedSelectionRule &Rule : Model.SelectionRules) { + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + Rule.OperandDefConstants) { + for (const NormalizedSelectionOperandDefConstantPredicate::Range &Range : Predicate.Ranges) + Output << " {" << Range.Minimum << ", " << Range.Maximum << "},\n"; + } + } + Output << "}};\n\n"; + Output << "constexpr std::array GeneratedGlobalISelInstructions = {{\n"; + std::size_t FirstConstantRange = 0; for (const NormalizedSelectionRule &Rule : Model.SelectionRules) { emitInstruction(Output, "CheckOpcode", 0, Rule.MatchOpcode); if (Rule.ResultType) @@ -74,21 +96,41 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view emitInstruction(Output, "CheckOperandBank", Predicate.OperandIndex, Predicate.Bank); for (const NormalizedSelectionOperandClassPredicate &Predicate : Rule.OperandClasses) emitInstruction(Output, "CheckOperandClass", Predicate.OperandIndex, Predicate.RegClass); - for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants) - emitInstruction(Output, "CheckOperandDefConstant", Predicate.OperandIndex, 0, "0", - Predicate.Value); - emitInstruction(Output, "MutateOpcode", 0, Rule.ResultOpcode); - if (Rule.OperandRenderers) { - for (const NormalizedSelectionOperandRenderer &Renderer : *Rule.OperandRenderers) { - if (Renderer.SourceKind == NormalizedSelectionOperandRenderer::Kind::Operand) + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + Rule.OperandDefConstants) { + emitInstruction(Output, "CheckOperandDefConstantRanges", Predicate.OperandIndex, + static_cast(FirstConstantRange), + std::to_string(Predicate.Ranges.size())); + FirstConstantRange += Predicate.Ranges.size(); + } + for (const NormalizedSelectionTemporary &Temporary : Rule.Temporaries) + emitInstruction(Output, "CreateTemporary", Temporary.TypeFromOperand, Temporary.ID); + for (const NormalizedSelectionAction &Action : Rule.Actions) { + emitInstruction(Output, Action.ReplacesRoot ? "MutateOpcode" : "BuildInstruction", 0, + Action.ResultOpcode); + for (const NormalizedSelectionOperandRenderer &Renderer : Action.OperandRenderers) { + switch (Renderer.SourceKind) { + case NormalizedSelectionOperandRenderer::Kind::Operand: emitInstruction(Output, "RenderOperand", Renderer.Value); - else + break; + case NormalizedSelectionOperandRenderer::Kind::PhysicalRegister: emitInstruction(Output, "RenderPhysicalRegister", 0, Renderer.Value, std::to_string(Renderer.Flags)); + break; + case NormalizedSelectionOperandRenderer::Kind::Temporary: + emitInstruction(Output, "RenderTemporary", 0, Renderer.Value, + std::to_string(Renderer.Flags)); + break; + case NormalizedSelectionOperandRenderer::Kind::CapturedImmediate: + emitInstruction(Output, "RenderCapturedImmediate", Renderer.Value, + static_cast(Renderer.Transform)); + break; + case NormalizedSelectionOperandRenderer::Kind::Immediate: + emitInstruction(Output, "RenderImmediate", 0, 0, "0", Renderer.Immediate); + break; + } } } - for (const std::int64_t Immediate : Rule.AppendedImmediates) - emitInstruction(Output, "AppendImmediate", 0, 0, "0", Immediate); for (const std::uint32_t OperandIndex : Rule.EraseOperandDefinitions) emitInstruction(Output, "EraseOperandDefinition", OperandIndex); emitInstruction(Output, "Complete", 0); @@ -107,7 +149,8 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view } Output << "}};\n\n"; Output << "[[nodiscard]] constexpr GIMatchTable generatedGlobalISelMatchTable() noexcept {\n" - " return {GeneratedGlobalISelInstructions, GeneratedGlobalISelRules};\n" + " return {GeneratedGlobalISelInstructions, GeneratedGlobalISelRules,\n" + " GeneratedGlobalISelConstantRanges};\n" "}\n\n"; Output << "#endif // GET_GLOBALISEL_MATCH_TABLE\n"; return Output.str(); -- cgit v1.2.3