[TableGen][GlobalISel] Add MIR Pattern Builtins

[Pierre-vh]

Summary

Adds a new feature to MIR patterns: builtin instructions.
They offer some additional capabilities that currently cannot be expressed without falling back to C++ code.
There are two builtins added with this patch, but more can be added later as new needs arise:

• GIReplaceReg
• GIEraseRoot

Depends on D158714, D158713

[Pierre-vh]

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

77

Note: as the name of the test indicates, this isn't supposed to be replaced, so this isn't a regression - it fixes a correctness issue.

[Pierre-vh]

fix small nit

[aemerson]

LGTM, nice!

[Pierre-vh]

Fix test
(Note that this depends on some other patches so it can't land yet)

llvm/docs/GlobalISel/MIRPatterns.rst

.. code-block:: text
   :caption: Pattern Example 2
 
   // using $x twice here checks that the operand 1 and 2 of the G_AND are
   // identical.
   (match (G_AND $root, $x, $x))
   // using $x again here copies operand 1 from G_AND into the new inst.
   (apply (COPY $root, $x))
 
+Builtin Operations
+------------------
+
+MIR Patterns also offer builtin operations, also called "builtin instructions".
+They offer some powerful features that would otherwise require use of C++ code.
+
+GIReplaceReg
+~~~~~~~~~~~~
+
+.. code-block:: text
+  :caption: Usage
+
+  (apply (GIReplaceReg $old, $new))
+
+Operands:
+
+* ``$old`` (out) register defined by a matched instruction
+* ``$new`` (in)  register
+
+Semantics:
+
+* Can only appear in an 'apply' pattern.
+* If both old/new are operands of matched instructions,
+  ``canReplaceReg`` is checked before applying the rule.
+
+
+GIEraseRoot
+~~~~~~~~~~~
+
+.. code-block:: text
+  :caption: Usage
+
+  (apply (GIEraseRoot))
+
+Semantics:
+
+* Can only appear as the only pattern of an 'apply' pattern list.
+* The root cannot have any output operands.
+* The root must be a CodeGenInstruction
+
 
 Limitations
 -----------
 
 This a non-exhaustive list of known issues with MIR patterns at this time.
 
 * Matching intrinsics is not yet possible.
 * Using ``GICombinePatFrag`` within another ``GICombinePatFrag`` is not
   supported.
 * ``GICombinePatFrag`` can only have a single root.
 * Instructions with multiple defs cannot be the root of a ``GICombinePatFrag``.
 * Using ``GICombinePatFrag`` in the ``apply`` pattern of a ``GICombineRule``
   is not supported.
-* Deleting the matched pattern in a ``GICombineRule`` needs to be done using
-  ``G_IMPLICIT_DEF`` or C++.
-* Replacing the root of a pattern with another instruction needs to be done
-  using COPY.
 * We cannot rewrite a matched instruction other than the root.
 * Matching/creating a (CImm) immediate >64 bits is not supported
   (see comment in ``GIM_CheckConstantInt``)
 * There is currently no way to constrain two register/immediate types to
   match. e.g. if a pattern needs to work on both i32 and i64, you either
   need to leave it untyped and check the type in C++, or duplicate the
   pattern.
 
.. code-block:: text
   def Foo : GICombineRule<
     (defs root:$root),
     (match (G_ZEXT $root, $src):$mi),
     (apply "foobar(${root}.getReg(), ${src}.getReg(), ${mi}->hasImplicitDef())")>;
 
 Common Pattern #1: Replace a Register with Another
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
-The 'apply' pattern must always redefine its root.
-It cannot just replace it with something else directly.
-A simple workaround is to just use a COPY that'll be eliminated later.
+The 'apply' pattern must always redefine all operands defined by the match root.
+Sometimes, we do not need to create instructions, simply replace a def with
+another matched register. The ``GIReplaceReg`` builtin can do just that.
 
 .. code-block:: text
 
   def Foo : GICombineRule<
     (defs root:$dst),
     (match (G_FNEG $tmp, $src), (G_FNEG $dst, $tmp)),
-    (apply (COPY $dst, $src))>;
+    (apply (GIReplaceReg $dst, $src))>;
 
-Common Pattern #2: Erasing a Pattern
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+This also works if the replacement register is a temporary register from the
+``apply`` pattern.
 
-As said before, we must always emit something in the 'apply' pattern.
-If we wish to delete the matched instruction, we can simply replace its
-definition with a ``G_IMPLICIT_DEF``.
+.. code-block:: text
+
+  def ReplaceTemp : GICombineRule<
+    (defs root:$a),
+    (match    (G_BUILD_VECTOR $tmp, $x, $y),
+              (G_UNMERGE_VALUES $a, $b, $tmp)),
+    (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
+            (GIReplaceReg $b, $new))>
+
+Common Pattern #2: Erasing a Def-less Root
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+If we simply want to erase a def-less match root, we can use the
+``GIEraseRoot`` builtin.
 
 .. code-block:: text
 
   def Foo : GICombineRule<
-    (defs root:$dst),
-    (match (G_FOO $tmp, $src), (G_BAR $dst, $tmp)),
-    (apply (G_IMPLICIT_DEF $dst))>;
-
-If the instruction has no definition, like ``G_STORE``, we cannot use
-an instruction pattern in 'apply' - C++ has to be used.
+    (defs root:$mi),
+    (match (G_STORE $a, $b):$mi),
+    (apply (GIEraseRoot))>;
 
 Common Pattern #3: Emitting a Constant Value
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 When an immediate operand appears in an 'apply' pattern, the behavior
 depends on whether it's typed or not.
 
 * If the immediate is typed, a ``G_CONSTANT`` is implicitly emitted

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

enum {
   /// comparing the operands.
   /// - InsnID - Instruction ID
   /// - OpIdx - Operand index
   /// - OtherInsnID - Other instruction ID
   /// - OtherOpIdx - Other operand index
   GIM_CheckIsSameOperand,
   GIM_CheckIsSameOperandIgnoreCopies,
 
+  /// Check we can replace all uses of a register with another.
+  /// - OldInsnID
+  /// - OldOpIdx
+  /// - NewInsnID
+  /// - NewOpIdx
+  GIM_CheckCanReplaceReg,
+
   /// Predicates with 'let PredicateCodeUsesOperands = 1' need to examine some
   /// named operands that will be recorded in RecordedOperands. Names of these
   /// operands are referenced in predicate argument list. Emitter determines
   /// StoreIdx(corresponds to the order in which names appear in argument list).
   /// - InsnID - Instruction ID
   /// - OpIdx - Operand index
   /// - StoreIdx - Store location in RecordedOperands.
   GIM_RecordNamedOperand,
enum {
   /// - InsnID - Instruction ID to erase
   GIR_EraseFromParent,
 
   /// Create a new temporary register that's not constrained.
   /// - TempRegID - The temporary register ID to initialize.
   /// - Expected type
   GIR_MakeTempReg,
 
+  /// Replaces all references to a register from an instruction
+  /// with another register from another instruction.
+  /// - OldInsnID
+  /// - OldOpIdx
+  /// - NewInsnID
+  /// - NewOpIdx
+  GIR_ReplaceReg,
+
+  /// Replaces all references to a register with a temporary register.
+  /// - OldInsnID
+  /// - OldOpIdx
+  /// - TempRegIdx
+  GIR_ReplaceRegWithTempReg,
+
   /// A successful emission
   GIR_Done,
 
   /// Increment the rule coverage counter.
   /// - RuleID - The ID of the rule that was covered.
   GIR_Coverage,
 
   /// Keeping track of the number of the GI opcodes. Must be the last entry.

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

case GIM_CheckIsSameOperandIgnoreCopies: {
       }
 
       if (!Op.isIdenticalTo(OtherOp)) {
         if (handleReject() == RejectAndGiveUp)
           return false;
       }
       break;
     }
+    case GIM_CheckCanReplaceReg: {
+      int64_t OldInsnID = MatchTable[CurrentIdx++];
+      int64_t OldOpIdx = MatchTable[CurrentIdx++];
+      int64_t NewInsnID = MatchTable[CurrentIdx++];
+      int64_t NewOpIdx = MatchTable[CurrentIdx++];
+
+      DEBUG_WITH_TYPE(TgtExecutor::getName(),
+                      dbgs() << CurrentIdx << ": GIM_CheckCanReplaceReg(MIs["
+                             << OldInsnID << "][" << OldOpIdx << "] = MIs["
+                             << NewInsnID << "][" << NewOpIdx << "])\n");
+
+      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
+      Register New = State.MIs[NewInsnID]->getOperand(NewOpIdx).getReg();
+      if (!canReplaceReg(Old, New, MRI)) {
+        if (handleReject() == RejectAndGiveUp)
+          return false;
+      }
+      break;
+    }
     case GIM_Reject:
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs() << CurrentIdx << ": GIM_Reject\n");
       if (handleReject() == RejectAndGiveUp)
         return false;
       break;
     case GIR_MutateOpcode: {
       int64_t OldInsnID = MatchTable[CurrentIdx++];
case GIR_MakeTempReg: {
 
       State.TempRegisters[TempRegID] =
           MRI.createGenericVirtualRegister(ExecInfo.TypeObjects[TypeID]);
       DEBUG_WITH_TYPE(TgtExecutor::getName(),
                       dbgs() << CurrentIdx << ": TempRegs[" << TempRegID
                              << "] = GIR_MakeTempReg(" << TypeID << ")\n");
       break;
     }
+    case GIR_ReplaceReg: {
+      int64_t OldInsnID = MatchTable[CurrentIdx++];
+      int64_t OldOpIdx = MatchTable[CurrentIdx++];
+      int64_t NewInsnID = MatchTable[CurrentIdx++];
+      int64_t NewOpIdx = MatchTable[CurrentIdx++];
+
+      DEBUG_WITH_TYPE(TgtExecutor::getName(),
+                      dbgs() << CurrentIdx << ": GIR_ReplaceReg(MIs["
+                             << OldInsnID << "][" << OldOpIdx << "] = MIs["
+                             << NewInsnID << "][" << NewOpIdx << "])\n");
 
+      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
+      Register New = State.MIs[NewInsnID]->getOperand(NewOpIdx).getReg();
+      if (Observer)
+        Observer->changingAllUsesOfReg(MRI, Old);
+      MRI.replaceRegWith(Old, New);
+      if (Observer)
+        Observer->finishedChangingAllUsesOfReg();
+      break;
+    }
+    case GIR_ReplaceRegWithTempReg: {
+      int64_t OldInsnID = MatchTable[CurrentIdx++];
+      int64_t OldOpIdx = MatchTable[CurrentIdx++];
+      int64_t TempRegID = MatchTable[CurrentIdx++];
+
+      DEBUG_WITH_TYPE(TgtExecutor::getName(),
+                      dbgs() << CurrentIdx << ": GIR_ReplaceRegWithTempReg(MIs["
+                             << OldInsnID << "][" << OldOpIdx << "] = TempRegs["
+                             << TempRegID << "])\n");
+
+      Register Old = State.MIs[OldInsnID]->getOperand(OldOpIdx).getReg();
+      Register New = State.TempRegisters[TempRegID];
+      if (Observer)
+        Observer->changingAllUsesOfReg(MRI, Old);
+      MRI.replaceRegWith(Old, New);
+      if (Observer)
+        Observer->finishedChangingAllUsesOfReg();
+      break;
+    }
     case GIR_Coverage: {
       int64_t RuleID = MatchTable[CurrentIdx++];
       assert(CoverageInfo);
       CoverageInfo->setCovered(RuleID);
 
       DEBUG_WITH_TYPE(TgtExecutor::getName(), dbgs() << CurrentIdx
                                                      << ": GIR_Coverage("
                                                      << RuleID << ")");

llvm/include/llvm/Target/GlobalISel/Combine.td

 // instruction pattern.
 class GICombinePatFrag<dag outs, dag ins, list<dag> alts> {
   dag InOperands = ins;
   dag OutOperands = outs;
   list<dag> Alternatives = alts;
 }
 
 //===----------------------------------------------------------------------===//
+// Pattern Builtins
+//===----------------------------------------------------------------------===//
+
+// "Magic" Builtin instructions for MIR patterns.
+// The definitions that implement
+class GIBuiltinInst;
+
+// Replace all references to a register with another one.
+//
+// Usage:
+//    (apply (GIReplaceReg $old, $new))
+//
+// Operands:
+// - $old (out) register defined by a matched instruction
+// - $new (in)  register
+//
+// Semantics:
+// - Can only appear in an 'apply' pattern.
+// - If both old/new are operands of matched instructions,
+//   "canReplaceReg" is checked before applying the rule.
+def GIReplaceReg : GIBuiltinInst;
+
+// Apply action that erases the match root.
+//
+// Usage:
+//    (apply (GIEraseRoot))
+//
+// Semantics:
+// - Can only appear as the only pattern of an 'apply' pattern list.
+// - The root cannot have any output operands.
+// - The root must be a CodeGenInstruction
+//
+// TODO: Allow using this directly, like (apply GIEraseRoot)
+def GIEraseRoot : GIBuiltinInst;
+
+//===----------------------------------------------------------------------===//
 
 def extending_load_matchdata : GIDefMatchData<"PreferredTuple">;
 def indexed_load_store_matchdata : GIDefMatchData<"IndexedLoadStoreMatchInfo">;
 def instruction_steps_matchdata: GIDefMatchData<"InstructionStepsMatchInfo">;
 
 def register_matchinfo: GIDefMatchData<"Register">;
 def int64_matchinfo: GIDefMatchData<"int64_t">;
 def apint_matchinfo : GIDefMatchData<"APInt">;

 def idempotent_prop_frags : GICombinePatFrag<
   (outs root:$dst, $src), (ins),
   !foreach(op, [G_FREEZE, G_FABS, G_FCANONICALIZE],
            (pattern (op $dst, $src), (op $src, $x)))>;
 
 def idempotent_prop : GICombineRule<
    (defs root:$dst),
    (match (idempotent_prop_frags $dst, $src)),
-   (apply (COPY $dst, $src))>;
+   (apply (GIReplaceReg $dst, $src))>;
 
 
 def extending_loads : GICombineRule<
   (defs root:$root, extending_load_matchdata:$matchinfo),
   (match (wip_match_opcode G_LOAD, G_SEXTLOAD, G_ZEXTLOAD):$root,
          [{ return Helper.matchCombineExtendingLoads(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyCombineExtendingLoads(*${root}, ${matchinfo}); }])>;
 
def select_same_val: GICombineRule<
   (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 2); }])
 >;
 
 // Fold (undef ? x : y) -> y
 def select_undef_cmp: GICombineRule<
   (defs root:$dst),
   (match (G_IMPLICIT_DEF $undef),
          (G_SELECT $dst, $undef, $x, $y)),
-  (apply (COPY $dst, $y))
+  (apply (GIReplaceReg $dst, $y))
 >;
 
 // Fold (true ? x : y) -> x
 // Fold (false ? x : y) -> y
 def select_constant_cmp_matchdata : GIDefMatchData<"unsigned">;
 def select_constant_cmp: GICombineRule<
   (defs root:$root, select_constant_cmp_matchdata:$matchinfo),
   (match (wip_match_opcode G_SELECT):$root,
def right_identity_zero_frags : GICombinePatFrag<
   (outs root:$dst), (ins $x),
   !foreach(op,
            [G_SUB, G_ADD, G_OR, G_XOR, G_SHL, G_ASHR,
             G_LSHR, G_PTR_ADD, G_ROTL, G_ROTR],
            (pattern (op $dst, $x, 0)))>;
 def right_identity_zero: GICombineRule<
   (defs root:$dst),
   (match (right_identity_zero_frags $dst, $lhs)),
-  (apply (COPY $dst, $lhs))
+  (apply (GIReplaceReg $dst, $lhs))
 >;
 
 // Fold x op 1 -> x
 def right_identity_one: GICombineRule<
   (defs root:$dst),
   (match (G_MUL $dst, $x, 1)),
-  (apply (COPY $dst, $x))
+  (apply (GIReplaceReg $dst, $x))
 >;
 
 // Fold (x op x) - > x
 def binop_same_val_frags : GICombinePatFrag<
   (outs root:$dst), (ins $x),
   [
     (pattern (G_AND $dst, $x, $x)),
     (pattern (G_OR $dst, $x, $x)),
   ]
 >;
 def binop_same_val: GICombineRule<
   (defs root:$dst),
   (match (binop_same_val_frags $dst, $src)),
-  (apply (COPY $dst, $src))
+  (apply (GIReplaceReg $dst, $src))
 >;
 
 // Fold (0 op x) - > 0
 def binop_left_to_zero: GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
     [{ return Helper.matchOperandIsZero(*${root}, 1); }]),
   (apply [{ Helper.replaceSingleDefInstWithOperand(*${root}, 1); }])
(match (wip_match_opcode G_SDIV, G_UDIV, G_SREM, G_UREM):$root,
     [{ return Helper.matchCombineDivRem(*${root}, ${matchinfo}); }]),
   (apply [{ Helper.applyCombineDivRem(*${root}, ${matchinfo}); }])
 >;
 
 // Fold (x op 0) - > 0
 def binop_right_to_zero: GICombineRule<
   (defs root:$dst),
   (match (G_MUL $dst, $lhs, 0:$zero)),
-  (apply (COPY $dst, $zero))
+  (apply (GIReplaceReg $dst, $zero))
 >;
 
 // Erase stores of undef values.
 def erase_undef_store : GICombineRule<
   (defs root:$root),
   (match (wip_match_opcode G_STORE):$root,
     [{ return Helper.matchUndefStore(*${root}); }]),
   (apply [{ Helper.eraseInst(*${root}); }])
def not_cmp_fold : GICombineRule<
   (apply [{ Helper.applyNotCmp(*${d}, ${info}); }])
 >;
 
 // Fold (fneg (fneg x)) -> x.
 def fneg_fneg_fold: GICombineRule <
   (defs root:$dst),
   (match (G_FNEG $t, $src),
          (G_FNEG $dst, $t)),
-  (apply (COPY $dst, $src))
+  (apply (GIReplaceReg $dst, $src))
 >;
 
 // Fold (unmerge(merge x, y, z)) -> z, y, z.
 def unmerge_merge_matchinfo : GIDefMatchData<"SmallVector<Register, 8>">;
 def unmerge_merge : GICombineRule<
   (defs root:$d, unmerge_merge_matchinfo:$info),
   (match (wip_match_opcode G_UNMERGE_VALUES): $d,
   [{ return Helper.matchCombineUnmergeMergeToPlainValues(*${d}, ${info}); }]),
def add_sub_reg_frags : GICombinePatFrag<
   (outs root:$dst), (ins $src),
   [
     (pattern (G_ADD $dst, $x, $tmp), (G_SUB $tmp, $src, $x)),
     (pattern (G_ADD $dst, $tmp, $x), (G_SUB $tmp, $src, $x))
   ]>;
 def add_sub_reg: GICombineRule <
   (defs root:$dst),
   (match (add_sub_reg_frags $dst, $src)),
-  (apply (COPY $dst, $src))>;
+  (apply (GIReplaceReg $dst, $src))>;
 
 def buildvector_identity_fold : GICombineRule<
   (defs root:$build_vector, register_matchinfo:$matchinfo),
   (match (wip_match_opcode G_BUILD_VECTOR_TRUNC, G_BUILD_VECTOR):$build_vector,
          [{ return Helper.matchBuildVectorIdentityFold(*${build_vector}, ${matchinfo}); }]),
   (apply [{ Helper.replaceSingleDefInstWithReg(*${build_vector}, ${matchinfo}); }])>;
 
 def trunc_buildvector_fold : GICombineRule<

llvm/test/CodeGen/AArch64/GlobalISel/prelegalizercombiner-trivial-arith.mir

 body:             |
   bb.1.entry:
     liveins: $w0
     ; Fold (x * 0) -> 0
     ;
     ; CHECK-LABEL: name: mul_0_cant_replace
     ; CHECK: liveins: $w0
     ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: %x:_(s32) = COPY $w0
     ; CHECK-NEXT: %cst:_(s32) = G_CONSTANT i32 0
-    ; CHECK-NEXT: %op:gpr(s32) = COPY %cst(s32)
+    ; CHECK-NEXT: %op:gpr(s32) = G_MUL %x, %cst
     ; CHECK-NEXT: $w0 = COPY %op(s32)
     ; CHECK-NEXT: RET_ReallyLR implicit $w0
     %x:_(s32) = COPY $w0
     %cst:_(s32) = G_CONSTANT i32 0
     %op:gpr(s32) = G_MUL %x(s32), %cst
     $w0 = COPY %op(s32)
     RET_ReallyLR implicit $w0
 

llvm/test/TableGen/GlobalISelCombinerEmitter/builtins/builtin-pattern-errors.td

+// RUN: not llvm-tblgen -I %p/../../../../include -gen-global-isel-combiner \
+// 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; }
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: expected operand 1 of 'GIReplaceReg' to be a name
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(GIReplaceReg ?:$dst, (i32 0))'
+def builtinpat_immop : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIReplaceReg $dst, (i32 0)))>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: expected operand 1 of 'GIReplaceReg' to be a name
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(GIReplaceReg ?:$dst, (i32 0):$k)'
+def builtinpat_namedimmop : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIReplaceReg $dst, (i32 0):$k))>;
+
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: 'GIEraseRoot' cannot be used in a 'match' pattern
+def eraseroot_in_match : GICombineRule<
+  (defs root:$dst),
+  (match (GIEraseRoot):$mi),
+  (apply (COPY $dst, $src))>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: 'GIEraseRoot' expected 0 operands, got 1
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(GIEraseRoot ?:$dst)'
+def eraseroot_ops : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIEraseRoot $dst), (COPY $dst, $src))>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: GIEraseRoot must be the only 'apply' pattern
+def eraseroot_multiapply : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIEraseRoot), (COPY $dst, $src))>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: GIEraseRoot can only be used if on roots that do not have any output operand
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: note: 'COPY' has 1 output operands
+def eraseroot_root_has_def: GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIEraseRoot))>;
+
+def TestPF: GICombinePatFrag<
+    (outs root:$def),
+    (ins),
+    [(pattern (COPY $def, $src))]>;
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: GIEraseRoot can only be used if the root is a CodeGenInstruction
+def eraseroot_notinstmatch: GICombineRule<
+  (defs root:$mi),
+  (match (TestPF $dst):$mi),
+  (apply (GIEraseRoot))>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: 'GIReplaceReg' cannot be used in a 'match' pattern
+def replacereg_in_match : GICombineRule<
+  (defs root:$dst),
+  (match (GIReplaceReg $dst, $src)),
+  (apply (COPY $dst, $src))>;
+
+// CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: 'GIReplaceReg' expected 2 operands, got 1
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(GIReplaceReg ?:$dst)'
+def replacereg_ops : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $src)),
+  (apply (GIReplaceReg $dst))>;
+
+// CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: GIReplaceReg cannot replace 'tmp': this builtin can only replace a register defined by the match root
+def replacereg_nonroot : GICombineRule<
+  (defs root:$dst),
+  (match (COPY $dst, $tmp), (COPY $tmp, $src)),
+  (apply (GIReplaceReg $dst, $src), (GIReplaceReg $tmp, $src))>;
+
+// CHECK: error: Failed to parse one or more rules
+
+def MyCombiner: GICombiner<"GenMyCombiner", [
+  builtinpat_immop,
+  builtinpat_namedimmop,
+  eraseroot_in_match,
+  eraseroot_ops,
+  eraseroot_multiapply,
+  eraseroot_root_has_def,
+  eraseroot_notinstmatch,
+  replacereg_in_match,
+  replacereg_ops,
+  replacereg_nonroot
+]>;

llvm/test/TableGen/GlobalISelCombinerEmitter/builtins/builtin-pattern-parrsing.td

+// RUN: llvm-tblgen -I %p/../../../../include -gen-global-isel-combiner \
+// 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; }
+
+// CHECK:      (CombineRule name:BuiltinTest0 id:0 root:a
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     <match_root>__BuiltinTest0_match_0:(CodeGenInstructionPattern G_TRUNC operands:[<def>$a, $b])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     <apply_root>__BuiltinTest0_apply_0:(BuiltinPattern GIReplaceReg operands:[<def>$a, $b])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable MatchPats
+// CHECK-NEXT:     a -> __BuiltinTest0_match_0
+// CHECK-NEXT:     b -> <live-in>
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable ApplyPats
+// CHECK-NEXT:     a -> __BuiltinTest0_apply_0
+// CHECK-NEXT:     b -> <live-in>
+// CHECK-NEXT:   )
+// CHECK-NEXT: )
+def BuiltinTest0 : GICombineRule<
+  (defs root:$a),
+  (match (G_TRUNC $a, $b)),
+  (apply (GIReplaceReg $a, $b))
+>;
+
+// CHECK:      (CombineRule name:BuiltinTest1 id:1 root:mi
+// CHECK-NEXT:   (MatchPats
+// CHECK-NEXT:     <match_root>mi:(CodeGenInstructionPattern G_STORE operands:[$a, $b])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (ApplyPats
+// CHECK-NEXT:     __BuiltinTest1_apply_0:(BuiltinPattern GIEraseRoot operands:[])
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable MatchPats
+// CHECK-NEXT:     a -> <live-in>
+// CHECK-NEXT:     b -> <live-in>
+// CHECK-NEXT:   )
+// CHECK-NEXT:   (OperandTable ApplyPats <empty>)
+// CHECK-NEXT: )
+def BuiltinTest1 : GICombineRule<
+  (defs root:$mi),
+  (match (G_STORE $a, $b):$mi),
+  (apply (GIEraseRoot))
+>;
+
+def MyCombiner: GICombiner<"GenMyCombiner", [
+  BuiltinTest0,
+  BuiltinTest1
+]>;

llvm/test/TableGen/GlobalISelCombinerEmitter/builtins/match-table-eraseroot.td

+// RUN: llvm-tblgen -I %p/../../../../include -gen-global-isel-combiner \
+// 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 Test0 : GICombineRule<
+  (defs root:$mi),
+  (match (G_STORE $a, $b):$mi),
+  (apply (GIEraseRoot))>;
+
+def MyCombiner: GICombiner<"GenMyCombiner", [
+  Test0,
+]>;
+
+// CHECK:      const int64_t *GenMyCombiner::getMatchTable() const {
+// CHECK-NEXT:   constexpr static int64_t MatchTable0[] = {
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 0*/ 10, // Rule ID 0 //
+// CHECK-NEXT:       GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule0Enabled,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_STORE,
+// CHECK-NEXT:       // MIs[0] a
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // MIs[0] b
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // Combiner Rule #0: Test0
+// CHECK-NEXT:       GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:       GIR_Done,
+// CHECK-NEXT:     // Label 0: @10
+// CHECK-NEXT:     GIM_Reject,
+// CHECK-NEXT:     };
+// CHECK-NEXT:   return MatchTable0;
+// CHECK-NEXT: }

llvm/test/TableGen/GlobalISelCombinerEmitter/builtins/match-table-replacerreg.td

+// RUN: llvm-tblgen -I %p/../../../../include -gen-global-isel-combiner \
+// 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 ReplaceMatched : GICombineRule<
+  (defs root:$dst),
+  (match  (G_FNEG $tmp, $src),
+          (G_FNEG $dst, $tmp)),
+  (apply  (GIReplaceReg $dst, $src))>;
+
+def ReplaceTemp : GICombineRule<
+  (defs root:$a),
+  (match    (G_BUILD_VECTOR $tmp, $x, $y),
+            (G_UNMERGE_VALUES $a, $b, $tmp)),
+  (apply  (G_UNMERGE_VALUES $a, i32:$new, $y),
+          (GIReplaceReg $b, $new))>;
+
+def MyCombiner: GICombiner<"GenMyCombiner", [
+  ReplaceMatched,
+  ReplaceTemp
+]>;
+
+// CHECK:      const int64_t *GenMyCombiner::getMatchTable() const {
+// CHECK-NEXT:   constexpr static int64_t MatchTable0[] = {
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 0*/ 29, // Rule ID 0 //
+// CHECK-NEXT:       GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule0Enabled,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_FNEG,
+// CHECK-NEXT:       // MIs[0] dst
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // MIs[0] tmp
+// CHECK-NEXT:       GIM_RecordInsnIgnoreCopies, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_FNEG,
+// CHECK-NEXT:       // MIs[1] src
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       GIM_CheckCanReplaceReg, /*OldInsnID*/0, /*OldOpIdx*/0, /*NewInsnId*/1, /*NewOpIdx*/1,
+// CHECK-NEXT:       GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT:       // Combiner Rule #0: ReplaceMatched
+// CHECK-NEXT:       GIR_ReplaceReg, /*OldInsnID*/0, /*OldOpIdx*/0, /*NewInsnId*/1, /*NewOpIdx*/1,
+// CHECK-NEXT:       GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:       GIR_Done,
+// CHECK-NEXT:     // Label 0: @29
+// CHECK-NEXT:     GIM_Try, /*On fail goto*//*Label 1*/ 76, // Rule ID 1 //
+// CHECK-NEXT:       GIM_CheckSimplePredicate, GICXXPred_Simple_IsRule1Enabled,
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_UNMERGE_VALUES,
+// CHECK-NEXT:       GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:       // MIs[0] a
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // MIs[0] b
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // MIs[0] tmp
+// CHECK-NEXT:       GIM_RecordInsnIgnoreCopies, /*DefineMI*/1, /*MI*/0, /*OpIdx*/2, // MIs[1]
+// CHECK-NEXT:       GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_BUILD_VECTOR,
+// CHECK-NEXT:       GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT:       // MIs[1] x
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       // MIs[1] y
+// CHECK-NEXT:       // No operand predicates
+// CHECK-NEXT:       GIM_CheckIsSafeToFold, /*InsnID*/1,
+// CHECK-NEXT:       GIR_MakeTempReg, /*TempRegID*/0, /*TypeID*/GILLT_s32,
+// CHECK-NEXT:       // Combiner Rule #1: ReplaceTemp
+// CHECK-NEXT:       GIR_BuildMI, /*InsnID*/0, /*Opcode*/TargetOpcode::G_UNMERGE_VALUES,
+// CHECK-NEXT:       GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/0, /*OpIdx*/0, // a
+// CHECK-NEXT:       GIR_AddTempRegister, /*InsnID*/0, /*TempRegID*/0, /*TempRegFlags*/0,
+// CHECK-NEXT:       GIR_Copy, /*NewInsnID*/0, /*OldInsnID*/1, /*OpIdx*/2, // y
+// CHECK-NEXT:       GIR_EraseFromParent, /*InsnID*/0,
+// CHECK-NEXT:       GIR_ReplaceRegWithTempReg, /*OldInsnID*/0, /*OldOpIdx*/1, /*TempRegID*/0,
+// CHECK-NEXT:       GIR_Done,
+// CHECK-NEXT:     // Label 1: @76
+// CHECK-NEXT:     GIM_Reject,
+// CHECK-NEXT:     };
+// CHECK-NEXT:   return MatchTable0;
+// CHECK-NEXT: }

llvm/test/TableGen/GlobalISelCombinerEmitter/pattern-errors.td

 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: 'b' must be redefined in the 'apply' pattern
 def no_redef_in_apply_multidefroot : GICombineRule<
   (defs root:$a),
   (match (G_UNMERGE_VALUES $a, $b, $c)),
   (apply (COPY $a, $c))>;
 
 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: cannot use wip_match_opcode in combination with apply instruction patterns
 def instpat_with_wipmatch : GICombineRule<
-  (defs root:$a),
+  (defs root:$d),
   (match (wip_match_opcode COPY):$d),
   (apply (COPY $x, $b):$d)>;
 
 // CHECK: :[[@LINE+2]]:{{[0-9]+}}: error: cannot parse operand '(i32)'
 // CHECK: :[[@LINE+1]]:{{[0-9]+}}: error: Failed to parse pattern: '(COPY ?:$x, (i32))
 def bad_imm_noarg : GICombineRule<
   (defs root:$a),
   (match (COPY $x, (i32)):$d),

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

 // CHECK-NEXT:   )
 // CHECK-NEXT: )
 def VariadicsOutTest : GICombineRule<
   (defs root:$a),
   (match (G_UNMERGE_VALUES $a, $b, $src)),
   (apply (COPY $a, (i32 0)),
          (COPY $b, (i32 0)))>;
 
+
 def MyCombiner: GICombiner<"GenMyCombiner", [
   WipOpcodeTest0,
   WipOpcodeTest1,
   InstTest0,
   InstTest1,
   InstTest2,
   InOutInstTest0,
   PatFragTest0,
   PatFragTest1,
   VariadicsInTest,
   VariadicsOutTest
 ]>;

llvm/utils/TableGen/GlobalISelCombinerEmitter.cpp

 cl::opt<bool> DebugCXXPreds(
     "gicombiner-debug-cxxpreds",
     cl::desc("Add Contextual/Debug comments to all C++ predicates"),
     cl::cat(GICombinerEmitterCat));
 
 constexpr StringLiteral CXXApplyPrefix = "GICXXCustomAction_CombineApply";
 constexpr StringLiteral CXXPredPrefix = "GICXXPred_MI_Predicate_";
 constexpr StringLiteral PatFragClassName = "GICombinePatFrag";
+constexpr StringLiteral BuiltinInstClassName = "GIBuiltinInst";
 
 std::string getIsEnabledPredicateEnumName(unsigned CombinerRuleID) {
   return "GICXXPred_Simple_IsRule" + to_string(CombinerRuleID) + "Enabled";
 }
 
 /// Copies a StringRef into a static pool to make sure it has a static lifetime.
 StringRef insertStrRef(StringRef S) {
   if (S.empty())

 class Pattern {
 public:
   enum {
     K_AnyOpcode,
     K_CXX,
 
     K_CodeGenInstruction,
     K_PatFrag,
+    K_Builtin,
   };
 
   virtual ~Pattern() = default;
 
   unsigned getKind() const { return Kind; }
   const char *getKindName() const;
 
   bool hasName() const { return !Name.empty(); }
const char *Pattern::getKindName() const {
   case K_AnyOpcode:
     return "AnyOpcodePattern";
   case K_CXX:
     return "CXXPattern";
   case K_CodeGenInstruction:
     return "CodeGenInstructionPattern";
   case K_PatFrag:
     return "PatFragPattern";
+  case K_Builtin:
+    return "BuiltinPattern";
   }
 
   llvm_unreachable("unknown pattern kind!");
 }
 
 void Pattern::printImpl(raw_ostream &OS, bool PrintName,
                         function_ref<void()> ContentPrinter) const {
   OS << "(" << getKindName() << " ";

 /// Base class for CodeGenInstructionPattern & PatFragPattern, which handles all
 /// the boilerplate for patterns that have a list of operands for some (pseudo)
 /// instruction.
 class InstructionPattern : public Pattern {
 public:
   virtual ~InstructionPattern() = default;
 
   static bool classof(const Pattern *P) {
-    return P->getKind() == K_CodeGenInstruction || P->getKind() == K_PatFrag;
+    return P->getKind() == K_CodeGenInstruction || P->getKind() == K_PatFrag ||
+           P->getKind() == K_Builtin;
   }
 
   template <typename... Ty> void addOperand(Ty &&...Init) {
     Operands.emplace_back(std::forward<Ty>(Init)...);
   }
 
   auto &operands() { return Operands; }
   const auto &operands() const { return Operands; }
   unsigned operands_size() const { return Operands.size(); }
   InstructionOperand &getOperand(unsigned K) { return Operands[K]; }
   const InstructionOperand &getOperand(unsigned K) const { return Operands[K]; }
 
   /// When this InstructionPattern is used as the match root, returns the
   /// operands that must be redefined in the 'apply' pattern for the rule to be
   /// valid.
   ///
-  /// For CodeGenInstructionPatterns, this just returns the defs of the CGI.
+  /// For most patterns, this just returns the defs.
   /// For PatFrag this only returns the root of the PF.
   ///
   /// Returns an empty array on error.
-  virtual ArrayRef<InstructionOperand> getApplyDefsNeeded() const = 0;
+  virtual ArrayRef<InstructionOperand> getApplyDefsNeeded() const {
+    return {operands().begin(), getNumInstDefs()};
+  }
 
   auto named_operands() {
     return make_filter_range(Operands,
                              [&](auto &O) { return O.isNamedOperand(); });
   }
 
   auto named_operands() const {
     return make_filter_range(Operands,
bool is(StringRef OpcodeName) const {
     return I.TheDef->getName() == OpcodeName;
   }
 
   bool hasVariadicDefs() const;
   bool isVariadic() const override { return I.Operands.isVariadic; }
   unsigned getNumInstDefs() const override;
   unsigned getNumInstOperands() const override;
 
-  ArrayRef<InstructionOperand> getApplyDefsNeeded() const override;
-
   const CodeGenInstruction &getInst() const { return I; }
   StringRef getInstName() const override { return I.TheDef->getName(); }
 
 private:
   const CodeGenInstruction &I;
 };
 
 bool CodeGenInstructionPattern::hasVariadicDefs() const {

 }
 
 unsigned CodeGenInstructionPattern::getNumInstOperands() const {
   unsigned NumCGIOps = I.Operands.size();
   return isVariadic() ? std::max<unsigned>(NumCGIOps, Operands.size())
                       : NumCGIOps;
 }
 
-ArrayRef<InstructionOperand>
-CodeGenInstructionPattern::getApplyDefsNeeded() const {
-  return {operands().begin(), getNumInstDefs()};
-}
-
 //===- OperandTypeChecker -------------------------------------------------===//
 
 /// This is a trivial type checker for all operands in a set of
 /// InstructionPatterns.
 ///
 /// It infers the type of each operand, check it's consistent with the known
 /// type of the operand, and then sets all of the types in all operands in
 /// setAllOperandTypes.
public:
   ///
   /// Each argument to the `pattern` DAG operator is parsed into a Pattern
   /// instance.
   struct Alternative {
     OperandTable<> OpTable;
     SmallVector<std::unique_ptr<Pattern>, 4> Pats;
   };
 
-  PatFrag(const Record &Def) : Def(Def) {}
+  explicit PatFrag(const Record &Def) : Def(Def) {
+    assert(Def.isSubClassOf(PatFragClassName));
+  }
 
   static StringRef getParamKindStr(ParamKind OK);
 
   StringRef getName() const { return Def.getName(); }
 
   const Record &getDef() const { return Def; }
   ArrayRef<SMLoc> getLoc() const { return Def.getLoc(); }
 

 
 bool PatFrag::checkSemantics() {
   for (const auto &Alt : Alts) {
     for (const auto &Pat : Alt.Pats) {
       switch (Pat->getKind()) {
       case Pattern::K_AnyOpcode:
         PrintError("wip_match_opcode cannot be used in " + PatFragClassName);
         return false;
+      case Pattern::K_Builtin:
+        PrintError("Builtin instructions cannot be used in " +
+                   PatFragClassName);
+        return false;
       case Pattern::K_CXX:
       case Pattern::K_CodeGenInstruction:
         continue;
       case Pattern::K_PatFrag:
         // TODO: It's just that the emitter doesn't handle it but technically
         // there is no reason why we can't. We just have to be careful with
         // operand mappings, it could get complex.
         PrintError("nested " + PatFragClassName + " are not supported");
for (const auto &[Idx, Op] : enumerate(operands())) {
     }
 
     llvm_unreachable("Unknown Operand Type!");
   }
 
   return true;
 }
 
+//===- BuiltinPattern -----------------------------------------------------===//
+
+enum BuiltinKind {
+  BI_ReplaceReg,
+  BI_EraseRoot,
+};
+
+class BuiltinPattern : public InstructionPattern {
+  struct BuiltinInfo {
+    StringLiteral DefName;
+    BuiltinKind Kind;
+    unsigned NumOps;
+    unsigned NumDefs;
+  };
+
+  static constexpr std::array<BuiltinInfo, 2> KnownBuiltins = {{
+      {"GIReplaceReg", BI_ReplaceReg, 2, 1},
+      {"GIEraseRoot", BI_EraseRoot, 0, 0},
+  }};
+
+public:
+  BuiltinPattern(const Record &Def, StringRef Name)
+      : InstructionPattern(K_Builtin, Name), I(getBuiltinInfo(Def)) {}
+
+  static bool classof(const Pattern *P) { return P->getKind() == K_Builtin; }
+
+  unsigned getNumInstOperands() const override { return I.NumOps; }
+  unsigned getNumInstDefs() const override { return I.NumDefs; }
+  StringRef getInstName() const override { return I.DefName; }
+  BuiltinKind getBuiltinKind() const { return I.Kind; }
+
+  bool checkSemantics(ArrayRef<SMLoc> Loc) override;
+
+private:
+  static BuiltinInfo getBuiltinInfo(const Record &Def);
+
+  BuiltinInfo I;
+};
+
+BuiltinPattern::BuiltinInfo BuiltinPattern::getBuiltinInfo(const Record &Def) {
+  assert(Def.isSubClassOf(BuiltinInstClassName));
+
+  StringRef Name = Def.getName();
+  for (const auto &KBI : KnownBuiltins) {
+    if (KBI.DefName == Name)
+      return KBI;
+  }
+
+  PrintFatalError(Def.getLoc(), "Unimplemented " + BuiltinInstClassName +
+                                    " def '" + Name + "'");
+}
+
+bool BuiltinPattern::checkSemantics(ArrayRef<SMLoc> Loc) {
+  if (!InstructionPattern::checkSemantics(Loc))
+    return false;
+
+  // For now all builtins just take names, no immediates.
+  for (const auto &[Idx, Op] : enumerate(operands())) {
+    if (!Op.isNamedOperand() || Op.isNamedImmediate()) {
+      PrintError(Loc, "expected operand " + to_string(Idx) + " of '" +
+                          getInstName() + "' to be a name");
+      return false;
+    }
+  }
+
+  return true;
+}
+
 //===- PrettyStackTrace Helpers  ------------------------------------------===//
 
 class PrettyStackTraceParse : public PrettyStackTraceEntry {
   const Record &Def;
 
 public:
   PrettyStackTraceParse(const Record &Def) : Def(Def) {}
 
private:
   void addCXXPredicate(RuleMatcher &M, const CodeExpansions &CE,
                        const CXXPattern &P, const PatternAlternatives &Alts);
 
   /// Adds an apply \p P to \p IM, expanding its code using \p CE.
   void addCXXAction(RuleMatcher &M, const CodeExpansions &CE,
                     const CXXPattern &P);
 
   bool hasOnlyCXXApplyPatterns() const;
-  bool hasAnyOpcodeMatchPattern() const {
-    return any_of(MatchPats, [&](const auto &E) {
-      return isa<AnyOpcodePattern>(E.second.get());
-    });
-  }
+  bool hasEraseRoot() const;
 
   // Infer machine operand types and check their consistency.
   bool typecheckPatterns();
 
   /// For all PatFragPatterns, add a new entry in PatternAlternatives for each
   /// PatternList it contains. This is multiplicative, so if we have 2
   /// PatFrags with 3 alternatives each, we get 2*3 permutations added to
   /// PermutationsToEmit. The "MaxPermutations" field controls how many
   /// permutations are allowed before an error is emitted and this function
   /// returns false. This is a simple safeguard to prevent combination of
   /// PatFrags from generating enormous amounts of rules.
   bool buildPermutationsToEmit();
 
+  /// Checks additional semantics of the Patterns.
+  bool checkSemantics();
+
   /// Creates a new RuleMatcher with some boilerplate
   /// settings/actions/predicates, and and adds it to \p OutRMs.
   /// \see addFeaturePredicates too.
   ///
   /// \param Alts Current set of alternatives, for debug comment.
   /// \param AdditionalComment Comment string to be added to the
   ///        `DebugCommentAction`.
   RuleMatcher &addRuleMatcher(const PatternAlternatives &Alts,
private:
   bool emitPatFragMatchPattern(CodeExpansions &CE,
                                const PatternAlternatives &Alts, RuleMatcher &RM,
                                InstructionMatcher *IM,
                                const PatFragPattern &PFP,
                                DenseSet<const Pattern *> &SeenPats);
 
   bool emitApplyPatterns(CodeExpansions &CE, RuleMatcher &M);
 
-  // Recursively visits CodeGenInstructionPattern from P to build up the
+  // Recursively visits InstructionPatterns from P to build up the
   // RuleMatcher actions.
-  bool
-  emitCodeGenInstructionApplyPattern(CodeExpansions &CE, RuleMatcher &M,
-                                     const CodeGenInstructionPattern &P,
-                                     DenseSet<const Pattern *> &SeenPats,
-                                     StringMap<unsigned> &OperandToTempRegID);
+  bool emitInstructionApplyPattern(CodeExpansions &CE, RuleMatcher &M,
+                                   const InstructionPattern &P,
 
   bool emitCodeGenInstructionApplyImmOperand(RuleMatcher &M,
                                              BuildMIAction &DstMI,
                                              const CodeGenInstructionPattern &P,
                                              const InstructionOperand &O);
 
+  bool emitBuiltinApplyPattern(CodeExpansions &CE, RuleMatcher &M,
+                               const BuiltinPattern &P,
+                               StringMap<unsigned> &OperandToTempRegID);
+
   // Recursively visits CodeGenInstructionPattern from P to build up the
   // RuleMatcher/InstructionMatcher. May create new InstructionMatchers as
   // needed.
   using OperandMapperFnRef =
       function_ref<InstructionOperand(const InstructionOperand &)>;
   using OperandDefLookupFn =
       function_ref<const InstructionPattern *(StringRef)>;
   bool emitCodeGenInstructionMatchPattern(
private:
 
   /// These maps have ownership of the actual Pattern objects.
   /// They both map a Pattern's name to the Pattern instance.
   PatternMap MatchPats;
   PatternMap ApplyPats;
 
   /// Operand tables to tie match/apply patterns together.
   OperandTable<> MatchOpTable;
-  OperandTable<CodeGenInstructionPattern> ApplyOpTable;
+  OperandTable<> ApplyOpTable;
 
   /// Set by findRoots.
   Pattern *MatchRoot = nullptr;
   SmallDenseSet<InstructionPattern *, 2> ApplyRoots;
 
   SmallVector<MatchDataInfo, 2> MatchDatas;
   SmallVector<PatternAlternatives, 1> PermutationsToEmit;
 
bool CombineRuleBuilder::parseAll() {
 
   if (!parsePatternList(
           *RuleDef.getValueAsDag("Apply"),
           [this](auto Pat) { return addApplyPattern(std::move(Pat)); }, "apply",
           RuleDef.getLoc(), (RuleDef.getName() + "_apply").str()))
     return false;
 
   if (!buildRuleOperandsTable() || !typecheckPatterns() || !findRoots() ||
-      !buildPermutationsToEmit())
+      !checkSemantics() || !buildPermutationsToEmit())
     return false;
   LLVM_DEBUG(verify());
   return true;
 }
 
 bool CombineRuleBuilder::emitRuleMatchers() {
   auto StackTrace = PrettyStackTraceEmit(RuleDef);
 
   assert(MatchRoot);
   CodeExpansions CE;
   declareAllMatchDatasExpansions(CE);
 
   assert(!PermutationsToEmit.empty());
   for (const auto &Alts : PermutationsToEmit) {
     switch (MatchRoot->getKind()) {
     case Pattern::K_AnyOpcode: {
       if (!emitMatchPattern(CE, Alts, *cast<AnyOpcodePattern>(MatchRoot)))
         return false;
       break;
     }
     case Pattern::K_PatFrag:
+    case Pattern::K_Builtin:
     case Pattern::K_CodeGenInstruction:
       if (!emitMatchPattern(CE, Alts, *cast<InstructionPattern>(MatchRoot)))
         return false;
       break;
     case Pattern::K_CXX:
       PrintError("C++ code cannot be the root of a rule!");
       return false;
     default:
bool CombineRuleBuilder::addApplyPattern(std::unique_ptr<Pattern> Pat) {
   }
 
   if (isa<AnyOpcodePattern>(Pat.get())) {
     PrintError("'" + Name +
                "': wip_match_opcode is not supported in apply patterns");
     return false;
   }
 
-  if (isa<InstructionPattern>(Pat.get())) {
-    if (hasAnyOpcodeMatchPattern()) {
-      PrintError("cannot use wip_match_opcode in combination with apply "
-                 "instruction patterns!");
-      return false;
-    }
-
-    if (isa<PatFragPattern>(Pat.get())) {
-      PrintError("'" + Name + "': using " + PatFragClassName +
-                 " is not supported in apply patterns");
-      return false;
-    }
-  }
 
   if (auto *CXXPat = dyn_cast<CXXPattern>(Pat.get()))
     CXXPat->setIsApply();
 
   ApplyPats[Name] = std::move(Pat);
   return true;
 }
 
 bool CombineRuleBuilder::addMatchPattern(std::unique_ptr<Pattern> Pat) {
   StringRef Name = Pat->getName();
   if (MatchPats.contains(Name)) {
     PrintError("'" + Name + "' match pattern defined more than once!");
     return false;
   }
 
-  // TODO: Could move this to some "checkSemantics" method?
-  if (isa<AnyOpcodePattern>(Pat.get())) {
-    if (hasAnyOpcodeMatchPattern()) {
-      PrintError("wip_opcode_match can only be present once");
-      return false;
-    }
-  }
-
-  if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat.get())) {
-    if (!CXXPat->getRawCode().contains("return ")) {
-      PrintWarning("'match' C++ code does not seem to return!");
-    }
-  }
+  // For now, none of the builtins can appear in 'match'.
+  if (const auto *BP = dyn_cast<BuiltinPattern>(Pat.get())) {
+    PrintError("'" + BP->getInstName() +
+               "' cannot be used in a 'match' pattern");
 
   MatchPats[Name] = std::move(Pat);
   return true;
 }
 
 void CombineRuleBuilder::declareAllMatchDatasExpansions(
     CodeExpansions &CE) const {
   for (const auto &MD : MatchDatas)

 }
 
 bool CombineRuleBuilder::hasOnlyCXXApplyPatterns() const {
   return all_of(ApplyPats, [&](auto &Entry) {
     return isa<CXXPattern>(Entry.second.get());
   });
 }
 
+bool CombineRuleBuilder::hasEraseRoot() const {
+  return any_of(ApplyPats, [&](auto &Entry) {
+    if (const auto *BP = dyn_cast<BuiltinPattern>(Entry.second.get()))
+      return BP->getBuiltinKind() == BI_EraseRoot;
+    return false;
+  });
+}
+
 bool CombineRuleBuilder::typecheckPatterns() {
   OperandTypeChecker OTC(RuleDef.getLoc());
 
   for (auto &Pat : values(MatchPats)) {
     if (auto *IP = dyn_cast<InstructionPattern>(Pat.get())) {
       if (!OTC.check(IP))
         return false;
     }
bool CombineRuleBuilder::buildPermutationsToEmit() {
   if (PermutationsToEmit.empty()) {
     PermutationsToEmit.emplace_back();
     return true;
   }
 
   return true;
 }
 
+bool CombineRuleBuilder::checkSemantics() {
+  assert(MatchRoot && "Cannot call this before findRoots()");
+
+  bool UsesWipMatchOpcode = false;
+  for (const auto &Match : MatchPats) {
+    const auto *Pat = Match.second.get();
+
+    if (const auto *CXXPat = dyn_cast<CXXPattern>(Pat)) {
+      if (!CXXPat->getRawCode().contains("return "))
+        PrintWarning("'match' C++ code does not seem to return!");
+      continue;
+    }
+
+    const auto *AOP = dyn_cast<AnyOpcodePattern>(Pat);
+    if (!AOP)
+      continue;
+
+    if (UsesWipMatchOpcode) {
+      PrintError("wip_opcode_match can only be present once");
+      return false;
+    }
+
+    UsesWipMatchOpcode = true;
+  }
+
+  for (const auto &Apply : ApplyPats) {
+    assert(Apply.second.get());
+    const auto *IP = dyn_cast<InstructionPattern>(Apply.second.get());
+    if (!IP)
+      continue;
+
+    if (UsesWipMatchOpcode) {
+      PrintError("cannot use wip_match_opcode in combination with apply "
+                 "instruction patterns!");
+      return false;
+    }
+
+    const auto *BIP = dyn_cast<BuiltinPattern>(IP);
+    if (!BIP)
+      continue;
+    StringRef Name = BIP->getInstName();
+
+    // (GIEraseInst) has to be the only apply pattern, or it can not be used at
+    // all. The root cannot have any defs either.
+    switch (BIP->getBuiltinKind()) {
+    case BI_EraseRoot: {
+      if (ApplyPats.size() > 1) {
+        PrintError(Name + " must be the only 'apply' pattern");
+        return false;
+      }
+
+      const auto *IRoot = dyn_cast<CodeGenInstructionPattern>(MatchRoot);
+      if (!IRoot) {
+        PrintError(Name +
+                   " can only be used if the root is a CodeGenInstruction");
+        return false;
+      }
+
+      if (IRoot->getNumInstDefs() != 0) {
+        PrintError(Name + " can only be used if on roots that do "
+                          "not have any output operand");
+        PrintNote("'" + IRoot->getInstName() + "' has " +
+                  Twine(IRoot->getNumInstDefs()) + " output operands");
+        return false;
+      }
+      break;
+    }
+    case BI_ReplaceReg: {
+      // (GIReplaceReg can only be used on the root instruction)
+      // TODO: When we allow rewriting non-root instructions, also allow this.
+      StringRef OldRegName = BIP->getOperand(0).getOperandName();
+      auto *Def = MatchOpTable.getDef(OldRegName);
+      if (!Def) {
+        PrintError(Name + " cannot find a matched pattern that defines '" +
+                   OldRegName + "'");
+        return false;
+      }
+      if (MatchOpTable.getDef(OldRegName) != MatchRoot) {
+        PrintError(Name + " cannot replace '" + OldRegName +
+                   "': this builtin can only replace a register defined by the "
+                   "match root");
+        return false;
+      }
+      break;
+    }
+    }
+  }
+
+  return true;
+}
+
 RuleMatcher &CombineRuleBuilder::addRuleMatcher(const PatternAlternatives &Alts,
                                                 Twine AdditionalComment) {
   auto &RM = OutRMs.emplace_back(RuleDef.getLoc());
   addFeaturePredicates(RM);
   RM.setPermanentGISelFlags(GISF_IgnoreCopies);
   RM.addRequiredSimplePredicate(getIsEnabledPredicateEnumName(RuleID));
 
   std::string Comment;
bool CombineRuleBuilder::addFeaturePredicates(RuleMatcher &M) {
 
   return true;
 }
 
 bool CombineRuleBuilder::findRoots() {
   const auto Finish = [&]() {
     assert(MatchRoot);
 
-    if (hasOnlyCXXApplyPatterns())
+    if (hasOnlyCXXApplyPatterns() || hasEraseRoot())
       return true;
 
     auto *IPRoot = dyn_cast<InstructionPattern>(MatchRoot);
     if (!IPRoot)
       return true;
 
     if (IPRoot->getNumInstDefs() == 0) {
       // No defs to work with -> find the root using the pattern name.
bool CombineRuleBuilder::buildRuleOperandsTable() {
 
   for (auto &Pat : values(MatchPats)) {
     auto *IP = dyn_cast<InstructionPattern>(Pat.get());
     if (IP && !MatchOpTable.addPattern(IP, DiagnoseRedefMatch))
       return false;
   }
 
   for (auto &Pat : values(ApplyPats)) {
-    auto *IP = dyn_cast<CodeGenInstructionPattern>(Pat.get());
+    auto *IP = dyn_cast<InstructionPattern>(Pat.get());
     if (IP && !ApplyOpTable.addPattern(IP, DiagnoseRedefApply))
       return false;
   }
 
   return true;
 }
 
 bool CombineRuleBuilder::parseDefs(const DagInit &Def) {
if (const DagInit *IP = getDagWithOperatorOfSubClass(Arg, "Instruction")) {
     Pat = std::make_unique<CodeGenInstructionPattern>(Instr, Name);
   } else if (const DagInit *PFP =
                  getDagWithOperatorOfSubClass(Arg, PatFragClassName)) {
     const Record *Def = PFP->getOperatorAsDef(RuleDef.getLoc());
     const PatFrag *PF = parsePatFrag(Def);
     if (!PF)
       return nullptr; // Already diagnosed by parsePatFrag
     Pat = std::make_unique<PatFragPattern>(*PF, Name);
+  } else if (const DagInit *BP =
+                 getDagWithOperatorOfSubClass(Arg, BuiltinInstClassName)) {
+    Pat = std::make_unique<BuiltinPattern>(
+        *BP->getOperatorAsDef(RuleDef.getLoc()), Name);
   } else {
     return nullptr;
   }
 
   for (unsigned K = 0; K < DagPat->getNumArgs(); ++K) {
     if (!parseInstructionPatternOperand(*Pat, DagPat->getArg(K),
                                         DagPat->getArgName(K)))
       return nullptr;
bool CombineRuleBuilder::emitMatchPattern(CodeExpansions &CE,
   } else if (const auto *PFP = dyn_cast<PatFragPattern>(&IP)) {
     if (!PFP->getPatFrag().canBeMatchRoot()) {
       PrintError("cannot use '" + PFP->getInstName() + " as match root");
       return false;
     }
 
     if (!emitPatFragMatchPattern(CE, Alts, M, &IM, *PFP, SeenPats))
       return false;
+  } else if (isa<BuiltinPattern>(&IP)) {
+    llvm_unreachable("No match builtins known!");
   } else
     llvm_unreachable("Unknown kind of InstructionPattern!");
 
   // Emit remaining patterns
   for (auto &Pat : values(MatchPats)) {
     if (SeenPats.contains(Pat.get()))
       continue;
 
     switch (Pat->getKind()) {
     case Pattern::K_AnyOpcode:
       PrintError("wip_match_opcode can not be used with instruction patterns!");
       return false;
     case Pattern::K_PatFrag: {
       if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,
                                    *cast<PatFragPattern>(Pat.get()), SeenPats))
         return false;
       continue;
     }
+    case Pattern::K_Builtin:
+      PrintError("No known match builtins");
+      return false;
     case Pattern::K_CodeGenInstruction:
       cast<InstructionPattern>(Pat.get())->reportUnreachable(RuleDef.getLoc());
       return false;
     case Pattern::K_CXX: {
       addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);
       continue;
     }
     default:
for (auto &Pat : values(MatchPats)) {
       case Pattern::K_PatFrag: {
         DenseSet<const Pattern *> SeenPats;
         if (!emitPatFragMatchPattern(CE, Alts, M, /*IM*/ nullptr,
                                      *cast<PatFragPattern>(Pat.get()),
                                      SeenPats))
           return false;
         continue;
       }
+      case Pattern::K_Builtin:
+        PrintError("No known match builtins");
+        return false;
       case Pattern::K_CodeGenInstruction:
         cast<InstructionPattern>(Pat.get())->reportUnreachable(
             RuleDef.getLoc());
         return false;
       case Pattern::K_CXX: {
         addCXXPredicate(M, CE, *cast<CXXPattern>(Pat.get()), Alts);
         break;
       }
for (auto &Pat : values(ApplyPats))
       addCXXAction(M, CE, *cast<CXXPattern>(Pat.get()));
     return true;
   }
 
   DenseSet<const Pattern *> SeenPats;
   StringMap<unsigned> OperandToTempRegID;
 
   for (auto *ApplyRoot : ApplyRoots) {
-    assert(isa<CodeGenInstructionPattern>(ApplyRoot) &&
-           "PatFragPatterns are not supported in apply patterns yet!");
-    if (!emitCodeGenInstructionApplyPattern(
-            CE, M, *cast<CodeGenInstructionPattern>(ApplyRoot), SeenPats,
-            OperandToTempRegID))
+    assert(isa<InstructionPattern>(ApplyRoot) &&
+           "Root can only be a InstructionPattern!");
+    if (!emitInstructionApplyPattern(CE, M,
+                                     cast<InstructionPattern>(*ApplyRoot),
+                                     SeenPats, OperandToTempRegID))
       return false;
   }
 
   for (auto &Pat : values(ApplyPats)) {
     if (SeenPats.contains(Pat.get()))
       continue;
 
     switch (Pat->getKind()) {
     case Pattern::K_AnyOpcode:
       llvm_unreachable("Unexpected pattern in apply!");
     case Pattern::K_PatFrag:
       // TODO: We could support pure C++ PatFrags as a temporary thing.
       llvm_unreachable("Unexpected pattern in apply!");
+    case Pattern::K_Builtin:
+      if (!emitInstructionApplyPattern(CE, M, cast<BuiltinPattern>(*Pat),
+                                       SeenPats, OperandToTempRegID))
+        return false;
+      break;
     case Pattern::K_CodeGenInstruction:
-      cast<CodeGenInstructionPattern>(Pat.get())->reportUnreachable(
-          RuleDef.getLoc());
+      cast<CodeGenInstructionPattern>(*Pat).reportUnreachable(RuleDef.getLoc());
       return false;
     case Pattern::K_CXX: {
       addCXXAction(M, CE, *cast<CXXPattern>(Pat.get()));
       continue;
     }
     default:
       llvm_unreachable("unknown pattern kind!");
     }
   }
 
   return true;
 }
 
-bool CombineRuleBuilder::emitCodeGenInstructionApplyPattern(
-    CodeExpansions &CE, RuleMatcher &M, const CodeGenInstructionPattern &P,
+bool CombineRuleBuilder::emitInstructionApplyPattern(
+    CodeExpansions &CE, RuleMatcher &M, const InstructionPattern &P,
     DenseSet<const Pattern *> &SeenPats,
     StringMap<unsigned> &OperandToTempRegID) {
   auto StackTrace = PrettyStackTraceEmit(RuleDef, &P);
 
   if (SeenPats.contains(&P))
     return true;
 
   SeenPats.insert(&P);
 
   // First, render the uses.
   for (auto &Op : P.named_operands()) {
     if (Op.isDef())
       continue;
 
     StringRef OpName = Op.getOperandName();
     if (const auto *DefPat = ApplyOpTable.getDef(OpName)) {
-      if (!emitCodeGenInstructionApplyPattern(CE, M, *DefPat, SeenPats,
-                                              OperandToTempRegID))
+      if (!emitInstructionApplyPattern(CE, M, *DefPat, SeenPats,
         return false;
     } else {
       // If we have no def, check this exists in the MatchRoot.
       if (!Op.isNamedImmediate() && !MatchOpTable.lookup(OpName).Found) {
         PrintError("invalid output operand '" + OpName +
                    "': operand is not a live-in of the match pattern, and it "
                    "has no definition");
         return false;
       }
     }
   }
 
+  if (const auto *BP = dyn_cast<BuiltinPattern>(&P))
+    return emitBuiltinApplyPattern(CE, M, *BP, OperandToTempRegID);
+
+  if (isa<PatFragPattern>(&P))
+    llvm_unreachable("PatFragPatterns is not supported in 'apply'!");
+
+  auto &CGIP = cast<CodeGenInstructionPattern>(P);
+
   // Now render this inst.
   auto &DstMI =
-      M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &P.getInst());
+      M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &CGIP.getInst());
 
   for (auto &Op : P.operands()) {
     if (Op.isNamedImmediate()) {
       PrintError("invalid output operand '" + Op.getOperandName() +
                  "': output immediates cannot be named");
       PrintNote("while emitting pattern '" + P.getName() + "' (" +
                 P.getInstName() + ")");
       return false;
     }
 
     if (Op.hasImmValue()) {
-      if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, P, Op))
+      if (!emitCodeGenInstructionApplyImmOperand(M, DstMI, CGIP, Op))
         return false;
       continue;
     }
 
     StringRef OpName = Op.getOperandName();
 
     // Uses of operand.
     if (!Op.isDef()) {
bool CombineRuleBuilder::emitCodeGenInstructionApplyImmOperand(
   M.insertAction<MakeTempRegisterAction>(ActIt, LLT, TempRegID);
   auto &ConstantMI = *static_cast<BuildMIAction *>(ActIt->get());
   ConstantMI.addRenderer<TempRegRenderer>(TempRegID);
   ConstantMI.addRenderer<ImmRenderer>(O.getImmValue(), LLT);
   DstMI.addRenderer<TempRegRenderer>(TempRegID);
   return true;
 }
 
+bool CombineRuleBuilder::emitBuiltinApplyPattern(
+    CodeExpansions &CE, RuleMatcher &M, const BuiltinPattern &P,
+    StringMap<unsigned> &OperandToTempRegID) {
+  const auto Error = [&](Twine Reason) {
+    PrintError("cannot emit '" + P.getInstName() + "' builtin: " + Reason);
+    return false;
+  };
+
+  switch (P.getBuiltinKind()) {
+  case BI_EraseRoot: {
+    // Root is always inst 0.
+    M.addAction<EraseInstAction>(/*InsnID*/ 0);
+    return true;
+  }
+  case BI_ReplaceReg: {
+    StringRef Old = P.getOperand(0).getOperandName();
+    StringRef New = P.getOperand(1).getOperandName();
+
+    if (!ApplyOpTable.lookup(New).Found && !MatchOpTable.lookup(New).Found)
+      return Error("unknown operand '" + Old + "'");
+
+    auto &OldOM = M.getOperandMatcher(Old);
+    if (auto It = OperandToTempRegID.find(New);
+        It != OperandToTempRegID.end()) {
+      // Replace with temp reg.
+      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),
+                                    It->second);
+    } else {
+      // Replace with matched reg.
+      auto &NewOM = M.getOperandMatcher(New);
+      M.addAction<ReplaceRegAction>(OldOM.getInsnVarID(), OldOM.getOpIdx(),
+                                    NewOM.getInsnVarID(), NewOM.getOpIdx());
+    }
+    // checkSemantics should have ensured that we can only rewrite the root.
+    // Ensure we're deleting it.
+    assert(MatchOpTable.getDef(Old) == MatchRoot);
+    // TODO: We could avoid adding the action again if it's already in. The
+    // MatchTable is smart enough to only emit one opcode even if
+    // EraseInstAction is present multiple times. I think searching for a copy
+    // is more expensive than just blindly adding it though.
+    M.addAction<EraseInstAction>(/*InsnID*/ 0);
+
+    return true;
+  }
+  }
+
+  llvm_unreachable("Unknown BuiltinKind!");
+}
+
 bool isLiteralImm(const InstructionPattern &P, unsigned OpIdx) {
   if (const auto *CGP = dyn_cast<CodeGenInstructionPattern>(&P)) {
     StringRef InstName = CGP->getInst().TheDef->getName();
     return (InstName == "G_CONSTANT" || InstName == "G_FCONSTANT") &&
            OpIdx == 1;
   }
 
   llvm_unreachable("TODO");

llvm/utils/TableGen/GlobalISelMatchTable.h

protected:
 
   /// Current GISelFlags
   GISelFlags Flags = 0;
 
   std::vector<std::string> RequiredSimplePredicates;
   std::vector<Record *> RequiredFeatures;
   std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
 
+  DenseSet<unsigned> ErasedInsnIDs;
+
   ArrayRef<SMLoc> SrcLoc;
 
   typedef std::tuple<Record *, unsigned, unsigned>
       DefinedComplexPatternSubOperand;
   typedef StringMap<DefinedComplexPatternSubOperand>
       DefinedComplexPatternSubOperandMap;
   /// A map of Symbolic Names to ComplexPattern sub-operands.
   DefinedComplexPatternSubOperandMap ComplexSubOperands;
public:
   const std::vector<Record *> &getRequiredFeatures() const;
 
   void addHwModeIdx(unsigned Idx) { HwModeIdx = Idx; }
   int getHwModeIdx() const { return HwModeIdx; }
 
   void addRequiredSimplePredicate(StringRef PredName);
   const std::vector<std::string> &getRequiredSimplePredicates();
 
+  /// Attempts to mark \p ID as erased (GIR_EraseFromParent called on it).
+  /// If \p ID has already been erased, returns false and GIR_EraseFromParent
+  /// should NOT be emitted.
+  bool tryEraseInsnID(unsigned ID) { return ErasedInsnIDs.insert(ID).second; }
+
   // 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) {

 /// * Changing the opcode of an instruction.
 /// * Adding an operand to an instruction.
 class MatchAction {
 public:
   enum ActionKind {
     AK_DebugComment,
     AK_CustomCXX,
     AK_BuildMI,
+    AK_EraseInst,
+    AK_ReplaceReg,
     AK_ConstraintOpsToDef,
     AK_ConstraintOpsToRC,
     AK_MakeTempReg,
   };
 
   MatchAction(ActionKind K) : Kind(K) {}
 
   ActionKind getKind() const { return Kind; }
 
   virtual ~MatchAction() {}
 
+  // Some actions may need to add extra predicates to ensure they can run.
+  virtual void emitAdditionalPredicates(MatchTable &Table,
+                                        RuleMatcher &Rule) const {}
+
   /// Emit the MatchTable opcodes to implement the action.
   virtual void emitActionOpcodes(MatchTable &Table,
                                  RuleMatcher &Rule) const = 0;
 
 private:
   ActionKind Kind;
 };
 
template <class Kind, class... Args> Kind &addRenderer(Args &&...args) {
     OperandRenderers.emplace_back(
         std::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
     return *static_cast<Kind *>(OperandRenderers.back().get());
   }
 
   void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
 };
 
+class EraseInstAction : public MatchAction {
+  unsigned InsnID;
+
+public:
+  EraseInstAction(unsigned InsnID)
+      : MatchAction(AK_EraseInst), InsnID(InsnID) {}
+
+  static bool classof(const MatchAction *A) {
+    return A->getKind() == AK_EraseInst;
+  }
+
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
+  static void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                                unsigned InsnID);
+};
+
+class ReplaceRegAction : public MatchAction {
+  unsigned OldInsnID, OldOpIdx;
+  unsigned NewInsnId = -1, NewOpIdx;
+  unsigned TempRegID = -1;
+
+public:
+  ReplaceRegAction(unsigned OldInsnID, unsigned OldOpIdx, unsigned NewInsnId,
+                   unsigned NewOpIdx)
+      : MatchAction(AK_EraseInst), OldInsnID(OldInsnID), OldOpIdx(OldOpIdx),
+        NewInsnId(NewInsnId), NewOpIdx(NewOpIdx) {}
+
+  ReplaceRegAction(unsigned OldInsnID, unsigned OldOpIdx, unsigned TempRegID)
+      : MatchAction(AK_EraseInst), OldInsnID(OldInsnID), OldOpIdx(OldOpIdx),
+        TempRegID(TempRegID) {}
+
+  static bool classof(const MatchAction *A) {
+    return A->getKind() == AK_ReplaceReg;
+  }
+
+  void emitAdditionalPredicates(MatchTable &Table,
+                                RuleMatcher &Rule) const override;
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override;
+};
+
 /// Generates code to constrain the operands of an output instruction to the
 /// register classes specified by the definition of that instruction.
 class ConstrainOperandsToDefinitionAction : public MatchAction {
   unsigned InsnID;
 
 public:
   ConstrainOperandsToDefinitionAction(unsigned InsnID)
       : MatchAction(AK_ConstraintOpsToDef), InsnID(InsnID) {}

llvm/utils/TableGen/GlobalISelMatchTable.cpp

if (!RequiredSimplePredicates.empty()) {
     for (const auto &Pred : RequiredSimplePredicates) {
       Table << MatchTable::Opcode("GIM_CheckSimplePredicate")
             << MatchTable::NamedValue(Pred) << MatchTable::LineBreak;
     }
   }
 
   Matchers.front()->emitPredicateOpcodes(Table, *this);
 
+  // Check if it's safe to replace registers.
+  for (const auto &MA : Actions)
+    MA->emitAdditionalPredicates(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
       // sinking to meet it.
       if (Pair.first == Matchers.front().get())
if (I->mayLoad || I->mayStore) {
     Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
           << MatchTable::LineBreak;
   }
 
   // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
   //        better for combines. Particularly when there are multiple match
   //        roots.
   if (InsnID == 0)
-    Table << MatchTable::Opcode("GIR_EraseFromParent")
-          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
-          << MatchTable::LineBreak;
+    EraseInstAction::emitActionOpcodes(Table, Rule, /*InsnID*/ 0);
+}
+
+//===- EraseInstAction ----------------------------------------------------===//
+
+void EraseInstAction::emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                                        unsigned InsnID) {
+  // Avoid erasing the same inst twice.
+  if (!Rule.tryEraseInsnID(InsnID))
+    return;
+
 }
 
+void EraseInstAction::emitActionOpcodes(MatchTable &Table,
+                                        RuleMatcher &Rule) const {
+  emitActionOpcodes(Table, Rule, InsnID);
+}
+
+//===- ReplaceRegAction ---------------------------------------------------===//
+
+void ReplaceRegAction::emitAdditionalPredicates(MatchTable &Table,
+                                                RuleMatcher &Rule) const {
+  if (TempRegID != (unsigned)-1)
+    return;
+
+  Table << MatchTable::Opcode("GIM_CheckCanReplaceReg")
+        << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnID)
+        << MatchTable::Comment("OldOpIdx") << MatchTable::IntValue(OldOpIdx)
+        << MatchTable::Comment("NewInsnId") << MatchTable::IntValue(NewInsnId)
+        << MatchTable::Comment("NewOpIdx") << MatchTable::IntValue(NewOpIdx)
+        << MatchTable::LineBreak;
+}
+
+void ReplaceRegAction::emitActionOpcodes(MatchTable &Table,
+                                         RuleMatcher &Rule) const {
+  if (TempRegID != (unsigned)-1) {
+    Table << MatchTable::Opcode("GIR_ReplaceRegWithTempReg")
+          << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnID)
+          << MatchTable::Comment("OldOpIdx") << MatchTable::IntValue(OldOpIdx)
+          << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
+          << MatchTable::LineBreak;
+  } else {
+    Table << MatchTable::Opcode("GIR_ReplaceReg")
+          << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnID)
+          << MatchTable::Comment("OldOpIdx") << MatchTable::IntValue(OldOpIdx)
+          << MatchTable::Comment("NewInsnId") << MatchTable::IntValue(NewInsnId)
+          << MatchTable::Comment("NewOpIdx") << MatchTable::IntValue(NewOpIdx)
+          << MatchTable::LineBreak;
+  }
+}
+
 //===- ConstrainOperandToRegClassAction -----------------------------------===//
 
 void ConstrainOperandToRegClassAction::emitActionOpcodes(
     MatchTable &Table, RuleMatcher &Rule) const {
   Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
         << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
         << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
         << MatchTable::NamedValue(RC.getQualifiedIdName())