From ca25d25d4c5131491a50b1a94e63e9b2d3c34ed4 Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Sun, 16 Aug 2026 16:13:12 +0800 Subject: [RISCV][GlobalISel] Select comparisons against zero --- .../rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h | 5 + backend/include/rcc/TableGen/Record.h | 23 ++ .../CodeGen/GlobalISel/GIMatchTableExecutor.cpp | 292 +++++++++++++++++++-- backend/lib/TableGen/Parser.cpp | 142 +++++++++- backend/lib/Target/RISCV/RISCVGISel.rccdesc | 21 ++ backend/utils/TableGen/Common/CodeGenSelection.cpp | 186 ++++++++++++- backend/utils/TableGen/Common/CodeGenTarget.h | 25 ++ backend/utils/TableGen/GlobalISelEmitter.cpp | 24 +- 8 files changed, 695 insertions(+), 23 deletions(-) (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h index 807cb4a..7cceca3 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h +++ b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h @@ -27,8 +27,13 @@ enum class GIMatchTableOpcode : std::uint8_t { CheckOperandType, CheckOperandBank, CheckOperandClass, + CheckIntegerPredicate, + CheckOperandDefConstant, MutateOpcode, + RenderOperand, + RenderPhysicalRegister, AppendImmediate, + EraseOperandDefinition, Complete, }; diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h index 94308c7..4378af8 100644 --- a/backend/include/rcc/TableGen/Record.h +++ b/backend/include/rcc/TableGen/Record.h @@ -229,16 +229,39 @@ struct SourceSelectionOperandClassPredicate final { TextRange Range; }; +struct SourceSelectionIntegerPredicate final { + std::uint32_t OperandIndex = 0; + std::string Predicate; + TextRange Range; +}; + +struct SourceSelectionOperandDefConstantPredicate final { + std::uint32_t OperandIndex = 0; + std::int64_t Value = 0; + TextRange Range; +}; + +struct SourceSelectionOperandRenderer final { + std::optional OperandIndex; + std::string PhysicalRegisterSymbol; + std::vector Flags; + TextRange Range; +}; + struct SourceSelectionRule final { std::string Symbol; std::uint32_t Priority = 0; std::string MatchOpcodeSymbol; std::optional ResultType; + std::optional IntegerPredicate; std::vector OperandTypes; std::vector OperandBanks; std::vector OperandClasses; + std::vector OperandDefConstants; std::string ResultOpcodeSymbol; + std::optional> OperandRenderers; std::vector AppendedImmediates; + std::vector EraseOperandDefinitions; TextRange Range; }; diff --git a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp index a195d11..38fb66d 100644 --- a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp +++ b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp @@ -2,6 +2,8 @@ #include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" +#include "rcc/CodeGen/GenericOpcodes.h" +#include "rcc/CodeGen/GlobalISel/Utils.h" #include "rcc/CodeGen/LowLevelType.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineInstr.h" @@ -9,8 +11,11 @@ #include "rcc/CodeGen/MachineRegisterInfo.h" #include "rcc/CodeGen/TargetDescription.h" +#include #include +#include #include +#include #include namespace rcc { @@ -83,9 +88,76 @@ namespace { return RegisterInfo.RegClass->value() == Step.Value; } +[[nodiscard]] Expected matchesIntegerPredicate(const MachineInstr &Instruction, + const GIMatchTableInstruction &Step) { + if (Step.Value >= static_cast(IntegerPredicate::Count)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid integer predicate"); + } + const MachineOperand *Operand = Instruction.operandAt(Step.OperandIndex); + const auto *Predicate = Operand == nullptr ? nullptr : Operand->getIf(); + const IntegerPredicate *Integer = Predicate == nullptr ? nullptr : Predicate->integerPredicate(); + 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); + const Register *Reg = Operand == nullptr ? nullptr : Operand->getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return false; + const MachineInstr *Definition = Function.registerInfo().getVRegDef(*Reg); + if (Definition == nullptr || Definition->opcode() != opcode(GenericOpcode::G_CONSTANT)) + return false; + const MachineOperand *Value = Definition->operandAt(1); + if (Value == nullptr) + return false; + if (const std::int64_t *Immediate = Value->getIf()) + return *Immediate == Step.Immediate; + const auto *Integer = Value->getIf(); + if (Integer == nullptr) + return false; + if (Step.Immediate == 0) + return Integer->Value.isZero(); + 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; +} + +[[nodiscard]] Expected registerFlagsFromRaw(std::uint32_t Raw) { + constexpr std::uint32_t ValidBits = + (std::uint32_t{1} << static_cast(RegisterOperandFlag::Count)) - 1U; + if ((Raw & ~ValidBits) != 0) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has invalid register flags"); + } + RegisterOperandFlags Flags; + for (std::uint16_t Index = 0; Index < static_cast(RegisterOperandFlag::Count); + ++Index) { + if ((Raw & (std::uint32_t{1} << Index)) != 0) + Flags.set(static_cast(Index)); + } + return Flags; +} + struct MatchedRule final { + struct RenderedOperand final { + enum class Kind : std::uint8_t { + RootOperand, + PhysicalRegister, + }; + + Kind SourceKind = Kind::RootOperand; + std::uint32_t Value = 0; + std::uint32_t Flags = 0; + }; + Opcode ResultOpcode; + std::optional> OperandLayout; std::vector AppendedImmediates; + std::vector EraseOperandDefinitions; }; [[nodiscard]] Expected> matchRule(const GIMatchTable &Table, @@ -146,6 +218,28 @@ struct MatchedRule final { return std::optional{}; break; } + case GIMatchTableOpcode::CheckIntegerPredicate: { + if (Applying) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after rendering"); + auto Matched = matchesIntegerPredicate(Instruction, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional{}; + break; + } + case GIMatchTableOpcode::CheckOperandDefConstant: { + if (Applying) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table performs a predicate after rendering"); + auto Matched = matchesOperandDefConstant(Instruction, Function, Step); + if (!Matched) + return std::unexpected(Matched.error()); + if (!*Matched) + return std::optional{}; + break; + } case GIMatchTableOpcode::MutateOpcode: if (Complete || HasResultOpcode || Step.Value == 0) return makeUnexpected(ErrorCode::VerificationError, @@ -154,13 +248,53 @@ struct MatchedRule final { Result.ResultOpcode = Opcode::fromValue(Step.Value); HasResultOpcode = true; break; + case GIMatchTableOpcode::RenderOperand: + if (Complete || !HasResultOpcode) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid operand renderer"); + Applying = true; + if (!Result.OperandLayout) + Result.OperandLayout.emplace(); + Result.OperandLayout->push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::RootOperand, + .Value = Step.OperandIndex, + .Flags = 0, + }); + break; + case GIMatchTableOpcode::RenderPhysicalRegister: + if (Complete || !HasResultOpcode || 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({ + .SourceKind = MatchedRule::RenderedOperand::Kind::PhysicalRegister, + .Value = Step.Value, + .Flags = Step.Auxiliary, + }); + break; case GIMatchTableOpcode::AppendImmediate: - if (Complete) + if (Complete || Result.OperandLayout) return makeUnexpected(ErrorCode::VerificationError, "generated match table renders after completion"); Applying = true; Result.AppendedImmediates.push_back(Step.Immediate); break; + case GIMatchTableOpcode::EraseOperandDefinition: { + if (Complete || !HasResultOpcode) + 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) return makeUnexpected(ErrorCode::VerificationError, @@ -176,36 +310,158 @@ struct MatchedRule final { return std::optional(std::move(Result)); } +[[nodiscard]] std::size_t explicitOperandCount(const MachineInstr &Instruction) noexcept { + std::size_t Count = 0; + while (Count < Instruction.operandCount() && !Instruction.operandAt(Count)->isImplicit()) + ++Count; + return Count; +} + +[[nodiscard]] Expected +restoreInstruction(MachineInstr &Instruction, Opcode OriginalOpcode, + const std::vector &OriginalOperands, + const std::vector> &Ties) { + while (Instruction.operandCount() != 0) { + auto Erased = Instruction.eraseOperand(Instruction.operandCount() - 1U); + if (!Erased) + return std::unexpected(Erased.error()); + } + auto RestoredOpcode = Instruction.setOpcode(OriginalOpcode); + if (!RestoredOpcode) + return std::unexpected(RestoredOpcode.error()); + for (const MachineOperand &Operand : OriginalOperands) { + auto Added = Instruction.addOperand(Operand.cloneDetached()); + if (!Added) + return std::unexpected(Added.error()); + } + for (const auto [DefIndex, UseIndex] : Ties) { + auto Tied = Instruction.tieOperands(DefIndex, UseIndex); + if (!Tied) + return std::unexpected(Tied.error()); + } + return {}; +} + [[nodiscard]] Expected applyRule(const MatchedRule &Rule, MachineInstr &Instruction, - const TargetDescription &Target) { + MachineFunction &Function, const TargetDescription &Target) { const InstructionDescriptor *Descriptor = Target.instructionDescriptor(Rule.ResultOpcode); if (Descriptor == nullptr) return makeUnexpected(ErrorCode::VerificationError, "generated match table selects an unknown instruction opcode"); - if (!Descriptor->Variadic && - Descriptor->Operands.size() != Instruction.operandCount() + Rule.AppendedImmediates.size()) { + + 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()) + OriginalOperands.push_back(Operand.cloneDetached()); + + std::vector> Ties; + for (std::size_t Index = 0; Index < OriginalOperandCount; ++Index) { + const std::optional Other = Instruction.operandAt(Index)->tiedOperandIndex(); + if (Other && Index < *Other) + Ties.emplace_back(Index, *Other); + } + + std::vector NewOperands; + 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"); + } + if (SourceToOutput[Rendered.Value] && + Instruction.operandAt(Rendered.Value)->tiedOperandIndex()) { + 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)); + } + } + 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(); + } + for (std::size_t Index = OriginalExplicitCount; Index < OriginalOperandCount; ++Index) { + SourceToOutput[Index] = NewOperands.size(); + NewOperands.push_back(Instruction.operandAt(Index)->cloneDetached()); + } + + if (!Descriptor->Variadic && Descriptor->Operands.size() != NewExplicitCount) { return makeUnexpected(ErrorCode::VerificationError, "generated match table result has an incompatible operand count"); } - const Opcode OriginalOpcode = Instruction.opcode(); auto SetOpcode = Instruction.setOpcode(Rule.ResultOpcode); if (!SetOpcode) return std::unexpected(SetOpcode.error()); - const std::size_t OriginalOperandCount = Instruction.operandCount(); - for (const std::int64_t Immediate : Rule.AppendedImmediates) { - auto Added = Instruction.addOperand(MachineOperand::immediate(Immediate)); - if (Added) + 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()); + } + } + for (MachineOperand &Operand : NewOperands) { + 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()); + } + } + + for (const auto [OldDef, OldUse] : Ties) { + const std::optional &NewDef = SourceToOutput[OldDef]; + const std::optional &NewUse = SourceToOutput[OldUse]; + if (!NewDef || !NewUse) continue; - while (Instruction.operandCount() > OriginalOperandCount) { - auto Removed = Instruction.eraseOperand(Instruction.operandCount() - 1U); - if (!Removed) - return std::unexpected(Removed.error()); + 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 Restored = Instruction.setOpcode(OriginalOpcode); - if (!Restored) - return std::unexpected(Restored.error()); - return std::unexpected(Added.error()); + } + + for (const Register Reg : Rule.EraseOperandDefinitions) { + MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); + if (Definition == nullptr || Definition == &Instruction || + !isTriviallyDead(*Definition, Function.registerInfo(), Target)) + continue; + auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); } return {}; } @@ -240,7 +496,7 @@ Expected GIMatchTableExecutor::select(const GIMatchTable &Table, MachineIn return std::unexpected(Match.error()); if (!*Match) continue; - auto Applied = applyRule(**Match, Instruction, Target); + auto Applied = applyRule(**Match, Instruction, Function, Target); if (!Applied) return std::unexpected(Applied.error()); return true; diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp index 65687da..9807534 100644 --- a/backend/lib/TableGen/Parser.cpp +++ b/backend/lib/TableGen/Parser.cpp @@ -270,6 +270,23 @@ private: return Result; } + [[nodiscard]] std::optional> + unsignedInteger32Sequence(const yaml::Node &Node, std::string_view Context) { + if (!requireSequence(&Node, Context)) + return std::nullopt; + std::vector Result; + for (const yaml::NodeID Value : Node.sequence()) { + const yaml::Node *Element = Input.node(Value); + if (Element == nullptr) + return std::nullopt; + const auto Parsed = unsignedInteger32(*Element, Context); + if (!Parsed) + return std::nullopt; + Result.push_back(*Parsed); + } + return Result; + } + [[nodiscard]] bool parseTarget(const yaml::Node &Node, SourceTarget &Result) { if (!requireMapping(&Node, "target")) return false; @@ -1135,10 +1152,110 @@ private: return true; } + [[nodiscard]] bool parseSelectionIntegerPredicate(const yaml::Node &Node, + SourceSelectionRule &Result) { + if (!requireMapping(&Node, "selection integer predicate") || + !checkKeys(Node, {"index", "value"}, "selection integer predicate")) { + return false; + } + const yaml::Node *IndexNode = requiredNode(Node, "index", "selection integer predicate"); + const auto Value = requiredScalar(Node, "value", "selection integer predicate"); + if (IndexNode == nullptr || !Value) + return false; + const auto Index = unsignedInteger32(*IndexNode, "selection integer predicate index"); + if (!Index) + return false; + Result.IntegerPredicate = SourceSelectionIntegerPredicate{ + .OperandIndex = *Index, + .Predicate = *Value, + .Range = Node.range(), + }; + return true; + } + + [[nodiscard]] bool parseSelectionOperandDefConstants( + const yaml::Node &Node, std::vector &Result) { + if (!requireSequence(&Node, "selection operand definition constants")) + return false; + 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")) { + 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) + 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) + return false; + Result.push_back({ + .OperandIndex = *Index, + .Value = *Value, + .Range = Element->range(), + }); + } + return true; + } + + [[nodiscard]] bool + parseSelectionOperandRenderers(const yaml::Node &Node, + std::vector &Result) { + if (!requireSequence(&Node, "selection operand renderers")) + return false; + 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"}, + "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'"); + return false; + } + SourceSelectionOperandRenderer Renderer{ + .OperandIndex = std::nullopt, + .PhysicalRegisterSymbol = {}, + .Flags = {}, + .Range = Element->range(), + }; + if (OperandNode != nullptr) { + const auto Index = unsignedInteger32(*OperandNode, "selection operand renderer operand"); + if (!Index) + return false; + Renderer.OperandIndex = Index; + } else { + const auto Symbol = + scalar(*PhysicalRegisterNode, "selection operand renderer physical register"); + if (!Symbol) + return false; + Renderer.PhysicalRegisterSymbol = *Symbol; + } + if (const yaml::Node *FlagsNode = optionalNode(*Element, "flags")) { + const auto Flags = scalarSequence(*FlagsNode, "selection operand renderer flags"); + if (!Flags) + return false; + Renderer.Flags = *Flags; + } + Result.push_back(std::move(Renderer)); + } + return true; + } + [[nodiscard]] bool parseSelectionRuleMatch(const yaml::Node &Node, SourceSelectionRule &Result) { if (!requireMapping(&Node, "selection rule match") || !checkKeys(Node, - {"opcode", "result_type", "operand_types", "operand_banks", "operand_classes"}, + {"opcode", "result_type", "integer_predicate", "operand_types", "operand_banks", + "operand_classes", "operand_def_constants"}, "selection rule match")) { return false; } @@ -1152,6 +1269,10 @@ private: return false; Result.ResultType = std::move(*Parsed); } + if (const yaml::Node *Predicate = optionalNode(Node, "integer_predicate")) { + if (!parseSelectionIntegerPredicate(*Predicate, Result)) + return false; + } if (const yaml::Node *OperandTypes = optionalNode(Node, "operand_types")) { if (!parseSelectionOperandTypes(*OperandTypes, Result.OperandTypes)) return false; @@ -1164,12 +1285,17 @@ private: if (!parseSelectionOperandClasses(*OperandClasses, Result.OperandClasses)) return false; } + if (const yaml::Node *OperandDefConstants = optionalNode(Node, "operand_def_constants")) { + if (!parseSelectionOperandDefConstants(*OperandDefConstants, Result.OperandDefConstants)) + return false; + } return true; } [[nodiscard]] bool parseSelectionRuleApply(const yaml::Node &Node, SourceSelectionRule &Result) { if (!requireMapping(&Node, "selection rule apply") || - !checkKeys(Node, {"opcode", "append_immediates"}, "selection rule apply")) { + !checkKeys(Node, {"opcode", "append_immediates", "operands", "erase_operand_definitions"}, + "selection rule apply")) { return false; } const auto Opcode = requiredScalar(Node, "opcode", "selection rule apply"); @@ -1182,6 +1308,18 @@ private: 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 (const yaml::Node *Erase = optionalNode(Node, "erase_operand_definitions")) { + auto Indices = unsignedInteger32Sequence(*Erase, "selection operand definitions"); + if (!Indices) + return false; + Result.EraseOperandDefinitions = std::move(*Indices); + } return true; } diff --git a/backend/lib/Target/RISCV/RISCVGISel.rccdesc b/backend/lib/Target/RISCV/RISCVGISel.rccdesc index 97ed3d6..bd946be 100644 --- a/backend/lib/Target/RISCV/RISCVGISel.rccdesc +++ b/backend/lib/Target/RISCV/RISCVGISel.rccdesc @@ -155,3 +155,24 @@ selection_rules: - { index: 0, bank: GPR } - { index: 1, bank: FPR } apply: { opcode: FCLASS_D } + - + id: select_g_icmp_ne_zero + priority: 200 + match: + opcode: G_ICMP + result_type: { kind: scalar, bits: 64 } + integer_predicate: { index: 1, value: ne } + operand_types: + - { index: 2, kind: scalar, bits: 64 } + operand_banks: + - { index: 0, bank: GPR } + - { index: 2, bank: GPR } + operand_def_constants: + - { index: 3, value: 0 } + apply: + opcode: SLTU + operands: + - { operand: 0 } + - { physical_register: X0, flags: [use] } + - { operand: 2 } + erase_operand_definitions: [3] diff --git a/backend/utils/TableGen/Common/CodeGenSelection.cpp b/backend/utils/TableGen/Common/CodeGenSelection.cpp index 0216136..cc80e41 100644 --- a/backend/utils/TableGen/Common/CodeGenSelection.cpp +++ b/backend/utils/TableGen/Common/CodeGenSelection.cpp @@ -3,11 +3,14 @@ #include "CodeGenTarget.h" #include "rcc/CodeGen/GenericOpcodes.h" #include "rcc/CodeGen/LowLevelType.h" +#include "rcc/CodeGen/MachineOperand.h" #include +#include #include #include #include +#include #include #include #include @@ -46,6 +49,86 @@ findInstructionBySymbol(const NormalizedTargetModel &Model, std::string_view Sym std::ranges::contains(Instruction.Operands[Index].Kinds, "Register"); } +[[nodiscard]] std::optional integerPredicateValue(std::string_view Symbol) noexcept { + static constexpr std::array, 2> Predicates = {{ + {"eq", IntegerPredicate::Equal}, + {"ne", IntegerPredicate::NotEqual}, + }}; + if (Symbol == "sgt") + return static_cast(IntegerPredicate::SignedGreaterThan); + if (Symbol == "sge") + return static_cast(IntegerPredicate::SignedGreaterEqual); + if (Symbol == "sle") + return static_cast(IntegerPredicate::SignedLessEqual); + if (Symbol == "slt") + return static_cast(IntegerPredicate::SignedLessThan); + if (Symbol == "ugt") + return static_cast(IntegerPredicate::UnsignedGreaterThan); + if (Symbol == "uge") + return static_cast(IntegerPredicate::UnsignedGreaterEqual); + if (Symbol == "ult") + return static_cast(IntegerPredicate::UnsignedLessThan); + if (Symbol == "ule") + return static_cast(IntegerPredicate::UnsignedLessEqual); + const auto *const Position = + std::ranges::find(Predicates, Symbol, &decltype(Predicates)::value_type::first); + if (Position == Predicates.end()) + return std::nullopt; + return static_cast(Position->second); +} + +[[nodiscard]] const NormalizedRegister *findRegisterBySymbol(const NormalizedTargetModel &Model, + std::string_view Symbol) { + const auto Position = std::ranges::find(Model.Registers, Symbol, &NormalizedRegister::Symbol); + return Position == Model.Registers.end() ? nullptr : &*Position; +} + +[[nodiscard]] std::optional +registerOperandFlags(std::span Names) noexcept { + RegisterOperandFlags Flags; + for (const std::string &Name : Names) { + const auto Set = [&Flags](RegisterOperandFlag Flag) { + Flags.set(Flag); + return true; + }; + if (Name == "define") + Set(RegisterOperandFlag::Define); + else if (Name == "use") + Set(RegisterOperandFlag::Use); + else if (Name == "implicit") + Set(RegisterOperandFlag::Implicit); + else if (Name == "kill") + Set(RegisterOperandFlag::Kill); + else if (Name == "dead") + Set(RegisterOperandFlag::Dead); + else if (Name == "undef") + Set(RegisterOperandFlag::Undef); + else if (Name == "early_clobber") + Set(RegisterOperandFlag::EarlyClobber); + else if (Name == "internal_read") + Set(RegisterOperandFlag::InternalRead); + else if (Name == "renamable") + Set(RegisterOperandFlag::Renamable); + else if (Name == "debug") + Set(RegisterOperandFlag::Debug); + else + return std::nullopt; + } + return Flags; +} + +[[nodiscard]] bool validRegisterOperandFlags(RegisterOperandFlags Flags) noexcept { + const bool IsDef = Flags.has(RegisterOperandFlag::Define); + const bool IsUse = Flags.has(RegisterOperandFlag::Use); + return (IsDef || IsUse) && (!Flags.has(RegisterOperandFlag::Kill) || IsUse) && + (!Flags.has(RegisterOperandFlag::Dead) || IsDef) && + (!Flags.has(RegisterOperandFlag::Undef) || IsUse) && + (!Flags.has(RegisterOperandFlag::EarlyClobber) || IsDef) && + (!Flags.has(RegisterOperandFlag::InternalRead) || (IsDef && IsUse)) && + (!(IsDef && IsUse) || Flags.has(RegisterOperandFlag::InternalRead)) && + (!Flags.has(RegisterOperandFlag::Debug) || (IsUse && !IsDef)); +} + } // namespace bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { @@ -73,7 +156,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { fail(Rule.Range, "selection rule result opcode must not be generic"); return false; } - if (MatchInstruction != nullptr && ResultInstruction != nullptr && + 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"); @@ -106,6 +189,7 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { Normalized.MatchOpcode = *MatchOpcode; Normalized.ResultOpcode = *ResultOpcode; Normalized.AppendedImmediates = Rule.AppendedImmediates; + Normalized.EraseOperandDefinitions = Rule.EraseOperandDefinitions; if (Rule.ResultType) { auto Type = NormalizeType(*Rule.ResultType); if (!Type) @@ -119,6 +203,29 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { ++Normalized.Specificity; } + if (Rule.IntegerPredicate) { + const auto Predicate = integerPredicateValue(Rule.IntegerPredicate->Predicate); + if (!Predicate) { + fail(Rule.IntegerPredicate->Range, + "selection integer predicate is not a recognized integer predicate"); + return false; + } + if (MatchInstruction != nullptr && + (Rule.IntegerPredicate->OperandIndex >= MatchInstruction->Operands.size() || + !std::ranges::contains( + MatchInstruction->Operands[Rule.IntegerPredicate->OperandIndex].Kinds, + "Predicate"))) { + fail(Rule.IntegerPredicate->Range, + "selection integer predicate requires a predicate operand"); + return false; + } + Normalized.IntegerPredicate = { + .OperandIndex = Rule.IntegerPredicate->OperandIndex, + .Predicate = *Predicate, + }; + ++Normalized.Specificity; + } + std::unordered_set TypeOperands; for (const SourceSelectionOperandTypePredicate &Predicate : Rule.OperandTypes) { auto Type = NormalizeType(Predicate.Type); @@ -166,6 +273,83 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { {.OperandIndex = Predicate.OperandIndex, .RegClass = RegClass->second}); ++Normalized.Specificity; } + + std::unordered_set ConstantOperands; + for (const SourceSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants) { + if (!ConstantOperands.insert(Predicate.OperandIndex).second || + (MatchInstruction != nullptr && + !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex))) { + fail(Predicate.Range, + "selection operand definition constant predicates require distinct register " + "operands"); + return false; + } + Normalized.OperandDefConstants.push_back( + {.OperandIndex = Predicate.OperandIndex, .Value = Predicate.Value}); + ++Normalized.Specificity; + } + + if (Rule.OperandRenderers) { + if (!Rule.AppendedImmediates.empty()) { + fail(Rule.Range, "selection rule cannot combine operand renderers and appended immediates"); + return false; + } + std::vector Renderers; + Renderers.reserve(Rule.OperandRenderers->size()); + for (const SourceSelectionOperandRenderer &Renderer : *Rule.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({ + .SourceKind = NormalizedSelectionOperandRenderer::Kind::Operand, + .Value = *Renderer.OperandIndex, + .Flags = 0, + }); + 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 (!validRegisterOperandFlags(*Flags)) { + fail(Renderer.Range, "selection physical register renderer is invalid"); + return false; + } + 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"); + 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"); + return false; + } + + std::unordered_set ErasedOperands; + for (const std::uint32_t OperandIndex : Rule.EraseOperandDefinitions) { + if (!ErasedOperands.insert(OperandIndex).second || + (MatchInstruction != nullptr && !isRegisterOperand(*MatchInstruction, OperandIndex))) { + fail(Rule.Range, "selection erased definitions require distinct register operands"); + 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 929d3e7..bee814f 100644 --- a/backend/utils/TableGen/Common/CodeGenTarget.h +++ b/backend/utils/TableGen/Common/CodeGenTarget.h @@ -189,17 +189,42 @@ struct NormalizedSelectionOperandClassPredicate final { std::uint32_t RegClass = 0; }; +struct NormalizedSelectionIntegerPredicate final { + std::uint32_t OperandIndex = 0; + std::uint32_t Predicate = 0; +}; + +struct NormalizedSelectionOperandDefConstantPredicate final { + std::uint32_t OperandIndex = 0; + std::int64_t Value = 0; +}; + +struct NormalizedSelectionOperandRenderer final { + enum class Kind : std::uint8_t { + Operand, + PhysicalRegister, + }; + + Kind SourceKind = Kind::Operand; + std::uint32_t Value = 0; + std::uint16_t Flags = 0; +}; + struct NormalizedSelectionRule final { std::string Symbol; std::uint32_t Priority = 0; std::uint32_t Specificity = 0; std::uint32_t MatchOpcode = 0; std::optional ResultType; + std::optional IntegerPredicate; std::vector OperandTypes; std::vector OperandBanks; std::vector OperandClasses; + std::vector OperandDefConstants; std::uint32_t ResultOpcode = 0; + std::optional> OperandRenderers; std::vector AppendedImmediates; + std::vector EraseOperandDefinitions; }; struct NormalizedTargetModel final { diff --git a/backend/utils/TableGen/GlobalISelEmitter.cpp b/backend/utils/TableGen/GlobalISelEmitter.cpp index 1634eb3..4bfeb22 100644 --- a/backend/utils/TableGen/GlobalISelEmitter.cpp +++ b/backend/utils/TableGen/GlobalISelEmitter.cpp @@ -39,8 +39,11 @@ 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.OperandTypes.size() + Rule.OperandBanks.size() + - Rule.OperandClasses.size() + Rule.AppendedImmediates.size(); + return 3U + (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(); } } // namespace @@ -62,15 +65,32 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view emitInstruction(Output, "CheckOpcode", 0, Rule.MatchOpcode); if (Rule.ResultType) emitTypePredicate(Output, 0, *Rule.ResultType); + if (Rule.IntegerPredicate) + emitInstruction(Output, "CheckIntegerPredicate", Rule.IntegerPredicate->OperandIndex, + Rule.IntegerPredicate->Predicate); for (const NormalizedSelectionOperandTypePredicate &Predicate : Rule.OperandTypes) emitTypePredicate(Output, Predicate.OperandIndex, Predicate.Type); for (const NormalizedSelectionOperandBankPredicate &Predicate : Rule.OperandBanks) 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) + emitInstruction(Output, "RenderOperand", Renderer.Value); + else + emitInstruction(Output, "RenderPhysicalRegister", 0, Renderer.Value, + std::to_string(Renderer.Flags)); + } + } 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); } Output << "}};\n\n"; -- cgit v1.2.3