[RFC][TableGen][GlobalISel] Add Combiner Match Table Backend

[Pierre-vh]

Summary

Adds a new backend to power the GISel Combiners using the InstructionSelector's match tables.
This does not depend on any of the data structures created for the current combiner and is intended to replace it entirely.

See the RFC for more details: https://discourse.llvm.org/t/rfc-matchtable-based-globalisel-combiners/71457/6
Note: this would replace D141135.

[Pierre-vh]

Rebase

[Pierre-vh]

Change include guards to remove redundancy

[Pierre-vh]

Merge GICXXPred_Invalid flags

[arsenm]

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td

76–79

I'd expect all of this boilerplate to be in member / per function state initialization in the combiner info

[arsenm]

llvm/utils/TableGen/GlobalISelMatchTable.cpp

921–922

Yes, I don't see how this would be avoidable

[Pierre-vh]

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td

76–79

MF/MRI maybe (see D153756), the others too?
Note ST is simply to shorten the code a bit, it's just used to fetch InstrInfo/RegBankInfo.

[Pierre-vh]

Comments + rebase

[Pierre-vh]

Some cleanups/tidying the file.

[aemerson]

One problem I had with the existing combiner was that it was difficult to understand for someone unfamiliar with it. I think it would be helpful to have some more documentation in some places, for example some of the methods in CombineRuleBuilder. If we can make this code more accessible it will lower the friction for new contributors to make improvements and fixes.

Another useful piece of docs is a comment somewhere describing the ownership semantics. I see unique_ptr allocations and ownership transfers but it's not clear looking at the code why some pointer is being moved. On that topic, just freestyling here: would it be possible to use SpecificBumpPtrAllocator so we can just destroy all the objects at once later and remove the need for keeping track of ownership?

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

150

Should this strip leading whitespace?

266

Can bump this to 4 since we often have >2 opcodes to wip_match_opcode

672

Use structured binding to unpack?

675–682

Invert condition to early-exit if !Operand.IsDef

692

ditto

695

ditto

[Pierre-vh]

Add more comments, try to improve readability a bit.

[Pierre-vh]

In D153757#4478556, @aemerson wrote:

One problem I had with the existing combiner was that it was difficult to understand for someone unfamiliar with it. I think it would be helpful to have some more documentation in some places, for example some of the methods in CombineRuleBuilder. If we can make this code more accessible it will lower the friction for new contributors to make improvements and fixes.

Definitely agree, I've tried to add as much docs as I could think of without making it too verbose, please let me know if you think it still needs more.

I also thought about splitting this up in different files to make it more readable but I feel like the logic is so connected everywhere that it'd have the opposite effect - I'd probably end up making things more confusing/verbose by trying to over-split things. Maybe the Patterns hierarchy could go in a separate file but that's about it. It's only 200 or so lines saved.

Another useful piece of docs is a comment somewhere describing the ownership semantics. I see unique_ptr allocations and ownership transfers but it's not clear looking at the code why some pointer is being moved. On that topic, just freestyling here: would it be possible to use SpecificBumpPtrAllocator so we can just destroy all the objects at once later and remove the need for keeping track of ownership?

SpecificBumpPtrAllocator is an interesting idea, if we'd prefer that I can add it. Though in this case ownership semantics are simple: every Pattern is owned by the CombineRuleBuilder's StringMaps, unique_ptr is just used to transfer ownership and keep pointers stable. Once a pattern is moved into one of the maps, it never moves again.
I like it because it's a way to express that a pattern isn't part of the builder yet. I'll make that clearer in the documentation but please let me know if that's not enough, then I can use the SpecificBumpPtrAllocator.

I've also moved some definitions out of line to improve readability.

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

150

This object is only created through CXXPattern, which already trims all leading/trailing whitespace in the constructor. I'll document it

672

It's a struct so I'd rather avoid it in this case, it could lead to subtle issues if fields are reordered.

[aemerson]

Thanks. This LGTM. @arsenm ok with you?

[arsenm]

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h

389

typo, s/instruction/instructions

[RKSimon]

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

1392

@Pierre-vh I'm seeing build warnings due to empty switch statements:

E:\llvm\ninja\lib\Target\Mips\MipsGenPostLegalizeGICombiner.inc(249): warning C4060: switch statement contains no 'case' or 'default' labels

Please can you wrap this in a if (!ApplyCode.empty()) like you did above?

[Pierre-vh]

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

1392

Sure, apologies for the inconvenience. Will do ASAP.

[MaskRay]

The test LLVM :: TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td relies on the iteration order of StringMap, which is not guaranteed. The bug is caught by D155789.

I have fixed one bug 6de2735c2428789f99a26bee66030ddfb0841b9e, but there are more.

curl -L 'https://reviews.llvm.org/D155789?download=1' | patch -p1
cmake ... -DLLVM_ENABLE_REVERSE_ITERATION=on
ninja -C ... check-llvm-tablegen

[Pierre-vh]

In D153757#4517505, @MaskRay wrote:

The test LLVM :: TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td relies on the iteration order of StringMap, which is not guaranteed. The bug is caught by D155789.

I have fixed one bug 6de2735c2428789f99a26bee66030ddfb0841b9e, but there are more.

curl -L 'https://reviews.llvm.org/D155789?download=1' | patch -p1
cmake ... -DLLVM_ENABLE_REVERSE_ITERATION=on
ninja -C ... check-llvm-tablegen

D155821

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutor.h

public:
 
   PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
     for (auto I : Init)
       std::bitset<MaxPredicates>::set(I);
   }
 };
 
 enum {
-  GICXXPred_I64_Invalid = 0,
-  GICXXPred_APInt_Invalid = 0,
-  GICXXPred_APFloat_Invalid = 0,
-  GICXXPred_MI_Invalid = 0,
+  GICXXPred_Invalid = 0,
+  GICXXCustomAction_Invalid = 0,
 };
 
 enum {
   /// Begin a try-block to attempt a match and jump to OnFail if it is
   /// unsuccessful.
   /// - OnFail - The MatchTable entry at which to resume if the match fails.
   ///
   /// FIXME: This ought to take an argument indicating the number of try-blocks
enum {
   /// Check if this is a vector that can be treated as a vector splat
   /// constant. This is valid for both G_BUILD_VECTOR as well as
   /// G_BUILD_VECTOR_TRUNC. For AllOnes refers to individual bits, so a -1
   /// element.
   /// - InsnID - Instruction ID
   GIM_CheckIsBuildVectorAllOnes,
   GIM_CheckIsBuildVectorAllZeros,
 
+  /// Check a trivial predicate which takes no arguments.
+  /// This can be used by executors to implement custom flags that don't fit in
+  /// target features.
+  GIM_CheckSimplePredicate,
+
   /// Check a generic C++ instruction predicate
   /// - InsnID - Instruction ID
   /// - PredicateID - The ID of the predicate function to call
   GIM_CheckCxxInsnPredicate,
 
   /// Check if there's no use of the first result.
   /// - InsnID - Instruction ID
   GIM_CheckHasNoUse,
enum {
   GIR_ComplexSubOperandSubRegRenderer,
 
   /// Render operands to the specified instruction using a custom function
   /// - InsnID - Instruction ID to modify
   /// - OldInsnID - Instruction ID to get the matched operand from
   /// - RendererFnID - Custom renderer function to call
   GIR_CustomRenderer,
 
+  /// Calls a C++ function to perform an action when a match is complete.
+  /// The MatcherState is passed to the function to allow it to modify
+  /// instructions.
+  /// This is less constrained than a custom renderer and can update instructions
+  /// in the state.
+  /// - FnID - The function to call.
+  /// TODO: Remove this at some point when combiners aren't reliant on it. It's
+  /// a bit of a hack.
+  GIR_CustomAction,
+
   /// Render operands to the specified instruction using a custom function,
   /// reading from a specific operand.
   /// - InsnID - Instruction ID to modify
   /// - OldInsnID - Instruction ID to get the matched operand from
   /// - OpIdx - Operand index in OldInsnID the render function should read
   /// from..
   /// - RendererFnID - Custom renderer function to call
   GIR_CustomOperandRenderer,
llvm_unreachable(
         "Subclasses must override this with a tablegen-erated function");
   }
   virtual bool testMIPredicate_MI(unsigned, const MachineInstr &,
                                   const MatcherState &State) const {
     llvm_unreachable(
         "Subclasses must override this with a tablegen-erated function");
   }
 
+  virtual bool testSimplePredicate(unsigned) const {
+    llvm_unreachable("Subclass does not implement testSimplePredicate!");
+  }
+
+  virtual void runCustomAction(unsigned, const MatcherState &State) const {
+    llvm_unreachable("Subclass does not implement runCustomAction!");
+  }
+
   bool isOperandImmEqual(const MachineOperand &MO, int64_t Value,
                          const MachineRegisterInfo &MRI) const;
 
   /// Return true if the specified operand is a G_PTR_ADD with a G_CONSTANT on
   /// the right-hand side. GlobalISel's separation of pointer and integer types
   /// means that we don't need to worry about G_OR with equivalent semantics.
   bool isBaseWithConstantOffset(const MachineOperand &Root,
                                 const MachineRegisterInfo &MRI) const;

llvm/include/llvm/CodeGen/GlobalISel/GIMatchTableExecutorImpl.h

case GIM_CheckImmOperandPredicate: {
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs() << CurrentIdx << ": GIM_CheckImmPredicate(MIs["
                              << InsnID << "]->getOperand(" << OpIdx
                              << "), Predicate=" << Predicate << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       assert((State.MIs[InsnID]->getOperand(OpIdx).isImm() ||
               State.MIs[InsnID]->getOperand(OpIdx).isCImm()) &&
              "Expected immediate operand");
-      assert(Predicate > GICXXPred_I64_Invalid && "Expected a valid predicate");
+      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
       int64_t Value = 0;
       if (State.MIs[InsnID]->getOperand(OpIdx).isCImm())
         Value = State.MIs[InsnID]->getOperand(OpIdx).getCImm()->getSExtValue();
       else if (State.MIs[InsnID]->getOperand(OpIdx).isImm())
         Value = State.MIs[InsnID]->getOperand(OpIdx).getImm();
       else
         llvm_unreachable("Expected Imm or CImm operand");
 
       if (!testImmPredicate_I64(Predicate, Value))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
     }
     case GIM_CheckAPIntImmPredicate: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t Predicate = MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs()
                           << CurrentIdx << ": GIM_CheckAPIntImmPredicate(MIs["
                           << InsnID << "], Predicate=" << Predicate << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_CONSTANT &&
              "Expected G_CONSTANT");
-      assert(Predicate > GICXXPred_APInt_Invalid &&
+      assert(Predicate > GICXXPred_Invalid &&
              "Expected a valid predicate");
       if (!State.MIs[InsnID]->getOperand(1).isCImm())
         llvm_unreachable("Expected Imm or CImm operand");
 
       const APInt &Value =
           State.MIs[InsnID]->getOperand(1).getCImm()->getValue();
       if (!testImmPredicate_APInt(Predicate, Value))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
     }
     case GIM_CheckAPFloatImmPredicate: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t Predicate = MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs()
                           << CurrentIdx << ": GIM_CheckAPFloatImmPredicate(MIs["
                           << InsnID << "], Predicate=" << Predicate << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
       assert(State.MIs[InsnID]->getOpcode() == TargetOpcode::G_FCONSTANT &&
              "Expected G_FCONSTANT");
       assert(State.MIs[InsnID]->getOperand(1).isFPImm() &&
              "Expected FPImm operand");
-      assert(Predicate > GICXXPred_APFloat_Invalid &&
+      assert(Predicate > GICXXPred_Invalid &&
              "Expected a valid predicate");
       const APFloat &Value =
           State.MIs[InsnID]->getOperand(1).getFPImm()->getValueAPF();
 
       if (!testImmPredicate_APFloat(Predicate, Value))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
case GIM_CheckIsBuildVectorAllZeros: {
         if (!isBuildVectorAllZeros(*MI, MRI)) {
           if (handleReject() == RejectAndGiveUp)
             return false;
         }
       }
 
       break;
     }
+    case GIM_CheckSimplePredicate: {
+      // Note: we don't check for invalid here because this is purely a hook to
+      // allow some executors (such as the combiner) to check arbitrary,
+      // contextless predicates, such as whether a rule is enabled or not.
+      int64_t Predicate = MatchTable[CurrentIdx++];
+      DEBUG_WITH_TYPE(TgtExecutor::getName(),
+                      dbgs() << CurrentIdx
+                             << ": GIM_CheckSimplePredicate(Predicate="
+                             << Predicate << ")\n");
+      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
+      if (!testSimplePredicate(Predicate)) {
+        if (handleReject() == RejectAndGiveUp)
+          return false;
+      }
+      break;
+    }
     case GIM_CheckCxxInsnPredicate: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t Predicate = MatchTable[CurrentIdx++];
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs()
                           << CurrentIdx << ": GIM_CheckCxxPredicate(MIs["
                           << InsnID << "], Predicate=" << Predicate << ")\n");
       assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
-      assert(Predicate > GICXXPred_MI_Invalid && "Expected a valid predicate");
+      assert(Predicate > GICXXPred_Invalid && "Expected a valid predicate");
 
       if (!testMIPredicate_MI(Predicate, *State.MIs[InsnID], State))
         if (handleReject() == RejectAndGiveUp)
           return false;
       break;
     }
     case GIM_CheckHasNoUse: {
       int64_t InsnID = MatchTable[CurrentIdx++];
case GIR_CustomRenderer: {
                       dbgs() << CurrentIdx << ": GIR_CustomRenderer(OutMIs["
                              << InsnID << "], MIs[" << OldInsnID << "], "
                              << RendererFnID << ")\n");
       (Exec.*ExecInfo.CustomRenderers[RendererFnID])(
           OutMIs[InsnID], *State.MIs[OldInsnID],
           -1); // Not a source operand of the old instruction.
       break;
     }
+    case GIR_CustomAction: {
+      int64_t FnID = MatchTable[CurrentIdx++];
+      DEBUG_WITH_TYPE(TgtExecutor::getName(),
+                      dbgs() << CurrentIdx << ": GIR_CustomAction(FnID=" << FnID
+                             << ")\n");
+      assert(FnID > GICXXCustomAction_Invalid && "Expected a valid FnID");
+      runCustomAction(FnID, State);
+      break;
+    }
     case GIR_CustomOperandRenderer: {
       int64_t InsnID = MatchTable[CurrentIdx++];
       int64_t OldInsnID = MatchTable[CurrentIdx++];
       int64_t OpIdx = MatchTable[CurrentIdx++];
       int64_t RendererFnID = MatchTable[CurrentIdx++];
       assert(OutMIs[InsnID] && "Attempted to add to undefined instruction");
 
       DEBUG_WITH_TYPE(TgtExecutor::getName(),

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/match-table.td

+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN:     -combiners=MyCombiner %s | \
+// RUN: FileCheck %s
+
+include "llvm/Target/Target.td"
+include "llvm/Target/GlobalISel/Combine.td"
+
+def MyTargetISA : InstrInfo;
+def MyTarget : Target { let InstructionSet = MyTargetISA; }
+
+def dummy;
+
+def R0 : Register<"r0"> { let Namespace = "MyTarget"; }
+def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>;
+class I<dag OOps, dag IOps, list<dag> Pat>
+  : Instruction {
+  let Namespace = "MyTarget";
+  let OutOperandList = OOps;
+  let InOperandList = IOps;
+  let Pattern = Pat;
+}
+def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+
+def HasAnswerToEverything : Predicate<"Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42">;
+
+def WipOpcodeTest0 : GICombineRule<
+  (defs root:$d),
+  (match (wip_match_opcode TRUNC):$d),
+  (apply [{ APPLY }])>;
+
+def WipOpcodeTest1 : GICombineRule<
+  (defs root:$d),
+  (match (wip_match_opcode TRUNC, SEXT):$d),
+  (apply [{ APPLY }])>;
+
+// Note: also checks that spaces in the type name are removed.
+def reg_matchinfo : GIDefMatchData<"Register  ">;
+def InstTest0 : GICombineRule<
+  (defs root:$d, reg_matchinfo:$r0, reg_matchinfo:$r1),
+  (match (MOV $a, $b):$d),
+  (apply [{ APPLY ${r0}, ${r1} }])>;
+
+let Predicates = [HasAnswerToEverything] in
+def InstTest1 : GICombineRule<
+  (defs root:$d, reg_matchinfo:$r0),
+  (match (MOV $a, $b):$d,
+         (ZEXT $b, $c),
+         [{ return CHECK ${a}, ${b}, ${c}, ${d} }]),
+  (apply [{ APPLY }])>;
+
+def MyCombiner: GICombinerHelper<"GenMyCombiner", [
+  WipOpcodeTest0,
+  WipOpcodeTest1,
+  InstTest0,
+  InstTest1
+]>;
+
+// We have at most 2 registers used by one rule at a time, so we should only have 2 registers MDInfos.
+
+// CHECK:      struct MatchInfosTy {
+// CHECK-NEXT:   Register MDInfo0, MDInfo1;
+// CHECK-NEXT: };
+
+// Check predicates
+// CHECK:      switch (PredicateID) {
+// CHECK-NEXT: case GICXXPred_MI_Predicate_GICombiner0: {
+// CHECK-NEXT:   return CHECK State.MIs[0]->getOperand(0), State.MIs[0]->getOperand(1), State.MIs[1]->getOperand(1), State.MIs[0]
+// CHECK-NEXT: }
+
+// Verify we reset MatchData on each tryCombineAll
+// CHECK:      bool GenMyCombiner::tryCombineAll(MachineInstr &I) const {
+// CHECK-NEXT:   const TargetSubtargetInfo &ST = MF.getSubtarget();
+// CHECK-NEXT:   const PredicateBitset AvailableFeatures = getAvailableFeatures();
+// CHECK-NEXT:   NewMIVector OutMIs;
+// CHECK-NEXT:   State.MIs.clear();
+// CHECK-NEXT:   State.MIs.push_back(&I);
+// CHECK-NEXT:   MatchInfos = MatchInfosTy();
+// CHECK-EMPTY:
+// CHECK-NEXT:   if (executeMatchTable(*this, OutMIs, State, ExecInfo, getMatchTable(), *ST.getInstrInfo(), MRI, *MRI.getTargetRegisterInfo(), *ST.getRegBankInfo(), AvailableFeatures, /*CoverageInfo*/ nullptr))
+// CHECK-NEXT:     return true;
+// CHECK-NEXT:   }
+// CHECK-EMPTY:
+// CHECK-NEXT:   return false;
+// CHECK-NEXT: }
+
+
+// Verify match table.
+// CHECK:      const int64_t *GenMyCombiner::getMatchTable() const {
+// CHECK-NEXT:   constexpr static int64_t MatchTable0[] = {
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 0*/ 20,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, MyTarget::TRUNC,
+// CHECK-NEXT:       GIM_Try, /*On fail goto*//*Label 1*/ 12, // Rule ID 0 //
+// CHECK-NEXT:         GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule0Enabled,
+// CHECK-NEXT:         // Combiner Rule #0: WipOpcodeTest0; wip_match_opcode alternative 'TRUNC'
+// CHECK-NEXT:         GIR_CustomAction, GICXXCustomAction_CombineApplyGICombiner0,
+// CHECK-NEXT:         GIR_Done,
+// CHECK-NEXT:       // Label 1: @12
+// CHECK-NEXT:       GIM_Try, /*On fail goto*//*Label 2*/ 19, // Rule ID 1 //
+// CHECK-NEXT:         GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule1Enabled,
+// CHECK-NEXT:         // Combiner Rule #1: WipOpcodeTest1; wip_match_opcode alternative 'TRUNC'
+// CHECK-NEXT:         GIR_CustomAction, GICXXCustomAction_CombineApplyGICombiner0,
+// CHECK-NEXT:         GIR_Done,
+// CHECK-NEXT:       // Label 2: @19
+// CHECK-NEXT:       GIM_Reject,
+// CHECK-NEXT:     // Label 0: @20
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 3*/ 30, // Rule ID 2 //
+// CHECK-NEXT:       GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule1Enabled,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, MyTarget::SEXT,
+// CHECK-NEXT:       // Combiner Rule #1: WipOpcodeTest1; wip_match_opcode alternative 'SEXT'
+// CHECK-NEXT:       GIR_CustomAction, GICXXCustomAction_CombineApplyGICombiner0,
+// CHECK-NEXT:       GIR_Done,
+// CHECK-NEXT:     // Label 3: @30
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 4*/ 64,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, MyTarget::MOV,
+// CHECK-NEXT:       GIM_Try, /*On fail goto*//*Label 5*/ 42, // Rule ID 3 //
+// CHECK-NEXT:         GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule2Enabled,
+// CHECK-NEXT:         // MIs[0] a
+// CHECK-NEXT:         // No operand predicates
+// CHECK-NEXT:         // MIs[0] b
+// CHECK-NEXT:         // No operand predicates
+// CHECK-NEXT:         // Combiner Rule #2: InstTest0
+// CHECK-NEXT:         GIR_CustomAction, GICXXCustomAction_CombineApplyGICombiner1,
+// CHECK-NEXT:         GIR_Done,
+// CHECK-NEXT:       // Label 5: @42
+// CHECK-NEXT:       GIM_Try, /*On fail goto*//*Label 6*/ 63, // Rule ID 4 //
+// CHECK-NEXT:         GIM_CheckFeatures, GIFBS_HasAnswerToEverything,
+// CHECK-NEXT:         GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule3Enabled,
+// CHECK-NEXT:         // MIs[0] a
+// CHECK-NEXT:         // No operand predicates
+// CHECK-NEXT:         // MIs[0] b
+// CHECK-NEXT:         GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:         GIM_CheckOpcode, /*MI*/1, MyTarget::ZEXT,
+// CHECK-NEXT:         // MIs[1] c
+// CHECK-NEXT:         // No operand predicates
+// CHECK-NEXT:         GIM_CheckCxxInsnPredicate, /*MI*/0, /*FnId*/GICXXPred_MI_Predicate_GICombiner0,
+// CHECK-NEXT:         GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT:         // Combiner Rule #3: InstTest1
+// CHECK-NEXT:         GIR_CustomAction, GICXXCustomAction_CombineApplyGICombiner0,
+// CHECK-NEXT:         GIR_Done,
+// CHECK-NEXT:       // Label 6: @63
+// CHECK-NEXT:       GIM_Reject,
+// CHECK-NEXT:     // Label 4: @64
+// CHECK-NEXT:     GIM_Reject,
+// CHECK-NEXT:     };
+// CHECK-NEXT:   return MatchTable0;
+// CHECK-NEXT: }

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing-errors.td

+// RUN: not llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN:     -combiners=MyCombiner %s 2>&1| \
+// RUN: FileCheck %s -implicit-check-not=error:
+
+include "llvm/Target/Target.td"
+include "llvm/Target/GlobalISel/Combine.td"
+
+def MyTargetISA : InstrInfo;
+def MyTarget : Target { let InstructionSet = MyTargetISA; }
+
+def dummy;
+
+def R0 : Register<"r0"> { let Namespace = "MyTarget"; }
+def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>;
+class I<dag OOps, dag IOps, list<dag> Pat>
+  : Instruction {
+  let Namespace = "MyTarget";
+  let OutOperandList = OOps;
+  let InOperandList = IOps;
+  let Pattern = Pat;
+}
+def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def SUB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def MUL : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
+def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ICMP : I<(outs GPR32:$dst), (ins GPR32:$tst, GPR32:$src1, GPR32:$src2), []>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Cannot find root 'missing' in match patterns!
+def root_not_found : GICombineRule<
+  (defs root:$missing),
+  (match (MOV $a, $b):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Cannot use live-in operand 'b' as match pattern root!
+def livein_root : GICombineRule<
+  (defs root:$b),
+  (match (MOV $a, $b)),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: 'MOV' expected 2 operands, got 1
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction
+def not_enough_operands : GICombineRule<
+  (defs root:$d),
+  (match (MOV $a):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: 'MOV' expected 2 operands, got 3
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Expected a subclass of GIMatchKind or a sub-dag whose operator is either of a GIMatchKindWithArgs or Instruction
+def too_many_operands : GICombineRule<
+  (defs root:$d),
+  (match (MOV $a, $b, $c):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Operand 'd' is defined multiple times in the 'match' patterns
+def multi_defs : GICombineRule<
+  (defs root:$d),
+  (match (MOV $d, $b), (MOV $d, $x)),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Instruction pattern '__anon_pat_match_5_0' is unreachable from the pattern root!
+def unreachable_pat : GICombineRule<
+  (defs root:$d),
+  (match (MOV $a, $b):$d, (MOV $z, $k)),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error:  wip_match_opcode can not be used with instruction patterns!
+def wip_match_opcode_with_inst_pat : GICombineRule<
+  (defs root:$d),
+  (match (MOV $a, $b):$d, (wip_match_opcode SEXT)),
+  (apply [{ APPLY }])>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error:  wip_opcode_match can only be present once
+def multiple_wip_match_opcode : GICombineRule<
+  (defs root:$d),
+  (match (wip_match_opcode MOV):$d, (wip_match_opcode SEXT)),
+  (apply [{ APPLY }])>;
+
+// CHECK: error: Failed to parse one or more rules
+
+def MyCombiner: GICombinerHelper<"GenMyCombiner", [
+  root_not_found,
+  livein_root,
+  not_enough_operands,
+  too_many_operands,
+  multi_defs,
+  unreachable_pat,
+  wip_match_opcode_with_inst_pat,
+  multiple_wip_match_opcode
+]>;

llvm/test/TableGen/GlobalISelCombinerMatchTableEmitter/pattern-parsing.td

+// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner-matchtable \
+// RUN:     -gicombiner-stop-after-parse -combiners=MyCombiner %s | \
+// RUN: FileCheck %s
+
+include "llvm/Target/Target.td"
+include "llvm/Target/GlobalISel/Combine.td"
+
+def MyTargetISA : InstrInfo;
+def MyTarget : Target { let InstructionSet = MyTargetISA; }
+
+def dummy;
+
+def R0 : Register<"r0"> { let Namespace = "MyTarget"; }
+def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>;
+class I<dag OOps, dag IOps, list<dag> Pat>
+  : Instruction {
+  let Namespace = "MyTarget";
+  let OutOperandList = OOps;
+  let InOperandList = IOps;
+  let Pattern = Pat;
+}
+def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>;
+
+def HasAnswerToEverything : Predicate<"Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42">;
+def reg_matchinfo : GIDefMatchData<"Register">;
+
+// CHECK:      (CombineRule name:WipOpcodeTest0 id:0 root:d
+// CHECK-NEXT:   (MatchDatas <empty>)
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     <root>d:(AnyOpcodePattern [TRUNC])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     __anon_pat_apply_0_0:(CXXPattern apply code:"APPLY")
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable <empty>)
+// CHECK-NEXT: )
+def WipOpcodeTest0 : GICombineRule<
+  (defs root:$d),
+  (match (wip_match_opcode TRUNC):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK:     (CombineRule name:WipOpcodeTest1 id:1 root:d
+// CHECK-NEXT:   (MatchDatas <empty>)
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     <root>d:(AnyOpcodePattern [TRUNC, SEXT])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     __anon_pat_apply_1_0:(CXXPattern apply code:"APPLY")
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable <empty>)
+// CHECK-NEXT: )
+def WipOpcodeTest1 : GICombineRule<
+  (defs root:$d),
+  (match (wip_match_opcode TRUNC, SEXT):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK:     (CombineRule name:InstTest0 id:2 root:d
+// CHECK-NEXT:   (MatchDatas <empty>)
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     <root>d:(InstructionPattern inst:MOV operands:[<def>a, b])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     __anon_pat_apply_2_0:(CXXPattern apply code:"APPLY")
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable
+// CHECK-NEXT:     [a match_pat:d]
+// CHECK-NEXT:     [b live-in]
+// CHECK-NEXT:   )
+// CHECK-NEXT: )
+def InstTest0 : GICombineRule<
+  (defs root:$d),
+  (match (MOV $a, $b):$d),
+  (apply [{ APPLY }])>;
+
+// CHECK:      (CombineRule name:InstTest1 id:3 root:d
+// CHECK-NEXT:   (MatchDatas
+// CHECK-NEXT:      (MatchDataInfo pattern_symbol:r0 type:'Register' var_name:MDInfo0)
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     __anon_pat_match_3_0:(InstructionPattern inst:ZEXT operands:[<def>x, a])
+// CHECK-NEXT:     <root>d:(InstructionPattern inst:MOV operands:[<def>a, b])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     __anon_pat_apply_3_1:(CXXPattern apply code:"APPLY")
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable
+// CHECK-NEXT:     [x match_pat:__anon_pat_match_3_0]
+// CHECK-NEXT:     [a match_pat:d]
+// CHECK-NEXT:     [b live-in]
+// CHECK-NEXT:   )
+// CHECK-NEXT: )
+let Predicates = [HasAnswerToEverything] in
+def InstTest1 : GICombineRule<
+  (defs root:$d, reg_matchinfo:$r0),
+  (match (MOV $a, $b):$d,
+         (ZEXT $x, $a)),
+  (apply [{ APPLY }])>;
+
+def MyCombiner: GICombinerHelper<"GenMyCombiner", [
+  WipOpcodeTest0,
+  WipOpcodeTest1,
+  InstTest0,
+  InstTest1
+]>;

llvm/test/TableGen/GlobalISelEmitter.td

 // CHECK-NEXT:    const ExecInfoTy<PredicateBitset, ComplexMatcherMemFn, CustomRendererFn> ExecInfo;
 // CHECK-NEXT:    static MyTargetInstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];
 // CHECK-NEXT:    static MyTargetInstructionSelector::CustomRendererFn CustomRenderers[];
 // CHECK-NEXT:    bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const override;
 // CHECK-NEXT:    bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) const override;
 // CHECK-NEXT:    bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat &Imm) const override;
 // CHECK-NEXT:    const int64_t *getMatchTable() const override;
 // CHECK-NEXT:    bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI, const MatcherState &State) const override;
+// CHECK-NEXT:    bool testSimplePredicate(unsigned PredicateID) const override;
+// CHECK-NEXT:    void runCustomAction(unsigned FnID, const MatcherState &State) const override;
 // CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL
 
 // CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_INIT
 // CHECK-NEXT:    , State(3),
 // CHECK-NEXT:    ExecInfo(TypeObjects, NumTypeObjects, FeatureBitsets, ComplexPredicateFns, CustomRenderers)
 // CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT
 
 // CHECK-LABEL: // LLT Objects.

 // CHECK-NEXT:  MyTargetInstructionSelector::ComplexPredicateFns[] = {
 // CHECK-NEXT:    nullptr, // GICP_Invalid
 // CHECK-NEXT:    &MyTargetInstructionSelector::selectComplexPattern, // gi_complex
 // CHECK-NEXT:    &MyTargetInstructionSelector::selectComplexPatternRR, // gi_complex_rr
 // CHECK-NEXT:  }
 
 // CHECK-LABEL: // PatFrag predicates.
 // CHECK-NEXT:  enum {
-// CHECK-NEXT:   GICXXPred_MI_Predicate_frag = GICXXPred_MI_Invalid + 1,
+// CHECK-NEXT:   GICXXPred_MI_Predicate_frag = GICXXPred_Invalid + 1,
 // CHECK-NEXT:  };
 
 // CHECK-LABEL: // PatFrag predicates.
 // CHECK-NEXT:  enum {
-// CHECK-NEXT:    GICXXPred_I64_Predicate_cimm8 = GICXXPred_I64_Invalid + 1,
+// CHECK-NEXT:    GICXXPred_I64_Predicate_cimm8 = GICXXPred_Invalid + 1,
 // CHECK-NEXT:    GICXXPred_I64_Predicate_simm8,
 // CHECK-NEXT:  };
 
 // CHECK-NEXT: bool MyTargetInstructionSelector::testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const {
 // CHECK-NEXT:   switch (PredicateID) {
 // CHECK-NEXT:   case GICXXPred_I64_Predicate_cimm8: {
 // CHECK-NEXT:     return isInt<8>(Imm);
 // CHECK-NEXT:   }
 // CHECK-NEXT:   case GICXXPred_I64_Predicate_simm8: {
 // CHECK-NEXT:     return isInt<8>(Imm);
 // CHECK-NEXT:   }
 // CHECK-NEXT:   }
 // CHECK-NEXT:   llvm_unreachable("Unknown predicate");
 // CHECK-NEXT:   return false;
 // CHECK-NEXT: }
 
 // CHECK-LABEL: // PatFrag predicates.
 // CHECK-NEXT:  enum {
-// CHECK-NEXT:    GICXXPred_APFloat_Predicate_fpimmz = GICXXPred_APFloat_Invalid + 1,
+// CHECK-NEXT:    GICXXPred_APFloat_Predicate_fpimmz = GICXXPred_Invalid + 1,
 // CHECK-NEXT:  };
 // CHECK-NEXT:  bool MyTargetInstructionSelector::testImmPredicate_APFloat(unsigned PredicateID, const APFloat & Imm) const {
 // CHECK-NEXT:    switch (PredicateID) {
 // CHECK-NEXT:    case GICXXPred_APFloat_Predicate_fpimmz: {
 // CHECK-NEXT:      return Imm->isExactlyValue(0.0);
 // CHECK-NEXT:    }
 // CHECK-NEXT:    }
 // CHECK-NEXT:    llvm_unreachable("Unknown predicate");
 // CHECK-NEXT:    return false;
 // CHECK-NEXT:  }
 
 // CHECK-LABEL: // PatFrag predicates.
 // CHECK-NEXT:  enum {
-// CHECK-NEXT:    GICXXPred_APInt_Predicate_simm9 = GICXXPred_APInt_Invalid + 1,
+// CHECK-NEXT:    GICXXPred_APInt_Predicate_simm9 = GICXXPred_Invalid + 1,
 // CHECK-NEXT:  };
 // CHECK-NEXT:  bool MyTargetInstructionSelector::testImmPredicate_APInt(unsigned PredicateID, const APInt & Imm) const {
 // CHECK-NEXT:    switch (PredicateID) {
 // CHECK-NEXT:    case GICXXPred_APInt_Predicate_simm9: {
 // CHECK-NEXT:      return isInt<9>(Imm->getSExtValue());
 // CHECK-NEXT:    }
 // CHECK-NEXT:    }
 // CHECK-NEXT:    llvm_unreachable("Unknown predicate");
 // CHECK-NEXT:    return false;
 // CHECK-NEXT:  }
 
 // CHECK-LABEL: // Custom renderers.
 // CHECK-NEXT: enum {
 // CHECK-NEXT:   GICR_Invalid,
 // CHECK-NEXT:   GICR_renderImm,
 // CHECK-NEXT: };
 // CHECK-NEXT: MyTargetInstructionSelector::CustomRendererFn
 // CHECK-NEXT: MyTargetInstructionSelector::CustomRenderers[] = {
 // CHECK-NEXT:   nullptr, // GICR_Invalid
 // CHECK-NEXT:   &MyTargetInstructionSelector::renderImm,
 // CHECK-NEXT: };
 
 // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage &CoverageInfo) const {
-// CHECK-NEXT: MachineRegisterInfo &MRI = MF->getRegInfo();
 // CHECK-NEXT: const PredicateBitset AvailableFeatures = getAvailableFeatures();
 // CHECK-NEXT: NewMIVector OutMIs;
 // CHECK-NEXT: State.MIs.clear();
 // CHECK-NEXT: State.MIs.push_back(&I);
 
-// CHECK:      if (executeMatchTable(*this, OutMIs, State, ExecInfo, getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures, &CoverageInfo)) {
+// CHECK:      if (executeMatchTable(*this, OutMIs, State, ExecInfo, getMatchTable(), TII, MF->getRegInfo(), TRI, RBI, AvailableFeatures, &CoverageInfo)) {
 // CHECK-NEXT:   return true;
 // CHECK-NEXT: }
 
 // CHECK: const int64_t *
 // CHECK-LABEL: MyTargetInstructionSelector::getMatchTable() const {
 // CHECK-NEXT: MatchTable0[] = {
 
 //===- Test a pattern with multiple ComplexPatterns in multiple instrs ----===//

llvm/test/TableGen/GlobalISelEmitterCustomPredicate.td

 // RUN: llvm-tblgen %s -gen-global-isel -optimize-match-table=false -I %p/../../include -I %p/Common -o - | FileCheck %s
 
 // Verify that all MI predicates are enumerated.
 //
 // CHECK: // PatFrag predicates.
 // CHECK-NEXT: enum {
-// CHECK-NEXT:   GICXXPred_MI_Predicate_and_or_pat = GICXXPred_MI_Invalid + 1,
+// CHECK-NEXT:   GICXXPred_MI_Predicate_and_or_pat = GICXXPred_Invalid + 1,
 // CHECK-NEXT:   GICXXPred_MI_Predicate_or_oneuse,
 // CHECK-NEXT:   GICXXPred_MI_Predicate_patfrags_test_pat,
 // CHECK-NEXT:   GICXXPred_MI_Predicate_sub3_pat,
 // CHECK-NEXT: };
 
 // Verify that we emit cases for all MI predicates.
 //
 // CHECK: bool MyTargetInstructionSelector::testMIPredicate_MI(

llvm/utils/TableGen/CMakeLists.txt

add_tablegen(llvm-tblgen LLVM
   DecoderEmitter.cpp
   DFAEmitter.cpp
   DFAPacketizerEmitter.cpp
   DisassemblerEmitter.cpp
   DXILEmitter.cpp
   ExegesisEmitter.cpp
   FastISelEmitter.cpp
   GICombinerEmitter.cpp
+  GlobalISelCombinerMatchTableEmitter.cpp
   GlobalISelEmitter.cpp
   GlobalISelMatchTable.cpp
   GlobalISelMatchTableExecutorEmitter.cpp
   InfoByHwMode.cpp
   InstrInfoEmitter.cpp
   InstrDocsEmitter.cpp
   OptEmitter.cpp
   OptParserEmitter.cpp

llvm/utils/TableGen/GICombinerEmitter.cpp

 //===- GlobalCombinerEmitter.cpp - Generate a combiner --------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file Generate a combiner implementation for GlobalISel from a declarative
 /// syntax
 ///
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenTarget.h"
 #include "GlobalISel/CodeExpander.h"
 #include "GlobalISel/CodeExpansions.h"
+#include "GlobalISel/CombinerUtils.h"
 #include "GlobalISel/GIMatchDag.h"
 #include "GlobalISel/GIMatchDagEdge.h"
 #include "GlobalISel/GIMatchDagInstr.h"
 #include "GlobalISel/GIMatchDagOperands.h"
 #include "GlobalISel/GIMatchDagPredicate.h"
 #include "GlobalISel/GIMatchTree.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"

 #define DEBUG_TYPE "gicombiner-emitter"
 
 // FIXME: Use ALWAYS_ENABLED_STATISTIC once it's available.
 unsigned NumPatternTotal = 0;
 STATISTIC(NumPatternTotalStatistic, "Total number of patterns");
 
 cl::OptionCategory
     GICombinerEmitterCat("Options for -gen-global-isel-combiner");
-static cl::list<std::string>
+cl::list<std::string>
     SelectedCombiners("combiners", cl::desc("Emit the specified combiners"),
                       cl::cat(GICombinerEmitterCat), cl::CommaSeparated);
 static cl::opt<bool> ShowExpansions(
     "gicombiner-show-expansions",
     cl::desc("Use C++ comments to indicate occurence of code expansion"),
     cl::cat(GICombinerEmitterCat));
-static cl::opt<bool> StopAfterParse(
+cl::opt<bool> StopAfterParse(
     "gicombiner-stop-after-parse",
     cl::desc("Stop processing after parsing rules and dump state"),
     cl::cat(GICombinerEmitterCat));
 static cl::opt<bool> StopAfterBuild(
     "gicombiner-stop-after-build",
     cl::desc("Stop processing after building the match tree"),
     cl::cat(GICombinerEmitterCat));
 
while (!EdgesRemaining.empty()) {
         LLVM_DEBUG(dbgs() << "No progress\n");
         return;
       }
       Progressed = false;
     }
   }
 };
 
-/// A convenience function to check that an Init refers to a specific def. This
-/// is primarily useful for testing for defs and similar in DagInit's since
-/// DagInit's support any type inside them.
-static bool isSpecificDef(const Init &N, StringRef Def) {
-  if (const DefInit *OpI = dyn_cast<DefInit>(&N))
-    if (OpI->getDef()->getName() == Def)
-      return true;
-  return false;
-}
-
-/// A convenience function to check that an Init refers to a def that is a
-/// subclass of the given class and coerce it to a def if it is. This is
-/// primarily useful for testing for subclasses of GIMatchKind and similar in
-/// DagInit's since DagInit's support any type inside them.
-static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
-  if (const DefInit *OpI = dyn_cast<DefInit>(&N))
-    if (OpI->getDef()->isSubClassOf(Cls))
-      return OpI->getDef();
-  return nullptr;
-}
-
-/// A convenience function to check that an Init refers to a dag whose operator
-/// is a specific def and coerce it to a dag if it is. This is primarily useful
-/// for testing for subclasses of GIMatchKind and similar in DagInit's since
-/// DagInit's support any type inside them.
-static const DagInit *getDagWithSpecificOperator(const Init &N,
-                                                 StringRef Name) {
-  if (const DagInit *I = dyn_cast<DagInit>(&N))
-    if (I->getNumArgs() > 0)
-      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
-        if (OpI->getDef()->getName() == Name)
-          return I;
-  return nullptr;
-}
-
-/// A convenience function to check that an Init refers to a dag whose operator
-/// is a def that is a subclass of the given class and coerce it to a dag if it
-/// is. This is primarily useful for testing for subclasses of GIMatchKind and
-/// similar in DagInit's since DagInit's support any type inside them.
-static const DagInit *getDagWithOperatorOfSubClass(const Init &N,
-                                                   StringRef Cls) {
-  if (const DagInit *I = dyn_cast<DagInit>(&N))
-    if (I->getNumArgs() > 0)
-      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
-        if (OpI->getDef()->isSubClassOf(Cls))
-          return I;
-  return nullptr;
-}
-
 StringRef makeNameForAnonInstr(CombineRule &Rule) {
   return insertStrTab(to_string(
       format("__anon%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
 }
 
 StringRef makeDebugName(CombineRule &Rule, StringRef Name) {
   return insertStrTab(Name.empty() ? makeNameForAnonInstr(Rule) : StringRef(Name));
 }

llvm/utils/TableGen/GlobalISel/CombinerUtils.h

+//===- CombinerUtils.h ----------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file Utility functions used by both Combiner backends.
+/// TODO: Can remove when MatchDAG-based backend is removed.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_COMBINERUTILS_H
+#define LLVM_UTILS_TABLEGEN_COMBINERUTILS_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/TableGen/Record.h"
+
+namespace llvm {
+
+/// A convenience function to check that an Init refers to a specific def. This
+/// is primarily useful for testing for defs and similar in DagInit's since
+/// DagInit's support any type inside them.
+inline bool isSpecificDef(const Init &N, StringRef Def) {
+  if (const DefInit *OpI = dyn_cast<DefInit>(&N))
+    if (OpI->getDef()->getName() == Def)
+      return true;
+  return false;
+}
+
+/// A convenience function to check that an Init refers to a def that is a
+/// subclass of the given class and coerce it to a def if it is. This is
+/// primarily useful for testing for subclasses of GIMatchKind and similar in
+/// DagInit's since DagInit's support any type inside them.
+inline Record *getDefOfSubClass(const Init &N, StringRef Cls) {
+  if (const DefInit *OpI = dyn_cast<DefInit>(&N))
+    if (OpI->getDef()->isSubClassOf(Cls))
+      return OpI->getDef();
+  return nullptr;
+}
+
+/// A convenience function to check that an Init refers to a dag whose operator
+/// is a specific def and coerce it to a dag if it is. This is primarily useful
+/// for testing for subclasses of GIMatchKind and similar in DagInit's since
+/// DagInit's support any type inside them.
+inline const DagInit *getDagWithSpecificOperator(const Init &N,
+                                                 StringRef Name) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->getName() == Name)
+          return I;
+  return nullptr;
+}
+
+/// A convenience function to check that an Init refers to a dag whose operator
+/// is a def that is a subclass of the given class and coerce it to a dag if it
+/// is. This is primarily useful for testing for subclasses of GIMatchKind and
+/// similar in DagInit's since DagInit's support any type inside them.
+inline const DagInit *getDagWithOperatorOfSubClass(const Init &N,
+                                                   StringRef Cls) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->isSubClassOf(Cls))
+          return I;
+  return nullptr;
+}
+} // namespace llvm
+
+#endif

llvm/utils/TableGen/GlobalISelCombinerMatchTableEmitter.cpp

+//===- GlobalISelCombinerMatchTableEmitter.cpp - --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file Generate a combiner implementation for GlobalISel from a declarative
+/// syntax using GlobalISelMatchTable.
+///
+//===----------------------------------------------------------------------===//
+
+#include "CodeGenInstruction.h"
+#include "CodeGenTarget.h"
+#include "GlobalISel/CodeExpander.h"
+#include "GlobalISel/CodeExpansions.h"
+#include "GlobalISel/CombinerUtils.h"
+#include "GlobalISelMatchTable.h"
+#include "GlobalISelMatchTableExecutorEmitter.h"
+#include "SubtargetFeatureInfo.h"
+#include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/StringMatcher.h"
+#include "llvm/TableGen/TableGenBackend.h"
+#include <cstdint>
+
+using namespace llvm;
+using namespace llvm::gi;
+
+#define DEBUG_TYPE "gicombiner-matchtable-emitter"
+
+extern cl::list<std::string> SelectedCombiners;
+extern cl::opt<bool> StopAfterParse;
+
+namespace {
+constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply";
+constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";
+
+std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {
+  return "GICXXPred_Simple_IsRule" + to_string(CombinerRuleID) + "Enabled";
+}
+
+void declareInstExpansion(CodeExpansions &CE, const InstructionMatcher &IM,
+                          StringRef Name) {
+  CE.declare(Name, "State.MIs[" + to_string(IM.getInsnVarID()) + "]");
+}
+
+void declareOperandExpansion(CodeExpansions &CE, const OperandMatcher &OM,
+                             StringRef Name) {
+  CE.declare(Name, "State.MIs[" + to_string(OM.getInsnVarID()) +
+                       "]->getOperand(" + to_string(OM.getOpIdx()) + ")");
+}
+
+//===- MatchData Handling -------------------------------------------------===//
+
+/// Represents MatchData defined by the match stage and required by the apply
+/// stage.
+///
+/// This allows the plumbing of arbitrary data from C++ predicates between the
+/// stages.
+///
+/// When this class is initially created, it only has a pattern symbol and a
+/// type. When all of the MatchDatas declarations of a given pattern have been
+/// parsed, `AssignVariables` must be called to assign storage variable names to
+/// each MatchDataInfo.
+class MatchDataInfo {
+  StringRef PatternSymbol;
+  StringRef Type;
+  std::string VarName;
+
+public:
+  static constexpr StringLiteral StructTypeName = "MatchInfosTy";
+  static constexpr StringLiteral StructName = "MatchInfos";
+
+  MatchDataInfo(StringRef PatternSymbol, StringRef Type)
+      : PatternSymbol(PatternSymbol), Type(Type.trim()) {}
+
+  StringRef getPatternSymbol() const { return PatternSymbol; };
+  StringRef getType() const { return Type; };
+
+  bool hasVariableName() const { return !VarName.empty(); }
+  void setVariableName(StringRef Name) { VarName = Name; }
+  StringRef getVariableName() const;
+
+  std::string getQualifiedVariableName() const {
+    return StructName.str() + "." + getVariableName().str();
+  }
+
+  void print(raw_ostream &OS) const;
+  void dump() const { print(dbgs()); }
+};
+
+StringRef MatchDataInfo::getVariableName() const {
+  assert(hasVariableName());
+  return VarName;
+}
+
+void MatchDataInfo::print(raw_ostream &OS) const {
+  OS << "(MatchDataInfo pattern_symbol:" << PatternSymbol << " type:'" << Type
+     << "' var_name:" << (VarName.empty() ? "<unassigned>" : VarName) << ")";
+}
+
+/// Pool of type -> variables used to emit MatchData variables declarations.
+///
+/// e.g. if the map contains "int64_t" -> ["MD0", "MD1"], then two variable
+/// declarations must be emitted: `int64_t MD0` and `int64_t MD1`.
+///
+/// This has a static lifetime and will outlive all the `MatchDataInfo` objects
+/// by design. It needs to persist after all `CombineRuleBuilder` objects died
+/// so we can emit the variable declarations.
+StringMap<std::vector<std::string>> AllMatchDataVars;
+
+// Assign variable names to all MatchDatas used by a pattern. This must be
+// called after all MatchData decls have been parsed inside a rule.
+//
+// Requires an array of MatchDataInfo so we can handle cases where a pattern
+// uses multiple instances of the same MatchData type.
+void AssignMatchDataVariables(MutableArrayRef<MatchDataInfo> Infos) {
+  static unsigned NextVarID = 0;
+
+  StringMap<unsigned> SeenTypes;
+  for (auto &I : Infos) {
+    unsigned &NumSeen = SeenTypes[I.getType()];
+    auto &ExistingVars = AllMatchDataVars[I.getType()];
+
+    if (NumSeen == ExistingVars.size())
+      ExistingVars.push_back("MDInfo" + to_string(NextVarID++));
+
+    I.setVariableName(ExistingVars[NumSeen++]);
+  }
+}
+
+//===- C++ Predicates Handling --------------------------------------------===//
+
+/// Entry into the static pool of all CXX Predicate code. This contains the
+/// fully expanded C++ code.
+///
+/// Each CXXPattern creates a new entry in the pool to store its data, even
+/// after the pattern is destroyed.
+///
+/// Note that CXXPattern trims C++ code, so the Code is already expected to be
+/// free of leading/trailing whitespace.
+struct CXXPredicateCode {
+  CXXPredicateCode(std::string Code, unsigned ID)
+      : Code(Code), ID(ID), BaseEnumName("GICombiner" + to_string(ID)) {
+    assert(StringRef(Code).trim() == Code &&
+           "Code was expected to be trimmed!");
+  }
+
+  const std::string Code;
+  const unsigned ID;
+  const std::string BaseEnumName;
+
+  bool needsUnreachable() const {
+    return !StringRef(Code).starts_with("return");
+  }
+
+  std::string getEnumNameWithPrefix(StringRef Prefix) const {
+    return Prefix.str() + BaseEnumName;
+  }
+};
+
+using CXXPredicateCodePool =
+    DenseMap<hash_code, std::unique_ptr<CXXPredicateCode>>;
+CXXPredicateCodePool AllCXXMatchCode;
+CXXPredicateCodePool AllCXXApplyCode;
+
+/// Gets an instance of `CXXPredicateCode` for \p Code, or returns an already
+/// existing one.
+const CXXPredicateCode &getOrInsert(CXXPredicateCodePool &Pool,
+                                    std::string Code) {
+  // Check if we already have an identical piece of code, if not, create an
+  // entry in the pool.
+  const auto CodeHash = hash_value(Code);
+  if (auto It = Pool.find(CodeHash); It != Pool.end())
+    return *It->second;
+
+  const auto ID = Pool.size();
+  auto OwnedData = std::make_unique<CXXPredicateCode>(std::move(Code), ID);
+  const auto &DataRef = *OwnedData;
+  Pool[CodeHash] = std::move(OwnedData);
+  return DataRef;
+}
+
+/// Sorts a `CXXPredicateCodePool` by their IDs and returns it.
+std::vector<const CXXPredicateCode *>
+getSorted(const CXXPredicateCodePool &Pool) {
+  std::vector<const CXXPredicateCode *> Out;
+  std::transform(Pool.begin(), Pool.end(), std::back_inserter(Out),
+                 [&](auto &Elt) { return Elt.second.get(); });
+  sort(Out, [](const auto *A, const auto *B) { return A->ID < B->ID; });
+  return Out;
+}
+
+//===- Pattern Base Class -------------------------------------------------===//
+
+// An abstract pattern found in a combine rule. This can be an apply or match
+// pattern.
+class Pattern {
+public:
+  enum {
+    K_AnyOpcode,
+    K_Inst,
+    K_CXX,
+  };
+
+  virtual ~Pattern() = default;
+
+  unsigned getKind() const { return Kind; }
+  const char *getKindName() const;
+
+  bool hasName() const { return !Name.empty(); }
+  StringRef getName() const { return Name; }
+
+  virtual void print(raw_ostream &OS, bool PrintName = true) const = 0;
+  void dump() const { return print(dbgs()); }
+
+protected:
+  Pattern(unsigned Kind, StringRef Name) : Kind(Kind), Name(Name.str()) {
+    assert(!Name.empty() && "unnamed pattern!");
+  }
+
+  void printImpl(raw_ostream &OS, bool PrintName,
+                 function_ref<void()> ContentPrinter) const;
+
+private:
+  unsigned Kind;
+  std::string Name;
+};
+
+const char *Pattern::getKindName() const {
+  switch (Kind) {
+  case K_AnyOpcode:
+    return "AnyOpcodePattern";
+  case K_Inst:
+    return "InstructionPattern";
+  case K_CXX:
+    return "CXXPattern";
+  }
+
+  llvm_unreachable("unknown pattern kind!");
+}
+
+void Pattern::printImpl(raw_ostream &OS, bool PrintName,
+                        function_ref<void()> ContentPrinter) const {
+  OS << "(" << getKindName() << " ";
+  if (PrintName)
+    OS << "name:" << getName() << " ";
+  ContentPrinter();
+  OS << ")";
+}
+
+//===- AnyOpcodePattern ---------------------------------------------------===//
+
+/// `wip_match_opcode` patterns.
+/// This matches one or more opcodes, and does not check any operands
+/// whatsoever.
+class AnyOpcodePattern : public Pattern {
+public:
+  AnyOpcodePattern(StringRef Name) : Pattern(K_AnyOpcode, Name) {}
+
+  static bool classof(const Pattern *P) { return P->getKind() == K_AnyOpcode; }
+
+  void addOpcode(const CodeGenInstruction *I) { Insts.push_back(I); }
+  const auto &insts() const { return Insts; }
+
+  void print(raw_ostream &OS, bool PrintName = true) const override;
+
+private:
+  SmallVector<const CodeGenInstruction *, 4> Insts;
+};
+
+void AnyOpcodePattern::print(raw_ostream &OS, bool PrintName) const {
+  printImpl(OS, PrintName, [&OS, this]() {
+    OS << "["
+       << join(map_range(Insts,
+                         [](const auto *I) { return I->TheDef->getName(); }),
+               ", ")
+       << "]";
+  });
+}
+
+//===- InstructionPattern -------------------------------------------------===//
+
+/// Matches an instruction, e.g. `G_ADD $x, $y, $z`.
+///
+/// This pattern is simply CodeGenInstruction + a list of operands.
+class InstructionPattern : public Pattern {
+public:
+  struct Operand {
+    std::string Name;
+    bool IsDef = false;
+  };
+
+  InstructionPattern(const CodeGenInstruction &I, StringRef Name)
+      : Pattern(K_Inst, Name), I(I) {}
+
+  static bool classof(const Pattern *P) { return P->getKind() == K_Inst; }
+
+  const auto &operands() const { return Operands; }
+  void addOperand(StringRef Name);
+  unsigned getNumDefs() const { return I.Operands.NumDefs; }
+
+  const CodeGenInstruction &getInst() const { return I; }
+  StringRef getInstName() const { return I.TheDef->getName(); }
+
+  void reportUnreachable(ArrayRef<SMLoc> Locs) const;
+  bool checkSemantics(ArrayRef<SMLoc> Loc) const;
+
+  void print(raw_ostream &OS, bool PrintName = true) const override;
+
+private:
+  const CodeGenInstruction &I;
+  SmallVector<Operand, 4> Operands;
+};
+
+void InstructionPattern::addOperand(StringRef Name) {
+  const bool IsDef = Operands.size() < getNumDefs();
+  Operands.emplace_back(Operand{Name.str(), IsDef});
+}
+
+void InstructionPattern::reportUnreachable(ArrayRef<SMLoc> Locs) const {
+  PrintError(Locs, "Instruction pattern '" + getName() +
+                       "' is unreachable from the pattern root!");
+}
+
+bool InstructionPattern::checkSemantics(ArrayRef<SMLoc> Loc) const {
+  unsigned NumExpectedOperands = I.Operands.size();
+  if (NumExpectedOperands != Operands.size()) {
+
+    PrintError(Loc, "'" + getInstName() + "' expected " +
+                        Twine(NumExpectedOperands) + " operands, got " +
+                        Twine(Operands.size()));
+    return false;
+  }
+  return true;
+}
+
+void InstructionPattern::print(raw_ostream &OS, bool PrintName) const {
+  printImpl(OS, PrintName, [&OS, this]() {
+    OS << "inst:" << I.TheDef->getName() << " operands:["
+       << join(map_range(Operands,
+                         [](const auto &O) {
+                           return (O.IsDef ? "<def>" : "") + O.Name;
+                         }),
+               ", ")
+       << "]";
+  });
+}
+
+//===- CXXPattern ---------------------------------------------------------===//
+
+/// Raw C++ code which may need some expansions.
+///
+///   e.g. [{ return isFooBux(${src}.getReg()); }]
+///
+/// For the expanded code, \see CXXPredicateCode. CXXPredicateCode objects are
+/// created through `expandCode`.
+///
+/// \see CodeExpander and \see CodeExpansions for more information on code
+/// expansions.
+///
+/// This object has two purposes:
+///   - Represent C++ code as a pattern entry.
+///   - Be a factory for expanded C++ code.
+///     - It's immutable and only holds the raw code so we can expand the same
+///       CXX pattern multiple times if we need to.
+///
+/// Note that the code is always trimmed in the constructor, so leading and
+/// trailing whitespaces are removed. This removes bloat in the output, avoids
+/// formatting issues, but also allows us to check things like
+/// `.startswith("return")` trivially without worrying about spaces.
+class CXXPattern : public Pattern {
+public:
+  CXXPattern(const StringInit &Code, StringRef Name, bool IsApply)
+      : CXXPattern(Code.getAsUnquotedString(), Name, IsApply) {}
+
+  CXXPattern(StringRef Code, StringRef Name, bool IsApply)
+      : Pattern(K_CXX, Name), IsApply(IsApply), RawCode(Code.trim().str()) {}
+
+  static bool classof(const Pattern *P) { return P->getKind() == K_CXX; }
+
+  bool isApply() const { return IsApply; }
+  StringRef getRawCode() const { return RawCode; }
+
+  /// Expands raw code, replacing things such as `${foo}` with their
+  /// substitution in \p CE.
+  ///
+  /// \param CE     Map of Code Expansions
+  /// \param Locs   SMLocs for the Code Expander, in case it needs to emit
+  ///               diagnostics.
+  /// \return A CXXPredicateCode object that contains the expanded code. Note
+  /// that this may or may not insert a new object. All CXXPredicateCode objects
+  /// are held in a set to avoid emitting duplicate C++ code.
+  const CXXPredicateCode &expandCode(const CodeExpansions &CE,
+                                     ArrayRef<SMLoc> Locs) const;
+
+  void print(raw_ostream &OS, bool PrintName = true) const override;
+
+private:
+  bool IsApply;
+  std::string RawCode;
+};
+
+const CXXPredicateCode &CXXPattern::expandCode(const CodeExpansions &CE,
+                                               ArrayRef<SMLoc> Locs) const {
+  std::string Result;
+  raw_string_ostream OS(Result);
+  CodeExpander Expander(RawCode, CE, Locs, /*ShowExpansions*/ false);
+  Expander.emit(OS);
+  return getOrInsert(IsApply ? AllCXXApplyCode : AllCXXMatchCode,
+                     std::move(Result));
+}
+
+void CXXPattern::print(raw_ostream &OS, bool PrintName) const {
+  printImpl(OS, PrintName, [&OS, this] {
+    OS << (IsApply ? "apply" : "match") << " code:\"";
+    printEscapedString(getRawCode(), OS);
+    OS << "\"";
+  });
+}
+
+//===- CombineRuleBuilder -------------------------------------------------===//
+
+/// Helper for CombineRuleBuilder.
+///
+/// Represents information about an operand.
+/// Operands with no MatchPat are considered live-in to the pattern.
+struct OperandTableEntry {
+  // The matcher pattern that defines this operand.
+  // null for live-ins.
+  InstructionPattern *MatchPat = nullptr;
+  // The apply pattern that (re)defines this operand.
+  // This can only be non-null if MatchPat is.
+  InstructionPattern *ApplyPat = nullptr;
+
+  bool isLiveIn() const { return !MatchPat; }
+};
+
+/// Parses combine rule and builds a small intermediate representation to tie
+/// patterns together and emit RuleMatchers to match them. This may emit more
+/// than one RuleMatcher, e.g. for `wip_match_opcode`.
+///
+/// Memory management for `Pattern` objects is done through `std::unique_ptr`.
+/// In most cases, there are two stages to a pattern's lifetime:
+///   - Creation in a `parse` function
+///     - The unique_ptr is stored in a variable, and may be destroyed if the
+///       pattern is found to be semantically invalid.
+///   - Ownership transfer into a `PatternStringMap`
+///     - Once a pattern is moved into either the map of Match or Apply
+///       patterns, it is known to be valid and it never moves back.
+class CombineRuleBuilder {
+public:
+  using PatternStringMap = StringMap<std::unique_ptr<Pattern>>;
+
+  CombineRuleBuilder(const CodeGenTarget &CGT,
+                     SubtargetFeatureInfoMap &SubtargetFeatures,
+                     Record &RuleDef, unsigned ID,
+                     std::vector<RuleMatcher> &OutRMs)
+      : CGT(CGT), SubtargetFeatures(SubtargetFeatures), RuleDef(RuleDef),
+        RuleID(ID), OutRMs(OutRMs) {}
+
+  /// Parses all fields in the RuleDef record.
+  bool parseAll();
+
+  /// Emits all RuleMatchers into the vector of RuleMatchers passed in the
+  /// constructor.
+  bool emitRuleMatchers();
+
+  void print(raw_ostream &OS) const;
+  void dump() const { print(dbgs()); }
+
+  /// Debug-only verification of invariants.
+  void verify() const;
+
+private:
+  void PrintError(Twine Msg) const { ::PrintError(RuleDef.getLoc(), Msg); }
+
+  /// Adds the expansions from \see MatchDatas to \p CE.
+  void declareAllMatchDatasExpansions(CodeExpansions &CE) const;
+
+  /// Adds \p P to \p IM, expanding its code using \p CE.
+  void addCXXPredicate(InstructionMatcher &IM, const CodeExpansions &CE,
+                       const CXXPattern &P);
+
+  /// Generates a name for anonymous patterns.
+  ///
+  /// e.g. (G_ADD $x, $y, $z):$foo is a pattern named "foo", but if ":$foo" is
+  /// absent, then the pattern is anonymous and this is used to assign it a
+  /// name.
+  std::string makeAnonPatName(StringRef Prefix) const;
+  mutable unsigned AnonIDCnt = 0;
+
+  /// Creates a new RuleMatcher with some boilerplate
+  /// settings/actions/predicates, and and adds it to \p OutRMs.
+  /// \see addFeaturePredicates too.
+  ///
+  /// \param AdditionalComment Comment string to be added to the
+  ///        `DebugCommentAction`.
+  RuleMatcher &addRuleMatcher(Twine AdditionalComment = "");
+  bool addFeaturePredicates(RuleMatcher &M);
+
+  bool findRoots();
+  bool buildOperandsTable();
+
+  bool parseDefs(DagInit &Def);
+  bool parseMatch(DagInit &Match);
+  bool parseApply(DagInit &Apply);
+
+  std::unique_ptr<Pattern> parseInstructionMatcher(const Init &Arg,
+                                                   StringRef PatName);
+  std::unique_ptr<Pattern> parseWipMatchOpcodeMatcher(const Init &Arg,
+                                                      StringRef PatName);
+
+  bool emitMatchPattern(CodeExpansions &CE, const InstructionPattern &IP);
+  bool emitMatchPattern(CodeExpansions &CE, const AnyOpcodePattern &AOP);
+
+  bool emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M);
+
+  // Recursively visits InstructionPattern from P to build up the
+  // RuleMatcher/InstructionMatcher. May create new InstructionMatchers as
+  // needed.
+  bool emitInstructionMatchPattern(CodeExpansions &CE, RuleMatcher &M,
+                                   InstructionMatcher &IM,
+                                   const InstructionPattern &P,
+                                   DenseSet<const Pattern *> &SeenPats);
+
+  const CodeGenTarget &CGT;
+  SubtargetFeatureInfoMap &SubtargetFeatures;
+  Record &RuleDef;
+  const unsigned RuleID;
+  std::vector<RuleMatcher> &OutRMs;
+
+  // For InstructionMatcher::addOperand
+  unsigned AllocatedTemporariesBaseID = 0;
+
+  /// The root of the pattern.
+  StringRef RootName;
+
+  /// These maps have ownership of the actual Pattern objects.
+  /// They both map a Pattern's name to the Pattern instance.
+  PatternStringMap MatchPats;
+  PatternStringMap ApplyPats;
+
+  /// Set by findRoots.
+  Pattern *MatchRoot = nullptr;
+
+  StringMap<OperandTableEntry> OperandTable;
+  SmallVector<MatchDataInfo, 2> MatchDatas;
+};
+
+bool CombineRuleBuilder::parseAll() {
+  if (!parseDefs(*RuleDef.getValueAsDag("Defs")))
+    return false;
+  if (!parseMatch(*RuleDef.getValueAsDag("Match")))
+    return false;
+  if (!parseApply(*RuleDef.getValueAsDag("Apply")))
+    return false;
+  if (!buildOperandsTable())
+    return false;
+  if (!findRoots())
+    return false;
+  LLVM_DEBUG(verify());
+  return true;
+}
+
+bool CombineRuleBuilder::emitRuleMatchers() {
+  assert(MatchRoot);
+  CodeExpansions CE;
+  declareAllMatchDatasExpansions(CE);
+
+  switch (MatchRoot->getKind()) {
+  case Pattern::K_AnyOpcode: {
+    if (!emitMatchPattern(CE, *cast<AnyOpcodePattern>(MatchRoot)))
+      return false;
+    break;
+  }
+  case Pattern::K_Inst:
+    if (!emitMatchPattern(CE, *cast<InstructionPattern>(MatchRoot)))
+      return false;
+    break;
+  case Pattern::K_CXX:
+    PrintError("C++ code cannot be the root of a pattern!");
+    return false;
+  default:
+    llvm_unreachable("unknown pattern kind!");
+  }
+
+  return true;
+}
+
+void CombineRuleBuilder::print(raw_ostream &OS) const {
+  OS << "(CombineRule name:" << RuleDef.getName() << " id:" << RuleID
+     << " root:" << RootName << "\n";
+
+  OS << "  (MatchDatas ";
+  if (MatchDatas.empty())
+    OS << "<empty>)\n";
+  else {
+    OS << "\n";
+    for (const auto &MD : MatchDatas) {
+      OS << "    ";
+      MD.print(OS);
+      OS << "\n";
+    }
+    OS << "  )\n";
+  }
+
+  const auto DumpPats = [&](StringRef Name, const PatternStringMap &Pats) {
+    OS << "  (" << Name << " ";
+    if (Pats.empty()) {
+      OS << "<empty>)\n";
+      return;
+    }
+
+    OS << "\n";
+    for (const auto &P : Pats) {
+      OS << "    ";
+      if (P.getValue().get() == MatchRoot)
+        OS << "<root>";
+      OS << P.getKey() << ":";
+      P.getValue()->print(OS, /*PrintName=*/false);
+      OS << "\n";
+    }
+    OS << "  )\n";
+  };
+
+  DumpPats("MatchPats", MatchPats);
+  DumpPats("ApplyPats", ApplyPats);
+
+  OS << "  (OperandTable ";
+  if (OperandTable.empty())
+    OS << "<empty>)\n";
+  else {
+    OS << "\n";
+    for (const auto &Entry : OperandTable) {
+      OS << "    [" << Entry.getKey();
+      auto &Val = Entry.getValue();
+      if (const auto *P = Val.MatchPat)
+        OS << " match_pat:" << P->getName();
+      if (const auto *P = Val.ApplyPat)
+        OS << " apply_pat:" << P->getName();
+      if (Val.isLiveIn())
+        OS << " live-in";
+      OS << "]\n";
+    }
+    OS << "  )\n";
+  }
+
+  OS << ")\n";
+}
+
+void CombineRuleBuilder::verify() const {
+  const auto VerifyPats = [&](const PatternStringMap &Pats) {
+    for (const auto &Entry : Pats) {
+      if (!Entry.getValue())
+        PrintFatalError("null pattern in pattern map!");
+
+      if (Entry.getKey() != Entry.getValue()->getName()) {
+        Entry.getValue()->dump();
+        PrintFatalError("Pattern name mismatch! Map name: " + Entry.getKey() +
+                        ", Pat name: " + Entry.getValue()->getName());
+      }
+    }
+  };
+
+  VerifyPats(MatchPats);
+  VerifyPats(ApplyPats);
+
+  for (const auto &[Name, Op] : OperandTable) {
+    if (Op.ApplyPat && !Op.MatchPat) {
+      dump();
+      PrintFatalError("Operand " + Name +
+                      " has an apply pattern, but no match pattern!");
+    }
+  }
+}
+
+bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {
+  if (!RuleDef.getValue("Predicates"))
+    return true;
+
+  ListInit *Preds = RuleDef.getValueAsListInit("Predicates");
+  for (Init *I : Preds->getValues()) {
+    if (DefInit *Pred = dyn_cast<DefInit>(I)) {
+      Record *Def = Pred->getDef();
+      if (!Def->isSubClassOf("Predicate")) {
+        ::PrintError(Def->getLoc(), "Unknown 'Predicate' Type");
+        return false;
+      }
+
+      if (Def->getValueAsString("CondString").empty())
+        continue;
+
+      if (SubtargetFeatures.count(Def) == 0) {
+        SubtargetFeatures.emplace(
+            Def, SubtargetFeatureInfo(Def, SubtargetFeatures.size()));
+      }
+
+      M.addRequiredFeature(Def);
+    }
+  }
+
+  return true;
+}
+
+void CombineRuleBuilder::declareAllMatchDatasExpansions(
+    CodeExpansions &CE) const {
+  for (const auto &MD : MatchDatas)
+    CE.declare(MD.getPatternSymbol(), MD.getQualifiedVariableName());
+}
+
+void CombineRuleBuilder::addCXXPredicate(InstructionMatcher &IM,
+                                         const CodeExpansions &CE,
+                                         const CXXPattern &P) {
+  const auto &ExpandedCode = P.expandCode(CE, RuleDef.getLoc());
+  IM.addPredicate<GenericInstructionPredicateMatcher>(
+      ExpandedCode.getEnumNameWithPrefix(CXXPredPrefix));
+}
+
+std::string CombineRuleBuilder::makeAnonPatName(StringRef Prefix) const {
+  return to_string("__anon_pat_" + Prefix + "_" + to_string(RuleID) + "_" +
+                   to_string(AnonIDCnt++));
+}
+
+RuleMatcher &CombineRuleBuilder::addRuleMatcher(Twine AdditionalComment) {
+  auto &RM = OutRMs.emplace_back(RuleDef.getLoc());
+  addFeaturePredicates(RM);
+  RM.addRequiredSimplePredicate(getIsEnabledPredicateEnumName(RuleID));
+  const std::string AdditionalCommentStr = AdditionalComment.str();
+  RM.addAction<DebugCommentAction>(
+      "Combiner Rule #" + to_string(RuleID) + ": " + RuleDef.getName().str() +
+      (AdditionalCommentStr.empty() ? "" : "; " + AdditionalCommentStr));
+  return RM;
+}
+
+bool CombineRuleBuilder::findRoots() {
+  // Look by pattern name, e.g.
+  //    (G_FNEG $x, $y):$root
+  if (auto It = MatchPats.find(RootName); It != MatchPats.end()) {
+    MatchRoot = MatchPats[RootName].get();
+    return true;
+  }
+
+  // Look by def:
+  //    (G_FNEG $root, $y)
+  auto It = OperandTable.find(RootName);
+  if (It == OperandTable.end()) {
+    PrintError("Cannot find root '" + RootName + "' in match patterns!");
+    return false;
+  }
+
+  if (!It->second.MatchPat) {
+    PrintError("Cannot use live-in operand '" + RootName +
+               "' as match pattern root!");
+    return false;
+  }
+
+  MatchRoot = It->second.MatchPat;
+  return true;
+}
+
+bool CombineRuleBuilder::buildOperandsTable() {
+  // Walk each instruction pattern
+  for (auto &P : MatchPats) {
+    auto *IP = dyn_cast<InstructionPattern>(P.getValue().get());
+    if (!IP)
+      continue;
+    for (const auto &Operand : IP->operands()) {
+      // Create an entry, no matter if it's a use or a def.
+      auto &Entry = OperandTable[Operand.Name];
+
+      // We only need to do additional checking on defs, though.
+      if (!Operand.IsDef)
+        continue;
+
+      if (Entry.MatchPat) {
+        PrintError("Operand '" + Operand.Name +
+                   "' is defined multiple times in the 'match' patterns");
+        return false;
+      }
+      Entry.MatchPat = IP;
+    }
+  }
+
+  for (auto &P : ApplyPats) {
+    auto *IP = dyn_cast<InstructionPattern>(P.getValue().get());
+    if (!IP)
+      continue;
+    for (const auto &Operand : IP->operands()) {
+      // Create an entry, no matter if it's a use or a def.
+      auto &Entry = OperandTable[Operand.Name];
+
+      // We only need to do additional checking on defs, though.
+      if (!Operand.IsDef)
+        continue;
+
+      if (!Entry.MatchPat) {
+        PrintError("Cannot define live-in operand '" + Operand.Name +
+                   "' in the 'apply' pattern");
+        return false;
+      }
+      if (Entry.ApplyPat) {
+        PrintError("Operand '" + Operand.Name +
+                   "' is defined multiple times in the 'apply' patterns");
+        return false;
+      }
+      Entry.ApplyPat = IP;
+    }
+  }
+
+  return true;
+}
+
+bool CombineRuleBuilder::parseDefs(DagInit &Def) {
+  if (Def.getOperatorAsDef(RuleDef.getLoc())->getName() != "defs") {
+    PrintError("Expected defs operator");
+    return false;
+  }
+
+  SmallVector<StringRef> Roots;
+  for (unsigned I = 0, E = Def.getNumArgs(); I < E; ++I) {
+    if (isSpecificDef(*Def.getArg(I), "root")) {
+      Roots.emplace_back(Def.getArgNameStr(I));
+      continue;
+    }
+
+    // Subclasses of GIDefMatchData should declare that this rule needs to pass
+    // data from the match stage to the apply stage, and ensure that the
+    // generated matcher has a suitable variable for it to do so.
+    if (Record *MatchDataRec =
+            getDefOfSubClass(*Def.getArg(I), "GIDefMatchData")) {
+      MatchDatas.emplace_back(Def.getArgNameStr(I),
+                              MatchDataRec->getValueAsString("Type"));
+      continue;
+    }
+
+    // Otherwise emit an appropriate error message.
+    if (getDefOfSubClass(*Def.getArg(I), "GIDefKind"))
+      PrintError("This GIDefKind not implemented in tablegen");
+    else if (getDefOfSubClass(*Def.getArg(I), "GIDefKindWithArgs"))
+      PrintError("This GIDefKindWithArgs not implemented in tablegen");
+    else
+      PrintError("Expected a subclass of GIDefKind or a sub-dag whose "
+                 "operator is of type GIDefKindWithArgs");
+    return false;
+  }
+
+  if (Roots.size() != 1) {
+    PrintError("Combine rules must have exactly one root");
+    return false;
+  }
+
+  RootName = Roots.front();
+
+  // Assign variables to all MatchDatas.
+  AssignMatchDataVariables(MatchDatas);
+  return true;
+}
+
+bool CombineRuleBuilder::parseMatch(DagInit &Match) {
+  if (Match.getOperatorAsDef(RuleDef.getLoc())->getName() != "match") {
+    PrintError("Expected match operator");
+    return false;
+  }
+
+  if (Match.getNumArgs() == 0) {
+    PrintError("Matcher is empty");
+    return false;
+  }
+
+  // The match section consists of a list of matchers and predicates. Parse each
+  // one and add the equivalent GIMatchDag nodes, predicates, and edges.
+  bool HasOpcodeMatcher = false;
+  for (unsigned I = 0; I < Match.getNumArgs(); ++I) {
+    Init *Arg = Match.getArg(I);
+    std::string Name = Match.getArgName(I)
+                           ? Match.getArgName(I)->getValue().str()
+                           : makeAnonPatName("match");
+
+    if (MatchPats.contains(Name)) {
+      PrintError("'" + Name + "' match pattern defined more than once!");
+      return false;
+    }
+
+    if (auto Pat = parseInstructionMatcher(*Arg, Name)) {
+      MatchPats[Pat->getName()] = std::move(Pat);
+      continue;
+    }
+
+    if (auto Pat = parseWipMatchOpcodeMatcher(*Arg, Name)) {
+      if (HasOpcodeMatcher) {
+        PrintError("wip_opcode_match can only be present once");
+        return false;
+      }
+      HasOpcodeMatcher = true;
+      MatchPats[Pat->getName()] = std::move(Pat);
+      continue;
+    }
+
+    // Parse arbitrary C++ code
+    if (const auto *StringI = dyn_cast<StringInit>(Arg)) {
+      auto CXXPat =
+          std::make_unique<CXXPattern>(*StringI, Name, /*IsApply*/ false);
+      if (!CXXPat->getRawCode().contains("return ")) {
+        PrintWarning(RuleDef.getLoc(),
+                     "'match' C++ code does not seem to return!");
+      }
+      MatchPats[Name] = std::move(CXXPat);
+      continue;
+    }
+
+    // TODO: don't print this on, e.g. bad operand count in inst pat
+    PrintError("Expected a subclass of GIMatchKind or a sub-dag whose "
+               "operator is either of a GIMatchKindWithArgs or Instruction");
+    PrintNote("Pattern was `" + Arg->getAsString() + "'");
+    return false;
+  }
+
+  return true;
+}
+
+bool CombineRuleBuilder::parseApply(DagInit &Apply) {
+  // Currently we only support C++ :(
+  if (Apply.getOperatorAsDef(RuleDef.getLoc())->getName() != "apply") {
+    PrintError("Expected 'apply' operator in Apply DAG");
+    return false;
+  }
+
+  if (Apply.getNumArgs() != 1) {
+    PrintError("Expected exactly 1 argument in 'apply'");
+    return false;
+  }
+
+  const StringInit *Code = dyn_cast<StringInit>(Apply.getArg(0));
+  const auto PatName = makeAnonPatName("apply");
+  ApplyPats[PatName] =
+      std::make_unique<CXXPattern>(*Code, PatName, /*IsApply*/ true);
+  return true;
+}
+
+std::unique_ptr<Pattern>
+CombineRuleBuilder::parseInstructionMatcher(const Init &Arg, StringRef Name) {
+  const DagInit *Matcher = getDagWithOperatorOfSubClass(Arg, "Instruction");
+  if (!Matcher)
+    return nullptr;
+
+  auto &Instr = CGT.getInstruction(Matcher->getOperatorAsDef(RuleDef.getLoc()));
+  auto Pat = std::make_unique<InstructionPattern>(Instr, Name);
+
+  for (const auto &NameInit : Matcher->getArgNames())
+    Pat->addOperand(NameInit->getAsUnquotedString());
+
+  if (!Pat->checkSemantics(RuleDef.getLoc()))
+    return nullptr;
+
+  return std::move(Pat);
+}
+
+std::unique_ptr<Pattern>
+CombineRuleBuilder::parseWipMatchOpcodeMatcher(const Init &Arg,
+                                               StringRef Name) {
+  const DagInit *Matcher = getDagWithSpecificOperator(Arg, "wip_match_opcode");
+  if (!Matcher)
+    return nullptr;
+
+  if (Matcher->getNumArgs() == 0) {
+    PrintError("Empty wip_match_opcode");
+    return nullptr;
+  }
+
+  // Each argument is an opcode that can match.
+  auto Result = std::make_unique<AnyOpcodePattern>(Name);
+  for (const auto &Arg : Matcher->getArgs()) {
+    Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");
+    if (OpcodeDef) {
+      Result->addOpcode(&CGT.getInstruction(OpcodeDef));
+      continue;
+    }
+
+    PrintError("Arguments to wip_match_opcode must be instructions");
+    return nullptr;
+  }
+
+  return std::move(Result);
+}
+
+bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
+                                          const InstructionPattern &IP) {
+  auto &M = addRuleMatcher();
+  InstructionMatcher &IM = M.addInstructionMatcher("root");
+  declareInstExpansion(CE, IM, IP.getName());
+
+  DenseSet<const Pattern *> SeenPats;
+  if (!emitInstructionMatchPattern(CE, M, IM, IP, SeenPats))
+    return false;
+
+  // Emit remaining patterns
+  for (auto &Entry : MatchPats) {
+    Pattern *CurPat = Entry.getValue().get();
+    if (SeenPats.contains(CurPat))
+      continue;
+
+    switch (CurPat->getKind()) {
+    case Pattern::K_AnyOpcode:
+      PrintError("wip_match_opcode can not be used with instruction patterns!");
+      return false;
+    case Pattern::K_Inst:
+      cast<InstructionPattern>(CurPat)->reportUnreachable(RuleDef.getLoc());
+      return false;
+    case Pattern::K_CXX: {
+      addCXXPredicate(IM, CE, *cast<CXXPattern>(CurPat));
+      continue;
+    }
+    default:
+      llvm_unreachable("unknown pattern kind!");
+    }
+  }
+
+  return emitApplyPatterns(CE, M);
+}
+
+bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
+                                          const AnyOpcodePattern &AOP) {
+
+  for (const CodeGenInstruction *CGI : AOP.insts()) {
+    auto &M = addRuleMatcher("wip_match_opcode alternative '" +
+                             CGI->TheDef->getName() + "'");
+
+    InstructionMatcher &IM = M.addInstructionMatcher(AOP.getName());
+    declareInstExpansion(CE, IM, AOP.getName());
+    // declareInstExpansion needs to be identical, otherwise we need to create a
+    // CodeExpansions object here instead.
+    assert(IM.getInsnVarID() == 0);
+
+    IM.addPredicate<InstructionOpcodeMatcher>(CGI);
+
+    // Emit remaining patterns.
+    for (auto &Entry : MatchPats) {
+      Pattern *CurPat = Entry.getValue().get();
+      if (CurPat == &AOP)
+        continue;
+
+      switch (CurPat->getKind()) {
+      case Pattern::K_AnyOpcode:
+        PrintError("wip_match_opcode can only be present once!");
+        return false;
+      case Pattern::K_Inst:
+        cast<InstructionPattern>(CurPat)->reportUnreachable(RuleDef.getLoc());
+        return false;
+      case Pattern::K_CXX: {
+        addCXXPredicate(IM, CE, *cast<CXXPattern>(CurPat));
+        break;
+      }
+      default:
+        llvm_unreachable("unknown pattern kind!");
+      }
+    }
+
+    if (!emitApplyPatterns(CE, M))
+      return false;
+  }
+
+  return true;
+}
+
+bool CombineRuleBuilder::emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M) {
+  for (auto &Entry : ApplyPats) {
+    Pattern *CurPat = Entry.getValue().get();
+    switch (CurPat->getKind()) {
+    case Pattern::K_AnyOpcode:
+    case Pattern::K_Inst:
+      llvm_unreachable("Unsupported pattern kind in output pattern!");
+    case Pattern::K_CXX: {
+      CXXPattern *CXXPat = cast<CXXPattern>(CurPat);
+      const auto &ExpandedCode = CXXPat->expandCode(CE, RuleDef.getLoc());
+      M.addAction<CustomCXXAction>(
+          ExpandedCode.getEnumNameWithPrefix(CXXApplyPrefix));
+      continue;
+    }
+    default:
+      llvm_unreachable("Unknown pattern kind!");
+    }
+  }
+
+  return true;
+}
+
+bool CombineRuleBuilder::emitInstructionMatchPattern(
+    CodeExpansions &CE, RuleMatcher &M, InstructionMatcher &IM,
+    const InstructionPattern &P, DenseSet<const Pattern *> &SeenPats) {
+  if (SeenPats.contains(&P))
+    return true;
+
+  SeenPats.insert(&P);
+
+  IM.addPredicate<InstructionOpcodeMatcher>(&P.getInst());
+  declareInstExpansion(CE, IM, P.getName());
+
+  unsigned OpIdx = 0;
+  for (auto &O : P.operands()) {
+    auto &OpTableEntry = OperandTable.at(O.Name);
+
+    OperandMatcher &OM =
+        IM.addOperand(OpIdx++, O.Name, AllocatedTemporariesBaseID++);
+    declareOperandExpansion(CE, OM, O.Name);
+
+    if (O.IsDef)
+      continue;
+
+    if (InstructionPattern *DefPat = OpTableEntry.MatchPat) {
+      auto InstOpM = OM.addPredicate<InstructionOperandMatcher>(M, O.Name);
+      if (!InstOpM) {
+        // TODO: copy-pasted from GlobalISelEmitter.cpp. Is it still relevant
+        // here?
+        PrintError("Nested instruction '" + DefPat->getName() +
+                   "' cannot be the same as another operand '" + O.Name + "'");
+        return false;
+      }
+
+      if (!emitInstructionMatchPattern(CE, M, (*InstOpM)->getInsnMatcher(),
+                                       *DefPat, SeenPats))
+        return false;
+    }
+  }
+
+  return true;
+}
+
+//===- GICombinerEmitter --------------------------------------------------===//
+
+/// This class is essentially the driver. It fetches all TableGen records, calls
+/// CombineRuleBuilder to build the MatchTable's RuleMatchers, then creates the
+/// MatchTable & emits it. It also handles emitting all the supporting code such
+/// as the list of LLTs, the CXXPredicates, etc.
+class GICombinerEmitter final : public GlobalISelMatchTableExecutorEmitter {
+  RecordKeeper &Records;
+  StringRef Name;
+  const CodeGenTarget &Target;
+  Record *Combiner;
+  unsigned NextRuleID = 0;
+
+  // List all combine rules (ID, name) imported.
+  // Note that the combiner rule ID is different from the RuleMatcher ID. The
+  // latter is internal to the MatchTable, the former is the canonical ID of the
+  // combine rule used to disable/enable it.
+  std::vector<std::pair<unsigned, std::string>> AllCombineRules;
+
+  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules);
+
+  void emitRuleConfigImpl(raw_ostream &OS);
+
+  void emitAdditionalImpl(raw_ostream &OS) override;
+
+  void emitMIPredicateFns(raw_ostream &OS) override;
+  void emitI64ImmPredicateFns(raw_ostream &OS) override;
+  void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
+  void emitAPIntImmPredicateFns(raw_ostream &OS) override;
+  void emitTestSimplePredicate(raw_ostream &OS) override;
+  void emitRunCustomAction(raw_ostream &OS) override;
+
+  void emitAdditionalTemporariesDecl(raw_ostream &OS,
+                                     StringRef Indent) override;
+
+  const CodeGenTarget &getTarget() const override { return Target; }
+  StringRef getClassName() const override {
+    return Combiner->getValueAsString("Classname");
+  }
+
+  std::string getRuleConfigClassName() const {
+    return getClassName().str() + "RuleConfig";
+  }
+
+  void gatherRules(std::vector<RuleMatcher> &Rules,
+                   const std::vector<Record *> &&RulesAndGroups);
+
+public:
+  explicit GICombinerEmitter(RecordKeeper &RK, const CodeGenTarget &Target,
+                             StringRef Name, Record *Combiner);
+  ~GICombinerEmitter() {}
+
+  void run(raw_ostream &OS);
+};
+
+void GICombinerEmitter::emitRuleConfigImpl(raw_ostream &OS) {
+  OS << "struct " << getRuleConfigClassName() << " {\n"
+     << "  SparseBitVector<> DisabledRules;\n\n"
+     << "  bool isRuleEnabled(unsigned RuleID) const;\n"
+     << "  bool parseCommandLineOption();\n"
+     << "  bool setRuleEnabled(StringRef RuleIdentifier);\n"
+     << "  bool setRuleDisabled(StringRef RuleIdentifier);\n"
+     << "};\n\n";
+
+  std::vector<std::pair<std::string, std::string>> Cases;
+  Cases.reserve(AllCombineRules.size());
+
+  for (const auto &[ID, Name] : AllCombineRules)
+    Cases.emplace_back(Name, "return " + to_string(ID) + ";\n");
+
+  OS << "static std::optional<uint64_t> getRuleIdxForIdentifier(StringRef "
+        "RuleIdentifier) {\n"
+     << "  uint64_t I;\n"
+     << "  // getAtInteger(...) returns false on success\n"
+     << "  bool Parsed = !RuleIdentifier.getAsInteger(0, I);\n"
+     << "  if (Parsed)\n"
+     << "    return I;\n\n"
+     << "#ifndef NDEBUG\n";
+  StringMatcher Matcher("RuleIdentifier", Cases, OS);
+  Matcher.Emit();
+  OS << "#endif // ifndef NDEBUG\n\n"
+     << "  return std::nullopt;\n"
+     << "}\n";
+
+  OS << "static std::optional<std::pair<uint64_t, uint64_t>> "
+        "getRuleRangeForIdentifier(StringRef RuleIdentifier) {\n"
+     << "  std::pair<StringRef, StringRef> RangePair = "
+        "RuleIdentifier.split('-');\n"
+     << "  if (!RangePair.second.empty()) {\n"
+     << "    const auto First = "
+        "getRuleIdxForIdentifier(RangePair.first);\n"
+     << "    const auto Last = "
+        "getRuleIdxForIdentifier(RangePair.second);\n"
+     << "    if (!First || !Last)\n"
+     << "      return std::nullopt;\n"
+     << "    if (First >= Last)\n"
+     << "      report_fatal_error(\"Beginning of range should be before "
+        "end of range\");\n"
+     << "    return {{*First, *Last + 1}};\n"
+     << "  }\n"
+     << "  if (RangePair.first == \"*\") {\n"
+     << "    return {{0, " << AllCombineRules.size() << "}};\n"
+     << "  }\n"
+     << "  const auto I = getRuleIdxForIdentifier(RangePair.first);\n"
+     << "  if (!I)\n"
+     << "    return std::nullopt;\n"
+     << "  return {{*I, *I + 1}};\n"
+     << "}\n\n";
+
+  for (bool Enabled : {true, false}) {
+    OS << "bool " << getRuleConfigClassName() << "::setRule"
+       << (Enabled ? "Enabled" : "Disabled") << "(StringRef RuleIdentifier) {\n"
+       << "  auto MaybeRange = getRuleRangeForIdentifier(RuleIdentifier);\n"
+       << "  if (!MaybeRange)\n"
+       << "    return false;\n"
+       << "  for (auto I = MaybeRange->first; I < MaybeRange->second; ++I)\n"
+       << "    DisabledRules." << (Enabled ? "reset" : "set") << "(I);\n"
+       << "  return true;\n"
+       << "}\n\n";
+  }
+
+  OS << "static std::vector<std::string> " << Name << "Option;\n"
+     << "static cl::list<std::string> " << Name << "DisableOption(\n"
+     << "    \"" << Name.lower() << "-disable-rule\",\n"
+     << "    cl::desc(\"Disable one or more combiner rules temporarily in "
+     << "the " << Name << " pass\"),\n"
+     << "    cl::CommaSeparated,\n"
+     << "    cl::Hidden,\n"
+     << "    cl::cat(GICombinerOptionCategory),\n"
+     << "    cl::callback([](const std::string &Str) {\n"
+     << "      " << Name << "Option.push_back(Str);\n"
+     << "    }));\n"
+     << "static cl::list<std::string> " << Name << "OnlyEnableOption(\n"
+     << "    \"" << Name.lower() << "-only-enable-rule\",\n"
+     << "    cl::desc(\"Disable all rules in the " << Name
+     << " pass then re-enable the specified ones\"),\n"
+     << "    cl::Hidden,\n"
+     << "    cl::cat(GICombinerOptionCategory),\n"
+     << "    cl::callback([](const std::string &CommaSeparatedArg) {\n"
+     << "      StringRef Str = CommaSeparatedArg;\n"
+     << "      " << Name << "Option.push_back(\"*\");\n"
+     << "      do {\n"
+     << "        auto X = Str.split(\",\");\n"
+     << "        " << Name << "Option.push_back((\"!\" + X.first).str());\n"
+     << "        Str = X.second;\n"
+     << "      } while (!Str.empty());\n"
+     << "    }));\n"
+     << "\n\n"
+     << "bool " << getRuleConfigClassName()
+     << "::isRuleEnabled(unsigned RuleID) const {\n"
+     << "    return  !DisabledRules.test(RuleID);\n"
+     << "}\n"
+     << "bool " << getRuleConfigClassName() << "::parseCommandLineOption() {\n"
+     << "  for (StringRef Identifier : " << Name << "Option) {\n"
+     << "    bool Enabled = Identifier.consume_front(\"!\");\n"
+     << "    if (Enabled && !setRuleEnabled(Identifier))\n"
+     << "      return false;\n"
+     << "    if (!Enabled && !setRuleDisabled(Identifier))\n"
+     << "      return false;\n"
+     << "  }\n"
+     << "  return true;\n"
+     << "}\n\n";
+}
+
+void GICombinerEmitter::emitAdditionalImpl(raw_ostream &OS) {
+  OS << "bool " << getClassName()
+     << "::tryCombineAll(MachineInstr &I) const {\n"
+     << "  const TargetSubtargetInfo &ST = MF.getSubtarget();\n"
+     << "  const PredicateBitset AvailableFeatures = "
+        "getAvailableFeatures();\n"
+     << "  NewMIVector OutMIs;\n"
+     << "  State.MIs.clear();\n"
+     << "  State.MIs.push_back(&I);\n"
+     << "  " << MatchDataInfo::StructName << " = "
+     << MatchDataInfo::StructTypeName << "();\n\n"
+     << "  if (executeMatchTable(*this, OutMIs, State, ExecInfo"
+     << ", getMatchTable(), *ST.getInstrInfo(), MRI, "
+        "*MRI.getTargetRegisterInfo(), *ST.getRegBankInfo(), AvailableFeatures"
+     << ", /*CoverageInfo*/ nullptr)) {\n"
+     << "    return true;\n"
+     << "  }\n\n"
+     << "  return false;\n"
+     << "}\n\n";
+}
+
+void GICombinerEmitter::emitMIPredicateFns(raw_ostream &OS) {
+  auto MatchCode = getSorted(AllCXXMatchCode);
+  emitMIPredicateFnsImpl<const CXXPredicateCode *>(
+      OS, "", ArrayRef<const CXXPredicateCode *>(MatchCode),
+      [](const CXXPredicateCode *C) -> StringRef { return C->BaseEnumName; },
+      [](const CXXPredicateCode *C) -> StringRef { return C->Code; });
+}
+
+void GICombinerEmitter::emitI64ImmPredicateFns(raw_ostream &OS) {
+  // Unused, but still needs to be called.
+  emitImmPredicateFnsImpl<unsigned>(
+      OS, "I64", "int64_t", {}, [](unsigned) { return ""; },
+      [](unsigned) { return ""; });
+}
+
+void GICombinerEmitter::emitAPFloatImmPredicateFns(raw_ostream &OS) {
+  // Unused, but still needs to be called.
+  emitImmPredicateFnsImpl<unsigned>(
+      OS, "APFloat", "const APFloat &", {}, [](unsigned) { return ""; },
+      [](unsigned) { return ""; });
+}
+
+void GICombinerEmitter::emitAPIntImmPredicateFns(raw_ostream &OS) {
+  // Unused, but still needs to be called.
+  emitImmPredicateFnsImpl<unsigned>(
+      OS, "APInt", "const APInt &", {}, [](unsigned) { return ""; },
+      [](unsigned) { return ""; });
+}
+
+void GICombinerEmitter::emitTestSimplePredicate(raw_ostream &OS) {
+  if (!AllCombineRules.empty()) {
+    OS << "enum {\n";
+    std::string EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";
+    // To avoid emitting a switch, we expect that all those rules are in order.
+    // That way we can just get the RuleID from the enum by subtracting
+    // (GICXXPred_Invalid + 1).
+    unsigned ExpectedID = 0;
+    for (const auto &[ID, _] : AllCombineRules) {
+      assert(ExpectedID++ == ID && "combine rules are not ordered!");
+      OS << "  " << getIsEnabledPredicateEnumName(ID) << EnumeratorSeparator;
+      EnumeratorSeparator = ",\n";
+    }
+    OS << "};\n\n";
+  }
+
+  OS << "bool " << getClassName()
+     << "::testSimplePredicate(unsigned Predicate) const {\n"
+     << "    return RuleConfig.isRuleEnabled(Predicate - "
+        "GICXXPred_Invalid - "
+        "1);\n"
+     << "}\n";
+}
+
+void GICombinerEmitter::emitRunCustomAction(raw_ostream &OS) {
+  const auto ApplyCode = getSorted(AllCXXApplyCode);
+
+  if (!ApplyCode.empty()) {
+    OS << "enum {\n";
+    std::string EnumeratorSeparator = " = GICXXCustomAction_Invalid + 1,\n";
+    for (const auto &Apply : ApplyCode) {
+      OS << "  " << Apply->getEnumNameWithPrefix(CXXApplyPrefix)
+         << EnumeratorSeparator;
+      EnumeratorSeparator = ",\n";
+    }
+    OS << "};\n";
+  }
+
+  OS << "void " << getClassName()
+     << "::runCustomAction(unsigned ApplyID, const MatcherState &State) const "
+        "{\n"
+     << "  switch(ApplyID) {\n";
+  for (const auto &Apply : ApplyCode) {
+    OS << "  case " << Apply->getEnumNameWithPrefix(CXXApplyPrefix) << ":{\n"
+       << "    " << Apply->Code << "\n"
+       << "    return;\n";
+    OS << "  }\n";
+  }
+  OS << "}\n"
+     << "  llvm_unreachable(\"Unknown Apply Action\");\n"
+     << "}\n";
+}
+
+void GICombinerEmitter::emitAdditionalTemporariesDecl(raw_ostream &OS,
+                                                      StringRef Indent) {
+  OS << Indent << "struct " << MatchDataInfo::StructTypeName << " {\n";
+  for (const auto &[Type, VarNames] : AllMatchDataVars) {
+    assert(!VarNames.empty() && "Cannot have no vars for this type!");
+    OS << Indent << "  " << Type << " " << join(VarNames, ", ") << ";\n";
+  }
+  OS << Indent << "};\n"
+     << Indent << "mutable " << MatchDataInfo::StructTypeName << " "
+     << MatchDataInfo::StructName << ";\n\n";
+}
+
+GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK,
+                                     const CodeGenTarget &Target,
+                                     StringRef Name, Record *Combiner)
+    : Records(RK), Name(Name), Target(Target), Combiner(Combiner) {}
+
+MatchTable
+GICombinerEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules) {
+  std::vector<Matcher *> InputRules;
+  for (Matcher &Rule : Rules)
+    InputRules.push_back(&Rule);
+
+  unsigned CurrentOrdering = 0;
+  StringMap<unsigned> OpcodeOrder;
+  for (RuleMatcher &Rule : Rules) {
+    const StringRef Opcode = Rule.getOpcode();
+    assert(!Opcode.empty() && "Didn't expect an undefined opcode");
+    if (OpcodeOrder.count(Opcode) == 0)
+      OpcodeOrder[Opcode] = CurrentOrdering++;
+  }
+
+  llvm::stable_sort(InputRules, [&OpcodeOrder](const Matcher *A,
+                                               const Matcher *B) {
+    auto *L = static_cast<const RuleMatcher *>(A);
+    auto *R = static_cast<const RuleMatcher *>(B);
+    return std::make_tuple(OpcodeOrder[L->getOpcode()], L->getNumOperands()) <
+           std::make_tuple(OpcodeOrder[R->getOpcode()], R->getNumOperands());
+  });
+
+  for (Matcher *Rule : InputRules)
+    Rule->optimize();
+
+  std::vector<std::unique_ptr<Matcher>> MatcherStorage;
+  std::vector<Matcher *> OptRules =
+      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
+
+  for (Matcher *Rule : OptRules)
+    Rule->optimize();
+
+  OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage);
+
+  return MatchTable::buildTable(OptRules, /*WithCoverage*/ false,
+                                /*IsCombiner*/ true);
+}
+
+/// Recurse into GICombineGroup's and flatten the ruleset into a simple list.
+void GICombinerEmitter::gatherRules(
+    std::vector<RuleMatcher> &ActiveRules,
+    const std::vector<Record *> &&RulesAndGroups) {
+  for (Record *R : RulesAndGroups) {
+    if (R->isValueUnset("Rules")) {
+      AllCombineRules.emplace_back(NextRuleID, R->getName().str());
+      CombineRuleBuilder CRB(Target, SubtargetFeatures, *R, NextRuleID++,
+                             ActiveRules);
+
+      if (!CRB.parseAll())
+        continue;
+
+      if (StopAfterParse) {
+        CRB.print(outs());
+        continue;
+      }
+
+      if (!CRB.emitRuleMatchers())
+        continue;
+    } else
+      gatherRules(ActiveRules, R->getValueAsListOfDefs("Rules"));
+  }
+}
+
+void GICombinerEmitter::run(raw_ostream &OS) {
+  Records.startTimer("Gather rules");
+  std::vector<RuleMatcher> Rules;
+  gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
+  if (ErrorsPrinted)
+    PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");
+
+  Records.startTimer("Creating Match Table");
+  unsigned MaxTemporaries = 0;
+  for (const auto &Rule : Rules)
+    MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
+
+  const MatchTable Table = buildMatchTable(Rules);
+
+  Records.startTimer("Emit combiner");
+
+  emitSourceFileHeader(getClassName().str() + " Combiner Match Table", OS);
+
+  // Unused
+  std::vector<StringRef> CustomRendererFns;
+  // Unused, but hack to avoid empty declarator
+  std::vector<LLTCodeGen> TypeObjects = {LLTCodeGen(LLT::scalar(1))};
+  // Unused
+  std::vector<Record *> ComplexPredicates;
+
+  // GET_GICOMBINER_DEPS, which pulls in extra dependencies.
+  OS << "#ifdef GET_GICOMBINER_DEPS\n"
+     << "#include \"llvm/ADT/SparseBitVector.h\"\n"
+     << "namespace llvm {\n"
+     << "extern cl::OptionCategory GICombinerOptionCategory;\n"
+     << "} // end namespace llvm\n"
+     << "#endif // ifdef GET_GICOMBINER_DEPS\n\n";
+
+  // GET_GICOMBINER_TYPES, which needs to be included before the declaration of
+  // the class.
+  OS << "#ifdef GET_GICOMBINER_TYPES\n";
+  emitRuleConfigImpl(OS);
+  OS << "#endif // ifdef GET_GICOMBINER_TYPES\n\n";
+  emitPredicateBitset(OS, "GET_GICOMBINER_TYPES");
+
+  // GET_GICOMBINER_CLASS_MEMBERS, which need to be included inside the class.
+  emitPredicatesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");
+  emitTemporariesDecl(OS, "GET_GICOMBINER_CLASS_MEMBERS");
+
+  // GET_GICOMBINER_IMPL, which needs to be included outside the class.
+  emitExecutorImpl(OS, Table, TypeObjects, Rules, ComplexPredicates,
+                   CustomRendererFns, "GET_GICOMBINER_IMPL");
+
+  // GET_GICOMBINER_CONSTRUCTOR_INITS, which are in the constructor's
+  // initializer list.
+  emitPredicatesInit(OS, "GET_GICOMBINER_CONSTRUCTOR_INITS");
+  emitTemporariesInit(OS, MaxTemporaries, "GET_GICOMBINER_CONSTRUCTOR_INITS");
+}
+
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
+
+static void EmitGICombiner(RecordKeeper &RK, raw_ostream &OS) {
+  CodeGenTarget Target(RK);
+
+  if (SelectedCombiners.empty())
+    PrintFatalError("No combiners selected with -combiners");
+  for (const auto &Combiner : SelectedCombiners) {
+    Record *CombinerDef = RK.getDef(Combiner);
+    if (!CombinerDef)
+      PrintFatalError("Could not find " + Combiner);
+    GICombinerEmitter(RK, Target, Combiner, CombinerDef).run(OS);
+  }
+}
+
+static TableGen::Emitter::Opt X("gen-global-isel-combiner-matchtable",
+                                EmitGICombiner,
+                                "Generate GlobalISel combiner Match Table");

llvm/utils/TableGen/GlobalISelEmitter.cpp

public:
   explicit GlobalISelEmitter(RecordKeeper &RK);
 
   void emitAdditionalImpl(raw_ostream &OS) override;
 
   void emitMIPredicateFns(raw_ostream &OS) override;
   void emitI64ImmPredicateFns(raw_ostream &OS) override;
   void emitAPFloatImmPredicateFns(raw_ostream &OS) override;
   void emitAPIntImmPredicateFns(raw_ostream &OS) override;
+  void emitTestSimplePredicate(raw_ostream &OS) override;
+  void emitRunCustomAction(raw_ostream &OS) override;
 
   const CodeGenTarget &getTarget() const override { return Target; }
   StringRef getClassName() const override { return ClassName; }
 
   void run(raw_ostream &OS);
 
 private:
   std::string ClassName;
GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
 
   return MatchTable::buildTable(OptRules, WithCoverage);
 }
 
 void GlobalISelEmitter::emitAdditionalImpl(raw_ostream &OS) {
   OS << "bool " << getClassName()
      << "::selectImpl(MachineInstr &I, CodeGenCoverage "
         "&CoverageInfo) const {\n"
-     << "  MachineRegisterInfo &MRI = MF->getRegInfo();\n"
      << "  const PredicateBitset AvailableFeatures = "
         "getAvailableFeatures();\n"
      << "  NewMIVector OutMIs;\n"
      << "  State.MIs.clear();\n"
      << "  State.MIs.push_back(&I);\n\n"
      << "  if (executeMatchTable(*this, OutMIs, State, ExecInfo"
-     << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures"
+     << ", getMatchTable(), TII, MF->getRegInfo(), TRI, RBI, AvailableFeatures"
      << ", &CoverageInfo)) {\n"
      << "    return true;\n"
      << "  }\n\n"
      << "  return false;\n"
      << "}\n\n";
 }
 
 void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) {
std::copy_if(AllPatFrags.begin(), AllPatFrags.end(),
                });
   emitImmPredicateFnsImpl<Record *>(
       OS, "APInt", "const APInt &", ArrayRef<Record *>(MatchedRecords),
       &getPatFragPredicateEnumName,
       [&](Record *R) { return R->getValueAsString("ImmediateCode"); },
       "PatFrag predicates.");
 }
 
+void GlobalISelEmitter::emitTestSimplePredicate(raw_ostream &OS) {
+  OS << "bool " << getClassName() << "::testSimplePredicate(unsigned) const {\n"
+     << "    llvm_unreachable(\"" + getClassName() +
+            " does not support simple predicates!\");\n"
+     << "  return false;\n"
+     << "}\n";
+}
+
+void GlobalISelEmitter::emitRunCustomAction(raw_ostream &OS) {
+  OS << "void " << getClassName()
+     << "::runCustomAction(unsigned, const MatcherState&) const {\n"
+     << "    llvm_unreachable(\"" + getClassName() +
+            " does not support custom C++ actions!\");\n"
+     << "}\n";
+}
+
 void GlobalISelEmitter::run(raw_ostream &OS) {
   if (!UseCoverageFile.empty()) {
     RuleCoverage = CodeGenCoverage();
     auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
     if (!RuleCoverageBufOrErr) {
       PrintWarning(SMLoc(), "Missing rule coverage data");
       RuleCoverage = std::nullopt;
     } else {

llvm/utils/TableGen/GlobalISelMatchTable.h

class MatchTable {
   /// The currently defined labels.
   DenseMap<unsigned, unsigned> LabelMap;
   /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
   unsigned CurrentSize = 0;
   /// A unique identifier for a MatchTable label.
   unsigned CurrentLabelID = 0;
   /// Determines if the table should be instrumented for rule coverage tracking.
   bool IsWithCoverage;
+  /// Whether this table is for the GISel combiner.
+  bool IsCombinerTable;
 
 public:
   static MatchTableRecord LineBreak;
   static MatchTableRecord Comment(StringRef Comment);
   static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0);
   static MatchTableRecord NamedValue(StringRef NamedValue);
   static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue);
   static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue);
   static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
                                      int64_t RawValue);
   static MatchTableRecord IntValue(int64_t IntValue);
   static MatchTableRecord Label(unsigned LabelID);
   static MatchTableRecord JumpTarget(unsigned LabelID);
 
-  static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage);
+  static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,
+                               bool IsCombiner = false);
 
-  MatchTable(bool WithCoverage, unsigned ID = 0)
-      : ID(ID), IsWithCoverage(WithCoverage) {}
+  MatchTable(bool WithCoverage, bool IsCombinerTable, unsigned ID = 0)
+      : ID(ID), IsWithCoverage(WithCoverage), IsCombinerTable(IsCombinerTable) {
+  }
 
   bool isWithCoverage() const { return IsWithCoverage; }
+  bool isCombiner() const { return IsCombinerTable; }
 
   void push_back(const MatchTableRecord &Value) {
     if (Value.Flags & MatchTableRecord::MTRF_Label)
       defineLabel(Value.LabelID);
     Contents.push_back(Value);
     CurrentSize += Value.size();
   }
 
protected:
   unsigned NextOutputInsnID;
 
   /// ID for the next temporary register ID allocated with allocateTempRegID()
   unsigned NextTempRegID;
 
   /// Current GISelFlags
   GISelFlags Flags = 0;
 
+  std::vector<std::string> RequiredSimplePredicates;
   std::vector<Record *> RequiredFeatures;
   std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
 
   ArrayRef<SMLoc> SrcLoc;
 
   typedef std::tuple<Record *, unsigned, unsigned>
       DefinedComplexPatternSubOperand;
   typedef StringMap<DefinedComplexPatternSubOperand>
public:
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
   uint64_t getRuleID() const { return RuleID; }
 
   InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
   void addRequiredFeature(Record *Feature);
   const std::vector<Record *> &getRequiredFeatures() const;
 
+  void addRequiredSimplePredicate(StringRef PredName);
+  const std::vector<std::string> &getRequiredSimplePredicates();
+
   // Emplaces an action of the specified Kind at the end of the action list.
   //
   // Returns a reference to the newly created action.
   //
   // Like std::vector::emplace_back(), may invalidate all iterators if the new
   // size exceeds the capacity. Otherwise, only invalidates the past-the-end
   // iterator.
   template <class Kind, class... Args> Kind &addAction(Args &&...args) {
public:
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override;
 };
 
 /// Generates code to check an arbitrary C++ instruction predicate.
 class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher {
 protected:
-  TreePredicateFn Predicate;
+  std::string EnumVal;
 
 public:
   GenericInstructionPredicateMatcher(unsigned InsnVarID,
-                                     TreePredicateFn Predicate)
+                                     TreePredicateFn Predicate);
+
+  GenericInstructionPredicateMatcher(unsigned InsnVarID,
+                                     const std::string &EnumVal)
       : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID),
-        Predicate(Predicate) {}
+        EnumVal(EnumVal) {}
 
   static bool classof(const InstructionPredicateMatcher *P) {
     return P->getKind() == IPM_GenericPredicate;
   }
   bool isIdentical(const PredicateMatcher &B) const override;
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override;
 };

 public:
   DebugCommentAction(StringRef S) : S(std::string(S)) {}
 
   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
     Table << MatchTable::Comment(S) << MatchTable::LineBreak;
   }
 };
 
+class CustomCXXAction : public MatchAction {
+  std::string FnEnumName;
+
+public:
+  CustomCXXAction(StringRef FnEnumName) : FnEnumName(FnEnumName.str()) {}
+
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
+};
+
 /// Generates code to build an instruction or mutate an existing instruction
 /// into the desired instruction when this is possible.
 class BuildMIAction : public MatchAction {
 private:
   unsigned InsnID;
   const CodeGenInstruction *I;
   InstructionMatcher *Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;

llvm/utils/TableGen/GlobalISelMatchTable.cpp

if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
       OS << std::string(Indentation, ' ');
 
     if (I->Flags & MatchTableRecord::MTRF_Outdent)
       Indentation -= 2;
   }
   OS << "};\n";
 }
 
-MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
-                                  bool WithCoverage) {
-  MatchTable Table(WithCoverage);
+MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage,
+                                  bool IsCombiner) {
+  MatchTable Table(WithCoverage, IsCombiner);
   for (Matcher *Rule : Rules)
     Rule->emit(Table);
 
   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 }
 
 //===- LLTCodeGen ---------------------------------------------------------===//
 

 }
 
 InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
   Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
   MutatableInsns.insert(Matchers.back().get());
   return *Matchers.back();
 }
 
+void RuleMatcher::addRequiredSimplePredicate(StringRef PredName) {
+  RequiredSimplePredicates.push_back(PredName.str());
+}
+
+const std::vector<std::string> &RuleMatcher::getRequiredSimplePredicates() {
+  return RequiredSimplePredicates;
+}
+
 void RuleMatcher::addRequiredFeature(Record *Feature) {
   RequiredFeatures.push_back(Feature);
 }
 
 const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
   return RequiredFeatures;
 }
 
Table << MatchTable::Opcode("GIM_Try", +1)
         << MatchTable::LineBreak;
 
   if (!RequiredFeatures.empty()) {
     Table << MatchTable::Opcode("GIM_CheckFeatures")
           << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
           << MatchTable::LineBreak;
   }
 
+  if (!RequiredSimplePredicates.empty()) {
+    for (const auto &Pred : RequiredSimplePredicates) {
+      Table << MatchTable::Opcode("GIM_CheckSimplePredicate")
+            << MatchTable::NamedValue(Pred) << MatchTable::LineBreak;
+    }
+  }
+
   Matchers.front()->emitPredicateOpcodes(Table, *this);
 
   // We must also check if it's safe to fold the matched instructions.
   if (InsnVariableIDs.size() >= 2) {
     // Invert the map to create stable ordering (by var names)
     SmallVector<unsigned, 2> InsnIDs;
     for (const auto &Pair : InsnVariableIDs) {
       // Skip the root node since it isn't moving anywhere. Everything else is
for (const auto &InsnID : InsnIDs) {
       //        Example:
       //                   G_CONDBR %cond, @BB1
       //                 BB0:
       //          MI1-->   %0 = load @a
       //                   G_BR @BB1
       //                 BB1:
       //          MI0-->   %2 = ... %0
       //          It's not always safe to sink %0 across control flow. In this
-      //          case it may introduce a memory fault. We currentl handle this
-      //          by rejecting all loads.
+      //          case it may introduce a memory fault. We currentl handle
+      //          this by rejecting all loads.
     }
   }
 
   for (const auto &PM : EpilogueMatchers)
     PM->emitPredicateOpcodes(Table, *this);
 
   for (const auto &MA : Actions)
     MA->emitActionOpcodes(Table, *this);
 
+  assert((Table.isWithCoverage() ? !Table.isCombiner() : true) &&
+         "Combiner tables don't support coverage!");
   if (Table.isWithCoverage())
     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
           << MatchTable::LineBreak;
-  else
+  else if (!Table.isCombiner())
     Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
           << MatchTable::LineBreak;
 
   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
         << MatchTable::Label(LabelID);
   ++NumPatternEmitted;
 }
 
else
     Table << MatchTable::Opcode("GIM_CheckIsBuildVectorAllZeros");
 
   Table << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID);
   Table << MatchTable::LineBreak;
 }
 
 //===- GenericInstructionPredicateMatcher ---------------------------------===//
 
+GenericInstructionPredicateMatcher::GenericInstructionPredicateMatcher(
+    unsigned InsnVarID, TreePredicateFn Predicate)
+    : GenericInstructionPredicateMatcher(InsnVarID,
+                                         getEnumNameForPredicate(Predicate)) {}
+
 bool GenericInstructionPredicateMatcher::isIdentical(
     const PredicateMatcher &B) const {
   return InstructionPredicateMatcher::isIdentical(B) &&
-         Predicate == static_cast<const GenericInstructionPredicateMatcher &>(B)
-                          .Predicate;
+         EnumVal ==
+             static_cast<const GenericInstructionPredicateMatcher &>(B).EnumVal;
 }
 void GenericInstructionPredicateMatcher::emitPredicateOpcodes(
     MatchTable &Table, RuleMatcher &Rule) const {
   Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate")
         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
-        << MatchTable::Comment("FnId")
-        << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
+        << MatchTable::Comment("FnId") << MatchTable::NamedValue(EnumVal)
         << MatchTable::LineBreak;
 }
 
 //===- InstructionMatcher -------------------------------------------------===//
 
 OperandMatcher &
 InstructionMatcher::addOperand(unsigned OpIdx, const std::string &SymbolicName,
                                unsigned AllocatedTemporariesBaseID) {

 }
 
 void InstructionMatcher::optimize() {
   SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash;
   const auto &OpcMatcher = getOpcodeMatcher();
 
   Stash.push_back(predicates_pop_front());
   if (Stash.back().get() == &OpcMatcher) {
-    if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
+    if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands() &&
+        getNumOperands() != 0)
       Stash.emplace_back(
           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
     NumOperandsCheck = false;
 
     for (auto &OM : Operands)
       for (auto &OP : OM->predicates())
         if (isa<IntrinsicIDOperandMatcher>(OP)) {
           Stash.push_back(std::move(OP));
Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
         << MatchTable::Comment("OpIdx")
         << MatchTable::IntValue(OpdMatcher.getOpIdx())
         << MatchTable::Comment("OperandRenderer")
         << MatchTable::NamedValue("GICR_" +
                                   Renderer.getValueAsString("RendererFn").str())
         << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
 }
 
+//===- CustomCXXAction ----------------------------------------------------===//
+
+void CustomCXXAction::emitActionOpcodes(MatchTable &Table,
+                                        RuleMatcher &Rule) const {
+  Table << MatchTable::Opcode("GIR_CustomAction")
+        << MatchTable::NamedValue(FnEnumName) << MatchTable::LineBreak;
+}
+
 //===- BuildMIAction ------------------------------------------------------===//
 
 bool BuildMIAction::canMutate(RuleMatcher &Rule,
                               const InstructionMatcher *Insn) const {
   if (!Insn)
     return false;
 
   if (OperandRenderers.size() != Insn->getNumOperands())

llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.h

void emitCxxPredicateFns(
       StringRef AdditionalDeclarations, ArrayRef<PredicateObject> Predicates,
       std::function<StringRef(PredicateObject)> GetPredEnumName,
       std::function<StringRef(PredicateObject)> GetPredCode,
       StringRef Comment) {
     if (!Comment.empty())
       OS << "// " << Comment << "\n";
     if (!Predicates.empty()) {
       OS << "enum {\n";
-      std::string EnumeratorSeparator =
-          (" = GICXXPred_" + TypeIdentifier + "_Invalid + 1,\n").str();
+      StringRef EnumeratorSeparator = " = GICXXPred_Invalid + 1,\n";
       for (const auto &Pred : Predicates) {
         OS << "  GICXXPred_" << TypeIdentifier << "_Predicate_"
            << GetPredEnumName(Pred) << EnumeratorSeparator;
         EnumeratorSeparator = ",\n";
       }
       OS << "};\n";
     }
 
public:
 
   /// Emit the `testImmPredicate_APFloat` function.
   /// Note: `emitImmPredicateFnsImpl` can be used to do most of the work.
   virtual void emitAPFloatImmPredicateFns(raw_ostream &OS) = 0;
 
   /// Emit the `testImmPredicate_APInt` function.
   /// Note: `emitImmPredicateFnsImpl` can be used to do most of the work.
   virtual void emitAPIntImmPredicateFns(raw_ostream &OS) = 0;
+  virtual void emitTestSimplePredicate(raw_ostream &OS) = 0;
+  virtual void emitRunCustomAction(raw_ostream &OS) = 0;
 
   void emitExecutorImpl(raw_ostream &OS, const gi::MatchTable &Table,
                         ArrayRef<gi::LLTCodeGen> TypeObjects,
                         ArrayRef<gi::RuleMatcher> Rules,
                         ArrayRef<Record *> ComplexOperandMatchers,
                         ArrayRef<StringRef> CustomOperandRenderers,
                         StringRef IfDefName);
   void emitPredicateBitset(raw_ostream &OS, StringRef IfDefName);

llvm/utils/TableGen/GlobalISelMatchTableExecutorEmitter.cpp

void GlobalISelMatchTableExecutorEmitter::emitExecutorImpl(
   OS << "#ifdef " << IfDefName << "\n";
   emitTypeObjects(OS, TypeObjects);
   emitSubtargetFeatureBitsetImpl(OS, Rules);
   emitComplexPredicates(OS, ComplexOperandMatchers);
   emitMIPredicateFns(OS);
   emitI64ImmPredicateFns(OS);
   emitAPFloatImmPredicateFns(OS);
   emitAPIntImmPredicateFns(OS);
+  emitTestSimplePredicate(OS);
   emitCustomOperandRenderers(OS, CustomOperandRenderers);
   emitAdditionalImpl(OS);
+  emitRunCustomAction(OS);
   emitMatchTable(OS, Table);
   OS << "#endif // ifdef " << IfDefName << "\n\n";
 }
 
 void GlobalISelMatchTableExecutorEmitter::emitPredicateBitset(
     raw_ostream &OS, StringRef IfDefName) {
   OS << "#ifdef " << IfDefName << "\n"
      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
<< "  bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const "
         "override;\n"
      << "  bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) "
         "const override;\n"
      << "  bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat "
         "&Imm) const override;\n"
      << "  const int64_t *getMatchTable() const override;\n"
      << "  bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI"
         ", const MatcherState &State) "
+        "const override;\n"
+     << "  bool testSimplePredicate(unsigned PredicateID) const override;\n"
+     << "  void runCustomAction(unsigned FnID, const MatcherState &State) "
         "const override;\n";
   emitAdditionalTemporariesDecl(OS, "  ");
   OS << "#endif // ifdef " << IfDefName << "\n\n";
 }
 
 void GlobalISelMatchTableExecutorEmitter::emitTemporariesInit(
     raw_ostream &OS, unsigned MaxTemporaries, StringRef IfDefName) {
   OS << "#ifdef " << IfDefName << "\n"