From df7095e67ea06f7d6a81d99e70c804ce54ef950d Mon Sep 17 00:00:00 2001 From: Richard-Qin-X Date: Wed, 19 Aug 2026 05:13:13 +0800 Subject: [GlobalISel] Generate prelegalizer combiner rules --- backend/include/rcc/CodeGen/GlobalISel/Combiner.h | 50 ++++ .../rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h | 15 ++ backend/include/rcc/TableGen/Record.h | 44 +++ backend/lib/CodeGen/GlobalISel/CMakeLists.txt | 4 + backend/lib/CodeGen/GlobalISel/Combiner.cpp | 103 +++++++ .../CodeGen/GlobalISel/GIMatchTableExecutor.cpp | 225 +++++++++++++++- backend/lib/TableGen/Parser.cpp | 183 ++++++++++++- backend/lib/Target/RISCV/CMakeLists.txt | 13 + .../lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp | 56 ++++ backend/lib/Target/RISCV/RISCV.h | 3 + .../lib/Target/RISCV/RISCVGISelCombiner.rccdesc | 173 ++++++++++++ backend/lib/Target/RISCV/RISCVPipeline.cpp | 10 +- backend/utils/TableGen/CMakeLists.txt | 1 + backend/utils/TableGen/Common/CodeGenSelection.cpp | 298 +++++++++++++++++++++ backend/utils/TableGen/Common/CodeGenTarget.cpp | 3 +- backend/utils/TableGen/Common/CodeGenTarget.h | 42 +++ .../utils/TableGen/GlobalISelCombinerEmitter.cpp | 154 +++++++++++ backend/utils/TableGen/TableGenBackends.h | 3 + backend/utils/TableGen/rcc-tblgen.cpp | 17 +- 19 files changed, 1381 insertions(+), 16 deletions(-) create mode 100644 backend/include/rcc/CodeGen/GlobalISel/Combiner.h create mode 100644 backend/lib/CodeGen/GlobalISel/Combiner.cpp create mode 100644 backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp create mode 100644 backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc create mode 100644 backend/utils/TableGen/GlobalISelCombinerEmitter.cpp (limited to 'backend') diff --git a/backend/include/rcc/CodeGen/GlobalISel/Combiner.h b/backend/include/rcc/CodeGen/GlobalISel/Combiner.h new file mode 100644 index 0000000..efb6bbf --- /dev/null +++ b/backend/include/rcc/CodeGen/GlobalISel/Combiner.h @@ -0,0 +1,50 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef RCC_CODEGEN_GLOBALISEL_COMBINER_H +#define RCC_CODEGEN_GLOBALISEL_COMBINER_H + +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" +#include "rcc/CodeGen/MachinePassManager.h" + +#include +#include +#include + +namespace rcc { + +class GlobalISelCombinerPass final : public MachineFunctionPass { +public: + GlobalISelCombinerPass(const GIMatchTable &Table, const GIMatchTableExecutor &Executor, + std::string PassName, std::size_t MaximumRewrites = 4096, + std::size_t MaximumIterations = 8) noexcept + : Table(&Table), Executor(&Executor), PassName(std::move(PassName)), + MaximumRewrites(MaximumRewrites), MaximumIterations(MaximumIterations) { + Contract.Name = this->PassName; + Contract.Requires = {MachineFunctionProperty::IsSSA}; + Contract.VerificationStage = PipelineStage::MachineIRInput; + Contract.ThreadSafety = PassThreadSafety::ThreadSafe; + Contract.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers}; + } + + [[nodiscard]] const MachinePassContract &contract() const noexcept override; + [[nodiscard]] Expected run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) override; + +private: + [[nodiscard]] Expected runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineActionReplay &Actions) const; + + const GIMatchTable *Table; + const GIMatchTableExecutor *Executor; + std::string PassName; + std::size_t MaximumRewrites; + std::size_t MaximumIterations; + MachinePassContract Contract; +}; + +} // namespace rcc + +#endif // RCC_CODEGEN_GLOBALISEL_COMBINER_H diff --git a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h index 31966fe..d8bdc1a 100644 --- a/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h +++ b/backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h @@ -34,6 +34,8 @@ enum class GIMatchImmediateTransform : std::uint8_t { enum class GIMatchTableOpcode : std::uint8_t { CheckOpcode, CheckOperandType, + CheckInstructionFlag, + ClearInstructionFlags, CheckOperandBank, CheckOperandClass, CheckIntegerPredicate, @@ -52,10 +54,12 @@ enum class GIMatchTableOpcode : std::uint8_t { RenderOperand, RenderComplexOperand, RenderCapturedOperand, + RenderCapturedTypeBits, RenderPhysicalRegister, RenderTemporary, RenderCapturedImmediate, RenderImmediate, + ReplaceRootWithCapturedOperand, EraseOperandDefinition, Complete, }; @@ -92,10 +96,16 @@ struct GIMatchTableRule final { std::uint32_t InstructionCount = 0; }; +enum class GIMatchTableKind : std::uint8_t { + Selection, + Combiner, +}; + struct GIMatchTable final { std::span Instructions; std::span Rules; std::span ConstantRanges; + GIMatchTableKind Kind = GIMatchTableKind::Selection; }; class GIMatchTableExecutor { @@ -112,6 +122,11 @@ public: MachineFunction &Function, const TargetDescription &Target) const; + // Match and apply one generated GlobalISel combiner rule. + [[nodiscard]] Expected combine(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const; + protected: [[nodiscard]] virtual Expected matchesTargetPredicate(std::string_view Name, const MachineInstr &Instruction, diff --git a/backend/include/rcc/TableGen/Record.h b/backend/include/rcc/TableGen/Record.h index b5abc23..9f3477f 100644 --- a/backend/include/rcc/TableGen/Record.h +++ b/backend/include/rcc/TableGen/Record.h @@ -334,6 +334,49 @@ struct SourceSelectionRule final { TextRange Range; }; +struct SourceCombinerOperandRenderer final { + enum class Kind : std::uint8_t { + RootOperand, + CapturedOperand, + CapturedTypeBits, + Immediate, + }; + + Kind SourceKind = Kind::RootOperand; + std::uint32_t OperandIndex = 0; + std::string CaptureSymbol; + std::int64_t Immediate = 0; + TextRange Range; +}; + +enum class SourceCombinerActionKind : std::uint8_t { + ReplaceRootWithCapturedOperand, + MutateRoot, +}; + +struct SourceCombinerAction final { + SourceCombinerActionKind Kind = SourceCombinerActionKind::ReplaceRootWithCapturedOperand; + std::string CapturedOperandSymbol; + std::string ResultOpcodeSymbol; + std::vector OperandRenderers; + std::vector ClearInstructionFlags; + TextRange Range; +}; + +struct SourceCombinerRule final { + std::string Symbol; + std::uint32_t Priority = 0; + std::string MatchOpcodeSymbol; + std::optional ResultType; + std::vector OperandTypes; + std::vector TargetPredicates; + std::vector InstructionFlags; + std::vector DefUsePredicates; + SourceCombinerAction Action; + std::vector EraseOperandDefinitions; + TextRange Range; +}; + struct DescriptionAST final { SourceTarget Target; std::vector RegisterUnits; @@ -350,6 +393,7 @@ struct DescriptionAST final { std::vector AssemblyFormats; std::vector Instructions; std::vector SelectionRules; + std::vector CombinerRules; }; [[nodiscard]] std::string lowerASCII(std::string_view Value); diff --git a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt index 5e3c33f..4a96d3a 100644 --- a/backend/lib/CodeGen/GlobalISel/CMakeLists.txt +++ b/backend/lib/CodeGen/GlobalISel/CMakeLists.txt @@ -4,6 +4,7 @@ set( RCCBackendGlobalISelSources CSEInfo.cpp CSEMIRBuilder.cpp + Combiner.cpp GIMatchTableExecutor.cpp GISelChangeObserver.cpp GISelValueTracking.cpp @@ -19,6 +20,7 @@ set( RCCBackendGlobalISelHeaders "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEInfo.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/CSEMIRBuilder.h" + "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/Combiner.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelChangeObserver.h" "${RCC_BACKEND_SOURCE_DIR}/include/rcc/CodeGen/GlobalISel/GISelValueTracking.h" @@ -39,6 +41,7 @@ target_sources(RCCBackendCodeGen PRIVATE ${RCCBackendGlobalISelSources}) rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/Combiner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GIMatchTableExecutor.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" @@ -54,6 +57,7 @@ rcc_backend_register_format_files( rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/CSEInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/CSEMIRBuilder.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/Combiner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GIMatchTableExecutor.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelChangeObserver.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISelValueTracking.cpp" diff --git a/backend/lib/CodeGen/GlobalISel/Combiner.cpp b/backend/lib/CodeGen/GlobalISel/Combiner.cpp new file mode 100644 index 0000000..6d65a50 --- /dev/null +++ b/backend/lib/CodeGen/GlobalISel/Combiner.cpp @@ -0,0 +1,103 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "rcc/CodeGen/GlobalISel/Combiner.h" + +#include "rcc/CodeGen/GlobalISel/Utils.h" +#include "rcc/CodeGen/LiveVariables.h" +#include "rcc/CodeGen/MachineBasicBlock.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineFunctionCloner.h" +#include "rcc/CodeGen/MachineInstr.h" + +#include +#include + +namespace rcc { + +const MachinePassContract &GlobalISelCombinerPass::contract() const noexcept { + return Contract; +} + +Expected GlobalISelCombinerPass::run(MachineFunction &Function, + const TargetDescription &Target, + MachineFunctionAnalysisManager &Analyses) { + if (!Function.properties().containsAll(contract().Requires)) + return makeUnexpected(ErrorCode::VerificationError, + "GlobalISel combiner input does not satisfy its stage contract"); + auto Trial = cloneMachineFunction( + Function, Target, + MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt}); + if (!Trial) + return std::unexpected(withErrorContext(Trial.error(), "GlobalISel combiner clone failed: ")); + + MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs); + auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions); + if (!TrialResult) + return std::unexpected(TrialResult.error()); + Actions.beginReplay(); + auto Result = runImplementation(Function, Target, Actions); + if (!Result) + return std::unexpected( + withErrorContext(Result.error(), "GlobalISel combiner replay diverged: ")); + auto Replayed = Actions.finishReplay(); + if (!Replayed) + return std::unexpected(Replayed.error()); + return Result; +} + +Expected +GlobalISelCombinerPass::runImplementation(MachineFunction &Function, + const TargetDescription &Target, + MachineActionReplay &Actions) const { + if (MaximumRewrites == 0 || MaximumIterations == 0) + return makeUnexpected(ErrorCode::InvalidArgument, + "GlobalISel combiner iteration limits must be nonzero"); + MachinePassResult Result; + std::size_t Rewrites = 0; + for (std::size_t Iteration = 0; Iteration < MaximumIterations; ++Iteration) { + bool IterationChanged = false; + for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; + Block = Block->next()) { + for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;) { + MachineInstr *Next = Instruction->next(); + auto Matches = Executor->match(*Table, *Instruction, Function, Target); + if (!Matches) + return std::unexpected(Matches.error()); + if (*Matches && Rewrites < MaximumRewrites) { + auto Accepted = Actions.request("gisel-combiner", Function, Instruction->stableID()); + if (!Accepted) + return std::unexpected(Accepted.error()); + if (*Accepted) { + auto Combined = Executor->combine(*Table, *Instruction, Function, Target); + if (!Combined) + return std::unexpected(Combined.error()); + if (*Combined) { + ++Rewrites; + IterationChanged = true; + Result.Changed = true; + } + } + } + Instruction = Next; + } + } + if (!IterationChanged || Rewrites == MaximumRewrites) + break; + } + + if (!Result.Changed) { + Result.Preserved = PreservedAnalyses::all(); + return Result; + } + if (Function.properties().has(MachineFunctionProperty::TracksLiveness)) { + auto Rebuilt = rebuildMachineLiveness(Function, Target); + if (!Rebuilt) + return std::unexpected(Rebuilt.error()); + } + Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands, + MachinePassChange::Registers}; + Result.Preserved = PreservedAnalyses::none(); + return Result; +} + +} // namespace rcc diff --git a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp index dd8d920..39699c2 100644 --- a/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp +++ b/backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp @@ -62,6 +62,11 @@ namespace { "generated match table has an invalid type predicate"); } +[[nodiscard]] bool matchesInstructionFlags(const MachineInstr &Instruction, + const GIMatchTableInstruction &Step) noexcept { + return (Instruction.flags().rawValue() & Step.Value) == Step.Value; +} + [[nodiscard]] Expected matchesMemorySize(const MachineInstr &Instruction, const GIMatchTableInstruction &Step) { if (Step.Value == 0) { @@ -299,6 +304,7 @@ struct MatchedRule final { PhysicalRegister, Temporary, CapturedImmediate, + CapturedTypeBits, Immediate, }; @@ -320,6 +326,8 @@ struct MatchedRule final { std::vector CapturedOperands; std::vector Instructions; std::vector EraseOperandDefinitions; + std::optional ReplaceRootCapture; + std::uint32_t ClearInstructionFlags = 0; }; [[nodiscard]] bool hasTemporary(const MatchedRule &Rule, std::uint32_t ID) { @@ -378,6 +386,22 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine return std::optional{}; break; } + case GIMatchTableOpcode::CheckInstructionFlag: + if (Applying || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid instruction flag predicate"); + if (!matchesInstructionFlags(Instruction, Step)) + return std::optional{}; + break; + case GIMatchTableOpcode::ClearInstructionFlags: + if (!Applying || Complete || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid flag clear action"); + if (Result.ClearInstructionFlags != 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table clears instruction flags twice"); + Result.ClearInstructionFlags = Step.Value; + break; case GIMatchTableOpcode::CheckOperandBank: { if (Applying) { return makeUnexpected(ErrorCode::VerificationError, @@ -607,6 +631,18 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine .ComplexRenderer = {}, }); break; + case GIMatchTableOpcode::RenderCapturedTypeBits: + if (Complete || Result.Instructions.empty() || Step.Value == 0 || + !hasCapturedOperand(Result, Step.Value)) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid captured type renderer"); + } + Result.Instructions.back().Operands.push_back({ + .SourceKind = MatchedRule::RenderedOperand::Kind::CapturedTypeBits, + .Value = Step.Value, + .ComplexRenderer = {}, + }); + break; case GIMatchTableOpcode::RenderPhysicalRegister: if (Complete || Result.Instructions.empty() || Step.Value == 0) { return makeUnexpected(ErrorCode::VerificationError, @@ -663,8 +699,18 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine .Immediate = Step.Immediate, }); break; + case GIMatchTableOpcode::ReplaceRootWithCapturedOperand: + if (Table.Kind != GIMatchTableKind::Combiner || Complete || Applying || + !Result.Instructions.empty() || Step.Value == 0 || + !hasCapturedOperand(Result, Step.Value) || Result.ReplaceRootCapture) { + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid root replacement action"); + } + Applying = true; + Result.ReplaceRootCapture = Step.Value; + break; case GIMatchTableOpcode::EraseOperandDefinition: { - if (Complete || Result.Instructions.empty()) { + if (Complete || (Result.Instructions.empty() && !Result.ReplaceRootCapture)) { return makeUnexpected(ErrorCode::VerificationError, "generated match table has an invalid erased definition"); } @@ -678,7 +724,8 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine break; } case GIMatchTableOpcode::Complete: - if (Complete || Result.Instructions.empty() || Index + 1 != First + Count) { + if (Complete || (Result.Instructions.empty() && !Result.ReplaceRootCapture) || + Index + 1 != First + Count) { return makeUnexpected(ErrorCode::VerificationError, "generated match table has an invalid completion action"); } @@ -687,7 +734,13 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine } } - if (!Complete || Result.Instructions.empty() || !Result.Instructions.front().ReplacesRoot) { + if (!Complete || + (Table.Kind == GIMatchTableKind::Selection && + (Result.Instructions.empty() || !Result.Instructions.front().ReplacesRoot)) || + (Table.Kind == GIMatchTableKind::Combiner && Result.Instructions.empty() && + !Result.ReplaceRootCapture) || + (Table.Kind == GIMatchTableKind::Combiner && !Result.Instructions.empty() && + Result.ReplaceRootCapture)) { return makeUnexpected(ErrorCode::VerificationError, "generated match table rule does not complete rendering"); } @@ -900,6 +953,24 @@ renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr & } return Captured->Operand.cloneDetached(); } + case MatchedRule::RenderedOperand::Kind::CapturedTypeBits: { + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(CapturedOperands, Rendered.Value); + if (Captured == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table renders an unknown captured type"); + const Register *Reg = Captured->Operand.getIf(); + if (Reg == nullptr || !Reg->isVirtual()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not a virtual register"); + auto Type = Function.registerInfo().getType(*Reg); + if (!Type) + return std::unexpected(Type.error()); + if (!Type->isCategoryNeutralScalar()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not scalar"); + return MachineOperand::immediate(static_cast(Type->scalarBitWidth())); + } case MatchedRule::RenderedOperand::Kind::PhysicalRegister: { auto Physical = PhysicalRegister::create(Rendered.Value); if (!Physical || Target.registers().physicalRegister(*Physical) == nullptr) { @@ -958,6 +1029,76 @@ renderOperand(const MatchedRule::RenderedOperand &Rendered, const MachineInstr & "generated match table has an invalid operand renderer"); } +[[nodiscard]] bool compatibleReplacement(Register Destination, Register Source, + const MachineFunction &Function, + const TargetDescription &Target) { + if (!Destination.isVirtual() || Source.isNoRegister()) + return false; + auto DestinationInfo = Function.registerInfo().virtualRegisterInfo(Destination); + if (!DestinationInfo) + return false; + const VirtualRegisterInfo &DestinationValue = DestinationInfo->get(); + if (Source.isPhysical()) { + const std::optional Physical = Source.physicalRegister(); + if (!Physical) + return false; + if (DestinationValue.RegClass && + !Target.registers().registerClassContains(*DestinationValue.RegClass, *Physical)) + return false; + return !DestinationValue.Bank || + Target.registers().bankContainsRegister(*DestinationValue.Bank, *Physical); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source); + if (!SourceInfo) + return false; + const VirtualRegisterInfo &SourceValue = SourceInfo->get(); + if (DestinationValue.Type != SourceValue.Type) + return false; + if (DestinationValue.Bank && + (!SourceValue.Bank || + !Target.registers().registerBanksOverlap(*DestinationValue.Bank, *SourceValue.Bank))) + return false; + if (DestinationValue.RegClass && + (!SourceValue.RegClass || !Target.registers().registerClassesOverlap( + *DestinationValue.RegClass, *SourceValue.RegClass))) + return false; + return true; +} + +[[nodiscard]] Expected replaceRootWithCapturedOperand(const MatchedRule &Rule, + MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) { + if (!Rule.ReplaceRootCapture) + return false; + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(Rule.CapturedOperands, *Rule.ReplaceRootCapture); + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Destination = Definition == nullptr ? nullptr : Definition->getIf(); + const Register *Source = Captured == nullptr ? nullptr : Captured->Operand.getIf(); + if (Destination == nullptr || Source == nullptr || !Definition->isDef() || Definition->isUse() || + (!Source->isVirtual() && !Source->isPhysical()) || Destination->isNoRegister() || + Source->isNoRegister() || !Destination->isVirtual() || + Function.registerInfo().getUniqueVRegDef(*Destination) != Definition || + !compatibleReplacement(*Destination, *Source, Function, Target)) { + return false; + } + if (Instruction.parent() == nullptr) + return makeUnexpected(ErrorCode::InternalError, "generated combiner root is detached"); + std::vector Uses; + for (MachineOperand &Use : Function.registerInfo().useOperands(*Destination, true)) + Uses.push_back(&Use); + for (MachineOperand *Use : Uses) { + auto Replaced = Use->setRegister(*Source); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + auto Erased = eraseInstr(Instruction, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + return true; +} + template [[nodiscard]] Expected applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &Function, const TargetDescription &Target, @@ -967,6 +1108,32 @@ template return makeUnexpected(ErrorCode::VerificationError, "generated match table input has no instruction descriptor"); } + if (Rule.ReplaceRootCapture) { + auto Replaced = replaceRootWithCapturedOperand(Rule, Instruction, Function, Target); + if (!Replaced) + return std::unexpected(Replaced.error()); + if (!*Replaced) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner root replacement is incompatible"); + for (const Register Reg : Rule.EraseOperandDefinitions) { + MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); + if (Definition == nullptr || !isTriviallyDead(*Definition, Function.registerInfo(), Target)) + continue; + auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast(Index)); + } + Instruction.setFlags(Flags); + } + return {}; + } const MachineInstrFlags InputFlags = Instruction.flags(); const bool InputMayRaiseFPException = InputDescriptor->Flags.has(InstructionFlag::MayRaiseFPException); @@ -1262,6 +1429,15 @@ template if (!Erased) return Rollback(Erased.error()); } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast(Index)); + } + Instruction.setFlags(Flags); + } return {}; } @@ -1370,4 +1546,47 @@ Expected GIMatchTableExecutor::select(const GIMatchTable &Table, MachineIn return false; } +Expected GIMatchTableExecutor::combine(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const { + if (Table.Kind != GIMatchTableKind::Combiner) + return makeUnexpected(ErrorCode::InvalidArgument, + "GlobalISel combiner received a selection match table"); + for (const GIMatchTableRule &Rule : Table.Rules) { + auto Match = matchRule(Table, Rule, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, + const TargetDescription &InputTarget) { + return matchesTargetPredicate(Name, Input, InputFunction, InputTarget); + }); + if (!Match) + return std::unexpected(Match.error()); + if (!*Match) + continue; + if (!(*Match)->ReplaceRootCapture) { + for (const MatchedRule::Instruction &Action : (*Match)->Instructions) { + if (Target.instructionDescriptor(Action.ResultOpcode) == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner selects an unknown instruction opcode"); + } + } + auto Applied = applyRule( + **Match, Instruction, Function, Target, + [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) { + return finalizeGeneratedInstruction(Output, Function, Target, InputFlags, + InputMayRaiseFPException); + }, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Applied) + return std::unexpected(Applied.error()); + return true; + } + return false; +} + } // namespace rcc diff --git a/backend/lib/TableGen/Parser.cpp b/backend/lib/TableGen/Parser.cpp index 50588fb..6c3b866 100644 --- a/backend/lib/TableGen/Parser.cpp +++ b/backend/lib/TableGen/Parser.cpp @@ -40,7 +40,8 @@ public: {"schema", "target", "register_units", "registers", "register_banks", "register_classes", "register_masks", "mir_operand_flags", "named_operands", "immediate_predicates", "scheduling_classes", "encoding_categories", - "assembly_formats", "calling_conventions", "instructions", "selection_rules"}, + "assembly_formats", "calling_conventions", "instructions", "selection_rules", + "combiner_rules"}, "target description root")) { return std::nullopt; } @@ -81,6 +82,7 @@ public: const yaml::Node *InstructionsNode = requiredNode(*Root, "instructions", "target description root"); const yaml::Node *SelectionRulesNode = optionalNode(*Root, "selection_rules"); + const yaml::Node *CombinerRulesNode = optionalNode(*Root, "combiner_rules"); if (UnitsNode == nullptr || RegistersNode == nullptr || BanksNode == nullptr || ClassesNode == nullptr || MasksNode == nullptr || NamedOperandsNode == nullptr || ImmediatePredicatesNode == nullptr || SchedulingClassesNode == nullptr || @@ -101,7 +103,9 @@ public: !parseCallingConventions(*CallingConventionsNode, Result.CallingConventions) || !parseInstructions(*InstructionsNode, Result.Instructions) || (SelectionRulesNode != nullptr && - !parseSelectionRules(*SelectionRulesNode, Result.SelectionRules))) { + !parseSelectionRules(*SelectionRulesNode, Result.SelectionRules)) || + (CombinerRulesNode != nullptr && + !parseCombinerRules(*CombinerRulesNode, Result.CombinerRules))) { return std::nullopt; } return Result; @@ -1712,6 +1716,181 @@ private: return true; } + [[nodiscard]] bool + parseCombinerOperandRenderers(const yaml::Node &Node, + std::vector &Result) { + if (!requireSequence(&Node, "combiner operand renderers")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "combiner operand renderer") || + !checkKeys(*Element, {"operand", "captured_operand", "captured_type_bits", "immediate"}, + "combiner operand renderer")) { + return false; + } + const yaml::Node *Operand = optionalNode(*Element, "operand"); + const yaml::Node *CapturedOperand = optionalNode(*Element, "captured_operand"); + const yaml::Node *CapturedTypeBits = optionalNode(*Element, "captured_type_bits"); + const yaml::Node *Immediate = optionalNode(*Element, "immediate"); + const std::uint32_t SourceCount = static_cast(Operand != nullptr) + + static_cast(CapturedOperand != nullptr) + + static_cast(CapturedTypeBits != nullptr) + + static_cast(Immediate != nullptr); + if (SourceCount != 1) { + fail(Element->range(), "combiner operand renderer requires exactly one source"); + return false; + } + SourceCombinerOperandRenderer Renderer{.SourceKind = + SourceCombinerOperandRenderer::Kind::RootOperand, + .OperandIndex = 0, + .CaptureSymbol = {}, + .Immediate = 0, + .Range = Element->range()}; + if (Operand != nullptr) { + const auto Index = unsignedInteger32(*Operand, "combiner operand renderer operand"); + if (!Index) + return false; + Renderer.OperandIndex = *Index; + } else if (CapturedOperand != nullptr) { + const auto Symbol = scalar(*CapturedOperand, "combiner operand renderer captured operand"); + if (!Symbol) + return false; + Renderer.SourceKind = SourceCombinerOperandRenderer::Kind::CapturedOperand; + Renderer.CaptureSymbol = *Symbol; + } else if (CapturedTypeBits != nullptr) { + const auto Symbol = + scalar(*CapturedTypeBits, "combiner operand renderer captured type bits"); + if (!Symbol) + return false; + Renderer.SourceKind = SourceCombinerOperandRenderer::Kind::CapturedTypeBits; + Renderer.CaptureSymbol = *Symbol; + } else { + const auto Value = signedInteger(*Immediate, "combiner operand renderer immediate"); + if (!Value) + return false; + Renderer.SourceKind = SourceCombinerOperandRenderer::Kind::Immediate; + Renderer.Immediate = *Value; + } + Result.push_back(std::move(Renderer)); + } + return true; + } + + [[nodiscard]] bool parseCombinerRuleMatch(const yaml::Node &Node, SourceCombinerRule &Result) { + if (!requireMapping(&Node, "combiner rule match") || + !checkKeys( + Node, + {"opcode", "result_type", "operand_types", "target_predicates", "flags", "def_use"}, + "combiner rule match")) { + return false; + } + const auto Opcode = requiredScalar(Node, "opcode", "combiner rule match"); + if (!Opcode) + return false; + Result.MatchOpcodeSymbol = *Opcode; + if (const yaml::Node *Type = optionalNode(Node, "result_type")) { + auto Parsed = parseSelectionTypePredicate(*Type, "combiner result type predicate"); + if (!Parsed) + return false; + Result.ResultType = std::move(*Parsed); + } + if (const yaml::Node *Types = optionalNode(Node, "operand_types")) { + if (!parseSelectionOperandTypes(*Types, Result.OperandTypes)) + return false; + } + if (const yaml::Node *Predicates = optionalNode(Node, "target_predicates")) { + if (!parseSelectionTargetPredicates(*Predicates, Result.TargetPredicates)) + return false; + } + if (const yaml::Node *Flags = optionalNode(Node, "flags")) { + const auto Parsed = scalarSequence(*Flags, "combiner instruction flags"); + if (!Parsed) + return false; + Result.InstructionFlags = *Parsed; + } + if (const yaml::Node *DefUse = optionalNode(Node, "def_use")) { + if (!parseSelectionDefUsePredicates(*DefUse, Result.DefUsePredicates)) + return false; + } + return true; + } + + [[nodiscard]] bool parseCombinerRuleApply(const yaml::Node &Node, SourceCombinerRule &Result) { + if (!requireMapping(&Node, "combiner rule apply") || + !checkKeys( + Node, + {"action", "capture", "opcode", "operands", "clear_flags", "erase_operand_definitions"}, + "combiner rule apply")) { + return false; + } + const auto Action = requiredScalar(Node, "action", "combiner rule apply"); + if (!Action) + return false; + if (*Action == "replace_root_with_capture") { + const auto Capture = requiredScalar(Node, "capture", "combiner rule apply"); + if (!Capture) + return false; + Result.Action.Kind = SourceCombinerActionKind::ReplaceRootWithCapturedOperand; + Result.Action.CapturedOperandSymbol = *Capture; + } else if (*Action == "mutate_root") { + const auto Opcode = requiredScalar(Node, "opcode", "combiner rule apply"); + const yaml::Node *Operands = requiredNode(Node, "operands", "combiner rule apply"); + if (!Opcode || Operands == nullptr) + return false; + Result.Action.Kind = SourceCombinerActionKind::MutateRoot; + Result.Action.ResultOpcodeSymbol = *Opcode; + if (!parseCombinerOperandRenderers(*Operands, Result.Action.OperandRenderers)) + return false; + } else { + fail(Node.range(), + "combiner rule apply action must be replace_root_with_capture or mutate_root"); + return false; + } + if (const yaml::Node *ClearFlags = optionalNode(Node, "clear_flags")) { + const auto Parsed = scalarSequence(*ClearFlags, "combiner action clear flags"); + if (!Parsed) + return false; + Result.Action.ClearInstructionFlags = *Parsed; + } + if (const yaml::Node *Erase = optionalNode(Node, "erase_operand_definitions")) { + auto Indices = unsignedInteger32Sequence(*Erase, "combiner operand definitions"); + if (!Indices) + return false; + Result.EraseOperandDefinitions = std::move(*Indices); + } + return true; + } + + [[nodiscard]] bool parseCombinerRules(const yaml::Node &Node, + std::vector &Result) { + if (!requireSequence(&Node, "combiner_rules")) + return false; + for (const yaml::NodeID ElementID : Node.sequence()) { + const yaml::Node *Element = Input.node(ElementID); + if (!requireMapping(Element, "combiner rule") || + !checkKeys(*Element, {"id", "priority", "match", "apply"}, "combiner rule")) { + return false; + } + const auto Symbol = requiredScalar(*Element, "id", "combiner rule"); + const yaml::Node *PriorityNode = requiredNode(*Element, "priority", "combiner rule"); + const yaml::Node *MatchNode = requiredNode(*Element, "match", "combiner rule"); + const yaml::Node *ApplyNode = requiredNode(*Element, "apply", "combiner rule"); + if (!Symbol || PriorityNode == nullptr || MatchNode == nullptr || ApplyNode == nullptr) + return false; + const auto Priority = unsignedInteger32(*PriorityNode, "combiner rule priority"); + if (!Priority) + return false; + SourceCombinerRule Rule; + Rule.Symbol = *Symbol; + Rule.Priority = *Priority; + Rule.Range = Element->range(); + if (!parseCombinerRuleMatch(*MatchNode, Rule) || !parseCombinerRuleApply(*ApplyNode, Rule)) + return false; + Result.push_back(std::move(Rule)); + } + return true; + } + [[nodiscard]] bool parseInstructions(const yaml::Node &Node, std::vector &Result) { if (!requireSequence(&Node, "instructions")) diff --git a/backend/lib/Target/RISCV/CMakeLists.txt b/backend/lib/Target/RISCV/CMakeLists.txt index 3972a92..2e1e224 100644 --- a/backend/lib/Target/RISCV/CMakeLists.txt +++ b/backend/lib/Target/RISCV/CMakeLists.txt @@ -19,6 +19,7 @@ set( "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelControlFlow.rccdesc" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelShift.rccdesc" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelFloating.rccdesc" + "${CMAKE_CURRENT_SOURCE_DIR}/RISCVGISelCombiner.rccdesc" ) set(RCCBackendRISCVTableGenArguments) foreach(RCCBackendRISCVDescriptionSource IN LISTS RCCBackendRISCVDescriptionSources) @@ -40,6 +41,10 @@ set( RCCBackendRISCVGeneratedGlobalISel "${RCC_BACKEND_BINARY_DIR}/generated/lib/Target/RISCV/RISCVGenGlobalISel.inc" ) +set( + RCCBackendRISCVGeneratedGlobalISelCombiner + "${RCC_BACKEND_BINARY_DIR}/generated/lib/Target/RISCV/RISCVGenGlobalISelCombiner.inc" +) add_custom_command( OUTPUT @@ -47,6 +52,7 @@ add_custom_command( "${RCCBackendRISCVGeneratedInstructionHeader}" "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" + "${RCCBackendRISCVGeneratedGlobalISelCombiner}" COMMAND "$" ${RCCBackendRISCVTableGenArguments} @@ -54,6 +60,7 @@ add_custom_command( --instruction-header "${RCCBackendRISCVGeneratedInstructionHeader}" --tables "${RCCBackendRISCVGeneratedTables}" --global-isel "${RCCBackendRISCVGeneratedGlobalISel}" + --global-isel-combiner "${RCCBackendRISCVGeneratedGlobalISelCombiner}" DEPENDS RCCBackendTableGenTool ${RCCBackendRISCVDescriptionSources} COMMENT "Generating RCC RV64GC target tables" VERBATIM @@ -66,6 +73,7 @@ add_custom_target( "${RCCBackendRISCVGeneratedInstructionHeader}" "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" + "${RCCBackendRISCVGeneratedGlobalISelCombiner}" ) set_source_files_properties( @@ -73,6 +81,7 @@ set_source_files_properties( "${RCCBackendRISCVGeneratedInstructionHeader}" "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" + "${RCCBackendRISCVGeneratedGlobalISelCombiner}" PROPERTIES GENERATED TRUE HEADER_FILE_ONLY TRUE ) @@ -80,6 +89,7 @@ add_library( RCCBackendRISCV GISel/RISCVCallLowering.cpp GISel/RISCVInstructionSelector.cpp + GISel/RISCVGISelCombiner.cpp GISel/RISCVLegalizerInfo.cpp GISel/RISCVRegisterBankInfo.cpp RISCVInstrInfo.cpp @@ -106,6 +116,7 @@ add_library( "${RCCBackendRISCVGeneratedInstructionHeader}" "${RCCBackendRISCVGeneratedTables}" "${RCCBackendRISCVGeneratedGlobalISel}" + "${RCCBackendRISCVGeneratedGlobalISelCombiner}" ) add_library(RCCBackend::RISCV ALIAS RCCBackendRISCV) add_dependencies(RCCBackendRISCV RCCBackendRISCVGeneratedTablesTarget) @@ -155,6 +166,7 @@ rcc_backend_register_format_files( "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVCallLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVCallLowering.h" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVInstructionSelector.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVGISelCombiner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVLegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVLegalizerInfo.h" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVRegisterBankInfo.cpp" @@ -199,6 +211,7 @@ rcc_backend_register_format_files( rcc_backend_register_tidy_files( "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVCallLowering.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVInstructionSelector.cpp" + "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVGISelCombiner.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVLegalizerInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/GISel/RISCVRegisterBankInfo.cpp" "${CMAKE_CURRENT_SOURCE_DIR}/RISCVInstrInfo.cpp" diff --git a/backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp b/backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp new file mode 100644 index 0000000..bf67c0a --- /dev/null +++ b/backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "RISCV.h" +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" +#include "rcc/CodeGen/MachineFunction.h" +#include "rcc/CodeGen/MachineInstr.h" +#include "rcc/CodeGen/MachineRegisterInfo.h" +#include "rcc/CodeGen/TargetDescription.h" + +#include + +namespace rcc::riscv { +namespace { + +#define GET_GLOBALISEL_COMBINER_TABLE +#include "RISCVGenGlobalISelCombiner.inc" +#undef GET_GLOBALISEL_COMBINER_TABLE + +class RISCVGISelCombinerExecutor final : public GIMatchTableExecutor { +protected: + [[nodiscard]] Expected + matchesTargetPredicate(std::string_view Name, const MachineInstr &Instruction, + const MachineFunction &Function, + const TargetDescription &Target) const override { + if (Name != "sext_cheaper_than_zext") + return GIMatchTableExecutor::matchesTargetPredicate(Name, Instruction, Function, Target); + const MachineOperand *Destination = Instruction.operandAt(0); + const MachineOperand *Source = Instruction.operandAt(1); + const Register *DestinationReg = + Destination == nullptr ? nullptr : Destination->getIf(); + const Register *SourceReg = Source == nullptr ? nullptr : Source->getIf(); + if (DestinationReg == nullptr || SourceReg == nullptr || !DestinationReg->isVirtual() || + !SourceReg->isVirtual()) + return false; + auto DestinationType = Function.registerInfo().getType(*DestinationReg); + auto SourceType = Function.registerInfo().getType(*SourceReg); + if (!DestinationType || !SourceType) + return false; + return DestinationType->isCategoryNeutralScalar() && SourceType->isCategoryNeutralScalar() && + DestinationType->scalarBitWidth() == 64 && SourceType->scalarBitWidth() == 32; + } +}; + +} // namespace + +const GIMatchTable &giselCombinerTable() noexcept { + static constexpr GIMatchTable Table = generatedGlobalISelCombinerMatchTable(); + return Table; +} + +const GIMatchTableExecutor &giselCombinerExecutor() noexcept { + static const RISCVGISelCombinerExecutor Executor; + return Executor; +} + +} // namespace rcc::riscv diff --git a/backend/lib/Target/RISCV/RISCV.h b/backend/lib/Target/RISCV/RISCV.h index 1a81f59..4699091 100644 --- a/backend/lib/Target/RISCV/RISCV.h +++ b/backend/lib/Target/RISCV/RISCV.h @@ -3,6 +3,7 @@ #ifndef RCC_LIB_TARGET_RISCV_RISCV_H #define RCC_LIB_TARGET_RISCV_RISCV_H +#include "rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h" #include "rcc/CodeGen/MachineCombinerPattern.h" #include "rcc/CodeGen/MachineOptimizationPipeline.h" #include "rcc/CodeGen/TargetFrameLowering.h" @@ -28,6 +29,8 @@ createRISCVInstructionSelector(const RISCVSubtarget &Subtarget, [[nodiscard]] const TargetFrameLowering &frameLowering() noexcept; [[nodiscard]] const TargetSchedulingModel &schedulingModel() noexcept; [[nodiscard]] const TargetMachineCombinerInfo &machineCombinerInfo() noexcept; +[[nodiscard]] const GIMatchTable &giselCombinerTable() noexcept; +[[nodiscard]] const GIMatchTableExecutor &giselCombinerExecutor() noexcept; [[nodiscard]] const TargetMemoryFoldingInfo &memoryFoldingInfo() noexcept; [[nodiscard]] const TargetPseudoExpansionInfo &pseudoExpansionInfo() noexcept; [[nodiscard]] MachineOptimizationPipelineTargetInfo optimizationPipelineInfo() noexcept; diff --git a/backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc b/backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc new file mode 100644 index 0000000..5f8585b --- /dev/null +++ b/backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc @@ -0,0 +1,173 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +combiner_rules: + - + id: combine_nneg_zext + priority: 500 + match: + opcode: G_ZEXT + result_type: { kind: scalar, bits: 64 } + operand_types: + - { index: 1, kind: scalar, bits: 32 } + target_predicates: [sext_cheaper_than_zext] + flags: [nneg] + def_use: + - + operand: 1 + opcode: G_TRUNC + captures: + - { id: source, operand: 1 } + - { id: trunc_result, operand: 0 } + apply: + action: mutate_root + opcode: G_SEXT_INREG + operands: + - { operand: 0 } + - { captured_operand: source } + - { captured_type_bits: trunc_result } + clear_flags: [nneg] + erase_operand_definitions: [1] + - + id: combine_shl_zero + priority: 100 + match: + opcode: G_SHL + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_lshr_zero + priority: 100 + match: + opcode: G_LSHR + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_ashr_zero + priority: 100 + match: + opcode: G_ASHR + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_sdiv_zero + priority: 100 + match: + opcode: G_SDIV + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_udiv_zero + priority: 100 + match: + opcode: G_UDIV + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_srem_zero + priority: 100 + match: + opcode: G_SREM + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_urem_zero + priority: 100 + match: + opcode: G_UREM + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] + - + id: combine_mul_zero + priority: 100 + match: + opcode: G_MUL + def_use: + - + operand: 1 + opcode: G_CONSTANT + captures: + - { id: zero, operand: 0 } + operand_def_constants: + - index: 1 + ranges: [{ min: 0, max: 0 }] + apply: + action: replace_root_with_capture + capture: zero + erase_operand_definitions: [1] diff --git a/backend/lib/Target/RISCV/RISCVPipeline.cpp b/backend/lib/Target/RISCV/RISCVPipeline.cpp index 00a4398..c24c57f 100644 --- a/backend/lib/Target/RISCV/RISCVPipeline.cpp +++ b/backend/lib/Target/RISCV/RISCVPipeline.cpp @@ -6,10 +6,10 @@ #include "GISel/RISCVRegisterBankInfo.h" #include "RISCV.h" #include "RISCVInstrInfo.h" +#include "rcc/CodeGen/GlobalISel/Combiner.h" #include "rcc/CodeGen/GlobalISel/InstructionSelect.h" #include "rcc/CodeGen/GlobalISel/Legalizer.h" #include "rcc/CodeGen/GlobalISel/RegBankSelect.h" -#include "rcc/CodeGen/MachineCombiner.h" #include "rcc/CodeGen/MachineFunction.h" #include "rcc/CodeGen/MachineOptimizationPipeline.h" #include "rcc/CodeGen/MachinePseudoExpansion.h" @@ -41,8 +41,8 @@ template [[nodiscard]] Expected addInitialPipeline(MachineFunctionPassManager &Pipeline, const RISCVSubtarget &Subtarget, RISCVPipelineOptions Options) { - auto Added = addPass(Pipeline, machineCombinerInfo(), - MachineCombinerStage::PreLegalizer); + auto Added = addPass( + Pipeline, giselCombinerTable(), giselCombinerExecutor(), "riscv-prelegalizer-combiner"); if (!Added) return std::unexpected(Added.error()); Added = addPass(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization, @@ -99,8 +99,8 @@ Expected addCanonicalPipeline(MachineFunctionPassManager &Pipeline, const MachineFunction &Function, const RISCVSubtarget &Subtarget, RISCVPipelineOptions Options) { if (!Function.properties().has(MachineFunctionProperty::Legalized)) { - auto Added = addPass(Pipeline, machineCombinerInfo(), - MachineCombinerStage::PreLegalizer); + auto Added = addPass( + Pipeline, giselCombinerTable(), giselCombinerExecutor(), "riscv-prelegalizer-combiner"); if (!Added) return std::unexpected(Added.error()); Added = addPass(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization, diff --git a/backend/utils/TableGen/CMakeLists.txt b/backend/utils/TableGen/CMakeLists.txt index 60fc769..4868946 100644 --- a/backend/utils/TableGen/CMakeLists.txt +++ b/backend/utils/TableGen/CMakeLists.txt @@ -6,6 +6,7 @@ set( CallingConvEmitter.cpp CodeEmitterGen.cpp GlobalISelEmitter.cpp + GlobalISelCombinerEmitter.cpp Common/CodeGenInstruction.cpp Common/CodeGenRegisters.cpp Common/CodeGenSchedule.cpp diff --git a/backend/utils/TableGen/Common/CodeGenSelection.cpp b/backend/utils/TableGen/Common/CodeGenSelection.cpp index 0d59d6b..5093f67 100644 --- a/backend/utils/TableGen/Common/CodeGenSelection.cpp +++ b/backend/utils/TableGen/Common/CodeGenSelection.cpp @@ -698,4 +698,302 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) { return true; } +bool CodeGenTarget::normalizeCombinerRules(NormalizedTargetModel &Result) { + std::unordered_set Symbols; + const auto NormalizeType = [this](const SourceSelectionTypePredicate &Source) + -> std::optional { + NormalizedSelectionTypeKind Kind = NormalizedSelectionTypeKind::Any; + if (Source.Kind == "scalar") + Kind = NormalizedSelectionTypeKind::Scalar; + else if (Source.Kind == "pointer") + Kind = NormalizedSelectionTypeKind::Pointer; + else if (Source.Kind != "any") { + fail(Source.Range, "combiner type kind must be 'any', 'scalar', or 'pointer'"); + return std::nullopt; + } + if (Source.Bits > LowLevelType::MaxBitWidth || + (Kind != NormalizedSelectionTypeKind::Any && Source.Bits == 0)) { + fail(Source.Range, "combiner type bit width is invalid for its kind"); + return std::nullopt; + } + return NormalizedSelectionTypePredicate{.Kind = Kind, .Bits = Source.Bits}; + }; + const auto NormalizeRanges = + [this](const std::vector &Ranges, + TextRange Range) -> std::optional> { + if (Ranges.empty()) { + fail(Range, "combiner def-use constant predicate requires at least one range"); + return std::nullopt; + } + std::vector ResultRanges; + ResultRanges.reserve(Ranges.size()); + for (const SourceSelectionConstantRange &Source : Ranges) { + if (Source.Minimum > Source.Maximum) { + fail(Source.SourceRange, "combiner def-use constant range is inverted"); + return std::nullopt; + } + ResultRanges.push_back({.Minimum = Source.Minimum, .Maximum = Source.Maximum}); + } + std::ranges::sort(ResultRanges, {}, &NormalizedSelectionConstantRange::Minimum); + for (std::size_t Index = 1; Index < ResultRanges.size(); ++Index) { + if (ResultRanges[Index].Minimum <= ResultRanges[Index - 1].Maximum) { + fail(Range, "combiner def-use constant ranges overlap"); + return std::nullopt; + } + } + return ResultRanges; + }; + const auto FlagValue = [](std::string_view Name) -> std::optional { + static constexpr std::array, 3> Flags = {{ + {"nneg", MachineInstrFlag::NonNeg}, + {"nsw", MachineInstrFlag::NoSignedWrap}, + {"nuw", MachineInstrFlag::NoUnsignedWrap}, + }}; + const auto Position = std::ranges::find(Flags, Name, &decltype(Flags)::value_type::first); + if (Position == Flags.end()) + return std::nullopt; + return std::uint32_t{1} << static_cast(Position->second); + }; + const auto FlagMask = [&FlagValue](std::span Names, + TextRange Range) -> std::optional { + std::uint32_t Mask = 0; + for (const std::string &Name : Names) { + const auto Value = FlagValue(Name); + if (!Value || (Mask & *Value) != 0) + return std::nullopt; + Mask |= *Value; + } + if (Names.size() != 0 && Mask == 0) + return std::nullopt; + (void)Range; + return Mask; + }; + + for (const SourceCombinerRule &Rule : Input.CombinerRules) { + const auto MatchOpcode = resolveOpcode(Result, Rule.MatchOpcodeSymbol); + const NormalizedInstruction *MatchInstruction = + findInstructionBySymbol(Result, Rule.MatchOpcodeSymbol); + if (!isIdentifier(Rule.Symbol) || !Symbols.insert(Rule.Symbol).second || !MatchOpcode) { + fail(Rule.Range, "combiner rules require a unique identifier and declared match opcode"); + return false; + } + if (MatchInstruction != nullptr && !std::ranges::contains(MatchInstruction->Flags, "Generic")) { + fail(Rule.Range, "combiner rule match opcode must be generic"); + return false; + } + + NormalizedCombinerRule Normalized; + Normalized.Symbol = Rule.Symbol; + Normalized.Priority = Rule.Priority; + Normalized.Specificity = 1; + Normalized.MatchOpcode = *MatchOpcode; + if (Rule.ResultType) { + auto Type = NormalizeType(*Rule.ResultType); + if (!Type) + return false; + if (MatchInstruction != nullptr && !isRegisterOperand(*MatchInstruction, 0)) { + fail(Rule.ResultType->Range, + "combiner result type predicate requires register operand zero"); + return false; + } + Normalized.ResultType = *Type; + ++Normalized.Specificity; + } + + std::unordered_set TypeOperands; + for (const SourceSelectionOperandTypePredicate &Predicate : Rule.OperandTypes) { + auto Type = NormalizeType(Predicate.Type); + if (!Type) + return false; + if (!TypeOperands.insert(Predicate.OperandIndex).second || + (MatchInstruction != nullptr && + !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex))) { + fail(Predicate.Range, + "combiner operand type predicates require distinct register operands"); + return false; + } + Normalized.OperandTypes.push_back({.OperandIndex = Predicate.OperandIndex, .Type = *Type}); + ++Normalized.Specificity; + } + + std::unordered_set TargetPredicates; + for (const SourceSelectionTargetPredicate &Predicate : Rule.TargetPredicates) { + if (!isIdentifier(Predicate.Symbol) || !TargetPredicates.insert(Predicate.Symbol).second) { + fail(Predicate.Range, "combiner target predicates require distinct identifiers"); + return false; + } + Normalized.TargetPredicates.push_back(Predicate.Symbol); + ++Normalized.Specificity; + } + + std::uint32_t InstructionFlags = 0; + for (const std::string &Name : Rule.InstructionFlags) { + const auto Value = FlagValue(Name); + if (!Value) { + fail(Rule.Range, "combiner instruction flag is not supported"); + return false; + } + if ((InstructionFlags & *Value) != 0) { + fail(Rule.Range, "combiner instruction flags must be unique"); + return false; + } + InstructionFlags |= *Value; + ++Normalized.Specificity; + } + if (InstructionFlags != 0) + Normalized.InstructionFlags.push_back(InstructionFlags); + + std::unordered_set DefUseRoots; + std::unordered_set CaptureIDs; + std::unordered_map Captures; + std::uint32_t NextCaptureID = 1; + for (const SourceSelectionDefUsePredicate &Predicate : Rule.DefUsePredicates) { + const auto DefOpcode = resolveOpcode(Result, Predicate.OpcodeSymbol); + const NormalizedInstruction *DefInstruction = + findInstructionBySymbol(Result, Predicate.OpcodeSymbol); + if (!DefOpcode || !DefUseRoots.insert(Predicate.RootOperandIndex).second || + (MatchInstruction != nullptr && + !isRegisterOperand(*MatchInstruction, Predicate.RootOperandIndex)) || + (DefInstruction != nullptr && !std::ranges::contains(DefInstruction->Flags, "Generic"))) { + fail(Predicate.Range, "combiner def-use predicate has an invalid root or opcode"); + return false; + } + NormalizedSelectionDefUsePredicate DefUse{ + .RootOperandIndex = Predicate.RootOperandIndex, + .Opcode = *DefOpcode, + .IntegerPredicate = std::nullopt, + .Captures = {}, + .OperandDefConstants = {}, + }; + for (const SourceSelectionDefUseCapture &Capture : Predicate.Captures) { + if (!isIdentifier(Capture.Symbol) || Captures.contains(Capture.Symbol) || + !CaptureIDs.insert(NextCaptureID).second || + (DefInstruction != nullptr && + !isRegisterOperand(*DefInstruction, Capture.OperandIndex))) { + fail(Capture.Range, "combiner captures require unique identifiers and register operands"); + return false; + } + Captures.emplace(Capture.Symbol, NextCaptureID); + DefUse.Captures.push_back({.ID = NextCaptureID, .OperandIndex = Capture.OperandIndex}); + ++NextCaptureID; + } + for (const SourceSelectionOperandDefConstantPredicate &PredicateConstant : + Predicate.OperandDefConstants) { + auto Ranges = NormalizeRanges(PredicateConstant.Ranges, PredicateConstant.Range); + if (!Ranges) + return false; + if (DefInstruction != nullptr && + (PredicateConstant.OperandIndex >= DefInstruction->Operands.size() || + (!std::ranges::contains(DefInstruction->Operands[PredicateConstant.OperandIndex].Kinds, + "Immediate") && + !std::ranges::contains(DefInstruction->Operands[PredicateConstant.OperandIndex].Kinds, + "IntegerImmediate")))) { + fail(PredicateConstant.Range, "combiner def-use constant operand is not immediate"); + return false; + } + DefUse.OperandDefConstants.push_back({ + .OperandIndex = PredicateConstant.OperandIndex, + .Ranges = std::move(*Ranges), + }); + } + Normalized.DefUsePredicates.push_back(std::move(DefUse)); + ++Normalized.Specificity; + } + if (Rule.DefUsePredicates.empty()) { + fail(Rule.Range, "combiner rule requires a def-use predicate"); + return false; + } + + NormalizedCombinerAction Action; + if (Rule.Action.Kind == SourceCombinerActionKind::ReplaceRootWithCapturedOperand) { + const auto Capture = Captures.find(Rule.Action.CapturedOperandSymbol); + if (Capture == Captures.end()) { + fail(Rule.Action.Range, "combiner replacement requires a matched capture"); + return false; + } + Action.Kind = NormalizedCombinerActionKind::ReplaceRootWithCapturedOperand; + Action.CapturedOperand = Capture->second; + } else { + const auto ResultOpcode = resolveOpcode(Result, Rule.Action.ResultOpcodeSymbol); + const NormalizedInstruction *ResultInstruction = + findInstructionBySymbol(Result, Rule.Action.ResultOpcodeSymbol); + if (!ResultOpcode || (ResultInstruction != nullptr && + !std::ranges::contains(ResultInstruction->Flags, "Generic"))) { + fail(Rule.Action.Range, "combiner mutation requires a declared generic result opcode"); + return false; + } + Action.Kind = NormalizedCombinerActionKind::MutateRoot; + Action.ResultOpcode = *ResultOpcode; + for (const SourceCombinerOperandRenderer &Renderer : Rule.Action.OperandRenderers) { + NormalizedCombinerOperandRenderer NormalizedRenderer; + switch (Renderer.SourceKind) { + case SourceCombinerOperandRenderer::Kind::RootOperand: + NormalizedRenderer.SourceKind = NormalizedCombinerOperandRenderer::Kind::RootOperand; + NormalizedRenderer.Value = Renderer.OperandIndex; + break; + case SourceCombinerOperandRenderer::Kind::CapturedOperand: { + const auto Capture = Captures.find(Renderer.CaptureSymbol); + if (Capture == Captures.end()) { + fail(Renderer.Range, "combiner renderer requires a matched capture"); + return false; + } + NormalizedRenderer.SourceKind = NormalizedCombinerOperandRenderer::Kind::CapturedOperand; + NormalizedRenderer.Value = Capture->second; + break; + } + case SourceCombinerOperandRenderer::Kind::CapturedTypeBits: { + const auto Capture = Captures.find(Renderer.CaptureSymbol); + if (Capture == Captures.end()) { + fail(Renderer.Range, "combiner type-width renderer requires a matched capture"); + return false; + } + NormalizedRenderer.SourceKind = NormalizedCombinerOperandRenderer::Kind::CapturedTypeBits; + NormalizedRenderer.Value = Capture->second; + break; + } + case SourceCombinerOperandRenderer::Kind::Immediate: + NormalizedRenderer.SourceKind = NormalizedCombinerOperandRenderer::Kind::Immediate; + NormalizedRenderer.Immediate = Renderer.Immediate; + break; + } + Action.OperandRenderers.push_back(NormalizedRenderer); + } + if (Action.OperandRenderers.empty()) { + fail(Rule.Action.Range, "combiner mutation requires operand renderers"); + return false; + } + } + if (!Rule.Action.ClearInstructionFlags.empty()) { + const auto ClearFlags = FlagMask(Rule.Action.ClearInstructionFlags, Rule.Action.Range); + if (!ClearFlags) { + fail(Rule.Action.Range, "combiner action clear flags are invalid or duplicated"); + return false; + } + Action.ClearInstructionFlags = *ClearFlags; + } + Normalized.Action = std::move(Action); + std::unordered_set Erased; + for (const std::uint32_t OperandIndex : Rule.EraseOperandDefinitions) { + if (!Erased.insert(OperandIndex).second || + (MatchInstruction != nullptr && !isRegisterOperand(*MatchInstruction, OperandIndex)) || + !DefUseRoots.contains(OperandIndex)) { + fail(Rule.Range, "combiner erased definitions must be distinct def-use operands"); + return false; + } + Normalized.EraseOperandDefinitions.push_back(OperandIndex); + } + Result.CombinerRules.push_back(std::move(Normalized)); + } + + std::ranges::sort(Result.CombinerRules, + [](const NormalizedCombinerRule &Left, const NormalizedCombinerRule &Right) { + if (Left.Priority != Right.Priority) + return Left.Priority > Right.Priority; + if (Left.Specificity != Right.Specificity) + return Left.Specificity > Right.Specificity; + return Left.Symbol < Right.Symbol; + }); + return true; +} + } // namespace rcc::targetgen diff --git a/backend/utils/TableGen/Common/CodeGenTarget.cpp b/backend/utils/TableGen/Common/CodeGenTarget.cpp index 6d2e47e..f3217cf 100644 --- a/backend/utils/TableGen/Common/CodeGenTarget.cpp +++ b/backend/utils/TableGen/Common/CodeGenTarget.cpp @@ -36,7 +36,7 @@ CodeGenTarget::CodeGenTarget(const DescriptionAST &Input, std::string SourceName !normalizeNamedOperands(Result) || !normalizeImmediatePredicates(Result) || !normalizeSchedulingClasses(Result) || !normalizeEncodingCategories(Result) || !normalizeAssemblyFormats(Result) || !normalizeInstructions(Result) || - !normalizeSelectionRules(Result)) { + !normalizeSelectionRules(Result) || !normalizeCombinerRules(Result)) { return std::nullopt; } std::ranges::sort(Result.RegisterUnits, {}, &SourceRegisterUnit::ID); @@ -216,6 +216,7 @@ DescriptionGenerationResult generateDescription(const std::string &SourceName, emitAssemblyWriter(*Model) + emitSearchableTables(*Model) + emitCallingConventions(*Model), .GlobalISel = emitGlobalISel(*Model, DisplayName), + .GlobalISelCombiner = emitGlobalISelCombiner(*Model, DisplayName), }, .Diagnostics = {}, }; diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h index 3a7d299..49d910e 100644 --- a/backend/utils/TableGen/Common/CodeGenTarget.h +++ b/backend/utils/TableGen/Common/CodeGenTarget.h @@ -290,6 +290,46 @@ struct NormalizedSelectionRule final { std::vector EraseOperandDefinitions; }; +enum class NormalizedCombinerActionKind : std::uint8_t { + ReplaceRootWithCapturedOperand, + MutateRoot, +}; + +struct NormalizedCombinerOperandRenderer final { + enum class Kind : std::uint8_t { + RootOperand, + CapturedOperand, + CapturedTypeBits, + Immediate, + }; + + Kind SourceKind = Kind::RootOperand; + std::uint32_t Value = 0; + std::int64_t Immediate = 0; +}; + +struct NormalizedCombinerAction final { + NormalizedCombinerActionKind Kind = NormalizedCombinerActionKind::ReplaceRootWithCapturedOperand; + std::uint32_t CapturedOperand = 0; + std::uint32_t ResultOpcode = 0; + std::vector OperandRenderers; + std::uint32_t ClearInstructionFlags = 0; +}; + +struct NormalizedCombinerRule final { + std::string Symbol; + std::uint32_t Priority = 0; + std::uint32_t Specificity = 0; + std::uint32_t MatchOpcode = 0; + std::optional ResultType; + std::vector OperandTypes; + std::vector TargetPredicates; + std::vector InstructionFlags; + std::vector DefUsePredicates; + NormalizedCombinerAction Action; + std::vector EraseOperandDefinitions; +}; + struct NormalizedTargetModel final { SourceTarget Target; std::vector RegisterUnits; @@ -306,6 +346,7 @@ struct NormalizedTargetModel final { std::vector AssemblyFormats; std::vector Instructions; std::vector SelectionRules; + std::vector CombinerRules; }; [[nodiscard]] std::optional @@ -348,6 +389,7 @@ private: std::vector &Result); [[nodiscard]] bool normalizeInstructions(NormalizedTargetModel &Result); [[nodiscard]] bool normalizeSelectionRules(NormalizedTargetModel &Result); + [[nodiscard]] bool normalizeCombinerRules(NormalizedTargetModel &Result); const DescriptionAST &Input; std::string SourceName; diff --git a/backend/utils/TableGen/GlobalISelCombinerEmitter.cpp b/backend/utils/TableGen/GlobalISelCombinerEmitter.cpp new file mode 100644 index 0000000..0c727e3 --- /dev/null +++ b/backend/utils/TableGen/GlobalISelCombinerEmitter.cpp @@ -0,0 +1,154 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "TableGenBackends.h" + +#include +#include +#include +#include +#include + +namespace rcc::targetgen { +namespace { + +void emitInstruction(std::ostream &Output, std::string_view Opcode, std::uint32_t OperandIndex = 0, + std::uint32_t Value = 0, std::uint32_t Auxiliary = 0, + std::int64_t Immediate = 0, std::string_view Symbol = {}) { + Output << " {GIMatchTableOpcode::" << Opcode << ", " << OperandIndex << ", " << Value << ", " + << Auxiliary << ", " << Immediate << ", "; + appendQuoted(Output, Symbol); + Output << "},\n"; +} + +[[nodiscard]] std::size_t instructionCount(const NormalizedCombinerRule &Rule) noexcept { + std::size_t Count = 2U + (Rule.ResultType ? 1U : 0U) + Rule.OperandTypes.size() + + Rule.TargetPredicates.size() + Rule.InstructionFlags.size() + + (Rule.Action.ClearInstructionFlags != 0 ? 1U : 0U) + + Rule.EraseOperandDefinitions.size(); + for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) + Count += 1U + DefUse.Captures.size() + DefUse.OperandDefConstants.size(); + Count += Rule.Action.Kind == NormalizedCombinerActionKind::ReplaceRootWithCapturedOperand + ? 1U + : 1U + Rule.Action.OperandRenderers.size(); + return Count; +} + +} // namespace + +std::string emitGlobalISelCombiner(const NormalizedTargetModel &Model, + std::string_view SourceName) { + std::size_t InstructionCount = 0; + std::size_t ConstantRangeCount = 0; + for (const NormalizedCombinerRule &Rule : Model.CombinerRules) { + InstructionCount += instructionCount(Rule); + for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + DefUse.OperandDefConstants) + ConstantRangeCount += Predicate.Ranges.size(); + } + + std::ostringstream Output; + Output << "// SPDX-License-Identifier: GPL-3.0-or-later\n\n"; + Output << "// This file is generated by rcc-tblgen from "; + appendQuoted(Output, SourceName); + Output << ". Do not edit it manually.\n\n"; + Output << "#ifdef GET_GLOBALISEL_COMBINER_TABLE\n\n"; + Output << "constexpr std::array GeneratedGlobalISelCombinerConstantRanges = {{\n"; + for (const NormalizedCombinerRule &Rule : Model.CombinerRules) { + for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) { + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + DefUse.OperandDefConstants) { + for (const NormalizedSelectionConstantRange &Range : Predicate.Ranges) + Output << " {" << Range.Minimum << ", " << Range.Maximum << "},\n"; + } + } + } + Output << "}};\n\n"; + + Output << "constexpr std::array GeneratedGlobalISelCombinerInstructions = {{\n"; + std::size_t FirstConstantRange = 0; + for (const NormalizedCombinerRule &Rule : Model.CombinerRules) { + emitInstruction(Output, "CheckOpcode", 0, Rule.MatchOpcode); + if (Rule.ResultType) { + const char *Kind = "Any"; + if (Rule.ResultType->Kind == NormalizedSelectionTypeKind::Scalar) + Kind = "Scalar"; + else if (Rule.ResultType->Kind == NormalizedSelectionTypeKind::Pointer) + Kind = "Pointer"; + emitInstruction(Output, "CheckOperandType", 0, Rule.ResultType->Bits, + static_cast(Rule.ResultType->Kind)); + (void)Kind; + } + for (const NormalizedSelectionOperandTypePredicate &Predicate : Rule.OperandTypes) { + emitInstruction(Output, "CheckOperandType", Predicate.OperandIndex, Predicate.Type.Bits, + static_cast(Predicate.Type.Kind)); + } + for (const std::string &Predicate : Rule.TargetPredicates) + emitInstruction(Output, "CheckTargetPredicate", 0, 0, 0, 0, Predicate); + for (const std::uint32_t Flags : Rule.InstructionFlags) + emitInstruction(Output, "CheckInstructionFlag", 0, Flags); + for (const NormalizedSelectionDefUsePredicate &DefUse : Rule.DefUsePredicates) { + emitInstruction(Output, "CheckOperandDefOpcode", DefUse.RootOperandIndex, DefUse.Opcode); + for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : + DefUse.OperandDefConstants) { + emitInstruction(Output, "CheckOperandDefOperandConstantRanges", DefUse.RootOperandIndex, + static_cast(FirstConstantRange), Predicate.OperandIndex, + static_cast(Predicate.Ranges.size())); + FirstConstantRange += Predicate.Ranges.size(); + } + for (const NormalizedSelectionDefUseCapture &Capture : DefUse.Captures) + emitInstruction(Output, "CaptureDefOperand", DefUse.RootOperandIndex, Capture.ID, + Capture.OperandIndex); + } + if (Rule.Action.Kind == NormalizedCombinerActionKind::ReplaceRootWithCapturedOperand) { + emitInstruction(Output, "ReplaceRootWithCapturedOperand", 0, Rule.Action.CapturedOperand); + } else { + emitInstruction(Output, "MutateOpcode", 0, Rule.Action.ResultOpcode); + for (const NormalizedCombinerOperandRenderer &Renderer : Rule.Action.OperandRenderers) { + switch (Renderer.SourceKind) { + case NormalizedCombinerOperandRenderer::Kind::RootOperand: + emitInstruction(Output, "RenderOperand", Renderer.Value); + break; + case NormalizedCombinerOperandRenderer::Kind::CapturedOperand: + emitInstruction(Output, "RenderCapturedOperand", 0, Renderer.Value); + break; + case NormalizedCombinerOperandRenderer::Kind::CapturedTypeBits: + emitInstruction(Output, "RenderCapturedTypeBits", 0, Renderer.Value); + break; + case NormalizedCombinerOperandRenderer::Kind::Immediate: + emitInstruction(Output, "RenderImmediate", 0, 0, 0, Renderer.Immediate); + break; + } + } + } + if (Rule.Action.ClearInstructionFlags != 0) + emitInstruction(Output, "ClearInstructionFlags", 0, Rule.Action.ClearInstructionFlags); + for (const std::uint32_t OperandIndex : Rule.EraseOperandDefinitions) + emitInstruction(Output, "EraseOperandDefinition", OperandIndex); + emitInstruction(Output, "Complete"); + } + Output << "}};\n\n"; + + Output << "constexpr std::array GeneratedGlobalISelCombinerRules = {{\n"; + std::size_t FirstInstruction = 0; + for (const NormalizedCombinerRule &Rule : Model.CombinerRules) { + const std::size_t Count = instructionCount(Rule); + Output << " {"; + appendQuoted(Output, Rule.Symbol); + Output << ", " << Rule.Priority << ", " << FirstInstruction << ", " << Count << "},\n"; + FirstInstruction += Count; + } + Output << "}};\n\n"; + Output + << "[[nodiscard]] constexpr GIMatchTable generatedGlobalISelCombinerMatchTable() noexcept {\n" + " return {GeneratedGlobalISelCombinerInstructions, GeneratedGlobalISelCombinerRules,\n" + " GeneratedGlobalISelCombinerConstantRanges, GIMatchTableKind::Combiner};\n" + "}\n\n"; + Output << "#endif // GET_GLOBALISEL_COMBINER_TABLE\n"; + return Output.str(); +} + +} // namespace rcc::targetgen diff --git a/backend/utils/TableGen/TableGenBackends.h b/backend/utils/TableGen/TableGenBackends.h index a5f283e..5ac280e 100644 --- a/backend/utils/TableGen/TableGenBackends.h +++ b/backend/utils/TableGen/TableGenBackends.h @@ -18,6 +18,7 @@ struct GeneratedDescription final { std::string InstructionHeader; std::string TargetTables; std::string GlobalISel; + std::string GlobalISelCombiner; }; struct DescriptionGenerationResult final { @@ -44,6 +45,8 @@ struct DescriptionGenerationResult final { [[nodiscard]] std::string emitSearchableTables(const NormalizedTargetModel &Model); [[nodiscard]] std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view SourceName); +[[nodiscard]] std::string emitGlobalISelCombiner(const NormalizedTargetModel &Model, + std::string_view SourceName); [[nodiscard]] DescriptionGenerationResult generateDescription(const std::string &SourceName, std::string SourceText); diff --git a/backend/utils/TableGen/rcc-tblgen.cpp b/backend/utils/TableGen/rcc-tblgen.cpp index 45690ee..5a5a419 100644 --- a/backend/utils/TableGen/rcc-tblgen.cpp +++ b/backend/utils/TableGen/rcc-tblgen.cpp @@ -22,6 +22,7 @@ struct CommandLine final { std::string InstructionHeaderPath; std::string TablesPath; std::string GlobalISelPath; + std::string GlobalISelCombinerPath; }; [[nodiscard]] bool parseCommandLine(int ArgumentCount, char *Arguments[], CommandLine &Result) { @@ -36,7 +37,8 @@ struct CommandLine final { continue; } if (Argument == "--register-header" || Argument == "--instruction-header" || - Argument == "--tables" || Argument == "--global-isel") { + Argument == "--tables" || Argument == "--global-isel" || + Argument == "--global-isel-combiner") { if (Index + 1 >= ArgumentCount) { std::cerr << "rcc-tblgen: missing value for " << Argument << '\n'; return false; @@ -48,6 +50,8 @@ struct CommandLine final { Destination = &Result.InstructionHeaderPath; else if (Argument == "--global-isel") Destination = &Result.GlobalISelPath; + else if (Argument == "--global-isel-combiner") + Destination = &Result.GlobalISelCombinerPath; else Destination = &Result.TablesPath; *Destination = Arguments[++Index]; @@ -58,11 +62,12 @@ struct CommandLine final { } if (!Result.InputPaths.empty() && !Result.RegisterHeaderPath.empty() && !Result.InstructionHeaderPath.empty() && !Result.TablesPath.empty() && - !Result.GlobalISelPath.empty()) { + !Result.GlobalISelPath.empty() && !Result.GlobalISelCombinerPath.empty()) { return true; } std::cerr << "usage: rcc-tblgen --input [--input ]... --register-header " - "--instruction-header --tables --global-isel \n"; + "--instruction-header --tables --global-isel " + "--global-isel-combiner \n"; return false; } @@ -166,7 +171,8 @@ combineDescriptionSources(const std::vector &Paths, Result.push_back(Section); continue; } - if (Section.Name != "instructions" && Section.Name != "selection_rules") { + if (Section.Name != "instructions" && Section.Name != "selection_rules" && + Section.Name != "combiner_rules") { std::cerr << "rcc-tblgen: duplicate description section '" << Section.Name << "' in '" << Paths[Index] << "'\n"; return std::nullopt; @@ -226,7 +232,8 @@ int main(int ArgumentCount, char *Arguments[]) { return writeFile(Command.RegisterHeaderPath, Output.RegisterHeader) && writeFile(Command.InstructionHeaderPath, Output.InstructionHeader) && writeFile(Command.TablesPath, Output.TargetTables) && - writeFile(Command.GlobalISelPath, Output.GlobalISel) + writeFile(Command.GlobalISelPath, Output.GlobalISel) && + writeFile(Command.GlobalISelCombinerPath, Output.GlobalISelCombiner) ? 0 : 1; } -- cgit v1.2.3