vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085

47 files changed, 4301 insertions, 894 deletions

diff --git a/llvm/utils/TableGen/AsmMatcherEmitter.cpp b/llvm/utils/TableGen/AsmMatcherEmitter.cpp
index 1d39b300091fc..ccf0959389ba9 100644
--- a/llvm/utils/TableGen/AsmMatcherEmitter.cpp
+++ b/llvm/utils/TableGen/AsmMatcherEmitter.cpp
@@ -3347,7 +3347,7 @@ void AsmMatcherEmitter::run(raw_ostream &OS) {
       return true;
     if (A.size() > B.size())
       return false;
-    for (const auto &Pair : zip(A, B)) {
+    for (auto Pair : zip(A, B)) {
       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
         return true;
       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
diff --git a/llvm/utils/TableGen/AsmWriterEmitter.cpp b/llvm/utils/TableGen/AsmWriterEmitter.cpp
index b5c7f35be0e54..58c0d32d44eb9 100644
--- a/llvm/utils/TableGen/AsmWriterEmitter.cpp
+++ b/llvm/utils/TableGen/AsmWriterEmitter.cpp
@@ -29,6 +29,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
@@ -274,13 +275,14 @@ void AsmWriterEmitter::EmitPrintInstruction(raw_ostream &O) {
   StringRef ClassName = AsmWriter->getValueAsString("AsmWriterClassName");
   bool PassSubtarget = AsmWriter->getValueAsInt("PassSubtarget");
 
-  O <<
-  "/// printInstruction - This method is automatically generated by tablegen\n"
-  "/// from the instruction set description.\n"
-    "void " << Target.getName() << ClassName
-            << "::printInstruction(const MCInst *MI, "
-            << (PassSubtarget ? "const MCSubtargetInfo &STI, " : "")
-            << "raw_ostream &O) {\n";
+  O << "/// printInstruction - This method is automatically generated by "
+       "tablegen\n"
+       "/// from the instruction set description.\n"
+       "void "
+    << Target.getName() << ClassName
+    << "::printInstruction(const MCInst *MI, uint64_t Address, "
+    << (PassSubtarget ? "const MCSubtargetInfo &STI, " : "")
+    << "raw_ostream &O) {\n";
 
   // Build an aggregate string, and build a table of offsets into it.
   SequenceToOffsetTable<std::string> StringTable;
@@ -616,17 +618,22 @@ namespace {
 // they both have the same conditionals. In which case, we cannot print out the
 // alias for that pattern.
 class IAPrinter {
-  std::vector<std::string> Conds;
   std::map<StringRef, std::pair<int, int>> OpMap;
 
+  std::vector<std::string> Conds;
+
   std::string Result;
   std::string AsmString;
 
+  unsigned NumMIOps;
+
 public:
-  IAPrinter(std::string R, std::string AS)
-      : Result(std::move(R)), AsmString(std::move(AS)) {}
+  IAPrinter(std::string R, std::string AS, unsigned NumMIOps)
+      : Result(std::move(R)), AsmString(std::move(AS)), NumMIOps(NumMIOps) {}
 
-  void addCond(const std::string &C) { Conds.push_back(C); }
+  void addCond(std::string C) { Conds.push_back(std::move(C)); }
+  ArrayRef<std::string> getConds() const { return Conds; }
+  size_t getCondCount() const { return Conds.size(); }
 
   void addOperand(StringRef Op, int OpIdx, int PrintMethodIdx = -1) {
     assert(OpIdx >= 0 && OpIdx < 0xFE && "Idx out of range");
@@ -635,6 +642,10 @@ public:
     OpMap[Op] = std::make_pair(OpIdx, PrintMethodIdx);
   }
 
+  unsigned getNumMIOps() { return NumMIOps; }
+
+  StringRef getResult() { return Result; }
+
   bool isOpMapped(StringRef Op) { return OpMap.find(Op) != OpMap.end(); }
   int getOpIndex(StringRef Op) { return OpMap[Op].first; }
   std::pair<int, int> &getOpData(StringRef Op) { return OpMap[Op]; }
@@ -664,35 +675,16 @@ public:
     return std::make_pair(StringRef(Start, I - Start), Next);
   }
 
-  void print(raw_ostream &O) {
-    if (Conds.empty()) {
-      O.indent(6) << "return true;\n";
-      return;
-    }
-
-    O << "if (";
-
-    for (std::vector<std::string>::iterator
-           I = Conds.begin(), E = Conds.end(); I != E; ++I) {
-      if (I != Conds.begin()) {
-        O << " &&\n";
-        O.indent(8);
-      }
-
-      O << *I;
-    }
-
-    O << ") {\n";
-    O.indent(6) << "// " << Result << "\n";
-
+  std::string formatAliasString(uint32_t &UnescapedSize) {
     // Directly mangle mapped operands into the string. Each operand is
     // identified by a '$' sign followed by a byte identifying the number of the
     // operand. We add one to the index to avoid zero bytes.
     StringRef ASM(AsmString);
-    SmallString<128> OutString;
-    raw_svector_ostream OS(OutString);
+    std::string OutString;
+    raw_string_ostream OS(OutString);
     for (StringRef::iterator I = ASM.begin(), E = ASM.end(); I != E;) {
       OS << *I;
+      ++UnescapedSize;
       if (*I == '$') {
         StringRef Name;
         std::tie(Name, I) = parseName(++I, E);
@@ -703,23 +695,25 @@ public:
         if (PrintIndex == -1) {
           // Can use the default printOperand route.
           OS << format("\\x%02X", (unsigned char)OpIndex + 1);
-        } else
+          ++UnescapedSize;
+        } else {
           // 3 bytes if a PrintMethod is needed: 0xFF, the MCInst operand
           // number, and which of our pre-detected Methods to call.
           OS << format("\\xFF\\x%02X\\x%02X", OpIndex + 1, PrintIndex + 1);
+          UnescapedSize += 3;
+        }
       } else {
         ++I;
       }
     }
 
-    // Emit the string.
-    O.indent(6) << "AsmString = \"" << OutString << "\";\n";
-
-    O.indent(6) << "break;\n";
-    O.indent(4) << '}';
+    OS.flush();
+    return OutString;
   }
 
   bool operator==(const IAPrinter &RHS) const {
+    if (NumMIOps != RHS.NumMIOps)
+      return false;
     if (Conds.size() != RHS.Conds.size())
       return false;
 
@@ -799,6 +793,9 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
   DenseMap<const Record*, unsigned> MCOpPredicateMap;
 
   for (auto &Aliases : AliasMap) {
+    // Collection of instruction alias rules. May contain ambiguous rules.
+    std::vector<IAPrinter> IAPs;
+
     for (auto &Alias : Aliases.second) {
       const CodeGenInstAlias &CGA = Alias.first;
       unsigned LastOpNo = CGA.ResultInstOperandIndex.size();
@@ -808,33 +805,18 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
       unsigned NumResultOps = CountNumOperands(FlatInstAsmString, Variant);
 
       std::string FlatAliasAsmString =
-        CodeGenInstruction::FlattenAsmStringVariants(CGA.AsmString,
-                                                      Variant);
+          CodeGenInstruction::FlattenAsmStringVariants(CGA.AsmString, Variant);
 
       // Don't emit the alias if it has more operands than what it's aliasing.
       if (NumResultOps < CountNumOperands(FlatAliasAsmString, Variant))
         continue;
 
-      IAPrinter IAP(CGA.Result->getAsString(), FlatAliasAsmString);
-
       StringRef Namespace = Target.getName();
-      std::vector<Record *> ReqFeatures;
-      if (PassSubtarget) {
-        // We only consider ReqFeatures predicates if PassSubtarget
-        std::vector<Record *> RF =
-            CGA.TheDef->getValueAsListOfDefs("Predicates");
-        copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
-          return R->getValueAsBit("AssemblerMatcherPredicate");
-        });
-      }
-
       unsigned NumMIOps = 0;
       for (auto &ResultInstOpnd : CGA.ResultInst->Operands)
         NumMIOps += ResultInstOpnd.MINumOperands;
 
-      std::string Cond;
-      Cond = std::string("MI->getNumOperands() == ") + utostr(NumMIOps);
-      IAP.addCond(Cond);
+      IAPrinter IAP(CGA.Result->getAsString(), FlatAliasAsmString, NumMIOps);
 
       bool CantHandle = false;
 
@@ -858,7 +840,9 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
           break;
         }
 
-        std::string Op = "MI->getOperand(" + utostr(MIOpNum) + ")";
+        // Ignore unchecked result operands.
+        while (IAP.getCondCount() < MIOpNum)
+          IAP.addCond("AliasPatternCond::K_Ignore, 0");
 
         const CodeGenInstAlias::ResultOperand &RO = CGA.ResultOperands[i];
 
@@ -885,19 +869,17 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
           if (Rec->isSubClassOf("RegisterOperand"))
             Rec = Rec->getValueAsDef("RegClass");
           if (Rec->isSubClassOf("RegisterClass")) {
-            IAP.addCond(Op + ".isReg()");
-
             if (!IAP.isOpMapped(ROName)) {
               IAP.addOperand(ROName, MIOpNum, PrintMethodIdx);
               Record *R = CGA.ResultOperands[i].getRecord();
               if (R->isSubClassOf("RegisterOperand"))
                 R = R->getValueAsDef("RegClass");
-              Cond = std::string("MRI.getRegClass(") + Target.getName().str() +
-                     "::" + R->getName().str() + "RegClassID).contains(" + Op +
-                     ".getReg())";
+              IAP.addCond(formatv(
+                  "AliasPatternCond::K_RegClass, {0}::{1}RegClassID", Namespace,
+                  R->getName()));
             } else {
-              Cond = Op + ".getReg() == MI->getOperand(" +
-                     utostr(IAP.getOpIndex(ROName)) + ").getReg()";
+              IAP.addCond(formatv("AliasPatternCond::K_TiedReg, {0}",
+                                  IAP.getOpIndex(ROName)));
             }
           } else {
             // Assume all printable operands are desired for now. This can be
@@ -914,21 +896,19 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
               } else
                 break; // No conditions on this operand at all
             }
-            Cond = (Target.getName() + ClassName + "ValidateMCOperand(" + Op +
-                    ", STI, " + utostr(Entry) + ")")
-                       .str();
+            IAP.addCond(formatv("AliasPatternCond::K_Custom, {0}", Entry));
           }
-          // for all subcases of ResultOperand::K_Record:
-          IAP.addCond(Cond);
           break;
         }
         case CodeGenInstAlias::ResultOperand::K_Imm: {
           // Just because the alias has an immediate result, doesn't mean the
           // MCInst will. An MCExpr could be present, for example.
-          IAP.addCond(Op + ".isImm()");
-
-          Cond = Op + ".getImm() == " + itostr(CGA.ResultOperands[i].getImm());
-          IAP.addCond(Cond);
+          auto Imm = CGA.ResultOperands[i].getImm();
+          int32_t Imm32 = int32_t(Imm);
+          if (Imm != Imm32)
+            PrintFatalError("Matching an alias with an immediate out of the "
+                            "range of int32_t is not supported");
+          IAP.addCond(formatv("AliasPatternCond::K_Imm, uint32_t({0})", Imm32));
           break;
         }
         case CodeGenInstAlias::ResultOperand::K_Reg:
@@ -939,9 +919,9 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
             break;
           }
 
-          Cond = Op + ".getReg() == " + Target.getName().str() + "::" +
-                 CGA.ResultOperands[i].getRegister()->getName().str();
-          IAP.addCond(Cond);
+          StringRef Reg = CGA.ResultOperands[i].getRegister()->getName();
+          IAP.addCond(
+              formatv("AliasPatternCond::K_Reg, {0}::{1}", Namespace, Reg));
           break;
         }
 
@@ -950,6 +930,16 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
 
       if (CantHandle) continue;
 
+      std::vector<Record *> ReqFeatures;
+      if (PassSubtarget) {
+        // We only consider ReqFeatures predicates if PassSubtarget
+        std::vector<Record *> RF =
+            CGA.TheDef->getValueAsListOfDefs("Predicates");
+        copy_if(RF, std::back_inserter(ReqFeatures), [](Record *R) {
+          return R->getValueAsBit("AssemblerMatcherPredicate");
+        });
+      }
+
       for (auto I = ReqFeatures.cbegin(); I != ReqFeatures.cend(); I++) {
         Record *R = *I;
         StringRef AsmCondString = R->getValueAsString("AssemblerCondString");
@@ -959,16 +949,12 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
         SplitString(AsmCondString, Ops, ",");
         assert(!Ops.empty() && "AssemblerCondString cannot be empty");
 
-        for (auto &Op : Ops) {
+        for (StringRef Op : Ops) {
           assert(!Op.empty() && "Empty operator");
-          if (Op[0] == '!')
-            Cond = ("!STI.getFeatureBits()[" + Namespace + "::" + Op.substr(1) +
-                    "]")
-                       .str();
-          else
-            Cond =
-                ("STI.getFeatureBits()[" + Namespace + "::" + Op + "]").str();
-          IAP.addCond(Cond);
+          bool IsNeg = Op[0] == '!';
+          StringRef Feature = Op.drop_front(IsNeg ? 1 : 0);
+          IAP.addCond(formatv("AliasPatternCond::K_{0}Feature, {1}::{2}",
+                              IsNeg ? "Neg" : "", Namespace, Feature));
         }
       }
 
@@ -988,13 +974,32 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
           << " *MI, " << (PassSubtarget ? "const MCSubtargetInfo &STI, " : "")
           << "raw_ostream &OS) {\n";
 
-  std::string Cases;
-  raw_string_ostream CasesO(Cases);
-
-  for (auto &Entry : IAPrinterMap) {
-    std::vector<IAPrinter> &IAPs = Entry.second;
+  std::string PatternsForOpcode;
+  raw_string_ostream OpcodeO(PatternsForOpcode);
+
+  unsigned PatternCount = 0;
+  std::string Patterns;
+  raw_string_ostream PatternO(Patterns);
+
+  unsigned CondCount = 0;
+  std::string Conds;
+  raw_string_ostream CondO(Conds);
+
+  // All flattened alias strings.
+  std::map<std::string, uint32_t> AsmStringOffsets;
+  std::vector<std::pair<uint32_t, std::string>> AsmStrings;
+  size_t AsmStringsSize = 0;
+
+  // Iterate over the opcodes in enum order so they are sorted by opcode for
+  // binary search.
+  for (const CodeGenInstruction *Inst : NumberedInstructions) {
+    auto It = IAPrinterMap.find(getQualifiedName(Inst->TheDef));
+    if (It == IAPrinterMap.end())
+      continue;
+    std::vector<IAPrinter> &IAPs = It->second;
     std::vector<IAPrinter*> UniqueIAPs;
 
+    // Remove any ambiguous alias rules.
     for (auto &LHS : IAPs) {
       bool IsDup = false;
       for (const auto &RHS : IAPs) {
@@ -1010,18 +1015,43 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
 
     if (UniqueIAPs.empty()) continue;
 
-    CasesO.indent(2) << "case " << Entry.first << ":\n";
+    unsigned PatternStart = PatternCount;
+
+    // Insert the pattern start and opcode in the pattern list for debugging.
+    PatternO << formatv("    // {0} - {1}\n", It->first, PatternStart);
 
     for (IAPrinter *IAP : UniqueIAPs) {
-      CasesO.indent(4);
-      IAP->print(CasesO);
-      CasesO << '\n';
+      // Start each condition list with a comment of the resulting pattern that
+      // we're trying to match.
+      unsigned CondStart = CondCount;
+      CondO << formatv("    // {0} - {1}\n", IAP->getResult(), CondStart);
+      for (const auto &Cond : IAP->getConds())
+        CondO << "    {" << Cond << "},\n";
+      CondCount += IAP->getCondCount();
+
+      // After operands have been examined, re-encode the alias string with
+      // escapes indicating how operands should be printed.
+      uint32_t UnescapedSize = 0;
+      std::string EncodedAsmString = IAP->formatAliasString(UnescapedSize);
+      auto Insertion =
+          AsmStringOffsets.insert({EncodedAsmString, AsmStringsSize});
+      if (Insertion.second) {
+        // If the string is new, add it to the vector.
+        AsmStrings.push_back({AsmStringsSize, EncodedAsmString});
+        AsmStringsSize += UnescapedSize + 1;
+      }
+      unsigned AsmStrOffset = Insertion.first->second;
+
+      PatternO << formatv("    {{{0}, {1}, {2}, {3} },\n", AsmStrOffset,
+                          CondStart, IAP->getNumMIOps(), IAP->getCondCount());
+      ++PatternCount;
     }
 
-    CasesO.indent(4) << "return false;\n";
+    OpcodeO << formatv("    {{{0}, {1}, {2} },\n", It->first, PatternStart,
+                       PatternCount - PatternStart);
   }
 
-  if (CasesO.str().empty()) {
+  if (OpcodeO.str().empty()) {
     O << HeaderO.str();
     O << "  return false;\n";
     O << "}\n\n";
@@ -1029,6 +1059,7 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
     return;
   }
 
+  // Forward declare the validation method if needed.
   if (!MCOpPredicates.empty())
     O << "static bool " << Target.getName() << ClassName
       << "ValidateMCOperand(const MCOperand &MCOp,\n"
@@ -1036,11 +1067,52 @@ void AsmWriterEmitter::EmitPrintAliasInstruction(raw_ostream &O) {
       << "                  unsigned PredicateIndex);\n";
 
   O << HeaderO.str();
-  O.indent(2) << "const char *AsmString;\n";
-  O.indent(2) << "switch (MI->getOpcode()) {\n";
-  O.indent(2) << "default: return false;\n";
-  O << CasesO.str();
-  O.indent(2) << "}\n\n";
+  O.indent(2) << "static const PatternsForOpcode OpToPatterns[] = {\n";
+  O << OpcodeO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const AliasPattern Patterns[] = {\n";
+  O << PatternO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const AliasPatternCond Conds[] = {\n";
+  O << CondO.str();
+  O.indent(2) << "};\n\n";
+  O.indent(2) << "static const char AsmStrings[] =\n";
+  for (const auto &P : AsmStrings) {
+    O.indent(4) << "/* " << P.first << " */ \"" << P.second << "\\0\"\n";
+  }
+
+  O.indent(2) << ";\n\n";
+
+  // Assert that the opcode table is sorted. Use a static local constructor to
+  // ensure that the check only happens once on first run.
+  O << "#ifndef NDEBUG\n";
+  O.indent(2) << "static struct SortCheck {\n";
+  O.indent(2) << "  SortCheck(ArrayRef<PatternsForOpcode> OpToPatterns) {\n";
+  O.indent(2) << "    assert(std::is_sorted(\n";
+  O.indent(2) << "               OpToPatterns.begin(), OpToPatterns.end(),\n";
+  O.indent(2) << "               [](const PatternsForOpcode &L, const "
+                 "PatternsForOpcode &R) {\n";
+  O.indent(2) << "                 return L.Opcode < R.Opcode;\n";
+  O.indent(2) << "               }) &&\n";
+  O.indent(2) << "           \"tablegen failed to sort opcode patterns\");\n";
+  O.indent(2) << "  }\n";
+  O.indent(2) << "} sortCheckVar(OpToPatterns);\n";
+  O << "#endif\n\n";
+
+  O.indent(2) << "AliasMatchingData M {\n";
+  O.indent(2) << "  makeArrayRef(OpToPatterns),\n";
+  O.indent(2) << "  makeArrayRef(Patterns),\n";
+  O.indent(2) << "  makeArrayRef(Conds),\n";
+  O.indent(2) << "  StringRef(AsmStrings, array_lengthof(AsmStrings)),\n";
+  if (MCOpPredicates.empty())
+    O.indent(2) << "  nullptr,\n";
+  else
+    O.indent(2) << "  &" << Target.getName() << ClassName << "ValidateMCOperand,\n";
+  O.indent(2) << "};\n";
+
+  O.indent(2) << "const char *AsmString = matchAliasPatterns(MI, "
+              << (PassSubtarget ? "&STI" : "nullptr") << ", M);\n";
+  O.indent(2) << "if (!AsmString) return false;\n\n";
 
   // Code that prints the alias, replacing the operands with the ones from the
   // MCInst.
diff --git a/llvm/utils/TableGen/AsmWriterInst.h b/llvm/utils/TableGen/AsmWriterInst.h
index 7d88e5a9d0378..a59112efea44f 100644
--- a/llvm/utils/TableGen/AsmWriterInst.h
+++ b/llvm/utils/TableGen/AsmWriterInst.h
@@ -36,7 +36,7 @@ namespace llvm {
 
     /// MiOpNo - For isMachineInstrOperand, this is the operand number of the
     /// machine instruction.
-    unsigned MIOpNo;
+    unsigned MIOpNo = 0;
 
     /// Str - For isLiteralTextOperand, this IS the literal text.  For
     /// isMachineInstrOperand, this is the PrinterMethodName for the operand..
diff --git a/llvm/utils/TableGen/CodeEmitterGen.cpp b/llvm/utils/TableGen/CodeEmitterGen.cpp
index 42f69cb253d21..68cb8f181e62d 100644
--- a/llvm/utils/TableGen/CodeEmitterGen.cpp
+++ b/llvm/utils/TableGen/CodeEmitterGen.cpp
@@ -563,7 +563,7 @@ void CodeEmitterGen::run(raw_ostream &o) {
       return true;
     if (A.size() > B.size())
       return false;
-    for (const auto &Pair : zip(A, B)) {
+    for (auto Pair : zip(A, B)) {
       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
         return true;
       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
index 46f986ca0176b..7e0ba98da94aa 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp
@@ -23,6 +23,7 @@
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/TypeSize.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <algorithm>
@@ -481,12 +482,12 @@ bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small,
 
     if (any_of(S, isIntegerOrPtr) && any_of(S, isIntegerOrPtr)) {
       auto NotInt = [](MVT VT) { return !isIntegerOrPtr(VT); };
-      Changed |= berase_if(S, NotInt) |
-                 berase_if(B, NotInt);
+      Changed |= berase_if(S, NotInt);
+      Changed |= berase_if(B, NotInt);
     } else if (any_of(S, isFloatingPoint) && any_of(B, isFloatingPoint)) {
       auto NotFP = [](MVT VT) { return !isFloatingPoint(VT); };
-      Changed |= berase_if(S, NotFP) |
-                 berase_if(B, NotFP);
+      Changed |= berase_if(S, NotFP);
+      Changed |= berase_if(B, NotFP);
     } else if (S.empty() || B.empty()) {
       Changed = !S.empty() || !B.empty();
       S.clear();
@@ -497,24 +498,30 @@ bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small,
     }
 
     if (none_of(S, isVector) || none_of(B, isVector)) {
-      Changed |= berase_if(S, isVector) |
-                 berase_if(B, isVector);
+      Changed |= berase_if(S, isVector);
+      Changed |= berase_if(B, isVector);
     }
   }
 
   auto LT = [](MVT A, MVT B) -> bool {
-    return A.getScalarSizeInBits() < B.getScalarSizeInBits() ||
-           (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
-            A.getSizeInBits() < B.getSizeInBits());
+    // Always treat non-scalable MVTs as smaller than scalable MVTs for the
+    // purposes of ordering.
+    auto ASize = std::make_tuple(A.isScalableVector(), A.getScalarSizeInBits(),
+                                 A.getSizeInBits());
+    auto BSize = std::make_tuple(B.isScalableVector(), B.getScalarSizeInBits(),
+                                 B.getSizeInBits());
+    return ASize < BSize;
   };
-  auto LE = [&LT](MVT A, MVT B) -> bool {
+  auto SameKindLE = [](MVT A, MVT B) -> bool {
     // This function is used when removing elements: when a vector is compared
-    // to a non-vector, it should return false (to avoid removal).
-    if (A.isVector() != B.isVector())
+    // to a non-vector or a scalable vector to any non-scalable MVT, it should
+    // return false (to avoid removal).
+    if (std::make_tuple(A.isVector(), A.isScalableVector()) !=
+        std::make_tuple(B.isVector(), B.isScalableVector()))
       return false;
 
-    return LT(A, B) || (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
-                        A.getSizeInBits() == B.getSizeInBits());
+    return std::make_tuple(A.getScalarSizeInBits(), A.getSizeInBits()) <=
+           std::make_tuple(B.getScalarSizeInBits(), B.getSizeInBits());
   };
 
   for (unsigned M : Modes) {
@@ -524,25 +531,29 @@ bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small,
     // smaller-or-equal than MinS.
     auto MinS = min_if(S.begin(), S.end(), isScalar, LT);
     if (MinS != S.end())
-      Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinS));
+      Changed |= berase_if(B, std::bind(SameKindLE,
+                                        std::placeholders::_1, *MinS));
 
     // MaxS = max scalar in Big, remove all scalars from Small that are
     // larger than MaxS.
     auto MaxS = max_if(B.begin(), B.end(), isScalar, LT);
     if (MaxS != B.end())
-      Changed |= berase_if(S, std::bind(LE, *MaxS, std::placeholders::_1));
+      Changed |= berase_if(S, std::bind(SameKindLE,
+                                        *MaxS, std::placeholders::_1));
 
     // MinV = min vector in Small, remove all vectors from Big that are
     // smaller-or-equal than MinV.
     auto MinV = min_if(S.begin(), S.end(), isVector, LT);
     if (MinV != S.end())
-      Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinV));
+      Changed |= berase_if(B, std::bind(SameKindLE,
+                                        std::placeholders::_1, *MinV));
 
     // MaxV = max vector in Big, remove all vectors from Small that are
     // larger than MaxV.
     auto MaxV = max_if(B.begin(), B.end(), isVector, LT);
     if (MaxV != B.end())
-      Changed |= berase_if(S, std::bind(LE, *MaxV, std::placeholders::_1));
+      Changed |= berase_if(S, std::bind(SameKindLE,
+                                        *MaxV, std::placeholders::_1));
   }
 
   return Changed;
@@ -625,7 +636,7 @@ bool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
   /// Return true if S has no element (vector type) that T is a sub-vector of,
   /// i.e. has the same element type as T and more elements.
   auto NoSubV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {
-    for (const auto &I : S)
+    for (auto I : S)
       if (IsSubVec(T, I))
         return false;
     return true;
@@ -634,7 +645,7 @@ bool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
   /// Return true if S has no element (vector type) that T is a super-vector
   /// of, i.e. has the same element type as T and fewer elements.
   auto NoSupV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {
-    for (const auto &I : S)
+    for (auto I : S)
       if (IsSubVec(I, T))
         return false;
     return true;
@@ -1304,13 +1315,29 @@ std::string TreePredicateFn::getCodeToRunOnSDNode() const {
 
   // Handle arbitrary node predicates.
   assert(hasPredCode() && "Don't have any predicate code!");
+
+  // If this is using PatFrags, there are multiple trees to search. They should
+  // all have the same class.  FIXME: Is there a way to find a common
+  // superclass?
   StringRef ClassName;
-  if (PatFragRec->getOnlyTree()->isLeaf())
-    ClassName = "SDNode";
-  else {
-    Record *Op = PatFragRec->getOnlyTree()->getOperator();
-    ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName();
+  for (const auto &Tree : PatFragRec->getTrees()) {
+    StringRef TreeClassName;
+    if (Tree->isLeaf())
+      TreeClassName = "SDNode";
+    else {
+      Record *Op = Tree->getOperator();
+      const SDNodeInfo &Info = PatFragRec->getDAGPatterns().getSDNodeInfo(Op);
+      TreeClassName = Info.getSDClassName();
+    }
+
+    if (ClassName.empty())
+      ClassName = TreeClassName;
+    else if (ClassName != TreeClassName) {
+      PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
+                      "PatFrags trees do not have consistent class");
+    }
   }
+
   std::string Result;
   if (ClassName == "SDNode")
     Result = "    SDNode *N = Node;\n";
@@ -3017,8 +3044,7 @@ CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R,
     : Records(R), Target(R), LegalVTS(Target.getLegalValueTypes()),
       PatternRewriter(PatternRewriter) {
 
-  Intrinsics = CodeGenIntrinsicTable(Records, false);
-  TgtIntrinsics = CodeGenIntrinsicTable(Records, true);
+  Intrinsics = CodeGenIntrinsicTable(Records);
   ParseNodeInfo();
   ParseNodeTransforms();
   ParseComplexPatterns();
diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.h b/llvm/utils/TableGen/CodeGenDAGPatterns.h
index 80fc932a7a502..2c081b670609d 100644
--- a/llvm/utils/TableGen/CodeGenDAGPatterns.h
+++ b/llvm/utils/TableGen/CodeGenDAGPatterns.h
@@ -194,6 +194,7 @@ struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
 
   TypeSetByHwMode() = default;
   TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
+  TypeSetByHwMode &operator=(const TypeSetByHwMode &) = default;
   TypeSetByHwMode(MVT::SimpleValueType VT)
     : TypeSetByHwMode(ValueTypeByHwMode(VT)) {}
   TypeSetByHwMode(ValueTypeByHwMode VT)
@@ -1144,7 +1145,6 @@ class CodeGenDAGPatterns {
   RecordKeeper &Records;
   CodeGenTarget Target;
   CodeGenIntrinsicTable Intrinsics;
-  CodeGenIntrinsicTable TgtIntrinsics;
 
   std::map<Record*, SDNodeInfo, LessRecordByID> SDNodes;
   std::map<Record*, std::pair<Record*, std::string>, LessRecordByID>
@@ -1195,12 +1195,6 @@ public:
     return F->second;
   }
 
-  typedef std::map<Record*, NodeXForm, LessRecordByID>::const_iterator
-          nx_iterator;
-  nx_iterator nx_begin() const { return SDNodeXForms.begin(); }
-  nx_iterator nx_end() const { return SDNodeXForms.end(); }
-
-
   const ComplexPattern &getComplexPattern(Record *R) const {
     auto F = ComplexPatterns.find(R);
     assert(F != ComplexPatterns.end() && "Unknown addressing mode!");
@@ -1210,24 +1204,18 @@ public:
   const CodeGenIntrinsic &getIntrinsic(Record *R) const {
     for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
       if (Intrinsics[i].TheDef == R) return Intrinsics[i];
-    for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
-      if (TgtIntrinsics[i].TheDef == R) return TgtIntrinsics[i];
     llvm_unreachable("Unknown intrinsic!");
   }
 
   const CodeGenIntrinsic &getIntrinsicInfo(unsigned IID) const {
     if (IID-1 < Intrinsics.size())
       return Intrinsics[IID-1];
-    if (IID-Intrinsics.size()-1 < TgtIntrinsics.size())
-      return TgtIntrinsics[IID-Intrinsics.size()-1];
     llvm_unreachable("Bad intrinsic ID!");
   }
 
   unsigned getIntrinsicID(Record *R) const {
     for (unsigned i = 0, e = Intrinsics.size(); i != e; ++i)
       if (Intrinsics[i].TheDef == R) return i;
-    for (unsigned i = 0, e = TgtIntrinsics.size(); i != e; ++i)
-      if (TgtIntrinsics[i].TheDef == R) return i + Intrinsics.size();
     llvm_unreachable("Unknown intrinsic!");
   }
 
@@ -1284,8 +1272,6 @@ public:
     return intrinsic_wo_chain_sdnode;
   }
 
-  bool hasTargetIntrinsics() { return !TgtIntrinsics.empty(); }
-
   unsigned allocateScope() { return ++NumScopes; }
 
   bool operandHasDefault(Record *Op) const {
diff --git a/llvm/utils/TableGen/CodeGenInstruction.cpp b/llvm/utils/TableGen/CodeGenInstruction.cpp
index fde946d065891..6bb4dbb511b65 100644
--- a/llvm/utils/TableGen/CodeGenInstruction.cpp
+++ b/llvm/utils/TableGen/CodeGenInstruction.cpp
@@ -396,6 +396,7 @@ CodeGenInstruction::CodeGenInstruction(Record *R)
   hasNoSchedulingInfo = R->getValueAsBit("hasNoSchedulingInfo");
   FastISelShouldIgnore = R->getValueAsBit("FastISelShouldIgnore");
   variadicOpsAreDefs = R->getValueAsBit("variadicOpsAreDefs");
+  isAuthenticated = R->getValueAsBit("isAuthenticated");
 
   bool Unset;
   mayLoad      = R->getValueAsBitOrUnset("mayLoad", Unset);
@@ -504,16 +505,18 @@ FlattenAsmStringVariants(StringRef Cur, unsigned Variant) {
   return Res;
 }
 
-bool CodeGenInstruction::isOperandAPointer(unsigned i) const {
-  if (DagInit *ConstraintList = TheDef->getValueAsDag("InOperandList")) {
-    if (i < ConstraintList->getNumArgs()) {
-      if (DefInit *Constraint = dyn_cast<DefInit>(ConstraintList->getArg(i))) {
-        return Constraint->getDef()->isSubClassOf("TypedOperand") &&
-               Constraint->getDef()->getValueAsBit("IsPointer");
-      }
-    }
-  }
-  return false;
+bool CodeGenInstruction::isOperandImpl(unsigned i,
+                                       StringRef PropertyName) const {
+  DagInit *ConstraintList = TheDef->getValueAsDag("InOperandList");
+  if (!ConstraintList || i >= ConstraintList->getNumArgs())
+    return false;
+
+  DefInit *Constraint = dyn_cast<DefInit>(ConstraintList->getArg(i));
+  if (!Constraint)
+    return false;
+
+  return Constraint->getDef()->isSubClassOf("TypedOperand") &&
+         Constraint->getDef()->getValueAsBit(PropertyName);
 }
 
 //===----------------------------------------------------------------------===//
diff --git a/llvm/utils/TableGen/CodeGenInstruction.h b/llvm/utils/TableGen/CodeGenInstruction.h
index 2cb28425df7aa..1f08ce481a898 100644
--- a/llvm/utils/TableGen/CodeGenInstruction.h
+++ b/llvm/utils/TableGen/CodeGenInstruction.h
@@ -29,10 +29,11 @@ template <typename T> class ArrayRef;
   class CGIOperandList {
   public:
     class ConstraintInfo {
-      enum { None, EarlyClobber, Tied } Kind;
-      unsigned OtherTiedOperand;
+      enum { None, EarlyClobber, Tied } Kind = None;
+      unsigned OtherTiedOperand = 0;
+
     public:
-      ConstraintInfo() : Kind(None) {}
+      ConstraintInfo() = default;
 
       static ConstraintInfo getEarlyClobber() {
         ConstraintInfo I;
@@ -277,6 +278,7 @@ template <typename T> class ArrayRef;
     bool hasChain : 1;
     bool hasChain_Inferred : 1;
     bool variadicOpsAreDefs : 1;
+    bool isAuthenticated : 1;
 
     std::string DeprecatedReason;
     bool HasComplexDeprecationPredicate;
@@ -308,7 +310,17 @@ template <typename T> class ArrayRef;
     // This can be used on intructions that use typeN or ptypeN to identify
     // operands that should be considered as pointers even though SelectionDAG
     // didn't make a distinction between integer and pointers.
-    bool isOperandAPointer(unsigned i) const;
+    bool isOperandAPointer(unsigned i) const {
+      return isOperandImpl(i, "IsPointer");
+    }
+
+    /// Check if the operand is required to be an immediate.
+    bool isOperandImmArg(unsigned i) const {
+      return isOperandImpl(i, "IsImmediate");
+    }
+
+  private:
+    bool isOperandImpl(unsigned i, StringRef PropertyName) const;
   };
 
 
@@ -332,9 +344,9 @@ template <typename T> class ArrayRef;
     struct ResultOperand {
     private:
       std::string Name;
-      Record *R;
+      Record *R = nullptr;
+      int64_t Imm = 0;
 
-      int64_t Imm;
     public:
       enum {
         K_Record,
diff --git a/llvm/utils/TableGen/CodeGenIntrinsics.h b/llvm/utils/TableGen/CodeGenIntrinsics.h
index 83e780671b438..723bbe0cc23d8 100644
--- a/llvm/utils/TableGen/CodeGenIntrinsics.h
+++ b/llvm/utils/TableGen/CodeGenIntrinsics.h
@@ -162,6 +162,8 @@ struct CodeGenIntrinsic {
   /// Note that this requires that \p IS.ParamVTs is available.
   bool isParamAPointer(unsigned ParamIdx) const;
 
+  bool isParamImmArg(unsigned ParamIdx) const;
+
   CodeGenIntrinsic(Record *R);
 };
 
@@ -176,7 +178,7 @@ public:
   };
   std::vector<TargetSet> Targets;
 
-  explicit CodeGenIntrinsicTable(const RecordKeeper &RC, bool TargetOnly);
+  explicit CodeGenIntrinsicTable(const RecordKeeper &RC);
   CodeGenIntrinsicTable() = default;
 
   bool empty() const { return Intrinsics.empty(); }
diff --git a/llvm/utils/TableGen/CodeGenRegisters.h b/llvm/utils/TableGen/CodeGenRegisters.h
index 6d933baec2aee..a8e9e0fbccbe5 100644
--- a/llvm/utils/TableGen/CodeGenRegisters.h
+++ b/llvm/utils/TableGen/CodeGenRegisters.h
@@ -635,9 +635,11 @@ namespace llvm {
     CodeGenSubRegIndex *
       getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8>&);
 
-    const std::deque<CodeGenRegister> &getRegisters() { return Registers; }
+    const std::deque<CodeGenRegister> &getRegisters() const {
+      return Registers;
+    }
 
-    const StringMap<CodeGenRegister*> &getRegistersByName() {
+    const StringMap<CodeGenRegister *> &getRegistersByName() const {
       return RegistersByName;
     }
 
@@ -686,7 +688,7 @@ namespace llvm {
     // Native units are the singular unit of a leaf register. Register aliasing
     // is completely characterized by native units. Adopted units exist to give
     // register additional weight but don't affect aliasing.
-    bool isNativeUnit(unsigned RUID) {
+    bool isNativeUnit(unsigned RUID) const {
       return RUID < NumNativeRegUnits;
     }
 
diff --git a/llvm/utils/TableGen/CodeGenTarget.cpp b/llvm/utils/TableGen/CodeGenTarget.cpp
index fa8b842c97f99..acfb143120af1 100644
--- a/llvm/utils/TableGen/CodeGenTarget.cpp
+++ b/llvm/utils/TableGen/CodeGenTarget.cpp
@@ -260,7 +260,7 @@ Record *CodeGenTarget::getAsmParser() const {
   return LI[AsmParserNum];
 }
 
-/// getAsmParserVariant - Return the AssmblyParserVariant definition for
+/// getAsmParserVariant - Return the AssemblyParserVariant definition for
 /// this target.
 ///
 Record *CodeGenTarget::getAsmParserVariant(unsigned i) const {
@@ -272,7 +272,7 @@ Record *CodeGenTarget::getAsmParserVariant(unsigned i) const {
   return LI[i];
 }
 
-/// getAsmParserVariantCount - Return the AssmblyParserVariant definition
+/// getAsmParserVariantCount - Return the AssemblyParserVariant definition
 /// available for this target.
 ///
 unsigned CodeGenTarget::getAsmParserVariantCount() const {
@@ -574,17 +574,14 @@ ComplexPattern::ComplexPattern(Record *R) {
 // CodeGenIntrinsic Implementation
 //===----------------------------------------------------------------------===//
 
-CodeGenIntrinsicTable::CodeGenIntrinsicTable(const RecordKeeper &RC,
-                                             bool TargetOnly) {
+CodeGenIntrinsicTable::CodeGenIntrinsicTable(const RecordKeeper &RC) {
   std::vector<Record*> Defs = RC.getAllDerivedDefinitions("Intrinsic");
 
   Intrinsics.reserve(Defs.size());
 
-  for (unsigned I = 0, e = Defs.size(); I != e; ++I) {
-    bool isTarget = Defs[I]->getValueAsBit("isTarget");
-    if (isTarget == TargetOnly)
-      Intrinsics.push_back(CodeGenIntrinsic(Defs[I]));
-  }
+  for (unsigned I = 0, e = Defs.size(); I != e; ++I)
+    Intrinsics.push_back(CodeGenIntrinsic(Defs[I]));
+
   llvm::sort(Intrinsics,
              [](const CodeGenIntrinsic &LHS, const CodeGenIntrinsic &RHS) {
                return std::tie(LHS.TargetPrefix, LHS.Name) <
@@ -820,3 +817,9 @@ bool CodeGenIntrinsic::isParamAPointer(unsigned ParamIdx) const {
   MVT ParamType = MVT(IS.ParamVTs[ParamIdx]);
   return ParamType == MVT::iPTR || ParamType == MVT::iPTRAny;
 }
+
+bool CodeGenIntrinsic::isParamImmArg(unsigned ParamIdx) const {
+  std::pair<unsigned, ArgAttribute> Val = {ParamIdx, ImmArg};
+  return std::binary_search(ArgumentAttributes.begin(),
+                            ArgumentAttributes.end(), Val);
+}
diff --git a/llvm/utils/TableGen/CodeGenTarget.h b/llvm/utils/TableGen/CodeGenTarget.h
index d52ffac4ce6ce..6c89f34c50ecc 100644
--- a/llvm/utils/TableGen/CodeGenTarget.h
+++ b/llvm/utils/TableGen/CodeGenTarget.h
@@ -86,12 +86,12 @@ public:
   ///
   Record *getAsmParser() const;
 
-  /// getAsmParserVariant - Return the AssmblyParserVariant definition for
+  /// getAsmParserVariant - Return the AssemblyParserVariant definition for
   /// this target.
   ///
   Record *getAsmParserVariant(unsigned i) const;
 
-  /// getAsmParserVariantCount - Return the AssmblyParserVariant definition
+  /// getAsmParserVariantCount - Return the AssemblyParserVariant definition
   /// available for this target.
   ///
   unsigned getAsmParserVariantCount() const;
diff --git a/llvm/utils/TableGen/DAGISelMatcherGen.cpp b/llvm/utils/TableGen/DAGISelMatcherGen.cpp
index 49c09c7d195e2..6a86868a9bcdc 100644
--- a/llvm/utils/TableGen/DAGISelMatcherGen.cpp
+++ b/llvm/utils/TableGen/DAGISelMatcherGen.cpp
@@ -1047,7 +1047,6 @@ void MatcherGen::EmitResultCode() {
     }
   }
 
-  assert(Ops.size() >= NumSrcResults && "Didn't provide enough results");
   SmallVector<unsigned, 8> Results(Ops);
 
   // Apply result permutation.
diff --git a/llvm/utils/TableGen/DFAPacketizerEmitter.cpp b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
index ccb4ef1b9678b..018bda1b60906 100644
--- a/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
+++ b/llvm/utils/TableGen/DFAPacketizerEmitter.cpp
@@ -16,15 +16,16 @@
 
 #define DEBUG_TYPE "dfa-emitter"
 
+#include "CodeGenSchedule.h"
 #include "CodeGenTarget.h"
 #include "DFAEmitter.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
-#include "llvm/TableGen/Record.h"
-#include "llvm/TableGen/TableGenBackend.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenBackend.h"
 #include <cassert>
 #include <cstdint>
 #include <map>
@@ -35,216 +36,101 @@
 
 using namespace llvm;
 
-// --------------------------------------------------------------------
-// Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
-
-// DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
-// This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
-//
-// e.g. terms x resource bit combinations that fit in uint32_t:
-//      4 terms x 8  bits = 32 bits
-//      3 terms x 10 bits = 30 bits
-//      2 terms x 16 bits = 32 bits
-//
-// e.g. terms x resource bit combinations that fit in uint64_t:
-//      8 terms x 8  bits = 64 bits
-//      7 terms x 9  bits = 63 bits
-//      6 terms x 10 bits = 60 bits
-//      5 terms x 12 bits = 60 bits
-//      4 terms x 16 bits = 64 bits <--- current
-//      3 terms x 21 bits = 63 bits
-//      2 terms x 32 bits = 64 bits
-//
-#define DFA_MAX_RESTERMS        4   // The max # of AND'ed resource terms.
-#define DFA_MAX_RESOURCES       16  // The max # of resource bits in one term.
-
-typedef uint64_t                DFAInput;
-typedef int64_t                 DFAStateInput;
-#define DFA_TBLTYPE             "int64_t" // For generating DFAStateInputTable.
+// We use a uint64_t to represent a resource bitmask.
+#define DFA_MAX_RESOURCES 64
 
 namespace {
+using ResourceVector = SmallVector<uint64_t, 4>;
 
-  DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
-    return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
-  }
-
-  /// Return the DFAInput for an instruction class input vector.
-  /// This function is used in both DFAPacketizer.cpp and in
-  /// DFAPacketizerEmitter.cpp.
-  DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
-    DFAInput InsnInput = 0;
-    assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
-           "Exceeded maximum number of DFA terms");
-    for (auto U : InsnClass)
-      InsnInput = addDFAFuncUnits(InsnInput, U);
-    return InsnInput;
-  }
-
-} // end anonymous namespace
+struct ScheduleClass {
+  /// The parent itinerary index (processor model ID).
+  unsigned ItineraryID;
 
-// --------------------------------------------------------------------
+  /// Index within this itinerary of the schedule class.
+  unsigned Idx;
 
-#ifndef NDEBUG
-// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
-//
-// dbgsInsnClass - When debugging, print instruction class stages.
-//
-void dbgsInsnClass(const std::vector<unsigned> &InsnClass);
-//
-// dbgsStateInfo - When debugging, print the set of state info.
-//
-void dbgsStateInfo(const std::set<unsigned> &stateInfo);
-//
-// dbgsIndent - When debugging, indent by the specified amount.
-//
-void dbgsIndent(unsigned indent);
-#endif
+  /// The index within the uniqued set of required resources of Resources.
+  unsigned ResourcesIdx;
 
-//
-// class DFAPacketizerEmitter: class that generates and prints out the DFA
-// for resource tracking.
-//
-namespace {
+  /// Conjunctive list of resource requirements:
+  ///   {a|b, b|c} => (a OR b) AND (b or c).
+  /// Resources are unique across all itineraries.
+  ResourceVector Resources;
+};
 
+// Generates and prints out the DFA for resource tracking.
 class DFAPacketizerEmitter {
 private:
   std::string TargetName;
-  //
-  // allInsnClasses is the set of all possible resources consumed by an
-  // InstrStage.
-  //
-  std::vector<std::vector<unsigned>> allInsnClasses;
   RecordKeeper &Records;
 
+  UniqueVector<ResourceVector> UniqueResources;
+  std::vector<ScheduleClass> ScheduleClasses;
+  std::map<std::string, uint64_t> FUNameToBitsMap;
+  std::map<unsigned, uint64_t> ComboBitToBitsMap;
+
 public:
   DFAPacketizerEmitter(RecordKeeper &R);
 
-  //
-  // collectAllFuncUnits - Construct a map of function unit names to bits.
-  //
-  int collectAllFuncUnits(std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           int &maxResources,
-                           raw_ostream &OS);
-
-  //
-  // collectAllComboFuncs - Construct a map from a combo function unit bit to
-  //                        the bits of all included functional units.
-  //
-  int collectAllComboFuncs(std::vector<Record*> &ComboFuncList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                           raw_ostream &OS);
-
-  //
-  // collectOneInsnClass - Populate allInsnClasses with one instruction class.
-  //
-  int collectOneInsnClass(const std::string &ProcName,
-                           std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           Record *ItinData,
-                           raw_ostream &OS);
-
-  //
-  // collectAllInsnClasses - Populate allInsnClasses which is a set of units
-  // used in each stage.
-  //
-  int collectAllInsnClasses(const std::string &ProcName,
-                           std::vector<Record*> &ProcItinList,
-                           std::map<std::string, unsigned> &FUNameToBitsMap,
-                           std::vector<Record*> &ItinDataList,
-                           int &maxStages,
-                           raw_ostream &OS);
+  // Construct a map of function unit names to bits.
+  int collectAllFuncUnits(
+      ArrayRef<const CodeGenProcModel *> ProcModels);
+
+  // Construct a map from a combo function unit bit to the bits of all included
+  // functional units.
+  int collectAllComboFuncs(ArrayRef<Record *> ComboFuncList);
+
+  ResourceVector getResourcesForItinerary(Record *Itinerary);
+  void createScheduleClasses(unsigned ItineraryIdx, const RecVec &Itineraries);
 
   // Emit code for a subset of itineraries.
   void emitForItineraries(raw_ostream &OS,
-                          std::vector<Record *> &ProcItinList,
+                          std::vector<const CodeGenProcModel *> &ProcItinList,
                           std::string DFAName);
 
   void run(raw_ostream &OS);
 };
 } // end anonymous namespace
 
-#ifndef NDEBUG
-// To enable debugging, run llvm-tblgen with: "-debug-only dfa-emitter".
-//
-// dbgsInsnClass - When debugging, print instruction class stages.
-//
-void dbgsInsnClass(const std::vector<unsigned> &InsnClass) {
-  LLVM_DEBUG(dbgs() << "InsnClass: ");
-  for (unsigned i = 0; i < InsnClass.size(); ++i) {
-    if (i > 0) {
-      LLVM_DEBUG(dbgs() << ", ");
-    }
-    LLVM_DEBUG(dbgs() << "0x" << Twine::utohexstr(InsnClass[i]));
-  }
-  DFAInput InsnInput = getDFAInsnInput(InsnClass);
-  LLVM_DEBUG(dbgs() << " (input: 0x" << Twine::utohexstr(InsnInput) << ")");
-}
+DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R)
+    : TargetName(CodeGenTarget(R).getName()), Records(R) {}
 
-//
-// dbgsIndent - When debugging, indent by the specified amount.
-//
-void dbgsIndent(unsigned indent) {
-  for (unsigned i = 0; i < indent; ++i) {
-    LLVM_DEBUG(dbgs() << " ");
-  }
-}
-#endif // NDEBUG
-
-DFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R):
-  TargetName(CodeGenTarget(R).getName()), Records(R) {}
-
-//
-// collectAllFuncUnits - Construct a map of function unit names to bits.
-//
 int DFAPacketizerEmitter::collectAllFuncUnits(
-                            std::vector<Record*> &ProcItinList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            int &maxFUs,
-                            raw_ostream &OS) {
+    ArrayRef<const CodeGenProcModel *> ProcModels) {
   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
                        "----------------------\n");
   LLVM_DEBUG(dbgs() << "collectAllFuncUnits");
-  LLVM_DEBUG(dbgs() << " (" << ProcItinList.size() << " itineraries)\n");
+  LLVM_DEBUG(dbgs() << " (" << ProcModels.size() << " itineraries)\n");
+
+  std::set<Record *> ProcItinList;
+  for (const CodeGenProcModel *Model : ProcModels)
+    ProcItinList.insert(Model->ItinsDef);
 
   int totalFUs = 0;
   // Parse functional units for all the itineraries.
-  for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) {
-    Record *Proc = ProcItinList[i];
-    std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU");
+  for (Record *Proc : ProcItinList) {
+    std::vector<Record *> FUs = Proc->getValueAsListOfDefs("FU");
 
-    LLVM_DEBUG(dbgs() << "    FU:" << i << " (" << FUs.size() << " FUs) "
-                      << Proc->getName());
+    LLVM_DEBUG(dbgs() << "    FU:"
+                      << " (" << FUs.size() << " FUs) " << Proc->getName());
 
     // Convert macros to bits for each stage.
     unsigned numFUs = FUs.size();
     for (unsigned j = 0; j < numFUs; ++j) {
-      assert ((j < DFA_MAX_RESOURCES) &&
-                      "Exceeded maximum number of representable resources");
-      unsigned FuncResources = (unsigned) (1U << j);
+      assert((j < DFA_MAX_RESOURCES) &&
+             "Exceeded maximum number of representable resources");
+      uint64_t FuncResources = 1ULL << j;
       FUNameToBitsMap[FUs[j]->getName()] = FuncResources;
       LLVM_DEBUG(dbgs() << " " << FUs[j]->getName() << ":0x"
                         << Twine::utohexstr(FuncResources));
     }
-    if (((int) numFUs) > maxFUs) {
-      maxFUs = numFUs;
-    }
     totalFUs += numFUs;
     LLVM_DEBUG(dbgs() << "\n");
   }
   return totalFUs;
 }
 
-//
-// collectAllComboFuncs - Construct a map from a combo function unit bit to
-//                        the bits of all included functional units.
-//
-int DFAPacketizerEmitter::collectAllComboFuncs(
-                            std::vector<Record*> &ComboFuncList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            std::map<unsigned, unsigned> &ComboBitToBitsMap,
-                            raw_ostream &OS) {
+int DFAPacketizerEmitter::collectAllComboFuncs(ArrayRef<Record *> ComboFuncList) {
   LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
                        "----------------------\n");
   LLVM_DEBUG(dbgs() << "collectAllComboFuncs");
@@ -253,27 +139,27 @@ int DFAPacketizerEmitter::collectAllComboFuncs(
   int numCombos = 0;
   for (unsigned i = 0, N = ComboFuncList.size(); i < N; ++i) {
     Record *Func = ComboFuncList[i];
-    std::vector<Record*> FUs = Func->getValueAsListOfDefs("CFD");
+    std::vector<Record *> FUs = Func->getValueAsListOfDefs("CFD");
 
     LLVM_DEBUG(dbgs() << "    CFD:" << i << " (" << FUs.size() << " combo FUs) "
                       << Func->getName() << "\n");
 
     // Convert macros to bits for each stage.
     for (unsigned j = 0, N = FUs.size(); j < N; ++j) {
-      assert ((j < DFA_MAX_RESOURCES) &&
-                      "Exceeded maximum number of DFA resources");
+      assert((j < DFA_MAX_RESOURCES) &&
+             "Exceeded maximum number of DFA resources");
       Record *FuncData = FUs[j];
       Record *ComboFunc = FuncData->getValueAsDef("TheComboFunc");
-      const std::vector<Record*> &FuncList =
-                                   FuncData->getValueAsListOfDefs("FuncList");
+      const std::vector<Record *> &FuncList =
+          FuncData->getValueAsListOfDefs("FuncList");
       const std::string &ComboFuncName = ComboFunc->getName();
-      unsigned ComboBit = FUNameToBitsMap[ComboFuncName];
-      unsigned ComboResources = ComboBit;
+      uint64_t ComboBit = FUNameToBitsMap[ComboFuncName];
+      uint64_t ComboResources = ComboBit;
       LLVM_DEBUG(dbgs() << "      combo: " << ComboFuncName << ":0x"
                         << Twine::utohexstr(ComboResources) << "\n");
       for (unsigned k = 0, M = FuncList.size(); k < M; ++k) {
         std::string FuncName = FuncList[k]->getName();
-        unsigned FuncResources = FUNameToBitsMap[FuncName];
+        uint64_t FuncResources = FUNameToBitsMap[FuncName];
         LLVM_DEBUG(dbgs() << "        " << FuncName << ":0x"
                           << Twine::utohexstr(FuncResources) << "\n");
         ComboResources |= FuncResources;
@@ -288,101 +174,33 @@ int DFAPacketizerEmitter::collectAllComboFuncs(
   return numCombos;
 }
 
-//
-// collectOneInsnClass - Populate allInsnClasses with one instruction class
-//
-int DFAPacketizerEmitter::collectOneInsnClass(const std::string &ProcName,
-                        std::vector<Record*> &ProcItinList,
-                        std::map<std::string, unsigned> &FUNameToBitsMap,
-                        Record *ItinData,
-                        raw_ostream &OS) {
-  const std::vector<Record*> &StageList =
-    ItinData->getValueAsListOfDefs("Stages");
-
-  // The number of stages.
-  unsigned NStages = StageList.size();
-
-  LLVM_DEBUG(dbgs() << "    " << ItinData->getValueAsDef("TheClass")->getName()
-                    << "\n");
-
-  std::vector<unsigned> UnitBits;
-
-  // Compute the bitwise or of each unit used in this stage.
-  for (unsigned i = 0; i < NStages; ++i) {
-    const Record *Stage = StageList[i];
-
-    // Get unit list.
-    const std::vector<Record*> &UnitList =
-      Stage->getValueAsListOfDefs("Units");
-
-    LLVM_DEBUG(dbgs() << "        stage:" << i << " [" << UnitList.size()
-                      << " units]:");
-    unsigned dbglen = 26;  // cursor after stage dbgs
-
-    // Compute the bitwise or of each unit used in this stage.
-    unsigned UnitBitValue = 0;
-    for (unsigned j = 0, M = UnitList.size(); j < M; ++j) {
-      // Conduct bitwise or.
-      std::string UnitName = UnitList[j]->getName();
-      LLVM_DEBUG(dbgs() << " " << j << ":" << UnitName);
-      dbglen += 3 + UnitName.length();
-      assert(FUNameToBitsMap.count(UnitName));
-      UnitBitValue |= FUNameToBitsMap[UnitName];
-    }
-
-    if (UnitBitValue != 0)
-      UnitBits.push_back(UnitBitValue);
-
-    while (dbglen <= 64) {   // line up bits dbgs
-        dbglen += 8;
-        LLVM_DEBUG(dbgs() << "\t");
+ResourceVector
+DFAPacketizerEmitter::getResourcesForItinerary(Record *Itinerary) {
+  ResourceVector Resources;
+  assert(Itinerary);
+  for (Record *StageDef : Itinerary->getValueAsListOfDefs("Stages")) {
+    uint64_t StageResources = 0;
+    for (Record *Unit : StageDef->getValueAsListOfDefs("Units")) {
+      StageResources |= FUNameToBitsMap[Unit->getName()];
     }
-    LLVM_DEBUG(dbgs() << " (bits: 0x" << Twine::utohexstr(UnitBitValue)
-                      << ")\n");
+    if (StageResources != 0)
+      Resources.push_back(StageResources);
   }
-
-  if (!UnitBits.empty())
-    allInsnClasses.push_back(UnitBits);
-
-  LLVM_DEBUG({
-    dbgs() << "        ";
-    dbgsInsnClass(UnitBits);
-    dbgs() << "\n";
-  });
-
-  return NStages;
+  return Resources;
 }
 
-//
-// collectAllInsnClasses - Populate allInsnClasses which is a set of units
-// used in each stage.
-//
-int DFAPacketizerEmitter::collectAllInsnClasses(const std::string &ProcName,
-                            std::vector<Record*> &ProcItinList,
-                            std::map<std::string, unsigned> &FUNameToBitsMap,
-                            std::vector<Record*> &ItinDataList,
-                            int &maxStages,
-                            raw_ostream &OS) {
-  // Collect all instruction classes.
-  unsigned M = ItinDataList.size();
-
-  int numInsnClasses = 0;
-  LLVM_DEBUG(dbgs() << "-------------------------------------------------------"
-                       "----------------------\n"
-                    << "collectAllInsnClasses " << ProcName << " (" << M
-                    << " classes)\n");
-
-  // Collect stages for each instruction class for all itinerary data
-  for (unsigned j = 0; j < M; j++) {
-    Record *ItinData = ItinDataList[j];
-    int NStages = collectOneInsnClass(ProcName, ProcItinList,
-                                      FUNameToBitsMap, ItinData, OS);
-    if (NStages > maxStages) {
-      maxStages = NStages;
+void DFAPacketizerEmitter::createScheduleClasses(unsigned ItineraryIdx,
+                                                 const RecVec &Itineraries) {
+  unsigned Idx = 0;
+  for (Record *Itinerary : Itineraries) {
+    if (!Itinerary) {
+      ScheduleClasses.push_back({ItineraryIdx, Idx++, 0, ResourceVector{}});
+      continue;
     }
-    numInsnClasses++;
+    ResourceVector Resources = getResourcesForItinerary(Itinerary);
+    ScheduleClasses.push_back(
+        {ItineraryIdx, Idx++, UniqueResources.insert(Resources), Resources});
   }
-  return numInsnClasses;
 }
 
 //
@@ -393,19 +211,17 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
      << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n";
   OS << "namespace llvm {\n";
 
-  OS << "\n// Input format:\n";
-  OS << "#define DFA_MAX_RESTERMS        " << DFA_MAX_RESTERMS
-     << "\t// maximum AND'ed resource terms\n";
-  OS << "#define DFA_MAX_RESOURCES       " << DFA_MAX_RESOURCES
-     << "\t// maximum resource bits in one term\n";
-
-  // Collect processor iteraries.
-  std::vector<Record*> ProcItinList =
-    Records.getAllDerivedDefinitions("ProcessorItineraries");
+  CodeGenTarget CGT(Records);
+  CodeGenSchedModels CGS(Records, CGT);
 
-  std::unordered_map<std::string, std::vector<Record*>> ItinsByNamespace;
-  for (Record *R : ProcItinList)
-    ItinsByNamespace[R->getValueAsString("PacketizerNamespace")].push_back(R);
+  std::unordered_map<std::string, std::vector<const CodeGenProcModel *>>
+      ItinsByNamespace;
+  for (const CodeGenProcModel &ProcModel : CGS.procModels()) {
+    if (ProcModel.hasItineraries()) {
+      auto NS = ProcModel.ItinsDef->getValueAsString("PacketizerNamespace");
+      ItinsByNamespace[NS].push_back(&ProcModel);
+    }
+  }
 
   for (auto &KV : ItinsByNamespace)
     emitForItineraries(OS, KV.second, KV.first);
@@ -413,80 +229,68 @@ void DFAPacketizerEmitter::run(raw_ostream &OS) {
 }
 
 void DFAPacketizerEmitter::emitForItineraries(
-    raw_ostream &OS, std::vector<Record *> &ProcItinList,
+    raw_ostream &OS, std::vector<const CodeGenProcModel *> &ProcModels,
     std::string DFAName) {
-  //
-  // Collect the Functional units.
-  //
-  std::map<std::string, unsigned> FUNameToBitsMap;
-  int maxResources = 0;
-  collectAllFuncUnits(ProcItinList,
-                              FUNameToBitsMap, maxResources, OS);
-
-  //
-  // Collect the Combo Functional units.
-  //
-  std::map<unsigned, unsigned> ComboBitToBitsMap;
-  std::vector<Record*> ComboFuncList =
-    Records.getAllDerivedDefinitions("ComboFuncUnits");
-  collectAllComboFuncs(ComboFuncList, FUNameToBitsMap, ComboBitToBitsMap, OS);
-
-  //
-  // Collect the itineraries.
-  //
-  int maxStages = 0;
-  int numInsnClasses = 0;
-  for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) {
-    Record *Proc = ProcItinList[i];
-
-    // Get processor itinerary name.
-    const std::string &ProcName = Proc->getName();
-
-    // Skip default.
-    if (ProcName == "NoItineraries")
-      continue;
-
-    // Sanity check for at least one instruction itinerary class.
-    unsigned NItinClasses =
-      Records.getAllDerivedDefinitions("InstrItinClass").size();
-    if (NItinClasses == 0)
-      return;
+  OS << "} // end namespace llvm\n\n";
+  OS << "namespace {\n";
+  collectAllFuncUnits(ProcModels);
+  collectAllComboFuncs(Records.getAllDerivedDefinitions("ComboFuncUnits"));
 
-    // Get itinerary data list.
-    std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID");
+  // Collect the itineraries.
+  DenseMap<const CodeGenProcModel *, unsigned> ProcModelStartIdx;
+  for (const CodeGenProcModel *Model : ProcModels) {
+    assert(Model->hasItineraries());
+    ProcModelStartIdx[Model] = ScheduleClasses.size();
+    createScheduleClasses(Model->Index, Model->ItinDefList);
+  }
 
-    // Collect all instruction classes
-    numInsnClasses += collectAllInsnClasses(ProcName, ProcItinList,
-                          FUNameToBitsMap, ItinDataList, maxStages, OS);
+  // Output the mapping from ScheduleClass to ResourcesIdx.
+  unsigned Idx = 0;
+  OS << "unsigned " << TargetName << DFAName << "ResourceIndices[] = {";
+  for (const ScheduleClass &SC : ScheduleClasses) {
+    if (Idx++ % 32 == 0)
+      OS << "\n  ";
+    OS << SC.ResourcesIdx << ", ";
+  }
+  OS << "\n};\n\n";
+
+  // And the mapping from Itinerary index into the previous table.
+  OS << "unsigned " << TargetName << DFAName
+     << "ProcResourceIndexStart[] = {\n";
+  OS << "  0, // NoSchedModel\n";
+  for (const CodeGenProcModel *Model : ProcModels) {
+    OS << "  " << ProcModelStartIdx[Model] << ", // " << Model->ModelName
+       << "\n";
   }
+  OS << ScheduleClasses.size() << "\n};\n\n";
 
   // The type of a state in the nondeterministic automaton we're defining.
-  using NfaStateTy = unsigned;
+  using NfaStateTy = uint64_t;
 
   // Given a resource state, return all resource states by applying
   // InsnClass.
-  auto applyInsnClass = [&](ArrayRef<unsigned> InsnClass,
-                            NfaStateTy State) -> std::deque<unsigned> {
-    std::deque<unsigned> V(1, State);
+  auto applyInsnClass = [&](const ResourceVector &InsnClass,
+                            NfaStateTy State) -> std::deque<NfaStateTy> {
+    std::deque<NfaStateTy> V(1, State);
     // Apply every stage in the class individually.
-    for (unsigned Stage : InsnClass) {
+    for (NfaStateTy Stage : InsnClass) {
       // Apply this stage to every existing member of V in turn.
       size_t Sz = V.size();
       for (unsigned I = 0; I < Sz; ++I) {
-        unsigned S = V.front();
+        NfaStateTy S = V.front();
         V.pop_front();
 
         // For this stage, state combination, try all possible resources.
         for (unsigned J = 0; J < DFA_MAX_RESOURCES; ++J) {
-          unsigned ResourceMask = 1U << J;
+          NfaStateTy ResourceMask = 1ULL << J;
           if ((ResourceMask & Stage) == 0)
             // This resource isn't required by this stage.
             continue;
-          unsigned Combo = ComboBitToBitsMap[ResourceMask];
+          NfaStateTy Combo = ComboBitToBitsMap[ResourceMask];
           if (Combo && ((~S & Combo) != Combo))
             // This combo units bits are not available.
             continue;
-          unsigned ResultingResourceState = S | ResourceMask | Combo;
+          NfaStateTy ResultingResourceState = S | ResourceMask | Combo;
           if (ResultingResourceState == S)
             continue;
           V.push_back(ResultingResourceState);
@@ -499,9 +303,9 @@ void DFAPacketizerEmitter::emitForItineraries(
   // Given a resource state, return a quick (conservative) guess as to whether
   // InsnClass can be applied. This is a filter for the more heavyweight
   // applyInsnClass.
-  auto canApplyInsnClass = [](ArrayRef<unsigned> InsnClass,
+  auto canApplyInsnClass = [](const ResourceVector &InsnClass,
                               NfaStateTy State) -> bool {
-    for (unsigned Resources : InsnClass) {
+    for (NfaStateTy Resources : InsnClass) {
       if ((State | Resources) == State)
         return false;
     }
@@ -515,20 +319,18 @@ void DFAPacketizerEmitter::emitForItineraries(
   while (!Worklist.empty()) {
     NfaStateTy State = Worklist.front();
     Worklist.pop_front();
-    for (unsigned i = 0; i < allInsnClasses.size(); i++) {
-      const std::vector<unsigned> &InsnClass = allInsnClasses[i];
-      if (!canApplyInsnClass(InsnClass, State))
+    for (const ResourceVector &Resources : UniqueResources) {
+      if (!canApplyInsnClass(Resources, State))
         continue;
-      for (unsigned NewState : applyInsnClass(InsnClass, State)) {
+      unsigned ResourcesID = UniqueResources.idFor(Resources);
+      for (uint64_t NewState : applyInsnClass(Resources, State)) {
         if (SeenStates.emplace(NewState).second)
           Worklist.emplace_back(NewState);
-        Emitter.addTransition(State, NewState, getDFAInsnInput(InsnClass));
+        Emitter.addTransition(State, NewState, ResourcesID);
       }
     }
   }
 
-  OS << "} // end namespace llvm\n\n";
-  OS << "namespace {\n";
   std::string TargetAndDFAName = TargetName + DFAName;
   Emitter.emit(TargetAndDFAName, OS);
   OS << "} // end anonymous namespace\n\n";
@@ -541,7 +343,13 @@ void DFAPacketizerEmitter::emitForItineraries(
      << "  static Automaton<uint64_t> A(ArrayRef<" << TargetAndDFAName
      << "Transition>(" << TargetAndDFAName << "Transitions), "
      << TargetAndDFAName << "TransitionInfo);\n"
-     << "  return new DFAPacketizer(IID, A);\n"
+     << "  unsigned ProcResIdxStart = " << TargetAndDFAName
+     << "ProcResourceIndexStart[IID->SchedModel.ProcID];\n"
+     << "  unsigned ProcResIdxNum = " << TargetAndDFAName
+     << "ProcResourceIndexStart[IID->SchedModel.ProcID + 1] - "
+        "ProcResIdxStart;\n"
+     << "  return new DFAPacketizer(IID, A, {&" << TargetAndDFAName
+     << "ResourceIndices[ProcResIdxStart], ProcResIdxNum});\n"
      << "\n}\n\n";
 }
 
diff --git a/llvm/utils/TableGen/FixedLenDecoderEmitter.cpp b/llvm/utils/TableGen/FixedLenDecoderEmitter.cpp
index ac69b431607df..21ec5897ea505 100644
--- a/llvm/utils/TableGen/FixedLenDecoderEmitter.cpp
+++ b/llvm/utils/TableGen/FixedLenDecoderEmitter.cpp
@@ -1058,10 +1058,9 @@ unsigned FilterChooser::getIslands(std::vector<unsigned> &StartBits,
   // 1: Water (the bit value does not affect decoding)
   // 2: Island (well-known bit value needed for decoding)
   int State = 0;
-  int64_t Val = -1;
 
   for (unsigned i = 0; i < BitWidth; ++i) {
-    Val = Value(Insn[i]);
+    int64_t Val = Value(Insn[i]);
     bool Filtered = PositionFiltered(i);
     switch (State) {
     default: llvm_unreachable("Unreachable code!");
diff --git a/llvm/utils/TableGen/GICombinerEmitter.cpp b/llvm/utils/TableGen/GICombinerEmitter.cpp
index 5dc4d6b07740e..34eb4edac8de5 100644
--- a/llvm/utils/TableGen/GICombinerEmitter.cpp
+++ b/llvm/utils/TableGen/GICombinerEmitter.cpp
@@ -11,8 +11,11 @@
 ///
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/StringMatcher.h"
@@ -20,6 +23,9 @@
 #include "CodeGenTarget.h"
 #include "GlobalISel/CodeExpander.h"
 #include "GlobalISel/CodeExpansions.h"
+#include "GlobalISel/GIMatchDag.h"
+#include "GlobalISel/GIMatchTree.h"
+#include <cstdint>
 
 using namespace llvm;
 
@@ -38,10 +44,63 @@ static cl::opt<bool> ShowExpansions(
     "gicombiner-show-expansions",
     cl::desc("Use C++ comments to indicate occurence of code expansion"),
     cl::cat(GICombinerEmitterCat));
+static cl::opt<bool> StopAfterParse(
+    "gicombiner-stop-after-parse",
+    cl::desc("Stop processing after parsing rules and dump state"),
+    cl::cat(GICombinerEmitterCat));
+static cl::opt<bool> StopAfterBuild(
+    "gicombiner-stop-after-build",
+    cl::desc("Stop processing after building the match tree"),
+    cl::cat(GICombinerEmitterCat));
 
 namespace {
 typedef uint64_t RuleID;
 
+// We're going to be referencing the same small strings quite a lot for operand
+// names and the like. Make their lifetime management simple with a global
+// string table.
+StringSet<> StrTab;
+
+StringRef insertStrTab(StringRef S) {
+  if (S.empty())
+    return S;
+  return StrTab.insert(S).first->first();
+}
+
+class format_partition_name {
+  const GIMatchTree &Tree;
+  unsigned Idx;
+
+public:
+  format_partition_name(const GIMatchTree &Tree, unsigned Idx)
+      : Tree(Tree), Idx(Idx) {}
+  void print(raw_ostream &OS) const {
+    Tree.getPartitioner()->emitPartitionName(OS, Idx);
+  }
+};
+raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) {
+  Fmt.print(OS);
+  return OS;
+}
+
+/// Declares data that is passed from the match stage to the apply stage.
+class MatchDataInfo {
+  /// The symbol used in the tablegen patterns
+  StringRef PatternSymbol;
+  /// The data type for the variable
+  StringRef Type;
+  /// The name of the variable as declared in the generated matcher.
+  std::string VariableName;
+
+public:
+  MatchDataInfo(StringRef PatternSymbol, StringRef Type, StringRef VariableName)
+      : PatternSymbol(PatternSymbol), Type(Type), VariableName(VariableName) {}
+
+  StringRef getPatternSymbol() const { return PatternSymbol; };
+  StringRef getType() const { return Type; };
+  StringRef getVariableName() const { return VariableName; };
+};
+
 class RootInfo {
   StringRef PatternSymbol;
 
@@ -52,12 +111,32 @@ public:
 };
 
 class CombineRule {
+public:
+
+  using const_matchdata_iterator = std::vector<MatchDataInfo>::const_iterator;
+
+  struct VarInfo {
+    const GIMatchDagInstr *N;
+    const GIMatchDagOperand *Op;
+    const DagInit *Matcher;
+
+  public:
+    VarInfo(const GIMatchDagInstr *N, const GIMatchDagOperand *Op,
+            const DagInit *Matcher)
+        : N(N), Op(Op), Matcher(Matcher) {}
+  };
+
 protected:
   /// A unique ID for this rule
   /// ID's are used for debugging and run-time disabling of rules among other
   /// things.
   RuleID ID;
 
+  /// A unique ID that can be used for anonymous objects belonging to this rule.
+  /// Used to create unique names in makeNameForAnon*() without making tests
+  /// overly fragile.
+  unsigned UID = 0;
+
   /// The record defining this rule.
   const Record &TheDef;
 
@@ -67,27 +146,135 @@ protected:
   /// from the bottom of the function to the top.
   std::vector<RootInfo> Roots;
 
+  GIMatchDag MatchDag;
+
   /// A block of arbitrary C++ to finish testing the match.
   /// FIXME: This is a temporary measure until we have actual pattern matching
   const CodeInit *MatchingFixupCode = nullptr;
+
+  /// The MatchData defined by the match stage and required by the apply stage.
+  /// This allows the plumbing of arbitrary data from C++ predicates between the
+  /// stages.
+  ///
+  /// For example, suppose you have:
+  ///   %A = <some-constant-expr>
+  ///   %0 = G_ADD %1, %A
+  /// you could define a GIMatchPredicate that walks %A, constant folds as much
+  /// as possible and returns an APInt containing the discovered constant. You
+  /// could then declare:
+  ///   def apint : GIDefMatchData<"APInt">;
+  /// add it to the rule with:
+  ///   (defs root:$root, apint:$constant)
+  /// evaluate it in the pattern with a C++ function that takes a
+  /// MachineOperand& and an APInt& with:
+  ///   (match [{MIR %root = G_ADD %0, %A }],
+  ///             (constantfold operand:$A, apint:$constant))
+  /// and finally use it in the apply stage with:
+  ///   (apply (create_operand
+  ///                [{ MachineOperand::CreateImm(${constant}.getZExtValue());
+  ///                ]}, apint:$constant),
+  ///             [{MIR %root = FOO %0, %constant }])
+  std::vector<MatchDataInfo> MatchDataDecls;
+
+  void declareMatchData(StringRef PatternSymbol, StringRef Type,
+                        StringRef VarName);
+
+  bool parseInstructionMatcher(const CodeGenTarget &Target, StringInit *ArgName,
+                               const Init &Arg,
+                               StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
+                               StringMap<std::vector<VarInfo>> &NamedEdgeUses);
+  bool parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
+                                  StringInit *ArgName, const Init &Arg);
+
 public:
-  CombineRule(const CodeGenTarget &Target, RuleID ID, const Record &R)
-      : ID(ID), TheDef(R) {}
+  CombineRule(const CodeGenTarget &Target, GIMatchDagContext &Ctx, RuleID ID,
+              const Record &R)
+      : ID(ID), TheDef(R), MatchDag(Ctx) {}
+  CombineRule(const CombineRule &) = delete;
+
   bool parseDefs();
   bool parseMatcher(const CodeGenTarget &Target);
 
   RuleID getID() const { return ID; }
+  unsigned allocUID() { return UID++; }
   StringRef getName() const { return TheDef.getName(); }
   const Record &getDef() const { return TheDef; }
   const CodeInit *getMatchingFixupCode() const { return MatchingFixupCode; }
   size_t getNumRoots() const { return Roots.size(); }
 
+  GIMatchDag &getMatchDag() { return MatchDag; }
+  const GIMatchDag &getMatchDag() const { return MatchDag; }
+
   using const_root_iterator = std::vector<RootInfo>::const_iterator;
   const_root_iterator roots_begin() const { return Roots.begin(); }
   const_root_iterator roots_end() const { return Roots.end(); }
   iterator_range<const_root_iterator> roots() const {
     return llvm::make_range(Roots.begin(), Roots.end());
   }
+
+  iterator_range<const_matchdata_iterator> matchdata_decls() const {
+    return make_range(MatchDataDecls.begin(), MatchDataDecls.end());
+  }
+
+  /// Export expansions for this rule
+  void declareExpansions(CodeExpansions &Expansions) const {
+    for (const auto &I : matchdata_decls())
+      Expansions.declare(I.getPatternSymbol(), I.getVariableName());
+  }
+
+  /// The matcher will begin from the roots and will perform the match by
+  /// traversing the edges to cover the whole DAG. This function reverses DAG
+  /// edges such that everything is reachable from a root. This is part of the
+  /// preparation work for flattening the DAG into a tree.
+  void reorientToRoots() {
+    SmallSet<const GIMatchDagInstr *, 5> Roots;
+    SmallSet<const GIMatchDagInstr *, 5> Visited;
+    SmallSet<GIMatchDagEdge *, 20> EdgesRemaining;
+
+    for (auto &I : MatchDag.roots()) {
+      Roots.insert(I);
+      Visited.insert(I);
+    }
+    for (auto &I : MatchDag.edges())
+      EdgesRemaining.insert(I);
+
+    bool Progressed = false;
+    SmallSet<GIMatchDagEdge *, 20> EdgesToRemove;
+    while (!EdgesRemaining.empty()) {
+      for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
+           EI != EE; ++EI) {
+        if (Visited.count((*EI)->getFromMI())) {
+          if (Roots.count((*EI)->getToMI()))
+            PrintError(TheDef.getLoc(), "One or more roots are unnecessary");
+          Visited.insert((*EI)->getToMI());
+          EdgesToRemove.insert(*EI);
+          Progressed = true;
+        }
+      }
+      for (GIMatchDagEdge *ToRemove : EdgesToRemove)
+        EdgesRemaining.erase(ToRemove);
+      EdgesToRemove.clear();
+
+      for (auto EI = EdgesRemaining.begin(), EE = EdgesRemaining.end();
+           EI != EE; ++EI) {
+        if (Visited.count((*EI)->getToMI())) {
+          (*EI)->reverse();
+          Visited.insert((*EI)->getToMI());
+          EdgesToRemove.insert(*EI);
+          Progressed = true;
+        }
+        for (GIMatchDagEdge *ToRemove : EdgesToRemove)
+          EdgesRemaining.erase(ToRemove);
+        EdgesToRemove.clear();
+      }
+
+      if (!Progressed) {
+        LLVM_DEBUG(dbgs() << "No progress\n");
+        return;
+      }
+      Progressed = false;
+    }
+  }
 };
 
 /// A convenience function to check that an Init refers to a specific def. This
@@ -111,6 +298,53 @@ static Record *getDefOfSubClass(const Init &N, StringRef Cls) {
   return nullptr;
 }
 
+/// A convenience function to check that an Init refers to a dag whose operator
+/// is a specific def and coerce it to a dag if it is. This is primarily useful
+/// for testing for subclasses of GIMatchKind and similar in DagInit's since
+/// DagInit's support any type inside them.
+static const DagInit *getDagWithSpecificOperator(const Init &N,
+                                                 StringRef Name) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->getName() == Name)
+          return I;
+  return nullptr;
+}
+
+/// A convenience function to check that an Init refers to a dag whose operator
+/// is a def that is a subclass of the given class and coerce it to a dag if it
+/// is. This is primarily useful for testing for subclasses of GIMatchKind and
+/// similar in DagInit's since DagInit's support any type inside them.
+static const DagInit *getDagWithOperatorOfSubClass(const Init &N,
+                                                   StringRef Cls) {
+  if (const DagInit *I = dyn_cast<DagInit>(&N))
+    if (I->getNumArgs() > 0)
+      if (const DefInit *OpI = dyn_cast<DefInit>(I->getOperator()))
+        if (OpI->getDef()->isSubClassOf(Cls))
+          return I;
+  return nullptr;
+}
+
+StringRef makeNameForAnonInstr(CombineRule &Rule) {
+  return insertStrTab(to_string(
+      format("__anon%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
+}
+
+StringRef makeDebugName(CombineRule &Rule, StringRef Name) {
+  return insertStrTab(Name.empty() ? makeNameForAnonInstr(Rule) : StringRef(Name));
+}
+
+StringRef makeNameForAnonPredicate(CombineRule &Rule) {
+  return insertStrTab(to_string(
+      format("__anonpred%" PRIu64 "_%u", Rule.getID(), Rule.allocUID())));
+}
+
+void CombineRule::declareMatchData(StringRef PatternSymbol, StringRef Type,
+                                   StringRef VarName) {
+  MatchDataDecls.emplace_back(PatternSymbol, Type, VarName);
+}
+
 bool CombineRule::parseDefs() {
   NamedRegionTimer T("parseDefs", "Time spent parsing the defs", "Rule Parsing",
                      "Time spent on rule parsing", TimeRegions);
@@ -128,6 +362,17 @@ bool CombineRule::parseDefs() {
       continue;
     }
 
+    // Subclasses of GIDefMatchData should declare that this rule needs to pass
+    // data from the match stage to the apply stage, and ensure that the
+    // generated matcher has a suitable variable for it to do so.
+    if (Record *MatchDataRec =
+            getDefOfSubClass(*Defs->getArg(I), "GIDefMatchData")) {
+      declareMatchData(Defs->getArgNameStr(I),
+                       MatchDataRec->getValueAsString("Type"),
+                       llvm::to_string(llvm::format("MatchData%" PRIu64, ID)));
+      continue;
+    }
+
     // Otherwise emit an appropriate error message.
     if (getDefOfSubClass(*Defs->getArg(I), "GIDefKind"))
       PrintError(TheDef.getLoc(),
@@ -149,9 +394,104 @@ bool CombineRule::parseDefs() {
   return true;
 }
 
+// Parse an (Instruction $a:Arg1, $b:Arg2, ...) matcher. Edges are formed
+// between matching operand names between different matchers.
+bool CombineRule::parseInstructionMatcher(
+    const CodeGenTarget &Target, StringInit *ArgName, const Init &Arg,
+    StringMap<std::vector<VarInfo>> &NamedEdgeDefs,
+    StringMap<std::vector<VarInfo>> &NamedEdgeUses) {
+  if (const DagInit *Matcher =
+          getDagWithOperatorOfSubClass(Arg, "Instruction")) {
+    auto &Instr =
+        Target.getInstruction(Matcher->getOperatorAsDef(TheDef.getLoc()));
+
+    StringRef Name = ArgName ? ArgName->getValue() : "";
+
+    GIMatchDagInstr *N =
+        MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
+                              MatchDag.getContext().makeOperandList(Instr));
+
+    N->setOpcodeAnnotation(&Instr);
+    const auto &P = MatchDag.addPredicateNode<GIMatchDagOpcodePredicate>(
+        makeNameForAnonPredicate(*this), Instr);
+    MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
+    unsigned OpIdx = 0;
+    for (const auto &NameInit : Matcher->getArgNames()) {
+      StringRef Name = insertStrTab(NameInit->getAsUnquotedString());
+      if (Name.empty())
+        continue;
+      N->assignNameToOperand(OpIdx, Name);
+
+      // Record the endpoints of any named edges. We'll add the cartesian
+      // product of edges later.
+      const auto &InstrOperand = N->getOperandInfo()[OpIdx];
+      if (InstrOperand.isDef()) {
+        NamedEdgeDefs.try_emplace(Name);
+        NamedEdgeDefs[Name].emplace_back(N, &InstrOperand, Matcher);
+      } else {
+        NamedEdgeUses.try_emplace(Name);
+        NamedEdgeUses[Name].emplace_back(N, &InstrOperand, Matcher);
+      }
+
+      if (InstrOperand.isDef()) {
+        if (find_if(Roots, [&](const RootInfo &X) {
+              return X.getPatternSymbol() == Name;
+            }) != Roots.end()) {
+          N->setMatchRoot();
+        }
+      }
+
+      OpIdx++;
+    }
+
+    return true;
+  }
+  return false;
+}
+
+// Parse the wip_match_opcode placeholder that's temporarily present in lieu of
+// implementing macros or choices between two matchers.
+bool CombineRule::parseWipMatchOpcodeMatcher(const CodeGenTarget &Target,
+                                             StringInit *ArgName,
+                                             const Init &Arg) {
+  if (const DagInit *Matcher =
+          getDagWithSpecificOperator(Arg, "wip_match_opcode")) {
+    StringRef Name = ArgName ? ArgName->getValue() : "";
+
+    GIMatchDagInstr *N =
+        MatchDag.addInstrNode(makeDebugName(*this, Name), insertStrTab(Name),
+                              MatchDag.getContext().makeEmptyOperandList());
+
+    if (find_if(Roots, [&](const RootInfo &X) {
+          return ArgName && X.getPatternSymbol() == ArgName->getValue();
+        }) != Roots.end()) {
+      N->setMatchRoot();
+    }
+
+    const auto &P = MatchDag.addPredicateNode<GIMatchDagOneOfOpcodesPredicate>(
+        makeNameForAnonPredicate(*this));
+    MatchDag.addPredicateDependency(N, nullptr, P, &P->getOperandInfo()["mi"]);
+    // Each argument is an opcode that will pass this predicate. Add them all to
+    // the predicate implementation
+    for (const auto &Arg : Matcher->getArgs()) {
+      Record *OpcodeDef = getDefOfSubClass(*Arg, "Instruction");
+      if (OpcodeDef) {
+        P->addOpcode(&Target.getInstruction(OpcodeDef));
+        continue;
+      }
+      PrintError(TheDef.getLoc(),
+                 "Arguments to wip_match_opcode must be instructions");
+      return false;
+    }
+    return true;
+  }
+  return false;
+}
 bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
   NamedRegionTimer T("parseMatcher", "Time spent parsing the matcher",
                      "Rule Parsing", "Time spent on rule parsing", TimeRegions);
+  StringMap<std::vector<VarInfo>> NamedEdgeDefs;
+  StringMap<std::vector<VarInfo>> NamedEdgeUses;
   DagInit *Matchers = TheDef.getValueAsDag("Match");
 
   if (Matchers->getOperatorAsDef(TheDef.getLoc())->getName() != "match") {
@@ -167,12 +507,22 @@ bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
   // The match section consists of a list of matchers and predicates. Parse each
   // one and add the equivalent GIMatchDag nodes, predicates, and edges.
   for (unsigned I = 0; I < Matchers->getNumArgs(); ++I) {
+    if (parseInstructionMatcher(Target, Matchers->getArgName(I),
+                                *Matchers->getArg(I), NamedEdgeDefs,
+                                NamedEdgeUses))
+      continue;
+
+    if (parseWipMatchOpcodeMatcher(Target, Matchers->getArgName(I),
+                                   *Matchers->getArg(I)))
+      continue;
+
 
     // Parse arbitrary C++ code we have in lieu of supporting MIR matching
     if (const CodeInit *CodeI = dyn_cast<CodeInit>(Matchers->getArg(I))) {
       assert(!MatchingFixupCode &&
              "Only one block of arbitrary code is currently permitted");
       MatchingFixupCode = CodeI;
+      MatchDag.setHasPostMatchPredicate(true);
       continue;
     }
 
@@ -182,6 +532,63 @@ bool CombineRule::parseMatcher(const CodeGenTarget &Target) {
     PrintNote("Pattern was `" + Matchers->getArg(I)->getAsString() + "'");
     return false;
   }
+
+  // Add the cartesian product of use -> def edges.
+  bool FailedToAddEdges = false;
+  for (const auto &NameAndDefs : NamedEdgeDefs) {
+    if (NameAndDefs.getValue().size() > 1) {
+      PrintError(TheDef.getLoc(),
+                 "Two different MachineInstrs cannot def the same vreg");
+      for (const auto &NameAndDefOp : NameAndDefs.getValue())
+        PrintNote("in " + to_string(*NameAndDefOp.N) + " created from " +
+                  to_string(*NameAndDefOp.Matcher) + "");
+      FailedToAddEdges = true;
+    }
+    const auto &Uses = NamedEdgeUses[NameAndDefs.getKey()];
+    for (const VarInfo &DefVar : NameAndDefs.getValue()) {
+      for (const VarInfo &UseVar : Uses) {
+        MatchDag.addEdge(insertStrTab(NameAndDefs.getKey()), UseVar.N, UseVar.Op,
+                         DefVar.N, DefVar.Op);
+      }
+    }
+  }
+  if (FailedToAddEdges)
+    return false;
+
+  // If a variable is referenced in multiple use contexts then we need a
+  // predicate to confirm they are the same operand. We can elide this if it's
+  // also referenced in a def context and we're traversing the def-use chain
+  // from the def to the uses but we can't know which direction we're going
+  // until after reorientToRoots().
+  for (const auto &NameAndUses : NamedEdgeUses) {
+    const auto &Uses = NameAndUses.getValue();
+    if (Uses.size() > 1) {
+      const auto &LeadingVar = Uses.front();
+      for (const auto &Var : ArrayRef<VarInfo>(Uses).drop_front()) {
+        // Add a predicate for each pair until we've covered the whole
+        // equivalence set. We could test the whole set in a single predicate
+        // but that means we can't test any equivalence until all the MO's are
+        // available which can lead to wasted work matching the DAG when this
+        // predicate can already be seen to have failed.
+        //
+        // We have a similar problem due to the need to wait for a particular MO
+        // before being able to test any of them. However, that is mitigated by
+        // the order in which we build the DAG. We build from the roots outwards
+        // so by using the first recorded use in all the predicates, we are
+        // making the dependency on one of the earliest visited references in
+        // the DAG. It's not guaranteed once the generated matcher is optimized
+        // (because the factoring the common portions of rules might change the
+        // visit order) but this should mean that these predicates depend on the
+        // first MO to become available.
+        const auto &P = MatchDag.addPredicateNode<GIMatchDagSameMOPredicate>(
+            makeNameForAnonPredicate(*this));
+        MatchDag.addPredicateDependency(LeadingVar.N, LeadingVar.Op, P,
+                                        &P->getOperandInfo()["mi0"]);
+        MatchDag.addPredicateDependency(Var.N, Var.Op, P,
+                                        &P->getOperandInfo()["mi1"]);
+      }
+    }
+  }
   return true;
 }
 
@@ -190,6 +597,8 @@ class GICombinerEmitter {
   const CodeGenTarget &Target;
   Record *Combiner;
   std::vector<std::unique_ptr<CombineRule>> Rules;
+  GIMatchDagContext MatchDagCtx;
+
   std::unique_ptr<CombineRule> makeCombineRule(const Record &R);
 
   void gatherRules(std::vector<std::unique_ptr<CombineRule>> &ActiveRules,
@@ -208,7 +617,9 @@ public:
   /// Emit the name matcher (guarded by #ifndef NDEBUG) used to disable rules in
   /// response to the generated cl::opt.
   void emitNameMatcher(raw_ostream &OS) const;
-  void generateCodeForRule(raw_ostream &OS, const CombineRule *Rule,
+
+  void generateDeclarationsCodeForTree(raw_ostream &OS, const GIMatchTree &Tree) const;
+  void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree,
                            StringRef Indent) const;
 };
 
@@ -246,12 +657,42 @@ void GICombinerEmitter::emitNameMatcher(raw_ostream &OS) const {
 std::unique_ptr<CombineRule>
 GICombinerEmitter::makeCombineRule(const Record &TheDef) {
   std::unique_ptr<CombineRule> Rule =
-      std::make_unique<CombineRule>(Target, NumPatternTotal, TheDef);
+      std::make_unique<CombineRule>(Target, MatchDagCtx, NumPatternTotal, TheDef);
 
   if (!Rule->parseDefs())
     return nullptr;
   if (!Rule->parseMatcher(Target))
     return nullptr;
+
+  Rule->reorientToRoots();
+
+  LLVM_DEBUG({
+    dbgs() << "Parsed rule defs/match for '" << Rule->getName() << "'\n";
+    Rule->getMatchDag().dump();
+    Rule->getMatchDag().writeDOTGraph(dbgs(), Rule->getName());
+  });
+  if (StopAfterParse)
+    return Rule;
+
+  // For now, don't support traversing from def to use. We'll come back to
+  // this later once we have the algorithm changes to support it.
+  bool EmittedDefToUseError = false;
+  for (const auto &E : Rule->getMatchDag().edges()) {
+    if (E->isDefToUse()) {
+      if (!EmittedDefToUseError) {
+        PrintError(
+            TheDef.getLoc(),
+            "Generated state machine cannot lookup uses from a def (yet)");
+        EmittedDefToUseError = true;
+      }
+      PrintNote("Node " + to_string(*E->getFromMI()));
+      PrintNote("Node " + to_string(*E->getToMI()));
+      PrintNote("Edge " + to_string(*E));
+    }
+  }
+  if (EmittedDefToUseError)
+    return nullptr;
+
   // For now, don't support multi-root rules. We'll come back to this later
   // once we have the algorithm changes to support it.
   if (Rule->getNumRoots() > 1) {
@@ -279,19 +720,43 @@ void GICombinerEmitter::gatherRules(
   }
 }
 
-void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
-                                            const CombineRule *Rule,
+void GICombinerEmitter::generateCodeForTree(raw_ostream &OS,
+                                            const GIMatchTree &Tree,
                                             StringRef Indent) const {
-  {
+  if (Tree.getPartitioner() != nullptr) {
+    Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent);
+    for (const auto &EnumChildren : enumerate(Tree.children())) {
+      OS << Indent << "if (Partition == " << EnumChildren.index() << " /* "
+         << format_partition_name(Tree, EnumChildren.index()) << " */) {\n";
+      generateCodeForTree(OS, EnumChildren.value(), (Indent + "  ").str());
+      OS << Indent << "}\n";
+    }
+    return;
+  }
+
+  bool AnyFullyTested = false;
+  for (const auto &Leaf : Tree.possible_leaves()) {
+    OS << Indent << "// Leaf name: " << Leaf.getName() << "\n";
+
+    const CombineRule *Rule = Leaf.getTargetData<CombineRule>();
     const Record &RuleDef = Rule->getDef();
 
     OS << Indent << "// Rule: " << RuleDef.getName() << "\n"
        << Indent << "if (!isRuleDisabled(" << Rule->getID() << ")) {\n";
 
     CodeExpansions Expansions;
-    for (const RootInfo &Root : Rule->roots()) {
-      Expansions.declare(Root.getPatternSymbol(), "MI");
+    for (const auto &VarBinding : Leaf.var_bindings()) {
+      if (VarBinding.isInstr())
+        Expansions.declare(VarBinding.getName(),
+                           "MIs[" + to_string(VarBinding.getInstrID()) + "]");
+      else
+        Expansions.declare(VarBinding.getName(),
+                           "MIs[" + to_string(VarBinding.getInstrID()) +
+                               "]->getOperand(" +
+                               to_string(VarBinding.getOpIdx()) + ")");
     }
+    Rule->declareExpansions(Expansions);
+
     DagInit *Applyer = RuleDef.getValueAsDag("Apply");
     if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() !=
         "apply") {
@@ -301,6 +766,29 @@ void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
 
     OS << Indent << "  if (1\n";
 
+    // Attempt to emit code for any untested predicates left over. Note that
+    // isFullyTested() will remain false even if we succeed here and therefore
+    // combine rule elision will not be performed. This is because we do not
+    // know if there's any connection between the predicates for each leaf and
+    // therefore can't tell if one makes another unreachable. Ideally, the
+    // partitioner(s) would be sufficiently complete to prevent us from having
+    // untested predicates left over.
+    for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) {
+      if (Predicate->generateCheckCode(OS, (Indent + "      ").str(),
+                                       Expansions))
+        continue;
+      PrintError(RuleDef.getLoc(),
+                 "Unable to test predicate used in rule");
+      PrintNote(SMLoc(),
+                "This indicates an incomplete implementation in tablegen");
+      Predicate->print(errs());
+      errs() << "\n";
+      OS << Indent
+         << "llvm_unreachable(\"TableGen did not emit complete code for this "
+            "path\");\n";
+      break;
+    }
+
     if (Rule->getMatchingFixupCode() &&
         !Rule->getMatchingFixupCode()->getValue().empty()) {
       // FIXME: Single-use lambda's like this are a serious compile-time
@@ -332,11 +820,64 @@ void GICombinerEmitter::generateCodeForRule(raw_ostream &OS,
     }
 
     OS << Indent << "}\n";
+
+    assert(Leaf.isFullyTraversed());
+
+    // If we didn't have any predicates left over and we're not using the
+    // trap-door we have to support arbitrary C++ code while we're migrating to
+    // the declarative style then we know that subsequent leaves are
+    // unreachable.
+    if (Leaf.isFullyTested() &&
+        (!Rule->getMatchingFixupCode() ||
+         Rule->getMatchingFixupCode()->getValue().empty())) {
+      AnyFullyTested = true;
+      OS << Indent
+         << "llvm_unreachable(\"Combine rule elision was incorrect\");\n"
+         << Indent << "return false;\n";
+    }
   }
+  if (!AnyFullyTested)
+    OS << Indent << "return false;\n";
 }
 
 void GICombinerEmitter::run(raw_ostream &OS) {
   gatherRules(Rules, Combiner->getValueAsListOfDefs("Rules"));
+  if (StopAfterParse) {
+    MatchDagCtx.print(errs());
+    PrintNote(Combiner->getLoc(),
+              "Terminating due to -gicombiner-stop-after-parse");
+    return;
+  }
+  if (ErrorsPrinted)
+    PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules");
+  LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n");
+  std::unique_ptr<GIMatchTree> Tree;
+  {
+    NamedRegionTimer T("Optimize", "Time spent optimizing the combiner",
+                       "Code Generation", "Time spent generating code",
+                       TimeRegions);
+
+    GIMatchTreeBuilder TreeBuilder(0);
+    for (const auto &Rule : Rules) {
+      bool HadARoot = false;
+      for (const auto &Root : enumerate(Rule->getMatchDag().roots())) {
+        TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(),
+                            Rule.get());
+        HadARoot = true;
+      }
+      if (!HadARoot)
+        PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root");
+    }
+
+    Tree = TreeBuilder.run();
+  }
+  if (StopAfterBuild) {
+    Tree->writeDOTGraph(outs());
+    PrintNote(Combiner->getLoc(),
+              "Terminating due to -gicombiner-stop-after-build");
+    return;
+  }
+
   NamedRegionTimer T("Emit", "Time spent emitting the combiner",
                      "Code Generation", "Time spent generating code",
                      TimeRegions);
@@ -359,7 +900,8 @@ void GICombinerEmitter::run(raw_ostream &OS) {
      << "  bool tryCombineAll(\n"
      << "    GISelChangeObserver &Observer,\n"
      << "    MachineInstr &MI,\n"
-     << "    MachineIRBuilder &B) const;\n"
+     << "    MachineIRBuilder &B,\n"
+     << "    CombinerHelper &Helper) const;\n"
      << "};\n\n";
 
   emitNameMatcher(OS);
@@ -415,15 +957,22 @@ void GICombinerEmitter::run(raw_ostream &OS) {
   OS << "bool " << getClassName() << "::tryCombineAll(\n"
      << "    GISelChangeObserver &Observer,\n"
      << "    MachineInstr &MI,\n"
-     << "    MachineIRBuilder &B) const {\n"
-     << "  CombinerHelper Helper(Observer, B);\n"
+     << "    MachineIRBuilder &B,\n"
+     << "    CombinerHelper &Helper) const {\n"
      << "  MachineBasicBlock *MBB = MI.getParent();\n"
      << "  MachineFunction *MF = MBB->getParent();\n"
      << "  MachineRegisterInfo &MRI = MF->getRegInfo();\n"
+     << "  SmallVector<MachineInstr *, 8> MIs = { &MI };\n\n"
      << "  (void)MBB; (void)MF; (void)MRI;\n\n";
 
+  OS << "  // Match data\n";
   for (const auto &Rule : Rules)
-    generateCodeForRule(OS, Rule.get(), "  ");
+    for (const auto &I : Rule->matchdata_decls())
+      OS << "  " << I.getType() << " " << I.getVariableName() << ";\n";
+  OS << "\n";
+
+  OS << "  int Partition = -1;\n";
+  generateCodeForTree(OS, *Tree, "  ");
   OS << "\n  return false;\n"
      << "}\n"
      << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n";
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp
new file mode 100644
index 0000000000000..a3a9b7d8b037a
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDag.cpp
@@ -0,0 +1,138 @@
+//===- GIMatchDag.cpp - A DAG representation of a pattern to be matched ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDag.h"
+
+#include "llvm/Support/Format.h"
+#include "llvm/TableGen/Record.h"
+#include "../CodeGenInstruction.h"
+
+using namespace llvm;
+
+void GIMatchDag::writeDOTGraph(raw_ostream &OS, StringRef ID) const {
+  const auto writePorts = [&](StringRef Prefix,
+                              const GIMatchDagOperandList &Operands) {
+    StringRef Separator = "";
+    OS << "{";
+    for (const auto &Op : enumerate(Operands)) {
+      OS << Separator << "<" << Prefix << format("%d", Op.index()) << ">"
+         << "#" << Op.index() << " $" << Op.value().getName();
+      Separator = "|";
+    }
+    OS << "}";
+  };
+
+  OS << "digraph \"" << ID << "\" {\n"
+     << "  rankdir=\"BT\"\n";
+  for (const auto &N : InstrNodes) {
+    OS << "  " << format("Node%p", &*N) << " [shape=record,label=\"{";
+    writePorts("s", N->getOperandInfo());
+    OS << "|" << N->getName();
+    if (N->getOpcodeAnnotation())
+      OS << "|" << N->getOpcodeAnnotation()->TheDef->getName();
+    if (N->isMatchRoot())
+      OS << "|Match starts here";
+    OS << "|";
+    SmallVector<std::pair<unsigned, StringRef>, 8> ToPrint;
+    for (const auto &Assignment : N->user_assigned_operand_names())
+      ToPrint.emplace_back(Assignment.first, Assignment.second);
+    llvm::sort(ToPrint.begin(), ToPrint.end());
+    StringRef Separator = "";
+    for (const auto &Assignment : ToPrint) {
+      OS << Separator << "$" << Assignment.second << "=getOperand("
+         << Assignment.first << ")";
+      Separator = ", ";
+    }
+    OS << format("|%p|", &N);
+    writePorts("d", N->getOperandInfo());
+    OS << "}\"";
+    if (N->isMatchRoot())
+      OS << ",color=red";
+    OS << "]\n";
+  }
+
+  for (const auto &E : Edges) {
+    const char *FromFmt = "Node%p:s%d:n";
+    const char *ToFmt = "Node%p:d%d:s";
+    if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
+      std::swap(FromFmt, ToFmt);
+    auto From = format(FromFmt, E->getFromMI(), E->getFromMO()->getIdx());
+    auto To = format(ToFmt, E->getToMI(), E->getToMO()->getIdx());
+    if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
+      std::swap(From, To);
+
+    OS << "  " << From << " -> " << To << " [label=\"$" << E->getName();
+    if (E->getFromMO()->isDef() == E->getToMO()->isDef())
+      OS << " INVALID EDGE!";
+    OS << "\"";
+    if (E->getFromMO()->isDef() == E->getToMO()->isDef())
+      OS << ",color=red";
+    else if (E->getFromMO()->isDef() && !E->getToMO()->isDef())
+      OS << ",dir=back,arrowtail=crow";
+    OS << "]\n";
+  }
+
+  for (const auto &N : PredicateNodes) {
+    OS << "  " << format("Pred%p", &*N) << " [shape=record,label=\"{";
+    writePorts("s", N->getOperandInfo());
+    OS << "|" << N->getName() << "|";
+    N->printDescription(OS);
+    OS << format("|%p|", &N);
+    writePorts("d", N->getOperandInfo());
+    OS << "}\",style=dotted]\n";
+  }
+
+  for (const auto &E : PredicateDependencies) {
+    const char *FromMIFmt = "Node%p:e";
+    const char *FromMOFmt = "Node%p:s%d:n";
+    const char *ToFmt = "Pred%p:d%d:s";
+    auto To = format(ToFmt, E->getPredicate(), E->getPredicateOp()->getIdx());
+    auto Style = "[style=dotted]";
+    if (E->getRequiredMO()) {
+      auto From =
+          format(FromMOFmt, E->getRequiredMI(), E->getRequiredMO()->getIdx());
+      OS << "  " << From << " -> " << To << " " << Style << "\n";
+      continue;
+    }
+    auto From = format(FromMIFmt, E->getRequiredMI());
+    OS << "  " << From << " -> " << To << " " << Style << "\n";
+  }
+
+  OS << "}\n";
+}
+
+LLVM_DUMP_METHOD void GIMatchDag::print(raw_ostream &OS) const {
+  OS << "matchdag {\n";
+  for (const auto &N : InstrNodes) {
+    OS << "  ";
+    N->print(OS);
+    OS << "\n";
+  }
+  for (const auto &E : Edges) {
+    OS << "  ";
+    E->print(OS);
+    OS << "\n";
+  }
+
+  for (const auto &P : PredicateNodes) {
+    OS << "  ";
+    P->print(OS);
+    OS << "\n";
+  }
+  for (const auto &D : PredicateDependencies) {
+    OS << "  ";
+    D->print(OS);
+    OS << "\n";
+  }
+  OS << "}\n";
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDag &G) {
+  G.print(OS);
+  return OS;
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDag.h b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h
new file mode 100644
index 0000000000000..5675805408779
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDag.h
@@ -0,0 +1,243 @@
+//===- GIMatchDag.h - Represent a DAG to be matched -----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAG_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAG_H
+
+#include "GIMatchDagEdge.h"
+#include "GIMatchDagInstr.h"
+#include "GIMatchDagOperands.h"
+#include "GIMatchDagPredicate.h"
+#include "GIMatchDagPredicateDependencyEdge.h"
+
+namespace llvm {
+class GIMatchDag;
+
+/// This class manages lifetimes for data associated with the GIMatchDag object.
+class GIMatchDagContext {
+  GIMatchDagOperandListContext OperandListCtx;
+
+public:
+  const GIMatchDagOperandList &makeEmptyOperandList() {
+    return OperandListCtx.makeEmptyOperandList();
+  }
+
+  const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I) {
+    return OperandListCtx.makeOperandList(I);
+  }
+
+  const GIMatchDagOperandList &makeMIPredicateOperandList() {
+    return OperandListCtx.makeMIPredicateOperandList();
+  }
+
+
+  const GIMatchDagOperandList &makeTwoMOPredicateOperandList() {
+    return OperandListCtx.makeTwoMOPredicateOperandList();
+  }
+
+  void print(raw_ostream &OS) const {
+    OperandListCtx.print(OS);
+  }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+class GIMatchDag {
+public:
+  using InstrNodesVec = std::vector<std::unique_ptr<GIMatchDagInstr>>;
+  using instr_node_iterator = raw_pointer_iterator<InstrNodesVec::iterator>;
+  using const_instr_node_iterator =
+      raw_pointer_iterator<InstrNodesVec::const_iterator>;
+
+  using EdgesVec = std::vector<std::unique_ptr<GIMatchDagEdge>>;
+  using edge_iterator = raw_pointer_iterator<EdgesVec::iterator>;
+  using const_edge_iterator = raw_pointer_iterator<EdgesVec::const_iterator>;
+
+  using PredicateNodesVec = std::vector<std::unique_ptr<GIMatchDagPredicate>>;
+  using predicate_iterator = raw_pointer_iterator<PredicateNodesVec::iterator>;
+  using const_predicate_iterator =
+      raw_pointer_iterator<PredicateNodesVec::const_iterator>;
+
+  using PredicateDependencyEdgesVec =
+      std::vector<std::unique_ptr<GIMatchDagPredicateDependencyEdge>>;
+  using predicate_edge_iterator =
+      raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>;
+  using const_predicate_edge_iterator =
+      raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>;
+
+protected:
+  GIMatchDagContext &Ctx;
+  InstrNodesVec InstrNodes;
+  PredicateNodesVec PredicateNodes;
+  EdgesVec Edges;
+  PredicateDependencyEdgesVec PredicateDependencies;
+  std::vector<GIMatchDagInstr *> MatchRoots;
+  // FIXME: This is a temporary measure while we still accept arbitrary code
+  //        blocks to fix up the matcher while it's being developed.
+  bool HasPostMatchPredicate = false;
+
+public:
+  GIMatchDag(GIMatchDagContext &Ctx)
+      : Ctx(Ctx), InstrNodes(), PredicateNodes(), Edges(),
+        PredicateDependencies() {}
+  GIMatchDag(const GIMatchDag &) = delete;
+
+  GIMatchDagContext &getContext() const { return Ctx; }
+  edge_iterator edges_begin() {
+    return raw_pointer_iterator<EdgesVec::iterator>(Edges.begin());
+  }
+  edge_iterator edges_end() {
+    return raw_pointer_iterator<EdgesVec::iterator>(Edges.end());
+  }
+  const_edge_iterator edges_begin() const {
+    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.begin());
+  }
+  const_edge_iterator edges_end() const {
+    return raw_pointer_iterator<EdgesVec::const_iterator>(Edges.end());
+  }
+  iterator_range<edge_iterator> edges() {
+    return make_range(edges_begin(), edges_end());
+  }
+  iterator_range<const_edge_iterator> edges() const {
+    return make_range(edges_begin(), edges_end());
+  }
+  iterator_range<std::vector<GIMatchDagInstr *>::iterator> roots() {
+    return make_range(MatchRoots.begin(), MatchRoots.end());
+  }
+  iterator_range<std::vector<GIMatchDagInstr *>::const_iterator> roots() const {
+    return make_range(MatchRoots.begin(), MatchRoots.end());
+  }
+
+  instr_node_iterator instr_nodes_begin() {
+    return raw_pointer_iterator<InstrNodesVec::iterator>(InstrNodes.begin());
+  }
+  instr_node_iterator instr_nodes_end() {
+    return raw_pointer_iterator<InstrNodesVec::iterator>(InstrNodes.end());
+  }
+  const_instr_node_iterator instr_nodes_begin() const {
+    return raw_pointer_iterator<InstrNodesVec::const_iterator>(
+        InstrNodes.begin());
+  }
+  const_instr_node_iterator instr_nodes_end() const {
+    return raw_pointer_iterator<InstrNodesVec::const_iterator>(
+        InstrNodes.end());
+  }
+  iterator_range<instr_node_iterator> instr_nodes() {
+    return make_range(instr_nodes_begin(), instr_nodes_end());
+  }
+  iterator_range<const_instr_node_iterator> instr_nodes() const {
+    return make_range(instr_nodes_begin(), instr_nodes_end());
+  }
+  predicate_edge_iterator predicate_edges_begin() {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>(
+        PredicateDependencies.begin());
+  }
+  predicate_edge_iterator predicate_edges_end() {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::iterator>(
+        PredicateDependencies.end());
+  }
+  const_predicate_edge_iterator predicate_edges_begin() const {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>(
+        PredicateDependencies.begin());
+  }
+  const_predicate_edge_iterator predicate_edges_end() const {
+    return raw_pointer_iterator<PredicateDependencyEdgesVec::const_iterator>(
+        PredicateDependencies.end());
+  }
+  iterator_range<predicate_edge_iterator> predicate_edges() {
+    return make_range(predicate_edges_begin(), predicate_edges_end());
+  }
+  iterator_range<const_predicate_edge_iterator> predicate_edges() const {
+    return make_range(predicate_edges_begin(), predicate_edges_end());
+  }
+  predicate_iterator predicates_begin() {
+    return raw_pointer_iterator<PredicateNodesVec::iterator>(
+        PredicateNodes.begin());
+  }
+  predicate_iterator predicates_end() {
+    return raw_pointer_iterator<PredicateNodesVec::iterator>(
+        PredicateNodes.end());
+  }
+  const_predicate_iterator predicates_begin() const {
+    return raw_pointer_iterator<PredicateNodesVec::const_iterator>(
+        PredicateNodes.begin());
+  }
+  const_predicate_iterator predicates_end() const {
+    return raw_pointer_iterator<PredicateNodesVec::const_iterator>(
+        PredicateNodes.end());
+  }
+  iterator_range<predicate_iterator> predicates() {
+    return make_range(predicates_begin(), predicates_end());
+  }
+  iterator_range<const_predicate_iterator> predicates() const {
+    return make_range(predicates_begin(), predicates_end());
+  }
+
+  template <class... Args> GIMatchDagInstr *addInstrNode(Args &&... args) {
+    auto Obj =
+        std::make_unique<GIMatchDagInstr>(*this, std::forward<Args>(args)...);
+    auto ObjRaw = Obj.get();
+    InstrNodes.push_back(std::move(Obj));
+    return ObjRaw;
+  }
+
+  template <class T, class... Args>
+  T *addPredicateNode(Args &&... args) {
+    auto Obj = std::make_unique<T>(getContext(), std::forward<Args>(args)...);
+    auto ObjRaw = Obj.get();
+    PredicateNodes.push_back(std::move(Obj));
+    return ObjRaw;
+  }
+
+  template <class... Args> GIMatchDagEdge *addEdge(Args &&... args) {
+    auto Obj = std::make_unique<GIMatchDagEdge>(std::forward<Args>(args)...);
+    auto ObjRaw = Obj.get();
+    Edges.push_back(std::move(Obj));
+    return ObjRaw;
+  }
+
+  template <class... Args>
+  GIMatchDagPredicateDependencyEdge *addPredicateDependency(Args &&... args) {
+    auto Obj = std::make_unique<GIMatchDagPredicateDependencyEdge>(
+        std::forward<Args>(args)...);
+    auto ObjRaw = Obj.get();
+    PredicateDependencies.push_back(std::move(Obj));
+    return ObjRaw;
+  }
+
+  size_t getInstrNodeIdx(instr_node_iterator I) {
+    return std::distance(instr_nodes_begin(), I);
+  }
+  size_t getInstrNodeIdx(const_instr_node_iterator I) const {
+    return std::distance(instr_nodes_begin(), I);
+  }
+  size_t getNumInstrNodes() const { return InstrNodes.size(); }
+  size_t getNumEdges() const { return Edges.size(); }
+  size_t getNumPredicates() const { return PredicateNodes.size(); }
+
+  void setHasPostMatchPredicate(bool V) { HasPostMatchPredicate = V; }
+  bool hasPostMatchPredicate() const { return HasPostMatchPredicate; }
+
+  void addMatchRoot(GIMatchDagInstr *N) { MatchRoots.push_back(N); }
+
+  LLVM_DUMP_METHOD void print(raw_ostream &OS) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+
+  void writeDOTGraph(raw_ostream &OS, StringRef ID) const;
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const GIMatchDag &G);
+
+} // end namespace llvm
+
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAG_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp
new file mode 100644
index 0000000000000..e59cb3aae49a9
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.cpp
@@ -0,0 +1,38 @@
+//===- GIMatchDagEdge.cpp - An edge describing a def/use lookup -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDagEdge.h"
+#include "GIMatchDagInstr.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+LLVM_DUMP_METHOD void GIMatchDagEdge::print(raw_ostream &OS) const {
+  OS << getFromMI()->getName() << "[" << getFromMO()->getName() << "] --["
+     << Name << "]--> " << getToMI()->getName() << "[" << getToMO()->getName()
+     << "]";
+}
+
+bool GIMatchDagEdge::isDefToUse() const {
+  // Def -> Def is invalid so we only need to check FromMO.
+  return FromMO->isDef();
+}
+
+void GIMatchDagEdge::reverse() {
+  std::swap(FromMI, ToMI);
+  std::swap(FromMO, ToMO);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void GIMatchDagEdge::dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagEdge &E) {
+  E.print(OS);
+  return OS;
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h
new file mode 100644
index 0000000000000..8e845ff0a51ee
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagEdge.h
@@ -0,0 +1,70 @@
+//===- GIMatchDagEdge.h - Represent a shared operand list for nodes -------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H
+
+#include "llvm/ADT/StringRef.h"
+
+namespace llvm {
+class raw_ostream;
+class GIMatchDagInstr;
+class GIMatchDagOperand;
+
+/// Represents an edge that connects two instructions together via a pair of
+/// operands. For example:
+///     %a = FOO ...
+///     %0 = BAR %a
+///     %1 = BAZ %a
+/// would have two edges for %a like so:
+///     BAR:Op#1 --[a]----> Op#0:FOO
+///                         ^
+///     BAZ:Op#1 --[a]------/
+/// Ideally, all edges in the DAG are from a use to a def as this is a many
+/// to one edge but edges from defs to uses are supported too.
+class GIMatchDagEdge {
+  /// The name of the edge. For example,
+  ///     (FOO $a, $b, $c)
+  ///     (BAR $d, $e, $a)
+  /// will create an edge named 'a' to connect FOO to BAR. Although the name
+  /// refers to the edge, the canonical value of 'a' is the operand that defines
+  /// it.
+  StringRef Name;
+  const GIMatchDagInstr *FromMI;
+  const GIMatchDagOperand *FromMO;
+  const GIMatchDagInstr *ToMI;
+  const GIMatchDagOperand *ToMO;
+
+public:
+  GIMatchDagEdge(StringRef Name, const GIMatchDagInstr *FromMI, const GIMatchDagOperand *FromMO,
+            const GIMatchDagInstr *ToMI, const GIMatchDagOperand *ToMO)
+      : Name(Name), FromMI(FromMI), FromMO(FromMO), ToMI(ToMI), ToMO(ToMO) {}
+
+  StringRef getName() const { return Name; }
+  const GIMatchDagInstr *getFromMI() const { return FromMI; }
+  const GIMatchDagOperand *getFromMO() const { return FromMO; }
+  const GIMatchDagInstr *getToMI() const { return ToMI; }
+  const GIMatchDagOperand *getToMO() const { return ToMO; }
+
+  /// Flip the direction of the edge.
+  void reverse();
+
+  /// Does this edge run from a def to (one of many) uses?
+  bool isDefToUse() const;
+
+  LLVM_DUMP_METHOD void print(raw_ostream &OS) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const;
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagEdge &E);
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGEDGE_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp
new file mode 100644
index 0000000000000..218b741be20c3
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.cpp
@@ -0,0 +1,48 @@
+//===- GIMatchDagInstr.cpp - A shared operand list for nodes --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDagInstr.h"
+#include "../CodeGenInstruction.h"
+#include "GIMatchDag.h"
+#include "llvm/TableGen/Record.h"
+
+using namespace llvm;
+
+void GIMatchDagInstr::print(raw_ostream &OS) const {
+  OS << "(";
+  if (const auto *Annotation = getOpcodeAnnotation())
+    OS << Annotation->TheDef->getName();
+  else
+    OS << "<unknown>";
+  OS << " ";
+  OperandInfo.print(OS);
+  OS << "):$" << Name;
+  if (!UserAssignedNamesForOperands.empty()) {
+    OS << " // ";
+    SmallVector<std::pair<unsigned, StringRef>, 8> ToPrint;
+    for (const auto &Assignment : UserAssignedNamesForOperands)
+      ToPrint.emplace_back(Assignment.first, Assignment.second);
+    llvm::sort(ToPrint.begin(), ToPrint.end());
+    StringRef Separator = "";
+    for (const auto &Assignment : ToPrint) {
+      OS << Separator << "$" << Assignment.second << "=getOperand("
+         << Assignment.first << ")";
+      Separator = ", ";
+    }
+  }
+}
+
+void GIMatchDagInstr::setMatchRoot() {
+  IsMatchRoot = true;
+  Dag.addMatchRoot(this);
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagInstr &N) {
+  N.print(OS);
+  return OS;
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h
new file mode 100644
index 0000000000000..4a07767a2e198
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagInstr.h
@@ -0,0 +1,115 @@
+//===- GIMatchDagInstr.h - Represent a instruction to be matched ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
+
+#include "GIMatchDagOperands.h"
+#include "llvm/ADT/DenseMap.h"
+
+namespace llvm {
+class GIMatchDag;
+
+/// Represents an instruction in the match DAG. This object knows very little
+/// about the actual instruction to be matched as the bulk of that is in
+/// predicates that are associated with the match DAG. It merely knows the names
+/// and indices of any operands that need to be matched in order to allow edges
+/// to link to them.
+///
+/// Instances of this class objects are owned by the GIMatchDag and are not
+/// shareable between instances of GIMatchDag. This is because the Name,
+/// IsMatchRoot, and OpcodeAnnotation are likely to differ between GIMatchDag
+/// instances.
+class GIMatchDagInstr {
+public:
+  using const_user_assigned_operand_names_iterator =
+      DenseMap<unsigned, StringRef>::const_iterator;
+
+protected:
+  /// The match DAG this instruction belongs to.
+  GIMatchDag &Dag;
+
+  /// The name of the instruction in the pattern. For example:
+  ///     (FOO $a, $b, $c):$name
+  /// will cause name to be assigned to this member. Anonymous instructions will
+  /// have a name assigned for debugging purposes.
+  StringRef Name;
+
+  /// The name of the instruction in the pattern as assigned by the user. For
+  /// example:
+  ///     (FOO $a, $b, $c):$name
+  /// will cause name to be assigned to this member. If a name is not provided,
+  /// this will be empty. This name is used to bind variables from rules to the
+  /// matched instruction.
+  StringRef UserAssignedName;
+
+  /// The name of each operand (if any) that was assigned by the user. For
+  /// example:
+  ///     (FOO $a, $b, $c):$name
+  /// will cause {0, "a"}, {1, "b"}, {2, "c} to be inserted into this map.
+  DenseMap<unsigned, StringRef> UserAssignedNamesForOperands;
+
+  /// The operand list for this instruction. This object may be shared with
+  /// other instructions of a similar 'shape'.
+  const GIMatchDagOperandList &OperandInfo;
+
+  /// For debugging purposes, it's helpful to have access to a description of
+  /// the Opcode. However, this object shouldn't use it for more than debugging
+  /// output since predicates are expected to be handled outside the DAG.
+  CodeGenInstruction *OpcodeAnnotation = 0;
+
+  /// When true, this instruction will be a starting point for a match attempt.
+  bool IsMatchRoot = false;
+
+public:
+  GIMatchDagInstr(GIMatchDag &Dag, StringRef Name, StringRef UserAssignedName,
+                  const GIMatchDagOperandList &OperandInfo)
+      : Dag(Dag), Name(Name), UserAssignedName(UserAssignedName),
+        OperandInfo(OperandInfo) {}
+
+  const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; }
+  StringRef getName() const { return Name; }
+  StringRef getUserAssignedName() const { return UserAssignedName; }
+  void assignNameToOperand(unsigned Idx, StringRef Name) {
+    assert(UserAssignedNamesForOperands[Idx].empty() && "Cannot assign twice");
+    UserAssignedNamesForOperands[Idx] = Name;
+  }
+
+  const_user_assigned_operand_names_iterator
+  user_assigned_operand_names_begin() const {
+    return UserAssignedNamesForOperands.begin();
+  }
+  const_user_assigned_operand_names_iterator
+  user_assigned_operand_names_end() const {
+    return UserAssignedNamesForOperands.end();
+  }
+  iterator_range<const_user_assigned_operand_names_iterator>
+  user_assigned_operand_names() const {
+    return make_range(user_assigned_operand_names_begin(),
+                      user_assigned_operand_names_end());
+  }
+
+  /// Mark this instruction as being a root of the match. This means that the
+  /// matcher will start from this node when attempting to match MIR.
+  void setMatchRoot();
+  bool isMatchRoot() const { return IsMatchRoot; }
+
+  void setOpcodeAnnotation(CodeGenInstruction *I) { OpcodeAnnotation = I; }
+  CodeGenInstruction *getOpcodeAnnotation() const { return OpcodeAnnotation; }
+
+  void print(raw_ostream &OS) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagInstr &N);
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGINSTR_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp
new file mode 100644
index 0000000000000..e79e4686b91e4
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.cpp
@@ -0,0 +1,153 @@
+//===- GIMatchDagOperands.cpp - A shared operand list for nodes -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDagOperands.h"
+
+#include "../CodeGenInstruction.h"
+
+using namespace llvm;
+
+void GIMatchDagOperand::Profile(FoldingSetNodeID &ID) const {
+  Profile(ID, Idx, Name, IsDef);
+}
+
+void GIMatchDagOperand::Profile(FoldingSetNodeID &ID, size_t Idx,
+                                       StringRef Name, bool IsDef) {
+  ID.AddInteger(Idx);
+  ID.AddString(Name);
+  ID.AddBoolean(IsDef);
+}
+
+void GIMatchDagOperandList::add(StringRef Name, unsigned Idx, bool IsDef) {
+  assert(Idx == Operands.size() && "Operands added in wrong order");
+  Operands.emplace_back(Operands.size(), Name, IsDef);
+  OperandsByName.try_emplace(Operands.back().getName(), Operands.size() - 1);
+}
+
+void GIMatchDagOperandList::Profile(FoldingSetNodeID &ID) const {
+  for (const auto &I : enumerate(Operands))
+    GIMatchDagOperand::Profile(ID, I.index(), I.value().getName(),
+                               I.value().isDef());
+}
+
+void GIMatchDagOperandList::print(raw_ostream &OS) const {
+  if (Operands.empty()) {
+    OS << "<empty>";
+    return;
+  }
+  StringRef Separator = "";
+  for (const auto &I : Operands) {
+    OS << Separator << I.getIdx() << ":" << I.getName();
+    if (I.isDef())
+      OS << "<def>";
+    Separator = ", ";
+  }
+}
+
+const GIMatchDagOperandList::value_type &GIMatchDagOperandList::
+operator[](StringRef K) const {
+  const auto &I = OperandsByName.find(K);
+  assert(I != OperandsByName.end() && "Operand not found by name");
+  return Operands[I->second];
+}
+
+const GIMatchDagOperandList &
+GIMatchDagOperandListContext::makeEmptyOperandList() {
+  FoldingSetNodeID ID;
+
+  void *InsertPoint;
+  GIMatchDagOperandList *Value =
+      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
+  if (Value)
+    return *Value;
+
+  std::unique_ptr<GIMatchDagOperandList> NewValue =
+      std::make_unique<GIMatchDagOperandList>();
+  OperandLists.InsertNode(NewValue.get(), InsertPoint);
+  OperandListsOwner.push_back(std::move(NewValue));
+  return *OperandListsOwner.back().get();
+}
+
+const GIMatchDagOperandList &
+GIMatchDagOperandListContext::makeOperandList(const CodeGenInstruction &I) {
+  FoldingSetNodeID ID;
+  for (unsigned i = 0; i < I.Operands.size(); ++i)
+    GIMatchDagOperand::Profile(ID, i, I.Operands[i].Name,
+                               i < I.Operands.NumDefs);
+
+  void *InsertPoint;
+  GIMatchDagOperandList *Value =
+      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
+  if (Value)
+    return *Value;
+
+  std::unique_ptr<GIMatchDagOperandList> NewValue =
+      std::make_unique<GIMatchDagOperandList>();
+  for (unsigned i = 0; i < I.Operands.size(); ++i)
+    NewValue->add(I.Operands[i].Name, i, i < I.Operands.NumDefs);
+  OperandLists.InsertNode(NewValue.get(), InsertPoint);
+  OperandListsOwner.push_back(std::move(NewValue));
+  return *OperandListsOwner.back().get();
+}
+
+const GIMatchDagOperandList &
+GIMatchDagOperandListContext::makeMIPredicateOperandList() {
+  FoldingSetNodeID ID;
+  GIMatchDagOperand::Profile(ID, 0, "$", true);
+  GIMatchDagOperand::Profile(ID, 1, "mi", false);
+
+  void *InsertPoint;
+  GIMatchDagOperandList *Value =
+      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
+  if (Value)
+    return *Value;
+
+  std::unique_ptr<GIMatchDagOperandList> NewValue =
+      std::make_unique<GIMatchDagOperandList>();
+  NewValue->add("$", 0, true);
+  NewValue->add("mi", 1, false);
+  OperandLists.InsertNode(NewValue.get(), InsertPoint);
+  OperandListsOwner.push_back(std::move(NewValue));
+  return *OperandListsOwner.back().get();
+}
+
+
+const GIMatchDagOperandList &
+GIMatchDagOperandListContext::makeTwoMOPredicateOperandList() {
+  FoldingSetNodeID ID;
+  GIMatchDagOperand::Profile(ID, 0, "$", true);
+  GIMatchDagOperand::Profile(ID, 1, "mi0", false);
+  GIMatchDagOperand::Profile(ID, 2, "mi1", false);
+
+  void *InsertPoint;
+  GIMatchDagOperandList *Value =
+      OperandLists.FindNodeOrInsertPos(ID, InsertPoint);
+  if (Value)
+    return *Value;
+
+  std::unique_ptr<GIMatchDagOperandList> NewValue =
+      std::make_unique<GIMatchDagOperandList>();
+  NewValue->add("$", 0, true);
+  NewValue->add("mi0", 1, false);
+  NewValue->add("mi1", 2, false);
+  OperandLists.InsertNode(NewValue.get(), InsertPoint);
+  OperandListsOwner.push_back(std::move(NewValue));
+  return *OperandListsOwner.back().get();
+}
+
+void GIMatchDagOperandListContext::print(raw_ostream &OS) const {
+  OS << "GIMatchDagOperandListContext {\n"
+     << "  OperandLists {\n";
+  for (const auto &I : OperandListsOwner) {
+    OS << "    ";
+    I->print(OS);
+    OS << "\n";
+  }
+  OS << "  }\n"
+     << "}\n";
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h
new file mode 100644
index 0000000000000..c2d30574231d4
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagOperands.h
@@ -0,0 +1,133 @@
+//===- GIMatchDagOperands.h - Represent a shared operand list for nodes ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H
+
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/StringMap.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/raw_ostream.h"
+
+#include <vector>
+
+namespace llvm {
+class CodeGenInstruction;
+/// Describes an operand of a MachineInstr w.r.t the DAG Matching. This
+/// information is derived from CodeGenInstruction::Operands but is more
+/// readily available for context-less access as we don't need to know which
+/// instruction it's used with or know how many defs that instruction had.
+///
+/// There may be multiple GIMatchDagOperand's with the same contents. However,
+/// they are uniqued within the set of instructions that have the same overall
+/// operand list. For example, given:
+///     Inst1 operands ($dst:<def>, $src1, $src2)
+///     Inst2 operands ($dst:<def>, $src1, $src2)
+///     Inst3 operands ($dst:<def>, $src)
+/// $src1 will have a single instance of GIMatchDagOperand shared by Inst1 and
+/// Inst2, as will $src2. $dst however, will have two instances one shared
+/// between Inst1 and Inst2 and one unique to Inst3. We could potentially
+/// fully de-dupe the GIMatchDagOperand instances but the saving is not expected
+/// to be worth the overhead.
+///
+/// The result of this is that the address of the object can be relied upon to
+/// trivially identify commonality between two instructions which will be useful
+/// when generating the matcher. When the pointers differ, the contents can be
+/// inspected instead.
+class GIMatchDagOperand {
+  unsigned Idx;
+  StringRef Name;
+  bool IsDef;
+
+public:
+  GIMatchDagOperand(unsigned Idx, StringRef Name, bool IsDef)
+      : Idx(Idx), Name(Name), IsDef(IsDef) {}
+
+  unsigned getIdx() const { return Idx; }
+  StringRef getName() const { return Name; }
+  bool isDef() const { return IsDef; }
+
+  /// This object isn't a FoldingSetNode but it's part of one. See FoldingSet
+  /// for details on the Profile function.
+  void Profile(FoldingSetNodeID &ID) const;
+
+  /// A helper that behaves like Profile() but is also usable without the object.
+  /// We use size_t here to match enumerate<...>::index(). If we don't match
+  /// that the hashes won't be equal.
+  static void Profile(FoldingSetNodeID &ID, size_t Idx, StringRef Name,
+                      bool IsDef);
+};
+
+/// A list of GIMatchDagOperands for an instruction without any association with
+/// a particular instruction.
+///
+/// An important detail to be aware of with this class is that they are shared
+/// with other instructions of a similar 'shape'. For example, all the binary
+/// instructions are likely to share a single GIMatchDagOperandList. This is
+/// primarily a memory optimization as it's fairly common to have a large number
+/// of instructions but only a few 'shapes'.
+///
+/// See GIMatchDagOperandList::Profile() for the details on how they are folded.
+class GIMatchDagOperandList : public FoldingSetNode {
+public:
+  using value_type = GIMatchDagOperand;
+
+protected:
+  using vector_type = SmallVector<GIMatchDagOperand, 3>;
+
+public:
+  using iterator = vector_type::iterator;
+  using const_iterator = vector_type::const_iterator;
+
+protected:
+  vector_type Operands;
+  StringMap<unsigned> OperandsByName;
+
+public:
+  void add(StringRef Name, unsigned Idx, bool IsDef);
+
+  /// See FoldingSet for details.
+  void Profile(FoldingSetNodeID &ID) const;
+
+  iterator begin() { return Operands.begin(); }
+  const_iterator begin() const { return Operands.begin(); }
+  iterator end() { return Operands.end(); }
+  const_iterator end() const { return Operands.end(); }
+
+  const value_type &operator[](unsigned I) const { return Operands[I]; }
+  const value_type &operator[](StringRef K) const;
+
+  void print(raw_ostream &OS) const;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+/// This is the portion of GIMatchDagContext that directly relates to
+/// GIMatchDagOperandList and GIMatchDagOperandList.
+class GIMatchDagOperandListContext {
+  FoldingSet<GIMatchDagOperandList> OperandLists;
+  std::vector<std::unique_ptr<GIMatchDagOperandList>> OperandListsOwner;
+
+public:
+  const GIMatchDagOperandList &makeEmptyOperandList();
+  const GIMatchDagOperandList &makeOperandList(const CodeGenInstruction &I);
+  const GIMatchDagOperandList &makeMIPredicateOperandList();
+  const GIMatchDagOperandList &makeTwoMOPredicateOperandList();
+
+  void print(raw_ostream &OS) const;
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGOPERANDS_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp
new file mode 100644
index 0000000000000..1aca2f9dc1352
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.cpp
@@ -0,0 +1,69 @@
+//===- GIMatchDagPredicate.cpp - Represent a predicate to check -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDagPredicate.h"
+
+#include "llvm/TableGen/Record.h"
+
+#include "GIMatchDagOperands.h"
+#include "../CodeGenInstruction.h"
+
+using namespace llvm;
+
+void GIMatchDagPredicate::print(raw_ostream &OS) const {
+  OS << "<<";
+  printDescription(OS);
+  OS << ">>:$" << Name;
+}
+
+void GIMatchDagPredicate::printDescription(raw_ostream &OS) const { OS << ""; }
+
+GIMatchDagOpcodePredicate::GIMatchDagOpcodePredicate(
+    GIMatchDagContext &Ctx, StringRef Name, const CodeGenInstruction &Instr)
+    : GIMatchDagPredicate(GIMatchDagPredicateKind_Opcode, Name,
+                          Ctx.makeMIPredicateOperandList()),
+      Instr(Instr) {}
+
+void GIMatchDagOpcodePredicate::printDescription(raw_ostream &OS) const {
+  OS << "$mi.getOpcode() == " << Instr.TheDef->getName();
+}
+
+GIMatchDagOneOfOpcodesPredicate::GIMatchDagOneOfOpcodesPredicate(
+    GIMatchDagContext &Ctx, StringRef Name)
+    : GIMatchDagPredicate(GIMatchDagPredicateKind_OneOfOpcodes, Name,
+                          Ctx.makeMIPredicateOperandList()) {}
+
+void GIMatchDagOneOfOpcodesPredicate::printDescription(raw_ostream &OS) const {
+  OS << "$mi.getOpcode() == oneof(";
+  StringRef Separator = "";
+  for (const CodeGenInstruction *Instr : Instrs) {
+    OS << Separator << Instr->TheDef->getName();
+    Separator = ",";
+  }
+  OS << ")";
+}
+
+GIMatchDagSameMOPredicate::GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx,
+                                                     StringRef Name)
+    : GIMatchDagPredicate(GIMatchDagPredicateKind_SameMO, Name,
+                          Ctx.makeTwoMOPredicateOperandList()) {}
+
+void GIMatchDagSameMOPredicate::printDescription(raw_ostream &OS) const {
+  OS << "$mi0 == $mi1";
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS, const GIMatchDagPredicate &N) {
+  N.print(OS);
+  return OS;
+}
+
+raw_ostream &llvm::operator<<(raw_ostream &OS,
+                              const GIMatchDagOpcodePredicate &N) {
+  N.print(OS);
+  return OS;
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h
new file mode 100644
index 0000000000000..9b030d6edb137
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicate.h
@@ -0,0 +1,141 @@
+//===- GIMatchDagPredicate - Represent a predicate to check ---------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
+
+#include "llvm/ADT/StringRef.h"
+#include "GIMatchDag.h"
+
+namespace llvm {
+class CodeExpansions;
+class CodeGenInstruction;
+class GIMatchDagOperandList;
+class GIMatchDagContext;
+class raw_ostream;
+
+/// Represents a predicate on the match DAG. This records the details of the
+/// predicate. The dependencies are stored in the GIMatchDag as edges.
+///
+/// Instances of this class objects are owned by the GIMatchDag and are not
+/// shareable between instances of GIMatchDag.
+class GIMatchDagPredicate {
+public:
+  enum GIMatchDagPredicateKind {
+    GIMatchDagPredicateKind_Opcode,
+    GIMatchDagPredicateKind_OneOfOpcodes,
+    GIMatchDagPredicateKind_SameMO,
+  };
+
+protected:
+  const GIMatchDagPredicateKind Kind;
+
+  /// The name of the predicate. For example:
+  ///     (FOO $a:s32, $b, $c)
+  /// will cause 's32' to be assigned to this member for the $a predicate.
+  /// Similarly, the opcode predicate will cause 'FOO' to be assigned to this
+  /// member. Anonymous instructions will have a name assigned for debugging
+  /// purposes.
+  StringRef Name;
+
+  /// The operand list for this predicate. This object may be shared with
+  /// other predicates of a similar 'shape'.
+  const GIMatchDagOperandList &OperandInfo;
+
+public:
+  GIMatchDagPredicate(GIMatchDagPredicateKind Kind, StringRef Name,
+                      const GIMatchDagOperandList &OperandInfo)
+      : Kind(Kind), Name(Name), OperandInfo(OperandInfo) {}
+  virtual ~GIMatchDagPredicate() {}
+
+  GIMatchDagPredicateKind getKind() const { return Kind; }
+
+  StringRef getName() const { return Name; }
+  const GIMatchDagOperandList &getOperandInfo() const { return OperandInfo; }
+
+  // Generate C++ code to check this predicate. If a partitioner has already
+  // tested this predicate then this function won't be called. If this function
+  // is called, it must emit code and return true to indicate that it did so. If
+  // it ever returns false, then the caller will abort due to an untested
+  // predicate.
+  virtual bool generateCheckCode(raw_ostream &OS, StringRef Indent,
+                                 const CodeExpansions &Expansions) const {
+    return false;
+  }
+
+  virtual void print(raw_ostream &OS) const;
+  virtual void printDescription(raw_ostream &OS) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+class GIMatchDagOpcodePredicate : public GIMatchDagPredicate {
+  const CodeGenInstruction &Instr;
+
+public:
+  GIMatchDagOpcodePredicate(GIMatchDagContext &Ctx, StringRef Name,
+                            const CodeGenInstruction &Instr);
+
+  static bool classof(const GIMatchDagPredicate *P) {
+    return P->getKind() == GIMatchDagPredicateKind_Opcode;
+  }
+
+  const CodeGenInstruction *getInstr() const { return &Instr; }
+
+  void printDescription(raw_ostream &OS) const override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+class GIMatchDagOneOfOpcodesPredicate : public GIMatchDagPredicate {
+  SmallVector<const CodeGenInstruction *, 4> Instrs;
+
+public:
+  GIMatchDagOneOfOpcodesPredicate(GIMatchDagContext &Ctx, StringRef Name);
+
+  void addOpcode(const CodeGenInstruction *Instr) { Instrs.push_back(Instr); }
+
+  static bool classof(const GIMatchDagPredicate *P) {
+    return P->getKind() == GIMatchDagPredicateKind_OneOfOpcodes;
+  }
+
+  const SmallVectorImpl<const CodeGenInstruction *> &getInstrs() const {
+    return Instrs;
+  }
+
+  void printDescription(raw_ostream &OS) const override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+class GIMatchDagSameMOPredicate : public GIMatchDagPredicate {
+public:
+  GIMatchDagSameMOPredicate(GIMatchDagContext &Ctx, StringRef Name);
+
+  static bool classof(const GIMatchDagPredicate *P) {
+    return P->getKind() == GIMatchDagPredicateKind_SameMO;
+  }
+
+  void printDescription(raw_ostream &OS) const override;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  virtual LLVM_DUMP_METHOD void dump() const override { print(errs()); }
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagPredicate &N);
+raw_ostream &operator<<(raw_ostream &OS, const GIMatchDagOpcodePredicate &N);
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATE_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp
new file mode 100644
index 0000000000000..2e804de1cd4e7
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.cpp
@@ -0,0 +1,37 @@
+//===- GIMatchDagPredicateDependencyEdge.cpp - Have inputs before check ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchDagPredicateDependencyEdge.h"
+
+#include "GIMatchDagInstr.h"
+#include "GIMatchDagPredicate.h"
+
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+LLVM_DUMP_METHOD void
+GIMatchDagPredicateDependencyEdge::print(raw_ostream &OS) const {
+  OS << getRequiredMI()->getName();
+  if (getRequiredMO())
+    OS << "[" << getRequiredMO()->getName() << "]";
+  OS << " ==> " << getPredicate()->getName() << "["
+     << getPredicateOp()->getName() << "]";
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+LLVM_DUMP_METHOD void GIMatchDagPredicateDependencyEdge::dump() const {
+  print(errs());
+}
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+
+raw_ostream &llvm::operator<<(raw_ostream &OS,
+                              const GIMatchDagPredicateDependencyEdge &E) {
+  E.print(OS);
+  return OS;
+}
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h
new file mode 100644
index 0000000000000..865455fe4e4d9
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchDagPredicateDependencyEdge.h
@@ -0,0 +1,60 @@
+//===- GIMatchDagPredicateDependencyEdge - Ensure predicates have inputs --===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H
+
+#include "GIMatchDagOperands.h"
+
+namespace llvm {
+class GIMatchDag;
+class GIMatchDagInstr;
+class GIMatchDagEdge;
+class GIMatchDagPredicate;
+
+/// Represents a dependency that must be met to evaluate a predicate.
+///
+/// Instances of this class objects are owned by the GIMatchDag and are not
+/// shareable between instances of GIMatchDag.
+class GIMatchDagPredicateDependencyEdge {
+  /// The MI that must be available in order to test the predicate.
+  const GIMatchDagInstr *RequiredMI;
+  /// The MO that must be available in order to test the predicate. May be
+  /// nullptr when only the MI is required.
+  const GIMatchDagOperand *RequiredMO;
+  /// The Predicate that requires information from RequiredMI/RequiredMO.
+  const GIMatchDagPredicate *Predicate;
+  /// The Predicate operand that requires information from
+  /// RequiredMI/RequiredMO.
+  const GIMatchDagOperand *PredicateOp;
+
+public:
+  GIMatchDagPredicateDependencyEdge(const GIMatchDagInstr *RequiredMI,
+                                    const GIMatchDagOperand *RequiredMO,
+                                    const GIMatchDagPredicate *Predicate,
+                                    const GIMatchDagOperand *PredicateOp)
+      : RequiredMI(RequiredMI), RequiredMO(RequiredMO), Predicate(Predicate),
+        PredicateOp(PredicateOp) {}
+
+  const GIMatchDagInstr *getRequiredMI() const { return RequiredMI; }
+  const GIMatchDagOperand *getRequiredMO() const { return RequiredMO; }
+  const GIMatchDagPredicate *getPredicate() const { return Predicate; }
+  const GIMatchDagOperand *getPredicateOp() const { return PredicateOp; }
+
+  void print(raw_ostream &OS) const;
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD void dump() const;
+#endif // if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+};
+
+raw_ostream &operator<<(raw_ostream &OS,
+                        const GIMatchDagPredicateDependencyEdge &N);
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHDAGPREDICATEEDGE_H
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp
new file mode 100644
index 0000000000000..4884bdadea91d
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchTree.cpp
@@ -0,0 +1,777 @@
+//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "GIMatchTree.h"
+
+#include "../CodeGenInstruction.h"
+
+#include "llvm/Support/Format.h"
+#include "llvm/Support/ScopedPrinter.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+
+#define DEBUG_TYPE "gimatchtree"
+
+using namespace llvm;
+
+void GIMatchTree::writeDOTGraph(raw_ostream &OS) const {
+  OS << "digraph \"matchtree\" {\n";
+  writeDOTGraphNode(OS);
+  OS << "}\n";
+}
+
+void GIMatchTree::writeDOTGraphNode(raw_ostream &OS) const {
+  OS << format("  Node%p", this) << " [shape=record,label=\"{";
+  if (Partitioner) {
+    Partitioner->emitDescription(OS);
+    OS << "|" << Partitioner->getNumPartitions() << " partitions|";
+  } else
+    OS << "No partitioner|";
+  bool IsFullyTraversed = true;
+  bool IsFullyTested = true;
+  StringRef Separator = "";
+  for (const auto &Leaf : PossibleLeaves) {
+    OS << Separator << Leaf.getName();
+    Separator = ",";
+    if (!Leaf.isFullyTraversed())
+      IsFullyTraversed = false;
+    if (!Leaf.isFullyTested())
+      IsFullyTested = false;
+  }
+  if (!Partitioner && !IsFullyTraversed)
+    OS << "|Not fully traversed";
+  if (!Partitioner && !IsFullyTested) {
+    OS << "|Not fully tested";
+    if (IsFullyTraversed) {
+      for (const GIMatchTreeLeafInfo &Leaf : PossibleLeaves) {
+        if (Leaf.isFullyTested())
+          continue;
+        OS << "\\n" << Leaf.getName() << ": " << &Leaf;
+        for (const GIMatchDagPredicate *P : Leaf.untested_predicates())
+          OS << *P;
+      }
+    }
+  }
+  OS << "}\"";
+  if (!Partitioner &&
+      (!IsFullyTraversed || !IsFullyTested || PossibleLeaves.size() > 1))
+    OS << ",color=red";
+  OS << "]\n";
+  for (const auto &C : Children)
+    C.writeDOTGraphNode(OS);
+  writeDOTGraphEdges(OS);
+}
+
+void GIMatchTree::writeDOTGraphEdges(raw_ostream &OS) const {
+  for (const auto &Child : enumerate(Children)) {
+    OS << format("  Node%p", this) << " -> " << format("Node%p", &Child.value())
+       << " [label=\"#" << Child.index() << " ";
+    Partitioner->emitPartitionName(OS, Child.index());
+    OS << "\"]\n";
+  }
+}
+
+GIMatchTreeBuilderLeafInfo::GIMatchTreeBuilderLeafInfo(
+    GIMatchTreeBuilder &Builder, StringRef Name, unsigned RootIdx,
+    const GIMatchDag &MatchDag, void *Data)
+    : Builder(Builder), Info(Name, RootIdx, Data), MatchDag(MatchDag),
+      InstrNodeToInfo(),
+      RemainingInstrNodes(BitVector(MatchDag.getNumInstrNodes(), true)),
+      RemainingEdges(BitVector(MatchDag.getNumEdges(), true)),
+      RemainingPredicates(BitVector(MatchDag.getNumPredicates(), true)),
+      TraversableEdges(MatchDag.getNumEdges()),
+      TestablePredicates(MatchDag.getNumPredicates()) {
+  // Number all the predicates in this DAG
+  for (auto &P : enumerate(MatchDag.predicates())) {
+    PredicateIDs.insert(std::make_pair(P.value(), P.index()));
+  }
+
+  // Number all the predicate dependencies in this DAG and set up a bitvector
+  // for each predicate indicating the unsatisfied dependencies.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    PredicateDepIDs.insert(std::make_pair(Dep.value(), Dep.index()));
+  }
+  UnsatisfiedPredDepsForPred.resize(MatchDag.getNumPredicates(),
+                                    BitVector(PredicateDepIDs.size()));
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    unsigned ID = PredicateIDs.lookup(Dep.value()->getPredicate());
+    UnsatisfiedPredDepsForPred[ID].set(Dep.index());
+  }
+}
+
+void GIMatchTreeBuilderLeafInfo::declareInstr(const GIMatchDagInstr *Instr, unsigned ID) {
+  // Record the assignment of this instr to the given ID.
+  auto InfoI = InstrNodeToInfo.insert(std::make_pair(
+      Instr, GIMatchTreeInstrInfo(ID, Instr)));
+  InstrIDToInfo.insert(std::make_pair(ID, &InfoI.first->second));
+
+  if (Instr == nullptr)
+    return;
+
+  if (!Instr->getUserAssignedName().empty())
+    Info.bindInstrVariable(Instr->getUserAssignedName(), ID);
+  for (const auto &VarBinding : Instr->user_assigned_operand_names())
+    Info.bindOperandVariable(VarBinding.second, ID, VarBinding.first);
+
+  // Clear the bit indicating we haven't visited this instr.
+  const auto &NodeI = std::find(MatchDag.instr_nodes_begin(),
+                            MatchDag.instr_nodes_end(), Instr);
+  assert(NodeI != MatchDag.instr_nodes_end() && "Instr isn't in this DAG");
+  unsigned InstrIdx = MatchDag.getInstrNodeIdx(NodeI);
+  RemainingInstrNodes.reset(InstrIdx);
+
+  // When we declare an instruction, we don't expose any traversable edges just
+  // yet. A partitioner has to check they exist and are registers before they
+  // are traversable.
+
+  // When we declare an instruction, we potentially activate some predicates.
+  // Mark the dependencies that are now satisfied as a result of this
+  // instruction and mark any predicates whose dependencies are fully
+  // satisfied.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    if (Dep.value()->getRequiredMI() == Instr &&
+        Dep.value()->getRequiredMO() == nullptr) {
+      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+        DepsFor.value().reset(Dep.index());
+        if (DepsFor.value().none())
+          TestablePredicates.set(DepsFor.index());
+      }
+    }
+  }
+}
+
+void GIMatchTreeBuilderLeafInfo::declareOperand(unsigned InstrID,
+                                                unsigned OpIdx) {
+  const GIMatchDagInstr *Instr = InstrIDToInfo.lookup(InstrID)->getInstrNode();
+
+  OperandIDToInfo.insert(std::make_pair(
+      std::make_pair(InstrID, OpIdx),
+      GIMatchTreeOperandInfo(Instr, OpIdx)));
+
+  // When an operand becomes reachable, we potentially activate some traversals.
+  // Record the edges that can now be followed as a result of this
+  // instruction.
+  for (auto &E : enumerate(MatchDag.edges())) {
+    if (E.value()->getFromMI() == Instr &&
+        E.value()->getFromMO()->getIdx() == OpIdx) {
+      TraversableEdges.set(E.index());
+    }
+  }
+
+  // When an operand becomes reachable, we potentially activate some predicates.
+  // Clear the dependencies that are now satisfied as a result of this
+  // operand and activate any predicates whose dependencies are fully
+  // satisfied.
+  for (auto &Dep : enumerate(MatchDag.predicate_edges())) {
+    if (Dep.value()->getRequiredMI() == Instr && Dep.value()->getRequiredMO() &&
+        Dep.value()->getRequiredMO()->getIdx() == OpIdx) {
+      for (auto &DepsFor : enumerate(UnsatisfiedPredDepsForPred)) {
+        DepsFor.value().reset(Dep.index());
+        if (DepsFor.value().none())
+          TestablePredicates.set(DepsFor.index());
+      }
+    }
+  }
+}
+
+void GIMatchTreeBuilder::addPartitionersForInstr(unsigned InstrIdx) {
+  // Find the partitioners that can be used now that this node is
+  // uncovered. Our choices are:
+  // - Test the opcode
+  addPartitioner(std::make_unique<GIMatchTreeOpcodePartitioner>(InstrIdx));
+}
+
+void GIMatchTreeBuilder::addPartitionersForOperand(unsigned InstrID,
+                                                   unsigned OpIdx) {
+  LLVM_DEBUG(dbgs() << "Add partitioners for Instrs[" << InstrID
+                    << "].getOperand(" << OpIdx << ")\n");
+  addPartitioner(
+      std::make_unique<GIMatchTreeVRegDefPartitioner>(InstrID, OpIdx));
+}
+
+void GIMatchTreeBuilder::filterRedundantPartitioners() {
+  // TODO: Filter partitioners for facts that are already known
+  // - If we know the opcode, we can elide the num operand check so long as
+  //   the instruction has a fixed number of operands.
+  // - If we know an exact number of operands then we can elide further number
+  //   of operand checks.
+  // - If the current min number of operands exceeds the one we want to check
+  //   then we can elide it.
+}
+
+void GIMatchTreeBuilder::evaluatePartitioners() {
+  // Determine the partitioning the partitioner would produce
+  for (auto &Partitioner : Partitioners) {
+    LLVM_DEBUG(dbgs() << "    Weighing up ";
+               Partitioner->emitDescription(dbgs()); dbgs() << "\n");
+    Partitioner->repartition(Leaves);
+    LLVM_DEBUG(Partitioner->emitPartitionResults(dbgs()));
+  }
+}
+
+void GIMatchTreeBuilder::runStep() {
+  LLVM_DEBUG(dbgs() << "Building match tree node for " << TreeNode << "\n");
+  LLVM_DEBUG(dbgs() << "  Rules reachable at this node:\n");
+  for (const auto &Leaf : Leaves) {
+    LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " (" << &Leaf.getInfo() << "\n");
+    TreeNode->addPossibleLeaf(Leaf.getInfo(), Leaf.isFullyTraversed(),
+                              Leaf.isFullyTested());
+  }
+
+  LLVM_DEBUG(dbgs() << "  Partitioners available at this node:\n");
+#ifndef NDEBUG
+  for (const auto &Partitioner : Partitioners)
+    LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
+               dbgs() << "\n");
+#endif // ifndef NDEBUG
+
+  // Check for unreachable rules. Rules are unreachable if they are preceeded by
+  // a fully tested rule.
+  // Note: This is only true for the current algorithm, if we allow the
+  //       algorithm to compare equally valid rules then they will become
+  //       reachable.
+  {
+    auto FullyTestedLeafI = Leaves.end();
+    for (auto LeafI = Leaves.begin(), LeafE = Leaves.end();
+         LeafI != LeafE; ++LeafI) {
+      if (LeafI->isFullyTraversed() && LeafI->isFullyTested())
+        FullyTestedLeafI = LeafI;
+      else if (FullyTestedLeafI != Leaves.end()) {
+        PrintError("Leaf " + LeafI->getName() + " is unreachable");
+        PrintNote("Leaf " + FullyTestedLeafI->getName() +
+                  " will have already matched");
+      }
+    }
+  }
+
+  LLVM_DEBUG(dbgs() << "  Eliminating redundant partitioners:\n");
+  filterRedundantPartitioners();
+  LLVM_DEBUG(dbgs() << "  Partitioners remaining:\n");
+#ifndef NDEBUG
+  for (const auto &Partitioner : Partitioners)
+    LLVM_DEBUG(dbgs() << "    "; Partitioner->emitDescription(dbgs());
+               dbgs() << "\n");
+#endif // ifndef NDEBUG
+
+  if (Partitioners.empty()) {
+    // Nothing left to do but check we really did identify a single rule.
+    if (Leaves.size() > 1) {
+      LLVM_DEBUG(dbgs() << "Leaf contains multiple rules, drop after the first "
+                           "fully tested rule\n");
+      auto FirstFullyTested =
+          std::find_if(Leaves.begin(), Leaves.end(),
+                       [](const GIMatchTreeBuilderLeafInfo &X) {
+                         return X.isFullyTraversed() && X.isFullyTested() &&
+                                !X.getMatchDag().hasPostMatchPredicate();
+                       });
+      if (FirstFullyTested != Leaves.end())
+        FirstFullyTested++;
+
+#ifndef NDEBUG
+      for (auto &Leaf : make_range(Leaves.begin(), FirstFullyTested))
+        LLVM_DEBUG(dbgs() << "  Kept " << Leaf.getName() << "\n");
+      for (const auto &Leaf : make_range(FirstFullyTested, Leaves.end()))
+        LLVM_DEBUG(dbgs() << "  Dropped " << Leaf.getName() << "\n");
+#endif // ifndef NDEBUG
+      TreeNode->dropLeavesAfter(
+          std::distance(Leaves.begin(), FirstFullyTested));
+    }
+    for (const auto &Leaf : Leaves) {
+      if (!Leaf.isFullyTraversed()) {
+        PrintError("Leaf " + Leaf.getName() + " is not fully traversed");
+        PrintNote("This indicates a missing partitioner within tblgen");
+        Leaf.dump(errs());
+        for (unsigned InstrIdx : Leaf.untested_instrs())
+          PrintNote("Instr " + llvm::to_string(*Leaf.getInstr(InstrIdx)));
+        for (unsigned EdgeIdx : Leaf.untested_edges())
+          PrintNote("Edge " + llvm::to_string(*Leaf.getEdge(EdgeIdx)));
+      }
+    }
+
+    // Copy out information about untested predicates so the user of the tree
+    // can deal with them.
+    for (auto LeafPair : zip(Leaves, TreeNode->possible_leaves())) {
+      const GIMatchTreeBuilderLeafInfo &BuilderLeaf = std::get<0>(LeafPair);
+      GIMatchTreeLeafInfo &TreeLeaf = std::get<1>(LeafPair);
+      if (!BuilderLeaf.isFullyTested())
+        for (unsigned PredicateIdx : BuilderLeaf.untested_predicates())
+          TreeLeaf.addUntestedPredicate(BuilderLeaf.getPredicate(PredicateIdx));
+    }
+    return;
+  }
+
+  LLVM_DEBUG(dbgs() << "  Weighing up partitioners:\n");
+  evaluatePartitioners();
+
+  // Select the best partitioner by its ability to partition
+  // - Prefer partitioners that don't distinguish between partitions. This
+  //   is to fail early on decisions that must go a single way.
+  auto PartitionerI = std::max_element(
+      Partitioners.begin(), Partitioners.end(),
+      [](const std::unique_ptr<GIMatchTreePartitioner> &A,
+         const std::unique_ptr<GIMatchTreePartitioner> &B) {
+        // We generally want partitioners that subdivide the
+        // ruleset as much as possible since these take fewer
+        // checks to converge on a particular rule. However,
+        // it's important to note that one leaf can end up in
+        // multiple partitions if the check isn't mutually
+        // exclusive (e.g. getVRegDef() vs isReg()).
+        // We therefore minimize average leaves per partition.
+        return (double)A->getNumLeavesWithDupes() / A->getNumPartitions() >
+               (double)B->getNumLeavesWithDupes() / B->getNumPartitions();
+      });
+
+  // Select a partitioner and partition the ruleset
+  // Note that it's possible for a single rule to end up in multiple
+  // partitions. For example, an opcode test on a rule without an opcode
+  // predicate will result in it being passed to all partitions.
+  std::unique_ptr<GIMatchTreePartitioner> Partitioner = std::move(*PartitionerI);
+  Partitioners.erase(PartitionerI);
+  LLVM_DEBUG(dbgs() << "  Selected partitioner: ";
+             Partitioner->emitDescription(dbgs()); dbgs() << "\n");
+
+  assert(Partitioner->getNumPartitions() > 0 &&
+         "Must always partition into at least one partition");
+
+  TreeNode->setNumChildren(Partitioner->getNumPartitions());
+  for (auto &C : enumerate(TreeNode->children())) {
+    SubtreeBuilders.emplace_back(&C.value(), NextInstrID);
+    Partitioner->applyForPartition(C.index(), *this, SubtreeBuilders.back());
+  }
+
+  TreeNode->setPartitioner(std::move(Partitioner));
+
+  // Recurse into the subtree builders. Each one must get a copy of the
+  // remaining partitioners as each path has to check everything.
+  for (auto &SubtreeBuilder : SubtreeBuilders) {
+    for (const auto &Partitioner : Partitioners)
+      SubtreeBuilder.addPartitioner(Partitioner->clone());
+    SubtreeBuilder.runStep();
+  }
+}
+
+std::unique_ptr<GIMatchTree> GIMatchTreeBuilder::run() {
+  unsigned NewInstrID = allocInstrID();
+  // Start by recording the root instruction as instr #0 and set up the initial
+  // partitioners.
+  for (auto &Leaf : Leaves) {
+    LLVM_DEBUG(Leaf.getMatchDag().writeDOTGraph(dbgs(), Leaf.getName()));
+    GIMatchDagInstr *Root =
+        *(Leaf.getMatchDag().roots().begin() + Leaf.getRootIdx());
+    Leaf.declareInstr(Root, NewInstrID);
+  }
+
+  addPartitionersForInstr(NewInstrID);
+
+  std::unique_ptr<GIMatchTree> TreeRoot = std::make_unique<GIMatchTree>();
+  TreeNode = TreeRoot.get();
+  runStep();
+
+  return TreeRoot;
+}
+
+void GIMatchTreeOpcodePartitioner::emitPartitionName(raw_ostream &OS, unsigned Idx) const {
+  if (PartitionToInstr[Idx] == nullptr) {
+    OS << "* or nullptr";
+    return;
+  }
+  OS << PartitionToInstr[Idx]->Namespace
+     << "::" << PartitionToInstr[Idx]->TheDef->getName();
+}
+
+void GIMatchTreeOpcodePartitioner::repartition(
+    GIMatchTreeBuilder::LeafVec &Leaves) {
+  Partitions.clear();
+  InstrToPartition.clear();
+  PartitionToInstr.clear();
+  TestedPredicates.clear();
+
+  for (const auto &Leaf : enumerate(Leaves)) {
+    bool AllOpcodes = true;
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    BitVector TestedPredicatesForLeaf(
+        Leaf.value().getMatchDag().getNumPredicates());
+
+    // If the instruction isn't declared then we don't care about it. Ignore
+    // it for now and add it to all partitions later once we know what
+    // partitions we have.
+    if (!InstrInfo) {
+      LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                        << " doesn't care about Instr[" << InstrID << "]\n");
+      assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
+      TestedPredicates.push_back(TestedPredicatesForLeaf);
+      continue;
+    }
+
+    // If the opcode is available to test then any opcode predicates will have
+    // been enabled too.
+    for (unsigned PIdx : Leaf.value().TestablePredicates.set_bits()) {
+      const auto &P = Leaf.value().getPredicate(PIdx);
+      SmallVector<const CodeGenInstruction *, 1> OpcodesForThisPredicate;
+      if (const auto *OpcodeP = dyn_cast<const GIMatchDagOpcodePredicate>(P)) {
+        // We've found _an_ opcode predicate, but we don't know if it's
+        // checking this instruction yet.
+        bool IsThisPredicate = false;
+        for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
+          if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
+              PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
+            IsThisPredicate = true;
+            break;
+          }
+        }
+        if (!IsThisPredicate)
+          continue;
+
+        // If we get here twice then we've somehow ended up with two opcode
+        // predicates for one instruction in the same DAG. That should be
+        // impossible.
+        assert(AllOpcodes && "Conflicting opcode predicates");
+        const CodeGenInstruction *Expected = OpcodeP->getInstr();
+        OpcodesForThisPredicate.push_back(Expected);
+      }
+
+      if (const auto *OpcodeP =
+              dyn_cast<const GIMatchDagOneOfOpcodesPredicate>(P)) {
+        // We've found _an_ oneof(opcodes) predicate, but we don't know if it's
+        // checking this instruction yet.
+        bool IsThisPredicate = false;
+        for (const auto &PDep : Leaf.value().getMatchDag().predicate_edges()) {
+          if (PDep->getRequiredMI() == InstrInfo->getInstrNode() &&
+              PDep->getRequiredMO() == nullptr && PDep->getPredicate() == P) {
+            IsThisPredicate = true;
+            break;
+          }
+        }
+        if (!IsThisPredicate)
+          continue;
+
+        // If we get here twice then we've somehow ended up with two opcode
+        // predicates for one instruction in the same DAG. That should be
+        // impossible.
+        assert(AllOpcodes && "Conflicting opcode predicates");
+        for (const CodeGenInstruction *Expected : OpcodeP->getInstrs())
+          OpcodesForThisPredicate.push_back(Expected);
+      }
+
+      for (const CodeGenInstruction *Expected : OpcodesForThisPredicate) {
+        // Mark this predicate as one we're testing.
+        TestedPredicatesForLeaf.set(PIdx);
+
+        // Partitions must be numbered 0, 1, .., N but instructions don't meet
+        // that requirement. Assign a partition number to each opcode if we
+        // lack one ...
+        auto Partition = InstrToPartition.find(Expected);
+        if (Partition == InstrToPartition.end()) {
+          BitVector Contents(Leaves.size());
+          Partition = InstrToPartition
+                          .insert(std::make_pair(Expected, Partitions.size()))
+                          .first;
+          PartitionToInstr.push_back(Expected);
+          Partitions.insert(std::make_pair(Partitions.size(), Contents));
+        }
+        // ... and mark this leaf as being in that partition.
+        Partitions.find(Partition->second)->second.set(Leaf.index());
+        AllOpcodes = false;
+        LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                          << " is in partition " << Partition->second << "\n");
+      }
+
+      // TODO: This is where we would handle multiple choices of opcode
+      //       the end result will be that this leaf ends up in multiple
+      //       partitions similarly to AllOpcodes.
+    }
+
+    // If we never check the opcode, add it to every partition.
+    if (AllOpcodes) {
+      // Add a partition for the default case if we don't already have one.
+      if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+        PartitionToInstr.push_back(nullptr);
+        BitVector Contents(Leaves.size());
+        Partitions.insert(std::make_pair(Partitions.size(), Contents));
+      }
+      LLVM_DEBUG(dbgs() << "      " << Leaf.value().getName()
+                        << " is in all partitions (opcode not checked)\n");
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+    }
+
+    assert(TestedPredicatesForLeaf.size() == Leaf.value().getMatchDag().getNumPredicates());
+    TestedPredicates.push_back(TestedPredicatesForLeaf);
+  }
+
+  if (Partitions.size() == 0) {
+    // Add a partition for the default case if we don't already have one.
+    if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+      PartitionToInstr.push_back(nullptr);
+      BitVector Contents(Leaves.size());
+      Partitions.insert(std::make_pair(Partitions.size(), Contents));
+    }
+  }
+
+  // Add any leaves that don't care about this instruction to all partitions.
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    if (!InstrInfo) {
+      // Add a partition for the default case if we don't already have one.
+      if (InstrToPartition.insert(std::make_pair(nullptr, 0)).second) {
+        PartitionToInstr.push_back(nullptr);
+        BitVector Contents(Leaves.size());
+        Partitions.insert(std::make_pair(Partitions.size(), Contents));
+      }
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+    }
+  }
+
+}
+
+void GIMatchTreeOpcodePartitioner::applyForPartition(
+    unsigned PartitionIdx, GIMatchTreeBuilder &Builder, GIMatchTreeBuilder &SubBuilder) {
+  LLVM_DEBUG(dbgs() << "  Making partition " << PartitionIdx << "\n");
+  const CodeGenInstruction *CGI = PartitionToInstr[PartitionIdx];
+
+  BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
+  // Consume any predicates we handled.
+  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+    if (!PossibleLeaves[EnumeratedLeaf.index()])
+      continue;
+
+    auto &Leaf = EnumeratedLeaf.value();
+    const auto &TestedPredicatesForLeaf =
+        TestedPredicates[EnumeratedLeaf.index()];
+
+    for (unsigned PredIdx : TestedPredicatesForLeaf.set_bits()) {
+      LLVM_DEBUG(dbgs() << "    " << Leaf.getName() << " tested predicate #"
+                        << PredIdx << " of " << TestedPredicatesForLeaf.size()
+                        << " " << *Leaf.getPredicate(PredIdx) << "\n");
+      Leaf.RemainingPredicates.reset(PredIdx);
+      Leaf.TestablePredicates.reset(PredIdx);
+    }
+    SubBuilder.addLeaf(Leaf);
+  }
+
+  // Nothing to do, we don't know anything about this instruction as a result
+  // of this partitioner.
+  if (CGI == nullptr)
+    return;
+
+  GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
+  // Find all the operands we know to exist and are referenced. This will
+  // usually be all the referenced operands but there are some cases where
+  // instructions are variadic. Such operands must be handled by partitioners
+  // that check the number of operands.
+  BitVector ReferencedOperands(1);
+  for (auto &Leaf : NewLeaves) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
+    // Skip any leaves that don't care about this instruction.
+    if (!InstrInfo)
+      continue;
+    const GIMatchDagInstr *Instr = InstrInfo->getInstrNode();
+    for (auto &E : enumerate(Leaf.getMatchDag().edges())) {
+      if (E.value()->getFromMI() == Instr &&
+          E.value()->getFromMO()->getIdx() < CGI->Operands.size()) {
+        ReferencedOperands.resize(E.value()->getFromMO()->getIdx() + 1);
+        ReferencedOperands.set(E.value()->getFromMO()->getIdx());
+      }
+    }
+  }
+  for (auto &Leaf : NewLeaves) {
+    for (unsigned OpIdx : ReferencedOperands.set_bits()) {
+      Leaf.declareOperand(InstrID, OpIdx);
+    }
+  }
+  for (unsigned OpIdx : ReferencedOperands.set_bits()) {
+    SubBuilder.addPartitionersForOperand(InstrID, OpIdx);
+  }
+}
+
+void GIMatchTreeOpcodePartitioner::emitPartitionResults(
+    raw_ostream &OS) const {
+  OS << "Partitioning by opcode would produce " << Partitions.size()
+     << " partitions\n";
+  for (const auto &Partition : InstrToPartition) {
+    if (Partition.first == nullptr)
+      OS << "Default: ";
+    else
+      OS << Partition.first->TheDef->getName() << ": ";
+    StringRef Separator = "";
+    for (unsigned I : Partitions.find(Partition.second)->second.set_bits()) {
+      OS << Separator << I;
+      Separator = ", ";
+    }
+    OS << "\n";
+  }
+}
+
+void GIMatchTreeOpcodePartitioner::generatePartitionSelectorCode(
+    raw_ostream &OS, StringRef Indent) const {
+  OS << Indent << "Partition = -1;\n"
+     << Indent << "switch (MIs[" << InstrID << "]->getOpcode()) {\n";
+  for (const auto &EnumInstr : enumerate(PartitionToInstr)) {
+    if (EnumInstr.value() == nullptr)
+      OS << Indent << "default:";
+    else
+      OS << Indent << "case " << EnumInstr.value()->Namespace
+         << "::" << EnumInstr.value()->TheDef->getName() << ":";
+    OS << " Partition = " << EnumInstr.index() << "; break;\n";
+  }
+  OS << Indent << "}\n"
+     << Indent
+     << "// Default case but without conflicting with potential default case "
+        "in selection.\n"
+     << Indent << "if (Partition == -1) return false;\n";
+}
+
+void GIMatchTreeVRegDefPartitioner::addToPartition(bool Result,
+                                                   unsigned LeafIdx) {
+  auto I = ResultToPartition.find(Result);
+  if (I == ResultToPartition.end()) {
+    ResultToPartition.insert(std::make_pair(Result, PartitionToResult.size()));
+    PartitionToResult.push_back(Result);
+  }
+  I = ResultToPartition.find(Result);
+  auto P = Partitions.find(I->second);
+  if (P == Partitions.end())
+    P = Partitions.insert(std::make_pair(I->second, BitVector())).first;
+  P->second.resize(LeafIdx + 1);
+  P->second.set(LeafIdx);
+}
+
+void GIMatchTreeVRegDefPartitioner::repartition(
+    GIMatchTreeBuilder::LeafVec &Leaves) {
+  Partitions.clear();
+
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    BitVector TraversedEdgesForLeaf(Leaf.value().getMatchDag().getNumEdges());
+
+    // If the instruction isn't declared then we don't care about it. Ignore
+    // it for now and add it to all partitions later once we know what
+    // partitions we have.
+    if (!InstrInfo) {
+      TraversedEdges.push_back(TraversedEdgesForLeaf);
+      continue;
+    }
+
+    // If this node has an use -> def edge from this operand then this
+    // instruction must be in partition 1 (isVRegDef()).
+    bool WantsEdge = false;
+    for (unsigned EIdx : Leaf.value().TraversableEdges.set_bits()) {
+      const auto &E = Leaf.value().getEdge(EIdx);
+      if (E->getFromMI() != InstrInfo->getInstrNode() ||
+          E->getFromMO()->getIdx() != OpIdx || E->isDefToUse())
+        continue;
+
+      // We're looking at the right edge. This leaf wants a vreg def so we'll
+      // put it in partition 1.
+      addToPartition(true, Leaf.index());
+      TraversedEdgesForLeaf.set(EIdx);
+      WantsEdge = true;
+    }
+
+    bool isNotReg = false;
+    if (!WantsEdge && isNotReg) {
+      // If this leaf doesn't have an edge and we _don't_ want a register,
+      // then add it to partition 0.
+      addToPartition(false, Leaf.index());
+    } else if (!WantsEdge) {
+      // If this leaf doesn't have an edge and we don't know what we want,
+      // then add it to partition 0 and 1.
+      addToPartition(false, Leaf.index());
+      addToPartition(true, Leaf.index());
+    }
+
+    TraversedEdges.push_back(TraversedEdgesForLeaf);
+  }
+
+  // Add any leaves that don't care about this instruction to all partitions.
+  for (const auto &Leaf : enumerate(Leaves)) {
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.value().getInstrInfo(InstrID);
+    if (!InstrInfo)
+      for (auto &Partition : Partitions)
+        Partition.second.set(Leaf.index());
+  }
+}
+
+void GIMatchTreeVRegDefPartitioner::applyForPartition(
+    unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
+    GIMatchTreeBuilder &SubBuilder) {
+  BitVector PossibleLeaves = getPossibleLeavesForPartition(PartitionIdx);
+
+  std::vector<BitVector> TraversedEdgesByNewLeaves;
+  // Consume any edges we handled.
+  for (auto &EnumeratedLeaf : enumerate(Builder.getPossibleLeaves())) {
+    if (!PossibleLeaves[EnumeratedLeaf.index()])
+      continue;
+
+    auto &Leaf = EnumeratedLeaf.value();
+    const auto &TraversedEdgesForLeaf = TraversedEdges[EnumeratedLeaf.index()];
+    TraversedEdgesByNewLeaves.push_back(TraversedEdgesForLeaf);
+    Leaf.RemainingEdges.reset(TraversedEdgesForLeaf);
+    Leaf.TraversableEdges.reset(TraversedEdgesForLeaf);
+    SubBuilder.addLeaf(Leaf);
+  }
+
+  // Nothing to do. The only thing we know is that it isn't a vreg-def.
+  if (PartitionToResult[PartitionIdx] == false)
+    return;
+
+  NewInstrID = SubBuilder.allocInstrID();
+
+  GIMatchTreeBuilder::LeafVec &NewLeaves = SubBuilder.getPossibleLeaves();
+  for (const auto I : zip(NewLeaves, TraversedEdgesByNewLeaves)) {
+    auto &Leaf = std::get<0>(I);
+    auto &TraversedEdgesForLeaf = std::get<1>(I);
+    GIMatchTreeInstrInfo *InstrInfo = Leaf.getInstrInfo(InstrID);
+    // Skip any leaves that don't care about this instruction.
+    if (!InstrInfo)
+      continue;
+    for (unsigned EIdx : TraversedEdgesForLeaf.set_bits()) {
+      const GIMatchDagEdge *E = Leaf.getEdge(EIdx);
+      Leaf.declareInstr(E->getToMI(), NewInstrID);
+    }
+  }
+  SubBuilder.addPartitionersForInstr(NewInstrID);
+}
+
+void GIMatchTreeVRegDefPartitioner::emitPartitionResults(
+    raw_ostream &OS) const {
+  OS << "Partitioning by vreg-def would produce " << Partitions.size()
+     << " partitions\n";
+  for (const auto &Partition : Partitions) {
+    OS << Partition.first << " (";
+    emitPartitionName(OS, Partition.first);
+    OS << "): ";
+    StringRef Separator = "";
+    for (unsigned I : Partition.second.set_bits()) {
+      OS << Separator << I;
+      Separator = ", ";
+    }
+    OS << "\n";
+  }
+}
+
+void GIMatchTreeVRegDefPartitioner::generatePartitionSelectorCode(
+    raw_ostream &OS, StringRef Indent) const {
+  OS << Indent << "Partition = -1\n"
+     << Indent << "if (MIs.size() <= NewInstrID) MIs.resize(NewInstrID + 1);\n"
+     << Indent << "MIs[" << NewInstrID << "] = nullptr;\n"
+     << Indent << "if (MIs[" << InstrID << "].getOperand(" << OpIdx
+     << ").isReg()))\n"
+     << Indent << "  MIs[" << NewInstrID << "] = MRI.getVRegDef(MIs[" << InstrID
+     << "].getOperand(" << OpIdx << ").getReg()));\n";
+
+  for (const auto &Pair : ResultToPartition)
+    OS << Indent << "if (MIs[" << NewInstrID << "] "
+       << (Pair.first ? "==" : "!=")
+       << " nullptr) Partition = " << Pair.second << ";\n";
+
+  OS << Indent << "if (Partition == -1) return false;\n";
+}
+
diff --git a/llvm/utils/TableGen/GlobalISel/GIMatchTree.h b/llvm/utils/TableGen/GlobalISel/GIMatchTree.h
new file mode 100644
index 0000000000000..b86f6454589c8
--- /dev/null
+++ b/llvm/utils/TableGen/GlobalISel/GIMatchTree.h
@@ -0,0 +1,629 @@
+//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+#define LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
+
+#include "GIMatchDag.h"
+#include "llvm/ADT/BitVector.h"
+
+namespace llvm {
+class raw_ostream;
+
+class GIMatchTreeBuilder;
+class GIMatchTreePartitioner;
+
+/// Describes the binding of a variable to the matched MIR
+class GIMatchTreeVariableBinding {
+  /// The name of the variable described by this binding.
+  StringRef Name;
+  // The matched instruction it is bound to. 
+  unsigned InstrID;
+  // The matched operand (if appropriate) it is bound to. 
+  Optional<unsigned> OpIdx;
+
+public:
+  GIMatchTreeVariableBinding(StringRef Name, unsigned InstrID,
+                             Optional<unsigned> OpIdx = None)
+      : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {}
+
+  bool isInstr() const { return !OpIdx.hasValue(); }
+  StringRef getName() const { return Name; }
+  unsigned getInstrID() const { return InstrID; }
+  unsigned getOpIdx() const {
+    assert(OpIdx.hasValue() && "Is not an operand binding");
+    return *OpIdx;
+  }
+};
+
+/// Associates a matchable with a leaf of the decision tree.
+class GIMatchTreeLeafInfo {
+public:
+  using const_var_binding_iterator =
+      std::vector<GIMatchTreeVariableBinding>::const_iterator;
+  using UntestedPredicatesTy = SmallVector<const GIMatchDagPredicate *, 1>;
+  using const_untested_predicates_iterator = UntestedPredicatesTy::const_iterator;
+
+protected:
+  /// A name for the matchable. This is primarily for debugging.
+  StringRef Name;
+  /// Where rules have multiple roots, this is which root we're starting from.
+  unsigned RootIdx;
+  /// Opaque data the caller of the tree building code understands.
+  void *Data;
+  /// Has the decision tree covered every edge traversal? If it hasn't then this
+  /// is an unrecoverable error indicating there's something wrong with the
+  /// partitioners.
+  bool IsFullyTraversed;
+  /// Has the decision tree covered every predicate test? If it has, then
+  /// subsequent matchables on the same leaf are unreachable. If it hasn't, the
+  /// code that requested the GIMatchTree is responsible for finishing off any
+  /// remaining predicates.
+  bool IsFullyTested;
+  /// The variable bindings associated with this leaf so far.
+  std::vector<GIMatchTreeVariableBinding> VarBindings;
+  /// Any predicates left untested by the time we reach this leaf.
+  UntestedPredicatesTy UntestedPredicates;
+
+public:
+  GIMatchTreeLeafInfo() { llvm_unreachable("Cannot default-construct"); }
+  GIMatchTreeLeafInfo(StringRef Name, unsigned RootIdx, void *Data)
+      : Name(Name), RootIdx(RootIdx), Data(Data), IsFullyTraversed(false),
+        IsFullyTested(false) {}
+
+  StringRef getName() const { return Name; }
+  unsigned getRootIdx() const { return RootIdx; }
+  template <class Ty> Ty *getTargetData() const {
+    return static_cast<Ty *>(Data);
+  }
+  bool isFullyTraversed() const { return IsFullyTraversed; }
+  void setIsFullyTraversed(bool V) { IsFullyTraversed = V; }
+  bool isFullyTested() const { return IsFullyTested; }
+  void setIsFullyTested(bool V) { IsFullyTested = V; }
+
+  void bindInstrVariable(StringRef Name, unsigned InstrID) {
+    VarBindings.emplace_back(Name, InstrID);
+  }
+  void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) {
+    VarBindings.emplace_back(Name, InstrID, OpIdx);
+  }
+
+  const_var_binding_iterator var_bindings_begin() const {
+    return VarBindings.begin();
+  }
+  const_var_binding_iterator var_bindings_end() const {
+    return VarBindings.end();
+  }
+  iterator_range<const_var_binding_iterator> var_bindings() const {
+    return make_range(VarBindings.begin(), VarBindings.end());
+  }
+  iterator_range<const_untested_predicates_iterator> untested_predicates() const {
+    return make_range(UntestedPredicates.begin(), UntestedPredicates.end());
+  }
+  void addUntestedPredicate(const GIMatchDagPredicate *P) {
+    UntestedPredicates.push_back(P);
+  }
+};
+
+/// The nodes of a decision tree used to perform the match.
+/// This will be used to generate the C++ code or state machine equivalent.
+///
+/// It should be noted that some nodes of this tree (most notably nodes handling
+/// def -> use edges) will need to iterate over several possible matches. As
+/// such, code generated from this will sometimes need to support backtracking.
+class GIMatchTree {
+  using LeafVector = std::vector<GIMatchTreeLeafInfo>;
+
+  /// The partitioner that has been chosen for this node. This may be nullptr if
+  /// a partitioner hasn't been chosen yet or if the node is a leaf.
+  std::unique_ptr<GIMatchTreePartitioner> Partitioner;
+  /// All the leaves that are possible for this node of the tree.
+  /// Note: This should be emptied after the tree is built when there are
+  /// children but this currently isn't done to aid debuggability of the DOT
+  /// graph for the decision tree.
+  LeafVector PossibleLeaves;
+  /// The children of this node. The index into this array must match the index
+  /// chosen by the partitioner.
+  std::vector<GIMatchTree> Children;
+
+  void writeDOTGraphNode(raw_ostream &OS) const;
+  void writeDOTGraphEdges(raw_ostream &OS) const;
+
+public:
+  void writeDOTGraph(raw_ostream &OS) const;
+
+  void setNumChildren(unsigned Num) { Children.resize(Num); }
+  void addPossibleLeaf(const GIMatchTreeLeafInfo &V, bool IsFullyTraversed,
+                       bool IsFullyTested) {
+    PossibleLeaves.push_back(V);
+    PossibleLeaves.back().setIsFullyTraversed(IsFullyTraversed);
+    PossibleLeaves.back().setIsFullyTested(IsFullyTested);
+  }
+  void dropLeavesAfter(size_t Length) {
+    if (PossibleLeaves.size() > Length)
+      PossibleLeaves.resize(Length);
+  }
+  void setPartitioner(std::unique_ptr<GIMatchTreePartitioner> &&V) {
+    Partitioner = std::move(V);
+  }
+  GIMatchTreePartitioner *getPartitioner() const { return Partitioner.get(); }
+
+  std::vector<GIMatchTree>::iterator children_begin() {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::iterator children_end() { return Children.end(); }
+  iterator_range<std::vector<GIMatchTree>::iterator> children() {
+    return make_range(children_begin(), children_end());
+  }
+  std::vector<GIMatchTree>::const_iterator children_begin() const {
+    return Children.begin();
+  }
+  std::vector<GIMatchTree>::const_iterator children_end() const {
+    return Children.end();
+  }
+  iterator_range<std::vector<GIMatchTree>::const_iterator> children() const {
+    return make_range(children_begin(), children_end());
+  }
+
+  LeafVector::const_iterator possible_leaves_begin() const {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::const_iterator possible_leaves_end() const {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::const_iterator>
+  possible_leaves() const {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+  LeafVector::iterator possible_leaves_begin() {
+    return PossibleLeaves.begin();
+  }
+  LeafVector::iterator possible_leaves_end() {
+    return PossibleLeaves.end();
+  }
+  iterator_range<LeafVector::iterator> possible_leaves() {
+    return make_range(possible_leaves_begin(), possible_leaves_end());
+  }
+};
+
+/// Record information that is known about the instruction bound to this ID and
+/// GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeInstrInfo to bind the shared IDs to an instr node in its
+/// DAG.
+///
+/// For example, if we know that there are 3 operands. We can record it here to
+/// elide duplicate checks.
+class GIMatchTreeInstrInfo {
+  /// The instruction ID for the matched instruction.
+  unsigned ID;
+  /// The corresponding instruction node in the MatchDAG.
+  const GIMatchDagInstr *InstrNode;
+
+public:
+  GIMatchTreeInstrInfo(unsigned ID, const GIMatchDagInstr *InstrNode)
+      : ID(ID), InstrNode(InstrNode) {}
+
+  unsigned getID() const { return ID; }
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+};
+
+/// Record information that is known about the operand bound to this ID, OpIdx,
+/// and GIMatchDagInstrNode. Every rule gets its own set of
+/// GIMatchTreeOperandInfo to bind the shared IDs to an operand of an
+/// instr node from its DAG.
+///
+/// For example, if we know that there the operand is a register. We can record
+/// it here to elide duplicate checks.
+class GIMatchTreeOperandInfo {
+  /// The corresponding instruction node in the MatchDAG that the operand
+  /// belongs to.
+  const GIMatchDagInstr *InstrNode;
+  unsigned OpIdx;
+
+public:
+  GIMatchTreeOperandInfo(const GIMatchDagInstr *InstrNode, unsigned OpIdx)
+      : InstrNode(InstrNode), OpIdx(OpIdx) {}
+
+  const GIMatchDagInstr *getInstrNode() const { return InstrNode; }
+  unsigned getOpIdx() const { return OpIdx; }
+};
+
+/// Represent a leaf of the match tree and any working data we need to build the
+/// tree.
+///
+/// It's important to note that each rule can have multiple
+/// GIMatchTreeBuilderLeafInfo's since the partitioners do not always partition
+/// into mutually-exclusive partitions. For example:
+///   R1: (FOO ..., ...)
+///   R2: (oneof(FOO, BAR) ..., ...)
+/// will partition by opcode into two partitions FOO=>[R1, R2], and BAR=>[R2]
+///
+/// As an optimization, all instructions, edges, and predicates in the DAGs are
+/// numbered and tracked in BitVectors. As such, the GIMatchDAG must not be
+/// modified once construction of the tree has begun.
+class GIMatchTreeBuilderLeafInfo {
+protected:
+  GIMatchTreeBuilder &Builder;
+  GIMatchTreeLeafInfo Info;
+  const GIMatchDag &MatchDag;
+  /// The association between GIMatchDagInstr* and GIMatchTreeInstrInfo.
+  /// The primary reason for this members existence is to allow the use of
+  /// InstrIDToInfo.lookup() since that requires that the value is
+  /// default-constructible.
+  DenseMap<const GIMatchDagInstr *, GIMatchTreeInstrInfo> InstrNodeToInfo;
+  /// The instruction information for a given ID in the context of this
+  /// particular leaf.
+  DenseMap<unsigned, GIMatchTreeInstrInfo *> InstrIDToInfo;
+  /// The operand information for a given ID and OpIdx in the context of this
+  /// particular leaf.
+  DenseMap<std::pair<unsigned, unsigned>, GIMatchTreeOperandInfo>
+      OperandIDToInfo;
+
+public:
+  /// The remaining instrs/edges/predicates to visit
+  BitVector RemainingInstrNodes;
+  BitVector RemainingEdges;
+  BitVector RemainingPredicates;
+
+  // The remaining predicate dependencies for each predicate
+  std::vector<BitVector> UnsatisfiedPredDepsForPred;
+
+  /// The edges/predicates we can visit as a result of the declare*() calls we
+  /// have already made. We don't need an instrs version since edges imply the
+  /// instr.
+  BitVector TraversableEdges;
+  BitVector TestablePredicates;
+
+  /// Map predicates from the DAG to their position in the DAG predicate
+  /// iterators.
+  DenseMap<GIMatchDagPredicate *, unsigned> PredicateIDs;
+  /// Map predicate dependency edges from the DAG to their position in the DAG
+  /// predicate dependency iterators.
+  DenseMap<GIMatchDagPredicateDependencyEdge *, unsigned> PredicateDepIDs;
+
+public:
+  GIMatchTreeBuilderLeafInfo(GIMatchTreeBuilder &Builder, StringRef Name,
+                             unsigned RootIdx, const GIMatchDag &MatchDag,
+                             void *Data);
+
+  StringRef getName() const { return Info.getName(); }
+  GIMatchTreeLeafInfo &getInfo() { return Info; }
+  const GIMatchTreeLeafInfo &getInfo() const { return Info; }
+  const GIMatchDag &getMatchDag() const { return MatchDag; }
+  unsigned getRootIdx() const { return Info.getRootIdx(); }
+
+  /// Has this DAG been fully traversed. This must be true by the time the tree
+  /// builder finishes.
+  bool isFullyTraversed() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none();
+  }
+
+  /// Has this DAG been fully tested. This hould be true by the time the tree
+  /// builder finishes but clients can finish any untested predicates left over
+  /// if it's not true.
+  bool isFullyTested() const {
+    // We don't need UnsatisfiedPredDepsForPred because RemainingPredicates
+    // can't be all-zero without satisfying all the dependencies. The same is
+    // almost true for Edges and Instrs but it's possible to have Instrs without
+    // Edges.
+    return RemainingInstrNodes.none() && RemainingEdges.none() &&
+           RemainingPredicates.none();
+  }
+
+  const GIMatchDagInstr *getInstr(unsigned Idx) const {
+    return *(MatchDag.instr_nodes_begin() + Idx);
+  }
+  const GIMatchDagEdge *getEdge(unsigned Idx) const {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  GIMatchDagEdge *getEdge(unsigned Idx) {
+    return *(MatchDag.edges_begin() + Idx);
+  }
+  const GIMatchDagPredicate *getPredicate(unsigned Idx) const {
+    return *(MatchDag.predicates_begin() + Idx);
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_instrs() const {
+    return RemainingInstrNodes.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_edges() const {
+    return RemainingEdges.set_bits();
+  }
+  iterator_range<llvm::BitVector::const_set_bits_iterator>
+  untested_predicates() const {
+    return RemainingPredicates.set_bits();
+  }
+
+  /// Bind an instr node to the given ID and clear any blocking dependencies
+  /// that were waiting for it.
+  void declareInstr(const GIMatchDagInstr *Instr, unsigned ID);
+
+  /// Bind an operand to the given ID and OpIdx and clear any blocking
+  /// dependencies that were waiting for it.
+  void declareOperand(unsigned InstrID, unsigned OpIdx);
+
+  GIMatchTreeInstrInfo *getInstrInfo(unsigned ID) const {
+    auto I = InstrIDToInfo.find(ID);
+    if (I != InstrIDToInfo.end())
+      return I->second;
+    return nullptr;
+  }
+
+  void dump(raw_ostream &OS) const {
+    OS << "Leaf " << getName() << " for root #" << getRootIdx() << "\n";
+    MatchDag.print(OS);
+    for (const auto &I : InstrIDToInfo)
+      OS << "Declared Instr #" << I.first << "\n";
+    for (const auto &I : OperandIDToInfo)
+      OS << "Declared Instr #" << I.first.first << ", Op #" << I.first.second
+         << "\n";
+    OS << RemainingInstrNodes.count() << " untested instrs of "
+       << RemainingInstrNodes.size() << "\n";
+    OS << RemainingEdges.count() << " untested edges of "
+       << RemainingEdges.size() << "\n";
+    OS << RemainingPredicates.count() << " untested predicates of "
+       << RemainingPredicates.size() << "\n";
+
+    OS << TraversableEdges.count() << " edges could be traversed\n";
+    OS << TestablePredicates.count() << " predicates could be tested\n";
+  }
+};
+
+/// The tree builder has a fairly tough job. It's purpose is to merge all the
+/// DAGs from the ruleset into a decision tree that walks all of them
+/// simultaneously and identifies the rule that was matched. In addition to
+/// that, it also needs to find the most efficient order to make decisions
+/// without violating any dependencies and ensure that every DAG covers every
+/// instr/edge/predicate.
+class GIMatchTreeBuilder {
+public:
+  using LeafVec = std::vector<GIMatchTreeBuilderLeafInfo>;
+
+protected:
+  /// The leaves that the resulting decision tree will distinguish.
+  LeafVec Leaves;
+  /// The tree node being constructed.
+  GIMatchTree *TreeNode;
+  /// The builders for each subtree resulting from the current decision.
+  std::vector<GIMatchTreeBuilder> SubtreeBuilders;
+  /// The possible partitioners we could apply right now.
+  std::vector<std::unique_ptr<GIMatchTreePartitioner>> Partitioners;
+  /// The next instruction ID to allocate when requested by the chosen
+  /// Partitioner.
+  unsigned NextInstrID;
+
+  /// Use any context we have stored to cull partitioners that only test things
+  /// we already know. At the time of writing, there's no need to do anything
+  /// here but it will become important once, for example, there is a
+  /// num-operands and an opcode partitioner. This is because applying an opcode
+  /// partitioner (usually) makes the number of operands known which makes
+  /// additional checking pointless.
+  void filterRedundantPartitioners();
+
+  /// Evaluate the available partioners and select the best one at the moment.
+  void evaluatePartitioners();
+
+  /// Construct the current tree node.
+  void runStep();
+
+public:
+  GIMatchTreeBuilder(unsigned NextInstrID) : NextInstrID(NextInstrID) {}
+  GIMatchTreeBuilder(GIMatchTree *TreeNode, unsigned NextInstrID)
+      : TreeNode(TreeNode), NextInstrID(NextInstrID) {}
+
+  void addLeaf(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag,
+               void *Data) {
+    Leaves.emplace_back(*this, Name, RootIdx, MatchDag, Data);
+  }
+  void addLeaf(const GIMatchTreeBuilderLeafInfo &L) { Leaves.push_back(L); }
+  void addPartitioner(std::unique_ptr<GIMatchTreePartitioner> P) {
+    Partitioners.push_back(std::move(P));
+  }
+  void addPartitionersForInstr(unsigned InstrIdx);
+  void addPartitionersForOperand(unsigned InstrID, unsigned OpIdx);
+
+  LeafVec &getPossibleLeaves() { return Leaves; }
+
+  unsigned allocInstrID() { return NextInstrID++; }
+
+  /// Construct the decision tree.
+  std::unique_ptr<GIMatchTree> run();
+};
+
+/// Partitioners are the core of the tree builder and are unfortunately rather
+/// tricky to write.
+class GIMatchTreePartitioner {
+protected:
+  /// The partitions resulting from applying the partitioner to the possible
+  /// leaves. The keys must be consecutive integers starting from 0. This can
+  /// lead to some unfortunate situations where partitioners test a predicate
+  /// and use 0 for success and 1 for failure if the ruleset encounters a
+  /// success case first but is necessary to assign the partition to one of the
+  /// tree nodes children. As a result, you usually need some kind of
+  /// indirection to map the natural keys (e.g. ptrs/bools) to this linear
+  /// sequence. The values are a bitvector indicating which leaves belong to
+  /// this partition.
+  DenseMap<unsigned, BitVector> Partitions;
+
+public:
+  virtual ~GIMatchTreePartitioner() {}
+  virtual std::unique_ptr<GIMatchTreePartitioner> clone() const = 0;
+
+  /// Determines which partitions the given leaves belong to. A leaf may belong
+  /// to multiple partitions in which case it will be duplicated during
+  /// applyForPartition().
+  ///
+  /// This function can be rather complicated. A few particular things to be
+  /// aware of include:
+  /// * One leaf can be assigned to multiple partitions when there's some
+  ///   ambiguity.
+  /// * Not all DAG's for the leaves may be able to perform the test. For
+  ///   example, the opcode partitiioner must account for one DAG being a
+  ///   superset of another such as [(ADD ..., ..., ...)], and [(MUL t, ...,
+  ///   ...), (ADD ..., t, ...)]
+  /// * Attaching meaning to a particular partition index will generally not
+  ///   work due to the '0, 1, ..., n' requirement. You might encounter cases
+  ///   where only partition 1 is seen, leaving a missing 0.
+  /// * Finding a specific predicate such as the opcode predicate for a specific
+  ///   instruction is non-trivial. It's often O(NumPredicates), leading to
+  ///   O(NumPredicates*NumRules) when applied to the whole ruleset. The good
+  ///   news there is that n is typically small thanks to predicate dependencies
+  ///   limiting how many are testable at once. Also, with opcode and type
+  ///   predicates being so frequent the value of m drops very fast too. It
+  ///   wouldn't be terribly surprising to see a 10k ruleset drop down to an
+  ///   average of 100 leaves per partition after a single opcode partitioner.
+  /// * The same goes for finding specific edges. The need to traverse them in
+  ///   dependency order dramatically limits the search space at any given
+  ///   moment.
+  /// * If you need to add a leaf to all partitions, make sure you don't forget
+  ///   them when adding partitions later.
+  virtual void repartition(GIMatchTreeBuilder::LeafVec &Leaves) = 0;
+
+  /// Delegate the leaves for a given partition to the corresponding subbuilder,
+  /// update any recorded context for this partition (e.g. allocate instr id's
+  /// for instrs recorder by the current node), and clear any blocking
+  /// dependencies this partitioner resolved.
+  virtual void applyForPartition(unsigned PartitionIdx,
+                                 GIMatchTreeBuilder &Builder,
+                                 GIMatchTreeBuilder &SubBuilder) = 0;
+
+  /// Return a BitVector indicating which leaves should be transferred to the
+  /// specified partition. Note that the same leaf can be indicated for multiple
+  /// partitions.
+  BitVector getPossibleLeavesForPartition(unsigned Idx) {
+    const auto &I = Partitions.find(Idx);
+    assert(I != Partitions.end() && "Requested non-existant partition");
+    return I->second;
+  }
+
+  size_t getNumPartitions() const { return Partitions.size(); }
+  size_t getNumLeavesWithDupes() const {
+    size_t S = 0;
+    for (const auto &P : Partitions)
+      S += P.second.size();
+    return S;
+  }
+
+  /// Emit a brief description of the partitioner suitable for debug printing or
+  /// use in a DOT graph.
+  virtual void emitDescription(raw_ostream &OS) const = 0;
+  /// Emit a label for the given partition suitable for debug printing or use in
+  /// a DOT graph.
+  virtual void emitPartitionName(raw_ostream &OS, unsigned Idx) const = 0;
+
+  /// Emit a long description of how the partitioner partitions the leaves.
+  virtual void emitPartitionResults(raw_ostream &OS) const = 0;
+
+  /// Generate code to select between partitions based on the MIR being matched.
+  /// This is typically a switch statement that picks a partition index.
+  virtual void generatePartitionSelectorCode(raw_ostream &OS,
+                                             StringRef Indent) const = 0;
+};
+
+/// Partition according to the opcode of the instruction.
+///
+/// Numbers CodeGenInstr ptrs for use as partition ID's. One special partition,
+/// nullptr, represents the case where the instruction isn't known.
+///
+/// * If the opcode can be tested and is a single opcode, create the partition
+///   for that opcode and assign the leaf to it. This partition no longer needs
+///   to test the opcode, and many details about the instruction will usually
+///   become known (e.g. number of operands for non-variadic instrs) via the
+///   CodeGenInstr ptr.
+/// * (not implemented yet) If the opcode can be tested and is a choice of
+///   opcodes, then the leaf can be treated like the single-opcode case but must
+///   be added to all relevant partitions and not quite as much becomes known as
+///   a result. That said, multiple-choice opcodes are likely similar enough
+///   (because if they aren't then handling them together makes little sense)
+///   that plenty still becomes known. The main implementation issue with this
+///   is having a description to represent the commonality between instructions.
+/// * If the opcode is not tested, the leaf must be added to all partitions
+///   including the wildcard nullptr partition. What becomes known as a result
+///   varies between partitions.
+/// * If the instruction to be tested is not declared then add the leaf to all
+///   partitions. This occurs when we encounter one rule that is a superset of
+///   the other and we are still matching the remainder of the superset. The
+///   result is that the cases that don't match the superset will match the
+///   subset rule, while the ones that do match the superset will match either
+///   (which one is algorithm dependent but will usually be the superset).
+class GIMatchTreeOpcodePartitioner : public GIMatchTreePartitioner {
+  unsigned InstrID;
+  DenseMap<const CodeGenInstruction *, unsigned> InstrToPartition;
+  std::vector<const CodeGenInstruction *> PartitionToInstr;
+  std::vector<BitVector> TestedPredicates;
+
+public:
+  GIMatchTreeOpcodePartitioner(unsigned InstrID) : InstrID(InstrID) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeOpcodePartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << InstrID << "].getOpcode()";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override;
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned Idx, GIMatchTreeBuilder &SubBuilder,
+                         GIMatchTreeBuilder &Builder) override;
+
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+class GIMatchTreeVRegDefPartitioner : public GIMatchTreePartitioner {
+  unsigned NewInstrID = -1;
+  unsigned InstrID;
+  unsigned OpIdx;
+  std::vector<BitVector> TraversedEdges;
+  DenseMap<unsigned, unsigned> ResultToPartition;
+  std::vector<bool> PartitionToResult;
+
+  void addToPartition(bool Result, unsigned LeafIdx);
+
+public:
+  GIMatchTreeVRegDefPartitioner(unsigned InstrID, unsigned OpIdx)
+      : InstrID(InstrID), OpIdx(OpIdx) {}
+
+  std::unique_ptr<GIMatchTreePartitioner> clone() const override {
+    return std::make_unique<GIMatchTreeVRegDefPartitioner>(*this);
+  }
+
+  void emitDescription(raw_ostream &OS) const override {
+    OS << "MI[" << NewInstrID << "] = getVRegDef(MI[" << InstrID
+       << "].getOperand(" << OpIdx << "))";
+  }
+
+  void emitPartitionName(raw_ostream &OS, unsigned Idx) const override {
+    bool Result = PartitionToResult[Idx];
+    if (Result)
+      OS << "true";
+    else
+      OS << "false";
+  }
+
+  void repartition(GIMatchTreeBuilder::LeafVec &Leaves) override;
+  void applyForPartition(unsigned PartitionIdx, GIMatchTreeBuilder &Builder,
+                         GIMatchTreeBuilder &SubBuilder) override;
+  void emitPartitionResults(raw_ostream &OS) const override;
+
+  void generatePartitionSelectorCode(raw_ostream &OS,
+                                     StringRef Indent) const override;
+};
+
+} // end namespace llvm
+#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREE_H
diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index d8d4c9f4f55cf..c14294951cc11 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -609,7 +609,7 @@ MatchTableRecord MatchTable::LineBreak = {
 void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
                             const MatchTable &Table) const {
   bool UseLineComment =
-      LineBreakIsNextAfterThis | (Flags & MTRF_LineBreakFollows);
+      LineBreakIsNextAfterThis || (Flags & MTRF_LineBreakFollows);
   if (Flags & (MTRF_JumpTarget | MTRF_CommaFollows))
     UseLineComment = false;
 
@@ -620,7 +620,7 @@ void MatchTableRecord::emit(raw_ostream &OS, bool LineBreakIsNextAfterThis,
   if (Flags & MTRF_Label)
     OS << ": @" << Table.getLabelIndex(LabelID);
 
-  if (Flags & MTRF_Comment && !UseLineComment)
+  if ((Flags & MTRF_Comment) && !UseLineComment)
     OS << "*/";
 
   if (Flags & MTRF_JumpTarget) {
@@ -1181,7 +1181,7 @@ public:
     TypeIDValues.clear();
 
     unsigned ID = 0;
-    for (const LLTCodeGen LLTy : KnownTypes)
+    for (const LLTCodeGen &LLTy : KnownTypes)
       TypeIDValues[LLTy] = ID++;
   }
 
@@ -1707,7 +1707,7 @@ public:
   }
 
   StringRef getOpcode() const { return I->TheDef->getName(); }
-  unsigned getNumOperands() const { return I->Operands.size(); }
+  bool isVariadicNumOperands() const { return I->Operands.isVariadic; }
 
   StringRef getOperandType(unsigned OpIdx) const {
     return I->Operands[OpIdx].OperandType;
@@ -2153,7 +2153,7 @@ public:
         return false;
     }
 
-    for (const auto &Operand : zip(Operands, B.Operands)) {
+    for (auto Operand : zip(Operands, B.Operands)) {
       if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand)))
         return true;
       if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand)))
@@ -2273,7 +2273,7 @@ void InstructionMatcher::optimize() {
 
   Stash.push_back(predicates_pop_front());
   if (Stash.back().get() == &OpcMatcher) {
-    if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands())
+    if (NumOperandsCheck && OpcMatcher.isVariadicNumOperands())
       Stash.emplace_back(
           new InstructionNumOperandsMatcher(InsnVarID, getNumOperands()));
     NumOperandsCheck = false;
@@ -2318,7 +2318,8 @@ public:
     OR_Register,
     OR_TempRegister,
     OR_ComplexPattern,
-    OR_Custom
+    OR_Custom,
+    OR_CustomOperand
   };
 
 protected:
@@ -2726,6 +2727,38 @@ public:
   }
 };
 
+class CustomOperandRenderer : public OperandRenderer {
+protected:
+  unsigned InsnID;
+  const Record &Renderer;
+  /// The name of the operand.
+  const std::string SymbolicName;
+
+public:
+  CustomOperandRenderer(unsigned InsnID, const Record &Renderer,
+                        StringRef SymbolicName)
+      : OperandRenderer(OR_CustomOperand), InsnID(InsnID), Renderer(Renderer),
+        SymbolicName(SymbolicName) {}
+
+  static bool classof(const OperandRenderer *R) {
+    return R->getKind() == OR_CustomOperand;
+  }
+
+  void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    const OperandMatcher &OpdMatcher = Rule.getOperandMatcher(SymbolicName);
+    Table << MatchTable::Opcode("GIR_CustomOperandRenderer")
+          << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("OldInsnID")
+          << MatchTable::IntValue(OpdMatcher.getInsnVarID())
+          << MatchTable::Comment("OpIdx")
+          << MatchTable::IntValue(OpdMatcher.getOpIdx())
+          << MatchTable::Comment("OperandRenderer")
+          << MatchTable::NamedValue(
+            "GICR_" + Renderer.getValueAsString("RendererFn").str())
+          << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
+  }
+};
+
 /// An action taken when all Matcher predicates succeeded for a parent rule.
 ///
 /// Typical actions include:
@@ -3159,7 +3192,7 @@ bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
   if (Matchers.size() < B.Matchers.size())
     return false;
 
-  for (const auto &Matcher : zip(Matchers, B.Matchers)) {
+  for (auto Matcher : zip(Matchers, B.Matchers)) {
     if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher)))
       return true;
     if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher)))
@@ -3281,8 +3314,8 @@ private:
                                            unsigned &TempOpIdx) const;
   Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
                            const TreePatternNode *SrcChild,
-                           bool OperandIsAPointer, unsigned OpIdx,
-                           unsigned &TempOpIdx);
+                           bool OperandIsAPointer, bool OperandIsImmArg,
+                           unsigned OpIdx, unsigned &TempOpIdx);
 
   Expected<BuildMIAction &> createAndImportInstructionRenderer(
       RuleMatcher &M, InstructionMatcher &InsnMatcher,
@@ -3722,9 +3755,19 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
     for (unsigned i = 0; i != NumChildren; ++i) {
       TreePatternNode *SrcChild = Src->getChild(i);
 
+      // We need to determine the meaning of a literal integer based on the
+      // context. If this is a field required to be an immediate (such as an
+      // immarg intrinsic argument), the required predicates are different than
+      // a constant which may be materialized in a register. If we have an
+      // argument that is required to be an immediate, we should not emit an LLT
+      // type check, and should not be looking for a G_CONSTANT defined
+      // register.
+      bool OperandIsImmArg = SrcGIOrNull->isOperandImmArg(i);
+
       // 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);
 
       if (IsIntrinsic) {
@@ -3737,16 +3780,17 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
           continue;
         }
 
-        // We have to check intrinsics for llvm_anyptr_ty parameters.
+        // We have to check intrinsics for llvm_anyptr_ty and immarg parameters.
         //
         // Note that we have to look at the i-1th parameter, because we don't
         // have the intrinsic ID in the intrinsic's parameter list.
         OperandIsAPointer |= II->isParamAPointer(i - 1);
+        OperandIsImmArg |= II->isParamImmArg(i - 1);
       }
 
       if (auto Error =
               importChildMatcher(Rule, InsnMatcher, SrcChild, OperandIsAPointer,
-                                 OpIdx++, TempOpIdx))
+                                 OperandIsImmArg, OpIdx++, TempOpIdx))
         return std::move(Error);
     }
   }
@@ -3784,12 +3828,10 @@ static StringRef getSrcChildName(const TreePatternNode *SrcChild,
   return SrcChildName;
 }
 
-Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
-                                            InstructionMatcher &InsnMatcher,
-                                            const TreePatternNode *SrcChild,
-                                            bool OperandIsAPointer,
-                                            unsigned OpIdx,
-                                            unsigned &TempOpIdx) {
+Error GlobalISelEmitter::importChildMatcher(
+    RuleMatcher &Rule, InstructionMatcher &InsnMatcher,
+    const TreePatternNode *SrcChild, bool OperandIsAPointer,
+    bool OperandIsImmArg, unsigned OpIdx, unsigned &TempOpIdx) {
 
   Record *PhysReg = nullptr;
   StringRef SrcChildName = getSrcChildName(SrcChild, PhysReg);
@@ -3819,10 +3861,14 @@ Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
     }
   }
 
-  if (auto Error =
-          OM.addTypeCheckPredicate(ChildTypes.front(), OperandIsAPointer))
-    return failedImport(toString(std::move(Error)) + " for Src operand (" +
-                        to_string(*SrcChild) + ")");
+  // Immediate arguments have no meaningful type to check as they don't have
+  // registers.
+  if (!OperandIsImmArg) {
+    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()) {
@@ -3873,7 +3919,13 @@ Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule,
 
   // Check for constant immediates.
   if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) {
-    OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
+    if (OperandIsImmArg) {
+      // Checks for argument directly in operand list
+      OM.addPredicate<LiteralIntOperandMatcher>(ChildInt->getValue());
+    } else {
+      // Checks for materialized constant
+      OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue());
+    }
     return Error::success();
   }
 
@@ -3939,12 +3991,22 @@ Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer(
   }
 
   if (!DstChild->isLeaf()) {
-
     if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) {
       auto Child = DstChild->getChild(0);
       auto I = SDNodeXFormEquivs.find(DstChild->getOperator());
       if (I != SDNodeXFormEquivs.end()) {
-        DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName());
+        Record *XFormOpc = DstChild->getOperator()->getValueAsDef("Opcode");
+        if (XFormOpc->getName() == "timm") {
+          // If this is a TargetConstant, there won't be a corresponding
+          // instruction to transform. Instead, this will refer directly to an
+          // operand in an instruction's operand list.
+          DstMIBuilder.addRenderer<CustomOperandRenderer>(*I->second,
+                                                          Child->getName());
+        } else {
+          DstMIBuilder.addRenderer<CustomRenderer>(*I->second,
+                                                   Child->getName());
+        }
+
         return InsertPt;
       }
       return failedImport("SDNodeXForm " + Child->getName() +
@@ -4309,18 +4371,48 @@ Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderers(
     ExpectedDstINumUses--;
   }
 
+  // NumResults - This is the number of results produced by the instruction in
+  // the "outs" list.
+  unsigned NumResults = OrigDstI->Operands.NumDefs;
+
+  // Number of operands we know the output instruction must have. If it is
+  // variadic, we could have more operands.
+  unsigned NumFixedOperands = DstI->Operands.size();
+
+  // Loop over all of the fixed operands of the instruction pattern, emitting
+  // code to fill them all in. The node 'N' usually has number children equal to
+  // the number of input operands of the instruction.  However, in cases where
+  // there are predicate operands for an instruction, we need to fill in the
+  // 'execute always' values. Match up the node operands to the instruction
+  // operands to do this.
   unsigned Child = 0;
+
+  // Similarly to the code in TreePatternNode::ApplyTypeConstraints, count the
+  // number of operands at the end of the list which have default values.
+  // Those can come from the pattern if it provides enough arguments, or be
+  // filled in with the default if the pattern hasn't provided them. But any
+  // operand with a default value _before_ the last mandatory one will be
+  // filled in with their defaults unconditionally.
+  unsigned NonOverridableOperands = NumFixedOperands;
+  while (NonOverridableOperands > NumResults &&
+         CGP.operandHasDefault(DstI->Operands[NonOverridableOperands - 1].Rec))
+    --NonOverridableOperands;
+
   unsigned NumDefaultOps = 0;
   for (unsigned I = 0; I != DstINumUses; ++I) {
-    const CGIOperandList::OperandInfo &DstIOperand =
-        DstI->Operands[DstI->Operands.NumDefs + I];
+    unsigned InstOpNo = DstI->Operands.NumDefs + I;
+
+    // Determine what to emit for this operand.
+    Record *OperandNode = DstI->Operands[InstOpNo].Rec;
 
     // If the operand has default values, introduce them now.
-    // FIXME: Until we have a decent test case that dictates we should do
-    // otherwise, we're going to assume that operands with default values cannot
-    // be specified in the patterns. Therefore, adding them will not cause us to
-    // end up with too many rendered operands.
-    if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) {
+    if (CGP.operandHasDefault(OperandNode) &&
+        (InstOpNo < NonOverridableOperands || Child >= Dst->getNumChildren())) {
+      // This is a predicate or optional def operand which the pattern has not
+      // overridden, or which we aren't letting it override; emit the 'default
+      // ops' operands.
+
+      const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[InstOpNo];
       DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps");
       if (auto Error = importDefaultOperandRenderers(
             InsertPt, M, DstMIBuilder, DefaultOps))
@@ -5082,7 +5174,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
      << "  typedef void(" << Target.getName()
      << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const "
-        "MachineInstr&) "
+        "MachineInstr&, int) "
         "const;\n"
      << "  const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, "
         "CustomRendererFn> "
@@ -5127,8 +5219,23 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
                });
 
   SubtargetFeatureInfo::emitComputeAvailableFeatures(
-      Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
+    Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures",
       ModuleFeatures, OS);
+
+
+  OS << "void " << Target.getName() << "InstructionSelector"
+    "::setupGeneratedPerFunctionState(MachineFunction &MF) {\n"
+    "  AvailableFunctionFeatures = computeAvailableFunctionFeatures("
+    "(const " << Target.getName() << "Subtarget*)&MF.getSubtarget(), &MF);\n"
+    "}\n";
+
+  if (Target.getName() == "X86" || Target.getName() == "AArch64") {
+    // TODO: Implement PGSO.
+    OS << "static bool shouldOptForSize(const MachineFunction *MF) {\n";
+    OS << "    return MF->getFunction().hasOptSize();\n";
+    OS << "}\n\n";
+  }
+
   SubtargetFeatureInfo::emitComputeAvailableFeatures(
       Target.getName(), "InstructionSelector",
       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
@@ -5168,7 +5275,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
       return true;
     if (A.size() > B.size())
       return false;
-    for (const auto &Pair : zip(A, B)) {
+    for (auto Pair : zip(A, B)) {
       if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
         return true;
       if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
@@ -5245,7 +5352,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
   OS << Target.getName() << "InstructionSelector::CustomRendererFn\n"
      << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n"
-     << "  nullptr, // GICP_Invalid\n";
+     << "  nullptr, // GICR_Invalid\n";
   for (const auto &Record : CustomRendererFns)
     OS << "  &" << Target.getName()
        << "InstructionSelector::" << Record->getValueAsString("RendererFn")
@@ -5273,10 +5380,6 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
         "&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 "
-        "than per-insn.\n"
-     << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
-        "&MF);\n"
      << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
      << "  NewMIVector OutMIs;\n"
      << "  State.MIs.clear();\n"
@@ -5312,6 +5415,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
      << "computeAvailableFunctionFeatures(const " << Target.getName()
      << "Subtarget *Subtarget,\n"
      << "                                 const MachineFunction *MF) const;\n"
+     << "void setupGeneratedPerFunctionState(MachineFunction &MF) override;\n"
      << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n";
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n"
diff --git a/llvm/utils/TableGen/InstrDocsEmitter.cpp b/llvm/utils/TableGen/InstrDocsEmitter.cpp
index 45fa936b9574b..07efa18854098 100644
--- a/llvm/utils/TableGen/InstrDocsEmitter.cpp
+++ b/llvm/utils/TableGen/InstrDocsEmitter.cpp
@@ -138,6 +138,7 @@ void EmitInstrDocs(RecordKeeper &RK, raw_ostream &OS) {
     FLAG(isConvergent)
     FLAG(hasNoSchedulingInfo)
     FLAG(variadicOpsAreDefs)
+    FLAG(isAuthenticated)
     if (!FlagStrings.empty()) {
       OS << "Flags: ";
       bool IsFirst = true;
diff --git a/llvm/utils/TableGen/InstrInfoEmitter.cpp b/llvm/utils/TableGen/InstrInfoEmitter.cpp
index 300ba36a70074..6ab58bd26a2c8 100644
--- a/llvm/utils/TableGen/InstrInfoEmitter.cpp
+++ b/llvm/utils/TableGen/InstrInfoEmitter.cpp
@@ -164,6 +164,11 @@ InstrInfoEmitter::GetOperandInfo(const CodeGenInstruction &Inst) {
       if (Op.Rec->isSubClassOf("OptionalDefOperand"))
         Res += "|(1<<MCOI::OptionalDef)";
 
+      // Branch target operands.  Check to see if the original unexpanded
+      // operand was of type BranchTargetOperand.
+      if (Op.Rec->isSubClassOf("BranchTargetOperand"))
+        Res += "|(1<<MCOI::BranchTarget)";
+
       // Fill in operand type.
       Res += ", ";
       assert(!Op.OperandType.empty() && "Invalid operand type.");
@@ -703,6 +708,7 @@ void InstrInfoEmitter::emitRecord(const CodeGenInstruction &Inst, unsigned Num,
   if (Inst.isInsertSubreg) OS << "|(1ULL<<MCID::InsertSubreg)";
   if (Inst.isConvergent) OS << "|(1ULL<<MCID::Convergent)";
   if (Inst.variadicOpsAreDefs) OS << "|(1ULL<<MCID::VariadicOpsAreDefs)";
+  if (Inst.isAuthenticated) OS << "|(1ULL<<MCID::Authenticated)";
 
   // Emit all of the target-specific flags...
   BitsInit *TSF = Inst.TheDef->getValueAsBitsInit("TSFlags");
diff --git a/llvm/utils/TableGen/IntrinsicEmitter.cpp b/llvm/utils/TableGen/IntrinsicEmitter.cpp
index e01f91c20456c..9a12571ac6bc9 100644
--- a/llvm/utils/TableGen/IntrinsicEmitter.cpp
+++ b/llvm/utils/TableGen/IntrinsicEmitter.cpp
@@ -15,28 +15,30 @@
 #include "SequenceToOffsetTable.h"
 #include "TableGenBackends.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/StringMatcher.h"
-#include "llvm/TableGen/TableGenBackend.h"
 #include "llvm/TableGen/StringToOffsetTable.h"
+#include "llvm/TableGen/TableGenBackend.h"
 #include <algorithm>
 using namespace llvm;
 
+cl::OptionCategory GenIntrinsicCat("Options for -gen-intrinsic-enums");
+cl::opt<std::string>
+    IntrinsicPrefix("intrinsic-prefix",
+                    cl::desc("Generate intrinsics with this target prefix"),
+                    cl::value_desc("target prefix"), cl::cat(GenIntrinsicCat));
+
 namespace {
 class IntrinsicEmitter {
   RecordKeeper &Records;
-  bool TargetOnly;
-  std::string TargetPrefix;
 
 public:
-  IntrinsicEmitter(RecordKeeper &R, bool T)
-    : Records(R), TargetOnly(T) {}
+  IntrinsicEmitter(RecordKeeper &R) : Records(R) {}
 
   void run(raw_ostream &OS, bool Enums);
 
-  void EmitPrefix(raw_ostream &OS);
-
   void EmitEnumInfo(const CodeGenIntrinsicTable &Ints, raw_ostream &OS);
   void EmitTargetInfo(const CodeGenIntrinsicTable &Ints, raw_ostream &OS);
   void EmitIntrinsicToNameTable(const CodeGenIntrinsicTable &Ints,
@@ -47,7 +49,6 @@ public:
   void EmitAttributes(const CodeGenIntrinsicTable &Ints, raw_ostream &OS);
   void EmitIntrinsicToBuiltinMap(const CodeGenIntrinsicTable &Ints, bool IsGCC,
                                  raw_ostream &OS);
-  void EmitSuffix(raw_ostream &OS);
 };
 } // End anonymous namespace
 
@@ -58,12 +59,7 @@ public:
 void IntrinsicEmitter::run(raw_ostream &OS, bool Enums) {
   emitSourceFileHeader("Intrinsic Function Source Fragment", OS);
 
-  CodeGenIntrinsicTable Ints(Records, TargetOnly);
-
-  if (TargetOnly && !Ints.empty())
-    TargetPrefix = Ints[0].TargetPrefix;
-
-  EmitPrefix(OS);
+  CodeGenIntrinsicTable Ints(Records);
 
   if (Enums) {
     // Emit the enum information.
@@ -90,40 +86,64 @@ void IntrinsicEmitter::run(raw_ostream &OS, bool Enums) {
     // Emit code to translate MS builtins into LLVM intrinsics.
     EmitIntrinsicToBuiltinMap(Ints, false, OS);
   }
-
-  EmitSuffix(OS);
-}
-
-void IntrinsicEmitter::EmitPrefix(raw_ostream &OS) {
-  OS << "// VisualStudio defines setjmp as _setjmp\n"
-        "#if defined(_MSC_VER) && defined(setjmp) && \\\n"
-        "                         !defined(setjmp_undefined_for_msvc)\n"
-        "#  pragma push_macro(\"setjmp\")\n"
-        "#  undef setjmp\n"
-        "#  define setjmp_undefined_for_msvc\n"
-        "#endif\n\n";
-}
-
-void IntrinsicEmitter::EmitSuffix(raw_ostream &OS) {
-  OS << "#if defined(_MSC_VER) && defined(setjmp_undefined_for_msvc)\n"
-        "// let's return it to _setjmp state\n"
-        "#  pragma pop_macro(\"setjmp\")\n"
-        "#  undef setjmp_undefined_for_msvc\n"
-        "#endif\n\n";
 }
 
 void IntrinsicEmitter::EmitEnumInfo(const CodeGenIntrinsicTable &Ints,
                                     raw_ostream &OS) {
-  OS << "// Enum values for Intrinsics.h\n";
-  OS << "#ifdef GET_INTRINSIC_ENUM_VALUES\n";
-  for (unsigned i = 0, e = Ints.size(); i != e; ++i) {
+  // Find the TargetSet for which to generate enums. There will be an initial
+  // set with an empty target prefix which will include target independent
+  // intrinsics like dbg.value.
+  const CodeGenIntrinsicTable::TargetSet *Set = nullptr;
+  for (const auto &Target : Ints.Targets) {
+    if (Target.Name == IntrinsicPrefix) {
+      Set = &Target;
+      break;
+    }
+  }
+  if (!Set) {
+    std::vector<std::string> KnownTargets;
+    for (const auto &Target : Ints.Targets)
+      if (!Target.Name.empty())
+        KnownTargets.push_back(Target.Name);
+    PrintFatalError("tried to generate intrinsics for unknown target " +
+                    IntrinsicPrefix +
+                    "\nKnown targets are: " + join(KnownTargets, ", ") + "\n");
+  }
+
+  // Generate a complete header for target specific intrinsics.
+  if (!IntrinsicPrefix.empty()) {
+    std::string UpperPrefix = StringRef(IntrinsicPrefix).upper();
+    OS << "#ifndef LLVM_IR_INTRINSIC_" << UpperPrefix << "_ENUMS_H\n";
+    OS << "#define LLVM_IR_INTRINSIC_" << UpperPrefix << "_ENUMS_H\n\n";
+    OS << "namespace llvm {\n";
+    OS << "namespace Intrinsic {\n";
+    OS << "enum " << UpperPrefix << "Intrinsics : unsigned {\n";
+  }
+
+  OS << "// Enum values for intrinsics\n";
+  for (unsigned i = Set->Offset, e = Set->Offset + Set->Count; i != e; ++i) {
     OS << "    " << Ints[i].EnumName;
-    OS << ((i != e-1) ? ", " : "  ");
+
+    // Assign a value to the first intrinsic in this target set so that all
+    // intrinsic ids are distinct.
+    if (i == Set->Offset)
+      OS << " = " << (Set->Offset + 1);
+
+    OS << ", ";
     if (Ints[i].EnumName.size() < 40)
-      OS << std::string(40-Ints[i].EnumName.size(), ' ');
+      OS.indent(40 - Ints[i].EnumName.size());
     OS << " // " << Ints[i].Name << "\n";
   }
-  OS << "#endif\n\n";
+
+  // Emit num_intrinsics into the target neutral enum.
+  if (IntrinsicPrefix.empty()) {
+    OS << "    num_intrinsics = " << (Ints.size() + 1) << "\n";
+  } else {
+    OS << "}; // enum\n";
+    OS << "} // namespace Intrinsic\n";
+    OS << "} // namespace llvm\n\n";
+    OS << "#endif\n";
+  }
 }
 
 void IntrinsicEmitter::EmitTargetInfo(const CodeGenIntrinsicTable &Ints,
@@ -588,11 +608,7 @@ void IntrinsicEmitter::EmitAttributes(const CodeGenIntrinsicTable &Ints,
                                       raw_ostream &OS) {
   OS << "// Add parameter attributes that are not common to all intrinsics.\n";
   OS << "#ifdef GET_INTRINSIC_ATTRIBUTES\n";
-  if (TargetOnly)
-    OS << "static AttributeList getAttributes(LLVMContext &C, " << TargetPrefix
-       << "Intrinsic::ID id) {\n";
-  else
-    OS << "AttributeList Intrinsic::getAttributes(LLVMContext &C, ID id) {\n";
+  OS << "AttributeList Intrinsic::getAttributes(LLVMContext &C, ID id) {\n";
 
   // Compute the maximum number of attribute arguments and the map
   typedef std::map<const CodeGenIntrinsic*, unsigned,
@@ -625,12 +641,7 @@ void IntrinsicEmitter::EmitAttributes(const CodeGenIntrinsicTable &Ints,
   OS << "  AttributeList AS[" << maxArgAttrs + 1 << "];\n";
   OS << "  unsigned NumAttrs = 0;\n";
   OS << "  if (id != 0) {\n";
-  OS << "    switch(IntrinsicsToAttributesMap[id - ";
-  if (TargetOnly)
-    OS << "Intrinsic::num_intrinsics";
-  else
-    OS << "1";
-  OS << "]) {\n";
+  OS << "    switch(IntrinsicsToAttributesMap[id - 1]) {\n";
   OS << "    default: llvm_unreachable(\"Invalid attribute number\");\n";
   for (UniqAttrMapTy::const_iterator I = UniqAttributes.begin(),
        E = UniqAttributes.end(); I != E; ++I) {
@@ -875,21 +886,12 @@ void IntrinsicEmitter::EmitIntrinsicToBuiltinMap(
   OS << "// in as TargetPrefix.  The result is assigned to 'IntrinsicID'.\n";
   OS << "#ifdef GET_LLVM_INTRINSIC_FOR_" << CompilerName << "_BUILTIN\n";
 
-  if (TargetOnly) {
-    OS << "static " << TargetPrefix << "Intrinsic::ID "
-       << "getIntrinsicFor" << CompilerName << "Builtin(const char "
-       << "*TargetPrefixStr, StringRef BuiltinNameStr) {\n";
-  } else {
-    OS << "Intrinsic::ID Intrinsic::getIntrinsicFor" << CompilerName
-       << "Builtin(const char "
-       << "*TargetPrefixStr, StringRef BuiltinNameStr) {\n";
-  }
+  OS << "Intrinsic::ID Intrinsic::getIntrinsicFor" << CompilerName
+     << "Builtin(const char "
+     << "*TargetPrefixStr, StringRef BuiltinNameStr) {\n";
 
   if (Table.Empty()) {
-    OS << "  return ";
-    if (!TargetPrefix.empty())
-      OS << "(" << TargetPrefix << "Intrinsic::ID)";
-    OS << "Intrinsic::not_intrinsic;\n";
+    OS << "  return Intrinsic::not_intrinsic;\n";
     OS << "}\n";
     OS << "#endif\n\n";
     return;
@@ -937,19 +939,15 @@ void IntrinsicEmitter::EmitIntrinsicToBuiltinMap(
     OS << "  }\n";
   }
   OS << "  return ";
-  if (!TargetPrefix.empty())
-    OS << "(" << TargetPrefix << "Intrinsic::ID)";
   OS << "Intrinsic::not_intrinsic;\n";
   OS << "}\n";
   OS << "#endif\n\n";
 }
 
-void llvm::EmitIntrinsicEnums(RecordKeeper &RK, raw_ostream &OS,
-                              bool TargetOnly) {
-  IntrinsicEmitter(RK, TargetOnly).run(OS, /*Enums=*/true);
+void llvm::EmitIntrinsicEnums(RecordKeeper &RK, raw_ostream &OS) {
+  IntrinsicEmitter(RK).run(OS, /*Enums=*/true);
 }
 
-void llvm::EmitIntrinsicImpl(RecordKeeper &RK, raw_ostream &OS,
-                             bool TargetOnly) {
-  IntrinsicEmitter(RK, TargetOnly).run(OS, /*Enums=*/false);
+void llvm::EmitIntrinsicImpl(RecordKeeper &RK, raw_ostream &OS) {
+  IntrinsicEmitter(RK).run(OS, /*Enums=*/false);
 }
diff --git a/llvm/utils/TableGen/OptEmitter.cpp b/llvm/utils/TableGen/OptEmitter.cpp
new file mode 100644
index 0000000000000..7fcf3074e0931
--- /dev/null
+++ b/llvm/utils/TableGen/OptEmitter.cpp
@@ -0,0 +1,84 @@
+//===- OptEmitter.cpp - Helper for emitting options.----------- -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "OptEmitter.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include <cctype>
+#include <cstring>
+
+namespace llvm {
+
+// Ordering on Info. The logic should match with the consumer-side function in
+// llvm/Option/OptTable.h.
+// FIXME: Make this take StringRefs instead of null terminated strings to
+// simplify callers.
+static int StrCmpOptionName(const char *A, const char *B) {
+  const char *X = A, *Y = B;
+  char a = tolower(*A), b = tolower(*B);
+  while (a == b) {
+    if (a == '\0')
+      return strcmp(A, B);
+
+    a = tolower(*++X);
+    b = tolower(*++Y);
+  }
+
+  if (a == '\0') // A is a prefix of B.
+    return 1;
+  if (b == '\0') // B is a prefix of A.
+    return -1;
+
+  // Otherwise lexicographic.
+  return (a < b) ? -1 : 1;
+}
+
+int CompareOptionRecords(Record *const *Av, Record *const *Bv) {
+  const Record *A = *Av;
+  const Record *B = *Bv;
+
+  // Sentinel options precede all others and are only ordered by precedence.
+  bool ASent = A->getValueAsDef("Kind")->getValueAsBit("Sentinel");
+  bool BSent = B->getValueAsDef("Kind")->getValueAsBit("Sentinel");
+  if (ASent != BSent)
+    return ASent ? -1 : 1;
+
+  // Compare options by name, unless they are sentinels.
+  if (!ASent)
+    if (int Cmp = StrCmpOptionName(A->getValueAsString("Name").str().c_str(),
+                                   B->getValueAsString("Name").str().c_str()))
+      return Cmp;
+
+  if (!ASent) {
+    std::vector<StringRef> APrefixes = A->getValueAsListOfStrings("Prefixes");
+    std::vector<StringRef> BPrefixes = B->getValueAsListOfStrings("Prefixes");
+
+    for (std::vector<StringRef>::const_iterator APre = APrefixes.begin(),
+                                                AEPre = APrefixes.end(),
+                                                BPre = BPrefixes.begin(),
+                                                BEPre = BPrefixes.end();
+         APre != AEPre && BPre != BEPre; ++APre, ++BPre) {
+      if (int Cmp = StrCmpOptionName(APre->str().c_str(), BPre->str().c_str()))
+        return Cmp;
+    }
+  }
+
+  // Then by the kind precedence;
+  int APrec = A->getValueAsDef("Kind")->getValueAsInt("Precedence");
+  int BPrec = B->getValueAsDef("Kind")->getValueAsInt("Precedence");
+  if (APrec == BPrec && A->getValueAsListOfStrings("Prefixes") ==
+                            B->getValueAsListOfStrings("Prefixes")) {
+    PrintError(A->getLoc(), Twine("Option is equivalent to"));
+    PrintError(B->getLoc(), Twine("Other defined here"));
+    PrintFatalError("Equivalent Options found.");
+  }
+  return APrec < BPrec ? -1 : 1;
+}
+
+} // namespace llvm
diff --git a/llvm/utils/TableGen/OptEmitter.h b/llvm/utils/TableGen/OptEmitter.h
new file mode 100644
index 0000000000000..c8f9246ef1e62
--- /dev/null
+++ b/llvm/utils/TableGen/OptEmitter.h
@@ -0,0 +1,16 @@
+//===- OptEmitter.h - Helper for emitting options. --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_UTILS_TABLEGEN_OPTEMITTER_H
+#define LLVM_UTILS_TABLEGEN_OPTEMITTER_H
+
+namespace llvm {
+class Record;
+int CompareOptionRecords(Record *const *Av, Record *const *Bv);
+} // namespace llvm
+#endif
diff --git a/llvm/utils/TableGen/OptParserEmitter.cpp b/llvm/utils/TableGen/OptParserEmitter.cpp
index 51b1cb093b213..c1978ac7ac661 100644
--- a/llvm/utils/TableGen/OptParserEmitter.cpp
+++ b/llvm/utils/TableGen/OptParserEmitter.cpp
@@ -6,7 +6,7 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "llvm/TableGen/Error.h"
+#include "OptEmitter.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Twine.h"
@@ -18,75 +18,6 @@
 
 using namespace llvm;
 
-// Ordering on Info. The logic should match with the consumer-side function in
-// llvm/Option/OptTable.h.
-// FIXME: Mmake this take StringRefs instead of null terminated strings to
-// simplify callers.
-static int StrCmpOptionName(const char *A, const char *B) {
-  const char *X = A, *Y = B;
-  char a = tolower(*A), b = tolower(*B);
-  while (a == b) {
-    if (a == '\0')
-      return strcmp(A, B);
-
-    a = tolower(*++X);
-    b = tolower(*++Y);
-  }
-
-  if (a == '\0') // A is a prefix of B.
-    return 1;
-  if (b == '\0') // B is a prefix of A.
-    return -1;
-
-  // Otherwise lexicographic.
-  return (a < b) ? -1 : 1;
-}
-
-static int CompareOptionRecords(Record *const *Av, Record *const *Bv) {
-  const Record *A = *Av;
-  const Record *B = *Bv;
-
-  // Sentinel options precede all others and are only ordered by precedence.
-  bool ASent = A->getValueAsDef("Kind")->getValueAsBit("Sentinel");
-  bool BSent = B->getValueAsDef("Kind")->getValueAsBit("Sentinel");
-  if (ASent != BSent)
-    return ASent ? -1 : 1;
-
-  // Compare options by name, unless they are sentinels.
-  if (!ASent)
-    if (int Cmp = StrCmpOptionName(A->getValueAsString("Name").str().c_str(),
-                                   B->getValueAsString("Name").str().c_str()))
-      return Cmp;
-
-  if (!ASent) {
-    std::vector<StringRef> APrefixes = A->getValueAsListOfStrings("Prefixes");
-    std::vector<StringRef> BPrefixes = B->getValueAsListOfStrings("Prefixes");
-
-    for (std::vector<StringRef>::const_iterator APre = APrefixes.begin(),
-                                                AEPre = APrefixes.end(),
-                                                BPre = BPrefixes.begin(),
-                                                BEPre = BPrefixes.end();
-                                                APre != AEPre &&
-                                                BPre != BEPre;
-                                                ++APre, ++BPre) {
-      if (int Cmp = StrCmpOptionName(APre->str().c_str(), BPre->str().c_str()))
-        return Cmp;
-    }
-  }
-
-  // Then by the kind precedence;
-  int APrec = A->getValueAsDef("Kind")->getValueAsInt("Precedence");
-  int BPrec = B->getValueAsDef("Kind")->getValueAsInt("Precedence");
-  if (APrec == BPrec &&
-      A->getValueAsListOfStrings("Prefixes") ==
-      B->getValueAsListOfStrings("Prefixes")) {
-    PrintError(A->getLoc(), Twine("Option is equivalent to"));
-    PrintError(B->getLoc(), Twine("Other defined here"));
-    PrintFatalError("Equivalent Options found.");
-  }
-  return APrec < BPrec ? -1 : 1;
-}
-
 static const std::string getOptionName(const Record &R) {
   // Use the record name unless EnumName is defined.
   if (isa<UnsetInit>(R.getValueInit("EnumName")))
@@ -310,9 +241,9 @@ void EmitOptParser(RecordKeeper &Records, raw_ostream &OS) {
     OS << "bool ValuesWereAdded;\n";
     OS << R.getValueAsString("ValuesCode");
     OS << "\n";
-    for (const std::string &Pref : R.getValueAsListOfStrings("Prefixes")) {
+    for (std::string S : R.getValueAsListOfStrings("Prefixes")) {
       OS << "ValuesWereAdded = Opt.addValues(";
-      std::string S = (Pref + R.getValueAsString("Name")).str();
+      S += R.getValueAsString("Name");
       write_cstring(OS, S);
       OS << ", Values);\n";
       OS << "(void)ValuesWereAdded;\n";
diff --git a/llvm/utils/TableGen/OptRSTEmitter.cpp b/llvm/utils/TableGen/OptRSTEmitter.cpp
new file mode 100644
index 0000000000000..3102f378bc1e9
--- /dev/null
+++ b/llvm/utils/TableGen/OptRSTEmitter.cpp
@@ -0,0 +1,86 @@
+//===- OptParserEmitter.cpp - Table Driven Command Line Parsing -----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "OptEmitter.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/TableGen/Error.h"
+#include "llvm/TableGen/Record.h"
+#include "llvm/TableGen/TableGenBackend.h"
+#include <cctype>
+#include <cstring>
+#include <map>
+
+using namespace llvm;
+
+/// OptParserEmitter - This tablegen backend takes an input .td file
+/// describing a list of options and emits a RST man page.
+namespace llvm {
+void EmitOptRST(RecordKeeper &Records, raw_ostream &OS) {
+  llvm::StringMap<std::vector<Record *>> OptionsByGroup;
+  std::vector<Record *> OptionsWithoutGroup;
+
+  // Get the options.
+  std::vector<Record *> Opts = Records.getAllDerivedDefinitions("Option");
+  array_pod_sort(Opts.begin(), Opts.end(), CompareOptionRecords);
+
+  // Get the option groups.
+  const std::vector<Record *> &Groups =
+      Records.getAllDerivedDefinitions("OptionGroup");
+  for (unsigned i = 0, e = Groups.size(); i != e; ++i) {
+    const Record &R = *Groups[i];
+    OptionsByGroup.try_emplace(R.getValueAsString("Name"));
+  }
+
+  // Map options to their group.
+  for (unsigned i = 0, e = Opts.size(); i != e; ++i) {
+    const Record &R = *Opts[i];
+    if (const DefInit *DI = dyn_cast<DefInit>(R.getValueInit("Group"))) {
+      OptionsByGroup[DI->getDef()->getValueAsString("Name")].push_back(Opts[i]);
+    } else {
+      OptionsByGroup["options"].push_back(Opts[i]);
+    }
+  }
+
+  // Print options under their group.
+  for (const auto &KV : OptionsByGroup) {
+    std::string GroupName = KV.getKey().upper();
+    OS << GroupName << '\n';
+    OS << std::string(GroupName.size(), '-') << '\n';
+    OS << '\n';
+
+    for (Record *R : KV.getValue()) {
+      OS << ".. option:: ";
+
+      // Print the prefix.
+      std::vector<StringRef> Prefixes = R->getValueAsListOfStrings("Prefixes");
+      if (!Prefixes.empty())
+        OS << Prefixes[0];
+
+      // Print the option name.
+      OS << R->getValueAsString("Name");
+
+      // Print the meta-variable.
+      if (!isa<UnsetInit>(R->getValueInit("MetaVarName"))) {
+        OS << '=';
+        OS.write_escaped(R->getValueAsString("MetaVarName"));
+      }
+
+      OS << "\n\n";
+
+      // The option help text.
+      if (!isa<UnsetInit>(R->getValueInit("HelpText"))) {
+        OS << ' ';
+        OS.write_escaped(R->getValueAsString("HelpText"));
+        OS << "\n\n";
+      }
+    }
+  }
+}
+} // end namespace llvm
diff --git a/llvm/utils/TableGen/RISCVCompressInstEmitter.cpp b/llvm/utils/TableGen/RISCVCompressInstEmitter.cpp
index 2f1d3898f1829..96e4f95937b2a 100644
--- a/llvm/utils/TableGen/RISCVCompressInstEmitter.cpp
+++ b/llvm/utils/TableGen/RISCVCompressInstEmitter.cpp
@@ -45,6 +45,14 @@
 //                     const MCRegisterInfo &MRI,
 //                     const MCSubtargetInfo &STI);
 //
+// In addition, it exports a function for checking whether
+// an instruction is compressable:
+//
+// bool isCompressibleInst(const MachineInstr& MI,
+//                           const RISCVSubtarget *Subtarget,
+//                           const MCRegisterInfo &MRI,
+//                           const MCSubtargetInfo &STI);
+//
 // The clients that include this auto-generated header file and
 // invoke these functions can compress an instruction before emitting
 // it in the target-specific ASM or ELF streamer or can uncompress
@@ -99,7 +107,7 @@ class RISCVCompressInstEmitter {
         : Source(S), Dest(D), PatReqFeatures(RF), SourceOperandMap(SourceMap),
           DestOperandMap(DestMap) {}
   };
-
+  enum EmitterType { Compress, Uncompress, CheckCompress };
   RecordKeeper &Records;
   CodeGenTarget Target;
   SmallVector<CompressPat, 4> CompressPatterns;
@@ -107,7 +115,7 @@ class RISCVCompressInstEmitter {
   void addDagOperandMapping(Record *Rec, DagInit *Dag, CodeGenInstruction &Inst,
                             IndexedMap<OpData> &OperandMap, bool IsSourceInst);
   void evaluateCompressPat(Record *Compress);
-  void emitCompressInstEmitter(raw_ostream &o, bool Compress);
+  void emitCompressInstEmitter(raw_ostream &o, EmitterType EType);
   bool validateTypes(Record *SubType, Record *Type, bool IsSourceInst);
   bool validateRegister(Record *Reg, Record *RegClass);
   void createDagOperandMapping(Record *Rec, StringMap<unsigned> &SourceOperands,
@@ -482,26 +490,39 @@ static void getReqFeatures(std::set<StringRef> &FeaturesSet,
   }
 }
 
-unsigned getMCOpPredicate(DenseMap<const Record *, unsigned> &MCOpPredicateMap,
-                          std::vector<const Record *> &MCOpPredicates,
-                          Record *Rec) {
-  unsigned Entry = MCOpPredicateMap[Rec];
+static unsigned getPredicates(DenseMap<const Record *, unsigned> &PredicateMap,
+                              std::vector<const Record *> &Predicates,
+                              Record *Rec, StringRef Name) {
+  unsigned Entry = PredicateMap[Rec];
   if (Entry)
     return Entry;
 
-  if (!Rec->isValueUnset("MCOperandPredicate")) {
-    MCOpPredicates.push_back(Rec);
-    Entry = MCOpPredicates.size();
-    MCOpPredicateMap[Rec] = Entry;
+  if (!Rec->isValueUnset(Name)) {
+    Predicates.push_back(Rec);
+    Entry = Predicates.size();
+    PredicateMap[Rec] = Entry;
     return Entry;
   }
 
-  PrintFatalError(Rec->getLoc(),
-                  "No MCOperandPredicate on this operand at all: " +
-                      Rec->getName().str() + "'");
+  PrintFatalError(Rec->getLoc(), "No " + Name +
+    " predicate on this operand at all: '" + Rec->getName().str() + "'");
   return 0;
 }
 
+static void printPredicates(std::vector<const Record *> &Predicates,
+                            StringRef Name, raw_ostream &o) {
+  for (unsigned i = 0; i < Predicates.size(); ++i) {
+    Init *Pred = Predicates[i]->getValueInit(Name);
+    if (CodeInit *SI = dyn_cast<CodeInit>(Pred))
+      o << "  case " << i + 1 << ": {\n"
+        << "  // " << Predicates[i]->getName().str() << "\n"
+        << "  " << SI->getValue() << "\n"
+        << "  }\n";
+    else
+      llvm_unreachable("Unexpected predicate field!");
+  }
+}
+
 static std::string mergeCondAndCode(raw_string_ostream &CondStream,
                                     raw_string_ostream &CodeStream) {
   std::string S;
@@ -519,7 +540,7 @@ static std::string mergeCondAndCode(raw_string_ostream &CondStream,
 }
 
 void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
-                                                       bool Compress) {
+                                                       EmitterType EType) {
   Record *AsmWriter = Target.getAsmWriter();
   if (!AsmWriter->getValueAsInt("PassSubtarget"))
     PrintFatalError(AsmWriter->getLoc(),
@@ -534,8 +555,9 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
   // source and destination are flipped and the sort key needs to change
   // accordingly.
   llvm::stable_sort(CompressPatterns,
-                    [Compress](const CompressPat &LHS, const CompressPat &RHS) {
-                      if (Compress)
+                    [EType](const CompressPat &LHS, const CompressPat &RHS) {
+                      if (EType == EmitterType::Compress ||
+                        EType == EmitterType::CheckCompress)
                         return (LHS.Source.TheDef->getName().str() <
                                 RHS.Source.TheDef->getName().str());
                       else
@@ -546,6 +568,9 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
   // A list of MCOperandPredicates for all operands in use, and the reverse map.
   std::vector<const Record *> MCOpPredicates;
   DenseMap<const Record *, unsigned> MCOpPredicateMap;
+  // A list of ImmLeaf Predicates for all operands in use, and the reverse map.
+  std::vector<const Record *> ImmLeafPredicates;
+  DenseMap<const Record *, unsigned> ImmLeafPredicateMap;
 
   std::string F;
   std::string FH;
@@ -553,32 +578,42 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
   raw_string_ostream FuncH(FH);
   bool NeedMRI = false;
 
-  if (Compress)
+  if (EType == EmitterType::Compress)
     o << "\n#ifdef GEN_COMPRESS_INSTR\n"
       << "#undef GEN_COMPRESS_INSTR\n\n";
-  else
+  else if (EType == EmitterType::Uncompress)
     o << "\n#ifdef GEN_UNCOMPRESS_INSTR\n"
       << "#undef GEN_UNCOMPRESS_INSTR\n\n";
+  else if (EType == EmitterType::CheckCompress)
+    o << "\n#ifdef GEN_CHECK_COMPRESS_INSTR\n"
+      << "#undef GEN_CHECK_COMPRESS_INSTR\n\n";
 
-  if (Compress) {
+  if (EType == EmitterType::Compress) {
     FuncH << "static bool compressInst(MCInst& OutInst,\n";
     FuncH.indent(25) << "const MCInst &MI,\n";
     FuncH.indent(25) << "const MCSubtargetInfo &STI,\n";
     FuncH.indent(25) << "MCContext &Context) {\n";
-  } else {
+  } else if (EType == EmitterType::Uncompress){
     FuncH << "static bool uncompressInst(MCInst& OutInst,\n";
     FuncH.indent(27) << "const MCInst &MI,\n";
     FuncH.indent(27) << "const MCRegisterInfo &MRI,\n";
     FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
+  } else if (EType == EmitterType::CheckCompress) {
+    FuncH << "static bool isCompressibleInst(const MachineInstr& MI,\n";
+    FuncH.indent(27) << "const RISCVSubtarget *Subtarget,\n";
+    FuncH.indent(27) << "const MCRegisterInfo &MRI,\n";
+    FuncH.indent(27) << "const MCSubtargetInfo &STI) {\n";
   }
 
   if (CompressPatterns.empty()) {
     o << FuncH.str();
     o.indent(2) << "return false;\n}\n";
-    if (Compress)
+    if (EType == EmitterType::Compress)
       o << "\n#endif //GEN_COMPRESS_INSTR\n";
-    else
+    else if (EType == EmitterType::Uncompress)
       o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
+    else if (EType == EmitterType::CheckCompress)
+      o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
     return;
   }
 
@@ -589,18 +624,24 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
   CaseStream << "  switch (MI.getOpcode()) {\n";
   CaseStream << "    default: return false;\n";
 
+  bool CompressOrCheck =
+    EType == EmitterType::Compress || EType == EmitterType::CheckCompress;
+  bool CompressOrUncompress =
+    EType == EmitterType::Compress || EType == EmitterType::Uncompress;
+
   for (auto &CompressPat : CompressPatterns) {
     std::string CondString;
     std::string CodeString;
     raw_string_ostream CondStream(CondString);
     raw_string_ostream CodeStream(CodeString);
     CodeGenInstruction &Source =
-        Compress ? CompressPat.Source : CompressPat.Dest;
-    CodeGenInstruction &Dest = Compress ? CompressPat.Dest : CompressPat.Source;
-    IndexedMap<OpData> SourceOperandMap =
-        Compress ? CompressPat.SourceOperandMap : CompressPat.DestOperandMap;
-    IndexedMap<OpData> &DestOperandMap =
-        Compress ? CompressPat.DestOperandMap : CompressPat.SourceOperandMap;
+        CompressOrCheck ?  CompressPat.Source : CompressPat.Dest;
+    CodeGenInstruction &Dest =
+        CompressOrCheck ? CompressPat.Dest : CompressPat.Source;
+    IndexedMap<OpData> SourceOperandMap = CompressOrCheck ?
+      CompressPat.SourceOperandMap : CompressPat.DestOperandMap;
+    IndexedMap<OpData> &DestOperandMap = CompressOrCheck ?
+      CompressPat.DestOperandMap : CompressPat.SourceOperandMap;
 
     CurOp = Source.TheDef->getName().str();
     // Check current and previous opcode to decide to continue or end a case.
@@ -670,7 +711,8 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
       }
     }
     CodeStream.indent(6) << "// " + Dest.AsmString + "\n";
-    CodeStream.indent(6) << "OutInst.setOpcode(" + Namespace +
+    if (CompressOrUncompress)
+      CodeStream.indent(6) << "OutInst.setOpcode(" + Namespace +
                                 "::" + Dest.TheDef->getName().str() + ");\n";
     OpNo = 0;
     for (const auto &DestOperand : Dest.Operands) {
@@ -692,42 +734,69 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
                        "RegClassID).contains(" + "MI.getOperand(" +
                        std::to_string(OpIdx) + ").getReg())) &&\n";
 
-          CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
-                                      std::to_string(OpIdx) + "));\n";
+          if (CompressOrUncompress)
+            CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
+                                        std::to_string(OpIdx) + "));\n";
         } else {
           // Handling immediate operands.
-          unsigned Entry = getMCOpPredicate(MCOpPredicateMap, MCOpPredicates,
-                                            DestOperand.Rec);
-          CondStream.indent(6) << Namespace + "ValidateMCOperand(" +
-                                      "MI.getOperand(" + std::to_string(OpIdx) +
-                                      "), STI, " + std::to_string(Entry) +
-                                      ") &&\n";
-          CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
-                                      std::to_string(OpIdx) + "));\n";
+          if (CompressOrUncompress) {
+            unsigned Entry = getPredicates(MCOpPredicateMap, MCOpPredicates,
+              DestOperand.Rec, StringRef("MCOperandPredicate"));
+            CondStream.indent(6) << Namespace + "ValidateMCOperand(" +
+                                        "MI.getOperand(" + std::to_string(OpIdx) +
+                                        "), STI, " + std::to_string(Entry) +
+                                        ") &&\n";
+          } else {
+            unsigned Entry = getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
+              DestOperand.Rec, StringRef("ImmediateCode"));
+            CondStream.indent(6) << "MI.getOperand(" + std::to_string(OpIdx) +
+                                    ").isImm() && \n";
+            CondStream.indent(6) << Namespace + "ValidateMachineOperand(" +
+                                        "MI.getOperand(" + std::to_string(OpIdx) +
+                                        "), Subtarget, " + std::to_string(Entry) +
+                                        ") &&\n";
+          }
+          if (CompressOrUncompress)
+            CodeStream.indent(6) << "OutInst.addOperand(MI.getOperand(" +
+                                        std::to_string(OpIdx) + "));\n";
         }
         break;
       }
       case OpData::Imm: {
-        unsigned Entry =
-            getMCOpPredicate(MCOpPredicateMap, MCOpPredicates, DestOperand.Rec);
-        CondStream.indent(6)
-            << Namespace + "ValidateMCOperand(" + "MCOperand::createImm(" +
-                   std::to_string(DestOperandMap[OpNo].Data.Imm) + "), STI, " +
-                   std::to_string(Entry) + ") &&\n";
-        CodeStream.indent(6)
-            << "OutInst.addOperand(MCOperand::createImm(" +
-                   std::to_string(DestOperandMap[OpNo].Data.Imm) + "));\n";
+        if (CompressOrUncompress) {
+          unsigned Entry = getPredicates(MCOpPredicateMap, MCOpPredicates,
+            DestOperand.Rec, StringRef("MCOperandPredicate"));
+          CondStream.indent(6)
+              << Namespace + "ValidateMCOperand(" + "MCOperand::createImm(" +
+                     std::to_string(DestOperandMap[OpNo].Data.Imm) + "), STI, " +
+                     std::to_string(Entry) + ") &&\n";
+        } else {
+          unsigned Entry = getPredicates(ImmLeafPredicateMap, ImmLeafPredicates,
+            DestOperand.Rec, StringRef("ImmediateCode"));
+          CondStream.indent(6)
+              << Namespace + "ValidateMachineOperand(" + "MachineOperand::CreateImm(" +
+                     std::to_string(DestOperandMap[OpNo].Data.Imm) + "), SubTarget, " +
+                     std::to_string(Entry) + ") &&\n";
+        }
+        if (CompressOrUncompress)
+          CodeStream.indent(6)
+              << "OutInst.addOperand(MCOperand::createImm(" +
+                     std::to_string(DestOperandMap[OpNo].Data.Imm) + "));\n";
       } break;
       case OpData::Reg: {
-        // Fixed register has been validated at pattern validation time.
-        Record *Reg = DestOperandMap[OpNo].Data.Reg;
-        CodeStream.indent(6) << "OutInst.addOperand(MCOperand::createReg(" +
-                                    Namespace + "::" + Reg->getName().str() +
-                                    "));\n";
+        if (CompressOrUncompress) {
+          // Fixed register has been validated at pattern validation time.
+          Record *Reg = DestOperandMap[OpNo].Data.Reg;
+          CodeStream.indent(6) << "OutInst.addOperand(MCOperand::createReg(" +
+                                      Namespace + "::" + Reg->getName().str() +
+                                      "));\n";
+        }
       } break;
       }
       ++OpNo;
     }
+    if (CompressOrUncompress)
+      CodeStream.indent(6) << "OutInst.setLoc(MI.getLoc());\n";
     CaseStream << mergeCondAndCode(CondStream, CodeStream);
     PrevOp = CurOp;
   }
@@ -747,29 +816,40 @@ void RISCVCompressInstEmitter::emitCompressInstEmitter(raw_ostream &o,
       << "    llvm_unreachable(\"Unknown MCOperandPredicate kind\");\n"
       << "    break;\n";
 
-    for (unsigned i = 0; i < MCOpPredicates.size(); ++i) {
-      Init *MCOpPred = MCOpPredicates[i]->getValueInit("MCOperandPredicate");
-      if (CodeInit *SI = dyn_cast<CodeInit>(MCOpPred))
-        o << "  case " << i + 1 << ": {\n"
-          << "   // " << MCOpPredicates[i]->getName().str() << SI->getValue()
-          << "\n"
-          << "    }\n";
-      else
-        llvm_unreachable("Unexpected MCOperandPredicate field!");
-    }
+    printPredicates(MCOpPredicates, "MCOperandPredicate", o);
+
+    o << "  }\n"
+      << "}\n\n";
+  }
+
+  if (!ImmLeafPredicates.empty()) {
+    o << "static bool " << Namespace
+      << "ValidateMachineOperand(const MachineOperand &MO,\n"
+      << "                  const RISCVSubtarget *Subtarget,\n"
+      << "                  unsigned PredicateIndex) {\n"
+      << "  int64_t Imm = MO.getImm(); \n"
+      << "  switch (PredicateIndex) {\n"
+      << "  default:\n"
+      << "    llvm_unreachable(\"Unknown ImmLeaf Predicate kind\");\n"
+      << "    break;\n";
+
+    printPredicates(ImmLeafPredicates, "ImmediateCode", o);
+
     o << "  }\n"
       << "}\n\n";
   }
 
   o << FuncH.str();
-  if (NeedMRI && Compress)
+  if (NeedMRI && EType == EmitterType::Compress)
     o.indent(2) << "const MCRegisterInfo &MRI = *Context.getRegisterInfo();\n";
   o << Func.str();
 
-  if (Compress)
+  if (EType == EmitterType::Compress)
     o << "\n#endif //GEN_COMPRESS_INSTR\n";
-  else
+  else if (EType == EmitterType::Uncompress)
     o << "\n#endif //GEN_UNCOMPRESS_INSTR\n\n";
+  else if (EType == EmitterType::CheckCompress)
+    o << "\n#endif //GEN_CHECK_COMPRESS_INSTR\n\n";
 }
 
 void RISCVCompressInstEmitter::run(raw_ostream &o) {
@@ -788,9 +868,11 @@ void RISCVCompressInstEmitter::run(raw_ostream &o) {
   // Emit file header.
   emitSourceFileHeader("Compress instruction Source Fragment", o);
   // Generate compressInst() function.
-  emitCompressInstEmitter(o, true);
+  emitCompressInstEmitter(o, EmitterType::Compress);
   // Generate uncompressInst() function.
-  emitCompressInstEmitter(o, false);
+  emitCompressInstEmitter(o, EmitterType::Uncompress);
+  // Generate isCompressibleInst() function.
+  emitCompressInstEmitter(o, EmitterType::CheckCompress);
 }
 
 namespace llvm {
diff --git a/llvm/utils/TableGen/RegisterInfoEmitter.cpp b/llvm/utils/TableGen/RegisterInfoEmitter.cpp
index 513cd14e0fabc..2586ec671b2ab 100644
--- a/llvm/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/llvm/utils/TableGen/RegisterInfoEmitter.cpp
@@ -742,7 +742,7 @@ RegisterInfoEmitter::emitComposeSubRegIndices(raw_ostream &OS,
     OS << "    { ";
     for (unsigned i = 0, e = SubRegIndicesSize; i != e; ++i)
       if (Rows[r][i])
-        OS << Rows[r][i]->EnumValue << ", ";
+        OS << Rows[r][i]->getQualifiedName() << ", ";
       else
         OS << "0, ";
     OS << "},\n";
diff --git a/llvm/utils/TableGen/SearchableTableEmitter.cpp b/llvm/utils/TableGen/SearchableTableEmitter.cpp
index f08f8aa019569..cfe48eb1949dc 100644
--- a/llvm/utils/TableGen/SearchableTableEmitter.cpp
+++ b/llvm/utils/TableGen/SearchableTableEmitter.cpp
@@ -44,7 +44,7 @@ struct GenericEnum {
   using Entry = std::pair<StringRef, int64_t>;
 
   std::string Name;
-  Record *Class;
+  Record *Class = nullptr;
   std::string PreprocessorGuard;
   std::vector<std::unique_ptr<Entry>> Entries;
   DenseMap<Record *, Entry *> EntryMap;
@@ -63,7 +63,7 @@ struct GenericField {
 struct SearchIndex {
   std::string Name;
   SmallVector<GenericField, 1> Fields;
-  bool EarlyOut;
+  bool EarlyOut = false;
 };
 
 struct GenericTable {
diff --git a/llvm/utils/TableGen/SequenceToOffsetTable.h b/llvm/utils/TableGen/SequenceToOffsetTable.h
index 8a826eff311d4..327da39f4774a 100644
--- a/llvm/utils/TableGen/SequenceToOffsetTable.h
+++ b/llvm/utils/TableGen/SequenceToOffsetTable.h
@@ -83,7 +83,7 @@ public:
   bool empty() const { return Seqs.empty(); }
 
   unsigned size() const {
-    assert(Entries && "Call layout() before size()");
+    assert((empty() || Entries) && "Call layout() before size()");
     return Entries;
   }
 
@@ -113,7 +113,7 @@ public:
   void emit(raw_ostream &OS,
             void (*Print)(raw_ostream&, ElemT),
             const char *Term = "0") const {
-    assert(Entries && "Call layout() before emit()");
+    assert((empty() || Entries) && "Call layout() before emit()");
     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
          I != E; ++I) {
       OS << "  /* " << I->second << " */ ";
diff --git a/llvm/utils/TableGen/TableGen.cpp b/llvm/utils/TableGen/TableGen.cpp
index f730d91160ad5..bdb963c15d322 100644
--- a/llvm/utils/TableGen/TableGen.cpp
+++ b/llvm/utils/TableGen/TableGen.cpp
@@ -40,11 +40,10 @@ enum ActionType {
   GenSubtarget,
   GenIntrinsicEnums,
   GenIntrinsicImpl,
-  GenTgtIntrinsicEnums,
-  GenTgtIntrinsicImpl,
   PrintEnums,
   PrintSets,
   GenOptParserDefs,
+  GenOptRST,
   GenCTags,
   GenAttributes,
   GenSearchableTables,
@@ -101,15 +100,12 @@ cl::opt<ActionType> Action(
                    "Generate intrinsic enums"),
         clEnumValN(GenIntrinsicImpl, "gen-intrinsic-impl",
                    "Generate intrinsic information"),
-        clEnumValN(GenTgtIntrinsicEnums, "gen-tgt-intrinsic-enums",
-                   "Generate target intrinsic enums"),
-        clEnumValN(GenTgtIntrinsicImpl, "gen-tgt-intrinsic-impl",
-                   "Generate target intrinsic information"),
         clEnumValN(PrintEnums, "print-enums", "Print enum values for a class"),
         clEnumValN(PrintSets, "print-sets",
                    "Print expanded sets for testing DAG exprs"),
         clEnumValN(GenOptParserDefs, "gen-opt-parser-defs",
                    "Generate option definitions"),
+        clEnumValN(GenOptRST, "gen-opt-rst", "Generate option RST"),
         clEnumValN(GenCTags, "gen-ctags", "Generate ctags-compatible index"),
         clEnumValN(GenAttributes, "gen-attrs", "Generate attributes"),
         clEnumValN(GenSearchableTables, "gen-searchable-tables",
@@ -126,8 +122,7 @@ cl::opt<ActionType> Action(
                    "Generate registers bank descriptions"),
         clEnumValN(GenExegesis, "gen-exegesis",
                    "Generate llvm-exegesis tables"),
-        clEnumValN(GenAutomata, "gen-automata",
-                   "Generate generic automata")));
+        clEnumValN(GenAutomata, "gen-automata", "Generate generic automata")));
 
 cl::OptionCategory PrintEnumsCat("Options for -print-enums");
 cl::opt<std::string> Class("class", cl::desc("Print Enum list for this class"),
@@ -195,15 +190,12 @@ bool LLVMTableGenMain(raw_ostream &OS, RecordKeeper &Records) {
   case GenIntrinsicImpl:
     EmitIntrinsicImpl(Records, OS);
     break;
-  case GenTgtIntrinsicEnums:
-    EmitIntrinsicEnums(Records, OS, true);
-    break;
-  case GenTgtIntrinsicImpl:
-    EmitIntrinsicImpl(Records, OS, true);
-    break;
   case GenOptParserDefs:
     EmitOptParser(Records, OS);
     break;
+  case GenOptRST:
+    EmitOptRST(Records, OS);
+    break;
   case PrintEnums:
   {
     for (Record *Rec : Records.getAllDerivedDefinitions(Class))
diff --git a/llvm/utils/TableGen/TableGenBackends.h b/llvm/utils/TableGen/TableGenBackends.h
index 8c067dd51b3b4..9eef77a4577f0 100644
--- a/llvm/utils/TableGen/TableGenBackends.h
+++ b/llvm/utils/TableGen/TableGenBackends.h
@@ -61,10 +61,8 @@ namespace llvm {
 class raw_ostream;
 class RecordKeeper;
 
-void EmitIntrinsicEnums(RecordKeeper &RK, raw_ostream &OS,
-                        bool TargetOnly = false);
-void EmitIntrinsicImpl(RecordKeeper &RK, raw_ostream &OS,
-                       bool TargetOnly = false);
+void EmitIntrinsicEnums(RecordKeeper &RK, raw_ostream &OS);
+void EmitIntrinsicImpl(RecordKeeper &RK, raw_ostream &OS);
 void EmitAsmMatcher(RecordKeeper &RK, raw_ostream &OS);
 void EmitAsmWriter(RecordKeeper &RK, raw_ostream &OS);
 void EmitCallingConv(RecordKeeper &RK, raw_ostream &OS);
@@ -81,6 +79,7 @@ void EmitRegisterInfo(RecordKeeper &RK, raw_ostream &OS);
 void EmitSubtarget(RecordKeeper &RK, raw_ostream &OS);
 void EmitMapTable(RecordKeeper &RK, raw_ostream &OS);
 void EmitOptParser(RecordKeeper &RK, raw_ostream &OS);
+void EmitOptRST(RecordKeeper &RK, raw_ostream &OS);
 void EmitCTags(RecordKeeper &RK, raw_ostream &OS);
 void EmitAttributes(RecordKeeper &RK, raw_ostream &OS);
 void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS);
diff --git a/llvm/utils/TableGen/X86DisassemblerTables.cpp b/llvm/utils/TableGen/X86DisassemblerTables.cpp
index 14bce4c294462..5dc653ac38060 100644
--- a/llvm/utils/TableGen/X86DisassemblerTables.cpp
+++ b/llvm/utils/TableGen/X86DisassemblerTables.cpp
@@ -667,16 +667,9 @@ void DisassemblerTables::emitModRMDecision(raw_ostream &o1, raw_ostream &o2,
   static uint32_t sEntryNumber = 1;
   ModRMDecisionType dt = getDecisionType(decision);
 
-  if (dt == MODRM_ONEENTRY && decision.instructionIDs[0] == 0)
-  {
-    o2.indent(i2) << "{ /* ModRMDecision */" << "\n";
-    i2++;
-
-    o2.indent(i2) << stringForDecisionType(dt) << "," << "\n";
-    o2.indent(i2) << 0 << " /* EmptyTable */\n";
-
-    i2--;
-    o2.indent(i2) << "}";
+  if (dt == MODRM_ONEENTRY && decision.instructionIDs[0] == 0) {
+    // Empty table.
+    o2 << "{ " << stringForDecisionType(dt) << ", 0 }";
     return;
   }
 
@@ -725,14 +718,8 @@ void DisassemblerTables::emitModRMDecision(raw_ostream &o1, raw_ostream &o2,
     i1--;
   }
 
-  o2.indent(i2) << "{ /* struct ModRMDecision */" << "\n";
-  i2++;
-
-  o2.indent(i2) << stringForDecisionType(dt) << "," << "\n";
-  o2.indent(i2) << EntryNumber << " /* Table" << EntryNumber << " */\n";
-
-  i2--;
-  o2.indent(i2) << "}";
+  o2 << "{ " << stringForDecisionType(dt) << ", " << EntryNumber << " /* Table"
+     << EntryNumber << " */ }";
 
   switch (dt) {
     default:
@@ -764,30 +751,43 @@ void DisassemblerTables::emitModRMDecision(raw_ostream &o1, raw_ostream &o2,
 void DisassemblerTables::emitOpcodeDecision(raw_ostream &o1, raw_ostream &o2,
                                             unsigned &i1, unsigned &i2,
                                             unsigned &ModRMTableNum,
-                                            OpcodeDecision &decision) const {
-  o2.indent(i2) << "{ /* struct OpcodeDecision */" << "\n";
-  i2++;
-  o2.indent(i2) << "{" << "\n";
-  i2++;
-
-  for (unsigned index = 0; index < 256; ++index) {
-    o2.indent(i2);
-
-    o2 << "/* 0x" << format("%02hhx", index) << " */" << "\n";
-
-    emitModRMDecision(o1, o2, i1, i2, ModRMTableNum,
-                      decision.modRMDecisions[index]);
-
-    if (index <  255)
-      o2 << ",";
-
-    o2 << "\n";
+                                            OpcodeDecision &opDecision) const {
+  o2 << "{";
+  ++i2;
+
+  unsigned index;
+  for (index = 0; index < 256; ++index) {
+    auto &decision = opDecision.modRMDecisions[index];
+    ModRMDecisionType dt = getDecisionType(decision);
+    if (!(dt == MODRM_ONEENTRY && decision.instructionIDs[0] == 0))
+      break;
+  }
+  if (index == 256) {
+    // If all 256 entries are MODRM_ONEENTRY, omit output.
+    assert(MODRM_ONEENTRY == 0);
+    --i2;
+    o2 << "},\n";
+  } else {
+    o2 << " /* struct OpcodeDecision */ {\n";
+    ++i2;
+    for (index = 0; index < 256; ++index) {
+      o2.indent(i2);
+
+      o2 << "/* 0x" << format("%02hhx", index) << " */ ";
+
+      emitModRMDecision(o1, o2, i1, i2, ModRMTableNum,
+                        opDecision.modRMDecisions[index]);
+
+      if (index < 255)
+        o2 << ",";
+
+      o2 << "\n";
+    }
+    --i2;
+    o2.indent(i2) << "}\n";
+    --i2;
+    o2.indent(i2) << "},\n";
   }
-
-  i2--;
-  o2.indent(i2) << "}" << "\n";
-  i2--;
-  o2.indent(i2) << "}" << "\n";
 }
 
 void DisassemblerTables::emitContextDecision(raw_ostream &o1, raw_ostream &o2,
@@ -803,14 +803,10 @@ void DisassemblerTables::emitContextDecision(raw_ostream &o1, raw_ostream &o2,
   for (unsigned index = 0; index < IC_max; ++index) {
     o2.indent(i2) << "/* ";
     o2 << stringForContext((InstructionContext)index);
-    o2 << " */";
-    o2 << "\n";
+    o2 << " */ ";
 
     emitOpcodeDecision(o1, o2, i1, i2, ModRMTableNum,
                        decision.opcodeDecisions[index]);
-
-    if (index + 1 < IC_max)
-      o2 << ", ";
   }
 
   i2--;
diff --git a/llvm/utils/TableGen/X86FoldTablesEmitter.cpp b/llvm/utils/TableGen/X86FoldTablesEmitter.cpp
index 2c15e35f234d4..8026c324cd401 100644
--- a/llvm/utils/TableGen/X86FoldTablesEmitter.cpp
+++ b/llvm/utils/TableGen/X86FoldTablesEmitter.cpp
@@ -618,14 +618,14 @@ void X86FoldTablesEmitter::run(formatted_raw_ostream &OS) {
     uint8_t Opc =
         getValueFromBitsInit(MemInst->TheDef->getValueAsBitsInit("Opcode"));
 
-    if (RegInsts.count(Opc) == 0)
+    auto RegInstsIt = RegInsts.find(Opc);
+    if (RegInstsIt == RegInsts.end())
       continue;
 
     // Two forms (memory & register) of the same instruction must have the same
     // opcode. try matching only with register form instructions with the same
     // opcode.
-    std::vector<const CodeGenInstruction *> &OpcRegInsts =
-        RegInsts.find(Opc)->second;
+    std::vector<const CodeGenInstruction *> &OpcRegInsts = RegInstsIt->second;
 
     auto Match = find_if(OpcRegInsts, IsMatch(MemInst, Records));
     if (Match != OpcRegInsts.end()) {
diff --git a/llvm/utils/TableGen/X86RecognizableInstr.cpp b/llvm/utils/TableGen/X86RecognizableInstr.cpp
index 33dc6f3f9e234..1048ef81a378a 100644
--- a/llvm/utils/TableGen/X86RecognizableInstr.cpp
+++ b/llvm/utils/TableGen/X86RecognizableInstr.cpp
@@ -879,9 +879,9 @@ OperandType RecognizableInstr::typeFromString(const std::string &s,
   TYPE("i128mem",             TYPE_M)
   TYPE("i256mem",             TYPE_M)
   TYPE("i512mem",             TYPE_M)
-  TYPE("i64i32imm_pcrel",     TYPE_REL)
-  TYPE("i16imm_pcrel",        TYPE_REL)
-  TYPE("i32imm_pcrel",        TYPE_REL)
+  TYPE("i64i32imm_brtarget",  TYPE_REL)
+  TYPE("i16imm_brtarget",     TYPE_REL)
+  TYPE("i32imm_brtarget",     TYPE_REL)
   TYPE("ccode",               TYPE_IMM)
   TYPE("AVX512RC",            TYPE_IMM)
   TYPE("brtarget32",          TYPE_REL)
@@ -1169,45 +1169,45 @@ RecognizableInstr::relocationEncodingFromString(const std::string &s,
   if(OpSize != X86Local::OpSize16) {
     // For instructions without an OpSize prefix, a declared 16-bit register or
     // immediate encoding is special.
-    ENCODING("i16imm",        ENCODING_IW)
+    ENCODING("i16imm",           ENCODING_IW)
   }
-  ENCODING("i16imm",          ENCODING_Iv)
-  ENCODING("i16i8imm",        ENCODING_IB)
-  ENCODING("i32imm",          ENCODING_Iv)
-  ENCODING("i32i8imm",        ENCODING_IB)
-  ENCODING("i64i32imm",       ENCODING_ID)
-  ENCODING("i64i8imm",        ENCODING_IB)
-  ENCODING("i8imm",           ENCODING_IB)
-  ENCODING("u8imm",           ENCODING_IB)
-  ENCODING("i16u8imm",        ENCODING_IB)
-  ENCODING("i32u8imm",        ENCODING_IB)
-  ENCODING("i64u8imm",        ENCODING_IB)
-  ENCODING("i64i32imm_pcrel", ENCODING_ID)
-  ENCODING("i16imm_pcrel",    ENCODING_IW)
-  ENCODING("i32imm_pcrel",    ENCODING_ID)
-  ENCODING("brtarget32",      ENCODING_ID)
-  ENCODING("brtarget16",      ENCODING_IW)
-  ENCODING("brtarget8",       ENCODING_IB)
-  ENCODING("i64imm",          ENCODING_IO)
-  ENCODING("offset16_8",      ENCODING_Ia)
-  ENCODING("offset16_16",     ENCODING_Ia)
-  ENCODING("offset16_32",     ENCODING_Ia)
-  ENCODING("offset32_8",      ENCODING_Ia)
-  ENCODING("offset32_16",     ENCODING_Ia)
-  ENCODING("offset32_32",     ENCODING_Ia)
-  ENCODING("offset32_64",     ENCODING_Ia)
-  ENCODING("offset64_8",      ENCODING_Ia)
-  ENCODING("offset64_16",     ENCODING_Ia)
-  ENCODING("offset64_32",     ENCODING_Ia)
-  ENCODING("offset64_64",     ENCODING_Ia)
-  ENCODING("srcidx8",         ENCODING_SI)
-  ENCODING("srcidx16",        ENCODING_SI)
-  ENCODING("srcidx32",        ENCODING_SI)
-  ENCODING("srcidx64",        ENCODING_SI)
-  ENCODING("dstidx8",         ENCODING_DI)
-  ENCODING("dstidx16",        ENCODING_DI)
-  ENCODING("dstidx32",        ENCODING_DI)
-  ENCODING("dstidx64",        ENCODING_DI)
+  ENCODING("i16imm",             ENCODING_Iv)
+  ENCODING("i16i8imm",           ENCODING_IB)
+  ENCODING("i32imm",             ENCODING_Iv)
+  ENCODING("i32i8imm",           ENCODING_IB)
+  ENCODING("i64i32imm",          ENCODING_ID)
+  ENCODING("i64i8imm",           ENCODING_IB)
+  ENCODING("i8imm",              ENCODING_IB)
+  ENCODING("u8imm",              ENCODING_IB)
+  ENCODING("i16u8imm",           ENCODING_IB)
+  ENCODING("i32u8imm",           ENCODING_IB)
+  ENCODING("i64u8imm",           ENCODING_IB)
+  ENCODING("i64i32imm_brtarget", ENCODING_ID)
+  ENCODING("i16imm_brtarget",    ENCODING_IW)
+  ENCODING("i32imm_brtarget",    ENCODING_ID)
+  ENCODING("brtarget32",         ENCODING_ID)
+  ENCODING("brtarget16",         ENCODING_IW)
+  ENCODING("brtarget8",          ENCODING_IB)
+  ENCODING("i64imm",             ENCODING_IO)
+  ENCODING("offset16_8",         ENCODING_Ia)
+  ENCODING("offset16_16",        ENCODING_Ia)
+  ENCODING("offset16_32",        ENCODING_Ia)
+  ENCODING("offset32_8",         ENCODING_Ia)
+  ENCODING("offset32_16",        ENCODING_Ia)
+  ENCODING("offset32_32",        ENCODING_Ia)
+  ENCODING("offset32_64",        ENCODING_Ia)
+  ENCODING("offset64_8",         ENCODING_Ia)
+  ENCODING("offset64_16",        ENCODING_Ia)
+  ENCODING("offset64_32",        ENCODING_Ia)
+  ENCODING("offset64_64",        ENCODING_Ia)
+  ENCODING("srcidx8",            ENCODING_SI)
+  ENCODING("srcidx16",           ENCODING_SI)
+  ENCODING("srcidx32",           ENCODING_SI)
+  ENCODING("srcidx64",           ENCODING_SI)
+  ENCODING("dstidx8",            ENCODING_DI)
+  ENCODING("dstidx16",           ENCODING_DI)
+  ENCODING("dstidx32",           ENCODING_DI)
+  ENCODING("dstidx64",           ENCODING_DI)
   errs() << "Unhandled relocation encoding " << s << "\n";
   llvm_unreachable("Unhandled relocation encoding");
 }