[GlobalISel] Improving InstructionSelect's performance by reducing MatchTable, mostly NFC, perf patch 1

This patch starts a series of patches that decrease time spent by
GlobalISel in its InstructionSelect pass by roughly 60% for -O0 builds
for large inputs as measured on sqlite3-amalgamation
(http://sqlite.org/download.html) targeting AArch64.

The performance improvements are achieved solely by reducing the
number of matching GIM_* opcodes executed by the MatchTable's
interpreter during the selection by approx. a factor of 30, which also
brings contribution of this particular part of the selection process
to the overall runtime of InstructionSelect pass down from approx.
60-70% to 5-7%, thus making further improvements in this particular
direction not very profitable.

The improvements described above are expected for any target that
doesn't have many complex patterns. The targets that do should
strictly benefit from the changes, but by how much exactly is hard to
estimate beforehand. It's also likely that such target WILL benefit
from further improvements to MatchTable, most likely the ones that
bring it closer to a perfect decision tree.

This commit specifically is rather large mostly NFC commit that does
necessary preparation work and refactoring, there will be a following
series of small patches introducing a specific optimization each
shortly after.

This commit specifically is expected to cause a small compile time
regression (around 2.5% of InstructionSelect pass time), which should
be fixed by the next commit of the series.

Every commit planned shares the same Phabricator Review.

Reviewers: qcolombet, dsanders, bogner, aemerson, javed.absar

Reviewed By: qcolombet

Subscribers: rovka, llvm-commits, kristof.beyls

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

llvm-svn: 332907

1 files changed, 560 insertions, 305 deletions

diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index 1237f8c4e16..c852fb36e17 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -100,6 +100,7 @@ private:
   LLT Ty;
 
 public:
+  LLTCodeGen() = default;
   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 
   std::string getCxxEnumValue() const {
@@ -401,13 +402,34 @@ public:
   /// A bitfield of RecordFlagsBits flags.
   unsigned Flags;
 
+  /// The actual run-time value, if known
+  int64_t RawValue;
+
   MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr,
-                   unsigned NumElements, unsigned Flags)
+                   unsigned NumElements, unsigned Flags,
+                   int64_t RawValue = std::numeric_limits<int64_t>::min())
       : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
-        EmitStr(EmitStr), NumElements(NumElements), Flags(Flags) {
+        EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
+        RawValue(RawValue) {
+
     assert((!LabelID_.hasValue() || LabelID != ~0u) &&
            "This value is reserved for non-labels");
   }
+  MatchTableRecord(const MatchTableRecord &Other) = default;
+  MatchTableRecord(MatchTableRecord &&Other) = default;
+
+  /// Useful if a Match Table Record gets optimized out
+  void turnIntoComment() {
+    Flags |= MTRF_Comment;
+    Flags &= ~MTRF_CommaFollows;
+    NumElements = 0;
+  }
+
+  /// For Jump Table generation purposes
+  bool operator<(const MatchTableRecord &Other) const {
+    return RawValue < Other.RawValue;
+  }
+  int64_t getRawValue() const { return RawValue; }
 
   void emit(raw_ostream &OS, bool LineBreakNextAfterThis,
             const MatchTable &Table) const;
@@ -453,11 +475,20 @@ public:
     return MatchTableRecord(None, NamedValue, 1,
                             MatchTableRecord::MTRF_CommaFollows);
   }
+  static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) {
+    return MatchTableRecord(None, NamedValue, 1,
+                            MatchTableRecord::MTRF_CommaFollows, RawValue);
+  }
   static MatchTableRecord NamedValue(StringRef Namespace,
                                      StringRef NamedValue) {
     return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
                             MatchTableRecord::MTRF_CommaFollows);
   }
+  static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue,
+                                     int64_t RawValue) {
+    return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1,
+                            MatchTableRecord::MTRF_CommaFollows, RawValue);
+  }
   static MatchTableRecord IntValue(int64_t IntValue) {
     return MatchTableRecord(None, llvm::to_string(IntValue), 1,
                             MatchTableRecord::MTRF_CommaFollows);
@@ -586,8 +617,12 @@ class RuleMatcher;
 class Matcher {
 public:
   virtual ~Matcher() = default;
+  virtual void optimize() {}
   virtual void emit(MatchTable &Table) = 0;
-  virtual std::unique_ptr<PredicateMatcher> forgetFirstCondition() = 0;
+
+  virtual bool hasFirstCondition() const = 0;
+  virtual const PredicateMatcher &getFirstCondition() const = 0;
+  virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
 };
 
 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
@@ -599,34 +634,75 @@ MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 }
 
-class GroupMatcher : public Matcher {
-  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions;
-  SmallVector<Matcher *, 8> Rules;
+class GroupMatcher final : public Matcher {
+  /// Conditions that form a common prefix of all the matchers contained.
+  SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions;
+
+  /// All the nested matchers, sharing a common prefix.
+  std::vector<Matcher *> Matchers;
+
+  /// An owning collection for any auxiliary matchers created while optimizing
+  /// nested matchers contained.
+  std::vector<std::unique_ptr<Matcher>> MatcherStorage;
 
 public:
-  void addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) {
-    Conditions.emplace_back(std::move(Predicate));
+  /// Add a matcher to the collection of nested matchers if it meets the
+  /// requirements, and return true. If it doesn't, do nothing and return false.
+  ///
+  /// Expected to preserve its argument, so it could be moved out later on.
+  bool addMatcher(Matcher &Candidate);
+
+  /// Mark the matcher as fully-built and ensure any invariants expected by both
+  /// optimize() and emit(...) methods. Generally, both sequences of calls
+  /// are expected to lead to a sensible result:
+  ///
+  /// addMatcher(...)*; finalize(); optimize(); emit(...); and
+  /// addMatcher(...)*; finalize(); emit(...);
+  ///
+  /// or generally
+  ///
+  /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }*
+  ///
+  /// Multiple calls to optimize() are expected to be handled gracefully, though
+  /// optimize() is not expected to be idempotent. Multiple calls to finalize()
+  /// aren't generally supported. emit(...) is expected to be non-mutating and
+  /// producing the exact same results upon repeated calls.
+  ///
+  /// addMatcher() calls after the finalize() call are not supported.
+  ///
+  /// finalize() and optimize() are both allowed to mutate the contained
+  /// matchers, so moving them out after finalize() is not supported.
+  void finalize();
+  void optimize() override {}
+  void emit(MatchTable &Table) override;
+
+  /// Could be used to move out the matchers added previously, unless finalize()
+  /// has been already called. If any of the matchers are moved out, the group
+  /// becomes safe to destroy, but not safe to re-use for anything else.
+  iterator_range<std::vector<Matcher *>::iterator> matchers() {
+    return make_range(Matchers.begin(), Matchers.end());
   }
-  void addRule(Matcher &Rule) { Rules.push_back(&Rule); }
-  const std::unique_ptr<PredicateMatcher> &conditions_back() const {
-    return Conditions.back();
+  size_t size() const { return Matchers.size(); }
+  bool empty() const { return Matchers.empty(); }
+
+  std::unique_ptr<PredicateMatcher> popFirstCondition() override {
+    assert(!Conditions.empty() &&
+           "Trying to pop a condition from a condition-less group");
+    std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front());
+    Conditions.erase(Conditions.begin());
+    return P;
   }
-  bool lastConditionMatches(const PredicateMatcher &Predicate) const;
-  bool conditions_empty() const { return Conditions.empty(); }
-  void clear() {
-    Conditions.clear();
-    Rules.clear();
+  const PredicateMatcher &getFirstCondition() const override {
+    assert(!Conditions.empty() &&
+           "Trying to get a condition from a condition-less group");
+    return *Conditions.front();
   }
-  void emit(MatchTable &Table) override;
+  bool hasFirstCondition() const override { return !Conditions.empty(); }
 
-  std::unique_ptr<PredicateMatcher> forgetFirstCondition() override {
-    // We shouldn't need to mess up with groups, since we
-    // should have merged everything shareable upfront.
-    // If we start to look into reordering predicates,
-    // we may want to reconsider this.
-    assert(0 && "Groups should be formed maximal for now");
-    llvm_unreachable("No need for this for now");
-  }
+private:
+  /// See if a candidate matcher could be added to this group solely by
+  /// analyzing its first condition.
+  bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
 };
 
 /// Generates code to check that a match rule matches.
@@ -640,20 +716,19 @@ protected:
   /// FIXME: This currently supports a single match position but could be
   /// extended to support multiple positions to support div/rem fusion or
   /// load-multiple instructions.
-  std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
+  using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
+  MatchersTy Matchers;
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
   ActionList Actions;
 
-  using DefinedInsnVariablesMap =
-      std::map<const InstructionMatcher *, unsigned>;
+  using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
 
-  /// A map of instruction matchers to the local variables created by
-  /// emitCaptureOpcodes().
+  /// A map of instruction matchers to the local variables
   DefinedInsnVariablesMap InsnVariableIDs;
 
-  using MutatableInsnSet = SmallPtrSet<const InstructionMatcher *, 4>;
+  using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
 
   // The set of instruction matchers that have not yet been claimed for mutation
   // by a BuildMI.
@@ -663,7 +738,7 @@ protected:
   /// the renderers.
   StringMap<OperandMatcher *> DefinedOperands;
 
-  /// ID for the next instruction variable defined with defineInsnVar()
+  /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
   unsigned NextInsnVarID;
 
   /// ID for the next output instruction allocated with allocateOutputInsnID()
@@ -673,6 +748,7 @@ protected:
   unsigned NextTempRegID;
 
   std::vector<Record *> RequiredFeatures;
+  std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
 
   ArrayRef<SMLoc> SrcLoc;
 
@@ -706,16 +782,9 @@ public:
   action_iterator insertAction(action_iterator InsertPt, Args &&... args);
 
   /// Define an instruction without emitting any code to do so.
-  /// This is used for the root of the match.
-  unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher);
-  void clearImplicitMap() {
-    NextInsnVarID = 0;
-    InsnVariableIDs.clear();
-  };
-  /// Define an instruction and emit corresponding state-machine opcodes.
-  unsigned defineInsnVar(MatchTable &Table, const InstructionMatcher &Matcher,
-                         unsigned InsnVarID, unsigned OpIdx);
-  unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const;
+  unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
+
+  unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
   DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
     return InsnVariableIDs.begin();
   }
@@ -737,7 +806,7 @@ public:
   mutatable_insns() const {
     return make_range(mutatable_insns_begin(), mutatable_insns_end());
   }
-  void reserveInsnMatcherForMutation(const InstructionMatcher *InsnMatcher) {
+  void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
     bool R = MutatableInsns.erase(InsnMatcher);
     assert(R && "Reserving a mutatable insn that isn't available");
     (void)R;
@@ -765,11 +834,10 @@ public:
     return I->second;
   }
 
-  const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
+  InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
   const OperandMatcher &getOperandMatcher(StringRef Name) const;
 
-  void emitCaptureOpcodes(MatchTable &Table);
-
+  void optimize() override;
   void emit(MatchTable &Table) override;
 
   /// Compare the priority of this object and B.
@@ -781,7 +849,11 @@ public:
   /// matcher.
   unsigned countRendererFns() const;
 
-  std::unique_ptr<PredicateMatcher> forgetFirstCondition() override;
+  std::unique_ptr<PredicateMatcher> popFirstCondition() override;
+  const PredicateMatcher &getFirstCondition() const override;
+  LLTCodeGen getFirstConditionAsRootType();
+  bool hasFirstCondition() const override;
+  unsigned getNumOperands() const;
 
   // FIXME: Remove this as soon as possible
   InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
@@ -789,6 +861,9 @@ public:
   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
   unsigned allocateTempRegID() { return NextTempRegID++; }
 
+  iterator_range<MatchersTy::iterator> insnmatchers() {
+    return make_range(Matchers.begin(), Matchers.end());
+  }
   bool insnmatchers_empty() const { return Matchers.empty(); }
   void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
 };
@@ -799,58 +874,69 @@ using action_iterator = RuleMatcher::action_iterator;
 
 template <class PredicateTy> class PredicateListMatcher {
 private:
-  typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec;
-  PredicateVec Predicates;
-
   /// Template instantiations should specialize this to return a string to use
   /// for the comment emitted when there are no predicates.
   std::string getNoPredicateComment() const;
 
+protected:
+  using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>;
+  PredicatesTy Predicates;
+
+  /// Track if the list of predicates was manipulated by one of the optimization
+  /// methods.
+  bool Optimized = false;
+
 public:
-  /// Construct a new operand predicate and add it to the matcher.
+  /// Construct a new predicate and add it to the matcher.
   template <class Kind, class... Args>
-  Optional<Kind *> addPredicate(Args&&... args) {
-    Predicates.emplace_back(
-        llvm::make_unique<Kind>(std::forward<Args>(args)...));
-    return static_cast<Kind *>(Predicates.back().get());
-  }
+  Optional<Kind *> addPredicate(Args &&... args);
 
-  typename PredicateVec::const_iterator predicates_begin() const {
+  typename PredicatesTy::iterator predicates_begin() {
     return Predicates.begin();
   }
-  typename PredicateVec::const_iterator predicates_end() const {
+  typename PredicatesTy::iterator predicates_end() {
     return Predicates.end();
   }
-  iterator_range<typename PredicateVec::const_iterator> predicates() const {
+  iterator_range<typename PredicatesTy::iterator> predicates() {
     return make_range(predicates_begin(), predicates_end());
   }
-  typename PredicateVec::size_type predicates_size() const {
+  typename PredicatesTy::size_type predicates_size() const {
     return Predicates.size();
   }
   bool predicates_empty() const { return Predicates.empty(); }
 
   std::unique_ptr<PredicateTy> predicates_pop_front() {
     std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
-    Predicates.erase(Predicates.begin());
+    Predicates.pop_front();
+    Optimized = true;
     return Front;
   }
 
+  void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) {
+    Predicates.push_front(std::move(Predicate));
+  }
+
+  void eraseNullPredicates() {
+    const auto NewEnd =
+        std::stable_partition(Predicates.begin(), Predicates.end(),
+                              std::logical_not<std::unique_ptr<PredicateTy>>());
+    if (NewEnd != Predicates.begin()) {
+      Predicates.erase(Predicates.begin(), NewEnd);
+      Optimized = true;
+    }
+  }
+
   /// Emit MatchTable opcodes that tests whether all the predicates are met.
   template <class... Args>
-  void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) const {
-    if (Predicates.empty()) {
+  void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) {
+    if (Predicates.empty() && !Optimized) {
       Table << MatchTable::Comment(getNoPredicateComment())
             << MatchTable::LineBreak;
       return;
     }
 
-    unsigned OpIdx = (*predicates_begin())->getOpIdx();
-    (void)OpIdx;
-    for (const auto &Predicate : predicates()) {
-      assert(Predicate->getOpIdx() == OpIdx &&
-             "Checks touch different operands?");
+    for (const auto &Predicate : predicates())
       Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
-    }
   }
 };
 
@@ -868,6 +954,7 @@ public:
   /// are currently not compared between each other.
   enum PredicateKind {
     IPM_Opcode,
+    IPM_NumOperands,
     IPM_ImmPredicate,
     IPM_AtomicOrderingMMO,
     IPM_MemoryLLTSize,
@@ -893,7 +980,9 @@ public:
   PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
       : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
 
+  unsigned getInsnVarID() const { return InsnVarID; }
   unsigned getOpIdx() const { return OpIdx; }
+
   virtual ~PredicateMatcher() = default;
   /// Emit MatchTable opcodes that check the predicate for the given operand.
   virtual void emitPredicateOpcodes(MatchTable &Table,
@@ -902,16 +991,23 @@ public:
   PredicateKind getKind() const { return Kind; }
 
   virtual bool isIdentical(const PredicateMatcher &B) const {
-    if (InsnVarID != 0 || OpIdx != (unsigned)~0) {
-      // We currently don't hoist the record of instruction properly.
-      // Therefore we can only work on the orig instruction (InsnVarID
-      // == 0).
-      LLVM_DEBUG(dbgs() << "Non-zero instr ID not supported yet\n");
-      return false;
-    }
     return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
            OpIdx == B.OpIdx;
   }
+
+  virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const {
+    return hasValue() && PredicateMatcher::isIdentical(B);
+  }
+
+  virtual MatchTableRecord getValue() const {
+    assert(hasValue() && "Can not get a value of a value-less predicate!");
+    llvm_unreachable("Not implemented yet");
+  }
+  virtual bool hasValue() const { return false; }
+
+  /// Report the maximum number of temporary operands needed by the predicate
+  /// matcher.
+  virtual unsigned countRendererFns() const { return 0; }
 };
 
 /// Generates code to check a predicate of an operand.
@@ -927,20 +1023,10 @@ public:
       : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
   virtual ~OperandPredicateMatcher() {}
 
-  /// Emit MatchTable opcodes to capture instructions into the MIs table.
-  ///
-  /// Only InstructionOperandMatcher needs to do anything for this method the
-  /// rest just walk the tree.
-  virtual void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {}
-
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
   virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const;
-
-  /// Report the maximum number of temporary operands needed by the predicate
-  /// matcher.
-  virtual unsigned countRendererFns() const { return 0; }
 };
 
 template <>
@@ -959,12 +1045,17 @@ public:
       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
         MatchingName(MatchingName) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_SameOperand;
   }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override;
+
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           MatchingName == cast<SameOperandMatcher>(&B)->MatchingName;
+  }
 };
 
 /// Generates code to check that an operand is a particular LLT.
@@ -973,6 +1064,16 @@ protected:
   LLTCodeGen Ty;
 
 public:
+  static std::map<LLTCodeGen, unsigned> TypeIDValues;
+
+  static void initTypeIDValuesMap() {
+    TypeIDValues.clear();
+
+    unsigned ID = 0;
+    for (const LLTCodeGen LLTy : KnownTypes)
+      TypeIDValues[LLTy] = ID++;
+  }
+
   LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty)
       : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
     KnownTypes.insert(Ty);
@@ -985,17 +1086,31 @@ public:
     return OperandPredicateMatcher::isIdentical(B) &&
            Ty == cast<LLTOperandMatcher>(&B)->Ty;
   }
+  MatchTableRecord getValue() const override {
+    const auto VI = TypeIDValues.find(Ty);
+    if (VI == TypeIDValues.end())
+      return MatchTable::NamedValue(getTy().getCxxEnumValue());
+    return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second);
+  }
+  bool hasValue() const override {
+    if (TypeIDValues.size() != KnownTypes.size())
+      initTypeIDValuesMap();
+    return TypeIDValues.count(Ty);
+  }
+
+  LLTCodeGen getTy() const { return Ty; }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI")
           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
           << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type")
-          << MatchTable::NamedValue(Ty.getCxxEnumValue())
-          << MatchTable::LineBreak;
+          << getValue() << MatchTable::LineBreak;
   }
 };
 
+std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues;
+
 /// Generates code to check that an operand is a pointer to any address space.
 ///
 /// In SelectionDAG, the types did not describe pointers or address spaces. As a
@@ -1227,7 +1342,18 @@ public:
     assert(SymbolicName.empty() && "Operand already has a symbolic name");
     SymbolicName = Name;
   }
-  unsigned getOperandIndex() const { return OpIdx; }
+
+  /// Construct a new operand predicate and add it to the matcher.
+  template <class Kind, class... Args>
+  Optional<Kind *> addPredicate(Args &&... args) {
+    if (isSameAsAnotherOperand())
+      return None;
+    Predicates.emplace_back(llvm::make_unique<Kind>(
+        getInsnVarID(), getOpIdx(), std::forward<Args>(args)...));
+    return static_cast<Kind *>(Predicates.back().get());
+  }
+
+  unsigned getOpIdx() const { return OpIdx; }
   unsigned getInsnVarID() const;
 
   std::string getOperandExpr(unsigned InsnVarID) const {
@@ -1240,23 +1366,19 @@ public:
   Error addTypeCheckPredicate(const TypeSetByHwMode &VTy,
                               bool OperandIsAPointer);
 
-  /// Emit MatchTable opcodes to capture instructions into the MIs table.
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
-    for (const auto &Predicate : predicates())
-      Predicate->emitCaptureOpcodes(Table, Rule);
-  }
-
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarID matches all the predicates and all the operands.
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
-    std::string Comment;
-    raw_string_ostream CommentOS(Comment);
-    CommentOS << "MIs[" << getInsnVarID() << "] ";
-    if (SymbolicName.empty())
-      CommentOS << "Operand " << OpIdx;
-    else
-      CommentOS << SymbolicName;
-    Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
+    if (!Optimized) {
+      std::string Comment;
+      raw_string_ostream CommentOS(Comment);
+      CommentOS << "MIs[" << getInsnVarID() << "] ";
+      if (SymbolicName.empty())
+        CommentOS << "Operand " << OpIdx;
+      else
+        CommentOS << SymbolicName;
+      Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
+    }
 
     emitPredicateListOpcodes(Table, Rule);
   }
@@ -1264,7 +1386,7 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  bool isHigherPriorityThan(const OperandMatcher &B) const {
+  bool isHigherPriorityThan(OperandMatcher &B) {
     // Operand matchers involving more predicates have higher priority.
     if (predicates_size() > B.predicates_size())
       return true;
@@ -1272,7 +1394,7 @@ public:
       return false;
 
     // This assumes that predicates are added in a consistent order.
-    for (const auto &Predicate : zip(predicates(), B.predicates())) {
+    for (auto &&Predicate : zip(predicates(), B.predicates())) {
       if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
         return true;
       if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
@@ -1284,7 +1406,7 @@ public:
 
   /// Report the maximum number of temporary operands needed by the operand
   /// matcher.
-  unsigned countRendererFns() const {
+  unsigned countRendererFns() {
     return std::accumulate(
         predicates().begin(), predicates().end(), 0,
         [](unsigned A,
@@ -1297,7 +1419,7 @@ public:
     return AllocatedTemporariesBaseID;
   }
 
-  bool isSameAsAnotherOperand() const {
+  bool isSameAsAnotherOperand() {
     for (const auto &Predicate : predicates())
       if (isa<SameOperandMatcher>(Predicate))
         return true;
@@ -1305,21 +1427,6 @@ public:
   }
 };
 
-// Specialize OperandMatcher::addPredicate() to refrain from adding redundant
-// predicates.
-template <>
-template <class Kind, class... Args>
-Optional<Kind *>
-PredicateListMatcher<OperandPredicateMatcher>::addPredicate(Args &&... args) {
-  auto *OpMatcher = static_cast<OperandMatcher *>(this);
-  if (static_cast<OperandMatcher *>(this)->isSameAsAnotherOperand())
-    return None;
-  Predicates.emplace_back(llvm::make_unique<Kind>(OpMatcher->getInsnVarID(),
-                                                  OpMatcher->getOperandIndex(),
-                                                  std::forward<Args>(args)...));
-  return static_cast<Kind *>(Predicates.back().get());
-}
-
 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
                                             bool OperandIsAPointer) {
   if (!VTy.isMachineValueType())
@@ -1363,15 +1470,11 @@ public:
   isHigherPriorityThan(const InstructionPredicateMatcher &B) const {
     return Kind < B.Kind;
   };
-
-  /// Report the maximum number of temporary operands needed by the predicate
-  /// matcher.
-  virtual unsigned countRendererFns() const { return 0; }
 };
 
 template <>
 std::string
-PredicateListMatcher<InstructionPredicateMatcher>::getNoPredicateComment() const {
+PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const {
   return "No instruction predicates";
 }
 
@@ -1380,7 +1483,17 @@ class InstructionOpcodeMatcher : public InstructionPredicateMatcher {
 protected:
   const CodeGenInstruction *I;
 
+  static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues;
+
 public:
+  static void initOpcodeValuesMap(const CodeGenTarget &Target) {
+    OpcodeValues.clear();
+
+    unsigned OpcodeValue = 0;
+    for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue())
+      OpcodeValues[I] = OpcodeValue++;
+  }
+
   InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
       : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
 
@@ -1392,12 +1505,19 @@ public:
     return InstructionPredicateMatcher::isIdentical(B) &&
            I == cast<InstructionOpcodeMatcher>(&B)->I;
   }
+  MatchTableRecord getValue() const override {
+    const auto VI = OpcodeValues.find(I);
+    if (VI != OpcodeValues.end())
+      return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(),
+                                    VI->second);
+    return MatchTable::NamedValue(I->Namespace, I->TheDef->getName());
+  }
+  bool hasValue() const override { return OpcodeValues.count(I); }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
-          << MatchTable::IntValue(InsnVarID)
-          << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
+          << MatchTable::IntValue(InsnVarID) << getValue()
           << MatchTable::LineBreak;
   }
 
@@ -1424,8 +1544,17 @@ public:
   bool isConstantInstruction() const {
     return I->TheDef->getName() == "G_CONSTANT";
   }
+
+  unsigned getNumOperands() const { return I->Operands.size(); }
+
+  StringRef getOperandType(unsigned OpIdx) const {
+    return I->Operands[OpIdx].OperandType;
+  }
 };
 
+DenseMap<const CodeGenInstruction *, unsigned>
+    InstructionOpcodeMatcher::OpcodeValues;
+
 /// Generates code to check that this instruction is a constant whose value
 /// meets an immediate predicate.
 ///
@@ -1503,10 +1632,17 @@ public:
       : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
         Order(Order), Comparator(Comparator) {}
 
-  static bool classof(const InstructionPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == IPM_AtomicOrderingMMO;
   }
 
+  bool isIdentical(const PredicateMatcher &B) const override {
+    if (!InstructionPredicateMatcher::isIdentical(B))
+      return false;
+    const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B);
+    return Order == R.Order && Comparator == R.Comparator;
+  }
+
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
     StringRef Opcode = "GIM_CheckAtomicOrdering";
@@ -1605,8 +1741,7 @@ public:
 /// Typical predicates include:
 /// * Has a specific opcode.
 /// * Has an nsw/nuw flag or doesn't.
-class InstructionMatcher
-    : public PredicateListMatcher<InstructionPredicateMatcher> {
+class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
 protected:
   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 
@@ -1627,9 +1762,17 @@ public:
     InsnVarID = Rule.implicitlyDefineInsnVar(*this);
   }
 
+  /// Construct a new instruction predicate and add it to the matcher.
+  template <class Kind, class... Args>
+  Optional<Kind *> addPredicate(Args &&... args) {
+    Predicates.emplace_back(
+        llvm::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...));
+    return static_cast<Kind *>(Predicates.back().get());
+  }
+
   RuleMatcher &getRuleMatcher() const { return Rule; }
 
-  unsigned getVarID() const { return InsnVarID; }
+  unsigned getInsnVarID() const { return InsnVarID; }
 
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
@@ -1645,7 +1788,7 @@ public:
   OperandMatcher &getOperand(unsigned OpIdx) {
     auto I = std::find_if(Operands.begin(), Operands.end(),
                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
-                            return X->getOperandIndex() == OpIdx;
+                            return X->getOpIdx() == OpIdx;
                           });
     if (I != Operands.end())
       return **I;
@@ -1668,21 +1811,18 @@ public:
 
   void pop_front() { Operands.erase(Operands.begin()); }
 
-  /// Emit MatchTable opcodes to check the shape of the match and capture
-  /// instructions into the MIs table.
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) {
+  void optimize() {}
+
+  /// Emit MatchTable opcodes that test whether the instruction named in
+  /// InsnVarName matches all the predicates and all the operands.
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) {
     Table << MatchTable::Opcode("GIM_CheckNumOperands")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Expected")
           << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
-    for (const auto &Operand : Operands)
-      Operand->emitCaptureOpcodes(Table, Rule);
-  }
 
-  /// Emit MatchTable opcodes that test whether the instruction named in
-  /// InsnVarName matches all the predicates and all the operands.
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
     emitPredicateListOpcodes(Table, Rule);
+
     for (const auto &Operand : Operands)
       Operand->emitPredicateOpcodes(Table, Rule);
   }
@@ -1690,17 +1830,19 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  bool isHigherPriorityThan(const InstructionMatcher &B) const {
+  bool isHigherPriorityThan(InstructionMatcher &B) {
     // Instruction matchers involving more operands have higher priority.
     if (Operands.size() > B.Operands.size())
       return true;
     if (Operands.size() < B.Operands.size())
       return false;
 
-    for (const auto &Predicate : zip(predicates(), B.predicates())) {
-      if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
+    for (auto &&P : zip(predicates(), B.predicates())) {
+      auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get());
+      auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get());
+      if (L->isHigherPriorityThan(*R))
         return true;
-      if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
+      if (R->isHigherPriorityThan(*L))
         return false;
     }
 
@@ -1716,13 +1858,13 @@ public:
 
   /// Report the maximum number of temporary operands needed by the instruction
   /// matcher.
-  unsigned countRendererFns() const {
-    return std::accumulate(predicates().begin(), predicates().end(), 0,
-                           [](unsigned A,
-                              const std::unique_ptr<InstructionPredicateMatcher>
-                                  &Predicate) {
-                             return A + Predicate->countRendererFns();
-                           }) +
+  unsigned countRendererFns() {
+    return std::accumulate(
+               predicates().begin(), predicates().end(), 0,
+               [](unsigned A,
+                  const std::unique_ptr<PredicateMatcher> &Predicate) {
+                 return A + Predicate->countRendererFns();
+               }) +
            std::accumulate(
                Operands.begin(), Operands.end(), 0,
                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
@@ -1730,24 +1872,30 @@ public:
                });
   }
 
-  bool isConstantInstruction() const {
-    for (const auto &P : predicates())
-      if (const InstructionOpcodeMatcher *Opcode =
-              dyn_cast<InstructionOpcodeMatcher>(P.get()))
-        return Opcode->isConstantInstruction();
-    return false;
+  InstructionOpcodeMatcher &getOpcodeMatcher() {
+    for (auto &P : predicates())
+      if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get()))
+        return *OpMatcher;
+    llvm_unreachable("Didn't find an opcode matcher");
+  }
+
+  bool isConstantInstruction() {
+    return getOpcodeMatcher().isConstantInstruction();
   }
 };
 
-template <>
-template <class Kind, class... Args>
-Optional<Kind *>
-PredicateListMatcher<InstructionPredicateMatcher>::addPredicate(
-    Args &&... args) {
-  InstructionMatcher *InstMatcher = static_cast<InstructionMatcher *>(this);
-  Predicates.emplace_back(llvm::make_unique<Kind>(InstMatcher->getVarID(),
-                                                  std::forward<Args>(args)...));
-  return static_cast<Kind *>(Predicates.back().get());
+unsigned RuleMatcher::getNumOperands() const {
+  return Matchers.front()->getNumOperands();
+}
+
+LLTCodeGen RuleMatcher::getFirstConditionAsRootType() {
+  InstructionMatcher &InsnMatcher = *Matchers.front();
+  if (!InsnMatcher.predicates_empty())
+    if (const auto *TM =
+            dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin()))
+      if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0)
+        return TM->getTy();
+  return {};
 }
 
 /// Generates code to check that the operand is a register defined by an
@@ -1775,17 +1923,20 @@ public:
 
   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    unsigned InsnID =
-        Rule.defineInsnVar(Table, *InsnMatcher, InsnVarID, getOpIdx());
-    (void)InsnID;
-    assert(InsnMatcher->getVarID() == InsnID &&
-           "Mismatch between build and emit");
-    InsnMatcher->emitCaptureOpcodes(Table, Rule);
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
+    const unsigned NewInsnVarID = InsnMatcher->getInsnVarID();
+    Table << MatchTable::Opcode("GIM_RecordInsn")
+          << MatchTable::Comment("DefineMI")
+          << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI")
+          << MatchTable::IntValue(getInsnVarID())
+          << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx())
+          << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
+          << MatchTable::LineBreak;
   }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
+    emitCaptureOpcodes(Table, Rule);
     InsnMatcher->emitPredicateOpcodes(Table, Rule);
   }
 
@@ -1859,7 +2010,7 @@ public:
     Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID")
           << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
-          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::IntValue(Operand.getOpIdx())
           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
@@ -1895,7 +2046,7 @@ public:
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
           << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
-          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::IntValue(Operand.getOpIdx())
           << MatchTable::NamedValue(
                  (ZeroRegisterDef->getValue("Namespace")
                       ? ZeroRegisterDef->getValueAsString("Namespace")
@@ -1926,7 +2077,7 @@ public:
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
                                        : "GIR_CopyConstantAsUImm")
@@ -1957,7 +2108,7 @@ public:
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
@@ -1997,7 +2148,7 @@ public:
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
           << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
-          << MatchTable::IntValue(Operand.getOperandIndex())
+          << MatchTable::IntValue(Operand.getOpIdx())
           << MatchTable::Comment("SubRegIdx")
           << MatchTable::IntValue(SubReg->EnumValue)
           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
@@ -2146,8 +2297,7 @@ public:
   }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    const InstructionMatcher &InsnMatcher =
-        Rule.getInstructionMatcher(SymbolicName);
+    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode("GIR_CustomRenderer")
           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
@@ -2193,7 +2343,7 @@ class BuildMIAction : public MatchAction {
 private:
   unsigned InsnID;
   const CodeGenInstruction *I;
-  const InstructionMatcher *Matched;
+  InstructionMatcher *Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 
   /// True if the instruction can be built solely by mutating the opcode.
@@ -2208,7 +2358,7 @@ private:
       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
         if (Insn != &OM.getInstructionMatcher() ||
-            OM.getOperandIndex() != Renderer.index())
+            OM.getOpIdx() != Renderer.index())
           return false;
       } else
         return false;
@@ -2225,7 +2375,7 @@ public:
   const CodeGenInstruction *getCGI() const { return I; }
 
   void chooseInsnToMutate(RuleMatcher &Rule) {
-    for (const auto *MutateCandidate : Rule.mutatable_insns()) {
+    for (auto *MutateCandidate : Rule.mutatable_insns()) {
       if (canMutate(Rule, MutateCandidate)) {
         // Take the first one we're offered that we're able to mutate.
         Rule.reserveInsnMatcherForMutation(MutateCandidate);
@@ -2417,27 +2567,13 @@ action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
                          llvm::make_unique<Kind>(std::forward<Args>(args)...));
 }
 
-unsigned
-RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
+unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
   unsigned NewInsnVarID = NextInsnVarID++;
   InsnVariableIDs[&Matcher] = NewInsnVarID;
   return NewInsnVarID;
 }
 
-unsigned RuleMatcher::defineInsnVar(MatchTable &Table,
-                                    const InstructionMatcher &Matcher,
-                                    unsigned InsnID, unsigned OpIdx) {
-  unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher);
-  Table << MatchTable::Opcode("GIM_RecordInsn")
-        << MatchTable::Comment("DefineMI") << MatchTable::IntValue(NewInsnVarID)
-        << MatchTable::Comment("MI") << MatchTable::IntValue(InsnID)
-        << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx)
-        << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]")
-        << MatchTable::LineBreak;
-  return NewInsnVarID;
-}
-
-unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const {
+unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
   const auto &I = InsnVariableIDs.find(&InsnMatcher);
   if (I != InsnVariableIDs.end())
     return I->second;
@@ -2455,7 +2591,7 @@ void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
 }
 
-const InstructionMatcher &
+InstructionMatcher &
 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
   for (const auto &I : InsnVariableIDs)
     if (I.first->getSymbolicName() == SymbolicName)
@@ -2474,25 +2610,10 @@ RuleMatcher::getOperandMatcher(StringRef Name) const {
   return *I->second;
 }
 
-/// Emit MatchTable opcodes to check the shape of the match and capture
-/// instructions into local variables.
-void RuleMatcher::emitCaptureOpcodes(MatchTable &Table) {
-  assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
-  unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
-  (void)InsnVarID;
-  assert(Matchers.front()->getVarID() == InsnVarID &&
-         "IDs differ between build and emit");
-  Matchers.front()->emitCaptureOpcodes(Table, *this);
-}
-
 void RuleMatcher::emit(MatchTable &Table) {
   if (Matchers.empty())
     llvm_unreachable("Unexpected empty matcher!");
 
-  // Reset the ID generation so that the emitted IDs match the ones
-  // we set while building the InstructionMatcher and such.
-  clearImplicitMap();
-
   // The representation supports rules that require multiple roots such as:
   //    %ptr(p0) = ...
   //    %elt0(s32) = G_LOAD %ptr
@@ -2506,7 +2627,9 @@ void RuleMatcher::emit(MatchTable &Table) {
 
   unsigned LabelID = Table.allocateLabelID();
   Table << MatchTable::Opcode("GIM_Try", +1)
-        << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(LabelID)
+        << MatchTable::Comment("On fail goto")
+        << MatchTable::JumpTarget(LabelID)
+        << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str())
         << MatchTable::LineBreak;
 
   if (!RequiredFeatures.empty()) {
@@ -2515,8 +2638,6 @@ void RuleMatcher::emit(MatchTable &Table) {
           << MatchTable::LineBreak;
   }
 
-  emitCaptureOpcodes(Table);
-
   Matchers.front()->emitPredicateOpcodes(Table, *this);
 
   // We must also check if it's safe to fold the matched instructions.
@@ -2576,12 +2697,18 @@ void RuleMatcher::emit(MatchTable &Table) {
     }
   }
 
+  for (const auto &PM : EpilogueMatchers)
+    PM->emitPredicateOpcodes(Table, *this);
+
   for (const auto &MA : Actions)
     MA->emitActionOpcodes(Table, *this);
 
   if (Table.isWithCoverage())
     Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID)
           << MatchTable::LineBreak;
+  else
+    Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str())
+          << MatchTable::LineBreak;
 
   Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
         << MatchTable::Label(LabelID);
@@ -2649,7 +2776,7 @@ void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
                                               RuleMatcher &Rule) const {
   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
-  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getVarID());
+  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID());
 
   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
@@ -2657,7 +2784,7 @@ void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
         << MatchTable::Comment("OtherMI")
         << MatchTable::IntValue(OtherInsnVarID)
         << MatchTable::Comment("OtherOpIdx")
-        << MatchTable::IntValue(OtherOM.getOperandIndex())
+        << MatchTable::IntValue(OtherOM.getOpIdx())
         << MatchTable::LineBreak;
 }
 
@@ -2700,6 +2827,8 @@ private:
   // Rule coverage information.
   Optional<CodeGenCoverage> RuleCoverage;
 
+  void gatherOpcodeValues();
+  void gatherTypeIDValues();
   void gatherNodeEquivs();
   Record *findNodeEquiv(Record *N) const;
   const CodeGenInstruction *getEquivNode(Record &Equiv,
@@ -2750,16 +2879,15 @@ private:
 
   void declareSubtargetFeature(Record *Predicate);
 
+  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
+                             bool WithCoverage);
+
+public:
   /// Takes a sequence of \p Rules and group them based on the predicates
-  /// they share. \p StorageGroupMatcher is used as a memory container
+  /// they share. \p MatcherStorage is used as a memory container
   /// for the group that are created as part of this process.
-  /// The optimization process does not change the relative order of
-  /// the rules. In particular, we don't try to share predicates if
-  /// that means reordering the rules (e.g., we won't group R1 and R3
-  /// in the following example as it would imply reordering R2 and R3
-  /// => R1 p1, R2 p2, R3 p1).
   ///
-  /// What this optimization does looks like:
+  /// What this optimization does looks like if GroupT = GroupMatcher:
   /// Output without optimization:
   /// \verbatim
   /// # R1
@@ -2780,14 +2908,20 @@ private:
   ///  # R2
   ///   # predicate C
   /// \endverbatim
-  std::vector<Matcher *> optimizeRules(
+  template <class GroupT>
+  static std::vector<Matcher *> optimizeRules(
       ArrayRef<Matcher *> Rules,
-      std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
-
-  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
-                             bool WithCoverage);
+      std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
 };
 
+void GlobalISelEmitter::gatherOpcodeValues() {
+  InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
+}
+
+void GlobalISelEmitter::gatherTypeIDValues() {
+  LLTOperandMatcher::initTypeIDValuesMap();
+}
+
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
   for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
@@ -3522,7 +3656,6 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) {
   M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) +
                                   "  =>  " +
                                   llvm::to_string(*P.getDstPattern()));
-  M.addAction<DebugCommentAction>("Rule ID " + llvm::to_string(M.getRuleID()));
 
   if (auto Error = importRulePredicates(M, P.getPredicates()))
     return std::move(Error);
@@ -3778,35 +3911,53 @@ void GlobalISelEmitter::emitImmPredicates(
      << "}\n";
 }
 
+template <class GroupT>
 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
     ArrayRef<Matcher *> Rules,
-    std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) {
+    std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
+
   std::vector<Matcher *> OptRules;
-  // Start with a stupid grouping for now.
-  std::unique_ptr<GroupMatcher> CurrentGroup = make_unique<GroupMatcher>();
-  assert(CurrentGroup->conditions_empty());
-  unsigned NbGroup = 0;
-  for (Matcher *Rule : Rules) {
-    std::unique_ptr<PredicateMatcher> Predicate = Rule->forgetFirstCondition();
-    if (!CurrentGroup->conditions_empty() &&
-        !CurrentGroup->lastConditionMatches(*Predicate)) {
-      // Start a new group.
-      ++NbGroup;
+  std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>();
+  assert(CurrentGroup->empty() && "Newly created group isn't empty!");
+  unsigned NumGroups = 0;
+
+  auto ProcessCurrentGroup = [&]() {
+    if (CurrentGroup->empty())
+      // An empty group is good to be reused:
+      return;
+
+    // If the group isn't large enough to provide any benefit, move all the
+    // added rules out of it and make sure to re-create the group to properly
+    // re-initialize it:
+    if (CurrentGroup->size() < 2)
+      for (Matcher *M : CurrentGroup->matchers())
+        OptRules.push_back(M);
+    else {
+      CurrentGroup->finalize();
       OptRules.push_back(CurrentGroup.get());
-      StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
-      CurrentGroup = make_unique<GroupMatcher>();
-      assert(CurrentGroup->conditions_empty());
+      MatcherStorage.emplace_back(std::move(CurrentGroup));
+      ++NumGroups;
     }
-    if (CurrentGroup->conditions_empty())
-      CurrentGroup->addCondition(std::move(Predicate));
-    CurrentGroup->addRule(*Rule);
-  }
-  if (!CurrentGroup->conditions_empty()) {
-    ++NbGroup;
-    OptRules.push_back(CurrentGroup.get());
-    StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+    CurrentGroup = make_unique<GroupT>();
+  };
+  for (Matcher *Rule : Rules) {
+    // Greedily add as many matchers as possible to the current group:
+    if (CurrentGroup->addMatcher(*Rule))
+      continue;
+
+    ProcessCurrentGroup();
+    assert(CurrentGroup->empty() && "A group wasn't properly re-initialized");
+
+    // Try to add the pending matcher to a newly created empty group:
+    if (!CurrentGroup->addMatcher(*Rule))
+      // If we couldn't add the matcher to an empty group, that group type
+      // doesn't support that kind of matchers at all, so just skip it:
+      OptRules.push_back(Rule);
   }
-  LLVM_DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
+  ProcessCurrentGroup();
+
+  DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
+  assert(CurrentGroup->empty() && "The last group wasn't properly processed");
   return OptRules;
 }
 
@@ -3820,9 +3971,15 @@ GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
   if (!Optimize)
     return MatchTable::buildTable(InputRules, WithCoverage);
 
-  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
+  for (Matcher *Rule : InputRules)
+    Rule->optimize();
+
+  std::vector<std::unique_ptr<Matcher>> MatcherStorage;
   std::vector<Matcher *> OptRules =
-      optimizeRules(InputRules, StorageGroupMatcher);
+      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
+
+  for (Matcher *Rule : OptRules)
+    Rule->optimize();
 
   return MatchTable::buildTable(OptRules, WithCoverage);
 }
@@ -3842,6 +3999,11 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
     }
   }
 
+  // Track the run-time opcode values
+  gatherOpcodeValues();
+  // Track the run-time LLT ID values
+  gatherTypeIDValues();
+
   // Track the GINodeEquiv definitions.
   gatherNodeEquivs();
 
@@ -3930,8 +4092,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
      << ", State(" << MaxTemporaries << "),\n"
-     << "ISelInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns, "
-        "CustomRenderers})\n"
+     << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
+     << ", ComplexPredicateFns, CustomRenderers)\n"
      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
@@ -3973,7 +4135,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
     TypeObject.emitCxxEnumValue(OS);
     OS << ",\n";
   }
-  OS << "};\n"
+  OS << "};\n";
+  OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
      << "const static LLT TypeObjects[] = {\n";
   for (const auto &TypeObject : TypeObjects) {
     OS << "  ";
@@ -4152,62 +4315,154 @@ void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
 }
 
-std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() {
+void RuleMatcher::optimize() {
+  for (auto &Item : InsnVariableIDs) {
+    InstructionMatcher &InsnMatcher = *Item.first;
+    for (auto &OM : InsnMatcher.operands()) {
+      // Register Banks checks rarely fail, but often crash as targets usually
+      // provide only partially defined RegisterBankInfo::getRegBankFromRegClass
+      // method. Often the problem is hidden as non-optimized MatchTable checks
+      // banks rather late, most notably after checking target / function /
+      // module features and a few opcodes. That makes these checks a)
+      // beneficial to delay until the very end (we don't want to perform a lot
+      // of checks that all pass and then fail at the very end) b) not safe to
+      // have as early checks.
+      for (auto &OP : OM->predicates())
+        if (isa<RegisterBankOperandMatcher>(OP) ||
+            isa<ComplexPatternOperandMatcher>(OP))
+          EpilogueMatchers.emplace_back(std::move(OP));
+      OM->eraseNullPredicates();
+    }
+    InsnMatcher.optimize();
+  }
+  llvm::sort(
+      EpilogueMatchers.begin(), EpilogueMatchers.end(),
+      [](const std::unique_ptr<PredicateMatcher> &L,
+         const std::unique_ptr<PredicateMatcher> &R) {
+        return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) <
+               std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx());
+      });
+}
+
+bool RuleMatcher::hasFirstCondition() const {
+  if (insnmatchers_empty())
+    return false;
+  InstructionMatcher &Matcher = insnmatchers_front();
+  if (!Matcher.predicates_empty())
+    return true;
+  for (auto &OM : Matcher.operands())
+    for (auto &OP : OM->predicates())
+      if (!isa<InstructionOperandMatcher>(OP))
+        return true;
+  return false;
+}
+
+const PredicateMatcher &RuleMatcher::getFirstCondition() const {
   assert(!insnmatchers_empty() &&
-         "Trying to forget something that does not exist");
+         "Trying to get a condition from an empty RuleMatcher");
 
   InstructionMatcher &Matcher = insnmatchers_front();
-  std::unique_ptr<PredicateMatcher> Condition;
   if (!Matcher.predicates_empty())
-    Condition = Matcher.predicates_pop_front();
-  if (!Condition) {
-    // If there is no more predicate on the instruction itself, look at its
-    // operands.
-    assert(!Matcher.operands_empty() &&
-           "Empty instruction should have been discarded");
-    OperandMatcher &OpMatcher = **Matcher.operands_begin();
-    assert(!OpMatcher.predicates_empty() && "no operand constraint");
-    Condition = OpMatcher.predicates_pop_front();
-    // If this operand is free of constraints, rip it off.
-    if (OpMatcher.predicates_empty())
-      Matcher.pop_front();
-  }
-  // Rip the instruction off when it is empty.
-  if (Matcher.operands_empty() && Matcher.predicates_empty())
-    insnmatchers_pop_front();
-  return Condition;
+    return **Matcher.predicates_begin();
+  // If there is no more predicate on the instruction itself, look at its
+  // operands.
+  for (auto &OM : Matcher.operands())
+    for (auto &OP : OM->predicates())
+      if (!isa<InstructionOperandMatcher>(OP))
+        return *OP;
+
+  llvm_unreachable("Trying to get a condition from an InstructionMatcher with "
+                   "no conditions");
 }
 
-bool GroupMatcher::lastConditionMatches(
+std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() {
+  assert(!insnmatchers_empty() &&
+         "Trying to pop a condition from an empty RuleMatcher");
+
+  InstructionMatcher &Matcher = insnmatchers_front();
+  if (!Matcher.predicates_empty())
+    return Matcher.predicates_pop_front();
+  // If there is no more predicate on the instruction itself, look at its
+  // operands.
+  for (auto &OM : Matcher.operands())
+    for (auto &OP : OM->predicates())
+      if (!isa<InstructionOperandMatcher>(OP)) {
+        auto Result = std::move(OP);
+        OM->eraseNullPredicates();
+        return Result;
+      }
+
+  llvm_unreachable("Trying to pop a condition from an InstructionMatcher with "
+                   "no conditions");
+}
+
+bool GroupMatcher::candidateConditionMatches(
     const PredicateMatcher &Predicate) const {
-  const auto &LastCondition = conditions_back();
-  return Predicate.isIdentical(*LastCondition);
+
+  if (empty()) {
+    // Sharing predicates for nested instructions is not supported yet as we
+    // currently don't hoist the GIM_RecordInsn's properly, therefore we can
+    // only work on the original root instruction (InsnVarID == 0):
+    if (Predicate.getInsnVarID() != 0)
+      return false;
+    // ... otherwise an empty group can handle any predicate with no specific
+    // requirements:
+    return true;
+  }
+
+  const Matcher &Representative = **Matchers.begin();
+  const auto &RepresentativeCondition = Representative.getFirstCondition();
+  // ... if not empty, the group can only accomodate matchers with the exact
+  // same first condition:
+  return Predicate.isIdentical(RepresentativeCondition);
+}
+
+bool GroupMatcher::addMatcher(Matcher &Candidate) {
+  if (!Candidate.hasFirstCondition())
+    return false;
+
+  const PredicateMatcher &Predicate = Candidate.getFirstCondition();
+  if (!candidateConditionMatches(Predicate))
+    return false;
+
+  Matchers.push_back(&Candidate);
+  return true;
+}
+
+void GroupMatcher::finalize() {
+  assert(Conditions.empty() && "Already finalized?");
+  if (empty())
+    return;
+
+  Matcher &FirstRule = **Matchers.begin();
+
+  Conditions.push_back(FirstRule.popFirstCondition());
+  for (unsigned I = 1, E = Matchers.size(); I < E; ++I)
+    Matchers[I]->popFirstCondition();
 }
 
 void GroupMatcher::emit(MatchTable &Table) {
-  unsigned LabelID = Table.allocateLabelID();
-  if (!conditions_empty()) {
+  unsigned LabelID = ~0U;
+  if (!Conditions.empty()) {
+    LabelID = Table.allocateLabelID();
     Table << MatchTable::Opcode("GIM_Try", +1)
           << MatchTable::Comment("On fail goto")
           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
-    for (auto &Condition : Conditions)
-      Condition->emitPredicateOpcodes(
-          Table, *static_cast<RuleMatcher *>(*Rules.begin()));
   }
-  // Emit the conditions.
-  // Then checks apply the rules.
-  for (const auto &Rule : Rules)
-    Rule->emit(Table);
-  // If we don't succeeded for that block, that means we are not going to select
-  // this instruction.
-  if (!conditions_empty()) {
-    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
-    Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+  for (auto &Condition : Conditions)
+    Condition->emitPredicateOpcodes(
+        Table, *static_cast<RuleMatcher *>(*Matchers.begin()));
+
+  for (const auto &M : Matchers)
+    M->emit(Table);
+
+  // Exit the group
+  if (!Conditions.empty())
+    Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak
           << MatchTable::Label(LabelID);
-  }
 }
 
-unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); }
+unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
 
 } // end anonymous namespace