aboutsummaryrefslogtreecommitdiff
path: root/backend/utils
diff options
context:
space:
mode:
Diffstat (limited to 'backend/utils')
-rw-r--r--backend/utils/TableGen/Common/CodeGenSelection.cpp221
-rw-r--r--backend/utils/TableGen/Common/CodeGenTarget.h35
-rw-r--r--backend/utils/TableGen/GlobalISelEmitter.cpp73
3 files changed, 256 insertions, 73 deletions
diff --git a/backend/utils/TableGen/Common/CodeGenSelection.cpp b/backend/utils/TableGen/Common/CodeGenSelection.cpp
index cc80e41..1e65e04 100644
--- a/backend/utils/TableGen/Common/CodeGenSelection.cpp
+++ b/backend/utils/TableGen/Common/CodeGenSelection.cpp
@@ -11,7 +11,9 @@
#include <optional>
#include <ranges>
#include <span>
+#include <string>
#include <string_view>
+#include <unordered_map>
#include <unordered_set>
#include <utility>
@@ -135,31 +137,18 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
std::unordered_set<std::string> Symbols;
for (const SourceSelectionRule &Rule : Input.SelectionRules) {
const auto MatchOpcode = resolveOpcode(Result, Rule.MatchOpcodeSymbol);
- const auto ResultOpcode = resolveOpcode(Result, Rule.ResultOpcodeSymbol);
const NormalizedInstruction *MatchInstruction =
findInstructionBySymbol(Result, Rule.MatchOpcodeSymbol);
- const NormalizedInstruction *ResultInstruction =
- findInstructionBySymbol(Result, Rule.ResultOpcodeSymbol);
- if (!isIdentifier(Rule.Symbol) || !Symbols.insert(Rule.Symbol).second || !MatchOpcode ||
- !ResultOpcode) {
- fail(Rule.Range,
- "selection rules require a unique identifier and declared match/result opcodes");
+ if (!isIdentifier(Rule.Symbol) || !Symbols.insert(Rule.Symbol).second || !MatchOpcode) {
+ fail(Rule.Range, "selection rules require a unique identifier and declared match opcode");
return false;
}
if (MatchInstruction != nullptr && !std::ranges::contains(MatchInstruction->Flags, "Generic")) {
fail(Rule.Range, "selection rule match opcode must be generic");
return false;
}
- if (isGenericOpcode(Opcode::fromValue(*ResultOpcode)) ||
- (ResultInstruction != nullptr &&
- std::ranges::contains(ResultInstruction->Flags, "Generic"))) {
- fail(Rule.Range, "selection rule result opcode must not be generic");
- return false;
- }
- if (!Rule.OperandRenderers && MatchInstruction != nullptr && ResultInstruction != nullptr &&
- ResultInstruction->Operands.size() !=
- MatchInstruction->Operands.size() + Rule.AppendedImmediates.size()) {
- fail(Rule.Range, "selection rule result opcode has an incompatible operand count");
+ if (Rule.Actions.empty()) {
+ fail(Rule.Range, "selection rule requires at least one generated instruction");
return false;
}
@@ -187,8 +176,6 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
Normalized.Priority = Rule.Priority;
Normalized.Specificity = 1;
Normalized.MatchOpcode = *MatchOpcode;
- Normalized.ResultOpcode = *ResultOpcode;
- Normalized.AppendedImmediates = Rule.AppendedImmediates;
Normalized.EraseOperandDefinitions = Rule.EraseOperandDefinitions;
if (Rule.ResultType) {
auto Type = NormalizeType(*Rule.ResultType);
@@ -278,32 +265,98 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
for (const SourceSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants) {
if (!ConstantOperands.insert(Predicate.OperandIndex).second ||
(MatchInstruction != nullptr &&
- !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex))) {
+ !isRegisterOperand(*MatchInstruction, Predicate.OperandIndex)) || Predicate.Ranges.empty()) {
fail(Predicate.Range,
"selection operand definition constant predicates require distinct register "
- "operands");
+ "operands and at least one range");
return false;
}
- Normalized.OperandDefConstants.push_back(
- {.OperandIndex = Predicate.OperandIndex, .Value = Predicate.Value});
+ NormalizedSelectionOperandDefConstantPredicate NormalizedPredicate{
+ .OperandIndex = Predicate.OperandIndex,
+ .Ranges = {},
+ };
+ for (const SourceSelectionOperandDefConstantPredicate::ConstantRange &Range :
+ Predicate.Ranges) {
+ if (Range.Minimum > Range.Maximum) {
+ fail(Range.SourceRange, "selection operand definition constant range is invalid");
+ return false;
+ }
+ NormalizedPredicate.Ranges.push_back({
+ .Minimum = Range.Minimum,
+ .Maximum = Range.Maximum,
+ });
+ }
+ std::ranges::sort(NormalizedPredicate.Ranges, {},
+ &NormalizedSelectionOperandDefConstantPredicate::Range::Minimum);
+ for (std::size_t Index = 1; Index < NormalizedPredicate.Ranges.size(); ++Index) {
+ const auto &Previous = NormalizedPredicate.Ranges[Index - 1];
+ const auto &Current = NormalizedPredicate.Ranges[Index];
+ if (Current.Minimum <= Previous.Maximum) {
+ fail(Predicate.Range, "selection operand definition constant ranges overlap");
+ return false;
+ }
+ }
+ Normalized.OperandDefConstants.push_back(std::move(NormalizedPredicate));
++Normalized.Specificity;
}
- if (Rule.OperandRenderers) {
- if (!Rule.AppendedImmediates.empty()) {
- fail(Rule.Range, "selection rule cannot combine operand renderers and appended immediates");
+ std::unordered_map<std::string, std::uint32_t> TemporaryIDs;
+ for (const SourceSelectionTemporary &Temporary : Rule.Temporaries) {
+ if (!isIdentifier(Temporary.Symbol) ||
+ !TemporaryIDs.emplace(Temporary.Symbol, TemporaryIDs.size() + 1U).second ||
+ (MatchInstruction != nullptr &&
+ !isRegisterOperand(*MatchInstruction, Temporary.TypeFromOperand))) {
+ fail(Temporary.Range,
+ "selection temporary requires a unique identifier and a register type source");
+ return false;
+ }
+ Normalized.Temporaries.push_back({
+ .ID = TemporaryIDs.at(Temporary.Symbol),
+ .TypeFromOperand = Temporary.TypeFromOperand,
+ });
+ }
+
+ bool HasRootAction = false;
+ for (std::size_t ActionIndex = 0; ActionIndex < Rule.Actions.size(); ++ActionIndex) {
+ const SourceSelectionAction &Action = Rule.Actions[ActionIndex];
+ const auto ResultOpcode = resolveOpcode(Result, Action.ResultOpcodeSymbol);
+ const NormalizedInstruction *ResultInstruction =
+ findInstructionBySymbol(Result, Action.ResultOpcodeSymbol);
+ if (!ResultOpcode || ResultInstruction == nullptr ||
+ isGenericOpcode(Opcode::fromValue(*ResultOpcode)) ||
+ std::ranges::contains(ResultInstruction->Flags, "Generic")) {
+ fail(Action.Range, "selection instruction opcode must name a declared target instruction");
+ return false;
+ }
+ if (Action.ReplacesRoot == HasRootAction || (Action.ReplacesRoot && ActionIndex != 0)) {
+ fail(Action.Range,
+ "selection instructions require exactly one root replacement as their first action");
return false;
}
- std::vector<NormalizedSelectionOperandRenderer> Renderers;
- Renderers.reserve(Rule.OperandRenderers->size());
- for (const SourceSelectionOperandRenderer &Renderer : *Rule.OperandRenderers) {
+ HasRootAction |= Action.ReplacesRoot;
+ if (ResultInstruction->Operands.size() != Action.OperandRenderers.size()) {
+ fail(Action.Range, "selection instruction has an incompatible operand count");
+ return false;
+ }
+
+ NormalizedSelectionAction NormalizedAction{
+ .ResultOpcode = *ResultOpcode,
+ .ReplacesRoot = Action.ReplacesRoot,
+ .OperandRenderers = {},
+ };
+ NormalizedAction.OperandRenderers.reserve(Action.OperandRenderers.size());
+ for (const SourceSelectionOperandRenderer &Renderer : Action.OperandRenderers) {
if (Renderer.OperandIndex) {
if (MatchInstruction != nullptr &&
*Renderer.OperandIndex >= MatchInstruction->Operands.size()) {
fail(Renderer.Range, "selection operand renderer references an unknown operand");
return false;
}
- Renderers.push_back({
+ if (!Renderer.Flags.empty()) {
+ fail(Renderer.Range, "selection operand renderer cannot replace source register flags");
+ return false;
+ }
+ NormalizedAction.OperandRenderers.push_back({
.SourceKind = NormalizedSelectionOperandRenderer::Kind::Operand,
.Value = *Renderer.OperandIndex,
.Flags = 0,
@@ -311,34 +364,90 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
continue;
}
- const NormalizedRegister *Physical =
- findRegisterBySymbol(Result, Renderer.PhysicalRegisterSymbol);
- const auto Flags = registerOperandFlags(Renderer.Flags);
- if (Physical == nullptr || Physical->ID == 0 || !Flags) {
- fail(Renderer.Range,
- "selection physical register renderer requires a declared register and valid "
- "register flags");
- return false;
+ if (!Renderer.PhysicalRegisterSymbol.empty()) {
+ const NormalizedRegister *Physical =
+ findRegisterBySymbol(Result, Renderer.PhysicalRegisterSymbol);
+ const auto Flags = registerOperandFlags(Renderer.Flags);
+ if (Physical == nullptr || Physical->ID == 0 || !Flags ||
+ !validRegisterOperandFlags(*Flags)) {
+ fail(Renderer.Range,
+ "selection physical register renderer requires a declared register and valid "
+ "register flags");
+ return false;
+ }
+ NormalizedAction.OperandRenderers.push_back({
+ .SourceKind = NormalizedSelectionOperandRenderer::Kind::PhysicalRegister,
+ .Value = Physical->ID,
+ .Flags = Flags->rawValue(),
+ });
+ continue;
}
- if (!validRegisterOperandFlags(*Flags)) {
- fail(Renderer.Range, "selection physical register renderer is invalid");
- return false;
+
+ if (!Renderer.TemporarySymbol.empty()) {
+ const auto Temporary = TemporaryIDs.find(Renderer.TemporarySymbol);
+ const auto Flags = registerOperandFlags(Renderer.Flags);
+ if (Temporary == TemporaryIDs.end() || !Flags || !validRegisterOperandFlags(*Flags)) {
+ fail(Renderer.Range,
+ "selection temporary renderer requires a declared temporary and valid register "
+ "flags");
+ return false;
+ }
+ NormalizedAction.OperandRenderers.push_back({
+ .SourceKind = NormalizedSelectionOperandRenderer::Kind::Temporary,
+ .Value = Temporary->second,
+ .Flags = Flags->rawValue(),
+ });
+ continue;
}
- Renderers.push_back({
- .SourceKind = NormalizedSelectionOperandRenderer::Kind::PhysicalRegister,
- .Value = Physical->ID,
- .Flags = Flags->rawValue(),
- });
- }
- if (ResultInstruction != nullptr && ResultInstruction->Operands.size() != Renderers.size()) {
- fail(Rule.Range, "selection operand renderer has an incompatible operand count");
+
+ if (Renderer.CapturedImmediateOperand) {
+ const auto Transform = [&Renderer]()
+ -> std::optional<NormalizedSelectionImmediateTransform> {
+ if (Renderer.ImmediateTransform == "identity")
+ return NormalizedSelectionImmediateTransform::Identity;
+ if (Renderer.ImmediateTransform == "negate")
+ return NormalizedSelectionImmediateTransform::Negate;
+ if (Renderer.ImmediateTransform == "plus_one")
+ return NormalizedSelectionImmediateTransform::PlusOne;
+ return std::nullopt;
+ }();
+ if (!ConstantOperands.contains(*Renderer.CapturedImmediateOperand) || !Transform ||
+ !Renderer.Flags.empty()) {
+ fail(Renderer.Range,
+ "selection captured immediate renderer requires a matched constant and known "
+ "transform");
+ return false;
+ }
+ NormalizedAction.OperandRenderers.push_back({
+ .SourceKind = NormalizedSelectionOperandRenderer::Kind::CapturedImmediate,
+ .Value = *Renderer.CapturedImmediateOperand,
+ .Flags = 0,
+ .Transform = *Transform,
+ });
+ continue;
+ }
+
+ if (Renderer.Immediate) {
+ if (!Renderer.Flags.empty() || Renderer.ImmediateTransform != "identity") {
+ fail(Renderer.Range, "selection immediate renderer cannot carry register flags");
+ return false;
+ }
+ NormalizedAction.OperandRenderers.push_back({
+ .SourceKind = NormalizedSelectionOperandRenderer::Kind::Immediate,
+ .Value = 0,
+ .Flags = 0,
+ .Immediate = *Renderer.Immediate,
+ });
+ continue;
+ }
+
+ fail(Renderer.Range, "selection operand renderer has no normalized source");
return false;
}
- Normalized.OperandRenderers = std::move(Renderers);
- } else if (ResultInstruction != nullptr && MatchInstruction != nullptr &&
- ResultInstruction->Operands.size() !=
- MatchInstruction->Operands.size() + Rule.AppendedImmediates.size()) {
- fail(Rule.Range, "selection rule result opcode has an incompatible operand count");
+ Normalized.Actions.push_back(std::move(NormalizedAction));
+ }
+ if (!HasRootAction) {
+ fail(Rule.Range, "selection instructions require exactly one root replacement");
return false;
}
@@ -349,6 +458,10 @@ bool CodeGenTarget::normalizeSelectionRules(NormalizedTargetModel &Result) {
fail(Rule.Range, "selection erased definitions require distinct register operands");
return false;
}
+ if (!ConstantOperands.contains(OperandIndex)) {
+ fail(Rule.Range, "selection erased definition requires a matched constant operand");
+ return false;
+ }
}
Result.SelectionRules.push_back(std::move(Normalized));
}
diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h
index bee814f..42a28c1 100644
--- a/backend/utils/TableGen/Common/CodeGenTarget.h
+++ b/backend/utils/TableGen/Common/CodeGenTarget.h
@@ -195,19 +195,47 @@ struct NormalizedSelectionIntegerPredicate final {
};
struct NormalizedSelectionOperandDefConstantPredicate final {
+ struct Range final {
+ std::int64_t Minimum = 0;
+ std::int64_t Maximum = 0;
+ };
+
std::uint32_t OperandIndex = 0;
- std::int64_t Value = 0;
+ std::vector<Range> Ranges;
+};
+
+struct NormalizedSelectionTemporary final {
+ std::uint32_t ID = 0;
+ std::uint32_t TypeFromOperand = 0;
+};
+
+enum class NormalizedSelectionImmediateTransform : std::uint8_t {
+ Identity,
+ Negate,
+ PlusOne,
};
struct NormalizedSelectionOperandRenderer final {
enum class Kind : std::uint8_t {
Operand,
PhysicalRegister,
+ Temporary,
+ CapturedImmediate,
+ Immediate,
};
Kind SourceKind = Kind::Operand;
std::uint32_t Value = 0;
std::uint16_t Flags = 0;
+ NormalizedSelectionImmediateTransform Transform =
+ NormalizedSelectionImmediateTransform::Identity;
+ std::int64_t Immediate = 0;
+};
+
+struct NormalizedSelectionAction final {
+ std::uint32_t ResultOpcode = 0;
+ bool ReplacesRoot = false;
+ std::vector<NormalizedSelectionOperandRenderer> OperandRenderers;
};
struct NormalizedSelectionRule final {
@@ -221,9 +249,8 @@ struct NormalizedSelectionRule final {
std::vector<NormalizedSelectionOperandBankPredicate> OperandBanks;
std::vector<NormalizedSelectionOperandClassPredicate> OperandClasses;
std::vector<NormalizedSelectionOperandDefConstantPredicate> OperandDefConstants;
- std::uint32_t ResultOpcode = 0;
- std::optional<std::vector<NormalizedSelectionOperandRenderer>> OperandRenderers;
- std::vector<std::int64_t> AppendedImmediates;
+ std::vector<NormalizedSelectionTemporary> Temporaries;
+ std::vector<NormalizedSelectionAction> Actions;
std::vector<std::uint32_t> EraseOperandDefinitions;
};
diff --git a/backend/utils/TableGen/GlobalISelEmitter.cpp b/backend/utils/TableGen/GlobalISelEmitter.cpp
index 4bfeb22..784d418 100644
--- a/backend/utils/TableGen/GlobalISelEmitter.cpp
+++ b/backend/utils/TableGen/GlobalISelEmitter.cpp
@@ -39,19 +39,29 @@ void emitTypePredicate(std::ostream &Output, std::uint32_t OperandIndex,
}
[[nodiscard]] std::size_t instructionCount(const NormalizedSelectionRule &Rule) noexcept {
- return 3U + (Rule.ResultType ? 1U : 0U) + (Rule.IntegerPredicate ? 1U : 0U) +
+ std::size_t Count = 2U + (Rule.ResultType ? 1U : 0U) +
+ (Rule.IntegerPredicate ? 1U : 0U) +
Rule.OperandTypes.size() + Rule.OperandBanks.size() + Rule.OperandClasses.size() +
- Rule.OperandDefConstants.size() +
- (Rule.OperandRenderers ? Rule.OperandRenderers->size() : 0U) +
- Rule.AppendedImmediates.size() + Rule.EraseOperandDefinitions.size();
+ Rule.OperandDefConstants.size() + Rule.Temporaries.size() +
+ Rule.EraseOperandDefinitions.size();
+ for (const NormalizedSelectionAction &Action : Rule.Actions)
+ Count += 1U + Action.OperandRenderers.size();
+ return Count;
}
} // namespace
std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view SourceName) {
std::size_t InstructionCount = 0;
+ std::size_t ConstantRangeCount = 0;
for (const NormalizedSelectionRule &Rule : Model.SelectionRules)
InstructionCount += instructionCount(Rule);
+ for (const NormalizedSelectionRule &Rule : Model.SelectionRules) {
+ for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+ Rule.OperandDefConstants) {
+ ConstantRangeCount += Predicate.Ranges.size();
+ }
+ }
std::ostringstream Output;
Output << "// SPDX-License-Identifier: GPL-3.0-or-later\n\n";
@@ -59,8 +69,20 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
appendQuoted(Output, SourceName);
Output << ". Do not edit it manually.\n\n";
Output << "#ifdef GET_GLOBALISEL_MATCH_TABLE\n\n";
+ Output << "constexpr std::array<GIMatchTableConstantRange, " << ConstantRangeCount
+ << "> GeneratedGlobalISelConstantRanges = {{\n";
+ for (const NormalizedSelectionRule &Rule : Model.SelectionRules) {
+ for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+ Rule.OperandDefConstants) {
+ for (const NormalizedSelectionOperandDefConstantPredicate::Range &Range : Predicate.Ranges)
+ Output << " {" << Range.Minimum << ", " << Range.Maximum << "},\n";
+ }
+ }
+ Output << "}};\n\n";
+
Output << "constexpr std::array<GIMatchTableInstruction, " << InstructionCount
<< "> GeneratedGlobalISelInstructions = {{\n";
+ std::size_t FirstConstantRange = 0;
for (const NormalizedSelectionRule &Rule : Model.SelectionRules) {
emitInstruction(Output, "CheckOpcode", 0, Rule.MatchOpcode);
if (Rule.ResultType)
@@ -74,21 +96,41 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
emitInstruction(Output, "CheckOperandBank", Predicate.OperandIndex, Predicate.Bank);
for (const NormalizedSelectionOperandClassPredicate &Predicate : Rule.OperandClasses)
emitInstruction(Output, "CheckOperandClass", Predicate.OperandIndex, Predicate.RegClass);
- for (const NormalizedSelectionOperandDefConstantPredicate &Predicate : Rule.OperandDefConstants)
- emitInstruction(Output, "CheckOperandDefConstant", Predicate.OperandIndex, 0, "0",
- Predicate.Value);
- emitInstruction(Output, "MutateOpcode", 0, Rule.ResultOpcode);
- if (Rule.OperandRenderers) {
- for (const NormalizedSelectionOperandRenderer &Renderer : *Rule.OperandRenderers) {
- if (Renderer.SourceKind == NormalizedSelectionOperandRenderer::Kind::Operand)
+ for (const NormalizedSelectionOperandDefConstantPredicate &Predicate :
+ Rule.OperandDefConstants) {
+ emitInstruction(Output, "CheckOperandDefConstantRanges", Predicate.OperandIndex,
+ static_cast<std::uint32_t>(FirstConstantRange),
+ std::to_string(Predicate.Ranges.size()));
+ FirstConstantRange += Predicate.Ranges.size();
+ }
+ for (const NormalizedSelectionTemporary &Temporary : Rule.Temporaries)
+ emitInstruction(Output, "CreateTemporary", Temporary.TypeFromOperand, Temporary.ID);
+ for (const NormalizedSelectionAction &Action : Rule.Actions) {
+ emitInstruction(Output, Action.ReplacesRoot ? "MutateOpcode" : "BuildInstruction", 0,
+ Action.ResultOpcode);
+ for (const NormalizedSelectionOperandRenderer &Renderer : Action.OperandRenderers) {
+ switch (Renderer.SourceKind) {
+ case NormalizedSelectionOperandRenderer::Kind::Operand:
emitInstruction(Output, "RenderOperand", Renderer.Value);
- else
+ break;
+ case NormalizedSelectionOperandRenderer::Kind::PhysicalRegister:
emitInstruction(Output, "RenderPhysicalRegister", 0, Renderer.Value,
std::to_string(Renderer.Flags));
+ break;
+ case NormalizedSelectionOperandRenderer::Kind::Temporary:
+ emitInstruction(Output, "RenderTemporary", 0, Renderer.Value,
+ std::to_string(Renderer.Flags));
+ break;
+ case NormalizedSelectionOperandRenderer::Kind::CapturedImmediate:
+ emitInstruction(Output, "RenderCapturedImmediate", Renderer.Value,
+ static_cast<std::uint32_t>(Renderer.Transform));
+ break;
+ case NormalizedSelectionOperandRenderer::Kind::Immediate:
+ emitInstruction(Output, "RenderImmediate", 0, 0, "0", Renderer.Immediate);
+ break;
+ }
}
}
- for (const std::int64_t Immediate : Rule.AppendedImmediates)
- emitInstruction(Output, "AppendImmediate", 0, 0, "0", Immediate);
for (const std::uint32_t OperandIndex : Rule.EraseOperandDefinitions)
emitInstruction(Output, "EraseOperandDefinition", OperandIndex);
emitInstruction(Output, "Complete", 0);
@@ -107,7 +149,8 @@ std::string emitGlobalISel(const NormalizedTargetModel &Model, std::string_view
}
Output << "}};\n\n";
Output << "[[nodiscard]] constexpr GIMatchTable generatedGlobalISelMatchTable() noexcept {\n"
- " return {GeneratedGlobalISelInstructions, GeneratedGlobalISelRules};\n"
+ " return {GeneratedGlobalISelInstructions, GeneratedGlobalISelRules,\n"
+ " GeneratedGlobalISelConstantRanges};\n"
"}\n\n";
Output << "#endif // GET_GLOBALISEL_MATCH_TABLE\n";
return Output.str();
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-29 11:13:14 +0000