[GlobalISel] Generate prelegalizer combiner rules

7 files changed, 512 insertions, 6 deletions

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;
 }