[GlobalISel] Generate prelegalizer combiner rules

3 files changed, 109 insertions, 0 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);