aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRichard-Qin-X <richard.qin.001@gmail.com>2026-08-19 05:13:13 +0800
committerRichard-Qin-X <richard.qin.001@gmail.com>2026-08-19 05:13:13 +0800
commitdf7095e67ea06f7d6a81d99e70c804ce54ef950d (patch)
treeb61459583ac9972b196d5e639f02593374eae41f
parent307fc0961972ac5264d6f3459978fbec95cad3a9 (diff)
downloadrcc-project-df7095e67ea06f7d6a81d99e70c804ce54ef950d.tar.gz
rcc-project-df7095e67ea06f7d6a81d99e70c804ce54ef950d.tar.xz
[GlobalISel] Generate prelegalizer combiner rules
Diffstat
-rw-r--r--backend/include/rcc/CodeGen/GlobalISel/Combiner.h50
-rw-r--r--backend/include/rcc/CodeGen/GlobalISel/GIMatchTableExecutor.h15
-rw-r--r--backend/include/rcc/TableGen/Record.h44
-rw-r--r--backend/lib/CodeGen/GlobalISel/CMakeLists.txt4
-rw-r--r--backend/lib/CodeGen/GlobalISel/Combiner.cpp103
-rw-r--r--backend/lib/CodeGen/GlobalISel/GIMatchTableExecutor.cpp225
-rw-r--r--backend/lib/TableGen/Parser.cpp183
-rw-r--r--backend/lib/Target/RISCV/CMakeLists.txt13
-rw-r--r--backend/lib/Target/RISCV/GISel/RISCVGISelCombiner.cpp56
-rw-r--r--backend/lib/Target/RISCV/RISCV.h3
-rw-r--r--backend/lib/Target/RISCV/RISCVGISelCombiner.rccdesc173
-rw-r--r--backend/lib/Target/RISCV/RISCVPipeline.cpp10
-rw-r--r--backend/utils/TableGen/CMakeLists.txt1
-rw-r--r--backend/utils/TableGen/Common/CodeGenSelection.cpp298
-rw-r--r--backend/utils/TableGen/Common/CodeGenTarget.cpp3
-rw-r--r--backend/utils/TableGen/Common/CodeGenTarget.h42
-rw-r--r--backend/utils/TableGen/GlobalISelCombinerEmitter.cpp154
-rw-r--r--backend/utils/TableGen/TableGenBackends.h3
-rw-r--r--backend/utils/TableGen/rcc-tblgen.cpp17
19 files changed, 1381 insertions, 16 deletions
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 <cstddef>
+#include <string>
+#include <utility>
+
+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<MachinePassResult> run(MachineFunction &Function,
+ const TargetDescription &Target,
+ MachineFunctionAnalysisManager &Analyses) override;
+
+private:
+ [[nodiscard]] Expected<MachinePassResult> 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<const GIMatchTableInstruction> Instructions;
std::span<const GIMatchTableRule> Rules;
std::span<const GIMatchTableConstantRange> 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<bool> combine(const GIMatchTable &Table, MachineInstr &Instruction,
+ MachineFunction &Function,
+ const TargetDescription &Target) const;
+
protected:
[[nodiscard]] virtual Expected<bool>
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<SourceCombinerOperandRenderer> OperandRenderers;
+ std::vector<std::string> ClearInstructionFlags;
+ TextRange Range;
+};
+
+struct SourceCombinerRule final {
+ std::string Symbol;
+ std::uint32_t Priority = 0;
+ std::string MatchOpcodeSymbol;
+ std::optional<SourceSelectionTypePredicate> ResultType;
+ std::vector<SourceSelectionOperandTypePredicate> OperandTypes;
+ std::vector<SourceSelectionTargetPredicate> TargetPredicates;
+ std::vector<std::string> InstructionFlags;
+ std::vector<SourceSelectionDefUsePredicate> DefUsePredicates;
+ SourceCombinerAction Action;
+ std::vector<std::uint32_t> EraseOperandDefinitions;
+ TextRange Range;
+};
+
struct DescriptionAST final {
SourceTarget Target;
std::vector<SourceRegisterUnit> RegisterUnits;
@@ -350,6 +393,7 @@ struct DescriptionAST final {
std::vector<SourceAssemblyFormat> AssemblyFormats;
std::vector<SourceInstruction> Instructions;
std::vector<SourceSelectionRule> SelectionRules;
+ std::vector<SourceCombinerRule> 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 <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,
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<std::string> Symbols;
+ const auto NormalizeType = [this](const SourceSelectionTypePredicate &Source)
+ -> std::optional<NormalizedSelectionTypePredicate> {
+ 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<SourceSelectionConstantRange> &Ranges,
+ TextRange Range) -> std::optional<std::vector<NormalizedSelectionConstantRange>> {
+ if (Ranges.empty()) {
+ fail(Range, "combiner def-use constant predicate requires at least one range");
+ return std::nullopt;
+ }
+ std::vector<NormalizedSelectionConstantRange> 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<std::uint32_t> {
+ static constexpr std::array<std::pair<std::string_view, MachineInstrFlag>, 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<std::uint8_t>(Position->second);
+ };
+ const auto FlagMask = [&FlagValue](std::span<const std::string> Names,
+ TextRange Range) -> std::optional<std::uint32_t> {
+ 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<std::uint32_t> 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<std::string> 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<std::uint32_t> DefUseRoots;
+ std::unordered_set<std::uint32_t> CaptureIDs;
+ std::unordered_map<std::string, std::uint32_t> 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<std::uint32_t> 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<std::uint32_t> 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<NormalizedCombinerOperandRenderer> 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<NormalizedSelectionTypePredicate> ResultType;
+ std::vector<NormalizedSelectionOperandTypePredicate> OperandTypes;
+ std::vector<std::string> TargetPredicates;
+ std::vector<std::uint32_t> InstructionFlags;
+ std::vector<NormalizedSelectionDefUsePredicate> DefUsePredicates;
+ NormalizedCombinerAction Action;
+ std::vector<std::uint32_t> EraseOperandDefinitions;
+};
+
struct NormalizedTargetModel final {
SourceTarget Target;
std::vector<SourceRegisterUnit> RegisterUnits;
@@ -306,6 +346,7 @@ struct NormalizedTargetModel final {
std::vector<NormalizedAssemblyFormat> AssemblyFormats;
std::vector<NormalizedInstruction> Instructions;
std::vector<NormalizedSelectionRule> SelectionRules;
+ std::vector<NormalizedCombinerRule> CombinerRules;
};
[[nodiscard]] std::optional<std::string_view>
@@ -348,6 +389,7 @@ private:
std::vector<NormalizedImplicitRegister> &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 <cstddef>
+#include <cstdint>
+#include <sstream>
+#include <string>
+#include <string_view>
+
+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<GIMatchTableConstantRange, " << ConstantRangeCount
+ << "> 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<GIMatchTableInstruction, " << InstructionCount
+ << "> 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<std::uint32_t>(Rule.ResultType->Kind));
+ (void)Kind;
+ }
+ for (const NormalizedSelectionOperandTypePredicate &Predicate : Rule.OperandTypes) {
+ emitInstruction(Output, "CheckOperandType", Predicate.OperandIndex, Predicate.Type.Bits,
+ static_cast<std::uint32_t>(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<std::uint32_t>(FirstConstantRange), Predicate.OperandIndex,
+ static_cast<std::int64_t>(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<GIMatchTableRule, " << Model.CombinerRules.size()
+ << "> 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 <file> [--input <fragment>]... --register-header <file> "
- "--instruction-header <file> --tables <file> --global-isel <file>\n";
+ "--instruction-header <file> --tables <file> --global-isel <file> "
+ "--global-isel-combiner <file>\n";
return false;
}
@@ -166,7 +171,8 @@ combineDescriptionSources(const std::vector<std::string> &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;
}
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 13:23:32 +0000