[globalisel][tablegen] Partially fix compile-time regressions by converting matcher to state-machine(s)

[dsanders]

Summary

Replace the matcher if-statements for each rule with a state-machine. This
significantly reduces compile time, memory allocations, and cumulative memory
allocation when compiling AArch64InstructionSelector.cpp.o after r303259 is
recommitted.

The following patches will expand on this further to fully fix the regressions.

[kristof.beyls]

Replace the matcher if-statements for each rule with a state-machine. This
significantly reduces compile time, memory allocations, and cumulative memory
allocation when compiling AArch64InstructionSelector.cpp.o after r303259 is
recommitted.

My guess is that the compiler compile time goes down simply because tablegen produces far less code?
Do you also have an insight of how using a state machine "interpreter" changes the run-time of the compiler itself compared to using the "directly-compiled" generated C++ code?
I can't predict really how the different tradeoffs in both approaches will affect the compiler's run-time performance in the end, so it would be nice to share insights you may have for this.

Also, if we end up using a state machine for this, I think it'd be a good idea to, after the design settles, write a blog post or something similar to explain how the state machine works, as I've heard from many people that reverse engineering the DAGISel-produced state machine was hard due to limited or no documentation on it.

[dsanders]

In D33758#769689, @kristof.beyls wrote:

Replace the matcher if-statements for each rule with a state-machine. This
significantly reduces compile time, memory allocations, and cumulative memory
allocation when compiling AArch64InstructionSelector.cpp.o after r303259 is
recommitted.

My guess is that the compiler compile time goes down simply because tablegen produces far less code?

That's right. Instead of generating C++ and having the compiler optimize a single massive function, it's compiling a single copy of each predicate and chaining them together with a table.

Do you also have an insight of how using a state machine "interpreter" changes the run-time of the compiler itself compared to using the "directly-compiled" generated C++ code?
I can't predict really how the different tradeoffs in both approaches will affect the compiler's run-time performance in the end, so it would be nice to share insights you may have for this.

I haven't measured it yet since the priority so far has been to get the compile times back down to a reasonable level. Once I've finished posting the patches for review I'll take a look at the run-time effect.

My intuition is that the compiler was unlikely to have optimized the previous implementation very well (particularly since it didn't inline the single-use lambdas) and assuming that's the case, the overhead of the interpreter is likely to be limited to the cost of the table lookups. It's possible that it will turn out to be faster since the previous implementation had no chance of fitting into an instruction cache whereas the new code may fit on some machines. On machines where it doesn't fit, some paths are more common than others so it may still be able to use the instruction cache better than the old implementation did.

Also, if we end up using a state machine for this, I think it'd be a good idea to, after the design settles, write a blog post or something similar to explain how the state machine works, as I've heard from many people that reverse engineering the DAGISel-produced state machine was hard due to limited or no documentation on it.

Ok.

[kristof.beyls]

In D33758#769748, @dsanders wrote:

In D33758#769689, @kristof.beyls wrote:

Replace the matcher if-statements for each rule with a state-machine. This
significantly reduces compile time, memory allocations, and cumulative memory
allocation when compiling AArch64InstructionSelector.cpp.o after r303259 is
recommitted.

My guess is that the compiler compile time goes down simply because tablegen produces far less code?

That's right. Instead of generating C++ and having the compiler optimize a single massive function, it's compiling a single copy of each predicate and chaining them together with a table.

Do you also have an insight of how using a state machine "interpreter" changes the run-time of the compiler itself compared to using the "directly-compiled" generated C++ code?
I can't predict really how the different tradeoffs in both approaches will affect the compiler's run-time performance in the end, so it would be nice to share insights you may have for this.

I haven't measured it yet since the priority so far has been to get the compile times back down to a reasonable level. Once I've finished posting the patches for review I'll take a look at the run-time effect.

My intuition is that the compiler was unlikely to have optimized the previous implementation very well (particularly since it didn't inline the single-use lambdas) and assuming that's the case, the overhead of the interpreter is likely to be limited to the cost of the table lookups. It's possible that it will turn out to be faster since the previous implementation had no chance of fitting into an instruction cache whereas the new code may fit on some machines. On machines where it doesn't fit, some paths are more common than others so it may still be able to use the instruction cache better than the old implementation did.

Also, if we end up using a state machine for this, I think it'd be a good idea to, after the design settles, write a blog post or something similar to explain how the state machine works, as I've heard from many people that reverse engineering the DAGISel-produced state machine was hard due to limited or no documentation on it.

Ok.

Thanks, that all makes sense.
I'm afraid I'll have to skip the detailed review of this and leave that to someone more up to speed with design of this part of GlobalISel.

[ab]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

65–73

Are all three opcodes necessary? It seems like we only need one, that defines an ID from an operand.

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

31

Should this be unsigned?

Also, is int64_t necessary? Seems like almost everything should fit in 16 bits. X86 is close to 15k opcodes, but we can complain when we emit something that doesn't fit. As for CheckInt, we can just encode the 64-bit value across 4 operands.

test/TableGen/GlobalISelEmitter.td

88

Add CHECK lines for ComplexPredicates, TypeObjects, Renderers? It's not crucial for testing, but it's helpful for reading.

utils/TableGen/GlobalISelEmitter.cpp

2082–2091

Instead of a hardcoded list, MVTToLLT whatever can be converted in MVT::all_valuetypes() ?

[dsanders]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

65–73

I think there's a potential argument for merging GIM_RecordInsn and GIM_PushInsnOpDef. They're currently separate because I wasn't completely convinced that all visited instructions needed to be recorded. I'm leaning towards all of them being recorded but I decided to come back to that once the compile-time regression was resolved.

GIM_PopInsn needs to be kept separate for the current DAG walking code. Without it we wouldn't be able to walk something like:

(G_MUL (G_ADD a, b), (G_ADD c, d))

since once you descend into either G_ADD you wouldn't be able to visit the other. That said, I agree that tweaking GIM_PushInsnOpDef so that it takes a source instruction ID would achieve the same effect.

Are you ok with me working on this change as an optimisation after the compile-time regression fixes are committed? Currently all my work is bottlenecked on that.

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

31

Should this be unsigned?

It needs to be signed at the moment but the reason isn't a particularly good one: GIM_CheckInt takes a signed integer immediate straight from the table.

Also, is int64_t necessary?

For most things no, but it's necessary for GIM_CheckInt at the moment. Narrowing the type is a size optimization that I decided to leave for after the compile-time issue was resolved since all the tablegen work is bottlenecked on it.

utils/TableGen/GlobalISelEmitter.cpp

2082–2091

This is another size optimization I left for later. I'd like this table to be created based on the calls to LLTCodeGen's constructor. This will make the table much smaller for most targets since many of these types are only needed on X86.

[rovka]

Not for this patch, but I feel like some of the names and comments (e.g. emitCxxCaptureStmts) are starting to drift a bit from the implementation. Maybe at the end of this patch stack you could look into brushing them up?

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

65–73

That looks like a good test case to add :)

I'm still not convinced that you need a stack though, can't you just record all instructions (as you said you are inclined to do anyway) and express everything in terms of InsnIDs?

168

Maybe put the Renderers, TypeObjects etc into a struct, so we don't have to change this signature every time we want to add or modify a state.

If not, at least consider using ArrayRef's for them.

test/TableGen/GlobalISelEmitter.td

141

Nitpick: "RegClassID, " (just so it matches the others).

utils/TableGen/GlobalISelEmitter.cpp

256–262

Please add a comment here explaining how this should be used and why it's different from defineInsnVar.

267

This doesn't seem to be caused by this patch, but the indentation here and below looks funny.

2018

Um... return A->getName() < B->getName() ?

2136

I would add a static helper for generating these names, so it's easier to keep in sync with the use in RuleMatcher::emit.

[ab]

With the non-optimization comments addressed, I'm OK with this.

[dsanders]

Merged GIM_RecordInsn, GIM_PushInsnOpDef, GIM_PopInsn to a single kind of node: GIM_RecordInsn
Bundled the matcher state into one object. AvailableFeatures isn't part of this because it doesn't quite fit.
Bundled the helper tables into one object.

Fixed several nits.

TODO: Rebase to ToT.

[dsanders]

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

65–73

I've merged the three opcodes into a single one and added a test like the one above (I used G_SUB on all three nodes to avoid commutativity).

There's a small optimization that could be applied to the table as a result of this but it's a job for another patch. If one rule causes us to record the instruction that def's MIs[1]->getOperand(2), then no subsequent rule needs to do it again.

168

I've made the following changes to this:

• Removed MIStack as part of another change.
• Combined MIs and Renderers into a mutable State object
• Combined TypeObjects, FeatureBitsets, ComplexPredicates into a constant MatcherInfo object.

AvailableFeatures is still separate because I don't think it quite fits into either group.

test/TableGen/GlobalISelEmitter.td

88

I've added checks to the start of the file for them.

141

Well spotted.

utils/TableGen/GlobalISelEmitter.cpp

256–262

It was supposed to be different but the implementations in this patch ended up the same. I must have forgotten to make the change I intended.

I've corrected the implementations and added a comment.

267

I'm not sure what happened here but I've fixed it in this patch.

2018

It's a lexicographic comparison rather than a pointer comparison. The StringRef returned by Record::getName() provides relational operators that compare the strings (similar to std::string)

[dsanders]

Rebase before commit

[dsanders]

I don't seem to be able to commit right now:

svn: E200029: Commit failed (details follow):
svn: E200029: Couldn't perform atomic initialization

I'll try again later.

include/llvm/CodeGen/GlobalISel/InstructionSelector.h

 /// This class is responsible for selecting machine instructions.
 /// It's implemented by the target. It's used by the InstructionSelect pass.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H
 
+#include "llvm/ADT/SmallVector.h"
 #include <bitset>
 #include <cstddef>
 #include <cstdint>
 #include <functional>
 #include <initializer_list>
+#include <vector>
 
 namespace llvm {
 
+class LLT;
 class MachineInstr;
 class MachineInstrBuilder;
 class MachineOperand;
 class MachineRegisterInfo;
 class RegisterBankInfo;
 class TargetInstrInfo;
 class TargetRegisterClass;
 class TargetRegisterInfo;
PredicateBitsetImpl(const std::bitset<MaxPredicates> &B)
       : std::bitset<MaxPredicates>(B) {}
 
   PredicateBitsetImpl(std::initializer_list<unsigned> Init) {
     for (auto I : Init)
       std::bitset<MaxPredicates>::set(I);
   }
 };
 
+enum {
+  /// Record the specified instruction
+  /// - NewInsnID - Instruction ID to define
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  GIM_RecordInsn,
+
+  /// Check the feature bits
+  /// - Expected features
+  GIM_CheckFeatures,
+
+  /// Check the opcode on the specified instruction
+  /// - InsnID - Instruction ID
+  /// - Expected opcode
+  GIM_CheckOpcode,
+  /// Check the instruction has the right number of operands
+  /// - InsnID - Instruction ID
+  /// - Expected number of operands
+  GIM_CheckNumOperands,
+
+  /// Check the type for the specified operand
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - Expected type
+  GIM_CheckType,
+  /// Check the register bank for the specified operand
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - Expected register bank (specified as a register class)
+  GIM_CheckRegBankForClass,
+  /// Check the operand matches a complex predicate
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - RendererID - The renderer to hold the result
+  /// - Complex predicate ID
+  GIM_CheckComplexPattern,
+  /// Check the operand is a specific integer
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - Expected integer
+  GIM_CheckConstantInt,
+  /// Check the operand is a specific literal integer (i.e. MO.isImm() or MO.isCImm() is true).
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  /// - Expected integer
+  GIM_CheckLiteralInt,
+  /// Check the specified operand is an MBB
+  /// - InsnID - Instruction ID
+  /// - OpIdx - Operand index
+  GIM_CheckIsMBB,
+
+  /// A successful match
+  GIM_Accept,
+};
+
 /// Provides the logic to select generic machine instructions.
 class InstructionSelector {
 public:
   virtual ~InstructionSelector() = default;
 
   /// Select the (possibly generic) instruction \p I to only use target-specific
   /// opcodes. It is OK to insert multiple instructions, but they cannot be
   /// generic pre-isel instructions.
   ///
   /// \returns whether selection succeeded.
   /// \pre  I.getParent() && I.getParent()->getParent()
   /// \post
   ///   if returns true:
   ///     for I in all mutated/inserted instructions:
   ///       !isPreISelGenericOpcode(I.getOpcode())
   ///
   virtual bool select(MachineInstr &I) const = 0;
 
 protected:
   using ComplexRendererFn = std::function<void(MachineInstrBuilder &)>;
+  using RecordedMIVector = SmallVector<MachineInstr *, 4>;
+
+  struct MatcherState {
+    std::vector<ComplexRendererFn> Renderers;
+    RecordedMIVector MIs;
+
+    MatcherState(unsigned MaxRenderers);
+  };
 
+public:
+  template <class PredicateBitset, class ComplexMatcherMemFn>
+  struct MatcherInfoTy {
+    const LLT *TypeObjects;
+    const PredicateBitset *FeatureBitsets;
+    const std::vector<ComplexMatcherMemFn> ComplexPredicates;
+  };
+
+protected:
   InstructionSelector();
 
+  /// Execute a given matcher table and return true if the match was successful
+  /// and false otherwise.
+  template <class TgtInstructionSelector, class PredicateBitset,
+            class ComplexMatcherMemFn>
+  bool executeMatchTable(
+      TgtInstructionSelector &ISel, MatcherState &State,
+      const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> &MatcherInfo,
+      const int64_t *MatchTable, MachineRegisterInfo &MRI,
+      const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI,
+      const PredicateBitset &AvailableFeatures) const;
+
   /// Constrain a register operand of an instruction \p I to a specified
   /// register class. This could involve inserting COPYs before (for uses) or
   /// after (for defs) and may replace the operand of \p I.
   /// \returns whether operand regclass constraining succeeded.
   bool constrainOperandRegToRegClass(MachineInstr &I, unsigned OpIdx,
                                      const TargetRegisterClass &RC,
                                      const TargetInstrInfo &TII,
                                      const TargetRegisterInfo &TRI,

include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h

+//==-- llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h ---------*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file declares the API for the instruction selector.
+/// This class is responsible for selecting machine instructions.
+/// It's implemented by the target. It's used by the InstructionSelect pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTORIMPL_H
+#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTORIMPL_H
+
+namespace llvm {
+template <class TgtInstructionSelector, class PredicateBitset,
+          class ComplexMatcherMemFn>
+bool InstructionSelector::executeMatchTable(
+    TgtInstructionSelector &ISel, MatcherState &State,
+    const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> &MatcherInfo,
+    const int64_t *MatchTable, MachineRegisterInfo &MRI,
+    const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI,
+    const PredicateBitset &AvailableFeatures) const {
+  const int64_t *Command = MatchTable;
+  while (true) {
+    switch (*Command++) {
+    case GIM_RecordInsn: {
+      int64_t NewInsnID = *Command++;
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+
+      MachineOperand &MO = State.MIs[InsnID]->getOperand(OpIdx);
+      if (!MO.isReg()) {
+        DEBUG(dbgs() << "Rejected (not a register)\n");
+        return false;
+      }
+      if (TRI.isPhysicalRegister(MO.getReg())) {
+        DEBUG(dbgs() << "Rejected (is a physical register)\n");
+        return false;
+      }
+
+      assert((size_t)NewInsnID == State.MIs.size() &&
+             "Expected to store MIs in order");
+      State.MIs.push_back(MRI.getVRegDef(MO.getReg()));
+      DEBUG(dbgs() << "MIs[" << NewInsnID << "] = GIM_RecordInsn(" << InsnID
+                   << ", " << OpIdx << ")\n");
+      break;
+    }
+
+    case GIM_CheckFeatures: {
+      int64_t ExpectedBitsetID = *Command++;
+      DEBUG(dbgs() << "GIM_CheckFeatures(ExpectedBitsetID=" << ExpectedBitsetID
+                   << ")\n");
+      if ((AvailableFeatures & MatcherInfo.FeatureBitsets[ExpectedBitsetID]) !=
+          MatcherInfo.FeatureBitsets[ExpectedBitsetID]) {
+        DEBUG(dbgs() << "Rejected\n");
+        return false;
+      }
+      break;
+    }
+
+    case GIM_CheckOpcode: {
+      int64_t InsnID = *Command++;
+      int64_t Expected = *Command++;
+      DEBUG(dbgs() << "GIM_CheckOpcode(MIs[" << InsnID
+                   << "], ExpectedOpcode=" << Expected << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (State.MIs[InsnID]->getOpcode() != Expected)
+        return false;
+      break;
+    }
+    case GIM_CheckNumOperands: {
+      int64_t InsnID = *Command++;
+      int64_t Expected = *Command++;
+      DEBUG(dbgs() << "GIM_CheckNumOperands(MIs[" << InsnID
+                   << "], Expected=" << Expected << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (State.MIs[InsnID]->getNumOperands() != Expected)
+        return false;
+      break;
+    }
+
+    case GIM_CheckType: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      int64_t TypeID = *Command++;
+      DEBUG(dbgs() << "GIM_CheckType(MIs[" << InsnID << "]->getOperand("
+                   << OpIdx << "), TypeID=" << TypeID << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (MRI.getType(State.MIs[InsnID]->getOperand(OpIdx).getReg()) !=
+          MatcherInfo.TypeObjects[TypeID])
+        return false;
+      break;
+    }
+    case GIM_CheckRegBankForClass: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      int64_t RCEnum = *Command++;
+      DEBUG(dbgs() << "GIM_CheckRegBankForClass(MIs[" << InsnID
+                   << "]->getOperand(" << OpIdx << "), RCEnum=" << RCEnum
+                   << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (&RBI.getRegBankFromRegClass(*TRI.getRegClass(RCEnum)) !=
+          RBI.getRegBank(State.MIs[InsnID]->getOperand(OpIdx).getReg(), MRI, TRI))
+        return false;
+      break;
+    }
+    case GIM_CheckComplexPattern: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      int64_t RendererID = *Command++;
+      int64_t ComplexPredicateID = *Command++;
+      DEBUG(dbgs() << "State.Renderers[" << RendererID
+                   << "] = GIM_CheckComplexPattern(MIs[" << InsnID
+                   << "]->getOperand(" << OpIdx
+                   << "), ComplexPredicateID=" << ComplexPredicateID << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      // FIXME: Use std::invoke() when it's available.
+      if (!(State.Renderers[RendererID] =
+                (ISel.*MatcherInfo.ComplexPredicates[ComplexPredicateID])(
+                    State.MIs[InsnID]->getOperand(OpIdx))))
+        return false;
+      break;
+    }
+    case GIM_CheckConstantInt: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      int64_t Value = *Command++;
+      DEBUG(dbgs() << "GIM_CheckConstantInt(MIs[" << InsnID << "]->getOperand("
+                   << OpIdx << "), Value=" << Value << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (!isOperandImmEqual(State.MIs[InsnID]->getOperand(OpIdx), Value, MRI))
+        return false;
+      break;
+    }
+    case GIM_CheckLiteralInt: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      int64_t Value = *Command++;
+      DEBUG(dbgs() << "GIM_CheckLiteralInt(MIs[" << InsnID << "]->getOperand(" << OpIdx
+                   << "), Value=" << Value << ")\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      MachineOperand &OM = State.MIs[InsnID]->getOperand(OpIdx);
+      if (!OM.isCImm() || !OM.getCImm()->equalsInt(Value))
+        return false;
+      break;
+    }
+    case GIM_CheckIsMBB: {
+      int64_t InsnID = *Command++;
+      int64_t OpIdx = *Command++;
+      DEBUG(dbgs() << "GIM_CheckIsMBB(MIs[" << InsnID << "]->getOperand("
+                   << OpIdx << "))\n");
+      assert(State.MIs[InsnID] != nullptr && "Used insn before defined");
+      if (!State.MIs[InsnID]->getOperand(OpIdx).isMBB())
+        return false;
+      break;
+    }
+
+    case GIM_Accept:
+      DEBUG(dbgs() << "GIM_Accept");
+      return true;
+    default:
+      llvm_unreachable("Unexpected command");
+    }
+  }
+}
+} // end namespace llvm
+
+#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTORIMPL_H

lib/CodeGen/GlobalISel/InstructionSelector.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include <cassert>
 
 #define DEBUG_TYPE "instructionselector"
 
 using namespace llvm;
 
+InstructionSelector::MatcherState::MatcherState(unsigned MaxRenderers)
+    : Renderers(MaxRenderers, nullptr), MIs() {}
+
 InstructionSelector::InstructionSelector() = default;
 
 bool InstructionSelector::constrainOperandRegToRegClass(
     MachineInstr &I, unsigned OpIdx, const TargetRegisterClass &RC,
     const TargetInstrInfo &TII, const TargetRegisterInfo &TRI,
     const RegisterBankInfo &RBI) const {
   MachineBasicBlock &MBB = *I.getParent();
   MachineFunction &MF = *MBB.getParent();

lib/Target/AArch64/AArch64InstructionSelector.cpp

 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "aarch64-isel"
 
+#include "llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h"
+
 using namespace llvm;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 namespace {
 

lib/Target/ARM/ARMInstructionSelector.cpp

 #include "ARMSubtarget.h"
 #include "ARMTargetMachine.h"
 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 
 #define DEBUG_TYPE "arm-isel"
 
+#include "llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h"
+
 using namespace llvm;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 namespace {
 

lib/Target/X86/X86InstructionSelector.cpp

 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/IR/Type.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "X86-isel"
 
+#include "llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h"
+
 using namespace llvm;
 
 #ifndef LLVM_BUILD_GLOBAL_ISEL
 #error "You shouldn't build this"
 #endif
 
 namespace {
 

test/TableGen/GlobalISelEmitter.td

 def m1Z : OperandWithDefaultOps <i32, (ops (i32 -1), R0)>;
 
 def HasA : Predicate<"Subtarget->hasA()">;
 def HasB : Predicate<"Subtarget->hasB()">;
 def HasC : Predicate<"Subtarget->hasC()"> { let RecomputePerFunction = 1; }
 
 //===- Test the function boilerplate. -------------------------------------===//
 
+// CHECK: const unsigned MAX_SUBTARGET_PREDICATES = 3;
+// CHECK: using PredicateBitset = llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;
+
+// CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_DECL
+// CHECK-NEXT:    mutable MatcherState State;
+// CHECK-NEXT:    typedef ComplexRendererFn(MyTargetInstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;
+// CHECK-NEXT:    const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> MatcherInfo;
+// CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL
+
+// CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_INIT
+// CHECK-NEXT:    , State(2),
+// CHECK-NEXT:    MatcherInfo({TypeObjects, FeatureBitsets, {
+// CHECK-NEXT:      nullptr, // GICP_Invalid
+// CHECK-NEXT:      &MyTargetInstructionSelector::selectComplexPattern, // gi_complex
+// CHECK-NEXT:    }})
+// CHECK-NEXT:  #endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT
+
 // CHECK-LABEL: enum SubtargetFeatureBits : uint8_t {
 // CHECK-NEXT:    Feature_HasABit = 0,
 // CHECK-NEXT:    Feature_HasBBit = 1,
 // CHECK-NEXT:    Feature_HasCBit = 2,
 // CHECK-NEXT:  };
 
 // CHECK-LABEL: PredicateBitset MyTargetInstructionSelector::
 // CHECK-NEXT:  computeAvailableModuleFeatures(const MyTargetSubtarget *Subtarget) const {

 // CHECK-NEXT:    PredicateBitset Features;
 // CHECK-NEXT:    if (Subtarget->hasC())
 // CHECK-NEXT:      Features[Feature_HasCBit] = 1;
 // CHECK-NEXT:    return Features;
 // CHECK-NEXT:  }
 
 // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const {
 // CHECK: MachineFunction &MF = *I.getParent()->getParent();
-// CHECK: const MachineRegisterInfo &MRI = MF.getRegInfo();
+// CHECK: MachineRegisterInfo &MRI = MF.getRegInfo();
+// CHECK: AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, &MF);
+// CHECK: const PredicateBitset AvailableFeatures = getAvailableFeatures();
 
 //===- Test a pattern with multiple ComplexPattern operands. --------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 4)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_SELECT) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((Renderer0 = selectComplexPattern(MI0.getOperand(2)))))) &&
-// CHECK-NEXT:        ((/* src3 */ (MRI.getType(MI0.getOperand(3).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((Renderer1 = selectComplexPattern(MI0.getOperand(3))))))) {
-// CHECK-NEXT:          // (select:i32 GPR32:i32:$src1, complex:i32:$src2, complex:i32:$src3) => (INSN2:i32 GPR32:i32:$src1, complex:i32:$src3, complex:i32:$src2)
-// CHECK-NEXT:          MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::INSN2));
-// CHECK-NEXT:          MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:          MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:          Renderer1(MIB);
-// CHECK-NEXT:          Renderer0(MIB);
-// CHECK-NEXT:          for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:            for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:              MIB.addMemOperand(MMO);
-// CHECK-NEXT:          I.eraseFromParent();
-// CHECK-NEXT:          MachineInstr &NewI = *MIB;
-// CHECK-NEXT:          constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:          return true;
-// CHECK-NEXT:        }
+// CHECK-LABEL: MatchTable0[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/4,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/2, /*Renderer*/0, GICP_gi_complex,
+// CHECK-NEXT:    // MIs[0] src3
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/3, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/3, /*Renderer*/1, GICP_gi_complex,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable0, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (select:i32 GPR32:i32:$src1, complex:i32:$src2, complex:i32:$src3) => (INSN2:i32 GPR32:i32:$src1, complex:i32:$src3, complex:i32:$src2)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::INSN2));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    Renderers[1](MIB);
+// CHECK-NEXT:    Renderers[0](MIB);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def : GINodeEquiv<G_SELECT, select>;
 def INSN2 : I<(outs GPR32:$dst), (ins GPR32Op:$src1, complex:$src2, complex:$src3), []>;
 def : Pat<(select GPR32:$src1, complex:$src2, complex:$src3),
           (INSN2 GPR32:$src1, complex:$src3, complex:$src2)>;
 
 //===- Test a simple pattern with regclass operands. ----------------------===//
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_ADD) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(2).getReg(), MRI, TRI)))))) {
-
-// CHECK-NEXT:      // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2)
-// CHECK-NEXT:      I.setDesc(TII.get(MyTarget::ADD));
-// CHECK-NEXT:      MachineInstr &NewI = I;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
-
+// CHECK-LABEL: MatchTable1[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_ADD,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID
+// CHECK-NEXT:    // MIs[0] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable1, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2)
+// CHECK-NEXT:    I.setDesc(TII.get(MyTarget::ADD));
+// CHECK-NEXT:    MachineInstr &NewI = I;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2),
             [(set GPR32:$dst, (add GPR32:$src1, GPR32:$src2))]>;
 
 //===- Test a nested instruction match. -----------------------------------===//
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    PredicateBitset ExpectedFeatures = {Feature_HasABit};
-// CHECK-NEXT:    if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if (!MI0.getOperand(1).isReg())
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if (TRI.isPhysicalRegister(MI0.getOperand(1).getReg()))
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    MachineInstr &MI1 = *MRI.getVRegDef(MI0.getOperand(1).getReg());
-// CHECK-NEXT:    if (MI1.getNumOperands() < 3)
+// CHECK-LABEL: MatchTable2[] = {
+// CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_ADD,
+// CHECK-NEXT:    // MIs[1] Operand 0
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    // MIs[1] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[1] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src3
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable2, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    if (!isObviouslySafeToFold(*State.MIs[1]))
 // CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (((MI1.getOpcode() == TargetOpcode::G_ADD) &&
-// CHECK-NEXT:        ((/* Operand 0 */ (MRI.getType(MI1.getOperand(0).getReg()) == (LLT::scalar(32))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI1.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI1.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(2).getReg(), MRI, TRI))))))
-// CHECK-NEXT:        ))) &&
-// CHECK-NEXT:        ((/* src3 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(2).getReg(), MRI, TRI)))))) {
-// CHECK-NEXT:        if (!isObviouslySafeToFold(MI1)) return false;
-// CHECK-NEXT:        // (mul:i32 (add:i32 GPR32:i32:$src1, GPR32:i32:$src2), GPR32:i32:$src3)  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
-// CHECK-NEXT:     MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MULADD));
-// CHECK-NEXT:     MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:     MIB.add(MI1.getOperand(1)/*src1*/);
-// CHECK-NEXT:     MIB.add(MI1.getOperand(2)/*src2*/);
-// CHECK-NEXT:     MIB.add(MI0.getOperand(2)/*src3*/);
-// CHECK-NEXT:     for (const auto *FromMI : {&MI0, &MI1, })
-// CHECK-NEXT:       for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:         MIB.addMemOperand(MMO);
-// CHECK-NEXT:     I.eraseFromParent();
-// CHECK-NEXT:     MachineInstr &NewI = *MIB;
-// CHECK-NEXT:     constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:     return true;
-// CHECK-NEXT:   }
+// CHECK-NEXT:    // (mul:i32 (add:i32 GPR32:i32:$src1, GPR32:i32:$src2), GPR32:i32:$src3)  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MULADD));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.add(State.MIs[1]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    MIB.add(State.MIs[1]->getOperand(2)/*src2*/);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(2)/*src3*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], State.MIs[1], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 // We also get a second rule by commutativity.
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    PredicateBitset ExpectedFeatures = {Feature_HasABit};
-// CHECK-NEXT:    if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if (!MI0.getOperand(2).isReg())
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if (TRI.isPhysicalRegister(MI0.getOperand(2).getReg()))
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    MachineInstr &MI1 = *MRI.getVRegDef(MI0.getOperand(2).getReg());
-// CHECK-NEXT:    if (MI1.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src3 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (((MI1.getOpcode() == TargetOpcode::G_ADD) &&
-// CHECK-NEXT:        ((/* Operand 0 */ (MRI.getType(MI1.getOperand(0).getReg()) == (LLT::scalar(32))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI1.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI1.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI1.getOperand(2).getReg(), MRI, TRI))))))
-// CHECK-NEXT:        )))) {
-// CHECK-NEXT:        if (!isObviouslySafeToFold(MI1)) return false;
-// CHECK-NEXT:        // (mul:i32 GPR32:i32:$src3, (add:i32 GPR32:i32:$src1, GPR32:i32:$src2))  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
+// CHECK-LABEL: MatchTable3[] = {
+// CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/2,
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src3
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_ADD,
+// CHECK-NEXT:    // MIs[1] Operand 0
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    // MIs[1] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[1] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable3, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:     if (!isObviouslySafeToFold(*State.MIs[1]))
+// CHECK-NEXT:       return false;
+// CHECK-NEXT:     // (mul:i32 GPR32:i32:$src3, (add:i32 GPR32:i32:$src1, GPR32:i32:$src2))  =>  (MULADD:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3)
 // CHECK-NEXT:     MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MULADD));
-// CHECK-NEXT:     MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:     MIB.add(MI1.getOperand(1)/*src1*/);
-// CHECK-NEXT:     MIB.add(MI1.getOperand(2)/*src2*/);
-// CHECK-NEXT:     MIB.add(MI0.getOperand(1)/*src3*/);
-// CHECK-NEXT:     for (const auto *FromMI : {&MI0, &MI1, })
+// CHECK-NEXT:     MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:     MIB.add(State.MIs[1]->getOperand(1)/*src1*/);
+// CHECK-NEXT:     MIB.add(State.MIs[1]->getOperand(2)/*src2*/);
+// CHECK-NEXT:     MIB.add(State.MIs[0]->getOperand(1)/*src3*/);
+// CHECK-NEXT:     for (const auto *FromMI : {State.MIs[0], State.MIs[1], })
 // CHECK-NEXT:       for (const auto &MMO : FromMI->memoperands())
 // CHECK-NEXT:         MIB.addMemOperand(MMO);
 // CHECK-NEXT:     I.eraseFromParent();
 // CHECK-NEXT:     MachineInstr &NewI = *MIB;
 // CHECK-NEXT:     constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
 // CHECK-NEXT:     return true;
 // CHECK-NEXT:   }
 
 def MULADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2, GPR32:$src3),
                [(set GPR32:$dst,
                      (mul (add GPR32:$src1, GPR32:$src2), GPR32:$src3))]>,
              Requires<[HasA]>;
 
 //===- Test another simple pattern with regclass operands. ----------------===//
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    PredicateBitset ExpectedFeatures = {Feature_HasABit, Feature_HasBBit, Feature_HasCBit};
-// CHECK-NEXT:    if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_MUL) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(2).getReg(), MRI, TRI)))))) {
-// CHECK-NEXT:      // (mul:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (MUL:i32 GPR32:i32:$src2, GPR32:i32:$src1)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MUL));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(2)/*src2*/);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:     for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:       for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:         MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable4[] = {
+// CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA_HasB_HasC,
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_MUL,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable4, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:   // (mul:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (MUL:i32 GPR32:i32:$src2, GPR32:i32:$src1)
+// CHECK-NEXT:   MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MUL));
+// CHECK-NEXT:   MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:   MIB.add(State.MIs[0]->getOperand(2)/*src2*/);
+// CHECK-NEXT:   MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:   for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:     for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:       MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def MUL : I<(outs GPR32:$dst), (ins GPR32:$src2, GPR32:$src1),
              [(set GPR32:$dst, (mul GPR32:$src1, GPR32:$src2))]>,
           Requires<[HasA, HasB, HasC]>;
 
+//===- Test a more complex multi-instruction match. -----------------------===//
+
+// CHECK-LABEL: MatchTable5[] = {
+// CHECK-NEXT:    GIM_CheckFeatures, GIFBS_HasA,
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/1, /*MI*/0, /*OpIdx*/1, // MIs[1]
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/1, /*Expected*/3,
+// CHECK-NEXT:    GIM_RecordInsn, /*DefineMI*/2, /*MI*/0, /*OpIdx*/2, // MIs[2]
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/2, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/1, TargetOpcode::G_SUB,
+// CHECK-NEXT:    // MIs[1] Operand 0
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    // MIs[1] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[1] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/1, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/1, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/2, TargetOpcode::G_SUB,
+// CHECK-NEXT:    // MIs[2] Operand 0
+// CHECK-NEXT:    GIM_CheckType, /*MI*/2, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    // MIs[2] src3
+// CHECK-NEXT:    GIM_CheckType, /*MI*/2, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/2, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[2] src4
+// CHECK-NEXT:    GIM_CheckType, /*MI*/2, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/2, /*Op*/2, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable5, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    if (!isObviouslySafeToFold(*State.MIs[1]))
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    if (!isObviouslySafeToFold(*State.MIs[2]))
+// CHECK-NEXT:      return false;
+// CHECK-NEXT:    // (sub:i32 (sub:i32 GPR32:i32:$src1, GPR32:i32:$src2), (sub:i32 GPR32:i32:$src3, GPR32:i32:$src4)) => (INSNBOB:i32 GPR32:i32:$src1, GPR32:i32:$src2, GPR32:i32:$src3, GPR32:i32:$src4)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::INSNBOB));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.add(State.MIs[1]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    MIB.add(State.MIs[1]->getOperand(2)/*src2*/);
+// CHECK-NEXT:    MIB.add(State.MIs[2]->getOperand(1)/*src3*/);
+// CHECK-NEXT:    MIB.add(State.MIs[2]->getOperand(2)/*src4*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], State.MIs[1], State.MIs[2], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
+
+def INSNBOB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2, GPR32:$src3, GPR32:$src4),
+                 [(set GPR32:$dst,
+                      (sub (sub GPR32:$src1, GPR32:$src2), (sub GPR32:$src3, GPR32:$src4)))]>,
+               Requires<[HasA]>;
+
 //===- Test a pattern with ComplexPattern operands. -----------------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_SUB) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        ((Renderer0 = selectComplexPattern(MI0.getOperand(2))))))) {
-// CHECK-NEXT:          // (sub:i32 GPR32:i32:$src1, complex:i32:$src2) => (INSN1:i32 GPR32:i32:$src1, complex:i32:$src2)
-// CHECK-NEXT:          MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::INSN1));
-// CHECK-NEXT:          MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:          MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:          Renderer0(MIB);
-// CHECK-NEXT:          for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:            for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:              MIB.addMemOperand(MMO);
-// CHECK-NEXT:          I.eraseFromParent();
-// CHECK-NEXT:          MachineInstr &NewI = *MIB;
-// CHECK-NEXT:          constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:          return true;
-// CHECK-NEXT:        }
+// CHECK-LABEL: MatchTable6[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SUB,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckComplexPattern, /*MI*/0, /*Op*/2, /*Renderer*/0, GICP_gi_complex,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable6, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (sub:i32 GPR32:i32:$src1, complex:i32:$src2) => (INSN1:i32 GPR32:i32:$src1, complex:i32:$src2)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::INSN1));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    Renderers[0](MIB);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def INSN1 : I<(outs GPR32:$dst), (ins GPR32:$src1, complex:$src2), []>;
 def : Pat<(sub GPR32:$src1, complex:$src2), (INSN1 GPR32:$src1, complex:$src2)>;
 
 //===- Test a simple pattern with a default operand. ----------------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -2, MRI))))) {
-// CHECK-NEXT:      // (xor:i32 GPR32:i32:$src1, -2:i32) => (XORI:i32 GPR32:i32:$src1)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORI));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.addImm(-1);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable7[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -2
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable7, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (xor:i32 GPR32:i32:$src1, -2:i32) => (XORI:i32 GPR32:i32:$src1)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORI));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.addImm(-1);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 // The -2 is just to distinguish it from the 'not' case below.
 def XORI : I<(outs GPR32:$dst), (ins m1:$src2, GPR32:$src1),
              [(set GPR32:$dst, (xor GPR32:$src1, -2))]>;
 
 //===- Test a simple pattern with a default register operand. -------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -3, MRI))))) {
-// CHECK-NEXT:      // (xor:i32 GPR32:i32:$src1, -3:i32) => (XOR:i32 GPR32:i32:$src1)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XOR));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable8[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -3
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable8, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (xor:i32 GPR32:i32:$src1, -3:i32) => (XOR:i32 GPR32:i32:$src1)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XOR));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 // The -3 is just to distinguish it from the 'not' case below and the other default op case above.
 def XOR : I<(outs GPR32:$dst), (ins Z:$src2, GPR32:$src1),
             [(set GPR32:$dst, (xor GPR32:$src1, -3))]>;
 
 //===- Test a simple pattern with a multiple default operands. ------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -4, MRI))))) {
-// CHECK-NEXT:      // (xor:i32 GPR32:i32:$src1, -4:i32) => (XORlike:i32 GPR32:i32:$src1)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORlike));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.addImm(-1);
-// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable9[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -4
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable9, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (xor:i32 GPR32:i32:$src1, -4:i32) => (XORlike:i32 GPR32:i32:$src1)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORlike));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.addImm(-1);
+// CHECK-NEXT:    MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 // The -4 is just to distinguish it from the other 'not' cases.
 def XORlike : I<(outs GPR32:$dst), (ins m1Z:$src2, GPR32:$src1),
                 [(set GPR32:$dst, (xor GPR32:$src1, -4))]>;
 
 //===- Test a simple pattern with multiple operands with defaults. --------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -5, MRI))))) {
-// CHECK-NEXT:      // (xor:i32 GPR32:i32:$src1, -5:i32) => (XORManyDefaults:i32 GPR32:i32:$src1)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORManyDefaults));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.addImm(-1);
-// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*src1*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable10[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -5,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable10, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (xor:i32 GPR32:i32:$src1, -5:i32) => (XORManyDefaults:i32 GPR32:i32:$src1)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::XORManyDefaults));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.addImm(-1);
+// CHECK-NEXT:    MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:    MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*src1*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 // The -5 is just to distinguish it from the other cases.
 def XORManyDefaults : I<(outs GPR32:$dst), (ins m1Z:$src3, Z:$src2, GPR32:$src1),
                         [(set GPR32:$dst, (xor GPR32:$src1, -5))]>;
 
 //===- Test a simple pattern with constant immediate operands. ------------===//
 //
 // This must precede the 3-register variants because constant immediates have
 // priority over register banks.
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 3)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_XOR) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Wm */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 2 */ (MRI.getType(MI0.getOperand(2).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:        (isOperandImmEqual(MI0.getOperand(2), -1, MRI))))) {
-// CHECK-NEXT:      // (xor:i32 GPR32:i32:$Wm, -1:i32) => (ORN:i32 R0:i32, GPR32:i32:$Wm)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::ORN));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      MIB.addReg(MyTarget::R0);
-// CHECK-NEXT:      MIB.add(MI0.getOperand(1)/*Wm*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable11[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/3,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_XOR,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Wm
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 2
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/2, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckConstantInt, /*MI*/0, /*Op*/2, -1,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable11, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (xor:i32 GPR32:i32:$Wm, -1:i32) => (ORN:i32 R0:i32, GPR32:i32:$Wm)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::ORN));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    MIB.addReg(MyTarget::R0);
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(1)/*Wm*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def ORN : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>;
 def : Pat<(not GPR32:$Wm), (ORN R0, GPR32:$Wm)>;
 
 //===- Test a COPY_TO_REGCLASS --------------------------------------------===//
 //
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 2)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_BITCAST) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* src1 */ (MRI.getType(MI0.getOperand(1).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::FPR32RegClass) == RBI.getRegBank(MI0.getOperand(1).getReg(), MRI, TRI))))))
-// CHECK-NEXT:      // (bitconvert:i32 FPR32:f32:$src1) => (COPY_TO_REGCLASS:i32 FPR32:f32:$src1, GPR32:i32)
-// CHECK-NEXT:      I.setDesc(TII.get(TargetOpcode::COPY));
-// CHECK-NEXT:      MachineInstr &NewI = I;
-// CHECK-NEXT:      constrainOperandRegToRegClass(NewI, 0, MyTarget::GPR32RegClass, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable12[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BITCAST,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] src1
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/1, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/1, /*RC*/MyTarget::FPR32RegClassID,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable12, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // (bitconvert:i32 FPR32:f32:$src1) => (COPY_TO_REGCLASS:i32 FPR32:f32:$src1, GPR32:i32)
+// CHECK-NEXT:    I.setDesc(TII.get(TargetOpcode::COPY));
+// CHECK-NEXT:    MachineInstr &NewI = I;
+// CHECK-NEXT:    constrainOperandRegToRegClass(NewI, 0, MyTarget::GPR32RegClass, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def : Pat<(i32 (bitconvert FPR32:$src1)),
           (COPY_TO_REGCLASS FPR32:$src1, GPR32)>;
 
 //===- Test a simple pattern with just a leaf immediate. ------------------===//
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:    MachineInstr &MI0 = I;
-// CHECK-NEXT:    if (MI0.getNumOperands() < 2)
-// CHECK-NEXT:      return false;
-// CHECK-NEXT:    if ((MI0.getOpcode() == TargetOpcode::G_CONSTANT) &&
-// CHECK-NEXT:        ((/* dst */ (MRI.getType(MI0.getOperand(0).getReg()) == (LLT::scalar(32))) &&
-// CHECK-NEXT:         ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(MI0.getOperand(0).getReg(), MRI, TRI))))) &&
-// CHECK-NEXT:        ((/* Operand 1 */ (MI0.getOperand(1).isCImm() && MI0.getOperand(1).getCImm()->equalsInt(1))))) {
-// CHECK-NEXT:      // 1:i32 => (MOV1:i32)
-// CHECK-NEXT:      MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MOV1));
-// CHECK-NEXT:      MIB.add(MI0.getOperand(0)/*dst*/);
-// CHECK-NEXT:      for (const auto *FromMI : {&MI0, })
-// CHECK-NEXT:        for (const auto &MMO : FromMI->memoperands())
-// CHECK-NEXT:          MIB.addMemOperand(MMO);
-// CHECK-NEXT:      I.eraseFromParent();
-// CHECK-NEXT:      MachineInstr &NewI = *MIB;
-// CHECK-NEXT:      constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:      return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable13[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/2,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_CONSTANT,
+// CHECK-NEXT:    // MIs[0] dst
+// CHECK-NEXT:    GIM_CheckType, /*MI*/0, /*Op*/0, /*Type*/GILLT_s32,
+// CHECK-NEXT:    GIM_CheckRegBankForClass, /*MI*/0, /*Op*/0, /*RC*/MyTarget::GPR32RegClassID,
+// CHECK-NEXT:    // MIs[0] Operand 1
+// CHECK-NEXT:    GIM_CheckLiteralInt, /*MI*/0, /*Op*/1, 1,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable13, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:    // 1:i32 => (MOV1:i32)
+// CHECK-NEXT:    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MOV1));
+// CHECK-NEXT:    MIB.add(State.MIs[0]->getOperand(0)/*dst*/);
+// CHECK-NEXT:    for (const auto *FromMI : {State.MIs[0], })
+// CHECK-NEXT:      for (const auto &MMO : FromMI->memoperands())
+// CHECK-NEXT:        MIB.addMemOperand(MMO);
+// CHECK-NEXT:    I.eraseFromParent();
+// CHECK-NEXT:    MachineInstr &NewI = *MIB;
+// CHECK-NEXT:    constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:    return true;
+// CHECK-NEXT:  }
 
 def MOV1 : I<(outs GPR32:$dst), (ins), [(set GPR32:$dst, 1)]>;
 
 //===- Test a pattern with an MBB operand. --------------------------------===//
 
-// CHECK-LABEL: if ([&]() {
-// CHECK-NEXT:      MachineInstr &MI0 = I;
-// CHECK-NEXT:      if (MI0.getNumOperands() < 1)
-// CHECK-NEXT:        return false;
-// CHECK-NEXT:      if ((MI0.getOpcode() == TargetOpcode::G_BR) &&
-// CHECK-NEXT:          ((/* target */ (MI0.getOperand(0).isMBB())))) {
-                    
-// CHECK-NEXT:       // (br (bb:Other):$target) => (BR (bb:Other):$target)
-// CHECK-NEXT:       I.setDesc(TII.get(MyTarget::BR));
-// CHECK-NEXT:       MachineInstr &NewI = I;
-// CHECK-NEXT:       constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
-// CHECK-NEXT:       return true;
-// CHECK-NEXT:    }
-// CHECK-NEXT:    return false;
-// CHECK-NEXT:  }()) { return true; }
+// CHECK-LABEL: MatchTable14[] = {
+// CHECK-NEXT:    GIM_CheckNumOperands, /*MI*/0, /*Expected*/1,
+// CHECK-NEXT:    GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_BR,
+// CHECK-NEXT:    // MIs[0] target
+// CHECK-NEXT:    GIM_CheckIsMBB, /*MI*/0, /*Op*/0,
+// CHECK-NEXT:    GIM_Accept,
+// CHECK-NEXT:  };
+// CHECK-NEXT:  MIs.clear();
+// CHECK-NEXT:  MIs.push_back(&I);
+// CHECK-NEXT:  if (executeMatchTable(*this, State, MatcherInfo, MatchTable14, MRI, TRI, RBI, AvailableFeatures)) {
+// CHECK-NEXT:     // (br (bb:Other):$target) => (BR (bb:Other):$target)
+// CHECK-NEXT:     I.setDesc(TII.get(MyTarget::BR));
+// CHECK-NEXT:     MachineInstr &NewI = I;
+// CHECK-NEXT:     constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);
+// CHECK-NEXT:     return true;
+// CHECK-NEXT:  }
 
 def BR : I<(outs), (ins unknown:$target),
             [(br bb:$target)]>;

utils/TableGen/GlobalISelEmitter.cpp

 /// equivalent at compiler run-time.
 class LLTCodeGen {
 private:
   LLT Ty;
 
 public:
   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 
+  void emitCxxEnumValue(raw_ostream &OS) const {
+    if (Ty.isScalar()) {
+      OS << "GILLT_s" << Ty.getSizeInBits();
+      return;
+    }
+    if (Ty.isVector()) {
+      OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
+      return;
+    }
+    llvm_unreachable("Unhandled LLT");
+  }
+
   void emitCxxConstructorCall(raw_ostream &OS) const {
     if (Ty.isScalar()) {
       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
       return;
     }
     if (Ty.isVector()) {
       OS << "LLT::vector(" << Ty.getNumElements() << ", "
          << Ty.getScalarSizeInBits() << ")";
       return;
     }
     llvm_unreachable("Unhandled LLT");
   }
 
   const LLT &get() const { return Ty; }
+
+  /// This ordering is used for std::unique() and std::sort(). There's no
+  /// particular logic behind the order.
+  bool operator<(const LLTCodeGen &Other) const {
+    if (!Ty.isValid())
+      return Other.Ty.isValid();
+    if (Ty.isScalar()) {
+      if (!Other.Ty.isValid())
+        return false;
+      if (Other.Ty.isScalar())
+        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
+      return false;
+    }
+    if (Ty.isVector()) {
+      if (!Other.Ty.isValid() || Other.Ty.isScalar())
+        return false;
+      if (Other.Ty.isVector()) {
+        if (Ty.getNumElements() < Other.Ty.getNumElements())
+          return true;
+        if (Ty.getNumElements() > Other.Ty.getNumElements())
+          return false;
+        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
+      }
+      return false;
+    }
+    llvm_unreachable("Unhandled LLT");
+  }
 };
 
 class InstructionMatcher;
 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
 static Optional<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) {
   MVT VT(SVT);
   if (VT.isVector() && VT.getVectorNumElements() != 1)
if (DefInit *VDefInit = dyn_cast<DefInit>(V)) {
     if (VDefInit->getDef()->isSubClassOf("RegisterOperand"))
       return VDefInit->getDef()->getValueAsDef("RegClass");
     if (VDefInit->getDef()->isSubClassOf("RegisterClass"))
       return VDefInit->getDef();
   }
   return nullptr;
 }
 
+std::string
+getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
+  std::string Name = "GIFBS";
+  for (const auto &Feature : FeatureBitset)
+    Name += ("_" + Feature->getName()).str();
+  return Name;
+}
 //===- Matchers -----------------------------------------------------------===//
 
 class OperandMatcher;
 class MatchAction;
 
 /// Generates code to check that a match rule matches.
 class RuleMatcher {
   /// A list of matchers that all need to succeed for the current rule to match.
   /// FIXME: This currently supports a single match position but could be
   /// extended to support multiple positions to support div/rem fusion or
   /// load-multiple instructions.
   std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
   std::vector<std::unique_ptr<MatchAction>> Actions;
 
   /// A map of instruction matchers to the local variables created by
   /// emitCxxCaptureStmts().
-  std::map<const InstructionMatcher *, std::string> InsnVariableNames;
+  std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;
 
   /// ID for the next instruction variable defined with defineInsnVar()
   unsigned NextInsnVarID;
 
   std::vector<Record *> RequiredFeatures;
 
 public:
   RuleMatcher()
-      : Matchers(), Actions(), InsnVariableNames(), NextInsnVarID(0) {}
+      : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
   RuleMatcher(RuleMatcher &&Other) = default;
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
   InstructionMatcher &addInstructionMatcher();
   void addRequiredFeature(Record *Feature);
+  const std::vector<Record *> &getRequiredFeatures() const;
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 
-  std::string defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
-                            StringRef Value);
-  StringRef getInsnVarName(const InstructionMatcher &InsnMatcher) const;
+  /// Define an instruction without emitting any code to do so.
+  /// This is used for the root of the match.
+  unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
+  /// Define an instruction and emit corresponding state-machine opcodes.
+  unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
+                         unsigned InsnVarID, unsigned OpIdx);
+  unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
 
   void emitCxxCapturedInsnList(raw_ostream &OS);
-  void emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr);
+  void emitCxxCaptureStmts(raw_ostream &OS);
 
-void emit(raw_ostream &OS, SubtargetFeatureInfoMap SubtargetFeatures);
+  void emit(raw_ostream &OS);
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const RuleMatcher &B) const;
 
   /// Report the maximum number of temporary operands needed by the rule
   /// matcher.
   unsigned countRendererFns() const;
 
   // FIXME: Remove this as soon as possible
   InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 };
 
 template <class PredicateTy> class PredicateListMatcher {
 private:
   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
   PredicateVec Predicates;
 
 public:
public:
   typename PredicateVec::size_type predicates_size() const {
     return Predicates.size();
   }
 
   /// Emit a C++ expression that tests whether all the predicates are met.
   template <class... Args>
   void emitCxxPredicateListExpr(raw_ostream &OS, Args &&... args) const {
     if (Predicates.empty()) {
-      OS << "true";
+      OS << "// No predicates\n";
       return;
     }
 
-    StringRef Separator = "";
-    for (const auto &Predicate : predicates()) {
-      OS << Separator << "(";
+    for (const auto &Predicate : predicates())
       Predicate->emitCxxPredicateExpr(OS, std::forward<Args>(args)...);
-      OS << ")";
-      Separator = " &&\n";
-    }
   }
 };
 
 /// Generates code to check a predicate of an operand.
 ///
 /// Typical predicates include:
 /// * Operand is a particular register.
 /// * Operand is assigned a particular register bank.
getOptionalOperand(StringRef SymbolicName) const {
     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
     return None;
   }
 
   /// Emit C++ statements to capture instructions into local variables.
   ///
   /// Only InstructionOperandMatcher needs to do anything for this method.
   virtual void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                                   StringRef Expr) const {}
+                                   unsigned InsnVarID, unsigned OpIdx) const {}
 
   /// Emit a C++ expression that checks the predicate for the given operand.
   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                                    StringRef OperandExpr) const = 0;
+                                    unsigned InsnVarID,
+                                    unsigned OpIdx) const = 0;
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
 
public:
   LLTOperandMatcher(const LLTCodeGen &Ty)
       : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_LLT;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "MRI.getType(" << OperandExpr << ".getReg()) == (";
-    Ty.emitCxxConstructorCall(OS);
-    OS << ")";
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
+       << ", /*Type*/";
+    Ty.emitCxxEnumValue(OS);
+    OS << ", \n";
   }
 };
 
 /// Generates code to check that an operand is a particular target constant.
 class ComplexPatternOperandMatcher : public OperandPredicateMatcher {
 protected:
   const OperandMatcher &Operand;
   const Record &TheDef;
 
   unsigned getAllocatedTemporariesBaseID() const;
 
 public:
   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
                                const Record &TheDef)
       : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
         TheDef(TheDef) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_ComplexPattern;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
+                            unsigned InsnVarID, unsigned OpIdx) const override {
     unsigned ID = getAllocatedTemporariesBaseID();
-    OS << "(Renderer" << ID << " = " << TheDef.getValueAsString("MatcherFn")
-       << "(" << OperandExpr << "))";
+    OS << "    GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
+       << TheDef.getName() << ",\n";
   }
 
   unsigned countRendererFns() const override {
     return 1;
   }
 };
 
 /// Generates code to check that an operand is in a particular register bank.
 class RegisterBankOperandMatcher : public OperandPredicateMatcher {
 protected:
   const CodeGenRegisterClass &RC;
 
 public:
   RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
       : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_RegBank;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
-       << "RegClass) == RBI.getRegBank(" << OperandExpr
-       << ".getReg(), MRI, TRI))";
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
   }
 };
 
 /// Generates code to check that an operand is a basic block.
 class MBBOperandMatcher : public OperandPredicateMatcher {
 public:
   MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_MBB;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << OperandExpr << ".isMBB()";
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
   }
 };
 
 /// Generates code to check that an operand is a G_CONSTANT with a particular
 /// int.
 class ConstantIntOperandMatcher : public OperandPredicateMatcher {
 protected:
   int64_t Value;
 
 public:
   ConstantIntOperandMatcher(int64_t Value)
       : OperandPredicateMatcher(OPM_Int), Value(Value) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_Int;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", " << Value << ",\n";
   }
 };
 
 /// Generates code to check that an operand is a raw int (where MO.isImm() or
 /// MO.isCImm() is true).
 class LiteralIntOperandMatcher : public OperandPredicateMatcher {
 protected:
   int64_t Value;
 
 public:
   LiteralIntOperandMatcher(int64_t Value)
       : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_LiteralInt;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << OperandExpr << ".isCImm() && " << OperandExpr
-       << ".getCImm()->equalsInt(" << Value << ")";
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", " << Value << ",\n";
   }
 };
 
 /// Generates code to check that a set of predicates match for a particular
 /// operand.
 class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> {
 protected:
   InstructionMatcher &Insn;
public:
   bool hasSymbolicName() const { return !SymbolicName.empty(); }
   const StringRef getSymbolicName() const { return SymbolicName; }
   void setSymbolicName(StringRef Name) {
     assert(SymbolicName.empty() && "Operand already has a symbolic name");
     SymbolicName = Name;
   }
   unsigned getOperandIndex() const { return OpIdx; }
 
-  std::string getOperandExpr(StringRef InsnVarName) const {
-    return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
+  std::string getOperandExpr(unsigned InsnVarID) const {
+    return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
+           llvm::to_string(OpIdx) + ")";
   }
 
   Optional<const OperandMatcher *>
   getOptionalOperand(StringRef DesiredSymbolicName) const {
     assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand");
     if (DesiredSymbolicName == SymbolicName)
       return this;
     for (const auto &OP : predicates()) {
       const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName);
       if (MaybeOperand.hasValue())
         return MaybeOperand.getValue();
     }
     return None;
   }
 
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 
   /// Emit C++ statements to capture instructions into local variables.
   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                           StringRef OperandExpr) const {
+                           unsigned InsnVarID) const {
     for (const auto &Predicate : predicates())
-      Predicate->emitCxxCaptureStmts(OS, Rule, OperandExpr);
+      Predicate->emitCxxCaptureStmts(OS, Rule, InsnVarID, OpIdx);
   }
 
   /// Emit a C++ expression that tests whether the instruction named in
-  /// InsnVarName matches all the predicate and all the operands.
+  /// InsnVarID matches all the predicates and all the operands.
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const {
-    OS << "(/* ";
+                            unsigned InsnVarID) const {
+    OS << "    // MIs[" << InsnVarID << "] ";
     if (SymbolicName.empty())
       OS << "Operand " << OpIdx;
     else
       OS << SymbolicName;
-    OS << " */ ";
-    emitCxxPredicateListExpr(OS, Rule, getOperandExpr(InsnVarName));
-    OS << ")";
+    OS << "\n";
+    emitCxxPredicateListExpr(OS, Rule, InsnVarID, OpIdx);
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const OperandMatcher &B) const {
     // Operand matchers involving more predicates have higher priority.
     if (predicates_size() > B.predicates_size())

 
 public:
   InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
   virtual ~InstructionPredicateMatcher() {}
 
   PredicateKind getKind() const { return Kind; }
 
   /// Emit a C++ expression that tests whether the instruction named in
-  /// InsnVarName matches the predicate.
+  /// InsnVarID matches the predicate.
   virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                                    StringRef InsnVarName) const = 0;
+                                    unsigned InsnVarID) const = 0;
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   virtual bool
   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
public:
   InstructionOpcodeMatcher(const CodeGenInstruction *I)
       : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
 
   static bool classof(const InstructionPredicateMatcher *P) {
     return P->getKind() == IPM_Opcode;
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const override {
-    OS << InsnVarName << ".getOpcode() == " << I->Namespace
-       << "::" << I->TheDef->getName();
+                            unsigned InsnVarID) const override {
+    OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
+       << "::" << I->TheDef->getName() << ",\n";
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool
   isHigherPriorityThan(const InstructionPredicateMatcher &B) const override {
     if (InstructionPredicateMatcher::isHigherPriorityThan(B))
public:
   OperandVec::const_iterator operands_begin() const { return Operands.begin(); }
   OperandVec::const_iterator operands_end() const { return Operands.end(); }
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
 
   /// Emit C++ statements to check the shape of the match and capture
   /// instructions into local variables.
-  void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule, StringRef Expr) {
-    OS << "if (" << Expr << ".getNumOperands() < " << getNumOperands() << ")\n"
-       << "  return false;\n";
-    for (const auto &Operand : Operands) {
-      Operand->emitCxxCaptureStmts(OS, Rule, Operand->getOperandExpr(Expr));
-    }
+  void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
+                           unsigned InsnID) {
+    OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
+       << getNumOperands() << ",\n";
+    for (const auto &Operand : Operands)
+      Operand->emitCxxCaptureStmts(OS, Rule, InsnID);
   }
 
   /// Emit a C++ expression that tests whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const {
-    emitCxxPredicateListExpr(OS, Rule, InsnVarName);
-    for (const auto &Operand : Operands) {
-      OS << " &&\n(";
-      Operand->emitCxxPredicateExpr(OS, Rule, InsnVarName);
-      OS << ")";
-    }
+                            unsigned InsnVarID) const {
+    emitCxxPredicateListExpr(OS, Rule, InsnVarID);
+    for (const auto &Operand : Operands)
+      Operand->emitCxxPredicateExpr(OS, Rule, InsnVarID);
   }
 
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   bool isHigherPriorityThan(const InstructionMatcher &B) const {
     // Instruction matchers involving more operands have higher priority.
     if (Operands.size() > B.Operands.size())
public:
 
   Optional<const OperandMatcher *>
   getOptionalOperand(StringRef SymbolicName) const override {
     assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
     return InsnMatcher->getOptionalOperand(SymbolicName);
   }
 
   void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                           StringRef OperandExpr) const override {
-    OS << "if (!" << OperandExpr + ".isReg())\n"
-       << "  return false;\n"
-       << "if (TRI.isPhysicalRegister(" << OperandExpr + ".getReg()))\n"
-       << "  return false;\n";
-    std::string InsnVarName = Rule.defineInsnVar(
-        OS, *InsnMatcher,
-        ("*MRI.getVRegDef(" + OperandExpr + ".getReg())").str());
-    InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarName);
+                           unsigned InsnID, unsigned OpIdx) const override {
+    unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
+    InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarID);
   }
 
   void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OperandExpr = Rule.getInsnVarName(*InsnMatcher);
-    OS << "(";
-    InsnMatcher->emitCxxPredicateExpr(OS, Rule, OperandExpr);
-    OS << ")\n";
+                            unsigned InsnVarID_,
+                            unsigned OpIdx_) const override {
+    unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
+    InsnMatcher->emitCxxPredicateExpr(OS, Rule, InsnVarID);
   }
 };
 
 //===- Actions ------------------------------------------------------------===//
 class OperandRenderer {
 public:
   enum RendererKind {
     OR_Copy,
public:
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Copy;
   }
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
-    StringRef InsnVarName =
-        Rule.getInsnVarName(Operand.getInstructionMatcher());
-    std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
+    unsigned InsnVarID =
+        Rule.getInsnVarID(Operand.getInstructionMatcher());
+    std::string OperandExpr = Operand.getOperandExpr(InsnVarID);
     OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
   }
 };
 
 /// A CopySubRegRenderer emits code to copy a single register operand from an
 /// existing instruction to the one being built and indicate that only a
 /// subregister should be copied.
 class CopySubRegRenderer : public OperandRenderer {
public:
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_CopySubReg;
   }
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
-    StringRef InsnVarName =
-        Rule.getInsnVarName(Operand.getInstructionMatcher());
-    std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
+    unsigned InsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
+    std::string OperandExpr = Operand.getOperandExpr(InsnVarID);
     OS << "    MIB.addReg(" << OperandExpr << ".getReg() /*" << SymbolicName
        << "*/, 0, " << SubReg->EnumValue << ");\n";
   }
 };
 
 /// Adds a specific physical register to the instruction being built.
 /// This is typically useful for WZR/XZR on AArch64.
 class AddRegisterRenderer : public OperandRenderer {
RenderComplexPatternOperand(const Record &TheDef, StringRef SymbolicName,
       : OperandRenderer(OR_ComplexPattern), TheDef(TheDef),
         SymbolicName(SymbolicName), RendererID(RendererID) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_ComplexPattern;
   }
 
   void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "Renderer" << RendererID << "(MIB);\n";
+    OS << "    State.Renderers[" << RendererID << "](MIB);\n";
   }
 };
 
 /// An action taken when all Matcher predicates succeeded for a parent rule.
 ///
 /// Typical actions include:
 /// * Changing the opcode of an instruction.
 /// * Adding an operand to an instruction.

 private:
   const PatternToMatch &P;
 
 public:
   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 
   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
                           StringRef RecycleVarName) const override {
-    OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
+    OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
   }
 };
 
 /// Generates code to build an instruction or mutate an existing instruction
 /// into the desired instruction when this is possible.
 class BuildMIAction : public MatchAction {
 private:
   std::string Name;
if (canMutate()) {
 
       OS << "    MachineInstr &" << Name << " = " << RecycleVarName << ";\n";
       return;
     }
 
     // TODO: Simple permutation looks like it could be almost as common as
     //       mutation due to commutative operations.
 
-    OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
+    OS << "    MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
           "I.getDebugLoc(), TII.get("
        << I->Namespace << "::" << I->TheDef->getName() << "));\n";
     for (const auto &Renderer : OperandRenderers)
       Renderer->emitCxxRenderStmts(OS, Rule);
     OS << "    for (const auto *FromMI : ";
     Rule.emitCxxCapturedInsnList(OS);
     OS << ")\n";
     OS << "      for (const auto &MMO : FromMI->memoperands())\n";
InstructionMatcher &RuleMatcher::addInstructionMatcher() {
   Matchers.emplace_back(new InstructionMatcher());
   return *Matchers.back();
 }
 
 void RuleMatcher::addRequiredFeature(Record *Feature) {
   RequiredFeatures.push_back(Feature);
 }
 
+const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
+  return RequiredFeatures;
+}
+
 template <class Kind, class... Args>
 Kind &RuleMatcher::addAction(Args &&... args) {
   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
   return *static_cast<Kind *>(Actions.back().get());
 }
 
-std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
-                                       const InstructionMatcher &Matcher,
-                                       StringRef Value) {
-  std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
-  OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
-  InsnVariableNames[&Matcher] = InsnVarName;
-  return InsnVarName;
+unsigned
+RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
+  unsigned NewInsnVarID = NextInsnVarID++;
+  InsnVariableIDs[&Matcher] = NewInsnVarID;
+  return NewInsnVarID;
+}
+
+unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
+                                    unsigned InsnID, unsigned OpIdx) {
+  unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
+  OS << "    GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
+     << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
+     << "]\n";
+  return NewInsnVarID;
 }
 
-StringRef
-RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
-  const auto &I = InsnVariableNames.find(&InsnMatcher);
-  if (I != InsnVariableNames.end())
+unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
+  const auto &I = InsnVariableIDs.find(&InsnMatcher);
+  if (I != InsnVariableIDs.end())
     return I->second;
   llvm_unreachable("Matched Insn was not captured in a local variable");
 }
 
 /// Emit a C++ initializer_list containing references to every matched
 /// instruction.
 void RuleMatcher::emitCxxCapturedInsnList(raw_ostream &OS) {
-  SmallVector<StringRef, 2> Names;
-  for (const auto &Pair : InsnVariableNames)
-    Names.push_back(Pair.second);
-  std::sort(Names.begin(), Names.end());
+  SmallVector<unsigned, 2> IDs;
+  for (const auto &Pair : InsnVariableIDs)
+    IDs.push_back(Pair.second);
+  std::sort(IDs.begin(), IDs.end());
 
   OS << "{";
-  for (const auto &Name : Names)
-    OS << "&" << Name << ", ";
+  for (const auto &ID : IDs)
+    OS << "State.MIs[" << ID << "], ";
   OS << "}";
 }
 
 /// Emit C++ statements to check the shape of the match and capture
 /// instructions into local variables.
-void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
+void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS) {
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
-  std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
-  Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
+  unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
+  Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarID);
 }
 
-void RuleMatcher::emit(raw_ostream &OS,
-                       SubtargetFeatureInfoMap SubtargetFeatures) {
+void RuleMatcher::emit(raw_ostream &OS) {
   if (Matchers.empty())
     llvm_unreachable("Unexpected empty matcher!");
 
   // The representation supports rules that require multiple roots such as:
   //    %ptr(p0) = ...
   //    %elt0(s32) = G_LOAD %ptr
   //    %1(p0) = G_ADD %ptr, 4
   //    %elt1(s32) = G_LOAD p0 %1
   // which could be usefully folded into:
   //    %ptr(p0) = ...
   //    %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr
   // on some targets but we don't need to make use of that yet.
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
 
-  OS << "if (";
-  OS << "[&]() {\n";
+  OS << "  const static int64_t MatchTable" << NumPatternEmitted << "[] = {\n";
   if (!RequiredFeatures.empty()) {
-    OS << "  PredicateBitset ExpectedFeatures = {";
-    StringRef Separator = "";
-    for (const auto &Predicate : RequiredFeatures) {
-      const auto &I = SubtargetFeatures.find(Predicate);
-      assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
-      OS << Separator << I->second.getEnumBitName();
-      Separator = ", ";
-    }
-    OS << "};\n";
-    OS << "if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)\n"
-       << "  return false;\n";
+    OS << "    GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
+       << ",\n";
   }
 
-  emitCxxCaptureStmts(OS, "I");
 
-  OS << "    if (";
+  emitCxxCaptureStmts(OS);
+
   Matchers.front()->emitCxxPredicateExpr(OS, *this,
-                                         getInsnVarName(*Matchers.front()));
-  OS << ") {\n";
+                                         getInsnVarID(*Matchers.front()));
+
+  OS << "    GIM_Accept,\n"
+     << "  };\n"
+     << "  State.MIs.clear();\n"
+     << "  State.MIs.push_back(&I);\n"
+     << "  if (executeMatchTable(*this, State, MatcherInfo, MatchTable"
+     << NumPatternEmitted << ", MRI, TRI, RBI, AvailableFeatures)) {\n";
 
   // We must also check if it's safe to fold the matched instructions.
-  if (InsnVariableNames.size() >= 2) {
+  if (InsnVariableIDs.size() >= 2) {
     // Invert the map to create stable ordering (by var names)
-    SmallVector<StringRef, 2> Names;
-    for (const auto &Pair : InsnVariableNames) {
+    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())
         continue;
 
-      Names.push_back(Pair.second);
+      InsnIDs.push_back(Pair.second);
     }
-    std::sort(Names.begin(), Names.end());
+    std::sort(InsnIDs.begin(), InsnIDs.end());
 
-    for (const auto &Name : Names) {
+    for (const auto &InsnID : InsnIDs) {
       // Reject the difficult cases until we have a more accurate check.
-      OS << "      if (!isObviouslySafeToFold(" << Name
-         << ")) return false;\n";
+      OS << "    if (!isObviouslySafeToFold(*State.MIs[" << InsnID << "]))\n"
+         << "      return false;\n";
 
       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
       //        account for unsafe cases.
       //
       //        Example:
       //          MI1--> %0 = ...
       //                 %1 = ... %0
       //          MI0--> %2 = ... %0
for (const auto &InsnID : InsnIDs) {
       //          by rejecting all loads.
     }
   }
 
   for (const auto &MA : Actions) {
     MA->emitCxxActionStmts(OS, *this, "I");
   }
 
-  OS << "      return true;\n";
-  OS << "    }\n";
-  OS << "    return false;\n";
-  OS << "  }()) { return true; }\n\n";
+  OS << "    return true;\n";
+  OS << "  }\n\n";
 }
 
 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
   // Rules involving more match roots have higher priority.
   if (Matchers.size() > B.Matchers.size())
     return true;
   if (Matchers.size() < B.Matchers.size())
     return false;
std::stable_sort(Rules.begin(), Rules.end(),
                 assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
                                                      "and less important at "
                                                      "the same time");
                 return true;
               }
               return false;
             });
 
+  std::vector<Record *> ComplexPredicates =
+      RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
+  std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
+            [](const Record *A, const Record *B) {
+              if (A->getName() < B->getName())
+                return true;
+              return false;
+            });
   unsigned MaxTemporaries = 0;
   for (const auto &Rule : Rules)
     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
      << ";\n"
      << "using PredicateBitset = "
         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
 
-  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
-  for (unsigned I = 0; I < MaxTemporaries; ++I)
-    OS << "  mutable ComplexRendererFn Renderer" << I << ";\n";
-  OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
-
-  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
-  for (unsigned I = 0; I < MaxTemporaries; ++I)
-    OS << ", Renderer" << I << "(nullptr)\n";
-  OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
+     << "  mutable MatcherState State;\n"
+     << "  typedef "
+        "ComplexRendererFn("
+     << Target.getName()
+     << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
+     << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
+        "MatcherInfo;\n"
+     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
+
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
+     << ", State(" << MaxTemporaries << "),\n"
+     << "MatcherInfo({TypeObjects, FeatureBitsets, {\n"
+     << "  nullptr, // GICP_Invalid\n";
+  for (const auto &Record : ComplexPredicates)
+    OS << "  &" << Target.getName()
+       << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
+       << ", // " << Record->getName() << "\n";
+  OS << "}})\n"
+     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
                                                            OS);
 
   // Separate subtarget features by how often they must be recomputed.
   SubtargetFeatureInfoMap ModuleFeatures;
   std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(),
void GlobalISelEmitter::run(raw_ostream &OS) {
   SubtargetFeatureInfo::emitComputeAvailableFeatures(
       Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
       ModuleFeatures, OS);
   SubtargetFeatureInfo::emitComputeAvailableFeatures(
       Target.getName(), "InstructionSelector",
       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
       "const MachineFunction *MF");
 
+  // Emit a table containing the LLT objects needed by the matcher and an enum
+  // for the matcher to reference them with.
+  std::vector<LLTCodeGen> TypeObjects = {
+      LLT::scalar(8),      LLT::scalar(16),     LLT::scalar(32),
+      LLT::scalar(64),     LLT::scalar(80),     LLT::vector(8, 1),
+      LLT::vector(16, 1),  LLT::vector(32, 1),  LLT::vector(64, 1),
+      LLT::vector(8, 8),   LLT::vector(16, 8),  LLT::vector(32, 8),
+      LLT::vector(64, 8),  LLT::vector(4, 16),  LLT::vector(8, 16),
+      LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32),
+      LLT::vector(4, 32),  LLT::vector(8, 32),  LLT::vector(16, 32),
+      LLT::vector(2, 64),  LLT::vector(4, 64),  LLT::vector(8, 64),
+  };
+  std::sort(TypeObjects.begin(), TypeObjects.end());
+  OS << "enum {\n";
+  for (const auto &TypeObject : TypeObjects) {
+    OS << "  ";
+    TypeObject.emitCxxEnumValue(OS);
+    OS << ",\n";
+  }
+  OS << "};\n"
+     << "const static LLT TypeObjects[] = {\n";
+  for (const auto &TypeObject : TypeObjects) {
+    OS << "  ";
+    TypeObject.emitCxxConstructorCall(OS);
+    OS << ",\n";
+  }
+  OS << "};\n\n";
+
+  // Emit a table containing the PredicateBitsets objects needed by the matcher
+  // and an enum for the matcher to reference them with.
+  std::vector<std::vector<Record *>> FeatureBitsets;
+  for (auto &Rule : Rules)
+    FeatureBitsets.push_back(Rule.getRequiredFeatures());
+  std::sort(
+      FeatureBitsets.begin(), FeatureBitsets.end(),
+      [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
+        if (A.size() < B.size())
+          return true;
+        if (A.size() > B.size())
+          return false;
+        for (const auto &Pair : zip(A, B)) {
+          if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
+            return true;
+          if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
+            return false;
+        }
+        return false;
+      });
+  FeatureBitsets.erase(
+      std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
+      FeatureBitsets.end());
+  OS << "enum {\n"
+     << "  GIFBS_Invalid,\n";
+  for (const auto &FeatureBitset : FeatureBitsets) {
+    if (FeatureBitset.empty())
+      continue;
+    OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
+  }
+  OS << "};\n"
+     << "const static PredicateBitset FeatureBitsets[] {\n"
+     << "  {}, // GIFBS_Invalid\n";
+  for (const auto &FeatureBitset : FeatureBitsets) {
+    if (FeatureBitset.empty())
+      continue;
+    OS << "  {";
+    for (const auto &Feature : FeatureBitset) {
+      const auto &I = SubtargetFeatures.find(Feature);
+      assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
+      OS << I->second.getEnumBitName() << ", ";
+    }
+    OS << "},\n";
+  }
+  OS << "};\n\n";
+
+  // Emit complex predicate table and an enum to reference them with.
+  OS << "enum {\n"
+     << "  GICP_Invalid,\n";
+  for (const auto &Record : ComplexPredicates)
+    OS << "  GICP_" << Record->getName() << ",\n";
+  OS << "};\n"
+     << "// See constructor for table contents\n\n";
+
   OS << "bool " << Target.getName()
      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
-     << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
+     << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
      << "  // FIXME: This should be computed on a per-function basis rather "
         "than per-insn.\n"
      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
         "&MF);\n"
      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n";
 
   for (auto &Rule : Rules) {
-    Rule.emit(OS, SubtargetFeatures);
+    Rule.emit(OS);
     ++NumPatternEmitted;
   }
 
   OS << "  return false;\n"
      << "}\n"
      << "#endif // ifdef GET_GLOBALISEL_IMPL\n";
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n"