[CodeGen] Generate RISC-V macro fusion rules

7 files changed, 339 insertions, 5 deletions

diff --git a/backend/utils/TableGen/CMakeLists.txt b/backend/utils/TableGen/CMakeLists.txt
index 4868946..ff6f8c8 100644
--- a/backend/utils/TableGen/CMakeLists.txt
+++ b/backend/utils/TableGen/CMakeLists.txt
@@ -7,7 +7,9 @@ set(
   CodeEmitterGen.cpp
   GlobalISelEmitter.cpp
   GlobalISelCombinerEmitter.cpp
+  MacroFusionEmitter.cpp
   Common/CodeGenInstruction.cpp
+  Common/CodeGenMacroFusion.cpp
   Common/CodeGenRegisters.cpp
   Common/CodeGenSchedule.cpp
   Common/CodeGenSelection.cpp
diff --git a/backend/utils/TableGen/Common/CodeGenMacroFusion.cpp b/backend/utils/TableGen/Common/CodeGenMacroFusion.cpp
new file mode 100644
index 0000000..7c4ea1c
--- /dev/null
+++ b/backend/utils/TableGen/Common/CodeGenMacroFusion.cpp
@@ -0,0 +1,175 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "CodeGenTarget.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <optional>
+#include <ranges>
+#include <string>
+#include <string_view>
+#include <unordered_set>
+#include <vector>
+
+namespace rcc::targetgen {
+namespace {
+
+[[nodiscard]] const NormalizedInstruction *findInstruction(const NormalizedTargetModel &Model,
+                                                           std::string_view Symbol) noexcept {
+  const auto Position =
+      std::ranges::find(Model.Instructions, Symbol, &NormalizedInstruction::Symbol);
+  return Position == Model.Instructions.end() ? nullptr : &*Position;
+}
+
+[[nodiscard]] bool isOperandKind(const NormalizedInstruction &Instruction,
+                                 std::uint32_t OperandIndex, std::string_view Kind) noexcept {
+  return OperandIndex < Instruction.Operands.size() &&
+         std::ranges::contains(Instruction.Operands[OperandIndex].Kinds, Kind);
+}
+
+[[nodiscard]] std::optional<NormalizedMacroFusionInstruction>
+normalizeInstructionSide(std::string_view Side) noexcept {
+  if (Side == "first")
+    return NormalizedMacroFusionInstruction::First;
+  if (Side == "second")
+    return NormalizedMacroFusionInstruction::Second;
+  return std::nullopt;
+}
+
+} // namespace
+
+bool CodeGenTarget::normalizeMacroFusionRules(NormalizedTargetModel &Result) {
+  std::unordered_set<std::string> Symbols;
+  std::unordered_set<std::string> Features;
+  for (const SourceMacroFusionRule &Rule : Input.MacroFusionRules) {
+    if (!isIdentifier(Rule.Symbol) || Rule.Feature.empty() || Rule.FirstOpcodeSymbols.empty() ||
+        Rule.SecondOpcodeSymbols.empty() || !Symbols.insert(Rule.Symbol).second ||
+        !Features.insert(Rule.Feature).second) {
+      fail(Rule.Range,
+           "macro fusion rules require unique identifiers and features plus nonempty opcode sets");
+      return false;
+    }
+
+    NormalizedMacroFusionRule Normalized{
+        .Symbol = Rule.Symbol,
+        .Feature = Rule.Feature,
+        .FirstOpcodes = {},
+        .SecondOpcodes = {},
+        .OpcodePairs = {},
+        .ImmediatePredicates = {},
+        .RegisterInequalities = {},
+        .ImmediateRelations = {},
+        .FirstDefinitionOperand = Rule.FirstDefinitionOperand,
+        .SecondUseOperand = Rule.SecondUseOperand,
+        .SecondDefinitionOperand = Rule.SecondDefinitionOperand,
+        .CommutableSecondUseOperand = Rule.CommutableSecondUseOperand,
+        .RequireSingleNonDebugUse = Rule.RequireSingleNonDebugUse,
+        .RequireSecondDestinationTie = Rule.RequireSecondDestinationTie,
+    };
+    std::unordered_set<std::uint32_t> FirstOpcodes;
+    std::unordered_set<std::uint32_t> SecondOpcodes;
+    std::vector<const NormalizedInstruction *> FirstInstructions;
+    std::vector<const NormalizedInstruction *> SecondInstructions;
+    const auto NormalizeOpcodes =
+        [this, &Result](const std::vector<std::string> &OpcodeSymbols,
+                        std::unordered_set<std::uint32_t> &Opcodes,
+                        std::vector<std::uint32_t> &Output,
+                        std::vector<const NormalizedInstruction *> &Instructions, TextRange Range) {
+          for (const std::string &Symbol : OpcodeSymbols) {
+            const NormalizedInstruction *Instruction = findInstruction(Result, Symbol);
+            if (Instruction == nullptr || !Opcodes.insert(Instruction->ID).second) {
+              fail(Range, "macro fusion opcodes must name distinct declared target instructions");
+              return false;
+            }
+            Output.push_back(Instruction->ID);
+            Instructions.push_back(Instruction);
+          }
+          return true;
+        };
+    if (!NormalizeOpcodes(Rule.FirstOpcodeSymbols, FirstOpcodes, Normalized.FirstOpcodes,
+                          FirstInstructions, Rule.Range) ||
+        !NormalizeOpcodes(Rule.SecondOpcodeSymbols, SecondOpcodes, Normalized.SecondOpcodes,
+                          SecondInstructions, Rule.Range)) {
+      return false;
+    }
+
+    const auto AllHaveOperandKind = [](const auto &Instructions, std::uint32_t Operand,
+                                       std::string_view Kind) {
+      return std::ranges::all_of(Instructions, [Operand, Kind](const auto *Instruction) {
+        return isOperandKind(*Instruction, Operand, Kind);
+      });
+    };
+    if (!AllHaveOperandKind(FirstInstructions, Rule.FirstDefinitionOperand, "Register") ||
+        !AllHaveOperandKind(SecondInstructions, Rule.SecondUseOperand, "Register") ||
+        (Rule.RequireSecondDestinationTie &&
+         !AllHaveOperandKind(SecondInstructions, Rule.SecondDefinitionOperand, "Register")) ||
+        (Rule.CommutableSecondUseOperand &&
+         !AllHaveOperandKind(SecondInstructions, *Rule.CommutableSecondUseOperand, "Register"))) {
+      fail(Rule.Range, "macro fusion linkage must reference register operands of every opcode");
+      return false;
+    }
+
+    std::unordered_set<std::uint64_t> OpcodePairs;
+    for (const SourceMacroFusionOpcodePair &Pair : Rule.OpcodePairs) {
+      const NormalizedInstruction *First = findInstruction(Result, Pair.FirstOpcodeSymbol);
+      const NormalizedInstruction *Second = findInstruction(Result, Pair.SecondOpcodeSymbol);
+      if (First == nullptr || Second == nullptr || !FirstOpcodes.contains(First->ID) ||
+          !SecondOpcodes.contains(Second->ID)) {
+        fail(Pair.Range, "macro fusion opcode pair must belong to the rule opcode sets");
+        return false;
+      }
+      const std::uint64_t Key = (static_cast<std::uint64_t>(First->ID) << 32U) | Second->ID;
+      if (!OpcodePairs.insert(Key).second) {
+        fail(Pair.Range, "macro fusion opcode pairs must be distinct");
+        return false;
+      }
+      Normalized.OpcodePairs.push_back({First->ID, Second->ID});
+    }
+
+    for (const SourceMacroFusionImmediatePredicate &Predicate : Rule.ImmediatePredicates) {
+      const auto Side = normalizeInstructionSide(Predicate.Instruction);
+      const auto &Instructions =
+          Side == NormalizedMacroFusionInstruction::First ? FirstInstructions : SecondInstructions;
+      if (!Side || Predicate.Minimum > Predicate.Maximum ||
+          !AllHaveOperandKind(Instructions, Predicate.OperandIndex, "Immediate")) {
+        fail(
+            Predicate.Range,
+            "macro fusion immediate predicate requires a valid side, range, and immediate operand");
+        return false;
+      }
+      Normalized.ImmediatePredicates.push_back(
+          {*Side, Predicate.OperandIndex, Predicate.Minimum, Predicate.Maximum});
+    }
+
+    for (const SourceMacroFusionRegisterInequality &Predicate : Rule.RegisterInequalities) {
+      const auto Side = normalizeInstructionSide(Predicate.Instruction);
+      const auto &Instructions =
+          Side == NormalizedMacroFusionInstruction::First ? FirstInstructions : SecondInstructions;
+      if (!Side || Predicate.LeftOperand == Predicate.RightOperand ||
+          !AllHaveOperandKind(Instructions, Predicate.LeftOperand, "Register") ||
+          !AllHaveOperandKind(Instructions, Predicate.RightOperand, "Register")) {
+        fail(
+            Predicate.Range,
+            "macro fusion register inequality requires distinct register operands on a valid side");
+        return false;
+      }
+      Normalized.RegisterInequalities.push_back(
+          {*Side, Predicate.LeftOperand, Predicate.RightOperand});
+    }
+
+    for (const SourceMacroFusionImmediateRelation &Relation : Rule.ImmediateRelations) {
+      if (Relation.Kind != "less_equal" ||
+          !AllHaveOperandKind(FirstInstructions, Relation.FirstOperand, "Immediate") ||
+          !AllHaveOperandKind(SecondInstructions, Relation.SecondOperand, "Immediate")) {
+        fail(Relation.Range,
+             "macro fusion immediate relation must be less_equal over immediate operands");
+        return false;
+      }
+      Normalized.ImmediateRelations.push_back({Relation.FirstOperand, Relation.SecondOperand});
+    }
+    Result.MacroFusionRules.push_back(std::move(Normalized));
+  }
+  return true;
+}
+
+} // namespace rcc::targetgen
diff --git a/backend/utils/TableGen/Common/CodeGenTarget.cpp b/backend/utils/TableGen/Common/CodeGenTarget.cpp
index f3217cf..9b96d2e 100644
--- a/backend/utils/TableGen/Common/CodeGenTarget.cpp
+++ b/backend/utils/TableGen/Common/CodeGenTarget.cpp
@@ -36,7 +36,8 @@ CodeGenTarget::CodeGenTarget(const DescriptionAST &Input, std::string SourceName
       !normalizeNamedOperands(Result) || !normalizeImmediatePredicates(Result) ||
       !normalizeSchedulingClasses(Result) || !normalizeEncodingCategories(Result) ||
       !normalizeAssemblyFormats(Result) || !normalizeInstructions(Result) ||
-      !normalizeSelectionRules(Result) || !normalizeCombinerRules(Result)) {
+      !normalizeSelectionRules(Result) || !normalizeCombinerRules(Result) ||
+      !normalizeMacroFusionRules(Result)) {
     return std::nullopt;
   }
   std::ranges::sort(Result.RegisterUnits, {}, &SourceRegisterUnit::ID);
@@ -217,6 +218,7 @@ DescriptionGenerationResult generateDescription(const std::string &SourceName,
                               emitCallingConventions(*Model),
               .GlobalISel = emitGlobalISel(*Model, DisplayName),
               .GlobalISelCombiner = emitGlobalISelCombiner(*Model, DisplayName),
+              .MacroFusion = emitMacroFusion(*Model, DisplayName),
           },
       .Diagnostics = {},
   };
diff --git a/backend/utils/TableGen/Common/CodeGenTarget.h b/backend/utils/TableGen/Common/CodeGenTarget.h
index 49d910e..6d3e185 100644
--- a/backend/utils/TableGen/Common/CodeGenTarget.h
+++ b/backend/utils/TableGen/Common/CodeGenTarget.h
@@ -106,6 +106,51 @@ struct NormalizedSchedulingClass final {
   std::uint32_t Latency = 0;
 };
 
+enum class NormalizedMacroFusionInstruction : std::uint8_t {
+  First,
+  Second,
+};
+
+struct NormalizedMacroFusionOpcodePair final {
+  std::uint32_t FirstOpcode = 0;
+  std::uint32_t SecondOpcode = 0;
+};
+
+struct NormalizedMacroFusionImmediatePredicate final {
+  NormalizedMacroFusionInstruction Instruction = NormalizedMacroFusionInstruction::First;
+  std::uint32_t OperandIndex = 0;
+  std::int64_t Minimum = 0;
+  std::int64_t Maximum = 0;
+};
+
+struct NormalizedMacroFusionRegisterInequality final {
+  NormalizedMacroFusionInstruction Instruction = NormalizedMacroFusionInstruction::First;
+  std::uint32_t LeftOperand = 0;
+  std::uint32_t RightOperand = 0;
+};
+
+struct NormalizedMacroFusionImmediateRelation final {
+  std::uint32_t FirstOperand = 0;
+  std::uint32_t SecondOperand = 0;
+};
+
+struct NormalizedMacroFusionRule final {
+  std::string Symbol;
+  std::string Feature;
+  std::vector<std::uint32_t> FirstOpcodes;
+  std::vector<std::uint32_t> SecondOpcodes;
+  std::vector<NormalizedMacroFusionOpcodePair> OpcodePairs;
+  std::vector<NormalizedMacroFusionImmediatePredicate> ImmediatePredicates;
+  std::vector<NormalizedMacroFusionRegisterInequality> RegisterInequalities;
+  std::vector<NormalizedMacroFusionImmediateRelation> ImmediateRelations;
+  std::uint32_t FirstDefinitionOperand = 0;
+  std::uint32_t SecondUseOperand = 0;
+  std::uint32_t SecondDefinitionOperand = 0;
+  std::optional<std::uint32_t> CommutableSecondUseOperand;
+  bool RequireSingleNonDebugUse = false;
+  bool RequireSecondDestinationTie = false;
+};
+
 struct NormalizedEncodingCategory final {
   std::uint32_t ID = 0;
   std::string Symbol;
@@ -347,6 +392,7 @@ struct NormalizedTargetModel final {
   std::vector<NormalizedInstruction> Instructions;
   std::vector<NormalizedSelectionRule> SelectionRules;
   std::vector<NormalizedCombinerRule> CombinerRules;
+  std::vector<NormalizedMacroFusionRule> MacroFusionRules;
 };
 
 [[nodiscard]] std::optional<std::string_view>
@@ -390,6 +436,7 @@ private:
   [[nodiscard]] bool normalizeInstructions(NormalizedTargetModel &Result);
   [[nodiscard]] bool normalizeSelectionRules(NormalizedTargetModel &Result);
   [[nodiscard]] bool normalizeCombinerRules(NormalizedTargetModel &Result);
+  [[nodiscard]] bool normalizeMacroFusionRules(NormalizedTargetModel &Result);
 
   const DescriptionAST &Input;
   std::string SourceName;
diff --git a/backend/utils/TableGen/MacroFusionEmitter.cpp b/backend/utils/TableGen/MacroFusionEmitter.cpp
new file mode 100644
index 0000000..2018a43
--- /dev/null
+++ b/backend/utils/TableGen/MacroFusionEmitter.cpp
@@ -0,0 +1,100 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "TableGenBackends.h"
+
+#include <cstddef>
+#include <cstdint>
+#include <ostream>
+#include <sstream>
+#include <string>
+#include <string_view>
+
+namespace rcc::targetgen {
+namespace {
+
+[[nodiscard]] std::string_view
+instructionSide(NormalizedMacroFusionInstruction Instruction) noexcept {
+  return Instruction == NormalizedMacroFusionInstruction::First ? "First" : "Second";
+}
+
+void emitOpcodes(std::ostream &Output, const NormalizedMacroFusionRule &Rule,
+                 std::string_view Suffix, const std::vector<std::uint32_t> &Opcodes) {
+  Output << "constexpr std::array<Opcode, " << Opcodes.size() << "> " << Rule.Symbol << Suffix
+         << " = {{\n";
+  for (const std::uint32_t Opcode : Opcodes)
+    Output << "    Opcode::fromValue(" << Opcode << "),\n";
+  Output << "}};\n";
+}
+
+} // namespace
+
+std::string emitMacroFusion(const NormalizedTargetModel &Model, std::string_view SourceName) {
+  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_MACRO_FUSION_RULES\n\n";
+  for (const NormalizedMacroFusionRule &Rule : Model.MacroFusionRules) {
+    emitOpcodes(Output, Rule, "FirstOpcodes", Rule.FirstOpcodes);
+    emitOpcodes(Output, Rule, "SecondOpcodes", Rule.SecondOpcodes);
+    Output << "constexpr std::array<MacroFusionOpcodePair, " << Rule.OpcodePairs.size() << "> "
+           << Rule.Symbol << "OpcodePairs = {{\n";
+    for (const NormalizedMacroFusionOpcodePair &Pair : Rule.OpcodePairs) {
+      Output << "    {Opcode::fromValue(" << Pair.FirstOpcode << "), Opcode::fromValue("
+             << Pair.SecondOpcode << ")},\n";
+    }
+    Output << "}};\n";
+    Output << "constexpr std::array<MacroFusionImmediatePredicate, "
+           << Rule.ImmediatePredicates.size() << "> " << Rule.Symbol
+           << "ImmediatePredicates = {{\n";
+    for (const NormalizedMacroFusionImmediatePredicate &Predicate : Rule.ImmediatePredicates) {
+      Output << "    {MacroFusionInstruction::" << instructionSide(Predicate.Instruction) << ", "
+             << Predicate.OperandIndex << ", " << Predicate.Minimum << ", " << Predicate.Maximum
+             << "},\n";
+    }
+    Output << "}};\n";
+    Output << "constexpr std::array<MacroFusionRegisterInequality, "
+           << Rule.RegisterInequalities.size() << "> " << Rule.Symbol
+           << "RegisterInequalities = {{\n";
+    for (const NormalizedMacroFusionRegisterInequality &Predicate : Rule.RegisterInequalities) {
+      Output << "    {MacroFusionInstruction::" << instructionSide(Predicate.Instruction) << ", "
+             << Predicate.LeftOperand << ", " << Predicate.RightOperand << "},\n";
+    }
+    Output << "}};\n";
+    Output << "constexpr std::array<MacroFusionImmediateRelation, "
+           << Rule.ImmediateRelations.size() << "> " << Rule.Symbol << "ImmediateRelations = {{\n";
+    for (const NormalizedMacroFusionImmediateRelation &Relation : Rule.ImmediateRelations)
+      Output << "    {" << Relation.FirstOperand << ", " << Relation.SecondOperand << "},\n";
+    Output << "}};\n\n";
+  }
+
+  Output << "constexpr std::array<MacroFusionRule, " << Model.MacroFusionRules.size()
+         << "> GeneratedMacroFusionRules = {{\n";
+  for (const NormalizedMacroFusionRule &Rule : Model.MacroFusionRules) {
+    Output << "    {";
+    appendQuoted(Output, Rule.Symbol);
+    Output << ", ";
+    appendQuoted(Output, Rule.Feature);
+    Output << ", " << Rule.Symbol << "FirstOpcodes, " << Rule.Symbol << "SecondOpcodes, "
+           << Rule.Symbol << "OpcodePairs, " << Rule.Symbol << "ImmediatePredicates, "
+           << Rule.Symbol << "RegisterInequalities, " << Rule.Symbol << "ImmediateRelations, "
+           << Rule.FirstDefinitionOperand << ", " << Rule.SecondUseOperand << ", "
+           << Rule.SecondDefinitionOperand << ", ";
+    if (Rule.CommutableSecondUseOperand)
+      Output << *Rule.CommutableSecondUseOperand;
+    else
+      Output << "MacroFusionRule::NoOperand";
+    Output << ", " << (Rule.RequireSingleNonDebugUse ? "true" : "false") << ", "
+           << (Rule.RequireSecondDestinationTie ? "true" : "false") << "},\n";
+  }
+  Output << "}};\n\n";
+  Output << "[[nodiscard]] constexpr std::span<const MacroFusionRule> "
+            "generatedMacroFusionRules() noexcept {\n"
+            "  return GeneratedMacroFusionRules;\n"
+            "}\n\n";
+  Output << "#endif // GET_MACRO_FUSION_RULES\n";
+  return Output.str();
+}
+
+} // namespace rcc::targetgen
diff --git a/backend/utils/TableGen/TableGenBackends.h b/backend/utils/TableGen/TableGenBackends.h
index 5ac280e..6315a6c 100644
--- a/backend/utils/TableGen/TableGenBackends.h
+++ b/backend/utils/TableGen/TableGenBackends.h
@@ -19,6 +19,7 @@ struct GeneratedDescription final {
   std::string TargetTables;
   std::string GlobalISel;
   std::string GlobalISelCombiner;
+  std::string MacroFusion;
 };
 
 struct DescriptionGenerationResult final {
@@ -47,6 +48,8 @@ struct DescriptionGenerationResult final {
                                          std::string_view SourceName);
 [[nodiscard]] std::string emitGlobalISelCombiner(const NormalizedTargetModel &Model,
                                                  std::string_view SourceName);
+[[nodiscard]] std::string emitMacroFusion(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 5a5a419..47f0de4 100644
--- a/backend/utils/TableGen/rcc-tblgen.cpp
+++ b/backend/utils/TableGen/rcc-tblgen.cpp
@@ -23,6 +23,7 @@ struct CommandLine final {
   std::string TablesPath;
   std::string GlobalISelPath;
   std::string GlobalISelCombinerPath;
+  std::string MacroFusionPath;
 };
 
 [[nodiscard]] bool parseCommandLine(int ArgumentCount, char *Arguments[], CommandLine &Result) {
@@ -38,7 +39,7 @@ struct CommandLine final {
     }
     if (Argument == "--register-header" || Argument == "--instruction-header" ||
         Argument == "--tables" || Argument == "--global-isel" ||
-        Argument == "--global-isel-combiner") {
+        Argument == "--global-isel-combiner" || Argument == "--macro-fusion") {
       if (Index + 1 >= ArgumentCount) {
         std::cerr << "rcc-tblgen: missing value for " << Argument << '\n';
         return false;
@@ -52,6 +53,8 @@ struct CommandLine final {
         Destination = &Result.GlobalISelPath;
       else if (Argument == "--global-isel-combiner")
         Destination = &Result.GlobalISelCombinerPath;
+      else if (Argument == "--macro-fusion")
+        Destination = &Result.MacroFusionPath;
       else
         Destination = &Result.TablesPath;
       *Destination = Arguments[++Index];
@@ -62,12 +65,13 @@ struct CommandLine final {
   }
   if (!Result.InputPaths.empty() && !Result.RegisterHeaderPath.empty() &&
       !Result.InstructionHeaderPath.empty() && !Result.TablesPath.empty() &&
-      !Result.GlobalISelPath.empty() && !Result.GlobalISelCombinerPath.empty()) {
+      !Result.GlobalISelPath.empty() && !Result.GlobalISelCombinerPath.empty() &&
+      !Result.MacroFusionPath.empty()) {
     return true;
   }
   std::cerr << "usage: rcc-tblgen --input <file> [--input <fragment>]... --register-header <file> "
                "--instruction-header <file> --tables <file> --global-isel <file> "
-               "--global-isel-combiner <file>\n";
+               "--global-isel-combiner <file> --macro-fusion <file>\n";
   return false;
 }
 
@@ -233,7 +237,8 @@ int main(int ArgumentCount, char *Arguments[]) {
                  writeFile(Command.InstructionHeaderPath, Output.InstructionHeader) &&
                  writeFile(Command.TablesPath, Output.TargetTables) &&
                  writeFile(Command.GlobalISelPath, Output.GlobalISel) &&
-                 writeFile(Command.GlobalISelCombinerPath, Output.GlobalISelCombiner)
+                 writeFile(Command.GlobalISelCombinerPath, Output.GlobalISelCombiner) &&
+                 writeFile(Command.MacroFusionPath, Output.MacroFusion)
              ? 0
              : 1;
 }