[globalisel][tablegen] Add control-flow to the MatchTable.

Summary:
This will allow us to merge the various sub-tables into a single table. This is a
compile-time saving at this point. However, this will also enable the optimization
of a table so that similar instructions can be tested together, reducing the time
spent on the matching the code.

The bulk of this patch is a mechanical conversion to the new MatchTable object
which is responsible for tracking label definitions and filling in the index of
the jump targets. It is also responsible for nicely formatting the table.

This was necessary to support the new GIM_Try opcode which takes the index to
jump to if the match should fail. This value is unknown during table
construction and is filled in during emission. To support nesting try-blocks
(although we currently don't emit tables with nested try-blocks), GIM_Reject
has been re-introduced to explicitly exit a try-block or fail the overall match
if there are no active try-blocks.

Reviewers: ab, t.p.northover, qcolombet, rovka, aditya_nandakumar

Reviewed By: rovka

Subscribers: kristof.beyls, igorb, llvm-commits

Differential Revision: https://reviews.llvm.org/D35117

llvm-svn: 308596

1 files changed, 411 insertions, 119 deletions

diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index cafcbeb57de..2cfcadd5e80 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -76,6 +76,14 @@ private:
 public:
   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 
+  std::string getCxxEnumValue() const {
+    std::string Str;
+    raw_string_ostream OS(Str);
+
+    emitCxxEnumValue(OS);
+    return OS.str();
+  }
+
   void emitCxxEnumValue(raw_ostream &OS) const {
     if (Ty.isScalar()) {
       OS << "GILLT_s" << Ty.getSizeInBits();
@@ -217,6 +225,222 @@ getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
     Name += ("_" + Feature->getName()).str();
   return Name;
 }
+
+//===- MatchTable Helpers -------------------------------------------------===//
+
+class MatchTable;
+
+/// A record to be stored in a MatchTable.
+///
+/// This class represents any and all output that may be required to emit the
+/// MatchTable. Instances  are most often configured to represent an opcode or
+/// value that will be emitted to the table with some formatting but it can also
+/// represent commas, comments, and other formatting instructions.
+struct MatchTableRecord {
+  enum RecordFlagsBits {
+    MTRF_None = 0x0,
+    /// Causes EmitStr to be formatted as comment when emitted.
+    MTRF_Comment = 0x1,
+    /// Causes the record value to be followed by a comma when emitted.
+    MTRF_CommaFollows = 0x2,
+    /// Causes the record value to be followed by a line break when emitted.
+    MTRF_LineBreakFollows = 0x4,
+    /// Indicates that the record defines a label and causes an additional
+    /// comment to be emitted containing the index of the label.
+    MTRF_Label = 0x8,
+    /// Causes the record to be emitted as the index of the label specified by
+    /// LabelID along with a comment indicating where that label is.
+    MTRF_JumpTarget = 0x10,
+    /// Causes the formatter to add a level of indentation before emitting the
+    /// record.
+    MTRF_Indent = 0x20,
+    /// Causes the formatter to remove a level of indentation after emitting the
+    /// record.
+    MTRF_Outdent = 0x40,
+  };
+
+  /// When MTRF_Label or MTRF_JumpTarget is used, indicates a label id to
+  /// reference or define.
+  unsigned LabelID;
+  /// The string to emit. Depending on the MTRF_* flags it may be a comment, a
+  /// value, a label name.
+  std::string EmitStr;
+
+private:
+  /// The number of MatchTable elements described by this record. Comments are 0
+  /// while values are typically 1. Values >1 may occur when we need to emit
+  /// values that exceed the size of a MatchTable element.
+  unsigned NumElements;
+
+public:
+  /// A bitfield of RecordFlagsBits flags.
+  unsigned Flags;
+
+  MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
+                   unsigned NumElements, unsigned Flags)
+      : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
+        EmitStr(EmitStr), NumElements(NumElements), Flags(Flags) {
+    assert((!LabelID_.hasValue() || LabelID != ~0u) &&
+           "This value is reserved for non-labels");
+  }
+
+  void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
+            const MatchTable &Table) const;
+  unsigned size() const { return NumElements; }
+};
+
+/// Holds the contents of a generated MatchTable to enable formatting and the
+/// necessary index tracking needed to support GIM_Try.
+class MatchTable {
+  /// An unique identifier for the table. The generated table will be named
+  /// MatchTable${ID}.
+  unsigned ID;
+  /// The records that make up the table. Also includes comments describing the
+  /// values being emitted and line breaks to format it.
+  std::vector<MatchTableRecord> Contents;
+  /// The currently defined labels.
+  DenseMap<unsigned, unsigned> LabelMap;
+  /// Tracks the sum of MatchTableRecord::NumElements as the table is built.
+  unsigned CurrentSize;
+
+public:
+  static MatchTableRecord LineBreak;
+  static MatchTableRecord Comment(StringRef Comment) {
+    return MatchTableRecord(None, Comment, 0, MatchTableRecord::MTRF_Comment);
+  }
+  static MatchTableRecord Opcode(StringRef Opcode, int IndentAdjust = 0) {
+    unsigned ExtraFlags = 0;
+    if (IndentAdjust > 0)
+      ExtraFlags |= MatchTableRecord::MTRF_Indent;
+    if (IndentAdjust < 0)
+      ExtraFlags |= MatchTableRecord::MTRF_Outdent;
+
+    return MatchTableRecord(None, Opcode, 1,
+                            MatchTableRecord::MTRF_CommaFollows | ExtraFlags);
+  }
+  static MatchTableRecord NamedValue(StringRef NamedValue) {
+    return MatchTableRecord(None, NamedValue, 1,
+                            MatchTableRecord::MTRF_CommaFollows);
+  }
+  static MatchTableRecord NamedValue(StringRef Namespace,
+                                     StringRef NamedValue) {
+    return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
+                            MatchTableRecord::MTRF_CommaFollows);
+  }
+  static MatchTableRecord IntValue(int64_t IntValue) {
+    return MatchTableRecord(None, llvm::to_string(IntValue), 1,
+                            MatchTableRecord::MTRF_CommaFollows);
+  }
+  static MatchTableRecord Label(unsigned LabelID) {
+    return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
+                            MatchTableRecord::MTRF_Label |
+                                MatchTableRecord::MTRF_Comment |
+                                MatchTableRecord::MTRF_LineBreakFollows);
+  }
+  static MatchTableRecord JumpTarget(unsigned LabelID) {
+    return MatchTableRecord(LabelID, "Label " + llvm::to_string(LabelID), 0,
+                            MatchTableRecord::MTRF_JumpTarget |
+                                MatchTableRecord::MTRF_Comment |
+                                MatchTableRecord::MTRF_CommaFollows);
+  }
+
+  MatchTable(unsigned ID) : ID(ID), CurrentSize(0) {}
+
+  void push_back(const MatchTableRecord &Value) {
+    if (Value.Flags & MatchTableRecord::MTRF_Label)
+      defineLabel(Value.LabelID);
+    Contents.push_back(Value);
+    CurrentSize += Value.size();
+  }
+
+  void defineLabel(unsigned LabelID) {
+    LabelMap.insert(std::make_pair(LabelID, CurrentSize + 1));
+  }
+
+  unsigned getLabelIndex(unsigned LabelID) const {
+    const auto I = LabelMap.find(LabelID);
+    assert(I != LabelMap.end() && "Use of undeclared label");
+    return I->second;
+  }
+
+  void emit(raw_ostream &OS) const {
+    unsigned Indentation = 4;
+    OS << "  const static int64_t MatchTable" << ID << "[] = {";
+    LineBreak.emit(OS, true, *this);
+    OS << std::string(Indentation, ' ');
+
+    for (auto I = Contents.begin(), E = Contents.end(); I != E;
+         ++I) {
+      bool LineBreakIsNext = false;
+      const auto &NextI = std::next(I);
+
+      if (NextI != E) {
+        if (NextI->EmitStr == "" &&
+            NextI->Flags == MatchTableRecord::MTRF_LineBreakFollows)
+          LineBreakIsNext = true;
+      }
+
+      if (I->Flags & MatchTableRecord::MTRF_Indent)
+        Indentation += 2;
+
+      I->emit(OS, LineBreakIsNext, *this);
+      if (I->Flags & MatchTableRecord::MTRF_LineBreakFollows)
+        OS << std::string(Indentation, ' ');
+
+      if (I->Flags & MatchTableRecord::MTRF_Outdent)
+        Indentation -= 2;
+    }
+    OS << "};\n";
+  }
+};
+
+MatchTableRecord MatchTable::LineBreak = {
+    None, "" /* Emit String */, 0 /* Elements */,
+    MatchTableRecord::MTRF_LineBreakFollows};
+
+void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
+                            const MatchTable &Table) const {
+  bool UseLineComment =
+      LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);
+  if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
+    UseLineComment = false;
+
+  if (Flags & MTRF_Comment)
+    OS << (UseLineComment ? "// " : "/*");
+
+  OS << EmitStr;
+  if (Flags & MTRF_Label)
+    OS << ": @" << Table.getLabelIndex(LabelID);
+
+  if (Flags & MTRF_Comment && !UseLineComment)
+    OS << "*/";
+
+  if (Flags & MTRF_JumpTarget) {
+    if (Flags & MTRF_Comment)
+      OS << " ";
+    OS << Table.getLabelIndex(LabelID);
+  }
+
+  if (Flags & MTRF_CommaFollows) {
+    OS << ",";
+    if (!LineBreakIsNextAfterThis && !(Flags & MTRF_LineBreakFollows))
+      OS << " ";
+  }
+
+  if (Flags & MTRF_LineBreakFollows)
+    OS << "\n";
+}
+
+MatchTable &operator<<(MatchTable &Table, const MatchTableRecord &Value) {
+  Table.push_back(Value);
+  return Table;
+}
+
+raw_ostream &operator<<(raw_ostream &OS, const MatchTable &Table) {
+  Table.emit(OS);
+  return OS;
+}
+
 //===- Matchers -----------------------------------------------------------===//
 
 class OperandMatcher;
@@ -259,11 +483,11 @@ public:
   /// 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 defineInsnVar(MatchTable &Table, const InstructionMatcher &Matcher,
                          unsigned InsnVarID, unsigned OpIdx);
   unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
 
-  void emitCaptureOpcodes(raw_ostream &OS);
+  void emitCaptureOpcodes(MatchTable &Table);
 
   void emit(raw_ostream &OS);
 
@@ -309,14 +533,14 @@ public:
 
   /// Emit MatchTable opcodes that tests whether all the predicates are met.
   template <class... Args>
-  void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const {
+  void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) const {
     if (Predicates.empty()) {
-      OS << "// No predicates\n";
+      Table << MatchTable::Comment("No predicates") << MatchTable::LineBreak;
       return;
     }
 
     for (const auto &Predicate : predicates())
-      Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...);
+      Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
   }
 };
 
@@ -370,11 +594,11 @@ public:
   ///
   /// Only InstructionOperandMatcher needs to do anything for this method the
   /// rest just walk the tree.
-  virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  virtual void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
                                   unsigned InsnVarID, unsigned OpIdx) const {}
 
   /// Emit MatchTable opcodes that check the predicate for the given operand.
-  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  virtual void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                                     unsigned InsnVarID,
                                     unsigned OpIdx) const = 0;
 
@@ -403,12 +627,13 @@ public:
     return P->getKind() == OPM_LLT;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
-       << ", /*Type*/";
-    Ty.emitCxxEnumValue(OS);
-    OS << ", \n";
+    Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
+          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
+          << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
+          << MatchTable::NamedValue(Ty.getCxxEnumValue())
+          << MatchTable::LineBreak;
   }
 };
 
@@ -430,12 +655,15 @@ public:
     return P->getKind() == OPM_ComplexPattern;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
     unsigned ID = getAllocatedTemporariesBaseID();
-    OS << "    GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
-       << TheDef.getName() << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckComplexPattern")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("Renderer") << MatchTable::IntValue(ID)
+          << MatchTable::NamedValue(("GICP_" + TheDef.getName()).str())
+          << MatchTable::LineBreak;
   }
 
   unsigned countRendererFns() const override {
@@ -456,10 +684,14 @@ public:
     return P->getKind() == OPM_RegBank;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
+    Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("RC")
+          << MatchTable::NamedValue(RC.getQualifiedName() + "RegClassID")
+          << MatchTable::LineBreak;
   }
 };
 
@@ -472,9 +704,11 @@ public:
     return P->getKind() == OPM_MBB;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
+          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
+          << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
   }
 };
 
@@ -492,10 +726,12 @@ public:
     return P->getKind() == OPM_Int;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", " << Value << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckConstantInt")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::IntValue(Value) << MatchTable::LineBreak;
   }
 };
 
@@ -513,10 +749,12 @@ public:
     return P->getKind() == OPM_LiteralInt;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", " << Value << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckLiteralInt")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::IntValue(Value) << MatchTable::LineBreak;
   }
 };
 
@@ -533,10 +771,13 @@ public:
     return P->getKind() == OPM_IntrinsicID;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
+          << MatchTable::LineBreak;
   }
 };
 
@@ -589,23 +830,26 @@ public:
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 
   /// Emit MatchTable opcodes to capture instructions into the MIs table.
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
                           unsigned InsnVarID) const {
     for (const auto &Predicate : predicates())
-      Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
+      Predicate->emitCaptureOpcodes(Table, Rule, InsnVarID, OpIdx);
   }
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarID matches all the predicates and all the operands.
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID) const {
-    OS << "    // MIs[" << InsnVarID << "] ";
+    std::string Comment;
+    raw_string_ostream CommentOS(Comment);
+    CommentOS << "MIs[" << InsnVarID << "] ";
     if (SymbolicName.empty())
-      OS << "Operand " << OpIdx;
+      CommentOS << "Operand " << OpIdx;
     else
-      OS << SymbolicName;
-    OS << "\n";
-    emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx);
+      CommentOS << SymbolicName;
+    Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
+
+    emitPredicateListOpcodes(Table, Rule, InsnVarID, OpIdx);
   }
 
   /// Compare the priority of this object and B.
@@ -673,7 +917,7 @@ public:
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarID matches the predicate.
-  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  virtual void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                                     unsigned InsnVarID) const = 0;
 
   /// Compare the priority of this object and B.
@@ -702,10 +946,12 @@ public:
     return P->getKind() == IPM_Opcode;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID) const override {
-    OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
-       << "::" << I->TheDef->getName() << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
+          << MatchTable::IntValue(InsnVarID)
+          << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
+          << MatchTable::LineBreak;
   }
 
   /// Compare the priority of this object and B.
@@ -795,21 +1041,23 @@ public:
 
   /// Emit MatchTable opcodes to check the shape of the match and capture
   /// instructions into the MIs table.
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
                           unsigned InsnID) {
-    OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
-       << getNumOperands() << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckNumOperands")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("Expected")
+          << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
     for (const auto &Operand : Operands)
-      Operand->emitCaptureOpcodes(OS, Rule, InsnID);
+      Operand->emitCaptureOpcodes(Table, Rule, InsnID);
   }
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID) const {
-    emitPredicateListOpcodes(OS, Rule, InsnVarID);
+    emitPredicateListOpcodes(Table, Rule, InsnVarID);
     for (const auto &Operand : Operands)
-      Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
+      Operand->emitPredicateOpcodes(Table, Rule, InsnVarID);
   }
 
   /// Compare the priority of this object and B.
@@ -886,17 +1134,17 @@ public:
     return InsnMatcher->getOptionalOperand(SymbolicName);
   }
 
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
                           unsigned InsnID, unsigned OpIdx) const override {
-    unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
-    InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
+    unsigned InsnVarID = Rule.defineInsnVar(Table, *InsnMatcher, InsnID, OpIdx);
+    InsnMatcher->emitCaptureOpcodes(Table, Rule, InsnVarID);
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
                             unsigned InsnVarID_,
                             unsigned OpIdx_) const override {
     unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
-    InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
+    InsnMatcher->emitPredicateOpcodes(Table, Rule, InsnVarID);
   }
 };
 
@@ -920,7 +1168,8 @@ public:
 
   RendererKind getKind() const { return Kind; }
 
-  virtual void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const = 0;
+  virtual void emitRenderOpcodes(MatchTable &Table,
+                                 RuleMatcher &Rule) const = 0;
 };
 
 /// A CopyRenderer emits code to copy a single operand from an existing
@@ -947,12 +1196,14 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
-    OS << "    GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/"
-       << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // "
-       << SymbolicName << "\n";
+    Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
+          << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
+          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
 
@@ -983,13 +1234,17 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
-    OS << "    GIR_CopySubReg, /*NewInsnID*/" << NewInsnID
-       << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/"
-       << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue
-       << ", // " << SymbolicName << "\n";
+    Table << MatchTable::Opcode("GIR_CopySubReg")
+          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
+          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::Comment("SubRegIdx")
+          << MatchTable::IntValue(SubReg->EnumValue)
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
 
@@ -1009,12 +1264,15 @@ public:
     return R->getKind() == OR_Register;
   }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "      GIR_AddRegister, /*InsnID*/" << InsnID << ", "
-       << (RegisterDef->getValue("Namespace")
-               ? RegisterDef->getValueAsString("Namespace")
-               : "")
-       << "::" << RegisterDef->getName() << ",\n";
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIR_AddRegister")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::NamedValue(
+                 (RegisterDef->getValue("Namespace")
+                      ? RegisterDef->getValueAsString("Namespace")
+                      : ""),
+                 RegisterDef->getName())
+          << MatchTable::LineBreak;
   }
 };
 
@@ -1032,9 +1290,10 @@ public:
     return R->getKind() == OR_Imm;
   }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "      GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm
-       << ",\n";
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIR_AddImm") << MatchTable::Comment("InsnID")
+          << MatchTable::IntValue(InsnID) << MatchTable::Comment("Imm")
+          << MatchTable::IntValue(Imm) << MatchTable::LineBreak;
   }
 };
 
@@ -1064,9 +1323,11 @@ public:
     return R->getKind() == OR_ComplexPattern;
   }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "    GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/"
-       << RendererID << ",\n";
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIR_ComplexRenderer")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("RendererID")
+          << MatchTable::IntValue(RendererID) << MatchTable::LineBreak;
   }
 };
 
@@ -1079,13 +1340,13 @@ class MatchAction {
 public:
   virtual ~MatchAction() {}
 
-  /// Emit the C++ statements to implement the action.
+  /// Emit the MatchTable opcodes to implement the action.
   ///
   /// \param RecycleInsnID If given, it's an instruction to recycle. The
   ///                      requirements on the instruction vary from action to
   ///                      action.
-  virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                                  unsigned RecycleInsnID) const = 0;
+  virtual void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                                 unsigned RecycleInsnID) const = 0;
 };
 
 /// Generates a comment describing the matched rule being acted upon.
@@ -1096,10 +1357,11 @@ private:
 public:
   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
-    OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern()
-       << "\n";
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                         unsigned RecycleInsnID) const override {
+    Table << MatchTable::Comment(llvm::to_string(*P.getSrcPattern()) + "  =>  " +
+                               llvm::to_string(*P.getDstPattern()))
+          << MatchTable::LineBreak;
   }
 };
 
@@ -1142,27 +1404,35 @@ public:
     return *static_cast<Kind *>(OperandRenderers.back().get());
   }
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                         unsigned RecycleInsnID) const override {
     if (canMutate()) {
-      OS << "    GIR_MutateOpcode, /*InsnID*/" << InsnID
-         << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
-         << I->Namespace << "::" << I->TheDef->getName() << ",\n";
+      Table << MatchTable::Opcode("GIR_MutateOpcode")
+            << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+            << MatchTable::Comment("RecycleInsnID")
+            << MatchTable::IntValue(RecycleInsnID)
+            << MatchTable::Comment("Opcode")
+            << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
+            << MatchTable::LineBreak;
 
       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
         for (auto Def : I->ImplicitDefs) {
           auto Namespace = Def->getValue("Namespace")
                                ? Def->getValueAsString("Namespace")
                                : "";
-          OS << "    GIR_AddImplicitDef, " << InsnID << ", " << Namespace
-             << "::" << Def->getName() << ",\n";
+          Table << MatchTable::Opcode("GIR_AddImplicitDef")
+                << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+                << MatchTable::NamedValue(Namespace, Def->getName())
+                << MatchTable::LineBreak;
         }
         for (auto Use : I->ImplicitUses) {
           auto Namespace = Use->getValue("Namespace")
                                ? Use->getValueAsString("Namespace")
                                : "";
-          OS << "    GIR_AddImplicitUse, " << InsnID << ", " << Namespace
-             << "::" << Use->getName() << ",\n";
+          Table << MatchTable::Opcode("GIR_AddImplicitUse")
+                << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+                << MatchTable::NamedValue(Namespace, Use->getName())
+                << MatchTable::LineBreak;
         }
       }
       return;
@@ -1171,13 +1441,18 @@ public:
     // TODO: Simple permutation looks like it could be almost as common as
     //       mutation due to commutative operations.
 
-    OS << "    GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/"
-       << I->Namespace << "::" << I->TheDef->getName() << ",\n";
+    Table << MatchTable::Opcode("GIR_BuildMI") << MatchTable::Comment("InsnID")
+          << MatchTable::IntValue(InsnID) << MatchTable::Comment("Opcode")
+          << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
+          << MatchTable::LineBreak;
     for (const auto &Renderer : OperandRenderers)
-      Renderer->emitRenderOpcodes(OS, Rule);
+      Renderer->emitRenderOpcodes(Table, Rule);
 
-    OS << "    GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
-       << "    GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
+    Table << MatchTable::Opcode("GIR_MergeMemOperands")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::LineBreak << MatchTable::Opcode("GIR_EraseFromParent")
+          << MatchTable::Comment("InsnID")
+          << MatchTable::IntValue(RecycleInsnID) << MatchTable::LineBreak;
   }
 };
 
@@ -1189,9 +1464,11 @@ class ConstrainOperandsToDefinitionAction : public MatchAction {
 public:
   ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
-    OS << "    GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n";
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                         unsigned RecycleInsnID) const override {
+    Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::LineBreak;
   }
 };
 
@@ -1207,10 +1484,13 @@ public:
                                    const CodeGenRegisterClass &RC)
       : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
-    OS << "    GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/"
-       << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n";
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule,
+                         unsigned RecycleInsnID) const override {
+    Table << MatchTable::Opcode("GIR_ConstrainOperandRC")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("RC " + RC.getName())
+          << MatchTable::IntValue(RC.EnumValue) << MatchTable::LineBreak;
   }
 };
 
@@ -1240,13 +1520,16 @@ RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
   return NewInsnVarID;
 }
 
-unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
+unsigned RuleMatcher::defineInsnVar(MatchTable &Table,
                                     const InstructionMatcher &Matcher,
                                     unsigned InsnID, unsigned OpIdx) {
   unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
-  OS << "    GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
-     << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
-     << "]\n";
+  Table << MatchTable::Opcode("GIM_RecordInsn")
+        << MatchTable::Comment("DefineMI") << MatchTable::IntValue(NewInsnVarID)
+        << MatchTable::Comment("MI") << MatchTable::IntValue(InsnID)
+        << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
+        << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
+        << MatchTable::LineBreak;
   return NewInsnVarID;
 }
 
@@ -1259,10 +1542,10 @@ unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const
 
 /// Emit MatchTable opcodes to check the shape of the match and capture
 /// instructions into local variables.
-void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) {
+void RuleMatcher::emitCaptureOpcodes(MatchTable &Table) {
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
   unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
-  Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID);
+  Matchers.front()->emitCaptureOpcodes(Table, *this, InsnVarID);
 }
 
 void RuleMatcher::emit(raw_ostream &OS) {
@@ -1280,15 +1563,20 @@ void RuleMatcher::emit(raw_ostream &OS) {
   // 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 << "  const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n";
+  MatchTable Table(CurrentMatchTableID);
+  Table << MatchTable::Opcode("GIM_Try", +1)
+        << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(0)
+        << MatchTable::LineBreak;
+
   if (!RequiredFeatures.empty()) {
-    OS << "    GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
-       << ",\n";
+    Table << MatchTable::Opcode("GIM_CheckFeatures")
+          << MatchTable::NamedValue(getNameForFeatureBitset(RequiredFeatures))
+          << MatchTable::LineBreak;
   }
 
-  emitCaptureOpcodes(OS);
+  emitCaptureOpcodes(Table);
 
-  Matchers.front()->emitPredicateOpcodes(OS, *this,
+  Matchers.front()->emitPredicateOpcodes(Table, *this,
                                          getInsnVarID(*Matchers.front()));
 
   // We must also check if it's safe to fold the matched instructions.
@@ -1307,7 +1595,9 @@ void RuleMatcher::emit(raw_ostream &OS) {
 
     for (const auto &InsnID : InsnIDs) {
       // Reject the difficult cases until we have a more accurate check.
-      OS << "    GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n";
+      Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
+            << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+            << MatchTable::LineBreak;
 
       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
       //        account for unsafe cases.
@@ -1347,9 +1637,11 @@ void RuleMatcher::emit(raw_ostream &OS) {
   }
 
   for (const auto &MA : Actions)
-    MA->emitCxxActionStmts(OS, *this, 0);
-  OS << "    GIR_Done,\n"
-     << "  };\n"
+    MA->emitActionOpcodes(Table, *this, 0);
+  Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+        << MatchTable::Label(0) << MatchTable::Opcode("GIM_Reject")
+        << MatchTable::LineBreak;
+  OS << Table
      << "  State.MIs.resize(1);\n"
      << "  DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
      << "\\n\");\n"