vendor/llvm/llvm-trunk-r307894

33 files changed, 809 insertions, 1310 deletions

diff --git a/utils/TableGen/AsmMatcherEmitter.cpp b/utils/TableGen/AsmMatcherEmitter.cpp
index 0980e08f67f7..1f8e1b125889 100644
--- a/utils/TableGen/AsmMatcherEmitter.cpp
+++ b/utils/TableGen/AsmMatcherEmitter.cpp
@@ -2222,7 +2222,7 @@ static void emitValidateOperandClass(AsmMatcherInfo &Info,
   OS << "    switch (Operand.getReg()) {\n";
   OS << "    default: OpKind = InvalidMatchClass; break;\n";
   for (const auto &RC : Info.RegisterClasses)
-    OS << "    case " << Info.Target.getName() << "::"
+    OS << "    case " << RC.first->getValueAsString("Namespace") << "::"
        << RC.first->getName() << ": OpKind = " << RC.second->Name
        << "; break;\n";
   OS << "    }\n";
@@ -2711,6 +2711,47 @@ static void emitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target,
   OS << "}\n\n";
 }
 
+static void emitMnemonicSpellChecker(raw_ostream &OS, CodeGenTarget &Target,
+                                     unsigned VariantCount) {
+  OS << "std::string " << Target.getName() << "MnemonicSpellCheck(StringRef S, uint64_t FBS) {\n";
+  if (!VariantCount)
+    OS <<  "  return \"\";";
+  else {
+    OS << "  const unsigned MaxEditDist = 2;\n";
+    OS << "  std::vector<StringRef> Candidates;\n";
+    OS << "  StringRef Prev = \"\";\n";
+    OS << "  auto End = std::end(MatchTable0);\n";
+    OS << "\n";
+    OS << "  for (auto I = std::begin(MatchTable0); I < End; I++) {\n";
+    OS << "    // Ignore unsupported instructions.\n";
+    OS << "    if ((FBS & I->RequiredFeatures) != I->RequiredFeatures)\n";
+    OS << "      continue;\n";
+    OS << "\n";
+    OS << "    StringRef T = I->getMnemonic();\n";
+    OS << "    // Avoid recomputing the edit distance for the same string.\n";
+    OS << "    if (T.equals(Prev))\n";
+    OS << "      continue;\n";
+    OS << "\n";
+    OS << "    Prev = T;\n";
+    OS << "    unsigned Dist = S.edit_distance(T, false, MaxEditDist);\n";
+    OS << "    if (Dist <= MaxEditDist)\n";
+    OS << "      Candidates.push_back(T);\n";
+    OS << "  }\n";
+    OS << "\n";
+    OS << "  if (Candidates.empty())\n";
+    OS << "    return \"\";\n";
+    OS << "\n";
+    OS << "  std::string Res = \", did you mean: \";\n";
+    OS << "  unsigned i = 0;\n";
+    OS << "  for( ; i < Candidates.size() - 1; i++)\n";
+    OS << "    Res += Candidates[i].str() + \", \";\n";
+    OS << "  return Res + Candidates[i].str() + \"?\";\n";
+  }
+  OS << "}\n";
+  OS << "\n";
+}
+
+
 void AsmMatcherEmitter::run(raw_ostream &OS) {
   CodeGenTarget Target(Records);
   Record *AsmParser = Target.getAsmParser();
@@ -2948,7 +2989,7 @@ void AsmMatcherEmitter::run(raw_ostream &OS) {
       std::string LenMnemonic = char(MI->Mnemonic.size()) + MI->Mnemonic.str();
       OS << "  { " << StringTable.GetOrAddStringOffset(LenMnemonic, false)
          << " /* " << MI->Mnemonic << " */, "
-         << Target.getName() << "::"
+         << Target.getInstNamespace() << "::"
          << MI->getResultInst()->TheDef->getName() << ", "
          << MI->ConversionFnKind << ", ";
 
@@ -2974,6 +3015,8 @@ void AsmMatcherEmitter::run(raw_ostream &OS) {
     OS << "};\n\n";
   }
 
+  emitMnemonicSpellChecker(OS, Target, VariantCount);
+
   // Finally, build the match function.
   OS << "unsigned " << Target.getName() << ClassName << "::\n"
      << "MatchInstructionImpl(const OperandVector &Operands,\n";
diff --git a/utils/TableGen/AsmWriterEmitter.cpp b/utils/TableGen/AsmWriterEmitter.cpp
index 30d21984c4d3..75b9bc6cca40 100644
--- a/utils/TableGen/AsmWriterEmitter.cpp
+++ b/utils/TableGen/AsmWriterEmitter.cpp
@@ -137,12 +137,12 @@ static void EmitInstructions(std::vector<AsmWriterInst> &Insts,
       O << "    switch (MI->getOpcode()) {\n";
       O << "    default: llvm_unreachable(\"Unexpected opcode.\");\n";
       std::vector<std::pair<std::string, AsmWriterOperand>> OpsToPrint;
-      OpsToPrint.push_back(std::make_pair(FirstInst.CGI->Namespace + "::" +
+      OpsToPrint.push_back(std::make_pair(FirstInst.CGI->Namespace.str() + "::" +
                                           FirstInst.CGI->TheDef->getName().str(),
                                           FirstInst.Operands[i]));
 
       for (const AsmWriterInst &AWI : SimilarInsts) {
-        OpsToPrint.push_back(std::make_pair(AWI.CGI->Namespace+"::" +
+        OpsToPrint.push_back(std::make_pair(AWI.CGI->Namespace.str()+"::" +
                                             AWI.CGI->TheDef->getName().str(),
                                             AWI.Operands[i]));
       }
diff --git a/utils/TableGen/CodeEmitterGen.cpp b/utils/TableGen/CodeEmitterGen.cpp
index b80dd5daefe0..23751a2cbfba 100644
--- a/utils/TableGen/CodeEmitterGen.cpp
+++ b/utils/TableGen/CodeEmitterGen.cpp
@@ -187,20 +187,18 @@ AddCodeToMergeInOperand(Record *R, BitsInit *BI, const std::string &VarName,
 std::string CodeEmitterGen::getInstructionCase(Record *R,
                                                CodeGenTarget &Target) {
   std::string Case;
-  
   BitsInit *BI = R->getValueAsBitsInit("Inst");
-  const std::vector<RecordVal> &Vals = R->getValues();
   unsigned NumberedOp = 0;
-
   std::set<unsigned> NamedOpIndices;
+
   // Collect the set of operand indices that might correspond to named
   // operand, and skip these when assigning operands based on position.
   if (Target.getInstructionSet()->
        getValueAsBit("noNamedPositionallyEncodedOperands")) {
     CodeGenInstruction &CGI = Target.getInstruction(R);
-    for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
+    for (const RecordVal &RV : R->getValues()) {
       unsigned OpIdx;
-      if (!CGI.Operands.hasOperandNamed(Vals[i].getName(), OpIdx))
+      if (!CGI.Operands.hasOperandNamed(RV.getName(), OpIdx))
         continue;
 
       NamedOpIndices.insert(OpIdx);
@@ -209,13 +207,13 @@ std::string CodeEmitterGen::getInstructionCase(Record *R,
 
   // Loop over all of the fields in the instruction, determining which are the
   // operands to the instruction.
-  for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
+  for (const RecordVal &RV : R->getValues()) { 
     // Ignore fixed fields in the record, we're looking for values like:
     //    bits<5> RST = { ?, ?, ?, ?, ? };
-    if (Vals[i].getPrefix() || Vals[i].getValue()->isComplete())
+    if (RV.getPrefix() || RV.getValue()->isComplete())
       continue;
     
-    AddCodeToMergeInOperand(R, BI, Vals[i].getName(), NumberedOp,
+    AddCodeToMergeInOperand(R, BI, RV.getName(), NumberedOp,
                             NamedOpIndices, Case, Target);
   }
 
diff --git a/utils/TableGen/CodeGenInstruction.h b/utils/TableGen/CodeGenInstruction.h
index 75db17b59ac3..e173e153879c 100644
--- a/utils/TableGen/CodeGenInstruction.h
+++ b/utils/TableGen/CodeGenInstruction.h
@@ -206,7 +206,7 @@ template <typename T> class ArrayRef;
   class CodeGenInstruction {
   public:
     Record *TheDef;            // The actual record defining this instruction.
-    std::string Namespace;     // The namespace the instruction is in.
+    StringRef Namespace;       // The namespace the instruction is in.
 
     /// AsmString - The format string used to emit a .s file for the
     /// instruction.
diff --git a/utils/TableGen/CodeGenMapTable.cpp b/utils/TableGen/CodeGenMapTable.cpp
index 60db6c267ad7..43348b622a74 100644
--- a/utils/TableGen/CodeGenMapTable.cpp
+++ b/utils/TableGen/CodeGenMapTable.cpp
@@ -367,7 +367,7 @@ unsigned MapTableEmitter::emitBinSearchTable(raw_ostream &OS) {
 
   ArrayRef<const CodeGenInstruction*> NumberedInstructions =
                                             Target.getInstructionsByEnumValue();
-  std::string Namespace = Target.getInstNamespace();
+  StringRef Namespace = Target.getInstNamespace();
   const std::vector<ListInit*> &ValueCols = InstrMapDesc.getValueCols();
   unsigned NumCol = ValueCols.size();
   unsigned TotalNumInstr = NumberedInstructions.size();
@@ -567,7 +567,7 @@ namespace llvm {
 //===----------------------------------------------------------------------===//
 void EmitMapTable(RecordKeeper &Records, raw_ostream &OS) {
   CodeGenTarget Target(Records);
-  std::string NameSpace = Target.getInstNamespace();
+  StringRef NameSpace = Target.getInstNamespace();
   std::vector<Record*> InstrMapVec;
   InstrMapVec = Records.getAllDerivedDefinitions("InstrMapping");
 
diff --git a/utils/TableGen/CodeGenTarget.cpp b/utils/TableGen/CodeGenTarget.cpp
index eb277f3298f9..58df3ceceee7 100644
--- a/utils/TableGen/CodeGenTarget.cpp
+++ b/utils/TableGen/CodeGenTarget.cpp
@@ -207,7 +207,7 @@ const StringRef CodeGenTarget::getName() const {
   return TargetRec->getName();
 }
 
-std::string CodeGenTarget::getInstNamespace() const {
+StringRef CodeGenTarget::getInstNamespace() const {
   for (const CodeGenInstruction *Inst : getInstructionsByEnumValue()) {
     // Make sure not to pick up "TargetOpcode" by accidentally getting
     // the namespace off the PHI instruction or something.
diff --git a/utils/TableGen/CodeGenTarget.h b/utils/TableGen/CodeGenTarget.h
index c822e940ffae..ff624ea559e5 100644
--- a/utils/TableGen/CodeGenTarget.h
+++ b/utils/TableGen/CodeGenTarget.h
@@ -86,7 +86,7 @@ public:
 
   /// getInstNamespace - Return the target-specific instruction namespace.
   ///
-  std::string getInstNamespace() const;
+  StringRef getInstNamespace() const;
 
   /// getInstructionSet - Return the InstructionSet object.
   ///
diff --git a/utils/TableGen/DAGISelMatcherGen.cpp b/utils/TableGen/DAGISelMatcherGen.cpp
index d239f96d2a60..d4a56a64324f 100644
--- a/utils/TableGen/DAGISelMatcherGen.cpp
+++ b/utils/TableGen/DAGISelMatcherGen.cpp
@@ -886,7 +886,7 @@ EmitResultInstructionAsOperand(const TreePatternNode *N,
   assert((!ResultVTs.empty() || TreeHasOutGlue || NodeHasChain) &&
          "Node has no result");
 
-  AddMatcher(new EmitNodeMatcher(II.Namespace+"::"+II.TheDef->getName().str(),
+  AddMatcher(new EmitNodeMatcher(II.Namespace.str()+"::"+II.TheDef->getName().str(),
                                  ResultVTs, InstOps,
                                  NodeHasChain, TreeHasInGlue, TreeHasOutGlue,
                                  NodeHasMemRefs, NumFixedArityOperands,
diff --git a/utils/TableGen/FastISelEmitter.cpp b/utils/TableGen/FastISelEmitter.cpp
index 0e7b0dc09442..25388b75cc0d 100644
--- a/utils/TableGen/FastISelEmitter.cpp
+++ b/utils/TableGen/FastISelEmitter.cpp
@@ -390,10 +390,10 @@ class FastISelMap {
   std::map<OperandsSignature, std::vector<OperandsSignature> >
     SignaturesWithConstantForms;
 
-  std::string InstNS;
+  StringRef InstNS;
   ImmPredicateSet ImmediatePredicates;
 public:
-  explicit FastISelMap(std::string InstNS);
+  explicit FastISelMap(StringRef InstNS);
 
   void collectPatterns(CodeGenDAGPatterns &CGP);
   void printImmediatePredicates(raw_ostream &OS);
@@ -417,7 +417,7 @@ static std::string getLegalCName(std::string OpName) {
   return OpName;
 }
 
-FastISelMap::FastISelMap(std::string instns) : InstNS(std::move(instns)) {}
+FastISelMap::FastISelMap(StringRef instns) : InstNS(instns) {}
 
 static std::string PhyRegForNode(TreePatternNode *Op,
                                  const CodeGenTarget &Target) {
@@ -440,10 +440,6 @@ static std::string PhyRegForNode(TreePatternNode *Op,
 void FastISelMap::collectPatterns(CodeGenDAGPatterns &CGP) {
   const CodeGenTarget &Target = CGP.getTargetInfo();
 
-  // Determine the target's namespace name.
-  InstNS = Target.getInstNamespace() + "::";
-  assert(InstNS.size() > 2 && "Can't determine target-specific namespace!");
-
   // Scan through all the patterns and record the simple ones.
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(),
        E = CGP.ptm_end(); I != E; ++I) {
@@ -659,8 +655,8 @@ void FastISelMap::emitInstructionCode(raw_ostream &OS,
     if (Memo.SubRegNo.empty()) {
       Operands.PrintManglingSuffix(OS, *Memo.PhysRegs,
      ImmediatePredicates, true);
-      OS << "(" << InstNS << Memo.Name << ", ";
-      OS << "&" << InstNS << Memo.RC->getName() << "RegClass";
+      OS << "(" << InstNS << "::" << Memo.Name << ", ";
+      OS << "&" << InstNS << "::" << Memo.RC->getName() << "RegClass";
       if (!Operands.empty())
         OS << ", ";
       Operands.PrintArguments(OS, *Memo.PhysRegs);
@@ -873,8 +869,8 @@ void EmitFastISel(RecordKeeper &RK, raw_ostream &OS) {
                        Target.getName().str() + " target", OS);
 
   // Determine the target's namespace name.
-  std::string InstNS = Target.getInstNamespace() + "::";
-  assert(InstNS.size() > 2 && "Can't determine target-specific namespace!");
+  StringRef InstNS = Target.getInstNamespace();
+  assert(!InstNS.empty() && "Can't determine target-specific namespace!");
 
   FastISelMap F(InstNS);
   F.collectPatterns(CGP);
diff --git a/utils/TableGen/FixedLenDecoderEmitter.cpp b/utils/TableGen/FixedLenDecoderEmitter.cpp
index 75fd73082b9a..03930d7132df 100644
--- a/utils/TableGen/FixedLenDecoderEmitter.cpp
+++ b/utils/TableGen/FixedLenDecoderEmitter.cpp
@@ -1691,9 +1691,7 @@ void FilterChooser::emitTableEntries(DecoderTableInfo &TableInfo) const {
   dumpStack(errs(), "\t\t");
 
   for (unsigned i = 0; i < Opcodes.size(); ++i) {
-    const std::string &Name = nameWithID(Opcodes[i]);
-
-    errs() << '\t' << Name << " ";
+    errs() << '\t' << nameWithID(Opcodes[i]) << " ";
     dumpBits(errs(),
              getBitsField(*AllInstructions[Opcodes[i]]->TheDef, "Inst"));
     errs() << '\n';
diff --git a/utils/TableGen/GlobalISelEmitter.cpp b/utils/TableGen/GlobalISelEmitter.cpp
index 924ed8f65c2c..cafcbeb57de5 100644
--- a/utils/TableGen/GlobalISelEmitter.cpp
+++ b/utils/TableGen/GlobalISelEmitter.cpp
@@ -53,6 +53,8 @@ STATISTIC(NumPatternTotal, "Total number of patterns");
 STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG");
 STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped");
 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
+/// A unique identifier for a MatchTable.
+static unsigned CurrentMatchTableID = 0;
 
 cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel");
 
@@ -74,6 +76,18 @@ private:
 public:
   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 
+  void emitCxxEnumValue(raw_ostream &OS) const {
+    if (Ty.isScalar()) {
+      OS << "GILLT_s" << Ty.getSizeInBits();
+      return;
+    }
+    if (Ty.isVector()) {
+      OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits();
+      return;
+    }
+    llvm_unreachable("Unhandled LLT");
+  }
+
   void emitCxxConstructorCall(raw_ostream &OS) const {
     if (Ty.isScalar()) {
       OS << "LLT::scalar(" << Ty.getSizeInBits() << ")";
@@ -88,6 +102,33 @@ public:
   }
 
   const LLT &get() const { return Ty; }
+
+  /// This ordering is used for std::unique() and std::sort(). There's no
+  /// particular logic behind the order.
+  bool operator<(const LLTCodeGen &Other) const {
+    if (!Ty.isValid())
+      return Other.Ty.isValid();
+    if (Ty.isScalar()) {
+      if (!Other.Ty.isValid())
+        return false;
+      if (Other.Ty.isScalar())
+        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
+      return false;
+    }
+    if (Ty.isVector()) {
+      if (!Other.Ty.isValid() || Other.Ty.isScalar())
+        return false;
+      if (Other.Ty.isVector()) {
+        if (Ty.getNumElements() < Other.Ty.getNumElements())
+          return true;
+        if (Ty.getNumElements() > Other.Ty.getNumElements())
+          return false;
+        return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
+      }
+      return false;
+    }
+    llvm_unreachable("Unhandled LLT");
+  }
 };
 
 class InstructionMatcher;
@@ -169,6 +210,13 @@ static Record *getInitValueAsRegClass(Init *V) {
   return nullptr;
 }
 
+std::string
+getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) {
+  std::string Name = "GIFBS";
+  for (const auto &Feature : FeatureBitset)
+    Name += ("_" + Feature->getName()).str();
+  return Name;
+}
 //===- Matchers -----------------------------------------------------------===//
 
 class OperandMatcher;
@@ -187,8 +235,8 @@ class RuleMatcher {
   std::vector<std::unique_ptr<MatchAction>> Actions;
 
   /// A map of instruction matchers to the local variables created by
-  /// emitCxxCaptureStmts().
-  std::map<const InstructionMatcher *, std::string> InsnVariableNames;
+  /// emitCaptureOpcodes().
+  std::map<const InstructionMatcher *, unsigned> InsnVariableIDs;
 
   /// ID for the next instruction variable defined with defineInsnVar()
   unsigned NextInsnVarID;
@@ -197,35 +245,39 @@ class RuleMatcher {
 
 public:
   RuleMatcher()
-      : Matchers(), Actions(), InsnVariableNames(), NextInsnVarID(0) {}
+      : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {}
   RuleMatcher(RuleMatcher &&Other) = default;
   RuleMatcher &operator=(RuleMatcher &&Other) = default;
 
   InstructionMatcher &addInstructionMatcher();
   void addRequiredFeature(Record *Feature);
+  const std::vector<Record *> &getRequiredFeatures() const;
 
   template <class Kind, class... Args> Kind &addAction(Args &&... args);
 
-  std::string defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
-                            StringRef Value);
-  StringRef getInsnVarName(const InstructionMatcher &InsnMatcher) const;
+  /// Define an instruction without emitting any code to do so.
+  /// This is used for the root of the match.
+  unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
+  /// Define an instruction and emit corresponding state-machine opcodes.
+  unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher,
+                         unsigned InsnVarID, unsigned OpIdx);
+  unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
 
-  void emitCxxCapturedInsnList(raw_ostream &OS);
-  void emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr);
+  void emitCaptureOpcodes(raw_ostream &OS);
 
-void emit(raw_ostream &OS, SubtargetFeatureInfoMap SubtargetFeatures);
+  void emit(raw_ostream &OS);
 
-/// Compare the priority of this object and B.
-///
-/// Returns true if this object is more important than B.
-bool isHigherPriorityThan(const RuleMatcher &B) const;
+  /// Compare the priority of this object and B.
+  ///
+  /// Returns true if this object is more important than B.
+  bool isHigherPriorityThan(const RuleMatcher &B) const;
 
-/// Report the maximum number of temporary operands needed by the rule
-/// matcher.
-unsigned countRendererFns() const;
+  /// Report the maximum number of temporary operands needed by the rule
+  /// matcher.
+  unsigned countRendererFns() const;
 
-// FIXME: Remove this as soon as possible
-InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
+  // FIXME: Remove this as soon as possible
+  InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
 };
 
 template <class PredicateTy> class PredicateListMatcher {
@@ -255,21 +307,16 @@ public:
     return Predicates.size();
   }
 
-  /// Emit a C++ expression that tests whether all the predicates are met.
+  /// Emit MatchTable opcodes that tests whether all the predicates are met.
   template <class... Args>
-  void emitCxxPredicateListExpr(raw_ostream &OS, Args &&... args) const {
+  void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const {
     if (Predicates.empty()) {
-      OS << "true";
+      OS << "// No predicates\n";
       return;
     }
 
-    StringRef Separator = "";
-    for (const auto &Predicate : predicates()) {
-      OS << Separator << "(";
-      Predicate->emitCxxPredicateExpr(OS, std::forward<Args>(args)...);
-      OS << ")";
-      Separator = " &&\n";
-    }
+    for (const auto &Predicate : predicates())
+      Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...);
   }
 };
 
@@ -291,6 +338,7 @@ public:
   enum PredicateKind {
     OPM_ComplexPattern,
     OPM_Instruction,
+    OPM_IntrinsicID,
     OPM_Int,
     OPM_LiteralInt,
     OPM_LLT,
@@ -318,15 +366,17 @@ public:
     return None;
   }
 
-  /// Emit C++ statements to capture instructions into local variables.
+  /// Emit MatchTable opcodes to capture instructions into the MIs table.
   ///
-  /// Only InstructionOperandMatcher needs to do anything for this method.
-  virtual void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                                   StringRef Expr) const {}
+  /// Only InstructionOperandMatcher needs to do anything for this method the
+  /// rest just walk the tree.
+  virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                                  unsigned InsnVarID, unsigned OpIdx) const {}
 
-  /// Emit a C++ expression that checks the predicate for the given operand.
-  virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                                    StringRef OperandExpr) const = 0;
+  /// Emit MatchTable opcodes that check the predicate for the given operand.
+  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                                    unsigned InsnVarID,
+                                    unsigned OpIdx) const = 0;
 
   /// Compare the priority of this object and B.
   ///
@@ -353,11 +403,12 @@ public:
     return P->getKind() == OPM_LLT;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "MRI.getType(" << OperandExpr << ".getReg()) == (";
-    Ty.emitCxxConstructorCall(OS);
-    OS << ")";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx
+       << ", /*Type*/";
+    Ty.emitCxxEnumValue(OS);
+    OS << ", \n";
   }
 };
 
@@ -379,11 +430,12 @@ public:
     return P->getKind() == OPM_ComplexPattern;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
     unsigned ID = getAllocatedTemporariesBaseID();
-    OS << "(Renderer" << ID << " = " << TheDef.getValueAsString("MatcherFn")
-       << "(" << OperandExpr << "))";
+    OS << "    GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", /*Renderer*/" << ID << ", GICP_"
+       << TheDef.getName() << ",\n";
   }
 
   unsigned countRendererFns() const override {
@@ -404,11 +456,10 @@ public:
     return P->getKind() == OPM_RegBank;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
-       << "RegClass) == RBI.getRegBank(" << OperandExpr
-       << ".getReg(), MRI, TRI))";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n";
   }
 };
 
@@ -421,9 +472,9 @@ public:
     return P->getKind() == OPM_MBB;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << OperandExpr << ".isMBB()";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n";
   }
 };
 
@@ -441,9 +492,10 @@ public:
     return P->getKind() == OPM_Int;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", " << Value << ",\n";
   }
 };
 
@@ -461,10 +513,30 @@ public:
     return P->getKind() == OPM_LiteralInt;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OS << OperandExpr << ".isCImm() && " << OperandExpr
-       << ".getCImm()->equalsInt(" << Value << ")";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", " << Value << ",\n";
+  }
+};
+
+/// Generates code to check that an operand is an intrinsic ID.
+class IntrinsicIDOperandMatcher : public OperandPredicateMatcher {
+protected:
+  const CodeGenIntrinsic *II;
+
+public:
+  IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II)
+      : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {}
+
+  static bool classof(const OperandPredicateMatcher *P) {
+    return P->getKind() == OPM_IntrinsicID;
+  }
+
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID, unsigned OpIdx) const override {
+    OS << "    GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/"
+       << OpIdx << ", Intrinsic::" << II->EnumName << ",\n";
   }
 };
 
@@ -496,8 +568,9 @@ public:
   }
   unsigned getOperandIndex() const { return OpIdx; }
 
-  std::string getOperandExpr(StringRef InsnVarName) const {
-    return (InsnVarName + ".getOperand(" + llvm::to_string(OpIdx) + ")").str();
+  std::string getOperandExpr(unsigned InsnVarID) const {
+    return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
+           llvm::to_string(OpIdx) + ")";
   }
 
   Optional<const OperandMatcher *>
@@ -515,25 +588,24 @@ public:
 
   InstructionMatcher &getInstructionMatcher() const { return Insn; }
 
-  /// Emit C++ statements to capture instructions into local variables.
-  void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                           StringRef OperandExpr) const {
+  /// Emit MatchTable opcodes to capture instructions into the MIs table.
+  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                          unsigned InsnVarID) const {
     for (const auto &Predicate : predicates())
-      Predicate->emitCxxCaptureStmts(OS, Rule, OperandExpr);
+      Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx);
   }
 
-  /// Emit a C++ expression that tests whether the instruction named in
-  /// InsnVarName matches all the predicate and all the operands.
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const {
-    OS << "(/* ";
+  /// Emit MatchTable opcodes that test whether the instruction named in
+  /// InsnVarID matches all the predicates and all the operands.
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID) const {
+    OS << "    // MIs[" << InsnVarID << "] ";
     if (SymbolicName.empty())
       OS << "Operand " << OpIdx;
     else
       OS << SymbolicName;
-    OS << " */ ";
-    emitCxxPredicateListExpr(OS, Rule, getOperandExpr(InsnVarName));
-    OS << ")";
+    OS << "\n";
+    emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx);
   }
 
   /// Compare the priority of this object and B.
@@ -599,10 +671,10 @@ public:
 
   PredicateKind getKind() const { return Kind; }
 
-  /// Emit a C++ expression that tests whether the instruction named in
-  /// InsnVarName matches the predicate.
-  virtual void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                                    StringRef InsnVarName) const = 0;
+  /// Emit MatchTable opcodes that test whether the instruction named in
+  /// InsnVarID matches the predicate.
+  virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                                    unsigned InsnVarID) const = 0;
 
   /// Compare the priority of this object and B.
   ///
@@ -630,10 +702,10 @@ public:
     return P->getKind() == IPM_Opcode;
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const override {
-    OS << InsnVarName << ".getOpcode() == " << I->Namespace
-       << "::" << I->TheDef->getName();
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID) const override {
+    OS << "    GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace
+       << "::" << I->TheDef->getName() << ",\n";
   }
 
   /// Compare the priority of this object and B.
@@ -721,26 +793,23 @@ public:
     return make_range(operands_begin(), operands_end());
   }
 
-  /// Emit C++ statements to check the shape of the match and capture
-  /// instructions into local variables.
-  void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule, StringRef Expr) {
-    OS << "if (" << Expr << ".getNumOperands() < " << getNumOperands() << ")\n"
-       << "  return false;\n";
-    for (const auto &Operand : Operands) {
-      Operand->emitCxxCaptureStmts(OS, Rule, Operand->getOperandExpr(Expr));
-    }
+  /// Emit MatchTable opcodes to check the shape of the match and capture
+  /// instructions into the MIs table.
+  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                          unsigned InsnID) {
+    OS << "    GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/"
+       << getNumOperands() << ",\n";
+    for (const auto &Operand : Operands)
+      Operand->emitCaptureOpcodes(OS, Rule, InsnID);
   }
 
-  /// Emit a C++ expression that tests whether the instruction named in
+  /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef InsnVarName) const {
-    emitCxxPredicateListExpr(OS, Rule, InsnVarName);
-    for (const auto &Operand : Operands) {
-      OS << " &&\n(";
-      Operand->emitCxxPredicateExpr(OS, Rule, InsnVarName);
-      OS << ")";
-    }
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID) const {
+    emitPredicateListOpcodes(OS, Rule, InsnVarID);
+    for (const auto &Operand : Operands)
+      Operand->emitPredicateOpcodes(OS, Rule, InsnVarID);
   }
 
   /// Compare the priority of this object and B.
@@ -817,24 +886,17 @@ public:
     return InsnMatcher->getOptionalOperand(SymbolicName);
   }
 
-  void emitCxxCaptureStmts(raw_ostream &OS, RuleMatcher &Rule,
-                           StringRef OperandExpr) const override {
-    OS << "if (!" << OperandExpr + ".isReg())\n"
-       << "  return false;\n"
-       << "if (TRI.isPhysicalRegister(" << OperandExpr + ".getReg()))\n"
-       << "  return false;\n";
-    std::string InsnVarName = Rule.defineInsnVar(
-        OS, *InsnMatcher,
-        ("*MRI.getVRegDef(" + OperandExpr + ".getReg())").str());
-    InsnMatcher->emitCxxCaptureStmts(OS, Rule, InsnVarName);
+  void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                          unsigned InsnID, unsigned OpIdx) const override {
+    unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx);
+    InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID);
   }
 
-  void emitCxxPredicateExpr(raw_ostream &OS, RuleMatcher &Rule,
-                            StringRef OperandExpr) const override {
-    OperandExpr = Rule.getInsnVarName(*InsnMatcher);
-    OS << "(";
-    InsnMatcher->emitCxxPredicateExpr(OS, Rule, OperandExpr);
-    OS << ")\n";
+  void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule,
+                            unsigned InsnVarID_,
+                            unsigned OpIdx_) const override {
+    unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
+    InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID);
   }
 };
 
@@ -858,13 +920,14 @@ public:
 
   RendererKind getKind() const { return Kind; }
 
-  virtual void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const = 0;
+  virtual void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const = 0;
 };
 
 /// A CopyRenderer emits code to copy a single operand from an existing
 /// instruction to the one being built.
 class CopyRenderer : public OperandRenderer {
 protected:
+  unsigned NewInsnID;
   /// The matcher for the instruction that this operand is copied from.
   /// This provides the facility for looking up an a operand by it's name so
   /// that it can be used as a source for the instruction being built.
@@ -873,9 +936,10 @@ protected:
   const StringRef SymbolicName;
 
 public:
-  CopyRenderer(const InstructionMatcher &Matched, StringRef SymbolicName)
-      : OperandRenderer(OR_Copy), Matched(Matched), SymbolicName(SymbolicName) {
-  }
+  CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
+               StringRef SymbolicName)
+      : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched),
+        SymbolicName(SymbolicName) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Copy;
@@ -883,12 +947,12 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
+  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
-    StringRef InsnVarName =
-        Rule.getInsnVarName(Operand.getInstructionMatcher());
-    std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
-    OS << "    MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n";
+    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
+    OS << "    GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/"
+       << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // "
+       << SymbolicName << "\n";
   }
 };
 
@@ -897,6 +961,7 @@ public:
 /// subregister should be copied.
 class CopySubRegRenderer : public OperandRenderer {
 protected:
+  unsigned NewInsnID;
   /// The matcher for the instruction that this operand is copied from.
   /// This provides the facility for looking up an a operand by it's name so
   /// that it can be used as a source for the instruction being built.
@@ -907,9 +972,9 @@ protected:
   const CodeGenSubRegIndex *SubReg;
 
 public:
-  CopySubRegRenderer(const InstructionMatcher &Matched, StringRef SymbolicName,
-                     const CodeGenSubRegIndex *SubReg)
-      : OperandRenderer(OR_CopySubReg), Matched(Matched),
+  CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched,
+                     StringRef SymbolicName, const CodeGenSubRegIndex *SubReg)
+      : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched),
         SymbolicName(SymbolicName), SubReg(SubReg) {}
 
   static bool classof(const OperandRenderer *R) {
@@ -918,13 +983,13 @@ public:
 
   const StringRef getSymbolicName() const { return SymbolicName; }
 
-  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
+  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
     const OperandMatcher &Operand = Matched.getOperand(SymbolicName);
-    StringRef InsnVarName =
-        Rule.getInsnVarName(Operand.getInstructionMatcher());
-    std::string OperandExpr = Operand.getOperandExpr(InsnVarName);
-    OS << "    MIB.addReg(" << OperandExpr << ".getReg() /*" << SymbolicName
-       << "*/, 0, " << SubReg->EnumValue << ");\n";
+    unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher());
+    OS << "    GIR_CopySubReg, /*NewInsnID*/" << NewInsnID
+       << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/"
+       << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue
+       << ", // " << SymbolicName << "\n";
   }
 };
 
@@ -932,39 +997,44 @@ public:
 /// This is typically useful for WZR/XZR on AArch64.
 class AddRegisterRenderer : public OperandRenderer {
 protected:
+  unsigned InsnID;
   const Record *RegisterDef;
 
 public:
-  AddRegisterRenderer(const Record *RegisterDef)
-      : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {}
+  AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef)
+      : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) {
+  }
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Register;
   }
 
-  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "    MIB.addReg(" << (RegisterDef->getValue("Namespace")
-                                    ? RegisterDef->getValueAsString("Namespace")
-                                    : "")
-       << "::" << RegisterDef->getName() << ");\n";
+  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
+    OS << "      GIR_AddRegister, /*InsnID*/" << InsnID << ", "
+       << (RegisterDef->getValue("Namespace")
+               ? RegisterDef->getValueAsString("Namespace")
+               : "")
+       << "::" << RegisterDef->getName() << ",\n";
   }
 };
 
 /// Adds a specific immediate to the instruction being built.
 class ImmRenderer : public OperandRenderer {
 protected:
+  unsigned InsnID;
   int64_t Imm;
 
 public:
-  ImmRenderer(int64_t Imm)
-      : OperandRenderer(OR_Imm), Imm(Imm) {}
+  ImmRenderer(unsigned InsnID, int64_t Imm)
+      : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_Imm;
   }
 
-  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "    MIB.addImm(" << Imm << ");\n";
+  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
+    OS << "      GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm
+       << ",\n";
   }
 };
 
@@ -972,6 +1042,7 @@ public:
 /// matcher function.
 class RenderComplexPatternOperand : public OperandRenderer {
 private:
+  unsigned InsnID;
   const Record &TheDef;
   /// The name of the operand.
   const StringRef SymbolicName;
@@ -984,17 +1055,18 @@ private:
   }
 
 public:
-  RenderComplexPatternOperand(const Record &TheDef, StringRef SymbolicName,
-                              unsigned RendererID)
-      : OperandRenderer(OR_ComplexPattern), TheDef(TheDef),
+  RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef,
+                              StringRef SymbolicName, unsigned RendererID)
+      : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef),
         SymbolicName(SymbolicName), RendererID(RendererID) {}
 
   static bool classof(const OperandRenderer *R) {
     return R->getKind() == OR_ComplexPattern;
   }
 
-  void emitCxxRenderStmts(raw_ostream &OS, RuleMatcher &Rule) const override {
-    OS << "Renderer" << RendererID << "(MIB);\n";
+  void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override {
+    OS << "    GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/"
+       << RendererID << ",\n";
   }
 };
 
@@ -1009,11 +1081,11 @@ public:
 
   /// Emit the C++ statements to implement the action.
   ///
-  /// \param RecycleVarName If given, it's an instruction to recycle. The
-  ///                       requirements on the instruction vary from action to
-  ///                       action.
+  /// \param RecycleInsnID If given, it's an instruction to recycle. The
+  ///                      requirements on the instruction vary from action to
+  ///                      action.
   virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                                  StringRef RecycleVarName) const = 0;
+                                  unsigned RecycleInsnID) const = 0;
 };
 
 /// Generates a comment describing the matched rule being acted upon.
@@ -1025,8 +1097,9 @@ public:
   DebugCommentAction(const PatternToMatch &P) : P(P) {}
 
   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          StringRef RecycleVarName) const override {
-    OS << "// " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern() << "\n";
+                          unsigned RecycleInsnID) const override {
+    OS << "    // " << *P.getSrcPattern() << "  =>  " << *P.getDstPattern()
+       << "\n";
   }
 };
 
@@ -1034,7 +1107,7 @@ public:
 /// into the desired instruction when this is possible.
 class BuildMIAction : public MatchAction {
 private:
-  std::string Name;
+  unsigned InsnID;
   const CodeGenInstruction *I;
   const InstructionMatcher &Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
@@ -1058,9 +1131,9 @@ private:
   }
 
 public:
-  BuildMIAction(const StringRef Name, const CodeGenInstruction *I,
+  BuildMIAction(unsigned InsnID, const CodeGenInstruction *I,
                 const InstructionMatcher &Matched)
-      : Name(Name), I(I), Matched(Matched) {}
+      : InsnID(InsnID), I(I), Matched(Matched) {}
 
   template <class Kind, class... Args>
   Kind &addRenderer(Args&&... args) {
@@ -1070,84 +1143,74 @@ public:
   }
 
   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          StringRef RecycleVarName) const override {
+                          unsigned RecycleInsnID) const override {
     if (canMutate()) {
-      OS << "    " << RecycleVarName << ".setDesc(TII.get(" << I->Namespace
-         << "::" << I->TheDef->getName() << "));\n";
+      OS << "    GIR_MutateOpcode, /*InsnID*/" << InsnID
+         << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/"
+         << I->Namespace << "::" << I->TheDef->getName() << ",\n";
 
       if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) {
-        OS << "    auto MIB = MachineInstrBuilder(MF, &" << RecycleVarName
-           << ");\n";
-
         for (auto Def : I->ImplicitDefs) {
           auto Namespace = Def->getValue("Namespace")
                                ? Def->getValueAsString("Namespace")
                                : "";
-          OS << "    MIB.addDef(" << Namespace << "::" << Def->getName()
-             << ", RegState::Implicit);\n";
+          OS << "    GIR_AddImplicitDef, " << InsnID << ", " << Namespace
+             << "::" << Def->getName() << ",\n";
         }
         for (auto Use : I->ImplicitUses) {
           auto Namespace = Use->getValue("Namespace")
                                ? Use->getValueAsString("Namespace")
                                : "";
-          OS << "    MIB.addUse(" << Namespace << "::" << Use->getName()
-             << ", RegState::Implicit);\n";
+          OS << "    GIR_AddImplicitUse, " << InsnID << ", " << Namespace
+             << "::" << Use->getName() << ",\n";
         }
       }
-
-      OS << "    MachineInstr &" << Name << " = " << RecycleVarName << ";\n";
       return;
     }
 
     // TODO: Simple permutation looks like it could be almost as common as
     //       mutation due to commutative operations.
 
-    OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, "
-          "I.getDebugLoc(), TII.get("
-       << I->Namespace << "::" << I->TheDef->getName() << "));\n";
+    OS << "    GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/"
+       << I->Namespace << "::" << I->TheDef->getName() << ",\n";
     for (const auto &Renderer : OperandRenderers)
-      Renderer->emitCxxRenderStmts(OS, Rule);
-    OS << "    for (const auto *FromMI : ";
-    Rule.emitCxxCapturedInsnList(OS);
-    OS << ")\n";
-    OS << "      for (const auto &MMO : FromMI->memoperands())\n";
-    OS << "        MIB.addMemOperand(MMO);\n";
-    OS << "    " << RecycleVarName << ".eraseFromParent();\n";
-    OS << "    MachineInstr &" << Name << " = *MIB;\n";
+      Renderer->emitRenderOpcodes(OS, Rule);
+
+    OS << "    GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n"
+       << "    GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n";
   }
 };
 
 /// Generates code to constrain the operands of an output instruction to the
 /// register classes specified by the definition of that instruction.
 class ConstrainOperandsToDefinitionAction : public MatchAction {
-  std::string Name;
+  unsigned InsnID;
 
 public:
-  ConstrainOperandsToDefinitionAction(const StringRef Name) : Name(Name) {}
+  ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {}
 
   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          StringRef RecycleVarName) const override {
-    OS << "      constrainSelectedInstRegOperands(" << Name
-       << ", TII, TRI, RBI);\n";
+                          unsigned RecycleInsnID) const override {
+    OS << "    GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n";
   }
 };
 
 /// Generates code to constrain the specified operand of an output instruction
 /// to the specified register class.
 class ConstrainOperandToRegClassAction : public MatchAction {
-  std::string Name;
+  unsigned InsnID;
   unsigned OpIdx;
   const CodeGenRegisterClass &RC;
 
 public:
-  ConstrainOperandToRegClassAction(const StringRef Name, unsigned OpIdx,
+  ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx,
                                    const CodeGenRegisterClass &RC)
-      : Name(Name), OpIdx(OpIdx), RC(RC) {}
+      : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {}
 
   void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule,
-                          StringRef RecycleVarName) const override {
-    OS << "      constrainOperandRegToRegClass(" << Name << ", " << OpIdx
-       << ", " << RC.getQualifiedName() << "RegClass, TII, TRI, RBI);\n";
+                          unsigned RecycleInsnID) const override {
+    OS << "    GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/"
+       << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n";
   }
 };
 
@@ -1160,53 +1223,49 @@ void RuleMatcher::addRequiredFeature(Record *Feature) {
   RequiredFeatures.push_back(Feature);
 }
 
+const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const {
+  return RequiredFeatures;
+}
+
 template <class Kind, class... Args>
 Kind &RuleMatcher::addAction(Args &&... args) {
   Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
   return *static_cast<Kind *>(Actions.back().get());
 }
 
-std::string RuleMatcher::defineInsnVar(raw_ostream &OS,
-                                       const InstructionMatcher &Matcher,
-                                       StringRef Value) {
-  std::string InsnVarName = "MI" + llvm::to_string(NextInsnVarID++);
-  OS << "MachineInstr &" << InsnVarName << " = " << Value << ";\n";
-  InsnVariableNames[&Matcher] = InsnVarName;
-  return InsnVarName;
+unsigned
+RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
+  unsigned NewInsnVarID = NextInsnVarID++;
+  InsnVariableIDs[&Matcher] = NewInsnVarID;
+  return NewInsnVarID;
 }
 
-StringRef
-RuleMatcher::getInsnVarName(const InstructionMatcher &InsnMatcher) const {
-  const auto &I = InsnVariableNames.find(&InsnMatcher);
-  if (I != InsnVariableNames.end())
-    return I->second;
-  llvm_unreachable("Matched Insn was not captured in a local variable");
+unsigned RuleMatcher::defineInsnVar(raw_ostream &OS,
+                                    const InstructionMatcher &Matcher,
+                                    unsigned InsnID, unsigned OpIdx) {
+  unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
+  OS << "    GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/"
+     << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID
+     << "]\n";
+  return NewInsnVarID;
 }
 
-/// Emit a C++ initializer_list containing references to every matched
-/// instruction.
-void RuleMatcher::emitCxxCapturedInsnList(raw_ostream &OS) {
-  SmallVector<StringRef, 2> Names;
-  for (const auto &Pair : InsnVariableNames)
-    Names.push_back(Pair.second);
-  std::sort(Names.begin(), Names.end());
-
-  OS << "{";
-  for (const auto &Name : Names)
-    OS << "&" << Name << ", ";
-  OS << "}";
+unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
+  const auto &I = InsnVariableIDs.find(&InsnMatcher);
+  if (I != InsnVariableIDs.end())
+    return I->second;
+  llvm_unreachable("Matched Insn was not captured in a local variable");
 }
 
-/// Emit C++ statements to check the shape of the match and capture
+/// Emit MatchTable opcodes to check the shape of the match and capture
 /// instructions into local variables.
-void RuleMatcher::emitCxxCaptureStmts(raw_ostream &OS, StringRef Expr) {
+void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) {
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
-  std::string InsnVarName = defineInsnVar(OS, *Matchers.front(), Expr);
-  Matchers.front()->emitCxxCaptureStmts(OS, *this, InsnVarName);
+  unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
+  Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID);
 }
 
-void RuleMatcher::emit(raw_ostream &OS,
-                       SubtargetFeatureInfoMap SubtargetFeatures) {
+void RuleMatcher::emit(raw_ostream &OS) {
   if (Matchers.empty())
     llvm_unreachable("Unexpected empty matcher!");
 
@@ -1221,47 +1280,34 @@ void RuleMatcher::emit(raw_ostream &OS,
   // on some targets but we don't need to make use of that yet.
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
 
-  OS << "if (";
-  OS << "[&]() {\n";
+  OS << "  const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n";
   if (!RequiredFeatures.empty()) {
-    OS << "  PredicateBitset ExpectedFeatures = {";
-    StringRef Separator = "";
-    for (const auto &Predicate : RequiredFeatures) {
-      const auto &I = SubtargetFeatures.find(Predicate);
-      assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
-      OS << Separator << I->second.getEnumBitName();
-      Separator = ", ";
-    }
-    OS << "};\n";
-    OS << "if ((AvailableFeatures & ExpectedFeatures) != ExpectedFeatures)\n"
-       << "  return false;\n";
+    OS << "    GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures)
+       << ",\n";
   }
 
-  emitCxxCaptureStmts(OS, "I");
+  emitCaptureOpcodes(OS);
 
-  OS << "    if (";
-  Matchers.front()->emitCxxPredicateExpr(OS, *this,
-                                         getInsnVarName(*Matchers.front()));
-  OS << ") {\n";
+  Matchers.front()->emitPredicateOpcodes(OS, *this,
+                                         getInsnVarID(*Matchers.front()));
 
   // We must also check if it's safe to fold the matched instructions.
-  if (InsnVariableNames.size() >= 2) {
+  if (InsnVariableIDs.size() >= 2) {
     // Invert the map to create stable ordering (by var names)
-    SmallVector<StringRef, 2> Names;
-    for (const auto &Pair : InsnVariableNames) {
+    SmallVector<unsigned, 2> InsnIDs;
+    for (const auto &Pair : InsnVariableIDs) {
       // Skip the root node since it isn't moving anywhere. Everything else is
       // sinking to meet it.
       if (Pair.first == Matchers.front().get())
         continue;
 
-      Names.push_back(Pair.second);
+      InsnIDs.push_back(Pair.second);
     }
-    std::sort(Names.begin(), Names.end());
+    std::sort(InsnIDs.begin(), InsnIDs.end());
 
-    for (const auto &Name : Names) {
+    for (const auto &InsnID : InsnIDs) {
       // Reject the difficult cases until we have a more accurate check.
-      OS << "      if (!isObviouslySafeToFold(" << Name
-         << ")) return false;\n";
+      OS << "    GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n";
 
       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
       //        account for unsafe cases.
@@ -1300,14 +1346,17 @@ void RuleMatcher::emit(raw_ostream &OS,
     }
   }
 
-  for (const auto &MA : Actions) {
-    MA->emitCxxActionStmts(OS, *this, "I");
-  }
-
-  OS << "      return true;\n";
-  OS << "    }\n";
-  OS << "    return false;\n";
-  OS << "  }()) { return true; }\n\n";
+  for (const auto &MA : Actions)
+    MA->emitCxxActionStmts(OS, *this, 0);
+  OS << "    GIR_Done,\n"
+     << "  };\n"
+     << "  State.MIs.resize(1);\n"
+     << "  DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID
+     << "\\n\");\n"
+     << "  if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable"
+     << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n"
+     << "    return true;\n"
+     << "  }\n\n";
 }
 
 bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const {
@@ -1366,7 +1415,8 @@ private:
   Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates);
   Expected<InstructionMatcher &>
   createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
-                               const TreePatternNode *Src) const;
+                               const TreePatternNode *Src,
+                               unsigned &TempOpIdx) const;
   Error importChildMatcher(InstructionMatcher &InsnMatcher,
                            const TreePatternNode *SrcChild, unsigned OpIdx,
                            unsigned &TempOpIdx) const;
@@ -1425,8 +1475,12 @@ GlobalISelEmitter::importRulePredicates(RuleMatcher &M,
   return Error::success();
 }
 
-Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
-    InstructionMatcher &InsnMatcher, const TreePatternNode *Src) const {
+Expected<InstructionMatcher &>
+GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher,
+                                                const TreePatternNode *Src,
+                                                unsigned &TempOpIdx) const {
+  const CodeGenInstruction *SrcGIOrNull = nullptr;
+
   // Start with the defined operands (i.e., the results of the root operator).
   if (Src->getExtTypes().size() > 1)
     return failedImport("Src pattern has multiple results");
@@ -1440,7 +1494,7 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
       return failedImport(
           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
   } else {
-    auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
+    SrcGIOrNull = findNodeEquiv(Src->getOperator());
     if (!SrcGIOrNull)
       return failedImport("Pattern operator lacks an equivalent Instruction" +
                           explainOperator(Src->getOperator()));
@@ -1451,7 +1505,6 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
   }
 
   unsigned OpIdx = 0;
-  unsigned TempOpIdx = 0;
   for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
     auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
 
@@ -1474,10 +1527,27 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher(
       return failedImport(
           "Unable to deduce gMIR opcode to handle Src (which is a leaf)");
   } else {
+    assert(SrcGIOrNull &&
+           "Expected to have already found an equivalent Instruction");
     // Match the used operands (i.e. the children of the operator).
     for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
-      if (auto Error = importChildMatcher(InsnMatcher, Src->getChild(i),
-                                          OpIdx++, TempOpIdx))
+      TreePatternNode *SrcChild = Src->getChild(i);
+
+      // For G_INTRINSIC, the operand immediately following the defs is an
+      // intrinsic ID.
+      if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) {
+        if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) {
+          OperandMatcher &OM =
+              InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx);
+          OM.addPredicate<IntrinsicIDOperandMatcher>(II);
+          continue;
+        }
+
+        return failedImport("Expected IntInit containing instrinsic ID)");
+      }
+
+      if (auto Error =
+              importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx))
         return std::move(Error);
     }
   }
@@ -1513,7 +1583,7 @@ Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
 
   auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
   if (!OpTyOrNone)
-    return failedImport("Src operand has an unsupported type");
+    return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")");
   OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone);
 
   // Check for nested instructions.
@@ -1521,8 +1591,8 @@ Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher,
     // Map the node to a gMIR instruction.
     InstructionOperandMatcher &InsnOperand =
         OM.addPredicate<InstructionOperandMatcher>();
-    auto InsnMatcherOrError =
-        createAndImportSelDAGMatcher(InsnOperand.getInsnMatcher(), SrcChild);
+    auto InsnMatcherOrError = createAndImportSelDAGMatcher(
+        InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx);
     if (auto Error = InsnMatcherOrError.takeError())
       return Error;
 
@@ -1581,7 +1651,7 @@ Error GlobalISelEmitter::importExplicitUseRenderer(
     if (DstChild->getOperator()->isSubClassOf("SDNode")) {
       auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator());
       if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
-        DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher,
+        DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
                                                DstChild->getName());
         return Error::success();
       }
@@ -1606,13 +1676,14 @@ Error GlobalISelEmitter::importExplicitUseRenderer(
       return failedImport("Dst operand has an unsupported type");
 
     if (ChildRec->isSubClassOf("Register")) {
-      DstMIBuilder.addRenderer<AddRegisterRenderer>(ChildRec);
+      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec);
       return Error::success();
     }
 
     if (ChildRec->isSubClassOf("RegisterClass") ||
         ChildRec->isSubClassOf("RegisterOperand")) {
-      DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstChild->getName());
+      DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher,
+                                             DstChild->getName());
       return Error::success();
     }
 
@@ -1624,7 +1695,7 @@ Error GlobalISelEmitter::importExplicitUseRenderer(
 
       const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName());
       DstMIBuilder.addRenderer<RenderComplexPatternOperand>(
-          *ComplexPattern->second, DstChild->getName(),
+          0, *ComplexPattern->second, DstChild->getName(),
           OM.getAllocatedTemporariesBaseID());
       return Error::success();
     }
@@ -1667,12 +1738,12 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
     IsExtractSubReg = true;
   }
 
-  auto &DstMIBuilder = M.addAction<BuildMIAction>("NewI", DstI, InsnMatcher);
+  auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher);
 
   // Render the explicit defs.
   for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) {
     const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I];
-    DstMIBuilder.addRenderer<CopyRenderer>(InsnMatcher, DstIOperand.Name);
+    DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name);
   }
 
   // EXTRACT_SUBREG needs to use a subregister COPY.
@@ -1695,7 +1766,7 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer(
       }
 
       DstMIBuilder.addRenderer<CopySubRegRenderer>(
-          InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
+          0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx);
       return DstMIBuilder;
     }
 
@@ -1751,12 +1822,12 @@ Error GlobalISelEmitter::importDefaultOperandRenderers(
     }
 
     if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) {
-      DstMIBuilder.addRenderer<AddRegisterRenderer>(DefaultDefOp->getDef());
+      DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef());
       continue;
     }
 
     if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) {
-      DstMIBuilder.addRenderer<ImmRenderer>(DefaultIntOp->getValue());
+      DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue());
       continue;
     }
 
@@ -1809,7 +1880,9 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
                         to_string(DstI.Operands.NumDefs) + " def(s))");
 
   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher();
-  auto InsnMatcherOrError = createAndImportSelDAGMatcher(InsnMatcherTemp, Src);
+  unsigned TempOpIdx = 0;
+  auto InsnMatcherOrError =
+      createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx);
   if (auto Error = InsnMatcherOrError.takeError())
     return std::move(Error);
   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
@@ -1875,7 +1948,7 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
       return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class");
 
     M.addAction<ConstrainOperandToRegClassAction>(
-        "NewI", 0, Target.getRegisterClass(DstIOpRec));
+        0, 0, Target.getRegisterClass(DstIOpRec));
 
     // We're done with this pattern!  It's eligible for GISel emission; return
     // it.
@@ -1903,8 +1976,7 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
       return failedImport("EXTRACT_SUBREG operand #1 isn't a register class");
 
     CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef());
-    CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(
-        getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()));
+    CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec);
 
     // It would be nice to leave this constraint implicit but we're required
     // to pick a register class so constrain the result to a register class
@@ -1918,12 +1990,16 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
     const auto &SrcRCDstRCPair =
         SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx);
     assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass");
-    M.addAction<ConstrainOperandToRegClassAction>("NewI", 0,
-                                                  *SrcRCDstRCPair->second);
-    M.addAction<ConstrainOperandToRegClassAction>("NewI", 1,
-                                                  *SrcRCDstRCPair->first);
-  } else
-    M.addAction<ConstrainOperandsToDefinitionAction>("NewI");
+    M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second);
+    M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first);
+
+    // We're done with this pattern!  It's eligible for GISel emission; return
+    // it.
+    ++NumPatternImported;
+    return std::move(M);
+  }
+
+  M.addAction<ConstrainOperandsToDefinitionAction>(0);
 
   // We're done with this pattern!  It's eligible for GISel emission; return it.
   ++NumPatternImported;
@@ -1969,6 +2045,14 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
               return false;
             });
 
+  std::vector<Record *> ComplexPredicates =
+      RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
+  std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
+            [](const Record *A, const Record *B) {
+              if (A->getName() < B->getName())
+                return true;
+              return false;
+            });
   unsigned MaxTemporaries = 0;
   for (const auto &Rule : Rules)
     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
@@ -1980,15 +2064,26 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
         "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n"
      << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n";
 
-  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n";
-  for (unsigned I = 0; I < MaxTemporaries; ++I)
-    OS << "  mutable ComplexRendererFn Renderer" << I << ";\n";
-  OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
-
-  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n";
-  for (unsigned I = 0; I < MaxTemporaries; ++I)
-    OS << ", Renderer" << I << "(nullptr)\n";
-  OS << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n"
+     << "  mutable MatcherState State;\n"
+     << "  typedef "
+        "ComplexRendererFn("
+     << Target.getName()
+     << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n"
+     << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> "
+        "MatcherInfo;\n"
+     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n";
+
+  OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
+     << ", State(" << MaxTemporaries << "),\n"
+     << "MatcherInfo({TypeObjects, FeatureBitsets, {\n"
+     << "  nullptr, // GICP_Invalid\n";
+  for (const auto &Record : ComplexPredicates)
+    OS << "  &" << Target.getName()
+       << "InstructionSelector::" << Record->getValueAsString("MatcherFn")
+       << ", // " << Record->getName() << "\n";
+  OS << "}})\n"
+     << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
   SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures,
@@ -2016,19 +2111,107 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
       "const MachineFunction *MF");
 
+  // Emit a table containing the LLT objects needed by the matcher and an enum
+  // for the matcher to reference them with.
+  std::vector<LLTCodeGen> TypeObjects = {
+      LLT::scalar(8),      LLT::scalar(16),     LLT::scalar(32),
+      LLT::scalar(64),     LLT::scalar(80),     LLT::vector(8, 1),
+      LLT::vector(16, 1),  LLT::vector(32, 1),  LLT::vector(64, 1),
+      LLT::vector(8, 8),   LLT::vector(16, 8),  LLT::vector(32, 8),
+      LLT::vector(64, 8),  LLT::vector(4, 16),  LLT::vector(8, 16),
+      LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32),
+      LLT::vector(4, 32),  LLT::vector(8, 32),  LLT::vector(16, 32),
+      LLT::vector(2, 64),  LLT::vector(4, 64),  LLT::vector(8, 64),
+  };
+  std::sort(TypeObjects.begin(), TypeObjects.end());
+  OS << "enum {\n";
+  for (const auto &TypeObject : TypeObjects) {
+    OS << "  ";
+    TypeObject.emitCxxEnumValue(OS);
+    OS << ",\n";
+  }
+  OS << "};\n"
+     << "const static LLT TypeObjects[] = {\n";
+  for (const auto &TypeObject : TypeObjects) {
+    OS << "  ";
+    TypeObject.emitCxxConstructorCall(OS);
+    OS << ",\n";
+  }
+  OS << "};\n\n";
+
+  // Emit a table containing the PredicateBitsets objects needed by the matcher
+  // and an enum for the matcher to reference them with.
+  std::vector<std::vector<Record *>> FeatureBitsets;
+  for (auto &Rule : Rules)
+    FeatureBitsets.push_back(Rule.getRequiredFeatures());
+  std::sort(
+      FeatureBitsets.begin(), FeatureBitsets.end(),
+      [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
+        if (A.size() < B.size())
+          return true;
+        if (A.size() > B.size())
+          return false;
+        for (const auto &Pair : zip(A, B)) {
+          if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())
+            return true;
+          if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName())
+            return false;
+        }
+        return false;
+      });
+  FeatureBitsets.erase(
+      std::unique(FeatureBitsets.begin(), FeatureBitsets.end()),
+      FeatureBitsets.end());
+  OS << "enum {\n"
+     << "  GIFBS_Invalid,\n";
+  for (const auto &FeatureBitset : FeatureBitsets) {
+    if (FeatureBitset.empty())
+      continue;
+    OS << "  " << getNameForFeatureBitset(FeatureBitset) << ",\n";
+  }
+  OS << "};\n"
+     << "const static PredicateBitset FeatureBitsets[] {\n"
+     << "  {}, // GIFBS_Invalid\n";
+  for (const auto &FeatureBitset : FeatureBitsets) {
+    if (FeatureBitset.empty())
+      continue;
+    OS << "  {";
+    for (const auto &Feature : FeatureBitset) {
+      const auto &I = SubtargetFeatures.find(Feature);
+      assert(I != SubtargetFeatures.end() && "Didn't import predicate?");
+      OS << I->second.getEnumBitName() << ", ";
+    }
+    OS << "},\n";
+  }
+  OS << "};\n\n";
+
+  // Emit complex predicate table and an enum to reference them with.
+  OS << "enum {\n"
+     << "  GICP_Invalid,\n";
+  for (const auto &Record : ComplexPredicates)
+    OS << "  GICP_" << Record->getName() << ",\n";
+  OS << "};\n"
+     << "// See constructor for table contents\n\n";
+
   OS << "bool " << Target.getName()
      << "InstructionSelector::selectImpl(MachineInstr &I) const {\n"
      << "  MachineFunction &MF = *I.getParent()->getParent();\n"
-     << "  const MachineRegisterInfo &MRI = MF.getRegInfo();\n"
+     << "  MachineRegisterInfo &MRI = MF.getRegInfo();\n"
      << "  // FIXME: This should be computed on a per-function basis rather "
         "than per-insn.\n"
      << "  AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, "
         "&MF);\n"
-     << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n";
+     << "  const PredicateBitset AvailableFeatures = getAvailableFeatures();\n"
+     << "  NewMIVector OutMIs;\n"
+     << "  State.MIs.clear();\n"
+     << "  State.MIs.push_back(&I);\n\n";
 
   for (auto &Rule : Rules) {
-    Rule.emit(OS, SubtargetFeatures);
+    Rule.emit(OS);
+    ++CurrentMatchTableID;
     ++NumPatternEmitted;
+    assert(CurrentMatchTableID == NumPatternEmitted &&
+           "Statistic deviates from number of emitted tables");
   }
 
   OS << "  return false;\n"
diff --git a/utils/TableGen/InstrInfoEmitter.cpp b/utils/TableGen/InstrInfoEmitter.cpp
index ab7d964cd671..e270a17356f7 100644
--- a/utils/TableGen/InstrInfoEmitter.cpp
+++ b/utils/TableGen/InstrInfoEmitter.cpp
@@ -67,7 +67,7 @@ private:
   void emitOperandTypesEnum(raw_ostream &OS, const CodeGenTarget &Target);
   void initOperandMapData(
             ArrayRef<const CodeGenInstruction *> NumberedInstructions,
-            const std::string &Namespace,
+            StringRef Namespace,
             std::map<std::string, unsigned> &Operands,
             OpNameMapTy &OperandMap);
   void emitOperandNameMappings(raw_ostream &OS, const CodeGenTarget &Target,
@@ -207,7 +207,7 @@ void InstrInfoEmitter::EmitOperandInfo(raw_ostream &OS,
 ///        well as the getNamedOperandIdx() function.
 void InstrInfoEmitter::initOperandMapData(
         ArrayRef<const CodeGenInstruction *> NumberedInstructions,
-        const std::string &Namespace,
+        StringRef Namespace,
         std::map<std::string, unsigned> &Operands,
         OpNameMapTy &OperandMap) {
   unsigned NumOperands = 0;
@@ -224,7 +224,7 @@ void InstrInfoEmitter::initOperandMapData(
       }
       OpList[I->second] = Info.MIOperandNo;
     }
-    OperandMap[OpList].push_back(Namespace + "::" +
+    OperandMap[OpList].push_back(Namespace.str() + "::" +
                                  Inst->TheDef->getName().str());
   }
 }
@@ -243,7 +243,7 @@ void InstrInfoEmitter::initOperandMapData(
 void InstrInfoEmitter::emitOperandNameMappings(raw_ostream &OS,
            const CodeGenTarget &Target,
            ArrayRef<const CodeGenInstruction*> NumberedInstructions) {
-  const std::string &Namespace = Target.getInstNamespace();
+  StringRef Namespace = Target.getInstNamespace();
   std::string OpNameNS = "OpName";
   // Map of operand names to their enumeration value.  This will be used to
   // generate the OpName enum.
@@ -315,7 +315,7 @@ void InstrInfoEmitter::emitOperandNameMappings(raw_ostream &OS,
 void InstrInfoEmitter::emitOperandTypesEnum(raw_ostream &OS,
                                             const CodeGenTarget &Target) {
 
-  const std::string &Namespace = Target.getInstNamespace();
+  StringRef Namespace = Target.getInstNamespace();
   std::vector<Record *> Operands = Records.getAllDerivedDefinitions("Operand");
 
   OS << "#ifdef GET_INSTRINFO_OPERAND_TYPES_ENUM\n";
@@ -576,7 +576,7 @@ void InstrInfoEmitter::emitEnums(raw_ostream &OS) {
   CodeGenTarget Target(Records);
 
   // We must emit the PHI opcode first...
-  std::string Namespace = Target.getInstNamespace();
+  StringRef Namespace = Target.getInstNamespace();
 
   if (Namespace.empty())
     PrintFatalError("No instructions defined!");
diff --git a/utils/TableGen/RegisterBankEmitter.cpp b/utils/TableGen/RegisterBankEmitter.cpp
index 3f11eff1d371..880d075da427 100644
--- a/utils/TableGen/RegisterBankEmitter.cpp
+++ b/utils/TableGen/RegisterBankEmitter.cpp
@@ -227,7 +227,7 @@ void RegisterBankEmitter::emitBaseClassImplementation(
       OS << "    // " << LowestIdxInWord << "-" << (LowestIdxInWord + 31) << "\n";
       for (const auto &RC : RCs) {
         std::string QualifiedRegClassID =
-            (Twine(TargetName) + "::" + RC->getName() + "RegClassID").str();
+            (Twine(RC->Namespace) + "::" + RC->getName() + "RegClassID").str();
         OS << "    (1u << (" << QualifiedRegClassID << " - "
            << LowestIdxInWord << ")) |\n";
       }
diff --git a/utils/TableGen/SearchableTableEmitter.cpp b/utils/TableGen/SearchableTableEmitter.cpp
index efd4e83eca90..f73c197dee5a 100644
--- a/utils/TableGen/SearchableTableEmitter.cpp
+++ b/utils/TableGen/SearchableTableEmitter.cpp
@@ -230,7 +230,7 @@ void SearchableTableEmitter::emitLookupDeclaration(StringRef Name,
 
 void SearchableTableEmitter::emitMapping(Record *InstanceClass,
                                          raw_ostream &OS) {
-  const std::string &TableName = InstanceClass->getName();
+  StringRef TableName = InstanceClass->getName();
   std::vector<Record *> Items = Records.getAllDerivedDefinitions(TableName);
 
   // Gather all the records we're going to need for this particular mapping.
@@ -265,8 +265,8 @@ void SearchableTableEmitter::emitMapping(Record *InstanceClass,
     ++Idx;
   }
 
-  OS << "#ifdef GET_" << StringRef(TableName).upper() << "_DECL\n";
-  OS << "#undef GET_" << StringRef(TableName).upper() << "_DECL\n";
+  OS << "#ifdef GET_" << TableName.upper() << "_DECL\n";
+  OS << "#undef GET_" << TableName.upper() << "_DECL\n";
 
   // Next emit the enum containing the top-level names for use in C++ code if
   // requested
@@ -281,8 +281,8 @@ void SearchableTableEmitter::emitMapping(Record *InstanceClass,
 
   OS << "#endif\n\n";
 
-  OS << "#ifdef GET_" << StringRef(TableName).upper() << "_IMPL\n";
-  OS << "#undef GET_" << StringRef(TableName).upper() << "_IMPL\n";
+  OS << "#ifdef GET_" << TableName.upper() << "_IMPL\n";
+  OS << "#undef GET_" << TableName.upper() << "_IMPL\n";
 
   // The primary data table contains all the fields defined for this map.
   emitPrimaryTable(TableName, FieldNames, SearchFieldNames, SearchTables, Items,
diff --git a/utils/TableGen/SubtargetEmitter.cpp b/utils/TableGen/SubtargetEmitter.cpp
index 16d5740b79a3..d1d873b66aaa 100644
--- a/utils/TableGen/SubtargetEmitter.cpp
+++ b/utils/TableGen/SubtargetEmitter.cpp
@@ -375,7 +375,7 @@ EmitStageAndOperandCycleData(raw_ostream &OS,
     if (FUs.empty())
       continue;
 
-    const std::string &Name = ProcModel.ItinsDef->getName();
+    StringRef Name = ProcModel.ItinsDef->getName();
     OS << "\n// Functional units for \"" << Name << "\"\n"
        << "namespace " << Name << "FU {\n";
 
@@ -429,7 +429,7 @@ EmitStageAndOperandCycleData(raw_ostream &OS,
     if (!ProcModel.hasItineraries())
       continue;
 
-    const std::string &Name = ProcModel.ItinsDef->getName();
+    StringRef Name = ProcModel.ItinsDef->getName();
 
     ItinList.resize(SchedModels.numInstrSchedClasses());
     assert(ProcModel.ItinDefList.size() == ItinList.size() && "bad Itins");
@@ -546,9 +546,6 @@ EmitItineraries(raw_ostream &OS,
     if (!ItinsDefSet.insert(ItinsDef).second)
       continue;
 
-    // Get processor itinerary name
-    const std::string &Name = ItinsDef->getName();
-
     // Get the itinerary list for the processor.
     assert(ProcItinListsIter != ProcItinLists.end() && "bad iterator");
     std::vector<InstrItinerary> &ItinList = *ProcItinListsIter;
@@ -562,7 +559,7 @@ EmitItineraries(raw_ostream &OS,
     OS << "static const llvm::InstrItinerary ";
 
     // Begin processor itinerary table
-    OS << Name << "[] = {\n";
+    OS << ItinsDef->getName() << "[] = {\n";
 
     // For each itinerary class in CodeGenSchedClass::Index order.
     for (unsigned j = 0, M = ItinList.size(); j < M; ++j) {
diff --git a/utils/TableGen/X86DisassemblerTables.cpp b/utils/TableGen/X86DisassemblerTables.cpp
index c9e36f96736a..c80b96905b30 100644
--- a/utils/TableGen/X86DisassemblerTables.cpp
+++ b/utils/TableGen/X86DisassemblerTables.cpp
@@ -10,7 +10,7 @@
 // This file is part of the X86 Disassembler Emitter.
 // It contains the implementation of the disassembler tables.
 // Documentation for the disassembler emitter in general can be found in
-//  X86DisasemblerEmitter.h.
+//  X86DisassemblerEmitter.h.
 //
 //===----------------------------------------------------------------------===//
 
diff --git a/utils/TableGen/X86DisassemblerTables.h b/utils/TableGen/X86DisassemblerTables.h
index 5a8688be0819..1171c7980f42 100644
--- a/utils/TableGen/X86DisassemblerTables.h
+++ b/utils/TableGen/X86DisassemblerTables.h
@@ -10,7 +10,7 @@
 // This file is part of the X86 Disassembler Emitter.
 // It contains the interface of the disassembler tables.
 // Documentation for the disassembler emitter in general can be found in
-//  X86DisasemblerEmitter.h.
+//  X86DisassemblerEmitter.h.
 //
 //===----------------------------------------------------------------------===//
 
diff --git a/utils/TableGen/X86ModRMFilters.h b/utils/TableGen/X86ModRMFilters.h
index d919c588c644..73d5602fd91c 100644
--- a/utils/TableGen/X86ModRMFilters.h
+++ b/utils/TableGen/X86ModRMFilters.h
@@ -11,7 +11,7 @@
 // It contains ModR/M filters that determine which values of the ModR/M byte
 //  are valid for a partiuclar instruction.
 // Documentation for the disassembler emitter in general can be found in
-//  X86DisasemblerEmitter.h.
+//  X86DisassemblerEmitter.h.
 //
 //===----------------------------------------------------------------------===//
 
diff --git a/utils/TableGen/X86RecognizableInstr.cpp b/utils/TableGen/X86RecognizableInstr.cpp
index 55e75763ad69..202a71ae4dc4 100644
--- a/utils/TableGen/X86RecognizableInstr.cpp
+++ b/utils/TableGen/X86RecognizableInstr.cpp
@@ -10,7 +10,7 @@
 // This file is part of the X86 Disassembler Emitter.
 // It contains the implementation of a single recognizable instruction.
 // Documentation for the disassembler emitter in general can be found in
-//  X86DisasemblerEmitter.h.
+//  X86DisassemblerEmitter.h.
 //
 //===----------------------------------------------------------------------===//
 
@@ -367,7 +367,7 @@ void RecognizableInstr::handleOperand(bool optional, unsigned &operandIndex,
     ++operandIndex;
   }
 
-  const std::string &typeName = (*Operands)[operandIndex].Rec->getName();
+  StringRef typeName = (*Operands)[operandIndex].Rec->getName();
 
   OperandEncoding encoding = encodingFromString(typeName, OpSize);
   // Adjust the encoding type for an operand based on the instruction.
diff --git a/utils/TableGen/X86RecognizableInstr.h b/utils/TableGen/X86RecognizableInstr.h
index 7fe731ec8b1c..ea99935f8790 100644
--- a/utils/TableGen/X86RecognizableInstr.h
+++ b/utils/TableGen/X86RecognizableInstr.h
@@ -10,7 +10,7 @@
 // This file is part of the X86 Disassembler Emitter.
 // It contains the interface of a single recognizable instruction.
 // Documentation for the disassembler emitter in general can be found in
-//  X86DisasemblerEmitter.h.
+//  X86DisassemblerEmitter.h.
 //
 //===----------------------------------------------------------------------===//
 
diff --git a/utils/docker/build_docker_image.sh b/utils/docker/build_docker_image.sh
index 2ec07ab6da4b..33f690ad5c43 100755
--- a/utils/docker/build_docker_image.sh
+++ b/utils/docker/build_docker_image.sh
@@ -16,20 +16,37 @@ BUILDSCRIPT_ARGS=""
 
 function show_usage() {
   usage=$(cat << EOF
-Usage: build_docker_image.sh [options] [-- [buildscript_args]...]
+Usage: build_docker_image.sh [options] [-- [cmake_args]...]
 
 Available options:
+  General:
+    -h|--help               show this help message
+  Docker-specific:
     -s|--source             image source dir (i.e. debian8, nvidia-cuda, etc)
     -d|--docker-repository  docker repository for the image
     -t|--docker-tag         docker tag for the image
-Required options: --source and --docker-repository.
-
-All options after '--' are passed to buildscript (see
-scripts/build_install_llvm.sh).
+  LLVM-specific:
+    -b|--branch         svn branch to checkout, i.e. 'trunk',
+                        'branches/release_40'
+                        (default: 'trunk')
+    -r|--revision       svn revision to checkout
+    -p|--llvm-project   name of an svn project to checkout. Will also add the
+                        project to a list LLVM_ENABLE_PROJECTS, passed to CMake.
+                        For clang, please use 'clang', not 'cfe'.
+                        Project 'llvm' is always included and ignored, if
+                        specified.
+                        Can be specified multiple times.
+    -i|--install-target name of a cmake install target to build and include in
+                        the resulting archive. Can be specified multiple times.
+
+Required options: --source and --docker-repository, at least one
+  --install-target.
+
+All options after '--' are passed to CMake invocation.
 
 For example, running:
 $ build_docker_image.sh -s debian8 -d mydocker/debian8-clang -t latest \ 
-  -- -p clang -i install-clang -i install-clang-headers
+  -p clang -i install-clang -i install-clang-headers
 will produce two docker images:
     mydocker/debian8-clang-build:latest - an intermediate image used to compile
       clang.
@@ -37,12 +54,21 @@ will produce two docker images:
 Please note that this example produces a not very useful installation, since it
 doesn't override CMake defaults, which produces a Debug and non-boostrapped
 version of clang.
-For an example of a somewhat more useful build, see build_clang_image.sh.
+
+To get a 2-stage clang build, you could use this command:
+$ ./build_docker_image.sh -s debian8 -d mydocker/clang-debian8 -t "latest" \ 
+    -p clang -i stage2-install-clang -i stage2-install-clang-headers \ 
+    -- \ 
+    -DLLVM_TARGETS_TO_BUILD=Native -DCMAKE_BUILD_TYPE=Release \ 
+    -DBOOTSTRAP_CMAKE_BUILD_TYPE=Release \ 
+    -DCLANG_ENABLE_BOOTSTRAP=ON \ 
+    -DCLANG_BOOTSTRAP_TARGETS="install-clang;install-clang-headers"
 EOF
 )
   echo "$usage"
 }
 
+SEEN_INSTALL_TARGET=0
 while [[ $# -gt 0 ]]; do
   case "$1" in
     -h|--help)
@@ -64,9 +90,16 @@ while [[ $# -gt 0 ]]; do
       DOCKER_TAG="$1"
       shift
       ;;
+    -i|--install-target|-r|--revision|-b|--branch|-p|--llvm-project)
+      if [ "$1" == "-i" ] || [ "$1" == "--install-target" ]; then
+        SEEN_INSTALL_TARGET=1
+      fi
+      BUILDSCRIPT_ARGS="$BUILDSCRIPT_ARGS $1 $2"
+      shift 2
+      ;;
     --)
       shift
-      BUILDSCRIPT_ARGS="$*"
+      BUILDSCRIPT_ARGS="$BUILDSCRIPT_ARGS -- $*"
       shift $#
       ;;
     *)
@@ -92,6 +125,11 @@ if [ "$DOCKER_REPOSITORY" == "" ]; then
   exit 1
 fi
 
+if [ $SEEN_INSTALL_TARGET -eq 0 ]; then
+  echo "Please provide at least one --install-target"
+  exit 1
+fi
+
 cd $(dirname $0)
 if [ ! -d $IMAGE_SOURCE ]; then
   echo "No sources for '$IMAGE_SOURCE' were found in $PWD"
diff --git a/utils/docker/scripts/build_install_llvm.sh b/utils/docker/scripts/build_install_llvm.sh
index 7e0e90657416..aef4e0cbca2c 100755
--- a/utils/docker/scripts/build_install_llvm.sh
+++ b/utils/docker/scripts/build_install_llvm.sh
@@ -65,6 +65,7 @@ while [[ $# -gt 0 ]]; do
     -r|--revision)
       shift
       LLVM_SVN_REV="$1"
+      shift
       ;;
     -b|--branch)
       shift
@@ -79,7 +80,10 @@ while [[ $# -gt 0 ]]; do
       fi
       if ! contains_project "$PROJ" ; then
         LLVM_PROJECTS="$LLVM_PROJECTS $PROJ"
-        CMAKE_LLVM_ENABLE_PROJECTS="$CMAKE_LLVM_ENABLED_PROJECTS;$PROJ"
+        if [ "$CMAKE_LLVM_ENABLE_PROJECTS" != "" ]; then
+          CMAKE_LLVM_ENABLE_PROJECTS="$CMAKE_LLVM_ENABLE_PROJECTS;"
+        fi
+        CMAKE_LLVM_ENABLE_PROJECTS="$CMAKE_LLVM_ENABLED_PROJECTS$PROJ"
       else
         echo "Project '$PROJ' is already enabled, ignoring extra occurences."
       fi
@@ -135,7 +139,7 @@ for LLVM_PROJECT in $LLVM_PROJECTS; do
     SVN_PROJECT="$LLVM_PROJECT"
   fi
 
-  echo "Checking out http://llvm.org/svn/llvm-project/$SVN_PROJECT to $CLANG_BUILD_DIR/src/$LLVM_PROJECT"
+  echo "Checking out https://llvm.org/svn/llvm-project/$SVN_PROJECT to $CLANG_BUILD_DIR/src/$LLVM_PROJECT"
   # FIXME: --trust-server-cert is required to workaround 'SSL issuer is not
   #        trusted' error. Using https seems preferable to http either way,
   #        albeit this is not secure.
@@ -144,11 +148,11 @@ for LLVM_PROJECT in $LLVM_PROJECTS; do
     "$CLANG_BUILD_DIR/src/$LLVM_PROJECT"
 done
 
-pushd "$CLANG_BUILD_DIR"
+mkdir "$CLANG_BUILD_DIR/build"
+pushd "$CLANG_BUILD_DIR/build"
 
 # Run the build as specified in the build arguments.
 echo "Running build"
-mkdir "$CLANG_BUILD_DIR/build"
 cmake -GNinja \
   -DCMAKE_INSTALL_PREFIX="$CLANG_INSTALL_DIR" \
   -DLLVM_ENABLE_PROJECTS="$CMAKE_LLVM_ENABLE_PROJECTS" \
diff --git a/utils/lit/lit/TestRunner.py b/utils/lit/lit/TestRunner.py
index 37b03cc19f85..8260d3813345 100644
--- a/utils/lit/lit/TestRunner.py
+++ b/utils/lit/lit/TestRunner.py
@@ -5,6 +5,11 @@ import platform
 import tempfile
 import threading
 
+try:
+    from StringIO import StringIO
+except ImportError:
+    from io import StringIO
+
 from lit.ShCommands import GlobItem
 import lit.ShUtil as ShUtil
 import lit.Test as Test
@@ -221,6 +226,155 @@ def updateEnv(env, cmd):
         env.env[key] = val
     cmd.args = cmd.args[arg_idx+1:]
 
+def executeBuiltinEcho(cmd, shenv):
+    """Interpret a redirected echo command"""
+    opened_files = []
+    stdin, stdout, stderr = processRedirects(cmd, subprocess.PIPE, shenv,
+                                             opened_files)
+    if stdin != subprocess.PIPE or stderr != subprocess.PIPE:
+        raise InternalShellError(
+                cmd, "stdin and stderr redirects not supported for echo")
+
+    # Some tests have un-redirected echo commands to help debug test failures.
+    # Buffer our output and return it to the caller.
+    is_redirected = True
+    if stdout == subprocess.PIPE:
+        is_redirected = False
+        stdout = StringIO()
+    elif kIsWindows:
+        # Reopen stdout in binary mode to avoid CRLF translation. The versions
+        # of echo we are replacing on Windows all emit plain LF, and the LLVM
+        # tests now depend on this.
+        stdout = open(stdout.name, stdout.mode + 'b')
+        opened_files.append((None, None, stdout, None))
+
+    # Implement echo flags. We only support -e and -n, and not yet in
+    # combination. We have to ignore unknown flags, because `echo "-D FOO"`
+    # prints the dash.
+    args = cmd.args[1:]
+    interpret_escapes = False
+    write_newline = True
+    while len(args) >= 1 and args[0] in ('-e', '-n'):
+        flag = args[0]
+        args = args[1:]
+        if flag == '-e':
+            interpret_escapes = True
+        elif flag == '-n':
+            write_newline = False
+
+    def maybeUnescape(arg):
+        if not interpret_escapes:
+            return arg
+        # Python string escapes and "echo" escapes are obviously different, but
+        # this should be enough for the LLVM test suite.
+        return arg.decode('string_escape')
+
+    if args:
+        for arg in args[:-1]:
+            stdout.write(maybeUnescape(arg))
+            stdout.write(' ')
+        stdout.write(maybeUnescape(args[-1]))
+    if write_newline:
+        stdout.write('\n')
+
+    for (name, mode, f, path) in opened_files:
+        f.close()
+
+    if not is_redirected:
+        return stdout.getvalue()
+    return ""
+
+def processRedirects(cmd, stdin_source, cmd_shenv, opened_files):
+    """Return the standard fds for cmd after applying redirects
+
+    Returns the three standard file descriptors for the new child process.  Each
+    fd may be an open, writable file object or a sentinel value from the
+    subprocess module.
+    """
+
+    # Apply the redirections, we use (N,) as a sentinel to indicate stdin,
+    # stdout, stderr for N equal to 0, 1, or 2 respectively. Redirects to or
+    # from a file are represented with a list [file, mode, file-object]
+    # where file-object is initially None.
+    redirects = [(0,), (1,), (2,)]
+    for (op, filename) in cmd.redirects:
+        if op == ('>',2):
+            redirects[2] = [filename, 'w', None]
+        elif op == ('>>',2):
+            redirects[2] = [filename, 'a', None]
+        elif op == ('>&',2) and filename in '012':
+            redirects[2] = redirects[int(filename)]
+        elif op == ('>&',) or op == ('&>',):
+            redirects[1] = redirects[2] = [filename, 'w', None]
+        elif op == ('>',):
+            redirects[1] = [filename, 'w', None]
+        elif op == ('>>',):
+            redirects[1] = [filename, 'a', None]
+        elif op == ('<',):
+            redirects[0] = [filename, 'r', None]
+        else:
+            raise InternalShellError(cmd, "Unsupported redirect: %r" % (r,))
+
+    # Open file descriptors in a second pass.
+    std_fds = [None, None, None]
+    for (index, r) in enumerate(redirects):
+        # Handle the sentinel values for defaults up front.
+        if isinstance(r, tuple):
+            if r == (0,):
+                fd = stdin_source
+            elif r == (1,):
+                if index == 0:
+                    raise InternalShellError(cmd, "Unsupported redirect for stdin")
+                elif index == 1:
+                    fd = subprocess.PIPE
+                else:
+                    fd = subprocess.STDOUT
+            elif r == (2,):
+                if index != 2:
+                    raise InternalShellError(cmd, "Unsupported redirect on stdout")
+                fd = subprocess.PIPE
+            else:
+                raise InternalShellError(cmd, "Bad redirect")
+            std_fds[index] = fd
+            continue
+
+        (filename, mode, fd) = r
+
+        # Check if we already have an open fd. This can happen if stdout and
+        # stderr go to the same place.
+        if fd is not None:
+            std_fds[index] = fd
+            continue
+
+        redir_filename = None
+        name = expand_glob(filename, cmd_shenv.cwd)
+        if len(name) != 1:
+           raise InternalShellError(cmd, "Unsupported: glob in "
+                                    "redirect expanded to multiple files")
+        name = name[0]
+        if kAvoidDevNull and name == '/dev/null':
+            fd = tempfile.TemporaryFile(mode=mode)
+        elif kIsWindows and name == '/dev/tty':
+            # Simulate /dev/tty on Windows.
+            # "CON" is a special filename for the console.
+            fd = open("CON", mode)
+        else:
+            # Make sure relative paths are relative to the cwd.
+            redir_filename = os.path.join(cmd_shenv.cwd, name)
+            fd = open(redir_filename, mode)
+        # Workaround a Win32 and/or subprocess bug when appending.
+        #
+        # FIXME: Actually, this is probably an instance of PR6753.
+        if mode == 'a':
+            fd.seek(0, 2)
+        # Mutate the underlying redirect list so that we can redirect stdout
+        # and stderr to the same place without opening the file twice.
+        r[2] = fd
+        opened_files.append((filename, mode, fd) + (redir_filename,))
+        std_fds[index] = fd
+
+    return std_fds
+
 def _executeShCmd(cmd, shenv, results, timeoutHelper):
     if timeoutHelper.timeoutReached():
         # Prevent further recursion if the timeout has been hit
@@ -269,6 +423,17 @@ def _executeShCmd(cmd, shenv, results, timeoutHelper):
         # following Popen calls will fail instead.
         return 0
 
+    # Handle "echo" as a builtin if it is not part of a pipeline. This greatly
+    # speeds up tests that construct input files by repeatedly echo-appending to
+    # a file.
+    # FIXME: Standardize on the builtin echo implementation. We can use a
+    # temporary file to sidestep blocking pipe write issues.
+    if cmd.commands[0].args[0] == 'echo' and len(cmd.commands) == 1:
+        output = executeBuiltinEcho(cmd.commands[0], shenv)
+        results.append(ShellCommandResult(cmd.commands[0], output, "", 0,
+                                          False))
+        return 0
+
     if cmd.commands[0].args[0] == 'export':
         if len(cmd.commands) != 1:
             raise ValueError("'export' cannot be part of a pipeline")
@@ -278,7 +443,7 @@ def _executeShCmd(cmd, shenv, results, timeoutHelper):
         return 0
 
     procs = []
-    input = subprocess.PIPE
+    default_stdin = subprocess.PIPE
     stderrTempFiles = []
     opened_files = []
     named_temp_files = []
@@ -295,72 +460,8 @@ def _executeShCmd(cmd, shenv, results, timeoutHelper):
             cmd_shenv = ShellEnvironment(shenv.cwd, shenv.env)
             updateEnv(cmd_shenv, j)
 
-        # Apply the redirections, we use (N,) as a sentinel to indicate stdin,
-        # stdout, stderr for N equal to 0, 1, or 2 respectively. Redirects to or
-        # from a file are represented with a list [file, mode, file-object]
-        # where file-object is initially None.
-        redirects = [(0,), (1,), (2,)]
-        for r in j.redirects:
-            if r[0] == ('>',2):
-                redirects[2] = [r[1], 'w', None]
-            elif r[0] == ('>>',2):
-                redirects[2] = [r[1], 'a', None]
-            elif r[0] == ('>&',2) and r[1] in '012':
-                redirects[2] = redirects[int(r[1])]
-            elif r[0] == ('>&',) or r[0] == ('&>',):
-                redirects[1] = redirects[2] = [r[1], 'w', None]
-            elif r[0] == ('>',):
-                redirects[1] = [r[1], 'w', None]
-            elif r[0] == ('>>',):
-                redirects[1] = [r[1], 'a', None]
-            elif r[0] == ('<',):
-                redirects[0] = [r[1], 'r', None]
-            else:
-                raise InternalShellError(j,"Unsupported redirect: %r" % (r,))
-
-        # Map from the final redirections to something subprocess can handle.
-        final_redirects = []
-        for index,r in enumerate(redirects):
-            if r == (0,):
-                result = input
-            elif r == (1,):
-                if index == 0:
-                    raise InternalShellError(j,"Unsupported redirect for stdin")
-                elif index == 1:
-                    result = subprocess.PIPE
-                else:
-                    result = subprocess.STDOUT
-            elif r == (2,):
-                if index != 2:
-                    raise InternalShellError(j,"Unsupported redirect on stdout")
-                result = subprocess.PIPE
-            else:
-                if r[2] is None:
-                    redir_filename = None
-                    name = expand_glob(r[0], cmd_shenv.cwd)
-                    if len(name) != 1:
-                       raise InternalShellError(j,"Unsupported: glob in redirect expanded to multiple files")
-                    name = name[0]
-                    if kAvoidDevNull and name == '/dev/null':
-                        r[2] = tempfile.TemporaryFile(mode=r[1])
-                    elif kIsWindows and name == '/dev/tty':
-                        # Simulate /dev/tty on Windows.
-                        # "CON" is a special filename for the console.
-                        r[2] = open("CON", r[1])
-                    else:
-                        # Make sure relative paths are relative to the cwd.
-                        redir_filename = os.path.join(cmd_shenv.cwd, name)
-                        r[2] = open(redir_filename, r[1])
-                    # Workaround a Win32 and/or subprocess bug when appending.
-                    #
-                    # FIXME: Actually, this is probably an instance of PR6753.
-                    if r[1] == 'a':
-                        r[2].seek(0, 2)
-                    opened_files.append(tuple(r) + (redir_filename,))
-                result = r[2]
-            final_redirects.append(result)
-
-        stdin, stdout, stderr = final_redirects
+        stdin, stdout, stderr = processRedirects(j, default_stdin, cmd_shenv,
+                                                 opened_files)
 
         # If stderr wants to come from stdout, but stdout isn't a pipe, then put
         # stderr on a pipe and treat it as stdout.
@@ -428,11 +529,11 @@ def _executeShCmd(cmd, shenv, results, timeoutHelper):
 
         # Update the current stdin source.
         if stdout == subprocess.PIPE:
-            input = procs[-1].stdout
+            default_stdin = procs[-1].stdout
         elif stderrIsStdout:
-            input = procs[-1].stderr
+            default_stdin = procs[-1].stderr
         else:
-            input = subprocess.PIPE
+            default_stdin = subprocess.PIPE
 
     # Explicitly close any redirected files. We need to do this now because we
     # need to release any handles we may have on the temporary files (important
diff --git a/utils/lit/lit/formats/googletest.py b/utils/lit/lit/formats/googletest.py
index b683f7c7db8e..9c55e71d2330 100644
--- a/utils/lit/lit/formats/googletest.py
+++ b/utils/lit/lit/formats/googletest.py
@@ -78,7 +78,10 @@ class GoogleTest(TestFormat):
                             litConfig, localConfig):
         source_path = testSuite.getSourcePath(path_in_suite)
         for subdir in self.test_sub_dirs:
-            for fn in lit.util.listdir_files(os.path.join(source_path, subdir),
+            dir_path = os.path.join(source_path, subdir)
+            if not os.path.isdir(dir_path):
+                continue
+            for fn in lit.util.listdir_files(dir_path,
                                              suffixes={self.test_suffix}):
                 # Discover the tests in this executable.
                 execpath = os.path.join(source_path, subdir, fn)
diff --git a/utils/lit/lit/main.py b/utils/lit/lit/main.py
index a7f407fc210c..530f962d336d 100755
--- a/utils/lit/lit/main.py
+++ b/utils/lit/lit/main.py
@@ -262,7 +262,8 @@ def main_with_tmp(builtinParameters):
     selection_group.add_argument("--filter", metavar="REGEX",
                      help=("Only run tests with paths matching the given "
                            "regular expression"),
-                     action="store", default=None)
+                     action="store",
+                     default=os.environ.get("LIT_FILTER"))
     selection_group.add_argument("--num-shards", dest="numShards", metavar="M",
                      help="Split testsuite into M pieces and only run one",
                      action="store", type=int,
diff --git a/utils/lit/tests/selecting.py b/utils/lit/tests/selecting.py
index 72d6fbabdc93..19ba240f9b0f 100644
--- a/utils/lit/tests/selecting.py
+++ b/utils/lit/tests/selecting.py
@@ -7,6 +7,11 @@
 # RUN: %{lit} --filter 'o[a-z]e' %{inputs}/discovery | FileCheck --check-prefix=CHECK-FILTER %s
 # CHECK-FILTER: Testing: 2 of 5 tests
 
+# Check that regex-filtering based on environment variables work.
+#
+# RUN: LIT_FILTER='o[a-z]e' %{lit} %{inputs}/discovery | FileCheck --check-prefix=CHECK-FILTER-ENV %s
+# CHECK-FILTER-ENV: Testing: 2 of 5 tests
+
 
 # Check that maximum counts work
 #
diff --git a/utils/opt-viewer/opt-diff.py b/utils/opt-viewer/opt-diff.py
deleted file mode 100755
index 9e921f8488d3..000000000000
--- a/utils/opt-viewer/opt-diff.py
+++ /dev/null
@@ -1,71 +0,0 @@
-#!/usr/bin/env python2.7
-
-from __future__ import print_function
-
-desc = '''Generate the difference of two YAML files into a new YAML file (works on
-pair of directories too).  A new attribute 'Added' is set to True or False
-depending whether the entry is added or removed from the first input to the
-next.
-
-The tools requires PyYAML.'''
-
-import yaml
-# Try to use the C parser.
-try:
-    from yaml import CLoader as Loader
-except ImportError:
-    from yaml import Loader
-
-import optrecord
-import argparse
-from collections import defaultdict
-from multiprocessing import cpu_count, Pool
-import os, os.path
-import fnmatch
-
-def find_files(dir_or_file):
-    if os.path.isfile(dir_or_file):
-        return [dir_or_file]
-
-    all = []
-    for dir, subdirs, files in os.walk(dir_or_file):
-        for file in files:
-            if fnmatch.fnmatch(file, "*.opt.yaml"):
-                all.append( os.path.join(dir, file))
-    return all
-
-if __name__ == '__main__':
-    parser = argparse.ArgumentParser(description=desc)
-    parser.add_argument('yaml_dir_or_file_1')
-    parser.add_argument('yaml_dir_or_file_2')
-    parser.add_argument(
-        '--jobs',
-        '-j',
-        default=cpu_count(),
-        type=int,
-        help='Max job count (defaults to %(default)s, the current CPU count)')
-    parser.add_argument(
-        '--no-progress-indicator',
-        '-n',
-        action='store_true',
-        default=False,
-        help='Do not display any indicator of how many YAML files were read.')
-    parser.add_argument('--output', '-o', default='diff.opt.yaml')
-    args = parser.parse_args()
-
-    files1 = find_files(args.yaml_dir_or_file_1)
-    files2 = find_files(args.yaml_dir_or_file_2)
-
-    print_progress = not args.no_progress_indicator
-    all_remarks1, _, _ = optrecord.gather_results(files1, args.jobs, print_progress)
-    all_remarks2, _, _ = optrecord.gather_results(files2, args.jobs, print_progress)
-
-    added = set(all_remarks2.values()) - set(all_remarks1.values())
-    removed = set(all_remarks1.values()) - set(all_remarks2.values())
-
-    for r in added:
-        r.Added = True
-    for r in removed:
-        r.Added = False
-    with open(args.output, 'w') as stream:
-        yaml.dump_all(added | removed, stream)
diff --git a/utils/opt-viewer/opt-stats.py b/utils/opt-viewer/opt-stats.py
deleted file mode 100755
index a7e598fdfd02..000000000000
--- a/utils/opt-viewer/opt-stats.py
+++ /dev/null
@@ -1,56 +0,0 @@
-#!/usr/bin/env python2.7
-
-from __future__ import print_function
-
-desc = '''Generate statistics about optimization records from the YAML files
-generated with -fsave-optimization-record and -fdiagnostics-show-hotness.
-
-The tools requires PyYAML and Pygments Python packages.'''
-
-import optrecord
-import argparse
-import operator
-from collections import defaultdict
-from multiprocessing import cpu_count, Pool
-
-if __name__ == '__main__':
-    parser = argparse.ArgumentParser(description=desc)
-    parser.add_argument('yaml_files', nargs='+')
-    parser.add_argument(
-        '--jobs',
-        '-j',
-        default=cpu_count(),
-        type=int,
-        help='Max job count (defaults to %(default)s, the current CPU count)')
-    parser.add_argument(
-        '--no-progress-indicator',
-        '-n',
-        action='store_true',
-        default=False,
-        help='Do not display any indicator of how many YAML files were read.')
-    args = parser.parse_args()
-
-    print_progress = not args.no_progress_indicator
-    all_remarks, file_remarks, _ = optrecord.gather_results(
-        args.yaml_files, args.jobs, print_progress)
-    if print_progress:
-        print('\n')
-
-    bypass = defaultdict(int)
-    byname = defaultdict(int)
-    for r in optrecord.itervalues(all_remarks):
-        bypass[r.Pass] += 1
-        byname[r.Pass + "/" + r.Name] += 1
-
-    total = len(all_remarks)
-    print("{:24s} {:10d}\n".format("Total number of remarks", total))
-
-    print("Top 10 remarks by pass:")
-    for (passname, count) in sorted(bypass.items(), key=operator.itemgetter(1),
-                                    reverse=True)[:10]:
-        print("  {:30s} {:2.0f}%". format(passname, count * 100. / total))
-
-    print("\nTop 10 remarks:")
-    for (name, count) in sorted(byname.items(), key=operator.itemgetter(1),
-                                reverse=True)[:10]:
-        print("  {:30s} {:2.0f}%". format(name, count * 100. / total))
diff --git a/utils/opt-viewer/opt-viewer.py b/utils/opt-viewer/opt-viewer.py
deleted file mode 100755
index 5e5daf7feb0d..000000000000
--- a/utils/opt-viewer/opt-viewer.py
+++ /dev/null
@@ -1,259 +0,0 @@
-#!/usr/bin/env python2.7
-
-from __future__ import print_function
-
-import argparse
-import cgi
-import errno
-import functools
-from multiprocessing import cpu_count
-import os.path
-import re
-import shutil
-
-from pygments import highlight
-from pygments.lexers.c_cpp import CppLexer
-from pygments.formatters import HtmlFormatter
-
-import optpmap
-import optrecord
-
-
-desc = '''Generate HTML output to visualize optimization records from the YAML files
-generated with -fsave-optimization-record and -fdiagnostics-show-hotness.
-
-The tools requires PyYAML and Pygments Python packages.'''
-
-
-# This allows passing the global context to the child processes.
-class Context:
-    def __init__(self, caller_loc = dict()):
-       # Map function names to their source location for function where inlining happened
-       self.caller_loc = caller_loc
-
-context = Context()
-
-class SourceFileRenderer:
-    def __init__(self, source_dir, output_dir, filename):
-        existing_filename = None
-        if os.path.exists(filename):
-            existing_filename = filename
-        else:
-            fn = os.path.join(source_dir, filename)
-            if os.path.exists(fn):
-                existing_filename = fn
-
-        self.stream = open(os.path.join(output_dir, optrecord.html_file_name(filename)), 'w')
-        if existing_filename:
-            self.source_stream = open(existing_filename)
-        else:
-            self.source_stream = None
-            print('''
-<html>
-<h1>Unable to locate file {}</h1>
-</html>
-            '''.format(filename), file=self.stream)
-
-        self.html_formatter = HtmlFormatter(encoding='utf-8')
-        self.cpp_lexer = CppLexer(stripnl=False)
-
-    def render_source_lines(self, stream, line_remarks):
-        file_text = stream.read()
-        html_highlighted = highlight(file_text, self.cpp_lexer, self.html_formatter)
-
-        # Take off the header and footer, these must be
-        #   reapplied line-wise, within the page structure
-        html_highlighted = html_highlighted.replace('<div class="highlight"><pre>', '')
-        html_highlighted = html_highlighted.replace('</pre></div>', '')
-
-        for (linenum, html_line) in enumerate(html_highlighted.split('\n'), start=1):
-            print('''
-<tr>
-<td><a name=\"L{linenum}\">{linenum}</a></td>
-<td></td>
-<td></td>
-<td><div class="highlight"><pre>{html_line}</pre></div></td>
-</tr>'''.format(**locals()), file=self.stream)
-
-            for remark in line_remarks.get(linenum, []):
-                self.render_inline_remarks(remark, html_line)
-
-    def render_inline_remarks(self, r, line):
-        inlining_context = r.DemangledFunctionName
-        dl = context.caller_loc.get(r.Function)
-        if dl:
-            link = optrecord.make_link(dl['File'], dl['Line'] - 2)
-            inlining_context = "<a href={link}>{r.DemangledFunctionName}</a>".format(**locals())
-
-        # Column is the number of characters *including* tabs, keep those and
-        # replace everything else with spaces.
-        indent = line[:max(r.Column, 1) - 1]
-        indent = re.sub('\S', ' ', indent)
-
-        print('''
-<tr>
-<td></td>
-<td>{r.RelativeHotness}</td>
-<td class=\"column-entry-{r.color}\">{r.PassWithDiffPrefix}</td>
-<td><pre style="display:inline">{indent}</pre><span class=\"column-entry-yellow\"> {r.message}&nbsp;</span></td>
-<td class=\"column-entry-yellow\">{inlining_context}</td>
-</tr>'''.format(**locals()), file=self.stream)
-
-    def render(self, line_remarks):
-        if not self.source_stream:
-            return
-
-        print('''
-<html>
-<head>
-<link rel='stylesheet' type='text/css' href='style.css'>
-</head>
-<body>
-<div class="centered">
-<table>
-<tr>
-<td>Line</td>
-<td>Hotness</td>
-<td>Optimization</td>
-<td>Source</td>
-<td>Inline Context</td>
-</tr>''', file=self.stream)
-        self.render_source_lines(self.source_stream, line_remarks)
-
-        print('''
-</table>
-</body>
-</html>''', file=self.stream)
-
-
-class IndexRenderer:
-    def __init__(self, output_dir):
-        self.stream = open(os.path.join(output_dir, 'index.html'), 'w')
-
-    def render_entry(self, r, odd):
-        escaped_name = cgi.escape(r.DemangledFunctionName)
-        print('''
-<tr>
-<td class=\"column-entry-{odd}\"><a href={r.Link}>{r.DebugLocString}</a></td>
-<td class=\"column-entry-{odd}\">{r.RelativeHotness}</td>
-<td class=\"column-entry-{odd}\">{escaped_name}</td>
-<td class=\"column-entry-{r.color}\">{r.PassWithDiffPrefix}</td>
-</tr>'''.format(**locals()), file=self.stream)
-
-    def render(self, all_remarks):
-        print('''
-<html>
-<head>
-<link rel='stylesheet' type='text/css' href='style.css'>
-</head>
-<body>
-<div class="centered">
-<table>
-<tr>
-<td>Source Location</td>
-<td>Hotness</td>
-<td>Function</td>
-<td>Pass</td>
-</tr>''', file=self.stream)
-        for i, remark in enumerate(all_remarks):
-            self.render_entry(remark, i % 2)
-        print('''
-</table>
-</body>
-</html>''', file=self.stream)
-
-
-def _render_file(source_dir, output_dir, ctx, entry):
-    global context
-    context = ctx
-    filename, remarks = entry
-    SourceFileRenderer(source_dir, output_dir, filename).render(remarks)
-
-
-def map_remarks(all_remarks):
-    # Set up a map between function names and their source location for
-    # function where inlining happened
-    for remark in optrecord.itervalues(all_remarks):
-        if isinstance(remark, optrecord.Passed) and remark.Pass == "inline" and remark.Name == "Inlined":
-            for arg in remark.Args:
-                caller = arg.get('Caller')
-                if caller:
-                    context.caller_loc[caller] = arg['DebugLoc']
-
-
-def generate_report(all_remarks,
-                    file_remarks,
-                    source_dir,
-                    output_dir,
-                    should_display_hotness,
-                    num_jobs,
-                    should_print_progress):
-    try:
-        os.makedirs(output_dir)
-    except OSError as e:
-        if e.errno == errno.EEXIST and os.path.isdir(output_dir):
-            pass
-        else:
-            raise
-
-    _render_file_bound = functools.partial(_render_file, source_dir, output_dir, context)
-    if should_print_progress:
-        print('Rendering HTML files...')
-    optpmap.pmap(_render_file_bound,
-                 file_remarks.items(),
-                 num_jobs,
-                 should_print_progress)
-
-    if should_display_hotness:
-        sorted_remarks = sorted(optrecord.itervalues(all_remarks), key=lambda r: (r.Hotness, r.File, r.Line, r.Column, r.PassWithDiffPrefix, r.yaml_tag, r.Function), reverse=True)
-    else:
-        sorted_remarks = sorted(optrecord.itervalues(all_remarks), key=lambda r: (r.File, r.Line, r.Column, r.PassWithDiffPrefix, r.yaml_tag, r.Function))
-    IndexRenderer(args.output_dir).render(sorted_remarks)
-
-    shutil.copy(os.path.join(os.path.dirname(os.path.realpath(__file__)),
-            "style.css"), output_dir)
-
-
-if __name__ == '__main__':
-    parser = argparse.ArgumentParser(description=desc)
-    parser.add_argument('yaml_files', nargs='+')
-    parser.add_argument(
-        '--output-dir',
-        '-o',
-        default='html',
-        help='Path to a directory where generated HTML files will be output. '
-             'If the directory does not already exist, it will be created. '
-             '"%(default)s" by default.')
-    parser.add_argument(
-        '--jobs',
-        '-j',
-        default=cpu_count(),
-        type=int,
-        help='Max job count (defaults to %(default)s, the current CPU count)')
-    parser.add_argument(
-        '-source-dir',
-        '-s',
-        default='',
-        help='set source directory')
-    parser.add_argument(
-        '--no-progress-indicator',
-        '-n',
-        action='store_true',
-        default=False,
-        help='Do not display any indicator of how many YAML files were read '
-             'or rendered into HTML.')
-    args = parser.parse_args()
-
-    print_progress = not args.no_progress_indicator
-    all_remarks, file_remarks, should_display_hotness = \
-        optrecord.gather_results(args.yaml_files, args.jobs, print_progress)
-
-    map_remarks(all_remarks)
-
-    generate_report(all_remarks,
-                    file_remarks,
-                    args.source_dir,
-                    args.output_dir,
-                    should_display_hotness,
-                    args.jobs,
-                    print_progress)
diff --git a/utils/opt-viewer/optpmap.py b/utils/opt-viewer/optpmap.py
deleted file mode 100644
index 01e848e03976..000000000000
--- a/utils/opt-viewer/optpmap.py
+++ /dev/null
@@ -1,53 +0,0 @@
-import sys
-import multiprocessing
-
-
-_current = None
-_total = None
-
-
-def _init(current, total):
-    global _current
-    global _total
-    _current = current
-    _total = total
-
-
-def _wrapped_func(func_and_args):
-    func, argument, should_print_progress = func_and_args
-
-    if should_print_progress:
-        with _current.get_lock():
-            _current.value += 1
-        sys.stdout.write('\r\t{} of {}'.format(_current.value, _total.value))
-
-    return func(argument)
-
-
-def pmap(func, iterable, processes, should_print_progress, *args, **kwargs):
-    """
-    A parallel map function that reports on its progress.
-
-    Applies `func` to every item of `iterable` and return a list of the
-    results. If `processes` is greater than one, a process pool is used to run
-    the functions in parallel. `should_print_progress` is a boolean value that
-    indicates whether a string 'N of M' should be printed to indicate how many
-    of the functions have finished being run.
-    """
-    global _current
-    global _total
-    _current = multiprocessing.Value('i', 0)
-    _total = multiprocessing.Value('i', len(iterable))
-
-    func_and_args = [(func, arg, should_print_progress,) for arg in iterable]
-    if processes <= 1:
-        result = map(_wrapped_func, func_and_args, *args, **kwargs)
-    else:
-        pool = multiprocessing.Pool(initializer=_init,
-                                    initargs=(_current, _total,),
-                                    processes=processes)
-        result = pool.map(_wrapped_func, func_and_args, *args, **kwargs)
-
-    if should_print_progress:
-        sys.stdout.write('\r')
-    return result
diff --git a/utils/opt-viewer/optrecord.py b/utils/opt-viewer/optrecord.py
deleted file mode 100644
index 61ed9626cffa..000000000000
--- a/utils/opt-viewer/optrecord.py
+++ /dev/null
@@ -1,235 +0,0 @@
-#!/usr/bin/env python2.7
-
-from __future__ import print_function
-
-import yaml
-# Try to use the C parser.
-try:
-    from yaml import CLoader as Loader
-except ImportError:
-    print("For faster parsing, you may want to install libYAML for PyYAML")
-    from yaml import Loader
-
-import cgi
-from collections import defaultdict
-import functools
-from multiprocessing import Lock
-import subprocess
-
-import optpmap
-
-
-p = subprocess.Popen(['c++filt', '-n'], stdin=subprocess.PIPE, stdout=subprocess.PIPE)
-p_lock = Lock()
-
-
-try:
-    dict.iteritems
-except AttributeError:
-    # Python 3
-    def itervalues(d):
-        return iter(d.values())
-    def iteritems(d):
-        return iter(d.items())
-else:
-    # Python 2
-    def itervalues(d):
-        return d.itervalues()
-    def iteritems(d):
-        return d.iteritems()
-
-
-def demangle(name):
-    with p_lock:
-        p.stdin.write((name + '\n').encode('utf-8'))
-        p.stdin.flush()
-        return p.stdout.readline().rstrip().decode('utf-8')
-
-
-def html_file_name(filename):
-    return filename.replace('/', '_') + ".html"
-
-
-def make_link(File, Line):
-    return "\"{}#L{}\"".format(html_file_name(File), Line)
-
-
-class Remark(yaml.YAMLObject):
-    # Work-around for http://pyyaml.org/ticket/154.
-    yaml_loader = Loader
-
-    def initmissing(self):
-        if not hasattr(self, 'Hotness'):
-            self.Hotness = 0
-        if not hasattr(self, 'Args'):
-            self.Args = []
-
-    @property
-    def File(self):
-        return self.DebugLoc['File']
-
-    @property
-    def Line(self):
-        return int(self.DebugLoc['Line'])
-
-    @property
-    def Column(self):
-        return self.DebugLoc['Column']
-
-    @property
-    def DebugLocString(self):
-        return "{}:{}:{}".format(self.File, self.Line, self.Column)
-
-    @property
-    def DemangledFunctionName(self):
-        return demangle(self.Function)
-
-    @property
-    def Link(self):
-        return make_link(self.File, self.Line)
-
-    def getArgString(self, mapping):
-        mapping = mapping.copy()
-        dl = mapping.get('DebugLoc')
-        if dl:
-            del mapping['DebugLoc']
-
-        assert(len(mapping) == 1)
-        (key, value) = mapping.items()[0]
-
-        if key == 'Caller' or key == 'Callee':
-            value = cgi.escape(demangle(value))
-
-        if dl and key != 'Caller':
-            return "<a href={}>{}</a>".format(
-                make_link(dl['File'], dl['Line']), value)
-        else:
-            return value
-
-    def getDiffPrefix(self):
-        if hasattr(self, 'Added'):
-            if self.Added:
-                return '+'
-            else:
-                return '-'
-        return ''
-
-    @property
-    def PassWithDiffPrefix(self):
-        return self.getDiffPrefix() + self.Pass
-
-    @property
-    def message(self):
-        # Args is a list of mappings (dictionaries)
-        values = [self.getArgString(mapping) for mapping in self.Args]
-        return "".join(values)
-
-    @property
-    def RelativeHotness(self):
-        if self.max_hotness:
-            return "{}%".format(int(round(self.Hotness * 100 / self.max_hotness)))
-        else:
-            return ''
-
-    @property
-    def key(self):
-        k = (self.__class__, self.PassWithDiffPrefix, self.Name, self.File, self.Line, self.Column, self.Function)
-        for arg in self.Args:
-            for (key, value) in iteritems(arg):
-                if type(value) is dict:
-                    value = tuple(value.items())
-                k += (key, value)
-        return k
-
-    def __hash__(self):
-        return hash(self.key)
-
-    def __eq__(self, other):
-        return self.key == other.key
-
-    def __repr__(self):
-        return str(self.key)
-
-
-class Analysis(Remark):
-    yaml_tag = '!Analysis'
-
-    @property
-    def color(self):
-        return "white"
-
-
-class AnalysisFPCommute(Analysis):
-    yaml_tag = '!AnalysisFPCommute'
-
-
-class AnalysisAliasing(Analysis):
-    yaml_tag = '!AnalysisAliasing'
-
-
-class Passed(Remark):
-    yaml_tag = '!Passed'
-
-    @property
-    def color(self):
-        return "green"
-
-
-class Missed(Remark):
-    yaml_tag = '!Missed'
-
-    @property
-    def color(self):
-        return "red"
-
-
-def get_remarks(input_file):
-    max_hotness = 0
-    all_remarks = dict()
-    file_remarks = defaultdict(functools.partial(defaultdict, list))
-
-    with open(input_file) as f:
-        docs = yaml.load_all(f, Loader=Loader)
-        for remark in docs:
-            remark.initmissing()
-            # Avoid remarks withoug debug location or if they are duplicated
-            if not hasattr(remark, 'DebugLoc') or remark.key in all_remarks:
-                continue
-            all_remarks[remark.key] = remark
-
-            file_remarks[remark.File][remark.Line].append(remark)
-
-            # If we're reading a back a diff yaml file, max_hotness is already
-            # captured which may actually be less than the max hotness found
-            # in the file.
-            if hasattr(remark, 'max_hotness'):
-                max_hotness = remark.max_hotness
-            max_hotness = max(max_hotness, remark.Hotness)
-
-    return max_hotness, all_remarks, file_remarks
-
-
-def gather_results(filenames, num_jobs, should_print_progress):
-    if should_print_progress:
-        print('Reading YAML files...')
-    remarks = optpmap.pmap(
-        get_remarks, filenames, num_jobs, should_print_progress)
-    max_hotness = max(entry[0] for entry in remarks)
-
-    def merge_file_remarks(file_remarks_job, all_remarks, merged):
-        for filename, d in iteritems(file_remarks_job):
-            for line, remarks in iteritems(d):
-                for remark in remarks:
-                    # Bring max_hotness into the remarks so that
-                    # RelativeHotness does not depend on an external global.
-                    remark.max_hotness = max_hotness
-                    if remark.key not in all_remarks:
-                        merged[filename][line].append(remark)
-
-    all_remarks = dict()
-    file_remarks = defaultdict(functools.partial(defaultdict, list))
-    for _, all_remarks_job, file_remarks_job in remarks:
-        merge_file_remarks(file_remarks_job, all_remarks, file_remarks)
-        all_remarks.update(all_remarks_job)
-
-    return all_remarks, file_remarks, max_hotness != 0
diff --git a/utils/opt-viewer/style.css b/utils/opt-viewer/style.css
deleted file mode 100644
index 595c3e46847d..000000000000
--- a/utils/opt-viewer/style.css
+++ /dev/null
@@ -1,198 +0,0 @@
-.red {
-  background-color: #ffd0d0;
-}
-.cyan {
-  background-color: cyan;
-}
-body {
-  font-family: -apple-system, sans-serif;
-}
-pre {
-  margin-top: 0px !important;
-  margin-bottom: 0px !important;
-}
-.source-name-title {
-  padding: 5px 10px;
-  border-bottom: 1px solid #dbdbdb;
-  background-color: #eee;
-  line-height: 35px;
-}
-.centered {
-  display: table;
-  margin-left: left;
-  margin-right: auto;
-  border: 1px solid #dbdbdb;
-  border-radius: 3px;
-}
-.expansion-view {
-  background-color: rgba(0, 0, 0, 0);
-  margin-left: 0px;
-  margin-top: 5px;
-  margin-right: 5px;
-  margin-bottom: 5px;
-  border: 1px solid #dbdbdb;
-  border-radius: 3px;
-}
-table {
-  border-collapse: collapse;
-}
-.light-row {
-  background: #ffffff;
-  border: 1px solid #dbdbdb;
-}
-.column-entry {
-  text-align: right;
-}
-.column-entry-left {
-  text-align: left;
-}
-.column-entry-white {
-  text-align: right;
-  background-color: #ffffff;
-}
-.column-entry-red {
-  text-align: right;
-  background-color: #ffd0d0;
-}
-.column-entry-green {
-  text-align: right;
-  background-color: #d0ffd0;
-}
-.column-entry-yellow {
-  text-align: left;
-  background-color: #ffe1a6;
-}
-.column-entry-0 {
-  background-color: #ffffff;
-}
-.column-entry-1 {
-  background-color: #eeeeee;
-}
-.line-number {
-  text-align: right;
-  color: #aaa;
-}
-.covered-line {
-  text-align: right;
-  color: #0080ff;
-}
-.uncovered-line {
-  text-align: right;
-  color: #ff3300;
-}
-.tooltip {
-  position: relative;
-  display: inline;
-  background-color: #b3e6ff;
-  text-decoration: none;
-}
-.tooltip span.tooltip-content {
-  position: absolute;
-  width: 100px;
-  margin-left: -50px;
-  color: #FFFFFF;
-  background: #000000;
-  height: 30px;
-  line-height: 30px;
-  text-align: center;
-  visibility: hidden;
-  border-radius: 6px;
-}
-.tooltip span.tooltip-content:after {
-  content: '';
-  position: absolute;
-  top: 100%;
-  left: 50%;
-  margin-left: -8px;
-  width: 0; height: 0;
-  border-top: 8px solid #000000;
-  border-right: 8px solid transparent;
-  border-left: 8px solid transparent;
-}
-:hover.tooltip span.tooltip-content {
-  visibility: visible;
-  opacity: 0.8;
-  bottom: 30px;
-  left: 50%;
-  z-index: 999;
-}
-th, td {
-  vertical-align: top;
-  padding: 2px 5px;
-  border-collapse: collapse;
-  border-right: solid 1px #eee;
-  border-left: solid 1px #eee;
-}
-td:first-child {
-  border-left: none;
-}
-td:last-child {
-  border-right: none;
-}
-
-/* Generated with pygmentize -S colorful -f html >> style.css */
-
-.hll { background-color: #ffffcc }
-.c { color: #888888 } /* Comment */
-.err { color: #FF0000; background-color: #FFAAAA } /* Error */
-.k { color: #008800; font-weight: bold } /* Keyword */
-.o { color: #333333 } /* Operator */
-.ch { color: #888888 } /* Comment.Hashbang */
-.cm { color: #888888 } /* Comment.Multiline */
-.cp { color: #557799 } /* Comment.Preproc */
-.cpf { color: #888888 } /* Comment.PreprocFile */
-.c1 { color: #888888 } /* Comment.Single */
-.cs { color: #cc0000; font-weight: bold } /* Comment.Special */
-.gd { color: #A00000 } /* Generic.Deleted */
-.ge { font-style: italic } /* Generic.Emph */
-.gr { color: #FF0000 } /* Generic.Error */
-.gh { color: #000080; font-weight: bold } /* Generic.Heading */
-.gi { color: #00A000 } /* Generic.Inserted */
-.go { color: #888888 } /* Generic.Output */
-.gp { color: #c65d09; font-weight: bold } /* Generic.Prompt */
-.gs { font-weight: bold } /* Generic.Strong */
-.gu { color: #800080; font-weight: bold } /* Generic.Subheading */
-.gt { color: #0044DD } /* Generic.Traceback */
-.kc { color: #008800; font-weight: bold } /* Keyword.Constant */
-.kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
-.kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
-.kp { color: #003388; font-weight: bold } /* Keyword.Pseudo */
-.kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
-.kt { color: #333399; font-weight: bold } /* Keyword.Type */
-.m { color: #6600EE; font-weight: bold } /* Literal.Number */
-.s { background-color: #fff0f0 } /* Literal.String */
-.na { color: #0000CC } /* Name.Attribute */
-.nb { color: #007020 } /* Name.Builtin */
-.nc { color: #BB0066; font-weight: bold } /* Name.Class */
-.no { color: #003366; font-weight: bold } /* Name.Constant */
-.nd { color: #555555; font-weight: bold } /* Name.Decorator */
-.ni { color: #880000; font-weight: bold } /* Name.Entity */
-.ne { color: #FF0000; font-weight: bold } /* Name.Exception */
-.nf { color: #0066BB; font-weight: bold } /* Name.Function */
-.nl { color: #997700; font-weight: bold } /* Name.Label */
-.nn { color: #0e84b5; font-weight: bold } /* Name.Namespace */
-.nt { color: #007700 } /* Name.Tag */
-.nv { color: #996633 } /* Name.Variable */
-.ow { color: #000000; font-weight: bold } /* Operator.Word */
-.w { color: #bbbbbb } /* Text.Whitespace */
-.mb { color: #6600EE; font-weight: bold } /* Literal.Number.Bin */
-.mf { color: #6600EE; font-weight: bold } /* Literal.Number.Float */
-.mh { color: #005588; font-weight: bold } /* Literal.Number.Hex */
-.mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
-.mo { color: #4400EE; font-weight: bold } /* Literal.Number.Oct */
-.sb { background-color: #fff0f0 } /* Literal.String.Backtick */
-.sc { color: #0044DD } /* Literal.String.Char */
-.sd { color: #DD4422 } /* Literal.String.Doc */
-.s2 { background-color: #fff0f0 } /* Literal.String.Double */
-.se { color: #666666; font-weight: bold; background-color: #fff0f0 } /* Literal.String.Escape */
-.sh { background-color: #fff0f0 } /* Literal.String.Heredoc */
-.si { background-color: #eeeeee } /* Literal.String.Interpol */
-.sx { color: #DD2200; background-color: #fff0f0 } /* Literal.String.Other */
-.sr { color: #000000; background-color: #fff0ff } /* Literal.String.Regex */
-.s1 { background-color: #fff0f0 } /* Literal.String.Single */
-.ss { color: #AA6600 } /* Literal.String.Symbol */
-.bp { color: #007020 } /* Name.Builtin.Pseudo */
-.vc { color: #336699 } /* Name.Variable.Class */
-.vg { color: #dd7700; font-weight: bold } /* Name.Variable.Global */
-.vi { color: #3333BB } /* Name.Variable.Instance */
-.il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
diff --git a/utils/vim/syntax/llvm.vim b/utils/vim/syntax/llvm.vim
index 22d688b14864..e795c7f62133 100644
--- a/utils/vim/syntax/llvm.vim
+++ b/utils/vim/syntax/llvm.vim
@@ -1,7 +1,7 @@
 " Vim syntax file
 " Language:   llvm
 " Maintainer: The LLVM team, http://llvm.org/
-" Version:      $Revision: 294808 $
+" Version:      $Revision: 307419 $
 
 if version < 600
   syntax clear
@@ -54,6 +54,7 @@ syn keyword llvmKeyword
       \ atomic
       \ available_externally
       \ blockaddress
+      \ builtin
       \ byval
       \ c
       \ catch
@@ -105,10 +106,12 @@ syn keyword llvmKeyword
       \ naked
       \ nest
       \ noalias
+      \ nobuiltin
       \ nocapture
       \ noimplicitfloat
       \ noinline
       \ nonlazybind
+      \ nonnull
       \ norecurse
       \ noredzone
       \ noreturn
@@ -134,6 +137,7 @@ syn keyword llvmKeyword
       \ signext
       \ singlethread
       \ source_filename
+      \ speculatable
       \ spir_func
       \ spir_kernel
       \ sret