vendor/llvm/llvm-trunk-r321017

1 files changed, 2270 insertions, 509 deletions

diff --git a/utils/TableGen/GlobalISelEmitter.cpp b/utils/TableGen/GlobalISelEmitter.cpp
index cafcbeb57de57..b80f023550622 100644
--- a/utils/TableGen/GlobalISelEmitter.cpp
+++ b/utils/TableGen/GlobalISelEmitter.cpp
@@ -36,6 +36,7 @@
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineValueType.h"
+#include "llvm/Support/CodeGenCoverage.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
@@ -43,8 +44,8 @@
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
-#include <string>
 #include <numeric>
+#include <string>
 using namespace llvm;
 
 #define DEBUG_TYPE "gisel-emitter"
@@ -52,9 +53,8 @@ using namespace llvm;
 STATISTIC(NumPatternTotal, "Total number of patterns");
 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
+STATISTIC(NumPatternsTested, "Number of patterns executed according to coverage information");
 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
-/// A unique identifier for a MatchTable.
-static unsigned CurrentMatchTableID = 0;
 
 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
 
@@ -64,9 +64,35 @@ static cl::opt<bool> WarnOnSkippedPatterns(
              "in the GlobalISel selector"),
     cl::init(false), cl::cat(GlobalISelEmitterCat));
 
+static cl::opt<bool> GenerateCoverage(
+    "instrument-gisel-coverage",
+    cl::desc("Generate coverage instrumentation for GlobalISel"),
+    cl::init(false), cl::cat(GlobalISelEmitterCat));
+
+static cl::opt<std::string> UseCoverageFile(
+    "gisel-coverage-file", cl::init(""),
+    cl::desc("Specify file to retrieve coverage information from"),
+    cl::cat(GlobalISelEmitterCat));
+
+static cl::opt<bool> OptimizeMatchTable(
+    "optimize-match-table",
+    cl::desc("Generate an optimized version of the match table"),
+    cl::init(true), cl::cat(GlobalISelEmitterCat));
+
 namespace {
 //===- Helper functions ---------------------------------------------------===//
 
+/// Get the name of the enum value used to number the predicate function.
+std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) {
+  return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" +
+         Predicate.getFnName();
+}
+
+/// Get the opcode used to check this predicate.
+std::string getMatchOpcodeForPredicate(const TreePredicateFn &Predicate) {
+  return "GIM_Check" + Predicate.getImmTypeIdentifier().str() + "ImmPredicate";
+}
+
 /// This class stands in for LLT wherever we want to tablegen-erate an
 /// equivalent at compiler run-time.
 class LLTCodeGen {
@@ -76,6 +102,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();
@@ -85,6 +119,12 @@ public:
       OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
       return;
     }
+    if (Ty.isPointer()) {
+      OS << "GILLT_p" << Ty.getAddressSpace();
+      if (Ty.getSizeInBits() > 0)
+        OS << "s" << Ty.getSizeInBits();
+      return;
+    }
     llvm_unreachable("Unhandled LLT");
   }
 
@@ -98,37 +138,42 @@ public:
          << Ty.getScalarSizeInBits() << ")";
       return;
     }
+    if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
+      OS << "LLT::pointer(" << Ty.getAddressSpace() << ", "
+         << Ty.getSizeInBits() << ")";
+      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.
+  /// particular logic behind the order but either A < B or B < A must be
+  /// true if A != B.
   bool operator<(const LLTCodeGen &Other) const {
+    if (Ty.isValid() != Other.Ty.isValid())
+      return Ty.isValid() < Other.Ty.isValid();
     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");
+
+    if (Ty.isVector() != Other.Ty.isVector())
+      return Ty.isVector() < Other.Ty.isVector();
+    if (Ty.isScalar() != Other.Ty.isScalar())
+      return Ty.isScalar() < Other.Ty.isScalar();
+    if (Ty.isPointer() != Other.Ty.isPointer())
+      return Ty.isPointer() < Other.Ty.isPointer();
+
+    if (Ty.isPointer() && Ty.getAddressSpace() != Other.Ty.getAddressSpace())
+      return Ty.getAddressSpace() < Other.Ty.getAddressSpace();
+
+    if (Ty.isVector() && Ty.getNumElements() != Other.Ty.getNumElements())
+      return Ty.getNumElements() < Other.Ty.getNumElements();
+
+    return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
   }
+
+  bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
 };
 
 class InstructionMatcher;
@@ -136,9 +181,11 @@ class InstructionMatcher;
 /// 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)
     return LLTCodeGen(
         LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits()));
+
   if (VT.isInteger() || VT.isFloatingPoint())
     return LLTCodeGen(LLT::scalar(VT.getSizeInBits()));
   return None;
@@ -150,10 +197,53 @@ static std::string explainPredicates(const TreePatternNode *N) {
   for (const auto &P : N->getPredicateFns()) {
     Explanation +=
         (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str();
+    Separator = ", ";
+
     if (P.isAlwaysTrue())
       Explanation += " always-true";
     if (P.isImmediatePattern())
       Explanation += " immediate";
+
+    if (P.isUnindexed())
+      Explanation += " unindexed";
+
+    if (P.isNonExtLoad())
+      Explanation += " non-extload";
+    if (P.isAnyExtLoad())
+      Explanation += " extload";
+    if (P.isSignExtLoad())
+      Explanation += " sextload";
+    if (P.isZeroExtLoad())
+      Explanation += " zextload";
+
+    if (P.isNonTruncStore())
+      Explanation += " non-truncstore";
+    if (P.isTruncStore())
+      Explanation += " truncstore";
+
+    if (Record *VT = P.getMemoryVT())
+      Explanation += (" MemVT=" + VT->getName()).str();
+    if (Record *VT = P.getScalarMemoryVT())
+      Explanation += (" ScalarVT(MemVT)=" + VT->getName()).str();
+
+    if (P.isAtomicOrderingMonotonic())
+      Explanation += " monotonic";
+    if (P.isAtomicOrderingAcquire())
+      Explanation += " acquire";
+    if (P.isAtomicOrderingRelease())
+      Explanation += " release";
+    if (P.isAtomicOrderingAcquireRelease())
+      Explanation += " acq_rel";
+    if (P.isAtomicOrderingSequentiallyConsistent())
+      Explanation += " seq_cst";
+    if (P.isAtomicOrderingAcquireOrStronger())
+      Explanation += " >=acquire";
+    if (P.isAtomicOrderingWeakerThanAcquire())
+      Explanation += " <acquire";
+    if (P.isAtomicOrderingReleaseOrStronger())
+      Explanation += " >=release";
+    if (P.isAtomicOrderingWeakerThanRelease())
+      Explanation += " <release";
   }
   return Explanation;
 }
@@ -165,7 +255,12 @@ std::string explainOperator(Record *Operator) {
   if (Operator->isSubClassOf("Intrinsic"))
     return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str();
 
-  return " (Operator not understood)";
+  if (Operator->isSubClassOf("ComplexPattern"))
+    return (" (Operator is an unmapped ComplexPattern, " + Operator->getName() +
+            ")")
+        .str();
+
+  return (" (Operator " + Operator->getName() + " not understood)").str();
 }
 
 /// Helper function to let the emitter report skip reason error messages.
@@ -176,17 +271,48 @@ static Error failedImport(const Twine &Reason) {
 static Error isTrivialOperatorNode(const TreePatternNode *N) {
   std::string Explanation = "";
   std::string Separator = "";
-  if (N->isLeaf()) {
-    if (isa<IntInit>(N->getLeafValue()))
-      return Error::success();
 
-    Explanation = "Is a leaf";
-    Separator = ", ";
-  }
+  bool HasUnsupportedPredicate = false;
+  for (const auto &Predicate : N->getPredicateFns()) {
+    if (Predicate.isAlwaysTrue())
+      continue;
 
-  if (N->hasAnyPredicate()) {
+    if (Predicate.isImmediatePattern())
+      continue;
+
+    if (Predicate.isNonExtLoad())
+      continue;
+
+    if (Predicate.isNonTruncStore())
+      continue;
+
+    if (Predicate.isLoad() || Predicate.isStore()) {
+      if (Predicate.isUnindexed())
+        continue;
+    }
+
+    if (Predicate.isAtomic() && Predicate.getMemoryVT())
+      continue;
+
+    if (Predicate.isAtomic() &&
+        (Predicate.isAtomicOrderingMonotonic() ||
+         Predicate.isAtomicOrderingAcquire() ||
+         Predicate.isAtomicOrderingRelease() ||
+         Predicate.isAtomicOrderingAcquireRelease() ||
+         Predicate.isAtomicOrderingSequentiallyConsistent() ||
+         Predicate.isAtomicOrderingAcquireOrStronger() ||
+         Predicate.isAtomicOrderingWeakerThanAcquire() ||
+         Predicate.isAtomicOrderingReleaseOrStronger() ||
+         Predicate.isAtomicOrderingWeakerThanRelease()))
+      continue;
+
+    HasUnsupportedPredicate = true;
     Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")";
     Separator = ", ";
+    Explanation += (Separator + "first-failing:" +
+                    Predicate.getOrigPatFragRecord()->getRecord()->getName())
+                       .str();
+    break;
   }
 
   if (N->getTransformFn()) {
@@ -194,7 +320,7 @@ static Error isTrivialOperatorNode(const TreePatternNode *N) {
     Separator = ", ";
   }
 
-  if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn())
+  if (!HasUnsupportedPredicate && !N->getTransformFn())
     return Error::success();
 
   return failedImport(Explanation);
@@ -217,13 +343,267 @@ 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;
+
+  /// A unique identifier for a MatchTable label.
+  static unsigned CurrentLabelID;
+
+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), 1,
+                            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();
+  }
+
+  unsigned allocateLabelID() const { return CurrentLabelID++; }
+
+  void defineLabel(unsigned LabelID) {
+    LabelMap.insert(std::make_pair(LabelID, CurrentSize));
+  }
+
+  unsigned getLabelIndex(unsigned LabelID) const {
+    const auto I = LabelMap.find(LabelID);
+    assert(I != LabelMap.end() && "Use of undeclared label");
+    return I->second;
+  }
+
+  void emitUse(raw_ostream &OS) const { OS << "MatchTable" << ID; }
+
+  void emitDeclaration(raw_ostream &OS) const {
+    unsigned Indentation = 4;
+    OS << "  constexpr 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";
+  }
+};
+
+unsigned MatchTable::CurrentLabelID = 0;
+
+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;
+}
+
 //===- Matchers -----------------------------------------------------------===//
 
 class OperandMatcher;
 class MatchAction;
+class PredicateMatcher;
+class RuleMatcher;
+
+class Matcher {
+public:
+  virtual ~Matcher() = default;
+  virtual void emit(MatchTable &Table) = 0;
+};
+
+class GroupMatcher : public Matcher {
+  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions;
+  SmallVector<Matcher *, 8> Rules;
+
+public:
+  void addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) {
+    Conditions.emplace_back(std::move(Predicate));
+  }
+  void addRule(Matcher &Rule) { Rules.push_back(&Rule); }
+  const std::unique_ptr<PredicateMatcher> &conditions_back() const {
+    return Conditions.back();
+  }
+  bool lastConditionMatches(const PredicateMatcher &Predicate) const;
+  bool conditions_empty() const { return Conditions.empty(); }
+  void clear() {
+    Conditions.clear();
+    Rules.clear();
+  }
+  void emit(MatchTable &Table) override;
+};
 
 /// Generates code to check that a match rule matches.
-class RuleMatcher {
+class RuleMatcher : public Matcher {
+public:
+  using ActionVec = std::vector<std::unique_ptr<MatchAction>>;
+  using action_iterator = ActionVec::iterator;
+
+protected:
   /// 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
@@ -232,40 +612,133 @@ class RuleMatcher {
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
-  std::vector<std::unique_ptr<MatchAction>> Actions;
+  ActionVec Actions;
+
+  using DefinedInsnVariablesMap =
+      std::map<const InstructionMatcher *, unsigned>;
 
   /// A map of instruction matchers to the local variables created by
   /// emitCaptureOpcodes().
-  std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;
+  DefinedInsnVariablesMap InsnVariableIDs;
+
+  using MutatableInsnSet = SmallPtrSet<const InstructionMatcher *, 4>;
+
+  // The set of instruction matchers that have not yet been claimed for mutation
+  // by a BuildMI.
+  MutatableInsnSet MutatableInsns;
+
+  /// A map of named operands defined by the matchers that may be referenced by
+  /// the renderers.
+  StringMap<OperandMatcher *> DefinedOperands;
 
   /// ID for the next instruction variable defined with defineInsnVar()
   unsigned NextInsnVarID;
 
+  /// ID for the next output instruction allocated with allocateOutputInsnID()
+  unsigned NextOutputInsnID;
+
+  /// ID for the next temporary register ID allocated with allocateTempRegID()
+  unsigned NextTempRegID;
+
   std::vector<Record *> RequiredFeatures;
 
+  ArrayRef<SMLoc> SrcLoc;
+
+  typedef std::tuple<Record *, unsigned, unsigned>
+      DefinedComplexPatternSubOperand;
+  typedef StringMap<DefinedComplexPatternSubOperand>
+      DefinedComplexPatternSubOperandMap;
+  /// A map of Symbolic Names to ComplexPattern sub-operands.
+  DefinedComplexPatternSubOperandMap ComplexSubOperands;
+
+  uint64_t RuleID;
+  static uint64_t NextRuleID;
+
 public:
-  RuleMatcher()
-      : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
+  RuleMatcher(ArrayRef<SMLoc> SrcLoc)
+      : Matchers(), Actions(), InsnVariableIDs(), MutatableInsns(),
+        DefinedOperands(), NextInsnVarID(0), NextOutputInsnID(0),
+        NextTempRegID(0), SrcLoc(SrcLoc), ComplexSubOperands(),
+        RuleID(NextRuleID++) {}
   RuleMatcher(RuleMatcher &&Other) = default;
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
-  InstructionMatcher &addInstructionMatcher();
+  uint64_t getRuleID() const { return RuleID; }
+
+  InstructionMatcher &addInstructionMatcher(StringRef SymbolicName);
   void addRequiredFeature(Record *Feature);
   const std::vector<Record *> &getRequiredFeatures() const;
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
+  template <class Kind, class... Args>
+  action_iterator insertAction(action_iterator InsertPt, Args &&... args);
 
   /// Define an instruction without emitting any code to do so.
   /// This is used for the root of the match.
   unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
+  void clearImplicitMap() {
+    NextInsnVarID = 0;
+    InsnVariableIDs.clear();
+  };
   /// 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;
+  DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
+    return InsnVariableIDs.begin();
+  }
+  DefinedInsnVariablesMap::const_iterator defined_insn_vars_end() const {
+    return InsnVariableIDs.end();
+  }
+  iterator_range<typename DefinedInsnVariablesMap::const_iterator>
+  defined_insn_vars() const {
+    return make_range(defined_insn_vars_begin(), defined_insn_vars_end());
+  }
+
+  MutatableInsnSet::const_iterator mutatable_insns_begin() const {
+    return MutatableInsns.begin();
+  }
+  MutatableInsnSet::const_iterator mutatable_insns_end() const {
+    return MutatableInsns.end();
+  }
+  iterator_range<typename MutatableInsnSet::const_iterator>
+  mutatable_insns() const {
+    return make_range(mutatable_insns_begin(), mutatable_insns_end());
+  }
+  void reserveInsnMatcherForMutation(const InstructionMatcher *InsnMatcher) {
+    bool R = MutatableInsns.erase(InsnMatcher);
+    assert(R && "Reserving a mutatable insn that isn't available");
+    (void)R;
+  }
+
+  action_iterator actions_begin() { return Actions.begin(); }
+  action_iterator actions_end() { return Actions.end(); }
+  iterator_range<action_iterator> actions() {
+    return make_range(actions_begin(), actions_end());
+  }
 
-  void emitCaptureOpcodes(raw_ostream &OS);
+  void defineOperand(StringRef SymbolicName, OperandMatcher &OM);
 
-  void emit(raw_ostream &OS);
+  void defineComplexSubOperand(StringRef SymbolicName, Record *ComplexPattern,
+                               unsigned RendererID, unsigned SubOperandID) {
+    assert(ComplexSubOperands.count(SymbolicName) == 0 && "Already defined");
+    ComplexSubOperands[SymbolicName] =
+        std::make_tuple(ComplexPattern, RendererID, SubOperandID);
+  }
+  Optional<DefinedComplexPatternSubOperand>
+  getComplexSubOperand(StringRef SymbolicName) const {
+    const auto &I = ComplexSubOperands.find(SymbolicName);
+    if (I == ComplexSubOperands.end())
+      return None;
+    return I->second;
+  }
+
+  const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
+  const OperandMatcher &getOperandMatcher(StringRef Name) const;
+
+  void emitCaptureOpcodes(MatchTable &Table);
+
+  void emit(MatchTable &Table) override;
 
   /// Compare the priority of this object and B.
   ///
@@ -276,22 +749,38 @@ public:
   /// matcher.
   unsigned countRendererFns() const;
 
+  std::unique_ptr<PredicateMatcher> forgetFirstCondition();
+
   // FIXME: Remove this as soon as possible
-  InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
+  InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
+
+  unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
+  unsigned allocateTempRegID() { return NextTempRegID++; }
+
+  bool insnmatchers_empty() const { return Matchers.empty(); }
+  void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
 };
 
+uint64_t RuleMatcher::NextRuleID = 0;
+
+using action_iterator = RuleMatcher::action_iterator;
+
 template <class PredicateTy> class PredicateListMatcher {
 private:
   typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
   PredicateVec Predicates;
 
+  /// Template instantiations should specialize this to return a string to use
+  /// for the comment emitted when there are no predicates.
+  std::string getNoPredicateComment() const;
+
 public:
   /// Construct a new operand predicate and add it to the matcher.
   template <class Kind, class... Args>
-  Kind &addPredicate(Args&&... args) {
+  Optional<Kind *> addPredicate(Args&&... args) {
     Predicates.emplace_back(
         llvm::make_unique<Kind>(std::forward<Args>(args)...));
-    return *static_cast<Kind *>(Predicates.back().get());
+    return static_cast<Kind *>(Predicates.back().get());
   }
 
   typename PredicateVec::const_iterator predicates_begin() const {
@@ -306,27 +795,34 @@ public:
   typename PredicateVec::size_type predicates_size() const {
     return Predicates.size();
   }
+  bool predicates_empty() const { return Predicates.empty(); }
+
+  std::unique_ptr<PredicateTy> predicates_pop_front() {
+    std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
+    Predicates.erase(Predicates.begin());
+    return Front;
+  }
 
   /// 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(getNoPredicateComment())
+            << MatchTable::LineBreak;
       return;
     }
 
-    for (const auto &Predicate : predicates())
-      Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...);
+    unsigned OpIdx = (*predicates_begin())->getOpIdx();
+    (void)OpIdx;
+    for (const auto &Predicate : predicates()) {
+      assert(Predicate->getOpIdx() == OpIdx &&
+             "Checks touch different operands?");
+      Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
+    }
   }
 };
 
-/// Generates code to check a predicate of an operand.
-///
-/// Typical predicates include:
-/// * Operand is a particular register.
-/// * Operand is assigned a particular register bank.
-/// * Operand is an MBB.
-class OperandPredicateMatcher {
+class PredicateMatcher {
 public:
   /// This enum is used for RTTI and also defines the priority that is given to
   /// the predicate when generating the matcher code. Kinds with higher priority
@@ -335,80 +831,172 @@ public:
   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
   /// but OPM_Int must have priority over OPM_RegBank since constant integers
   /// are represented by a virtual register defined by a G_CONSTANT instruction.
+  ///
+  /// Note: The relative priority between IPM_ and OPM_ does not matter, they
+  /// are currently not compared between each other.
   enum PredicateKind {
+    IPM_Opcode,
+    IPM_ImmPredicate,
+    IPM_AtomicOrderingMMO,
+    OPM_SameOperand,
     OPM_ComplexPattern,
-    OPM_Instruction,
     OPM_IntrinsicID,
+    OPM_Instruction,
     OPM_Int,
     OPM_LiteralInt,
     OPM_LLT,
+    OPM_PointerToAny,
     OPM_RegBank,
     OPM_MBB,
   };
 
 protected:
   PredicateKind Kind;
+  unsigned InsnVarID;
+  unsigned OpIdx;
 
 public:
-  OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
-  virtual ~OperandPredicateMatcher() {}
+  PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
+      : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
+
+  unsigned getOpIdx() const { return OpIdx; }
+  virtual ~PredicateMatcher() = default;
+  /// Emit MatchTable opcodes that check the predicate for the given operand.
+  virtual void emitPredicateOpcodes(MatchTable &Table,
+                                    RuleMatcher &Rule) const = 0;
 
   PredicateKind getKind() const { return Kind; }
 
-  /// Return the OperandMatcher for the specified operand or nullptr if there
-  /// isn't one by that name in this operand predicate matcher.
-  ///
-  /// InstructionOperandMatcher is the only subclass that can return non-null
-  /// for this.
-  virtual Optional<const OperandMatcher *>
-  getOptionalOperand(StringRef SymbolicName) const {
-    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
-    return None;
+  virtual bool isIdentical(const PredicateMatcher &B) const {
+    if (InsnVarID != 0 || OpIdx != (unsigned)~0) {
+      // We currently don't hoist the record of instruction properly.
+      // Therefore we can only work on the orig instruction (InsnVarID
+      // == 0).
+      DEBUG(dbgs() << "Non-zero instr ID not supported yet\n");
+      return false;
+    }
+    return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
+           OpIdx == B.OpIdx;
   }
+};
+
+/// Generates code to check a predicate of an operand.
+///
+/// Typical predicates include:
+/// * Operand is a particular register.
+/// * Operand is assigned a particular register bank.
+/// * Operand is an MBB.
+class OperandPredicateMatcher : public PredicateMatcher {
+public:
+  OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
+                          unsigned OpIdx)
+      : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
+  virtual ~OperandPredicateMatcher() {}
 
   /// Emit MatchTable opcodes to capture instructions into the MIs table.
   ///
   /// Only InstructionOperandMatcher needs to do anything for this method the
   /// rest just walk the tree.
-  virtual void emitCaptureOpcodes(raw_ostream &OS, 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,
-                                    unsigned InsnVarID,
-                                    unsigned OpIdx) const = 0;
+  virtual void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {}
 
   /// 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;
-  };
+  virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
 
   /// Report the maximum number of temporary operands needed by the predicate
   /// matcher.
   virtual unsigned countRendererFns() const { return 0; }
 };
 
+template <>
+std::string
+PredicateListMatcher<OperandPredicateMatcher>::getNoPredicateComment() const {
+  return "No operand predicates";
+}
+
+/// Generates code to check that a register operand is defined by the same exact
+/// one as another.
+class SameOperandMatcher : public OperandPredicateMatcher {
+  std::string MatchingName;
+
+public:
+  SameOperandMatcher(StringRef MatchingName, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
+        MatchingName(MatchingName) {}
+
+  static bool classof(const OperandPredicateMatcher *P) {
+    return P->getKind() == OPM_SameOperand;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override;
+};
+
 /// Generates code to check that an operand is a particular LLT.
 class LLTOperandMatcher : public OperandPredicateMatcher {
 protected:
   LLTCodeGen Ty;
 
 public:
-  LLTOperandMatcher(const LLTCodeGen &Ty)
-      : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {}
+  static std::set<LLTCodeGen> KnownTypes;
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  LLTOperandMatcher(const LLTCodeGen &Ty, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
+    KnownTypes.insert(Ty);
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_LLT;
   }
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Ty == cast<LLTOperandMatcher>(&B)->Ty;
+  }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
-       << ", /*Type*/";
-    Ty.emitCxxEnumValue(OS);
-    OS << ", \n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    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;
+  }
+};
+
+std::set<LLTCodeGen> LLTOperandMatcher::KnownTypes;
+
+/// Generates code to check that an operand is a pointer to any address space.
+///
+/// In SelectionDAG, the types did not describe pointers or address spaces. As a
+/// result, iN is used to describe a pointer of N bits to any address space and
+/// PatFrag predicates are typically used to constrain the address space. There's
+/// no reliable means to derive the missing type information from the pattern so
+/// imported rules must test the components of a pointer separately.
+///
+/// If SizeInBits is zero, then the pointer size will be obtained from the
+/// subtarget.
+class PointerToAnyOperandMatcher : public OperandPredicateMatcher {
+protected:
+  unsigned SizeInBits;
+
+public:
+  PointerToAnyOperandMatcher(unsigned SizeInBits, unsigned InsnVarID,
+                             unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
+        SizeInBits(SizeInBits) {}
+
+  static bool classof(const OperandPredicateMatcher *P) {
+    return P->getKind() == OPM_PointerToAny;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckPointerToAny")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("SizeInBits")
+          << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
   }
 };
 
@@ -421,21 +1009,27 @@ protected:
   unsigned getAllocatedTemporariesBaseID() const;
 
 public:
+  bool isIdentical(const PredicateMatcher &B) const override { return false; }
+
   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
-                               const Record &TheDef)
-      : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
-        TheDef(TheDef) {}
+                               const Record &TheDef, unsigned InsnVarID,
+                               unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
+        Operand(Operand), TheDef(TheDef) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_ComplexPattern;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) 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 {
@@ -449,32 +1043,45 @@ protected:
   const CodeGenRegisterClass &RC;
 
 public:
-  RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
-      : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
+  RegisterBankOperandMatcher(const CodeGenRegisterClass &RC, unsigned InsnVarID,
+                             unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_RegBank;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    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;
   }
 };
 
 /// Generates code to check that an operand is a basic block.
 class MBBOperandMatcher : public OperandPredicateMatcher {
 public:
-  MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
+  MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_MBB;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
+          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
+          << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
   }
 };
 
@@ -485,17 +1092,24 @@ protected:
   int64_t Value;
 
 public:
-  ConstantIntOperandMatcher(int64_t Value)
-      : OperandPredicateMatcher(OPM_Int), Value(Value) {}
+  ConstantIntOperandMatcher(int64_t Value, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Value == cast<ConstantIntOperandMatcher>(&B)->Value;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_Int;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", " << Value << ",\n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckConstantInt")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::IntValue(Value) << MatchTable::LineBreak;
   }
 };
 
@@ -506,17 +1120,25 @@ protected:
   int64_t Value;
 
 public:
-  LiteralIntOperandMatcher(int64_t Value)
-      : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}
+  LiteralIntOperandMatcher(int64_t Value, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
+        Value(Value) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Value == cast<LiteralIntOperandMatcher>(&B)->Value;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_LiteralInt;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", " << Value << ",\n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckLiteralInt")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::IntValue(Value) << MatchTable::LineBreak;
   }
 };
 
@@ -526,17 +1148,26 @@ protected:
   const CodeGenIntrinsic *II;
 
 public:
-  IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II)
-      : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {}
+  IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II, unsigned InsnVarID,
+                            unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           II == cast<IntrinsicIDOperandMatcher>(&B)->II;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_IntrinsicID;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    OS << "    GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
-       << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::NamedValue("Intrinsic::" + II->EnumName)
+          << MatchTable::LineBreak;
   }
 };
 
@@ -567,45 +1198,37 @@ public:
     SymbolicName = Name;
   }
   unsigned getOperandIndex() const { return OpIdx; }
+  unsigned getInsnVarID() const;
 
   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; }
 
+  Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
+                              bool OperandIsAPointer);
+
   /// Emit MatchTable opcodes to capture instructions into the MIs table.
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned InsnVarID) const {
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
     for (const auto &Predicate : predicates())
-      Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
+      Predicate->emitCaptureOpcodes(Table, Rule);
   }
 
   /// 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,
-                            unsigned InsnVarID) const {
-    OS << "    // MIs[" << InsnVarID << "] ";
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
+    std::string Comment;
+    raw_string_ostream CommentOS(Comment);
+    CommentOS << "MIs[" << getInsnVarID() << "] ";
     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);
   }
 
   /// Compare the priority of this object and B.
@@ -643,8 +1266,51 @@ public:
   unsigned getAllocatedTemporariesBaseID() const {
     return AllocatedTemporariesBaseID;
   }
+
+  bool isSameAsAnotherOperand() const {
+    for (const auto &Predicate : predicates())
+      if (isa<SameOperandMatcher>(Predicate))
+        return true;
+    return false;
+  }
 };
 
+// Specialize OperandMatcher::addPredicate() to refrain from adding redundant
+// predicates.
+template <>
+template <class Kind, class... Args>
+Optional<Kind *>
+PredicateListMatcher<OperandPredicateMatcher>::addPredicate(Args &&... args) {
+  auto *OpMatcher = static_cast<OperandMatcher *>(this);
+  if (static_cast<OperandMatcher *>(this)->isSameAsAnotherOperand())
+    return None;
+  Predicates.emplace_back(llvm::make_unique<Kind>(
+      std::forward<Args>(args)..., OpMatcher->getInsnVarID(),
+      OpMatcher->getOperandIndex()));
+  return static_cast<Kind *>(Predicates.back().get());
+}
+
+Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
+                                            bool OperandIsAPointer) {
+  if (!VTy.isMachineValueType())
+    return failedImport("unsupported typeset");
+
+  if (VTy.getMachineValueType() == MVT::iPTR && OperandIsAPointer) {
+    addPredicate<PointerToAnyOperandMatcher>(0);
+    return Error::success();
+  }
+
+  auto OpTyOrNone = MVTToLLT(VTy.getMachineValueType().SimpleTy);
+  if (!OpTyOrNone)
+    return failedImport("unsupported type");
+
+  if (OperandIsAPointer)
+    addPredicate<PointerToAnyOperandMatcher>(OpTyOrNone->get().getSizeInBits());
+  else
+    addPredicate<LLTOperandMatcher>(*OpTyOrNone);
+  return Error::success();
+}
+
 unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
   return Operand.getAllocatedTemporariesBaseID();
 }
@@ -654,28 +1320,12 @@ unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const {
 /// Typical predicates include:
 /// * The opcode of the instruction is a particular value.
 /// * The nsw/nuw flag is/isn't set.
-class InstructionPredicateMatcher {
-protected:
-  /// This enum is used for RTTI and also defines the priority that is given to
-  /// the predicate when generating the matcher code. Kinds with higher priority
-  /// must be tested first.
-  enum PredicateKind {
-    IPM_Opcode,
-  };
-
-  PredicateKind Kind;
-
+class InstructionPredicateMatcher : public PredicateMatcher {
 public:
-  InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
+  InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
+      : PredicateMatcher(Kind, InsnVarID) {}
   virtual ~InstructionPredicateMatcher() {}
 
-  PredicateKind getKind() const { return Kind; }
-
-  /// Emit MatchTable opcodes that test whether the instruction named in
-  /// InsnVarID matches the predicate.
-  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                                    unsigned InsnVarID) const = 0;
-
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
@@ -689,23 +1339,36 @@ public:
   virtual unsigned countRendererFns() const { return 0; }
 };
 
+template <>
+std::string
+PredicateListMatcher<InstructionPredicateMatcher>::getNoPredicateComment() const {
+  return "No instruction predicates";
+}
+
 /// Generates code to check the opcode of an instruction.
 class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
 protected:
   const CodeGenInstruction *I;
 
 public:
-  InstructionOpcodeMatcher(const CodeGenInstruction *I)
-      : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
+  InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
+      : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
 
-  static bool classof(const InstructionPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == IPM_Opcode;
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID) const override {
-    OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
-       << "::" << I->TheDef->getName() << ",\n";
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return InstructionPredicateMatcher::isIdentical(B) &&
+           I == cast<InstructionOpcodeMatcher>(&B)->I;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    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.
@@ -727,6 +1390,107 @@ public:
 
     return false;
   };
+
+  bool isConstantInstruction() const {
+    return I->TheDef->getName() == "G_CONSTANT";
+  }
+};
+
+/// Generates code to check that this instruction is a constant whose value
+/// meets an immediate predicate.
+///
+/// Immediates are slightly odd since they are typically used like an operand
+/// but are represented as an operator internally. We typically write simm8:$src
+/// in a tablegen pattern, but this is just syntactic sugar for
+/// (imm:i32)<<P:Predicate_simm8>>:$imm which more directly describes the nodes
+/// that will be matched and the predicate (which is attached to the imm
+/// operator) that will be tested. In SelectionDAG this describes a
+/// ConstantSDNode whose internal value will be tested using the simm8 predicate.
+///
+/// The corresponding GlobalISel representation is %1 = G_CONSTANT iN Value. In
+/// this representation, the immediate could be tested with an
+/// InstructionMatcher, InstructionOpcodeMatcher, OperandMatcher, and a
+/// OperandPredicateMatcher-subclass to check the Value meets the predicate but
+/// there are two implementation issues with producing that matcher
+/// configuration from the SelectionDAG pattern:
+/// * ImmLeaf is a PatFrag whose root is an InstructionMatcher. This means that
+///   were we to sink the immediate predicate to the operand we would have to
+///   have two partial implementations of PatFrag support, one for immediates
+///   and one for non-immediates.
+/// * At the point we handle the predicate, the OperandMatcher hasn't been
+///   created yet. If we were to sink the predicate to the OperandMatcher we
+///   would also have to complicate (or duplicate) the code that descends and
+///   creates matchers for the subtree.
+/// Overall, it's simpler to handle it in the place it was found.
+class InstructionImmPredicateMatcher : public InstructionPredicateMatcher {
+protected:
+  TreePredicateFn Predicate;
+
+public:
+  InstructionImmPredicateMatcher(unsigned InsnVarID,
+                                 const TreePredicateFn &Predicate)
+      : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
+        Predicate(Predicate) {}
+
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return InstructionPredicateMatcher::isIdentical(B) &&
+           Predicate.getOrigPatFragRecord() ==
+               cast<InstructionImmPredicateMatcher>(&B)
+                   ->Predicate.getOrigPatFragRecord();
+  }
+
+  static bool classof(const PredicateMatcher *P) {
+    return P->getKind() == IPM_ImmPredicate;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Predicate")
+          << MatchTable::NamedValue(getEnumNameForPredicate(Predicate))
+          << MatchTable::LineBreak;
+  }
+};
+
+/// Generates code to check that a memory instruction has a atomic ordering
+/// MachineMemoryOperand.
+class AtomicOrderingMMOPredicateMatcher : public InstructionPredicateMatcher {
+public:
+  enum AOComparator {
+    AO_Exactly,
+    AO_OrStronger,
+    AO_WeakerThan,
+  };
+
+protected:
+  StringRef Order;
+  AOComparator Comparator;
+
+public:
+  AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
+                                    AOComparator Comparator = AO_Exactly)
+      : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
+        Order(Order), Comparator(Comparator) {}
+
+  static bool classof(const InstructionPredicateMatcher *P) {
+    return P->getKind() == IPM_AtomicOrderingMMO;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    StringRef Opcode = "GIM_CheckAtomicOrdering";
+
+    if (Comparator == AO_OrStronger)
+      Opcode = "GIM_CheckAtomicOrderingOrStrongerThan";
+    if (Comparator == AO_WeakerThan)
+      Opcode = "GIM_CheckAtomicOrderingWeakerThan";
+
+    Table << MatchTable::Opcode(Opcode) << MatchTable::Comment("MI")
+          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Order")
+          << MatchTable::NamedValue(("(int64_t)AtomicOrdering::" + Order).str())
+          << MatchTable::LineBreak;
+  }
 };
 
 /// Generates code to check that a set of predicates and operands match for a
@@ -740,16 +1504,35 @@ class InstructionMatcher
 protected:
   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 
+  RuleMatcher &Rule;
+
   /// The operands to match. All rendered operands must be present even if the
   /// condition is always true.
   OperandVec Operands;
 
+  std::string SymbolicName;
+  unsigned InsnVarID;
+
 public:
+  InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
+      : Rule(Rule), SymbolicName(SymbolicName) {
+    // We create a new instruction matcher.
+    // Get a new ID for that instruction.
+    InsnVarID = Rule.implicitlyDefineInsnVar(*this);
+  }
+
+  RuleMatcher &getRuleMatcher() const { return Rule; }
+
+  unsigned getVarID() const { return InsnVarID; }
+
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
                              unsigned AllocatedTemporariesBaseID) {
     Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName,
                                              AllocatedTemporariesBaseID));
+    if (!SymbolicName.empty())
+      Rule.defineOperand(SymbolicName, *Operands.back());
+
     return *Operands.back();
   }
 
@@ -763,24 +1546,7 @@ public:
     llvm_unreachable("Failed to lookup operand");
   }
 
-  Optional<const OperandMatcher *>
-  getOptionalOperand(StringRef SymbolicName) const {
-    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
-    for (const auto &Operand : Operands) {
-      const auto &OM = Operand->getOptionalOperand(SymbolicName);
-      if (OM.hasValue())
-        return OM.getValue();
-    }
-    return None;
-  }
-
-  const OperandMatcher &getOperand(StringRef SymbolicName) const {
-    Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName);
-    if (OM.hasValue())
-      return *OM.getValue();
-    llvm_unreachable("Failed to lookup operand");
-  }
-
+  StringRef getSymbolicName() const { return SymbolicName; }
   unsigned getNumOperands() const { return Operands.size(); }
   OperandVec::iterator operands_begin() { return Operands.begin(); }
   OperandVec::iterator operands_end() { return Operands.end(); }
@@ -792,24 +1558,27 @@ public:
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
+  bool operands_empty() const { return Operands.empty(); }
+
+  void pop_front() { Operands.erase(Operands.begin()); }
 
   /// Emit MatchTable opcodes to check the shape of the match and capture
   /// instructions into the MIs table.
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned InsnID) {
-    OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
-       << getNumOperands() << ",\n";
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) {
+    Table << MatchTable::Opcode("GIM_CheckNumOperands")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Expected")
+          << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
     for (const auto &Operand : Operands)
-      Operand->emitCaptureOpcodes(OS, Rule, InsnID);
+      Operand->emitCaptureOpcodes(Table, Rule);
   }
 
   /// 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,
-                            unsigned InsnVarID) const {
-    emitPredicateListOpcodes(OS, Rule, InsnVarID);
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
+    emitPredicateListOpcodes(Table, Rule);
     for (const auto &Operand : Operands)
-      Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
+      Operand->emitPredicateOpcodes(Table, Rule);
   }
 
   /// Compare the priority of this object and B.
@@ -854,8 +1623,27 @@ public:
                  return A + Operand->countRendererFns();
                });
   }
+
+  bool isConstantInstruction() const {
+    for (const auto &P : predicates())
+      if (const InstructionOpcodeMatcher *Opcode =
+              dyn_cast<InstructionOpcodeMatcher>(P.get()))
+        return Opcode->isConstantInstruction();
+    return false;
+  }
 };
 
+template <>
+template <class Kind, class... Args>
+Optional<Kind *>
+PredicateListMatcher<InstructionPredicateMatcher>::addPredicate(
+    Args &&... args) {
+  InstructionMatcher *InstMatcher = static_cast<InstructionMatcher *>(this);
+  Predicates.emplace_back(llvm::make_unique<Kind>(InstMatcher->getVarID(),
+                                                  std::forward<Args>(args)...));
+  return static_cast<Kind *>(Predicates.back().get());
+}
+
 /// Generates code to check that the operand is a register defined by an
 /// instruction that matches the given instruction matcher.
 ///
@@ -870,33 +1658,29 @@ protected:
   std::unique_ptr<InstructionMatcher> InsnMatcher;
 
 public:
-  InstructionOperandMatcher()
-      : OperandPredicateMatcher(OPM_Instruction),
-        InsnMatcher(new InstructionMatcher()) {}
+  InstructionOperandMatcher(RuleMatcher &Rule, StringRef SymbolicName,
+                            unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
+        InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_Instruction;
   }
 
   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 
-  Optional<const OperandMatcher *>
-  getOptionalOperand(StringRef SymbolicName) const override {
-    assert(!SymbolicName.empty() && "Cannot lookup unnamed operand");
-    return InsnMatcher->getOptionalOperand(SymbolicName);
-  }
-
-  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned InsnID, unsigned OpIdx) const override {
-    unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
-    InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    unsigned InsnID =
+        Rule.defineInsnVar(Table, *InsnMatcher, InsnVarID, getOpIdx());
+    (void)InsnID;
+    assert(InsnMatcher->getVarID() == InsnID &&
+           "Mismatch between build and emit");
+    InsnMatcher->emitCaptureOpcodes(Table, Rule);
   }
 
-  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
-                            unsigned InsnVarID_,
-                            unsigned OpIdx_) const override {
-    unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
-    InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    InsnMatcher->emitPredicateOpcodes(Table, Rule);
   }
 };
 
@@ -905,9 +1689,13 @@ class OperandRenderer {
 public:
   enum RendererKind {
     OR_Copy,
+    OR_CopyOrAddZeroReg,
     OR_CopySubReg,
+    OR_CopyConstantAsImm,
+    OR_CopyFConstantAsFPImm,
     OR_Imm,
     OR_Register,
+    OR_TempRegister,
     OR_ComplexPattern
   };
 
@@ -920,7 +1708,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
@@ -928,18 +1717,15 @@ public:
 class CopyRenderer : public OperandRenderer {
 protected:
   unsigned NewInsnID;
-  /// The matcher for the instruction that this operand is copied from.
-  /// This provides the facility for looking up an a operand by it's name so
-  /// that it can be used as a source for the instruction being built.
-  const InstructionMatcher &Matched;
   /// The name of the operand.
   const StringRef SymbolicName;
 
 public:
-  CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
-               StringRef SymbolicName)
-      : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
-        SymbolicName(SymbolicName) {}
+  CopyRenderer(unsigned NewInsnID, StringRef SymbolicName)
+      : OperandRenderer(OR_Copy), NewInsnID(NewInsnID),
+        SymbolicName(SymbolicName) {
+    assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
+  }
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Copy;
@@ -947,12 +1733,117 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
-    const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const OperandMatcher &Operand = Rule.getOperandMatcher(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;
+  }
+};
+
+/// A CopyOrAddZeroRegRenderer emits code to copy a single operand from an
+/// existing instruction to the one being built. If the operand turns out to be
+/// a 'G_CONSTANT 0' then it replaces the operand with a zero register.
+class CopyOrAddZeroRegRenderer : public OperandRenderer {
+protected:
+  unsigned NewInsnID;
+  /// The name of the operand.
+  const StringRef SymbolicName;
+  const Record *ZeroRegisterDef;
+
+public:
+  CopyOrAddZeroRegRenderer(unsigned NewInsnID,
+                           StringRef SymbolicName, Record *ZeroRegisterDef)
+      : OperandRenderer(OR_CopyOrAddZeroReg), NewInsnID(NewInsnID),
+        SymbolicName(SymbolicName), ZeroRegisterDef(ZeroRegisterDef) {
+    assert(!SymbolicName.empty() && "Cannot copy from an unspecified source");
+  }
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_CopyOrAddZeroReg;
+  }
+
+  const StringRef getSymbolicName() const { return SymbolicName; }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const OperandMatcher &Operand = Rule.getOperandMatcher(SymbolicName);
+    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
+    Table << MatchTable::Opcode("GIR_CopyOrAddZeroReg")
+          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
+          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::NamedValue(
+                 (ZeroRegisterDef->getValue("Namespace")
+                      ? ZeroRegisterDef->getValueAsString("Namespace")
+                      : ""),
+                 ZeroRegisterDef->getName())
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
+  }
+};
+
+/// A CopyConstantAsImmRenderer emits code to render a G_CONSTANT instruction to
+/// an extended immediate operand.
+class CopyConstantAsImmRenderer : public OperandRenderer {
+protected:
+  unsigned NewInsnID;
+  /// The name of the operand.
+  const std::string SymbolicName;
+  bool Signed;
+
+public:
+  CopyConstantAsImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
+      : OperandRenderer(OR_CopyConstantAsImm), NewInsnID(NewInsnID),
+        SymbolicName(SymbolicName), Signed(true) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_CopyConstantAsImm;
+  }
+
+  const StringRef getSymbolicName() const { return SymbolicName; }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
+    Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
+                                       : "GIR_CopyConstantAsUImm")
+          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID)
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
+  }
+};
+
+/// A CopyFConstantAsFPImmRenderer emits code to render a G_FCONSTANT
+/// instruction to an extended immediate operand.
+class CopyFConstantAsFPImmRenderer : public OperandRenderer {
+protected:
+  unsigned NewInsnID;
+  /// The name of the operand.
+  const std::string SymbolicName;
+
+public:
+  CopyFConstantAsFPImmRenderer(unsigned NewInsnID, StringRef SymbolicName)
+      : OperandRenderer(OR_CopyFConstantAsFPImm), NewInsnID(NewInsnID),
+        SymbolicName(SymbolicName) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_CopyFConstantAsFPImm;
+  }
+
+  const StringRef getSymbolicName() const { return SymbolicName; }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
+    Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
+          << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OldInsnVarID)
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
 
@@ -962,19 +1853,15 @@ public:
 class CopySubRegRenderer : public OperandRenderer {
 protected:
   unsigned NewInsnID;
-  /// The matcher for the instruction that this operand is copied from.
-  /// This provides the facility for looking up an a operand by it's name so
-  /// that it can be used as a source for the instruction being built.
-  const InstructionMatcher &Matched;
   /// The name of the operand.
   const StringRef SymbolicName;
   /// The subregister to extract.
   const CodeGenSubRegIndex *SubReg;
 
 public:
-  CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
-                     StringRef SymbolicName, const CodeGenSubRegIndex *SubReg)
-      : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched),
+  CopySubRegRenderer(unsigned NewInsnID, StringRef SymbolicName,
+                     const CodeGenSubRegIndex *SubReg)
+      : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID),
         SymbolicName(SymbolicName), SubReg(SubReg) {}
 
   static bool classof(const OperandRenderer *R) {
@@ -983,13 +1870,17 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
-    const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const OperandMatcher &Operand = Rule.getOperandMatcher(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 +1900,46 @@ 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;
+  }
+};
+
+/// Adds a specific temporary virtual register to the instruction being built.
+/// This is used to chain instructions together when emitting multiple
+/// instructions.
+class TempRegRenderer : public OperandRenderer {
+protected:
+  unsigned InsnID;
+  unsigned TempRegID;
+  bool IsDef;
+
+public:
+  TempRegRenderer(unsigned InsnID, unsigned TempRegID, bool IsDef = false)
+      : OperandRenderer(OR_Register), InsnID(InsnID), TempRegID(TempRegID),
+        IsDef(IsDef) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_TempRegister;
+  }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIR_AddTempRegister")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
+          << MatchTable::Comment("TempRegFlags");
+    if (IsDef)
+      Table << MatchTable::NamedValue("RegState::Define");
+    else
+      Table << MatchTable::IntValue(0);
+    Table << MatchTable::LineBreak;
   }
 };
 
@@ -1032,9 +1957,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;
   }
 };
 
@@ -1049,6 +1975,9 @@ private:
   /// The renderer number. This must be unique within a rule since it's used to
   /// identify a temporary variable to hold the renderer function.
   unsigned RendererID;
+  /// When provided, this is the suboperand of the ComplexPattern operand to
+  /// render. Otherwise all the suboperands will be rendered.
+  Optional<unsigned> SubOperand;
 
   unsigned getNumOperands() const {
     return TheDef.getValueAsDag("Operands")->getNumArgs();
@@ -1056,17 +1985,26 @@ private:
 
 public:
   RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
-                              StringRef SymbolicName, unsigned RendererID)
+                              StringRef SymbolicName, unsigned RendererID,
+                              Optional<unsigned> SubOperand = None)
       : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
-        SymbolicName(SymbolicName), RendererID(RendererID) {}
+        SymbolicName(SymbolicName), RendererID(RendererID),
+        SubOperand(SubOperand) {}
 
   static bool classof(const OperandRenderer *R) {
     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(SubOperand.hasValue() ? "GIR_ComplexSubOperandRenderer"
+                                                      : "GIR_ComplexRenderer")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("RendererID")
+          << MatchTable::IntValue(RendererID);
+    if (SubOperand.hasValue())
+      Table << MatchTable::Comment("SubOperand")
+            << MatchTable::IntValue(SubOperand.getValue());
+    Table << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
 
@@ -1079,27 +2017,21 @@ class MatchAction {
 public:
   virtual ~MatchAction() {}
 
-  /// Emit the C++ statements 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;
+  /// Emit the MatchTable opcodes to implement the action.
+  virtual void emitActionOpcodes(MatchTable &Table,
+                                 RuleMatcher &Rule) const = 0;
 };
 
 /// Generates a comment describing the matched rule being acted upon.
 class DebugCommentAction : public MatchAction {
 private:
-  const PatternToMatch &P;
+  std::string S;
 
 public:
-  DebugCommentAction(const PatternToMatch &P) : P(P) {}
+  DebugCommentAction(StringRef S) : S(S) {}
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
-    OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern()
-       << "\n";
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Comment(S) << MatchTable::LineBreak;
   }
 };
 
@@ -1109,18 +2041,21 @@ class BuildMIAction : public MatchAction {
 private:
   unsigned InsnID;
   const CodeGenInstruction *I;
-  const InstructionMatcher &Matched;
+  const InstructionMatcher *Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 
   /// True if the instruction can be built solely by mutating the opcode.
-  bool canMutate() const {
-    if (OperandRenderers.size() != Matched.getNumOperands())
+  bool canMutate(RuleMatcher &Rule, const InstructionMatcher *Insn) const {
+    if (!Insn)
+      return false;
+
+    if (OperandRenderers.size() != Insn->getNumOperands())
       return false;
 
     for (const auto &Renderer : enumerate(OperandRenderers)) {
       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
-        const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName());
-        if (&Matched != &OM.getInstructionMatcher() ||
+        const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
+        if (Insn != &OM.getInstructionMatcher() ||
             OM.getOperandIndex() != Renderer.index())
           return false;
       } else
@@ -1131,38 +2066,61 @@ private:
   }
 
 public:
-  BuildMIAction(unsigned InsnID, const CodeGenInstruction *I,
-                const InstructionMatcher &Matched)
-      : InsnID(InsnID), I(I), Matched(Matched) {}
+  BuildMIAction(unsigned InsnID, const CodeGenInstruction *I)
+      : InsnID(InsnID), I(I), Matched(nullptr) {}
+
+  const CodeGenInstruction *getCGI() const { return I; }
+
+  void chooseInsnToMutate(RuleMatcher &Rule) {
+    for (const auto *MutateCandidate : Rule.mutatable_insns()) {
+      if (canMutate(Rule, MutateCandidate)) {
+        // Take the first one we're offered that we're able to mutate.
+        Rule.reserveInsnMatcherForMutation(MutateCandidate);
+        Matched = MutateCandidate;
+        return;
+      }
+    }
+  }
 
   template <class Kind, class... Args>
   Kind &addRenderer(Args&&... args) {
     OperandRenderers.emplace_back(
-        llvm::make_unique<Kind>(std::forward<Args>(args)...));
+        llvm::make_unique<Kind>(InsnID, std::forward<Args>(args)...));
     return *static_cast<Kind *>(OperandRenderers.back().get());
   }
 
-  void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          unsigned RecycleInsnID) const override {
-    if (canMutate()) {
-      OS << "    GIR_MutateOpcode, /*InsnID*/" << InsnID
-         << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
-         << I->Namespace << "::" << I->TheDef->getName() << ",\n";
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    if (Matched) {
+      assert(canMutate(Rule, Matched) &&
+             "Arranged to mutate an insn that isn't mutatable");
+
+      unsigned RecycleInsnID = Rule.getInsnVarID(*Matched);
+      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 +2129,41 @@ 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);
+
+    if (I->mayLoad || I->mayStore) {
+      Table << MatchTable::Opcode("GIR_MergeMemOperands")
+            << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+            << MatchTable::Comment("MergeInsnID's");
+      // Emit the ID's for all the instructions that are matched by this rule.
+      // TODO: Limit this to matched instructions that mayLoad/mayStore or have
+      //       some other means of having a memoperand. Also limit this to
+      //       emitted instructions that expect to have a memoperand too. For
+      //       example, (G_SEXT (G_LOAD x)) that results in separate load and
+      //       sign-extend instructions shouldn't put the memoperand on the
+      //       sign-extend since it has no effect there.
+      std::vector<unsigned> MergeInsnIDs;
+      for (const auto &IDMatcherPair : Rule.defined_insn_vars())
+        MergeInsnIDs.push_back(IDMatcherPair.second);
+      std::sort(MergeInsnIDs.begin(), MergeInsnIDs.end());
+      for (const auto &MergeInsnID : MergeInsnIDs)
+        Table << MatchTable::IntValue(MergeInsnID);
+      Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
+            << MatchTable::LineBreak;
+    }
 
-    OS << "    GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
-       << "    GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
+    // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
+    //        better for combines. Particularly when there are multiple match
+    //        roots.
+    if (InsnID == 0)
+      Table << MatchTable::Opcode("GIR_EraseFromParent")
+            << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+            << MatchTable::LineBreak;
   }
 };
 
@@ -1189,9 +2175,10 @@ 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) const override {
+    Table << MatchTable::Opcode("GIR_ConstrainSelectedInstOperands")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::LineBreak;
   }
 };
 
@@ -1207,15 +2194,38 @@ 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) 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;
   }
 };
 
-InstructionMatcher &RuleMatcher::addInstructionMatcher() {
-  Matchers.emplace_back(new InstructionMatcher());
+/// Generates code to create a temporary register which can be used to chain
+/// instructions together.
+class MakeTempRegisterAction : public MatchAction {
+private:
+  LLTCodeGen Ty;
+  unsigned TempRegID;
+
+public:
+  MakeTempRegisterAction(const LLTCodeGen &Ty, unsigned TempRegID)
+      : Ty(Ty), TempRegID(TempRegID) {}
+
+  void emitActionOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIR_MakeTempReg")
+          << MatchTable::Comment("TempRegID") << MatchTable::IntValue(TempRegID)
+          << MatchTable::Comment("TypeID")
+          << MatchTable::NamedValue(Ty.getCxxEnumValue())
+          << MatchTable::LineBreak;
+  }
+};
+
+InstructionMatcher &RuleMatcher::addInstructionMatcher(StringRef SymbolicName) {
+  Matchers.emplace_back(new InstructionMatcher(*this, SymbolicName));
+  MutatableInsns.insert(Matchers.back().get());
   return *Matchers.back();
 }
 
@@ -1227,12 +2237,33 @@ const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
   return RequiredFeatures;
 }
 
+// Emplaces an action of the specified Kind at the end of the action list.
+//
+// Returns a reference to the newly created action.
+//
+// Like std::vector::emplace_back(), may invalidate all iterators if the new
+// size exceeds the capacity. Otherwise, only invalidates the past-the-end
+// iterator.
 template <class Kind, class... Args>
 Kind &RuleMatcher::addAction(Args &&... args) {
   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
   return *static_cast<Kind *>(Actions.back().get());
 }
 
+// Emplaces an action of the specified Kind before the given insertion point.
+//
+// Returns an iterator pointing at the newly created instruction.
+//
+// Like std::vector::insert(), may invalidate all iterators if the new size
+// exceeds the capacity. Otherwise, only invalidates the iterators from the
+// insertion point onwards.
+template <class Kind, class... Args>
+action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
+                                          Args &&... args) {
+  return Actions.emplace(InsertPt,
+                         llvm::make_unique<Kind>(std::forward<Args>(args)...));
+}
+
 unsigned
 RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
   unsigned NewInsnVarID = NextInsnVarID++;
@@ -1240,13 +2271,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;
 }
 
@@ -1257,15 +2291,48 @@ unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const
   llvm_unreachable("Matched Insn was not captured in a local variable");
 }
 
+void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
+  if (DefinedOperands.find(SymbolicName) == DefinedOperands.end()) {
+    DefinedOperands[SymbolicName] = &OM;
+    return;
+  }
+
+  // If the operand is already defined, then we must ensure both references in
+  // the matcher have the exact same node.
+  OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
+}
+
+const InstructionMatcher &
+RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
+  for (const auto &I : InsnVariableIDs)
+    if (I.first->getSymbolicName() == SymbolicName)
+      return *I.first;
+  llvm_unreachable(
+      ("Failed to lookup instruction " + SymbolicName).str().c_str());
+}
+
+const OperandMatcher &
+RuleMatcher::getOperandMatcher(StringRef Name) const {
+  const auto &I = DefinedOperands.find(Name);
+
+  if (I == DefinedOperands.end())
+    PrintFatalError(SrcLoc, "Operand " + Name + " was not declared in matcher");
+
+  return *I->second;
+}
+
 /// 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);
+  (void)InsnVarID;
+  assert(Matchers.front()->getVarID() == InsnVarID &&
+         "IDs differ between build and emit");
+  Matchers.front()->emitCaptureOpcodes(Table, *this);
 }
 
-void RuleMatcher::emit(raw_ostream &OS) {
+void RuleMatcher::emit(MatchTable &Table) {
   if (Matchers.empty())
     llvm_unreachable("Unexpected empty matcher!");
 
@@ -1280,16 +2347,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";
+  unsigned LabelID = Table.allocateLabelID();
+  Table << MatchTable::Opcode("GIM_Try", +1)
+        << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(LabelID)
+        << 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,
-                                         getInsnVarID(*Matchers.front()));
+  Matchers.front()->emitPredicateOpcodes(Table, *this);
 
   // We must also check if it's safe to fold the matched instructions.
   if (InsnVariableIDs.size() >= 2) {
@@ -1307,7 +2378,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,16 +2420,14 @@ void RuleMatcher::emit(raw_ostream &OS) {
   }
 
   for (const auto &MA : Actions)
-    MA->emitCxxActionStmts(OS, *this, 0);
-  OS << "    GIR_Done,\n"
-     << "  };\n"
-     << "  State.MIs.resize(1);\n"
-     << "  DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
-     << "\\n\");\n"
-     << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable"
-     << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
-     << "    return true;\n"
-     << "  }\n\n";
+    MA->emitActionOpcodes(Table, *this);
+
+  if (GenerateCoverage)
+    Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
+          << MatchTable::LineBreak;
+
+  Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+        << MatchTable::Label(LabelID);
 }
 
 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
@@ -1384,6 +2455,54 @@ unsigned RuleMatcher::countRendererFns() const {
       });
 }
 
+bool OperandPredicateMatcher::isHigherPriorityThan(
+    const OperandPredicateMatcher &B) const {
+  // Generally speaking, an instruction is more important than an Int or a
+  // LiteralInt because it can cover more nodes but theres an exception to
+  // this. G_CONSTANT's are less important than either of those two because they
+  // are more permissive.
+
+  const InstructionOperandMatcher *AOM =
+      dyn_cast<InstructionOperandMatcher>(this);
+  const InstructionOperandMatcher *BOM =
+      dyn_cast<InstructionOperandMatcher>(&B);
+  bool AIsConstantInsn = AOM && AOM->getInsnMatcher().isConstantInstruction();
+  bool BIsConstantInsn = BOM && BOM->getInsnMatcher().isConstantInstruction();
+
+  if (AOM && BOM) {
+    // The relative priorities between a G_CONSTANT and any other instruction
+    // don't actually matter but this code is needed to ensure a strict weak
+    // ordering. This is particularly important on Windows where the rules will
+    // be incorrectly sorted without it.
+    if (AIsConstantInsn != BIsConstantInsn)
+      return AIsConstantInsn < BIsConstantInsn;
+    return false;
+  }
+
+  if (AOM && AIsConstantInsn && (B.Kind == OPM_Int || B.Kind == OPM_LiteralInt))
+    return false;
+  if (BOM && BIsConstantInsn && (Kind == OPM_Int || Kind == OPM_LiteralInt))
+    return true;
+
+  return Kind < B.Kind;
+}
+
+void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
+                                              RuleMatcher &Rule) const {
+  const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
+  unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
+  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getVarID());
+
+  Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
+        << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+        << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
+        << MatchTable::Comment("OtherMI")
+        << MatchTable::IntValue(OtherInsnVarID)
+        << MatchTable::Comment("OtherOpIdx")
+        << MatchTable::IntValue(OtherOM.getOperandIndex())
+        << MatchTable::LineBreak;
+}
+
 //===- GlobalISelEmitter class --------------------------------------------===//
 
 class GlobalISelEmitter {
@@ -1397,9 +2516,11 @@ private:
   const CodeGenTarget &Target;
   CodeGenRegBank CGRegs;
 
-  /// Keep track of the equivalence between SDNodes and Instruction.
+  /// Keep track of the equivalence between SDNodes and Instruction by mapping
+  /// SDNodes to the GINodeEquiv mapping. We need to map to the GINodeEquiv to
+  /// check for attributes on the relation such as CheckMMOIsNonAtomic.
   /// This is defined using 'GINodeEquiv' in the target description.
-  DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
+  DenseMap<Record *, Record *> NodeEquivs;
 
   /// Keep track of the equivalence between ComplexPattern's and
   /// GIComplexOperandMatcher. Map entries are specified by subclassing
@@ -1409,41 +2530,99 @@ private:
   // Map of predicates to their subtarget features.
   SubtargetFeatureInfoMap SubtargetFeatures;
 
+  // Rule coverage information.
+  Optional<CodeGenCoverage> RuleCoverage;
+
   void gatherNodeEquivs();
-  const CodeGenInstruction *findNodeEquiv(Record *N) const;
-
-  Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
-  Expected<InstructionMatcher &>
-  createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
-                               const TreePatternNode *Src,
-                               unsigned &TempOpIdx) const;
-  Error importChildMatcher(InstructionMatcher &InsnMatcher,
-                           const TreePatternNode *SrcChild, unsigned OpIdx,
+  Record *findNodeEquiv(Record *N) const;
+
+  Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates);
+  Expected<InstructionMatcher &> createAndImportSelDAGMatcher(
+      RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
+      const TreePatternNode *Src, unsigned &TempOpIdx) const;
+  Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R,
+                                           unsigned &TempOpIdx) const;
+  Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
+                           const TreePatternNode *SrcChild,
+                           bool OperandIsAPointer, unsigned OpIdx,
                            unsigned &TempOpIdx) const;
+
   Expected<BuildMIAction &>
-  createAndImportInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst,
-                                     const InstructionMatcher &InsnMatcher);
-  Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder,
-                                  TreePatternNode *DstChild,
-                                  const InstructionMatcher &InsnMatcher) const;
+  createAndImportInstructionRenderer(RuleMatcher &M,
+                                     const TreePatternNode *Dst);
+  Expected<action_iterator> createAndImportSubInstructionRenderer(
+      action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
+      unsigned TempReg);
+  Expected<action_iterator>
+  createInstructionRenderer(action_iterator InsertPt, RuleMatcher &M,
+                            const TreePatternNode *Dst);
+  void importExplicitDefRenderers(BuildMIAction &DstMIBuilder);
+  Expected<action_iterator>
+  importExplicitUseRenderers(action_iterator InsertPt, RuleMatcher &M,
+                             BuildMIAction &DstMIBuilder,
+                             const llvm::TreePatternNode *Dst);
+  Expected<action_iterator>
+  importExplicitUseRenderer(action_iterator InsertPt, RuleMatcher &Rule,
+                            BuildMIAction &DstMIBuilder,
+                            TreePatternNode *DstChild);
   Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder,
                                       DagInit *DefaultOps) const;
   Error
   importImplicitDefRenderers(BuildMIAction &DstMIBuilder,
                              const std::vector<Record *> &ImplicitDefs) const;
 
+  void emitImmPredicates(raw_ostream &OS, StringRef TypeIdentifier,
+                         StringRef Type,
+                         std::function<bool(const Record *R)> Filter);
+
   /// Analyze pattern \p P, returning a matcher for it if possible.
   /// Otherwise, return an Error explaining why we don't support it.
   Expected<RuleMatcher> runOnPattern(const PatternToMatch &P);
 
   void declareSubtargetFeature(Record *Predicate);
+
+  TreePatternNode *fixupPatternNode(TreePatternNode *N);
+  void fixupPatternTrees(TreePattern *P);
+
+  /// Takes a sequence of \p Rules and group them based on the predicates
+  /// they share. \p StorageGroupMatcher is used as a memory container
+  /// for the the group that are created as part of this process.
+  /// The optimization process does not change the relative order of
+  /// the rules. In particular, we don't try to share predicates if
+  /// that means reordering the rules (e.g., we won't group R1 and R3
+  /// in the following example as it would imply reordering R2 and R3
+  /// => R1 p1, R2 p2, R3 p1).
+  ///
+  /// What this optimization does looks like:
+  /// Output without optimization:
+  /// \verbatim
+  /// # R1
+  ///  # predicate A
+  ///  # predicate B
+  ///  ...
+  /// # R2
+  ///  # predicate A // <-- effectively this is going to be checked twice.
+  ///                //     Once in R1 and once in R2.
+  ///  # predicate C
+  /// \endverbatim
+  /// Output with optimization:
+  /// \verbatim
+  /// # Group1_2
+  ///  # predicate A // <-- Check is now shared.
+  ///  # R1
+  ///   # predicate B
+  ///  # R2
+  ///   # predicate C
+  /// \endverbatim
+  std::vector<Matcher *> optimizeRules(
+      std::vector<RuleMatcher> &Rules,
+      std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
 };
 
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
-    NodeEquivs[Equiv->getValueAsDef("Node")] =
-        &Target.getInstruction(Equiv->getValueAsDef("I"));
+    NodeEquivs[Equiv->getValueAsDef("Node")] = Equiv;
 
   assert(ComplexPatternEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) {
@@ -1454,31 +2633,33 @@ void GlobalISelEmitter::gatherNodeEquivs() {
  }
 }
 
-const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const {
+Record *GlobalISelEmitter::findNodeEquiv(Record *N) const {
   return NodeEquivs.lookup(N);
 }
 
 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
-    : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), CGRegs(RK) {}
+    : RK(RK), CGP(RK, [&](TreePattern *P) { fixupPatternTrees(P); }),
+      Target(CGP.getTargetInfo()), CGRegs(RK, Target.getHwModes()) {}
 
 //===- Emitter ------------------------------------------------------------===//
 
 Error
 GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
-                                        ArrayRef<Init *> Predicates) {
-  for (const Init *Predicate : Predicates) {
-    const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate);
-    declareSubtargetFeature(PredicateDef->getDef());
-    M.addRequiredFeature(PredicateDef->getDef());
+                                        ArrayRef<Predicate> Predicates) {
+  for (const Predicate &P : Predicates) {
+    if (!P.Def)
+      continue;
+    declareSubtargetFeature(P.Def);
+    M.addRequiredFeature(P.Def);
   }
 
   return Error::success();
 }
 
-Expected<InstructionMatcher &>
-GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
-                                                const TreePatternNode *Src,
-                                                unsigned &TempOpIdx) const {
+Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
+    RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
+    const TreePatternNode *Src, unsigned &TempOpIdx) const {
+  Record *SrcGIEquivOrNull = nullptr;
   const CodeGenInstruction *SrcGIOrNull = nullptr;
 
   // Start with the defined operands (i.e., the results of the root operator).
@@ -1494,34 +2675,122 @@ GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
       return failedImport(
           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
   } else {
-    SrcGIOrNull = findNodeEquiv(Src->getOperator());
-    if (!SrcGIOrNull)
+    SrcGIEquivOrNull = findNodeEquiv(Src->getOperator());
+    if (!SrcGIEquivOrNull)
       return failedImport("Pattern operator lacks an equivalent Instruction" +
                           explainOperator(Src->getOperator()));
-    auto &SrcGI = *SrcGIOrNull;
+    SrcGIOrNull = &Target.getInstruction(SrcGIEquivOrNull->getValueAsDef("I"));
 
     // The operators look good: match the opcode
-    InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI);
+    InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull);
   }
 
   unsigned OpIdx = 0;
-  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
-    auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
-
-    if (!OpTyOrNone)
-      return failedImport(
-          "Result of Src pattern operator has an unsupported type");
-
+  for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
     // Results don't have a name unless they are the root node. The caller will
     // set the name if appropriate.
     OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
-    OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
+    if (auto Error = OM.addTypeCheckPredicate(VTy, false /* OperandIsAPointer */))
+      return failedImport(toString(std::move(Error)) +
+                          " for result of Src pattern operator");
+  }
+
+  for (const auto &Predicate : Src->getPredicateFns()) {
+    if (Predicate.isAlwaysTrue())
+      continue;
+
+    if (Predicate.isImmediatePattern()) {
+      InsnMatcher.addPredicate<InstructionImmPredicateMatcher>(Predicate);
+      continue;
+    }
+
+    // No check required. G_LOAD by itself is a non-extending load.
+    if (Predicate.isNonExtLoad())
+      continue;
+
+    // No check required. G_STORE by itself is a non-extending store.
+    if (Predicate.isNonTruncStore())
+      continue;
+
+    if (Predicate.isLoad() || Predicate.isStore() || Predicate.isAtomic()) {
+      if (Predicate.getMemoryVT() != nullptr) {
+        Optional<LLTCodeGen> MemTyOrNone =
+            MVTToLLT(getValueType(Predicate.getMemoryVT()));
+
+        if (!MemTyOrNone)
+          return failedImport("MemVT could not be converted to LLT");
+
+        OperandMatcher &OM = InsnMatcher.getOperand(0);
+        OM.addPredicate<LLTOperandMatcher>(MemTyOrNone.getValue());
+        continue;
+      }
+    }
+
+    if (Predicate.isLoad() || Predicate.isStore()) {
+      // No check required. A G_LOAD/G_STORE is an unindexed load.
+      if (Predicate.isUnindexed())
+        continue;
+    }
+
+    if (Predicate.isAtomic()) {
+      if (Predicate.isAtomicOrderingMonotonic()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "Monotonic");
+        continue;
+      }
+      if (Predicate.isAtomicOrderingAcquire()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Acquire");
+        continue;
+      }
+      if (Predicate.isAtomicOrderingRelease()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("Release");
+        continue;
+      }
+      if (Predicate.isAtomicOrderingAcquireRelease()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "AcquireRelease");
+        continue;
+      }
+      if (Predicate.isAtomicOrderingSequentiallyConsistent()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "SequentiallyConsistent");
+        continue;
+      }
+
+      if (Predicate.isAtomicOrderingAcquireOrStronger()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "Acquire", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
+        continue;
+      }
+      if (Predicate.isAtomicOrderingWeakerThanAcquire()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "Acquire", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
+        continue;
+      }
+
+      if (Predicate.isAtomicOrderingReleaseOrStronger()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "Release", AtomicOrderingMMOPredicateMatcher::AO_OrStronger);
+        continue;
+      }
+      if (Predicate.isAtomicOrderingWeakerThanRelease()) {
+        InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>(
+            "Release", AtomicOrderingMMOPredicateMatcher::AO_WeakerThan);
+        continue;
+      }
+    }
+
+    return failedImport("Src pattern child has predicate (" +
+                        explainPredicates(Src) + ")");
   }
+  if (SrcGIEquivOrNull && SrcGIEquivOrNull->getValueAsBit("CheckMMOIsNonAtomic"))
+    InsnMatcher.addPredicate<AtomicOrderingMMOPredicateMatcher>("NotAtomic");
 
   if (Src->isLeaf()) {
     Init *SrcInit = Src->getLeafValue();
     if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) {
-      OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
+      OperandMatcher &OM =
+          InsnMatcher.addOperand(OpIdx++, Src->getName(), TempOpIdx);
       OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue());
     } else
       return failedImport(
@@ -1529,13 +2798,29 @@ GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
   } else {
     assert(SrcGIOrNull &&
            "Expected to have already found an equivalent Instruction");
+    if (SrcGIOrNull->TheDef->getName() == "G_CONSTANT" ||
+        SrcGIOrNull->TheDef->getName() == "G_FCONSTANT") {
+      // imm/fpimm still have operands but we don't need to do anything with it
+      // here since we don't support ImmLeaf predicates yet. However, we still
+      // need to note the hidden operand to get GIM_CheckNumOperands correct.
+      InsnMatcher.addOperand(OpIdx++, "", TempOpIdx);
+      return InsnMatcher;
+    }
+
     // Match the used operands (i.e. the children of the operator).
     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
       TreePatternNode *SrcChild = Src->getChild(i);
 
-      // For G_INTRINSIC, the operand immediately following the defs is an
-      // intrinsic ID.
-      if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
+      // SelectionDAG allows pointers to be represented with iN since it doesn't
+      // distinguish between pointers and integers but they are different types in GlobalISel.
+      // Coerce integers to pointers to address space 0 if the context indicates a pointer.
+      bool OperandIsAPointer = SrcGIOrNull->isOperandAPointer(i);
+
+      // For G_INTRINSIC/G_INTRINSIC_W_SIDE_EFFECTS, the operand immediately
+      // following the defs is an intrinsic ID.
+      if ((SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" ||
+           SrcGIOrNull->TheDef->getName() == "G_INTRINSIC_W_SIDE_EFFECTS") &&
+          i == 0) {
         if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
           OperandMatcher &OM =
               InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
@@ -1547,7 +2832,8 @@ GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
       }
 
       if (auto Error =
-              importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx))
+              importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
+                                 OpIdx++, TempOpIdx))
         return std::move(Error);
     }
   }
@@ -1555,18 +2841,30 @@ GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
   return InsnMatcher;
 }
 
-Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
+Error GlobalISelEmitter::importComplexPatternOperandMatcher(
+    OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const {
+  const auto &ComplexPattern = ComplexPatternEquivs.find(R);
+  if (ComplexPattern == ComplexPatternEquivs.end())
+    return failedImport("SelectionDAG ComplexPattern (" + R->getName() +
+                        ") not mapped to GlobalISel");
+
+  OM.addPredicate<ComplexPatternOperandMatcher>(OM, *ComplexPattern->second);
+  TempOpIdx++;
+  return Error::success();
+}
+
+Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
+                                            InstructionMatcher &InsnMatcher,
                                             const TreePatternNode *SrcChild,
+                                            bool OperandIsAPointer,
                                             unsigned OpIdx,
                                             unsigned &TempOpIdx) const {
   OperandMatcher &OM =
       InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx);
+  if (OM.isSameAsAnotherOperand())
+    return Error::success();
 
-  if (SrcChild->hasAnyPredicate())
-    return failedImport("Src pattern child has predicate (" +
-                        explainPredicates(SrcChild) + ")");
-
-  ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
+  ArrayRef<TypeSetByHwMode> ChildTypes = SrcChild->getExtTypes();
   if (ChildTypes.size() != 1)
     return failedImport("Src pattern child has multiple results");
 
@@ -1581,24 +2879,55 @@ Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
     }
   }
 
-  auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
-  if (!OpTyOrNone)
-    return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
-  OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
+  if (auto Error =
+          OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
+    return failedImport(toString(std::move(Error)) + " for Src operand (" +
+                        to_string(*SrcChild) + ")");
 
   // Check for nested instructions.
   if (!SrcChild->isLeaf()) {
+    if (SrcChild->getOperator()->isSubClassOf("ComplexPattern")) {
+      // When a ComplexPattern is used as an operator, it should do the same
+      // thing as when used as a leaf. However, the children of the operator
+      // name the sub-operands that make up the complex operand and we must
+      // prepare to reference them in the renderer too.
+      unsigned RendererID = TempOpIdx;
+      if (auto Error = importComplexPatternOperandMatcher(
+              OM, SrcChild->getOperator(), TempOpIdx))
+        return Error;
+
+      for (unsigned i = 0, e = SrcChild->getNumChildren(); i != e; ++i) {
+        auto *SubOperand = SrcChild->getChild(i);
+        if (!SubOperand->getName().empty())
+          Rule.defineComplexSubOperand(SubOperand->getName(),
+                                       SrcChild->getOperator(), RendererID, i);
+      }
+
+      return Error::success();
+    }
+
+    auto MaybeInsnOperand = OM.addPredicate<InstructionOperandMatcher>(
+        InsnMatcher.getRuleMatcher(), SrcChild->getName());
+    if (!MaybeInsnOperand.hasValue()) {
+      // This isn't strictly true. If the user were to provide exactly the same
+      // matchers as the original operand then we could allow it. However, it's
+      // simpler to not permit the redundant specification.
+      return failedImport("Nested instruction cannot be the same as another operand");
+    }
+
     // Map the node to a gMIR instruction.
-    InstructionOperandMatcher &InsnOperand =
-        OM.addPredicate<InstructionOperandMatcher>();
+    InstructionOperandMatcher &InsnOperand = **MaybeInsnOperand;
     auto InsnMatcherOrError = createAndImportSelDAGMatcher(
-        InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
+        Rule, InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
     if (auto Error = InsnMatcherOrError.takeError())
       return Error;
 
     return Error::success();
   }
 
+  if (SrcChild->hasAnyPredicate())
+    return failedImport("Src pattern child has unsupported predicate");
+
   // Check for constant immediates.
   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
     OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
@@ -1617,19 +2946,17 @@ Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
       return Error::success();
     }
 
-    // Check for ComplexPattern's.
-    if (ChildRec->isSubClassOf("ComplexPattern")) {
-      const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec);
-      if (ComplexPattern == ComplexPatternEquivs.end())
-        return failedImport("SelectionDAG ComplexPattern (" +
-                            ChildRec->getName() + ") not mapped to GlobalISel");
-
-      OM.addPredicate<ComplexPatternOperandMatcher>(OM,
-                                                    *ComplexPattern->second);
-      TempOpIdx++;
+    // Check for ValueType.
+    if (ChildRec->isSubClassOf("ValueType")) {
+      // We already added a type check as standard practice so this doesn't need
+      // to do anything.
       return Error::success();
     }
 
+    // Check for ComplexPattern's.
+    if (ChildRec->isSubClassOf("ComplexPattern"))
+      return importComplexPatternOperandMatcher(OM, ChildRec, TempOpIdx);
+
     if (ChildRec->isSubClassOf("ImmLeaf")) {
       return failedImport(
           "Src pattern child def is an unsupported tablegen class (ImmLeaf)");
@@ -1642,49 +2969,112 @@ Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
   return failedImport("Src pattern child is an unsupported kind");
 }
 
-Error GlobalISelEmitter::importExplicitUseRenderer(
-    BuildMIAction &DstMIBuilder, TreePatternNode *DstChild,
-    const InstructionMatcher &InsnMatcher) const {
-  // The only non-leaf child we accept is 'bb': it's an operator because
-  // BasicBlockSDNode isn't inline, but in MI it's just another operand.
+Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
+    action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder,
+    TreePatternNode *DstChild) {
+  if (DstChild->getTransformFn() != nullptr) {
+    return failedImport("Dst pattern child has transform fn " +
+                        DstChild->getTransformFn()->getName());
+  }
+
+  const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName());
+  if (SubOperand.hasValue()) {
+    DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
+        *std::get<0>(*SubOperand), DstChild->getName(),
+        std::get<1>(*SubOperand), std::get<2>(*SubOperand));
+    return InsertPt;
+  }
+
   if (!DstChild->isLeaf()) {
+    // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't
+    // inline, but in MI it's just another operand.
     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-        DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
-                                               DstChild->getName());
-        return Error::success();
+        DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
+        return InsertPt;
       }
     }
-    return failedImport("Dst pattern child isn't a leaf node or an MBB");
+
+    // Similarly, imm is an operator in TreePatternNode's view but must be
+    // rendered as operands.
+    // FIXME: The target should be able to choose sign-extended when appropriate
+    //        (e.g. on Mips).
+    if (DstChild->getOperator()->getName() == "imm") {
+      DstMIBuilder.addRenderer<CopyConstantAsImmRenderer>(DstChild->getName());
+      return InsertPt;
+    } else if (DstChild->getOperator()->getName() == "fpimm") {
+      DstMIBuilder.addRenderer<CopyFConstantAsFPImmRenderer>(
+          DstChild->getName());
+      return InsertPt;
+    }
+
+    if (DstChild->getOperator()->isSubClassOf("Instruction")) {
+      ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
+      if (ChildTypes.size() != 1)
+        return failedImport("Dst pattern child has multiple results");
+
+      Optional<LLTCodeGen> OpTyOrNone = None;
+      if (ChildTypes.front().isMachineValueType())
+        OpTyOrNone =
+            MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
+      if (!OpTyOrNone)
+        return failedImport("Dst operand has an unsupported type");
+
+      unsigned TempRegID = Rule.allocateTempRegID();
+      InsertPt = Rule.insertAction<MakeTempRegisterAction>(
+          InsertPt, OpTyOrNone.getValue(), TempRegID);
+      DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID);
+
+      auto InsertPtOrError = createAndImportSubInstructionRenderer(
+          ++InsertPt, Rule, DstChild, TempRegID);
+      if (auto Error = InsertPtOrError.takeError())
+        return std::move(Error);
+      return InsertPtOrError.get();
+    }
+
+    return failedImport("Dst pattern child isn't a leaf node or an MBB" + llvm::to_string(*DstChild));
   }
 
-  // Otherwise, we're looking for a bog-standard RegisterClass operand.
-  if (DstChild->hasAnyPredicate())
-    return failedImport("Dst pattern child has predicate (" +
-                        explainPredicates(DstChild) + ")");
+  // It could be a specific immediate in which case we should just check for
+  // that immediate.
+  if (const IntInit *ChildIntInit =
+          dyn_cast<IntInit>(DstChild->getLeafValue())) {
+    DstMIBuilder.addRenderer<ImmRenderer>(ChildIntInit->getValue());
+    return InsertPt;
+  }
 
+  // Otherwise, we're looking for a bog-standard RegisterClass operand.
   if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) {
     auto *ChildRec = ChildDefInit->getDef();
 
-    ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes();
+    ArrayRef<TypeSetByHwMode> ChildTypes = DstChild->getExtTypes();
     if (ChildTypes.size() != 1)
       return failedImport("Dst pattern child has multiple results");
 
-    auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
+    Optional<LLTCodeGen> OpTyOrNone = None;
+    if (ChildTypes.front().isMachineValueType())
+      OpTyOrNone = MVTToLLT(ChildTypes.front().getMachineValueType().SimpleTy);
     if (!OpTyOrNone)
       return failedImport("Dst operand has an unsupported type");
 
     if (ChildRec->isSubClassOf("Register")) {
-      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec);
-      return Error::success();
+      DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
+      return InsertPt;
     }
 
     if (ChildRec->isSubClassOf("RegisterClass") ||
-        ChildRec->isSubClassOf("RegisterOperand")) {
-      DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
-                                             DstChild->getName());
-      return Error::success();
+        ChildRec->isSubClassOf("RegisterOperand") ||
+        ChildRec->isSubClassOf("ValueType")) {
+      if (ChildRec->isSubClassOf("RegisterOperand") &&
+          !ChildRec->isValueUnset("GIZeroRegister")) {
+        DstMIBuilder.addRenderer<CopyOrAddZeroRegRenderer>(
+            DstChild->getName(), ChildRec->getValueAsDef("GIZeroRegister"));
+        return InsertPt;
+      }
+
+      DstMIBuilder.addRenderer<CopyRenderer>(DstChild->getName());
+      return InsertPt;
     }
 
     if (ChildRec->isSubClassOf("ComplexPattern")) {
@@ -1693,11 +3083,11 @@ Error GlobalISelEmitter::importExplicitUseRenderer(
         return failedImport(
             "SelectionDAG ComplexPattern not mapped to GlobalISel");
 
-      const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
+      const OperandMatcher &OM = Rule.getOperandMatcher(DstChild->getName());
       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
-          0, *ComplexPattern->second, DstChild->getName(),
+          *ComplexPattern->second, DstChild->getName(),
           OM.getAllocatedTemporariesBaseID());
-      return Error::success();
+      return InsertPt;
     }
 
     if (ChildRec->isSubClassOf("SDNodeXForm"))
@@ -1712,8 +3102,50 @@ Error GlobalISelEmitter::importExplicitUseRenderer(
 }
 
 Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
-    RuleMatcher &M, const TreePatternNode *Dst,
-    const InstructionMatcher &InsnMatcher) {
+    RuleMatcher &M, const TreePatternNode *Dst) {
+  auto InsertPtOrError = createInstructionRenderer(M.actions_end(), M, Dst);
+  if (auto Error = InsertPtOrError.takeError())
+    return std::move(Error);
+
+  action_iterator InsertPt = InsertPtOrError.get();
+  BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPt->get());
+
+  importExplicitDefRenderers(DstMIBuilder);
+
+  if (auto Error = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst)
+                       .takeError())
+    return std::move(Error);
+
+  return DstMIBuilder;
+}
+
+Expected<action_iterator>
+GlobalISelEmitter::createAndImportSubInstructionRenderer(
+    action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst,
+    unsigned TempRegID) {
+  auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst);
+
+  // TODO: Assert there's exactly one result.
+
+  if (auto Error = InsertPtOrError.takeError())
+    return std::move(Error);
+  InsertPt = InsertPtOrError.get();
+
+  BuildMIAction &DstMIBuilder =
+      *static_cast<BuildMIAction *>(InsertPtOrError.get()->get());
+
+  // Assign the result to TempReg.
+  DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true);
+
+  InsertPtOrError = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst);
+  if (auto Error = InsertPtOrError.takeError())
+    return std::move(Error);
+
+  return InsertPtOrError.get();
+}
+
+Expected<action_iterator> GlobalISelEmitter::createInstructionRenderer(
+    action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst) {
   Record *DstOp = Dst->getOperator();
   if (!DstOp->isSubClassOf("Instruction")) {
     if (DstOp->isSubClassOf("ValueType"))
@@ -1723,38 +3155,47 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
   }
   CodeGenInstruction *DstI = &Target.getInstruction(DstOp);
 
-  unsigned DstINumUses = DstI->Operands.size() - DstI->Operands.NumDefs;
-  unsigned ExpectedDstINumUses = Dst->getNumChildren();
-  bool IsExtractSubReg = false;
-
   // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction
   // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy.
-  if (DstI->TheDef->getName() == "COPY_TO_REGCLASS") {
+  if (DstI->TheDef->getName() == "COPY_TO_REGCLASS")
     DstI = &Target.getInstruction(RK.getDef("COPY"));
-    DstINumUses--; // Ignore the class constraint.
-    ExpectedDstINumUses--;
-  } else if (DstI->TheDef->getName() == "EXTRACT_SUBREG") {
+  else if (DstI->TheDef->getName() == "EXTRACT_SUBREG")
     DstI = &Target.getInstruction(RK.getDef("COPY"));
-    IsExtractSubReg = true;
-  }
+  else if (DstI->TheDef->getName() == "REG_SEQUENCE")
+    return failedImport("Unable to emit REG_SEQUENCE");
 
-  auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher);
+  return M.insertAction<BuildMIAction>(InsertPt, M.allocateOutputInsnID(),
+                                       DstI);
+}
 
-  // Render the explicit defs.
+void GlobalISelEmitter::importExplicitDefRenderers(
+    BuildMIAction &DstMIBuilder) {
+  const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
-    DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name);
+    DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
   }
+}
+
+Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
+    action_iterator InsertPt, RuleMatcher &M, BuildMIAction &DstMIBuilder,
+    const llvm::TreePatternNode *Dst) {
+  const CodeGenInstruction *DstI = DstMIBuilder.getCGI();
+  CodeGenInstruction *OrigDstI = &Target.getInstruction(Dst->getOperator());
 
   // EXTRACT_SUBREG needs to use a subregister COPY.
-  if (IsExtractSubReg) {
+  if (OrigDstI->TheDef->getName() == "EXTRACT_SUBREG") {
     if (!Dst->getChild(0)->isLeaf())
       return failedImport("EXTRACT_SUBREG child #1 is not a leaf");
 
     if (DefInit *SubRegInit =
             dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) {
-      CodeGenRegisterClass *RC = CGRegs.getRegClass(
-          getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()));
+      Record *RCDef = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue());
+      if (!RCDef)
+        return failedImport("EXTRACT_SUBREG child #0 could not "
+                            "be coerced to a register class");
+
+      CodeGenRegisterClass *RC = CGRegs.getRegClass(RCDef);
       CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
 
       const auto &SrcRCDstRCPair =
@@ -1765,15 +3206,22 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
           return failedImport("EXTRACT_SUBREG requires an additional COPY");
       }
 
-      DstMIBuilder.addRenderer<CopySubRegRenderer>(
-          0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
-      return DstMIBuilder;
+      DstMIBuilder.addRenderer<CopySubRegRenderer>(Dst->getChild(0)->getName(),
+                                                   SubIdx);
+      return InsertPt;
     }
 
     return failedImport("EXTRACT_SUBREG child #1 is not a subreg index");
   }
 
   // Render the explicit uses.
+  unsigned DstINumUses = OrigDstI->Operands.size() - OrigDstI->Operands.NumDefs;
+  unsigned ExpectedDstINumUses = Dst->getNumChildren();
+  if (OrigDstI->TheDef->getName() == "COPY_TO_REGCLASS") {
+    DstINumUses--; // Ignore the class constraint.
+    ExpectedDstINumUses--;
+  }
+
   unsigned Child = 0;
   unsigned NumDefaultOps = 0;
   for (unsigned I = 0; I != DstINumUses; ++I) {
@@ -1793,9 +3241,11 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
       continue;
     }
 
-    if (auto Error = importExplicitUseRenderer(
-            DstMIBuilder, Dst->getChild(Child), InsnMatcher))
+    auto InsertPtOrError = importExplicitUseRenderer(InsertPt, M, DstMIBuilder,
+                                                     Dst->getChild(Child));
+    if (auto Error = InsertPtOrError.takeError())
       return std::move(Error);
+    InsertPt = InsertPtOrError.get();
     ++Child;
   }
 
@@ -1806,7 +3256,7 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
                         " explicit ones and " + llvm::to_string(NumDefaultOps) +
                         " default ones");
 
-  return DstMIBuilder;
+  return InsertPt;
 }
 
 Error GlobalISelEmitter::importDefaultOperandRenderers(
@@ -1822,12 +3272,12 @@ Error GlobalISelEmitter::importDefaultOperandRenderers(
     }
 
     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
-      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef());
+      DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
       continue;
     }
 
     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
-      DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue());
+      DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
       continue;
     }
 
@@ -1847,10 +3297,12 @@ Error GlobalISelEmitter::importImplicitDefRenderers(
 
 Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   // Keep track of the matchers and actions to emit.
-  RuleMatcher M;
-  M.addAction<DebugCommentAction>(P);
+  RuleMatcher M(P.getSrcRecord()->getLoc());
+  M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
+                                  "  =>  " +
+                                  llvm::to_string(*P.getDstPattern()));
 
-  if (auto Error = importRulePredicates(M, P.getPredicates()->getValues()))
+  if (auto Error = importRulePredicates(M, P.getPredicates()))
     return std::move(Error);
 
   // Next, analyze the pattern operators.
@@ -1865,8 +3317,68 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     return failedImport("Src pattern root isn't a trivial operator (" +
                         toString(std::move(Err)) + ")");
 
-  if (Dst->isLeaf())
+  // The different predicates and matchers created during
+  // addInstructionMatcher use the RuleMatcher M to set up their
+  // instruction ID (InsnVarID) that are going to be used when
+  // M is going to be emitted.
+  // However, the code doing the emission still relies on the IDs
+  // returned during that process by the RuleMatcher when issuing
+  // the recordInsn opcodes.
+  // Because of that:
+  // 1. The order in which we created the predicates
+  //    and such must be the same as the order in which we emit them,
+  //    and
+  // 2. We need to reset the generation of the IDs in M somewhere between
+  //    addInstructionMatcher and emit
+  //
+  // FIXME: Long term, we don't want to have to rely on this implicit
+  // naming being the same. One possible solution would be to have
+  // explicit operator for operation capture and reference those.
+  // The plus side is that it would expose opportunities to share
+  // the capture accross rules. The downside is that it would
+  // introduce a dependency between predicates (captures must happen
+  // before their first use.)
+  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
+  unsigned TempOpIdx = 0;
+  auto InsnMatcherOrError =
+      createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
+  // Reset the ID generation so that the emitted IDs match the ones
+  // in the InstructionMatcher and such.
+  M.clearImplicitMap();
+  if (auto Error = InsnMatcherOrError.takeError())
+    return std::move(Error);
+  InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
+
+  if (Dst->isLeaf()) {
+    Record *RCDef = getInitValueAsRegClass(Dst->getLeafValue());
+
+    const CodeGenRegisterClass &RC = Target.getRegisterClass(RCDef);
+    if (RCDef) {
+      // We need to replace the def and all its uses with the specified
+      // operand. However, we must also insert COPY's wherever needed.
+      // For now, emit a copy and let the register allocator clean up.
+      auto &DstI = Target.getInstruction(RK.getDef("COPY"));
+      const auto &DstIOperand = DstI.Operands[0];
+
+      OperandMatcher &OM0 = InsnMatcher.getOperand(0);
+      OM0.setSymbolicName(DstIOperand.Name);
+      M.defineOperand(OM0.getSymbolicName(), OM0);
+      OM0.addPredicate<RegisterBankOperandMatcher>(RC);
+
+      auto &DstMIBuilder =
+          M.addAction<BuildMIAction>(M.allocateOutputInsnID(), &DstI);
+      DstMIBuilder.addRenderer<CopyRenderer>(DstIOperand.Name);
+      DstMIBuilder.addRenderer<CopyRenderer>(Dst->getName());
+      M.addAction<ConstrainOperandToRegClassAction>(0, 0, RC);
+
+      // We're done with this pattern!  It's eligible for GISel emission; return
+      // it.
+      ++NumPatternImported;
+      return std::move(M);
+    }
+
     return failedImport("Dst pattern root isn't a known leaf");
+  }
 
   // Start with the defined operands (i.e., the results of the root operator).
   Record *DstOp = Dst->getOperator();
@@ -1879,19 +3391,11 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
                         to_string(Src->getExtTypes().size()) + " def(s) vs " +
                         to_string(DstI.Operands.NumDefs) + " def(s))");
 
-  InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
-  unsigned TempOpIdx = 0;
-  auto InsnMatcherOrError =
-      createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
-  if (auto Error = InsnMatcherOrError.takeError())
-    return std::move(Error);
-  InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
-
   // The root of the match also has constraints on the register bank so that it
   // matches the result instruction.
   unsigned OpIdx = 0;
-  for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
-    (void)Ty;
+  for (const TypeSetByHwMode &VTy : Src->getExtTypes()) {
+    (void)VTy;
 
     const auto &DstIOperand = DstI.Operands[OpIdx];
     Record *DstIOpRec = DstIOperand.Rec;
@@ -1920,13 +3424,13 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
 
     OperandMatcher &OM = InsnMatcher.getOperand(OpIdx);
     OM.setSymbolicName(DstIOperand.Name);
+    M.defineOperand(OM.getSymbolicName(), OM);
     OM.addPredicate<RegisterBankOperandMatcher>(
         Target.getRegisterClass(DstIOpRec));
     ++OpIdx;
   }
 
-  auto DstMIBuilderOrError =
-      createAndImportInstructionRenderer(M, Dst, InsnMatcher);
+  auto DstMIBuilderOrError = createAndImportInstructionRenderer(M, Dst);
   if (auto Error = DstMIBuilderOrError.takeError())
     return std::move(Error);
   BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get();
@@ -1936,6 +3440,8 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs()))
     return std::move(Error);
 
+  DstMIBuilder.chooseInsnToMutate(M);
+
   // Constrain the registers to classes. This is normally derived from the
   // emitted instruction but a few instructions require special handling.
   if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") {
@@ -2006,7 +3512,92 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   return std::move(M);
 }
 
+// Emit imm predicate table and an enum to reference them with.
+// The 'Predicate_' part of the name is redundant but eliminating it is more
+// trouble than it's worth.
+void GlobalISelEmitter::emitImmPredicates(
+    raw_ostream &OS, StringRef TypeIdentifier, StringRef Type,
+    std::function<bool(const Record *R)> Filter) {
+  std::vector<const Record *> MatchedRecords;
+  const auto &Defs = RK.getAllDerivedDefinitions("PatFrag");
+  std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords),
+               [&](Record *Record) {
+                 return !Record->getValueAsString("ImmediateCode").empty() &&
+                        Filter(Record);
+               });
+
+  if (!MatchedRecords.empty()) {
+    OS << "// PatFrag predicates.\n"
+       << "enum {\n";
+    std::string EnumeratorSeparator =
+        (" = GIPFP_" + TypeIdentifier + "_Invalid + 1,\n").str();
+    for (const auto *Record : MatchedRecords) {
+      OS << "  GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName()
+         << EnumeratorSeparator;
+      EnumeratorSeparator = ",\n";
+    }
+    OS << "};\n";
+  }
+
+  for (const auto *Record : MatchedRecords)
+    OS << "static bool Predicate_" << Record->getName() << "(" << Type
+       << " Imm) {" << Record->getValueAsString("ImmediateCode") << "}\n";
+
+  OS << "static InstructionSelector::" << TypeIdentifier
+     << "ImmediatePredicateFn " << TypeIdentifier << "ImmPredicateFns[] = {\n"
+     << "  nullptr,\n";
+  for (const auto *Record : MatchedRecords)
+    OS << "  Predicate_" << Record->getName() << ",\n";
+  OS << "};\n";
+}
+
+std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
+    std::vector<RuleMatcher> &Rules,
+    std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) {
+  std::vector<Matcher *> OptRules;
+  // Start with a stupid grouping for now.
+  std::unique_ptr<GroupMatcher> CurrentGroup = make_unique<GroupMatcher>();
+  assert(CurrentGroup->conditions_empty());
+  unsigned NbGroup = 0;
+  for (RuleMatcher &Rule : Rules) {
+    std::unique_ptr<PredicateMatcher> Predicate = Rule.forgetFirstCondition();
+    if (!CurrentGroup->conditions_empty() &&
+        !CurrentGroup->lastConditionMatches(*Predicate)) {
+      // Start a new group.
+      ++NbGroup;
+      OptRules.push_back(CurrentGroup.get());
+      StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+      CurrentGroup = make_unique<GroupMatcher>();
+      assert(CurrentGroup->conditions_empty());
+    }
+    if (CurrentGroup->conditions_empty())
+      CurrentGroup->addCondition(std::move(Predicate));
+    CurrentGroup->addRule(Rule);
+  }
+  if (!CurrentGroup->conditions_empty()) {
+    ++NbGroup;
+    OptRules.push_back(CurrentGroup.get());
+    StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+  }
+  DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
+  return OptRules;
+}
+
 void GlobalISelEmitter::run(raw_ostream &OS) {
+  if (!UseCoverageFile.empty()) {
+    RuleCoverage = CodeGenCoverage();
+    auto RuleCoverageBufOrErr = MemoryBuffer::getFile(UseCoverageFile);
+    if (!RuleCoverageBufOrErr) {
+      PrintWarning(SMLoc(), "Missing rule coverage data");
+      RuleCoverage = None;
+    } else {
+      if (!RuleCoverage->parse(*RuleCoverageBufOrErr.get(), Target.getName())) {
+        PrintWarning(SMLoc(), "Ignoring invalid or missing rule coverage data");
+        RuleCoverage = None;
+      }
+    }
+  }
+
   // Track the GINodeEquiv definitions.
   gatherNodeEquivs();
 
@@ -2016,6 +3607,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
   // Look through the SelectionDAG patterns we found, possibly emitting some.
   for (const PatternToMatch &Pat : CGP.ptms()) {
     ++NumPatternTotal;
+
     auto MatcherOrErr = runOnPattern(Pat);
 
     // The pattern analysis can fail, indicating an unsupported pattern.
@@ -2031,20 +3623,16 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
       continue;
     }
 
+    if (RuleCoverage) {
+      if (RuleCoverage->isCovered(MatcherOrErr->getRuleID()))
+        ++NumPatternsTested;
+      else
+        PrintWarning(Pat.getSrcRecord()->getLoc(),
+                     "Pattern is not covered by a test");
+    }
     Rules.push_back(std::move(MatcherOrErr.get()));
   }
 
-  std::stable_sort(Rules.begin(), Rules.end(),
-            [&](const RuleMatcher &A, const RuleMatcher &B) {
-              if (A.isHigherPriorityThan(B)) {
-                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(),
@@ -2067,22 +3655,19 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
      << "  mutable MatcherState State;\n"
      << "  typedef "
-        "ComplexRendererFn("
+        "ComplexRendererFns("
      << Target.getName()
      << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
-     << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
+     << "  const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
         "MatcherInfo;\n"
+     << "  static " << Target.getName()
+     << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\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"
+     << "MatcherInfo({TypeObjects, FeatureBitsets, I64ImmPredicateFns, "
+        "APIntImmPredicateFns, APFloatImmPredicateFns, ComplexPredicateFns})\n"
      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
@@ -2113,18 +3698,12 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
   // 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::vector<LLTCodeGen> TypeObjects;
+  for (const auto &Ty : LLTOperandMatcher::KnownTypes)
+    TypeObjects.push_back(Ty);
   std::sort(TypeObjects.begin(), TypeObjects.end());
-  OS << "enum {\n";
+  OS << "// LLT Objects.\n"
+     << "enum {\n";
   for (const auto &TypeObject : TypeObjects) {
     OS << "  ";
     TypeObject.emitCxxEnumValue(OS);
@@ -2162,7 +3741,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
   FeatureBitsets.erase(
       std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
       FeatureBitsets.end());
-  OS << "enum {\n"
+  OS << "// Feature bitsets.\n"
+     << "enum {\n"
      << "  GIFBS_Invalid,\n";
   for (const auto &FeatureBitset : FeatureBitsets) {
     if (FeatureBitset.empty())
@@ -2186,15 +3766,40 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
   OS << "};\n\n";
 
   // Emit complex predicate table and an enum to reference them with.
-  OS << "enum {\n"
+  OS << "// ComplexPattern predicates.\n"
+     << "enum {\n"
      << "  GICP_Invalid,\n";
   for (const auto &Record : ComplexPredicates)
     OS << "  GICP_" << Record->getName() << ",\n";
   OS << "};\n"
      << "// See constructor for table contents\n\n";
 
+  emitImmPredicates(OS, "I64", "int64_t", [](const Record *R) {
+    bool Unset;
+    return !R->getValueAsBitOrUnset("IsAPFloat", Unset) &&
+           !R->getValueAsBit("IsAPInt");
+  });
+  emitImmPredicates(OS, "APFloat", "const APFloat &", [](const Record *R) {
+    bool Unset;
+    return R->getValueAsBitOrUnset("IsAPFloat", Unset);
+  });
+  emitImmPredicates(OS, "APInt", "const APInt &", [](const Record *R) {
+    return R->getValueAsBit("IsAPInt");
+  });
+  OS << "\n";
+
+  OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n"
+     << Target.getName() << "InstructionSelector::ComplexPredicateFns[] = {\n"
+     << "  nullptr, // GICP_Invalid\n";
+  for (const auto &Record : ComplexPredicates)
+    OS << "  &" << Target.getName()
+       << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
+       << ", // " << Record->getName() << "\n";
+  OS << "};\n\n";
+
   OS << "bool " << Target.getName()
-     << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
+     << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage "
+        "&CoverageInfo) const {\n"
      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
      << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
      << "  // FIXME: This should be computed on a per-function basis rather "
@@ -2206,13 +3811,37 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
      << "  State.MIs.clear();\n"
      << "  State.MIs.push_back(&I);\n\n";
 
-  for (auto &Rule : Rules) {
-    Rule.emit(OS);
-    ++CurrentMatchTableID;
+  std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
+                                                   const RuleMatcher &B) {
+    if (A.isHigherPriorityThan(B)) {
+      assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
+                                           "and less important at "
+                                           "the same time");
+      return true;
+    }
+    return false;
+  });
+  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
+
+  std::vector<Matcher *> OptRules;
+  if (OptimizeMatchTable)
+    OptRules = optimizeRules(Rules, StorageGroupMatcher);
+  else
+    for (Matcher &Rule : Rules)
+      OptRules.push_back(&Rule);
+
+  MatchTable Table(0);
+  for (Matcher *Rule : OptRules) {
+    Rule->emit(Table);
     ++NumPatternEmitted;
-    assert(CurrentMatchTableID == NumPatternEmitted &&
-           "Statistic deviates from number of emitted tables");
   }
+  Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+  Table.emitDeclaration(OS);
+  OS << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, ";
+  Table.emitUse(OS);
+  OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n"
+     << "    return true;\n"
+     << "  }\n\n";
 
   OS << "  return false;\n"
      << "}\n"
@@ -2245,6 +3874,138 @@ void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
 }
 
+TreePatternNode *GlobalISelEmitter::fixupPatternNode(TreePatternNode *N) {
+  if (!N->isLeaf()) {
+    for (unsigned I = 0, E = N->getNumChildren(); I < E; ++I) {
+      TreePatternNode *OrigChild = N->getChild(I);
+      TreePatternNode *NewChild = fixupPatternNode(OrigChild);
+      if (OrigChild != NewChild)
+        N->setChild(I, NewChild);
+    }
+
+    if (N->getOperator()->getName() == "ld") {
+      // If it's a signext-load we need to adapt the pattern slightly. We need
+      // to split the node into (sext (ld ...)), remove the <<signext>> predicate,
+      // and then apply the <<signextTY>> predicate by updating the result type
+      // of the load.
+      //
+      // For example:
+      //   (ld:[i32] [iPTR])<<unindexed>><<signext>><<signexti16>>
+      // must be transformed into:
+      //   (sext:[i32] (ld:[i16] [iPTR])<<unindexed>>)
+      //
+      // Likewise for zeroext-load and anyext-load.
+
+      std::vector<TreePredicateFn> Predicates;
+      bool IsSignExtLoad = false;
+      bool IsZeroExtLoad = false;
+      bool IsAnyExtLoad = false;
+      Record *MemVT = nullptr;
+      for (const auto &P : N->getPredicateFns()) {
+        if (P.isLoad() && P.isSignExtLoad()) {
+          IsSignExtLoad = true;
+          continue;
+        }
+        if (P.isLoad() && P.isZeroExtLoad()) {
+          IsZeroExtLoad = true;
+          continue;
+        }
+        if (P.isLoad() && P.isAnyExtLoad()) {
+          IsAnyExtLoad = true;
+          continue;
+        }
+        if (P.isLoad() && P.getMemoryVT()) {
+          MemVT = P.getMemoryVT();
+          continue;
+        }
+        Predicates.push_back(P);
+      }
+
+      if ((IsSignExtLoad || IsZeroExtLoad || IsAnyExtLoad) && MemVT) {
+        assert((IsSignExtLoad + IsZeroExtLoad + IsAnyExtLoad) == 1 &&
+               "IsSignExtLoad, IsZeroExtLoad, IsAnyExtLoad are mutually exclusive");
+        TreePatternNode *Ext = new TreePatternNode(
+            RK.getDef(IsSignExtLoad ? "sext"
+                                    : IsZeroExtLoad ? "zext" : "anyext"),
+            {N}, 1);
+        Ext->setType(0, N->getType(0));
+        N->clearPredicateFns();
+        N->setPredicateFns(Predicates);
+        N->setType(0, getValueType(MemVT));
+        return Ext;
+      }
+    }
+  }
+
+  return N;
+}
+
+void GlobalISelEmitter::fixupPatternTrees(TreePattern *P) {
+  for (unsigned I = 0, E = P->getNumTrees(); I < E; ++I) {
+    TreePatternNode *OrigTree = P->getTree(I);
+    TreePatternNode *NewTree = fixupPatternNode(OrigTree);
+    if (OrigTree != NewTree)
+      P->setTree(I, NewTree);
+  }
+}
+
+std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() {
+  assert(!insnmatchers_empty() &&
+         "Trying to forget something that does not exist");
+
+  InstructionMatcher &Matcher = insnmatchers_front();
+  std::unique_ptr<PredicateMatcher> Condition;
+  if (!Matcher.predicates_empty())
+    Condition = Matcher.predicates_pop_front();
+  if (!Condition) {
+    // If there is no more predicate on the instruction itself, look at its
+    // operands.
+    assert(!Matcher.operands_empty() &&
+           "Empty instruction should have been discarded");
+    OperandMatcher &OpMatcher = **Matcher.operands_begin();
+    assert(!OpMatcher.predicates_empty() && "no operand constraint");
+    Condition = OpMatcher.predicates_pop_front();
+    // If this operand is free of constraints, rip it off.
+    if (OpMatcher.predicates_empty())
+      Matcher.pop_front();
+  }
+  // Rip the instruction off when it is empty.
+  if (Matcher.operands_empty() && Matcher.predicates_empty())
+    insnmatchers_pop_front();
+  return Condition;
+}
+
+bool GroupMatcher::lastConditionMatches(
+    const PredicateMatcher &Predicate) const {
+  const auto &LastCondition = conditions_back();
+  return Predicate.isIdentical(*LastCondition);
+}
+
+void GroupMatcher::emit(MatchTable &Table) {
+  unsigned LabelID = Table.allocateLabelID();
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Try", +1)
+          << MatchTable::Comment("On fail goto")
+          << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
+    for (auto &Condition : Conditions)
+      Condition->emitPredicateOpcodes(
+          Table, *static_cast<RuleMatcher *>(*Rules.begin()));
+  }
+  // Emit the conditions.
+  // Then checks apply the rules.
+  for (const auto &Rule : Rules)
+    Rule->emit(Table);
+  // If we don't succeeded for that block, that means we are not going to select
+  // this instruction.
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+    Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+          << MatchTable::Label(LabelID);
+  }
+}
+
+unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); }
+
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//