diff options
Diffstat (limited to 'backend/lib')
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/CMakeLists.txt | 4 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/Combiner.cpp | 103 | ||||
| -rw-r--r-- | backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp | 225 | ||||
| -rw-r--r-- | backend/lib/TableGen/Parser.cpp | 183 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/CMakeLists.txt | 13 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp | 56 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/RISCV.h | 3 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc | 173 | ||||
| -rw-r--r-- | backend/lib/Target/RISCV/RISCVPipeline.cpp | 10 |
9 files changed, 760 insertions, 10 deletions
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 <optional> +#include <string> + +namespace rcc { + +const MachinePassContract &GlobalISelCombinerPass::contract() const noexcept { + return Contract; +} + +Expected<MachinePassResult> 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<MachinePassResult> +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<bool> 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<CapturedOperand> CapturedOperands; std::vector<Instruction> Instructions; std::vector<Register> EraseOperandDefinitions; + std::optional<std::uint32_t> ReplaceRootCapture; + std::uint32_t ClearInstructionFlags = 0; }; [[nodiscard]] bool hasTemporary(const MatchedRule &Rule, std::uint32_t ID) { @@ -378,6 +386,22 @@ matchRule(const GIMatchTable &Table, const GIMatchTableRule &Rule, const Machine return std::optional<MatchedRule>{}; break; } + case GIMatchTableOpcode::CheckInstructionFlag: + if (Applying || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid instruction flag predicate"); + if (!matchesInstructionFlags(Instruction, Step)) + return std::optional<MatchedRule>{}; + break; + case GIMatchTableOpcode::ClearInstructionFlags: + if (!Applying || Complete || Step.Value == 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table has an invalid flag clear action"); + if (Result.ClearInstructionFlags != 0) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table clears instruction flags twice"); + Result.ClearInstructionFlags = Step.Value; + break; case GIMatchTableOpcode::CheckOperandBank: { if (Applying) { return makeUnexpected(ErrorCode::VerificationError, @@ -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<Register>(); + if (Reg == nullptr || !Reg->isVirtual()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not a virtual register"); + auto Type = Function.registerInfo().getType(*Reg); + if (!Type) + return std::unexpected(Type.error()); + if (!Type->isCategoryNeutralScalar()) + return makeUnexpected(ErrorCode::VerificationError, + "generated match table captured type is not scalar"); + return MachineOperand::immediate(static_cast<std::int64_t>(Type->scalarBitWidth())); + } case MatchedRule::RenderedOperand::Kind::PhysicalRegister: { auto Physical = PhysicalRegister::create(Rendered.Value); if (!Physical || Target.registers().physicalRegister(*Physical) == nullptr) { @@ -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<PhysicalRegister> Physical = Source.physicalRegister(); + if (!Physical) + return false; + if (DestinationValue.RegClass && + !Target.registers().registerClassContains(*DestinationValue.RegClass, *Physical)) + return false; + return !DestinationValue.Bank || + Target.registers().bankContainsRegister(*DestinationValue.Bank, *Physical); + } + auto SourceInfo = Function.registerInfo().virtualRegisterInfo(Source); + if (!SourceInfo) + return false; + const VirtualRegisterInfo &SourceValue = SourceInfo->get(); + if (DestinationValue.Type != SourceValue.Type) + return false; + if (DestinationValue.Bank && + (!SourceValue.Bank || + !Target.registers().registerBanksOverlap(*DestinationValue.Bank, *SourceValue.Bank))) + return false; + if (DestinationValue.RegClass && + (!SourceValue.RegClass || !Target.registers().registerClassesOverlap( + *DestinationValue.RegClass, *SourceValue.RegClass))) + return false; + return true; +} + +[[nodiscard]] Expected<bool> replaceRootWithCapturedOperand(const MatchedRule &Rule, + MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) { + if (!Rule.ReplaceRootCapture) + return false; + const MatchedRule::CapturedOperand *Captured = + findCapturedOperand(Rule.CapturedOperands, *Rule.ReplaceRootCapture); + const MachineOperand *Definition = Instruction.operandAt(0); + const Register *Destination = Definition == nullptr ? nullptr : Definition->getIf<Register>(); + const Register *Source = Captured == nullptr ? nullptr : Captured->Operand.getIf<Register>(); + if (Destination == nullptr || Source == nullptr || !Definition->isDef() || Definition->isUse() || + (!Source->isVirtual() && !Source->isPhysical()) || Destination->isNoRegister() || + Source->isNoRegister() || !Destination->isVirtual() || + Function.registerInfo().getUniqueVRegDef(*Destination) != Definition || + !compatibleReplacement(*Destination, *Source, Function, Target)) { + return false; + } + if (Instruction.parent() == nullptr) + return makeUnexpected(ErrorCode::InternalError, "generated combiner root is detached"); + std::vector<MachineOperand *> Uses; + for (MachineOperand &Use : Function.registerInfo().useOperands(*Destination, true)) + Uses.push_back(&Use); + for (MachineOperand *Use : Uses) { + auto Replaced = Use->setRegister(*Source); + if (!Replaced) + return std::unexpected(Replaced.error()); + } + auto Erased = eraseInstr(Instruction, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + return true; +} + template <typename Finalizer, typename ComplexRenderer> [[nodiscard]] Expected<void> applyRule(const MatchedRule &Rule, MachineInstr &Instruction, MachineFunction &Function, const TargetDescription &Target, @@ -967,6 +1108,32 @@ template <typename Finalizer, typename ComplexRenderer> return makeUnexpected(ErrorCode::VerificationError, "generated match table input has no instruction descriptor"); } + if (Rule.ReplaceRootCapture) { + auto Replaced = replaceRootWithCapturedOperand(Rule, Instruction, Function, Target); + if (!Replaced) + return std::unexpected(Replaced.error()); + if (!*Replaced) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner root replacement is incompatible"); + for (const Register Reg : Rule.EraseOperandDefinitions) { + MachineInstr *Definition = Function.registerInfo().getVRegDef(Reg); + if (Definition == nullptr || !isTriviallyDead(*Definition, Function.registerInfo(), Target)) + continue; + auto Erased = eraseInstr(*Definition, Function.registerInfo(), Target); + if (!Erased) + return std::unexpected(Erased.error()); + } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast<std::uint32_t>(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast<MachineInstrFlag>(Index)); + } + Instruction.setFlags(Flags); + } + return {}; + } const MachineInstrFlags InputFlags = Instruction.flags(); const bool InputMayRaiseFPException = InputDescriptor->Flags.has(InstructionFlag::MayRaiseFPException); @@ -1262,6 +1429,15 @@ template <typename Finalizer, typename ComplexRenderer> if (!Erased) return Rollback(Erased.error()); } + if (Rule.ClearInstructionFlags != 0) { + MachineInstrFlags Flags = Instruction.flags(); + for (std::uint32_t Index = 0; Index < static_cast<std::uint32_t>(MachineInstrFlag::Count); + ++Index) { + if ((Rule.ClearInstructionFlags & (std::uint32_t{1} << Index)) != 0) + Flags.clear(static_cast<MachineInstrFlag>(Index)); + } + Instruction.setFlags(Flags); + } return {}; } @@ -1370,4 +1546,47 @@ Expected<bool> GIMatchTableExecutor::select(const GIMatchTable &Table, MachineIn return false; } +Expected<bool> GIMatchTableExecutor::combine(const GIMatchTable &Table, MachineInstr &Instruction, + MachineFunction &Function, + const TargetDescription &Target) const { + if (Table.Kind != GIMatchTableKind::Combiner) + return makeUnexpected(ErrorCode::InvalidArgument, + "GlobalISel combiner received a selection match table"); + for (const GIMatchTableRule &Rule : Table.Rules) { + auto Match = matchRule(Table, Rule, Instruction, Function, Target, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, + const TargetDescription &InputTarget) { + return matchesTargetPredicate(Name, Input, InputFunction, InputTarget); + }); + if (!Match) + return std::unexpected(Match.error()); + if (!*Match) + continue; + if (!(*Match)->ReplaceRootCapture) { + for (const MatchedRule::Instruction &Action : (*Match)->Instructions) { + if (Target.instructionDescriptor(Action.ResultOpcode) == nullptr) + return makeUnexpected(ErrorCode::VerificationError, + "generated combiner selects an unknown instruction opcode"); + } + } + auto Applied = applyRule( + **Match, Instruction, Function, Target, + [this, &Function, &Target](MachineInstr &Output, MachineInstrFlags InputFlags, + bool InputMayRaiseFPException) { + return finalizeGeneratedInstruction(Output, Function, Target, InputFlags, + InputMayRaiseFPException); + }, + [this](std::string_view Name, const MachineInstr &Input, + const MachineFunction &InputFunction, const TargetDescription &InputTarget, + std::uint32_t OperandIndex) { + return renderComplexOperand(Name, Input, InputFunction, InputTarget, OperandIndex); + }); + if (!Applied) + return std::unexpected(Applied.error()); + return true; + } + return false; +} + } // namespace rcc 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<SourceCombinerOperandRenderer> &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<std::uint32_t>(Operand != nullptr) + + static_cast<std::uint32_t>(CapturedOperand != nullptr) + + static_cast<std::uint32_t>(CapturedTypeBits != nullptr) + + static_cast<std::uint32_t>(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<SourceCombinerRule> &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<SourceInstruction> &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 "$<TARGET_FILE:RCCBackendTableGenTool>" ${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 <string> + +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<bool> + 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<Register>(); + const Register *SourceReg = Source == nullptr ? nullptr : Source->getIf<Register>(); + 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 <typename PassT, typename... ArgumentT> [[nodiscard]] Expected<void> addInitialPipeline(MachineFunctionPassManager &Pipeline, const RISCVSubtarget &Subtarget, RISCVPipelineOptions Options) { - auto Added = addPass<MachineCombinerPass>(Pipeline, machineCombinerInfo(), - MachineCombinerStage::PreLegalizer); + auto Added = addPass<GlobalISelCombinerPass>( + Pipeline, giselCombinerTable(), giselCombinerExecutor(), "riscv-prelegalizer-combiner"); if (!Added) return std::unexpected(Added.error()); Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization, @@ -99,8 +99,8 @@ Expected<void> addCanonicalPipeline(MachineFunctionPassManager &Pipeline, const MachineFunction &Function, const RISCVSubtarget &Subtarget, RISCVPipelineOptions Options) { if (!Function.properties().has(MachineFunctionProperty::Legalized)) { - auto Added = addPass<MachineCombinerPass>(Pipeline, machineCombinerInfo(), - MachineCombinerStage::PreLegalizer); + auto Added = addPass<GlobalISelCombinerPass>( + Pipeline, giselCombinerTable(), giselCombinerExecutor(), "riscv-prelegalizer-combiner"); if (!Added) return std::unexpected(Added.error()); Added = addPass<Legalizer>(Pipeline, Subtarget.getLegalizerInfo(), Options.Optimization, |